梁洪亮， 陳奕修， 裴霄瀟， 謝卓思

(北京郵電大學(xué) 計(jì)算機(jī)學(xué)院，北京 100876)

本文關(guān)注軟件測(cè)試的兩個(gè)重要技術(shù)：fuzzing和混合執(zhí)行. fuzzing背后的關(guān)鍵思想是生成大量測(cè)試用例并將其提供給目標(biāo)程序，以便發(fā)現(xiàn)潛在的缺陷. fuzzing的原則之一是最大化計(jì)算資源的使用. 研究人員可能希望他們的fuzzer(即fuzzing工具)每秒評(píng)估上百萬(wàn)個(gè)測(cè)試用例[1]. 然而，由于其固有的盲目性(即在測(cè)試用例生成過(guò)程期間缺乏足夠的引導(dǎo))，fuzzer通常不能到達(dá)目標(biāo)程序較深的代碼分支. 相比之下，混合執(zhí)行使用白盒方法來(lái)生成測(cè)試用例，這可以引導(dǎo)目標(biāo)程序執(zhí)行某些路徑. 從理論上講，它可以覆蓋大多數(shù)程序路徑. 然而，路徑爆炸、約束求解等實(shí)際挑戰(zhàn)使其成為一種耗時(shí)且相對(duì)復(fù)雜的技術(shù)[2].

因此，fuzzing和混合執(zhí)行之間互補(bǔ)的優(yōu)勢(shì)使得它們的組合成為有價(jià)值的研究方向. 例如，Stephens等[3]實(shí)現(xiàn)了一個(gè)名為Driller的二進(jìn)制分析工具. Driller的設(shè)計(jì)基于以下觀察：程序的輸入可以分為兩類(lèi)：“一般輸入”，具有廣泛的有效值，“特定輸入”，只能從幾個(gè)可能的值中選擇. “特定輸入”將程序分成幾個(gè)區(qū)域，這些區(qū)域中不同的程序路徑映射到不同的“一般輸入”，并且這些“一般輸入”可以通過(guò)fuzzing來(lái)產(chǎn)生. 此外，由于混合執(zhí)行有出色的約束求解能力，因此它適合于生成“特定輸入”. 實(shí)驗(yàn)顯示，這種以混合執(zhí)行為輔、fuzzing為主的方法找的程序缺陷數(shù)量要超過(guò)單獨(dú)使用fuzzing和混合執(zhí)行找到的程序缺陷數(shù)量的總和.

但是，由于無(wú)法區(qū)分同一函數(shù)的不同調(diào)用，Driller可能會(huì)錯(cuò)過(guò)潛在的缺陷. 具體來(lái)說(shuō)，在fuzzing階段，Driller會(huì)記錄探索的路徑. 當(dāng)它遇到一對(duì)新的路徑時(shí)，會(huì)根據(jù)路徑的地址計(jì)算一個(gè)值，并使用該值來(lái)表示新的路徑對(duì). 這種路徑記錄方法很簡(jiǎn)單，但不能區(qū)分同一函數(shù)的不同調(diào)用之間的路徑. 因此，在執(zhí)行階段，Driller將忽略一些程序分支，從而錯(cuò)過(guò)這些路徑中的潛在缺陷.

本文提出了一種新方法來(lái)表示對(duì)程序進(jìn)行fuzzing時(shí)的探索路徑并在Digger工具中實(shí)現(xiàn)了新方法. 具體來(lái)說(shuō)，在狀態(tài)轉(zhuǎn)換信息中添加函數(shù)的返回地址，因此本文的fuzzer可以在不同的調(diào)用點(diǎn)區(qū)分同一函數(shù)的不同路徑. 此外，還解決了Driller無(wú)法檢測(cè)輸入為文件的被測(cè)程序的局限.

本文有如下內(nèi)容：

① 提出了一種新的路徑記錄方法，以結(jié)合混合執(zhí)行和fuzzing技術(shù). 該方法在不同的調(diào)用點(diǎn)區(qū)分同一函數(shù)的不同路徑；

② 實(shí)現(xiàn)了一個(gè)應(yīng)用了新路徑記錄方法的混合執(zhí)行輔助的fuzzing工具，Digger. 該工具可對(duì)32位和64位二進(jìn)制程序進(jìn)行測(cè)試，且能夠支持從文件讀取輸入的被測(cè)程序；

