提高fuzzing邊覆蓋率的改進(jìn)方法賈春福;嚴(yán)盛博;王志;武辰璐;黎航期刊名稱】《《通信學(xué)報(bào)》》年(卷),期】2019(040)011【總頁數(shù)】10頁(P76-85)【關(guān)鍵詞】fuzzing技術(shù);漏洞;AFL;邊覆蓋【作者】賈春福;嚴(yán)盛博;王志;武辰璐;黎航【作者單位】南開大學(xué)網(wǎng)絡(luò)空間安全學(xué)院天津300350;南開大學(xué)人工智能學(xué)院天津300350【正文語種】中文【中圖分類】TP311.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,basicblock)覆蓋數(shù)，Libfuzzer、honggfuzzy和VUzzer［3］都是通過程序插樁來跟蹤BBL的覆蓋信息。另一種是計(jì)算邊覆蓋數(shù)，AFL(Americanfuzzylop)是第一個(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,probabilisticcontextsensitivegrammar)來描述語法特征和語義規(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è)試24h后，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年起就已存在。相關(guān)知識(shí)和技術(shù)概述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è)種子文件。圖1AFL簡(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)過程，直到人工終止。邊覆蓋記錄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算法生成的，記錄覆蓋信息的算法偽代碼如下。edge_hash二cur_bbl人(last_bbl>>1)shared_mem[edge_hash]++很顯然步驟1)中的hash算法會(huì)存在沖突問題，但這不是本文的研究重點(diǎn)。本文把-個(gè)hash記錄直接對(duì)應(yīng)為一條邊覆蓋記錄。種子選擇算法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è)固定的選擇順序。能量調(diào)度Bohme等［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è)問題。有效字節(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(effectormaps)來記錄這個(gè)字節(jié)，在確定性測(cè)試的剩余子階段中只對(duì)eff_map中記錄的字節(jié)進(jìn)行變異。這樣一般可以將測(cè)試的執(zhí)行次數(shù)減少10%~40%左右，而不會(huì)顯著降低覆蓋率。在極端情況下，例如塊對(duì)齊的tar文件，執(zhí)行次數(shù)可能減少高達(dá)90%。fuzzing改進(jìn)方法完全覆蓋種子選擇算法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所示。圖2AFL種子選擇算法缺陷示例表1路徑說明假設(shè)這些邊經(jīng)過hash運(yùn)算后的值，從小到大的順序?yàn)?e9,e8,e17,e6,...)，且測(cè)試按照以下步驟進(jìn)行。步驟1測(cè)試ql,發(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è)試q6o整個(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)出Q1UQ2UQ3能夠完全覆蓋當(dāng)前所有的邊。按照算法2，在步驟1中Q1全部被選中，而步驟4是檢查步驟，當(dāng)發(fā)現(xiàn)某條邊e尚未被覆蓋時(shí)，則eQ1,那么必然有eEQ2UQ3,這說明從當(dāng)前位置向后查找，—定可以找到一個(gè)種子文件對(duì)應(yīng)的路徑包含e。因此，步驟4完成后可保證對(duì)邊的上述證明說明算法2滿足完全覆蓋性約束，同時(shí)算法2采用亂序選擇，且從當(dāng)前位置開始選擇新的優(yōu)先種子，可以有效避免出現(xiàn)算法1的2個(gè)缺點(diǎn)。基于邊覆蓋熱度的能量調(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ù)。種子原來的測(cè)試次數(shù)乘以調(diào)整系數(shù)，即為種子新的測(cè)試次數(shù)。該算法的優(yōu)點(diǎn)如下。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)。有效字節(jié)信息的進(jìn)一步利用節(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原有的方式。系統(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è)種子需要占用8KB的內(nèi)存空間。在本文的實(shí)驗(yàn)中，總路徑很少有超過12000的，因此，總計(jì)算次數(shù)不會(huì)超過600，單個(gè)進(jìn)程的內(nèi)存增長(zhǎng)數(shù)不會(huì)超過100MB，對(duì)計(jì)算機(jī)資源的整體消耗非常小。在確定性階段測(cè)試過的種子，需要把它的有效字節(jié)信息記錄到一個(gè)對(duì)應(yīng)的以.eff為后綴的文件。eff文件中每一位表示該種子的1B是否是有效，因此eff文件大小只有種子文件的，對(duì)存儲(chǔ)資源的消耗也非常小。實(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è)試。共選擇了5個(gè)常用的目標(biāo)程序，分別是binutils程序集中的objdump、nm、readelf，以及l(fā)ibtiff和tcpdump。對(duì)每個(gè)測(cè)試程序選擇了5個(gè)有代表性的初始輸入，輸入分別來源于空種子、隨機(jī)種子、公開的測(cè)試樣本、漏洞的POC(proofofconcept)，表3是實(shí)驗(yàn)中具體使用的輸入文件。由于有些程序使用空種子和隨機(jī)種子無法測(cè)試，因此本文使用其他種子代替這2個(gè)種子的實(shí)驗(yàn)。涉及對(duì)邊覆蓋數(shù)進(jìn)行比較的實(shí)驗(yàn)，每個(gè)實(shí)驗(yàn)都測(cè)試30次，每次測(cè)試時(shí)間為25h由于實(shí)驗(yàn)數(shù)據(jù)并不是實(shí)時(shí)更新的，選取第24h這個(gè)時(shí)間點(diǎn)的數(shù)據(jù)來進(jìn)行評(píng)估。最終結(jié)果取30次的平均值。每次實(shí)驗(yàn)使用一個(gè)主進(jìn)程和一個(gè)從進(jìn)程共同測(cè)試，更加接近真實(shí)使用環(huán)境。以AFL和AFLFast作為比較對(duì)象。AFLFast和efuzz一樣，也是針對(duì)AFL本身算法的改進(jìn)，且是開源軟件，方便進(jìn)行實(shí)驗(yàn)。Stephens等［6］指出使用唯一狀態(tài)轉(zhuǎn)換的數(shù)量作為邊覆蓋的度量是合理的，本文實(shí)驗(yàn)也使用狀態(tài)轉(zhuǎn)換的數(shù)量作為邊覆蓋的度量。表3實(shí)驗(yàn)使用測(cè)試程序和種子文件注：empty:空種子文件，rand100:100個(gè)隨機(jī)字節(jié)，regdbdump:64位Ubuntu16.04中的/sbin/regdbdump，CVE-*:對(duì)應(yīng)CVE漏洞的POC樣本，其他：測(cè)試程序自身提供的測(cè)試樣本。實(shí)驗(yàn)共使用了3臺(tái)服務(wù)器，都是64位Ubuntu16.04LTS系統(tǒng)，CPU為Intel(R)Xeon(R)*****************，內(nèi)存64GB，硬盤12TB。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)行1h。由于efuzz采用了新的種子選擇算法，保證了覆蓋的完整性，結(jié)果中并未出現(xiàn)覆蓋不全的情況。而AFL中出現(xiàn)了大量覆蓋不全的情況，如表4所示。表4AFL邊覆蓋不全的記錄由表4可知，AFL覆蓋不全的比例非常大，雖然每次未覆蓋的邊數(shù)非常少，但依然說明了AFL的種子選擇算法在一輪循環(huán)中并未滿足完全覆蓋性約束。能量調(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ù)注：tcpdump1:使用表3中的第一個(gè)種子文件測(cè)試tcpdump，F(xiàn)ast：AFLFastEnery：efuzz-Enery，Bytes：efuzz-Bytes，Enery|AFL:efuzz-Enery相對(duì)AFL的提高。從比較結(jié)果來看，efuzz-Enery相對(duì)AFLFast有比較大的提高，同時(shí)比AFL也有—定提高，證明了本文的能量調(diào)度算法比AFLFast在邊覆蓋率上更有優(yōu)勢(shì)。通過比較efuzz-Bytes與AFL可以看到，efuzz-Bytes相對(duì)AFL也有少量的提高，說明有效字節(jié)信息的合理利用可以在一定程度上提升AFL的效果。efuzz與其他工具的比較實(shí)驗(yàn)對(duì)比efuzz、AFL和AFLFast，使用5個(gè)程序，并把每個(gè)程序?qū)?yīng)的5個(gè)種子文件分別作為初始輸入，共25組實(shí)驗(yàn)。進(jìn)行該測(cè)試的資源要求非常高，總開銷為25x30x25x2x3=112500核?小時(shí)=4687.5核?天。表6是24h的平均邊覆蓋數(shù)結(jié)果，從整體來看，efuzz在覆蓋數(shù)上優(yōu)于AFL和AFLFast。同時(shí)也發(fā)現(xiàn)，AFLFast在平均覆蓋數(shù)上要略差于AFL。表625組實(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工具的有效性。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。表7LAVA-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ù)表8efuzz發(fā)現(xiàn)的漏洞表8中CVE-2018-20671最早存在于binutils2.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平均只需要519s就能發(fā)現(xiàn)這個(gè)漏洞，而AFL和AFLFast在相同時(shí)間內(nèi)都無法發(fā)現(xiàn)這個(gè)漏洞。這進(jìn)一步證明了efuzz的有效性。結(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)行更深入的研究。相關(guān)文獻(xiàn)】SUTTONM,GREENEA,AMINIP.Fuzzing:bruteforcevulnerabilitydiscovery[M].NJ:PearsonEducation,2007.CHENC,CUIB,MAJ,etal.Asystematicreviewoffuzzingtechniques[J].Computers&Security,2018,75(1):118-137.RAWATS,JAINV,KUMARA,etal.VUzzer:application-awareevolutionaryfuzzing[C]//ISOCNetworkandDistributedSystemSecuritySymposium.ISOC,2017:1-14.B0HMEM,PHAMVT,NGUYENMD,etal.Directedgreyboxfuzzing[C]//ACMConfereneeonComputerandCommunicationsSecurity.ACM,2017:2329-2344CHENH,XUEY,LIY,etal.Hawkeye:towardsadesireddirectedgrey-boxfuzzer[C]//ACMConferenceonComputerandCommunicationsSecurity.ACM,2018:2095-2108.STEPHENSN,GROSENJ,SALLSC,etal.Driller:augmentingfuzzingthroughselectivesymbolicexecution[C]//ISOCNetworkandDistributedSystemSecuritySymposium.ISOC,2016:1-16.SHOSHITAISHVILIY,WANGR,SALLSC,etal.Sok:stateoftheartofwar:offensivetechniquesinbinaryanalysis[C]//IEEESymposiumonSecurityandPrivacy.IEEE,2016:138-157.OGNAWALAS,KILGERF,PRETSCHNERA.Compositionalfuzzingaidedbytargetedsymbolicexecution[J].arXivPreprint,arXiv:1903.02981,2019.CADARC,DUNBARD,ENGLERDR.KLEE:unassistedandautomaticgenerationofhigh-coveragetestsforcomplexsystemsprograms[C]//USENIXSymposiumonOperatingSystemsDesignandImplementation.USENIX,2008:209-224.孫鴻宇，何遠(yuǎn)，王基策，等?人工智能技術(shù)在安全漏洞領(lǐng)域的應(yīng)用[J]?通信學(xué)報(bào),2018,39(8):1-17.SUNHY,HEY,WANGJC,etal.Applicationofartificialintelligencetechnologyinthefield