模糊測試變異算子調度優化模型

李明磊，陸余良，黃 暉，朱凱龍

(國防科技大學 電子對抗學院，合肥 230037) (網絡空間安全態勢感知與評估安徽省重點實驗室，合肥 230037)

1 背 景

模糊測試技術是一種通過隨機輸入對程序進行測試的技術.研究人員通過分析程序崩潰時的程序上下文狀態與輸入的測試用例實現對程序漏洞的定位[1].模糊測試技術因其自動化程度高、軟件適用性好等優點被廣泛應用于軟件測試當中.為提高模糊測試技術的效率，研究人員對模糊測試技術開展了廣泛的研究，將靜態分析、污點分析、符號執行等技術引入到模糊測試技術中，使得模糊測試技術可以通過收集程序運行狀態指導測試用例的生成，出現了以AFL[2]、Driller[3]、AflFast[4]、Skyfire[5]、BORG[6]為代表的反饋式模糊測試器.

當前模糊測試技術有基于變異和基于語義的兩種測試用例生成方法[7].基于變異的測試用例生成方法指模糊測試器對測試用例進行隨機變化，產生新的程序輸入作為測試用例，每一種隨機變化方式稱為一種變異算子，基于變異生成測試用例的模糊測試器有AFL、AflFast、Peach[8]、EcoFuzz[9]等.基于語義的測試用例生成方法指模糊測試器對程序輸入的語義進行分析得到程序輸入的格式，模糊測試器在程序輸入格式的指導下生成測試用例，基于語義生成測試用例的模糊測試器有SPIKE[10]、Learn & Fuzz[11]等.

無論是基于變異還是基于語義的測試用例生成方法都只關注單一變異算子本身的變異效率，在實際測試過程中模糊測試器會同時調用多種變異算子生成測試用例.面對同時調用多種變異算子的情況時，當前模糊測試技術認為不同變異算子變異效率相同，不考慮不同程序狀態對不同變異算子的影響，簡單地通過固定順序或隨機調度方式選擇變異算子，造成模糊測試器性能的浪費.

本文對不同變異算子之間的協同調度問題進行研究，首先通過大量實驗，分析不同變異算子在不同程序狀態下的變異效率，為建立變異算子調度模型提供數據支撐，其次根據實驗數據以探索利用模型為基礎，建立變異算子調用優化模型EE-POS，并基于開源項目AFL實現了EE-POS-AFL.

2 相關研究

在本節中以開源模糊測試器AFL為例，對變異算子的變異效率進行研究，表1為AFL中用到的變異算子[12].AFL通過固定順序與隨機調度相結合的策略對變異算子進行調度.當測試用例進行第1輪變異時，AFL按照固定順序依次調用表1中的變異算子生成測試用例，當該測試用例進行第2輪變異時，AFL隨機調用表1中的幾種變異算子進行組合生成測試用例.這種變異調度方式雖然簡單快捷，但會產生大量的無效變異，無法保證模糊測試器整體變異效率最優.

表1 變異算子

為進一步解釋隨機調度變異算子無法保證模糊測試整體效率最優的原因，本文使用AFL分別對命令處理類軟件Objdump、圖像處理類軟件Tiff和流媒體軟件Libming進行持續一周的測試，統計不同變異算子調用的次數與該變異算子產生的有效測試用例的數量，本文中有效測試用例指該測試用例覆蓋到了程序新的路徑.表2統計了AFL持續運行7天后，不同變異算子被調用的次數與產生的有效測試用例數量.Exe表示變異算子選用了幾次，單位兆次.Num表示變異算子產生的有效測試用例的數量.

表2 變異算子調用產出表

為便于分析對表2數據進行處理，處理后的數據如圖1、圖2、圖3所示.圖1為Libming變異效率比例圖，圖2為Objdump變異效率比例圖，圖3為Tiff變異效率比例圖.圖中橫坐標為模糊測試器調用的變異算子，縱坐標分別為該變異被調用的次數在總調用次數中的占比(左側有填充條柱)和該變異算子產生的有效測試用例在有效測試用例總體中的占比(右側無填充條柱).

圖1 Libming 變異效率比例圖

