1. 摘要
目標(biāo)：挖掘競爭漏洞，如CVE-2016-8655, CVE-2017-2636, CVE-2017-17712。
問題：race漏洞受到系統(tǒng)不確定行為的影響，如線程調(diào)度與同步機(jī)制。
技術(shù)：靜態(tài)分析定位可能引發(fā)競爭的代碼；確定性的線程交錯技術(shù)，控制線程調(diào)度，提供準(zhǔn)確的并行執(zhí)行信息，降低不確定性。
對比：Syzkaller[42]，SKI[16]。
結(jié)果：發(fā)現(xiàn)30個競爭漏洞，16個已確認(rèn)。
2. 問題與設(shè)計需求
（1）數(shù)據(jù)競爭定義
????若兩條指令滿足以下條件則為數(shù)據(jù)競爭：
????????????a.訪問的內(nèi)存地址相同
????????????b.至少其中一條指令是對內(nèi)存的寫
????????????c.兩條指令可以并發(fā)執(zhí)行
（2）標(biāo)記
（3）競爭案例—CVE-2017-2636
? ??????兩個線程分別調(diào)用ioctl(fd,TCFLSH)和write(fd,…)，對變量n_hdlc->tbuf的并發(fā)讀寫導(dǎo)致競爭（n_hdlc->tbuf = NULL;與tbuf = n_hdlc->tbuf;），該內(nèi)存地址在free_list中保存了兩次，最后ioctl(fd,TCXONC)將導(dǎo)致double free。
（4）設(shè)計要求
R1——找到執(zhí)行RacePair_cand的輸入程序。即找到一個多線程的用戶態(tài)程序，每個線程能夠在內(nèi)核態(tài)分別執(zhí)行到RacePair_cand的指令。需求1把問題做了簡化，并不去考慮并行執(zhí)行的問題，就不用考慮線程調(diào)度對分析的影響。
R2——根據(jù)R1輸入程序，找到并發(fā)執(zhí)行RacePair_cand的線程執(zhí)行序列。需求2主要是去尋找一個交錯執(zhí)行的線程調(diào)度方案，使得RacePair_cand的指令能并行執(zhí)行。
3.?設(shè)計
? ? 整體流程如圖：
3.1靜態(tài)分析—識別RacePair_cand
方法：指向分析（尋找內(nèi)核中對同一個結(jié)構(gòu)體的內(nèi)存訪問），但限制是準(zhǔn)確率與性能，需要精確的CF/DF信息（運(yùn)行時更準(zhǔn)確）和并發(fā)信息（受到調(diào)度和同步原語的影響）。指向分析的時間開銷是O(n^3)。
Razzer改進(jìn)
（1）準(zhǔn)確性
????????采用指向分析得到近似的RacePair_cand（上下文敏感、流敏感、區(qū)域敏感），后續(xù)通過動態(tài)分析來確認(rèn)。去除不會引起競爭的指令，例如訪問結(jié)構(gòu)中不同變量。
（2）性能
????????分部分分析，減小分析的代碼量。作者按目錄結(jié)構(gòu)劃分模塊，如kernel, mm, fs, drivers，但有些模塊如fs和net/core會被每個模塊調(diào)用。
缺點(diǎn)：未分析同步原語如read_lock(), br_read_lock(), spin_lock_irqsave(), up()，該分析可以排除不會引發(fā)競爭的內(nèi)存對。
3.2 線程調(diào)度-hypervisor
方法：待Fuzz的內(nèi)核運(yùn)行在虛擬化的環(huán)境中，為了控制虛擬CPU的調(diào)度，作者修改了虛擬環(huán)境的Hypervisor，增加了三個功能。
（1）為每個虛擬CPU設(shè)置斷點(diǎn)
超級調(diào)用接口：hcall_set_bp(vCPU_TD, guest_addr)。由虛擬機(jī)guest kernel調(diào)用，監(jiān)管者收到后在guest_addr地址下硬件斷點(diǎn)。
兩點(diǎn)要求：
????????a.準(zhǔn)確設(shè)置每個vCPU的斷點(diǎn)：斷點(diǎn)地址存入virtualized debug register，每個vCPU有一個VDR，就能保證只有相關(guān)vCPU執(zhí)行時才會觸發(fā)斷點(diǎn)；設(shè)置Intel VT-x中Virtual Machine Control Structure (VMCS)的中斷表的相應(yīng)位（硬件斷點(diǎn)中斷），就能保證VMEXIT事件首先交給監(jiān)管器而非guest kernel。
????????b.確定斷點(diǎn)是否被指定內(nèi)核線程觸發(fā)：有可能是其他無關(guān)線程觸發(fā)，利用virtual machine introspection（VMI）獲取內(nèi)核線程上下文，找到線程號，也即通過thread_info -> task_struct -> 內(nèi)核線程號，確定是否被指定內(nèi)核線程觸發(fā)。
（2）控制線程執(zhí)行順序
????????Hcall_set_order(vCPU_ID)，恢復(fù)指定線程執(zhí)行，不同的執(zhí)行順序決定是否觸發(fā)錯誤。
（3）檢測競爭結(jié)果
檢查競爭指令訪問地址是否相同，相同則為RacePair_true。
3.3 多線程fuzz
（1）單線程fuzzing
目的：生成單線程程序，執(zhí)行RacePair_cand。
generator：生成單線程用戶程序P_st—隨機(jī)syscall序列。
????????????????兩種策略：一是generation，使用syzkaller[42]定義的syscall語法（含參數(shù)值范圍），生成隨機(jī)調(diào)用序列，傳遞調(diào)用參數(shù)；二是mutation，對已有的P_st進(jìn)行drop/insert/change。
executor：執(zhí)行P_st。
????????????a.用KCov[3]收集執(zhí)行覆蓋路徑，看是否有2個syscall執(zhí)行RacePair_cand指令；
????????????b.記錄這2個syscall+RacePair_cand在syscall中地址+P_st，發(fā)送給多線程fuzzing。
? ? ? ? ? ? 反饋：若某個P_st產(chǎn)生新的路徑覆蓋，則作為反饋加入到變異種子隊列。
（2）多線程fuzzing
目的：生成多線程程序，觸發(fā)競爭。
generator：P_st→P_mt，轉(zhuǎn)化為一個多線程版本P_mt。在轉(zhuǎn)換過程中還會進(jìn)行一些插樁，與Hypervisor協(xié)作控制程序的調(diào)度。輸入P_st，i（syscall下標(biāo)），j，RP_i，RP_j（競爭指令地址）。
executor：運(yùn)行P_mt，檢測RacePair_cand是否觸發(fā)競爭。
????????????判斷條件：a.捕捉到2個斷點(diǎn)RacePair_cand；b. RacePair_cand指令訪問地址相同。
????????????razzer競爭檢查：使用lockdep[29]，KASAN[2]，或手動插入assertion。
????????????反饋：導(dǎo)致競爭的P_mt用于進(jìn)一步變異，以觸發(fā)崩潰。
4.實現(xiàn)
4.1 靜態(tài)分析
????????基于LLVM+SVF[39]。
????????改進(jìn)SVF—指向分析：處理內(nèi)核內(nèi)存分配/釋放；處理堆/全局結(jié)構(gòu)中的非指針變量。
????????輸出：RacePair_cand（含源文件名+行號），編譯利用GCC的調(diào)試信息將之轉(zhuǎn)化為二進(jìn)制地址。
4.2 hypervisor
????????基于QEMU+KVM（kernel-based Virtual Machine）硬件加速；
????????Capstone[1]反匯編來檢查RacePair_cand；
????????fuzzer基于Syzkaller[42]。
4.3 代碼量
????????SVF靜態(tài)分析—638 LoC C++；
????????QEMU實現(xiàn)hypervisor 652 LoC c；
????????Syzkaller實現(xiàn)fuzzer 6403 LoC Go和286 LoC。
5.評價
（1）發(fā)現(xiàn)的競爭漏洞，競爭漏洞列表見Fig6。
????????能發(fā)現(xiàn)很老的洞，2007，見Fig8。
????????Report對于漏洞修復(fù)幫助很大
（2）靜態(tài)分析有效性
????????分部分分析效率很高見Fig9，整體分析耗時7天。
????????RacePair_cand有效性，有效引導(dǎo)到低于0.1%的可疑競爭點(diǎn)。
（3）hypervisor性能開銷
????????hypercall開銷很小，見Fig12。
（4）與syzkaller/SKI工具進(jìn)行比較
????????找單線程輸入程序：執(zhí)行速度慢于syzkaller，但找有害競爭快于syzkaller。
????????找多線程交錯程序：由于SKI不開源，所以根據(jù)SKI隨機(jī)線程交錯特性實現(xiàn)SKI_Emu—修改Razzer的多線程fuzzing部分（不使用hypercall），效率明顯高于SKI。
6. 未來工作
（1）優(yōu)化靜態(tài)分析
????????本文假設(shè)不同內(nèi)核模塊之間很少有競爭，分部分分析導(dǎo)致錯過很多RacePair_cand；提高靜態(tài)分析的準(zhǔn)確性，以識別不會競爭的指令對，可分析同步原語[14,41]（如read_lock(), br_read_lock(), spin_lock_irqsave(), up()，該分析可以排除不會引發(fā)競爭的內(nèi)存對）。
（2）擴(kuò)展性
????????移植到別的OS，如Windows/MacOSX/FreeBSD。
????????擴(kuò)展到用戶程序分析，用戶程序不需要其他變異策略，因為用戶程序競爭和內(nèi)核不一樣，只要發(fā)生競爭都算作漏洞。
