投機実行(Speculative Execution)

プロセサは、メモリ上に並んでいる命令を1個ずつ順番に実行していくというのが基本的な考え方である。しかし、より性能を高めるため、条件分岐の分岐先がどちらか決まらないうちに、どちらに行くかを予測してその先の命令を実行してしまうという投機実行が行われる。

予測が当たっていれば、そのまま実行を続ければ、分岐先が決まるまでの待ち時間の分、早く実行でき、性能が上がる。一方、予測が外れた場合は、予測で実行してしまった命令で書き変えてしまったレジスタを元に戻し、条件分岐命令に戻って実行をやり直すため、余計に時間が掛かってしまうが、予測が当たる確率が高ければ、総合的に実行時間を短くし、性能を上げることができる。

間違った予測で実行された命令で書き変えたレジスタを元に戻しているので、予測で実行してしまった命令の影響は取り消され、それらの命令を実行した影響は残らないと考えられてきた。しかし、今回、GoogleのProject Zeroと、それとは独立にPaul Kocher氏のグループとMoritz Lipp氏のグループが投機実行によるセキュリティホールが存在するという論文を発表した。なお、Paul Kocher氏もMoritz Lipp氏も両方の論文の著者になっており、2つのグループのメンバーはかなり重複している。

これらのセキュリティホールは、SpectreとMeltdownと呼ばれている。Spectreはお化けとか妖怪という意味であるが、Spec-lative Execution(投機実行)と掛けた命名となっている。また、Meltdownは、メモリ領域を分離する壁を熔かして除去してしまうことから名付けられている。

SpectreとMeltdownは、簡単に言うと、本来は実行されないはずの命令を投機実行させ、その命令で本来はアクセスできないメモリを読み出してしまう。この命令は投機実行が誤りであることが判明すると実行を取り消されてしまうのであるが、キャッシュを利用した秘密の抜け道を使って、取り消される前に本来はアクセスできない命令のデータを運び出してしまう。

  • Spectreの秘密情報盗み出し方法の概要

    Spectreの秘密情報盗み出し方法の概要

条件分岐に使われる変数がキャッシュに入っておらずメモリから読む場合などでは、100サイクル程度の待ちが必要となり、分岐予測ミスであることが判明する前に、多くの命令が投機的に実行されてしまう。Spectreの論文では180命令以上の命令が投機的に実行されるケースがあると書かれている。

なお、これはIntel CPUでの観測で、Intel CPUは予測と投機実行を頑張って性能を引き上げることを強力に行っているので、SpectreやMeltdownの攻撃を受けやすいという面があると思われる。

この分岐予測ミスを起こさせる部分は、

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

のような、指標xがarray1のサイズを超えているかどうかをチェックして、範囲内であれば、array1とarray2を読むというプログラムの小片である。このようなプログラムの小片は、被害者プログラムをスキャンすれば容易に見つかる。 攻撃プログラムは、この小片に飛び込んで攻撃を仕掛ける。

まず、攻撃プログラムはarray1_sizeより小さいxを与えて、この条件分岐を分岐せずに、次のy=の文を実行するようにトレーニングする。そして、xにarray1_sizeを超える大きな数を入れて攻撃を開始する。この時、xの値は、値を読み出したい攻撃対象のメモリアドレスになるように選んで置く。

本来は、xの値がarray1のサイズを超えているので、条件は不成立で、次のy=の文は実行されないのであるが、攻撃開始の直前にarray1_sizeをキャッシュから追い出しておけば、アクセスに長い時間が掛かってしまうので、条件の判定を待たずに投機的にy=の文が実行されてしまう。そして、array1[x]のアドレスのメモリを読んでキャッシュに入れる。しかし、このリードは投機的に実行したものであるから、その後に取り消されてしまい、array1[x]の値を読み出すことはできない。

なお、y=array1[x];のような文を入れると、array1[x]の値を変数yに格納しようとするが、投機的にメモリへの書き込みを行ってしまうと、その値は、キャッシュコヒーレンス機構が働いて他のCPUからも読める状態になってしまい取り消しができない。このため、投機的なリードは許されるが、投機的なライトは出来ないという作りが普通である。したがって、array1[x]の値を直接読むことは出来ないようになっている。

キャッシュを使う秘密の抜け道

この問題を回避するため、この攻撃の前に、キャッシュの内容はフラッシュして空にしておく。そうすると、攻撃の直後には、array1[x]の値を読むので、キャッシュのarray1[x]に対応するキャッシュラインだけにデータがあり、他のエントリはフラッシュされて空の状態になっている。

ここで256を掛けているのは、array2[array1[x] *256]を異なるキャッシュラインに入れるためである。

そして、array2[k*256]をk=0~255として順番に読み出していくと、k=Mod256(array1[x])の場合は、キャッシュがヒットするので読み出し時間が短く、kがその他の値の読み出しはキャッシュミスとなり、読み出し時間が長くなる。したがって、この読み出し時間を測定していけばarray[x]の値を推定する手がかりが得られる。

  • Meltdownの論文に載っているキャッシュのアクセス時間の測定データ

    Meltdownの論文に載っているキャッシュのアクセス時間の測定データ。Page=84の時だけ200サイクル程度でアクセスできているが、それ以外のページのアクセスは400サイクルかそれ以上かかっている

このキャッシュを使う攻撃はSpectreより以前から知られており、FLUSH+RELOAD攻撃と呼ばれている。

ここで説明した攻撃は、配列のアクセスを行うときに、配列の範囲チェックをかいくぐって本来のアクセスの範囲外のメモリをアクセスするものであるが、Spectreには、間接分岐命令の跳び先を変えてしまうという攻撃モードもある。しかし、こちらの手順はさらに複雑であるので、説明は割愛する。

Spectreは投機実行の隙を突くもので、Intel CPUだけでなく、AMDやArmでも攻撃できるのであるが、被害者プログラムの中のコードの小片の投機実行で範囲外のメモリをアクセスするので、被害者プログラムのメモリのページ一覧表に入っていないメモリのデータを読み出すことはできないという制約がある。

(次回は1月18日に掲載します)