基于符號(hào)執(zhí)行與模糊測(cè)試的混合測(cè)試方法*

謝肖飛,李曉紅,陳 翔,孟國(guó)柱,劉 楊

1(天津市先進(jìn)網(wǎng)絡(luò)重點(diǎn)實(shí)驗(yàn)室(天津大學(xué)),天津 300050)

2(南通大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,江蘇 南通 226019)

3(信息安全國(guó)家重點(diǎn)研究室(中國(guó)科學(xué)院 信息工程研究所),北京 100093)

4(School of Computer Science and Engineering,Nanyang Technological University 639798,Singapore)

1 引 言

隨著信息技術(shù)的發(fā)展,軟件已經(jīng)滲透到現(xiàn)代社會(huì)的方方面面,而由于開(kāi)發(fā)不當(dāng)引入的軟件漏洞也日益增多.據(jù)統(tǒng)計(jì),最近5 年內(nèi)軟件漏洞數(shù)增加了38%,而僅在2016 年～2017 年間就增加了14%[1].軟件測(cè)試是檢測(cè)軟件漏洞的一種主要方法,當(dāng)前工業(yè)界的主流方法還是通過(guò)手工設(shè)計(jì)測(cè)試用例來(lái)提高軟件產(chǎn)品的質(zhì)量,然而,手工生成測(cè)試用例通常效率較低、成本高昂并且容易出錯(cuò)[2].每年成千上億的資金被投入到軟件行業(yè),其中軟件測(cè)試一般需要占據(jù)50%以上的成本預(yù)算[3].

軟件漏洞可以被看作是隱藏在某個(gè)條件下的錯(cuò)誤語(yǔ)句,通過(guò)提升測(cè)試用例的代碼覆蓋率可以提高軟件漏洞的檢測(cè)概率.軟件測(cè)試致力于為待測(cè)程序生成高代碼覆蓋率(例如語(yǔ)句覆蓋、分支覆蓋等)的測(cè)試用例以發(fā)現(xiàn)軟件漏洞,當(dāng)被測(cè)程序配套的測(cè)試用例覆蓋率高且均執(zhí)行通過(guò)時(shí),則認(rèn)為該程序在一定程度上具有高可靠性.

基于覆蓋率引導(dǎo)的模糊測(cè)試(coverage-guided fuzz testing)[4-7](下文中所提到的模糊測(cè)試均指基于覆蓋引導(dǎo)的模糊測(cè)試)與符號(hào)執(zhí)行(symbolic execution)[8-12]是目前兩種被廣泛研究和使用的測(cè)試技術(shù).給定初始測(cè)試用例,模糊測(cè)試(例如AFL 工具)動(dòng)態(tài)地執(zhí)行目標(biāo)程序,并基于覆蓋率選擇已有測(cè)試用例進(jìn)行隨機(jī)變異(mutation),從而生成新的測(cè)試用例.常見(jiàn)的變異操作包括字節(jié)翻轉(zhuǎn)等.該過(guò)程將不斷被重復(fù),直到不能覆蓋到更多的分支或語(yǔ)句為止.在動(dòng)態(tài)執(zhí)行測(cè)試用例時(shí),如果檢測(cè)到異常崩潰(crash),則認(rèn)為發(fā)現(xiàn)了漏洞.由于模糊測(cè)試采取隨機(jī)變異,因此難以生成可以覆蓋到復(fù)雜條件的測(cè)試用例.例如,圖1(a)中,若通過(guò)隨機(jī)變異的方法,則需要最多變換232次才能覆蓋到條件input=123456789.圖1(b)所示的模糊測(cè)試覆蓋圖表示模糊測(cè)試難以檢測(cè)到漏洞error1(即左側(cè)紅色節(jié)點(diǎn));而對(duì)于處于較深位置的漏洞error2(即右側(cè)紅色節(jié)點(diǎn)),模糊測(cè)試由于采用動(dòng)態(tài)執(zhí)行的方法,因此容易檢測(cè)到漏洞error2.

符號(hào)執(zhí)行通過(guò)符號(hào)化執(zhí)行程序來(lái)收集約束條件,并借助約束求解器[13-15]為每條路徑生成測(cè)試用例.例如,符號(hào)執(zhí)行可以很容易生成覆蓋input=123456789 分支并觸發(fā)漏洞error1 的測(cè)試用例.但其缺點(diǎn)是,由于需要符號(hào)化地執(zhí)行程序,因此在遇到循環(huán),尤其是循環(huán)次數(shù)依賴于輸入的循環(huán)(例如圖1(a)中的while 循環(huán))時(shí),循環(huán)的執(zhí)行次數(shù)無(wú)法確定,此時(shí),符號(hào)執(zhí)行會(huì)陷入不停的循環(huán)展開(kāi)中,從而影響到測(cè)試用例生成的效率.并且,當(dāng)遍歷到程序很深的位置時(shí),約束條件也會(huì)變得更為復(fù)雜,使得約束求解器很難進(jìn)行求解.例如,在圖1(b)中,由于循環(huán)或者其他函數(shù)的存在,造成符號(hào)執(zhí)行很難覆蓋到較深的位置,從而難以檢測(cè)到漏洞error2.

Fig.1 Code coverage comparison圖1 代碼覆蓋率比較

當(dāng)前已有多個(gè)工作[2,17-21]提出了混合測(cè)試的方法,從而可以更高效地生成測(cè)試用例.例如,DART[16]、SAGE[17]、SYMFUZZ[18]以及HCT[2]將隨機(jī)測(cè)試與符號(hào)執(zhí)行一起使用,但這些方法的隨機(jī)測(cè)試中并未考慮程序的覆蓋信息.而且,DART、SAGE 以及SYMFUZZ 都屬于單向結(jié)合.具體來(lái)說(shuō),DART 與SAGE 利用隨機(jī)測(cè)試提高符號(hào)執(zhí)行,而SYMFUZZ 利用符號(hào)執(zhí)行輔助隨機(jī)測(cè)試.Munch[19]將符號(hào)執(zhí)行與模糊測(cè)試相結(jié)合,但其目的在于提高函數(shù)覆蓋率,Driller[20]將混合執(zhí)行與模糊測(cè)試相結(jié)合,其效果依賴于混合執(zhí)行所選取的測(cè)試用例.不同于上述方法,本文通過(guò)分析模糊測(cè)試與符號(hào)執(zhí)行的優(yōu)缺點(diǎn),以分支覆蓋信息為引導(dǎo),提出了一種符合執(zhí)行與模糊測(cè)試多次交互與結(jié)合的混合測(cè)試方法.

模糊測(cè)試和符號(hào)執(zhí)行各有優(yōu)缺點(diǎn),通過(guò)結(jié)合雙方優(yōu)點(diǎn)可以在一定程度上彌補(bǔ)不足,從而獲得更高的覆蓋率.直觀上,程序的運(yùn)行空間可以看作是一棵執(zhí)行樹(shù),模糊測(cè)試通過(guò)隨機(jī)變異的方法可以覆蓋執(zhí)行樹(shù)上的多條路徑,并且每條路徑都可以執(zhí)行到較深的位置;而由于一些復(fù)雜的條件分支,使得執(zhí)行樹(shù)中較淺的位置無(wú)法被突破.而符號(hào)執(zhí)行可以突破執(zhí)行樹(shù)內(nèi)較淺位置的復(fù)雜條件分支,但卻難以深入到較深的位置.因此,本文的出發(fā)點(diǎn)是通過(guò)模糊測(cè)試探索程序執(zhí)行樹(shù)中的多個(gè)易覆蓋的以及較深位置的分支,通過(guò)符號(hào)執(zhí)行來(lái)系統(tǒng)地搜索執(zhí)行樹(shù),以盡可能地覆蓋模糊測(cè)試未覆蓋到的分支.例如,通過(guò)結(jié)合模糊測(cè)試和符號(hào)執(zhí)行,本文所提方法可以覆蓋圖1(a)中的所有分支(如圖1(c)所示).

具體來(lái)說(shuō),本文提出了一種將模糊測(cè)試(基于american fuzzy lop[4],簡(jiǎn)稱AFL)與符號(hào)執(zhí)行(基于KLEE[9])相結(jié)合的方法,并開(kāi)發(fā)出相應(yīng)的工具Afleer.其中,AFL 進(jìn)行標(biāo)準(zhǔn)的模糊測(cè)試,KLEE 依據(jù)AFL 當(dāng)前的覆蓋信息調(diào)整搜索策略,當(dāng)遇到未覆蓋的分支時(shí)生成測(cè)試用例并發(fā)送給AFL.AFL 通過(guò)讀取新的測(cè)試用例進(jìn)而探索該分支下更多的分支.在實(shí)證研究中,將Afleer 工具應(yīng)用到標(biāo)準(zhǔn)程序集LAVA-M[21]以及1 個(gè)實(shí)際項(xiàng)目oSIP[22]上,以分析本方法的代碼覆蓋能力和漏洞檢測(cè)能力.實(shí)證研究結(jié)果表明:與AFL 相比,在標(biāo)準(zhǔn)程序集上,Afleer 可以檢測(cè)到755 個(gè)漏洞而AFL 僅能發(fā)現(xiàn)1 個(gè).并且,在分支覆蓋與路徑覆蓋上都有不同程度的提升.其中,LAVA-M 在最好情況下(項(xiàng)目who 中),分支覆蓋率提升了35%,路徑覆蓋率提升了492%.在實(shí)際項(xiàng)目oSIP 中,分支覆蓋率提升了2.4 倍,路徑覆蓋率提升了6.1 倍.除此之外,在oSIP 中,Afleer 發(fā)現(xiàn)了一個(gè)新漏洞并已被提交.上述實(shí)證研究結(jié)果證明了Afleer 的有效性.

