基于深度學(xué)習(xí)的混合模糊測試方法*

高鳳娟 ,王 豫 ,司徒凌云 ,王林章

1(計(jì)算機(jī)軟件新技術(shù)國家重點(diǎn)實(shí)驗(yàn)室(南京大學(xué)),江蘇 南京 210023)

2(南京大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系,江蘇 南京 210023)

3(南京大學(xué) 信息管理學(xué)院,江蘇 南京 210023)

軟件是推動(dòng)新一代信息技術(shù)發(fā)展的驅(qū)動(dòng)力,隨著物聯(lián)網(wǎng)、云計(jì)算、人工智能等技術(shù)的快速發(fā)展,面向這些領(lǐng)域的軟件不斷發(fā)展.但是,相應(yīng)地,與之而來的是軟件質(zhì)量保障、軟件安全性等問題.領(lǐng)域軟件面臨的挑戰(zhàn)不僅是軟件數(shù)目的增加,更主要的是,由于領(lǐng)域應(yīng)用有其自身特點(diǎn),例如工控、制造等領(lǐng)域往往具備動(dòng)態(tài)組織單元、網(wǎng)絡(luò)泛在、數(shù)字孿生等特征,對(duì)生產(chǎn)效率和安全性也有著更高的要求.軟件缺陷,作為從軟件誕生就存在的問題,至今依舊威脅著領(lǐng)域軟件的魯棒性和安全性.