③ 在現(xiàn)實(shí)應(yīng)用程序(如GNU Coreutils)上進(jìn)行了對(duì)比實(shí)驗(yàn)，結(jié)果顯示Digger較現(xiàn)有工具Driller能夠達(dá)到更高的代碼覆蓋率，且能夠發(fā)現(xiàn)更多程序缺陷.

1 背 景

本節(jié)描述必要的背景知識(shí)，主要包括fuzzing、混合執(zhí)行和插樁3種技術(shù)，以及與這3種技術(shù)對(duì)應(yīng)的3個(gè)工具：AFL、angr和DynamoRIO，本文工具Digger是基于它們開(kāi)發(fā)的.

① fuzzing.

fuzzing生成測(cè)試用例的方式主要有兩種：基于變異的和基于語(yǔ)法的. 在本文中主要關(guān)注基于變異的fuzzing.

基于變異的fuzzing通常需要研究人員提供初始測(cè)試用例. 基于這些用例，使用替換、比特反轉(zhuǎn)、數(shù)據(jù)添加或刪除等不同的變異策略來(lái)生成大量新的測(cè)試用例[4]. 但其中只有部分能夠探索新的程序路徑. 因此，對(duì)于基于變異的fuzzer，了解測(cè)試用例如何影響目標(biāo)程序的執(zhí)行，如何調(diào)整變異策略，如何調(diào)整測(cè)試用例的數(shù)量和大小可以影響測(cè)試的結(jié)果和效率.

AFL[5]是一個(gè)流行的覆蓋率引導(dǎo)fuzzer. 當(dāng)目標(biāo)程序是二進(jìn)制時(shí)，它使用QEMU[6]來(lái)獲取分支覆蓋的運(yùn)行時(shí)信息和分支命中計(jì)數(shù). AFL根據(jù)這些信息來(lái)快速評(píng)估當(dāng)前的測(cè)試用例. 能夠找到新的程序狀態(tài)轉(zhuǎn)換的測(cè)試用例將被保留并進(jìn)入下一輪變異. 在此過(guò)程中，引發(fā)崩潰的測(cè)試用例將被保留，供測(cè)試人員稍后進(jìn)行分析.

② 混合執(zhí)行.

混合執(zhí)行是一種結(jié)合具體執(zhí)行和符號(hào)執(zhí)行的技術(shù). 給定具體的輸入，目標(biāo)程序在特定路徑上執(zhí)行，同時(shí)，混合執(zhí)行工具符號(hào)化輸入，并收集對(duì)應(yīng)路徑上輸入變量的約束[7]. 然后它選擇性地忽略或者求解約束以生成新的具體值輸入，引導(dǎo)程序執(zhí)行其他路徑. 混合執(zhí)行是一種頗具潛力的程序分析技術(shù)，因?yàn)槔碚撋纤梢院w幾乎所有的程序路徑. 但是，其可行性受到許多實(shí)際問(wèn)題的限制. 路徑爆炸是混合執(zhí)行主要的瓶頸，因?yàn)榧词故且粋€(gè)小程序也可以擁有大量的分支. 不精確的約束求解是另一個(gè)瓶頸，當(dāng)前SMT求解器的能力是有限的，無(wú)法求解很復(fù)雜的路徑約束[2].

Angr是一個(gè)集成了許多先進(jìn)的二進(jìn)制分析技術(shù)的二進(jìn)制分析框架[8]，混合執(zhí)行就是其中之一. 它為用戶提供了大量API來(lái)實(shí)現(xiàn)特定的功能. 例如，用戶可以決定忽略和求解哪些路徑，是否應(yīng)該探索一條分支以及應(yīng)該探索多遠(yuǎn)等等.

③ 插樁.

插樁是用來(lái)輔助程序分析的一種非常有用的技術(shù). 通過(guò)插入不會(huì)影響目標(biāo)程序原始邏輯的額外代碼，測(cè)試人員可以在運(yùn)行時(shí)獲取程序的狀態(tài)信息和行為信息. 該技術(shù)廣泛用于fuzzing. 通過(guò)插樁，fuzzer能夠知道程序路徑是否已被執(zhí)行，及其執(zhí)行次數(shù)等. fuzzer根據(jù)這些信息評(píng)估測(cè)試用例并在不會(huì)丟失代碼覆蓋率的基礎(chǔ)上對(duì)其進(jìn)行剪枝[1]. 插樁的其他應(yīng)用場(chǎng)景包括污點(diǎn)分析、程序調(diào)試、性能分析等[9-10].

