基于覆蓋率的Fuzzer和AFL

一
Fuzzer的類型

模糊測試器的分類方法方式有好幾種，本文將著重介紹基于覆蓋率的模糊測試器，因此只詳細介紹根據fuzzing策略的分類。基于fuzzing的策略，可將fuzzer分為基于定向的fuzzing和基于覆蓋率的fuzzing。

對于基于覆蓋率的模糊測試工具來說，往往需要使用恰當的種子測試目標程序，基于目標程序的反饋引導種子的變異生成更多恰當的測試用例，以引導測試覆蓋盡可能多的代碼路徑。之所以用覆蓋率這一個指標做為衡量，是因為在實踐中人們發現更高的覆蓋率往往能夠找到更多的bug。

然而在實際場景中，一個項目中大部分代碼都是不包含bug的，而且實際過程中，對于覆蓋率模糊測試，僅靠依靠模糊測試器自己盲目測試是幾乎不可能達到極高的覆蓋率。定向模糊工具正是基于上訴原因應運而生。因此對于定向模糊測試工具而言，其目的旨在快速的測試特定的目標位置是否可能存在bug。（定向模糊測試工具并非本文的著眼點，因此將略過。）

二
基于覆蓋率的Fuzzer

基于覆蓋率的模糊測試策略是最先被完整應用的，在長時間的應用中十分可靠，高效且有效。對于基于代碼覆蓋率的Fuzzer來說，我們先講一個重要的概念，代碼覆蓋率（Code Coverage），其次我們再介紹基于覆蓋率的Fuzzer的一般工作流程，最后我們簡單的介紹以下fuzzing另一個重要的概念種子語料庫（Seed Corpus）。

代碼覆蓋率及度量方法

代碼覆蓋是軟件測試中的一種度量，描述程序中源代碼被測試的比例和程度，簡單的說即測試目標代碼的覆蓋程度，所得比例稱為**代碼覆蓋率。**代碼覆蓋率的度量方式主要有基本快覆蓋、邊覆蓋率、條件覆蓋率。

基本塊(Basic Block)是具有單一入口和單一出口的代碼片段，即一組順序執行的指令。如下圖，IDA中CFG圖的代碼塊即是一種基本塊。

一個基本塊從其中第一條指令執行開始，直到執行到最后一條指令才結束（跳轉到其他塊）。也即，單一入口是指只能從基本塊的第一條指令進入基本塊，單一出口是指只能從基本塊的最后一條指令跳轉離開。

所謂基本塊覆蓋率即統計代碼中基本塊執行的情況，那些基本塊執行了，那些沒有執行。用執行了的基本塊除于總的基本塊即是基本塊覆蓋率。

邊的概念也是依托于基本塊的概念，基本塊之間的跳轉若用一條線畫出來，這條線就叫做邊。如下圖所示。

所謂邊覆蓋率則是統計基本塊之間的分支跳轉的情況，也即統計那些邊被執行了，那些邊沒有。相信諸位眼尖的可能發現了，邊覆蓋率能夠覆蓋相比于基本塊覆蓋率，雖然代碼執行語句上似乎并無區別，但覆蓋了更多的代碼邏輯。

我們用一個例子來說明。如下圖所示，有BB1、BB2、BB3和BB4，四個基本塊。若執行路徑BB1->BB2->BB3->BB4，則以基本塊覆蓋率來說，我們可以理所當然的說，覆蓋率已經達100%了。

但是我們卻發現代碼中許多隱含的邏輯并未被測試出來。例如，我們走BB1->BB3->BB4和BB1->BB2->BB4，顯然用基本塊覆蓋率來衡量自然是100%，但是卻展示了一種全然不同的代碼邏輯。

我們發現，若我們以邊的執行程度來衡量，當所有的邊被訪問時，此時基本塊覆蓋率必然100%，并且還挖掘出許多隱含的代碼邏輯，也是說，不但代碼測的全還測的更加徹底。

一般工作流程

我們以《Fuzzing：a survey》給出的覆蓋率Fuzzer的一般工作過程的偽代碼做為例子來解讀。

首先，我們需要輸入一個初始種子S，若沒有給定初始種子S，則模糊器自己將構造一個。

隨后，從初始種子選擇種子進行變異生成測試用例，測試程序，若測試的結果為crash則加入Crash輸出集。若并未產生crash則模糊器判斷該測試用例是否有價值、足夠有趣，若答案是肯定的則加入種子集合，再后續的主循環中利用。直到模糊器收到終止信號，則退出循環，并將運行中收集到的crash集輸出。

我們可以從這樣一個流程中看到，模糊器無外乎做了兩件事情，一是根據種子生成測試用例，二是根據測試用例測試程序并追蹤程序的狀態，如此循環往復。可以簡單的兌換為以下的流程圖。

種子語料庫

我們在0x02章中，工作流程這個小節中發掘，種子庫對于fuzzer來說是一個至關重要的環節，而在實踐過程中也的確證實，好的種子庫對于fuzzer結果的影響和執行效率都十分巨大。

對于基于覆蓋率的fuzzer來說，種子語料庫的質量顯著的影響fuzzing的質量。良好的初始種子可以顯著提高fuzzing的效率和效果。

具體來說，提供目標測試程序輸入要求良好格式的種子，可以避免因大量無用的CPU消耗。良好的種子輸入格式，可以避免模糊器在該階段盲目的變異猜測。良好輸入的格式的種子可以抵達更深和盲目變異難以抵達的路徑。

此外，種子語料庫的制作是也是一門重要的技能。

