基于路徑風險適應度的模糊測試方法*

周 霞，胡 勇

（四川大學 網絡空間安全學院，四川 成都 610207）

0 引言

模糊測試技術[1,2]可以分為基于變異的模糊測試和基于生成的模糊測試兩類[3]。基于變異的模糊測試使用隨機化或啟發式算法的方法來變異現有的輸入以生成新的測試用例，能夠發現現有輸入不能發現的安全漏洞。該方法隨機變異，所以通過率和代碼覆蓋率低，且對初始樣本的依賴性較強。基于生成的模糊測試根據有效輸入的規范來生成格式良好的測試用例，該方法對測試人員的綜合能力要求高。

AFL（American Fuzzy Lop）通過變異和種子選擇來智能和有效地模糊由覆蓋信息引導的目標程序，所以選擇有效的種子選擇方法是至關重要的。本文針對AFL 因為僅依賴控制流信息，所以難以發現內存操作錯誤的問題，以及其簡單地判定種子是否為喜愛的（favorite）策略導致會觸發崩潰的種子不能被即時執行的問題，提出風險適應度指導種子選擇的方法：

（1）基于程序執行路徑上的危險函數和函數調用來計算程序執行路徑（種子）的風險適應度，具體是通過插樁技術，在程序運行過程中，先計算執行路徑上產生的內存操作數和函數調用數，然后計算程序路徑的風險值和廣度；

（2）使用程序路徑的風險值和廣度來計算路徑的風險適應度，從而指導種子選擇，具體是使用路徑風險值和廣度兩個指標計算路徑的風險適應度，并使用風險適應度改進AFL 的種子選擇策略，有效地將模糊測試集中到缺陷多發區域，增強崩潰發現的能力。

1 相關工作

1.1 背 景

1989—2002 年，研究者們主要采用隨機變異的方式生成半有效的數據，該方法代碼覆蓋率低，漏報率高。2002 年，隨著SPIKE[4]的提出，模糊測試通過人工分析的方法構造測試用例，實現了對文件與協議的模糊測試。2004 年，文獻[5]提出了peach 工具，該工具能夠分解有效文件并將它們重組為新的有效文件，并使用刪除數據塊以及修改重要的數據值等手段來生成新的輸入，實現模糊測試。2013[6]年提出的AFL 方法結合Forkserver 和遺傳算法，且以覆蓋率為導向，盡可能變異能產生新路徑的測試用例，提高變異后程序發現新路徑、新覆蓋的可能性。文獻[7]提出的AFLFast 使用馬爾科夫鏈建模來定位未被AFL 發現的路徑。文獻[8]提出的AFLGo 對給定位置或目標進行可達性分析，對距離目標較近的種子進行優先排序。文獻[9]實現了工具Augmented-AFL，該方法通過神經網絡預測種子文件中的突變位置，并對PDF、PNG 等多種格式的文件進行了測試。文獻[10]提出的Angora工具基于梯度下降執行搜索，以提高其覆蓋范圍。文獻[11]提出的Vuzzer 方法不需要任何輸入及目標程序的先驗知識，將目標程序建模成馬爾科夫模型，然后決定哪些基本塊難以到達，并為其分配權重，決定哪些基本塊優先被測試。文獻[12]提出的AFLSmart 方法融合了peach 的輸入結構和AFL 的覆蓋率反饋機制，根據規范將有效的輸入優先模糊，使模糊器能夠探索有效文件的更多變化。文獻[13]提出的CollAFL 通過提供更準確的平均信息來減少AFL 的哈希沖突。上述方法已在實踐中證明了它們的有效性。

如今已有很多增強技術用于模糊測試，從不同的方面提高模糊測試的效率，但是模糊測試效率低、代碼覆蓋率低、測試用例冗余高的問題仍然存在。

1.2 AFL 簡介

AFL 是一個邊覆蓋引導的灰盒模糊器，它使用了一種新穎的插樁工具和遺傳算法來自動發現“有趣的”測試用例，即能發現新路徑或能命中已發現路徑分支的測試用例，這些測試用例能夠觸發目標程序的崩潰或發現新的路徑，其工作流程如圖1所示。