DynamoRIO是一款專業(yè)的二進(jìn)制檢測(cè)工具. 它為用戶提供了充足的API來(lái)構(gòu)建自己的插件(也稱為客戶端)以滿足需求[11]. 具體而言，它采用了回調(diào)機(jī)制，提供了許多事件供用戶注冊(cè)，在程序運(yùn)行時(shí)，每當(dāng)發(fā)生被注冊(cè)的事件，它就會(huì)執(zhí)行用戶自己寫(xiě)的回調(diào)函數(shù)，回調(diào)函數(shù)中就是用戶希望進(jìn)行的操作，如通過(guò)插樁得到基本塊的地址、函數(shù)名等[12].

2 動(dòng) 機(jī)

本節(jié)首先描述了Driller采用的路徑記錄方法，然后舉例說(shuō)明為什么這種方法會(huì)導(dǎo)致問(wèn)題及其帶來(lái)的影響.

Driller中有兩個(gè)模塊，一個(gè)用于fuzzing，另一個(gè)模塊用于混合執(zhí)行. fuzzing模塊基于AFL. Driller無(wú)法處理的情況是由AFL使用的程序路徑記錄方法引起的. AFL是一個(gè)覆蓋引導(dǎo)的fuzzer，它在運(yùn)行時(shí)獲取探索的程序路徑，并使用數(shù)組記錄這些路徑的信息. 如果它找到一對(duì)新的相鄰路徑(由prev_loc和cur_loc表示)，它首先計(jì)算prev_loc^cur_loc的值并將該值視為數(shù)組的索引，然后，它標(biāo)記索引相應(yīng)的值來(lái)記錄新的路徑對(duì). 如果當(dāng)前測(cè)試用例能夠引發(fā)新的狀態(tài)轉(zhuǎn)換，AFL將此測(cè)試用例視為“感興趣”的測(cè)試用例，并將其作為下一輪突變的基礎(chǔ)放入特殊隊(duì)列. 該程序路徑重新編碼方法相對(duì)簡(jiǎn)單且有效，因此Driller將其應(yīng)用于fuzzing和混合執(zhí)行模塊.

圖1展示了Driller不能很好處理的一種情形. 這段代碼旨在處理多種命令. 在主函數(shù)中，字符串比較函數(shù)static_strcmp()分別在3個(gè)不同的條件語(yǔ)句中被調(diào)用. 因?yàn)閡ser_command是一個(gè)“特定輸入”，意味著它有特定的值，很難由fuzzing生成，在這種情況下，混合執(zhí)行會(huì)被調(diào)用. 然而，Driller使用的程序路徑記錄方法不能區(qū)分不同調(diào)用點(diǎn)處static_strcmp()的函數(shù)內(nèi)部路徑(第4部分RQ1實(shí)證了這一點(diǎn)). 因此，混合執(zhí)行第一次執(zhí)行static_strcmp()并探索它所有路徑之后，接下來(lái)兩次調(diào)用都不會(huì)再求解約束. 如果沒(méi)有合理的輸入，程序就永遠(yuǎn)不會(huì)執(zhí)行到后兩條條件分支中的代碼，而其中有一個(gè)程序缺陷. 實(shí)際上這種代碼結(jié)構(gòu)很常見(jiàn)，因此解決這個(gè)問(wèn)題對(duì)于提高代碼覆蓋率以及找到潛在缺陷的概率有很大幫助.

圖1 由Driller路徑記錄方式所引發(fā)的問(wèn)題的示例代碼[3] Fig.1 Sample code for problems caused by Driller’s path-recording method[3]

3 設(shè) 計(jì)

3.1 解決方案

為了解決在第2節(jié)描述的問(wèn)題，提出了一種改進(jìn)的路徑編碼方法，該方法使用三元組代替兩元組來(lái)表示Driller中使用的狀態(tài)轉(zhuǎn)換. 添加函數(shù)標(biāo)簽(即函數(shù)的返回地址)以區(qū)分在不同調(diào)用點(diǎn)的相同函數(shù).

圖2顯示了混合執(zhí)行模塊調(diào)用SMT約束求解器的算法，其中branches代表目前分支點(diǎn)處所有可能的分支路徑(一般只有兩條)，“t”代表在給定的具體輸入下混合執(zhí)行模塊所走的路徑，branches.active代表在當(dāng)前分支點(diǎn)處所真正執(zhí)行的路徑，branches.missed代表在當(dāng)前分支點(diǎn)處所沒(méi)有選擇的路徑，一般正常情況下branches.active和branches.missed都各有一條.

