面向二進制程序的導向性模糊測試方法

張瀚方 周安民 賈鵬 劉露平 劉亮

摘 要：為了解決當前模糊測試技術中變異存在一定的盲目性以及變異生成的樣本大多經過相同的高頻路徑的問題，提出并實現了一種基于輕量級程序分析技術的二進制程序模糊測試方法。首先對目標二進制程序進行靜態分析來篩選在模糊測試過程中阻礙樣本文件深入程序內部的比較指令;隨后對目標文件進行插樁來獲取比較指令中操作數的具體值，并根據該具體值為比較指令建立實時的比較進度信息，通過比較進度衡量樣本的重要程度;然后基于模糊測試過程中實時的路徑覆蓋信息為經過稀有路徑的樣本增加其被挑選進行變異的概率;最后根據比較進度信息并結合啟發式策略有針對性地對樣本文件進行變異，通過變異引導提高模糊測試中生成能夠繞過程序規約檢查的有效樣本的效率。實驗結果表明， 所提方法發現crash及發現新路徑的能力均優于模糊測試工具AFLDyninst。

關鍵詞：導向性模糊測試;反饋式模糊測試;二進制模糊測試;程序插樁;漏洞挖掘

中圖分類號：TP311

文獻標志碼：A

Abstract： In order to address the problem that the mutation in the current fuzzing has certain blindness and the samples generated by the mutation mostly pass through the same highfrequency paths， a binary fuzzing method based on lightweight program analysis technology was proposed and implemented. Firstly， the target binary program was statically analyzed to filter out the comparison instructions which hinder the sample files from penetrating deeply into the program during the fuzzing process. Secondly， the target binary program was instrumented to obtain the specific values of the operands in the comparison instructions， according to which the realtime comparison progress information for each comparison instruction was established， and the importance of each sample was measured according to the comparison progress information. Thirdly， the realtime path coverage information in the fuzzing process was used to increase the probability that the samples passing through rare paths were selected to be mutated. Finally， the input files were directed and mutated by the comparison progress information combining with a heuristic strategy to improve the efficiency of generating valid inputs that could bypass the comparison checks in the program. The experimental results show that the proposed method is better than the current binary fuzzing tool AFLDyninst both in finding crashes and discovering new paths.

英文關鍵詞Key words： directed fuzzing; feedback fuzzing; binary fuzzing; program instrumentation; vulnerability mining

0 引言

隨著計算機的廣泛使用和網絡技術的飛快發展，計算機軟件早已融入到人們的日常生活中，在金融、交通、醫療衛生和國防科技等領域中發揮著重要作用。軟件數量日益增加，與之俱來的軟件安全問題也越發突出。軟件中存在的漏洞為攻擊者提供了可乘之機，近年來攻擊者利用軟件漏洞實施攻擊的事件屢見不鮮，2017年wannacry勒索病毒利用永恒之藍漏洞進行傳播，造成巨大經濟損失[1];2018年黑客利用思科高危漏洞攻擊關鍵基礎設施，導致全球20萬臺交換機受到影響[2]。

由于軟件功能的增加，軟件的代碼量越來越大，代碼結構越來越復雜，復雜的工作邏輯與數據處理過程導致軟件在運行過程中極易產生bug，嚴重的則會引發安全漏洞。高效、自動化的安全測試理論和方法對軟件測試和安全檢測具有重要意義，也是計算機學科和網絡安全學科的一個重要研究方向。模糊測試是一種有效的軟件安全性檢測方法，其基本思想是通過不斷構造不規則數據作為應用程序的輸入，執行并監視應用程序在處理輸入數據時是否發生崩潰等異常來發現應用程序潛在的安全問題[3]。當前，模糊測試技術已被谷歌[4]、微軟[5]等軟件公司用于軟件安全的測試。針對計算機軟件的模糊測試可以根據能否獲得應用程序的源碼而分為針對開源軟件的源碼級別模糊測試和針對閉源軟件的二進制級別模糊測試。由于大部分的軟件廠商出于知識產權保護和商業利益的考慮并不會開放其軟件源代碼，在針對二進制程序的測試中可能存在輸入數據格式未知等情況，因此相比于源碼級別的模糊測試，二進制級別的模糊測試難度更大，面向二進制程序的軟件漏洞挖掘技術也是當今研究的一個熱點[6]。

