張琦 馬鶯姿

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

關(guān)鍵詞：模糊測試;AFL;種子變異策略;錯誤檢測

中圖分類號：TP391;TP311 ? ? ? ?文獻(xiàn)標(biāo)識碼：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 ?引 ?言

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

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

1 ?理論知識

1.1 ?AFL工作流程

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

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

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

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

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

（5）如果新產(chǎn)生的變異導(dǎo)致了新的狀態(tài)轉(zhuǎn)換，將變異的輸出插入到隊列中。

（6）重復(fù)步驟2。

1.2 ?AFL變異策略

AFL變異階段最重要的任務(wù)就是對種子文件進(jìn)行變異。AFL維護(hù)了一個輸入隊列，每次從輸入隊列中取出一個文件，對其進(jìn)行大量變異，經(jīng)過變異后的文件喂給目標(biāo)程序執(zhí)行，觀察執(zhí)行過程中是否引起程序崩潰、發(fā)現(xiàn)新路徑等結(jié)果。對于發(fā)現(xiàn)新路徑的文件會返回輸入隊列繼續(xù)進(jìn)行變異并一直持續(xù)下去。

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

bitflip，按位翻轉(zhuǎn)，1變?yōu)?，0變?yōu)?。這一階段還會按照不同的長度和步長進(jìn)行多種不同的翻轉(zhuǎn)，每次翻轉(zhuǎn)1/2/4/8/16/32 bit，依次進(jìn)行。

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

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

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

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

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

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

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

2 ?種子變異優(yōu)化算法

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

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

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

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

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

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

3 ?對AFL的改進(jìn)

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

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

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

當(dāng)執(zhí)行完flipbit 8/8階段后，整個測試用例的所有字節(jié)對應(yīng)的shadow_map標(biāo)識完成。在隨后的havoc隨機變異階段，先判斷要變異的字節(jié)是否為有效字節(jié)，來減少無效測試用例的生成。具體改進(jìn)后的變異算法如表1改進(jìn)后的種子變異策略所示。

4 ?實驗與分析

使用AFL模糊測試器對程序進(jìn)行模糊測試的命令為：

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

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

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

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

5 ?結(jié) ?論

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

參考文獻(xiàn)：

[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] 任澤眾，鄭晗，張嘉元，等.模糊測試技術(shù)綜述 [J].計算機研究與發(fā)展，2021，58（5）：944-963.

[6] 李明磊，陸余良，黃暉，等.模糊測試變異算子調(diào)度優(yōu)化模型 [J].小型微型計算機系統(tǒng)，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—），男，漢族，江蘇連云港人，碩士生導(dǎo)師，碩士研究生，研究方向：軟件工程、軟件運行時驗證;馬鶯姿（1996—），女，漢族，山東淄博人，碩士研究生在讀，研究方向：軟件工程、軟件驗證。