面向熱點代碼的路徑搜索方法研究

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

(1.信息工程大學信息工程學院，河南鄭州450002;2.中國信息安全測評中心，北京100085)

0 引言

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

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

1 熱點代碼

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

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

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

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

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

2 面向熱點代碼的路徑搜索

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

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

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

2.1 DFS路徑遍歷

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

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

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

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

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

(3)路徑遍歷過程中每一輪將當前執(zhí)行路徑上的一個分支語句的路徑條件取反，即在符號執(zhí)行樹上前進一個分支，路徑搜索效率低。

2.2 熱點代碼最短路徑搜索算法

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

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

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

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

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

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

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

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

圖2 面向熱點代碼的最短路徑搜索算法

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

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

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

3 實驗及分析

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

圖3 不可達子路徑消除算法

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

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

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

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

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

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

表1 基準程序測試結果

4 結束語

熱點代碼 (hotspot)是程序缺陷的多發(fā)區(qū)。本文提出面向熱點代碼的路徑搜索方法，結合了靜態(tài)分析 (快速搜索最短可達路徑)和動態(tài)分析 (判斷路徑約束條件進一步判斷路徑可達性)的優(yōu)勢，與BFS及引入隨機搜索的啟發(fā)式搜索方法相比更有針對性。本文提出了單熱點搜索算法和多熱點搜索優(yōu)化策略，實驗結果表明該方法達到相同熱點代碼覆蓋率情形下能夠有效減少生成的測試路徑數(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.