FPGA開発日記

FPGAというより、コンピュータアーキテクチャかもね! カテゴリ別記事インデックス https://msyksphinz.github.io/github_pages

CPUの新たな脆弱性 SPOILERの論文を読む

arxiv.org

GIGAZINEでも紹介された新たなCPUの脆弱性の論文"SPOILER"が発表された。GIGAZINEがこのような記事を公開するのは珍しいなと思いつつ、面白そうなので読んでみることにした。

ちなみに、筆者は例によってセキュリティの専門家ではないし、CPUアーキテクチャにしてもデスクトップクラスの本格的なものは設計経験がないので、いまいち本文から読み取れない部分があったりとか、間違っている部分があるかもしれない。


この攻撃手法も、CPUの高速化を達成するための様々な機構を悪用する手法となっている。

SPOILERが対象とするのは、ストア命令の内容をロード命令でフォワードするためのMOB(Memory Order Buffer)の機構だ。例えば以下のようなコードを書いた場合、

sw a0, 0(sp)
lw a1, 0(sp)

ストア命令は、投機実行をしてしまうとメモリの中身を誤って書き換えてしまうため投機実行はできない。しかし、ロード命令は投機実行をしてもレジスタの中身を復帰すればよいから投機実行できる。そこで、ストア命令の完了を待たずして、次のロード命令を実行するということが可能になる。

しかしこの例で示すように、ストア命令が完了する前にロード命令が実行されてしまい愚直にメモリから値を読んでくると、まだストア処理が完了していないためswが格納するデータを読み込むことができない。 そこで、ストア命令のデータが格納されている「ストアバッファ」の中身を確認して、ロード命令とストア命令が同じアドレスを参照すればそのデータをそのままロード命令にフォワードする「ストアフォワーディング」という技法が使われる。

f:id:msyksphinz:20190310170018p:plain
本論文より引用。Figure 1. MOBの構成

ところがこれは物理アドレスしか用いない場合は容易に実現できるが、仮想アドレスと物理アドレスが混在している場合はそうはいかない。アドレスが同じだと思っていても、物理アドレスが異なる場合、さらに仮想アドレスが異なっていても物理アドレスが同一である場合もある。ここで、LSUでメモリアクセスを発行していない場合にはまだ仮想アドレスで取り扱われており、物理アドレスに変換されていないことが問題となる。この場合LSUの中でどのようにストアフォワーディングを行うのだろうか。

ここで、一般的に以下のような手順を取ると考える。

  1. ルーズネット : アドレスの下位(ページオフセット)のみ比較する。ページオフセットは仮想アドレスと物理アドレスで異なることはないので、ここでアドレスが異なっていればフォワーディングする必要はない。もし一致している場合は、上位アドレスも比較しなければならないので次に進む。
  2. ファインネット : 仮想アドレスの上位ビットと、物理アドレスのタグビットを比較する。これでヒットすると、ストアフォワーディングを行う必要性が高まるが、まだ確定ではない。このステージでアドレスがヒットする場合、ロード命令の実行を止めるか、ストアフォワーディングを行う。そうでない場合は、最後のステージに進む。
  3. 物理アドレスマッチング : すべての物理アドレスのマッチングを行う。このステージで、ストアフォワーディングを行う必要があるかどうかが最終的に判定される。

この場合、物理アドレスが計算されるためにはTLBまで進んでアドレス計算を行う必要があるため、フォワーディングの可否が最終的に判別されるのはロード命令のコミットステージまで先延ばしにされてしまう。つまりここも投機的に実行されているわけだ。最終的な確認のために、変換されたアドレスを物理アドレスバッファ(PAB)に保管している。

この投機的実行を間違えるとどうなるか。ロード命令がストアフォワーディングの投機的実行を間違えたため、当然パイプラインはフラッシュされロード命令を再実行するということになる。これには、結構なサイクル数を消費してしまう。この事象を観測するという訳だ。

Spoiler Attackの実験

Spoiler Attackの実験を行うために、以下のようなアルゴリズムを使ってキャッシュの動きの調査を行っている。

f:id:msyksphinz:20190310170127p:plain
本論文より引用。アルゴリズム1. SPOILER Attackの基本アルゴリズム

あまりきちんと理解しているわけではないが、キャッシュのページ毎にストア命令を発行し、その直後にx番目のページに対するロード命令を実行している。先ほどの、アドレス変換によるアドレス衝突のアルゴリズムに則るならば、

  1. ルーズネット : 常にページの先頭にアクセスしているので、アドレスが一致する。したがってファインネットに移動する。
  2. ファインネット : 物理アドレスのタグビットと仮想アドレスの上位アドレスを比較する。

このときにこのプログラムを実行するのに必要なサイクル数と、発生したイベントをイベントカウンタから取得する。その結果が以下のグラフとなっている。

