基于深度學習的混合模糊測試方法*

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

1(計算機軟件新技術國家重點實驗室(南京大學),江蘇 南京 210023)

2(南京大學 計算機科學與技術系,江蘇 南京 210023)

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

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

軟件缺陷(software defect)產生于開發人員的編碼過程,軟件開發過程不合理或開發人員的經驗不足,均有可能產生軟件缺陷.而含有缺陷的軟件在運行時可能會產生意料之外的不良后果,嚴重時會給企業造成巨大的經濟損失,甚至會威脅到人們的生命財產安全.因此,越早發現軟件缺陷,越能降低修復缺陷的代價.

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

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

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

總而言之,本文的主要貢獻如下:

· 提出了基于深度學習的符號執行與模糊測試的路徑預測方法;

· 提出了制導的符號執行和制導的模糊測試方法,制導符號執行(或模糊測試)優先探索模型預測出的適合符號執行(或模糊測試)的路徑集;

· 提出了通過結合基于符號執行的測試和模糊測試的混合測試方法;

· 開發了原型工具SmartFuSE,通過實驗體現SmartFuSE 的有效性.

本文第1 節介紹相關背景,包括符號執行、模糊測試技術和圖神經網絡.第2 節介紹SmartFuSE 的方法框架.第3 節介紹如何進行數據表示和數據收集以訓練圖神經網絡模型.第4 節介紹如何基于圖神經網絡模型制導符號執行和模糊測試的混合測試過程.第5 節介紹工具實現,并通過實驗評估SmartFuSE 的有效性和性能.第6 節介紹相關工作.第7 節對本文工作進行總結.

1 相關背景

1.1 符號執行

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

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

Fig.1 Example program圖1 示例程序

1.2 模糊測試

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

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

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

1.3 圖神經網絡

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

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

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

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

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

2 SmartFuSE 方法框架

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

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

在混合測試模塊,該模塊的輸入是某個被測程序,針對該被測程序,由于路徑數目龐大,我們先只抽取一定深度的路徑,然后在更深處的路徑中只選取部分路徑,以控制需要預測的路徑數目.在抽取了路徑之后,針對分析出的路徑,SmartFuSE 借助模型訓練模塊得到的模型預測每條路徑是符合模糊測試還是符號執行.針對所有適合模糊測試的路徑,SmartFuSE 制導模糊測試向著這些路徑執行.如果適合符號執行,那么SmartFuSE 會制導符號執行優先以這些路徑作為目標.

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

3 模型訓練

我們將依次介紹樣本數據集收集的方式、路徑編碼和GGNN 神經網絡.

3.1 數據集

在機器學習中,數據集占據著十分重要的地位,如何有效地生成數據集是一個難點.一般都會使用已有的數據集,既可以提供基本的數據,也可以作為評估實驗效果的基準.但是,當前沒有發現針對符號執行或模糊測試的數據集.

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

3.2 程序執行路徑表示

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

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

算法1.程序路徑的圖表示構造算法.

函數:buildPathGraph(Path,AST)

輸入:Path,AST;

輸出:PathGraph.

如下文的圖3 即為圖1 示例程序中的函數foo 中某一條執行路徑(覆蓋的代碼行為〈4,8,9,12,15,16〉)的路徑表示,其中的節點對應于AST 節點,不帶箭頭的邊為AST 中的邊,實線箭頭的邊表示控制流邊,紅色實線空心箭頭的邊表示路徑標識邊,綠色虛線箭頭的邊表示數據依賴邊.

4 混合測試

混合測試模塊分為3 部分:路徑抽取和路徑分類、制導的符號執行以及制導的模糊測試.

4.1 路徑抽取和路徑分類

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

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

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

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

算法2 .路徑抽取算法.

函數:extractPaths(AST,depth)

輸入:AST,depth;

輸出:PS(Path set).

4.2 制導的符號執行

在預測出適合符號執行的路徑集SEPathSet 后,SmartFuSE 將制導符號執行優先探索該路徑集.其核心思路是在傳統的符號執行基礎之上,增加路徑集作為輸入,為與這些目標路徑相關的執行狀態賦予更高的優先級,以此達到優先探索分析目標路徑的目的.

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

算法3.符號執行制導算法.

函數:GuidedSymbolicExecution()

輸入:SEPathSet;

4.3 制導的模糊測試

同樣,在預測出適合模糊測試的路徑集FuzzPathSet 后,SmartFuSE 將制導模糊測試優先探索該路徑集.其核心思想是,程序中FuzzPathSet 的路徑經過次數越多的節點,擁有更高的權重;通過對新產生的測試用例經過的路徑節點計算總權重可知,總權重越高,優先級就越高.模糊測試每次選擇優先級最高的測試用例作為輸入進行下一輪的模糊測試.

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