軟件缺陷(software defect)產(chǎn)生于開發(fā)人員的編碼過程,軟件開發(fā)過程不合理或開發(fā)人員的經(jīng)驗(yàn)不足,均有可能產(chǎn)生軟件缺陷.而含有缺陷的軟件在運(yùn)行時(shí)可能會(huì)產(chǎn)生意料之外的不良后果,嚴(yán)重時(shí)會(huì)給企業(yè)造成巨大的經(jīng)濟(jì)損失,甚至?xí){到人們的生命財(cái)產(chǎn)安全.因此,越早發(fā)現(xiàn)軟件缺陷,越能降低修復(fù)缺陷的代價(jià).

模糊測試和基于符號(hào)執(zhí)行的測試方法是當(dāng)前主流的、有效的缺陷檢測方法.模糊測試(fuzzing)是通過向被測程序不斷提供非預(yù)期的輸入并監(jiān)視該程序是否出現(xiàn)異常,從而達(dá)到探測軟件缺陷的目的,是一種基于缺陷注入的自動(dòng)軟件測試技術(shù).它使用大量自動(dòng)生成的測試用例作為應(yīng)用程序的輸入,以發(fā)現(xiàn)應(yīng)用程序中可能存在的安全缺陷,比如緩沖區(qū)溢出.符號(hào)執(zhí)行(symbolic execution)是一種程序分析技術(shù).其可以通過分析程序來得到執(zhí)行特定程序路徑的輸入.在使用符號(hào)執(zhí)行分析一個(gè)程序時(shí),該程序會(huì)使用符號(hào)值作為輸入,而非一般執(zhí)行程序時(shí)使用的具體值.在達(dá)到目標(biāo)代碼時(shí),分析器可以得到相應(yīng)的路徑約束,然后通過約束求解器得到可以觸發(fā)目標(biāo)代碼的具體輸入.這兩種方法都存在一定的局限性.模糊測試方法由于無法意識(shí)到路徑條件,所以,如果遇到窄約束的情況(如兩個(gè)字符串是否相等),則無法高效地覆蓋此路徑[1].相比之下,基于符號(hào)執(zhí)行的測試方法則由于路徑爆炸以及約束求解等問題,雖然能處理窄約束,但卻無法全面、快速地覆蓋程序空間[2](比如較深的程序位置).

目前,有一些針對(duì)基于符號(hào)執(zhí)行的測試和模糊測試相結(jié)合的方法[1-7],這些方法主要都是在其中一種方法遇到瓶頸時(shí)借助另一種方法來克服.例如,Driller[1]是在模糊測試時(shí),當(dāng)遇到特殊邊界條件(比如滿足特定輸入的窄路徑)無法繼續(xù)探索時(shí),則借助符號(hào)執(zhí)行技術(shù)求解該路徑,再將求解出的結(jié)果返回模糊測試.但是,這些方法都存在一個(gè)效率問題,即只能在其中一種方法遇到困難時(shí)才去調(diào)用另一種方法,這樣會(huì)降低效率.

為了解決該效率問題,我們提出名為SmartFuSE(SMART FUzzing and symbolic execution)的基于深度學(xué)習(xí)的、將基于符號(hào)執(zhí)行的測試與模糊測試相結(jié)合的混合測試方法.給定一個(gè)程序,構(gòu)造該程序的路徑的圖表示,通過神經(jīng)網(wǎng)絡(luò)模型預(yù)測路徑是適合模糊測試還是適合符號(hào)執(zhí)行.對(duì)于適合符號(hào)執(zhí)行的路徑集,則制導(dǎo)符號(hào)執(zhí)行,優(yōu)先執(zhí)行該路徑集.對(duì)于適合模糊測試的路徑集,同樣通過制導(dǎo)模糊測試工具嘗試優(yōu)先執(zhí)行該路徑集.同時(shí),我們還提出混合機(jī)制以完成基于符號(hào)執(zhí)行的測試與模糊測試的交互,從而進(jìn)一步提升整體的覆蓋率.我們針對(duì)LAVA-M 中的4 個(gè)程序進(jìn)行測試,實(shí)驗(yàn)結(jié)果表明,我們的方法相對(duì)于單獨(dú)通過模糊測試或符號(hào)執(zhí)行的方法能夠提升20%+的分支覆蓋率,增加約1～13 倍的路徑數(shù)目,多檢測到929 個(gè)缺陷.

總而言之,本文的主要貢獻(xiàn)如下:

· 提出了基于深度學(xué)習(xí)的符號(hào)執(zhí)行與模糊測試的路徑預(yù)測方法;

· 提出了制導(dǎo)的符號(hào)執(zhí)行和制導(dǎo)的模糊測試方法,制導(dǎo)符號(hào)執(zhí)行(或模糊測試)優(yōu)先探索模型預(yù)測出的適合符號(hào)執(zhí)行(或模糊測試)的路徑集;

· 提出了通過結(jié)合基于符號(hào)執(zhí)行的測試和模糊測試的混合測試方法;

· 開發(fā)了原型工具SmartFuSE,通過實(shí)驗(yàn)體現(xiàn)SmartFuSE 的有效性.

本文第1 節(jié)介紹相關(guān)背景,包括符號(hào)執(zhí)行、模糊測試技術(shù)和圖神經(jīng)網(wǎng)絡(luò).第2 節(jié)介紹SmartFuSE 的方法框架.第3 節(jié)介紹如何進(jìn)行數(shù)據(jù)表示和數(shù)據(jù)收集以訓(xùn)練圖神經(jīng)網(wǎng)絡(luò)模型.第4 節(jié)介紹如何基于圖神經(jīng)網(wǎng)絡(luò)模型制導(dǎo)符號(hào)執(zhí)行和模糊測試的混合測試過程.第5 節(jié)介紹工具實(shí)現(xiàn),并通過實(shí)驗(yàn)評(píng)估SmartFuSE 的有效性和性能.第6 節(jié)介紹相關(guān)工作.第7 節(jié)對(duì)本文工作進(jìn)行總結(jié).

1 相關(guān)背景

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

符號(hào)執(zhí)行技術(shù)是一種常用的軟件分析技術(shù),最早是由King 等人于1975 年左右提出[8].目前,KLEE[9]是應(yīng)用得最為廣泛的符號(hào)執(zhí)行引擎之一.符號(hào)執(zhí)行的關(guān)鍵思想就是,用符號(hào)值代替具體值作為輸入,并用符號(hào)表達(dá)式來表示與符號(hào)值相關(guān)的程序變量的值.在遇到程序分支指令時(shí),程序的執(zhí)行也相應(yīng)地搜索每個(gè)分支,分支條件被加入到符號(hào)執(zhí)行保存的程序狀態(tài)的π 中,表示當(dāng)前路徑的約束條件.在收集了路徑約束條件π 之后,使用約束求解器來驗(yàn)證約束的可滿足性,以確定該路徑是否可達(dá).若該路徑約束可解,則說明該路徑是可達(dá)的,將會(huì)繼續(xù)探索該路徑;反之,則說明該路徑不可達(dá),將會(huì)結(jié)束對(duì)該路徑的繼續(xù)探索.

對(duì)于圖1 所示的示例,通過對(duì)main 函數(shù)入口參數(shù)進(jìn)行符號(hào)化,符號(hào)執(zhí)行將符號(hào)地執(zhí)行程序.當(dāng)執(zhí)行到第4 行的if 語句時(shí),符號(hào)執(zhí)行將為兩個(gè)分支各分化出一個(gè)狀態(tài),并在true 分支的狀態(tài)中增加路徑約束x*len==30,在false分支的狀態(tài)中增加路徑約束x*len!=30.這樣,隨著執(zhí)行路徑越來越深,符號(hào)執(zhí)行狀態(tài)中的路徑約束也會(huì)越來越復(fù)雜,約束求解也會(huì)更加耗時(shí).尤其是在執(zhí)行第12 行的循環(huán)語句時(shí),還會(huì)導(dǎo)致狀態(tài)爆炸問題,可能會(huì)導(dǎo)致符號(hào)執(zhí)行無法很好地繼續(xù)深入探索其他路徑空間.

Fig.1 Example program圖1 示例程序

1.2 模糊測試

模糊測試(fuzz testing,簡稱fuzzing)是一種常用的軟件測試技術(shù),最早是由Millor 等人于1988 年提出[10,11],其核心思想是將自動(dòng)或半自動(dòng)生成的隨機(jī)數(shù)據(jù)輸入到一個(gè)程序中,并監(jiān)視程序是否異常,若發(fā)生崩潰、斷言(assertion)失敗,即可發(fā)現(xiàn)可能的程序錯(cuò)誤,比如內(nèi)存泄漏.模糊測試常常用于檢測軟件或計(jì)算機(jī)系統(tǒng)的安全缺陷.模糊測試是一個(gè)自動(dòng)或半自動(dòng)的過程,這個(gè)過程包括反復(fù)操縱目標(biāo)軟件并為其提供處理數(shù)據(jù).模糊測試過程的關(guān)鍵是模糊測試用例的生成方法,用于生成模糊數(shù)據(jù)的工具可稱為模糊器.

AFL(American fuzzy lop)[12]是由安全研究員Zalewski 開發(fā)的一款基于覆蓋引導(dǎo)(coverage-guided)的模糊測試工具,是目前應(yīng)用最為廣泛的模糊測試工具之一.AFL 通過在編譯時(shí)對(duì)代碼進(jìn)行插樁,以記錄代碼覆蓋率.然后對(duì)輸入隊(duì)列中的測試用例按照特定的策略進(jìn)行變異,比如位翻轉(zhuǎn)、字節(jié)拷貝、字節(jié)刪除等操作.如果變異后的輸入可以增加代碼覆蓋,則保留該輸入到輸入隊(duì)列中.上述過程一直重復(fù)進(jìn)行,直到執(zhí)行觸發(fā)到crash,將報(bào)告并記錄相應(yīng)的測試用例.

對(duì)于圖1 所示的示例,AFL 通過模糊測試將能夠在數(shù)秒內(nèi)生成可覆蓋到第5 行代碼的輸入,即if (x*len==30)的true 分支.但是,對(duì)于第10 行代碼,即if (strcmp(s,"abc")==0)的true 分支,AFL 在10 個(gè)小時(shí)內(nèi)都無法生成能夠覆蓋到該代碼的測試輸入.

1.3 圖神經(jīng)網(wǎng)絡(luò)

我們借助圖神經(jīng)網(wǎng)絡(luò)的變種,即門控圖神經(jīng)網(wǎng)絡(luò)(gated graph neural network,簡稱GGNN).GGNN 是一種基于圖神經(jīng)網(wǎng)絡(luò)的模型,它采用與門控遞歸單元(GRU——LSTM 的變種,可以解決遠(yuǎn)距離依賴)類似的門控機(jī)制來擴(kuò)展這些架構(gòu).這允許通過反向傳播過程來學(xué)習(xí)網(wǎng)絡(luò).

我們首先介紹GNN.定義圖G=(V,E,M),V為節(jié)點(diǎn),E為邊,M是向量的集合,即(μv1,…,μvm),其中,μv1是實(shí)數(shù),用于記錄節(jié)點(diǎn)v在圖中的表示.GNN 通過如下傳播規(guī)則更新每個(gè)節(jié)點(diǎn)的表示:

具體而言,節(jié)點(diǎn)v的新的表示是通過整合計(jì)算相鄰節(jié)點(diǎn)的表示(向量形式)而得到的.Nk(v)是與v相連接的,并且邊的類型為k的所有相鄰節(jié)點(diǎn).即Nk(v)={u|(u,v,k)∈ε}∪{u|(v,u,k)∈ε}.隨后,對(duì)?v∈V,重復(fù)該過程L次,以更新uv為多數(shù)GNN 通過為不同類型的邊計(jì)算單獨(dú)的表示,再將這些表示合并得到最終的節(jié)點(diǎn)表示[13].

公式(4)表示初始的情況,即l 為0 并且μv是初始的向量.W1、W2和W3這3 個(gè)矩陣是需要被學(xué)習(xí)的變量,σ1和σ2是非線性激活函數(shù).為了進(jìn)一步提高模型的能力,Li 等人[14]提出了門控圖神經(jīng)網(wǎng)絡(luò)(GGNN),主要差別在于使用了(gated recurrent unit,簡稱GRN)[15]作為公式(1)中h的實(shí)例化.如下兩個(gè)公式解釋了GGNN 是如何工作的.

為了更新節(jié)點(diǎn)v的表示,如公式(5),將會(huì)對(duì)節(jié)點(diǎn)v的所有相鄰節(jié)點(diǎn)N(v)的表示使用f(·)函數(shù)(例如線性函數(shù))并求和計(jì)算得到消息.然后,如公式(6),GRU 基于和當(dāng)前節(jié)點(diǎn)v的表示來計(jì)算下一步新的表示類似地,這個(gè)傳播過程會(huì)重復(fù)一個(gè)特定次數(shù).最后,使用最后一步得到的節(jié)點(diǎn)表示作為這個(gè)節(jié)點(diǎn)的最終表示.

2 SmartFuSE 方法框架

SmartFuSE 框架如圖2 所示,主要分為兩部分:模型訓(xùn)練模塊和混合測試模塊.在模型訓(xùn)練模塊,我們先收集一定的樣本,樣本是路徑的集合和到達(dá)每條路徑時(shí)符號(hào)執(zhí)行和模糊測試分別所需時(shí)間(無法到達(dá)時(shí),時(shí)間為無限大).借助已經(jīng)收集到的樣本信息,SmartFuSE 首先依據(jù)路徑信息對(duì)路徑進(jìn)行編碼,用圖的方式表示該路徑.最后,借助圖神經(jīng)網(wǎng)絡(luò)模型針對(duì)樣本進(jìn)行訓(xùn)練.該模塊的輸出是一個(gè)已經(jīng)訓(xùn)練完畢的模型.

Fig.2 The overall framework of our method圖2 本文方法框架圖

在混合測試模塊,該模塊的輸入是某個(gè)被測程序,針對(duì)該被測程序,由于路徑數(shù)目龐大,我們先只抽取一定深度的路徑,然后在更深處的路徑中只選取部分路徑,以控制需要預(yù)測的路徑數(shù)目.在抽取了路徑之后,針對(duì)分析出的路徑,SmartFuSE 借助模型訓(xùn)練模塊得到的模型預(yù)測每條路徑是符合模糊測試還是符號(hào)執(zhí)行.針對(duì)所有適合模糊測試的路徑,SmartFuSE 制導(dǎo)模糊測試向著這些路徑執(zhí)行.如果適合符號(hào)執(zhí)行,那么SmartFuSE 會(huì)制導(dǎo)符號(hào)執(zhí)行優(yōu)先以這些路徑作為目標(biāo).

由于預(yù)測的不準(zhǔn)確性,會(huì)導(dǎo)致某些適合模糊測試(符號(hào)執(zhí)行)的方法被傳遞給符號(hào)執(zhí)行(模糊測試).所以,為了進(jìn)一步提升性能,SmartFuSE 將預(yù)測出的適合模糊測試(符號(hào)執(zhí)行)的路徑集中,而模糊測試(符號(hào)執(zhí)行)無法覆蓋的路徑傳遞給符號(hào)執(zhí)行(模糊測試),即路徑交換,以嘗試遍歷該路徑,以此進(jìn)一步提升覆蓋率.

3 模型訓(xùn)練

我們將依次介紹樣本數(shù)據(jù)集收集的方式、路徑編碼和GGNN 神經(jīng)網(wǎng)絡(luò).

3.1 數(shù)據(jù)集

在機(jī)器學(xué)習(xí)中,數(shù)據(jù)集占據(jù)著十分重要的地位,如何有效地生成數(shù)據(jù)集是一個(gè)難點(diǎn).一般都會(huì)使用已有的數(shù)據(jù)集,既可以提供基本的數(shù)據(jù),也可以作為評(píng)估實(shí)驗(yàn)效果的基準(zhǔn).但是,當(dāng)前沒有發(fā)現(xiàn)針對(duì)符號(hào)執(zhí)行或模糊測試的數(shù)據(jù)集.

因此,為了收集用于訓(xùn)練模型的數(shù)據(jù),需要在已有的項(xiàng)目上收集、分析數(shù)據(jù).我們將收集的數(shù)據(jù)表示為一個(gè)3 元組:〈Path,SE_Time,Fuzz_Time〉,其中,Path=(l1,l2,…,ln)表示程序中的一條路徑,li(i∈{1,…,n})表示該路徑覆蓋的代碼行,信息包括代碼行所在的文件名以及具體行號(hào).SE_Time是符號(hào)執(zhí)行首次覆蓋路徑Path所需要的時(shí)間.類似地,Fuzz_Time是模糊測試首次覆蓋路徑Path所需要的時(shí)間.如果在指定的時(shí)間內(nèi)某種方法沒有被覆蓋,則對(duì)應(yīng)的覆蓋時(shí)間為正無窮.在無循環(huán)的情況下,一個(gè)Path表示的路徑能夠與其他Path不相關(guān).但是,在有循環(huán)的情況下,循環(huán)體執(zhí)行的次數(shù)會(huì)生成多個(gè)Path,這些路徑由于只有循環(huán)體重復(fù)次數(shù)不同,具有相關(guān)性,并且會(huì)大幅度地增加數(shù)據(jù)集的數(shù)據(jù)量,從而影響其他數(shù)據(jù)的比例.因此,為了解決這個(gè)問題,我們將會(huì)通過一個(gè)配置項(xiàng)來限制具有相關(guān)性的Path的數(shù)目,默認(rèn)為3.

3.2 程序執(zhí)行路徑表示

本文基于抽象語法樹(AST),在控制流和數(shù)據(jù)流之上構(gòu)造程序路徑的表示,并將到達(dá)的路徑染色,以區(qū)分未被覆蓋的路徑.本文使用圖G=〈V,E〉表示一條程序路徑Path的路徑表示圖.每一個(gè)節(jié)點(diǎn)V對(duì)應(yīng)一個(gè)AST 節(jié)點(diǎn),節(jié)點(diǎn)的類型包括FunctionDecl、UnaryOperator、BinaryOperator、IfStmt、ForStmt、WhileStmt 等.每一條邊E表示節(jié)點(diǎn)之間的關(guān)系,所有邊的類型包括:AST 邊、控制流邊、數(shù)據(jù)依賴邊和路徑標(biāo)識(shí)邊.控制流邊即控制流圖(CFG)中的邊.針對(duì)控制流邊的表示,SmartFuSE 依據(jù)執(zhí)行路徑,抽取該路徑下的函數(shù)調(diào)用關(guān)系.再依據(jù)該調(diào)用關(guān)系分析每個(gè)函數(shù)的控制流圖.依據(jù)函數(shù)調(diào)用關(guān)系連接這些控制流圖會(huì)得到一個(gè)整體的控制流圖,該控制流圖稱為函數(shù)間控制流圖(ICFG).隨后,SmartFuSE 進(jìn)一步在函數(shù)間控制流圖上分析數(shù)據(jù)依賴關(guān)系.針對(duì)其中的每一個(gè)變量,SmartFuSE 都會(huì)增加與該變量的數(shù)據(jù)依賴邊.這些依賴關(guān)系在函數(shù)間控制流圖上是通過額外的邊表達(dá)出來的.除此之外,我們引入路徑標(biāo)識(shí)邊,用于表示該路徑具體執(zhí)行了哪些語句.如果路徑標(biāo)識(shí)邊和控制流邊同時(shí)存在,則只保留路徑標(biāo)識(shí)邊,用于表示執(zhí)行路徑的染色信息.

程序路徑的圖表示構(gòu)造過程如算法1 所示.首先,基于AST 構(gòu)造函數(shù)間控制流圖ICFG(行1),然后在ICFG上分析數(shù)據(jù)依賴關(guān)系[16],并加入數(shù)據(jù)依賴邊,構(gòu)成新的圖DF-ICFG(行2).之后,除Path中的l1之外,針對(duì)Path中的每一個(gè)行號(hào)l,抽取對(duì)應(yīng)的控制流節(jié)點(diǎn)bb,其前一行prevLine的控制流節(jié)點(diǎn)為prevbb,將在DF-ICFG 中增加從prevbb到bb的路徑標(biāo)識(shí)邊(行4～行12).最后,通過trimGraph 只保留包含路徑標(biāo)識(shí)邊的CFG,否則,在ICFG 中刪除對(duì)應(yīng)的CFG,得到最終的程序路徑Path的圖表示PathGraph(行13).

算法1.程序路徑的圖表示構(gòu)造算法.

函數(shù):buildPathGraph(Path,AST)

輸入:Path,AST;

輸出:PathGraph.

如下文的圖3 即為圖1 示例程序中的函數(shù)foo 中某一條執(zhí)行路徑(覆蓋的代碼行為〈4,8,9,12,15,16〉)的路徑表示,其中的節(jié)點(diǎn)對(duì)應(yīng)于AST 節(jié)點(diǎn),不帶箭頭的邊為AST 中的邊,實(shí)線箭頭的邊表示控制流邊,紅色實(shí)線空心箭頭的邊表示路徑標(biāo)識(shí)邊,綠色虛線箭頭的邊表示數(shù)據(jù)依賴邊.

4 混合測試

混合測試模塊分為3 部分:路徑抽取和路徑分類、制導(dǎo)的符號(hào)執(zhí)行以及制導(dǎo)的模糊測試.

4.1 路徑抽取和路徑分類

由于程序路徑數(shù)目往往極大,無法窮盡所有路徑.所以,為了效率起見,SmartFuSE 選擇抽取程序的部分路徑.如算法2 所示,SmartFuSE 依據(jù)預(yù)先設(shè)定的路徑深度depth,使用extractPathsByStmtCov 策略遍歷所有到達(dá)該深度的路徑(行6～行7).extractPathsByStmtCov 表示通過隨機(jī)選擇語句的方式抽取能夠達(dá)到語句覆蓋的路徑集合.但是,某個(gè)特定深度路徑下的路徑,其更深的路徑信息也會(huì)有重要的參考價(jià)值.所以,針對(duì)每一條到達(dá)特定深度的路徑,SmartFuSE 分析更深路徑下的路徑,但會(huì)降低抽取路徑的要求,以減少抽取的路徑數(shù)目.

這里采用extractPathsByBranchCov 策略,即通過隨機(jī)選擇分支的方式抽取能夠達(dá)到分支覆蓋的路徑集合(行9).

通過路徑抽取,得到路徑集合.然后將按照算法1,對(duì)集合中的每一條路徑構(gòu)造圖表示.針對(duì)抽取出的路徑的圖表示,SmartFuSE 將用訓(xùn)練完畢的模型預(yù)測這些圖,預(yù)測的路徑分?jǐn)?shù)以二元組(X,Y)表示,X表示適合模糊測試的分?jǐn)?shù),而Y表示適合符號(hào)執(zhí)行的分?jǐn)?shù),兩者之和等于1.我們定義3 種路徑分類結(jié)果,適合模糊測試(X＞Y)、適合符號(hào)執(zhí)行(X＜Y)和不確定(X≈Y).不確定是指X和Y的值相差很小(如小于0.05).如果適合某種方法,則將該路徑信息傳遞給這種方法.如果是不確定,則同時(shí)傳遞給兩種方法.我們將分類為適合符號(hào)執(zhí)行的路徑構(gòu)成路徑集SEPathSet,將分類為適合模糊測試的路徑構(gòu)成路徑集FuzzPathSet.

