張晨輝，周安民，賈 鵬

（四川大學(xué)網(wǎng)絡(luò)空間安全學(xué)院，成都 610041）

0 引言

模糊測(cè)試是現(xiàn)代漏洞挖掘最有效的技術(shù)之一，其為被測(cè)程序提供大量輸入，并監(jiān)視其出現(xiàn)的異常行為（例如堆棧溢出、越界讀寫(xiě)、內(nèi)存泄漏等）。自從模糊測(cè)試方法問(wèn)世以來(lái)，其在業(yè)界和學(xué)界受到廣泛關(guān)注并不斷發(fā)展，研究人員開(kāi)發(fā)了各種工具應(yīng)用于不同的測(cè)試場(chǎng)景。近年來(lái)，隨著AFL（American Fuzzing Loop）家族的出現(xiàn)，灰盒模糊測(cè)試的發(fā)展不斷完善，并取得了優(yōu)秀的成果。定向灰盒模糊測(cè)試的概念提出于2017年發(fā)表于CCS 的《Directed Greybox Fuzzing》，定向模糊測(cè)試需要事先指定目標(biāo)點(diǎn)，例如，在有源碼的情況下可以指定代碼行數(shù)，定向模糊測(cè)試的目的就是為了使輸入到達(dá)目標(biāo)點(diǎn)，以探測(cè)該代碼段是否存在安全問(wèn)題。定向模糊測(cè)試主要應(yīng)用在補(bǔ)丁檢測(cè)、漏洞PoC復(fù)現(xiàn)以及靜態(tài)分析驗(yàn)證等場(chǎng)景。但目前的定向模糊測(cè)試存在種子能量分配不均的問(wèn)題，由于能量分配采用模擬退火算法，距離目標(biāo)點(diǎn)近的種子分配的能量過(guò)多，而距離遠(yuǎn)的種子可能會(huì)被“餓死”；又或者設(shè)置種子能量與時(shí)間不相關(guān)，可以使每個(gè)種子得到對(duì)應(yīng)的能量但同時(shí)忽視了時(shí)間有限這一因素。

基于此，本文在定向模糊測(cè)試中加入了時(shí)間分片的思想，將運(yùn)行時(shí)間分為四個(gè)階段，分別為探索階段、短距離優(yōu)先階段、長(zhǎng)距離探索階段和長(zhǎng)距離優(yōu)先階段。每個(gè)階段采用不同的能量調(diào)度算法，使得每一個(gè)種子會(huì)在不同的階段發(fā)揮其本身的優(yōu)勢(shì)；并且，在保證短距離種子分配到更多能量的同時(shí)，長(zhǎng)距離種子在某些階段也會(huì)分配到更多的能量。實(shí)驗(yàn)中，我們?cè)赽inutils 測(cè)試集共7 個(gè)真實(shí)程序上進(jìn)行實(shí)驗(yàn)，結(jié)果遠(yuǎn)優(yōu)于AFLGo和Hawkeye。

1 相關(guān)技術(shù)介紹

1.1 模糊測(cè)試

模糊測(cè)試是指向待測(cè)程序提供大量畸形數(shù)據(jù)作為輸入，監(jiān)視程序的異常情況，基于導(dǎo)致異常的輸入進(jìn)行分析發(fā)現(xiàn)漏洞的一種方法。根據(jù)測(cè)試用例生成的方法，可以分為基于生成的模糊測(cè)試和基于變異的模糊測(cè)試。前者需要已知的數(shù)據(jù)格式，在不破壞格式的前提下生成測(cè)試用例；后者是將初始數(shù)據(jù)進(jìn)行大量變異生成測(cè)試用例。按照對(duì)待測(cè)程序的分析程度，可以分為白盒模糊測(cè)試、灰盒模糊測(cè)試和黑盒模糊測(cè)試。白盒模糊測(cè)需要全部源代碼，黑盒則不需要任何待測(cè)程序的信息，灰盒模糊測(cè)試介于二者之間，通過(guò)運(yùn)行時(shí)的反饋來(lái)指導(dǎo)模糊測(cè)試。模糊測(cè)試已在漏洞挖掘領(lǐng)域發(fā)揮重要作用，但其仍然面臨著許多問(wèn)題：如代碼覆蓋率不高、不能完全探索程序空間等。目前主流的模糊測(cè)試工具有AFL、Peach、AFLGo、Hawkeye等。

