SEAMFUZZ：學習灰盒模糊測試的種子自適應突變策略｜技術進展

一、 引言

灰盒模糊測試器的性能很大程度取決于變異策略。通常，基于變異的模糊測試工具維護一組預定義的變異方法，這些方法指定變異的位置和變異的方式。傳統模糊測試器（如AFL、HONGFUZZ和 VUZZER）遵循預定義的概率分布來選擇突變策略，而不管目標是什么程序，這可能會降低模糊測試整體性能。程序自適應方法（如MOPT）旨在通過學習每個目標程序最優變異策略的概率分布解決這一問題。然而，程序自適應方法主要觀察由大多數種子輸入共有的特征觸發的行為，經常會錯過每個種子輸入與大多數種子輸入不同的個體特征。然而，這些個體特征往往在滿足程序特定條件以到達深層次的程序位置方面發揮關鍵作用。

因此，作者提出了 SEAMFUZZ，一種具有新型種子自適應突變策略的灰盒模糊測試器。SEAMFUZZ 旨在捕獲種子輸入的個體特征，并對不同的種子輸入應用不同的變異策略。

二、 概述

SEAMFUZZ 的工作流程如圖1所示，在傳統模糊測試的基礎上新增兩個步驟：（1）種子聚類，將種子輸入聚類到具有相似特征的種子組中；（2）概率分布學習，通過不斷進行模糊測試學習適合每個種子組的有效突變方法。

圖1 SEAMFUZZ工作流程圖

SEAMFUZZ的算法如圖2所示。在第 2-3 行將崩潰觸發集 Crash 和種子組信息集 G 初始化為空集。在第5行從種子輸入語料庫 I 中選擇一個種子輸入 s。在第 7-8行，函數CLUSTER將選擇的種子輸入s聚類到所對應的種子組，返回組信息g=(s_id, S, P_id, Dg, Db)，并從種子信息集G中移除種子組g。在第 11 -13行確定是遵循學習概率 P_id（利用）還是隨機概率 P_r（探索）來為種子采樣變異方法，根據選定的概率分布 P 采樣有效的變異方法 M 來變異種子輸入s。在第14行使用變異得到的測試用例 s' 執行程序 pgm，得到反饋信息(I , Crash, g)。在第15-16行 LEARN 函數利用反饋信息更新種子組g和種子組信息集G。通過 CLUSTER 和 LEARN 之間的迭代交互, SEAMFUZZ 能夠學習到針對種子組的選擇有效變異方法的概率分布。

圖2 SEAMFUZZ算法圖

三、種子聚類

給定一個種子輸入 s 和一個種子組集合G，種子聚類的目標是將選定的種子輸入 s 聚類到具有相似特征的適當種子組g中。為了實現這個目標，作者定義了相似度得分score_sim表示種子輸入與種子組的相似程度，CLUSTER 函數根據分數將種子輸入分組到種子組。相似度分數包括語法相似性得分、語義相似性得分、稀有度相似性得分。

（一）語義相似性

語義相似性 Sim_sem 描述種子輸入與種子組的行為有多相似。更準確地說，它描述了種子輸入和種子組所覆蓋的執行路徑的相似性；覆蓋的執行路徑越相同，它們就越相似。本文將覆蓋的執行路徑信息表示為兩個基本塊之間的一組覆蓋轉換，即A：a->b。由于種子組包含多個種子輸入，本文通過計算單個種子組中所有種子輸入覆蓋的執行路徑轉換的集合 Cov_all 來定義種子組的一般語義行為。語義相似度是給定種子輸入 s 和一組種子輸入 S 共同覆蓋的路徑轉換與集合 S 覆蓋的路徑轉換的比率。

若Cov(s) = {A, B, D, Z}, Cov all(S) = {A, B, C,E, F, K, T, S}，則該種子輸入與種子組的語義相似性為0.25。

（二）語法相似性

