姍姍來遲的Meltdown/Spectre分析

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

背景知識(shí)

亂序執(zhí)行

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

Common Data Bus (CDB).

Unified Reservation Station (Scheduler).

Register Renaming (Reorder Buffer).

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

這幅圖可以對(duì)ROB有個(gè)大致了解:

旁路攻擊

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的時(shí)間有數(shù)量級(jí)差異, 所以通過衡量時(shí)間就可以判斷出數(shù)據(jù)是否在cache里面.

Attacker先通過Flush清空對(duì)應(yīng)的cache line

觸發(fā)Victim訪問該數(shù)據(jù)

Attacker會(huì)訪問同一數(shù)據(jù)并測(cè)量訪問時(shí)間

投機(jī)執(zhí)行

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

分支預(yù)測(cè)

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使用虛擬地址, 并且是截?cái)嗟牡刂? 不需要和victim完全一樣的地址

SMT會(huì)共享同一個(gè)BTB, 即使不在同一個(gè)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

攻擊方法

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

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

其中0xffffffff81a000e0是位于kernel space的地址, 選擇這個(gè)位置是因?yàn)樗锩媸谴_定的值, 方便驗(yàn)證方法是否有效:

# sudo grep linux_banner /proc/kallsyms ffffffff81a000e0 R linux_banner

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

kernel space和user space在同一地址空間, 即使cpu會(huì)執(zhí)行權(quán)限檢查

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

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

舉個(gè)例子

以這個(gè)為例: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" );

執(zhí)行結(jié)果如下:

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是很有效的. 代碼里面關(guān)鍵的幾點(diǎn):

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行. 似乎完全不相干, 即使刪掉它們, 運(yùn)行結(jié)果也完全一樣!

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

_mm_mfence();

先把它刪掉, 重新執(zhí)行還是能夠讀出數(shù)據(jù), 但是score很多已經(jīng)到個(gè)位數(shù)了, 說明已經(jīng)不能穩(wěn)定讀出數(shù)據(jù)了. 更進(jìn)一步, 把其中rept的指令改成:

mov $0x141, %%rax

此時(shí)已經(jīng)完全不能讀出數(shù)據(jù)了, 即使把mfence加回來也無濟(jì)于事. 這是因?yàn)閙eltdown要攻擊成功, 需要時(shí)間窗口, 越權(quán)訪問那條指令必須在第二條指令加載數(shù)據(jù)到cache之后(or in flight?) retire, 否則觸發(fā)異常從而會(huì)中斷亂序執(zhí)行. 從測(cè)試可以知道:

mfence能很好地起到阻塞后面異常指令retire, 因?yàn)樗苈? 而且cpu是順序retire的

rept中add $0x141, %%rax一定程度也能起到阻塞的作用, 但是沒有mfence穩(wěn)定. 注意這條add指令會(huì)同時(shí)讀寫rax寄存器, 導(dǎo)致這300條指令前后形成read-after-write的依賴關(guān)系, 這樣在執(zhí)行的時(shí)候就會(huì)形成依賴關(guān)系, 從而導(dǎo)致ROB上指令的積壓, 而mov $0x141 %%rax因?yàn)閞egister renaming的原因并不會(huì)形成真實(shí)的依賴關(guān)系. (ROB的容量和入隊(duì)速率, ALU執(zhí)行單元個(gè)數(shù), Reservation State的容量, 這些可以進(jìn)行更細(xì)致的分析)

防御方法

Kernel Page Table Isolation (KPTI) 中user space對(duì)應(yīng)的頁(yè)表已經(jīng)沒有kernel space的內(nèi)容, 這樣就不能訪問到kernel的數(shù)據(jù)了, 不管有沒有亂序執(zhí)行.

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仍然可能先投機(jī)執(zhí)行第二條語句, 從而訪問到不應(yīng)該訪問的數(shù)據(jù)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, 這樣條件指令所需時(shí)間更長(zhǎng), 有利于投機(jī)執(zhí)行; array1[x]在cache, 這樣array2[array1[x] * 4096]才能盡早發(fā)出

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

防御方法

防御的思路是: 即使投機(jī)執(zhí)行了錯(cuò)誤路徑也不會(huì)泄露信息, 這種方式比較簡(jiǎn)單:

index < size. 正確性沒有影響

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

/* * 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條不同的執(zhí)行路徑, 而v2通過訓(xùn)練indirect branch, 理論上可以引誘cpu[錯(cuò)誤路徑]去執(zhí)行任意gadget.

防御方法

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

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

關(guān)鍵點(diǎn)在于ret導(dǎo)致的分支預(yù)測(cè)采用了RSB的內(nèi)容, 而該內(nèi)容是在call的時(shí)候產(chǎn)生的, 也就是上面的語句2. 所以即使針對(duì)ret的分支預(yù)測(cè)錯(cuò)了, 語句2并不會(huì)泄漏任何信息, 最后ret語句讀到(%rsp)的內(nèi)容, 該值和RSB里的值不符, 投機(jī)執(zhí)行結(jié)束, 它沒產(chǎn)生任何正向效果, 但是也沒有任何負(fù)面效果.

引用

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

原文標(biāo)題：遲到的Meltdown/Spectre分析

文章出處：【微信公眾號(hào)：Linuxer】歡迎添加關(guān)注！文章轉(zhuǎn)載請(qǐng)注明出處。

責(zé)任編輯：haq