本文的主要貢獻(xiàn)可總結(jié)如下.

·本文提出了一種將模糊測(cè)試與符號(hào)執(zhí)行相結(jié)合的新方法,即通過(guò)模糊測(cè)試的覆蓋率信息來(lái)引導(dǎo)符號(hào)執(zhí)行的搜索,從而生成具有更高代碼覆蓋率的測(cè)試用例,并有助于找到更多的軟件漏洞.

·基于該方法,實(shí)現(xiàn)了工具Afleer,并設(shè)計(jì)了相關(guān)實(shí)驗(yàn),在標(biāo)準(zhǔn)程序集與實(shí)際項(xiàng)目上證明了本方法的有效性.

·本文深入分析了影響代碼覆蓋率的因素,在此基礎(chǔ)上討論了符號(hào)執(zhí)行和模糊測(cè)試的優(yōu)缺點(diǎn),為之后兩種技術(shù)的研究以及結(jié)合提供了指導(dǎo)性建議.

本文第2 節(jié)介紹研究背景.第3 節(jié)介紹所提方法的框架和具體實(shí)現(xiàn)細(xì)節(jié).第4 節(jié)介紹本文的實(shí)證研究并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析與討論.第5 節(jié)對(duì)相關(guān)工作進(jìn)行總結(jié),并與本文所提方法進(jìn)行比較.最后進(jìn)行總結(jié)并對(duì)未來(lái)工作加以展望.

2 研究背景和研究動(dòng)機(jī)

2.1 模糊測(cè)試與AFL工具

基于覆蓋率引導(dǎo)的模糊測(cè)試是一種高效的自動(dòng)化測(cè)試技術(shù),它通過(guò)隨機(jī)變異的方式來(lái)生成大量測(cè)試用例,依靠覆蓋信息來(lái)決定新生成的測(cè)試用例是否應(yīng)該被保留.其中,American Fuzzy Lop(AFL)[4]工具是當(dāng)前最先進(jìn)和最流行的模糊測(cè)試工具之一,并已在大量實(shí)際項(xiàng)目中檢測(cè)到了新的漏洞.

AFL 在編譯過(guò)程中對(duì)程序進(jìn)行插樁來(lái)記錄程序的覆蓋信息,并使用遺傳算法來(lái)變異已有測(cè)試用例以生成最有可能探索到新的程序狀態(tài)的測(cè)試用例.具體來(lái)說(shuō),AFL 在編譯過(guò)程中為待測(cè)程序的每個(gè)基本塊(basic block)插入一個(gè)編號(hào),當(dāng)一個(gè)條件分支(prev,cur)被覆蓋一次時(shí),其執(zhí)行次數(shù)加1(即trace_bits[h(prev,cur)]++).其中,prev和cur分別表示先前基本塊與當(dāng)前基本塊的編號(hào),trace_bits是記錄當(dāng)前測(cè)試用例覆蓋信息的數(shù)組,索引值表示分支的哈希值.這樣,在執(zhí)行一個(gè)測(cè)試用例后,trace_bits記錄了程序中每個(gè)分支的覆蓋次數(shù).同時(shí),在執(zhí)行多個(gè)測(cè)試用例后,AFL 也會(huì)記錄全局覆蓋信息數(shù)組virgin_bits,它表示已執(zhí)行的所有測(cè)試用例的覆蓋信息.通過(guò)比較trace_bits與virgin_bits,可以判斷出當(dāng)前測(cè)試用例是否可以覆蓋到新?tīng)顟B(tài),從而決定是否保留該測(cè)試用例.

AFL 通過(guò)以下變異操作來(lái)對(duì)一個(gè)已有測(cè)試用例進(jìn)行變異,對(duì)于變異后的新測(cè)試用例,如果其可以覆蓋到新?tīng)顟B(tài),則保留該測(cè)試用例.

·變異操作1:針對(duì)位或者字節(jié)進(jìn)行翻轉(zhuǎn).

·變異操作2:以單字節(jié)、雙字節(jié)或者四字節(jié)為單位進(jìn)行加減操作.

·變異操作3:刪除、復(fù)制、重寫或者插入新的字節(jié)塊.

·變異操作4:兩個(gè)測(cè)試用例隨機(jī)選取位置并進(jìn)行拼接.

2.2 符號(hào)執(zhí)行與KLEE工具

動(dòng)態(tài)執(zhí)行時(shí),一個(gè)具體測(cè)試用例對(duì)應(yīng)于程序控制流圖(control flow graph,簡(jiǎn)稱CFG)中的一條路徑.因此,模糊測(cè)試通常只能執(zhí)行到程序的部分行為(即under-approximation).

與此相反,符號(hào)執(zhí)行的輸入不是一個(gè)具體測(cè)試用例,而是一個(gè)符號(hào)值,這樣可以模擬執(zhí)行程序的多條路徑.符號(hào)執(zhí)行在執(zhí)行過(guò)程中為每條路徑記錄一個(gè)路徑條件(path condition)φ,當(dāng)遇到一個(gè)分支條件時(shí),該分支條件ρ分叉(fork)為兩條路徑,其路徑條件被更新為φ^ρ以及φ^﹁ρ.通過(guò)約束求解器[14,16]可以檢查路徑條件是否能夠進(jìn)行求解,如果無(wú)法求解,則該條路徑是不可行的(infeasible);否則,沿該分支將繼續(xù)往下執(zhí)行.當(dāng)遇到循環(huán)時(shí),其多次迭代可以看作是多個(gè)條件分支,在循環(huán)的每次迭代中都將進(jìn)行分叉.KLEE 工具[9]是基于LLVM[23]實(shí)現(xiàn)的符號(hào)執(zhí)行工具.被測(cè)程序被編譯為L(zhǎng)LVM 位碼,KLEE 直接解釋指令集并將其轉(zhuǎn)為相應(yīng)的約束條件.

2.3 優(yōu)缺點(diǎn)分析及研究動(dòng)機(jī)

正如引言所述,模糊測(cè)試的優(yōu)點(diǎn)在于動(dòng)態(tài)執(zhí)行,因此執(zhí)行一個(gè)測(cè)試用例,其可以覆蓋到較深的位置;而缺點(diǎn)是當(dāng)遇到復(fù)雜的分支條件時(shí),則很難通過(guò)隨機(jī)變異的方法來(lái)生成滿足該條件的測(cè)試用例.符號(hào)執(zhí)行的優(yōu)點(diǎn)是其可以突破復(fù)雜分支條件,由于維護(hù)了路徑條件,因此通過(guò)約束求解器可以生成滿足該條件的測(cè)試用例.而缺點(diǎn)是由于所有值都需要進(jìn)行符號(hào)化,因此,當(dāng)遇到依賴符號(hào)輸入的循環(huán)或者遞歸時(shí),其無(wú)法確定迭代次數(shù),從而陷入到循環(huán)展開(kāi)中.此外,隨著路徑深度的增加,路徑條件也會(huì)越來(lái)越復(fù)雜,其對(duì)于約束求解器也會(huì)構(gòu)成很大的挑戰(zhàn).

綜上所述,如果將程序看作執(zhí)行樹(shù),一個(gè)分支能否被覆蓋,主要受到兩個(gè)因素的影響:分支所在路徑的深度以及分支所在路徑的路徑條件復(fù)雜度.該因素主要受到兩種方法的本質(zhì)特征所決定.從概率上來(lái)講,符號(hào)執(zhí)行屬于白盒測(cè)試技術(shù),其符號(hào)化地遍歷程序的整個(gè)執(zhí)行樹(shù).當(dāng)分支所在路徑的深度較深時(shí),符號(hào)執(zhí)行遍歷到該分支的概率也會(huì)降低,并且約束求解的難度也會(huì)提高,符號(hào)執(zhí)行此時(shí)會(huì)比較低效.而模糊測(cè)試屬于灰盒測(cè)試技術(shù),其本質(zhì)是在程序的輸入集內(nèi)進(jìn)行隨機(jī)枚舉,此時(shí),基于執(zhí)行樹(shù)上的路徑,把輸入集劃分為不同的區(qū)域(即不同的輸入會(huì)執(zhí)行不同的路徑).路徑條件復(fù)雜可以理解為該路徑可執(zhí)行的輸入集較小,因此模糊測(cè)試變異到的概率也會(huì)變小,此時(shí),模糊測(cè)試會(huì)比較低效.

如圖2 所示,本文將求解難度分為4 類:當(dāng)該分支所在位置較淺并且路徑條件復(fù)雜度較低時(shí),符號(hào)執(zhí)行和模糊測(cè)試都能快速生成相應(yīng)的測(cè)試用例;當(dāng)該路徑條件復(fù)雜度較高但是該分支位置較淺時(shí),符號(hào)執(zhí)行更適合為其生成測(cè)試用例;當(dāng)路徑條件復(fù)雜度較低但是分支位置較深時(shí),模糊測(cè)試更適合為其生成測(cè)試用例.對(duì)于分支位置較深并且路徑復(fù)雜度較高的情況(如圖2 中的藍(lán)色方塊所示),此時(shí)兩種方法都會(huì)遇到瓶頸.本文從這點(diǎn)出發(fā),結(jié)合了這兩種方法的優(yōu)點(diǎn),從而可以覆蓋到更深、更難的分支條件.

Fig.2 Analysis of branch coverage on program execution tree圖2 程序執(zhí)行樹(shù)中的分支覆蓋分析

3 主要方法

3.1 方法框架

