基于種子變異潛力的模糊測(cè)試方法

王 喬，宋禮鵬

(中北大學(xué)大數(shù)據(jù)學(xué)院，太原 030051)

模糊測(cè)試是一種通過(guò)向目標(biāo)系統(tǒng)或軟件提供大量自動(dòng)生成的畸形數(shù)據(jù)來(lái)發(fā)現(xiàn)漏洞的軟件安全測(cè)試方法。模糊測(cè)試時(shí)，被測(cè)程序的代碼覆蓋率越高，發(fā)現(xiàn)漏洞的機(jī)會(huì)越大。自第一代模糊測(cè)試技術(shù)[1]出現(xiàn)以來(lái)，研究人員為提高代碼覆蓋率提出了覆蓋率導(dǎo)向策略，以覆蓋率信息指導(dǎo)測(cè)試進(jìn)行。在收集覆蓋率信息方面，目前主要有兩種策略：第一種是收集已測(cè)試種子的覆蓋率信息，如AFL(American fuzzy loop)對(duì)覆蓋新路徑的種子進(jìn)行變異[2]；AFLfast[3]以覆蓋不被頻繁覆蓋的路徑數(shù)量作為判斷種子變異潛力高低的條件；AFLgo以種子覆蓋路徑和目標(biāo)之間的距離來(lái)決定種子變異的優(yōu)先級(jí)[4]；FairFuzz則通過(guò)收集對(duì)分支的命中情況，選擇命中稀有分支的種子進(jìn)行變異[5]。第二種策略則是利用程序分析技術(shù)，如CollAFL[6]和Vuzzer[7]使用了靜態(tài)分析技術(shù)[8]來(lái)提取控制流和數(shù)據(jù)流情況，而Driller[9]則通過(guò)利用符號(hào)執(zhí)行[10]技術(shù)處理復(fù)雜約束。

覆蓋率導(dǎo)向策略的主要問(wèn)題是如何得到更精確的覆蓋率信息以及如何判斷種子變異潛力的高低。在選擇優(yōu)質(zhì)種子時(shí)，變異潛力的高低應(yīng)該是衡量種子優(yōu)質(zhì)程度的最主要標(biāo)準(zhǔn)，而諸如選擇覆蓋新分支的種子或選擇覆蓋稀有路徑的種子進(jìn)行下一輪變異等策略往往會(huì)導(dǎo)致變異結(jié)果不夠理想，這是因?yàn)榉N子效果好和種子變異潛力高并不等價(jià)，新分支可能在下次變異后不被覆蓋而失去價(jià)值，或者新分支可能導(dǎo)向一個(gè)錯(cuò)誤處理塊或程序終止塊，這種類型基本塊并不具有高的漏洞挖掘價(jià)值，因此覆蓋這種類型分支的種子價(jià)值較低、變異潛力也較低。

針對(duì)上述問(wèn)題，提出了一種基于種子變異潛力分析的模糊測(cè)試方法，首先提取程序控制流圖，以基本塊入口地址作為其標(biāo)記，考慮基本塊自身情況以及互相之間調(diào)用情況來(lái)賦予其權(quán)值。同時(shí)，在每一代種子運(yùn)行結(jié)束后，根據(jù)種子覆蓋路徑附近未被覆蓋的基本塊權(quán)值情況以及種子運(yùn)行時(shí)資源開銷情況來(lái)計(jì)算適應(yīng)度，從而篩選優(yōu)質(zhì)種子，投入下一代變異。本文策略能體現(xiàn)種子變異潛力主要由于以下兩個(gè)方面。

(1)以種子覆蓋路徑附近未被覆蓋的基本塊數(shù)量作為衡量標(biāo)準(zhǔn)之一，這樣得到的高適應(yīng)度種子通過(guò)變異到達(dá)未探索基本塊概率大，并且可能到達(dá)的未探索基本塊數(shù)量多。

(2)對(duì)基本塊進(jìn)行賦權(quán)操作，將變異潛力體現(xiàn)在底層基本塊上。對(duì)于兩個(gè)不同的未覆蓋基本塊，后繼塊多的基本塊往往意味著如果通過(guò)變異實(shí)現(xiàn)對(duì)該基本塊的覆蓋，則通過(guò)該基本塊到達(dá)新基本塊的可能情況越多并且可能性越大，因此覆蓋該基本塊的價(jià)值就越大。

圖1 PAFuzz結(jié)構(gòu)Fig.1 Structure of PAFuzz

1 基于種子變異潛力的模糊測(cè)試技術(shù)

