看板 PC_Shopping
作者 jk21234 (BL2400PT真不錯)
標題 Re: [情報] Intel嚴重漏洞 OS更新將會降低效能
時間 Sat Jan  6 00:20:55 2018



為什麼cache預料之外的hit會導致data外流....

其實表面來說 資料沒有被讀出來 但是是被窮舉的方式猜出來的

基本原理

0.   int64 a = rdtsc()

RDTSC = Read the Time Stamp Counter,
這個數字從開機的時候就從0開始增加,一個cycle + 1.
這個指令不用進入高權限模式就可以執行
Pentium 75開始就有,在1995之後大量被使用
來測試效能 或者是作速度控制.
導致為了相容性不容易把它拔掉或者禁止低權限模式使用

有些範例會用進階的rdtscp(),這個是修正版本
需要SSE2,但是跟多核心cpu相容...RDTSC在多核心cpu的值
不一樣,本用途則差異不大

     int64 a = rdtsc()
     b = load_mem(ADR_A)
     a = rdtsc() - a

這時候a會相近於這次load_mem所花掉的cycle數,
有一些誤差 但是通常在10 cycle以下

如果我做兩次 一次得到的a是> 200 , 一次是 < 20,
對cpu有點了解的就知道,cpu有一種叫做cache的機制
讓讀取有些時候可以加快不用那麼慢


所以很直覺的, >200 應該表示cache miss , 原本不在cache中,
< 20 , 上次應該就在cache中

這個後面會應用到

                         <======想按左鍵嗎??

1. 假設已知CPU的最後一層Cache 有10MB, 而且為12-way,

如果我有一個陣列U[10MB].考慮最簡單的情況
我連續讀取這10MB之後那一瞬間,是不是會把cache中原本的資料幾乎
全部洗出來,cache中幾乎全部是我這10MB的資料.

是的 這是基本假設

然後我們進階一點,cache被U[10MB]塞滿之後 我再load_mem(A),
這時候因為cache沒有他的資料,一定是cache miss,然後放棄掉U[10MB]中的
某區塊不在cache中,下次就是這個區塊的記憶體萬一又要讀取到 就會miss

(中間省略)最後針對一個Address A,我都可以在U中找到32Byte*12
總共384Byte的位址 只要這群資料用12個load_mem()讀入,就會
保證Address A的資料被擠出Cache

    Q1:所以要先知道cpu cache的大小跟規格???

     A:不用 用前面的方法本身就可以探索出cpu cache的最大值
       跟way-associative的數值,其實就是拿各種size的陣列U
       讀取跟分割讀取,可以求到的數值


2.

     a = rdtsc()
     b = load_mem(SYSTEM_A)
     a = rdtsc() - a

會發生甚麼事情?如果SYSTEM_A是一個猜的Address,位在保護區段且不可讀取
其實正常就是產生General Protection Fault,但可以Program自己接手回來
這個Exception


正常來說, B不會被更新, 但關鍵在第二次的rdtsc()甚麼時候執行
Out of order 有可能

     a. load_mem之前
     b. load_mem之後,exception之前
     c. exception之後

第一種情況會得到一個特小個位數的值 也可以用mem_barrier()
或者mem_fence() (這兩種指令是規定指令與mem_load要排隊)
隔離開 第一種情況基本上就不會發生

第二種情況 驚異的是它很接近一般的mem_load,有時候可以看到
  > 200t, 有時候看到 < 20t,明明SYSTEM_A就不給讀取...

第三種就是rdtsc會超長,1000cycle內不太可能,或者.多核心之下不一定正常
可以當雜訊值排除

不是用這個方法 但是繼續進化的話...

3.設定一個陣列X,可以是256 Byte,或者適當的倍數
然後我同樣有個U[10MB]的陣列

     a = rdtsc()
     b = load_mem(SYSTEM_A)
     c = load_mem(&X + b)
     mem_fense()
     a = rdtsc() - a

第一次做無效的SYSTEM_A的load, B不會得到結果

但是,我這端不知道B的值 可是CPU知道X陣列的第B個元素
加起來是多少,他去載入這個位置了.....會在C拿到嗎
不會 第一次load_mem無效,第二次load_mem一樣無效

至於exception的問題同前,但是多跑幾次在這組行為中看到cache miss

與cache hit的時間差異


