提高fuzzing 邊覆蓋率的改進方法

賈春福，嚴盛博，王志，武辰璐，黎航

（1.南開大學網(wǎng)絡(luò)空間安全學院，天津 300350；2.南開大學人工智能學院，天津 300350）

1 引言

fuzzing[1]是一種有效的漏洞挖掘技術(shù)，它通過生成大量的測試用例來對目標程序進行測試，同時監(jiān)視目標程序的運行過程，發(fā)現(xiàn)程序暴露出的缺陷。傳統(tǒng)的fuzzing 工具由于生成測試用例時過于隨機，其測試存在盲目性，雖然測試速度很快，但效率很低。針對fuzzing 存在的問題，研究者提出了很多新的技術(shù)和方法，結(jié)合覆蓋引導、靜態(tài)分析、動態(tài)符號執(zhí)行、語法表示、動態(tài)污點分析和機器學習等多種技術(shù)，大大提高了fuzzing 的效率，并且在現(xiàn)實的軟件中發(fā)現(xiàn)了大量漏洞[2]。

覆蓋引導的fuzzing 策略被廣泛使用，并且已被證明是非常有效的。它盡可能地測試更多的代碼分支，使程序的代碼覆蓋率實現(xiàn)最大化。目前，代碼覆蓋率有2種基本的測量方式。一種是計算基本塊（BBL,basic block）覆蓋數(shù)，Libfuzzer、honggfuzzy和VUzzer[3]都是通過程序插樁來跟蹤BBL 的覆蓋信息。另一種是計算邊覆蓋數(shù)，AFL（American fuzzy lop）是第一個將邊覆蓋引入fuzzing 的工具，其通過編譯時靜態(tài)插樁，當程序運行時可獲取邊覆蓋信息，提供了比BBL 覆蓋更加精確的信息。

最近幾年發(fā)表了大量基于AFL 的研究。一類研究是定向fuzzing。例如，AFLGo[4]和Hawkeye[5]通過對程序的靜態(tài)分析來調(diào)整種子排序和種子的測試次數(shù)，逐步引導程序到達目標點。另一類研究結(jié)合了符號執(zhí)行技術(shù)。Driller[6]使用選擇性的混合符號執(zhí)行技術(shù)，當AFL 被“卡住”時，調(diào)用 Angr[7]來生成合法輸入，從而有效地分析大規(guī)模程序。WildFire[8]先通過單獨測試程序中的函數(shù)來發(fā)現(xiàn)漏洞，再使用KLEE[9]來校驗這些漏洞的可行性。還有一類研究結(jié)合了人工智能技術(shù)。孫鴻宇等[10]分析了人工智能技術(shù)在安全漏洞領(lǐng)域的應用。Godefroid等[11]基于神經(jīng)網(wǎng)絡(luò)的統(tǒng)計機器學習，生成富含格式的文件作為AFL 的初始種子。Skyfire[12]從樣本中學習一種概率上下文敏感語法（PCSG,probabilistic context sensitive grammar）來描述語法特征和語義規(guī)則，利用PCSG 生成具有不同語法結(jié)構(gòu)的種子輸入，從而為處理高度結(jié)構(gòu)化輸入的程序生成正確、多樣和不常見的種子。

然而，AFL 本身也存在一些缺陷，通過對這些缺陷的修復，可以優(yōu)化上述方法的效果。例如，CollAFL[13]針對AFL 邊覆蓋記錄存在沖突的問題，通過靜態(tài)分析生成新的hash 計算式，把沖突率降低到接近0，大大增加了覆蓋信息的準確率，提升了AFL 的效果。

此外，本文研究團隊也發(fā)掘出AFL 中隱藏的幾個缺陷和可以進一步改進的地方，主要有以下幾個方面。1)AFL 的種子選擇算法存在缺陷。其進行選擇時，實際隱含了一個固定順序，使隊列中排在越后面的種子被選中的概率越低。更嚴重的問題是，執(zhí)行完一輪循環(huán)后，被選中的種子可能并沒有覆蓋到所有的邊。2)AFL 對每個選中的種子執(zhí)行的變異次數(shù)幾乎一樣，沒有考慮到每條邊的熱度（即這條邊被覆蓋到的次數(shù)）。3)AFL 會記錄哪些字節(jié)變化時會產(chǎn)生新的狀態(tài)轉(zhuǎn)移，但是這些記錄信息未被有效利用，并且在從進程中無法使用這些記錄信息。

