劉 杰，王嘉捷，任 棟，王清賢

(1.信息工程大學(xué)信息工程學(xué)院，河南鄭州450002;2.中國(guó)信息安全測(cè)評(píng)中心，北京100085)

0 引言

符號(hào)執(zhí)行［1］(symbolic execution)基本思想是用符號(hào)值代替程序的具體輸入值，在模擬程序執(zhí)行過程中計(jì)算路徑的約束條件，求解約束條件并自動(dòng)生成測(cè)試輸入來遍歷程序中的所有可行路徑。

符號(hào)執(zhí)行是一種路徑敏感的分析方法，在遇到程序中分支語(yǔ)句、循環(huán)、嵌套調(diào)用等存在路徑爆炸問題，產(chǎn)生的路徑與程序內(nèi)部判斷分支的數(shù)量成指數(shù)級(jí)增長(zhǎng)。為了緩解路徑爆炸問題，提高測(cè)試覆蓋率，研究人員提出了多種路徑搜索策略。文獻(xiàn) ［2］采用了深度優(yōu)先 (depth-first search，DFS)搜索方法，并試圖在CFG上搜索與目標(biāo)或未覆蓋的分支的最短距離，該方法實(shí)際上程序目標(biāo)代碼覆蓋率較低，而且這種靜態(tài)搜索會(huì)生成不滿足約束條件的不可達(dá)路徑。為了快速覆蓋到程序缺陷語(yǔ)句，需求驅(qū)動(dòng)［3］(demand-driven)搜索方法首先選擇一定的目標(biāo)點(diǎn)，然后趨向于目標(biāo)點(diǎn)的方向遍歷生成執(zhí)行樹，如果發(fā)現(xiàn)執(zhí)行的路徑偏離目標(biāo)點(diǎn)，則選擇其它路徑繼續(xù)搜索。文獻(xiàn)［4］提出混合符號(hào)執(zhí)行 (hybrid concolic testing)思想，交互使用隨機(jī)測(cè)試和符號(hào)執(zhí)行以達(dá)到對(duì)程序狀態(tài)空間的較深和較廣的搜索，該算法適合于周期性的從運(yùn)行環(huán)境中得到輸入值的程序。SAGE［5］提出了代搜索 (generational search)策略，由種子文件驅(qū)動(dòng)程序執(zhí)行，在獲取一條執(zhí)行路徑后離線分析程序路徑約束并生成新一代測(cè)試用例，并采用覆蓋率標(biāo)準(zhǔn)對(duì)測(cè)試用例的優(yōu)先級(jí)排序，使得目標(biāo)程序每一代的執(zhí)行路徑更加深入。文獻(xiàn) ［6］提出了最佳優(yōu)先 (best-first search，BFS)搜索方法，采用啟發(fā)式方法優(yōu)先選取未覆蓋的代碼進(jìn)行遍歷，該方法提高了代碼覆蓋率但是仍缺乏遍歷目標(biāo)性。本文提出一種面向熱點(diǎn)代碼的路徑搜索方法，研究單熱點(diǎn)路徑搜索方法的基礎(chǔ)上，提出了多熱點(diǎn)最短路徑搜索優(yōu)化策略，該方法生成覆蓋熱點(diǎn)代碼的測(cè)試輸入時(shí)效率高。

1 熱點(diǎn)代碼

當(dāng)前軟件安全測(cè)試領(lǐng)域的研究表明，程序熱點(diǎn)代碼(hot spot code)［7］中存在更多代碼缺陷或安全漏洞，為了能夠盡可能多的發(fā)現(xiàn)程序缺陷，軟件安全測(cè)試更關(guān)心熱點(diǎn)代碼的執(zhí)行情況。本文中熱點(diǎn)代碼是指程序中容易觸發(fā)缺陷的代碼塊集合，熱點(diǎn)代碼主要有以下3種情況:

(1)圈復(fù)雜度 (cyclomatic complexity)［7］高的代碼塊:圈復(fù)雜度V(G)=E－N+2P，其中E表示控制流圖邊的數(shù)量，N表示節(jié)點(diǎn)數(shù)量，P表示控制流圖連接子圖數(shù)目 (通常為1)。較高的圈復(fù)雜度預(yù)示著難以理解的代碼，很可能比較脆弱或存在缺陷。

(2)包含危險(xiǎn)函數(shù)的代碼塊:處理外界環(huán)境引入的不可信輸入數(shù)據(jù)，但是邊界檢查不嚴(yán)格的函數(shù)。如字符串處理函數(shù)strcpy，strcat等，包含危險(xiǎn)函數(shù)的代碼塊容易觸發(fā)緩沖區(qū)漏洞。