圖2 混合執(zhí)行所采用的算法Fig.2 Concolic execution algorithm

這個(gè)算法可以判斷branches.missed中的路徑是否值得求解，具體過(guò)程為：首先獲取并處理3個(gè)所需的地址信息，即上一條路徑的地址，當(dāng)前也就是處于branches.missed中的路徑的地址，以及當(dāng)前所在函數(shù)的返回地址，這3條地址信息在經(jīng)過(guò)一定的處理后得到長(zhǎng)度大小合適的3個(gè)數(shù)值prev_loc、cur_loc和func_label，接著將這3個(gè)數(shù)值進(jìn)行異或運(yùn)算，將得到的數(shù)值作為索引，查看fuzz_bitmap中對(duì)應(yīng)的數(shù)值，fuzz_bitmap是用于記錄已覆蓋路徑的數(shù)組，如果對(duì)應(yīng)位置的數(shù)值為0則說(shuō)明該分支對(duì)以前沒(méi)有被覆蓋過(guò)，此時(shí)混合執(zhí)行模塊就會(huì)調(diào)用其SMT求解器對(duì)該分支路徑上的約束條件進(jìn)行求解，得到能夠使得程序執(zhí)行該路徑的測(cè)試用例. 在處理完一個(gè)分支點(diǎn)處的路徑后，繼續(xù)往下執(zhí)行，通過(guò)t.next_branch()走到下一個(gè)分支點(diǎn)處. 該過(guò)程一直持續(xù)下去，直到在具體輸入下的這條路徑執(zhí)行結(jié)束為止.

3.2 架構(gòu)設(shè)計(jì)

本文用模塊化的方式設(shè)計(jì)了Digger，并基于跨平臺(tái)的工具來(lái)進(jìn)行實(shí)現(xiàn). 因此Digger在具有可拓展性的同時(shí)，還可以輕松地移植到其他操作系統(tǒng). 如圖3所示，Digger有3個(gè)模塊. 以下詳細(xì)介紹所有模塊的功能和各模塊之間如何協(xié)同工作.

圖3 Digger系統(tǒng)架構(gòu)圖Fig.3 System architecture of Digger

調(diào)度模塊主要負(fù)責(zé)兩個(gè)任務(wù)：第一，開(kāi)啟和結(jié)束整個(gè)程序的運(yùn)行；第二，監(jiān)控fuzzing模塊，在恰當(dāng)?shù)臅r(shí)間開(kāi)啟混合執(zhí)行模塊，使其能夠輔助fuzzing模塊的執(zhí)行. 具體來(lái)說(shuō)，調(diào)度程序模塊提供了一個(gè)配置文件來(lái)幫助用戶設(shè)置一些必要參數(shù)，例如被測(cè)程序的存放路徑、測(cè)試結(jié)果的存放路徑、測(cè)試時(shí)長(zhǎng)、被測(cè)程序的參數(shù)、被測(cè)程序的輸入是標(biāo)準(zhǔn)輸入還是文件、插樁參數(shù)等. 測(cè)試開(kāi)始后，調(diào)度模塊首先開(kāi)啟fuzzing模塊的功能，并監(jiān)控該模塊記錄測(cè)試用例狀態(tài)的文件. 如果fuzzing模塊變異運(yùn)行完所有“感興趣的”測(cè)試用例后，還是沒(méi)能發(fā)現(xiàn)新的程序路徑，則調(diào)度模塊就會(huì)開(kāi)啟混合執(zhí)行. 而在進(jìn)行混合執(zhí)行的過(guò)程中，fuzzing模塊會(huì)一直在后臺(tái)運(yùn)行.