算法4.模糊測試制導算法.

函數:GuidedFuzzing

輸入:P,FuzzPathSet,Seeds;

基層黨組織功能的轉變過程，實質上是我們黨由革命黨向執政黨轉變的探索過程。這個過程始終處于動態，并充滿復雜性和曲折性。正如有學者認為的那樣，“新的歷史條件下我們黨正在進行的執政黨建設探索，無論在規模上，在任務的艱巨性上，還是在意義上，都不亞于革命斗爭時期的黨的建設，是一項名副其實的‘新的偉大工程’”［4］29。中國共產黨由革命黨向執政黨的轉變，對機關黨組織功能上也產生了新的挑戰。這種挑戰，根源在于作為執政黨，黨的領導方式和執政方式發生變化的基礎上，黨的基層組織的功能定位也在發生變化。

4.4 混合機制

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

同時,對于模糊測試已經覆蓋到的路徑,也被傳遞給符號執行,當符號在執行過程中再次探索到這些路徑時,可以選擇不再進行耗時的約束求解,而將更多的時間用于探索其他路徑.

5 實現與實驗

5.1 實現與實驗設置

本文實現了混合測試工具SmartFuSE,整體框架主要通過Python 實現,其中使用Tensorflow 1.4 建立GGNN的模型,在KLEE 和AFL 的基礎之上修改成制導的符號執行和模糊測試方法.

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

RQ1:SmartFuSE 中通過路徑分類預測模型預測的路徑,制導符號執行、模糊測試的效果如何?

RQ2:SmartFuSE 中的路徑分類制導和混合機制對模糊測試的優化效果如何?

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

5.2 實驗結果

為了驗證SmartFuSE 路徑分類預測模型預測的準確性,我們收集了bzip2-1.0.6 在KLEE、AFL 上分別運行2小時執行的路徑,并記錄了產生覆蓋該路徑的測試用例所需時間,然后與SmartFuSE 路徑分類預測模型預測的路徑分類結果進行比對,發現SmartFuSE 路徑分類預測模型預測的準確率為84.7%.

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

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

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

Table 1 Coverage information of KLEE and guided KLEE on LAVA-M表1 LAVA-M 上KLEE 和制導的KLEE 的覆蓋統計

Table 2 Coverage information of AFL and guided AFL on LAVA-M表2 LAVA-M 上AFL 和制導的AFL 的覆蓋統計

5.2.2 SmartFuSE 中的路徑分類制導和混合機制對模糊測試的優化效果(RQ2)

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

Table 3 Coverage information on LAVA-M表3 LAVA-M 上的覆蓋統計

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

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

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

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

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

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

5.3 實驗討論

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

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

6 相關工作

我們主要從符號執行、模糊測試以及符號執行與模糊測試結合的混合測試技術這3 個方面介紹相關工作.

6.1 符號執行

符號執行技術是一種常用的軟件分析技術,但是傳統的符號執行方法面臨著路徑爆炸、環境交互、系統調用和約束求解等問題[24],因此有許多針對符號執行的優化技術被提出.

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

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

對于約束求解問題,Z3[43]作為當前主流的SMT 約束求解器,在符號執行引擎中,比如KLEE、Mayhem[39]、Angr[44],得到了廣泛應用.同時,EXE[45]、KLEE、AEG 還使用了STP[46]約束求解器.另外,符號執行引擎中也針對約束求解進行了優化設計.比如,在EXE、KLEE、S2E 中通過對收集到的約束進行化簡來降低約束的復雜度.EXE、KLEE、Memoise[47]、GreenTrie[48]等符號執行引擎中還會對約束求解的結果進行緩存從而減少對求解器的調用.

我們的方法通過將基于符號執行的測試與模糊測試相結合,也可以幫助應對符號執行面臨的環境交互和約束求解等問題.

6.2 模糊測試

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

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

6.3 基于符號執行的測試與模糊測試結合的混合測試

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

7 總結

本文提出了一種基于深度學習將基于符號執行的測試與模糊測試相結合的混合測試方法,并基于符號執行工具KLEE 和模糊測試工具AFL,實現了一個基于符號執行的測試與模糊測試的混合測試工具SmartFuSE.我們通過對LAVA-M 程序集中的幾個程序進行測試,結果表明,我們的工具SmartFuSE 相對于單獨通過模糊測試或符號執行的方法,不僅能夠提升對代碼的覆蓋率,并且對缺陷的檢測能力也得到了顯著提升.

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