Fig.3 Example of path representation圖3 路徑表示示例

算法2 .路徑抽取算法.

函數(shù):extractPaths(AST,depth)

輸入:AST,depth;

輸出:PS(Path set).

4.2 制導(dǎo)的符號(hào)執(zhí)行

在預(yù)測出適合符號(hào)執(zhí)行的路徑集SEPathSet 后,SmartFuSE 將制導(dǎo)符號(hào)執(zhí)行優(yōu)先探索該路徑集.其核心思路是在傳統(tǒng)的符號(hào)執(zhí)行基礎(chǔ)之上,增加路徑集作為輸入,為與這些目標(biāo)路徑相關(guān)的執(zhí)行狀態(tài)賦予更高的優(yōu)先級(jí),以此達(dá)到優(yōu)先探索分析目標(biāo)路徑的目的.

如算法3 所示,制導(dǎo)的符號(hào)執(zhí)行將路徑抽取和路徑分類預(yù)測得到的適合符號(hào)執(zhí)行的路徑集SEPathSet 作為輸入.每次符號(hào)執(zhí)行從狀態(tài)池中選擇一個(gè)優(yōu)先級(jí)最高的狀態(tài)進(jìn)行執(zhí)行,如果狀態(tài)池中的所有狀態(tài)優(yōu)先級(jí)都相同,則按照符號(hào)執(zhí)行引擎中的搜索策略(比如DFS、BFS、random path、random state 等)選擇狀態(tài)(GuidedSymbolicExecution⑥).在執(zhí)行到分支語句時(shí)(ExecuteInstruction①),復(fù)制狀態(tài)賦給兩個(gè)分支(ExecuteInstruction②-⑤),并更新兩個(gè)狀態(tài)的優(yōu)先級(jí)(ExecuteInstruction⑥-⑦).即對(duì)于每一個(gè)狀態(tài),判斷其基本塊的第1 條語句是否在路徑集SEPathSet 中,如果該分支在路徑集中,則提升其對(duì)應(yīng)的執(zhí)行狀態(tài)的優(yōu)先級(jí)(UpdatePrioriy①②).