三
AFL

AFL是由Google工程師開發的一款基于引導覆蓋的模糊測試器，可以用于白盒測試與黑盒測試。在Github上，Google官方的AFL項目對AFL的描述如下：

American Fuzzy Lop is a brute-force fuzzer coupled with an exceedingly simple but rock-solid instrumentation-guided genetic algorithm. It uses a modified form of edge coverage to effortlessly pick up subtle, local-scale changes to program control flow.

AFL工作流程

AFL的工作流程可以體現為下圖。根據Google對AFL主要算法工作原理的總結，可以歸納為下面幾點：

1.從用戶獲取初始種子，加載到種子池隊列中。

2.從隊列中獲取一個種子文件，并且優先取得最小和最快的種子。

3.對取得的種子文件進行變異，生成一系列測試例子。

4.將一系列的測試例子，基于AFL的模糊測試策略進行測試和追蹤。

5.對于有利于提高覆蓋率的測試例子將被篩選為好的例子，加入到種子隊列中，同時記錄Crash。

6.go to 2。

在AFL執行流程的每一步中，都有許多迫切的問題。例如，如何挑選種子、如何變異、如何測試、如何測量覆蓋率等等，許多的問題都有行之有效的解決方法，但有效的人工干預仍然是一個好的選擇。

再下面一節，我們將討論再AFL中，對于上訴問題采取什么策略，是如何應對的。

AFL的工作原理

覆蓋率度量與引導

AFL的覆蓋率度量是一種混合度量，它將邊覆蓋率與在一次執行中相應邊的次數相結合，并設置一個上限（一個2的冪次方），防止路徑爆炸。

如果一個testcase訪問到了一條新的邊(edge)，那么AFL則認為它是有趣的（GOOD），將加入到種子隊列中。

那么AFL又是如何記錄已經訪問的邊呢？AFL是這樣計算的。如下圖所示，有兩個基本塊BB1和BB2，當發生從BB1到BB2的跳轉時，即可認為BB1和BB2之間的邊被訪問。AFL在會在編譯插樁階段對基本塊BB1和BB2分別插入一個標識R1和R2，根據這個R1和R2計算出一個哈希值，更新至位圖中相應索引的字節。

上訴邏輯可以兌現為如下偽代碼。

cur_location = 
shared_mem[cur_location ^ prev_location]++;
pre_location = cur_location >> 1;

Seed Mutations

AFL的變異分為deterministic和havoc兩種類型。其中deterministic對testcase的內容進行確定性的突變，如位翻轉、加法、一些特定值的替換(-1、INT_MAX)等。

havoc模式中，突變將具有更大的不可確定性，如可能會調整testcase的內容（添加或刪除部分內容）。

ForkServer

最初AFL對于每次fuzz都會建立一個虛擬進程空間，顯而易見，頻繁的進程創建對CPU來說是一個巨大的開銷，對于fuzzing的效率不可忍受。

為了避免execve()的開銷，AFL設計了一套Forkserver機制。每當AFL需要fuzz新的testcase時，AFL會重新寫入testcase，然后告訴target fork自己。在這種情況下，AFL不需要每次都支付新進程初始化的開銷，而是fork一次后不斷在在第一次fork的進程中復用進程空間的資源，直到發生write時。

使用AFL進行fuzzing

優先推薦使用AFL的增強版本，AFL++。在比較新的Linux發行版上，大都可以通過一條命令安裝AFL++，以Ubuntu為例子，執行以下命令即可。

sudo apt install afl

然而，更加簡單快捷的使用完整的新版本AFL++，可以選擇容器構建。具體的只需要執行如下命令即可。

docker pull aflplusplus/aflplusplus
docker run -ti -v /location/of/your/target:/src aflplusplus/aflplusplus

具體的如何使用AFL進行fuzzing可以參考我的一篇文章，Fuzzing101-Exercise2 fuzz CVE-2009-3895和CVE-2012-2836 - 辰星-cxing - 博客園（https://www.cnblogs.com/cx1ng/p/17362871.html）

Fuzzer面臨的挑戰

fuzzer面臨的挑戰有許多，這里挑選了可以通過人工干預改進fuzzer效率和結果的幾個問題。

第一個是關于變異種子的，有兩個關鍵的問題，分別是在哪里變異、如何變異。因此只有少數關鍵位置上的恰當變異才會實質的影響程序的控制流。

第二個是關于驗證。許多的程序中有各種各樣的驗證，諸如驗證版本號、Magic值、特定字符串、特征值、輸入格式等等。這個問題在黑盒測試過程中尤為重要，你不能期待fuzzer的盲目試探可以給你一個很好的結果，由于上訴驗證的存在，盲目的變異將極大降低fuzzing的效率。

對于fuzzer的使用者來說，這兩個問題實際上都指向一個問題，即如何制作一個行之有效的種子語料庫，正確的意識到這兩個問題對于我們制作特定程序高質量的種子庫有十分巨大的幫助。

具體的，對于驗證我們可以制作有通過驗證與沒有通過驗證的種子，這樣我們即可以測試驗證代碼又可以繞過驗證代碼繼而測試更深處的代碼，這將大幅提高fuzzing的效率。對于這種子變異問題，我們也可以人工干預，在某些我們感興趣的位置制作一些指向目標代碼區域的種子。

此外，除了制作種子之外，我們可以通過修改目標程序的一些代碼，使fuzzing容易的略過一些我們不感興趣或充分fuzzing的區域，使得fuzzing可以更加容易的深入，但需要注意。