結構狀態覆蓋導向的灰盒模糊測試技術

劉華淵，蘇云飛，李瑞林，唐朝京

(國防科技大學 電子科學學院，湖南 長沙 410073)

1 代碼覆蓋導向的模糊測試問題分析

代碼覆蓋率導向的模糊測試技術是一種灰盒模糊測試技術，其通過提高代碼覆蓋率來發現程序中的漏洞。AFL[1](American Fuzzy Lop)是典型的代碼覆蓋導向的模糊測試工具，FairFuzz[2]、AFLFast[3]等工具都是基于AFL實現的。AFL通過輕量級的代碼插樁，在運行時收集程序代碼覆蓋信息，并以此為依據保留提升代碼覆蓋的種子文件。此類工具主要區別在代碼覆蓋率的計算方式、種子篩選和能量調度策略[4]等方面?；液心：郎y試技術[5-8]和靜態分析[9-10]、符號執行[11-13]、污點分析[14-16]等技術結合，能夠有效地增加代碼覆蓋率。

以圖1所示代碼來說明筆者關注的問題。該代碼來自于RHG比賽中的heap buffer over flow BRHG-A006。此類程序包含while-switch-case結構，不同的輸入會導致不同的case語句被執行。

圖1 BRHG-A006簡化版代碼

該程序依據opt的值執行不同的堆操作模塊，包括堆申請、堆內存寫、堆內存讀、堆內存釋放模塊。漏洞觸發條件為堆申請空間小于堆內存寫空間。

圖2 崩潰樣本控制流圖

圖2給出BRHG-A006中觸發堆溢出漏洞的一個最簡化的崩潰樣本的控制流圖。add會分配0x20長度的堆塊，edit可以往堆塊中寫入任意長度的數據。觸發漏洞的狀態覆蓋條件并不復雜，但AFL、FairFuzz、AFLFast在一個小時內均無法發現存在的堆溢出漏洞。

1.1 測試用例的結構狀態分布

1.2 基本塊跳轉作為反饋指標的局限性

基于AFL實現的模糊測試工具將基本塊跳轉的覆蓋次數作為評價變異效果的指標。考慮兩個結構狀態序列長度為4的測試用例的執行跡 case1-case4-case2-case2 和case1-case2-case2-case4，這兩個測試用例在AFL的測試用例評價策略中是等價的，因此后變異出來的測試用例會被丟棄。一些漏洞(諸如堆溢出、釋放后重用等)狀態激活時對內存狀態有嚴格要求。在圖1所示這類程序中，內存狀態跟結構覆蓋狀態有對應關系，隊列中種子的結構狀態分布不均勻，導致模糊測試過程中總是針對少數幾種特定結構狀態進行變異。FairFuzz通過加大覆蓋較少分支的變異次數來均勻化分支分布，提升總體代碼覆蓋速度，同樣無法解決完全結構狀態不均勻的問題。

使用AFL、FairFuzz對BRHG-A006(簡化版)、BRHG-A007、BRHG-A0014測試24 h，并收集隊列中序列長度為4的結構狀態，結果如圖3所示。

在圖3中，(a)為BRHG-A006(簡化版)、(b)為BRHG-A007、(c)為BRHG-A0014的結構狀態覆蓋對比圖。在雷達圖中，圓周上的坐標(如1222)表示測試用例的結構狀態(case1-case2-case2-case2)，半徑標度為結構狀態的覆蓋次數。為了消除case語句中基本塊數量不同導致的誤差，將BRHG-A006(改)的代碼中各個case的代碼修改成完全一致，以保證基本塊數量一致。不難發現，AFL和FairFuzz在隊列中的結構狀態覆蓋分布不均勻，導致模糊測試過程中有價值的結構狀態覆蓋變異次數過少甚至被丟棄。收集全部變異產生的測試用例的結構狀態序列進行分析，在隊列內種子越多、代碼覆蓋越充分的情況下，新的結構狀態覆蓋種子被丟棄的現象越明顯。

圖3 用AFL、FairFuzz 測試24 h的隊列結構狀態覆蓋對比圖

1.3 特定結構的普適性分析

在DARPA公布的CGC測試集中，60個包含堆類型漏洞(51個堆溢出，9個釋放后重用)中有12個程序是while-swtich-case結構，22個是while-嵌套if結構(可以轉換成while-switch-case結構)。

真實軟件中存在的一部分漏洞符合圖1描述的代碼結構特點，如 cve-2018-20623(use after free)、cve-2020-6224(heap based buffer overflow)、cve-2020-9273(double free)。這類程序包含對圖片、音頻的解析功能，涉及大量的堆內存申請訪問釋放操作。軟件設計者出于代碼復用的考慮，通常采用switch-case區分不同類型的文件格式。