針對上述問題，本文著眼于AFL 算法的缺陷，同時對一些功能進行了改進，具體包括以下幾個方面。

1)提出了完全覆蓋種子選擇算法。該算法隨機打亂邊的順序，以打亂后的順序進行種子選擇，且只選擇隊列中位于當前位置之后的種子，最后對覆蓋情況進行檢查并修復覆蓋不全的問題。本文所提算法避免了按固定順序選擇優(yōu)先種子集，同時也避免了對邊覆蓋不完全的情況。

2)提出了基于邊覆蓋熱度的能量調(diào)度算法。根據(jù)路徑中邊的覆蓋熱度，對每條路徑進行評分,以此為依據(jù)動態(tài)調(diào)整每個種子文件的變異次數(shù)。

3)增加對有效字節(jié)的利用。在進行隨機性變異時，更多地對有效字節(jié)部分進行變異。同時加快了有效字節(jié)的產(chǎn)生，并在主進程和從進程之間同步有效字節(jié)信息。

基于上述方法，本文在開源的AFL 工具上，設(shè)計和實現(xiàn)了新的fuzzing 工具—efuzz，并按照Klees等[14]提出的測試思想進行實驗，實驗結(jié)果表明efuzz的邊覆蓋和漏洞發(fā)現(xiàn)能力都超過了 AFL 和AFLFast。使用常用軟件測試24 h 后，efuzz 的平均邊覆蓋數(shù)相比AFL 和AFLFast 分別提升了5%和9%，某些情況下甚至達到20%以上。使用LAVA-M[15]測試7天后，efuzz 發(fā)現(xiàn)的漏洞總數(shù)超過了AFL。在常用軟件中，efuzz 發(fā)現(xiàn)了3個新的CVE漏洞，其中一個是 binutils 工具包中的漏洞CVE-2018-20671，該漏洞從2001年起就已存在。

2 相關(guān)知識和技術(shù)概述

2.1 AFL 概述

AFL 是一個覆蓋率引導的灰盒測試工具。它基于遺傳算法，采用編譯時插樁的方式，通過獲取被測試程序運行時的覆蓋信息反饋，來判斷是否觸發(fā)了目標程序新的內(nèi)部狀態(tài)，從而發(fā)現(xiàn)感興趣的測試用例，以此引導fuzzing 策略，這大大提高了測試工具的覆蓋率。

圖1展示了AFL 的簡易流程，具體步驟如下。

步驟1提供一個初始輸入集加入種子隊列。

步驟2按照種子選擇算法從種子隊列中選擇優(yōu)先種子集。

步驟3按預設(shè)概率，順序從種子隊列中選擇一個種子文件。

圖1 AFL 簡易流程

步驟4使用多種變異算法對種子文件進行變異，循環(huán)生成大量測試用例進行測試。

步驟5如果發(fā)現(xiàn)程序崩潰，那么這可能是一個潛在的漏洞。

步驟6如果發(fā)現(xiàn)了新的路徑，那么把生成該路徑的測試用例加到種子隊列。

步驟7對該種子生成的所有測試用例，如果測試結(jié)束，回到步驟3。

整個測試是一個無限循環(huán)過程，直到人工終止。

2.2 邊覆蓋記錄

AFL 記錄的邊覆蓋信息包括邊的hash 以及這個邊被命中的次數(shù)。邊覆蓋信息使用規(guī)模為216的數(shù)組記錄，邊hash 作為數(shù)組的索引，數(shù)組中的值是邊被覆蓋的次數(shù)。為了加快處理速度，AFL 在每個BBL 中插入了一個0～65535的隨機數(shù)，邊hash 是由邊的首尾2個BBL 中的隨機數(shù)通過簡單hash 算法生成的，記錄覆蓋信息的算法偽代碼如下。

1)edge_hash=cur_bbl ^(last_bbl >>1)