當前在模糊測試領域，AFL（American Fuzzy Loop）[7]是最具有代表性的工具之一，它使用遺傳算法，并將代碼覆蓋信息作為反饋用于篩選子代。相對于傳統的模糊測試方法，AFL提高了模糊測試的效率;但是該工具仍存在一定的局限性，如變異生成的輸入文件大多會運行到相同的高頻路徑[8-9]，在面向二進制程序的模糊測試中難以產生能夠通過程序規約檢查的有效用例，變異存在一定的盲目性，導致難以發現存在于程序深處的bug等。

針對于上述問題，本文提出了一種面向二進制程序的導向性模糊測試方法，該方法在AFL原有遺傳算法的基礎上提高經過稀有路徑的種子文件被選中的概率，考慮到程序規約檢查中的magic值校驗檢查，該方法通過二進制插樁技術并結合比較進度信息來指導樣本變異以高效地生成能夠通過規約檢查從而觸發程序新路徑的變異樣本，提高模糊測試的效率。

1 研究現狀

在軟件安全檢測領域中，常用的漏洞挖掘方法有靜態分析、污點分析、符號執行和模糊測試等方法。其中，靜態分析誤報率較高，隨著應用程序功能的增多，代碼復雜度也日益增加，靜態分析方法越發難以發現應用程序中存在的漏洞; 污點分析方法的主要問題是效率較低，需要消耗大量的計算資源; 符號執行方法面臨路徑爆炸和約束求解困難等問題[10]; 相對于這些技術，模糊測試自動化程度高、原理簡單并且誤報率極低，因此受到了越來越多的關注[11-12]。

近幾年來，針對于模糊測試的研究大多數是結合諸如符號執行[13-14]、污點分析[15]等方法以幫助模糊測試生成有效測試用例，通過結合其他方法的優勢提高模糊測試的檢測效果。

2 問題分析

在如下的應用程序中包含了magic值字段檢查以及嵌套的if條件檢查，輸入文件只有在逐個繞過這些檢查的情況下才能觸發程序中所存在的bug，對于這樣的應用程序AFL難以生成能夠成功觸發bug的樣本文件。在對該代碼進行長達 24h 的測試中，AFL并沒有產生任何能夠導致程序發生崩潰的測試用例。而在實際應用中，程序往往會通過大量的magic值校驗以對輸入文件進行格式檢查。

在挑選樣本進行變異時，通過Check 2檢查的樣本文件相對于只繞過Check 1檢查的樣本文件更容易觸發程序中所存在的bug，樣本文件只有在繞過Check 1的基礎上才可能通過Check 2，因此通向Check 2的路徑相比通向Check 1的路徑更稀有。AFL會為每條路徑挑選文件體積小且執行時間快的文件并將其標記為favored，在挑選文件進行變異時，被標記為favored的文件被選中的概率遠遠大于其他非favored的文件[21]。AFL的種子隊列只增不減，在所給程序中，每條路徑都可能存在其對應的文件體積最小并且執行時間最少的favored樣本，因此在樣本執行過的路徑中可能會有多個favored文件，AFL沒有考慮稀有路徑使得這些樣本在變異時均會被選擇變異，但是，由于通過了Check 2的樣本更容易觸發程序中所存在的bug，增加通過Check 2校驗的樣本被選中的概率顯然會增加樣本觸發bug的概率。