(3)包含危險(xiǎn)指令的代碼塊:操作數(shù)被外界環(huán)境引入的不可信輸入數(shù)據(jù)污染，包含可能觸發(fā)程序異常甚至篡改執(zhí)行順序等操作的指令，如跳轉(zhuǎn) (jmp)、調(diào)用 (call，ret)以及數(shù)據(jù)轉(zhuǎn)移的目的地址 (rep movs)等，包含危險(xiǎn)操作的代碼塊容易引起程序異常甚至安全漏洞。

熱點(diǎn)代碼識(shí)別定位可通過程序靜態(tài)分析方法實(shí)現(xiàn)。生成程序的控制流圖，通過代碼度量方法識(shí)別第1種熱點(diǎn)代碼;通過函數(shù)和指令掃描識(shí)別和定位第2、3種熱點(diǎn)代碼，熱點(diǎn)代碼記為集合

2 面向熱點(diǎn)代碼的路徑搜索

識(shí)別程序的熱點(diǎn)代碼后，本文期望在路徑搜索中優(yōu)先生成能夠覆蓋熱點(diǎn)代碼的測(cè)試數(shù)據(jù)。為了便于描述路徑搜索算法，給出定義如下:

給定程序P的輸入向量I，則P的執(zhí)行過程對(duì)應(yīng)一條執(zhí)行路徑w。路徑w是若干條順序執(zhí)行的語(yǔ)句組成的序列，記為:w={l1，l2，…，li|i∈N}。用 w［l0，ln］表示所有以 l0為起點(diǎn)，以ln為終點(diǎn)的路徑。用w(l0，ln］表示所有以l0后繼節(jié)點(diǎn)為起點(diǎn)，以ln為終點(diǎn)的路徑，用w［l0，ln)表示所有以l0起點(diǎn)，以ln前驅(qū)節(jié)點(diǎn)為終點(diǎn)的路徑，使用|w|表示路徑長(zhǎng)度。

符號(hào)執(zhí)行的路徑條件和路徑之間有以下性質(zhì):對(duì)于任意程序路徑w，給定輸入向量I，程序P執(zhí)行路徑w當(dāng)且僅當(dāng)輸入向量I滿足w的路徑約束φw。

2.1 DFS路徑遍歷

符號(hào)執(zhí)行方法的路徑遍歷過程如下:給定初始輸入生成一條初始路徑，將執(zhí)行路徑上的分支語(yǔ)句的路徑條件逐個(gè)取反生成新路徑，求解新路徑約束條件并生成能夠引導(dǎo)程序執(zhí)行進(jìn)路徑的輸入數(shù)據(jù)，繼續(xù)上述遍歷過程直到所有的程序路徑都至少覆蓋一次結(jié)束。如圖1所示的符號(hào)執(zhí)行樹，Entry節(jié)點(diǎn)是程序入口，w1為初始執(zhí)行路徑，路徑約束為φw1={PC1∧PC2∧PC3}。將初始路徑上的路徑條件依次取反，那么相應(yīng)的路徑約束分別為:

圖1 符號(hào)執(zhí)行樹遍歷過程

DFS搜索方法每次將符號(hào)執(zhí)行樹上盡可能深的分支語(yǔ)句的路徑條件取反，直到該分支遍歷完畢后回溯到前一個(gè)分支繼續(xù)遍歷，通常對(duì)于一個(gè)有d個(gè)分支語(yǔ)句的程序，該方法生成2d條程序路徑。由于DFS搜索方法生成的2d條路徑中僅少部分路徑能夠覆蓋熱點(diǎn)代碼;而且搜索策略會(huì)優(yōu)先搜索路徑w1(如圖1)，直到w2及其后續(xù)路徑遍歷完成后才開始搜索可達(dá)熱點(diǎn)代碼的路徑w3，因此該方法效果不理想。基于DFS等搜索方法用于熱點(diǎn)代碼覆蓋測(cè)試時(shí)效率低，原因有以下三點(diǎn):

(1)未考慮當(dāng)前執(zhí)行路徑與熱點(diǎn)代碼之間的可達(dá)性，如果當(dāng)前分支與熱點(diǎn)代碼之間沒有可達(dá)路徑，仍然會(huì)持續(xù)深度優(yōu)先搜索并生成一系列無效測(cè)試用例;

(2)路徑遍歷過程中將當(dāng)前節(jié)點(diǎn)的孩子節(jié)點(diǎn)或兄弟節(jié)點(diǎn)的路徑條件取反生成新的執(zhí)行路徑，未考慮該執(zhí)行路徑上多個(gè)判斷分支節(jié)點(diǎn)與熱點(diǎn)代碼之間的距離;