fuzzing模塊采用了基于變異的技術(shù)，需要外界提供至少一個(gè)種子(seed)作為初始測(cè)試用例. 這個(gè)種子以格式良好且大小小于1 kB為佳. 在測(cè)試期間，該模塊保存引起崩潰的測(cè)試用例以供后續(xù)進(jìn)一步分析. 在fuzzing模塊運(yùn)行的過(guò)程中，它會(huì)通過(guò)代碼插樁技術(shù)來(lái)獲取當(dāng)前測(cè)試用例所覆蓋的程序路徑信息，并用數(shù)組(在圖3中顯示為fuzz_bitmap)來(lái)記錄這些信息. 基于該信息，fuzzing模塊可以確定當(dāng)前測(cè)試用例是否可以發(fā)現(xiàn)新的狀態(tài)轉(zhuǎn)換. 如果是，則更新fuzz_bitmap并將該輸入保留下來(lái)作為“感興趣的”測(cè)試用例以供后續(xù)變異使用. 當(dāng)調(diào)度程序發(fā)現(xiàn)fuzzing模塊找不到更多新的程序路徑時(shí)，則會(huì)開(kāi)啟混合執(zhí)行模塊.

混合執(zhí)行模塊的功能就是在需要時(shí)以fuzzing模塊傳遞過(guò)來(lái)的測(cè)試用例為輸入對(duì)被測(cè)程序進(jìn)行混合執(zhí)行，以生成能夠突破fuzzing模塊所遇到的程序瓶頸的測(cè)試用例，并將它們返回給fuzzing模塊. 混合執(zhí)行需要具體的輸入來(lái)運(yùn)行目標(biāo)程序. 在本文的工具中，具體的輸入是“感興趣的”測(cè)試用例，這些測(cè)試用例可以覆蓋所有fuzzing模塊探索過(guò)的程序路徑. 在執(zhí)行的過(guò)程中，每當(dāng)遇到一個(gè)條件分支，就與fuzz_bitmap進(jìn)行對(duì)比，由此可判斷另一條分支以前是否被覆蓋過(guò)，如果沒(méi)有就使用約束求解器求解與另一條分支對(duì)應(yīng)的路徑約束，得到能夠使得程序走向另一條分支的外界輸入，如果覆蓋過(guò)就繼續(xù)向下執(zhí)行. 最后得到的新的測(cè)試用例傳遞給fuzzing模塊，以幫助其突破所遇到的程序瓶頸.

3.3 系統(tǒng)流程

分析過(guò)程從fuzzing開(kāi)始. 在fuzzing期間，它會(huì)把能夠發(fā)現(xiàn)新的程序狀態(tài)轉(zhuǎn)移的測(cè)試用例保留下來(lái). 這些測(cè)試用例被視為下一輪變異的基礎(chǔ)，并周期性地對(duì)該“感興趣的”測(cè)試用例集進(jìn)行大小和數(shù)量上的精簡(jiǎn)，前提是保證該集合所覆蓋的整體程序路徑不變. 如果fuzzing遇到一些復(fù)雜的條件語(yǔ)句，若想通過(guò)這些條件語(yǔ)句就需要獲得特定的外界輸入，而這些特定的數(shù)值很難通過(guò)fuzzing的變異得來(lái)，則啟動(dòng)混合執(zhí)行. 混合執(zhí)行模塊接收從fuzzing模塊傳遞過(guò)來(lái)“感興趣的”測(cè)試用例，如果遇到一個(gè)分支點(diǎn)，就通過(guò)與fuzz_bitmap的對(duì)比判斷另一條當(dāng)前沒(méi)有執(zhí)行的分支以前是否被覆蓋過(guò)，如果沒(méi)有就使用約束求解器求解出能夠使得程序執(zhí)行另一條分支的具體輸入. 當(dāng)執(zhí)行完所有“感興趣的”測(cè)試用例后，混合執(zhí)行模塊就將所生成的新的測(cè)試用例傳遞給fuzzing模塊，幫助其通過(guò)程序中的復(fù)雜條件語(yǔ)句繼續(xù)執(zhí)行. 當(dāng)達(dá)到最大測(cè)試時(shí)間或手動(dòng)停止時(shí)，整個(gè)分析過(guò)程停止，fuzzing模塊導(dǎo)出可以觸發(fā)崩潰的測(cè)試用例.

4 評(píng) 估

本文基于AFL 2.35b，DynamoRIO-Linux-6.2.0-2和angr 5.6.12開(kāi)發(fā)Digger. Digger使用DynamoRIO獲取運(yùn)行時(shí)信息，AFL和angr分別用于fuzzing和混合執(zhí)行.

在本節(jié)中將展示3個(gè)實(shí)驗(yàn)的結(jié)果，這些實(shí)驗(yàn)用于從不同方面評(píng)估Digger.

① 新提出的程序路徑編碼方法能否比成熟工具Driller更有效地工作？