從圖1、圖2、圖3可以看出，不同變異算子在不同類型的程序上的變異效率不同，以變異算子Arith8/8為例，在Libming中以19.2%的調用比生成了32.9%的有效測試用例；在Objdump中以19.1%的調用比生成了18.8%的有效測試用例；在Tiff中以4.7%的調用比生成了25.4%的有效測試用例.

圖1、圖2、圖3對同一個變異算子在不同程序上的變異效率進行了研究，接下來對同一個變異算子在一個程序不同時刻的變異效率展開研究，為便于展示從15個變異算子中選取4個變異算子進行跟蹤分析.分析結果如圖4、圖5、圖6所示.圖4為Libming變異效率變化曲線，圖5為Tiff變異效率變化曲線，圖6為Objdump變異效率變化曲線.

圖2 Objdump 變異效率比例圖

圖3 Tiff 變異效率比例

在圖4、圖5、圖6的變化中可以看到，隨著時間的變化不同變異算子的變異效率在動態變化.以變異算子Arith8/8為例，在對測試程序Libming進行測試的過程中，Arith8/8在0到960分鐘內的變異效率要高于960分鐘到2880分鐘內的變異效率.此外，通過圖4、圖5、圖6的變化變化趨勢可以看出，每個變異算子的變異效率具有收斂性，從實驗數據可以得出以下4個結論：

圖4 Libming 變異效率變化曲線

圖5 Tiff 變異效率變化曲線

圖6 Objdump 變異效率變化曲線

1)同一變異算子在不同程序上變異效率不同.

2)同一變異算子在同一程序上不同時刻的變異效率不同.

3)隨著變異算子調用次數的增多，該變異算子變異效率逐漸降低.

4)隨著變異算子調用次數的增多，不同變異算子之間發現的路徑數量比例趨于穩定.

基于以上4點結論，可以看出隨機或固定順序的變異算子調度策略無法使模糊測試器對所有類型的程序都保持一個較高的變異效率.合理的變異算子調度策略應該滿足適應不同程序、適應不同時刻和資源占用低3個特性.具體來講，一個合理的變異調度策略可以花費極少的資源對當前變異算子的變異效率進行統計，并根據變異算子的變異效率進行變異調度，使得模糊測試器始終保持一個較高的變異效率.

3 變異算子優化模型

3.1 探索與利用模型

探索與利用模型是一種通用的強化學習模型，常被用來解決在有限次嘗試中獲取最大收益類的問題，以多臂老虎機問題對該模型解決的問題進行簡要介紹[13].假設當前有k個老虎機，每個老虎機會以一定概率吐出金幣，如何在n次的選擇中獲取最多的收益是探索與利用模型所解決的問題.

在多臂老虎機問題中，每個老虎機吐出金幣的概率未知.在進行選擇前需要先對每個老虎機進行一定次的選取，以估算每個老虎機吐出金幣的概率，之后根據不同老虎機吐出金幣的概率對老虎機進行選擇.估算老虎機吐出金幣概率的過程稱為探索，根據概率進行老虎機選取的過程稱為利用.

在變異調度問題中，變異算子之間無相互干擾，每個變異算子可以類比為一臺老虎機，變異調度問題可以轉化為探索與利用問題進行解決.但與理想情況下的老虎機問題不同，變異算子得到有效測試用例的概率是動態變化的.因此，需要對利用階段變異算子發現有效測試用例的概率進行動態更新.

基于探索利用模型并結合第2章對變異算子變異效率的分析，可以得到變異調度優化模型應滿足的3條原則.

1)在利用階段動態更新變異算子發現有效測試用例的概率.

2)變異算子整體發現有效測試用例概率最高.

3)在利用階段保持一定比例的探索.

3.2 變異算子調度優化模型

在3.1節討論了變異算子優化模型設計的3條原則.在本節中對變異算子調度優化模型進行設計.首先給出變異算子優化模型的優化目標函數，如公式(1)所示.

(1)