(3)路徑遍歷過程中每一輪將當(dāng)前執(zhí)行路徑上的一個(gè)分支語(yǔ)句的路徑條件取反，即在符號(hào)執(zhí)行樹上前進(jìn)一個(gè)分支，路徑搜索效率低。

2.2 熱點(diǎn)代碼最短路徑搜索算法

在面向熱點(diǎn)代碼的覆蓋測(cè)試中可通過基于程序控制流圖的靜態(tài)分析方法優(yōu)化，文獻(xiàn)［8］提出了基于控制流導(dǎo)向的路徑搜索策略對(duì)DFS方法做了改進(jìn)，但是靜態(tài)搜索的路徑可能在實(shí)際執(zhí)行時(shí)不可達(dá)。本文通過在程序控制流圖上搜索能夠到達(dá)熱點(diǎn)代碼路徑，并生成路徑約束判斷路徑可達(dá)性，引導(dǎo)遍歷過程快速覆蓋熱點(diǎn)代碼。

程序控制流圖 (control flow graph，CFG)可以用四元組G=(N，E，Entry，Exit)表示，其中N是節(jié)點(diǎn)集合，每個(gè)節(jié)點(diǎn)是一個(gè)具有唯一出口和唯一入的基本代碼塊，E是邊的集合，每條邊是一個(gè)有序節(jié)點(diǎn)對(duì)〈Ni，Nj〉，他表示從Ni到Nj可能存在控制轉(zhuǎn)移，Entry表示程序的入口節(jié)點(diǎn) (只有一個(gè))，Exit表示出口節(jié)點(diǎn) (可能不止一個(gè))。在程序CFG上的熱點(diǎn)代碼最短路徑搜索包括以下兩個(gè)步驟:

(1)分支語(yǔ)句與熱點(diǎn)代碼之間的最短路徑搜索。對(duì)于程序執(zhí)行路徑w，在程序CFG上搜索條件路徑wc={c1，c2，…，ci|i∈N}中的分支語(yǔ)句與熱點(diǎn)代碼h之間的最短路徑。該問題與單源最短路徑問題類似，通過迪杰斯特拉算法求解。搜索結(jié)果為最短路徑集合{w［ci，h］|i∈N}，并按照路徑長(zhǎng)度排序，如果沒有可達(dá)路徑則|w［ci，h］|=∞ 。

(2)最短路徑的約束條件。從程序入口到熱點(diǎn)代碼的完整路徑 w=w［l0，ci］∪w［ci，h］，由從程序入口到某分支語(yǔ)句的前段路徑wp=w［l0，ci］和分支語(yǔ)句到熱點(diǎn)代碼的后段路徑 ws=w［ci，h］兩段路徑組成。由于路徑 w［l0，ci］是程序的真實(shí)執(zhí)行路徑，路徑約束可滿足;而w［ci，h］是靜態(tài)分析得到的路徑，路徑約束可能不滿足。通過符號(hào)執(zhí)行方法計(jì)算φs的路徑約束。完整的路徑約束為φw=φp∧φs。

圖2給出了面向熱點(diǎn)代碼的最短路徑搜索算法，該算法采用多輪搜索方法，每輪選定當(dāng)前路徑與熱點(diǎn)代碼h的最短可達(dá)路徑生成測(cè)試用例t驅(qū)動(dòng)程序執(zhí)行，最終返回能夠覆蓋熱點(diǎn)代碼h的程序路徑w。

2.3 多熱點(diǎn)代碼路徑搜索優(yōu)化

對(duì)于程序中的熱點(diǎn)代碼集合H={h1，h2，…，hi|i∈N}，圖2所示的算法可逐個(gè)對(duì)熱點(diǎn)代碼進(jìn)行覆蓋測(cè)試。由于搜索過程中存在多個(gè)熱點(diǎn)代碼被同一條執(zhí)行路徑覆蓋的情況，或者多個(gè)熱點(diǎn)代碼的最短路徑經(jīng)過了當(dāng)前執(zhí)行路徑w的同一個(gè)分支語(yǔ)句ci，即存在公共路徑。為了減少冗余路徑，更快的覆蓋熱點(diǎn)代碼集合，對(duì)于多熱點(diǎn)代碼搜索問題有以下3種優(yōu)化策略:

(1)多熱點(diǎn)代碼最短路徑搜索。在程序CFG上搜索條件路徑中的分支語(yǔ)句與熱點(diǎn)代碼集合之間的最短路徑。類似于多源最短路徑問題，采用弗洛伊德算法求解。

