Windows で Spectre する

はじめに

前回の記事で、Meltdown/Spectre の概要と、Meltdown の詳細について説明しました。今回は Spectre を Windows で再現する方法について説明します。本記事では前回の記事で使った単語などを説明せずに使っている部分があるため、前回の記事に目を通していただくことをおすすめします。手抜きで申し訳ないです。

Windows で Meltdown する - Qiita
https://qiita.com/msmania/items/794e3dbe82db86c4c4e6

全ての PoC は Meltdown と同じリポジトリにあります。

msmania/microarchitectural-attack: Meltdown/Spectre PoC for Windows
https://github.com/msmania/microarchitectural-attack

Spectre とは

Spectre には、大きく分けて 2 つのバリアントが存在します。GPZ のブログではそれぞれ Variant 1: bounds check bypass (CVE-2017-5753)、 Variant 2: branch target injection (CVE-2017-5715) と呼ばれています。Spectre 論文 ではそれぞれ順に "4. Exploiting Conditional Branch Misprediction"、"5. Poisoning Indirect Branches" と呼ばれています。どちらのバリアントも Meltdown 論文で言うところの厳密な意味での Speculative execution を利用するという点では共通ですが、Speculative Execution を発動させるコードが異なります。さらに Variant 2 は、プロセスの壁を越えてデータを読み取れることが特徴です。一方 Variant 1 の主な目的は、JavaScript など制御された環境からプロセス内の任意のアドレスのデータをロードすることです。

端的に言えば、Meltdown で例外を発生させるコードだった部分が、条件分岐 (Conditional branch; if 文など) に置き換えたのが Variant 1、Indirect branch 命令 (関数ポインターの呼び出しや VTable を利用した仮想関数の呼び出しなど、メモリにあるアドレスをロードしてそこにジャンプする命令) に置き換えたのが Variant 2 です。

根拠となる CPU の動作、及び Exploit を作る過程には大きな違いがあります。Meltdown では、メモリへのアクセスが例外を発生させるかどうかをチェックする処理と、そのメモリ アドレスからデータをロードしてくる処理を同時に実行できることを基にした out-of-order execution を利用していました。Spectre では、CPU が実行フローを分岐させる際に過去の分岐の実績を micro-architecture レベルで保存していて、その実績に基づいて投機的実行が行われることを利用し、攻撃者がその実績をトレーニング実行によって作り出して投機的実行を誘導します。このトレーニングという作業が Spectre に特有の過程です。

Spectre Variant 1: Bounds Check Bypass (CVE-2017-5753)

動作原理

Bounds Check Bypass はシンプルで分かりやすく、再現を作るのも簡単です。論文のセクション 4. に Listing 1 として書かれているコードが Spectre Variant 1 方程式です。

if (x < array1_size)
  y = array2[array1[x] * 256];

Spectre 以前では、これは無害なコードのはずでした。しかし micro-architectural なレイヤーではデータが漏れ得るコードです。というのも、x < array1_size の実際の結果が false であったとしても、それまでの実績として x < array1_size が true になっているパターンが多ければ、実際に x < array1_size の結果が出る前に if ブロック内の処理が投機的に実行されるからです。トレーニングとして、条件が true になるように調整した x と array1_size の組み合わせ (例えば (x, array1_size) = (0, 1) のような組み合わせ) で if 文を何回か実行しておくと、その後で条件が false になるような x と array1_size の組み合わせが来ても、if の中身が投機的に実行される様子を観察できます。ただし、投機的実行をするための時間的猶予が必要なので、x と array1_size がレジスターに格納されているようなパターンは駄目で、どちらかがメモリ上に保存されて if 文のときにロードされるような工夫が必要です。

if 文の中の array2[array1[x] * 256] が、後の Flush+Reload で検出可能な micro-architectural な変更を引き起こすためのコードです。盗みたい秘密のデータは array1[x] です。array1 が N バイト型の配列だった場合、array1[x] は array1 + x * N で計算されるアドレスの値をロードします。そこで任意のアドレス z について x = (z - array1) / N となる x を選ぶことで、アドレス z の値を読みだすコードを投機的に実行させることができます。例えば array1_size の値を 1 で固定しておけば、x = 0 を渡すことがトレーニング実行になるのでそれを何度か繰り返し、続いて (z - array1) / N を渡すと、z をロードする命令が投機的実行が誘発される本番実行になります。

