蔡軍，鄒鵬 ，馬金鑫，何駿

(1.裝備學(xué)院 復(fù)雜電子系統(tǒng)仿真實(shí)驗(yàn)室，北京101416; 2.中國(guó)信息安全測(cè)評(píng)中心，北京100085)

21 世紀(jì)是網(wǎng)絡(luò)時(shí)代，信息網(wǎng)絡(luò)已經(jīng)成為全球經(jīng)濟(jì)中最重要的基礎(chǔ)設(shè)施，與此同時(shí)，網(wǎng)絡(luò)安全問(wèn)題成為潛藏在我們每一個(gè)人身邊的現(xiàn)實(shí)威脅，軟件漏洞是網(wǎng)絡(luò)安全問(wèn)題的根源之一，大部分網(wǎng)絡(luò)攻擊都是基于軟件漏洞來(lái)實(shí)施的.例如2014 年9 月發(fā)現(xiàn)的“ShellShock”漏洞，被稱為是歷來(lái)發(fā)現(xiàn)的最嚴(yán)重和最普遍的軟件漏洞之一，利用這一漏洞，遠(yuǎn)程攻擊者可能在受影響的系統(tǒng)上執(zhí)行任意代碼，其危害性震撼全球.因此，軟件漏洞檢測(cè)在網(wǎng)絡(luò)安全領(lǐng)域受到了越來(lái)越多的關(guān)注.

本文主要研究面向二進(jìn)制程序的動(dòng)態(tài)漏洞檢測(cè)方法.目前主流的動(dòng)態(tài)漏洞檢測(cè)方法包括模糊測(cè)試、動(dòng)態(tài)符號(hào)執(zhí)行和動(dòng)態(tài)污點(diǎn)分析3 種方法.模糊測(cè)試的基本思想是:構(gòu)造大量畸形輸入，交給目標(biāo)程序執(zhí)行，如果程序產(chǎn)生異常(崩潰、掛起等)，就有可能存在一個(gè)潛在的漏洞;動(dòng)態(tài)污點(diǎn)分析追蹤用戶輸入在程序執(zhí)行過(guò)程中的傳播，通過(guò)檢查軟件中的安全敏感操作的輸入數(shù)據(jù)是否為污點(diǎn)數(shù)據(jù)來(lái)檢測(cè)漏洞.以上兩種方法都有各自的優(yōu)缺點(diǎn)，模糊測(cè)試使用簡(jiǎn)單但是隨機(jī)性太強(qiáng)，動(dòng)態(tài)污點(diǎn)分析能夠精確分析漏洞成因但是只能分析當(dāng)前已經(jīng)執(zhí)行到的程序路徑，使用這兩種方法的共同缺點(diǎn)是難以獲得較高的代碼覆蓋率.代碼覆蓋率是軟件在測(cè)試中執(zhí)行到的代碼量占軟件代碼總量的比率.理論上，如果軟件在某次測(cè)試中能達(dá)到百分之百的代碼覆蓋率，就能發(fā)現(xiàn)其所有漏洞.與模糊測(cè)試、動(dòng)態(tài)污點(diǎn)分析相比，動(dòng)態(tài)符號(hào)執(zhí)行在提高軟件測(cè)試代碼覆蓋率方面具有很大的優(yōu)勢(shì)，成為漏洞檢測(cè)技術(shù)的研究熱點(diǎn)和發(fā)展趨勢(shì).

本文針對(duì)現(xiàn)有動(dòng)態(tài)符號(hào)執(zhí)行方法在通過(guò)約束求解生成測(cè)試用例時(shí)，生成的測(cè)試用例存在大量重復(fù)或近似重復(fù)的問(wèn)題，提出了一種基于禁忌搜索(Tabu Search，TS)的動(dòng)態(tài)符號(hào)執(zhí)行方法，并實(shí)現(xiàn)了一個(gè)相應(yīng)的工具原型SwordSE.SwordSE 的核心思想為:①以Valgrind VEX［1］中間表示作為符號(hào)執(zhí)行的基礎(chǔ)，通過(guò)動(dòng)態(tài)插樁來(lái)實(shí)現(xiàn)符號(hào)引入、符號(hào)傳播和約束收集;②使用Simple Theorem Prover(STP)［2］約束求解器求解路徑約束來(lái)生成測(cè)試用例，通過(guò)約束分析和求解緩存來(lái)提高求解效率;③以禁忌搜索算法作為路徑搜索算法，減少重復(fù)測(cè)試和避免循環(huán)，提高路徑搜索效率.

1 概 述

1.1 禁忌搜索算法

禁忌搜索算法是一種亞啟發(fā)式(meta-heuristic)隨機(jī)搜索算法，它從一個(gè)初始可行解出發(fā)，選擇一系列的特定搜索方向(移動(dòng))作為試探，選擇實(shí)現(xiàn)讓特定的目標(biāo)函數(shù)值變化最多的移動(dòng).為了避免陷入局部最優(yōu)解，禁忌搜索采用禁忌表(tabu list)對(duì)已經(jīng)進(jìn)行的優(yōu)化過(guò)程進(jìn)行記錄和選擇，指導(dǎo)下一步的搜索方向［3-5］.