本文所提出的Afleer 方法的框架如圖3 所示,該方法主要包括兩個(gè)階段:左邊是編譯階段,右邊是運(yùn)行階段.給定一個(gè)程序,首先我們將其編譯為插樁后的LLVM 位碼以及插樁后的可執(zhí)行文件,其中,LLVM 位碼用于符號(hào)執(zhí)行,而可執(zhí)行文件用于模糊測(cè)試.需要注意的是,LLVM 位碼和可執(zhí)行文件必須一致,亦即在優(yōu)化后,最終的控制流圖相同并且插樁信息保持一致.在運(yùn)行階段,Afleer 分別運(yùn)行模糊測(cè)試以及符號(hào)執(zhí)行,其中模糊測(cè)試不斷地生成測(cè)試用例并更新覆蓋信息(例如,AFL 中的virgin_bits),該信息反映了哪些分支已經(jīng)被覆蓋到或者尚未被覆蓋到.而在另一端,符號(hào)執(zhí)行系統(tǒng)性地搜索程序執(zhí)行樹(shù),當(dāng)發(fā)現(xiàn)某個(gè)分支(p,c)未被覆蓋時(shí),則生成相應(yīng)的測(cè)試用例T并加入到測(cè)試用例集中.模糊測(cè)試監(jiān)控新增測(cè)試用例集,當(dāng)有新的測(cè)試用例T時(shí),將其讀入并加入到自己的測(cè)試用例隊(duì)列中,此時(shí),(p,c)已被覆蓋.基于新的測(cè)試用例,模糊測(cè)試可以繼續(xù)探索(p,c)后面的分支.通過(guò)不斷的迭代,最終Afleer 可以覆蓋到更多的分支.下面,我們將詳細(xì)介紹Afleer 方法的實(shí)現(xiàn)細(xì)節(jié).

Fig.3 Overview of Afleer圖3 Afleer 的主要框架

3.2 代碼插樁處理

插樁一致性.符號(hào)執(zhí)行與模糊測(cè)試結(jié)合的前提是其雙方版本一致.具體來(lái)說(shuō),在源文件以及可執(zhí)行文件這兩個(gè)版本中,需要保證控制流圖以及每個(gè)基本塊的插樁編號(hào)相同,使得雙方在覆蓋信息上保持一致.

例如,KLEE 的輸入是LLVM 位碼,而AFL 可以基于LLVM 進(jìn)行插樁,為了保證插樁信息一致,該項(xiàng)工作修改了編譯工具Whole Program LLVM[24](簡(jiǎn)寫為WLLVM).WLLVM 是一個(gè)可以為項(xiàng)目生成LLVM 位碼以及可執(zhí)行文件的工具,但是,由于WLLVM 生成LLVM 位碼與可執(zhí)行代碼是分兩次編譯的,從而導(dǎo)致同一個(gè)基本塊在兩次編譯中隨機(jī)生成兩個(gè)不同的編號(hào).最終,模糊測(cè)試與符號(hào)執(zhí)行無(wú)法同步覆蓋信息.修改該工具如下:首先插樁并編譯為L(zhǎng)LVM位碼,之后再將位碼編譯為目標(biāo)代碼(object文件),最終將目標(biāo)文件鏈接為可執(zhí)行文件.修改后的WLLVM 中僅插樁一次,從而保證了LLVM 位碼與可執(zhí)行代碼的插樁信息保持一致.

插樁預(yù)處理.經(jīng)過(guò)模糊測(cè)試插樁后,每個(gè)基本塊都加入了統(tǒng)計(jì)覆蓋信息的代碼.例如,在AFL 插樁后會(huì)引入兩個(gè)外部全局變量,并且LLVM 位碼中的每個(gè)基本塊會(huì)多出8 條計(jì)算指令.而符號(hào)執(zhí)行不需要這些動(dòng)態(tài)計(jì)算覆蓋信息,因此,這些指令會(huì)極大地影響符號(hào)執(zhí)行的執(zhí)行效率.我們給出算法來(lái)獲得插樁信息中的編號(hào),并刪除其他無(wú)用指令.

算法1 給出了針對(duì)AFL 插樁的預(yù)處理算法,其輸入是LLVM 的模塊M.在第1 行刪除AFL 引入的外部全局變量(即afl_prev_loc 與afl_area_ptr),由于這兩個(gè)全局變量都是外部變量,會(huì)造成符號(hào)執(zhí)行運(yùn)行時(shí)無(wú)法找到變量而報(bào)錯(cuò),第1 行將其刪除.其次,在模塊M中的每一個(gè)基本塊中,刪除AFL 插樁的額外代碼.對(duì)于每個(gè)基本塊B,首先解析插樁指令,并得到隨機(jī)插樁編號(hào)ID(第3 行),然后刪除插樁指令(第4 行),并插入一條指令(第5 行)以保存ID 的值.針對(duì)KLEE,我們選擇加入一條KLEE 未支持的指令A(yù)tmoicRMW 來(lái)保存ID.因此,在經(jīng)過(guò)預(yù)處理后,在每個(gè)基本塊中8 條指令將減少為1 條.

算法1.插樁預(yù)處理.

Input:M:LLVM 模塊(Module).

1刪除M中模糊測(cè)試引入的全局變量;

2

3ID=從插樁代碼中解析基本塊的編號(hào);4刪除所有插樁的代碼;

5插入一條指令以保存ID;

6end

3.3 Afleer模糊測(cè)試模塊

算法2 展示了Afleer 中模糊測(cè)試模塊.Afleer 主要擴(kuò)展了AFL 的算法,輸入為已有測(cè)試用例Seeds、待測(cè)程序P以及來(lái)自符號(hào)執(zhí)行的新增測(cè)試用例集SE_Seeds.輸出是生成的所有測(cè)試用例,其中,包含可以觸發(fā)漏洞的輸入.AFL 依次遍歷Seeds中的每一個(gè)測(cè)試用例seed.首先對(duì)其進(jìn)行變異,得到新的測(cè)試用例newseed(第2 行).注意,一個(gè)測(cè)試用例可以通過(guò)多種變異操作得到多個(gè)測(cè)試用例,不失一般性,這里假設(shè)其結(jié)果為newseed.然后程序P執(zhí)行新的測(cè)試用例newseed(第3 行),得到覆蓋信息以及運(yùn)行結(jié)果.如果運(yùn)行結(jié)果發(fā)現(xiàn)異常,則找到了觸發(fā)漏洞的測(cè)試用例(第4 行).如果該測(cè)試用例使得新的分支被覆蓋(第7 行),則將其加入測(cè)試用例集合(第8 行)并更新覆蓋信息(第9 行).在完成一個(gè)測(cè)試用例的處理后,將檢查是否符號(hào)執(zhí)行探索到新的未覆蓋分支,如果發(fā)現(xiàn)(第11行)新的測(cè)試用例,則將其加入Seeds的最前列,并將SE_Seeds清空.這樣,在符號(hào)執(zhí)行發(fā)現(xiàn)新的測(cè)試用例后,模糊測(cè)試將對(duì)其進(jìn)行變異,以探索該分支下更深位置的分支.

算法2.Afleer 模糊測(cè)試模塊.

Input:Seeds:己有測(cè)試用例,P:待測(cè)程序,SE Seeds:新增測(cè)試用例;

Output:測(cè)試用例.

3.4 Afleer符號(hào)執(zhí)行模塊

算法3 展示了Afleer 中符號(hào)執(zhí)行模塊的主要思想.Afleer 主要擴(kuò)展了KLEE 的算法,算法輸入是LLVM 的模塊M,覆蓋信息virgin_bits,輸出為新生成的測(cè)試用例SE_Seeds.首先創(chuàng)建一個(gè)初始狀態(tài)(第1 行),并將其加入到狀態(tài)集合States中(第2 行).此時(shí),從初始狀態(tài)開(kāi)始進(jìn)行遍歷,在集合States中選擇一個(gè)狀態(tài)(第4 行),這里,搜索方法可以采取不同的策略(例如,深度優(yōu)先策略或者廣度優(yōu)先策略等).接下來(lái)得到當(dāng)前狀態(tài)的指令 inst,根據(jù)指令的不同類型對(duì)其進(jìn)行解釋執(zhí)行(第6 行～第30 行).例如,當(dāng)指令為分支條件時(shí)(第7 行),當(dāng)前狀態(tài)分叉為兩個(gè)狀態(tài)并更新路徑條件state.pc.如果當(dāng)前分支的路徑條件可滿足(第8 行與第12 行),則將生成的新?tīng)顟B(tài)加入狀態(tài)集合.當(dāng)遇到指令A(yù)tmoicRMW(來(lái)自算法1)時(shí)解析得到基本塊編號(hào)(第18 行),基于該編號(hào)可以檢查當(dāng)前分支是否被覆蓋.第18 行～第20 行計(jì)算當(dāng)前分支的哈希值(與AFL 中的插樁計(jì)算等價(jià)).如果覆蓋到新的分支(第21 行),則生成測(cè)試用例(第22 行),并將其加入到測(cè)試用例集合SE_Seeds(第23 行).當(dāng)該路徑生成新的分支后,我們將該狀態(tài)優(yōu)先級(jí)降低(第24 行),因?yàn)樵诜?hào)執(zhí)行突破新的分支后,我們期待模糊測(cè)試基于該測(cè)試用例進(jìn)行更深位置的探索.因此,為了提高效率,此時(shí),符號(hào)執(zhí)行將優(yōu)先探索其他分支,從而避免與模糊測(cè)試進(jìn)行同位置的探索.第4 行的搜索算法將同時(shí)考慮各個(gè)狀態(tài)的優(yōu)先級(jí).對(duì)于其他類型的指令,符號(hào)執(zhí)行將根據(jù)相應(yīng)的語(yǔ)義進(jìn)行解釋與執(zhí)行(第28 行).

算法3.Afleer 符號(hào)執(zhí)行模塊.

Input:M:LLVM 模塊,virgin bits:覆蓋信息;Output:SE_Seeds:新增測(cè)試用例.