得られた array1[x] に 256 を掛けて array2 の配列のインデックスとして使用しているのは Meltdown と同じ意図で、アドレス z のデータに応じて少し離れた領域をキャッシュさせるための工夫です。Meltdown では 256 の代わりに 4096 が使われていました。この値はキャッシュ ラインのサイズより大きければ問題ありません。

JavaScript 実装

Bounds Check Bypass を C/C++ やアセンブリのようなネイティブ言語で書くことは、現実的な攻撃という観点では意味がありません。ネイティブ言語の Remote Code Execution が可能であれば、 *reinterpret_cast<uint8_t*>(z) などのように任意のアドレスの値をロードすることは簡単だからです。この Variant 1 は、JavaScript などのある程度限定された環境でも実行可能なところに意味があります。論文では Listing 2, 3 に Chrome の V8 を使った JavaScript での実装例が示されています。

JavaScript の配列に対して simpleByteArray[index] というコードを実行できる状況があり、さらに 2 つの変数 simpleByteArray、index を完全に制御できるとしても、スクリプトの実行環境が配列の境界チェックを暗黙的に行うため、ネイティブの言語と違って任意のデータを読み取ることはできません。しかし現在の JavaScript エンジンはスクリプト コードをマシン語にコンパイルしてから実行するため、投機的実行はネイティブ言語と同様に発生することが予想できます。

攻撃を成功させるためには、投機的実行だけでなく Flush+Reload もスクリプト言語で実行できるのがベストです。Flush+Reload のスクリプト実装で重要なのは、x86 の rdtsc 命令のような高精度なタイマーがあるかどうかです。JavaScript では、performance.now() や SharedArrayBuffer を利用した即席タイマーが利用できました。JavaScript で利用可能な高精度タイマーについては、以下の論文に詳しくまとめられています。

Fantastic timers and where to find them: high-resolution microarchitectural attacks in JavaScript
https://gruss.cc/files/fantastictimers.pdf

Spectre Variant 1 に対しては、これらの高精度タイマーの存在が第一に問題とされたようです。例えば Chromium では、performance.now() の精度を意図的に落とす実装が Meltdown/Spectre が公表された翌日の 1/4 に追加されています。

Clamp performance.now() to 100us. (I7e401d7b) · Gerrit Code Review
https://chromium-review.googlesource.com/c/chromium/src/+/849993

Spectre 論文における C での実装例 (Appendix A) の単純化

前述のように、実際の攻撃として Variant 1 をネイティブ言語で実装することはありませんが、Proof of Concept として動作を確認するためにはとても有用です。論文の末尾には C で書かれた単独動作可能なプログラムが掲載されています。Meltdown の IAIK 実装と違ってアセンブリを使っていない (intrinsic は使っていますが) ので、コンパイラーの最適化を外すための Spectre とは無関係なテクニックが散見され、少し読みにくいです。

アセンブリを使って単純化した Windows で実行可能な PoC のコードが ↓ です。後述する Variant 2 も試せます。

microarchitectural-attack/02_spectre_toy at master · msmania/microarchitectural-attack
https://github.com/msmania/microarchitectural-attack/tree/master/02_spectre_toy

論文の例とは、大きく 2 つの部分を変えました。Appendix A では、Listing 1 と対比しやすくするためか、Listing 1 のコードを victim_function としてそのまま (ただし stride がなぜか 256 ではなく 512 に変わっています) 実装しています。しかし Variant 1 の本質は、条件分岐のコード実行時に過去の履歴に基づいた投機的実行が発生するという点であり、分岐の条件が配列の長さをチェックするコードである必要はありません (その点で、GPZ の言う "Bounds Check Bypass" という名前は実用に偏りすぎていて、論文の "Exploiting Conditional Branch Misprediction" の方が本質を捉えていると言えます)。そこで victim_function の代わりとして、アセンブリで以下の branch_predictor という関数を使いました。

branch_predictor:
  cmp rcx, [r8]
  jae .skip_access

  movzx rax, byte [rdx + rcx]
  shl rax, 0Ch
  mov al, byte [r9 + rax]

.skip_access:
  ret

