????分享一下讀過(guò)的最新的fuzzing論文，目前是用Xmind記錄的，可能過(guò)于詳細(xì)了些，未來(lái)會(huì)更加精簡(jiǎn)一點(diǎn)，以博客的方式來(lái)進(jìn)行總結(jié)，思維導(dǎo)圖和論文原文見(jiàn)[我的github](https://github.com/bsauce/Some-Papers-About-Fuzzing)。

? ? 最近開(kāi)始有人關(guān)注我的總結(jié)，索性我就將之前看的論文都整理一下放上來(lái)。其實(shí)本文在github上已經(jīng)半年沒(méi)有更新了，主要是精力有限，沒(méi)有時(shí)間去讀那么多的論文，真心希望有志同道合、愿意分享的朋友和我一起來(lái)整理四大安全頂會(huì)的論文，最好是做成CTF WIKI那種東西，方便所有人一起閱讀，有感興趣的師傅可以聯(lián)系我，我們?cè)趃ithub上弄一個(gè)總結(jié)。分類方法是按專題和會(huì)議類型，內(nèi)容是對(duì)論文的簡(jiǎn)短總結(jié)和xmind思維導(dǎo)圖。

? ? 有感興趣的師傅可以聯(lián)系我?。。。?/p>

? 簡(jiǎn)書網(wǎng)址：http://www.itdecent.cn/u/a12c5b882be2

?github網(wǎng)址：https://github.com/bsauce/Some-Papers-About-Fuzzing

灰盒測(cè)試

0-fuzz綜述—Fuzzing：State of the Art

????看完綜述，感覺(jué)還有好多文章值得看看，如下。

fuzz類：

SAGE[14]目標(biāo)：windows x86大型讀文件應(yīng)用（如文件解析器，視頻播放器，圖片處理器）。原理：concolic execution+啟發(fā)式搜索算法。

Buzzfuzz[46]首先插樁，然后污點(diǎn)分析，得到影響“攻擊點(diǎn)”（如庫(kù)調(diào)用）的輸入中的變異位置，接著變異相應(yīng)位置來(lái)生成新的測(cè)試用例，最后執(zhí)行測(cè)試用例觀察是否崩潰。

TaintScope36針對(duì)checksum采用污點(diǎn)分析+預(yù)定義規(guī)則，檢測(cè)checksum點(diǎn)和熱輸入字節(jié)（能污染目標(biāo)程序的API），然后變異熱字節(jié)并修改checksum點(diǎn)以通過(guò)完整性校驗(yàn)，最后利用SE+約束求解來(lái)修復(fù)測(cè)試用例的校驗(yàn)值，并使程序崩潰。

內(nèi)核fuzz

Trinity[32]Syzkaller[15]IOCTL Fuzzer[148]KernelAFL（kAFL）[149]CAB-Fuzz[150]

程序分析技術(shù)—基礎(chǔ)

污點(diǎn)分析-[105]符號(hào)執(zhí)行-[39]

1.VUzzer Application-aware Evolutionary Fuzzing-ndss2017

總體：VUzzer—開(kāi)源，二進(jìn)制文件（不需源碼），灰盒-基于代碼覆蓋-基于變異，充分利用程序特性（DF/CF）來(lái)優(yōu)化變異，利用控制流指定路徑優(yōu)先級(jí)：識(shí)別error-handling塊，深路優(yōu)先，常路滯后；利用數(shù)據(jù)流特性（DTA分析）可確定變異哪些字節(jié)+如何變異？?jī)蓚€(gè)亮點(diǎn)：一是路徑權(quán)重計(jì)算，二是magic bytes策略。

基于：動(dòng)態(tài)污點(diǎn)分析基于DataTracker，插樁基于Pin，靜態(tài)分析基于IDA腳本。輕型的程序分析

