王松 方勇 賈鵬

灰盒模糊測試技術(shù)已被證實(shí)是一種高效實(shí)用的漏洞挖掘技術(shù)，在漏洞挖掘領(lǐng)域應(yīng)用廣泛，有大量的高危漏洞都是通過灰盒模糊測試找到的.AFL是灰盒模糊測試的經(jīng)典代表之作，大量后續(xù)灰盒模糊測試都是在AFL的基礎(chǔ)上根據(jù)不同條件進(jìn)行改進(jìn)得到的，可以說AFL是主流灰盒模糊測試的奠基之作.但是AFL仍然存在一些問題，AFL在對(duì)目標(biāo)待測程序進(jìn)行插樁時(shí)采用隨機(jī)數(shù)代表樁點(diǎn)，在測試過程中采用兩個(gè)樁點(diǎn)的隨機(jī)數(shù)進(jìn)行異或運(yùn)算，得到結(jié)果用來表示一條邊.這種方式使得在進(jìn)行邊的統(tǒng)計(jì)時(shí)就會(huì)出現(xiàn)HASH碰撞問題，導(dǎo)致有一定的概率新邊無法被發(fā)現(xiàn)，從而影響AFL的漏洞挖掘效率.這個(gè)問題會(huì)隨著待測程序的代碼規(guī)模變大而顯得愈發(fā)突出.本文通過改進(jìn)匯編級(jí)插樁的方式，將基本塊敏感的插樁改為分支敏感的插樁，從而將程序的控制流圖改變?yōu)槎鏄涞男问剑⒉捎梅请S機(jī)編碼來標(biāo)記各個(gè)樁點(diǎn)，較好地解決了HASH碰撞的問題.實(shí)驗(yàn)證明該方法有效，且由于該改進(jìn)對(duì)于上層是透明的，可以應(yīng)用于各個(gè)基于AFL的灰盒模糊測試工具中，從而提高模糊測試的效率.

灰盒模糊測試； AFL； 插樁； HASH碰撞； 基本塊； 分支敏感

TP391.1A2023.033004

收稿日期： 2023-01-06

作者簡介： 王松（1988-）， 男， 四川眉山人， 碩士研究生， 研究方向?yàn)榫W(wǎng)絡(luò)信息對(duì)抗.E-mail：271974754@qq.com

通訊作者： 賈鵬.E-mail： pengjia@scu.edu.cn

Research on Collision-Free grey box fuzzing method

WANG Song， FANG Yong， JIA Peng

（School of Cyber Science and Engineering， Sichuan University， Chengdu 610065， China）

Grey-box fuzzing technology has been proved to be an efficient and practical vulnerability mining technology. It is widely used in the field of vulnerability mining， and many high-risk vulnerabilities are found through grey-box fuzzing. American Fuzzy Lop（AFL） is a classic representative of grey-box fuzzing and many subsequent grey-box fuzzing are improved on the basis of AFL according to different conditions? but AFL still faces certain issues.AFL uses random numbers to represent instrumentation points when performing instrumentation on target program， the random numbers of the two instrumentation points are used to perform the XOR operation in the testing process， and the result is used to represent an edge.This method can lead to HASH collision problems when performing edge statistics， which decreases the probability of discovering new edges and affects AFL's vulnerability mining efficiency， especially for larger code sizes..In this paper， by improving the way of assembly-level instrumentation， the basic block-sensitive instrumentation is changed to branch-sensitive instrumentation， so that the control flow graph of the program is changed into a binary tree form， and non-random numbers are used to mark each instrumentation point， which is relatively well solved the problem of HASH collision. Experiments show that the propsosed method is effective， and since the improvement is transparent to the upper layer， it can be applied to various AFL-based grey-box fuzzing tools， thereby improving the efficiency of the fuzzing test.

Grey-box fuzzing; AFL; Instrumentation; HASH collision; Basic block; Branch sensitive