4 實(shí)證研究

本節(jié)介紹本文的實(shí)證研究,首先提出研究問(wèn)題,接著介紹實(shí)驗(yàn)設(shè)計(jì)的具體方法,然后總結(jié)并分析實(shí)驗(yàn)結(jié)果,最后對(duì)Afleer 的優(yōu)缺點(diǎn)進(jìn)行討論,并對(duì)符號(hào)執(zhí)行及模糊測(cè)試相結(jié)合的未來(lái)研究工作進(jìn)行分析.

4.1 實(shí)驗(yàn)設(shè)計(jì)

基準(zhǔn)方法的選擇.Afleer 方法的目的是通過(guò)結(jié)合符號(hào)執(zhí)行幫助模糊測(cè)試能夠覆蓋到更多的分支,從而發(fā)現(xiàn)更多的漏洞.在實(shí)驗(yàn)中我們選擇AFL(本文提供的方法是通用的,可以很容易地?cái)U(kuò)展到其他AFL 優(yōu)化的方法上,例如AFLfast[25]、Steelix[26]以及Skyfire[27]等)作為基準(zhǔn)方法,而未選擇KLEE 作為基準(zhǔn)方法,其主要原因總結(jié)如下.

(1)在Afleer 中,主要使用KLEE 增強(qiáng)AFL 尋找未覆蓋邊的能力.而不是用AFL 去輔助KLEE 生成測(cè)試用例,因此,本文將側(cè)重點(diǎn)放在對(duì)模糊測(cè)試方法的改進(jìn)上;

(2)為了提高效率,Afleer 中KLEE 未對(duì)AFL 已覆蓋的邊生成測(cè)試用例,因此,Afleer 生成的測(cè)試用例更適合與AFL 生成的測(cè)試用例進(jìn)行對(duì)比;

(3)即使將Afleer 中的KLEE 按標(biāo)準(zhǔn)方式加以運(yùn)行,其生成的測(cè)試用例一定是Afleer 生成的測(cè)試用例的子集,因此,將兩者進(jìn)行比較沒(méi)有意義.

除此之外,將符號(hào)執(zhí)行與動(dòng)態(tài)測(cè)試結(jié)合的技術(shù)還有Driller[20]以及配套工具HCT[2]等,然而,由于HCT 工具沒(méi)有開(kāi)源,Driller 僅能夠運(yùn)行在DECREE 的二進(jìn)制程序上,因此,在我們?cè)O(shè)計(jì)的實(shí)驗(yàn)中并沒(méi)有與其直接進(jìn)行比較,在相關(guān)工作中,我們將從方法上進(jìn)行比較.

研究問(wèn)題.為了驗(yàn)證Afleer 的有效性,本文嘗試回答如下研究問(wèn)題.

·RQ1.Afleer 在漏洞檢測(cè)上的效果如何?與AFL 相比,其是否可以在相同的指定時(shí)間內(nèi)檢測(cè)到更多的漏洞?或者對(duì)于同樣的漏洞,其是否可以更快地檢測(cè)到?

·RQ2.Afleer 在測(cè)試覆蓋能力上的效果如何?是否借助符號(hào)執(zhí)行可以有效輔助Afleer 覆蓋到更多的分支?

實(shí)驗(yàn)數(shù)據(jù)集.為了回答上述研究問(wèn)題,本文選擇了標(biāo)準(zhǔn)程序集LAVA-M[22]以及一個(gè)實(shí)際項(xiàng)目oSIP-4.0.0[22]作為實(shí)驗(yàn)對(duì)象.其中,LAVA-M 中的每個(gè)程序均包含了大量的已知漏洞,因此可以用來(lái)公平地比較各種方法的漏洞檢測(cè)能力,實(shí)際項(xiàng)目oSIP 則可用來(lái)驗(yàn)證Afleer 的可擴(kuò)展性以及有效性.標(biāo)準(zhǔn)程序集LAVA-M 和項(xiàng)目oSIP 的具體信息總結(jié)如下.

·LVAM-M 包含4 個(gè)帶有漏洞的Linux 系統(tǒng)工具程序:base64、md5sum、uniq 以及who.數(shù)據(jù)集的搜集人員按照一定標(biāo)準(zhǔn)在每個(gè)程序中插入了大量的難以檢測(cè)到的漏洞.其中,每個(gè)漏洞都有一個(gè)唯一編號(hào),當(dāng)該漏洞被觸發(fā)時(shí)則打印對(duì)應(yīng)漏洞編號(hào).我們使用LAVA-M 來(lái)比較Afleer 以及AFL 的漏洞檢測(cè)能力,由于這些程序都來(lái)自實(shí)際項(xiàng)目,因此,它們同時(shí)也被用來(lái)比較不同方法的代碼覆蓋能力.注意,在運(yùn)行base64與md5sum時(shí),我們分別使用了參數(shù)-d 與-c.

·oSIP 實(shí)現(xiàn)了SIP 協(xié)議[28],其為用戶提供了初始化以及控制SIP 會(huì)話的接口實(shí)現(xiàn).由于其包含了SIP 協(xié)議的語(yǔ)法解析器,因此,AFL 難以生成可以通過(guò)復(fù)雜語(yǔ)法檢查的測(cè)試用例,我們將分析Afleer 在該項(xiàng)目中的代碼覆蓋能力.

評(píng)測(cè)指標(biāo).針對(duì)漏洞檢測(cè)能力以及代碼覆蓋能力,本文通過(guò)以下指標(biāo)來(lái)評(píng)測(cè)不同方法.