2)shared_mem [ edge_ hash ]++

很顯然步驟1)中的hash 算法會存在沖突問題，但這不是本文的研究重點。本文把一個hash 記錄直接對應為一條邊覆蓋記錄。

2.3 種子選擇算法

fuzzing 中如何從種子隊列中選擇種子是一個非常關(guān)鍵的問題。之前的工作已經(jīng)證明，良好的種子選擇策略可以顯著提高模糊效率，更快地發(fā)現(xiàn)更多的bug[16]。

為了理解AFL 的種子選擇算法，首先介紹以下2個概念。

優(yōu)先種子。覆蓋到某一條邊的最好種子稱為該邊的優(yōu)先種子。最好種子就是所有能夠覆蓋到該邊的種子中，對其進行一次完整測試所消耗時間最短的種子。

優(yōu)先種子集。可以覆蓋當前已經(jīng)發(fā)現(xiàn)的所有邊的優(yōu)先種子集合，即優(yōu)先種子集的覆蓋面等價于當前所有種子的覆蓋面。

AFL 調(diào)用種子選擇算法從整個種子隊列中選出優(yōu)先種子集，隨后按概率優(yōu)先選擇其中的種子來進行測試。該算法本質(zhì)上是一個貪婪算法，如算法1所示。

算法1AFL 的種子選擇算法

輸入每條邊對應的優(yōu)先種子T[65536]、種子隊列Q

輸出選擇結(jié)果S

算法1按照邊的hash 值，在0～65535范圍內(nèi)按從小到大的順序選擇該邊的優(yōu)先種子，直到覆蓋所有已發(fā)現(xiàn)的邊。由于被測試程序編譯生成后，所有邊的hash 值就已經(jīng)確定了，因此這實際上是一個固定的選擇順序。

2.4 能量調(diào)度

B?hme 等[17]提出了能量的概念，能量指一個種子被選中后的測試次數(shù)。能量調(diào)度即按照一定算法對能量進行控制。AFL 給每個種子分配相同的能量，這忽略了對路徑稀有度的考量，可能將過多的能量分配給高密度區(qū)域[18]。AFLFast 使用馬爾可夫模型，給低頻路徑分配了更多的能量。但是，AFLFast 總是朝著低頻路徑，可能會錯失對一些邊的探索，導致代碼覆蓋率不高。Klees 等[14]也指出了AFLFast 的這個問題。

2.5 有效字節(jié)信息

如果對種子文件中某個字節(jié)進行翻轉(zhuǎn)后產(chǎn)生了與原種子對應路徑不同的新路徑，那么這個字節(jié)就是有效字節(jié)。下面具體解釋相關(guān)概念。

確定性階段和隨機性階段。AFL 分為確定性測試和隨機性測試兩大類。確定性測試階段對種子的變異方式是高度確定的，且每個種子只會經(jīng)歷一次確定性測試，而隨機性階段會調(diào)用一些隨機算法對種子進行變異。

主進程和從進程。AFL 可以有多個進程并行工作，主進程對每個選中的種子先進行確定性測試，再進行隨機性測試；從進程只進行隨機性測試。同時，主進程和從進程之間定期進行種子同步。

AFL 使用如下方法來記錄有效字節(jié)信息。當一個種子經(jīng)過確定性階段的字節(jié)翻轉(zhuǎn)子階段時，觀察種子文件中某個字節(jié)的翻轉(zhuǎn)對執(zhí)行路徑是否有影響。如果對這個字節(jié)翻轉(zhuǎn)后，產(chǎn)生了與種子對應路徑不同的新路徑，則使用 eff_map（effector maps）來記錄這個字節(jié)，在確定性測試的剩余子階段中只對eff_map 中記錄的字節(jié)進行變異。這樣一般可以將測試的執(zhí)行次數(shù)減少10%～40%左右，而不會顯著降低覆蓋率。在極端情況下，例如塊對齊的tar 文件，執(zhí)行次數(shù)可能減少高達90%。

3 fuzzing 改進方法

3.1 完全覆蓋種子選擇算法