1 引 言在漏洞挖掘領(lǐng)域，灰盒模糊測試［1］（Greybox Fuzzing）是一種最具可擴(kuò)展性和實(shí)用性的方法.它是介于黑盒和白盒之間的一種更有效的模糊測試.由于黑盒模糊測試缺乏對(duì)目標(biāo)待測程序的分析，測試用例的生成過于盲目，灰盒模糊測試比黑盒模糊測試更具有效性；灰盒模糊測試對(duì)目標(biāo)待測程序的分析相對(duì)于白盒模糊測試來說是輕量級(jí)的，它比白盒模糊測試有更高的效率［2-7］.灰盒模糊測試廣泛應(yīng)用于大量軟件測試、庫以及內(nèi)核代碼的檢測.有大量的高危漏洞都是通過灰盒模糊測試找到的.截止到2022年7月，谷歌的OSS-Fuzz平臺(tái)利用幾款灰盒模糊測試工具如libFuzzer［8］、Honggfuzz［9］、American Fuzzy Lop（AFL）［10］和AFL++［11］發(fā)現(xiàn)了650款開源軟件中的超過40 000個(gè)漏洞［12］.

灰盒模糊測試的基本過程是將初始種子文件按照一定的策略進(jìn)行變異后得到大量程序輸入，并將這些輸入放到目標(biāo)待測程序中運(yùn)行，同時(shí)跟蹤記錄并反饋程序的運(yùn)行狀態(tài)信息來指導(dǎo)后續(xù)的測試，最后對(duì)引起程序崩潰的輸入進(jìn)行分析，從而找到程序的漏洞.

AFL是灰盒模糊測試的經(jīng)典代表之作，其實(shí)用性得到了廣大學(xué)者的青睞.大量后續(xù)的灰盒模糊測試都是基于AFL在不同的條件下改進(jìn)得到的，如 AFLGO［13］、AFLFast［14］、AFL++等.可以說，AFL是主流灰盒模糊測試的奠基之作.

但是AFL這類主流Fuzzer仍然存在一些不可忽視的問題，例如HASH碰撞問題［15］.HASH碰撞問題會(huì)導(dǎo)致待測程序在被測試中反饋的覆蓋率信息有錯(cuò)，進(jìn)一步導(dǎo)致有價(jià)值的測試用例被拋棄.這個(gè)問題將隨著程序代碼規(guī)模的變大而變得更加嚴(yán)重.

本文將采用改進(jìn)插樁代碼的方式，通過新的統(tǒng)計(jì)方法來解決HASH碰撞問題，實(shí)現(xiàn)待測程序的覆蓋率提高，從而提高漏洞挖掘的效率.

2 背 景

2.1 AFL簡介

以AFL為代表的主流灰盒模糊測試大多都是基于邊覆蓋率引導(dǎo)來進(jìn)行測試的，即CGF（Coverage-guide Greybox Fuzzing）.CGF一般會(huì)在待測程序源代碼中進(jìn)行插樁（樁代碼），從而可以在每一次測試程序時(shí)獲得程序路徑覆蓋率信息的反饋，并對(duì)出現(xiàn)過的程序路徑信息進(jìn)行記錄匯總，產(chǎn)生總的程序路徑信息位圖（bitmap）.用單個(gè)測試用例的覆蓋程序路徑信息和總的bitmap進(jìn)行對(duì)比，通過覆蓋率是否提高進(jìn)行判斷，篩選出有價(jià)值的測試用例，再賦予不同的能量（即變異時(shí)間）對(duì)有價(jià)值的測試用例進(jìn)行重點(diǎn)測試，以提高模糊測試的效率.圖1為AFL的工作流程圖.

這樣做的目的是在有限的時(shí)間內(nèi)覆蓋盡可能多的程序路徑.基于覆蓋率引導(dǎo)的測試思想對(duì)后續(xù)研究有著深遠(yuǎn)的影響.其原理和核心思想是基于被測試到的程序代碼不一定能發(fā)現(xiàn)漏洞，但是沒被測試到的程序代碼肯定不能發(fā)現(xiàn)漏洞.所以在測試過程中要盡量去發(fā)現(xiàn)新的程序路徑（即新邊），有新邊出現(xiàn)的測試用例將被認(rèn)定為好的種子，獲得更多的變異可能和測試時(shí)間，從而增大發(fā)現(xiàn)漏洞的概率.

2.2 HASH碰撞問題