禁忌搜索算法的特征由禁忌對(duì)象和長(zhǎng)度、候選集和評(píng)價(jià)函數(shù)、停止規(guī)則和一些計(jì)算信息組成.具體可描述為［6］:

步驟1 初始化禁忌表H =?，選定一個(gè)初始解xnow.

步驟2 滿足停止規(guī)則時(shí)，停止計(jì)算，輸出結(jié)果;否則，在xnow的鄰域N(xnow)中選出滿足不受禁忌的候選集Can_N(xnow);在Can_N(xnow)中選一個(gè)評(píng)價(jià)值最佳的解xnext，xnow:=xnext;更新歷史記錄H，重復(fù)步驟2.

1.2 動(dòng)態(tài)符號(hào)執(zhí)行

動(dòng)態(tài)符號(hào)執(zhí)行以符號(hào)輸入代替實(shí)際輸入，以符號(hào)表達(dá)式代表程序變量，在模擬程序執(zhí)行過(guò)程中遇到分支時(shí)收集約束條件，通過(guò)求解約束條件并自動(dòng)生成測(cè)試用例來(lái)遍歷程序中的所有可達(dá)路徑［7-9］.從2005 年最早出現(xiàn)至今，已經(jīng)涌現(xiàn)出了一些優(yōu)秀的動(dòng)態(tài)符號(hào)執(zhí)行工具，本文對(duì)它們做了一個(gè)對(duì)比分析，重點(diǎn)比較它們采用的路徑搜索算法.如表1 所示，可以看出，各個(gè)工具采用的路徑搜索算法不盡相同，DART 和CUTE 的算法最簡(jiǎn)單，僅僅使用了深度優(yōu)先算法，S2E 的算法相對(duì)復(fù)雜，綜合使用了深度優(yōu)先、廣度優(yōu)先和隨機(jī)算法.總的來(lái)說(shuō)，動(dòng)態(tài)符號(hào)執(zhí)行的路徑搜索算法正朝著智能化、多樣化的方向發(fā)展，另外一個(gè)趨勢(shì)是由面向源碼向直接面向二進(jìn)制程序發(fā)展.

表1 典型動(dòng)態(tài)符號(hào)執(zhí)行工具對(duì)比Table 1 Contrast of typical dynamic symbolic execution tools

2 SwordSE 的設(shè)計(jì)和實(shí)現(xiàn)

SwordSE 是在開(kāi)源動(dòng)態(tài)符號(hào)執(zhí)行工具Fuzzgrind［15］的基礎(chǔ)上設(shè)計(jì)實(shí)現(xiàn)的，其工作流程如圖1所示.種子輸入是提供給目標(biāo)程序的初始輸入，分為兩類:一類是文件，一類是命令行參數(shù).符號(hào)引入、符號(hào)傳播和約束收集這3 個(gè)步驟借助Valgrind 插樁平臺(tái)完成，約束求解這一步驟借助STP求解器完成.給定一個(gè)種子輸入和一個(gè)目標(biāo)程序，SwordSE 就會(huì)自動(dòng)搜索程序的不同執(zhí)行路徑，并為每一條執(zhí)行路徑生成一個(gè)測(cè)試用例，如果在某條執(zhí)行路徑上有異常，就將相應(yīng)的測(cè)試用例保存到一個(gè)專門(mén)的文件夾中.SwordSE 的設(shè)計(jì)目標(biāo)是在盡可能短的時(shí)間內(nèi)找到盡可能多的沒(méi)有重復(fù)的路徑，獲得盡可能高的代碼覆蓋率.

圖1 SwordSE 工作流程Fig.1 Workflow of SwordSE

2.1 基于Valgrind VEX 的約束收集

Valgrind 是運(yùn)行在Linux 系統(tǒng)上的一個(gè)開(kāi)源的動(dòng)態(tài)二進(jìn)制插樁平臺(tái)，它使用VEX 中間表示(Intermediate Representation，IR)來(lái)實(shí)施代碼分析和插樁.使用中間表示的好處有兩點(diǎn):①中間表示是體系結(jié)構(gòu)無(wú)關(guān)的，對(duì)于不同的指令體系表示是一致的;②中間表示將復(fù)雜的二進(jìn)制指令轉(zhuǎn)換成了簡(jiǎn)單的中間表達(dá)形式，相比直接分析二進(jìn)制指令，分析中間表示要簡(jiǎn)單得多.SwordSE 收集的路徑約束就是由中間表示構(gòu)成的公式，下面詳細(xì)介紹約束收集過(guò)程.

2.1.1 符號(hào)引入