圖4 隊列結構狀態覆蓋對比圖

圖4 (a)是jhead-3.03中AFL和FairFuzz測試24 h的隊列中結構狀態覆蓋分布圖。兩種引擎的結構狀態分布類似。受真實軟件中程序功能限制，結構狀態覆蓋的雷達圖分布無法成圓環狀分布，分布優化目標呈圓弧狀分布。圖4(b)是CGC中Modern_Faimly_Tree 利用Angora[10]測試24 h的隊列中結構狀態覆蓋分布圖。此時程序總體的代碼覆蓋率僅為23%，switch結構只覆蓋了20%。這種結構覆蓋率不足的軟件不能進行結構狀態覆蓋分析。

基于上述兩個觀察實驗，需主要解決代碼覆蓋導向的模糊測試技術中的兩個問題：

(1) 在代碼覆蓋足夠的情況下，解決產生新的結構狀態覆蓋的測試用例被丟棄的問題；

(2) 結構狀態覆蓋變異次數不均勻的問題。

2 解決方案

對現有的代碼覆蓋率導向的灰盒模糊測試方法進行分析。通過對源碼進行結構狀態插樁分析和運行時統計結構狀態覆蓋分布分析，設計并實現了原型系統SFL，均勻化了程序狀態分布，加速了漏洞發現過程。

2.1 源碼結構狀態插樁分析

程序中會包含許多的while-switch-case結構。為了避免switch-case嵌套導致的結構狀態爆炸，每次只對一個目標結構進行插樁。插樁完成后獲得一組目標程序，依據軟件歷史cve的補丁信息，優先選擇包含歷史漏洞的目標結構進行模糊測試。

轉換while-if-else程序，在while-if-else結構中找到能夠跳轉回while語句的基本塊，以此作為插樁點。

2.2 結構狀態分布的統計度量

定義2給出了程序的結構狀態分布的概念，現給出模糊測試過程中統計結構狀態分布的方法。由于不同插樁點A：{ai}之間可能存在約束，因此程序的結構狀態分布中隨機變量X的個數N

對一個確定的程序P，很難預先分析出P的全體結構狀態。因此，在一個模糊測試周期中，將概率分布為p(x′)的全體測試用例的結構狀態空間X′近似為概率分布為p(x)程序的結構狀態空間X，記均勻分布概率為Q(x)。使用KL(Kullback-Leibler)距離[17-18]衡量結構狀態分布和均勻分布的差異：

(1)

測試周期越長，全體測試用例的結構狀態空間X′中隨機變量的個數越多，X′越逼近X。即使在樣本空間不斷變大的情況下，KL距離也能夠很好地描述結構狀態均勻分布的差異。

在樣本空間變化的過程中KL距離的變動特性：一般而言，發現新的結構狀態會使KL距離突然升高，分布均勻化的過程就是KL距離逐漸降低的過程。

3 系統實現

圖5表示SFL的系統組成。在對源代碼進行靜態分析并標記出特定結構中的程序狀態點之后，將收集結構狀態覆蓋的信息代碼插樁到目標程序中。提供兩種插樁的方式：結構狀態覆蓋和堆內存狀態覆蓋。在模糊測試的過程中，首先從隊列中選取結構狀態覆蓋分布最少的種子作為候選者，根據全局結構狀態分布補償能量；然后通過變異生成測試用例，使用插樁后的目標二進制運行測試用例檢查是否有新的狀態覆蓋和代碼覆蓋，通過檢查的種子加入下一輪變異隊列中。

圖5 SFL系統結構框圖

3.1 結構狀態覆蓋插樁算法

算法1表示插樁方式的具體細節。算法的輸入是原始程序P和目標結構基本塊集合T，輸出是已插樁的程序P。插樁算法主要有兩個步驟：① 使用共享內存case_map 記錄目標結構的命中次數；② 使用Seq_map記錄結構狀態基本塊跳轉序列。所有的共享內存和序列長度被初始化為0(Line 1)插樁的具體實現流程，遍歷所有的基本塊，進行基礎工具的插樁算法(Line 3)。首次遇見目標結構集合T中的基本塊bi時，產生一個隨機數Id作為不同結構狀態點的標記(Line 5)。程序執行到bi時，case_map[Id]自增1(Line 6)，隨后在Seq_map的末尾插入當前基本塊的id記錄執行序列。

算法1結構狀態信息收集插樁。

輸入：原始程序P，目標結構集合T。

輸出：已插樁程序P′。