AFL 的種子算法本身基于如下完全覆蓋性約束：選出的優(yōu)先種子集必須能完全覆蓋所有已經(jīng)發(fā)現(xiàn)的邊。通過2.3節(jié)的介紹以及實驗測試，發(fā)現(xiàn)算法1存在以下缺點。

1)按照邊的hash 值以0～65535的固定順序選擇，導致種子被選中的概率相差太多，hash 較小的邊對應的優(yōu)先種子總是被先選擇。舉個極端的例子：按照算法1，假設(shè)hash 值為0的優(yōu)先種子T[0]被選中，而T[0]對應的種子為s0，如果s0生成的路徑剛好覆蓋了所有已發(fā)現(xiàn)的邊,那么每次都只會選擇s0這一個種子,其他種子永遠無法被選到優(yōu)先集合。在實驗中記錄每次選出的優(yōu)先種子集也發(fā)現(xiàn)，每次選擇出的優(yōu)先種子集變化極小。如果采用隨機的順序進行種子選擇，可以緩解這個問題。

2)AFL 每測試一個種子后，如果種子隊列發(fā)生了變化，就會調(diào)用一次算法1，這可能導致執(zhí)行一輪循環(huán)后，有的邊沒有被覆蓋，這種情況違背了完全覆蓋性約束。出現(xiàn)這個問題的根本原因在于選擇了隊列中位于當前位置之前的種子，具體以代碼1為例進行說明。

代碼1AFL 種子選擇算法缺陷示例代碼

代碼1編譯后對應的控制流程如圖2所示。

圖2中每條邊上的數(shù)字代表該邊的編號，以ei表示邊i，只有順序通過邊e2、e6、e14的路徑才會觸發(fā)bug。

以qj表示第j條路徑，假設(shè)初始發(fā)現(xiàn)的6條路徑如表1所示。

圖2 AFL 種子選擇算法缺陷示例

表1 路徑說明

假設(shè)這些邊經(jīng)過hash 運算后的值，從小到大的順序為(e9,e8,e17,e6,…)，且測試按照以下步驟進行。

步驟1測試q1，發(fā)現(xiàn)新路徑{q2,q3,q4}，這時覆蓋的所有邊集合為{e1,e2,e3,e4,e5,e6,e7,e9,e15,e16,e17}。調(diào)用算法1選擇優(yōu)先種子集，按照邊hash順序(e9,e17,e6)，先選擇e9對應的優(yōu)先種子q4，再選e17對應的優(yōu)先種子q3，這時已經(jīng)覆蓋了所有邊，選擇結(jié)束，優(yōu)先種子集的結(jié)果為{q3,q4}。

步驟2q2不在優(yōu)先種子集中，被跳過。

步驟3測試q3，發(fā)現(xiàn)新路徑{q5,q6}，這時覆蓋的所有邊集合為{e1,e2,e3,e4,e5,e6,e7,e8,e9,e12,e15,e16,e17}。再次調(diào)用算法1，按邊hash 順序(e9,e8,e17,e6)，先選擇e9對應的優(yōu)先種子q5，再選擇e8對應的優(yōu)先種子q6，由于e17已經(jīng)被q6覆蓋，對其跳過處理，最后選e6對應的優(yōu)先種子q2，選擇結(jié)束，結(jié)果為{p5,q6,q2}。

步驟4q4不在優(yōu)先種子集中，被跳過。

步驟5測試q5。

步驟6測試q6。

整個測試過程中，按照種子隊列從前向后的順序判斷是否選擇該種子，沒有對可到達e6的q2和q4進行測試。雖然AFL 存在隨機性變異，也有可能通過其他種子變異出到達e6的測試用例，但是隨機性變異過于盲目，概率過低，導致很難到達e14，從而無法觸發(fā)bug。

上述例子說明了AFL 在一輪循環(huán)中，雖然每次選擇的優(yōu)先種子集能覆蓋所有已發(fā)現(xiàn)的邊，但是真正測試的種子卻可能會漏掉某些邊。上述情況看似概率很小，但是本文通過實驗發(fā)現(xiàn)這種情況大量存在。

針對上述2個問題，本文提出了完全覆蓋種子選擇算法，如算法2所示。

