李明磊,陸余良,黃 暉,朱凱龍
(國(guó)防科技大學(xué) 電子對(duì)抗學(xué)院,合肥 230037) (網(wǎng)絡(luò)空間安全態(tài)勢(shì)感知與評(píng)估安徽省重點(diǎn)實(shí)驗(yàn)室,合肥 230037)
模糊測(cè)試技術(shù)是一種通過(guò)隨機(jī)輸入對(duì)程序進(jìn)行測(cè)試的技術(shù).研究人員通過(guò)分析程序崩潰時(shí)的程序上下文狀態(tài)與輸入的測(cè)試用例實(shí)現(xiàn)對(duì)程序漏洞的定位[1].模糊測(cè)試技術(shù)因其自動(dòng)化程度高、軟件適用性好等優(yōu)點(diǎn)被廣泛應(yīng)用于軟件測(cè)試當(dāng)中.為提高模糊測(cè)試技術(shù)的效率,研究人員對(duì)模糊測(cè)試技術(shù)開(kāi)展了廣泛的研究,將靜態(tài)分析、污點(diǎn)分析、符號(hào)執(zhí)行等技術(shù)引入到模糊測(cè)試技術(shù)中,使得模糊測(cè)試技術(shù)可以通過(guò)收集程序運(yùn)行狀態(tài)指導(dǎo)測(cè)試用例的生成,出現(xiàn)了以AFL[2]、Driller[3]、AflFast[4]、Skyfire[5]、BORG[6]為代表的反饋式模糊測(cè)試器.
當(dāng)前模糊測(cè)試技術(shù)有基于變異和基于語(yǔ)義的兩種測(cè)試用例生成方法[7].基于變異的測(cè)試用例生成方法指模糊測(cè)試器對(duì)測(cè)試用例進(jìn)行隨機(jī)變化,產(chǎn)生新的程序輸入作為測(cè)試用例,每一種隨機(jī)變化方式稱為一種變異算子,基于變異生成測(cè)試用例的模糊測(cè)試器有AFL、AflFast、Peach[8]、EcoFuzz[9]等.基于語(yǔ)義的測(cè)試用例生成方法指模糊測(cè)試器對(duì)程序輸入的語(yǔ)義進(jìn)行分析得到程序輸入的格式,模糊測(cè)試器在程序輸入格式的指導(dǎo)下生成測(cè)試用例,基于語(yǔ)義生成測(cè)試用例的模糊測(cè)試器有SPIKE[10]、Learn & Fuzz[11]等.
無(wú)論是基于變異還是基于語(yǔ)義的測(cè)試用例生成方法都只關(guān)注單一變異算子本身的變異效率,在實(shí)際測(cè)試過(guò)程中模糊測(cè)試器會(huì)同時(shí)調(diào)用多種變異算子生成測(cè)試用例.面對(duì)同時(shí)調(diào)用多種變異算子的情況時(shí),當(dāng)前模糊測(cè)試技術(shù)認(rèn)為不同變異算子變異效率相同,不考慮不同程序狀態(tài)對(duì)不同變異算子的影響,簡(jiǎn)單地通過(guò)固定順序或隨機(jī)調(diào)度方式選擇變異算子,造成模糊測(cè)試器性能的浪費(fèi).
本文對(duì)不同變異算子之間的協(xié)同調(diào)度問(wèn)題進(jìn)行研究,首先通過(guò)大量實(shí)驗(yàn),分析不同變異算子在不同程序狀態(tài)下的變異效率,為建立變異算子調(diào)度模型提供數(shù)據(jù)支撐,其次根據(jù)實(shí)驗(yàn)數(shù)據(jù)以探索利用模型為基礎(chǔ),建立變異算子調(diào)用優(yōu)化模型EE-POS,并基于開(kāi)源項(xiàng)目AFL實(shí)現(xiàn)了EE-POS-AFL.
在本節(jié)中以開(kāi)源模糊測(cè)試器AFL為例,對(duì)變異算子的變異效率進(jìn)行研究,表1為AFL中用到的變異算子[12].AFL通過(guò)固定順序與隨機(jī)調(diào)度相結(jié)合的策略對(duì)變異算子進(jìn)行調(diào)度.當(dāng)測(cè)試用例進(jìn)行第1輪變異時(shí),AFL按照固定順序依次調(diào)用表1中的變異算子生成測(cè)試用例,當(dāng)該測(cè)試用例進(jìn)行第2輪變異時(shí),AFL隨機(jī)調(diào)用表1中的幾種變異算子進(jìn)行組合生成測(cè)試用例.這種變異調(diào)度方式雖然簡(jiǎn)單快捷,但會(huì)產(chǎn)生大量的無(wú)效變異,無(wú)法保證模糊測(cè)試器整體變異效率最優(yōu).
表1 變異算子
為進(jìn)一步解釋隨機(jī)調(diào)度變異算子無(wú)法保證模糊測(cè)試整體效率最優(yōu)的原因,本文使用AFL分別對(duì)命令處理類軟件Objdump、圖像處理類軟件Tiff和流媒體軟件Libming進(jìn)行持續(xù)一周的測(cè)試,統(tǒng)計(jì)不同變異算子調(diào)用的次數(shù)與該變異算子產(chǎn)生的有效測(cè)試用例的數(shù)量,本文中有效測(cè)試用例指該測(cè)試用例覆蓋到了程序新的路徑.表2統(tǒng)計(jì)了AFL持續(xù)運(yùn)行7天后,不同變異算子被調(diào)用的次數(shù)與產(chǎn)生的有效測(cè)試用例數(shù)量.Exe表示變異算子選用了幾次,單位兆次.Num表示變異算子產(chǎn)生的有效測(cè)試用例的數(shù)量.
表2 變異算子調(diào)用產(chǎn)出表
為便于分析對(duì)表2數(shù)據(jù)進(jìn)行處理,處理后的數(shù)據(jù)如圖1、圖2、圖3所示.圖1為L(zhǎng)ibming變異效率比例圖,圖2為Objdump變異效率比例圖,圖3為T(mén)iff變異效率比例圖.圖中橫坐標(biāo)為模糊測(cè)試器調(diào)用的變異算子,縱坐標(biāo)分別為該變異被調(diào)用的次數(shù)在總調(diào)用次數(shù)中的占比(左側(cè)有填充條柱)和該變異算子產(chǎn)生的有效測(cè)試用例在有效測(cè)試用例總體中的占比(右側(cè)無(wú)填充條柱).
圖1 Libming 變異效率比例圖
從圖1、圖2、圖3可以看出,不同變異算子在不同類型的程序上的變異效率不同,以變異算子Arith8/8為例,在Libming中以19.2%的調(diào)用比生成了32.9%的有效測(cè)試用例;在Objdump中以19.1%的調(diào)用比生成了18.8%的有效測(cè)試用例;在Tiff中以4.7%的調(diào)用比生成了25.4%的有效測(cè)試用例.
圖1、圖2、圖3對(duì)同一個(gè)變異算子在不同程序上的變異效率進(jìn)行了研究,接下來(lái)對(duì)同一個(gè)變異算子在一個(gè)程序不同時(shí)刻的變異效率展開(kāi)研究,為便于展示從15個(gè)變異算子中選取4個(gè)變異算子進(jìn)行跟蹤分析.分析結(jié)果如圖4、圖5、圖6所示.圖4為L(zhǎng)ibming變異效率變化曲線,圖5為T(mén)iff變異效率變化曲線,圖6為Objdump變異效率變化曲線.
圖2 Objdump 變異效率比例圖
圖3 Tiff 變異效率比例
在圖4、圖5、圖6的變化中可以看到,隨著時(shí)間的變化不同變異算子的變異效率在動(dòng)態(tài)變化.以變異算子Arith8/8為例,在對(duì)測(cè)試程序Libming進(jìn)行測(cè)試的過(guò)程中,Arith8/8在0到960分鐘內(nèi)的變異效率要高于960分鐘到2880分鐘內(nèi)的變異效率.此外,通過(guò)圖4、圖5、圖6的變化變化趨勢(shì)可以看出,每個(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)度策略無(wú)法使模糊測(cè)試器對(duì)所有類型的程序都保持一個(gè)較高的變異效率.合理的變異算子調(diào)度策略應(yīng)該滿足適應(yīng)不同程序、適應(yīng)不同時(shí)刻和資源占用低3個(gè)特性.具體來(lái)講,一個(gè)合理的變異調(diào)度策略可以花費(fèi)極少的資源對(duì)當(dāng)前變異算子的變異效率進(jìn)行統(tǒng)計(jì),并根據(jù)變異算子的變異效率進(jìn)行變異調(diào)度,使得模糊測(cè)試器始終保持一個(gè)較高的變異效率.
探索與利用模型是一種通用的強(qiáng)化學(xué)習(xí)模型,常被用來(lái)解決在有限次嘗試中獲取最大收益類的問(wèn)題,以多臂老虎機(jī)問(wèn)題對(duì)該模型解決的問(wèn)題進(jìn)行簡(jiǎn)要介紹[13].假設(shè)當(dāng)前有k個(gè)老虎機(jī),每個(gè)老虎機(jī)會(huì)以一定概率吐出金幣,如何在n次的選擇中獲取最多的收益是探索與利用模型所解決的問(wèn)題.
在多臂老虎機(jī)問(wèn)題中,每個(gè)老虎機(jī)吐出金幣的概率未知.在進(jìn)行選擇前需要先對(duì)每個(gè)老虎機(jī)進(jìn)行一定次的選取,以估算每個(gè)老虎機(jī)吐出金幣的概率,之后根據(jù)不同老虎機(jī)吐出金幣的概率對(duì)老虎機(jī)進(jìn)行選擇.估算老虎機(jī)吐出金幣概率的過(guò)程稱為探索,根據(jù)概率進(jìn)行老虎機(jī)選取的過(guò)程稱為利用.
在變異調(diào)度問(wèn)題中,變異算子之間無(wú)相互干擾,每個(gè)變異算子可以類比為一臺(tái)老虎機(jī),變異調(diào)度問(wèn)題可以轉(zhuǎn)化為探索與利用問(wèn)題進(jìn)行解決.但與理想情況下的老虎機(jī)問(wèn)題不同,變異算子得到有效測(cè)試用例的概率是動(dòng)態(tài)變化的.因此,需要對(duì)利用階段變異算子發(fā)現(xiàn)有效測(cè)試用例的概率進(jìn)行動(dòng)態(tài)更新.
基于探索利用模型并結(jié)合第2章對(duì)變異算子變異效率的分析,可以得到變異調(diào)度優(yōu)化模型應(yīng)滿足的3條原則.
1)在利用階段動(dòng)態(tài)更新變異算子發(fā)現(xiàn)有效測(cè)試用例的概率.
2)變異算子整體發(fā)現(xiàn)有效測(cè)試用例概率最高.
3)在利用階段保持一定比例的探索.
在3.1節(jié)討論了變異算子優(yōu)化模型設(shè)計(jì)的3條原則.在本節(jié)中對(duì)變異算子調(diào)度優(yōu)化模型進(jìn)行設(shè)計(jì).首先給出變異算子優(yōu)化模型的優(yōu)化目標(biāo)函數(shù),如公式(1)所示.
(1)
公式(1)中X表示變異算子被選中的總次數(shù),Pi表示第i個(gè)變異算子生成有效測(cè)試用例的概率,xi表示第i個(gè)變異算子被選中的次數(shù).F(X)為優(yōu)化目標(biāo),求解該問(wèn)題的關(guān)鍵在于為變異算子i分配合理的選擇次數(shù),使得模糊測(cè)試器在有限次變異中發(fā)現(xiàn)更多的路徑.這類問(wèn)題最簡(jiǎn)單的做法是將所有選擇次數(shù)都分配給Pi最大的變異算子.但在變異算子優(yōu)化模型中Pi為估計(jì)值,該值在模型初期誤差較大,將所有的選擇次數(shù)都分配給Pi最大的變異算子將會(huì)引入較大的誤差.此外,Pi的值隨時(shí)間動(dòng)態(tài)變化,變異算子優(yōu)化模型需要具備對(duì)Pi進(jìn)行定期更新的能力.這就要求在利用階段每個(gè)變異算子都應(yīng)被分配到一定比例的選擇次數(shù).因此每個(gè)變異算子被選中的次數(shù)必須大于0.
在變異算子優(yōu)化模型中,將采取按比例分配的方式為每個(gè)變異算子分配執(zhí)行次數(shù),如公式(2)所示.公式中R表示Pi更新的輪次,C表示Pi在R次更新和R+1次更新之間,模糊測(cè)試器選擇變異算子的總次數(shù).
(2)
通過(guò)按比例分配執(zhí)行次數(shù)的方式,將每個(gè)變異算子的執(zhí)行次數(shù)與其生成有效測(cè)試用例的概率掛鉤,這樣可以將探索過(guò)程與利用過(guò)程相結(jié)合.在模型初始化階段給每一個(gè)變異算子賦予相同的概率,可以使得每個(gè)變異算子得到相同的執(zhí)行次數(shù),此時(shí)模型以探索為主.隨著模型不斷更新,不同變異算子之間的概率差異變大,每個(gè)模型分配到的執(zhí)行次數(shù)隨著產(chǎn)生分化,此時(shí)模型以利用為主.
(3)
(4)
在得到了Pi更新函數(shù)后,對(duì)Pi更新周期進(jìn)行研究.從圖4、圖5、圖6可以看出變異算子的變異效率在測(cè)試初期波動(dòng)較大,隨著模糊測(cè)試的不斷進(jìn)行,變異算子的變異效率趨于穩(wěn)定.因此,Pi在變異效率波動(dòng)較大時(shí)應(yīng)快速更新,在變異效率趨于穩(wěn)定時(shí)應(yīng)降低更新頻率,以降低模型更新帶來(lái)的資源開(kāi)銷.在模型中引入擾動(dòng)系數(shù)F描述每次更新Pi后模型波動(dòng)的大小,如公式(5)所示.在模型運(yùn)行過(guò)程中通過(guò)擾動(dòng)系數(shù)F對(duì)每輪測(cè)試的時(shí)長(zhǎng)進(jìn)行控制,擾動(dòng)系數(shù)越大模型波動(dòng)越劇烈,模型應(yīng)該提高Pi更新速度.
(5)
在3.2節(jié)中給出了模型的關(guān)鍵函數(shù),在本節(jié)中對(duì)模型的實(shí)現(xiàn)進(jìn)行介紹.變異調(diào)度優(yōu)化模型分為3個(gè)模塊:初始化模塊、探索與利用模塊、概率更新模塊.在初始化模塊中對(duì)模型中的數(shù)據(jù)結(jié)構(gòu)進(jìn)行優(yōu)化,為每個(gè)變異算子賦予初始概率.探索與利用模塊按照變異算子生成有效測(cè)試用例的概率為每個(gè)變異算子分配選擇次數(shù),調(diào)用模糊測(cè)試器中的變異操作對(duì)程序進(jìn)行測(cè)試并收集反饋信息.概率更新模塊根據(jù)探索與利用模塊收集到的反饋信息計(jì)算變異算子生成有效測(cè)試用例的概率和模型波動(dòng)系數(shù),模型運(yùn)行過(guò)程如算法1所示.
算法輸入為每輪測(cè)試選擇次數(shù)Limit,變異算子初始化概率Init[i],模型波動(dòng)系數(shù)F,變異算子個(gè)數(shù).算法輸出為變異算子發(fā)現(xiàn)的有效測(cè)試用例集.
算法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行判斷模糊測(cè)試是否接收到終止信號(hào),算法第7行判斷當(dāng)前更新輪次執(zhí)行次數(shù)是否小于當(dāng)前更新輪次限定的執(zhí)行次數(shù),小于則繼續(xù)執(zhí)行本輪次更新,大于則對(duì)變異算子發(fā)現(xiàn)有效測(cè)試用例的概率進(jìn)行更新.算法第8行調(diào)用模糊測(cè)試器中的Calculation_score函數(shù),該函數(shù)從測(cè)試用例集中選擇一個(gè)測(cè)試用例計(jì)算該測(cè)試用例需要進(jìn)行變異的總次數(shù).算法第10行按照公式2為每個(gè)變異算子分配選擇次數(shù).算法第11行調(diào)用模糊測(cè)試器中的fuzz函數(shù),該函數(shù)按照分配好的變異次數(shù)調(diào)用不同的變異算子對(duì)測(cè)試用例進(jìn)行變異,統(tǒng)計(jì)每個(gè)變異算子生成的有效測(cè)試用例數(shù)量,并將產(chǎn)生的有效測(cè)試用例加入到輸出集合中.
算法13到16行為模型更新概率更新模塊,算法13行按照公式(3)、公式(4)更新變異算子發(fā)現(xiàn)有效測(cè)試用例的概率.算法14行按照公式(5)計(jì)算模型的波動(dòng)系數(shù).
為說(shuō)明變異算子調(diào)度優(yōu)化模型對(duì)模糊測(cè)試器運(yùn)行效率的影響,從時(shí)間復(fù)雜度和空間復(fù)雜度兩個(gè)方面進(jìn)行分析.
首先對(duì)空間復(fù)雜度進(jìn)行分析,在變異調(diào)度優(yōu)化模型中共引入了4個(gè)n維數(shù)組(n為變異算子的數(shù)量)記錄變異算子的初始變異效率、被選中次數(shù)、有效變異次數(shù)等信息,產(chǎn)生的額外空間開(kāi)銷為O(n).
為了檢驗(yàn)變異算子調(diào)度優(yōu)化模型的效果,本文在開(kāi)源項(xiàng)目AFL基礎(chǔ)上實(shí)現(xiàn)了EE-POS-AFL,并與AFL進(jìn)行對(duì)比實(shí)驗(yàn).實(shí)驗(yàn)對(duì)模糊測(cè)試器路徑發(fā)現(xiàn)效率、Crash發(fā)現(xiàn)效率兩個(gè)指標(biāo)進(jìn)行對(duì)比.測(cè)試程序分為兩類,一類為真實(shí)目標(biāo)程序Libming、Tiff和Objdump;第2類為模糊測(cè)試器通用測(cè)試集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)硬盤(pán),操作系統(tǒng)為Unbuntu server 20.04.
Libming、Tiff和Objdump初始測(cè)試用例為選取自Testsuite測(cè)試集,Who、Base64、Md5sum和Uniq初始測(cè)試用例選取自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測(cè)試器覆蓋到的路徑數(shù)量,Crash表示模糊測(cè)試器生成的可以使程序奔潰的測(cè)試用例.
表3 實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)
為便于分析對(duì)表3的數(shù)據(jù)進(jìn)行處理生成效率對(duì)比表,如表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 效率對(duì)比表
從表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è)測(cè)試程序上EE-POS-AFL效果提升并不明顯.通過(guò)對(duì)初始測(cè)試用例的分析,發(fā)現(xiàn)Who、Md5sum的初始測(cè)試用例較小,經(jīng)過(guò)長(zhǎng)時(shí)間的模糊測(cè)試已經(jīng)無(wú)法生成有效的測(cè)試用例使得程序覆蓋到新的路徑.為更進(jìn)一步對(duì)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為例對(duì)圖像進(jìn)行分析.在對(duì)Who的測(cè)試中,前240分鐘AFL發(fā)現(xiàn)新路徑的效率要高于EE-POS-AFL,240分鐘到測(cè)試結(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的效率超過(guò)AFL.
對(duì)比實(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)化模型的有效性.
本文對(duì)模糊測(cè)試過(guò)程中分別對(duì)變異算子在不同類型程序上的效率、變異算子在同一程序不同時(shí)刻的變異效率進(jìn)行分析,找到了現(xiàn)有變異算子調(diào)度規(guī)則的不足,并針對(duì)不足提出了理想的變異算子調(diào)度規(guī)則應(yīng)滿足的3個(gè)特性.
本文以探索利用模型為基礎(chǔ),設(shè)計(jì)實(shí)現(xiàn)了變異算子調(diào)度優(yōu)化模型,并在開(kāi)源框架AFL上實(shí)現(xiàn)了該模型,對(duì)比實(shí)驗(yàn)表明該模型可以有效提高模糊測(cè)試器的變異效率.
下一步將會(huì)對(duì)基于語(yǔ)義變異的模糊測(cè)試工具進(jìn)行分析研究,對(duì)本文模型進(jìn)行擴(kuò)展.