模糊測(cè)試技術(shù)整體設(shè)計(jì)如圖1所示，首先在AFL的基礎(chǔ)上增加靜態(tài)分析模塊，提取該程序中不同基本塊信息和控制流圖，根據(jù)權(quán)值計(jì)算策略計(jì)算基本塊權(quán)值。其次對(duì)被測(cè)程序進(jìn)行插樁，追蹤種子在測(cè)試期間的路徑信息以及覆蓋情況，結(jié)合基本塊權(quán)值，根據(jù)適應(yīng)度函數(shù)計(jì)算種子適應(yīng)度，選擇適應(yīng)度大的部分種子投入變異池進(jìn)行變異，利用生成的新一代種子進(jìn)行下一輪測(cè)試，迭代上述過(guò)程，并基于以上策略設(shè)計(jì)了模糊測(cè)試工具PAFuzz。所用方案一方面在適應(yīng)度計(jì)算時(shí)加入路徑潛力信息，提高了適應(yīng)度函數(shù)的篩選效果，另一方面以入口地址標(biāo)記基本塊，以前驅(qū)和后繼兩個(gè)基本塊的入口地址組成的元組標(biāo)記分支，避免了傳統(tǒng)模糊測(cè)試策略標(biāo)記分支時(shí)不同分支間的碰撞問(wèn)題。

1.1 基本塊賦權(quán)

為了得到更有效更精確的路徑信息，在開始測(cè)試前先對(duì)被測(cè)程序進(jìn)行靜態(tài)分析，提取控制流和數(shù)據(jù)流信息，以便在后續(xù)測(cè)試過(guò)程中能更有效地計(jì)算種子的覆蓋情況。在靜態(tài)分析方面，選擇使用IDA python插件對(duì)被測(cè)程序進(jìn)行分析，提取函數(shù)基本塊的入口地址，出口地址和調(diào)用情況。

圖2 控制流圖Fig.2 Graph of Control flow

圖2為控制流圖，每個(gè)方塊代表一個(gè)基本塊，A代表主函數(shù)Main，箭頭表示調(diào)用關(guān)系。傳統(tǒng)的覆蓋率導(dǎo)向策略主要考慮種子的優(yōu)質(zhì)程度，例如，對(duì)于種子a，如果a覆蓋的路徑為(A、B、F、H)而分支{F->H}為新分支，則將a視為優(yōu)質(zhì)種子，分配更多變異機(jī)會(huì)。但一方面新分支{F->H}可能在變異之后不被覆蓋，另一方面H是一個(gè)程序終止塊，無(wú)后繼塊不具備任何變異潛力，因此這樣的篩選策略效果并不理想。權(quán)值計(jì)算方法綜合考慮兩個(gè)方面的信息。

(1)離根節(jié)點(diǎn)(孤立節(jié)點(diǎn))越近的基本塊權(quán)值參數(shù)越高，而每遠(yuǎn)一層，參數(shù)減半，在大多數(shù)情況下，處于越高層的基本塊往往意味著可能存在更多的子孫塊，例如基本塊B，對(duì)覆蓋B的種子進(jìn)行變異，可能到達(dá)的基本塊有E、F、H、I、C、G、K，而對(duì)覆蓋G的種子進(jìn)行變異則可能覆蓋的基本塊為K。雖然處于低層的基本塊F實(shí)際上比處于高層的C和D存在更多的子孫塊，但認(rèn)為通常情況下高層的基本塊存在更大變異潛力。由于同一基本塊可能存在于不同路徑中導(dǎo)致其在程序中所處層次不同，本文以距離根塊最短的路徑作為基本塊位置；

(2)對(duì)于每一個(gè)基本塊來(lái)說(shuō)，后繼塊的個(gè)數(shù)越多，則代表對(duì)覆蓋該基本塊的種子進(jìn)行變異，可能到達(dá)的不同基本塊越多，而無(wú)后繼塊的基本塊，除該塊本身可能存在的漏洞以外，無(wú)任何變異潛力，因?yàn)闊o(wú)論如何變異，只要到達(dá)這個(gè)基本塊，則程序運(yùn)行走到終點(diǎn)，這種基本塊的典型代表就是錯(cuò)誤處理塊，當(dāng)程序運(yùn)行滿足不了既定條件時(shí)，轉(zhuǎn)向錯(cuò)誤處理塊、報(bào)錯(cuò)并終止程序，考慮到基本塊本身可能存在的漏洞可能使其存在一定價(jià)值，在計(jì)算基本塊后繼時(shí)進(jìn)行了加1操作，可以有效提高適應(yīng)度函數(shù)的效果。