HASH碰撞問題會(huì)導(dǎo)致待測程序在被測試后，不同的邊被視為相同的邊.這樣將會(huì)有一定的概率導(dǎo)致新邊被誤認(rèn)為是舊邊，進(jìn)一步導(dǎo)致測試用例被拋棄.這和AFL的核心思想是相矛盾的——命中了新邊的測試用例反而被拋棄將大大影響漏洞的挖掘效率.

對(duì)這個(gè)問題有很多學(xué)者都進(jìn)行了相關(guān)研究，例如BigMap［16］、INSTRIM［17］、CollAFL［18］等.有的是采用擴(kuò)大內(nèi)存的方法，有的是采用改變邊覆蓋為基本塊覆蓋的方法，本文將采用改進(jìn)匯編級(jí)插樁的方式并通過新的統(tǒng)計(jì)方法來嘗試解決這個(gè)問題.

2.2.1 問題成因 AFL在對(duì)待測程序進(jìn)行插樁時(shí)會(huì)在每個(gè)插樁點(diǎn)放置一個(gè)隨機(jī)數(shù)（范圍：0～65 535），在測試過程中使用前一個(gè)樁點(diǎn)隨機(jī)數(shù)右移一位和當(dāng)前樁點(diǎn)隨機(jī)數(shù)的異或值來表示這條程序邊，并對(duì)每條邊的命中次數(shù)進(jìn)行統(tǒng)計(jì)，結(jié)果放入trace_bits數(shù)組中，用以反饋邊覆蓋率信息，過程示意如下.

CurBlock_Num=Random（0， 65 535）

Edge=（PreBlockNum>>1）^CurBlock_Num

Trace_bits［edge］++

由于異或操作造成了樁點(diǎn)信息損失（且隨機(jī)數(shù)本身就有一定的可能直接相同），即HASH碰撞問題，例如：

Block_A = 0×02 Block_B = 0×011

EdgeAB=（0×02>>1）^0×11=0×10

Block_C = 0×22 Block_D = 0×01

EdgeCD=（0×22>>1）^0×01=0×10

AB和CD是完全不同的兩條程序邊，但是在統(tǒng)計(jì)命中次數(shù)時(shí)會(huì)被視為等同，產(chǎn)生了HASH碰撞.

2.2.2 問題影響 在程序規(guī)模較小時(shí)，這個(gè)問題影響不大，但是它會(huì)隨著程序規(guī)模的增加而變得越來越嚴(yán)重.在對(duì)不同邊規(guī)模的程序進(jìn)行100次重復(fù)模擬碰撞測試后，取平均值得到的程序邊規(guī)模和總體碰撞率的關(guān)系如表1所示.

程序邊規(guī)模為N時(shí)，總體碰撞率計(jì)算公式經(jīng)過本文歸納總結(jié)可表示為

P=∑Ni=2（|Ri|-|Ri-1|）N（1）

其中，Ri={r1，r2，……，ri}；ri是代表每條邊的隨機(jī)數(shù).

在模糊測試過程中，對(duì)靠后的測試用例進(jìn)行測試時(shí)，由于已經(jīng)產(chǎn)生了很多舊邊，若此時(shí)再有新邊出現(xiàn)，單條新邊的碰撞率會(huì)更高，如表2所示.

單條新邊在程序邊規(guī)模為N時(shí)碰撞概率公式為

P=1N（2）

較高的單條新邊碰撞概率，會(huì)造成模糊測試越往后進(jìn)行越難以發(fā)現(xiàn)有價(jià)值的測試用例（即命中新邊的測試用例），這與邊覆蓋率引導(dǎo)測試的核心思想是相違背的.

3 優(yōu)化方法

如果完整的記錄起點(diǎn)終點(diǎn)的隨機(jī)數(shù)，不做異或操作，則可以避免HASH碰撞問題.但是這樣做會(huì)造成記錄邊信息的存儲(chǔ)空間爆炸.當(dāng)完整地記錄每條邊的起點(diǎn)終點(diǎn)隨機(jī)數(shù)用以區(qū)分每條邊時(shí)，要考慮65 536×65 536種可能，共享內(nèi)存為232byte，開銷太大.共享內(nèi)存過大會(huì)造成尋址速度大大降低，進(jìn)行bitmap比對(duì)時(shí)也會(huì)耗費(fèi)更多的時(shí)間，將嚴(yán)重影響漏洞挖掘的效率.如圖2所示.