算法2完全覆蓋種子選擇算法

輸入每條邊對應的最好種子T[65536]、種子隊列Q、當前位置queue_cur

輸出選擇結(jié)果S

算法2共分為4個步驟，具體如下。

步驟1把本次循環(huán)中已經(jīng)測試過的種子文件直接加入S并更新C。

步驟2生成0～65535的亂序排列。

步驟3按照步驟2生成的序列從T中挑選種子加入S，并更新C。只有當前位置之后的種子才會被加入S。

步驟4檢查每條邊是否被覆蓋，如果沒有覆蓋，從當前位置向后找到一個可以覆蓋該邊的種子文件，添加到S并更新C。

下面使用數(shù)學歸納法對上述算法的覆蓋完整性進行證明。

1)測試開始時第一次選擇的優(yōu)先種子集顯然可以覆蓋到所有已經(jīng)發(fā)現(xiàn)的邊。

2)假設(shè)第n次選擇的優(yōu)先種子集Qn能夠覆蓋到所有已經(jīng)發(fā)現(xiàn)的邊。當?shù)趎+1次選擇時，當前位置把Qn切分為兩部分，一部分是在當前位置之前（不包含當前位置）的集合Q1，另一部分是當前位置之后（包含當前位置）的集合Q2。如果出現(xiàn)了新的邊，這些邊對應的種子文件會被增加到隊列尾部，這些新種子文件的集合記為Q3。根據(jù)假設(shè)，可推導出Q1∪Q2∪Q3能夠完全覆蓋當前所有的邊。按照算法2，在步驟1中Q1全部被選中，而步驟4是檢查步驟，當發(fā)現(xiàn)某條邊e尚未被覆蓋時，則e?Q1，那么必然有e∈Q2∪Q3，這說明從當前位置向后查找，一定可以找到一個種子文件對應的路徑包含e。因此，步驟4完成后可保證對邊的完全覆蓋。

上述證明說明算法2滿足完全覆蓋性約束，同時算法2采用亂序選擇，且從當前位置開始選擇新的優(yōu)先種子，可以有效避免出現(xiàn)算法1的2個缺點。

3.2 基于邊覆蓋熱度的能量調(diào)度算法

王志等[19]分析僵尸網(wǎng)絡(luò)控制命令時，提出了BBL 覆蓋率的概念，用來描述一個BBL 被執(zhí)行路徑覆蓋的頻繁程度。受此思想啟發(fā)，本文用邊的熱度來描述一條邊被所有路徑覆蓋的次數(shù)，結(jié)合2.4節(jié)的分析，提出了一個新的能量調(diào)度算法。

用N(e)表示邊e的熱度，計算式為

邊的評分與該邊的熱度成反比，即這條邊被覆蓋的次數(shù)越多，評分越低。每個種子文件對應一條執(zhí)行路徑，一條執(zhí)行路徑由多條邊組成。路徑評分為該路徑中邊的評分之和，p(q)為路徑q的評分，定義為

將上述評分進行歸一化，得到路徑q的調(diào)整系數(shù)，定義為

其中，pavg為所有種子對應路徑評分的均值，pmin為最小值，pmax為最大值。分別為預定義的調(diào)整系數(shù)。

1)熱度越低的邊，被給予越高的權(quán)重，有可能得到越多的執(zhí)行機會。

2)fuzzing 往往難以到達很深的代碼塊，該算法對邊評分采用加法，較長路徑的評分會有更多的優(yōu)勢，有利于覆蓋更深的邊。但這也可能導致路徑探索被局限在某一些分支上，針對這個問題，在具體實現(xiàn)中可通過對系數(shù)的調(diào)整來達到一定的平衡。

AFLFast 通過路徑覆蓋頻率來選擇種子，而本文方法則是通過邊覆蓋熱度來選擇種子，通過實驗分析，本文方法在邊覆蓋上比AFLFast 更優(yōu)。

3.3 有效字節(jié)信息的進一步利用

2.5節(jié)中提到的有效字節(jié)機制非常可靠，并且很容易實現(xiàn)，但是也存在如下問題。

1)只有確定性階段使用了有效字節(jié)信息，隨機性階段并沒有使用，未能充分發(fā)揮其效果。