① Share_memory Seq_map，Share_memory case_map，Basick Block B，Sequence Length L。

② For each﹤b0，…，bn﹥∈B do

③ AFL_Instrumention( )；

④ If bi∈T do

⑤ Id=get ID( )；

⑥ case_map[Id]+=1；

⑦ Seq_map[L]=Id；

⑧ L+=1；

⑨ End。

3.2 測試用例評估策略

評估測試用例的目的是選取下一輪變異時的基準。在模糊過程中，代碼覆蓋導向和結構狀態覆蓋導向的切換時機非常重要。筆者采取的切換標準為全局case_map覆蓋率超過80%時，開啟結構狀態覆蓋導向模式。當使用AFL的評價標準要丟棄測試用例時，分析此測試用例序列狀態。如果是新的序列狀態，則加入下一輪隊列中。

3.3 能量調度策略

能量調度依據種子的結構狀態覆蓋分布分配變異機會。現有的代碼覆蓋導向的模糊測試采用如下方式分配能量[10]：

E(i)=a(qi) ，

(2)

其中，i為等待變異的種子，qi為種子的評價得分。計算方式為種子長度、運行時間、代碼覆蓋等綜合計算。SFL依據全局結構狀態覆蓋分布為種子提供補償能量，計算方式如下：

ec=ebα，

(3)

其中，ec為異種子的補償能量，eb為能量補償基準，α為補償系數。αi的計算方式為

αi=1-p(Xi) ，

(4)

其中，p(Xi)為種子的結構狀態序列在全局變異中的分布比率。

4 實驗與評估

為了驗證筆者提出方法的有效性，基于AFL實現了原型系統SFL，并與AFL進行對比實驗。

測試集選取bctf漏洞自動化攻防比賽中的賽題BRHG-A006、BRHG-A007、BRHG-A0014，測試時間為1 h，重復測試4次。測試環境為Intel Xeon 6154 CPU@3.0GHz(72核)和512 GB內存，64位Ubuntu 18.04 LTS系統。min KL距離的計算的基準分布為均勻分布，采樣間隔為4 min，取4次重復實驗的平均值，測試初始種子采用零種子測試(AAAA)。實驗結果如圖6和圖7所示。

如圖6所示，KL距離突然增高的原因是發現新的結構狀態。在這種情況下，KL距離會隨著時間逐漸平穩。實驗數據表明，SFL能有效地穩定KL距離，使模糊測試過程中結構狀態分布更加均勻，從而提升發現漏洞的速度，如圖7所示。對于BRHG-A007和BRHG-A0014，SFL比AFL挖掘效果更明顯。

為了驗證方法的泛化性，選取libtiff-4.09軟件中的tiff2pdf進行測試。為了滿足路徑覆蓋率足夠的要求，輸入采用AFL進行120 h測試后產生的隊列文件。測試時間12 h，測試結果如圖8至圖10所示。采樣間隔為1 h。

圖8表示SFL和AFL測試時的路徑覆蓋率隨時間的變化趨勢圖。實驗表明，筆者提出的方法對路徑覆蓋速度影響不明顯，7.5 h后均達到分支覆蓋最大值。

圖8 AFL和SFL的分支覆蓋率對比圖

圖10 AFL和SFL 的unique crash數量對比圖

圖9表示SFL和AFL測試時的KL距離隨時間的變化趨勢。這里與有效性驗證實驗采用的零種子不同，由于初始種子已經覆蓋了目標結構，目標結構狀態覆蓋的調度更有助于發現漏洞。AFL的KL距離較低的原因是對大量不在目標區域的種子進行變異，因此初始值較低。KL距離的初始值高，則表明更多的能量分配給針對目標結構狀態覆蓋的變異上，這也是SFL能發現漏洞的主要原因。如圖10所示，在實驗中，SFL在7 h 30 min發現首個crash，而AFL沒有發現，經人工驗證，該crash是堆溢出造成的。

5 結束語

對Fuzzing模糊測試過程中種子收集方法和能量分配進行了改進，均勻化程序的結構狀態覆蓋，可以增強模糊測試對狀態相關漏洞的挖掘能力。通過實驗，證明這種方法能夠有效地提高模糊測試中結構狀態的覆蓋均勻程度，加速漏洞挖掘速度?，F有的模糊測試引擎擅長解決路徑突破的問題，針對已覆蓋的代碼區域，沒有考慮到結構狀態覆蓋的問題，導致很難發現一些與程序狀態相關的漏洞。但是盲目地變異很難完成結構狀態序列的增加，因此在下一步工作中，將與導向性的模糊測試集合起來，導向性產生新的結構狀態覆蓋。