符號(hào)引入是將用戶輸入符號(hào)化的過(guò)程.SwordSE 當(dāng)前支持兩類輸入的符號(hào)化:一類是文件類輸入，一類是命令行輸入，兩類輸入均以字節(jié)為單位進(jìn)行符號(hào)化，即一個(gè)字節(jié)對(duì)應(yīng)一個(gè)符號(hào)變量.

對(duì)于文件類輸入，通過(guò)編寫(xiě)回調(diào)函數(shù)，調(diào)用“VG_(needs_syscall_wrapper)”函數(shù)插樁文件相關(guān)系統(tǒng)調(diào)用來(lái)引入符號(hào)，首先插樁open 系統(tǒng)調(diào)用，如果打開(kāi)的是指定的輸入文件，則將其文件描述符fd 加入到感興趣的描述符集合中;接下來(lái)插樁read 系統(tǒng)調(diào)用，如果讀取的是感興趣的描述符集合中的文件，則引入符號(hào)，即為每一個(gè)讀入的字節(jié)指派一個(gè)符號(hào)變量，并將這個(gè)字節(jié)在內(nèi)存中的存放地址加入到受依賴的地址集合.最后還要插樁close 系統(tǒng)調(diào)用，如果有打開(kāi)的文件被關(guān)閉了，就將其對(duì)應(yīng)的fd 從感興趣的描述符集合中刪除.另外，還需要對(duì)mmap 系統(tǒng)調(diào)用做類似于read 的插樁，因?yàn)橛行┏绦蚴峭ㄟ^(guò)mmap 讀入文件數(shù)據(jù)的.

對(duì)于命令行輸入，則調(diào)用“VG_(track_pre_thread_first_insn)”函數(shù)來(lái)插樁線程，捕捉傳遞給線程的命令行參數(shù)及參數(shù)的存放地址.每個(gè)參數(shù)是一個(gè)字符串，SwordSE 為字符串的每一個(gè)字節(jié)(字符)指派一個(gè)符號(hào)變量，并將其存放地址加入到受依賴的地址集合.SwordSE 不能同時(shí)將文件和命令行設(shè)為符號(hào)，要么符號(hào)化文件輸入，要么符號(hào)化命令行輸入.

2.1.2 符號(hào)傳播

符號(hào)傳播是根據(jù)程序執(zhí)行語(yǔ)義，追蹤程序變量對(duì)輸入的依賴，將程序變量由上一步引入的符號(hào)變量的表達(dá)式來(lái)表示.符號(hào)傳播也是通過(guò)插樁回調(diào)函數(shù)來(lái)實(shí)現(xiàn)，SwordSE 直接在VEX IR 上做插樁，插樁的基本單位為中間表示超級(jí)塊(Intermediate Representation Super Block，IRSB).一 個(gè)IRSB 可以代表1 ～50 條匯編指令，它是一個(gè)單入口多出口的代碼塊.每個(gè)IRSB 由3 個(gè)部分組成:一個(gè)變量類型列表，指明了這個(gè)IRSB 中出現(xiàn)的所有臨時(shí)變量的類型;一個(gè)IR 語(yǔ)句序列，代表一條或多條匯編指令;一個(gè)跳轉(zhuǎn)語(yǔ)句，在IRSB 的末尾，指示這個(gè)IRSB 執(zhí)行完后下一個(gè)要執(zhí)行的IRSB 的地址(在IRSB 的中間可能還會(huì)有條件跳轉(zhuǎn)語(yǔ)句).圖2 是IRSB 的一個(gè)示例，可以看出這個(gè)IRSB 中有3 個(gè)臨時(shí)變量t0、t1、t2，類型均為I32(32 位整型);有6 條IR 語(yǔ)句(編號(hào)為1 ～6)，其中第1 ～5 條語(yǔ)句就是一個(gè)IR 語(yǔ)句序列，代表了一條匯編指令(這個(gè)IRSB 是一個(gè)小型的IRSB，大的IRSB 由上百條的語(yǔ)句序列構(gòu)成，可以代表50 條匯編指令);最后一條IR 語(yǔ)句(第6 條)就是一個(gè)跳轉(zhuǎn)語(yǔ)句，是每個(gè)IRSB 末尾都要有的語(yǔ)句，可以是返回跳轉(zhuǎn)(return)，也可以是條件跳轉(zhuǎn)(if).

IRSB 主要由IR 語(yǔ)句(statement)組成，而IR語(yǔ)句又由IR 表達(dá)式(expression)構(gòu)成.語(yǔ)句有Ist_IMark，Ist_Put，Ist_Store，Ist_Exit 等12 種類型;表達(dá)式也有Iex_Triop，Iex_Binop，Iex_Unop 等12 種類型.符號(hào)傳播的過(guò)程就是插樁每個(gè)IRSB，逐條分析IRSB 中的語(yǔ)句(有的語(yǔ)句類型還需進(jìn)一步分析構(gòu)成它們的表達(dá)式類型，如Ist_WrTmp 語(yǔ)句)，根據(jù)語(yǔ)句類型及構(gòu)成它們的表達(dá)式類型插樁相應(yīng)的回調(diào)函數(shù)，記錄它們對(duì)符號(hào)變量進(jìn)行的操作.

