Re: [情報] Intel嚴重漏洞 OS更新將會降低效能

[jk21234 (BL2400PT真不錯)]

為什麼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
※ 文章網址: https://www.ptt.cc/bbs/PC_Shopping/M.1515169257.A.E56.html
推 kira925     : 推
推 hizerg      : 推
推 royroy666   : 先推
→ PlayStation3: JK神
推 Shauter     : JK最高
推 s25g5d4     : 推 JK 神
→ jk21234     : 3的描述有bug, X要是256 Byte的很多倍而且&X + 0
→ jk21234     : 該知道我簡化過不想修正回來了..
→ KotoriCute  : jk神！先推再說
推 ang728      : 好久沒推 先推再說
推 winiel559   : 推jk神
推 Windcws9Z   : 推
推 jior        : 快推，免得人家知道我是文組!!
推 alexgame01  : 推
推 saito2190   : 先推，資工肥宅快要看不懂了
推 tyler930030 : 我也那麼認為呢
推 ccc73123    : 這個理組也不一定看得懂好嗎XD
推 i9602283    : 看不懂，推
推 ken841520   : 推，我開始覺得我4年CS白唸了QQ
→ jk21234     : 我大二計算機結構交作業就是用rdtsc提供cpu cache
→ jk21234     : 資料
推 Winux       : 比較好奇這麼久的bug 怎麼會到現在才被找出來？
→ Winux       : 是因為這方法太蠢嗎？
推 ctes940008  : 推
推 cory8249    : 推    Archi / OS 都快忘光了  QQ
→ jk21234     : 想出2的例子的是好幾年前就有但這樣只能分析系統虛
→ jk21234     : 擬機中 別人正在跑什麼程式 或者小機率猜正在加密
→ jk21234     : 的資料可能是什麼
→ jk21234     : 直到3的例子成立才會變資料能被分析走
→ commandoEX  : 所以是Intel挖坑自己跳
推 bf000777966 : RDTSC本來就不該讓低權限的APP使用，CPUID也是
→ bf000777966 : 難怪有人說X86是個爛架構
推 bf000777966 : 剛剛查了一下資料，RDTSC指令是可以禁止在CPL=3執
→ bf000777966 : 行的，其實只要OS把這個指令禁止掉所有的問題不都
→ bf000777966 : 解決了嗎？
推 pimachu     : 快推 不然會被發現看不懂
推 htps0763    : 感覺一直以來x86為相容性付出的成本太大了
推 NCTUFAIWEN  : 推
→ quamtum     : mem[mem[a+b]可以直接一條執行代表btb一猜錯馬上有
→ quamtum     : cache資料洩漏問題，包括in order cpu
推 weichen5566 : 推了表示懂
→ quamtum     : 像clflush是cpl3可跑但wbinvd 只有cpl0可跑也蠻怪
推 Jay915      : 推
推 ken720331   : 推
→ mensalord   : 推了表示跨謀
推 DKPCOFGS    : 有推有懂
推 b09134      : 我懂我懂…
推 spfy        : 沒錯 跟我想的...算了
推 kipi91718   : 感謝分享，又更了解一些了! 這應該能拿到CS課堂上講
推 c60203      : 略懂略懂 可是電蝦點在？（ 被毆
推 attis       : 其實跟x86沒有關係 純粹是為了快略過檢查導致這個漏
→ attis       : 洞 不然x86的amd沒這個問題 risc的arm和A系列晶片有
→ attis       : 這個問題
→ chinfu1222  : 趕快推 不然人家以為你文組看不懂
推 dustlike    : 只能推了
推 kqalea      : 最主要是cache的演算法問題
→ kqalea      : 不管是x86 ARM powerpc 或是各種DSP RISC
→ kqalea      : cache 演算法不外乎就是random , round robin 之類
→ kqalea      : 因為ASIC成本考量大部分人不可能實作一個很複雜的
→ kqalea      : 演算法去增加那1~5%效能或是安全性check
→ kqalea      : 最有效簡單的方式就是一個夠大夠快fetch的cache
→ kqalea      : 用指令架構上的做法確保cache的安全性是合乎邏輯的
→ kqalea      : AMD跟ARM這次不受災的原因在於他們很早就用比較新的
→ kqalea      : 演算法去處理cache coherence的問題
→ kuma660224  : intel工程師睡了很久。
推 kqalea      : 若是相信陰謀論的話這個印該是intel故意不修復的
推 hms5232     : 資管系路過 到2就看不太懂了zz
推 SULAjardin  : 理工組推 (前3行都看DER懂)
→ eva19452002 : 靠北哦，這串討論串到底是有多少神人啊？
推 leeart20    : 看不懂的死肥宅來推…（滾走）
推 david7112123: 推
推 fuhu66      : 靠，最近計算機結構大爆發
推 vvind       : 這篇看不懂
推 a1u1usul3   : 這篇講得非常詳細且清楚，感謝
推 leo0519     : 台大計系先推