模糊測試器AFL種子變異策略優化研究

張琦 馬鶯姿

摘 ?要：AFL作為模糊測試領域最具有代表性的工具，使用至今已發現大量軟件的內存漏洞。實驗表明，AFL超過60%的變異操作不會產生任何新路徑，這些變異都是無效的變異。文章對AFL種子變異策略進行分析，研究并提出了一種變異策略的優化算法。該算法通過在確定性變異階段記錄種子文件的有效字節數組，在隨機性變異階段判斷要變異的字節是否為有效字節來進行選擇性的變異。根據所提出的算法對AFL進行了優化，實驗驗證了該種子變異優化算法的有效性。

關鍵詞：模糊測試;AFL;種子變異策略;錯誤檢測

中圖分類號：TP391;TP311 ? ? ? ?文獻標識碼：A文章編號：2096-4706（2021）24-0142-04

Abstract： As the most representative tool in the field of Fuzzing， AFL has found a large number of software memory vulnerabilities so far. Experiment results show that more than 60% of AFLs mutations will not find any new paths， and these mutations are invalid. The paper analyzes the AFL seed mutation strategy， studies and proposes an optimization algorithm for the mutation strategy. The algorithm performs selective mutation by recording the effective byte array of the seed file in the deterministic mutation stage， and judging whether the bytes to be mutated are valid bytes in the random mutation stage. According to the proposed algorithm， AFL is optimized， and the experiment verifies the effectiveness of the seed mutation optimization algorithm.

Keywords： Fuzzing; AFL; seed mutation strategy; error detection

0 ?引 ?言

隨著社會不斷發展，信息化給人類的衣、食、住、行等各個方面帶來了極大的便利。計算機軟件給社會帶來便利的同時，也潛藏著一些安全問題。OpenSSL[1]本身是一個進行安全通信、可以保障通信保密性和可靠性的應用程序，然而，在2014年，OpenSSL被爆出“心臟滴血”重大漏洞，攻擊者可以通過這一漏洞，獲取應用程序源碼、用戶的網絡訪問請求和用戶的cookie信息，甚至可以獲取到用戶的電子郵件、銀行卡賬號密碼等，帶來了無法估量的損失。為了保證軟件的可靠性和信息的安全性，越來越多的技術關注于檢測軟件系統的內存安全性。

AFL[2-4]模糊測試器基本思想是將種子測試用例作為被測程序的輸入，檢測程序的執行過程并按照種子變異策略生成新的測試用例喂給被測程序，最終報告異常行為。其中種子變異策略是模糊測試器的關鍵核心，測試用例的生成質量，決定了模糊測試器的執行效率。實驗表明，AFL在進行種子變異的時候，超過60%的變異操作不會產生任何新路徑，這些變異都是無效的變異，提高種子變異的有效性是提升模糊測試效率的關鍵。

1 ?理論知識

1.1 ?AFL工作流程

AFL由前Google安全研究員lcamtuf開發的一款基于代碼覆蓋率的模糊測試工具，它通過記錄輸入的測試文件的代碼覆蓋率，從而調整輸入樣本以提高覆蓋率。目標源程序經過插樁編譯后生成插樁二進制文件，將初始種子文件輸入到模糊器進行變異喂給插樁后的目標程序，挖掘程序中的漏洞。如圖1所示，算法流程總結如下[5]：

（1）將用戶提供的初始測試種子文件加載到輸入隊列中。

（2）從輸入隊列獲取下一個測試文件。

（3）嘗試將測試用例精簡到最小尺寸，并且不改變程序的測試行為。

（4）使用一些傳統模糊算法不斷地變異文件。

（5）如果新產生的變異導致了新的狀態轉換，將變異的輸出插入到隊列中。

（6）重復步驟2。

1.2 ?AFL變異策略

AFL變異階段最重要的任務就是對種子文件進行變異。AFL維護了一個輸入隊列，每次從輸入隊列中取出一個文件，對其進行大量變異，經過變異后的文件喂給目標程序執行，觀察執行過程中是否引起程序崩潰、發現新路徑等結果。對于發現新路徑的文件會返回輸入隊列繼續進行變異并一直持續下去。

AFL的變異策略主要包括確定性變異和隨機變異[6]。其中確定性變異策略主要包括比特翻轉、算術運算、特殊值替換和字典值，具體類型如下：

bitflip，按位翻轉，1變為0，0變為1。這一階段還會按照不同的長度和步長進行多種不同的翻轉，每次翻轉1/2/4/8/16/32 bit，依次進行。

arithmetic，整數加/減算術運算。跟bitflip類似，arithmetic根據目標大小的不同，也分為了多個子階段，依次對8/16/32 bit進行加減運算。

interest，把一些特殊內容替換到原文件中。同樣每次對8/16/32 bit進行替換。所謂的特殊內容是AFL預設的一些比較特殊的數，比如可能造成溢出的數。

dictionary，把自動生成或用戶提供的字典值替換或插入到原測試用例中。