然後我找個樣本

     a = rdtsc()
     b = load_mem(DUMMY)
     c = load_mem(&X + 0)
     mem_fense()
     a = rdtsc() - a

找出U[10MB]之中,對第二次&X + 0
具有cache互斥性的384 Byte資料為一組

抽出來 跟
     a = rdtsc()
     b = load_mem(SYSTEM_A)
     c = load_mem(&X + B)
     mem_fense()
     a = rdtsc() - a
一起玩

如果發現&X + B的載入行為,Cache Miss的時間
和&X + 0的對照組相同

那麼, B的內容就是0
如果比照起來不相似&X + 0與它的384 byte伙伴的相處關係
那就要再找&X + 1,這時候是另外384 byte快樂伙伴
來比較.....最多比較256次來確定一個Byte

實際上這整個流程都在窮舉 應該全速運作也要十萬個cycle以上
才能確定1 Byte的資料

3a.Speculative Execution

我不太確定正確的方法要不要應用speculative execution的指令
在這件事情需要用被動的指令speculativity還是主動指定為
speculative execution 但假設是的話 可以應用的範圍為

無效的mem_load,原本會產生exception,
但是我可以用speculative execution,放在不會執行的if-else中
但CPU不具有足夠條件做出正確的branch prediction的話,
在不執行那端的mem_load也會排入pipeline,並且在最後取消

     volatile V = *Y
     a = rdtsc()
     if (V > 0)
     else
     {
     b = load_mem(DUMMY)
     c = load_mem(&X + 0)
     }
     a = rdtsc() - a

==>speculative execution化

     volatile V = *Y
     a = rdtsc()
     SPEC_TRUE(V) { }
     SPEC_FALSE(V)
     {
     b = load_mem(DUMMY)
     c = load_mem(&X + 0)
     }
     a = rdtsc() - a

這時候CPU ooo會同時開始執行SPEC_TRUE與SPEC_FALSE的指令
最後SPEC_FALSE因為不成立,所以load_mem執行到中間就被取消
但這中間已經去Memory動作了 因此Cache也產生變化,但是取消
後不發exception,可能速度會加快很多 然後Host OS無法

偵測到你一直在產生GPF,降低被發現的機率


