Meltdown/Spectre在2018年初鬧得沸沸揚揚, 可以說是有史以來最有影響的cpu漏洞了. 當時有過簡單了解, 但是不夠深入, 這兩天重新又看了一下.

背景知識

亂序執行

cpu的亂序執行一般都使用Tomasulo算法, x86也不例外, 主要包括:

Common Data Bus (CDB).

Unified Reservation Station (Scheduler).

Register Renaming (Reorder Buffer).

該算法雖然是亂序執行, 但是會順序完成 (retire), 只有在retire后它的輸出才會architectually visible (簡單地說, 不影響程序邏輯), 但是沒有architectually visible不等于沒有影響, 當輸出更新到reservation station后, 因為cdb的存在, 其他指令已經可以讀到. 另外, 非常重要的一點, 異常只有在指令retire的時候才會觸發, 對于上面的例子, 即使cpu已經檢查到第一條指令沒有訪問權限, 也只能等到該指令retire時才會觸發, 取決于該指令在ROB的位置, 可能馬上觸發也可能很久之后, ROB容量可以很容易做到比如192這個級別.

這幅圖可以對ROB有個大致了解:

旁路攻擊

Meltdown/Spectre使用的都是旁路攻擊(Side Channel Attack), 這里引用What Is a Side Channel Attack的描述:

Side channel attacks take advantage of patterns in the information exhaust that computers constantly give off: the electric emissions from a computer's monitor or hard drive, for instance, that emanate slightly differently depending on what information is crossing the screen or being read by the drive's magnetic head. Or the fact that computer components draw different amounts of power when carrying out certain processes. Or that a keyboard's click-clacking can reveal a user's password through sound alone.

Meltdown/Spectre利用了旁路攻擊的一種常見手段Flush+Reload, CPU訪問DRAM和cache的時間有數量級差異, 所以通過衡量時間就可以判斷出數據是否在cache里面.

Attacker先通過Flush清空對應的cache line

觸發Victim訪問該數據

Attacker會訪問同一數據并測量訪問時間

投機執行

投機執行(Speculative Execution)本質上是亂序執行的一種, 存在條件判斷的時候, cpu如果預測該分支為true, 則投機執行里面的語句.

分支預測

Indirect branch

Branch Target Buffer (BTB)

Indirect JMP and CALL instructions consult the indirect branch predictor to direct speculative execution to the most likely target of the branch. The indirect branch predictor is a relatively large hardware structure which cannot be easily managed by the operating system.

Return Stack Buffer (RSB)

Prediction of RET instructions differs from JMP and CALL instructions because RET first relies on the Return Stack Buffer (RSB). In contrast to the indirect branch predictors RSB is a last-in-first-out (LIFO) stack where CALL instructions “push”entries and RET instructions “pop” entries. This mechanism is amenable to predictable software control.

Train BTB

BTB使用虛擬地址, 并且是截斷的地址, 不需要和victim完全一樣的地址

SMT會共享同一個BTB, 即使不在同一個cpu[線程]上, 也可以train

Gadget

Spectre Attacks: Exploiting Speculative Execution

Return-Oriented Programming (ROP) [63] is a technique that allows an attacker who hijacks control flow to make a victim perform complex operations by chaining together machine code snippets, called gadgets, found in the code of the vulnerable victim. More specifically, the attacker first finds usable gadgets in the victim binary. Each gadget performs some computation before executing a return instruction.

Meltdown and Spectre - Usenix LISA 2018

A“gadget”is a piece of existing code in an (unmodified) existing program binary. For example code contained within the Linux kernel, or in another “victim” application
A malicious actor influences program control flow to cause gadget code to run
Gadget code performs some action of interest to the attacker
For example loading sensitive secrets from privileged memory
The code following the bounds check is known as a “gadget”

Meltdown

攻擊方法

先看一個meltdown的示例程序, 普通權限用戶通過它能夠讀出kernel space中0xffffffff81a000e0的內容, 以下是攻擊者的代碼:

char data = *(char*) 0xffffffff81a000e0; array[data * 4096] = 0;

其中0xffffffff81a000e0是位于kernel space的地址, 選擇這個位置是因為它里面是確定的值, 方便驗證方法是否有效:

# sudo grep linux_banner /proc/kallsyms ffffffff81a000e0 R linux_banner

按照正常的理解, 第一條語句訪問內核地址會觸發異常, 所以不能獲得data值. Meltdown利用了以下因素:

kernel space和user space在同一地址空間, 即使cpu會執行權限檢查

cpu亂序執行. 第一條語句確實[最終]會觸發異常, 但是并沒有阻止第二條語句的執行. 當然攻擊者需要處理該異常信號, 否則代碼不能繼續執行, 信號處理函數的具體處理邏輯可以見下面提到的例子. 另外也可以使用別的手段, 比如放在投機執行的地方, 投機執行的指令導致的異常會被忽略

第二條語句通過旁路攻擊的方法獲得data的值. data取值只有256種可能, 通過訪問array[]不同偏移的時長確定data的取值. 這里能夠同時獲取8bit數據, 也可以設計出獲取其他長度數據的代碼

舉個例子

以這個為例:github.com/paboldin/mel, 里面主要邏輯如下:

asm volatile ( "1: " ".rept 300 " "add $0x141, %%rax " ".endr " "movzx (%[addr]), %%eax " "shl $12, %%rax " "jz 1b " "movzx (%[target], %%rax, 1), %%rbx " "stopspeculate: " "nop " : : [target] "r" (target_array), [addr] "r" (addr) : "rax", "rbx" );

執行結果如下:

cached = 31, uncached = 336, threshold 102 read ffffffff8164e080 = 25 % (score=999/1000) read ffffffff8164e081 = 73 s (score=1000/1000) read ffffffff8164e082 = 20 (score=996/1000) read ffffffff8164e083 = 76 v (score=999/1000) read ffffffff8164e084 = 65 e (score=999/1000) read ffffffff8164e085 = 72 r (score=1000/1000) read ffffffff8164e086 = 73 s (score=999/1000) read ffffffff8164e087 = 69 i (score=1000/1000) read ffffffff8164e088 = 6f o (score=1000/1000) read ffffffff8164e089 = 6e n (score=999/1000) read ffffffff8164e08a = 20 (score=1000/1000) read ffffffff8164e08b = 25 % (score=1000/1000) read ffffffff8164e08c = 73 s (score=1000/1000) read ffffffff8164e08d = 20 (score=1000/1000) read ffffffff8164e08e = 29 ( (score=998/1000) read ffffffff8164e08f = 61 % (score=999/1000)

可以看到上面的score都非常高, 說明通過Flush+Reload是很有效的. 代碼里面關鍵的幾點:

8-11行是主要代碼, 和論文里的例子幾乎一樣

10行的jz論文里提到: While CPUs generally stall if a value is not available during an out-of-order load operation [28], CPUs might continue with the out-of-order execution by assuming a value for the load.

4-6行. 似乎完全不相干, 即使刪掉它們, 運行結果也完全一樣!

繼續來看4-6行的作用, 首先看到在上面的匯編代碼執行之前, 執行了語句:

_mm_mfence();

先把它刪掉, 重新執行還是能夠讀出數據, 但是score很多已經到個位數了, 說明已經不能穩定讀出數據了. 更進一步, 把其中rept的指令改成:

mov $0x141, %%rax

此時已經完全不能讀出數據了, 即使把mfence加回來也無濟于事. 這是因為meltdown要攻擊成功, 需要時間窗口, 越權訪問那條指令必須在第二條指令加載數據到cache之后(or in flight?) retire, 否則觸發異常從而會中斷亂序執行. 從測試可以知道:

mfence能很好地起到阻塞后面異常指令retire, 因為它很慢, 而且cpu是順序retire的

rept中add $0x141, %%rax一定程度也能起到阻塞的作用, 但是沒有mfence穩定. 注意這條add指令會同時讀寫rax寄存器, 導致這300條指令前后形成read-after-write的依賴關系, 這樣在執行的時候就會形成依賴關系, 從而導致ROB上指令的積壓, 而mov $0x141 %%rax因為register renaming的原因并不會形成真實的依賴關系. (ROB的容量和入隊速率, ALU執行單元個數, Reservation State的容量, 這些可以進行更細致的分析)

防御方法

Kernel Page Table Isolation (KPTI) 中user space對應的頁表已經沒有kernel space的內容, 這樣就不能訪問到kernel的數據了, 不管有沒有亂序執行.

Whereas current systems have a single set of page tables for each process, KAISER implements two. One set is essentially unchanged; it includes both kernel-space and user-space addresses, but it is only used when the system is running in kernel mode. The second "shadow" page table contains a copy of all of the user-space mappings, but leaves out the kernel side. Instead, there is a minimal set of kernel-space mappings that provides the information needed to handle system calls and interrupts, but no more. Copying the page tables may sound inefficient, but the copying only happens at the top level of the page-table hierarchy, so the bulk of that data is shared between the two copies.

Whenever a process is running in user mode, the shadow page tables will be active. The bulk of the kernel's address space will thus be completely hidden from the process, defeating the known hardware-based attacks. Whenever the system needs to switch to kernel mode, in response to a system call, an exception, or an interrupt, for example, a switch to the other page tables will be made. The code that manages the return to user space must then make the shadow page tables active again.

Spectre V1

攻擊方法

以下代碼中即使if條件為false, cpu仍然可能先投機執行第二條語句, 從而訪問到不應該訪問的數據array1[x], 其中x >= array1_size, 所以這種攻擊也稱為Bounds Check Bypass.

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

上面是victim的代碼, 為了完成攻擊:

attacker需要在victim中找到該段代碼, 毫無疑問

attacker需要能夠控制變量x

attacker需要能夠訪問array2, 否則沒有side channel

array2不在cache, 這是旁路攻擊使用Flush+Reload的前提

array1_size不在cache, 這樣條件指令所需時間更長, 有利于投機執行; array1[x]在cache, 這樣array2[array1[x] * 4096]才能盡早發出

一般來說要同時滿足條件1,2,3并不容易, 但是eBPF可以比較容易構造, 畢竟可以自己寫eBPF腳本.

防御方法

防御的思路是: 即使投機執行了錯誤路徑也不會泄露信息, 這種方式比較簡單:

index < size. 正確性沒有影響

index >= size. array_index_nospec返回值范圍在[0, size), 所以不會有越界訪問

/* * array_index_nospec - sanitize an array index after a bounds check * * For a code sequence like: * * if (index < size) { * index = array_index_nospec(index, size); * val = array[index]; * } * * ...if the CPU speculates past the bounds check then * array_index_nospec() will clamp the index within the range of [0, * size). */ #define array_index_nospec(index, size) ({ typeof(index) _i = (index); typeof(size) _s = (size); unsigned long _mask = array_index_mask_nospec(_i, _s); BUILD_BUG_ON(sizeof(_i) > sizeof(long)); BUILD_BUG_ON(sizeof(_s) > sizeof(long)); (typeof(_i)) (_i & _mask); })

Spectre V2

v1通過bypass bounds check, 可以在選擇2條不同的執行路徑, 而v2通過訓練indirect branch, 理論上可以引誘cpu[錯誤路徑]去執行任意gadget.

防御方法

Retpoline通過把jmp/call指令轉換為ret解決分支預測的問題, 也即把分支預測由BTB轉移到了RSB, 注意軟件可以很方便地控制RSB (underflow問題這里不討論).

這里一jmp指令的indirect branch為例:

關鍵點在于ret導致的分支預測采用了RSB的內容, 而該內容是在call的時候產生的, 也就是上面的語句2. 所以即使針對ret的分支預測錯了, 語句2并不會泄漏任何信息, 最后ret語句讀到(%rsp)的內容, 該值和RSB里的值不符, 投機執行結束, 它沒產生任何正向效果, 但是也沒有任何負面效果.

引用

Meltdown: Reading Kernel Memory from User Space

Spectre Attacks: Exploiting Speculative Execution

Meltdown and Spectre - Usenix LISA 2018

Retpoline: A Branch Target Injection Mitigation

Hacker Lexicon: What Is a Side Channel Attack?

KAISER: hiding the kernel from user space

本文作者：J.FW

原文標題：遲到的Meltdown/Spectre分析

文章出處：【微信公眾號：Linuxer】歡迎添加關注！文章轉載請注明出處。

責任編輯：haq