型を無視して C で表現すると、以下のようになります。第三引数の comparer は配列とは無関係で、ポインターを dereference したときの *comparer が常に 1 となるようなアドレスを渡しています。comparer としてポインターではなく値の 1 そのものを渡してしまうと、条件比較が一瞬で終わってしまって投機的実行が十分に実行されません。この例では、comparer (r8 レジスター) の指すアドレスから値をロードし、それを rcx の値と比較する間に、jae と skip_access の間にある 3 つの命令が全て投機的に実行されることを期待しています。

void branch_predictor(uint64_t relative_target,
                      void *basepos,
                      uint64_t *comparer,
                      void *probe) {
  if (relative_target < *comparer)
    volatile auto junk = probe_start[*(basepos + relative_target) * 4096];
}

大きく変更したもう一点は、トレーニングの部分です。Appendix A では、victim_function の引数 x として {training_x, training_x, training_x, training_x, training_x, malicious_x} のように、トレーニング 5 回分の値を渡した後に本番の値を 1 回渡すシナリオを 1 セットとして、それを 6 セット繰り返して 1 試行にしています。training_x は、[0, 16) に収まる値で、array1_size は 16 で固定なので、トレーニング実行時に if 文の条件は必ず true となります。配列 array1 の先頭には初期値が埋められていて、トレーニング時の Flush+Reload で得られた結果を後で検出して除外できるようになっています。

CPU に依存するのかもしれませんが、トレーニングの回数は 2 セットで十分でした。また、トレーニング データの生成ではビット演算を使わず、以下のように配列を直接用意するだけでも動きました。前述のように comparer は 1 で固定しているので、トレーニング時には常に if (0 < 1) という比較が発生します。

uint64_t train_and_attack[12] = {};
train_and_attack[5]
  = train_and_attack[11]
  = reinterpret_cast<uint64_t>(target_address) - reinterpret_cast<uint64_t>(gateway);

Variant 1 の再現は以上です。特に難しいこともなく 100% 動くものが作れました。

Spectre Variant 2: Branch Target Injection (CVE-2017-5715)

動作原理

Variant 2 の Branch Target Injection では、条件分岐の代わりに Indirect branch 命令を使います。Indirect branch とは、実行時に初めてジャンプ先が分かる命令のことです。C/C++ で言えば、関数ポインターや仮想関数の呼び出しが例として該当します。Indirect branch においても過去の履歴に基づいて投機的実行が行われます。その動作を利用して、攻撃者が選んだジャンプ先をトレーニングによって覚えさせ、ジャンプ先のコードの投機的実行を引き起こし、Flush+Reload で変化を検出する方法が Variant 2 です。これは Variant 1 に比べて遥かに自由度が高い方法です。Variant 1 では、トレーニングさせるのは条件分岐であって、ジャンプ先は予め決められています。if 文であれば 2 択、switch 文のジャンプ テーブルであったとしてもジャンプ先の自由度は大幅に制限されます。Variant 2 では、ジャンプ先そのものをトレーニングできる点が異なります。

論文では、5.2 Example Implementation on Windows において、別プロセスから値を取ってくる方法の道筋が示されていますが、残念ながら実装例は一切書かれていません。本記事では、プロセス内、プロセス間両方の Windows における再現方法について紹介します。

プロセス内 Branch Target Injection

Variant 2 のコアとなるコードをアセンブリで書きました。ジャンプ先のアドレスが格納されたポインターを第一引数の rcx レジスターで受け取ります。投機的実行のための時間的猶予を得るため、call で indirect ジャンプする前にジャンプ先の格納アドレスを clflush しています。分岐は一切存在しない単純なルーチンですが、このコードをトレーニングさせて、オリジナルの呼び出し先とは全く無関係なコードを投機的実行させることができます。

indirect_call:
  mov rax, rcx
  mov rcx, rdx ; 1st パラメーターの準備
  mov rdx, r8 ; 2nd パラメーターの準備
  clflush [rax]
  call [rax]
  ret

indirect_call 関数からのジャンプ先として、2 つの関数 do_nothing と touch_and_break を用意します。do_nothing は名前の通り何もせずに終わる関数です。投機的実行させたい関数は touch_and_break で、中に Flush+Reload のための仕込みが含まれています。投機的実行の効果を判断しやすくするため、関数の最後には ret ではなく sysenter を埋めました。普通に touch_and_break を実行すると、システムコールの設定を何もしていないので例外が発生します。

void do_nothing(uint8_t*, uint8_t*) {}