圖2 IRSB 示例Fig.2 An example of IRSB

2.1.3 約束收集

在上一步符號(hào)傳播的過(guò)程中，記錄了對(duì)符號(hào)變量的操作，并保存在一個(gè)數(shù)據(jù)結(jié)構(gòu)DEP 中，如圖3 所示，在DEP 中，value 記錄了符號(hào)變量的存放地址，buf 記錄了對(duì)符號(hào)變量的操作.SwordSE為每個(gè)符號(hào)變量維持一個(gè)這樣的數(shù)據(jù)結(jié)構(gòu).在程序運(yùn)行過(guò)程中，會(huì)產(chǎn)生很多臨時(shí)變量，SwordSE 為每個(gè)臨時(shí)變量也維持一個(gè)DEP.

圖3 DEP 數(shù)據(jù)結(jié)構(gòu)Fig.3 DEP data structure

約束收集就是在遇到if 條件跳轉(zhuǎn)語(yǔ)句(Ist_Exit 語(yǔ)句)時(shí)，插入分析代碼，檢查條件表達(dá)式的值是否受輸入影響，這個(gè)值也是一個(gè)臨時(shí)變量，因此只需檢查這個(gè)臨時(shí)變量的DEP 中的buf 是否為空，如果不為空，則將當(dāng)前指令地址和buf 中的內(nèi)容以一定格式輸出到一個(gè)文件中，這個(gè)buf 就是一個(gè)由IR 表示的路徑約束公式.圖4 是一個(gè)簡(jiǎn)單的路徑約束示例，可以看出這條路徑僅受符號(hào)輸入“input(0)”(即輸入的第1 個(gè)字節(jié))影響.

圖4 IR 表示的路徑約束示例Fig.4 An example of path constraint represented by IR

對(duì)輸出的文件進(jìn)行分析，查找所有的“depending on input”語(yǔ)句，將if 后面的約束公式提取出來(lái)，存放到一個(gè)集合中，這個(gè)集合就是路徑約束集合PC.

2.2 基于STP 求解器的約束求解

上一步進(jìn)行了約束收集，得到一個(gè)用VEX IR表示的約束公式集合PC，接下來(lái)就要用求解器［18-22］對(duì)PC 中的約束公式逐個(gè)求解.

SwordSE 基于以下兩點(diǎn)選擇STP 作為約束求解器:①STP 開(kāi)源且代碼量不大，且支持多種輸入格式;②STP 適合于求解位向量，而SwordSE 產(chǎn)生的約束公式正好是位向量.

求解過(guò)程分為兩步:①將IR 表示的約束公式集合PC 里的公式全部轉(zhuǎn)換為STP 支持的輸入格式，得到新的公式集合pc.例如，圖4 中的路徑約束轉(zhuǎn)換為STP 格式后如圖5 所示;②對(duì)pc 里的公式逐個(gè)取反求解，生成新的輸入.

圖5 圖4 中的路徑約束對(duì)應(yīng)的STP 格式Fig.5 STP format of path constraint showed in Fig.4

2.3 基于禁忌搜索的路徑搜索

第2.1 ～2.2 節(jié)實(shí)現(xiàn)了一個(gè)基本的動(dòng)態(tài)符號(hào)執(zhí)行功能，即給定一個(gè)種子輸入，能夠通過(guò)符號(hào)約束收集求解生成新的子輸入(也叫測(cè)試用例)，這些測(cè)試用例能夠驅(qū)使程序走不同于種子輸入的執(zhí)行路徑.

在程序執(zhí)行過(guò)程中，會(huì)遇到很多的分支節(jié)點(diǎn)(條件跳轉(zhuǎn)語(yǔ)句)，由此產(chǎn)生了不同的程序執(zhí)行路徑，如圖6 所示，①②④⑧、①③⑥、①②⑤○11○14、①②⑤⑩○12○16○17都是程序執(zhí)行路徑，程序分支節(jié)點(diǎn)越多，路徑數(shù)量就越大.SwordSE 的目的就是要在盡可能短的時(shí)間內(nèi)找到通向程序漏洞的路徑.

圖6 程序執(zhí)行路徑Fig.6 Program execution paths

動(dòng)態(tài)符號(hào)執(zhí)行一次執(zhí)行只遍歷程序的一條路徑，一個(gè)測(cè)試用例就代表了程序的一條路徑，這樣在路徑遍歷時(shí)，就需要遵循一定的路徑搜索算法，如表1 所示.路徑搜索算法的好壞直接影響路徑搜索的效率.