·漏洞檢測(cè)數(shù)(#bugs):在指定時(shí)間內(nèi)找到的漏洞總數(shù).

·邊覆蓋數(shù)(#edges):AFL 中的邊指的是分支,邊覆蓋數(shù)表示在指定時(shí)間內(nèi)的分支覆蓋數(shù).

·路徑覆蓋數(shù)(#path):路徑數(shù)表示AFL 在指定時(shí)間內(nèi)生成的測(cè)試用例數(shù).注意,AFL 采用了循環(huán)桶(loop bucket)的思想,部分路徑的測(cè)試用例不會(huì)被保留.

運(yùn)行實(shí)驗(yàn)的機(jī)器配置信息總結(jié)如下:CPU Intel Xeon E5-1650 v3,內(nèi)存16GB,操作系統(tǒng)64 位Ubuntu 16.04LTS,并且運(yùn)行時(shí)間固定為5 小時(shí).

4.2 實(shí)驗(yàn)結(jié)果分析

4.2.1 LAVA-M 程序集上的漏洞檢測(cè)能力比較(RQ1)

表1 總結(jié)了在LAVA-M 程序集上Afleer 與AFL 的比較結(jié)果.其中,前兩行表示LAVA-M 數(shù)據(jù)集的相關(guān)信息,第1 行表示項(xiàng)目名字,第2 行總結(jié)了每個(gè)項(xiàng)目中插入的漏洞數(shù)(即已知的漏洞數(shù)).隨后兩行總結(jié)了Afleer 檢測(cè)出的漏洞數(shù),第4 行(#afleerbugs)總結(jié)了Afleer 在每個(gè)項(xiàng)目中檢測(cè)到的漏洞數(shù)以及占所有已知漏洞數(shù)的比例.如果一些漏洞在KLEE 中被直接發(fā)現(xiàn)并發(fā)送給AFL,則將其總結(jié)在第3 行(#kleebugs).最后一行(#aflbugs)總結(jié)了在執(zhí)行標(biāo)準(zhǔn)AFL 時(shí)所檢測(cè)到的漏洞數(shù).

Table 1 Results of bugs found on benchmark LAVA-M表1 LAVA-M 程序集上的漏洞檢測(cè)結(jié)果比較

基于表1 可以看出,Afleer 總共檢測(cè)出755(33%)個(gè)漏洞,其中,在base64、md5sum、uniq 以及who 上分別檢測(cè)出11(25%)、0、8(28.57%)以及736(4%)個(gè)漏洞.而標(biāo)準(zhǔn)的AFL 基本沒(méi)有檢測(cè)出漏洞,其中,僅在who 上檢測(cè)出1 個(gè)漏洞.另外,值得注意的是,KLEE 在依據(jù)覆蓋信息進(jìn)行搜索遍歷時(shí)也可以直接檢測(cè)出漏洞,例如KLEE分別為4 個(gè)項(xiàng)目檢測(cè)到了6、0、8、9 個(gè)漏洞.除去23(1%)個(gè)KLEE 發(fā)現(xiàn)的漏洞,Afleer 中的AFL 仍然發(fā)現(xiàn)了722(32%)個(gè)漏洞,其漏洞檢測(cè)能力要顯著優(yōu)于AFL.

圖4 給出了隨著時(shí)間的推移,Afleer 與AFL 在3 個(gè)項(xiàng)目(因?yàn)閙d5sum 上均未檢測(cè)到漏洞,因此未給出趨勢(shì)圖)中漏洞檢測(cè)的趨勢(shì)圖,其中,橫坐標(biāo)為方法運(yùn)行的時(shí)間,縱坐標(biāo)為檢測(cè)到的漏洞數(shù).注意,在AFL 執(zhí)行過(guò)程中對(duì)一個(gè)漏洞可能會(huì)產(chǎn)生多個(gè)測(cè)試用例,因此,圖4 所示中縱坐標(biāo)顯示的漏洞數(shù)(crashes no)要多于表1 中檢測(cè)到的漏洞數(shù).從圖4 可以看到,3 個(gè)項(xiàng)目在開(kāi)始時(shí),檢測(cè)到的漏洞數(shù)都會(huì)快速增長(zhǎng),因?yàn)殚_(kāi)始時(shí),KLEE 會(huì)快速突破某些分支并找到一定的漏洞,使得漏洞數(shù)快速增長(zhǎng).之后,一些處于較深位置的漏洞將無(wú)法被KLEE 探索到,而AFL 在此基礎(chǔ)上將進(jìn)一步找到一些更深位置的漏洞.而在uniq 上,當(dāng)KLEE 檢測(cè)到所有漏洞后,Afleer 并沒(méi)有檢測(cè)到更新的漏洞.與AFL 相比,其在沒(méi)有KLEE 提供漏洞的情況下,幾乎檢測(cè)不到任何漏洞.

Fig.4 Increasing of bugs finding on LAVA-M圖4 LAVA-M 漏洞檢測(cè)趨勢(shì)圖

通過(guò)查看LAVA-M 中漏洞插入的代碼,我們分析了AFL 難以檢測(cè)到漏洞而Afleer 可以檢測(cè)到漏洞的原因.LAVA-M 中插入的漏洞的觸發(fā)條件主要是針對(duì)魔術(shù)字節(jié)(magic byte)的比較,例如,0x6c617564==lava_get(253).因此,普通AFL 很難突破這些分支,從而無(wú)法找到漏洞.而在Afleer 中,KLEE 可以為其生成相應(yīng)的測(cè)試用例0x6c617564.并且,這些漏洞之間是有一定的關(guān)系的,例如,AFL 讀取KLEE 發(fā)送的測(cè)試用例0x6c617564 后,在其基礎(chǔ)上很容易變異出一個(gè)可以覆蓋條件0x6c617562==lava_get(255)的測(cè)試用例(其只有一個(gè)字節(jié)是不同的),并且不受該條件所處深度的影響.例如,在uniq 中,KLEE 提供了8 個(gè)觸發(fā)漏洞的測(cè)試用例,而AFL 基于該測(cè)試用例并沒(méi)有發(fā)現(xiàn)新的漏洞.其主要原因是,觸發(fā)其他漏洞的測(cè)試用例與KLEE 已生成的測(cè)試用例在字節(jié)上相差很大,因此,基于變異策略的AFL 無(wú)法更快地生成新的漏洞.而如果其處于深位置,則KLEE 也將很難搜索到該位置.該結(jié)果表明了Afleer 的有效性.

同時(shí),通過(guò)分析現(xiàn)有測(cè)試用例的覆蓋率,我們進(jìn)一步獲得了其他漏洞未被檢測(cè)到的原因,主要原因是由于符號(hào)執(zhí)行與模糊測(cè)試本身的弱點(diǎn)導(dǎo)致某些分支難以被覆蓋.具體地,我們從符號(hào)執(zhí)行與模糊測(cè)試兩方面來(lái)進(jìn)行分析.

(1)從符號(hào)執(zhí)行方面進(jìn)行分析,其主要由兩個(gè)原因?qū)е?首先,符號(hào)執(zhí)行面臨狀態(tài)爆炸問(wèn)題,由于一些分支在有限時(shí)間內(nèi)無(wú)法被遍歷到,因此無(wú)法生成相應(yīng)的測(cè)試用例.其次,某些分支條件依賴于其相應(yīng)的前置條件,即使這些分支可以被覆蓋到,但在某些前置條件下,分支條件永遠(yuǎn)無(wú)法得到滿足,因此也會(huì)導(dǎo)致無(wú)法生成相應(yīng)的測(cè)試用例.例如,KLEE 與AFL 在md5sum 程序上都沒(méi)有檢測(cè)到漏洞,其原因主要是無(wú)法突破開(kāi)始時(shí)的哈希函數(shù),因此難以覆蓋到含有漏洞的分支.

(2)在模糊測(cè)試方面,由于LAVA 數(shù)據(jù)集中都是較難的數(shù)字比較條件,因此,模糊測(cè)試通過(guò)隨機(jī)變異很難生成相應(yīng)的測(cè)試用例,從而無(wú)法發(fā)現(xiàn)漏洞.

在Afleer 總共發(fā)現(xiàn)的755 個(gè)漏洞中,通過(guò)符號(hào)執(zhí)行Aflee_KLEE 找到了23 個(gè),而通過(guò)模糊測(cè)試Afleer_Afl找到了722 個(gè).因此,與單獨(dú)使用符號(hào)執(zhí)行工具KLEE 相比,Afleer 多發(fā)現(xiàn)了722(超過(guò)31 倍)個(gè)漏洞.

基于上述分析我們認(rèn)為,通過(guò)結(jié)合KLEE 與AFL,Afleer 與單獨(dú)使用KLEE 及AFL 相比可以顯著提高漏洞檢測(cè)的能力(即基于LAVA-M 評(píng)測(cè)集可以比AFL 多發(fā)現(xiàn)754 個(gè)漏洞,比KLEE 多發(fā)現(xiàn)722 個(gè)漏洞).

4.2.2 LAVA-M 程序集上的代碼覆蓋能力比較(RQ2)

本節(jié)我們將依次比較Afleer 與AFL 在LAVA-M 程序集上的分支覆蓋能力以及路徑覆蓋能力.

圖5 給出了4 個(gè)程序中不同方法的分支覆蓋趨勢(shì)圖,其中,橫坐標(biāo)為時(shí)間,縱坐標(biāo)為覆蓋的分支數(shù).從中可以看到,base64、md5sum 以及uniq 上,Afleer 無(wú)明顯提高,通過(guò)觀察代碼,我們分析了其主要原因在于:(1)代碼量較小,例如base64、uniq 以及md5sum 分別包含350 行、700 行以及1 000 行左右,此時(shí)Afleer 與AFL 在很短的時(shí)間內(nèi)就可以收斂;(2)一些較難的分支無(wú)法被KLEE 突破,因此Afleer 此時(shí)會(huì)與AFL 的分支覆蓋能力相似,例如md5sum 包含哈希計(jì)算,導(dǎo)致后面的分支都無(wú)法突破,并且也沒(méi)有檢測(cè)到任何漏洞(見(jiàn)表1).而對(duì)于who,其包含4 600 多行代碼,此時(shí),Afleer 明顯可以突破更多的分支條件,并可以額外覆蓋3 500(35%)個(gè)新分支.

Fig.5 Increasing of branch coverage on LAVA-M圖5 LAVA-M 分支覆蓋趨勢(shì)圖

表2 顯示了Afleer 與AFL 在4 個(gè)項(xiàng)目中分別生成的測(cè)試用例數(shù).表格左邊為Afleer 的結(jié)果,右邊為AFL 的結(jié)果.同時(shí)我們也統(tǒng)計(jì)了Afleer 中AFL 與KLEE 分別貢獻(xiàn)的測(cè)試用例總數(shù)(即Afleer_AFL 與Afleer_KLEE),可以發(fā)現(xiàn),AFL 生成的測(cè)試用例要顯著多于KLEE 生成的測(cè)試用例(KLEE 在4 個(gè)項(xiàng)目中分別貢獻(xiàn)12%、3%、21%以及3%),即分別生成了24、10、20 以及26 個(gè)測(cè)試用例.需要注意的是,在Afleer 剛開(kāi)始運(yùn)行時(shí),KLEE 和AFL同時(shí)運(yùn)行,此時(shí),一些容易覆蓋的分支還未被AFL 覆蓋,但是優(yōu)先被KLEE 搜索到從而生成測(cè)試用例.因此,列Afleer_KLEE 包含的測(cè)試用例不全是AFL 難以覆蓋到的路徑.通過(guò)與AFL 的結(jié)果進(jìn)行比較(最后一列)可以發(fā)現(xiàn),Afleer 在base64 上提升了42(28%)、在md5sum 上提升了94(35%)、在uniq 上提升了4(4%)、在who 上提升了699(大約5 倍),上述結(jié)果表明,Afleer 在路徑覆蓋能力上有明顯的提升.此外,圖6 中給出了路徑覆蓋的趨勢(shì)圖,橫坐標(biāo)表示時(shí)間,縱坐標(biāo)表示路徑覆蓋數(shù).

Table 2 Comparison of the total number of test cases generated by Afleer and AFL表2 Afleer 與AFL 生成的測(cè)試用例總數(shù)比較結(jié)果

基于上述及表2 和圖6 的分析,Afleer 在分支覆蓋能力與路徑覆蓋能力上都有不同程度的提升.在某些項(xiàng)目上,即使分支覆蓋能力沒(méi)有明顯提升,但路徑覆蓋能力仍有明顯提升.因此,Afleer 可以大幅度提高程序的覆蓋能力,尤其是在大規(guī)模程序上.與KLEE 相比,可以發(fā)現(xiàn),Afleer 中AFL 貢獻(xiàn)了更多的測(cè)試用例(4 倍～32 倍).該結(jié)果符合我們的預(yù)期,即AFL 可以快速生成大量較容易的測(cè)試用例,而KLEE 由于可擴(kuò)展性差,因此主要用于生成較難的測(cè)試用例.

Fig.6 Increasing of branch coverage and bug finding on oSIP圖6 LAVA-M 路徑覆蓋趨勢(shì)圖

4.2.3 基于實(shí)際項(xiàng)目的比較(RQ1 和RQ2)

我們將Afleer 應(yīng)用在實(shí)際項(xiàng)目oSIP 中,并發(fā)現(xiàn)了一個(gè)新的漏洞,該漏洞目前已被提交給GNU 處理[29].在實(shí)驗(yàn)中,我們對(duì)輸入規(guī)模進(jìn)行了限制(即將輸入規(guī)模限定為10 字節(jié)或者128 字節(jié)),并通過(guò)不同的輸入規(guī)模來(lái)分析其對(duì)覆蓋能力以及漏洞檢測(cè)能力的影響.

圖7 顯示了oSIP 在輸入規(guī)模為10 字節(jié)與128 字節(jié)時(shí)的分支覆蓋趨勢(shì)圖、路徑覆蓋趨勢(shì)圖以及漏洞檢測(cè)趨勢(shì)圖.與AFL 相比,Afleer 在輸入規(guī)模為10 字節(jié)時(shí)分支覆蓋能力提升了1.3 倍,路徑覆蓋能力提升了54%;當(dāng)輸入規(guī)模為128 字節(jié)時(shí),分支覆蓋能力提升了2.4 倍,路徑覆蓋能力提升了6.1 倍.在漏洞檢測(cè)能力上,當(dāng)輸入為10 字節(jié)時(shí),由于輸入規(guī)模太小,因此都未檢測(cè)出漏洞.而當(dāng)輸入規(guī)模變?yōu)?28 字節(jié)時(shí),此時(shí)Afleer 可以檢測(cè)到漏洞,而AFL 仍然未檢測(cè)到.注意,圖7(f)所示的70 多個(gè)可以觸發(fā)漏洞的測(cè)試用例都屬于觸發(fā)同一個(gè)漏洞.同時(shí),通過(guò)比較不同輸入規(guī)模的結(jié)果可以發(fā)現(xiàn),隨著輸入規(guī)模的擴(kuò)大,其可以生成的測(cè)試用例數(shù)也在增加,因此,可以覆蓋的分支、路徑以及可檢測(cè)出的漏洞都會(huì)提高.