touch_and_break:
  movzx eax, byte [rcx]
  shl rax, 0Ch
  mov al, byte [rax+rdx]
  sysenter

トレーニングでは、indirect_call の第一引数に touch_and_break のアドレスが入ったポインターを渡します。ただし単純に touch_and_break を呼ぶと、末尾の sysenter でプロセスがクラッシュするので、トレーニング時には touch_and_break の先頭に ret 命令である 0xC3 を埋めて、呼ばれてすぐに関数が終わるようにします。トレーニングは Variant 1 に倣って 5 回繰り返します。

トレーニング後の本番実行では、touch_and_break の先頭バイトを元に戻してから、do_nothing のアドレスが入ったポインターを indirect_call に渡します。トレーニングの効果があれば、indirect_call の中で touch_and_break が投機的実行されるため、その後の Flush+Reload で変化が検出できるはずです。投機的実行なので、本番実行時に sysenter が呼ばれてプロセスがクラッシュすることはありません。

以上の作業、すなわちトレーニングと本番実行を実施するコードを Flush+Reload の処理を省いて抜粋すると以下の通りです。要素として {0,0,0,0,0,1} という値を持つ配列 train_and_attack を作って要素を列挙するループを回し、要素が 0 ならトレーニング、1 なら本番実行の処理が走ります。

  uint8_t train_and_attack[6] = {};
  train_and_attack[5] = 1;

  for (auto x : train_and_attack) {
    *reinterpret_cast<uint8_t*>(touch_and_break) = x ? original_prologue : 0xC3;
    target_proc = x ? do_nothing : touch_and_break;
    indirect_call(call_destination, target_address, probe);
  }

この PoC は Windows でほぼ 100% 動きます。indirect_call の中で clflush しているのが仕込みっぽくて非現実的ですが、clflush しなくても成功率は下がるものの動きます。Branch predictor というものが CPU 内に存在し、Indirect branch 命令の実行履歴が、同じ Indirect branch 命令における投機的実行を誘発できることが証明されました。

プロセス間 Branch Target Injection

Variant 2 が強力であるのは、別プロセスに働きかけることができる点です。これは、Indirect branch を管理している branch predictor がプロセスで分離されていないことに起因しており、Spectre 以前からも推測されていたアイディアです。GPZ ブログの Variant 2 の冒頭から引用します。このアイディアを使うと、単一のループで行なっていたトレーニングと本番実行を、それぞれ別プロセスで実行してもトレーニングの効果を得ることができます。

Prior research (see the Literature section at the end) has shown that it is possible for code in separate security contexts to influence each other's branch prediction. So far, this has only been used to infer information about where code is located (in other words, to create interference from the victim to the attacker); however, the basic hypothesis of this attack variant is that it can also be used to redirect execution of code in the victim context (in other words, to create interference from the attacker to the victim; the other way around).

別プロセスに対するトレーニングを行うにあたっての基本的な条件が、論文の 5.1 Discussion に箇条書きされています。特に重要なものを意訳して掲載します。

• ジャンプ先のメモリ ページは実行可能でなければならない
• Windows では、ロードされた実行可能モジュール (DLL/EXE) は基本的に複数のプロセスから共有され、共通の仮想アドレスが使われる
• プロセス間で共有されるモジュールのメモリ領域は、どのプロセスからでも clflush できる
• ジャンプ履歴の管理は、ジャンプ元仮想アドレスの全ビットではなく、一部の下位ビットが使われる
• Branch predictor は、ジャンプ先の仮想アドレスに着目し、命令コード、物理アドレス、プロセス ID は考慮しない
• Branch predictor は CPU コア間で独立しており、トレーニングは異なるコアには影響を与えない

以上を踏まえて、プロセス間で Branch Target Injection の再現を試みます。論文の 5.2 Example Implementation on Windows では、Haswell で動作する Windows 8 32bit 上で、Sleep 関数呼び出しの Indirect branch をトレーニングして実現できたようです。しかし、同じことを一週間ほど試行錯誤しましたが失敗に終わりました。この論文の実行環境はいささか奇妙です。普通なら彼らも当然 Windows 10 64bit で試したはずで、何らかの理由で困難だったのかもしれません。私の方では、手元の Haswell マシンになぜか Windows 8 32bit がインストールできず、代わりに Windows 8.1 32bit を入れても再現できませんでした。条件を緩めて、成功率が低いなりに Windows 10 64bit で動作する PoC が書けたので、その過程について紹介したいと思います。