具體：改進(jìn)AFL的反饋循環(huán)，給interesting路徑更大的權(quán)重，亮點(diǎn)一在于路徑權(quán)重的計(jì)算?；贛arkov模型，塊之間轉(zhuǎn)移概率獨(dú)立，即基本塊的概率只和相連塊有關(guān)，概率的倒數(shù)就是塊權(quán)重，error-handling塊權(quán)重為負(fù)值，路徑上各塊權(quán)重之和（取對(duì)數(shù)）即為路徑權(quán)重，權(quán)重越大的路徑對(duì)應(yīng)的輸入在下一輪變異中優(yōu)先級(jí)越高。缺點(diǎn)是error-handling塊的識(shí)別依賴種子輸入的質(zhì)量，數(shù)量要多且不會(huì)走error-handling塊。亮點(diǎn)二是通過(guò)Pin插樁識(shí)別magic bytes（DTA分析），在cmp/lea處插樁，解決where/what問(wèn)題。

缺點(diǎn)：error-handling代碼尋找極度依賴種子輸入的有效性；若某字節(jié)被多個(gè)輸入字節(jié)所影響，而不是連續(xù)的magic bytes，則magic bytes失效；不適用于菜單式程序或交互式程序。

2-AFLFast_Coverage-based Greybox Fuzzing as Markov Chain-CCS2016

????????AFLFast—開(kāi)源，灰盒fuzzing，基于AFL。目標(biāo)：AFL花大量時(shí)間執(zhí)行高頻路徑，改進(jìn)AFL，使其更多的fuzz低頻路徑。只能提高效率，而不能提高效果。改進(jìn)AFL的ChooseNext()和AssignEnergy()函數(shù)，ChooseNext()（搜索策略）優(yōu)先選擇較少被選擇的或低頻路徑的輸入，變異次數(shù)由能量決定，能量調(diào)度策略是，被選次數(shù)更多的和被執(zhí)行次數(shù)較少的（低頻路徑）能量較高。

可了解的工具：

QEMU-運(yùn)行時(shí)插樁AFLDynInst [20]-將listing 1代碼直接插入二進(jìn)制文件。 [20] Tool. A binary instrumentation. https://github.com/vrtadmin/moow/tree/master/a-dyninst. Accessed:2016-05-13.

Markov鏈規(guī)律：狀態(tài)之間的轉(zhuǎn)換概率tp只取決于當(dāng)前狀態(tài)，而不是當(dāng)前狀態(tài)的路徑。只能提高效率，而不能提高效果。

3-CollAFL：Path Sensitive Fuzzing-SP-2018

亮點(diǎn)是解決hash碰撞問(wèn)題并保持較低插樁開(kāi)銷，提出3種種子選取策略。

????cur_location = <COMPILE_TIME_RANDOM>;??

????shared_mem[cur_location ^ prev_location]++;??

? ? prev_location = cur_location >> 1;

（1）解決hash碰撞問(wèn)題（對(duì)于多前驅(qū)中的無(wú)碰撞塊，F(xiàn)mul(cur,prev)=(cur>>x)^(prev>>y)+z；對(duì)于多前驅(qū)中的碰撞塊，F(xiàn)hash(cur,prev)=hash_table_lookup(cur,prev)采用離線查表的方式；對(duì)于單前驅(qū)塊，hash值可任意指定，硬編碼。），采用貪心搜索確定最優(yōu)xyz的值，若不能解決碰撞，可將bitmap大小擴(kuò)充至128K。

（2）種子選取策略，路徑上未探索相鄰分支數(shù)、未探索孫子數(shù)、內(nèi)存訪問(wèn)操作數(shù)大的優(yōu)先變異，前兩種策略效果最好。

afl-collect和AddressSanitizer[32]（檢測(cè)緩沖區(qū)溢出和UAF）可以對(duì)crash進(jìn)行去重。

未來(lái)方向：結(jié)合AdressSanitizer，檢測(cè)非crash漏洞；現(xiàn)在依賴源碼，未來(lái)在二進(jìn)制程序上插樁。

4-Angora：Efficient Fuzzing by principled Search

?? ? ? ? Angora開(kāi)源，亮點(diǎn)是用梯度下降方法（機(jī)器學(xué)習(xí)）求解約束條件，而不用符號(hào)執(zhí)行的求解器