此外，還考慮到孤立塊以及不在根塊的子孫集合中的基本塊的情況，如圖2所示的L、M、O、N，對(duì)于孤立塊，則賦予其和根塊一樣的權(quán)值參數(shù)，而對(duì)于既是根塊A的子孫塊，又是孤立塊L、O的子孫塊，以其在主函數(shù)下的位置情況賦予其權(quán)值。

定義入口地址的集合為Ast，基本塊的集合為BBAst，程序入口地址為ADD，基本塊權(quán)值參數(shù)集合為WHbb.Ast，基本塊權(quán)值集合為FWbb.Ast，考慮到要計(jì)算基本塊處于的最高層情況，采用層次遍歷的算法計(jì)算基本塊權(quán)值，具體算法描述如算法1所示。

算法1

for bb in BBAst:

if bb.Ast==ADD and len(list(bb.preds()))==0:

WHbb.Ast=n

FWbb.Ast=WHbb.Ast*(len(list(bb.succs()))+1)

V.append(bb.Ast)

T.append(bb)

while len(T)！=0:

cb=T.popleft

for cbb in cb.succs():

if cbb.Ast not in V:

WHcbb.Ast=WHcb.Ast/2

FWcbb.Ast=WHcbb.Ast*(len(list(cbb.succs()))+1)

V.Add(cbb.Ast)

T.Add(cbb)

而對(duì)于孤立塊和非根塊子孫集合中的基本塊，則執(zhí)行算法2處理。

算法2

for bb in BBAst

if bb.Ast！=ADD and len(list(bb.preds()))==0:

WHbb.Ast=n

FWbb.Ast=WHbb.Ast*(len(list(bb.succs()))+1)

V.append(bb.Ast)

T.append(bb)

while len(T)！=0:

cb=T.popleft

for cbb in cb.succs():

if cbb.Ast not in V:

WHcbb.Ast=WHcb.Ast/2

FWcbb.Ast=WHcbb.Ast*(len(list(cbb.succs()))+1)

V.Add(cbb.Ast)

T.Add(cbb)

else:

pass

1.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)的計(jì)算是最能體現(xiàn)種子潛力的部分，對(duì)于模糊測(cè)試環(huán)來(lái)說(shuō)十分重要。一旦一個(gè)種子生成，那么該種子能否參與下一代變異取決于該種子的適應(yīng)度函數(shù)大小。采用二進(jìn)制插樁的方法，收集種子運(yùn)行過(guò)程中對(duì)代碼塊的覆蓋情況?？紤]圖2所示的例子，如果種子S1經(jīng)過(guò)的路徑為(A、B、F、H)，種子S2經(jīng)過(guò)的路徑為(A、C、G、K)，基礎(chǔ)權(quán)值參數(shù)為n，而測(cè)試過(guò)程中覆蓋過(guò)的基本塊為A、B、C、F、G、H、K，如果考慮種子覆蓋基本塊的權(quán)值，則S1權(quán)值和為(4+1.5+0.75+0.125)n=6.375n，S2權(quán)值和為(4+1+0.5+0.125)n=5.625n，因此S1覆蓋路徑比S2有更大變異潛力，但是對(duì)于這種策略，對(duì)于覆蓋較高權(quán)值基本塊的種子將不斷獲得變異機(jī)會(huì)，測(cè)試前期能夠?qū)崿F(xiàn)對(duì)附近分支多的種子分配更多變異機(jī)會(huì)，實(shí)現(xiàn)覆蓋率的快速提高，但是由于所有基本塊權(quán)值固定，覆蓋較高權(quán)值的基本塊無(wú)論其附近基本塊覆蓋情況如何，將不斷獲得變異機(jī)會(huì)，導(dǎo)致測(cè)試后期種子多樣性降低，不利于測(cè)試持續(xù)高效進(jìn)行。因此在該策略的基礎(chǔ)上提出收集種子覆蓋路徑附近基本塊情況，由其中未被覆蓋的基本塊權(quán)值和來(lái)體現(xiàn)路徑種子變異潛力，則S1覆蓋路徑周圍未探索基本塊為D、E、I，權(quán)值和為(1.5+0.25+0.25)n=2n，S2覆蓋路徑周圍未探索基本塊為D，權(quán)值和為1.5n，因此S1覆蓋路徑比S2有更大變異潛力。