本文在一個(gè)Driller無(wú)法處理的程序上分別運(yùn)行Driller和Digger. 編寫(xiě)了與圖1相同結(jié)構(gòu)的目標(biāo)程序，以保證Driller無(wú)法處理. 程序的主函數(shù)中共有3個(gè)判斷語(yǔ)句，且在每個(gè)條件語(yǔ)句中都調(diào)用了相同的字符串比較函數(shù). 該函數(shù)有一個(gè)由外界傳入的參數(shù)，當(dāng)外界輸入為first_cmd和Second_cmd時(shí)，程序分別能夠進(jìn)入兩個(gè)沒(méi)有缺陷存在的分支. 但當(dāng)外界輸入為crash_cmd時(shí)會(huì)走到存在程序缺陷的分支，引發(fā)程序崩潰.

表1顯示了該實(shí)驗(yàn)的結(jié)果. Digger很快就生成導(dǎo)致程序崩潰的輸入，相比之下，無(wú)論Driller運(yùn)行多長(zhǎng)時(shí)間，它都無(wú)法觸發(fā)目標(biāo)程序的崩潰. 至于代碼覆蓋率，Driller覆蓋了60%的分支并執(zhí)行了約78%的語(yǔ)句，而Digger覆蓋了程序的所有分支和所有語(yǔ)句.

表1 實(shí)驗(yàn)1的結(jié)果Tab.1 Result of experiment 1

結(jié)果表明，通過(guò)本文方法，Digger可以有效地解決Driller的問(wèn)題，并在Driller錯(cuò)過(guò)的程序路徑中找到漏洞. 本文提出的路徑記錄方法能夠有效地區(qū)分原本方法所不能區(qū)分的程序路徑，從而幫助生成能夠覆蓋新的程序路徑的測(cè)試用例，實(shí)現(xiàn)代碼覆蓋率的提高，并提高發(fā)現(xiàn)隱藏在目標(biāo)程序中的缺陷的可能性.

② Digger能否實(shí)現(xiàn)比Driller更高的代碼覆蓋率？

第2個(gè)實(shí)驗(yàn)中的目標(biāo)程序選自GNU Coreutils. Driller可測(cè)試的軟件必須為能夠從標(biāo)準(zhǔn)輸入讀取數(shù)據(jù)的軟件，故本文所選取的10個(gè)軟件都可以從標(biāo)準(zhǔn)輸入讀取數(shù)據(jù). Driller與Digger 2列數(shù)據(jù)為執(zhí)行基本命令的結(jié)果，Digger*為執(zhí)行附加了其他參數(shù)的結(jié)果，三者的執(zhí)行時(shí)間一致. 為了看看Digger的附加功能(即設(shè)置目標(biāo)程序的參數(shù))會(huì)帶來(lái)什么影響，本文設(shè)置了1個(gè)控制組(Driller)和2個(gè)實(shí)驗(yàn)組(Digger和Digger*). 前兩個(gè)不帶任何參數(shù)地運(yùn)行目標(biāo)程序，而Digger*使用額外的參數(shù)運(yùn)行. 例如，使用參數(shù)“-a”運(yùn)行“who”. 在測(cè)試時(shí)間相同的情況下，Driller，Digger和Digger*的語(yǔ)句覆蓋和分支覆蓋結(jié)果分別如表2和表3所示. 圖4為更加直觀的實(shí)驗(yàn)結(jié)果條形對(duì)比圖.

圖4 Coreutils實(shí)驗(yàn)的語(yǔ)句和分支覆蓋率Fig.4 Line coverage and branch coverage of Coreutils experiment

表2 Coreutils實(shí)驗(yàn)語(yǔ)句覆蓋率Tab.2 Line coverage of Coreutils experiment %

表3 Coreutils實(shí)驗(yàn)分支覆蓋率Tab.3 Branch coverage of CoreUtils experiment %

表2中的結(jié)果表明，在相同的輸入和時(shí)間限制下，語(yǔ)句覆蓋上，Digger比Driller有小幅提高. 具體而言，10個(gè)命令中，平均增幅約為2%. 分支覆蓋上，整體增幅比較明顯，平均增幅約為4%. 這說(shuō)明在測(cè)試時(shí)間相同、不添加任何參數(shù)的情況下，較Driller而言，Digger具有更多的代碼覆蓋.