算法3.符號(hào)執(zhí)行制導(dǎo)算法.

函數(shù):GuidedSymbolicExecution()

輸入:SEPathSet;

4.3 制導(dǎo)的模糊測試

同樣,在預(yù)測出適合模糊測試的路徑集FuzzPathSet 后,SmartFuSE 將制導(dǎo)模糊測試優(yōu)先探索該路徑集.其核心思想是,程序中FuzzPathSet 的路徑經(jīng)過次數(shù)越多的節(jié)點(diǎn),擁有更高的權(quán)重;通過對(duì)新產(chǎn)生的測試用例經(jīng)過的路徑節(jié)點(diǎn)計(jì)算總權(quán)重可知,總權(quán)重越高,優(yōu)先級(jí)就越高.模糊測試每次選擇優(yōu)先級(jí)最高的測試用例作為輸入進(jìn)行下一輪的模糊測試.

具體制導(dǎo)過程如算法4 所示,制導(dǎo)的模糊測試以目標(biāo)路徑的集合FuzzPathSet 作為輸入.首先,SmartFuSE 將會(huì)為程序中每一個(gè)節(jié)點(diǎn)計(jì)算權(quán)重(GuidedFuzzing①),將每一個(gè)節(jié)點(diǎn)的權(quán)重初始化為0,然后對(duì)于每一個(gè)節(jié)點(diǎn)V,若FuzzPathSet 經(jīng)過該節(jié)點(diǎn)的路徑數(shù)目為N,則節(jié)點(diǎn)V的權(quán)重為N(initWeight①～⑧).然后為測試輸入列表Seeds中的每一個(gè)種子seed 計(jì)算其優(yōu)先級(jí)(GuidedFuzzing③～④),首先獲取原模糊測試工具為該種子計(jì)算的優(yōu)先級(jí),并把該值標(biāo)準(zhǔn)化到[0,1]區(qū)間的值(記為v)作為FuzzPathSet 中seed 的初始優(yōu)先級(jí)(computePriority①);然后在v的基礎(chǔ)上,增加該種子經(jīng)過路徑上的節(jié)點(diǎn)的權(quán)重之和,作為該種子的最終優(yōu)先級(jí)(computePriority②～⑤).這樣可以制導(dǎo)模糊測試優(yōu)先探索FuzzPathSet 的路徑,當(dāng)FuzzPathSet 中的路徑探索完之后就會(huì)按照原模糊測試工具計(jì)算的優(yōu)先級(jí)選擇種子進(jìn)行后續(xù)的模糊測試.在計(jì)算得到測試輸入列表Seeds 中的每一個(gè)種子的優(yōu)先級(jí)后,選取優(yōu)先級(jí)最高的種子selectedSeed(GuidedFuzzing⑥),對(duì)selectedSeed 進(jìn)行變異操作得到新的測試輸入newSeed(GuidedFuzzing⑦),并將selectedSeed 從Seeds 中移除(GuidedFuzzing⑧).隨后執(zhí)行新的測試輸入newSeed,如果newSeed 可以覆蓋新的代碼分支,則將newSeed 加入到測試輸入列表Seeds 中(GuidedFuzzing⑨～?).同時(shí),如果newSeed經(jīng)過的路徑在FuzzPathSet 中,則將該路徑上的所有節(jié)點(diǎn)的權(quán)重減1(GuidedFuzzing).這樣可以不再重復(fù)制導(dǎo)模糊測試去探索FuzzPathSet 中已經(jīng)覆蓋過的路徑.當(dāng)程序中所有節(jié)點(diǎn)的權(quán)重都減少到0 時(shí),意味著已經(jīng)完成了FuzzPathSet 中所有路徑的覆蓋.此后,根據(jù)computePriority 中的算法,將使用原模糊測試工具計(jì)算的優(yōu)先級(jí)選擇種子進(jìn)行后續(xù)的模糊測試,即嘗試覆蓋SmartFuSE 尚未覆蓋到的新的代碼和分支.

算法4.模糊測試制導(dǎo)算法.

函數(shù):GuidedFuzzing

輸入:P,FuzzPathSet,Seeds;