除此之外，考慮到計(jì)算機(jī)資源開銷問(wèn)題，處理時(shí)間和種子文件大小也是影響適應(yīng)度的兩個(gè)因素，在處理效果相同時(shí)，處理時(shí)間較短和文件大小較小的種子往往意味著更高的處理效率和更小的資源開銷，因此對(duì)于一代種子S，將以下兩個(gè)參數(shù)加入到適應(yīng)度函數(shù)計(jì)算中。

Tseed=time(s)/avet(S)，s∈S

(1)

Lseed=length(s)/avel(S)，s∈S

(2)

式(1)表示種子s在處理時(shí)間上的優(yōu)質(zhì)程度，式(2)表示種子s在大小上的優(yōu)質(zhì)程度，其中avet(S)和avel(S)代表所有種子平均時(shí)間開銷和平均長(zhǎng)度。結(jié)合基本塊權(quán)值信息，可以計(jì)算得到種子的適應(yīng)度函數(shù)，如式(3)所示：

(3)

式(3)中:BB(s)代表s周圍未覆蓋的基本塊集合；FW(bb)為bb的權(quán)值；freq(bb)為bb出現(xiàn)在s周圍的次數(shù)，選擇每一代中適應(yīng)度最高的部分種子進(jìn)行下一代變異。

1.3 變異策略

AFL在種子變異方面主要采用了按位翻轉(zhuǎn)(將二進(jìn)制位1變成0或0變成1)、整數(shù)加減、特殊內(nèi)容替換、自動(dòng)生成或用戶提供的token插入和文件拼接五種策略，主要結(jié)合遺傳算法[11]實(shí)現(xiàn)種子變異，主要策略如下。

1.3.1 交叉變異

如圖3所示，從優(yōu)質(zhì)種子中隨機(jī)選取兩個(gè)，對(duì)隨機(jī)選擇的一段比特位進(jìn)行交換，得到兩個(gè)子代種子。

圖3 交叉變異Fig.3 Cross variation

1.3.2 替換變異

如圖4所示，對(duì)優(yōu)質(zhì)種子的隨機(jī)選擇的一段比特位，使用特殊數(shù)據(jù)或隨機(jī)數(shù)據(jù)進(jìn)行替換。

圖4 替換變異Fig.4 Replacement variation

1.3.3 大規(guī)模突變

適應(yīng)度函數(shù)篩選優(yōu)質(zhì)種子不可避免會(huì)導(dǎo)致種子池在后期多樣性降低，無(wú)論交叉還是替換操作都不能再給種子質(zhì)量帶來(lái)有效提高，因此當(dāng)程序在一定輪數(shù)之后未發(fā)現(xiàn)新塊，則選擇執(zhí)行大規(guī)模突變，提升種子池多樣性并一定程度恢復(fù)種子探索新路徑能力。

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

為了測(cè)試所用模糊測(cè)試方案的效果，將本文方案在LAVA-M數(shù)據(jù)集[12]和真實(shí)Linux程序上進(jìn)行了測(cè)試，實(shí)驗(yàn)結(jié)果與目前廣泛使用的模糊測(cè)試工具AFL(2.52b)在漏洞發(fā)現(xiàn)能力、覆蓋率、漏洞發(fā)現(xiàn)速度和輸入數(shù)據(jù)總大小方面進(jìn)行了對(duì)比，測(cè)試環(huán)境為Ubuntu系統(tǒng)，并為其配置了4-core的CPU和4GB內(nèi)存，測(cè)試初始種子集相同。

2.1 漏洞挖掘能力

發(fā)現(xiàn)漏洞的能力是模糊測(cè)試工具優(yōu)劣的集中體現(xiàn)，因此比較了24 h內(nèi)發(fā)現(xiàn)漏洞情況，AFL使用QEMU對(duì)二進(jìn)制程序進(jìn)行插樁，被測(cè)程序選擇LAVA-M數(shù)據(jù)集，漏洞發(fā)現(xiàn)情況結(jié)果如表1所示。同時(shí)，將本文方案和AFL在真實(shí)Linux應(yīng)用進(jìn)行了對(duì)比測(cè)試，結(jié)果如表2所示。

表1 LAVA-M上漏洞發(fā)現(xiàn)能力對(duì)比Table 1 Comparison of vulnerability discovery capabilities on LAVA-M

表2 真實(shí)程序上漏洞發(fā)現(xiàn)能力對(duì)比Table 2 Comparison of vulnerability detection capabilities on real programs