而隨機變異策略主要包括havoc大破壞和文件拼接：

havoc，對文件進行大量的破壞，此階段會對原文件進行大量隨機變異。包括隨機翻轉、加減、替換和刪除等操作。

splice，此階段會將兩個文件拼接起來得到一個新的文件，并對這個新文件繼續執行havoc變異。

具體地，AFL在種子文件隊列中隨機選取一個，與當前的種子文件對比。如果兩者差別不大，就再重新隨機選一個;否則就隨機選取位置進行拼接，產生新的文件。在這里，AFL還會過濾掉拼接文件未發生變化的情況。

2 ?種子變異優化算法

在AFL對種子文件進行變異的時候，除了確定性變異階段，還伴隨著隨機變異階段，通常，大量新路徑都是在隨機變異階段發現的。但是由于隨機havoc階段的變異盲目隨機，會導致大量無效的測試用例的生成，影響模糊測試效率[7]。因此，對havoc階段變異策略的優化是本文的研究重點。

一般來說，二進制輸入的種子文件通常具有一定的格式，分為“元數據”和“數據”兩部分。比如可執行鏈接格式ELF對象文件，通常分為ELF頭部，用來描述整個文件的組織，包括魔數、版本、類別、系統架構、程序頭起點等信息。程序頭部表提供系統創建進程映像的信息。節區頭部表則描述了節區的名稱，節區大小等信息。而節區部分則包含鏈接視圖的數據、指令、符號表和重定位信息等。而段類似與節區，包含程序的代碼段和數據段相關信息[8]。

為了減少隨機變異階段盲目的變異，提高模糊測試效率，本文提出一種思想來對隨機變異階段進行改進。其主要思想是：在對種子文件進行變異的時候，對其每個字節進行記錄，如果該字節的變化（包括其中某些bit的翻轉，字節的加減運算，字節的替換等）會引起新的路徑變化，則將該字節標記為有效字節，如果該字節的變化不會引發新路徑，則該字節是無效字節。那么在隨機變異階段，可以判斷出對無效字節的變異往往不會有太大的效果。因此，通過在隨機變異階段判斷字節是否為有效來決定是否對該字節進行變異，可以有效地提高種子文件的變異效率。

針對種子文件中不同字節對程序執行路徑的影響，可以把執行相同路徑的連續字節劃分為同一輸入域，對同一輸入域中某些字節的變異可能不會導致目標程序執行路徑的變化，比如分別改變某一輸入域中的第一個字節和第二個字節時，程序的執行路徑可能都會發生變化，但是這兩種變異后新的執行路徑可能為同一條，這種情況就不能同時把這兩個字節都標識為有效字節。

如圖2所示，圖中屬于同一個輸入域的相鄰字節被框在一起。當第0個字節發生變化時，目標程序沒有產生新的執行路徑，則將該字節標記為無效，即標記為0。而當第2個字節發生變化時，AFL檢測到目標程序產生了新的執行路徑，則將其對應的字節標記為1，代表著該字節是一個有效字節。需要注意，對應同一塊輸入域，比如圖中的第2到5個字節屬于同一個輸入域，當分別單獨對第2、3、4、5個字節進行變異后，相比于原來的種子文件，目標程序都產生了新的執行路徑，但是我們還需要判斷產生的新執行路徑是否為同一條，因為同一塊輸入域的中字節的變化產生的路徑往往是相同的。對于這種情況，需要做如下簡單的判斷：如果改變了某一字節引起了新的路徑變化，并且該路徑與改變其前一個字節引發的路徑不同，才將這個字節標記為有效字節。

當對種子文件的所有字節都進行單獨變異后，我們就可以根據變異結果對所有字節進行標識。隨后在對種子文件進行havoc隨機變異階段，AFL會隨機選取種子文件中的某些位置，對該位置的字節進行某些變異操作，充滿了隨機性。改進后的種子變異策略在havoc階段首先根據標識結果對要進行變異的字節判斷是否為有效字節，如果是有效字節，則進行該次變異，否則跳過該字節，減少變異次數和目標程序的執行次數。

3 ?對AFL的改進

根據上述的優化思路，需要對AFL的代碼進行改進。首先，在AFL的種子變異的方法中定義一個長度等于輸入種子文件字節長度的unsigned char類型數組shadow_map用來標識種子文件對應字節是否為有效字節。shadow_map[i]為1表示測試用例的第i個字節為有效字節。為了給shadow_map賦值，我們需要單獨遍歷種子文件的每個字節并對其進行變異，來判斷該字節是否會產生新的執行路徑。

這里采用的方法是利用確定性變異階段的字節翻轉變異策略，即bitflip 8/8。該階段是依次對每個字節進行翻轉，判斷是否會產生新的路徑。同時，為了避免輸入域產生相同路徑的影響，我們還需要判斷前一個字節的變化和當前字節的變化是否會導致同一新路徑。

