什么是Fuzz?
嘛這篇blog 還是會是一篇和計(jì)算機(jī)相關(guān)的Blog, 希望有機(jī)會我也能寫一些和上面圖里的Fuzzer相關(guān)的文章hhhhh
如何保證程序的正確性？
相信每一個(gè)程序員都會因?yàn)檫@個(gè)問題而感到困擾。我在雪城學(xué)到最多的一點(diǎn)就是行嗤，正確是需要代價(jià)的
這一點(diǎn)其實(shí)在生活中或者工作中被我們常常忽視楚里， 我們用大量的時(shí)間去學(xué)習(xí)開發(fā)程序但是大多數(shù)人并沒有認(rèn)識如何向別人證明你的程序是正確的累铅。 而在計(jì)算機(jī)科學(xué)中，這種昂貴的正確性給了很多研究者funding。
程序無非是符號運(yùn)算冒萄， 有一種做法是，使用邏輯學(xué)數(shù)學(xué)工具橙数，抽象出我們使用的編程語言的語義尊流，然后通過數(shù)學(xué)的方式去證明你的程序是正確的， 這是一種非常嚴(yán)謹(jǐn)?shù)姆绞剑?被稱作 形式驗(yàn)證 灯帮。 這種方式聽起來很美好，但是這種正確卻是有極其巨大的代價(jià)的， 通常蛮浑，證明一個(gè)程序正確需要的時(shí)間达舒，人數(shù)是編寫這個(gè)程序的10倍以上。 這對于很多開發(fā)者和團(tuán)隊(duì)來說往往是不能接受的腻贰，而且世界上可能也并沒有這么多的Proof Engineer 給你去招聘吁恍。
還有一種做法，使用一些簡化的語義播演， 或者說冀瓦，把你程序中的一些重要的性質(zhì)單獨(dú)拿出來研究，比如我們只關(guān)注和用戶輸入輸相關(guān)的性質(zhì)（taint analysis）写烤。 這種做法的本質(zhì)(在一些流派看來)是把程序的執(zhí)行通過某種數(shù)學(xué)映射翼闽，映射到一比較簡單，并且具有單調(diào)性質(zhì)的執(zhí)行上洲炊。這種方法叫做 程序分析感局。
不論是程序分析還是形式驗(yàn)證都是非常嚴(yán)謹(jǐn)?shù)姆椒ǎ?他們本質(zhì)都是使用數(shù)學(xué)的性質(zhì)去證明和驗(yàn)證分析一個(gè)程序尼啡。也就是說他們非常非常的注重Soundness.
但是上面說的方法都有一個(gè)致命的缺點(diǎn)：他們都需要在你知道程序源代碼。這么說甚至還不準(zhǔn)確蓝厌。你不能只是“知道”玄叠，你必須對這段代碼的理解非常非常的深刻。事實(shí)情況是拓提，對大多數(shù)人來說读恃，自己的代碼往往都無法做到徹底清晰，時(shí)常過幾天就不知道自己之前寫的啥玩意代态，對于自己使用的程序語言的性質(zhì)往往都一知半解寺惫，更不要說抽象出程序的語義了。
這些方法和其他的一些方法比如符號執(zhí)行(symbolic execution) 本質(zhì)上都屬于白盒方法蹦疑。
如果我們對程序一無所知西雀，那么其實(shí)也是有辦法的。比如絕大多數(shù)的研發(fā)團(tuán)隊(duì)都會有配套的測試團(tuán)隊(duì)歉摧。對于測試工程師來說艇肴， 他們并不編寫程序，也不了解程序叁温，他們只關(guān)心程序的輸入和輸出再悼， 這種方法屬于黑盒方法。傳統(tǒng)測試是一種非常不嚴(yán)謹(jǐn)?shù)姆椒ㄏサ词故峭ㄟ^了測試冲九，你的程序大概率依然是千瘡百孔的。 這也是為上程序員都要花大量的時(shí)間在debug上跟束。莺奸。。冀宴。
上面提到的這些驗(yàn)證程序正確的方法想必對于大多數(shù)人都是聽說過或者使用過的灭贷。 那么有沒有一種能夠介于白盒和黑盒之間的方法呢？
當(dāng)然是有的
同時(shí)對源代碼和程序的輸入動手腳略贮！今天我要介紹的灰盒Fuzz就是這種思想的一種體現(xiàn)甚疟。Fuzzer通過修改源代碼/二進(jìn)制程序的方式，插入一些探針刨肃，通過這些探針來了解程序運(yùn)行過程中一些性質(zhì)古拴，比如程序的控制流/數(shù)據(jù)流信息。其實(shí)可以說是一些動態(tài)分析的手段真友。在獲取了這些信息后黄痪，以此來評價(jià)測試用例的“好壞”， 通過這種反饋機(jī)制盔然， 再對輸入的測試用例進(jìn)行變異(mutation)桅打， 進(jìn)而不斷的自動生成大量的測試用例是嗜，盡可能的去觸發(fā)程序崩潰。以此來找到藏在程序中的bug挺尾。
Fuzz測試器
一個(gè)Fuzz測試器從總體結(jié)構(gòu)上可以分為前端鹅搪，后端，F(xiàn)uzz算法三個(gè)部分遭铺。前端部分包括和測試用例相關(guān)的部分丽柿， 而后端部分則是包含和被測試程序源代碼相關(guān)的部分。
先從后端部分開始說吧魂挂。
Fuzzer后端的主要工作是插入指令(instrumentation). 之前說了灰盒fuzzer是需要知道程序的源代碼的甫题，并且會修改程序的代碼，但是我們又不希望在測試的過程中去深入了解代碼本身寫了什么涂召。 一種很直接的想法就是在編譯器上動手腳坠非。 比如在編譯的時(shí)候增加一道llvm pass，或者修改as匯編器果正， 在生成匯編的時(shí)候插入一些我們需要用的和內(nèi)存炎码，控制流相關(guān)的指令，收集我們要的信息然后輸出到文件或者共享內(nèi)存之類的地方秋泳，讓fuzzer程序能夠閱讀到這些信息潦闲。
fuzzer的前端部分一般主要包含3個(gè)重要的組成部分（有的fuzz器可能只有其中的兩個(gè)）。 讓fuzzer能夠不斷的生成新測試用例的核心部分變異器(mutator), 控制生成的測試用例長度的修剪器(trimer), 和生成初始測試用例的seed/cropus生成器轮锥，(cropus只是在fuzzer界比較常用的一個(gè)稱呼seed初始測試用例的名詞)矫钓。其中最最重要的就是mutator要尔，mutator一般來說是一個(gè)隨機(jī)程序舍杜， 根據(jù)一定的規(guī)則對測試用例進(jìn)行隨機(jī)變異。比如赵辕，每6個(gè)bit取一次反既绩，插入一些奇怪的int值之類的。
Fuzz算法部分其實(shí)反而是一個(gè)沒有那么多變化的部分还惠∷俏眨總的來說，fuzz算法都是一些類似遺傳算法的啟發(fā)式的算法蚕键。他們一般會對測試用例和程序之間的關(guān)系給出一個(gè)基本的假設(shè)救欧，然后fuzzer在這種方向上，根據(jù)后端給出的反饋數(shù)據(jù)锣光，給前端的每一次mutation進(jìn)行打分笆怠，保留優(yōu)秀的變異， 去除不良的變異誊爹，嘗試的去學(xué)習(xí)什么是一個(gè)更加容易crash程序的mutation蹬刷。一般來說這種打分機(jī)制會會越來越接近真實(shí)的程序輸入瓢捉。比如對于一個(gè)jpg處理程序， 初始的seed很可能只有一和hello world字符串办成，但是fuzz算法可以通過不斷學(xué)習(xí)最后讓測試用例變異成真正的jpg格式.
有人是不是很想說這個(gè)和神經(jīng)網(wǎng)絡(luò)泡态，人工智能很像可以用AI方法啥的。
然而遺憾的是迂卢。Fuzz算法和AI風(fēng)馬牛不相及某弦，甚至我覺得是完全相反的追求。Fuzz算法的策略是固定的而克，也就是說我們預(yù)先已經(jīng)假設(shè)好了什么樣的mutation是好的刀崖，而現(xiàn)在的AI大部分是希望能去學(xué)習(xí)得到什么樣的是好的策略，AI往往需要辦法去學(xué)習(xí)得到一個(gè)非常復(fù)雜的規(guī)則拍摇，比如一個(gè)巨大的特征矩陣亮钦。但是一個(gè)優(yōu)秀的fuzz算法必須是非常簡潔，甚至是非常粗糙的充活。因?yàn)閒uzz器的算法部分非常追求極致的效率蜂莉，甚至對于每個(gè)bit比較的性能都非常的計(jì)較。因?yàn)槌绦虻倪壿嫷膹?fù)雜性往往遠(yuǎn)超程序員的想象混卵，如果你做過SE,或者使用過程序分析的工具映穗，你就會很明白，稍微精度高一些的工具對時(shí)間復(fù)雜度的變化根本不是幾倍或者幾十倍的區(qū)別幕随，是直接從多項(xiàng)式P時(shí)間退化到NP的差距蚁滋。所以Fuzz的哲學(xué)就是，徹底放棄精度赘淮，用海量的測試來來代替辕录。一個(gè)Fuzzer迭代周期很可能在12小時(shí)以上，一次常規(guī)的fuzz測試往往需要10個(gè)以上的迭代周期梢卸，稍微復(fù)雜一點(diǎn)就會把幾天的工作變成幾個(gè)周走诞。。蛤高。
覆蓋率導(dǎo)向Fuzz(Coverage Guided Fuzz)
目前最流行的Fuzz工具毫無疑問是AFL, 全名叫American fuzzy lop蚣旱。
反正是很草的一個(gè)名字.
當(dāng)然LLVM宇宙肯定是有自己的fuzz工具的叫libFuzzer.
這兩種非常流行的fuzz測試工具都屬于覆蓋率導(dǎo)向Fuzz。他們的Fuzz算法部分和后端部分本質(zhì)都是一樣的戴陡，即認(rèn)為塞绿，如果想要生成crash程序的變異，那生成的變異就要盡可能的去覆蓋新的程序Control Flow Path恤批。這樣從總體來說异吻，F(xiàn)uzzer就可以不斷的提高程序測試用例對于程序控制流的覆蓋率。
這是一種非常直接并且被證明異常高效的Fuzz策略开皿。下面我會主要介紹AFL的后續(xù)機(jī)型AFL++涧黄。
AFL本體是成熟篮昧，具有工業(yè)強(qiáng)度，在各大廠被廣泛應(yīng)用的測試工具笋妥，F(xiàn)ireFox等大型項(xiàng)目都在使用懊昨。所有沒有任何理由不把他加入你的CI/CD工具鏈！４盒酵颁！
AFL的后端部分主要是兩個(gè)程序，一個(gè)是一個(gè)被修改過的as匯編器月帝，一個(gè)是afl-clang-fast躏惋。其實(shí)還有一個(gè)gcc的wrapper但是實(shí)際上afl-gcc只是設(shè)置一下編譯參數(shù)，真正的instrument的部分都在as中完成嚷辅。afl-clang-fast沒什么好多說的簿姨，對llvm ir進(jìn)行instrument. 其實(shí)這部分比我想象中的簡單，原理是簸搞。 在共享內(nèi)存里預(yù)先會由afl本體生成一個(gè)bitmap扁位，每一個(gè)index對應(yīng)程序中的一個(gè)或者多個(gè)控制流節(jié)點(diǎn)，為什么不是1對1呢趁俊？因?yàn)槌绦虻目刂屏骺赡芊浅?fù)雜域仇，節(jié)點(diǎn)非常多，為了效率這里就只能近似一下了寺擂。在每一個(gè)cfg的block前面都插入一個(gè)隨機(jī)生成的id, 如果程序執(zhí)行到這個(gè)block就把id對應(yīng)的Bitmap位置置1暇务。最終所有被標(biāo)記1的位置就是一條程序的執(zhí)行path。這個(gè)方法其實(shí)很粗糙怔软，第一是節(jié)點(diǎn)映射不是單射垦细，第二對于path經(jīng)過節(jié)點(diǎn)的先后順序其實(shí)沒法準(zhǔn)確的區(qū)分。
前端部分爽雄，AFL對于seed/cropus沒有太多的處理蝠检，只是會trim, 也不會管是不是一個(gè)比較優(yōu)質(zhì)的seed沐鼠。 他的mutator主要是依賴bitfliper策略和插值策略挚瘟。 bitfliper會在input 測試用例上每隔幾個(gè)bit對bit進(jìn)行一次反轉(zhuǎn)，這種策略很蠢但是很快饲梭，數(shù)量和啟發(fā)式算法可以彌補(bǔ)這一點(diǎn)乘盖。 插值就是afl會插入一些interesting value，這些value主要有兩個(gè)來源：
- 一個(gè)用戶指定的字典
- Fuzz算法在打分過程中發(fā)現(xiàn)的比較容易產(chǎn)生變異的數(shù)據(jù)憔涉。
簡單的來說就是這樣订框，當(dāng)然AFL里有很多東西遠(yuǎn)比我想象的復(fù)雜，比如如何提升效率兜叨，如何處理error的程序等等穿扳。
AFL++
AFL++是我目前在使用的Fuzzer衩侥， 這個(gè)東西是AFL的后續(xù)型號， 我主要是為了他的Custom Mutator 功能矛物。 在AFL++中用戶可以定義自己的mutator來提高變異的質(zhì)量茫死。因?yàn)閷τ谝恍┏绦颍热缇幾g器履羞，他的輸入總是一個(gè)程序代碼峦萎，在變異的過程中比較有效的變異肯定是起碼還是要讓他是個(gè)代碼。但是原生AFL的變異比如bitfliper,插入int值之類的忆首，一變代碼就不再是代碼了爱榔。。糙及。详幽。對于seed program簡直是反向變異，就算是找到啦bug很可能也是一些比較無聊的bug浸锨。
最后放個(gè)圖妒潭。。揣钦。怎么fuzz編譯器是個(gè)更加復(fù)雜的問題雳灾，下次得單獨(dú)開blog講啦。
