ASPLOS-18 にて、 BranchScope と呼ばれる新しいCPUの脆弱性を付く攻撃手法が発表された。
今年の頭に ”Meltdown", "Spectre" で世間を騒がせたCPUの脆弱性の件だが、今回別の形で攻撃する手法を発見したということで、面白そうなので調査してみることにした。
こちらも現代のコンピュータアーキテクチャが誇る高性能CPUの機構をうまく活用するものであり、Spectreと考え方は近いようだ。
ちなみに、原論文は以下で入手することが可能だ。
- BranchScope: A New Side-Channel Attack on Directional Branch Predictor
http://www.cs.ucr.edu/~nael/pubs/asplos18.pdf
ざっくりと前半のしくみの部分を読んで、なるほど、こういう手もあるのか。という感じ。
Spectreのキーとなる技術は、L1Dキャッシュに乗ることでデータアクセスのタイミングが変わり、それで他プロセスの挙動を知ることができるのだが、このBranchScopeはL1Dキャッシュを使わない。
その代わりに分岐予測器を使う。L1Dキャッシュがなくてもこの攻撃手法は成立するし、Spectreとは考え方の異なる手法と言えるだろう。
はてさて、新しいIntelのプロセッサはこの攻撃を回避できるように作られているのか？
ちなみに、筆者は例によってセキュリティの専門家ではないし、CPUアーキテクチャにしてもデスクトップクラスの本格的なものは設計経験がないので、いまいち本文から読み取れない部分があったりとか、間違っている部分があるかもしれない。
概念的な部分でしか読み取れないのはいつも悲しいところだ。。。
Directional Branch Predictor とは
本文中でDirectional Branch Predictor という用語が出ており、これは何かというと「分岐をするかしないか」というのを決める機構のことを言っている。
BPU(Branch Prediction Unit) は大きく分けて2つのユニットで構成されており、それが"Branch Target Buffer (BTB)" および "Directional Branch Predictor" である。
ちなみに、Spectre と Meltdown などのCPU脆弱性は前者のBTBを使う攻撃手法であり、 Directional Branch Predictor を使った攻撃については本論文が初めてである、とのこと。
一般的にアウトオブオーダプロセッサなどの高性能プロセッサは、分岐予測において "Hybrid Branch Prediction" というものが搭載されており、 ”Local分岐予測" と "Global 分岐予測" を両方活用したものだ。
"Local Predictor" または本文で "1-level Predictor" と呼ばれている分岐予測は、プログラムカウンタの値に依存した分岐予測であり、「そのPCアドレスの命令が過去にどのような挙動(分岐したかしないか？)」に基づいて分岐予測を行うものである。
アーキテクチャ界隈で有名な図で以下のものが相当する。これは2ビット飽和カウンタで、あるPCアドレスに存在する分岐命令がジャンプするかしないかを2ビットで予測する。
2ビットで予測するため、例えばループを実行中に、分岐予測器はそのループを抜けるときだけ予測を外すのだが、再度そのループに入ったときにもう一度分岐予測が外れてしまうことを防いでいる。
1ビット分岐予測で都合が悪い例として、例えば以下のようなプログラムが存在するとき、
- j = 0 / i = 0 ... 10 : i が0から順番に進んでいく。内側のループは i = 2(i=1のときに分岐予測を外すと仮定) から i = 9までは分岐予測が当たるが、i = 10で外す。このとき、1ビット分岐予測だと「次の:A は分岐成立しない」と予測する (1ビットしか記憶がないため)
- j = 1 で再び内側のループを実行すするとき、 j = 1 / i = 1の場合(内側の最初のループ実行時)に、↑で「:Aは成立しない」と予測したため再び外す。i=2から当たり始める。
上記のように、1ビット分岐予測だと、10回のループが発生した場合、最初と最後は必ず外すことになってしまい、少し予測精度が悪い。
for (j < 10) {
for (i < 10) {
i++
} : A
}
一方で2ビット分岐予測により「1回外したけどこれまでずっと分岐成立してたし次も分岐するだろ」という予想を立てておけば、内側のループの最初 (i=0)で分岐予測を外すことがなくなり、予測精度が増す。
と、長々と説明したがこれが "1-level Predictor" の仕組みである。(2ビット持っていても1-level Predictorなのだ)
次に、"2-level Predictor" というのは、分岐命令を実行したPCアドレスに依存せず、過去に実行した分岐命令の相対位置関係を利用する。プログラムを実行してきた中で、過去にどのようなパタンで分岐が実行されたかの情報をBranch History Table (BHT)に記録する。このパタン記録と分岐アドレスから、Pattern History Tableのどのエントリにアクセスするかインデックスを計算し、どの分岐予測器を使用するか決定する。
BranchScope の攻撃の概要
- ステージ1. PHT エントリの準備
攻撃プロセスにより、ターゲットとするPHTエントリを特定の状態にする。PHTエントリは、各エントリ内に2ビット飽和カウンタが入っているので、特定パタンの分岐を何度も実行すると、特定の状態にPHTエントリを設定できる。
- ステージ2: victimプロセスを実行する。victimプロセスによりPHTの状態が変更されるまで、攻撃プロセスは待ち合わせを行う。
- ステージ3: PHTエントリの状態を検出する。攻撃プロセスターゲットのPHTエントリを叩くようなは分岐命令をさらに実行する。
これにより攻撃者は分岐予測の予測結果のタイミングを測定することで、victimプロセスの分岐方向を特定することでvictimプロセスを予測できるようになる。
ここで必要なのは、victimプロセスと攻撃プロセスで使用するPHTエントリをあわせることが出来ること。
PHTエントリは何で決まるかというと分岐アドレスで決まるため、それぞれのプロセスの仮想アドレスを取得して一致させせることでPHTエントリを衝突させることが出来る。
一方でアドレスのランダム化技法(ASLR: Address Space Layout Randomization)を使っていてもそれを元に戻す手法を使うことが出来るとしている([48])。
さて、ここでで問題になるのがどのようにしてPHTの衝突を起こさせるかと言うkとである。
このためには、非常に複雑なG-share分岐予測を使うのではなく、1-level分岐予測器が使われるように仕向けるのが良いだろう。
現代のプロセッサはハイブリッド分岐予測といって、1-level Predictorと2-level Predictorの両方を使い、その中でヒット率の良いものを採用すると言う機構を取っているため、わざと1-level Predictorの分岐予測精度を上げてやり、1-level Predictorを使うように仕向ける必要がある。
次に、PHTの衝突を起こさせたとして、次にどのようにPHTの状態を特定するか、ということになる。
PHTの状態を読み取るには、分岐予測の方向を読み取ることが出来るようになる。このためには、victimプロセスによりPHTの状態を特定の状態にしておくことが必要になる。
選択論理を制御することで、VictimプロセスとAtackerプロセスで衝突を発生させる方法
まず、victimプロセスと衝突プロセスをが使用するPHTを一致させるためには、選択論理を制御する必要がある。
上記のように構成のプロセッサはハイブリッド分岐予測により1-level Predictorと2-level Predictorを使い分けているため、どうにかしてプログラムを工夫して1-level Predictorを使うように仕向けたい。
1-level Predictorと2-level Predictorの特徴を上手く使い分ければこれが実現可能だ。
まず、1-level Predictorは同一の分岐命令であっても、その結果がランダムである場合に予測することが難しい。それは、その命令の過去の分岐結果が、次の分岐の結果に依存しないからだ。
一方で、2-level Predictorはうまくパタンにはまれば予測できるようになる。
そこで、以下のような実験を行った。
- 10ビットの変数を用意し、変数の値をランダムに初期化する。この10ビットの値は、それぞれのビットにより分岐が成立するかどうかを決定する要素となる。
- 単一の(つまり同じアドレス上に配置された)分岐命令で、この10ビットの変数の内容に基づいて分岐を行う。
この分岐を20回実行するとどうなるだろうか？
1-level Predictorは分岐予測精度が50%程度になるだろう。しかし、10ビットの変数を2回使うので、g-shareの分岐予測器はパタンを記憶し分岐予測が出来るようになる。
この結果を示したのがグラフ2.となっている。縦軸は10回の分岐命令においてヒットした回数で、横軸は試行回数だ。
図. 10ビット変数の値に基づく分岐命令の分岐予測結果。回数を繰り返すごとに予測精度が向上する。これがg-share分岐予測器の能力だ。(図は本論文から抜粋)
最初の1ループ目はほぼ50%の精度となっている。
これは1-level Predictorではこのスタイルのループは予測することは出来ず、また2-level Predictorではまだパタンを記憶できていないため予測が出来ない。
しかしパタンを覚え始める、つまり2ループ目から先は2-level Predictorがパタンを記憶しているため分岐精度は向上しており、ほぼ100%に近づく。
つまり、このようなプログラムのパタンでは2-level Predictorが予測精度を向上させていることが分かる。
では、ループの最初、つまり1-level Predictorと2-level Predictorのどちらも学習を行っていない場合はどうか。
ここで、そのような場合は1-level Predictorが使われると推測する。
これは、2-level Predictorのほうが学習に時間が掛かるため、学習時間が短い1-level Predictorが使われるであろうと言う直感である。
なんとかプログラムを工夫すれば、1-level Predictorのみ使うことが出来そうだ。
必要なのは、
- 2-level Predictorに検知されやすい分岐パタンが発生することを避けること。分岐パタンが予測しやすいと、2-level Predictorの予測結果が選択されてしまう。
- ターゲットとなる分岐命令が使われてないこと。BPUにとって始めて遭遇する分岐命令ならば、2-level Predictorが使われず1-level Predictorが選択されるはず。
まず、
* 完全に分岐予測が難しい状況を作り出すこと。2-level Predictorの分岐精度が低下している場合、1-level Predictorが使用されるため、アドレスの衝突が起こしやすい。
* Branch Predictorが学習する前の状態を作り出すこと。分岐予測率が低ければ、1-level Predictorが利用されやすい。
そこで、以下のようなプログラムを作ってみる。これがSpyプログラムである。
分岐命令の後続にランダムにnopが挿入されている。これにより分岐先アドレスが分散され、PHTをまんべんなく初期化する目的がある。
すべてのPHTテーブルを初期化するのに、100,000個分の分岐を実行すればよいということが実験の結果分かった。
randomize_pht:
cmp %rcx, %rcx;
je .L0; nop; .L0: jne .L1; nop; .L1: je .L2;
............
.L99998: je .L99999; nop; .L99999: nop;
次に、分岐予測の論理を見てみよう。分岐予測器の内部、つまりPHTのエントリの中身はFSM(Finite State Machine)だ。これは上記で説明したように、飽和カウンタとして動作し、2段階の分岐予測器として動作する。
と、教科書的には言われているが、実際にはどうだろう？分岐予測器の内部を事実から推論してみよう。
分岐予測器を思い通りに動かすテクニック
分岐予測器を使った攻撃について見てみる。ここでは、3ステージに分けて攻撃手法を説明している。
- Primeステージ : 同じ方向に分岐命令を3回実行する。これにより、間違いなく2ステージ飽和カウンタは、Strong Taken(ST) / Strong NotTaken (SN)に移動する。
- Targetステージ : 分岐予測器を今度は1回だけ、Taken or NotTaken で分岐命令を実行する。
- もし、もともとST状態にいて、Takenならば相変わらずSTステージのままであるはず。
- もし、もともとSN状態にいて、TakenならばWN(Weakly NotTaken)に移動するはず。
- もし、もともとST状態にいて、NotTakenならばWT(Weakly Taken)に移動するはず。
- もし、もともとSN状態にいて、NotTakenならば相変わらずSNステージのままであるはず。
- Probingステージ : 分岐予測器が予測ミスをするように、もう2回ほど分岐命令を実行する。このときの分岐予測結果を観測することにより、2. のTargetステージの分岐結果を予測できるようになる。
たとえば、
- Primeステージにて分岐結果がTakenとなる命令を3回実行したとする。飽和カウンタはSTとなる。
- Targetステージでの分岐命令がTakenならば、飽和カウンタはSTのままである。Targetステージでの分岐命令がNotTakenならば、飽和カウンタはWTとなる。
- ProbingステージでNotTakenとなるように分岐命令を2回実行する。
- Targetステージの分岐がTakenならば、飽和カウンタはST → WT → WSとなり、2回とも分岐予測を外す。
- Targetステージの分岐がNotTakenならば、飽和カウンタはWT →WN → SNとなり、1回目は分岐予測を外すが、2回目は予測が当たる。
つまり、Primeステージで攻撃者が分岐予測器をある方向に持っていき、次にvictimプロセスが1回分岐を実行する。最後にTargetステージで攻撃者が分岐命令を実行することで、Targetステージの動作を予測できるようになる、ということだ。
これがBranchScopeの基本的な考え方となる。
図. 2ビット飽和カウンタの動きと、その飽和カウンタの動きから、前の分岐結果を読み取る仕組み (本論文から抜粋)
BranchScopeの実装
BranchScopeの実装は疑似コードで提示されており、2つに分かれている。
- Victimプロセス (つまり攻撃対象のプロセスをモデル化したもの)
- Atackerプロセス (Victimプロセスの中身を読み取る)
それぞれのコードは以下の図のようになっている(本論文より抜粋)。
図. VictimプログラムとAtckerプログラムの疑似コード
Victimプログラムは、sec_dataと呼ばれる配列に格納されているデータに基づきプログラムが動作する。このsec_dataの配列はAtackerプロセスからは見えていないもので、Atackerは分岐結果を見ながらsec_dataの内容を読み解いていく。
ここで重要になるのは、上記にも示した通り、Victimプログラムが一度だけ実行される環境を作り出すことだ。これにはいくつか手法があるようだが、Victimプログラムをわざと非常に低速に動くように設定し、分岐が一度だけ実行され、Atackerにプロセスが移るような環境を作り出す。
そしてAtacker側のコードだが、まずはPHTの初期化を行う(randomize_pht())。これにより2-level Predictorの予測精度が低下し、1-level Predictorが使われるようになる。
次にVictimプロセスが分岐を一度だけ実行される。その間Atackerプロセスは待っている (usleep(SLEEP_TIME))。
最後に、spy_functionコードを実行し、if(array[i]) (つまり方向の決まっている分岐命令)を2回実行し、その時の分岐予測結果を読み取る (これにはいろんな手法があるだろうが、おそらくカウンタを使って次の命令のフェッチまでにかかる時間を計測するのがよかろう)。
この計測時間の違いにより、Victimプロセスで分岐が行われたかどうかを判定し、しいてはsec_dataの値が推測できるようになる、というカラクリだ。
図. Atacker と Victim プログラムの実行手順
