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

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

1 代碼覆蓋導(dǎo)向的模糊測試問題分析

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

以圖1所示代碼來說明筆者關(guān)注的問題。該代碼來自于RHG比賽中的heap buffer over flow BRHG-A006。此類程序包含while-switch-case結(jié)構(gòu)，不同的輸入會導(dǎo)致不同的case語句被執(zhí)行。

圖1 BRHG-A006簡化版代碼

該程序依據(jù)opt的值執(zhí)行不同的堆操作模塊，包括堆申請、堆內(nèi)存寫、堆內(nèi)存讀、堆內(nèi)存釋放模塊。漏洞觸發(fā)條件為堆申請空間小于堆內(nèi)存寫空間。

圖2 崩潰樣本控制流圖

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

1.1 測試用例的結(jié)構(gòu)狀態(tài)分布

1.2 基本塊跳轉(zhuǎn)作為反饋指標(biāo)的局限性

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

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

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

圖3 用AFL、FairFuzz 測試24 h的隊列結(jié)構(gòu)狀態(tài)覆蓋對比圖

1.3 特定結(jié)構(gòu)的普適性分析

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

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

圖4 隊列結(jié)構(gòu)狀態(tài)覆蓋對比圖

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

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

(1) 在代碼覆蓋足夠的情況下，解決產(chǎn)生新的結(jié)構(gòu)狀態(tài)覆蓋的測試用例被丟棄的問題；

(2) 結(jié)構(gòu)狀態(tài)覆蓋變異次數(shù)不均勻的問題。

2 解決方案

對現(xiàn)有的代碼覆蓋率導(dǎo)向的灰盒模糊測試方法進(jìn)行分析。通過對源碼進(jìn)行結(jié)構(gòu)狀態(tài)插樁分析和運行時統(tǒng)計結(jié)構(gòu)狀態(tài)覆蓋分布分析，設(shè)計并實現(xiàn)了原型系統(tǒng)SFL，均勻化了程序狀態(tài)分布，加速了漏洞發(fā)現(xiàn)過程。

2.1 源碼結(jié)構(gòu)狀態(tài)插樁分析

程序中會包含許多的while-switch-case結(jié)構(gòu)。為了避免switch-case嵌套導(dǎo)致的結(jié)構(gòu)狀態(tài)爆炸，每次只對一個目標(biāo)結(jié)構(gòu)進(jìn)行插樁。插樁完成后獲得一組目標(biāo)程序，依據(jù)軟件歷史cve的補丁信息，優(yōu)先選擇包含歷史漏洞的目標(biāo)結(jié)構(gòu)進(jìn)行模糊測試。

轉(zhuǎn)換while-if-else程序，在while-if-else結(jié)構(gòu)中找到能夠跳轉(zhuǎn)回while語句的基本塊，以此作為插樁點。

2.2 結(jié)構(gòu)狀態(tài)分布的統(tǒng)計度量

定義2給出了程序的結(jié)構(gòu)狀態(tài)分布的概念，現(xiàn)給出模糊測試過程中統(tǒng)計結(jié)構(gòu)狀態(tài)分布的方法。由于不同插樁點A：{ai}之間可能存在約束，因此程序的結(jié)構(gòu)狀態(tài)分布中隨機變量X的個數(shù)N

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

(1)

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

在樣本空間變化的過程中KL距離的變動特性：一般而言，發(fā)現(xiàn)新的結(jié)構(gòu)狀態(tài)會使KL距離突然升高，分布均勻化的過程就是KL距離逐漸降低的過程。

3 系統(tǒng)實現(xiàn)

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

圖5 SFL系統(tǒng)結(jié)構(gòu)框圖

3.1 結(jié)構(gòu)狀態(tài)覆蓋插樁算法

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

算法1結(jié)構(gòu)狀態(tài)信息收集插樁。

輸入：原始程序P，目標(biāo)結(jié)構(gòu)集合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 測試用例評估策略

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

3.3 能量調(diào)度策略

能量調(diào)度依據(jù)種子的結(jié)構(gòu)狀態(tài)覆蓋分布分配變異機會。現(xiàn)有的代碼覆蓋導(dǎo)向的模糊測試采用如下方式分配能量[10]：

E(i)=a(qi) ，

(2)

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

ec=ebα，

(3)

其中，ec為異種子的補償能量，eb為能量補償基準(zhǔn)，α為補償系數(shù)。αi的計算方式為

αi=1-p(Xi) ，

(4)

其中，p(Xi)為種子的結(jié)構(gòu)狀態(tài)序列在全局變異中的分布比率。

4 實驗與評估

為了驗證筆者提出方法的有效性，基于AFL實現(xiàn)了原型系統(tǒng)SFL，并與AFL進(jìn)行對比實驗。

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

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

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

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

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

圖10 AFL和SFL 的unique crash數(shù)量對比圖

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

5 結(jié)束語

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