基層黨組織功能的轉(zhuǎn)變過程，實(shí)質(zhì)上是我們黨由革命黨向執(zhí)政黨轉(zhuǎn)變的探索過程。這個(gè)過程始終處于動(dòng)態(tài)，并充滿復(fù)雜性和曲折性。正如有學(xué)者認(rèn)為的那樣，“新的歷史條件下我們黨正在進(jìn)行的執(zhí)政黨建設(shè)探索，無論在規(guī)模上，在任務(wù)的艱巨性上，還是在意義上，都不亞于革命斗爭時(shí)期的黨的建設(shè)，是一項(xiàng)名副其實(shí)的‘新的偉大工程’”［4］29。中國共產(chǎn)黨由革命黨向執(zhí)政黨的轉(zhuǎn)變，對(duì)機(jī)關(guān)黨組織功能上也產(chǎn)生了新的挑戰(zhàn)。這種挑戰(zhàn)，根源在于作為執(zhí)政黨，黨的領(lǐng)導(dǎo)方式和執(zhí)政方式發(fā)生變化的基礎(chǔ)上，黨的基層組織的功能定位也在發(fā)生變化。

4.4 混合機(jī)制

一方面,模型的預(yù)測準(zhǔn)確率一般都不會(huì)是100%的準(zhǔn)確率,為了容忍路徑分類預(yù)測錯(cuò)誤的情況,SmartFuSE 會(huì)在符號(hào)執(zhí)行或模糊測試無法產(chǎn)生新的分支覆蓋的時(shí)間超過指定的時(shí)間時(shí),將沒有覆蓋的路徑從自身的制導(dǎo)路徑集中(SEPathSet/FuzzPathSet)移除并傳遞給另一方,再進(jìn)行一次制導(dǎo),以此進(jìn)一步提升覆蓋率.另一方面,如果僅僅通過路徑預(yù)測獲得適合符號(hào)執(zhí)行(或模糊測試)并制導(dǎo)符號(hào)執(zhí)行(或模糊測試),該制導(dǎo)策略更多的是能夠快速提升符號(hào)執(zhí)行(或模糊測試)對(duì)適合符號(hào)執(zhí)行(或模糊測試)的代碼的路徑覆蓋.這種制導(dǎo)策略無法應(yīng)對(duì)符號(hào)執(zhí)行和模糊測試都很難覆蓋到的路徑.因此,我們將符號(hào)執(zhí)行生成的所有測試用例也傳遞給模糊測試,讓模糊測試能夠在這些輸入的基礎(chǔ)上,變異出新的輸入,以此嘗試覆蓋之前符號(hào)執(zhí)行和模糊測試都很難覆蓋到的路徑.

同時(shí),對(duì)于模糊測試已經(jīng)覆蓋到的路徑,也被傳遞給符號(hào)執(zhí)行,當(dāng)符號(hào)在執(zhí)行過程中再次探索到這些路徑時(shí),可以選擇不再進(jìn)行耗時(shí)的約束求解,而將更多的時(shí)間用于探索其他路徑.

5 實(shí)現(xiàn)與實(shí)驗(yàn)

5.1 實(shí)現(xiàn)與實(shí)驗(yàn)設(shè)置

本文實(shí)現(xiàn)了混合測試工具SmartFuSE,整體框架主要通過Python 實(shí)現(xiàn),其中使用Tensorflow 1.4 建立GGNN的模型,在KLEE 和AFL 的基礎(chǔ)之上修改成制導(dǎo)的符號(hào)執(zhí)行和模糊測試方法.

本文選擇了模糊測試常用測試對(duì)象LAVA-M[17]項(xiàng)目中的程序,即base64、md5sum、uniq 和who,這些程序中被插入了大量難以檢測的缺陷.我們在LAVA-M 程序上測試了工具SmartFuSE 的有效性,通過實(shí)驗(yàn)嘗試回答以下問題.

RQ1:SmartFuSE 中通過路徑分類預(yù)測模型預(yù)測的路徑,制導(dǎo)符號(hào)執(zhí)行、模糊測試的效果如何?

RQ2:SmartFuSE 中的路徑分類制導(dǎo)和混合機(jī)制對(duì)模糊測試的優(yōu)化效果如何?

RQ3:SmartFuSE 與其他混合測試、模糊測試工具相比,檢測缺陷的效果如何?

5.2 實(shí)驗(yàn)結(jié)果

為了驗(yàn)證SmartFuSE 路徑分類預(yù)測模型預(yù)測的準(zhǔn)確性,我們收集了bzip2-1.0.6 在KLEE、AFL 上分別運(yùn)行2小時(shí)執(zhí)行的路徑,并記錄了產(chǎn)生覆蓋該路徑的測試用例所需時(shí)間,然后與SmartFuSE 路徑分類預(yù)測模型預(yù)測的路徑分類結(jié)果進(jìn)行比對(duì),發(fā)現(xiàn)SmartFuSE 路徑分類預(yù)測模型預(yù)測的準(zhǔn)確率為84.7%.

5.2.1 LAVA-M 程序上通過路徑分類預(yù)測模型預(yù)測的路徑,制導(dǎo)符號(hào)執(zhí)行、模糊測試的代碼覆蓋能力的比較(RQ1)

如表1 所示,我們分別統(tǒng)計(jì)了在LAVA-M 的4 個(gè)程序上,KLEE 和制導(dǎo)的KLEE 的語句覆蓋率、分支覆蓋率和路徑數(shù)目.從語句覆蓋率來看,制導(dǎo)的KLEE 相比KLEE 多覆蓋了1.5%的代碼.從分支覆蓋率來看,制導(dǎo)的KLEE 比KLEE 多覆蓋了2.7%的分支.而在路徑覆蓋方面,制導(dǎo)的KLEE 相比KLEE 增加了5.5 倍.表中KLEE的路徑數(shù)目只統(tǒng)計(jì)其生成的測試用例能夠覆蓋的路徑數(shù)目,可以看出,KLEE 由于約束求解等操作非常耗時(shí),無法像AFL 那樣僅通過變異就能產(chǎn)生大量的測試用例.通過SmartFuSE 路徑分類預(yù)測模型預(yù)測的適合KLEE 的路徑來制導(dǎo)KLEE,可以有效提高KLEE 的代碼覆蓋率.

如表2 所示,我們分別統(tǒng)計(jì)了在LAVA-M 的4 個(gè)程序上,AFL 和制導(dǎo)的AFL 的語句覆蓋率、分支覆蓋率和路徑數(shù)目.從語句覆蓋率來看,制導(dǎo)的AFL 相比AFL 沒有顯著增加.從分支覆蓋率來看,制導(dǎo)的AFL 比AFL 多覆蓋了3%的分支.而在路徑覆蓋方面,制導(dǎo)的AFL 相比AFL 增加了0.4 倍.

Table 1 Coverage information of KLEE and guided KLEE on LAVA-M表1 LAVA-M 上KLEE 和制導(dǎo)的KLEE 的覆蓋統(tǒng)計(jì)

Table 2 Coverage information of AFL and guided AFL on LAVA-M表2 LAVA-M 上AFL 和制導(dǎo)的AFL 的覆蓋統(tǒng)計(jì)

5.2.2 SmartFuSE 中的路徑分類制導(dǎo)和混合機(jī)制對(duì)模糊測試的優(yōu)化效果(RQ2)

如表3 所示,我們分別統(tǒng)計(jì)了在LAVA-M 的4 個(gè)程序上,KLEE、AFL 和SmartFuSE 的語句覆蓋率、分支覆蓋率和路徑數(shù)目.從語句覆蓋率來看,SmartFuSE 相比單獨(dú)的KLEE、AFL 增長得不是很明顯,總體上,SmartFuSE比KLEE 多覆蓋了3.4%的代碼,比AFL 多覆蓋了2.8%的代碼.從分支覆蓋率來看,SmartFuSE 比KLEE 多覆蓋了26.9%的分支,比AFL 多覆蓋了20.7%的分支.而在路徑覆蓋方面,SmartFuSE 則明顯比KLEE、AFL 能夠覆蓋更多的路徑,路徑覆蓋數(shù)目相比KLEE 增加了13.5 倍,相比AFL 增加了0.9 倍.

Table 3 Coverage information on LAVA-M表3 LAVA-M 上的覆蓋統(tǒng)計(jì)