同時(shí),我們也分析了Afleer 中AFL 與KLEE 的各自貢獻(xiàn)率(記為KLEE/AFL).其中,在測(cè)試用例生成方面,當(dāng)輸入長(zhǎng)度為10 字節(jié)時(shí)為60/78,當(dāng)輸入長(zhǎng)度為128 字節(jié)時(shí)為2/680.可以看到,在輸入長(zhǎng)度較小時(shí),KLEE 會(huì)快速生成更多的測(cè)試用例,因?yàn)楫?dāng)輸入長(zhǎng)度較小時(shí),KLEE 的約束復(fù)雜度較低,從而使得求解速度快速提高.在漏洞發(fā)現(xiàn)方面,KLEE 沒(méi)有發(fā)現(xiàn)該漏洞.

總的來(lái)說(shuō),Afleer 在實(shí)際項(xiàng)目中比AFL 和KLEE 在代碼覆蓋能力及漏洞檢測(cè)能力上都具有顯著的提升,因此證明了Afleer 的可擴(kuò)展性和有效性.

Fig.7 Increasing of branch coverage and bug finding on oSIP圖7 oSIP 分支覆蓋以及漏洞檢測(cè)趨勢(shì)圖

4.3 進(jìn)一步討論

本節(jié)將結(jié)合上述實(shí)驗(yàn)結(jié)果進(jìn)一步討論影響Afleer 有效性的因素,在Afleer 中,KLEE 的方式是搜索執(zhí)行樹(shù)而AFL 的方式是變異測(cè)試用例,因此,Afleer 的有效性受制于KLEE 與AFL 本身在目標(biāo)程序上的搜索效率與變異效率.

從KLEE 角度出發(fā),其在搜索時(shí)會(huì)存在狀態(tài)爆炸問(wèn)題.當(dāng)目標(biāo)分支在目標(biāo)程序的較淺位置時(shí),KLEE 比較容易搜索到該分支,從而生成相應(yīng)的測(cè)試用例.例如,圖4 中,KLEE 在開(kāi)始時(shí)會(huì)很快找到較淺位置的漏洞.相反,即使已知某個(gè)分支難以覆蓋到,但是,如果其處于較深位置,則KLEE 仍將難以找到一條可以滿足該分支條件的路徑.例如,對(duì)于其他未檢測(cè)到的漏洞,KLEE 在有限時(shí)間內(nèi)也難以檢測(cè)到.

從AFL 的角度出發(fā),測(cè)試用例在內(nèi)容上的關(guān)聯(lián)程度對(duì)其影響較大.假設(shè)KLEE 已為某個(gè)目標(biāo)分支生成測(cè)試用例并提交給AFL,如果剩余未覆蓋分支的測(cè)試用例與當(dāng)前測(cè)試用例關(guān)聯(lián)程度較強(qiáng)(即相似度較高),則AFL 通過(guò)變異可以很快覆蓋到其他分支,并且不受深度的影響.例如,在上一節(jié)所述內(nèi)容中,KLEE 生成了測(cè)試用例0x6c617564 后,對(duì)于另一個(gè)處于較深位置的未覆蓋分支0x6c617562==lava_get(255)則很難搜索到.但是,AFL 通過(guò)變異可以很快地為其生成測(cè)試用例,在項(xiàng)目who 中,KLEE 為其找到了9 個(gè)漏洞,在此基礎(chǔ)上,AFL 仍多檢測(cè)到727 個(gè)漏洞(見(jiàn)表1).相反,如果其他分支的測(cè)試用例與當(dāng)前測(cè)試用例完全不同,此時(shí),AFL 難以通過(guò)變異當(dāng)前測(cè)試用例來(lái)覆蓋到新分支.例如,在uniq 中,Afleer 找到的漏洞都來(lái)自KLEE.

總的來(lái)說(shuō),當(dāng)符號(hào)執(zhí)行發(fā)現(xiàn)某個(gè)未覆蓋的分支,而模糊測(cè)試基于該分支可以找到更多的未覆蓋分支時(shí),雙方結(jié)合的方式將會(huì)更加高效.當(dāng)KLEE 無(wú)法搜索到未覆蓋的分支,或者AFL 無(wú)法基于KLEE 生成的測(cè)試用例找到更多的測(cè)試用例時(shí),雙方結(jié)合的方式將會(huì)低效.

此外,在Afleer 的設(shè)計(jì)中,KLEE 的不同之處在于:(1)對(duì)于AFL 已經(jīng)覆蓋到的邊,KLEE 仍然可以到達(dá)該邊但是不會(huì)生成測(cè)試用例;(2)對(duì)于AFL 未覆蓋的邊,則生成測(cè)試用例并發(fā)送給AFL.KLEE 在Afleer 中執(zhí)行的先后順序僅影響AFL 與KLEE 中都容易生成的測(cè)試用例,而不影響整體效率.具體來(lái)講,如果KLEE 先執(zhí)行,則KLEE 將會(huì)優(yōu)先生成多個(gè)AFL 未遍歷的測(cè)試用例(假設(shè)測(cè)試用例集合為P+Q,P表示對(duì)AFL 容易覆蓋到的測(cè)試用例集合,Q表示AFL 較難覆蓋到的測(cè)試用例集合).由于此時(shí)AFL 還未執(zhí)行,P與Q執(zhí)行的路徑并未被覆蓋,因此,將由KLEE 優(yōu)先生成.而如果AFL 先執(zhí)行,則P將由AFL 快速生成,此時(shí),KLEE 在遍歷時(shí)如果遇到這些邊則不再需要生成P,僅只生成AFL 難以生成的測(cè)試用例Q.總的來(lái)說(shuō),KLEE 與AFL 的先后執(zhí)行順序僅影響P由哪部分優(yōu)先生成;而對(duì)于AFL 難以生成的測(cè)試用例Q,理論上無(wú)論哪部分先執(zhí)行,其基本上都將被KLEE 生成.

為了解決Afleer 現(xiàn)有的不足,未來(lái)可以從以下幾個(gè)方面進(jìn)行改進(jìn).在符號(hào)執(zhí)行方面,可以采用加入靜態(tài)分析(例如文獻(xiàn)[31])來(lái)引導(dǎo)符號(hào)執(zhí)行更高效的搜索.循環(huán)與遞歸是影響符號(hào)執(zhí)行狀態(tài)爆炸的主要因素,通過(guò)加入循環(huán)(遞歸)分析與總結(jié)可以緩解該問(wèn)題.利用程序切片分析發(fā)現(xiàn)不相關(guān)的狀態(tài),在符號(hào)執(zhí)行中略過(guò)這些狀態(tài)也是另外一種方法.對(duì)于位置較深使得符號(hào)執(zhí)行難以到達(dá)的分支,可以通過(guò)混合執(zhí)行來(lái)快速達(dá)到,或者進(jìn)行目標(biāo)驅(qū)動(dòng)的數(shù)據(jù)流分析來(lái)尋找到達(dá)該分支的路徑.在模糊測(cè)試方面,可以加入現(xiàn)有的技術(shù),如污點(diǎn)分析(Steelix[26],Angora[30])、定向模糊測(cè)試(AFLgo[31],Hawkeye[32])以及其他策略(Skyfire[25],AFLFast[27])來(lái)提高模糊測(cè)試的能力,從而提高混合測(cè)試的整體性能.

5 相關(guān)工作

本節(jié)將分別從模糊測(cè)試、符號(hào)執(zhí)行以及混合測(cè)試等角度對(duì)已有研究工作進(jìn)行總結(jié).

5.1 模糊測(cè)試