Fuzzgrind 采用的路徑搜索算法是代搜索.該算法將種子輸入的執(zhí)行路徑作為第1 代路徑，收集路徑約束得到路徑約束集合pc，然后對(duì)pc 中的約束逐個(gè)取反，通過(guò)約束求解生成第1 代測(cè)試用例;然后按照深度優(yōu)先的原則從已生成的測(cè)試用例中選擇一個(gè)作為第2 代路徑的種子輸入，生成第2 代測(cè)試用例，接著按照同樣的方法生成第3代測(cè)試用例，依次類推，所有新生成的測(cè)試用例都將作為種子輸入，直到找出所有可能的程序路徑時(shí)停止搜索.

事實(shí)上，在對(duì)Fuzzgrind 做了大量測(cè)試后，發(fā)現(xiàn)它在生成測(cè)試用例時(shí)，生成了大量重復(fù)和近似重復(fù)的測(cè)試用例，而且很容易陷入局部鄰域搜索，導(dǎo)致路徑搜索效率很低.出現(xiàn)這個(gè)問(wèn)題的原因主要在于種子輸入的選擇上，F(xiàn)uzzgrind 將所有生成的測(cè)試用例按照深度優(yōu)先的原則依次作為種子輸入，這樣存在兩個(gè)問(wèn)題:①兩個(gè)相鄰代的種子之間差異可能很小甚至相同，由此找到的不同路徑很少;②將所有生成的測(cè)試用例都作為種子輸入，導(dǎo)致迭代的次數(shù)過(guò)多，甚至是陷入循環(huán).

針對(duì)上述問(wèn)題，SwordSE 采用了禁忌搜索算法，禁忌搜索是一種全局逐步尋優(yōu)算法，正好能解決上述問(wèn)題，這是因?yàn)?①禁忌搜索通過(guò)建立評(píng)價(jià)函數(shù)，選擇評(píng)價(jià)好的子輸入作為種子輸入，而不是將所有的子輸入作為種子輸入，減少了迭代次數(shù);②禁忌搜索通過(guò)建立禁忌表，避免了重復(fù)搜索，避免了循環(huán).SwordSE 通過(guò)使用禁忌搜索算法，能夠在單位時(shí)間內(nèi)找到更多的沒(méi)有重復(fù)的路徑，大大提高了路徑搜索效率，進(jìn)而提高了漏洞檢測(cè)效率.下面具體描述算法的實(shí)現(xiàn).

2.3.1 建立評(píng)價(jià)函數(shù)

建立評(píng)價(jià)函數(shù)的目的是為選擇合適的子輸入作為新的種子輸入提供依據(jù).SwordSE 以程序執(zhí)行到的IRSB 的數(shù)量來(lái)作為子輸入的評(píng)價(jià)值，如式(1)所示.評(píng)價(jià)值越大，說(shuō)明該子輸入執(zhí)行到的IRSB 的數(shù)量越多.

要計(jì)算IRSB 的數(shù)量，只需寫(xiě)一個(gè)簡(jiǎn)單的Valgrind tool，對(duì)IRSB 進(jìn)行插樁，設(shè)定一個(gè)全局變量N，每執(zhí)行一個(gè)IRSB，就將N 加1.

2.3.2 建立候選集

SwordSE 通過(guò)約束求解從一個(gè)種子輸入派生出多個(gè)子輸入，候選集Can_N(xnow)是這些子輸入的一個(gè)子集，如式(2)所示，候選集里的元素是將要作為種子的子輸入.

候選集的建立過(guò)程如下:首先，對(duì)每一個(gè)子輸入進(jìn)行異常檢測(cè)，查看將它們作為目標(biāo)程序的輸入時(shí)是否會(huì)導(dǎo)致程序異常，如果導(dǎo)致程序異常，就將該子輸入保存在crash 文件夾;接下來(lái)，對(duì)每個(gè)子輸入依據(jù)評(píng)價(jià)函數(shù)進(jìn)行評(píng)價(jià)，然后進(jìn)行去重處理，對(duì)評(píng)價(jià)值相同的多個(gè)子輸入，只保留一個(gè)進(jìn)入候選集.

建立候選集后，對(duì)其按評(píng)價(jià)值進(jìn)行排序，選取評(píng)價(jià)值最大的子輸入作為下一代種子輸入，如式(3)所示.每動(dòng)態(tài)符號(hào)執(zhí)行一次，候選集就更新一次，每次動(dòng)態(tài)符號(hào)執(zhí)行的種子輸入都是當(dāng)前候選集中未作過(guò)種子的且評(píng)價(jià)值最大的子輸入.

2.3.3 建立禁忌表

禁忌表H 記錄的是已經(jīng)作過(guò)種子的測(cè)試用例的評(píng)價(jià)值，如式(4)所示.如果新找到的測(cè)試用例的評(píng)價(jià)值已經(jīng)在禁忌表中或者與禁忌表中的某一項(xiàng)十分接近(十分接近指數(shù)值相差很小，小于一個(gè)預(yù)先設(shè)定的差值上限，例如差值上限為3 表示數(shù)值相差在3 以內(nèi))，則該測(cè)試用例不能被選入候選集，從而避免了重復(fù).