1.2 定向模糊測(cè)試

定向模糊測(cè)試主要應(yīng)用在補(bǔ)丁檢測(cè)、漏洞PoC復(fù)現(xiàn)以及靜態(tài)分析驗(yàn)證等場(chǎng)景。對(duì)于補(bǔ)丁測(cè)試，在程序出現(xiàn)漏洞時(shí)通常會(huì)打補(bǔ)丁，對(duì)打補(bǔ)丁后的版本可以針對(duì)補(bǔ)丁代碼段進(jìn)行測(cè)試，查看補(bǔ)丁的有效性；對(duì)于漏洞重現(xiàn)，因?yàn)椴糠諧VE由于隱私問(wèn)題不會(huì)提供PoC，只會(huì)在報(bào)告中展示漏洞代碼出現(xiàn)的位置，因此可以利用定向模糊測(cè)試進(jìn)行CVE 復(fù)現(xiàn)；在靜態(tài)分析驗(yàn)證中，通過(guò)靜態(tài)分析得到的可能存在漏洞的代碼，需要通過(guò)動(dòng)態(tài)測(cè)試來(lái)驗(yàn)證。

定向模糊測(cè)試的基本原理如下：定向模糊測(cè)試實(shí)現(xiàn)給定目標(biāo)代碼段，通過(guò)靜態(tài)分析提取函數(shù)調(diào)用圖（Call Graph，CG）和控制流圖（Control Flow Graph，CFG），計(jì)算所有基本塊到達(dá)目標(biāo)點(diǎn)的最小距離，如Dijkstra 距離，這些距離用于在模糊測(cè)試時(shí)計(jì)算種子的優(yōu)先度、能量分配等，使定向模糊測(cè)試趨向于目標(biāo)點(diǎn)。在靜態(tài)分析中，由于LLVM 可跨平臺(tái)、編譯速度顯著優(yōu)于gcc，并且可以設(shè)計(jì)插件提取CFG 和CG，因此在定向模糊測(cè)試中，通過(guò)LLVM 插樁的方式將距離和覆蓋率信息插入目標(biāo)程序。

1.3 符號(hào)執(zhí)行

符號(hào)執(zhí)行是指將程序的約束條件轉(zhuǎn)化為抽象的符號(hào)，則一個(gè)程序的輸出即可轉(zhuǎn)化為一個(gè)關(guān)于輸入的函數(shù)，符號(hào)執(zhí)行可以得出到達(dá)目標(biāo)代碼段所需要的輸入條件。符號(hào)執(zhí)行分為靜態(tài)符號(hào)執(zhí)行和動(dòng)態(tài)符號(hào)執(zhí)行，其中靜態(tài)符號(hào)執(zhí)行是通過(guò)符號(hào)值模擬程序執(zhí)行，而動(dòng)態(tài)符號(hào)執(zhí)行是在程序運(yùn)行時(shí)進(jìn)行約束求解。雖然符號(hào)執(zhí)行可以達(dá)到較高的代碼覆蓋率，但是其狀態(tài)空間爆炸、復(fù)雜約束無(wú)法求解、資源開(kāi)銷(xiāo)過(guò)大等問(wèn)題限制了符號(hào)執(zhí)行的實(shí)際使用。目前，主流的符號(hào)執(zhí)行工具有KLEE、CUTE等。

2 整體流程和核心模塊設(shè)計(jì)