但是通過分析可以注意到每一個(gè)樁點(diǎn)的跳轉(zhuǎn)可能性是有限的，即以每一個(gè)樁點(diǎn)為起點(diǎn)的邊的數(shù)目是有限可控的.基于此點(diǎn)，可以嘗試找到一種方法適當(dāng)增大共享內(nèi)存，以較小代價(jià)解決HASH碰撞問題.

3.1 基于分支敏感的插樁

以AFL為代表的灰盒模糊測試一般采用的插樁策略是以基本塊為最小單位的，這樣就會(huì)在各基本塊的起始位置進(jìn)行插樁，例如在函數(shù)頭、各跳轉(zhuǎn)分支點(diǎn)、標(biāo)號(hào)進(jìn)行插樁并產(chǎn)生程序的邊信息，如圖3所示.

這樣做的壞處是會(huì)產(chǎn)生一些多余的邊.可以將它改進(jìn)為基于分支敏感的插樁策略，取消必經(jīng)點(diǎn)的插樁，因?yàn)闇y試過程只對(duì)程序的不同路徑感興趣，如圖4所示.通過對(duì)比，可以看到相同的程序結(jié)構(gòu)，在必經(jīng)點(diǎn)（B、C都是必經(jīng)點(diǎn)）處不再插樁后，程序邊數(shù)有所減少，這對(duì)漏洞挖掘工作是有利的.

采用基于分支敏感的插樁策略后，在插樁時(shí)，不再對(duì)函數(shù)頭這類必經(jīng)點(diǎn)進(jìn)行插樁，找到分支點(diǎn)（跳轉(zhuǎn)指令和標(biāo)號(hào)）進(jìn)行插樁即可.由于實(shí)現(xiàn)的是匯編級(jí)插樁，根據(jù)匯編語言的特點(diǎn)，例如jz等語句產(chǎn)生的后續(xù)分支都只有兩種可能，這樣得到的程序所有分支點(diǎn)構(gòu)成一個(gè)二叉樹結(jié)構(gòu)，即每一個(gè)樁點(diǎn)的后續(xù)節(jié)點(diǎn)只有兩種可能，這對(duì)后續(xù)的統(tǒng)計(jì)方法改進(jìn)有著至關(guān)重要的作用，可以避免路徑爆炸問題，如圖5所示.

如果不取消函數(shù)頭這類必經(jīng)點(diǎn)的插樁，則可能出現(xiàn)一個(gè)函數(shù)跳轉(zhuǎn)到多個(gè)函數(shù)的情況（即一個(gè)樁點(diǎn)的后續(xù)樁點(diǎn)有多種可能），造成程序邊路徑爆炸，這種情況下的樁點(diǎn)結(jié)構(gòu)遠(yuǎn)比基于分支敏感的樁點(diǎn)結(jié)構(gòu)要復(fù)雜得多，將導(dǎo)致記錄邊信息需要的內(nèi)存過大而無法實(shí)現(xiàn)有效改進(jìn)，如圖6所示.

3.2 分支節(jié)點(diǎn)順序編碼

采用順序編碼對(duì)各分支點(diǎn)進(jìn)行插樁標(biāo)記，即從1開始依次遞增標(biāo)記每個(gè)樁點(diǎn).這樣做可以避免隨機(jī)數(shù)生成時(shí)造成的隨機(jī)數(shù)相同而導(dǎo)致的碰撞（兩個(gè)不同的樁點(diǎn)隨機(jī)數(shù)相同，進(jìn)而導(dǎo)致邊表示可能相同），且各個(gè)樁點(diǎn)的規(guī)律性和可辨識(shí)度更高.

3.3 擴(kuò)大共享內(nèi)存并改變統(tǒng)計(jì)方法

采用基于分支敏感的插樁策略后，程序插樁點(diǎn)是二叉樹結(jié)構(gòu)，即單一樁點(diǎn)的后繼節(jié)點(diǎn)只有兩種可能.可以通過擴(kuò)大一定的內(nèi)存來記錄一條程序邊的起點(diǎn)及終點(diǎn)的完整信息，而不再采用異或的方式來表示邊.

