一種基于時間分片的定向模糊測試

張晨輝，周安民，賈 鵬

（四川大學網絡空間安全學院，成都 610041）

0 引言

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

基于此，本文在定向模糊測試中加入了時間分片的思想，將運行時間分為四個階段，分別為探索階段、短距離優先階段、長距離探索階段和長距離優先階段。每個階段采用不同的能量調度算法，使得每一個種子會在不同的階段發揮其本身的優勢；并且，在保證短距離種子分配到更多能量的同時，長距離種子在某些階段也會分配到更多的能量。實驗中，我們在binutils 測試集共7 個真實程序上進行實驗，結果遠優于AFLGo和Hawkeye。

1 相關技術介紹

1.1 模糊測試

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

1.2 定向模糊測試

定向模糊測試主要應用在補丁檢測、漏洞PoC復現以及靜態分析驗證等場景。對于補丁測試，在程序出現漏洞時通常會打補丁，對打補丁后的版本可以針對補丁代碼段進行測試，查看補丁的有效性；對于漏洞重現，因為部分CVE由于隱私問題不會提供PoC，只會在報告中展示漏洞代碼出現的位置，因此可以利用定向模糊測試進行CVE 復現；在靜態分析驗證中，通過靜態分析得到的可能存在漏洞的代碼，需要通過動態測試來驗證。

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

1.3 符號執行

符號執行是指將程序的約束條件轉化為抽象的符號，則一個程序的輸出即可轉化為一個關于輸入的函數，符號執行可以得出到達目標代碼段所需要的輸入條件。符號執行分為靜態符號執行和動態符號執行，其中靜態符號執行是通過符號值模擬程序執行，而動態符號執行是在程序運行時進行約束求解。雖然符號執行可以達到較高的代碼覆蓋率，但是其狀態空間爆炸、復雜約束無法求解、資源開銷過大等問題限制了符號執行的實際使用。目前，主流的符號執行工具有KLEE、CUTE等。

2 整體流程和核心模塊設計

如圖1所示，SliceAFL 分為兩個部分，靜態分析階段基于AFLGo，通過構建CG（call graph）和CFG（control flow graph），計算每一個基本塊距離目標點的最短距離，距離基于Dijkstra 算法，基本塊級別距離和函數級別距離基于AFLGo 實現。將每一個基本塊的距離編譯時插樁，插樁基于LLVM-Clang。

圖1 SliceAFL整體框架示意圖

在Fuzzing Loop 中，SliceAFL 設置1h 為一輪探索時間，每一輪分為四個階段：前20 分鐘為無差別探索階段，接下來的20 分鐘為短距離優先階段，第40-50 分鐘為長距離探索階段，第50-60 分鐘為長距離優先階段。除了探索階段，其余階段按照需求進行基于模擬退火的能量調度。

2.1 基于時間分片的四個階段

2.1.1 無差別探索階段

本階段旨在為Fuzzer 探索更多狀態的初始種子。基于距離引導的定向模糊測試中，距離越短的種子越可能到達目標點，但是從模糊測試早期一直選擇距離最短的種子很容易使Fuzzer陷入某個局部路徑。所以，無差別探索階段的目的就是盡可能地探索早期程序空間，得到各種狀態的種子，為接下來的幾個階段提供種子基礎。該階段按照種子隊列順序選擇種子，對每一個種子不進行基于模擬退火的能量調度，每一個種子的能量都取決于種子本身的性質而不是時間。因此，經過一段時間的探索后，種子隊列里應當存在各種狀態下的種子。

2.1.2 短距離優先階段

在定向模糊測試中，時間是一個寶貴的資源，所以應當盡早到達目標點。在該階段Fuzzer將全部能量投入到探索短距離的種子，距離越短的種子能量越大，越優先運行，意圖在該階段以最快的速度逼近目標點。但是該階段的問題是一直選擇短距離種子，會忽略長距離種子，而長距離種子也有可能觸發crash，因此需要后續的階段解決這個問題。

2.1.3 長路徑探索階段

該階段是為了彌補第二階段趨向于短路徑的問題，該階段將能量投入到基本塊數量更多的種子。通過插樁時定義bb_passed 標志，以記錄當前種子經過的基本塊數量。本文認為，經過的基本塊數量越多，該種子就探索了程序中更復雜的狀態，這樣的種子具有更大的探索價值。本文在該階段沒有選擇距離最遠的種子，理由如下：距離最遠的種子可能位于程序的初始階段，離目標點過于遠，探索該類種子需要的時間消耗過大；其次，該類種子可以在無差別探索階段被執行，所以長路徑探索階段不追求一味地探索距離最遠的種子，而是探索基本塊數量更多的種子，更復雜的程序狀態意味著更多的可能性，會給目標函數帶來更多觸發crash的可能。

2.1.4 長距離優先階段

該階段作為長路徑探索階段的輔助階段，優先選取上一階段中產生的距離最近的種子，并給予較高的能量。特殊情況下，如果上一階段沒有產生新種子或者所有新種子都已經過一輪變異且沒有產生新路徑，則轉入短距離優先階段。這種情況意味著當前種子隊列中的長路徑探索效果不明顯，所以將當前模糊測試的目標重新變為追求距離更近的種子以快速到達目標點。

2.2 基于基本塊數量的模擬退火算法

在定向模糊測試中，我們通常只有有限的時間，因此AFLGo 采用了模擬退火的能量調度算法。模擬退火是指在隨機游走過程中，該算法總是接受更好的解決方案，但偶爾也會接受較差的方案。溫度是模擬退火算法的一個參數，用來調節接受較差解的概率，并隨退火過程逐漸降低。初始時當=0=1 時，模擬退火算法總是能夠接受較差解，當接近0 時，退化為經典的梯度下降算法，只接受更好的解。

換句話說，當=1 時，Fuzzer 剛開始運行，對于距離長和距離短的種子，都能夠獲得一定的能量，當接近0 時，距離長的種子的能量逐漸變少，距離越近的種子能量越高。然而，AFLGo 的模擬退火算法會導致長路徑“餓死”。由于距離遠的種子可能探索了更多的基本塊數量，基本塊數量越多可能代表著越復雜的程序狀態，因此，在SliceAFL 中認為，程序空間復雜度和經過的基本塊數量正相關，本文保留AFLGo 原有的基于距離的模擬退火算法的同時，增加一個基于基本塊數量的退火算法：

定義annealing-based power schedule（APS），對于給定的seeds 和目標基本塊，APS 將能量定義為：

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

注意，即使在第四階段，即長距離優先階段，雖然優先選擇距離最近的種子，但仍然采用基于基本塊數量的退火算法，因為該階段的種子距離可能離目標點仍然較遠，如果采用基于距離的退火算法可能會造成大部分種子分配的能量過少，詳情參考AFLGo的模擬退火算法。

3 實驗部分

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

表1 SliceAFL與AFLGo和Hawkeye的crash速度對比

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

4 結語

本文提出了一種新的定向模糊測試工具SliceAFL。SliceAFL 在時間有限的前提下將時間分段，并在不同的時間片段采取不同的模擬退火策略，從而更加快速地到達目標點。通過對比實驗可以看出，SliceAFL 在探索長距離crash方面更有優勢，并且在探索目標更多狀態上取得了很好的效果。在未來的工作中，將會進一步完善種子選擇策略，并在提高命中率方面作更多的研究工作。