AFL中使用trace_bits字節數組記錄分支信息的執行次數，我們使用哈希函數計算trace_bits的哈希值，通過比較種子文件變異前后的哈希值來比較執行路徑是否發生了變化。在測試用例的數據結構中存儲該用例未進行變異之前的trace_bits的哈希值exec_cksum，使用臨時變量記錄前一個字節trace_bits的哈希值pre_cksum。在對當前字節進行改變后的用例執行完目標程序后，計算當前trace_bits的哈希值cksum，當cksum不等于exec_cksum且cksum不等于pre_cksum時，我們將當前字節對應的shadow_map標識為1。

當執行完flipbit 8/8階段后，整個測試用例的所有字節對應的shadow_map標識完成。在隨后的havoc隨機變異階段，先判斷要變異的字節是否為有效字節，來減少無效測試用例的生成。具體改進后的變異算法如表1改進后的種子變異策略所示。

4 ?實驗與分析

使用AFL模糊測試器對程序進行模糊測試的命令為：

afl-fuzz -i in/ -o out/ -- /path/to/fuzz_app [option]

其中in為輸入的種子文件夾，out為輸出文件夾，包括了崩潰信息、種子隊列信息等，-- 后指定要進行模糊測試的程序。常用的afl-fuzz命令如表2所示。

由于本文對AFL變異策略的優化針對的是二進制文件中的每一個字節進行有效性記錄，在隨機變異階段對字節進行改變時首先判斷該字節的有效性，對于無效字節則不進行變異，從而提高變異的效率。因此，該部分的實驗針對的程序輸入為二進制文件，我們對Mibench中幾個輸入為音頻和圖片的測試用例進行測試。由于模糊測試的隨機性影響較大，因此本次實驗對每一個測試用例分別使用原始的AFL模糊測試器和改進后的AFL各進行三次實驗，每次實驗進行一小時，然后取平均值，具體的測試結果如表3所示。

其中total paths表示總的執行路徑，uniq crashes為找到的不同漏洞的個數。由于初始種子文件的大小對AFL的影響較大，因此表格中不同的測試用例的結果差異較大。比如對于ghostscript來說，由于種子文件所占字節較多，在對初始種子進行確定性變異階段執行的過程較久，而優化前后的AFL測試器對確定性變異階段沒有影響，而隨機變異階段在較大種子測試用例中所占的比重較輕，因此相較于其他的測試軟件，優化后的AFL相比于原始AFL所執行到的路徑提升較小。而對于大多數的測試軟件，改進后的AFL模糊測試器所能執行到的路徑可以提升10%至20%以上。同樣從測試結果中可以看出，使用改進后變異策略的AFL對同一測試用例進行同樣時間的模糊測試，往往能夠發生更多的崩潰。

5 ?結 ?論

本文介紹了AFL對種子文件進行模糊測試的相關變異策略，分析了隨機變異階段的缺陷，針對隨機變異階段的有效測試用例生成效率低的問題，提出了相應的解決方案：即在確定性變異階段通過記錄每個字節對變異的有效性，指導后續隨機變異，以提高AFL測試用例的生成效率。在未來的工作中，我們會繼續研究其他形式輸入的模糊測試項目，比如字符串文本輸入，提高該類型的種子變異效率。

參考文獻：

[1] VIEGA J， MESSIER M， CHANDRA P. Network security with openSSL：cryptography for secure communications [M].[S.I.]：OReilly Media，2002.

[2] CORDY J R. The TXL source transformation language [J].Science of Computer Programming，2006，61（3）：190-210.

[3] BHARDWAJ M，BAWA S. Fuzz testing in stack-based buffer overflow [EB/OL].[2021-11-01].https：//link.springer.com/chapter/10.1007/978-981-13-0341-8_3.

[4] LIANG J，WANG M Z，CHEN Y L，et al. Fuzz testing in practice：Obstacles and solutions [C]//2018 IEEE 25th International Conference on Software Analysis，Evolution and Reengineering（SANER）.Campobasso：IEEE，2018：562-566.

[5] 任澤眾，鄭晗，張嘉元，等.模糊測試技術綜述 [J].計算機研究與發展，2021，58（5）：944-963.

[6] 李明磊，陸余良，黃暉，等.模糊測試變異算子調度優化模型 [J].小型微型計算機系統，2021，42（10）：2190-2195.

[7] WANG H J，XIE X F，LI Y，et al. Typestate-guided fuzzer for discovering use-after-free vulnerabilities [C]//2020 IEEE/ACM 42nd International Conference on Software Engineering（ICSE）.Seoul：IEEE，2020：999-1010.

[8] YOU W，WANG X Q，MA S Q，et al. Profuzzer：On-the-fly input type probing for better zero-day vulnerability discovery [C]//2019 IEEE Symposium on Security and Privacy（SP）.San Francisco：IEEE，2019：769-786.

作者簡介：張琦（1992—），男，漢族，江蘇連云港人，碩士生導師，碩士研究生，研究方向：軟件工程、軟件運行時驗證;馬鶯姿（1996—），女，漢族，山東淄博人，碩士研究生在讀，研究方向：軟件工程、軟件驗證。