AFL使用代碼覆蓋信息作為反饋以篩選保留子代，在變異過程中生成的變異文件如果能夠覆蓋新的代碼將會被保留。對于magic值校驗的情況，如Check 2需要將變異樣本的前5個字節設置為“MAGIC”字符串才能通過檢查，即使AFL在變異過程中已經將變異樣本的前5個字節設置為“MAGIX”，由于最后一個字節不匹配將導致校驗失敗，并沒有觸發新的代碼，AFL在這樣的情況下會舍棄該變異樣本。AFL舍棄掉部分字節匹配的樣本意味著之前達到部分字節匹配的變異工作對生成通過校驗的樣本毫無幫助，然而在匹配到部分字節的樣本基礎上進行變異，相對于在沒有匹配到任何一個字節的樣本基礎上進行變異更容易通過校驗。

本文考慮從兩個角度解決上述在模糊測試中所面臨的難題。首先在調度策略方面，將在原有AFL的基礎上進一步增大經過稀有路徑的樣本文件被挑選進行變異以產生子代樣本文件的概率。另外，在變異時將結合一定的啟發式策略進行引導并保留具有高比較進度信息的樣本以供進一步的變異。

3 導向性模糊測試方法

為了提高面向二進制程序的模糊測試的效率，本文提出了一種面向二進制程序的導向性模糊測試方法。其整體思路如圖1所示。與傳統AFL框架相比，該方法增加的策略有以下幾個方面：

1）對目標二進制文件進行分析，提取其中含有的關鍵比較指令信息，并根據得到的指令信息有針對性地對目標二進制文件進行插樁以在模糊測試過程中獲取比較進度信息和比較指令中操作數的具體值;

2）在模糊測試過程中，在選擇種子文件進行變異時優先考慮經過稀有路徑的樣本文件;

3）在模糊測試過程中，在代碼覆蓋情況沒有發生改變的條件下優先保留比較進度較高的樣本文件，一旦變異文件觸發或提高了比較進度信息將保留該變異文件以供進一步的變異，并且將使用比較進度得到提高的比較指令中操作數的值對當前樣本變異位置前后特定數量的字節進行變異。

3.1 關鍵指令與比較進度

大部分的應用程序在執行初期的規約檢查中往往會通過比較指令對輸入文件進行格式檢查，可能包括大量magic值的檢查等校驗，其中比較指令主要是指如cmp、strncmp等對操作數進行比較的指令。該類指令的執行結果將會影響程序運行的路徑，從而影響后續的代碼覆蓋情況，因此本方法主要關注比較指令。應用程序中通常包含大量的比較指令，需要對其進行合理的篩選，由于本文目標是解決magic值校驗的問題，所以在對比較指令進行過濾篩選時將重點關注操作數包含有立即值的比較指令。

在對比較指令篩選后，需要根據其地址信息有針對性地對目標二進制文件進行插樁，從而獲取比較指令中操作數的具體值并根據該具體值建立對應的比較指令的比較進度信息。每條比較指令的進度信息為該比較指令中兩個操作數中所匹配的字節的數目。如圖2所示的示例中，magic值為“ELF+”，如果兩個操作數的值完全相同則將該比較指令的比較進度設為0xFF，當操作數的值為“EXFO”時，此時兩個操作數中僅第1個字節和第3個字節相同，此時比較進度將被設為0x2。

該比較進度信息將會作為后續挑選樣本的一個重要參考信息。

3.2 種子文件選擇

為了在模糊測試過程中能夠優先選擇經過稀有路徑的樣本進行變異，本文方法增加了經過稀有路徑的樣本文件被選中的概率。由于稀有路徑需要根據程序在模糊測試過程中實時的測試情況才能確定，因此本文基于模糊測試過程中各樣本的路徑覆蓋信息實時計算挑選稀有路徑，通過實時的路徑信息為每個種子文件計算能量，能量越高的種子文件被選中的概率越大。該方法以路徑被樣本隊列中的樣本所執行的累計次數判斷路徑是否稀有，考慮到在模糊測試過程中樣本執行代碼片段越多則越可能觸發新路徑，因此在計算樣本的能量時將會計算各個分支的執行情況從整體上來為種子文件分配能量。

首先記錄各分支路徑被種子隊列中的樣本文件所執行的次數，每個分支被執行的次數等于各樣本文件所執行該分支的次數的總和：

hitstimebranch=∑input∈queuehits（input，branch）（1）