2)有效字節(jié)信息由主進程產(chǎn)生，但主進程速度很慢。在實驗中發(fā)現(xiàn)，有時主進程用一周時間都無法執(zhí)行完一次循環(huán)，這會導致可利用信息非常少。

本文提出了3種進一步利用有效字節(jié)信息的方法。

1)在隨機性階段使用有效字節(jié)信息引導變異。在應用隨機性算法時，按一定概率只對有效字節(jié)進行變異。

2)在從進程中也使用有效字節(jié)信息。保存主進程中記錄的信息，供從進程使用。

3)當存在從進程時，主進程去掉隨機性階段，只處理確定性階段，可加快有效字節(jié)信息的產(chǎn)生。

針對以上方法，需要在確定性階段把eff_map信息記錄到文件，當從進程對這個種子進行測試時，直接加載這個文件。

AFL 中共有16種變異方法，如表2所示。這些方法中，變異位置都是隨機選擇的。efuzz 中對此進行了改進，按一定概率只選擇eff_map 中記錄的位置進行變異，不再是完全隨機選擇變異位置。

表2 隨機性階段的變異方法

隨機性階段會對文件進行多次變異。除了12、13、16這3種方法可能改變種子文件長度外，其他方法不會改變種子文件的長度。一旦變異過程中文件長度發(fā)生變化，eff_map 記錄信息將不再準確。因此，efuzz 把隨機性階段又分成了2個子階段：第一個子階段不采用12、13、16這3種方法；第二個子階段采用所有16種方法，一旦文件長度發(fā)生了變化，就立即恢復到AFL 原有的方式。

4 系統(tǒng)設(shè)計和實現(xiàn)

AFL 的最新開源版本是2.52b，efuzz 擴展了這個版本，共添加了不到1000行的C 代碼，實現(xiàn)了第3節(jié)中描述的技術(shù)。

在算法2中對每個種子進行順序編號，相比原來的算法，僅增加了種子選取順序的隨機化處理和最后的檢查，因此整體增加的CPU 消耗幾乎可以忽略不計。

在能量調(diào)度算法中，對路徑的評分實際上是很難準確定義的，本文采用了比較保守的策略，設(shè)置3個調(diào)整系統(tǒng)的值分別為0.2、0.8、4，且只有在發(fā)現(xiàn)的總路徑數(shù)超過200時，才啟用這一策略。因為該算法中都是浮點計算，為降低計算量，每增加20條以上的新路徑才重新計算一次評分。其次，該算法中所有種子對應的覆蓋信息都要記錄下來，每個種子需要占用8 KB 的內(nèi)存空間。在本文的實驗中，總路徑很少有超過12000的，因此，總計算次數(shù)不會超過600，單個進程的內(nèi)存增長數(shù)不會超過100 MB，對計算機資源的整體消耗非常小。

在確定性階段測試過的種子，需要把它的有效字節(jié)信息記錄到一個對應的以.eff 為后綴的文件。eff 文件中每一位表示該種子的1 B 是否是有效，因此eff 文件大小只有種子文件的，對存儲資源的消耗也非常小。

5 實驗與分析

Klees 等[14]指出了當前fuzzing 實驗中普遍存在的一些問題，并給出建議的測試方法，希望能建立統(tǒng)一的測試標準。本文中的實驗按照他們提出的測試思想，以如下方式進行測試。

1)共選擇了5個常用的目標程序，分別是binutils 程序集中的objdump、nm、readelf，以及l(fā)ibtiff和tcpdump。

2)對每個測試程序選擇了5個有代表性的初始輸入，輸入分別來源于空種子、隨機種子、公開的測試樣本、漏洞的POC（proof of concept），表3是實驗中具體使用的輸入文件。由于有些程序使用空種子和隨機種子無法測試，因此本文使用其他種子代替這2個種子的實驗。

3)涉及對邊覆蓋數(shù)進行比較的實驗，每個實驗都測試30次，每次測試時間為25 h。由于實驗數(shù)據(jù)并不是實時更新的，選取第24 h 這個時間點的數(shù)據(jù)來進行評估。最終結(jié)果取30次的平均值。

