AFL解析篇0x01 AFL技術(shù)手冊（翻譯）
前言
本文翻譯自AFL的技術(shù)白皮書，如果英文水平足夠還是建議去看原文
https://lcamtuf.coredump.cx/afl/technical_details.txt
在對AFL進(jìn)行源碼剖析之前，先看一下里邊包含了哪些技術(shù)點(diǎn)，使得在后續(xù)閱讀源碼的時(shí)候能做到有的放矢。
0.設(shè)計(jì)說明
AFL盡量不去關(guān)注任何單一的操作原則，也不去證明任何特定的理論。這個(gè)工具可以被看作是經(jīng)過時(shí)間測試的一組技巧，它們被發(fā)現(xiàn)非常有效，并且以最簡單、最見狀的方式實(shí)現(xiàn)。
許多由此產(chǎn)生的特性之所以成為可能，都要?dú)w功于作為該工具基礎(chǔ)的輕量級工具的可用性，但這種機(jī)制應(yīng)該僅僅被視為達(dá)到目的的一種手段。唯一真正的控制原則是速度、可靠性和易用性。
1.覆蓋率度量
通過插樁收集編譯后程序的分支（邊）覆蓋率，以及粗糙的分支命中計(jì)數(shù)，在分支點(diǎn)注入的代碼本質(zhì)上等同于
cur_location=<COMPILE_TIME_RANDOM>;
shared_mem[cur_location ^ prev_location]++;
prev_location=cur_location >> 1;
cur_location的值是隨機(jī)生成的，以簡化連接復(fù)雜項(xiàng)目的過程，并保持異或操作之后的分布均勻。
shared_mem[] 數(shù)組是一個(gè)64kb的哈希區(qū)域，由調(diào)用者傳遞給檢測的二進(jìn)制文件。輸出映射中的每個(gè)字節(jié)集都可以看作是插樁代碼中特定數(shù)組（branch_src,branch_dst）的一次命中。
map的大小是由所有預(yù)期的目標(biāo)決定的，盡量減少碰撞，通常運(yùn)動2k和10k之間的可發(fā)現(xiàn)分支點(diǎn)
Branch cnt | Colliding tuples | Example targets
------------+------------------+-----------------
1,000 | 0.75% | giflib, lzo
2,000 | 1.5% | zlib, tar, xz
5,000 | 3.5% | libpng, libwebp
10,000 | 7% | libxml
20,000 | 14% | sqlite
50,000 | 30% | -
同時(shí)，它的大小足夠小，可以讓map在接收端在幾微妙內(nèi)被分析，并且可以輕松地裝入L2緩存。
這種形式地覆蓋比簡單的塊覆蓋更能深入了解程序的執(zhí)行路徑。特別是，它簡單地區(qū)分了以下執(zhí)行跟蹤：
A -> B -> C -> D -> E (tuples: AB, BC, CD, DE)
A -> B -> D -> C -> E (tuples: AB, BD, DC, CE)
這有助于發(fā)現(xiàn)底層代碼中的細(xì)微錯誤條件，因?yàn)榘踩┒锤嗟嘏c意外或不正確地狀態(tài)轉(zhuǎn)換有關(guān)，而不是僅僅與到達(dá)一個(gè)新的基本塊有關(guān)。
移位操作的原因在偽代碼的最后一句顯示，通過這個(gè)可以區(qū)分出來（BA,AB）.
intel cpu上沒有簡單的飽和算術(shù)操作碼，這意味著命中計(jì)數(shù)器有時(shí)會繞到零。由于這是一個(gè)不大可能發(fā)生的本地化事件，因此它被視為可接受的性能權(quán)衡。
2.檢測新的行為
fuzzer維持一個(gè)之間執(zhí)行中的全局元組的map；這些數(shù)據(jù)可以與單獨(dú)的跟蹤進(jìn)行快速編輯哦，并且在兩個(gè)dword或qword范圍的指令和一個(gè)簡單的循環(huán)中進(jìn)行更新
當(dāng)一個(gè)變異后的輸入產(chǎn)生了一個(gè)包含新元組的執(zhí)行軌跡，相應(yīng)的輸入文件將被保留并且添加后續(xù)的路由。對于在執(zhí)行軌跡中不能觸發(fā)新的區(qū)域的轉(zhuǎn)換被拋棄，即使即使它們的整體控制流序列是唯一的。
這種方法允許對程序狀態(tài)進(jìn)行非常細(xì)粒度和長期的探索，同時(shí)不需要對復(fù)雜的執(zhí)行軌跡執(zhí)行任何計(jì)算密集型和脆弱的全局比較，同時(shí)避免路徑爆炸的問題。
為了解釋該算法，考慮以下兩種路徑，第二條路徑較之第一條會被認(rèn)為是全新的，因?yàn)橛行碌脑M(CA,AE):
#1: A -> B -> C -> D -> E
#2: A -> B -> C -> A -> E
與此同時(shí)，在處理了#2之后，下面的模式將不再被視為唯一的模式，盡管它有一個(gè)明顯不同的整體執(zhí)行路徑
#3: A -> B -> C -> A -> B -> C -> A -> B -> C -> D -> E
除了檢測新的元組外，fuzzer還考慮粗糙的元組命中計(jì)數(shù)，這些被分為幾個(gè)部分：
1, 2, 3, 4-7, 8-15, 16-31, 32-127, 128+
在某種程度上，命中的數(shù)量是一個(gè)實(shí)現(xiàn)工件：它允許由檢測生成的8位計(jì)數(shù)器到fuzzer可執(zhí)行文件所依賴的8位位圖的原位映射，以跟蹤每個(gè)元組已經(jīng)看到的執(zhí)行次數(shù)。
在單個(gè)桶范圍內(nèi)的變化被忽略；從一個(gè)桶到另一個(gè)桶的轉(zhuǎn)換被標(biāo)記為程序控制流中一個(gè)有趣的變化，并被路由到下面一節(jié)中概述的進(jìn)化過程。
命中計(jì)數(shù)行為提供了一種方法來區(qū)分可能感興趣的控制流更改，例如執(zhí)行兩次的代碼塊，而該代碼塊通常只命中一次。與此同時(shí)，它對經(jīng)驗(yàn)上不太顯著的變化相當(dāng)不敏感，比如從47循環(huán)到48循環(huán)的循環(huán)。計(jì)數(shù)器還提供了某種程度的對密集跟蹤映射中元組沖突的”意外“免疫。
執(zhí)行受到內(nèi)存和執(zhí)行時(shí)間的限制；默認(rèn)情況下，超時(shí)設(shè)置為初始校準(zhǔn)執(zhí)行速度的5倍，四舍五入到20毫秒。激進(jìn)的超時(shí)是為了防止模糊器的性能急劇下降，比如，提高1%的覆蓋率，同時(shí)速度慢100倍；我們務(wù)實(shí)地拒絕它們，并希望fuzzer將找到一個(gè)更便宜地方式來達(dá)到相同的代碼。經(jīng)驗(yàn)檢驗(yàn)強(qiáng)烈表明，更慷慨的時(shí)間限制并不值得付出代價(jià)。
3.演化輸入隊(duì)列
在程序中產(chǎn)生新狀態(tài)轉(zhuǎn)換的突變測試用例將被添加到輸入隊(duì)列中，并用作未來幾輪模糊操作的起點(diǎn)。它們補(bǔ)充，但不會自動取代現(xiàn)有的發(fā)現(xiàn)。
與更貪婪的遺傳算法相比，這種方法允許工具逐步探索底層數(shù)據(jù)格式的各種不關(guān)聯(lián)和可能相互不兼容的特性。
這個(gè)過程生成的合成語料庫本質(zhì)上是”嗯，這做了一些新事情！“。輸入文件的緊湊集合，可以用來為任何其他測試過程提供種子（例如，手動對資源密集型桌面應(yīng)用程序進(jìn)行壓力測試）
使用這種方法，大多數(shù)目標(biāo)的隊(duì)列會增長1k到10k條目之間；其中大約10%-30%歸因于新元組的發(fā)現(xiàn)，其余部分與命中數(shù)的變化有關(guān)。
在前面提到的時(shí)候，遺傳模糊的一些早期工作依賴于維護(hù)單個(gè)測試用例，并將其演化以最大化覆蓋范圍。至少在上面描述的測試中，這種”貪婪“的方法似乎并沒有比盲目模糊策略帶來實(shí)質(zhì)性的好處。
4.精簡語料庫
上面概述的漸進(jìn)狀態(tài)探索方法意位著，在測試中稍后合成的一些測試用例可能具有新的邊緣覆蓋，是它們的祖先提供的覆蓋的嚴(yán)格超集。
為了優(yōu)化模糊工作，AFL使用一種快速算法周期性地重新評估隊(duì)列，該算法選擇一個(gè)更小的測試用例子集，這些測試用例仍然覆蓋到目前為止看到的每個(gè)元組，并且它們的特征使它們特別適合該工具。
該算法的工作原理是根據(jù)每個(gè)隊(duì)列條目的執(zhí)行延遲和文件大小為其分配一個(gè)分?jǐn)?shù)；然后為每個(gè)元組選擇得分最低的候選人。
使用一個(gè)簡單的工作流元組順序處理：
1）查找下一個(gè)元組中是否有臨時(shí)工作集
2）定位贏得隊(duì)列輸入的元組
3）在工作集中注冊該條目跟蹤中存在的所有元組
4）如果集合中有任何遺漏的元組，回到1）
生成的”偏好“條目語料庫通常比起始數(shù)據(jù)集小5-10倍。不喜歡的條目不會被丟棄，但是當(dāng)在隊(duì)列中遇到它們時(shí)，它們會從不同的概率被跳過。
-如果觸發(fā)了新的行為，沒有被fuzz過的favorites在隊(duì)列中，99%的不感興趣的輸入將跳過 從而得到favored ones。
-如果沒有行為：
-如果當(dāng)前不敢興趣的輸入之前被fuzz過了，其被跳過的概率是95%
-如果它還沒有被fuzz，跳過的概率下降到75%
通過實(shí)證測試，在隊(duì)列循環(huán)速度和測試用例多樣性之間實(shí)現(xiàn)了合理的平衡。
使用afl-cmin，可以對輸入或輸出語料庫進(jìn)行稍微復(fù)雜但速度慢得多的精簡。該工具永久地丟棄冗余條目，并生成一個(gè)適合與afl-fuzz或外部工具一起使用地較小的語料庫。
5.修剪輸入文件
文件大小對模糊性能有顯著的影響，這是因?yàn)榇笪募鼓繕?biāo)二進(jìn)制文件變慢，而且它們降低了突變接觸重要格式控制結(jié)構(gòu)的可能性。
除了用戶可能會提供低質(zhì)量的起始語料庫外，某些類型的編譯可能會產(chǎn)生迭代式地增加生成文件大小的影響，因此扭轉(zhuǎn)這種趨勢很重要。
幸運(yùn)的是，檢測反饋提供了一種簡單的方法來自動削減輸入文件，同時(shí)確保對文件所做的更改不會影響執(zhí)行路徑。
afl-fuzz的內(nèi)置修剪器試圖順序地刪除具有可變長度和跨越的數(shù)據(jù)塊；任何不影響跟蹤映射的校驗(yàn)和的刪除都被提交到磁盤。修剪器的設(shè)計(jì)不是特別徹底；相反，它試圖在精度和花費(fèi)在進(jìn)程上的execve()調(diào)用數(shù)之間取得平衡，選擇匹配的塊大小和跨越。每個(gè)文件的平均增益約為5-20%。
獨(dú)立的afl-tmin工具使用了更詳盡的迭代算法，并嘗試對裁剪后的文件執(zhí)行字母規(guī)范化。afl-tmin的操作如下。
首先，工具自動選擇操作模式。如果初始輸入使目標(biāo)二進(jìn)制程序崩潰，afl-tmin將在非插樁模式下運(yùn)行，只需保持任何產(chǎn)生更簡單文件的調(diào)整，但仍然使目標(biāo)程序崩潰。如果目標(biāo)是非崩潰的，工具使用插樁模式，只保留產(chǎn)生完全相同的執(zhí)行路徑的調(diào)整。
實(shí)際的最小化算法為：
1） 嘗試對大的數(shù)據(jù)塊進(jìn)行零轉(zhuǎn)換。從經(jīng)驗(yàn)上看，這可以通過在以后搶占更細(xì)粒度的工作來減少執(zhí)行人員的數(shù)量。
2）以二進(jìn)制搜索的方式，通過減少塊大小和步進(jìn)來執(zhí)行塊刪除過程。
3）通過計(jì)數(shù)唯一的字符并嘗試用零值批量替換每個(gè)字符來執(zhí)行字母規(guī)范化。
4）最后，在非零字節(jié)上執(zhí)行逐字節(jié)規(guī)格化。
afl-tmin不適用0x00字節(jié)進(jìn)行歸零，而是使用ASCII數(shù)字‘0’.這樣做是因?yàn)檫@樣的修改不太可能干擾文本解析，所以更有可能成功地最小化文本文件。
這里使用的算法比學(xué)術(shù)工作中提出的其他一些測試用例最小化方法涉及的少，但需要執(zhí)行的次數(shù)少得多，并且往往在大多數(shù)真實(shí)應(yīng)用程序中產(chǎn)生可比較的結(jié)果。
6.fuzzing策略
該工具提供的反饋使人們更容易理解各種模糊策略的價(jià)值，并優(yōu)化它們的參數(shù)，以便它們在廣泛的文件類型中同樣良好地工作。afl-fuzz使用地策略通常使與格式無關(guān)的，這里將進(jìn)行更詳細(xì)的討論。
值得注意的是，特別是在早期，afl-fuzz完成的大部分工作實(shí)際上是高度確定性的，并且只在后期階段才發(fā)展到隨機(jī)堆疊修改和測試用例拼接。確定性策略包括：
-具有不同長度和跨越的順序位翻轉(zhuǎn)
-小整數(shù)的序列加減
-順序插入已知的感興趣的整數(shù)(0,1,INT_MAX,etc)
使用確定性步驟的目的與它們產(chǎn)生緊湊測試用例的傾向以及非崩潰輸入和崩潰輸入之間的小差異有關(guān)。
隨著確定性模糊的消失，非確定性步驟包括堆疊位翻轉(zhuǎn)、插入、刪除、算術(shù)和不同測試用例的拼接。
所有這些策略的相對收益和執(zhí)行成本已經(jīng)在前面提到的博客文章中進(jìn)行了調(diào)查和討論。
由于historical_notes.txt中談?wù)摰脑颍ㄖ饕切阅?、簡單性和可靠性），AFL通常不會試圖推理特定突變和程序狀態(tài)之間的關(guān)系；模糊步驟在名義上是盲目的，并且僅由輸入隊(duì)列的進(jìn)化設(shè)計(jì)來引導(dǎo)。
也就是說，這條規(guī)則有一個(gè)（微不足道的）例外：當(dāng)一個(gè)新的隊(duì)列條目經(jīng)過確定性fuzz的初始步驟，并調(diào)整一些地區(qū)在文件的校驗(yàn)和觀察到?jīng)]有影響執(zhí)行路徑，他們可能被排除在確定性的剩余階段，fuzzer可能直奔隨機(jī)調(diào)整。特別是對于冗長的、人類可讀的數(shù)據(jù)格式，這可以減少10%-40%左右的執(zhí)行次數(shù)，而不會顯著降低覆蓋率。在極端情況下，例如生成的塊對其tar壓縮文件，增益可以高達(dá)90%。
因?yàn)榈讓拥摹毙?yīng)器映射“對每個(gè)隊(duì)列條目都是本地的，并且只在不改變底層文件的大小或總體布局的確定性階段有效，所以這種機(jī)制看起來工作得非?？煽?，而且被證明是很容易實(shí)現(xiàn)的。
7.字典
該工具提供的反饋使自動識別某些類型的輸入文件中的語法標(biāo)記變得很容易，并且可以檢測預(yù)定義的或自動檢測字典術(shù)語的某些組合是否構(gòu)成測試解析器的有效語法。
實(shí)質(zhì)上，當(dāng)基本的、通常很容易獲得的語法標(biāo)記以純粹隨機(jī)的方式組合在一起時(shí)，插樁和隊(duì)列的進(jìn)化設(shè)計(jì)一起提供了一種反饋機(jī)制，以區(qū)分無意義的突變和在插樁代碼中觸發(fā)新行為的突變——并在此發(fā)現(xiàn)的基礎(chǔ)上逐步構(gòu)建更復(fù)雜的語法。
詞典使fuzzer能夠快速重建高度冗長和復(fù)雜的語言（如JavaScript、SQL或XML）的語法。
有趣的是，AFL檢測還允許fuzzer自動隔離輸入文件中已經(jīng)存在的語法標(biāo)記。它可以通過查找字節(jié)的運(yùn)行，當(dāng)翻轉(zhuǎn)時(shí)，對程序的執(zhí)行路徑產(chǎn)生一致的變化；這暗示了與代碼中預(yù)定義值的底層原子比較。fuzzer依靠這個(gè)信號來構(gòu)建緊湊的”汽車詞典“，然后與其他模糊策略一起使用。
8. De-duping crashes去除復(fù)制的崩潰
對任何有能力的模糊工具來說，消除崩潰的重復(fù)是一個(gè)更重要的問題。許多幼稚的方法會遇到問題；特別是，如果故障發(fā)生在公共庫函數(shù)（例如，strcmp,strcpy）中，只查看故障地址可能會導(dǎo)致完全不相關(guān)的問題聚集在一起；如果可以通過許多不同的、可能是遞歸的代碼路徑到達(dá)錯誤，則校驗(yàn)和調(diào)用堆?；厮菘赡軙?dǎo)致極端的崩潰計(jì)數(shù)膨脹。
在afl-fuzz中實(shí)現(xiàn)的解決方案認(rèn)為，如果滿足兩個(gè)條件中的任何一個(gè)，則崩潰是唯一的。
-奔潰跟蹤包括一個(gè)在以前的任何崩潰中都沒有看到的元組
-崩潰跟蹤缺少在之前的崩潰中始終存在的元組
這種方法在早期很容易受到路徑計(jì)數(shù)膨脹的影響，但表現(xiàn)出很強(qiáng)的自我限制效應(yīng)，類似于afl-fuzz基本的執(zhí)行路徑分析邏輯。
9.調(diào)查崩潰
許多類型崩潰的可利用性可能是模棱兩可的，afl-fuzz試圖通過提供一個(gè)崩潰探索模式來解決這個(gè)問題，在這個(gè)模式中，已知的故障測試用例以一種非常類似于fuzzer的正常的操作的方式被模糊，但是有一個(gè)約束會導(dǎo)致任何非崩潰突變被丟棄。
該方法使用插樁返回來探索崩潰程序的狀態(tài)，以克服模糊的故障條件，然后將新發(fā)現(xiàn)的輸入分離出來供人審查。
關(guān)于崩潰的主體，值得注意的是，與正常的隊(duì)列條目相比，崩潰的輸入是”沒有“修剪的；他們被完全保留在發(fā)現(xiàn)的位置，以便更容易將他們與父隊(duì)列中的非崩潰入口及逆行比較。也就是說，afl-tmin可以用來隨意縮小它們。
10. The fork server
為了提高性能，afl-fuzz使用了一個(gè)"fork服務(wù)器"，其中模糊進(jìn)程只經(jīng)過execve()、鏈接和libc初始化一次，然后利用寫時(shí)復(fù)制從停止的進(jìn)程映像中克隆。這里更詳細(xì)地描述了實(shí)現(xiàn)。
http://lcamtuf.blogspot.com/2014/10/fuzzing-binaries-without-execve.html
fork服務(wù)器是注入的檢測的一個(gè)重要方面，它知識在第一個(gè)檢測函數(shù)處停止，等待afl-fuzz的命令。
對于快速目標(biāo)，分叉服務(wù)器可以提供相當(dāng)大的性能提升，通常在1.5倍到2倍之間，這也是可能的。
-在手動（”延遲“）模式下使用fork服務(wù)器，跳過較大的、用戶選擇的初始化代碼塊。它需要對目標(biāo)程序進(jìn)行非常溫和的代碼更改，有些目標(biāo)可以產(chǎn)生10倍以上的性能增益。
-啟用”持久“模式，其中單個(gè)進(jìn)程用于嘗試多個(gè)輸入，極大地限制了重復(fù)fork()調(diào)用的開銷。這通常需要對目標(biāo)程序進(jìn)行一些代碼更改，但可以將快速目標(biāo)的性能提高5倍或更多——近似于進(jìn)程內(nèi)模糊的好處，同時(shí)仍然保持fuzzer進(jìn)程和目標(biāo)二進(jìn)制之間非常健壯的隔離。
11.平行化
并行化機(jī)制依賴于周期性地檢查由其他CPU核心或遠(yuǎn)程機(jī)器上獨(dú)立運(yùn)行地實(shí)例產(chǎn)生地隊(duì)列，然后有選擇地拉入測試用例，這些測試用例在本地測試時(shí)產(chǎn)生fuzzer尚未看到的行為。
這為fuzzer設(shè)置了極大的靈活性，包括針對同一種通用數(shù)據(jù)格式的不同解析器運(yùn)行同步實(shí)例，通常具有協(xié)同效果。
12.二進(jìn)制插樁
對黑盒、只有二進(jìn)制的程序插樁需要依靠QEMU用戶模擬模式的幫助。這也允許執(zhí)行跨架構(gòu)的代碼——比如，x86上的ARM二進(jìn)制代碼。
QEMU使用基本塊作為翻譯單元；插樁是在此基礎(chǔ)上實(shí)現(xiàn)的，并使用一個(gè)大致類似于編譯時(shí)鉤子的模型。
if (block_address > elf_text_start && block_address < elf_text_end) {
cur_location = (block_address >> 4) ^ (block_address << 8);
shared_mem[cur_location ^ prev_location]++;
prev_location = cur_location >> 1;
}
第二行中基于移位和xor的置亂用于掩蓋指令對齊的效果。
QEMU、DynamoRIO和PIN等二進(jìn)制翻譯程序的啟動相當(dāng)緩慢；為了解決這個(gè)問題，QEMU模式利用了一個(gè)類似于用于編譯器插樁代碼的fork server，有效地生成在_start處暫停地已經(jīng)初始化地進(jìn)程的副本。
第一次翻譯一個(gè)新的基本塊也會引起大量的延遲。為了消除這個(gè)問題，AFL fork server通過在正在運(yùn)行的模擬器和父進(jìn)程之間提供一個(gè)通道進(jìn)行了擴(kuò)展。該通道用于將新遇到的塊的地址通知父進(jìn)程，并將它們添加到將為將來的子進(jìn)程復(fù)制的轉(zhuǎn)換緩存中。
這兩個(gè)優(yōu)化的結(jié)果是，QEMU模式的開銷大約是2-5倍，而PIN模式的開銷是100倍以上。