2.3.4 建立停止規(guī)則

理論上，利用動(dòng)態(tài)符號(hào)執(zhí)行技術(shù)可以找出所有的程序執(zhí)行路徑，但事實(shí)上到目前為止，受限于求解器的求解能力和符號(hào)模擬的精確程度，加之大型應(yīng)用程序的路徑數(shù)量相當(dāng)龐大，國(guó)內(nèi)外還沒(méi)有哪一個(gè)動(dòng)態(tài)符號(hào)執(zhí)行工具能做到這一點(diǎn).現(xiàn)有的工具都是力爭(zhēng)在盡可能短的時(shí)間內(nèi)找到盡可能多的路徑，或者是直接尋找最有可能通向軟件漏洞的路徑，測(cè)試對(duì)象也基本都是小型程序.

SwordSE 的停止規(guī)則分為兩種情況:①自動(dòng)停止，即當(dāng)搜索完目標(biāo)程序的所有執(zhí)行路徑(再也找不到新的路徑)時(shí)，自動(dòng)停止搜索，適用于小型程序;②強(qiáng)制停止，即通過(guò)設(shè)定一些閾值，達(dá)到閾值后即停止搜索，閾值可以是約束公式的最大長(zhǎng)度，也可以是禁忌表的最大元素個(gè)數(shù)等等，適用于中大型程序.

與Fuzzgrind 類似，SwordSE 提供一個(gè)配置文件“settings.cfg”來(lái)作為用戶接口.用戶可以通過(guò)編輯這個(gè)配置文件來(lái)設(shè)置第2.3.3 節(jié)提到的差值上限和本節(jié)提到的閾值等參數(shù)，配置文件的格式如圖7 所示.例如要測(cè)試軟件“gzip”，只需按照?qǐng)D7 的格式在配置文件中配置好各種參數(shù)，然后在命令行終端運(yùn)行“./SwordSE.py gzip”即可開(kāi)始測(cè)試.

圖7 配置文件格式Fig.7 Format of configuration file

3 實(shí)驗(yàn)分析

本節(jié)對(duì)SwordSE 進(jìn)行實(shí)驗(yàn)測(cè)試和性能評(píng)估，主要測(cè)試其兩個(gè)方面的能力:①路徑搜索能力，以經(jīng)典的動(dòng)態(tài)二進(jìn)制符號(hào)執(zhí)行工具Fuzzgrind 作為參照;②漏洞檢測(cè)能力，看它能否自動(dòng)檢測(cè)出0day 漏洞.

測(cè)試環(huán)境為:Intel i5-4200M，CPU 主頻為2.5 GHz，內(nèi)存為4 G，操作系統(tǒng)為Ubuntu 12.04 32位系統(tǒng).測(cè)試對(duì)象為運(yùn)行在Linux 系統(tǒng)下的一些常用的小型應(yīng)用軟件.

3.1 路徑搜索能力測(cè)試

主要測(cè)試在相同的時(shí)間內(nèi)，針對(duì)同一個(gè)目標(biāo)程序，SwordSE 和Fuzzgrind 兩者誰(shuí)找到的無(wú)重復(fù)路徑更多.需要說(shuō)明的是Fuzzgrind 并不能直接運(yùn)行在Ubuntu 12.04 系統(tǒng)上，而只能運(yùn)行在版本比較陳舊的Ubuntu 9.04 系統(tǒng)上，且依賴于較低版本的Valgrind.SwordSE 對(duì)Fuzzgrind 做了以下幾個(gè)方面的改進(jìn):①將其匹配到較新的Valgrind 版本，使它能夠在Ubuntu 12.04 上運(yùn)行;②增加了更多的指令支持，使它能測(cè)試代碼量更大的程序;③增加了命令行參數(shù)作為符號(hào)輸入;④引入了禁忌搜索算法.

因此，這一部分的實(shí)驗(yàn)，重點(diǎn)是比較引入禁忌搜索算法后的SwordSE 和未引入禁忌搜索算法的Fuzzgrind(移植到Ubuntu 12.04 上 后的Fuzzgrind)的路徑搜索效率.

實(shí)驗(yàn)過(guò)程如下:選取7 款軟件作為待測(cè)軟件，在配置文件中設(shè)置好各種參數(shù)，其中SwordSE 的“MaxCons”均設(shè)置為200，“MaxDiff”均設(shè)置為1，“MaxH”均設(shè)置為無(wú)限大;Fuzzgirnd 沒(méi)有“Max-Diff”和“MaxH”參數(shù)，“MaxCons”也均設(shè)置為200.對(duì)于同一款軟件，給定相同的種子輸入，開(kāi)啟兩個(gè)命令行終端，同時(shí)開(kāi)始運(yùn)行SwordSE 和Fuzzgrind，并計(jì)時(shí)，每隔一段時(shí)間查看兩者產(chǎn)生的測(cè)試用例的數(shù)目，并檢查是否有重復(fù)的測(cè)試用例產(chǎn)生.