此外，表2和表3中的結(jié)果表明，在測(cè)試時(shí)間相同，添加了附加參數(shù)的情況下，Digger較Driller而言在語(yǔ)句和分支覆蓋方面均有明顯的增長(zhǎng). 語(yǔ)句覆蓋上，10個(gè)軟件中最高增幅為37.2%，平均增幅為12.31%. 分支覆蓋上，10個(gè)軟件中最高增幅為36%，平均增幅為12.14%. 這說(shuō)明能夠添加參數(shù)這一功能可以有效幫助Digger覆蓋更多的程序路徑.

③ Digger可以在實(shí)際軟件中找到更多缺陷嗎？

為了檢驗(yàn)Digger測(cè)試實(shí)際軟件的能力，本文進(jìn)行了第3次對(duì)比實(shí)驗(yàn)，用Digger和Driller測(cè)試3個(gè)文件格式轉(zhuǎn)換軟件：catdvi-0.14、gif2png-2.5.9和pdf2svg-0.2.3. 測(cè)試所得數(shù)據(jù)如表4所示.

表4 catdvi,gif2png,pdf2svg的測(cè)試結(jié)果Tab.4 Test result of catdvi,gif2png,pdf2svg

在相同的時(shí)間限制下，對(duì)于被測(cè)軟件catdvi和gif2png來(lái)說(shuō)，Digger在語(yǔ)句覆蓋范圍和分支覆蓋范圍方面取得了進(jìn)步(增加約10%～20%). 而對(duì)于pdf2svg來(lái)說(shuō)，由于該軟件只能從文件讀取輸入，故用Driller測(cè)試得到的覆蓋率很低，即被測(cè)程序在運(yùn)行伊始就終止了. 相對(duì)較高的覆蓋率說(shuō)明Digger在處理從文件讀取輸入的目標(biāo)程序上具有明顯的優(yōu)勢(shì).

在測(cè)試結(jié)束后，本文使用GDB的exploitable插件對(duì)能夠?qū)е鲁绦虮罎⒌臏y(cè)試用例進(jìn)行了分析. 根據(jù)缺陷發(fā)生的位置，Digger在3個(gè)被測(cè)程序中的兩個(gè)發(fā)現(xiàn)更多的崩潰. 具體來(lái)說(shuō)，對(duì)于catdvi，Digger發(fā)現(xiàn)了空指針解引用、超出數(shù)組邊界和除零3種缺陷. 對(duì)于gif2png，這2個(gè)工具都會(huì)發(fā)現(xiàn)超出數(shù)組邊界缺陷. 對(duì)于pdf2svg，Digger在它的lib poppler中找到一個(gè)空指針解引用缺陷. 這些缺陷都是新發(fā)現(xiàn)的. 以catdvi為例，漏洞的詳細(xì)信息見(jiàn)表5.

表5 catdvi的測(cè)試結(jié)果Tab.5 Test result of catdvi

總之，上述3個(gè)實(shí)驗(yàn)的結(jié)果表明：本文的路徑記錄方法可以有效地工作，并且應(yīng)用此方法的工具Digger在測(cè)試實(shí)際軟件時(shí)能夠在較短的時(shí)間內(nèi)達(dá)到較高的代碼覆蓋率，且能夠有效地觸發(fā)導(dǎo)致軟件崩潰的程序缺陷，具有良好的實(shí)用性.

5 相關(guān)工作

本節(jié)介紹在結(jié)合fuzzing和符號(hào)執(zhí)行技術(shù)，以及覆蓋引導(dǎo)fuzzing方面的相關(guān)工作. 對(duì)于具有特定程序路徑約束來(lái)說(shuō)，符號(hào)執(zhí)行很有效，而fuzzing可以非常有效地生成測(cè)試用例. 這2種技術(shù)相結(jié)合的研究方向最近引起了人們的廣泛關(guān)注. 在fuzzing中使用的各種方法中，覆蓋引導(dǎo)方法因其出色的表現(xiàn)脫穎而出.

① fuzzing結(jié)合符合執(zhí)行.