如圖1所示，SliceAFL 分為兩個(gè)部分，靜態(tài)分析階段基于AFLGo，通過(guò)構(gòu)建CG（call graph）和CFG（control flow graph），計(jì)算每一個(gè)基本塊距離目標(biāo)點(diǎn)的最短距離，距離基于Dijkstra 算法，基本塊級(jí)別距離和函數(shù)級(jí)別距離基于AFLGo 實(shí)現(xiàn)。將每一個(gè)基本塊的距離編譯時(shí)插樁，插樁基于LLVM-Clang。

圖1 SliceAFL整體框架示意圖

在Fuzzing Loop 中，SliceAFL 設(shè)置1h 為一輪探索時(shí)間，每一輪分為四個(gè)階段：前20 分鐘為無(wú)差別探索階段，接下來(lái)的20 分鐘為短距離優(yōu)先階段，第40-50 分鐘為長(zhǎng)距離探索階段，第50-60 分鐘為長(zhǎng)距離優(yōu)先階段。除了探索階段，其余階段按照需求進(jìn)行基于模擬退火的能量調(diào)度。

2.1 基于時(shí)間分片的四個(gè)階段

2.1.1 無(wú)差別探索階段

本階段旨在為Fuzzer 探索更多狀態(tài)的初始種子?；诰嚯x引導(dǎo)的定向模糊測(cè)試中，距離越短的種子越可能到達(dá)目標(biāo)點(diǎn)，但是從模糊測(cè)試早期一直選擇距離最短的種子很容易使Fuzzer陷入某個(gè)局部路徑。所以，無(wú)差別探索階段的目的就是盡可能地探索早期程序空間，得到各種狀態(tài)的種子，為接下來(lái)的幾個(gè)階段提供種子基礎(chǔ)。該階段按照種子隊(duì)列順序選擇種子，對(duì)每一個(gè)種子不進(jìn)行基于模擬退火的能量調(diào)度，每一個(gè)種子的能量都取決于種子本身的性質(zhì)而不是時(shí)間。因此，經(jīng)過(guò)一段時(shí)間的探索后，種子隊(duì)列里應(yīng)當(dāng)存在各種狀態(tài)下的種子。

2.1.2 短距離優(yōu)先階段

在定向模糊測(cè)試中，時(shí)間是一個(gè)寶貴的資源，所以應(yīng)當(dāng)盡早到達(dá)目標(biāo)點(diǎn)。在該階段Fuzzer將全部能量投入到探索短距離的種子，距離越短的種子能量越大，越優(yōu)先運(yùn)行，意圖在該階段以最快的速度逼近目標(biāo)點(diǎn)。但是該階段的問(wèn)題是一直選擇短距離種子，會(huì)忽略長(zhǎng)距離種子，而長(zhǎng)距離種子也有可能觸發(fā)crash，因此需要后續(xù)的階段解決這個(gè)問(wèn)題。

2.1.3 長(zhǎng)路徑探索階段

該階段是為了彌補(bǔ)第二階段趨向于短路徑的問(wèn)題，該階段將能量投入到基本塊數(shù)量更多的種子。通過(guò)插樁時(shí)定義bb_passed 標(biāo)志，以記錄當(dāng)前種子經(jīng)過(guò)的基本塊數(shù)量。本文認(rèn)為，經(jīng)過(guò)的基本塊數(shù)量越多，該種子就探索了程序中更復(fù)雜的狀態(tài)，這樣的種子具有更大的探索價(jià)值。本文在該階段沒(méi)有選擇距離最遠(yuǎn)的種子，理由如下：距離最遠(yuǎn)的種子可能位于程序的初始階段，離目標(biāo)點(diǎn)過(guò)于遠(yuǎn)，探索該類(lèi)種子需要的時(shí)間消耗過(guò)大；其次，該類(lèi)種子可以在無(wú)差別探索階段被執(zhí)行，所以長(zhǎng)路徑探索階段不追求一味地探索距離最遠(yuǎn)的種子，而是探索基本塊數(shù)量更多的種子，更復(fù)雜的程序狀態(tài)意味著更多的可能性，會(huì)給目標(biāo)函數(shù)帶來(lái)更多觸發(fā)crash的可能。