由表1、表2可知，在變異策略基本相同的情況下，基于本文策略的模糊測(cè)試工具在漏洞挖掘能力方面相比于以是否發(fā)現(xiàn)新分支作為種子優(yōu)劣標(biāo)準(zhǔn)AFL有明顯提高，充分說(shuō)明本文策略篩選出的種子變異后測(cè)試效果優(yōu)于AFL。

2.2 覆蓋率情況

代碼覆蓋率情況是衡量技術(shù)性能的重要指標(biāo)，一方面能反映篩選策略的優(yōu)劣程度，另一方面體現(xiàn)變異策略的效率，在對(duì)上述程序進(jìn)行測(cè)試時(shí)，收集并統(tǒng)計(jì)了本文方案和AFL在24 h內(nèi)覆蓋的總路徑情況，結(jié)果如表3所示。

表3 覆蓋率情況對(duì)比Table 3 Comparison of coverage

由表3可知，被測(cè)程序的路徑覆蓋率平均提高了14.73%，這是由于所篩選策略將種子變異后可能到達(dá)的新基本塊情況作為衡量標(biāo)準(zhǔn)，變異后種子覆蓋新路徑的可能性比AFL更大，在變異策略基本相同的情況下，所篩選策略得到的覆蓋率情況明顯優(yōu)于AFL。

2.3 輸入數(shù)據(jù)

對(duì)24 h內(nèi)測(cè)試過(guò)的種子總大小進(jìn)行統(tǒng)計(jì)，結(jié)果如表4所示。分析結(jié)果可知，相比于AFL，PAFuzz將種子大小和運(yùn)行速度作為衡量標(biāo)準(zhǔn)之一，整個(gè)測(cè)試過(guò)程中生成的測(cè)試用例空間開銷更小，效率更高。

表4 測(cè)試用例總大小對(duì)比Table 4 Comparison of test case total size

2.4 漏洞發(fā)現(xiàn)速度

為了對(duì)比整個(gè)實(shí)驗(yàn)過(guò)程中AFL和PAFuzz在24 h內(nèi)各個(gè)時(shí)間段漏洞發(fā)現(xiàn)情況以及整體漏洞發(fā)現(xiàn)趨勢(shì)，以2 h為間隔對(duì)兩個(gè)方案漏洞發(fā)現(xiàn)情況進(jìn)行采樣，對(duì)比了兩個(gè)方案的漏洞發(fā)現(xiàn)速度，對(duì)比結(jié)果如圖5所示。分析圖5可知，由于本文方案篩選出的優(yōu)質(zhì)種子執(zhí)行速度快變異潛力大，變異后可能覆蓋的新路徑多，因此本文方案能夠快速提升代碼覆蓋率并在測(cè)試前期觸發(fā)更多漏洞。同時(shí)，AFL由于使用簡(jiǎn)單的遺傳算法，導(dǎo)致種子在后期的差異性變小,替換變異和交叉變異的效果大幅度減弱，發(fā)現(xiàn)漏洞能力嚴(yán)重下滑，而本文方案則有效避免了這一情況，同時(shí)由于存在大規(guī)模突變機(jī)制，可以有效提高測(cè)試后期種子多樣性，因此在后期發(fā)現(xiàn)漏洞的能力也優(yōu)于AFL，更加證明本文策略的有效性。

圖5 漏洞發(fā)現(xiàn)情況對(duì)比Fig.5 Comparison of vulnerability discovery

3 結(jié)論

針對(duì)傳統(tǒng)模糊測(cè)試在種子篩選時(shí)數(shù)據(jù)粗糙、算法簡(jiǎn)單、無(wú)法真正分辨種子變異潛力的問(wèn)題，提出一種改進(jìn)方案，主要是結(jié)合基本塊的位置和后繼基本塊的數(shù)量分析基本塊的變異潛力，追蹤種子覆蓋路徑附近未被覆蓋的基本塊情況，綜合種子的處理速度和大小，給出其適應(yīng)度函數(shù)值。實(shí)驗(yàn)表明在相同時(shí)間內(nèi)，本文方法在漏洞發(fā)現(xiàn)數(shù)量、漏洞發(fā)現(xiàn)速度和代碼覆蓋率方面都有所提高，同時(shí)還避免了覆蓋率導(dǎo)向技術(shù)中存在的碰撞問(wèn)題。

在下一步的研究中，將結(jié)合諸如污點(diǎn)分析[13]、符號(hào)執(zhí)行等技術(shù)對(duì)變異策略進(jìn)行進(jìn)一步優(yōu)化以應(yīng)對(duì)程序中的復(fù)雜約束，覆蓋程序深處代碼塊。