目前存在很多基于遺傳算法并基于覆蓋率引導(dǎo)的模糊測(cè)試工具,例如:AFL[4]、libFuzzer[7]以及honggfuzz[6].污點(diǎn)分析(taint analysis)用于分析程序輸入與程序邏輯之間的關(guān)系,目前,很多基于污點(diǎn)分析的方法已被用來(lái)提高模糊測(cè)試的能力.BuzzFuzz[33]以及FairFuzz[35]使用動(dòng)態(tài)污點(diǎn)分析的方法來(lái)定位輸入中感興趣的字節(jié),隨后重點(diǎn)對(duì)這些字節(jié)進(jìn)行變異,從而提高效率.Taintscope[36]通過(guò)污點(diǎn)分析來(lái)識(shí)別驗(yàn)證校驗(yàn)和(checksum)數(shù)字的分支,并通過(guò)改變控制流來(lái)繞過(guò)這些難以通過(guò)的分支.與BuzzFuzz 和FairFuzz 類似,在繞過(guò)校驗(yàn)和的檢驗(yàn)后,其識(shí)別出輸入中與危險(xiǎn)操作相關(guān)的字節(jié)并進(jìn)行重點(diǎn)變異.Dowser[38]對(duì)緩沖區(qū)溢出漏洞進(jìn)行檢查,通過(guò)污點(diǎn)分析檢查輸入中影響到數(shù)組索引變化的字節(jié).污點(diǎn)分析雖然可以識(shí)別出重要字節(jié),但同時(shí)也會(huì)付出很高的性能代價(jià),并減緩模糊測(cè)試的執(zhí)行速度.VUzzer[37]通過(guò)污點(diǎn)分析識(shí)別出魔術(shù)字節(jié)(magic bytes)在輸入中的位置,從而對(duì)這些字節(jié)進(jìn)行變異,其缺點(diǎn)是魔術(shù)字節(jié)在輸入中的位置是固定的.Steelix[26]在固定位置通過(guò)細(xì)粒度的插裝方式來(lái)拆分程序中魔術(shù)字節(jié)的比較狀態(tài).例如,一個(gè)32 位的整數(shù)比較可以記錄為4 個(gè)8 位整型的比較,從而加快魔術(shù)字節(jié)的匹配速度,Steelix 適用于魔術(shù)字節(jié)比較中變量直接來(lái)自輸入的場(chǎng)景.Angora[30]提供了一種不通過(guò)符號(hào)執(zhí)行來(lái)求解路徑約束的方法,通過(guò)污點(diǎn)分析,借助梯度下降來(lái)搜索可以滿足約束條件的測(cè)試用例.基于上述分析可以看出,基于污點(diǎn)分析的模糊測(cè)試與本文所提出的Afleer 的目標(biāo)相似,都是針對(duì)難以覆蓋的分支來(lái)生成測(cè)試用例.其優(yōu)勢(shì)在于,當(dāng)分支條件中的變量直接來(lái)自輸入的某些字節(jié)時(shí),即使該分支處于較深的位置都可以快速生成測(cè)試用例.而如果分支條件中的變量依賴于輸入變量的所有字節(jié)或者依賴于部分字節(jié)的復(fù)雜計(jì)算,則基于污點(diǎn)分析的方法將會(huì)失效,而Afleer 通過(guò)符號(hào)執(zhí)行則可以有效解決該問(wèn)題.

除此之外,研究人員還提出了一些用來(lái)提高模糊測(cè)試效率的方法.例如,Rebert[38]等人以及Woo 等人[39]在模糊測(cè)試中,借助測(cè)試用例選擇以及調(diào)度策略來(lái)提升漏洞檢測(cè)能力.AFLFast[25]發(fā)現(xiàn)模糊測(cè)試在大部分時(shí)候都在嘗試高概率路徑,而很難觸發(fā)到新的低概率路徑,因此其通過(guò)給覆蓋低概率路徑的測(cè)試用例賦予更多的時(shí)間進(jìn)行變異來(lái)提升效率.AFLgo[31]是一種針對(duì)特定目標(biāo)點(diǎn)的模糊測(cè)試技術(shù),其通過(guò)為測(cè)試用例排序來(lái)進(jìn)行高效率的有針對(duì)性的測(cè)試.Skyfire[27]從現(xiàn)有測(cè)試用例中學(xué)習(xí)出基于概率的上下文敏感語(yǔ)法(probabilistic context sensitive grammar),以指導(dǎo)生成高質(zhì)量的結(jié)構(gòu)型測(cè)試用例.CollAFL[40]提出了一種可以解決模糊測(cè)試中路徑碰撞(path collisions)問(wèn)題的方法,路徑碰撞問(wèn)題主要由插裝過(guò)程中的基本塊編號(hào)碰撞所導(dǎo)致,該問(wèn)題會(huì)對(duì)新漏洞檢測(cè)能力產(chǎn)生影響.不難看出,這些方法與Afleer 存在正交關(guān)系,在下一步工作中,我們可以進(jìn)一步融合這些方法來(lái)提升Afleer 中模糊測(cè)試的能力.

5.2 符號(hào)執(zhí)行

符號(hào)執(zhí)行已得到廣泛研究,并在工業(yè)界與學(xué)術(shù)界中涌現(xiàn)出了很多優(yōu)秀工具,例如:KLEE[9]、JPF[10]、CUTE[11]、S2E[41]、PEX[12]以及Angr[20]等.符號(hào)執(zhí)行時(shí)最大的問(wèn)題是狀態(tài)爆炸或者路徑爆炸,目前,存在很多針對(duì)該問(wèn)題的研究工作.

使用更好的搜索策略是解決狀態(tài)爆炸問(wèn)題的一種方法,例如:隨機(jī)路徑探索[9]、深度優(yōu)先探索[11]、廣度優(yōu)先探索[42]、基于覆蓋信息的探索[43].謝濤等人[44]提出了一種基于適應(yīng)度函數(shù)的路徑探索方法.陳振邦等人[45]提出了一種基于待驗(yàn)證性質(zhì)引導(dǎo)的搜索策略.李宣東等人[46]提出了一種優(yōu)先搜索最少被遍歷過(guò)的路徑從而提高整個(gè)覆蓋率的方法.王海軍等人[47]提出了一種基于路徑依賴分析以刪除冗余路徑的方法,從而緩解了狀態(tài)爆炸問(wèn)題.實(shí)證研究結(jié)果表明,這些策略可以在一定程度上緩解路徑爆炸的問(wèn)題.

通過(guò)狀態(tài)約減[48]也是解決路徑爆炸問(wèn)題的一種方法,如果一條路徑不可達(dá)或者約束條件與之前遍歷的路徑的約束條件相同,則可以不必執(zhí)行該路徑.甘水滔等人[49]提出了一種根據(jù)程序功能進(jìn)行切片分析的方法,進(jìn)而引導(dǎo)符號(hào)執(zhí)行并約減無(wú)關(guān)狀態(tài).Trabish 等人[50]提出的方法,可以在符號(hào)執(zhí)行過(guò)程中實(shí)時(shí)地過(guò)濾無(wú)關(guān)代碼從而提高效率.此外,合并路徑[51,52]也是一種提高符號(hào)執(zhí)行效率的方法.例如,函數(shù)總結(jié)[53]以及循環(huán)總結(jié)技術(shù)[54-56]可以被用來(lái)合并路徑,從而避免函數(shù)在循環(huán)或者函數(shù)中不斷被搜索.除此之外,一些研究針對(duì)混合執(zhí)行(concolic execution)的優(yōu)化問(wèn)題[57,58]并提出了相應(yīng)解決方案[59].

不難看出,上述針對(duì)符號(hào)執(zhí)行的研究工作與本文所提出的Afleer 同樣存在正交關(guān)系,在下一步工作中,我們可以進(jìn)一步融合這些方法,幫助Afleer 更高效地搜索到未覆蓋的分支,從而提升Afleer 的效率.

5.3 符號(hào)執(zhí)行與模糊測(cè)試結(jié)合的混合測(cè)試

目前已有很多關(guān)于符號(hào)執(zhí)行與模糊測(cè)試(或隨機(jī)測(cè)試)結(jié)合的混合測(cè)試.DART[16]與SAGE[17]通過(guò)隨機(jī)測(cè)試產(chǎn)生一定數(shù)量的測(cè)試用例,之后選取測(cè)試用例并運(yùn)用混合執(zhí)行來(lái)系統(tǒng)性地遍歷程序.與Afleer 相比,DART 與SAGE 使用隨機(jī)測(cè)試以及混合執(zhí)行,而Afleer 使用符號(hào)執(zhí)行與基于覆蓋率的灰盒測(cè)試.DART 與SAGE 是單向的,其僅將隨機(jī)測(cè)試生成的測(cè)試用例用于混合執(zhí)行,而 Afleer 是雙向交互的,因此能夠更高效地生成測(cè)試用例.SYMFUZZ[18]通過(guò)符號(hào)執(zhí)行分析兩個(gè)程序輸入之間的依賴關(guān)系,基于依賴信息計(jì)算測(cè)試用例的變異率,并用隨機(jī)測(cè)試來(lái)進(jìn)行變異.SYMFUZZ 不是直接將符號(hào)執(zhí)行與隨機(jī)測(cè)試結(jié)合,而是使用符號(hào)執(zhí)行計(jì)算出一定的信息來(lái)提高隨機(jī)測(cè)試的效率.Brian 等人[60]提出了一種結(jié)合符號(hào)執(zhí)行與模糊測(cè)試的混合測(cè)試方法.與Afleer 不同的地方在于:(1)該方法使用隨機(jī)測(cè)試生成測(cè)試用例來(lái)發(fā)現(xiàn)哪些基本塊較容易被覆蓋.基于該信息,利用符號(hào)執(zhí)行來(lái)搜索難以覆蓋的基本塊.而Afleer直接使用模糊測(cè)試的覆蓋信息來(lái)指導(dǎo)符號(hào)執(zhí)行的搜索過(guò)程.(2)不同于傳統(tǒng)模糊測(cè)試,在該方法中,模糊測(cè)試不進(jìn)行測(cè)試用例的變異操作,而僅用來(lái)運(yùn)行符號(hào)執(zhí)行生成的測(cè)試用例,以檢測(cè)程序是否出現(xiàn)崩潰,因此,其并未充分利用模糊測(cè)試的信息及優(yōu)勢(shì).