傳統(tǒng)的符號(hào)執(zhí)行可以最大化代碼覆蓋率來(lái)找到程序缺陷[13-14]，但是路徑爆炸還有約束求解帶來(lái)的困難使得傳統(tǒng)符號(hào)執(zhí)行難以繼續(xù)拓展[8,15]. 因此出現(xiàn)了一些工具試圖將其與fuzzing結(jié)合來(lái)解決這種困難[3,16-18]. DART[16]和SAGE[17]使用混合執(zhí)行引擎來(lái)修改fuzzing中的輸入. SYMFUZZ[18]利用對(duì)于執(zhí)行路徑上對(duì)的符號(hào)分析來(lái)檢測(cè)輸入中比特位的依賴，然后利用這個(gè)依賴來(lái)計(jì)算最佳突變比率來(lái)指導(dǎo)fuzzing. Driller[3]只有在AFL的模糊測(cè)試卡住時(shí)才使用動(dòng)態(tài)符號(hào)執(zhí)行. Angora[19]也可以處理大型真實(shí)世界的程序以及利用符號(hào)執(zhí)行的強(qiáng)大功能來(lái)解決難以通過(guò)的約束. Fietkau等[20]提出了另一種用混合執(zhí)行輔助fuzzing的方法. 先運(yùn)行動(dòng)態(tài)符號(hào)工具執(zhí)行一段時(shí)間，再將其生成的測(cè)試用例作為種子傳遞給fuzzing工具. 但他們的方法只在最開(kāi)始調(diào)用混合執(zhí)行一次.

② 覆蓋引導(dǎo)fuzzing.

反饋fuzzing因其在真實(shí)應(yīng)用中發(fā)現(xiàn)缺陷的突出能力而備受關(guān)注. 覆蓋的程序路徑信息是最常用的反饋. 覆蓋引導(dǎo)的fuzzer使用此反饋來(lái)生成高質(zhì)量的測(cè)試用例. 目前，許多灰盒式fuzzer(如AFL，Syzkaller，LibFuzzer等)都采用了這種方法并取得了豐碩的成果.

Syzkaller[21]的目標(biāo)程序是Linux內(nèi)核. 雖然該工具需要依據(jù)模板(用于描述每個(gè)系統(tǒng)調(diào)用的參數(shù)取值范圍)來(lái)生成測(cè)試用例，但它也會(huì)在運(yùn)行時(shí)收集有關(guān)被覆蓋路徑的信息，并據(jù)此指導(dǎo)變異過(guò)程. LibFuzzer[22]是專門(mén)用于測(cè)試庫(kù)函數(shù)的fuzzing工具. 它可以在沒(méi)有種子用例的情況下運(yùn)行，但是當(dāng)被測(cè)庫(kù)函數(shù)接收的是結(jié)構(gòu)化的、復(fù)雜的參數(shù)時(shí)，該工具的效率會(huì)有所下降. AFLFast[23]觀察到大多數(shù)fuzzing最后都陷入了相同的幾條高頻路徑，而他們使用馬爾可夫鏈來(lái)識(shí)別低頻路徑，優(yōu)先考慮包含此類(lèi)路徑的輸入. AFLGo[24]提出模擬退火的能量調(diào)度算法來(lái)到達(dá)某些特定的程序位置. VUzzer[25]使用控制流特征來(lái)為路徑建模，優(yōu)先考慮執(zhí)行到難以到達(dá)的路徑的輸入. 此外，VUzzer會(huì)檢測(cè)錯(cuò)誤處理的基本塊，并優(yōu)先考慮不包含這些基本塊的有效輸入. FAIRFUZZ[26]旨在探索被測(cè)程序的罕見(jiàn)部分，它首先優(yōu)先生成可以執(zhí)行到程序罕見(jiàn)部分的輸入，然后提高變異后的輸入能執(zhí)行到相同的罕見(jiàn)部分，并且探索到不同路徑的概率.

6 結(jié) 論

本文提出了一種新的程序路徑記錄方法，并將其應(yīng)用于二進(jìn)制分析工具Digger. 除了路徑記錄方法，與Driller相比，本文的工具還具有一些附加功能，如處理目標(biāo)程序，從文件中讀取輸入，設(shè)置目標(biāo)程序的參數(shù)等. 實(shí)驗(yàn)表明，與Driller相比，Digger能夠達(dá)到更高的代碼覆蓋率，能夠發(fā)現(xiàn)Driller不能探查到的程序缺陷，且在測(cè)試實(shí)際應(yīng)用程序時(shí)也達(dá)到了良好的效果，由此證明了本文提出的方法的有效性和工具的實(shí)用性.

在未來(lái)，作者將使用DynamoRIO和angr的能力使Digger支持更多類(lèi)型的架構(gòu)，還考慮提高Digger的性能，使其更有效地執(zhí)行.