謝肖飛,李曉紅,陳 翔,孟國柱,劉 楊

1(天津市先進網(wǎng)絡重點實驗室(天津大學),天津 300050)

2(南通大學 計算機科學與技術學院,江蘇 南通 226019)

3(信息安全國家重點研究室(中國科學院 信息工程研究所),北京 100093)

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

1 引 言

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

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

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

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

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

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

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

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

本文的主要貢獻可總結如下.

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

·基于該方法,實現(xiàn)了工具Afleer,并設計了相關實驗,在標準程序集與實際項目上證明了本方法的有效性.

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

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

2 研究背景和研究動機

2.1 模糊測試與AFL工具

基于覆蓋率引導的模糊測試是一種高效的自動化測試技術,它通過隨機變異的方式來生成大量測試用例,依靠覆蓋信息來決定新生成的測試用例是否應該被保留.其中,American Fuzzy Lop(AFL)[4]工具是當前最先進和最流行的模糊測試工具之一,并已在大量實際項目中檢測到了新的漏洞.

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

AFL 通過以下變異操作來對一個已有測試用例進行變異,對于變異后的新測試用例,如果其可以覆蓋到新狀態(tài),則保留該測試用例.

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

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

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

·變異操作4:兩個測試用例隨機選取位置并進行拼接.

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

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

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

2.3 優(yōu)缺點分析及研究動機

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

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

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

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

3 主要方法

3.1 方法框架

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

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

3.2 代碼插樁處理

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

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

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

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

算法1.插樁預處理.

Input:M:LLVM 模塊(Module).

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

2

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

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

6end

3.3 Afleer模糊測試模塊

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

算法2.Afleer 模糊測試模塊.

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

Output:測試用例.

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

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

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

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

4 實證研究

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

4.1 實驗設計

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

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

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

(3)即使將Afleer 中的KLEE 按標準方式加以運行,其生成的測試用例一定是Afleer 生成的測試用例的子集,因此,將兩者進行比較沒有意義.

除此之外,將符號執(zhí)行與動態(tài)測試結合的技術還有Driller[20]以及配套工具HCT[2]等,然而,由于HCT 工具沒有開源,Driller 僅能夠運行在DECREE 的二進制程序上,因此,在我們設計的實驗中并沒有與其直接進行比較,在相關工作中,我們將從方法上進行比較.

研究問題.為了驗證Afleer 的有效性,本文嘗試回答如下研究問題.

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

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

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

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

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

評測指標.針對漏洞檢測能力以及代碼覆蓋能力,本文通過以下指標來評測不同方法.

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

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

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

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

4.2 實驗結果分析

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

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

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

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

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

Fig.4 Increasing of bugs finding on LAVA-M圖4 LAVA-M 漏洞檢測趨勢圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.2.3 基于實際項目的比較(RQ1 和RQ2)

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

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

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

總的來說,Afleer 在實際項目中比AFL 和KLEE 在代碼覆蓋能力及漏洞檢測能力上都具有顯著的提升,因此證明了Afleer 的可擴展性和有效性.

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

4.3 進一步討論

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

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

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

總的來說,當符號執(zhí)行發(fā)現(xiàn)某個未覆蓋的分支,而模糊測試基于該分支可以找到更多的未覆蓋分支時,雙方結合的方式將會更加高效.當KLEE 無法搜索到未覆蓋的分支,或者AFL 無法基于KLEE 生成的測試用例找到更多的測試用例時,雙方結合的方式將會低效.

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

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

5 相關工作

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

5.1 模糊測試

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

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

5.2 符號執(zhí)行

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

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

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

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

5.3 符號執(zhí)行與模糊測試結合的混合測試

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

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

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

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

6 總結與展望

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

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