論文における Windows での実装例

プロセス間 Branch Target Injection 実現までの具体的なステップは以下の通りです。

Step 1. Indirect branch 実行時に、外部から値をコントロールできるレジスターが存在する箇所を選ぶ

攻撃対象のプロセスは、攻撃者が何らかの入力データを与えられるものに限定されます。例えば Office が Office 文書をファイルから読み込む場合や、ブラウザーがネットワーク経由でデータを受信する場合では、攻撃者はユーザーを何らかの形でそのデータに誘導することで作為的なデータをユーザーに入力させることができます。このとき、入力データを制御することで値を任意に制御できるレジスターが存在しつつ、Indirect branch が実行される箇所を見つけます。まあこれは頑張って見つけるしかありません。論文の例では、32bit プログラムにおいて ebx と edi が入力ファイルによって制御できる状況で、Sleep API が Indirect branch で呼ばれる状況を使っています。実際この状況が発生するプログラムは、特に変なトリックを使わなくても簡単に書くことができます。特に Sleep 呼び出しは、KERNEL32!SleepStub に call で飛び、そこから KERNELBASE!Sleep にジャンプする動きになるので、常に kernel32.dll 上で Indirecte branch 命令の実行が発生するので使いやすいです。

Step 2. コントロールできるレジスターを使うと任意の箇所を Flush+Reload できるコードを共有 DLL の実行可能領域から探す

これも頑張って見つけるしかないです。論文では、ntdll.dll の実行可能領域に以下の 2 命令を実行する 9 バイトの領域 (= gadget) が存在することを使っています。ebx と edi は制御できていて、edx はいつも 3 になるらしいので、一つ目の命令で任意の場所からデータをロードさせることができます。ただしこの gadget は、読むデータが 1 バイトではなく 4 バイト値であるのが難点です。もし盗み出したい領域の近傍に既知の数バイトが存在すれば、edi を工夫することで隣り合うデータを知ることはできます。例えば、?? ab cd ef みたいな箇所があったとき、一つ目の命令で 0xefcdab00 + ?? という値が来ることは分かるので、edi を調整すれば二つ目の命令で probe + ?? の位置をロードすることができます。その取ってきた値に応じて再度入力データを変更することを繰り返し、既知の領域を広げていけばいいわけです。

adc edi,dword ptr [ebx+edx+13BE13BDh]
adc dl,byte ptr [edi]

Step 3. トレーニング (branch mistraining) を行う

実際に攻撃プログラム (以下 attacker と表記) を動かします。attacker は以下のタスクを同時に、タイミングよくこなさないといけません。それぞれにタスクに対して、1 つまたは複数のスレッドを作成して実現します。

Task 1: Train

Indirect branch があるのは kernel32.dll 上なので、攻撃用プログラムが Sleep を呼び出せば、本来は攻撃対象プログラム (以下 victim と表記) と同じ仮想アドレスで Indirect branch を実行できるはずです。attacker 内では、kernel32.dll の実行領域を書き換えて、KERNELBASE!Sleep にジャンプする代わりに ntdll.dll 内の gadget にジャンプするように変更します。さらに、ジャンプした後はすぐに呼び出し元に戻ってくるように ret を埋めておきます。

ここまで仕込んでおけば、あとは attacker 内で Sleep を呼ぶだけでトレーニングが行われるはずなのですが、論文はなぜか以下のように続きます。