接下來,我們進(jìn)一步分析SmartFuSE 的缺陷檢測能力.如圖4 所示,在LAVA-M 的每個(gè)程序中,除了程序中已有的缺陷外,還被人工植入了若干缺陷,其中,base64 中植入44 個(gè)、md5sum 中植入57 個(gè),uniq 中植入28 個(gè),who中植入2 136 個(gè)缺陷.

Fig.4 The number of crashes detected by SmartFuSE,AFL and KLEE on LAVA-M圖4 SmartFuSE,AFL and KLEE 在LAVA-M 程序集上檢測到的缺陷數(shù)目結(jié)果

通過對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析可以發(fā)現(xiàn),SmartFuSE 在LAVA-M 程序集上的缺陷檢測能力相比KLEE 和AFL有了很大的提升.單獨(dú)的KLEE 執(zhí)行24 小時(shí),未能在LAVA-M 任一程序中發(fā)現(xiàn)缺陷.單獨(dú)的AFL 執(zhí)行24 小時(shí)僅能檢測1～2 個(gè)缺陷.我們分析其原因應(yīng)該是:KLEE 雖然有較好的語句覆蓋率,但其僅覆蓋了很少數(shù)目的路徑,所以未能檢測到缺陷;AFL 由于比較依賴于好的測試輸入,實(shí)驗(yàn)中僅為AFL 提供了LAVA-M 中給出的測試輸入,AFL 基于較少的種子難以變異出豐富的測試用例.而通過簡單的AFL+KLEE,即在AFL 和KLEE 同時(shí)執(zhí)行24小時(shí)的過程中,將KLEE 的測試用例傳遞給AFL,可以在who 程序中檢測到74 個(gè)缺陷.這也說明,KLEE 能夠覆蓋AFL 不同的代碼空間,將KLEE 的測試用例傳遞給AFL,可以幫助AFL 探索新的代碼空間.但是,AFL+KLEE檢測缺陷的能力相對(duì)還是較差.SmartFuSE(unguided)通過進(jìn)一步在AFL+KLEE 的基礎(chǔ)上引入混合機(jī)制進(jìn)行優(yōu)化,讓AFL 優(yōu)先變異KLEE 傳遞過來具有新的分支覆蓋的種子,讓KLEE 對(duì)AFL 已經(jīng)覆蓋的路徑不再約束求解產(chǎn)生重復(fù)的測試用例.從圖4 可以看出,SmartFuSE(unguided)相比簡單的AFL+KLEE 可以多檢測到500 多個(gè)缺陷.這也顯示出本文的混合機(jī)制可以優(yōu)化AFL 和KLEE 的執(zhí)行效果.進(jìn)一步地,SmartFuSE 在SmartFuSE(unguided)的基礎(chǔ)上,增加了通過路徑分類預(yù)測模型預(yù)測的路徑,制導(dǎo)符號(hào)執(zhí)行、模糊測試,同時(shí)針對(duì)預(yù)測錯(cuò)誤的情況所做的處理等.從圖4 可以發(fā)現(xiàn),SmartFuSE 執(zhí)行24 小時(shí),在base64 中不僅發(fā)現(xiàn)了人工植入的所有44 個(gè)缺陷,另外還檢測到了11 個(gè)缺陷;在uniq 中發(fā)現(xiàn)了18 個(gè)缺陷;在who 中發(fā)現(xiàn)了856 個(gè)缺陷,總共發(fā)現(xiàn)了929 個(gè)缺陷.md5sum 程序中,SmartFuSE 未能檢測到任何缺陷,我們調(diào)查后發(fā)現(xiàn)這是由于該程序中的哈希運(yùn)算所致[2].總之,通過圖4 可以看出,本文提出的路徑分類制導(dǎo)和混合機(jī)制可以幫助KLEE 和AFL 發(fā)現(xiàn)更多的程序缺陷.

5.2.3 SmartFuSE 與其他混合測試、模糊測試工具的比較(RQ3)

由于我們在使用Driller(shellphuzz)的過程中出現(xiàn)了部分執(zhí)行錯(cuò)誤,可能會(huì)影響其測試結(jié)果,因此,我們還參考PANGOLIN[19]工作中的實(shí)驗(yàn)結(jié)果,對(duì)比了SmartFuSE 與已有的一些混合測試和模糊測試工具的效果.這里,AFL 的實(shí)驗(yàn)結(jié)果使用2 個(gè)AFL 進(jìn)程完成,而上文中的AFL 實(shí)驗(yàn)結(jié)果使用1 個(gè)AFL 進(jìn)程完成.如圖5 所示,展示了混合模糊測試工具PANGOLIN、QSYM[5]、Driller 和SmartFuSE 以及模糊測試工具AFL、AFLFast[21]、Angora[22]和T-Fuzz[23]24 小時(shí)內(nèi)在LAVA-M 程序集上檢測到的缺陷數(shù)目.從圖5 中可以看出,在base64 程序中SmartFuSE 發(fā)現(xiàn)的缺陷數(shù)目最多,而在另外3 個(gè)程序中SmartFuSE 檢測到的缺陷數(shù)目處于中等水平.在4 個(gè)項(xiàng)目中,SmartFuSE 都能夠比AFL、Driller 檢測到更多的缺陷.我們將在相關(guān)工作中討論這幾個(gè)工具的特性.

Fig.5 The number of crashes detected by several fuzzing and hybrid tools on LAVA-M圖5 幾個(gè)模糊測試和混合測試工具在LAVA-M 程序集上檢測到的缺陷數(shù)目結(jié)果

5.3 實(shí)驗(yàn)討論

通過對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析可以發(fā)現(xiàn),SmartFuSE 在LAVA-M 程序集上的缺陷檢測能力相比KLEE、AFL 有了很大的提升.我們進(jìn)一步對(duì)SmartFuSE 模糊測試中產(chǎn)生的能夠觸發(fā)缺陷的測試用例進(jìn)行了分析,發(fā)現(xiàn)有很多測試用例正是在SmartFuSE 符號(hào)執(zhí)行模塊產(chǎn)生的測試用例的基礎(chǔ)上不斷進(jìn)行變異操作后得到的新的測試用例.同時(shí),SmartFuSE 通過制導(dǎo)符號(hào)執(zhí)行,可以使其更快地探索適合符號(hào)執(zhí)行的路徑,并生成更多的測試用例;符號(hào)執(zhí)行階段為模糊測試階段提供更多測試用例,幫助模糊測試突破其不太容易覆蓋的路徑,生成具有更高代碼覆蓋的測試用例,進(jìn)而檢測到更多的程序缺陷.這也證明了我們的基于符號(hào)執(zhí)行的測試和模糊測試的混合機(jī)制確實(shí)可以幫助SmartFuSE 更快地覆蓋到符號(hào)執(zhí)行和模糊測試都很難覆蓋到的程序路徑,使得SmartFuSE 工具的缺陷檢測能力相比單獨(dú)的符號(hào)執(zhí)行或者模糊測試都更強(qiáng)、更有效.

