前言
模糊測試（Fuzzing）技術(shù)作為漏洞挖掘最有效的手段之一，近年來一直是眾多安全研究人員發(fā)現(xiàn)漏洞的首選技術(shù)。AFL、LibFuzzer、honggfuzz等操作簡單友好的工具相繼出現(xiàn)，也極大地降低了模糊測試的門檻。
基于工程實踐的要求，我需要對afl進(jìn)行源碼閱讀，需要了解afl的實現(xiàn)細(xì)節(jié)，借此blog記錄對源碼的理解。
在這里我選擇閱讀 aflplusplus源碼，降低入門門檻，希望能夠粗略理解afl具體做了什么。同時，AFLplusplus，引進(jìn)了更強(qiáng)的編譯算法，如果是源碼插樁的方式，更適合使用 AFLplusplus。
AFL白皮書
參考
http://www.itdecent.cn/p/cc7a486e5adb
想要搞清楚AFL到底干了什么，直接看源碼肯定是一頭扎進(jìn)深潭，無源死水，所以還是先看懂原理，從afl白皮書入手。在這之前，還是得了解一下測試中的一些術(shù)語。
插樁(instrumentation)
它是在保證被測程序原有邏輯完整性的基礎(chǔ)上在程序中插入一些[探針]（又稱為“探測儀”，本質(zhì)上就是進(jìn)行信息采集的代碼段，可以是[賦值語句]或采集覆蓋信息的[函數(shù)調(diào)用]），通過[探針]的執(zhí)行并拋出程序運行的[特征]數(shù)據(jù)（方法本身、方法參數(shù)值、返回值等），通過對這些數(shù)據(jù)的分析，可以獲得程序的控制流和數(shù)據(jù)流信息，進(jìn)而得到邏輯覆蓋等動態(tài)信息，從而實現(xiàn)測試目的方法。
果我們想要了解一個程序在某次運行中可執(zhí)行語句被覆蓋的情況，或是每個語句的實際執(zhí)行次數(shù)，最好的辦法就是利用插裝技術(shù)。
最簡單的插樁：在程序中插入打印語句printf(“ ...”)語句。
1.插樁位置：a.程序的第一條語句；b.分支語句的開始；c.循環(huán)語句的開始；d.下一個入口語句之前的語句；e.程序的結(jié)束語句；f.分支語句的結(jié)束；g.循環(huán)語句的結(jié)束。
2.插樁策略：
①語句覆蓋探針（基本塊探針）：在基本塊的入口和出口處，分別植入相應(yīng)的探針，以確定程序執(zhí)行時該基本塊是否被覆蓋。
②分支覆蓋探針：c/c++語言中，分支由分支點確定。對于每個分支，在其開始處植入一個相應(yīng)的探針，以確定程序執(zhí)行時該分支是否被覆蓋。
③條件覆蓋探針：c/c++語言中，if, swich,while, do-while, for 幾種語法結(jié)構(gòu)都支持條件判定，在每個條件表達(dá)式的布爾表達(dá)式處植入探針，進(jìn)行變量跟蹤取值，以確定其被覆蓋情況。
代碼覆蓋（Code coverage）
是軟件測試中的一種度量，描述程式中源代碼被測試的比例和程度，所得比例稱為代碼覆蓋率。
AFL的工作流程
①從源碼編譯程序時進(jìn)行插樁，以記錄代碼覆蓋率（Code Coverage）；
②選擇一些輸入文件，作為初始測試集加入輸入隊列（queue）；
③將隊列中的文件按一定的策略進(jìn)行“突變”；
④如果經(jīng)過變異文件更新了覆蓋范圍，則將其保留添加到隊列中;
⑤上述過程會一直循環(huán)進(jìn)行，期間觸發(fā)了crash的文件會被記錄下來
1. 覆蓋率計算(Coverage measurements)
通過在編譯程序中注入插樁(instrumentation)來捕獲分支(邊緣)覆蓋率，并且還能檢測到粗略的分支執(zhí)行命中次數(shù)(branch-taken hit counts)。在分支點注入的代碼大致如下：
cur_location = <COMPILE_TIME_RANDOM>;
shared_mem[cur_location ^ prev_location]++;
prev_location = cur_location >> 1;
我們把路徑定義為tuples
A -> B -> C -> D -> E (tuples: AB, BC, CD, DE)
A -> B -> D -> C -> E (tuples: AB, BD, DC, CE)
cur_location:隨機(jī)生成，以簡化鏈接復(fù)雜項目的過程并保持XOR輸出均勻分布。-
shared_mem: 調(diào)用者(caller)傳給被插樁的二進(jìn)制程序(passed to the instrumented binary)的64kB的共享存儲空間。在輸出映射中設(shè)置的每個字節(jié)都可以視為命中檢測代碼中的特定（branch_src，branch_dst）元組。也就是說shared_mem記錄了從A->B路徑的次數(shù)，同時也能區(qū)分上述兩條A->E是不同的路徑。
選擇這個數(shù)組大小的原因是讓沖突(collisions)盡可能減少。這樣通常能處理2k到10k的分支點。同時，它的大小也足以達(dá)到毫秒級的分析。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% - prev_location注意第一句話：“通過在編譯程序中注入插樁(instrumentation)來捕獲分支(邊緣)覆蓋率”。我們要找的是分支，也就是代碼塊A->B->C...的路徑，但是A->B和B->A是不一樣的路徑。
最后一行的左移操作就是為了讓tuples有定向性，否則AB和BA就沒有了區(qū)別。
2. 發(fā)現(xiàn)新路徑
AFL的fuzzer維護(hù)一個全局的Map來存儲之前執(zhí)行時看到的tuple。這些數(shù)據(jù)可以被用來對不同的trace進(jìn)行快速比較和更新，從而可以計算出是否新執(zhí)行了一個dword指令/一個qword-wide指令/一個簡單的循環(huán)（缺乏前景知識有點難理解）。
再來復(fù)習(xí)一下afl工作流程
①從源碼編譯程序時進(jìn)行插樁，以記錄代碼覆蓋率（Code Coverage）；
②選擇一些輸入文件，作為初始測試集加入輸入隊列（queue）；
③將隊列中的文件按一定的策略進(jìn)行“突變”；
④如果經(jīng)過變異文件更新了覆蓋范圍，則將其保留添加到隊列中;
⑤上述過程會一直循環(huán)進(jìn)行，期間觸發(fā)了crash的文件會被記錄下來
afl通過輸入文件的突變產(chǎn)生新路徑(新tuples),當(dāng)一個變異的輸入產(chǎn)生了一個包含新tuple的執(zhí)行路徑時，對應(yīng)的輸入文件就被保存，這種變異測試用例會被加入到輸入隊列(input queue)中，當(dāng)做下一次fuzz的起點。對于那些沒有產(chǎn)生新路徑的輸入，就算他們的路徑是不同的，也會被拋棄掉。
考慮下面兩個路徑,第二個路徑出現(xiàn)了新的tuples(CA, AE):
#1: A -> B -> C -> D -> E
#2: A -> B -> C -> A -> E
再來看一條路徑# 3
#3: A -> B -> C -> A -> B -> C -> A -> B -> C -> D -> E
因為#2的關(guān)系，盡管整體上看這條執(zhí)行路徑非常不同，但認(rèn)為他們是同一條路徑
因為只出現(xiàn)了AB BC CD DE CA AE這幾個tuple。
除了檢測新的tuple之外，AFL的fuzzer也會粗略地記錄tuple的命中數(shù)(hit counts)。這些被分割成幾個buckets：
1, 2, 3, 4-7, 8-15, 16-31, 32-127, 128+
buckets里面的數(shù)字是一個8-bit counter和一個8-position bitmap的映射。一個8-bit counter和一個8-position bitmap的映射。（很難理解）
先下結(jié)論：從一個bucket變成另一個bucket才是重要的。
從一個bucket到另一個bucket 會被標(biāo)記被程序流中的一個有趣的變化(interesting change)，傳入到輸入隊列的進(jìn)化過程里【也就是步驟4的部分】。而單個bucket的改變就被忽略掉，不管了。
通過命中次數(shù)(hit count)，我們能夠分辨控制流是否發(fā)生變化。例如一個代碼塊被執(zhí)行了兩次，但只命中了一次。并且這種方法對循環(huán)的次數(shù)不敏感(循環(huán)47次和48次沒區(qū)別)。
3. 輸入隊列的進(jìn)化(Evolving the input queue)
變異測試用例(Mutated test cases)是能夠產(chǎn)生新的語句轉(zhuǎn)移(即新的tuple)的測試用例。這種變異測試用例會被加入到輸入隊列(input queue)中，當(dāng)做下一次fuzz的起點。它們作為已有測試用例的補(bǔ)充，但并不替換掉已有測試用例。
白皮書貼了張圖來說明上述算法的作用
http://lcamtuf.coredump.cx/afl/afl_gzip.png
與更貪婪的遺傳算法相反，此方法允許該工具逐步探索基礎(chǔ)數(shù)據(jù)格式的各種不相交和可能相互不兼容的特征
在(使用算法)過程中生成的語料庫是那些“有用的”輸入的集合，這個語料庫可以直接給其他測試過程當(dāng)做seed(例如，手動對一些desktop apps進(jìn)行壓力測試)。
使用這種算法，大多數(shù)目標(biāo)程序的輸入隊列會到1k到10k。其中，大約10-30%是發(fā)現(xiàn)的新tuple，剩下的都是和命中次數(shù)(hit count)的改變有關(guān)。
白皮書3、4節(jié)講的比較晦澀。3、4、5節(jié)聯(lián)系比較緊密，索性用更直白的方式描述4、5節(jié)。
4. 語料篩選與修剪（Culling the corpus and Trimming input files)
語料庫
我的理解就是初始輸入集。必須確保語料庫盡可能多地覆蓋目標(biāo)代碼，也就是讓程序執(zhí)行不同的路徑，因為這增加了在其中發(fā)現(xiàn)bug的機(jī)會。此外，必須避免語料庫中的冗余，以便每個測試用例觸發(fā)目標(biāo)的獨特行為。
AFL需要一些初始輸入數(shù)據(jù)（也叫種子文件）作為Fuzzing的起點，這些輸入甚至可以是毫無意義的數(shù)據(jù)，AFL可以通過啟發(fā)式算法自動確定文件格式結(jié)構(gòu)。lcamtuf就在博客中給出了一個有趣的例子——對djpeg進(jìn)行Fuzzing時，僅用一個字符串”hello”作為輸入，最后憑空生成大量jpge圖像！
盡管AFL如此強(qiáng)大，但如果要獲得更快的Fuzzing速度，那么就有必要生成一個高質(zhì)量的語料庫。
1. 選擇語料庫的原則
(1) 有效的輸入
盡管有時候無效輸入會產(chǎn)生bug和崩潰，但有效輸入可以更快的找到更多執(zhí)行路徑。
(2) 盡量小的體積
較小的文件會不僅可以減少測試和處理的時間，也能節(jié)約更多的內(nèi)存，AFL給出的建議是最好小于1 KB，但其實可以根據(jù)自己測試的程序權(quán)衡，這在AFL文檔的perf_tips.txt中有具體說明。
2. 尋找語料庫
- 使用項目自身提供的測試用例
- 目標(biāo)程序bug提交頁面
- 使用格式轉(zhuǎn)換器，用從現(xiàn)有的文件格式生成一些不容易找到的文件格式：
- afl源碼的testcases目錄下提供了一些測試用例
- 其他大型的語料庫
- afl generated image test sets
- fuzzer-test-suite
- libav samples
- ffmpeg samples
- fuzzdata
- moonshine
3. 輸入文件修剪
語料庫蒸餾（Corpus Distillation）
核心思想是首先收集大量有效的輸入。然后，對于每個輸入，測量基本塊的代碼覆蓋，如果輸入僅觸發(fā)先前輸入已經(jīng)訪問過的基本塊，則將其從集合中移除。
為了優(yōu)化fuzzing，AFL會用一個快速算法周期性的重新評估(re-evaluates)隊列，這種算法會選擇隊列的一個更小的子集，并且這個子集仍能覆蓋所有的tuple。
該算法通過為每個隊列條目分配與執(zhí)行延遲和文件大小成比例的分?jǐn)?shù)來工作。然后為每個元組選擇得分最低的候選者。
然后使用簡單的工作流依次處理元組：
1）在臨時工作集中找到下一個元組，
2）找到該元組的獲勝隊列條目，
3）在工作集中注冊該條目的跟蹤中存在的所有元組，
4）如果集合中缺少任何元組，請轉(zhuǎn)到＃1。
生成的“收藏”條目的語料庫通常比起始數(shù)據(jù)集小5-10倍。非優(yōu)先項不會被丟棄，但是在隊列中遇到時，它們會以不同的概率被跳過：
如果隊列中存在新的但尚未模糊的收藏夾，則99％的非喜歡條目將被跳過，以得到喜歡的條目。
-
如果沒有新的收藏夾：
如果當(dāng)前的不喜歡的條目之前是模糊的，它將被跳過
95％的時間。如果還沒有經(jīng)過任何模糊測試，那么跳過的幾率就很大
下降到75％。
同時白皮書的第四第五節(jié)提到了兩個工具afl-cmin和afl-tmin
一個用來移除執(zhí)行相同代碼的輸入文件——AFL-CMIN
一個用來減小單個輸入文件的大小——AFL-TMIN
afl-cmin
使用afl-cmin工具能夠?qū)斎牖蜉敵龅恼Z料庫進(jìn)行稍微復(fù)雜但慢得多的的處理，
可以精簡語料庫，去掉可能重復(fù)的測試用例，針對一些復(fù)雜的語料庫十分有用，可大大減少無用的 fuzz 用例。產(chǎn)生適用于afl-fuzz或者外部工具的更小的語料庫
afl-cmin的核心思想是：嘗試找到與語料庫全集具有相同覆蓋范圍的最小子集。舉個例子：假設(shè)有多個文件，都覆蓋了相同的代碼，那么就丟掉多余的文件。
afl-tmin
afl-tmin工具減小單個文件的大小，對每個文件進(jìn)行更細(xì)化的處理，因為 afl 要求測試用例的大小最好小于 1KB，因此最好將精簡后的用例進(jìn)一步縮小體積。
5. 模糊測試策略(Fuzzing strategies)
值得注意的是，尤其是在早期，afl-fuzz所做的大部分工作實際上都是高度確定性(highly deterministic)的，并且僅在后期才進(jìn)行到隨機(jī)堆疊的修改(random stacked modifications)和測試用例的拼接(test case splicing)【讀到這里就一堆問號了】
確定性策略包。
- 使用變化的長度和步距(lengths and stepovers)來連續(xù)(sequential)進(jìn)行位反轉(zhuǎn)。
- 對小的整型數(shù)(small integers)來連續(xù)進(jìn)行加法和減法。
- 對已知的interesting integers(例如 0,1，INT_MAX等)連續(xù)地插入。
使用這些確定步驟的目的在于，生成緊湊的(compact)測試用例，以及在產(chǎn)生non-crashing的輸入和產(chǎn)生crashing的輸入之間，有很小的差異(small diffs)。
我的理解是這里說的是對輸入數(shù)據(jù)的改變一開始是一點一點變化的，因為一開始的時候比較容易找到大部分的分支，后面找那些隱藏的比較深的比較難得可能就用上比較復(fù)雜的非確定性的策略。
非確定性(non-deterministic)策略的步驟包括：stacked bit flips、插入(insertions)、刪除(deletions)、算數(shù)(arithmetics)和不同測試用例之間的接片(splicing)。
再后面的就是更加晦澀的內(nèi)容，對初入門的人來說更難理解，就此打住。
AFL++
參考 http://rk700.github.io/2017/12/28/afl-internals/
AFL++源碼有很多個文件，上來一看頭就很大了，但其命名也是很有規(guī)律的，有些過于底層的我們必要去細(xì)究，理解了重要的再說。
afl-analyze.c
afl-as.c
afl-cc.c
afl-common.c
afl-forkserver.c
afl-fuzz-bitmap.c
afl-fuzz-cmplog.c
afl-fuzz-extras.c
afl-fuzz-init.c
afl-fuzz-mutators.c
afl-fuzz-one.c
afl-fuzz-python.c
afl-fuzz-queue.c
afl-fuzz-redqueen.c
afl-fuzz-run.c
afl-fuzz-state.c
afl-fuzz-stats.c
afl-fuzz-statsd.c
afl-fuzz.c
afl-gotcpu.c
afl-ld-lto.c
afl-performance.c
afl-sharedmem.c
afl-showmap.c
afl-tmin.c
README.md
afl-as
as是匯編器assembler的縮寫，那afl-as.c就應(yīng)該是和匯編有關(guān)的了。
如果了解編譯過程，那么就知道把源代碼編譯成二進(jìn)制，主要是經(jīng)過”源代碼”->”匯編代碼”->”二進(jìn)制”這樣的過程。而將匯編代碼編譯成為二進(jìn)制的工具，即為匯編器assembler。Linux系統(tǒng)下的常用匯編器是as。不過，編譯完成AFL后，在其目錄下也會存在一個as文件，并作為符號鏈接指向afl-as。所以，如果通過-B選項為gcc設(shè)置了搜索路徑，那么afl-as便會作為匯編器，執(zhí)行實際的匯編操作。
所以，AFL的代碼插樁，就是在將源文件編譯為匯編代碼后，通過afl-as完成。
接下來，我們繼續(xù)閱讀文件afl-as.c。其大致邏輯是處理匯編代碼，在分支處插入樁代碼，并最終再調(diào)用as進(jìn)行真正的匯編。
afl-as.c就是關(guān)于插樁的代碼，定位到295行
295 fprintf(outf, use_64bit ? trampoline_fmt_64 : trampoline_fmt_32,
R(MAP_SIZE));
這里通過fprintf()將格式化字符串添加到匯編文件的相應(yīng)位置。
R(x)的定義是(random() % (x))，所以R(MAP_SIZE)即為0到MAP_SIZE之間的一個隨機(jī)數(shù)。也就是之前白皮書里我們分析過的那行偽代碼!
cur_location = <COMPILE_TIME_RANDOM>;
那MAP_SIZE是多少？我們share_mem的容量是64kB,所以MAP_SIZE是64k。
use_64bit ? trampoline_fmt_64 : trampoline_fmt_32,應(yīng)該是看機(jī)器是不是使用64位，不是就用32位的情況
static const u8 *trampoline_fmt_32 =
"\n"
"/* --- AFL TRAMPOLINE (32-BIT) --- */\n"
"\n"
".align 4\n"
"\n"
"leal -16(%%esp), %%esp\n"
"movl %%edi, 0(%%esp)\n"
"movl %%edx, 4(%%esp)\n"
"movl %%ecx, 8(%%esp)\n"
"movl %%eax, 12(%%esp)\n"
"movl $0x%08x, %%ecx\n"
"call __afl_maybe_log\n"
"movl 12(%%esp), %%eax\n"
"movl 8(%%esp), %%ecx\n"
"movl 4(%%esp), %%edx\n"
"movl 0(%%esp), %%edi\n"
"leal 16(%%esp), %%esp\n"
"\n"
"/* --- END --- */\n"
"\n";
mov是將數(shù)據(jù)從源操作傳到目的操作數(shù)中
lea是將源操作數(shù)的地址傳到目的操作數(shù)中
一個是數(shù)據(jù)，一個是地址
movl %%edi, 0(%%esp) #把32位的edi寄存器值傳送給32為的esp寄存器
leal -16(%%esp), %%esp是傳送 esp-16（值）到 寄存器esp
call是過程調(diào)用
這一段匯編代碼，主要的操作是：
- 保存edi等寄存器
- 將ecx的值設(shè)置為fprintf()所要打印的變量內(nèi)容
- 調(diào)用方法__afl_maybe_log()
- 恢復(fù)寄存器
這里我們只分析"movl $0x%08x, %%ecx\n"這條指令
__afl_maybe_log是插樁代碼所執(zhí)行的實際內(nèi)容，會在接下來詳細(xì)展開，
因此，在處理到某個分支，需要插入樁代碼時，afl-as會生成一個隨機(jī)數(shù)，作為運行時保存在ecx中的值。而這個隨機(jī)數(shù)，便是用于標(biāo)識這個代碼塊的key。