語法相似性 Sim_syn描述種子輸入在語法上如何與種子組相似。將種子輸入 s 視為大小為N位的位串，并定義種子組的代表性種子輸入s_id為種子組的語法特征。代表性種子是種子組中能夠到達最多罕見覆蓋路徑轉換Cov_rare的種子，其作用是描述引導探索罕見覆蓋路徑轉換的語法特征。

μ(s, sid) 是種子s與sid之間相同比特位置上值相同的次數，s[i] 表示種子輸入 s 的第i個比特的值，N為長度更長的種子輸入的大小。若s = “0 1 0 1 0 0 0 0 1 1”, sid = “0 1 1 0 0 0 0 1 1 1”，則種子輸入與種子組之間的語法相似性為0.7。

（三）稀有度相似性

稀有度相似性基于從很少探索的執行轉換開始的突變可能會探索更深的程序位置的假設。 （） 表示種子組覆蓋中那些罕見路徑覆蓋轉換的集合。

其中 hit(path) 表示執行路徑的命中計數。如果 Sim_rare 覆蓋了更多很少探索的路徑轉換，則需要為給定種子輸入 s 分配更多的分數。與其他兩個相似性不同，Sim_rare對聚類沒有太大影響，但當種子組之間沒有顯著差異時，對識別最相似的種子組仍然有用。

（四）相似度得分

在獲得三種不同的相似性（即語法、語義和稀有度）后，CLUSTER 計算種子輸入與每個種子組之間的相似性分數（score_sim），并確定給定的種子輸入所屬的種子組。CLUSTER 函數定義為

其中d_max表示種子與所有種子組計算得到的最高相似性分數。當d_max超過γ值時，argmax 函數返回得分為d_max的種子組。否則，種子輸入 s 不屬于任何現有種子組， CLUSTER 函數通過使用代表性種子輸入 s 初始化組來組織新的種子組，將 Pid 初始化為均勻分布 (Pr)。通過使用以下等式獲得相似性分數score_sim。

超參數α反映了語法相似度與語義相似度的重要程度。經過反復試驗，將α值設置為 0.9。

四、概率分布學習

概率學習器，它學習針對每個種子組選擇有效變異方法的概率分布。

（一）采樣空間

首先定義一個采樣空間，用于選擇變異方法 m，該空間指定在哪里變異 (loc) 以及如何變異 (op)。如何變異與預定義的變異算子直接相關，因此，可以很容易地確定選擇變異算子的采樣空間。然而，由于給定的種子輸入大小不同，使得難以定義選擇突變位置的采樣空間。

為了具體確定選擇 loc 的采樣空間，本文將種子輸入的長度除以 p 值，使 loc 的采樣空間大小為 p，而不管種子輸入如何。通過對空間進行分區，本文可以將采樣空間從未定義大小 (loc) 轉換為具體確定大小 (p) 的位置。一旦本文的變異策略選擇了某個變異分區，它就會隨機選擇所選分區內的位置。

（二）湯普森采樣

為了學習對種子組最有效的變異方法，本文問題可以自然地表示為多臂老虎機 (MAB) 問題。MAB 問題假設有 N 臺老虎機，其目標是從它們那里獲得最大的獎勵。在每一輪中，本文選擇一個老虎機進行游戲，并通過遵循為每個老虎機設定的概率分布來獲得獎勵。在本文的問題設置中，每個老虎機對應于每個變異算子 op 和變異分區 p；在模糊測試技術中，獎勵可能對應于找到新的執行路徑或新的崩潰輸入。

本文方法的目標變成了找到最有利可圖的老虎機（即有效的變異方法）以實現最大化的獎勵，其中第 k 個老虎機獲得獎勵的成功概率為θk。為實現這一目標，本文采用了 Thompson 抽樣算法，這是經典 MAB 問題的著名解決方案。湯普森抽樣根據觀察到的獎勵建立概率模型，并從相應模型中采樣每個老虎機的期望值，以選擇下一輪的老虎機。直覺上，對特定老虎機觀察到的獎勵越多，就越有可能在下一輪選擇該老虎機。如果某個老虎機的成功概率很低，則隨著觀察到的數據越多，選擇這個老虎機的概率也會越低。

（三）學習算法