?? ? ? ? Angora屬于灰盒fuzzing（需要源碼），有四點(diǎn)創(chuàng)新：采用上下文敏感的分支計(jì)數(shù)，對(duì)同一函數(shù)的不同調(diào)用算作不同分支，增大代碼覆蓋率；采用字節(jié)級(jí)污點(diǎn)追蹤，只變異影響路徑走向的字節(jié)，樹(shù)結(jié)構(gòu)存儲(chǔ)污點(diǎn)標(biāo)記；變異方法是基于梯度下降方法（將判斷條件轉(zhuǎn)化為f(x)相關(guān)的函數(shù)），走未探索分支；有長(zhǎng)度和類型推斷技術(shù)，長(zhǎng)度根據(jù)輸入字節(jié)數(shù)與1248匹配，類型是根據(jù)指令的操作類型；輸入長(zhǎng)度探索是根據(jù)插樁確定，若read返回值參與條件判斷，可適當(dāng)調(diào)整輸入字節(jié)。

?? ? ? ? 基于工具：插樁-LLVMPass；污點(diǎn)追蹤-DataFlowSanitizer

5.Steelix：Program-State Based Binary Fuzzing-FSE 2017

????????? Steelix—開(kāi)源，針對(duì)binary，基于AFL 2.33b，基于灰盒變異fuzzing，基于代碼覆蓋。動(dòng)態(tài)插樁是基于Dyninst，靜態(tài)分析基于IDAPython。 模仿VUzzer。 目標(biāo)是解決magic bytes比較問(wèn)題，使用輕量級(jí)的靜態(tài)分析收集interesting的比較（test/cmp/strcmp），利用二進(jìn)制插樁獲取運(yùn)行時(shí)的比較值、生成運(yùn)行時(shí)的比較進(jìn)展信息（若匹配到1字節(jié)，相鄰字節(jié)窮舉變異的啟發(fā)式策略）。缺點(diǎn)是不適用于不連續(xù)magic bytes和函數(shù)返回值比較（如hash值計(jì)算）。

6-AFLGo-Directed Greybox Fuzzing-CCS2017

引申學(xué)習(xí)：學(xué)LLVM，Adressanitizer

????????AFLGo——開(kāi)源，導(dǎo)向型灰盒fuzzing，給距離目標(biāo)近的種子更多能量，亮點(diǎn)是如何求種子到多個(gè)目標(biāo)的距離。缺點(diǎn)是需要外界輸入目標(biāo)，需要C源碼?；贏FL實(shí)現(xiàn)

7-Hawkeye-Towards a Desired Directed Grey-box Fuzzer-CCS2018

????????導(dǎo)向性灰盒fuzzer，需要源碼+目標(biāo)點(diǎn)，主要優(yōu)化了AFLGo（不僅考慮短路徑，也考慮能夠到達(dá)目標(biāo)點(diǎn)的長(zhǎng)路徑）。插樁基于LLVM，fuzz基于AFL，指針?lè)治龌诔涕g靜態(tài)數(shù)據(jù)流分析工具SVF[41]。 3個(gè)亮點(diǎn)，1是權(quán)衡短路徑與長(zhǎng)路徑的能量分配，覆蓋期望集（所有能到達(dá)目標(biāo)點(diǎn)的函數(shù)集）上更多函數(shù)的種子優(yōu)先變異，路徑越長(zhǎng)重合越多，分?jǐn)?shù)越高；2是適應(yīng)性變異策略，若seed到達(dá)目標(biāo)，細(xì)粒度變異增大，粗粒度變異下降；3是新種子優(yōu)先級(jí)排序，分3層存儲(chǔ)，若為新種子，且發(fā)現(xiàn)新邊、能量較高、可到達(dá)目標(biāo)點(diǎn)，則放第1層，否則放第2層，不為新種子則放第3層。

未來(lái)工作：實(shí)現(xiàn)binary fuzzing，目標(biāo)識(shí)別基于二進(jìn)制代碼匹配[947]，靜態(tài)分析基于IDA[20]，插樁基于Intel Pin[1]。

? 提出4個(gè)導(dǎo)向型fuzzer的特性并進(jìn)行改進(jìn)：考慮所有到達(dá)目標(biāo)點(diǎn)的路徑，不管長(zhǎng)短；平衡靜態(tài)分析的開(kāi)銷和實(shí)用性；合理分配能量；適應(yīng)性變異策略。

8.Evaluating Fuzz Testing-2018

????????調(diào)查32篇fuzz論文，研究如何設(shè)計(jì)fuzz實(shí)驗(yàn)才能得到可靠結(jié)果。

? ????a. 選取基準(zhǔn)算法