圖1 AFL 的工作流程

AFL 的工作流程具體包括以下步驟：

（1）目標程序插樁；

（2）將初始輸入讀入種子隊列中；

（3）根據AFL 的種子選擇策略從隊列中選擇1 個種子參與下一次的模糊；

（4）使用多種變異算法來變異選擇的種子，并生成新的測試用例；

（5）將測試用例作為輸入，執行目標程序并跟蹤其狀態變化；

（6）如果在程序執行的過程中觸發崩潰，將該種子加入到崩潰文件中，供后續分析；

（7）如果發現新的邊或新的覆蓋，將種子加入到種子隊列中參與后續的模糊；

（8）如果本輪模糊測試結束，轉到步驟（3），直到手動結束。

代碼插樁指在編譯時插入自定義的代碼段，這對獲取模糊測試反饋信息和跟蹤路徑具有良好的效果。在進行模糊測試時，AFL 使用afl-gcc 或者aflclang 插入樁代碼來跟蹤分支覆蓋，此外，根據是否有源碼，AFL 提供了兩種插樁方式：在有源碼時，AFL 根據使用的編譯器提供了gcc 插樁和clang 插樁；在沒有源碼時，AFL 提供了虛擬化模擬器（Quick Emulator，QEMU）模式對二進制文件進行插樁。AFL 通過一個位圖（bitmap）來保存已經訪問的邊以及邊的命中次數，為每一個基本塊分配一個隨機數作為其ID，并使用當前基本塊和其前一個基本塊ID 的異或值來標記一條邊。AFL 通過插樁計算覆蓋率的代碼如下：

其中，變量cur_location 保存當前基本塊的ID，prev_location 保存其前一個基本塊的ID，使用右移來區分A->B 和B->A 的轉換。

2 Risk-AFL 設計及實現

2.1 危險函數的定義

具有危險函數的地方可能會觸發漏洞。函數memcpy 將讀取的內容復制到分配的固定空間時，如果在復制之前沒有進行錯誤檢查，存入的數據長度超過分配的內存空間，則會導致內存寫入超出邊界的風險。危險函數是決定路徑風險值的重要信息，一般滿足以下特點：

（1）沒有對輸入的數據進行檢驗，這是因為如果函數沒有對外部輸入的數據進行錯誤檢查，就可能存在漏洞；

（2）函數使用了外部傳入的數據，這是因為如果函數沒有使用外部輸入，則不存在被利用的風險，但是如果使用了外部輸入，就有可能被人利用。

本文使用表1 中的函數作為危險函數，包括內存分配、內存釋放、字符串操作等。

表1 危險函數

2.2 計算路徑風險和廣度

由于源碼插樁執行速度快、效率高、程序性能損耗小，所以本文選擇基于底層虛擬機（Low Level Virtual Machine，LLVM）[14]技術的源碼插樁來獲取程序運行時信息。目標程序運行時，通過樁代碼記錄輸入執行路徑的邊的風險值和邊廣度，其中分別使用指針MemFuncPtr和callPtr記錄。使用指針變量MemFuncPtr和危險邊的集danger_edges來更新邊的風險值，即危險函數的數量，其表達式為：

式中：memFunc_bits用以保存邊的風險值。

通過指針callPtr和發生函數調用的邊的集合call_edges來更新邊的廣度，即函數調用數量，其表達式為：

式中：memCall_bits用以保存邊的廣度。

給定一個種子s以及該種子執行路徑所有邊的風險值和復雜度，則種子s的路徑風險值s.risk和路徑廣度s.extent的計算公式分別為：

式中：N為種子s覆蓋的風險邊的數量；n為種子s覆蓋的發生函數調用的邊的數量。

式（3）使用風險邊的平均風險值作為路徑的風險值指標，該指標越大，表示該種子檢測危險位置的能力越強，更容易發現深層bug。式（4）使用這些邊的平均函數調用數量作為路徑的廣度指標，該指標越大，函數調用越多，控制流圖就盡可能完整，更容易發現淺層的bug。

2.3 計算種子的風險適應度