基于湯普森抽樣，定義選擇第 i 個變異算子的概率如下：

其中  表示從 Beta 分布 beta(  ，  ) 中采樣的第i個老虎機（第i個變異算子）的預期獎勵。|V^op|表示突變算子的數量。向量  表示選擇第i個變異算子生成有效測試用例的次數，而  表示生成失敗的測試用例。

定義模糊測試成功和失敗的最簡單方法是生成的測試用例是否是一個有趣的輸入；否則，認為該測試用例失敗。如果天真地定義成功和失敗案例，將無法學習選擇有效變異方法的概率分布。由于灰盒模糊測試技術的低效率，選擇有效變異方法的概率分布將退化為均勻分布。為了解決這個問題，本文為成功和失敗案例引入了額外的分類標準：

1) s ' 覆蓋 Covrare 中的至少一個路徑轉換，

2) s ' 覆蓋 Covcommon 中超過 80% 的路徑轉換。

要成為成功測試用例，s’需要滿足有趣或上述第一個條件。僅僅是一個無趣的測試用例還不足以成為一個失敗用例，必須滿足第二個條件。有了這兩個附加條件，可以提高成功次數并降低失敗次數。本文為每個路徑轉換維護一個命中計數表。每當使用生成的測試用例執行程序 pgm 時，都會更新此命中計數表。使用此命中計數信息按升序排列，建立 Covrare（前30%） 和 Covcommon（后30%）兩個集合。

在此示例中，s1 和 s2 都不是有趣的測試用例，因為它們未能涵蓋新的執行路徑。然而，s1 被認為是成功案例，因為它滿足第一個條件，本文使用的變異方法更新良好的學習數據 Dg 以生成 s1。對于 s2 ，本文不更新 Dg 或 Db，因為它不成功并且不滿足任何條件。

基于上述分類標準，將在運行過程中更新學習數據 Dg 和 Db。學習數據D是一對兩個向量，變異算子數據（V^op）和變異分區數據（V^p）；每個向量的第i個元素分別表示第i個變異算子和分區被選擇的次數。在學習數據 D 的基礎上，Dg 用于累積變異方法在生成成功測試用例時使用的數量，而 Db 用于生成失敗測試用例。

比較早期和后期生成的成功測試用例的數量時，隨著時間的推移，找到有效輸入變得越來越困難。理論上，后期獲得的成功獎勵應該要比前期相對高一些，模糊測試才能有效進行。因此，隨著模糊測試的進行，會逐漸增加基礎獎勵以便后續生成成功測試用例獲得更多利潤。

五、實驗設計及結果

（一）實驗設置

為了進行評估，本文使用了 FUZZBENCH，一種具有多種指標的模糊器基準測試框架。將FUZZBENCH中使用的所有參數值設置為默認值，并使用FUZZBENCH提供的運行腳本文件。本文在 AFL++上實現SEAMFUZZ，并將其與兩種不同的基于突變的灰盒模糊器 AFL++ 和 AFL++MOPT 進行了比較。

評估的三個模糊器均基于 AFL++，版本為 3.15a。在 24 小時內通過 20 次試驗評估了每個基準程序，以減輕模糊測試技術固有隨機性的影響，并報告了平均結果。所有實驗均在運行 Ubuntu 20.04 的機器上完成，該機器配備 64 個 CPU 和 256GB 內存，由 AMD Ryzen Threadripper 3990X 64 核處理器提供支持。實驗基準如圖3所示：

圖3 基準程序

（二）具體實驗

實驗一：SEAMFUZZ的有效性

圖4展示了SEAMFUZZ的性能表現。SEAMFUZZ 平均覆蓋的分支比 AFL++ 和 AFL++MOPT 分別多 5.6% 和 7.7%。在碰撞輸入生成能力方面，SEAMFUZZ 成功地生成了比 AFL++ 和 AFL++MOPT 多 56.4% 和 57.1% 的碰撞輸入。SEAMFUZZ 通常實現最高數量的覆蓋分支。例如，在 objdump 上，SEAMFUZZ 成功覆蓋了 5,759 個分支，而 AFL++ 和 AFL++MOPT 分別只覆蓋了 4,969 和 4,663 個分支。SEAMFUZZ 可以產生比其他模糊器多得多的崩潰輸入，即使分支覆蓋范圍的增量很小。例如，在 php-parser 上，SEAMFUZZ 生成的崩潰輸入比 AFL++ 多 233.3%，而覆蓋分支數量的增加僅為 0.4%