2.1.4 長(zhǎng)距離優(yōu)先階段

該階段作為長(zhǎng)路徑探索階段的輔助階段，優(yōu)先選取上一階段中產(chǎn)生的距離最近的種子，并給予較高的能量。特殊情況下，如果上一階段沒(méi)有產(chǎn)生新種子或者所有新種子都已經(jīng)過(guò)一輪變異且沒(méi)有產(chǎn)生新路徑，則轉(zhuǎn)入短距離優(yōu)先階段。這種情況意味著當(dāng)前種子隊(duì)列中的長(zhǎng)路徑探索效果不明顯，所以將當(dāng)前模糊測(cè)試的目標(biāo)重新變?yōu)樽非缶嚯x更近的種子以快速到達(dá)目標(biāo)點(diǎn)。

2.2 基于基本塊數(shù)量的模擬退火算法

在定向模糊測(cè)試中，我們通常只有有限的時(shí)間，因此AFLGo 采用了模擬退火的能量調(diào)度算法。模擬退火是指在隨機(jī)游走過(guò)程中，該算法總是接受更好的解決方案，但偶爾也會(huì)接受較差的方案。溫度是模擬退火算法的一個(gè)參數(shù)，用來(lái)調(diào)節(jié)接受較差解的概率，并隨退火過(guò)程逐漸降低。初始時(shí)當(dāng)=0=1 時(shí)，模擬退火算法總是能夠接受較差解，當(dāng)接近0 時(shí)，退化為經(jīng)典的梯度下降算法，只接受更好的解。

換句話(huà)說(shuō)，當(dāng)=1 時(shí)，F(xiàn)uzzer 剛開(kāi)始運(yùn)行，對(duì)于距離長(zhǎng)和距離短的種子，都能夠獲得一定的能量，當(dāng)接近0 時(shí)，距離長(zhǎng)的種子的能量逐漸變少，距離越近的種子能量越高。然而，AFLGo 的模擬退火算法會(huì)導(dǎo)致長(zhǎng)路徑“餓死”。由于距離遠(yuǎn)的種子可能探索了更多的基本塊數(shù)量，基本塊數(shù)量越多可能代表著越復(fù)雜的程序狀態(tài)，因此，在SliceAFL 中認(rèn)為，程序空間復(fù)雜度和經(jīng)過(guò)的基本塊數(shù)量正相關(guān)，本文保留AFLGo 原有的基于距離的模擬退火算法的同時(shí)，增加一個(gè)基于基本塊數(shù)量的退火算法：

定義annealing-based power schedule（APS），對(duì)于給定的seeds 和目標(biāo)基本塊，APS 將能量定義為：

其中，() =/，表示當(dāng)前種子經(jīng)過(guò)的基本塊數(shù)量和所有種子經(jīng)過(guò)的最大基本塊數(shù)量的比值，保證了能量∈[0,1]；，表示探索的時(shí)間。在長(zhǎng)路徑探索階段，剛開(kāi)始運(yùn)行時(shí)，APS 將相同的能量分配給經(jīng)過(guò)不同基本塊數(shù)量的種子，隨著時(shí)間的推移，經(jīng)過(guò)基本塊數(shù)量越多的種子獲得越來(lái)越多的能量，而經(jīng)過(guò)基本塊數(shù)量較少的種子獲得的能量越來(lái)越少。SliceAFL在長(zhǎng)距離探索階段和長(zhǎng)距離優(yōu)先階段不采用原有的基于距離退火，而是采用上述的基于基本塊數(shù)量退火，保證了在短路徑優(yōu)先的前提下，同時(shí)探索了長(zhǎng)路徑的可能性。

注意，即使在第四階段，即長(zhǎng)距離優(yōu)先階段，雖然優(yōu)先選擇距離最近的種子，但仍然采用基于基本塊數(shù)量的退火算法，因?yàn)樵撾A段的種子距離可能離目標(biāo)點(diǎn)仍然較遠(yuǎn)，如果采用基于距離的退火算法可能會(huì)造成大部分種子分配的能量過(guò)少，詳情參考AFLGo的模擬退火算法。