表2 記錄了在使用SwordSE 和Fuzzgrind 測(cè)試7 款軟件時(shí)，測(cè)試時(shí)間分別為5 min 和10 min 時(shí)兩者找到的路徑數(shù)目.從表2 可以看出，在相同的時(shí)間內(nèi)，SwordSE 找到的路徑數(shù)目明顯多于Fuzzgrind.通過(guò)對(duì)二者產(chǎn)生的測(cè)試用例進(jìn)行檢查，發(fā)現(xiàn)SwordSE 生成的測(cè)試用例沒(méi)有重復(fù)而Fuzzgrind 生成的測(cè)試用例存在較多重復(fù).此外，在實(shí)驗(yàn)中還觀察到SwordSE 在達(dá)到閾值后能自動(dòng)停止，而Fuzzgrind 有時(shí)會(huì)陷入局部循環(huán)搜索(即循環(huán)往復(fù)的生成重復(fù)的測(cè)試用例)而停不下來(lái).綜上所述，SwordSE 的路徑搜索效率明顯優(yōu)于Fuzzgrind.

表2 SwordSE 和Fuzzgrind 路徑搜索能力比較Table 2 Comparison of SwordSE and Fuzzgrind’s path searching ability

3.2 漏洞檢測(cè)能力測(cè)試

這一部分實(shí)驗(yàn)主要測(cè)試SwordSE 的0day 漏洞檢測(cè)能力.截至目前為止，SwordSE 在實(shí)驗(yàn)中已經(jīng)發(fā)現(xiàn)了4 個(gè)0day 漏洞(這些漏洞用原始版本的Fuzzgrind 不可發(fā)現(xiàn))，包括兩個(gè)整數(shù)溢出漏洞、一個(gè)整數(shù)除0 漏洞和一個(gè)雙重釋放漏洞(double free)，具體如表3 所示.

表3 SwordSE 已檢測(cè)到的0day 漏洞Table 3 0day vulnerabilities detected by SwordSE

以wav2swf 0.9.2 整數(shù)除0 漏洞為例進(jìn)行分析.種子輸入為一個(gè)正常的wav 音頻文件yujian.wav，大小為172 KB，觸發(fā)漏洞的測(cè)試用例為第558個(gè)測(cè)試用例558.wav，對(duì)兩者的十六進(jìn)制格式進(jìn)行比較，發(fā)現(xiàn)它們的前19 個(gè)字節(jié)完全不同，其他字節(jié)均相同，如圖8 所示.

圖8 yujian.wav 與558.wav 前48 個(gè)字節(jié)Fig.8 The first 48 bytes of yujian.wav and 558.wav

漏洞現(xiàn)象如圖9 所示，當(dāng)以558.wav 作為wav2swf 0.92 的輸入時(shí)，軟件發(fā)生異常終止，系統(tǒng)提示發(fā)生了“浮點(diǎn)數(shù)例外(核心已轉(zhuǎn)儲(chǔ))”.通過(guò)進(jìn)一步跟蹤調(diào)試，找到該漏洞的起因是發(fā)生了整數(shù)除0 異常，558.wav 的第33 個(gè)和第34 個(gè)字節(jié)代表的數(shù)值“0x0000”被作為了除數(shù).

圖9 wav2swf 0.9.2 整數(shù)除0 漏洞現(xiàn)象Fig.9 Phenomenon of wav2swf 0.9.2 integer division by zero vulnerability

4 結(jié) 論

本文提出了一種基于禁忌搜索的動(dòng)態(tài)符號(hào)執(zhí)行方法，并實(shí)現(xiàn)了一個(gè)相應(yīng)的工具原型SwordSE.該方法充分利用了禁忌搜索算法的全局逐步尋優(yōu)能力，有效避免了重復(fù)路徑搜索和局部循環(huán)搜索問(wèn)題，大大提高了路徑搜索效率.SwordSE 不依賴于軟件源碼，直接面向二進(jìn)制程序，支持將文件和命令行參數(shù)這兩類輸入作為符號(hào)來(lái)實(shí)施動(dòng)態(tài)符號(hào)執(zhí)行，實(shí)驗(yàn)表明，相比現(xiàn)有動(dòng)態(tài)符號(hào)執(zhí)行方法，SwordSE 能夠在相同的時(shí)間內(nèi)找到更多的無(wú)重復(fù)測(cè)試用例，且在實(shí)驗(yàn)中已經(jīng)發(fā)現(xiàn)了4 個(gè)0day 漏洞，體現(xiàn)了較強(qiáng)的漏洞自動(dòng)化檢測(cè)能力.

References)

［1］ Armour-Brown C，Borntraeger C，F(xiàn)itzhardinge J，et al.Valgrind［EB/OL］.［S.l.，s.n.］［2015-05-15］.http:∥valgrind.org/.