????? b. 選取測(cè)試目標(biāo)程序

????? c. 選取評(píng)測(cè)標(biāo)準(zhǔn)——發(fā)現(xiàn)bug數(shù)

????? d. 確定算法參數(shù)——seed選取、time(24h)

????? e. 多次測(cè)試-30次取平均

Crash去重方法

（1）Ground Truth：找到的bug數(shù)目

? ????修補(bǔ)對(duì)應(yīng)bug，看其他輸入還能否觸發(fā)crash，以確保唯一性

（2）AFL Coverage Profile

????? 若邊覆蓋（路徑）唯一，就判定該crash“unique”

（3）Stack hashes

????? 根據(jù)N層遞歸調(diào)用來(lái)區(qū)別漏洞。N：3-5，可快速比對(duì)漏洞

內(nèi)核fuzz

1.DIFUZE- Interface Aware Fuzzing for Kernel Drivers-CCS-2017

????????DIFUZE—開(kāi)源，需要源碼，接口感知型fuzzing—自動(dòng)靜態(tài)分析（先編譯成LLVM中間碼）驅(qū)動(dòng)號(hào)（Range Analyziz[52]收集有效驅(qū)動(dòng)號(hào)）、驅(qū)動(dòng)文件名、輸入?yún)?shù)的結(jié)構(gòu)，已整合到Syzkaller。流程：分析內(nèi)核源碼，收集接口信息（如有效ioctl號(hào)、參數(shù)結(jié)構(gòu)類型，采用LLVM 3.8實(shí)現(xiàn)），然后合成這些結(jié)構(gòu)信息，發(fā)送給目標(biāo)設(shè)備。缺點(diǎn)：依賴內(nèi)核源碼

缺點(diǎn)：

? a. 早期就崩了，reboot，導(dǎo)致不能觸發(fā)更深的功能。 b. 不能收集結(jié)構(gòu)的復(fù)雜關(guān)系，eg，結(jié)構(gòu)的length區(qū)域決定了某緩沖區(qū)的size。

未來(lái)工作：加上覆蓋引導(dǎo)。想法：VEX中間代碼分析windows驅(qū)動(dòng)？

interface recovery主要包含以下步驟：

????（1）使用GCC及LLVM編譯kernel，用于靜態(tài)分析。

????（2）識(shí)別驅(qū)動(dòng)為處理交互創(chuàng)建的ioctl_handler函數(shù)。

????（3）在ioctl_handler函數(shù)中分析出設(shè)備名信息。

????（4）使用Range Analysis搜索判等表達(dá)式識(shí)別出command常量。

????（5）追蹤接受了用戶態(tài)參數(shù)的copy_from_user等方法，找到command可以對(duì)應(yīng)的結(jié)構(gòu)體名稱，為所有command建立結(jié)構(gòu)體對(duì)應(yīng)表。

????（6）搜索整個(gè)kernel代碼找到所有有效結(jié)構(gòu)體的定義，并轉(zhuǎn)換格式，記錄在xml中。

????（7）通過(guò)interface recovery后，作者能夠利用這樣有效的信息去生成有效合理的輸入。

2.kAFL- Hardware-Assisted Feedback Fuzzing for OS Kernels-USENIX-2017

????????kAFL—開(kāi)源，無(wú)需源碼，windows/linux/MacOS通用，基于AFL、VT-x、PT-Trace?；谟布o助反饋方式來(lái)fuzz閉源內(nèi)核。 利用兩個(gè)硬件特性：VT-x虛擬化技術(shù)；PT-Trace追蹤功能。第一種是用于提高虛擬化效率的技術(shù)，相較于傳統(tǒng)的模擬化，這種虛擬化使得VMM操作和控制VM時(shí)，將更加快速、可靠和安全。第二種PT追蹤技術(shù)，讓CPU可以搜集指令運(yùn)行的部分上下文信息，這些信息對(duì)于推測(cè)Fuzz輸入來(lái)說(shuō)十分重要。將這兩種技術(shù)與AFL相結(jié)合，實(shí)現(xiàn)kAFL。漏洞發(fā)現(xiàn)能力和效率都不錯(cuò)，附加開(kāi)銷很?。ㄐ∮?5%）。