F.最後結論


  以上的用法有需多前提條件 因此了解這個條件後有對應的話
  可能可以避開.....對這沒甚麼自信 降低發生問題的洞

  1.電腦Cache讀取的時間與外部記憶體差異巨大
    現況一定是這樣 未來也一定是 無解

  2.rdtsc精確度太高 來個1000 cycle誤差就行
    或者限制僅kernel mode可以用(規格上已經支援 但為了相容性不開)
    總之rdtsc要背太多舊程式相容性的鍋..

  3.直覺上,跑一個記憶體載入指令,應該要在合法的位置才啟動啊

    但實際上:

                 |TLB/PF  |VALID|
    |FETCH|DECODE|MEM-----|ADR  |WRITE|

    為了加速,計算Address合法性要經過TLB不比Memory回來快上多少
    因此在檢查的同時也發出了Memory 存取的功能,讓兩個一起發動

    如果指令在MEM之前能檢查完Address的合法性 連整個

    MEM/Cache Stage都不啟動的話則降低這種事情被分析跟被窮舉的可能

  4.上面的例子等於一個指令中有Indirect Memory的存取.但沒有支援
    這種指令的RISC並沒有完全避掉問題 所以單一指令有沒有MEM[MEM[ADR]]
    這樣的存取能力是不是重點就不知道了

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.243.156.56
※ 文章代碼(AID): #1QJwNfvM (PC_Shopping)
※ 文章網址: https://www.ptt.cc/bbs/PC_Shopping/M.1515169257.A.E56.html
※ 同主題文章:
Re: [情報] Intel嚴重漏洞 OS更新將會降低效能
01-06 00:20 jk21234.
kira925: 推1F 01/06 00:25
hizerg: 推2F 01/06 00:25
royroy666: 先推3F 01/06 00:29
PlayStation3: JK神4F 01/06 00:30
Shauter: JK最高5F 01/06 00:35
s25g5d4: 推 JK 神6F 01/06 00:41
jk21234: 3的描述有bug, X要是256 Byte的很多倍而且&X + 0
該知道我簡化過不想修正回來了..7F 01/06 00:43
KotoriCute: jk神!先推再說9F 01/06 00:45
ang728: 好久沒推 先推再說10F 01/06 00:49
winiel559: 推jk神11F 01/06 01:00
Windcws9Z: 推12F 01/06 01:06
jior: 快推,免得人家知道我是文組!!13F 01/06 01:09
alexgame01: 推14F 01/06 01:24
saito2190: 先推,資工肥宅快要看不懂了15F 01/06 01:43
tyler930030: 我也那麼認為呢16F 01/06 01:48
ccc73123: 這個理組也不一定看得懂好嗎XD17F 01/06 01:59
i9602283: 看不懂,推18F 01/06 02:20
ken841520: 推,我開始覺得我4年CS白唸了QQ19F 01/06 02:25
jk21234: 我大二計算機結構交作業就是用rdtsc提供cpu cache資料20F 01/06 02:28
Winux: 比較好奇這麼久的bug 怎麼會到現在才被找出來?
是因為這方法太蠢嗎?22F 01/06 02:29
ctes940008: 推24F 01/06 02:34
cory8249: 推    Archi / OS 都快忘光了  QQ25F 01/06 02:36
jk21234: 想出2的例子的是好幾年前就有但這樣只能分析系統虛擬機中 別人正在跑什麼程式 或者小機率猜正在加密的資料可能是什麼
直到3的例子成立才會變資料能被分析走26F 01/06 02:39
commandoEX: 所以是Intel挖坑自己跳30F 01/06 02:45
bf000777966: RDTSC本來就不該讓低權限的APP使用,CPUID也是
難怪有人說X86是個爛架構
剛剛查了一下資料,RDTSC指令是可以禁止在CPL=3執行的,其實只要OS把這個指令禁止掉所有的問題不都解決了嗎?31F 01/06 03:23
pimachu: 快推 不然會被發現看不懂36F 01/06 04:03
htps0763: 感覺一直以來x86為相容性付出的成本太大了37F 01/06 04:13
NCTUFAIWEN: 推38F 01/06 04:58
quamtum: mem[mem[a+b]可以直接一條執行代表btb一猜錯馬上有cache資料洩漏問題,包括in order cpu39F 01/06 07:04
weichen5566: 推了表示懂41F 01/06 07:05
quamtum: 像clflush是cpl3可跑但wbinvd 只有cpl0可跑也蠻怪42F 01/06 07:07
Jay915: 推43F 01/06 08:01
ken720331: 推44F 01/06 08:14
mensalord: 推了表示跨謀45F 01/06 08:27
DKPCOFGS: 有推有懂46F 01/06 09:24
b09134: 我懂我懂…47F 01/06 09:32
spfy: 沒錯 跟我想的...算了48F 01/06 10:18
kipi91718: 感謝分享,又更了解一些了! 這應該能拿到CS課堂上講49F 01/06 11:22
c60203: 略懂略懂 可是電蝦點在?( 被毆50F 01/06 11:49
attis: 其實跟x86沒有關係 純粹是為了快略過檢查導致這個漏洞 不然x86的amd沒這個問題 risc的arm和A系列晶片有這個問題51F 01/06 13:12
chinfu1222: 趕快推 不然人家以為你文組看不懂54F 01/06 13:22
dustlike: 只能推了55F 01/06 13:46
kqalea: 最主要是cache的演算法問題
不管是x86 ARM powerpc 或是各種DSP RISC
cache 演算法不外乎就是random , round robin 之類因為ASIC成本考量大部分人不可能實作一個很複雜的演算法去增加那1~5%效能或是安全性check
最有效簡單的方式就是一個夠大夠快fetch的cache
用指令架構上的做法確保cache的安全性是合乎邏輯的AMD跟ARM這次不受災的原因在於他們很早就用比較新的演算法去處理cache coherence的問題56F 01/06 14:42
kuma660224: intel工程師睡了很久。65F 01/06 14:58
kqalea: 若是相信陰謀論的話這個印該是intel故意不修復的66F 01/06 15:01
hms5232: 資管系路過 到2就看不太懂了zz67F 01/06 16:53
SULAjardin: 理工組推 (前3行都看DER懂)68F 01/06 22:01
eva19452002: 靠北哦,這串討論串到底是有多少神人啊?69F 01/06 23:00
leeart20: 看不懂的死肥宅來推…(滾走)70F 01/07 00:52
david7112123: 推71F 01/07 01:00
fuhu66: 靠,最近計算機結構大爆發72F 01/07 04:57

--