圖2 面向熱點(diǎn)代碼的最短路徑搜索算法

(2)測(cè)試用例t的選取:對(duì)于搜索到的熱點(diǎn)代碼最短路徑集合{w［ci，hn］|i，n∈N}，優(yōu)先選取能夠覆蓋多個(gè)熱點(diǎn)代碼的程序路徑或者經(jīng)過相同分支語(yǔ)句ci的測(cè)試用例t。如果發(fā)現(xiàn)wn執(zhí)行路徑能夠覆蓋熱點(diǎn)代碼hn，則將hn從熱點(diǎn)代碼集合H中刪除，繼續(xù)搜索其它熱點(diǎn)代碼的最短路徑。

(3)不可達(dá)子路徑消除。到達(dá)熱點(diǎn)代碼hm和hn之間存在公共子路徑子路徑的路徑約束有以下性質(zhì):對(duì)于程序路徑w的一個(gè)子路徑w'，w'是連續(xù)的且w'∈w，如果φw約束可滿足，那么對(duì)于約束可滿足;反之，如果-w'，w'∈w，如果φw'約束不可滿足，則必有φw約束不可滿足。

圖3所示不可達(dá)子路徑消除的輔助算法，該算法輸入當(dāng)前條件路徑wc和熱點(diǎn)代碼集合H，采用自動(dòng)學(xué)習(xí)方式收集搜索過程的不可達(dá)的子路徑，用于后續(xù)路徑的可達(dá)性判斷。根據(jù)子路徑約束的性質(zhì)，對(duì)于每輪搜索到的最短路徑首先判斷是否包含Θ中的某條不可達(dá)路徑，如果是則不可達(dá);該策略可省去計(jì)算的路徑約束和約束求解的開銷。算法最后輸出到達(dá)熱點(diǎn)代碼的最短路徑及其路徑約束集合Wmin。

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

實(shí)現(xiàn)了一個(gè)基于微軟的編譯器架構(gòu)Phonix［9］的路徑搜索插件HotTrace，Phonix支持對(duì)高級(jí)語(yǔ)言編譯器前端產(chǎn)生的代碼中間表示進(jìn)行分析、優(yōu)化和測(cè)試，能夠?yàn)橥獠坎寮峁┴S富的分析代碼庫(kù)。HotTrace提取程序的控制流圖CFG，根據(jù)靜態(tài)分析結(jié)果在CFG標(biāo)識(shí)熱點(diǎn)代碼位置;基于Phonix生成的中間表示IR上運(yùn)行符號(hào)執(zhí)行引擎，收集條件路徑的約束條件;采用微軟開發(fā)的Z3［10］求解器進(jìn)行路徑約束求解。

圖3 不可達(dá)子路徑消除算法

測(cè)試對(duì)象為Verisec Security Benchmark［11］集合 (Verisec 0.2，經(jīng)典的緩沖區(qū)溢出缺陷測(cè)試代碼集，收集了12個(gè)開源軟件的發(fā)生緩沖區(qū)溢出缺陷的真實(shí)代碼片段)中的4個(gè)程序，如表1所示。其中定位的熱點(diǎn)代碼為:WU-ftpd［linkpath-strcpy-strcat］、Sendmail［arr-chars-bad］、OpenSER［full-ptr-bad］、Apache［prefix-ptr-bad］。

實(shí)驗(yàn)過程:由于4個(gè)程序都是讀取函數(shù)參數(shù)作為輸入數(shù)據(jù)，首先給定初始參數(shù);分別采用BFS［6］方法和HotTrace方法進(jìn)行路徑搜索，生成新的輸入?yún)?shù)并驅(qū)動(dòng)程序執(zhí)行;程序執(zhí)行過程中檢測(cè)熱點(diǎn)代碼的覆蓋情況。當(dāng)BFS方法和HotTrace方法對(duì)熱點(diǎn)代碼的覆蓋率超過90%時(shí)，終止測(cè)試過程。

測(cè)試結(jié)果見表1，與BFS方法相比，HotTrace在達(dá)到同樣的熱點(diǎn)代碼覆蓋率 (90%)時(shí)，需要遍歷的執(zhí)行路徑數(shù)量減少了68.6%。路徑搜索時(shí)間減少了近2/3。HotTrace方法對(duì)于熱點(diǎn)代碼覆蓋效率有較大提高。對(duì)實(shí)驗(yàn)結(jié)果的進(jìn)一步分析如下:

(1)實(shí)驗(yàn)過程中有少部分熱點(diǎn)代碼沒有覆蓋到，原因是HotTrace采用的最短路徑搜索策略是一種貪心算法，搜索CFG得到的最短路徑可能不可達(dá)，而實(shí)際可達(dá)路徑卻不是最短路徑。實(shí)際情況下要求測(cè)試覆蓋率達(dá)到100%是不可能，HotTrace的目標(biāo)是快速覆蓋代碼熱區(qū)。

(2)引入不可達(dá)子路徑消除對(duì)于路徑可達(dá)性分析有很大貢獻(xiàn)，HotTrace在實(shí)驗(yàn)過程中收集了約1600條不可達(dá)子路徑，利用這些路徑在后續(xù)路徑判斷中直接排除5000多條路徑。由于對(duì)程序路徑的符號(hào)執(zhí)行和約束求解運(yùn)算相對(duì)耗時(shí)較多，該策略有效降低了分析時(shí)間。

(3)HotTrace通過分段路徑約束方法生產(chǎn)的測(cè)試輸入在程序?qū)嶋H執(zhí)行未能覆蓋預(yù)期的最短路徑，實(shí)驗(yàn)中測(cè)試輸入的失效率為42%，跟蹤分析發(fā)現(xiàn)符號(hào)執(zhí)行在遇到符號(hào)化地址和循環(huán)時(shí)運(yùn)算不精確，導(dǎo)致最短路徑采用靜態(tài)符號(hào)執(zhí)行分析計(jì)算路徑約束時(shí)有較大誤差，該問題是靜態(tài)符號(hào)執(zhí)行的固有問題，通過循環(huán)優(yōu)化和指針推理方法優(yōu)化路徑約束計(jì)算。

表1 基準(zhǔn)程序測(cè)試結(jié)果

4 結(jié)束語(yǔ)

熱點(diǎn)代碼 (hotspot)是程序缺陷的多發(fā)區(qū)。本文提出面向熱點(diǎn)代碼的路徑搜索方法，結(jié)合了靜態(tài)分析 (快速搜索最短可達(dá)路徑)和動(dòng)態(tài)分析 (判斷路徑約束條件進(jìn)一步判斷路徑可達(dá)性)的優(yōu)勢(shì)，與BFS及引入隨機(jī)搜索的啟發(fā)式搜索方法相比更有針對(duì)性。本文提出了單熱點(diǎn)搜索算法和多熱點(diǎn)搜索優(yōu)化策略，實(shí)驗(yàn)結(jié)果表明該方法達(dá)到相同熱點(diǎn)代碼覆蓋率情形下能夠有效減少生成的測(cè)試路徑數(shù)量。

［1］Corina SW.Visser:A survey of new trends in symbolic execution for software testing and analysis［J］.International Journal on Software Tools for Technology Transfer，2009，11(4):339-353.

［2］Burnim J，Sen K.Heuristics for scalable dynamic test generation［C］//Proceedings of the 23th International Conference on Automated Software Engineering.L'Aquila，Italy，IEEE Computer Society Press，2008:443-446.

［3］Anand S，Godefroid P，Tillmann N.Demand-driven compositional symbolic execution［C］//Procee-dings of 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems.Berlin，Heidelberg:Springer-Verlag，2008:367-381.

［4］Majumdar R，Sen K.Hybrid Concolic testing［C］//Proceedings of 29th International Conference on Software Engineering.DC，USA:IEEE Computer Society Press，2007:416-426.

［5］Godefroid P，Levin M，Molnar D.Automated whitebox fuzz testing［C］//Proceedings of the 15th Annual Network and Distributed System Security Symposium.San Diego，CA:Internet Society Press，2008.

［6］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):1-38.

［7］Viet Hung Nguyen，Le Minh Sang Tran.Predicting vulnerable software components with dependency graphs［C］//Procee-dings of the6th International Workshop on Security Measurements and Metrics.Bolzano，Italy:ACM Press，2010.

［8］Saparya K，HSIAO S，Loganathan L.Strategies for scalable symbolic execution-driven test generation for programs［J］.Science China Information Sciences， September， 2011， 54 (9):1797-1812.

［9］Phoenix-Microsoft research［EB/OL］.［2010-10-04］.http://research.microsoft.com/en-us/collaboration/focus/cs/phoenix.aspx.

［10］Z3.An efficient SMT solver［EB/OL］.［2010-10-01］.http://research.microsoft.com/en-us/um/redmond/projects/z3/.

［11］Ku K，Hart T E，Chechik M，et al.A buffer overflow benchmark for software model checkers［C］//Proceedings of 22th International Conference on Automated Software Engineering.NY，USA:ACM Press，2007:389-392.