公式(1)中X表示變異算子被選中的總次數，Pi表示第i個變異算子生成有效測試用例的概率，xi表示第i個變異算子被選中的次數.F(X)為優化目標，求解該問題的關鍵在于為變異算子i分配合理的選擇次數，使得模糊測試器在有限次變異中發現更多的路徑.這類問題最簡單的做法是將所有選擇次數都分配給Pi最大的變異算子.但在變異算子優化模型中Pi為估計值，該值在模型初期誤差較大，將所有的選擇次數都分配給Pi最大的變異算子將會引入較大的誤差.此外，Pi的值隨時間動態變化，變異算子優化模型需要具備對Pi進行定期更新的能力.這就要求在利用階段每個變異算子都應被分配到一定比例的選擇次數.因此每個變異算子被選中的次數必須大于0.

在變異算子優化模型中，將采取按比例分配的方式為每個變異算子分配執行次數，如公式(2)所示.公式中R表示Pi更新的輪次，C表示Pi在R次更新和R+1次更新之間，模糊測試器選擇變異算子的總次數.

(2)

通過按比例分配執行次數的方式，將每個變異算子的執行次數與其生成有效測試用例的概率掛鉤，這樣可以將探索過程與利用過程相結合.在模型初始化階段給每一個變異算子賦予相同的概率，可以使得每個變異算子得到相同的執行次數，此時模型以探索為主.隨著模型不斷更新，不同變異算子之間的概率差異變大，每個模型分配到的執行次數隨著產生分化，此時模型以利用為主.

(3)

(4)

在得到了Pi更新函數后，對Pi更新周期進行研究.從圖4、圖5、圖6可以看出變異算子的變異效率在測試初期波動較大，隨著模糊測試的不斷進行，變異算子的變異效率趨于穩定.因此，Pi在變異效率波動較大時應快速更新，在變異效率趨于穩定時應降低更新頻率，以降低模型更新帶來的資源開銷.在模型中引入擾動系數F描述每次更新Pi后模型波動的大小，如公式(5)所示.在模型運行過程中通過擾動系數F對每輪測試的時長進行控制，擾動系數越大模型波動越劇烈，模型應該提高Pi更新速度.

(5)

3.3 模型實現

在3.2節中給出了模型的關鍵函數，在本節中對模型的實現進行介紹.變異調度優化模型分為3個模塊：初始化模塊、探索與利用模塊、概率更新模塊.在初始化模塊中對模型中的數據結構進行優化，為每個變異算子賦予初始概率.探索與利用模塊按照變異算子生成有效測試用例的概率為每個變異算子分配選擇次數，調用模糊測試器中的變異操作對程序進行測試并收集反饋信息.概率更新模塊根據探索與利用模塊收集到的反饋信息計算變異算子生成有效測試用例的概率和模型波動系數，模型運行過程如算法1所示.

算法輸入為每輪測試選擇次數Limit，變異算子初始化概率Init[i]，模型波動系數F，變異算子個數.算法輸出為變異算子發現的有效測試用例集.

算法1.變異調度優化算法

輸入：Limit，Init[i]，F，Op，TestCaseSet

輸出：EffectiveCaseSet

1. P[i]=Init[i]

2. F=1

3. C=0

4. X[i]=0

5. f[i]=0

6. While(Stop)//是否收到終止信號

8. {tmp=Calculation_score()

9. C=C+tmp

10. X[i]=Distribution(tmp，P[i])

11. Fuzz(X[i]，f[i])

12. }

13. P[i]=Update_efficiency(X[i]，f[i])

14. F=Calculate_fluctuation(X[i]，f[i])

15. f[i]=0

16. C=0

17.}

算法1到5行為模型的初始化模塊，執行初始化操作，為模型中的數據結構賦初始值.

算法第6到第12行為模型的探索利用模塊，算法第6行判斷模糊測試是否接收到終止信號，算法第7行判斷當前更新輪次執行次數是否小于當前更新輪次限定的執行次數，小于則繼續執行本輪次更新，大于則對變異算子發現有效測試用例的概率進行更新.算法第8行調用模糊測試器中的Calculation_score函數，該函數從測試用例集中選擇一個測試用例計算該測試用例需要進行變異的總次數.算法第10行按照公式2為每個變異算子分配選擇次數.算法第11行調用模糊測試器中的fuzz函數，該函數按照分配好的變異次數調用不同的變異算子對測試用例進行變異，統計每個變異算子生成的有效測試用例數量，并將產生的有效測試用例加入到輸出集合中.