3 實(shí)驗(yàn)部分

為了驗(yàn)證SliceAFL 的有效性，本文選取AFLGo 和Hawkeye 為對(duì)比對(duì)象。由于本文關(guān)注復(fù)現(xiàn)漏洞時(shí)間快慢的對(duì)比，以及長(zhǎng)路徑的探索能力，所以使用Binutils測(cè)試集以及AFLGo 曾經(jīng)復(fù)現(xiàn)過(guò)的部分漏洞程序進(jìn)行實(shí)驗(yàn)對(duì)比。由于Hawkeye 并沒(méi)有公開(kāi)源碼，所以本文中關(guān)于Hawkeye 的對(duì)比參考Hawkeye 文章中的數(shù)據(jù)結(jié)果。本文的實(shí)驗(yàn)運(yùn)行在Inter Xeon CPU E5-2697 v3@ 2.60 GHz，包括14 個(gè)核心處理器，實(shí)驗(yàn)中使用10 個(gè)核心處理器，另外4 個(gè)留給其他程序。系統(tǒng)版本為Ubuntu 16.04 LTS。本文在Binutils上進(jìn)行了測(cè)試，并與AFLGo，Hawkeye 進(jìn)行對(duì)比。同樣地，本文將每個(gè)實(shí)驗(yàn)運(yùn)行20 次，時(shí)間預(yù)算設(shè)置為8個(gè)小時(shí)，初始種子輸入文件只包含一個(gè)換行符（由echo“”＞in/file）生成，結(jié)果見(jiàn)表1。

表1 SliceAFL與AFLGo和Hawkeye的crash速度對(duì)比

其中Runs 代表復(fù)現(xiàn)該CVE 的次數(shù)，μTTE（s）表示平均復(fù)現(xiàn)該CVE 需要的時(shí)間，F(xiàn)actors 表示與SliceAFL 的μTTE（s）的倍數(shù)關(guān)系。在這些漏洞中，除了CVE-2016-4491 和CVE-2016-6131，其他CVE 漏洞的復(fù)現(xiàn)時(shí)間都很短。AFLGo 在文章中同時(shí)對(duì)比了AFL 的復(fù)現(xiàn)能力，AFL 也僅僅比AFLGo 慢了幾分鐘，因此在這些漏洞上對(duì)比定向模糊測(cè)試的能力并不準(zhǔn)確。而對(duì)于CVE-2016-4491 和CVE-2016-6131，AFLGo 與Hawkeye 發(fā)現(xiàn)探測(cè)到這兩個(gè)漏洞的時(shí)間都需要5 個(gè)小時(shí)以上，這種探索時(shí)間較長(zhǎng)的CVE 才更能體現(xiàn)出定向Fuzz 的能力。SliceAFL 對(duì)于CVE-2016-4491 和CVE-2016-6131 都取得了更好的成果，擊中次數(shù)略高于Hawkeye（分別為9 次和10 次），TTE遠(yuǎn)短于Hawkeye（15006 s和15872 s）。這種基于時(shí)間分片的思想取得了更好的效果。

4 結(jié)語(yǔ)

本文提出了一種新的定向模糊測(cè)試工具SliceAFL。SliceAFL 在時(shí)間有限的前提下將時(shí)間分段，并在不同的時(shí)間片段采取不同的模擬退火策略，從而更加快速地到達(dá)目標(biāo)點(diǎn)。通過(guò)對(duì)比實(shí)驗(yàn)可以看出，SliceAFL 在探索長(zhǎng)距離crash方面更有優(yōu)勢(shì)，并且在探索目標(biāo)更多狀態(tài)上取得了很好的效果。在未來(lái)的工作中，將會(huì)進(jìn)一步完善種子選擇策略，并在提高命中率方面作更多的研究工作。