可能影響工具效果的因素包括:(1) 數(shù)據(jù)集的豐富性,將會(huì)影響SmartFuSE 路徑分類預(yù)測模型的準(zhǔn)確性,也將影響工具的實(shí)用性.訓(xùn)練神經(jīng)網(wǎng)絡(luò)需要大量的數(shù)據(jù)集,而目前沒有相關(guān)的已有的數(shù)據(jù)集能夠直接供我們使用.所以在實(shí)驗(yàn)中為了降低對(duì)數(shù)據(jù)集數(shù)目的要求,我們選取中小規(guī)模的程序來生成數(shù)據(jù)集.因?yàn)檫@些程序已被KLEE 廣泛使用,KLEE 容易生成測試用例.相比之下,大規(guī)模程序中,KLEE 執(zhí)行這些程序并求解約束生成測試用例所需時(shí)間和內(nèi)存開銷極大,短時(shí)間內(nèi)無法收集足夠的數(shù)據(jù)集,這也是我們后續(xù)工作中需要解決的問題.另外,預(yù)測模型可能在訓(xùn)練集程序上有較好的預(yù)測準(zhǔn)確性,但在其他程序上沒有滿意的預(yù)測效果.(2) SmartFuSE 路徑分類預(yù)測模型的準(zhǔn)確性,將會(huì)影響SmartFuSE 混合測試的執(zhí)行效率.模型的預(yù)測準(zhǔn)確率一般都不會(huì)是100%的準(zhǔn)確率.路徑分類預(yù)測錯(cuò)誤將會(huì)導(dǎo)致SmartFuSE 制導(dǎo)符號(hào)執(zhí)行(模糊測試)模塊去探索并不適合該模塊的路徑.為了降低錯(cuò)誤的路徑分類預(yù)測帶來的不良影響,我們通過設(shè)置制導(dǎo)的時(shí)間閾值,當(dāng)一定時(shí)間無法制導(dǎo)符號(hào)執(zhí)行(模糊測試)覆蓋該路徑時(shí),將嘗試讓模糊測試(符號(hào)執(zhí)行)來覆蓋該路徑.(3) 時(shí)間閾值的設(shè)置會(huì)影響執(zhí)行的效果.過大,會(huì)導(dǎo)致錯(cuò)誤預(yù)測的嘗試時(shí)間過長;過小,又會(huì)導(dǎo)致正確的預(yù)測(如預(yù)測為適合符號(hào)執(zhí)行)被不適合的方法(如模糊測試)嘗試,從而無法覆蓋對(duì)應(yīng)路徑.

6 相關(guān)工作

我們主要從符號(hào)執(zhí)行、模糊測試以及符號(hào)執(zhí)行與模糊測試結(jié)合的混合測試技術(shù)這3 個(gè)方面介紹相關(guān)工作.

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

符號(hào)執(zhí)行技術(shù)是一種常用的軟件分析技術(shù),但是傳統(tǒng)的符號(hào)執(zhí)行方法面臨著路徑爆炸、環(huán)境交互、系統(tǒng)調(diào)用和約束求解等問題[24],因此有許多針對(duì)符號(hào)執(zhí)行的優(yōu)化技術(shù)被提出.

為了應(yīng)對(duì)環(huán)境交互和系統(tǒng)調(diào)用等問題,KLEE[9]、AEG[25]都為系統(tǒng)調(diào)用建立了抽象模型,以支持符號(hào)化文件、套接字等作為符號(hào)執(zhí)行的輸入.而選擇性符號(hào)執(zhí)行(selective symbolic execution),比如S2E[26]基于KLEE 和QEMU 虛擬機(jī),通過將具體值的單路徑執(zhí)行和符號(hào)值的多路徑執(zhí)行同時(shí)進(jìn)行,以支持在程序中目標(biāo)代碼進(jìn)行符號(hào)執(zhí)行,在調(diào)用系統(tǒng)內(nèi)核函數(shù)時(shí)進(jìn)行具體執(zhí)行,以實(shí)現(xiàn)符號(hào)執(zhí)行過程與具體執(zhí)行過程之間的無縫切換.

為了應(yīng)對(duì)路徑爆炸問題,許多研究工作提出了不同的解決方法.一類工作提出了路徑選擇的優(yōu)化算法[9,25,27-30],即符號(hào)執(zhí)行搜索策略.例如,KLEE 中就提供了多種路徑搜索策略,包括深度優(yōu)先搜索策略(DFS)、廣度優(yōu)先搜索策略(BFS)、隨機(jī)狀態(tài)搜索策略、隨機(jī)路徑搜索策略等.一類工作提出使用函數(shù)摘要技術(shù)[31-33]和循環(huán)摘要技術(shù)[34,35],通過復(fù)用已經(jīng)探索過的代碼的執(zhí)行信息,避免對(duì)同一代碼的重復(fù)執(zhí)行,來提高符號(hào)執(zhí)行效率.還有一類工作提出通過狀態(tài)合并[36,37],即將幾條路徑合并成一個(gè)狀態(tài),以有效地減少需要遍歷的路徑.但是狀態(tài)合并會(huì)導(dǎo)致路徑約束更加復(fù)雜,增大了約束求解的難度.還有一些工作通過與其他程序分析技術(shù)相結(jié)合[38-42],比如程序切片、污點(diǎn)分析、類型檢查和編譯優(yōu)化等技術(shù),修剪掉不感興趣的路徑,使得符號(hào)執(zhí)行著重分析更容易發(fā)現(xiàn)程序錯(cuò)誤和缺陷的代碼空間.

對(duì)于約束求解問題,Z3[43]作為當(dāng)前主流的SMT 約束求解器,在符號(hào)執(zhí)行引擎中,比如KLEE、Mayhem[39]、Angr[44],得到了廣泛應(yīng)用.同時(shí),EXE[45]、KLEE、AEG 還使用了STP[46]約束求解器.另外,符號(hào)執(zhí)行引擎中也針對(duì)約束求解進(jìn)行了優(yōu)化設(shè)計(jì).比如,在EXE、KLEE、S2E 中通過對(duì)收集到的約束進(jìn)行化簡來降低約束的復(fù)雜度.EXE、KLEE、Memoise[47]、GreenTrie[48]等符號(hào)執(zhí)行引擎中還會(huì)對(duì)約束求解的結(jié)果進(jìn)行緩存從而減少對(duì)求解器的調(diào)用.

我們的方法通過將基于符號(hào)執(zhí)行的測試與模糊測試相結(jié)合,也可以幫助應(yīng)對(duì)符號(hào)執(zhí)行面臨的環(huán)境交互和約束求解等問題.

6.2 模糊測試

模糊測試技術(shù)有基于白盒、基于黑盒和基于灰盒之分[49].黑盒模糊測試不會(huì)分析程序本身,而是基于預(yù)設(shè)的規(guī)則來變異和生成新的種子,比如基于遺傳算法的模糊測試通過位翻轉(zhuǎn)、字節(jié)拷貝、字節(jié)刪除等操作變異出新的輸入;基于語法的模糊測試則依據(jù)語法規(guī)則自動(dòng)生成新的種子[50].相比之下,白盒模糊測試會(huì)分析程序本身的信息,包括控制流、數(shù)據(jù)流等.白盒模糊測試最早是由Godefroid 等人提出來的[51,52],該方法提出的工具SAGE通過在實(shí)際執(zhí)行具體輸入時(shí)收集路徑約束,然后基于代碼覆蓋最大化準(zhǔn)則,將約束系統(tǒng)地取反后求解,生成新的測試輸入,繼續(xù)進(jìn)行模糊測試.灰盒模糊測試介于黑盒模糊測試和白盒模糊測試之間,該技術(shù)常常用到代碼插樁技術(shù)[53,54]、污點(diǎn)分析技術(shù)[55]等.