［2］ Ganesh V，Hansen T.STP constraint solver［EB/OL］.［S.l.，s.n.］(2015-04-02)［2015-05-15］.http:∥stp.github.io/.

［3］ Glover F.Tabu search—Part I［J］.ORSA Journal on Computing，1989，1(3):190-206.

［4］ Glover F.Tabu search—Part II［J］.ORSA Journal on Computing，1990，2(1):4-32.

［5］百度百科.禁忌搜索算法［EB/OL］.［S.l.，s.n.］［2015-05-15］.http:∥baike.baidu.com/link?url=JqehYmMCAMqByyTSESOHM4_qjLUmbDLbM7L3iX2ZSu5vQRFpQgWXDR2Q2CDAR-qdgQfD4ORzYq5e3EvEUT_Ta.Baidu encyclopedia.Tabu search algorithm［EB/OL］.［S.l.，s.n.］［2015-05-15］.http:∥baike.baidu.com/link?url = JqehYmMCAMqByyTSESOHM4_qjLUmbDLbM7L3iX2ZSu5vQRFp Qg-WXDR2Q2CDAR-qdgQfD4OR-zYq5e3EvEUT_Ta.

［6］ 邢文訓(xùn)，謝金星.現(xiàn)代優(yōu)化計(jì)算方法［M］.第2 版.北京:清華大學(xué)出版社，2005:51-58.

Xing W X，Xie J X.Modern optimization methods［M］.2nd ed.Beijing:Tsinghua University Press，2005:51-58.

［7］ Cadar C，Godefroid P，Khurshid S，et al.Symbolic execution for software testing in practice:Preliminary assessment［C］∥Proceedings of the 33rd International Conference on Software Engineering.New York:ACM，2011:1066-1071.

［8］ Avgerinos T，Rebert A，Cha S K，et al.Enhancing symbolic execution with veritesting［C］∥Proceedings of the 36th International Conference on Software Engineering.New York:ACM，2014:1083-1094.

［9］ 王鐵磊.面向二進(jìn)制程序的漏洞挖掘關(guān)鍵技術(shù)研究［D］.北京:北京大學(xué)，2011.

Wang T L.Research on binary-executable-oriented software vulnerability detection［D］.Beijing:Peking University，2011(in Chinese).

［10］ Godefroid P，Klarlund N，Sen K.Dart:Directed automated random testing［C］∥Proceedings of the 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation.New York:ACM，2005:213-223.

［11］ Sen K，Marinov D，Agha G.Cute:A concolic unit testing engine for C［C］∥Proceedings of the Joint 10th European Software Engineering Conference and 13th ACM SIGSOFT Symposium on the Foundations of Software Engineering.New York:ACM，2005:263-272.

［12］ Cadar C，Ganesh V，Pawlowski P M，et al.EXE:Automatically generating inputs of death［J］.ACM Transactions on Information and System Security，2008，12(2):10.

［13］ Cadar C，Dunbar D，Engler D R.KLEE:Unassisted and automatic generation of high-coverage tests for complex systems programs［C］∥Proceedings of the 8th USENIX Symposium on Operating System Design and Implementation.Berkeley，CA:USENIX，2008，8:209-224.

［14］ Godefroid P，Levin M，Molnar D.Automated whitebox fuzz testing［C］∥Proceedings of the 16th Annual Network and Distributed System Security Symposium.［s.l.］:The Internet Society，2008:151-166.

［15］ Sogeti ESEC Lab.Fuzzgrind［EB/OL］.［S.l.，s.n.］［2015-05-15］.http:∥esec-lab.sogeti.com/pages/fuzzgrind.html.

［16］ Chipounov V，Kuznetsov V，Candea G.S2E:A platform for invivo multi-path analysis of software systems［J］.ACM SIGARCH Computer Architecture News，2011，39(1):265-278.

［17］ Martignoni L，McCamant S，Poosankam P，et al.Path-exploration lifting:Hi-fi tests for lo-fi emulators［J］.ACM SIGARCH Computer Architecture News，2012，40(1):337-348.

［18］ Moskewicz M W，Madigan C F，Zhao Y，et al.Chaff:Engineering an efficient SAT solver［C］∥Proceedings of the 38th Annual Design Automation Conference.New York:ACM，2001:530-535.

［19］ Goldberg E，Novikov Y.BerkMin:A fast and robust SAT-solver［J］.Discrete Applied Mathematics，2007，155(12):1549-1561.

［20］ Hamadi Y，Jabbour S，Sais L.ManySAT:A parallel SAT solver［J］.Journal on Satisfiability Boolean Modeling＆Computation，2009，6(4):245-262.

［21］ de Moura L，Bj?rner N.Tools and algorithms for the construction and analysis of systems［M］.Berlin Heidelberg:Springer，2008:337-340.

［22］ Bouton T，de Oliveira D C B，Déharbe D，et al.Automated deduction-CADE-22［M］.Berlin Heidelberg:Springer，2009:151-156.