f:id:msyksphinz:20190310170254p:plain
本論文より引用。図.4. 黒色のグラフでは、ページ番号に応じてレイテンシが大きくなる現象が観測で来ている。HPCイベントでは、`Cycle_Activity:Stalls_Ldm_Pending`(青色のグラフ) と `Ld_Blocks_Partial:Address_Alias`(赤色のグラフ)で反応が見られる。

つまり、ページアクセスに対するエイリアシングが発生しているかどうかは、上記の2つのイベントカウンタを観測すれば計測できるということが分かる。このグラフを見てわかることは、256ページ毎にサイクル数が変動しているということ。256ページというのは256x4kByte=1MBということになる。1MB毎にエイリアシングが生じているということが分かる。イベントにおける:

  • Cycle_Activity:Stalls_Ldm_Pending : ロード命令において、ストールにより命令が実行されなかったサイクル数を記録する。
  • Ld_Blocks_Partial:Address_Alias : ルーズネットが4Kバイトのエイリアスを解決した際に、偽の依存性の数を示す。

上記のグラフをもう一度見直すと、1MBのエイリアシングによりロード命令が遅延すると、当然のごとくCycle_Activity:Stalls_Ldm_Pendingが増加していく。一方で、Ld_Blocks_Partial:Address_Aliasが減少していくのは、xxx

もう少し詳細に見ていくと、1MBのエイリアシングが発生するアドレスにストアが発生した場合は、サイクル数が大きくなりピークに達する(図6)。そこから先の次のページにアクセスする場合は少しずつサイクル数が減少していき、ステップ上にサイクル数は減っていく。これはIntelの特許に記載されているアルゴリズム"Carry chain algorithm"と一致する。ちなみに、このような現象はARMプロセッサやAMDのプロセッサでは発生しない。

f:id:msyksphinz:20190310170324p:plain
本論文より引用。いくつかのページに対して、サイクル数の変化がみられる。
図7では、エイリアシングによりメモリアクセスに必要なサイクル数のヒストグラムを示している。
f:id:msyksphinz:20190310170423p:plain
本論文より引用。ストア命令とロード命令のアドレスによりサイクル数が異なる現象をヒストグラムで表現する。
  • ストア命令とロード命令の間にエイリアシングが発生しない(つまり、オフセットアドレスからずれたストア命令とロード命令の関係) : 30サイクルでロード命令が完了する。
  • ここで面白いのが、同一ページオフセットを持っているが実際のアドレスが異なるストア命令が複数存在し、さらにオフセットと全く異なるロード命令を発行すると、ロード命令には100サイクルが消費される。つまり、直接ロード・ストア命令で4kエイリアシングが発生しなくても、ロード命令のアクセスサイクル数は減少する。
  • 4Kバイトのエイリアシングが発生した場合(つまり同一オフセットでのロード命令とメモリ命令が存在した場合)、ロード命令のアクセスサイクルは120サイクルに増加する。
  • さらに1MBのエイリアシングが発生する場合は、ロード命令は1200サイクル以上消費される。

Javascriptを用いたSPOILER攻撃

Javascriptに移植したSPOILERのコードを実行すると、ネイティブで実行したものと似たような傾向が得られた。つまり、これはブラウザ経由からSPOILERの攻撃も有効であるということを意味する。ネイティブと比較して多少ノイズが混じっているが、明らかな特徴を検出できることはネイティブの実装と同一である。

f:id:msyksphinz:20190310170526p:plain
本論文より引用。JavascriptでSPOILERを実装し実行した結果。ネイティブ版とほぼ同様の結果が得られる。

RowHammerにSPOILERを活用する

RowHammer攻撃というのは、DRAMに対して実行する攻撃手法で、メモリセルの電荷が漏れる事象を活用し、メモリアドレスで指定した場所以外の隣接したアドレスのデータを取得する攻撃手法だ。例えば取得したいアドレスがあるとしてそのデータセルの隣接するアドレスに対して何度もアクセスを繰り返すと、攻撃対象のデータが漏れ出してデータを取得できる可能性がある。

この攻撃を成立させるためには、攻撃対象となるセルの隣接するバンクを取得しなければならないのだが、これにSPOILERを使用する。SPOILERを使用すれば、攻撃対象の物理アドレスの1MB協会までのアドレスを知ることができるため、これにより対象となるバンクを取得し、RowHammerの攻撃をより効率化することができる。

回避策

今のところ有効な回避策はなく、ストア命令がバッファに入っている間にロード命令を投機的に実行することを禁止にすると性能に重大な問題を引き起こしてしまう。ソフトウェア的にはストアとロードの間にフェンスを入れることが有効ではあるが、それをすべてのソフトウェアに適用させることはできない。

ハードウェア的にも性能低下を避けるためには、投機的実行の手法を考え直す必要がある。性能を低下させずにこの問題を解決するためには、何らかの方法を考える必要があるものと思われる。