為了提升模糊測試的代碼覆蓋能力和執(zhí)行效率,許多研究工作提出了改進(jìn)方法.BuzzFuzz[56]使用動(dòng)態(tài)污點(diǎn)分析識(shí)別輸入中與目標(biāo)缺陷點(diǎn)相關(guān)的部分,并變異生成新的測試輸入.AFLFast[21]通過構(gòu)建馬爾可夫鏈模型評(píng)估種子,為能夠覆蓋到低頻路徑的測試輸入賦予更高的優(yōu)先級(jí)和更長的變異時(shí)間.為了使模糊測試更快地覆蓋到給定的目標(biāo)位置,AFLgo[57]提出制導(dǎo)的模糊測試,通過計(jì)算種子到目標(biāo)點(diǎn)的距離,然后使用馬爾可夫鏈蒙特卡羅(MCMC)優(yōu)化技術(shù)選取離目標(biāo)點(diǎn)更近的種子賦予其更高的優(yōu)先級(jí)和更長的變異時(shí)間.Vuzzer[58]通過動(dòng)態(tài)污點(diǎn)分析定位出輸入中的魔法字節(jié)(magic bytes),然后對(duì)魔法字節(jié)進(jìn)行變異來生成新的輸入.Steelix[59]則提出使用輕量級(jí)的靜態(tài)分析和二進(jìn)制插樁來定位輸入中的魔法字節(jié).Neuzz[60]使用神經(jīng)網(wǎng)絡(luò)模型學(xué)習(xí)出程序中分支行為的平滑近似,并基于梯度制導(dǎo)策略對(duì)測試用例進(jìn)行變異,從而平滑模糊測試搜索過程.Skyfire[61]提出了一種數(shù)據(jù)驅(qū)動(dòng)的種子生成方法,該方法根據(jù)已有的大量測試輸入學(xué)習(xí)出輸入的語法和語義信息,據(jù)此可以為具有高結(jié)構(gòu)化輸入的被測程序生成模糊測試的輸入.為了不使用符號(hào)執(zhí)行就能對(duì)路徑約束進(jìn)行求解,Angora[22]提出了字節(jié)級(jí)污點(diǎn)分析,并使用梯度下降方法快速找到滿足復(fù)雜路徑約束的解,從而為模糊測試得到新的輸入.T-Fuzz[23]通過對(duì)TTCN-3 模型進(jìn)行建模,提出針對(duì)通信協(xié)議的模糊測試工具.

6.3 基于符號(hào)執(zhí)行的測試與模糊測試結(jié)合的混合測試

Driller[1]針對(duì)二進(jìn)制代碼,在模糊測試(AFL)的基礎(chǔ)上結(jié)合了混合執(zhí)行引擎Angr,當(dāng)模糊測試遇到一些特殊邊界條件(比如滿足特定輸入的窄路徑)無法繼續(xù)探索時(shí),將會(huì)啟用二進(jìn)制混合測試模塊(Angr).該模塊通過約束求解生成能夠突破這些限制的新輸入,并將輸入返回給模糊測試作為種子,使得模糊測試可以繼續(xù)執(zhí)行.DigFuzz[3]提出使用蒙托卡羅概率模型對(duì)模糊測試中執(zhí)行到的路徑計(jì)算優(yōu)先級(jí),將更加困難的路徑交給混合執(zhí)行來求解.Pak 等人[4]提出的混合模糊測試方法是首先使用符號(hào)執(zhí)行探索程序的空間,然后將得到的測試輸入中路徑關(guān)鍵部分的字節(jié)保持不變,其他部分的字節(jié)進(jìn)行隨機(jī)變異以生成新的輸入,再交給模糊測試進(jìn)行探索.與之類似,QSYM[5]通過對(duì)混合測試中的部分路徑約束進(jìn)行求解生成測試用例作為基礎(chǔ)種子,然后在這些種子的基礎(chǔ)上進(jìn)行變異來生成滿足需求的測試輸入.SYMFUZZ[6]首先通過符號(hào)執(zhí)行,對(duì)黑盒模糊測試的兩個(gè)輸入種子的符號(hào)執(zhí)行軌跡進(jìn)行分析,得到輸入位之間的依賴關(guān)系,然后基于該依賴關(guān)系,計(jì)算種子的最佳突變率,然后將新生成的種子作為模糊測試新的輸入.Munch[7]提出了較為粗粒度的混合模糊測試方法,即為了提高函數(shù)覆蓋率,首先使用模糊測試運(yùn)行程序,然后使用制導(dǎo)符號(hào)執(zhí)行對(duì)模糊測試未覆蓋到的函數(shù)探索,產(chǎn)生新的測試輸入繼續(xù)模糊測試.Afleer[2]提出了更為細(xì)粒度的混合模糊測試方法,通過對(duì)源碼插樁生成插樁后的LLVM 中間碼和插樁后的可執(zhí)行文件,然后同時(shí)運(yùn)行模糊測試和符號(hào)執(zhí)行.模糊測試不斷生成新的測試用例,并更新覆蓋信息;符號(hào)執(zhí)行則系統(tǒng)地探索程序狀態(tài)空間,為未被覆蓋的分支生成測試用例,作為模糊測試的種子.該方法中符號(hào)執(zhí)行不可避免地會(huì)去探索本身并不適合該工具的路徑.相比之下,SmartFuSE 還通過對(duì)路徑進(jìn)行分類預(yù)測,進(jìn)而對(duì)符號(hào)執(zhí)行和模糊測試過程進(jìn)行制導(dǎo),讓它們各自優(yōu)先探索適合它們的路徑.這樣可以使符號(hào)執(zhí)行在前期分配更多的時(shí)間探索和求解適合其執(zhí)行的路徑.同時(shí)對(duì)預(yù)測出的以及一定時(shí)間執(zhí)行后發(fā)現(xiàn)不適合符號(hào)執(zhí)行的路徑,也會(huì)制導(dǎo)模糊測試優(yōu)先探索,從而,進(jìn)一步提高SmartFuSE 所能覆蓋的路徑.PANGOLIN[19]提出增量式模糊測試方法,通過對(duì)未覆蓋的路徑使用多面體進(jìn)行路徑抽象,可以制導(dǎo)種子變異和混合測試過程,在多項(xiàng)式時(shí)間內(nèi)生成大量的測試輸入.SeededFuzz[62]使用靜態(tài)分析、動(dòng)態(tài)監(jiān)測和符號(hào)執(zhí)行為模糊測試生成和選擇合適的種子.Berry[63]中提出的序列制導(dǎo)模糊測試(SDHF),在給定一個(gè)程序的語句序列時(shí),該方法利用序列制導(dǎo)策略和混合執(zhí)行來增強(qiáng)模糊測試的能力.ILF[64]提出了一種基于模仿學(xué)習(xí)的模糊測試方法(imitation learning based fuzzer),通過神經(jīng)網(wǎng)絡(luò)模型對(duì)基于覆蓋的符號(hào)執(zhí)行產(chǎn)生的高質(zhì)量的測試用例進(jìn)行學(xué)習(xí),從而習(xí)得模糊測試生成種子的策略.該方法只是將符號(hào)執(zhí)行作為學(xué)習(xí)對(duì)象來提高模糊測試種子生成的質(zhì)量,而我們的方法是通過深度學(xué)習(xí)為符號(hào)執(zhí)行和模糊測試分配各自更適合執(zhí)行路徑來完成混合測試.目前,這些已有的符號(hào)執(zhí)行與模糊測試結(jié)合的混合測試方法都沒有使用深度學(xué)習(xí)來為兩者分配合適的路徑,并以此制導(dǎo)符號(hào)執(zhí)行與模糊測試來進(jìn)行混合測試.

7 總結(jié)

本文提出了一種基于深度學(xué)習(xí)將基于符號(hào)執(zhí)行的測試與模糊測試相結(jié)合的混合測試方法,并基于符號(hào)執(zhí)行工具KLEE 和模糊測試工具AFL,實(shí)現(xiàn)了一個(gè)基于符號(hào)執(zhí)行的測試與模糊測試的混合測試工具SmartFuSE.我們通過對(duì)LAVA-M 程序集中的幾個(gè)程序進(jìn)行測試,結(jié)果表明,我們的工具SmartFuSE 相對(duì)于單獨(dú)通過模糊測試或符號(hào)執(zhí)行的方法,不僅能夠提升對(duì)代碼的覆蓋率,并且對(duì)缺陷的檢測能力也得到了顯著提升.

盡管我們通過深度學(xué)習(xí)的方法探索出了基于符號(hào)執(zhí)行的測試與模糊測試對(duì)代碼空間的探索具有不同的偏好,但是并沒有提供符號(hào)執(zhí)行與模糊測試到底各自更適合的代碼空間具有怎樣的特征.我們考慮可以將符號(hào)執(zhí)行與模糊測試到底各自更適合的代碼特征總結(jié)出來,可以為未來的基于符號(hào)執(zhí)行的測試、模糊測試以及它們的混合測試方法的優(yōu)化提供參考.