將記錄程序邊命中次數(shù)的64 kB的trace_bits內(nèi)存擴(kuò)大為128 kB，即邊的可能性由65 536條變?yōu)?5 536×2條.再增加維護(hù)另一個(gè)數(shù)組edgeinformation，即邊的信息數(shù)組，大小為65 536×2×2 byte=256 kB，此時(shí)共享內(nèi)存大小為384 kB.在統(tǒng)計(jì)時(shí)記錄樁點(diǎn)的后繼節(jié)點(diǎn)信息用以區(qū)分兩條邊的不同，如圖7所示.

因?yàn)樵挤椒ǖ倪吤写螖?shù)數(shù)組（trace_bits）地址即代表邊的有序排列，所以在對(duì)比邊命中信息時(shí)只需要依次按字節(jié)進(jìn)行對(duì)比即可.改進(jìn)后的方法則需要根據(jù)記錄的邊的信息將地圖稍做調(diào)整即可（即將二叉樹的左右后繼節(jié)點(diǎn)位置調(diào)整得相同）.

改進(jìn)后的插樁統(tǒng)計(jì)函數(shù)以匯編代碼實(shí)現(xiàn)在樁代碼中，其流程如圖8所示.

4 實(shí)驗(yàn)及分析

本文在AFL2.52b的基礎(chǔ)上實(shí)現(xiàn)了模糊測試工具NHFuzzer，并進(jìn)行了實(shí)驗(yàn)對(duì)比.實(shí)驗(yàn)選取libxml2、ntpq、libelfmaster、LIEF、sendmail、binutils和libexif作為目標(biāo)，實(shí)驗(yàn)主機(jī)CPU型號(hào)為Intel Xeon CPU E3-1231 v3@3.4 GHz，系統(tǒng)版本為Ubuntu18.04.5.每次實(shí)驗(yàn)運(yùn)行24 h，分別運(yùn)行3次后取平均值得到實(shí)驗(yàn)結(jié)果.

4.1 插樁數(shù)對(duì)比

如圖9所示，各個(gè)測試對(duì)象的插樁數(shù)都有明確減少但是減少幅度不大，都在6%以內(nèi)，因?yàn)楹瘮?shù)頭類必經(jīng)點(diǎn)占比規(guī)模不大.插樁數(shù)減少可以小幅度減少待測程序的邊規(guī)模，但是去掉函數(shù)頭類必經(jīng)點(diǎn)的最大意義是使得匯編級(jí)的二叉樹分支圖得以呈現(xiàn)，后續(xù)的邊信息可以得以全存儲(chǔ).

4.2 覆蓋率、有價(jià)值種子數(shù)及崩潰數(shù)對(duì)比

如表3所示，通過實(shí)驗(yàn)可以看到NHFuzz使得待測試程序的邊覆蓋率、有價(jià)值的種子數(shù)以及獨(dú)特崩潰數(shù)三個(gè)主要指標(biāo)都得到了有效提升.在libexif、LIEF和senmail中，邊覆蓋率、有價(jià)值的種子數(shù)和獨(dú)特崩潰數(shù)三個(gè)指標(biāo)都提升了10%以上，提升最為明顯.因?yàn)殡S著程序規(guī)模的增大，HASH碰撞問題會(huì)更加嚴(yán)重，效率提升空間就更大，這和之前的問題分析也是相符合的.從總體實(shí)驗(yàn)結(jié)果來看，本文提出的基于分支敏感的方法通過解決HASH碰撞問題來提高程序覆蓋率，進(jìn)而提高灰盒模糊測試效率是有效的.

5 結(jié) 論

針對(duì)AFL為代表的傳統(tǒng)灰盒模糊測試中存在的HASH碰撞問題，本文對(duì)問題成因及影響進(jìn)行了細(xì)致的分析，并提出了基于分支敏感的插樁及新的統(tǒng)計(jì)方法，并實(shí)現(xiàn)了模糊測試工具NHFuzzer.實(shí)驗(yàn)證明，NHFuzzer在提高代碼覆蓋率，提升漏洞挖掘效率上是行之有效的，且實(shí)驗(yàn)表明該方法在大規(guī)模程序的測試中效果更好.下一步考慮研究在必經(jīng)點(diǎn)的分析提取上做相關(guān)工作進(jìn)一步提升模糊測試的效率.