其中queue屬于當前的樣本隊列。根據分支執行次數的總和可以判斷出哪些路徑為稀有路徑，為了讓模糊測試合理使用資源探索新路徑，通過為經過稀有路徑的種子文件分配更多能量使得其被選中進行變異的概率增大，能量計算公式如下：

E（input）=∑branch∈Bhits（input，branch）hitstimebranch（2）

其中：hitstimebranch是當前branch路徑被樣本隊列所執行的累計次數總和，而branch是當前樣本文件所執行到的任一分支，hits（input，branch）為當前該樣本在執行過程中執行branch分支的次數，B為當前執行到的所有程序路徑分支。如果路徑被執行次數較多，則該路徑為高頻路徑，其獲得的能量比重減小。 一個樣本的能量比重為該樣本所執行到的所有分支能量的總和。

3.3 變異引導

為了引導樣本文件進行有效變異以產生能夠通過比較檢查指令的有效子代樣本文件，本文在AFL的基礎上進行了3個方面的改進：首先是保留比較進度有所增長的樣本，其次是根據啟發式規則對樣本的特定位置進行變異，最后是以比較指令中出現的立即數為取值范圍對樣本進行變異。

在所給程序中，生成了繞過Check 1的樣本后，在對樣本文件進行進一步變異以生成通過Check 2校驗的樣本時，AFL會根據其變異規則對樣本文件進行比特翻轉、算術操作等，由于AFL將覆蓋新代碼作為保留子代的條件，即使變異樣本已經部分匹配到“MAGIC”值，代碼覆蓋情況并沒有改變，變異文件仍然會被舍棄，因此要求變異樣本文件的前5個字節必須完全匹配“MAGIC”才能被保留，在這樣的條件下，AFL要生成能夠通過Check 2的樣本最多需要28×5次變異。這樣嚴苛的條件導致AFL很難生成能夠成功通過Check 2的樣本。為了降低難度，本文通過引入比較進度信息，在樣本變異過程中匹配到magic值校驗中的任一字節，即觸發了比較進度后，將保留該變異文件進行進一步的變異，在進一步的變異中，將保留具有高比較進度信息的變異樣本，在這樣的條件下，要通過Check 2校驗最多需要28×5次變異。通過引入比較進度信息本方法將極大降低生成通過Check 2樣本的難度。

雖然為了通過規約檢查引入比較進度后的變異難度已經大幅度減小，但是在對樣本變異時需要進行變異的字節位于樣本哪個偏移仍然是未知的，因此在實際情況中，變異出能夠通過Check 2檢查的樣本所需要的最多變異次數遠遠大于28×5，仍然存在很大難度。即使能夠準確定位到需要變異的位置，但是面臨28×5次變異仍然是一個較大的開銷。為了進一步提高變異的準確率和有效性，本文采用一種簡單的啟發式方法以減小變異范圍和搜尋空間。在變異過程中，一旦對樣本文件的某個偏移位置進行變異后觸發或提高了比較指令的比較進度信息，那么將認為這個字節即為magic值校驗檢查中的一個字節，由于大部分的magic值是以連續字節的方式存放在輸入文件中供應用程序進行校驗檢查的，因此位于該偏移位置前后的字節很有可能同樣是magic字節，因此本方法將會在該變異位置前后的（sizeoperand-1）個字節優先使用該比較進度所對應的比較指令中立即數的具體值逐字節對樣本文件進行變異。如在所給程序中，在對樣本文件第1個字節進行變異時將第1個字節變異為M后，比較進度信息將被觸發，本文方法將會使用“MAGIC”這5個字符逐字節對樣本文件的第2～第5個字節進行變異，這將大幅度提高變異的準確性，能夠快速生成通過Check 2的變異樣本文件從而觸發到Check 3的新路徑。

4 實驗與分析