4)每次實驗使用一個主進程和一個從進程共同測試，更加接近真實使用環(huán)境。

5)以AFL 和AFLFast 作為比較對象。AFLFast和efuzz 一樣，也是針對AFL 本身算法的改進，且是開源軟件，方便進行實驗。

6)Stephens 等[6]指出使用唯一狀態(tài)轉(zhuǎn)換的數(shù)量作為邊覆蓋的度量是合理的，本文實驗也使用狀態(tài)轉(zhuǎn)換的數(shù)量作為邊覆蓋的度量。

表3 實驗使用測試程序和種子文件

實驗共使用了3臺服務器，都是64位Ubuntu 16.04 LTS系統(tǒng)，CPU為Intel(R)Xeon(R)E5-2620 v4@2.10 GHz，內(nèi)存64 GB，硬盤12 TB。

5.1 邊覆蓋的完整性測試

為了對AFL 和efuzz 的種子選擇算法進行測試，在它們的算法中添加了檢查代碼，每次算法執(zhí)行完時，都對優(yōu)先種子集的邊覆蓋情況進行校驗，檢查本輪循環(huán)中已測試過的優(yōu)先種子和當前位置之后還未測試的優(yōu)先種子是否覆蓋了所有已經(jīng)發(fā)現(xiàn)的邊，如果出現(xiàn)覆蓋不全的情況，則進行日志記錄，并記下每次選擇最多有多少邊未被覆蓋。

實驗用表3中各測試程序?qū)?個文件共同作為該程序的初始化種子，只運行1 h。由于efuzz采用了新的種子選擇算法，保證了覆蓋的完整性，結(jié)果中并未出現(xiàn)覆蓋不全的情況。而AFL 中出現(xiàn)了大量覆蓋不全的情況，如表4所示。

表4 AFL 邊覆蓋不全的記錄

由表4可知，AFL 覆蓋不全的比例非常大，雖然每次未覆蓋的邊數(shù)非常少，但依然說明了AFL 的種子選擇算法在一輪循環(huán)中并未滿足完全覆蓋性約束。

5.2 能量調(diào)度算法和有效字節(jié)信息改進的效果驗證

實驗中開發(fā)了僅啟用能量調(diào)度算法的程序efuzz-Enery 和僅啟用有效字節(jié)信息改進的程序efuzz-Bytes，用于單獨測試這2個改進的有效性。每個改進的測試選擇了5個實驗，每個實驗進行30次，結(jié)果如表5所示。

表5 單獨測量的邊覆蓋數(shù)

從比較結(jié)果來看，efuzz-Enery 相對AFLFast 有比較大的提高，同時比AFL 也有一定提高，證明了本文的能量調(diào)度算法比AFLFast 在邊覆蓋率上更有優(yōu)勢。

通過比較efuzz-Bytes 與AFL 可以看到，efuzz-Bytes 相對AFL 也有少量的提高，說明有效字節(jié)信息的合理利用可以在一定程度上提升AFL 的效果。

5.3 efuzz 與其他工具的比較

實驗對比efuzz、AFL 和AFLFast，使用5個程序，并把每個程序?qū)?個種子文件分別作為初始輸入，共25組實驗。進行該測試的資源要求非常高，總開銷為25×30×25×2×3=112500核·小時=4687.5核·天。表6是24 h 的平均邊覆蓋數(shù)結(jié)果，從整體來看，efuzz 在覆蓋數(shù)上優(yōu)于AFL 和AFLFast。同時也發(fā)現(xiàn)，AFLFast 在平均覆蓋數(shù)上要略差于AFL。

表6 25組實驗的平均邊覆蓋數(shù)

單獨分析每一組實驗，efuzz 幾乎在所有情況下都優(yōu)于AFL 和AFLFast。在nm2中，efuzz 的邊覆蓋數(shù)甚至提高超過20%，但在tcpdump 實驗中，efuzz 表現(xiàn)一般，僅僅略好于AFL，tcpdump2中甚至比AFL 低0.07%。這說明本文的改進方法在絕大多數(shù)情況下提高了邊覆蓋率，但是在極少數(shù)情況下也引入了一些限制。這也進一步說明了Klees 等[14]提出的評估方法的合理性，只有通過大量不同條件下的實驗，才能比較全面地評估fuzzing 工具的有效性。