圖4 24 小時內對 14 個程序進行 20 次試驗的平均結果。

實驗二：BUG發現能力

圖 5顯示種子自適應方法在發現各種錯誤方面具有相當大的潛力。SEAMFUZZ 可以發現最多的獨特錯誤（99個錯誤），包括 27 個其他基線模糊器未檢測到的錯誤，而 AFL++ 和 AFL++MOPT 在 14 個基準程序中發現了 85 和 87 個獨特錯誤。

圖5 每個工具發現的獨特錯誤的維恩圖

圖6展示了評估每個工具在 MAGMA上的錯誤發現能力。由于 MAGMA 提供了多個模糊測試目標程序，本文評估了每個程序的實驗。為了在 FUZZBENCH 上評估注入錯誤的 MAGMA 基準程序，本文插入了斷言語句來指定 MAGMA 中的錯誤條件。所有的模糊器都可以檢測到相同的 14 個 MAGMA 錯誤，SEAMFUZZ 和 AFL++ 在 libxml2 中檢測到另一個錯誤“XML002”，而 AFL++MOPT 只能在 openssl 中檢測到SSL020”。

圖6 每個模糊器都發現的MAGMA錯誤

實驗三：種子聚類的有效性

為了研究種子聚類的功效，本文實施了 NOCLUSTER 和 EACHCLUSTER，它們維護不同數量的種子組。更準確地說，NOCLUSTER 只維護一個種子組，并將所有選定的種子輸入聚集到這個組中，這模擬了程序自適應方法。EACHCLUSTER 為每個種子輸入分配一個種子組，它分別應用為每個種子輸入量身定制的不同變異策略。

圖7展示采用聚類方法與否的實驗性能。圖8展示相似性分數中超參數α的選取實驗結果。在所有 14 個程序中，與 SEAMFUZZ 相比，NOCLUSTER 和 EACHCLUSTER 覆蓋的分支分別減少了 4.9% 和 4.4%。碰撞輸入生成的性能下降更為嚴重；NOCLUSTER 和 EACHCLUSTER 分別減少了 36.3% 和 25.5% 的碰撞輸入。

圖7 不同粒度的種子聚類性能表現

圖8 不同超參數α下性能表現

實驗四：學習算法的有效性

圖9展示評估 Thompson 抽樣算法中成功和失敗案例的分類標準如何影響 SEAMFUZZ 在前 9 個程序中的整體性能。更準確地說，本文將 SEAMFUZZ 與 NAIVESEAMFUZZ 進行了比較，為 Thompson 采樣定制的標準提高了路徑發現和崩潰生成能力；與樸素分類相比，它有助于多覆蓋 6.1% 的分支并多生成 57.1% 的碰撞輸入。

圖9 不同數據分類標準下性能表現

本文調查了成功獎勵的增加值如何影響本文方法的性能。為了觀察獎勵動態變化對績效的影響，本文用五種不同的設置評估了 SEAMFUZZ；REWARDN 將獎勵增加“N”。如圖10所示，使用適當的值動態更新獎勵可以顯著提高本文方法的性能。

圖10 不同獎勵值增長下性能表現

六、 總結

最近，灰盒模糊器的程序自適應突變策略已經成功地改進了現有的與程序無關的模糊器。在本文中更進一步，呼吁關注從程序自適應方法到種子自適應方法的轉變。關鍵思想是根據句法和語義相似性將種子輸入聚類到種子組中，并使用 Thompson 抽樣的變體在線學習針對每個種子組優化的變異策略。證明了本文的種子自適應方法在覆蓋率和錯誤發現方面極大地增強了最先進的程序自適應技術。