Majumdar 等人[2]提出了一種混合執(zhí)行與隨機(jī)測(cè)試交互執(zhí)行的方法(簡(jiǎn)稱HCT),其通過(guò)隨機(jī)測(cè)試產(chǎn)生測(cè)試用例,當(dāng)隨機(jī)測(cè)試收斂時(shí)(即無(wú)法生成新的測(cè)試用例)轉(zhuǎn)到混合執(zhí)行.一旦混合執(zhí)行找到新的測(cè)試用例,則返回隨機(jī)測(cè)試?yán)^續(xù)進(jìn)行.Yun 等人[61]提出了一種適合混合測(cè)試的混合執(zhí)行工具QSYM,他們深入分析了影響混合測(cè)試的主要性能瓶頸:即混合執(zhí)行測(cè)試.該方法與我們的方法是正交關(guān)系,通過(guò)引入其改進(jìn)的混合執(zhí)行測(cè)試方法QSYM,可以提升 Afleer 的整體效率.Chao-Chun 等人[62]提出了一種以發(fā)現(xiàn)漏洞為目標(biāo)的混合執(zhí)行方法CRAXfuzz.首先對(duì)一些與安全密切相關(guān)的函數(shù)進(jìn)行hook,例如malloc、strcpy 以及printf 等.之后基于某個(gè)種子進(jìn)行混合執(zhí)行測(cè)試,CRAXfuzz 采用目標(biāo)驅(qū)動(dòng)的搜索策略來(lái)檢測(cè)被hook 的函數(shù)是否具有安全問(wèn)題.如果當(dāng)前種子未發(fā)現(xiàn)漏洞,則用模糊測(cè)試或者符號(hào)執(zhí)行生成新的種子進(jìn)行嘗試.

與Afleer 比較類似的工作是Saahil 等人[19]提出的方法Munch.Munch 也是使用KLEE 與AFL 進(jìn)行結(jié)合來(lái)提高測(cè)試的覆蓋率,但是,這兩種方法具有很大的不同:(1)兩者最大的不同在于目標(biāo)不同,Afleer 側(cè)重于提高分支覆蓋率,而Munch 側(cè)重于提高函數(shù)覆蓋率.因此,Afleer 采用細(xì)粒度的覆蓋信息(即分支覆蓋)來(lái)指導(dǎo)KLEE 的搜索,而Munch 采用粗粒度的函數(shù)覆蓋來(lái)引導(dǎo)KLEE 搜索(即sonar-search).(2)由于AFL 默認(rèn)也使用分支覆蓋引導(dǎo)并生成分支覆蓋信息,因此,通過(guò)分支覆蓋則可以更直接、更有效地將KLEE 與AFL 結(jié)合.例如,Afleer 中KLEE 的搜索利用AFL 的分支覆蓋信息進(jìn)行引導(dǎo),從而避免搜索AFL 已覆蓋的分支.因此,KLEE 新生成的測(cè)試用例一定是AFL 感興趣的測(cè)試用例(該測(cè)試用例會(huì)覆蓋AFL 未覆蓋的分支).因此,Afleer 中AFL 與KLEE 通過(guò)多次雙向交互,可以更高效地提高分支覆蓋率.在AFL 中未考慮函數(shù)覆蓋信息,Munch 中的兩種策略都分別屬于單向交互(即KLEE 到AFL 或者AFL 到KLEE).而在Munch 的實(shí)驗(yàn)結(jié)果中(原文圖3)可以發(fā)現(xiàn),由于覆蓋率的反饋信息較粗,隨著函數(shù)深度的逐漸加深,Munch 的兩種策略并未比AFL 有明顯的提升.而通過(guò)細(xì)粒度的覆蓋信息反饋,Afleer 在分支覆蓋上有明顯提升.(3)與Munch 相比,Afleer 在漏洞發(fā)現(xiàn)上更直接并且更有優(yōu)勢(shì).因?yàn)槁┒赐ǔＬ幱陔y以覆蓋的分支下,通過(guò)盡可能地覆蓋更多分支則會(huì)更容易發(fā)現(xiàn)潛在的漏洞.而函數(shù)覆蓋與漏洞發(fā)現(xiàn)則沒(méi)有直接的關(guān)系.例如在圖1(a)中,Munch 的主要目標(biāo)是函數(shù)覆蓋,因此,任何一個(gè)不等于123456789 的input都可以得到100%的函數(shù)覆蓋率(即當(dāng)前函數(shù)與func 函數(shù)都可以被覆蓋),但不能發(fā)現(xiàn)條件input==123456789 下的漏洞.Afleer 通過(guò)分支覆蓋的引導(dǎo),則可以直接檢測(cè)該漏洞.(4)兩種方法雖然不同,但在某種程度上又具有一定的互補(bǔ)性.通過(guò)Munch 首先覆蓋難覆蓋的函數(shù),然后在該函數(shù)內(nèi)利用Afleer 更系統(tǒng)性地進(jìn)行測(cè)試,從而可以盡可能地覆蓋函數(shù)內(nèi)全部分支.例如,在文獻(xiàn)[19]的圖1 中,如果某個(gè)漏洞處于最深層函數(shù)(如b0),則Afleer 中KLEE會(huì)首先搜索父節(jié)點(diǎn)的函數(shù),難以覆蓋到深處的函數(shù).而如果通過(guò)Munch 先搜索到b0,再進(jìn)行分支覆蓋搜索,則會(huì)更快地發(fā)現(xiàn)該漏洞.

Driller[21]將混合執(zhí)行工具Angr 與基于覆蓋率的AFL 相結(jié)合.首先運(yùn)行AFL,當(dāng)AFL 無(wú)法生成新的測(cè)試用例時(shí),則Angr 選取一個(gè)測(cè)試用例進(jìn)行混合執(zhí)行,直到發(fā)現(xiàn)新的測(cè)試用例,之后將新的測(cè)試用例再轉(zhuǎn)交給AFL 來(lái)繼續(xù)進(jìn)行.這兩種方法與Afleer 類似,都是通過(guò)符號(hào)執(zhí)行/混合執(zhí)行與灰盒測(cè)試/隨機(jī)測(cè)試結(jié)合,并且雙向交互.與HTC 不同的是,Afleer 與Driller 使用了灰盒測(cè)試,因此可以利用覆蓋率信息來(lái)指導(dǎo)符號(hào)執(zhí)行或混合執(zhí)行的搜索,進(jìn)而效率更高.而Afleer 與Driller 的不同之處在于:Afleer 運(yùn)行在源碼上,而Driller 運(yùn)行在二進(jìn)制代碼上;并且Afleer 使用的是符號(hào)執(zhí)行,而Driller 使用的是混合執(zhí)行.混合執(zhí)行的優(yōu)勢(shì)是,如果從AFL 的結(jié)果中選取高質(zhì)量的測(cè)試用例執(zhí)行,則有助于找到新分支.但在實(shí)際執(zhí)行過(guò)程中,不是所有測(cè)試用例都是高質(zhì)量的,例如:即使某個(gè)測(cè)試用例在控制流圖上可以到達(dá)未覆蓋的分支,但該測(cè)試用例在該路徑下產(chǎn)生的約束條件仍可能無(wú)法使分支條件得到滿足,此時(shí)就會(huì)影響效率.因此,其是一個(gè)平衡的過(guò)程,引入混合執(zhí)行在某些情況下可以快速找到并覆蓋處于深處的分支,但在某些條件下會(huì)出現(xiàn)大量的可到達(dá)但無(wú)法覆蓋深分支的情況.基于上述分析,Afleer 沒(méi)有采用混合執(zhí)行方式,而是使用符號(hào)執(zhí)行并依據(jù)覆蓋信息(即AFL 實(shí)時(shí)更新的文件)進(jìn)行系統(tǒng)性的搜索,該策略首先可以保證更快速地覆蓋淺位置的新分支.同時(shí),基于覆蓋信息以及控制流圖可以運(yùn)用更通用的搜索算法來(lái)遍歷程序執(zhí)行樹(shù).

6 總結(jié)與展望

本文深入分析了現(xiàn)有符號(hào)執(zhí)行與模糊測(cè)試的優(yōu)缺點(diǎn),并提出了一種將符號(hào)執(zhí)行與模糊測(cè)試相結(jié)合的新穎方法Afleer.該方法綜合利用了符號(hào)執(zhí)行可以解決復(fù)雜條件的能力,模糊測(cè)試可以覆蓋深分支的能力進(jìn)而生成具有高覆蓋率的測(cè)試用例.具體來(lái)說(shuō),模糊測(cè)試可以快速生成大量的測(cè)試用例,符號(hào)執(zhí)行基于模糊測(cè)試的覆蓋信息進(jìn)行搜索,當(dāng)搜索到新的未覆蓋分支時(shí)則生成測(cè)試用例,模糊測(cè)試基于符號(hào)執(zhí)行生成的測(cè)試用例繼續(xù)變異.本文將Afleer 用于標(biāo)準(zhǔn)程序集LAVAM-M 以及實(shí)際項(xiàng)目oSIP,最終結(jié)果驗(yàn)證了該方法的有效性.

我們?cè)谙乱徊焦ぷ髦?將從符號(hào)執(zhí)行與模糊測(cè)試本身存在的不足之處出發(fā),進(jìn)一步增強(qiáng)Afleer 的能力.首先,將現(xiàn)有的基于污點(diǎn)分析以及有目標(biāo)性的策略集成到模糊測(cè)試中,其可以提高模糊測(cè)試處理復(fù)雜分支的能力.其次,將前期的循環(huán)分析與總結(jié)工作[58-60]集成到符號(hào)執(zhí)行中,以加速符號(hào)執(zhí)行的效率.最后,如何基于模糊測(cè)試的動(dòng)態(tài)信息來(lái)指導(dǎo)符號(hào)執(zhí)行的搜索也將是下一步需要重點(diǎn)關(guān)注的課題.