為了驗證所提方法的有效性，本文實現了一個模糊測試系統RMFuzzer并對其進行了實驗評估。RMFuzzer使用二進制插樁平臺Dyninst[22]以及模糊測試工具AFL進行開發，同時還使用IDA Pro（Interactive Disassembler Professional）及IDAPython輔助對二進制程序進行分析和相關指令信息的提取。在相同實驗環境下與二進制模糊測試工具AFLDyninst（該工具采用Dyninst插樁框架對二進制文件進行插樁，其模糊測試器為AFL）進行對比。測試環境為Ubuntu 16.04 LTS32位系統，Intel Xeon CPU E31231 v3處理器和8GB的內存。實驗采用了兩個數據集進行實驗評估，其中包括LAVAM測試集以及現實生活中的實際應用程序。

4.1 LAVAM測試集

LAVAM是一個人工構造的含有大量bug的數據集，其采用了污點分析等技術向應用程序中注入了大量難以被觸發的bug[23]。

在對RMFuzzer和AFLDyninst進行對比實驗時，使用相同的文件作為初始種子，運行時間為5h，由于模糊測試過程中變異存在一定的隨機性，因此前后共進行了3輪測試，實驗結果取3次實驗的平均數據。在3次實驗過程中，AFLDyninst均沒有產生任何能夠觸發crash的樣本文件，而RMFuzzer在4個應用程序中均產生了觸發其中所存在的部分crash的樣本文件。實驗結果如表1所示。從實驗結果可以看出，在LAVAM測試集中，RMFuzzer能夠發現其中注入的bug，其測試效果明顯好于AFLDyninst。

5 結語

針對現有模糊測試技術存在的路徑覆蓋能力不足、變異存在一定盲目性等問題，本文提出了一種面向二進制程序的導向性模糊測試方法，并基于該方法實現了模糊測試工具RMFuzzer。該方法主要從種子文件的調度策略以及變異策略上對模糊測試過程進行了引導，相對于其他將污點分析或符號執行與模糊測試相結合的方法，本文方法采用輕量級的靜態分析方法與插樁技術，因此通用性更高，同時節約計算資源。通過實驗證明RMFuzzer無論是在發現crash的能力方面還是在路徑發現與代碼覆蓋方面均優于當前流行的模糊測試工具，但是該方法仍然存在一定的問題：

1）在進行變異引導時，本方法采用了一個啟發式的策略，一旦該變異位置提高了比較指令中的比較進度就在該位置附近字節進行變異，但是如果輸入文件中magic字段并不是連續存放的，那么這種啟發式策略將不再奏效。故進一步的工作需要考慮如何解決這樣的問題。

2）其次，存在變異導致控制流改變而進一步觸發比較進度的情況，在這樣的情況下，本文提出的變異引導方法將不再適用，在之后的研究工作中，需要考慮如何能更準確地對需要變異的文件位置進行定位，提高變異引導的效率和準確性。

3）本方法著重于解決應用程序規約檢查中輸入文件的magic字段的檢查問題，在接下來的工作中應進一步研究如何生成能夠快速繞過其他類型的程序檢查的樣本以提高模糊測試的效率。

參考文獻 （References）

[1] Wikipedia. WannaCry ransomware attack[EB/OL].[2018-03-10]. https：//en.wikipedia.org/wiki/WannaCry_ransomware_attack.

[2] KHANDELWAL S. Critical flaw leaves thousands of Cisco switches vulnerable to remote hacking[EB/OL].[2018-03-10]. https：//thehackernews.com/2018/04/ciscoswitcheshacking.html.

[3] MILLER B P， FREDRIKSEN L， SO B. An empirical study of the reliability of UNIX utilities[J]. Communications of the ACM， 1990， 33（12）： 32-44.

[4] OSSFuzzContinuous fuzzing for open source software[EB/OL]. [2018-03-10]. https：//github.com/google/ossfuzz.

[5] Microsoft security development lifecycle[EB/OL].[2018-03-10]. https：//www.microsoft.com/enus/sdl/process/verification.aspx.

[6] SHOSHITAISHVILI Y， WANG R， SALLS C， et al. SOK： （State of） the art of war： offensive techniques in binary analysis[C]// Proceedings of the 2016 IEEE Symposium on Security and Privacyn Security and Privacy. Piscataway， NJ： IEEE， 2016： 138-157.