參考文獻(xiàn)：

［1］ Li J， Zhao B， Zhang C. Fuzzing： a survey ［J］. Cybersecurity， 2018， 1： 1.

［2］ Chen C， Cui B， Ma J， et al. A systematic review of fuzzing techniques［J］. Comput Secur， 2018， 75： 118.

［3］ Cadar C， Dunbar D， Engler D R. Klee： unassisted and automatic generation of high-coverage tests for complex systems programs ［C］//Usenix Conference on Operating Systems Design and Implementation.San Diego： USENIX Association， 2008： 209.

［4］ Ahmed A， Mishra P. QUEBS： qualifying event based search in concolic testing for validation of RTL models ［C］//International Conference on Computer Design （ICCD）. Boston： IEEE， 2017： 185.

［5］ Lyu Y， Ahmed A， Mishra P. Automated activation of multiple targets in rtl models using concolic testing ［C］//2019 Design， Automation & Test in Europe Conference & Exhibition （DATE）. Florence： IEEE， 2019： 354.

［6］ Ahmed A， Farahmandi F， Mishra P. Directed test generation using concolic testing on rtl models ［C］//2018 Design， Automation & Test in Europe Conference & Exhibition （DATE）. Dresden： IEEE， 2018： 1538.

［7］ Ren Z， Zheng H， Zhang J， et al. A review of fuzzing techniques ［J］. Comput Resnd Dev， 2021， 58： 944.

［8］ Serebryany K. Continuous fuzzing with libfuzzer and addresssanitizer［C］//Cybersecurity Development. Boston： IEEE， 2016： 157.

［9］ Swiecki R. Honggfuzz： a general-purpose， easy-to-use fuzzer with interesting analysis options［EB/OL］. ［2022-10-17］.https：//github.com/google/honggfuzz.

［10］ Zalewski M. American fuzzy lop ［EB/OL］. ［2022-10-17］. http：//lcamtuf.coredump.cx/afl/.

［11］ Fioraldi A， Maier D， Eifeldt H， et al. {AFL++}： combining incremental steps of fuzzing research［C］//14th USENIX Workshop on Offensive Technologies （WOOT 20）. ［S.l.： s.n.］， 2020： 10.

［12］ Serebryany K . Oss-fuzz-googles continuousfuzzing service for open source software ［EB/OL］. ［2022-10-17］.https：//github.com/google/oss-fuzz/.

［13］ Bhme M， Pham V T， Nguyen M D， et al. Directed greybox fuzzing［C］//Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. New York： ACM， 2017.

［14］ Bhme M， Pham V T， Roychoudhury A. Coverage-based greybox fuzzing as markov chain［C］//Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. New York： ACM， 2016.

［15］ TN_root. AFL技術(shù)實(shí)現(xiàn)分析 ［EB/OL］. ［2018-06-06］. https：//blog.csdn.net/qq_32464719/article/details/80592902.

［16］ Ahmed A， Hiser J D， Nguyen-Tuong A， et al. BigMap： future-proofing fuzzers with efficient large maps［C］//Proceedings of the 2021 51st Annual IEEE/IFIP International Conference on Dependable Systems and Networks （DSN）.Taiwan：IEEE， 2021.

［17］ Hsu C C， Wu C Y， Hsiao H C， et al. Instrim： lightweight instrumentation for coverage-guided fuzzing ［C］//Symposium on Network and Distributed System Security （NDSS）. San Diego：ISOC， 2018.

［18］ Gan S， Zhang C， Qin X， et al. Collafl： path sensitive fuzzing［C］//Proceedings of the 2018 IEEE Symposium on Security and Privacy （SP）.San Francisco： IEEE， 2018： 679.

引用本文格式：

中 文： 王松， 方勇， 賈鵬. 無碰撞灰盒模糊測試方法研究［J］. 四川大學(xué)學(xué)報(bào)： 自然科學(xué)版， 2023， 60： 033004.

英 文： Wang S， Fang Y， Jia P. Research on Collision-Free grey box fuzzing method? ［J］. J Sichuan Univ： Nat Sci Ed， 2023， 60： 033004.