賈春福，嚴(yán)盛博，王志，武辰璐，黎航

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

1 引言

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

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

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

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

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

針對(duì)上述問題，本文著眼于AFL 算法的缺陷，同時(shí)對(duì)一些功能進(jìn)行了改進(jìn)，具體包括以下幾個(gè)方面。

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

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

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

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

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

2.1 AFL 概述

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

圖1展示了AFL 的簡(jiǎn)易流程，具體步驟如下。

步驟1提供一個(gè)初始輸入集加入種子隊(duì)列。

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

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

圖1 AFL 簡(jiǎn)易流程

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

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

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

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

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

2.2 邊覆蓋記錄

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

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

2)shared_mem [ edge_ hash ]++

很顯然步驟1)中的hash 算法會(huì)存在沖突問題，但這不是本文的研究重點(diǎn)。本文把一個(gè)hash 記錄直接對(duì)應(yīng)為一條邊覆蓋記錄。

2.3 種子選擇算法

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

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

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

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

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

算法1AFL 的種子選擇算法

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

輸出選擇結(jié)果S

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

2.4 能量調(diào)度

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

2.5 有效字節(jié)信息

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

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

主進(jìn)程和從進(jìn)程。AFL 可以有多個(gè)進(jìn)程并行工作，主進(jìn)程對(duì)每個(gè)選中的種子先進(jìn)行確定性測(cè)試，再進(jìn)行隨機(jī)性測(cè)試；從進(jìn)程只進(jìn)行隨機(jī)性測(cè)試。同時(shí)，主進(jìn)程和從進(jìn)程之間定期進(jìn)行種子同步。

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

3 fuzzing 改進(jìn)方法

3.1 完全覆蓋種子選擇算法

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

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

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

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

代碼1編譯后對(duì)應(yīng)的控制流程如圖2所示。

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

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

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

表1 路徑說明

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

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

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

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

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

步驟5測(cè)試q5。

步驟6測(cè)試q6。

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

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

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

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

輸入每條邊對(duì)應(yīng)的最好種子T[65536]、種子隊(duì)列Q、當(dāng)前位置queue_cur

輸出選擇結(jié)果S

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1)在隨機(jī)性階段使用有效字節(jié)信息引導(dǎo)變異。在應(yīng)用隨機(jī)性算法時(shí)，按一定概率只對(duì)有效字節(jié)進(jìn)行變異。

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

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

針對(duì)以上方法，需要在確定性階段把eff_map信息記錄到文件，當(dāng)從進(jìn)程對(duì)這個(gè)種子進(jìn)行測(cè)試時(shí)，直接加載這個(gè)文件。

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

表2 隨機(jī)性階段的變異方法

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

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

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

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

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

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

5 實(shí)驗(yàn)與分析

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

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

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

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

4)每次實(shí)驗(yàn)使用一個(gè)主進(jìn)程和一個(gè)從進(jìn)程共同測(cè)試，更加接近真實(shí)使用環(huán)境。

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

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

表3 實(shí)驗(yàn)使用測(cè)試程序和種子文件

實(shí)驗(yàn)共使用了3臺(tái)服務(wù)器，都是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 邊覆蓋的完整性測(cè)試

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

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

表4 AFL 邊覆蓋不全的記錄

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

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

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

表5 單獨(dú)測(cè)量的邊覆蓋數(shù)

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

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

5.3 efuzz 與其他工具的比較

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

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

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

5.4 LAVA-M 測(cè)試

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

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

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

5.5 新的CVE 漏洞

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

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

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

6 結(jié)束語

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