[7] ZALEWSKI M. American fuzzy lop （2.52b）[EB/OL]. [2018-03-10]. http：//lcamtuf.coredump.cx/afl/.

[8] BHME M， PHAM V T， ROYCHOUDHURY A. Coveragebased greybox fuzzing as Markov chain[C]// Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. New York： ACM， 2016： 1032-1043.

[9] LEMIEUX C， SEN K. FairFuzz： a targeted mutation strategy for increasing greybox fuzz testing coverage[C]// Proceedings of the 2018 ACM/IEEE International Conference on Automated Software Engineering. Piscataway， NJ： IEEE， 2018： 475-485.

[10] CADAR C， SEN K. Symbolic execution for software testing： three decades later[J].Communications of the ACM， 2013， 56（2）： 82-90.

[11] LIANG H L， PEI X X， JIA X D， et al. Fuzzing： state of the art[J]. IEEE Transactions on Reliability， 2018， 67（3）： 1199-1218.

[12] GAN S T， ZHANG C， QIN X J， et al. CollAFL： path sensitive fuzzing[C]// Proceedings of the 2018 IEEE Symposium on Security and Privacy. Piscataway， NJ： IEEE， 2018： 679-696.

[13] PENG H， SHOSHITAISHVILI Y， PAYER M. TFuzz： fuzzing by program transformation[C]// Proceedings of the 2018 IEEE Symposium on Security and Privacy. Piscataway， NJ： IEEE， 2018： 697-710.

[14] PHAM V T， ROYCHOUDHURY A. Modelbased whitebox fuzzing for program binaries[C]// Proceedings of the 2016 IEEE/ACM International Conference on Automated Software Engineering. Piscataway， NJ： IEEE， 2016： 543-553.

[15] RAWAT S， JAIN V， KUMAR A， et al. VUzzer： applicationaware evolutionary fuzzing [EB/OL].[2018-03-20].https：//mirror.explodie.org/3714.pdf.

[16] 張斌， 李孟君， 吳波， 等. 基于動態污點分析的二進制程序導向性模糊測試方法[J]. 現代電子技術， 2014， 37（19）： 89-94. （ZHANG B， LI M J， WU B， et al. Method of binary oriented fuzzy testing based on dynamic taint analysis [J]. Modern Electronics Technique， 2014， 37（19）： 89-94.）

[17] 王鐵磊. 面向二進制程序的漏洞挖掘關鍵技術研究[D]. 北京：北京大學， 2011： 41-69. （WANG T L. Research on binaryexecutableoriented software vulnerability detection[D]. Beijing： Peking University， 2011： 41-69.）

[18] STEPHENS N， GROSEN J， SALLS C， et al. Driller： augmenting fuzzing through selective symbolic execution[EB/OL].[2018-03-20].http：//www.cs.ucsb.edu/～chris/research/doc/ndss16_driller.pdf.

[19] LI Y K， CHEN B H， CHANDRAMOHAN M， et al. Steelix： programstate based binary fuzzing[C]// Proceedings of the 2017 Joint Meeting on Foundations of Software Engineering. New York： ACM， 2017： 627-637.

[20] CHEN P， CHEN H. Angora： efficient fuzzing by principled search[C]// Proceedings of the 2018 IEEE Symposium on Security and Privacy. Piscataway， NJ： IEEE， 2018： 697-710.

[21] ZALEWSKI M. Technical “whitepaper” for AFLfuzz[EB/OL]. [2018-03-20]. http：//lcamtuf.coredump.cx/afl/technical_details.txt.

[22] Paradyn/DyninstWelcome[EB/OL]. [2018-03-20]. https：//dyninst.org/.

[23] DOLANGAVITT B， HULIN P， KIRDA E， et al. LAVA： largescale automated vulnerability addition[C]// Proceedings of the 2016 IEEE Symposium on Security and Privacy. Piscataway， NJ： IEEE， 2016： 110-121.