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

(國防科技大學(xué) 電子對抗學(xué)院，合肥 230037) (網(wǎng)絡(luò)空間安全態(tài)勢感知與評(píng)估安徽省重點(diǎn)實(shí)驗(yàn)室，合肥 230037)

1 背 景

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

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

無論是基于變異還是基于語義的測試用例生成方法都只關(guān)注單一變異算子本身的變異效率，在實(shí)際測試過程中模糊測試器會(huì)同時(shí)調(diào)用多種變異算子生成測試用例.面對同時(shí)調(diào)用多種變異算子的情況時(shí)，當(dāng)前模糊測試技術(shù)認(rèn)為不同變異算子變異效率相同，不考慮不同程序狀態(tài)對不同變異算子的影響，簡單地通過固定順序或隨機(jī)調(diào)度方式選擇變異算子，造成模糊測試器性能的浪費(fèi).

本文對不同變異算子之間的協(xié)同調(diào)度問題進(jìn)行研究，首先通過大量實(shí)驗(yàn)，分析不同變異算子在不同程序狀態(tài)下的變異效率，為建立變異算子調(diào)度模型提供數(shù)據(jù)支撐，其次根據(jù)實(shí)驗(yàn)數(shù)據(jù)以探索利用模型為基礎(chǔ)，建立變異算子調(diào)用優(yōu)化模型EE-POS，并基于開源項(xiàng)目AFL實(shí)現(xiàn)了EE-POS-AFL.

2 相關(guān)研究

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

表1 變異算子

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

表2 變異算子調(diào)用產(chǎn)出表

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

圖1 Libming 變異效率比例圖

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

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

圖2 Objdump 變異效率比例圖

圖3 Tiff 變異效率比例

在圖4、圖5、圖6的變化中可以看到，隨著時(shí)間的變化不同變異算子的變異效率在動(dòng)態(tài)變化.以變異算子Arith8/8為例，在對測試程序Libming進(jìn)行測試的過程中，Arith8/8在0到960分鐘內(nèi)的變異效率要高于960分鐘到2880分鐘內(nèi)的變異效率.此外，通過圖4、圖5、圖6的變化變化趨勢可以看出，每個(gè)變異算子的變異效率具有收斂性，從實(shí)驗(yàn)數(shù)據(jù)可以得出以下4個(gè)結(jié)論：

圖4 Libming 變異效率變化曲線

圖5 Tiff 變異效率變化曲線

圖6 Objdump 變異效率變化曲線

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

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

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

4)隨著變異算子調(diào)用次數(shù)的增多，不同變異算子之間發(fā)現(xiàn)的路徑數(shù)量比例趨于穩(wěn)定.

基于以上4點(diǎn)結(jié)論，可以看出隨機(jī)或固定順序的變異算子調(diào)度策略無法使模糊測試器對所有類型的程序都保持一個(gè)較高的變異效率.合理的變異算子調(diào)度策略應(yīng)該滿足適應(yīng)不同程序、適應(yīng)不同時(shí)刻和資源占用低3個(gè)特性.具體來講，一個(gè)合理的變異調(diào)度策略可以花費(fèi)極少的資源對當(dāng)前變異算子的變異效率進(jìn)行統(tǒng)計(jì)，并根據(jù)變異算子的變異效率進(jìn)行變異調(diào)度，使得模糊測試器始終保持一個(gè)較高的變異效率.

3 變異算子優(yōu)化模型

3.1 探索與利用模型

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

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

在變異調(diào)度問題中，變異算子之間無相互干擾，每個(gè)變異算子可以類比為一臺(tái)老虎機(jī)，變異調(diào)度問題可以轉(zhuǎn)化為探索與利用問題進(jìn)行解決.但與理想情況下的老虎機(jī)問題不同，變異算子得到有效測試用例的概率是動(dòng)態(tài)變化的.因此，需要對利用階段變異算子發(fā)現(xiàn)有效測試用例的概率進(jìn)行動(dòng)態(tài)更新.

基于探索利用模型并結(jié)合第2章對變異算子變異效率的分析，可以得到變異調(diào)度優(yōu)化模型應(yīng)滿足的3條原則.

1)在利用階段動(dòng)態(tài)更新變異算子發(fā)現(xiàn)有效測試用例的概率.

2)變異算子整體發(fā)現(xiàn)有效測試用例概率最高.

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

3.2 變異算子調(diào)度優(yōu)化模型