算法13到16行為模型更新概率更新模塊，算法13行按照公式(3)、公式(4)更新變異算子發現有效測試用例的概率.算法14行按照公式(5)計算模型的波動系數.

3.4 模型效率分析

為說明變異算子調度優化模型對模糊測試器運行效率的影響，從時間復雜度和空間復雜度兩個方面進行分析.

首先對空間復雜度進行分析，在變異調度優化模型中共引入了4個n維數組(n為變異算子的數量)記錄變異算子的初始變異效率、被選中次數、有效變異次數等信息，產生的額外空間開銷為O(n).

4 實 驗

為了檢驗變異算子調度優化模型的效果，本文在開源項目AFL基礎上實現了EE-POS-AFL，并與AFL進行對比實驗.實驗對模糊測試器路徑發現效率、Crash發現效率兩個指標進行對比.測試程序分為兩類，一類為真實目標程序Libming、Tiff和Objdump；第2類為模糊測試器通用測試集LAVA-M[14]中的Who、Base64、Md5sum和Uniq.

實驗服務器設置為：Intel(R)Xeon(R)Gold 6230×4，252G內存，8T固態硬盤，操作系統為Unbuntu server 20.04.

Libming、Tiff和Objdump初始測試用例為選取自Testsuite測試集，Who、Base64、Md5sum和Uniq初始測試用例選取自LAVA-M自帶的初始化種子.實驗持續進行7天，進行5次重復實驗，實驗結果取平均值.實驗結果如表3所示，表中Path測試器覆蓋到的路徑數量，Crash表示模糊測試器生成的可以使程序奔潰的測試用例.

表3 實驗結果統計

為便于分析對表3的數據進行處理生成效率對比表，如表4所示.表中Improve_p表示EE-POS-AFL與AFL相比發現的路徑總數提高的倍數.表4中Improve_c表示EE-POS-AFL與AFL相比發現的Crash總數提高的倍數.

表4 效率對比表

從表4可以看出相比AFL，EE-POS-AFL在路徑發現數量和Crash發現數量上都有明顯的提升，在實際應用程序上提升更為明顯.在Objdump上路徑發現數量提升了4.03倍，Crash發現數量提升16倍.在Who、Md5sum兩個測試程序上EE-POS-AFL效果提升并不明顯.通過對初始測試用例的分析，發現Who、Md5sum的初始測試用例較小，經過長時間的模糊測試已經無法生成有效的測試用例使得程序覆蓋到新的路徑.為更進一步對AFL與EE-POS-AFL的效率進行比較，將Who和Md5sum的路徑發現數量與時間之間的關系繪制成圖像，如圖7、圖8所示.圖7為Md5sum路徑發現數量隨時間變化圖，圖8為Who路徑發現數量隨時間變化圖AFL.

圖7 Md5sum 路徑發現數量

圖8 Who 路徑發現數量

圖7和圖8中的變化曲線具有相同的變化規律，因此以圖8為例對圖像進行分析.在對Who的測試中，前240分鐘AFL發現新路徑的效率要高于EE-POS-AFL，240分鐘到測試結束這段時間EE-POS-AFL發現新路徑的效率要高于AFL.這是因為在變異調度優化模型中，變異算子初始狀態為人為賦值誤差較大，此時AFL的效率高于EE-POS-AFL.隨著模型不斷地探索，變異算子的狀態趨近于最優，此時EE-POS-AFL的效率超過AFL.

對比實驗表明本文設計的變異算子調度優化模型相比傳統的隨機調度模型，路徑發現效率提高了63%，Crash發現效率提高了153%，證明了變異算子調度優化模型的有效性.

5 總 結

本文對模糊測試過程中分別對變異算子在不同類型程序上的效率、變異算子在同一程序不同時刻的變異效率進行分析，找到了現有變異算子調度規則的不足，并針對不足提出了理想的變異算子調度規則應滿足的3個特性.

本文以探索利用模型為基礎，設計實現了變異算子調度優化模型，并在開源框架AFL上實現了該模型，對比實驗表明該模型可以有效提高模糊測試器的變異效率.

下一步將會對基于語義變異的模糊測試工具進行分析研究，對本文模型進行擴展.