5.4 LAVA-M 測試

對LAVA-M 中的4個程序，使用其提供的默認種子文件進行測試，每個程序各運行7天。表7中數(shù)據(jù)顯示，AFL 在base64和uniq 中發(fā)現(xiàn)的漏洞數(shù)超過了efuzz，但efuzz 在who 中發(fā)現(xiàn)的漏洞數(shù)遠超AFL，且在4個程序中發(fā)現(xiàn)的漏洞總數(shù)也超過了AFL。

表7 LAVA-M 測試發(fā)現(xiàn)漏洞數(shù)

LAVA-M 在測試程序中插入了許多字符串比較和整數(shù)校驗代碼來阻礙fuzzing 工具，而AFL 的變異算法很難產(chǎn)生適當?shù)妮斎肜@過這些代碼，導致無法到達新的代碼塊，因此AFL 和efuzz 在LAVA-M上的效果都很差。雖然efuzz 在who 上的表現(xiàn)超過了AFL，但發(fā)現(xiàn)的漏洞數(shù)也僅占總漏洞數(shù)的2%。efuzz 在base64和uniq 上差于AFL，再次說明了efuzz 的改進方法在有些情況下反而效果更差，且同樣對校驗性的代碼無法達到很好的繞過效果。

5.5 新的CVE 漏洞

表8是使用efuzz 發(fā)現(xiàn)的3個新的CVE 漏洞，CVE-2018-20671是binutils 中的一個整型溢出漏洞，最終會觸發(fā)堆溢出。CVE-2018-20467是ImageMagick 中的一個拒絕服務漏洞，會造成CPU和內(nèi)存資源的耗盡。CVE-2019-6988是openjpeg 中的一個拒絕服務漏洞，由于其邏輯問題，會長時間占用大量CPU 資源。本文研究團隊向相關(guān)廠商反饋了這些問題，現(xiàn)在這3個漏洞都已經(jīng)得到修復。

表8 efuzz 發(fā)現(xiàn)的漏洞

表8中CVE-2018-20671最早存在于binutils 2.11中的objdump 程序，該版本的發(fā)布時間是2001年。從那時起，絕大多數(shù)的版本都存在這個漏洞。objdump 是一個廣泛使用的二進制工具，也是很多相關(guān)論文中的測試目標程序，大量的研究者對其進行fuzzing，都沒有發(fā)現(xiàn)這個漏洞。本文使用收集整理的種子文件，用一個進程進行30次測試，efuzz平均只需要519 s 就能發(fā)現(xiàn)這個漏洞，而AFL 和AFLFast 在相同時間內(nèi)都無法發(fā)現(xiàn)這個漏洞。這進一步證明了efuzz 的有效性。

6 結(jié)束語

目前，fuzzing 是軟件漏洞挖掘領(lǐng)域最有效的方式之一，覆蓋率的提高一直是研究的重要方向。本文首先基于fuzzing 中邊的完全覆蓋性約束，設(shè)計了完全覆蓋種子選擇算法，并基于邊覆蓋熱度提出了新的能量調(diào)度算法，最后進一步利用了AFL 中的有效字節(jié)信息。上述改進方法也可推廣到其他fuzzing 工具中。從實驗結(jié)果來看，本文實現(xiàn)的efuzz 相對AFL 和AFLFast 在邊覆蓋率和漏洞發(fā)現(xiàn)能力上都有提高，并在常用軟件中發(fā)現(xiàn)了新的漏洞。但efuzz 依然存在很多改進空間，比如在tcpdump 上的效果并不明顯，在tcpdump-2、base64、uniq 上的實驗結(jié)果還要略差于AFL。同時在不知道被測程序結(jié)構(gòu)的情況下進行fuzzing 依然存在盲目性，如何結(jié)合程序分析來獲取更多被測程序信息，以及結(jié)合其他方法進一步提高邊覆蓋率，還需要在接下來的工作中進行更深入的研究。