在3.1節(jié)討論了變異算子優(yōu)化模型設(shè)計(jì)的3條原則.在本節(jié)中對變異算子調(diào)度優(yōu)化模型進(jìn)行設(shè)計(jì).首先給出變異算子優(yōu)化模型的優(yōu)化目標(biāo)函數(shù)，如公式(1)所示.

(1)

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

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

(2)

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

(3)

(4)

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

(5)

3.3 模型實(shí)現(xiàn)

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

算法輸入為每輪測試選擇次數(shù)Limit，變異算子初始化概率Init[i]，模型波動(dòng)系數(shù)F，變異算子個(gè)數(shù).算法輸出為變異算子發(fā)現(xiàn)的有效測試用例集.

算法1.變異調(diào)度優(yōu)化算法

輸入：Limit，Init[i]，F(xiàn)，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)//是否收到終止信號(hào)

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行為模型的初始化模塊，執(zhí)行初始化操作，為模型中的數(shù)據(jù)結(jié)構(gòu)賦初始值.

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

算法13到16行為模型更新概率更新模塊，算法13行按照公式(3)、公式(4)更新變異算子發(fā)現(xiàn)有效測試用例的概率.算法14行按照公式(5)計(jì)算模型的波動(dòng)系數(shù).

3.4 模型效率分析

為說明變異算子調(diào)度優(yōu)化模型對模糊測試器運(yùn)行效率的影響，從時(shí)間復(fù)雜度和空間復(fù)雜度兩個(gè)方面進(jìn)行分析.

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

4 實(shí) 驗(yàn)

為了檢驗(yàn)變異算子調(diào)度優(yōu)化模型的效果，本文在開源項(xiàng)目AFL基礎(chǔ)上實(shí)現(xiàn)了EE-POS-AFL，并與AFL進(jìn)行對比實(shí)驗(yàn).實(shí)驗(yàn)對模糊測試器路徑發(fā)現(xiàn)效率、Crash發(fā)現(xiàn)效率兩個(gè)指標(biāo)進(jìn)行對比.測試程序分為兩類，一類為真實(shí)目標(biāo)程序Libming、Tiff和Objdump；第2類為模糊測試器通用測試集LAVA-M[14]中的Who、Base64、Md5sum和Uniq.

實(shí)驗(yàn)服務(wù)器設(shè)置為：Intel(R)Xeon(R)Gold 6230×4，252G內(nèi)存，8T固態(tài)硬盤，操作系統(tǒng)為Unbuntu server 20.04.

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

表3 實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)

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

表4 效率對比表

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

圖7 Md5sum 路徑發(fā)現(xiàn)數(shù)量

圖8 Who 路徑發(fā)現(xiàn)數(shù)量

圖7和圖8中的變化曲線具有相同的變化規(guī)律，因此以圖8為例對圖像進(jìn)行分析.在對Who的測試中，前240分鐘AFL發(fā)現(xiàn)新路徑的效率要高于EE-POS-AFL，240分鐘到測試結(jié)束這段時(shí)間EE-POS-AFL發(fā)現(xiàn)新路徑的效率要高于AFL.這是因?yàn)樵谧儺愓{(diào)度優(yōu)化模型中，變異算子初始狀態(tài)為人為賦值誤差較大，此時(shí)AFL的效率高于EE-POS-AFL.隨著模型不斷地探索，變異算子的狀態(tài)趨近于最優(yōu)，此時(shí)EE-POS-AFL的效率超過AFL.

對比實(shí)驗(yàn)表明本文設(shè)計(jì)的變異算子調(diào)度優(yōu)化模型相比傳統(tǒng)的隨機(jī)調(diào)度模型，路徑發(fā)現(xiàn)效率提高了63%，Crash發(fā)現(xiàn)效率提高了153%，證明了變異算子調(diào)度優(yōu)化模型的有效性.

5 總 結(jié)

本文對模糊測試過程中分別對變異算子在不同類型程序上的效率、變異算子在同一程序不同時(shí)刻的變異效率進(jìn)行分析，找到了現(xiàn)有變異算子調(diào)度規(guī)則的不足，并針對不足提出了理想的變異算子調(diào)度規(guī)則應(yīng)滿足的3個(gè)特性.

本文以探索利用模型為基礎(chǔ)，設(shè)計(jì)實(shí)現(xiàn)了變異算子調(diào)度優(yōu)化模型，并在開源框架AFL上實(shí)現(xiàn)了該模型，對比實(shí)驗(yàn)表明該模型可以有效提高模糊測試器的變異效率.

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