These use a 2^20 byte (1MB) executable memory region filled with 0xC3 bytes (ret instructions. The victim’s pattern of jump destinations is mapped to addresses in this area, with an adjustment for ASLR found during an initial training process (see below). The mistraining threads run a loop which pushes the mapped addresses onto the stack such that an initiating ret instruction results in the processor performing a series of return instructions in the memory region, then branches to the gadget address, then (because of the ret placed there) immediately returns back to the loop.

どうやら単純に Sleep を呼び出すだけではないようです。この引用部分のうち特に、"run a loop which pushes the mapped addresses onto the stack such that an initiating ret instruction results in..." の部分の解釈に悩みました。おそらく、1MB 領域において 1024x1024 箇所ある 1 バイト単位のアドレスそれぞれから、ret で gadget に飛ぶような処理を実行することでトレーニングを行うことを言っているのだと考えています。

なぜこんな作業が必要かと言えば、ジャンプ先の ASLR に対応するためと書かれています。1MB の根拠は、2.3 Branch Prediction の最後に以下のように書かれている通り、Branch predictor がジャンプ先の下位 20bit のみを使っているという考えに基づいているはずです。

Evtyushkin et al. [11] analyze the BTB of a Intel Haswell processor and conclude that only the 30 least significant bits of the branch address are used to index the BTB. Our experiments on show similar results but that only 20 bits are required.

1MB = 20bit なので、1MB 全ての領域から gadget に飛ばすということは、プログラムのどこで Indirect branch が発生しても gadget への投機的実行が起こるように誘導していると考えられます。これは当初なかった構想ですし、その必要性は未だに理解できていません。Branch predictor が仮想アドレスのみに基づいていて、kernel32.dll の仮想アドレスがプロセス間で共有なのであれば、Sleep を呼ぶだけでトレーニングになるはずですし、後述の PoC でもそれは証明できています。不可解です。

Task 2: Evict

victim 内で発生する投機的実行分の時間を稼ぐため、Indirect branch のジャンプ先をメモリからロードするときに cache hit することを防がないといけません。プロセス内 PoC では call の前に clflush を実行して実現していましたが、今回 clflush したいのは victim 側です。attacker 内では、その部分のメモリ領域はトレーニング用にジャンプ先を書き換えており、同じ仮想アドレスでも、victim は KERNELBASE!Sleep、attacker は gadget を指しています。これは書き換えのタイミングで Copy-on-Write が発生したためで、victim と attacker とで異なる物理メモリが割り当てられています。したがって attacker 内で仮想アドレスに対して clflush しても、victim 内の仮想アドレスは clflush されません。そこで attacker 側では、L1/L2 キャッシュの容量 (CPU によりますが、数 MB 程度) に合わせた領域を確保しておいて、それらの領域全てがキャッシュに乗るようにメモリにアクセスするループを定期的に実行することで、clflush の brute-force のようなことをします。

Task 3: Probe

これまで何度も出てきた Flush+Reload ですが、上述の Train、Evict とタイミングを合わせる必要があります。以下のステップのタイミングが重要です。

1. [attacker: probe] Flush+Reload のための probe 領域の clflush
2. [attacker: train] gadget への mistraining
3. [attacker: evict] victim プロセスが保持している indirect branch 先のアドレスが入った領域のキャッシュ クリア
4. [victim] Sleep への indirect branch 実行
5. [attacker: probe] Flush+Reload のための probe 領域の探索

前述の通り branch predictor は物理コアごとに独立しているため、train が行われた直後に同じ物理コア上で victim での indirect branch 命令が実行される状況を作り出さないといけません。victim のスレッドにアフィニティーが設定されていることは通常期待できないので、attacker のスレッドにアフィニティーを設定して、victim スレッドを空きスレッドに追いやることは可能です。

Flush+Reload を同じコアで実行する必要はありませんが、evict の処理と victim プロセスによる indirect branch 実行を Flush と Reload の間に実行させる必要があり、ここがハードルの高い部分です。具体的にどのようにタイミングを合わせたのかは論文に書かれていません。

以上が、論文で紹介されているプロセス間の Spectre Variant 2 の Windows における実装例ですが、現実にはかなり制限が厳しいことが分かると思います。記述に沿うように全部実装して動かしてみたのですが、この方法では再現できていません。より簡単に PoC を実装する方法を検討してみましょう。

実際に Windows で動く プロセス間 Branch Target Injection の実装

まずは Indirect branch 命令だけを別プロセスで実行

論文の例から始めると、そもそも動くものが作れず、何をどう直せばいいのかが分からず苦しむ結果となりました。そこで、簡単な実装から難易度を少しずつ上げていく方針に切り替えます。現時点で既に実現できているのは、プロセス内 Branch Target Injection です。この PoC には大きく 4 つの処理があり、今のところすべてが同じプロセスで動いています。

• ジャンプ先のトレーニング
• ジャンプ先アドレス格納領域の Evict
• Indirect branch 命令の本番実行
• Flush+Reload

目標は Indirect branch の本番実行だけを単独のプロセスで実行することですが、それを極端に難しくしている理由は、タイミングを揃えるのがとにかく難しいからです。Proof-of-Concept の大前提として第一に実証したいのは、トレーニングが別プロセスの branch predictor に影響を与えるかどうかです。そこで、トレーニングだけを別プロセスで実行し、Flush+Reload と Indirect branch は同じプロセスで実行して結果を見てみます。

プロセス間で共有されているべき gadget は、既存の DLL から探すのではなく、都合のいい gadget を持つ DLL 作って attacker と victim から静的にロードすることにします。ジャンプ先アドレス格納領域の Evict についても、メモリクリアを brute-force する方法だと効率が悪いので、プロセス内 PoC と同様に call の直前に clflush を実行することにします。これで Evict を考える必要はなくなります。

Flush+Reload で使う領域もプロセス間で共有されていないといけません。Meltdown やこれまでの例で使ってきたように、256 * 4096 = 1MB の領域がプロセス間で共有されていると便利です。そこで、gadget を含む DLL に数 MB のビットマップ画像をリソースとして組み込んで、その領域を使うことにしました。

これを実現した PoC が、PoC #4 の最初の Run & Output に書いた部分です。トレーニングは Indirect branch を無限ループで回すだけです。Flush+Reload と本番用の Indirect branch 実行は、プロセス内 PoC とほぼ同じ処理であり、Flush と Reload の間で無害な Indirect branch を実行することで実現しています。

ここで一点、論文や GPZ の記述と異なる動作に遭遇しました。PoC では、トレーニングと Indirect branch を同じ CPU コアで実行するため、SetThreadAffinityMask でアフィニティーを設定しています。この API は、物理コアではなく Hyperthread 単位でアフィニティーを設定するものです。記述と異なる動作とは、victim プロセスと attacker 内のトレーニング スレッドのそれぞれに対して、同じ CPU コア上の異なる hyperthread を指定すると、トレーニング結果が victim に全く反映されず、PoC が完全に失敗する現象です。これは、branch predictor が CPU コアではなく hyperthread 単位でしか共有されていないことを示唆しています。Haswell を始め、Sandy bridge や Ivy bridge で試しても同様の結果が得られました。

一方論文では 5.1 Dicussion の冒頭に、Branch predictor は異なる hyperthread 間で共有されることが確認された、とはっきり書かれています。

Tests, primarily on a Haswell-based Surface Pro 3, confirmed that code executing in one hyper-thread of Intel x86 processors can mistrain the branch predictor for code running on the same CPU in a different hyper-thread. Tests on Skylake additionally indicated branch history mistraining between processes on the same vCPU (which likely occurs on Haswell as well).

GPZ のブログでは、BTB が hyperthread 間でも共有されることの根拠として Intel のマニュアルの記述を引用しています。

[10] Intel's optimization manual states that "In the first implementation of HT Technology, the physical execution resources are shared and the architecture state is duplicated for each logical processor", so it would be plausible for predictor state to be shared. While predictor state could be tagged by logical core, that would likely reduce performance for multithreaded processes, so it doesn't seem likely.

Intel のマニュアルの言う first implementation と今の hyperthread の実装が異なる可能性はありますが、論文の記述とここまで対立するのは奇妙です。おそらく私が何かを見逃しているのでしょうが。何にせよ、今のやり方ではトレーニングと victim を同じ hyperthread で動かさないといけない制限があります。

Flush+Reload を attacker で実行させる

前セクションが成功したということで、プロセスでの Indirect branch の実行履歴が、別プロセスの Branch predictor の動作に影響を与えることは証明できました。また、論文の例と違って 1MB 領域から闇雲に gadget に飛ばすように学習させる必要はなく、粛々と Indirect branch を無限ループで回すだけで十分な結果が得られました。さらに、Branch predictor の影響範囲が、物理コアではなく hyperthread 単位であるという新事実も得られました。これだけで Spectre Variant 2 の Proof-of-Concept としては十分とも言えますが、Flush+Reload を victim プロセスで実行しているのはあまりにも自虐的なので、もう少し実例に近づけてみましょう。

ということで、Flush+Reload の処理をそのまま attacker に移してみたところ、成功率はかなり低いながらも、attacker 側で victim が speculative execution した結果を読みだすことができました。成功率は、いかにタイミングを揃えられるのかにかかっています。まず、attacker の probe スレッドで Flush と Reload の間に for (volatile int z = 0; z < 1000000; ++z); という行を入れています。この僅かな間に victim 内で投機的実行が発生することを期待しています。Sleep でもいいのですが、何度か試して for ループの方が成功率が少し高かったので採用しました。

(2018/3/10 修正)
IAIK/meltdown の flush_reload と同じ実装を取り入れることで、probe スレッドに for 文を入れるハックは不要になりました。

もう一つは、そのうち代替策を見つけないといけない謎のハックなのですが、victim で Indirect branch を実行する前に、Flush+Reload の Flush 部分だけを実行する処理が入っています。これはもともと消し忘れていたものを気づかずに実行したらなぜか上手くいった、という全くの偶然の産物で、困ったことにこれがないと PoC は全く動きません。思い付く範囲で別のコード (Sleep や、brute-force なキャッシュ クリア) を試したのですが、代替案とはなりませんでした。この動作から何かヒントを得られそうなのですが、試行錯誤にはもう少し時間がかかりそうです。

PoC の動かし方などは GitHub の README に書いてあるので、そちらを見て下さい。

最後に、職場にあった適当なマシンで片っ端から検証した結果を載せておきます。Success Score は、PoC を 5 分間動かしっぱなしにして読み取れた回数を 5 で割った数値です。victim で Sleep、probe で for ループを使って遅れを発生させており、クロックが違うとタイミングの取り方が変わってくるので CPU 間でスコアの大小を比較してもあまり意味がありません。動作中の他プロセスからも影響を受けるせいか、同じマシンですらタイミングによってばらつきが多いので精度は悪いです。

明白なのは、最新の Update をインストールするとスコアが 0 になることです。表中の Ivy Bridge マシンは、同じマシンを使って KB4074588 有りだと成功率 0、KB4074588 アンインストール後に再現し放題になったので、OS 側で何らかの修正が施されたのは間違いありません。ただし、victim 側で Flush+Reload を実行する PoC はアップデート有りでも 100% 成功するので、コンテキスト スイッチのタイミングか何かで、プロセスを越えた Flush+Reload を防いでいるのかもしれません。

Core 2 には rdtscp 命令が存在しないため、lfence;rdtsc に置き換えて実行しました。さすがに CPU が古いので期待していなかったのですが、予想を裏切られました。Core 2 Duo でも Spectre は健在です。

と、最初の投稿の時に書きましたが、家にある 2 台のマシン (表の末尾に追加) では、Windows 10 1709 + KB4074588 の環境でもうまくいきました。OS レベルでの修正は幻だったかもしれない・・。

CPU	# of Core/HT	OS	Update	Success Score (bytes/minute)
Core™ i7-4712HQ (Haswell)	4/8	Windows 10 1709	RTM	0.4
Core™ i5-3320M (Ivy Bridge)	2/4	Windows 10 1709	KB4074588 (Februrary 2018 Update)	0
Core™ i5-3320M (Ivy Bridge)	2/4	Windows 10 1709	RTM	16
Xeon® E5-1650 (Sandy Bridge)	6/12	Windows Server 2016	KB4074590 (Februrary 2018 Update)	0
Xeon® E5-1620 (Sandy Bridge)	4/8	Windows Server 2016	KB4022723 (June 2017 Update)	3.4
Xeon® W3550 (Nehalem)	2/4	Windows Server 2012 R2	KB4048958 (November 2017 Update)	2.8
Core™2 6600 (Core)	2/-	Windows 10 1709	RTM	0.8
Core™ i7-2600 (Sandy Bridge)	4/8	Windows 10 1709	KB4074588 (Februrary 2018 Update)	6.2
Core™ i3-530 (Westmere)	2/4	Windows 10 1709	KB4074588 (Februrary 2018 Update)	2.0

おわりに

Spectre の 2 つのバリアントの動作原理と、それぞれを Windows で再現する方法について説明しました。PoC としては動くものの、最後のピースがまだ足りず改善の余地が大いにあります。

Meltdown/Spectre どちらも、今までなかった全く未知の知見ではなく、これまで研究者たちが積み重ねてきた知見が組み合わさってついに芽を結んだ、という印象があります。今回大きく日の目を見たことで、今後さらに発展していくかもしれません。

MeltdownPrime と SpectrePrime はいつやるの？

論文はダウンロードした、が、読んでません。読んでみて面白そうだったらやります。