VMM中可以分為3個(gè)模塊KVM，QEMU-PT和kAFL。VM又能分為Target Kernel和Agent。見(jiàn)Fig1-kAFL總體架構(gòu)。

????????-KVM中實(shí)現(xiàn)了PT追蹤功能，負(fù)責(zé)收集目標(biāo)內(nèi)核的運(yùn)行信息。

????????? -QEMU-PT除了作為KVM和kAFL交互的中間件之外，還有一個(gè)很重要的功能就是作為PT data的decoder。

????????? -kAFL就是Fuzz工具的邏輯部分了，整體設(shè)計(jì)實(shí)現(xiàn)上都借鑒了AFL的思路。會(huì)根據(jù)反饋結(jié)果更高效的生成下一次輸入。

? ? ? ? ?-Target Kernel就是目標(biāo)Kernel了，該工具對(duì)主流的操作系統(tǒng)都做了支持。

????????? -Agent同樣也作為一個(gè)交互的中間件，主要和目標(biāo)Kernel做一些交互操作，如掛載鏡像。

程序分析技術(shù)

1.AddressSanitizer：A Fast Address Sanity Checker-USENIX-2012

????????AddressSanitizer:源碼插樁，已整合到LLVM 3.1。（http://clang.llvm.org/docs/AddressSanitizer.html）。通過(guò)在用戶內(nèi)存（棧變量、全局變量、堆塊）周圍插入redzones，通過(guò)影子內(nèi)存（1字節(jié)影子內(nèi)存記錄8字節(jié)用戶空間，0表示都可訪問(wèn)，1-7表示前7字節(jié)可訪問(wèn)，負(fù)數(shù)表示不可訪問(wèn)）的記錄來(lái)檢查是否越界和UAF，堆檢測(cè)是通過(guò)替換malloc和free函數(shù)。

ASAN組成：

? a.插樁模塊：在load/store處檢查影子狀態(tài)shadow state以檢測(cè)越界訪問(wèn)；在棧/全局對(duì)象周圍創(chuàng)建毒區(qū)poisoned redzones（>=2^3字節(jié)，以檢測(cè)棧/全局變量的上溢和下溢）。

????????ShadowAddr = (Addr >> 3) + Offset;

????????k = *ShadowAddr;

????????if (k != 0 && ((Addr & 7) + AccessSize > k))

?????????????ReportAndCrash(Addr);

b.運(yùn)行庫(kù)：替換malloc/free及相關(guān)函數(shù)，在堆塊周圍創(chuàng)建毒區(qū)redzone(>=32字節(jié)，檢測(cè)堆溢出)，延遲釋放塊的再使用（檢測(cè)UAF），錯(cuò)誤報(bào)告。 缺點(diǎn)：信息泄露漏洞不能立即被發(fā)現(xiàn)，也即未初始化讀漏洞。 改進(jìn)想法：釋放后標(biāo)記為不可讀寫，若再次申請(qǐng)到剛釋放的塊，仍保持為不可讀，只有寫入后才能讀。

不足：

????????未初始化讀漏洞；未對(duì)齊越界訪問(wèn)漏洞；超長(zhǎng)越界訪問(wèn)（redzone太?。?。

對(duì)比工具：

????????Valgrind[21]/Dr.Memory[8]速度減慢20x至10x，能檢測(cè)未初始化讀和內(nèi)存泄露，不能檢測(cè)棧、全局變量越界訪問(wèn)。

2.All You Ever Wanted to Know About DTA and SE-Oakland-2010

????????主要內(nèi)容是采用SimpIL語(yǔ)言統(tǒng)一描述DTA和SE過(guò)程，并描述其中的挑戰(zhàn)。DTA的主要挑戰(zhàn)是地址也被污染，控制流被污染，去掉不必要的污染，檢測(cè)被攻擊的時(shí)機(jī)；SE的挑戰(zhàn)是符號(hào)化內(nèi)存地址（別名分析），執(zhí)行路徑選擇，符號(hào)化的跳轉(zhuǎn)地址（如jump tables），處理系統(tǒng)/庫(kù)調(diào)用，優(yōu)化性能，部分變量符號(hào)化mixed execution。

????DTA和SE主要用于未知漏洞檢測(cè)；自動(dòng)輸入篩選器生成（入侵檢測(cè)）；惡意軟件分析；測(cè)試樣例生成。