本文在不同的模糊時期分別賦予路徑風險值和路徑廣度不同的權值以實現路徑風險適應度的動態計算和更新。前期注重路徑廣度，后期注重路徑風險值。適應度risk_fitness的具體計算公式為：

式中：fuzz為該種子被模糊的次數。為了使適應度函數連續，使用x，y變量來計算路徑風險值和路徑廣度的權重，參數x和y滿足，p為適應度閾值。在本文中取經驗值6，表示模糊次數小于6 次時，注重路徑廣度，發現更多路徑和淺層bug；大于6 次時，則注重路徑風險，發現更深層次的bug。該方法可以有效地發現路徑，并將模糊集中到缺陷多發區域，發現更多崩潰。

2.4 種子選擇策略及favorite 策略優化

本文通過結合邊的風險值和廣度來進行favorite判斷以指導種子篩選。優化后的favorite 策略如算法1 所示。該算法中，首先判斷當前種子的風險值或者廣度，選擇風險值或廣度大的測試用例加入top_rated 數組中，即確定其為favorite 的種子（5～14行）。如果風險值和廣度值都相等則使用AFL 原始的favorite 策略進行判斷（8～9 行）。

Risk-AFL 在使用風險適應度選擇種子時，使用平均適應度作為閾值，當種子適應度大于平均適應度的種子參與后續的模糊，種子選擇策略如算法2 所示，在選擇種子時，遍歷隊列求平均適應度（2～6行），然后再選擇適應度大于平均適應度的種子（7～18 行）進行模糊。

3 實驗評估

3.1 實驗環境及對象

實驗環境為ubuntu 16.01 LTS 64 位的虛擬機，該系統的處理器為AMD Ryzen 5 4600G with Radeon Graphics，空間大小為20 GB。本文選擇了xmllint、tiff2bw、mp3gain、tiff2pdf 這4 個應用進行實驗，并與基準工具AFL 進行比較，目標程序信息如表2所示。

表2 目標程序

初始種子對于模糊測試也是至關重要的，本文使用幾個來源構建初始輸入。xmllint 使用其自帶的dtd 文件，其余文件從github[15]倉庫中的文件自主創建初始文件的詳細信息如表3 所示。

表3 初始種子信息

3.2 實驗結果及分析

本文的方法是在AFL_2.52b 的基礎上實現的，為了驗證方法的有效性，將本文實現的工具與原版的AFL_2.52b 進行對比。通過對每個應用分別進行5 次，每次24 小時的測試，最后取平均值作為模糊測試結果，表4 給出了對比實驗的具體數據。

通過表4 可知，本文的方法在總路徑數、獨特崩潰數以及覆蓋率方面都有明顯的提升。對于xmllint 應用，Risk-AFL 在路徑數上增加了37.72%，覆蓋率提高了6.72%，崩潰數增加了75.96%；對于mp3gain，在路徑數上增加了61.84%，覆蓋率降低了34.93%，崩潰數增加了8.77%；對于tiff2pdf，在路徑數上增加了19.07%，覆蓋率提高了6.66%，崩潰數增加了25.21%；對于應用tiff2bw，在路徑數上增加了16.15%，覆蓋率提高了13.25%，崩潰數增加了16.66%。

表4 對比實驗數據

除在mp3gain 這個應用上覆蓋率沒有提升外，在其他應用上，各指標都明顯提高。根據實驗得到的路徑總數和崩潰數，可以說明本文的方法在路徑和漏洞發現上都具有較好的效果，即證明通過獲取執行路徑內存操作數和函數調用數來計算路徑風險適應度的方法更容易發現新路徑，也更容易觸發崩潰。

4 結論

本文提出先通過插樁獲取程序的反饋信息，然后計算路徑的風險適應度以指導種子選擇，對favorite 策略進行優化，并設計實現了Risk-AFL 工具。實驗表明，與原始的AFL 相比，本文實現的工具Risk-AFL 在路徑發現和崩潰發現上都有一定提高。然而，由于AFL 以隨機變異的方式生成輸入，因此導致大量輸入執行相同的路徑，同時發現長路徑的能力比較低，所以覆蓋率提升不顯著，在以后的工作中可以結合啟發式算法、強化學習等技術針對AFL 的變異部分進行研究和優化。