無碰撞灰盒模糊測試方法研究

王松 方勇 賈鵬

灰盒模糊測試技術已被證實是一種高效實用的漏洞挖掘技術，在漏洞挖掘領域應用廣泛，有大量的高危漏洞都是通過灰盒模糊測試找到的.AFL是灰盒模糊測試的經典代表之作，大量后續灰盒模糊測試都是在AFL的基礎上根據不同條件進行改進得到的，可以說AFL是主流灰盒模糊測試的奠基之作.但是AFL仍然存在一些問題，AFL在對目標待測程序進行插樁時采用隨機數代表樁點，在測試過程中采用兩個樁點的隨機數進行異或運算，得到結果用來表示一條邊.這種方式使得在進行邊的統計時就會出現HASH碰撞問題，導致有一定的概率新邊無法被發現，從而影響AFL的漏洞挖掘效率.這個問題會隨著待測程序的代碼規模變大而顯得愈發突出.本文通過改進匯編級插樁的方式，將基本塊敏感的插樁改為分支敏感的插樁，從而將程序的控制流圖改變為二叉樹的形式，并采用非隨機編碼來標記各個樁點，較好地解決了HASH碰撞的問題.實驗證明該方法有效，且由于該改進對于上層是透明的，可以應用于各個基于AFL的灰盒模糊測試工具中，從而提高模糊測試的效率.

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

TP391.1A2023.033004

收稿日期： 2023-01-06

作者簡介： 王松（1988-）， 男， 四川眉山人， 碩士研究生， 研究方向為網絡信息對抗.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 引 言在漏洞挖掘領域，灰盒模糊測試［1］（Greybox Fuzzing）是一種最具可擴展性和實用性的方法.它是介于黑盒和白盒之間的一種更有效的模糊測試.由于黑盒模糊測試缺乏對目標待測程序的分析，測試用例的生成過于盲目，灰盒模糊測試比黑盒模糊測試更具有效性；……