甘水滔 , 王林章 , 謝向輝 , 秦曉軍 , 周 林 , 陳左寧

1(數(shù)學工程與先進計算國家重點實驗室,江蘇 無錫 214083)

2(計算機軟件新技術國家重點實驗室(南京大學),江蘇 南京 210023)

大多數(shù)應用軟件中存在多個功能選項.在Linux 系統(tǒng)下,目錄“/bin”和“/usr/bin”下的絕大多數(shù)應用程序包含多個功能選項,表 1 中列舉了從Linux 系統(tǒng)下隨機挑選的應用程序,并且統(tǒng)計了各自的功能選項數(shù)量,如coreutils8.22 中的ls 程序包含54 個選項,who 程序中包含14 個選項,mkdir 程序中包含6 個選項,diffutils3.2 中diff 程序包含46 個選項等.可以發(fā)現(xiàn),每個功能選項或幾個功能選項組合,對應程序中一部分獨立的執(zhí)行路徑.圖1 給出了一個典型的示例程序.該程序從命令行可輸入a,b,c,d,e,f等選項,每個選項的輸入將執(zhí)行其對應的功能函數(shù),如a選項對應exe_a函數(shù)等,選項e和選項f必須在選項c使用之后有效.本文把程序的命令行選項開關稱為功能標簽.

Table 1 Parts of applications containing function label random relected in Linux system表1 Linux 系統(tǒng)下的隨機挑選的部分包含功能標簽的應用程序

Fig.1 Sample program圖1 示例程序

針對這種帶功能標簽的應用軟件,其測試手段主要依賴于靜態(tài)分析和動態(tài)分析兩大類方法.靜態(tài)分析可以通過控制流、數(shù)據(jù)流分析等方法[1]獲取功能標簽、程序路徑及程序缺陷的相關信息,但由于不能構造測試用例,無法驗證其分析結果的真實性.動態(tài)分析方法主要分為基于輸入數(shù)據(jù)變異的動態(tài)分析方法[2]和符號執(zhí)行分析方法[3]:基于輸入數(shù)據(jù)變異的動態(tài)分析方法在不知道功能標簽信息的情況下,難以自動生成功能標簽信息,因而在測試的過程中極其容易陷入只對部分或極少數(shù)的功能路徑進行分析,具有很強的隨機性;符號執(zhí)行方法把程序的外部輸入數(shù)據(jù)視為符號變量,運行并分析程序路徑上的所有語句,對數(shù)據(jù)依賴于外部輸入的變量進行符號化,不斷收集條件分支語句的條件約束建立相應的約束系統(tǒng),再利用約束求解器判定并求解執(zhí)行路徑對應的約束集,能夠自動生成可行路徑的測試例.通過精確地模擬程序的執(zhí)行、跟蹤變量的所有取值,理論上,符號執(zhí)行可以做到對任意可執(zhí)行路徑的覆蓋,實現(xiàn)對所有功能標簽相關路徑的測試例求解.因此,與其他測試方法相比,在功能覆蓋及全局路徑的覆蓋效果上,符號執(zhí)行方法更能適應于該類帶功能標簽的應用軟件.但程序路徑爆炸和求解開銷過大,一直是限制符號執(zhí)行分析效率的主要難題,尤其是在不知道程序執(zhí)行路徑片段和各個功能標簽關系的前提下,利用符號執(zhí)行進行程序分析會面臨以下3 個問題.

?問題1:對于給定的可能存在缺陷的執(zhí)行路徑片段,難以確定較優(yōu)的路徑搜索策略進行動態(tài)目標制導.

如圖1 和后文圖3,假設需要制導的路徑位置處于功能標簽c和e的相關路徑中,當選擇采用深度優(yōu)先搜索策略(DFS)時,必須遍歷所有和功能標簽a和b相關的路徑;當采用廣度優(yōu)先搜索策略(BFS)進行路徑制導時,如果目標點較深,也將遍歷與功能標簽c和e之外的功能標簽相關路徑;當選擇采用隨機搜索策略時,將會以極小的概率制導該路徑片段.

?問題2:難以對某功能標簽的所有相關路徑進行正確性驗證.

如圖1 和后文圖3,假設只需要驗證功能標簽e相關的執(zhí)行路徑,和問題1 類似,在不知道功能標簽信息前提下,不論采用何種路徑搜索策略,無法只選擇某功能標簽相關路徑.如果采取種子模式,即構造一個帶選項e的測試例進行混合執(zhí)行,由于不知道功能標簽之間的關系,難以構造測試例成功到達功能標簽e相關的執(zhí)行路徑中.

?問題3:容易卡在某個包含多層循環(huán)的功能標簽代碼片段上.

如果某塊功能代碼中包含多層循環(huán)結構,一旦符號執(zhí)行分析進入該代碼中,容易導致過度的時間消耗,難以執(zhí)行到其他的功能代碼上,這樣不利于對程序的全局覆蓋測試.

針對以上3 個問題,本文提出一種基于程序功能標簽切片的制導符號執(zhí)行分析方法(OPT-SSE),根據(jù)程序的功能文檔建立相應的功能標簽集合,利用靜態(tài)分析方法對程序進行不同功能劃分,在程序依賴圖上生成不同功能標簽的切片,把執(zhí)行路徑有序的映射到不同功能上,對于給定需要制導的目標點,提取與目標點相關的切片,通過對切片相關節(jié)點進行標記,為符號執(zhí)行的路徑選擇提供制導信息.利用預定義的功能標簽流制導規(guī)則裁剪無關路徑,不僅可以加速目標點制導過程以及提升特定功能模塊的覆蓋率,通過功能切片的制導信息分離,還提升了對整個程序的覆蓋率.

本文第1 節(jié)描述OPT-SSE 的基本實現(xiàn)框架和流程,簡要分析該模型如何對圖1 給出的示例程序進行制導加速及全局覆蓋率提升,并給出模型后面算法和規(guī)則描述的基本定義.第2 節(jié)描述功能標簽流排序算法.第3 節(jié)描述基于符號執(zhí)行的功能標簽流制導規(guī)則.第4 節(jié)描述測試與分析.第5 節(jié)對符號執(zhí)行相關工作進行總結.第6節(jié)對本文主要工作進行總結.

1 基于程序功能標簽切片的制導符號執(zhí)行分析模型

1.1 模型概述

圖2 給出了功能切片符號執(zhí)行模型OPT-SSE(OPT-sliced symbolic execution)的主要執(zhí)行流程,具體如下.

(1)獲取功能標簽.分析軟件的功能文檔,獲取功能標簽集合,如命令行功能選項集合.

(2)靜態(tài)控制流分析與制導規(guī)則生成.首先,生成軟件代碼的中間代碼,生成每個基本塊的相關信息,再利用控制流分析生成控制流圖CFG;其次,遍歷該程序控制流圖,確定每個和功能標簽相關的基本塊,生成功能標簽控制流圖OPT-CFG;最后,在功能標簽控制流圖基礎上,遍歷生成功能標簽路徑OPT-Path,并利用排序規(guī)則進行排序.

(3)制導符號執(zhí)行.

?將特定功能或特定代碼目標點映射到對應的一條或多條功能標簽路徑.

?在符號執(zhí)行分析過程中,引入針對功能標簽路徑的制導規(guī)則.制導規(guī)則包括兩種:一種為不帶功能標簽路徑排序信息的制導規(guī)則,另一種是帶功能標簽路徑排序信息的制導規(guī)則.

?針對特定功能對應的功能標簽路徑,生成相應的測試例集合,并進行缺陷分析.

?針對特定代碼目標點進行制導分析,需要生成相應的可達測試例集合.

Fig.2 Guided symbolic execution model based on program function label slice (OPT-SSE)圖2 基于程序功能標簽切片的制導符號執(zhí)行模型(OPT-SSE)

以圖1 的程序為示例,圖3 和圖4 展示了OPT-SSE 模型的優(yōu)化思想.

Fig.3 OPT-SSESpeeding up goal-guided process圖3 OPT-SSE加速目標點制導

Fig.4 OPT-SSEImproving whole coverage圖4 OPT-SSE提升全局覆蓋率

圖3 描述了OPT-SSE 模型加速目標點制導過程:通過靜態(tài)分析目標點和各個功能標簽的隸屬關系,為符號執(zhí)行過程提供特定功能代碼分析的制導信息,在符號執(zhí)行框架下,定義針對不同指令的制導語義規(guī)則,盡早地裁剪無關的路徑分支,以加速動態(tài)符號執(zhí)行的目標制導過程.其中,實線箭頭指向的路徑是需要制導的目標路徑,斜杠表示的是分支裁剪操作.圖4 描述了OPT-SSE 模型提升全局覆蓋率過程:通過對不同的功能代碼進行有效分割,可對整個程序進行并行化符號執(zhí)行;同時,采用多個客戶端對不同的功能代碼塊進行分析,可避免卡在對某個功能代碼塊的分析上,以提升全局覆蓋率.即同時采用多個符號,執(zhí)行客戶端對不同的實線箭頭指向的路徑進行制導分析.

1.2 模型基本定義

定義1(程序功能標簽).一個測試程序的功能文檔中可獲取有限個功能標簽,構成一張功能標簽符號表OPT={option0,option1,…,optionnum},num為功能標簽的個數(shù),optioni表示為程序的第i個功能標簽(0＜i＜num).

定義2(功能類型分支判定條件).對于功能標簽符號表OPT={option0,option1,…,optionnum}的程序,其功能類型分支判定條件集用OPTcondition描述.用樹結構描述程序中任一分支判定條件condition對應的表達式,操作符operators為中間節(jié)點,操作數(shù)operands為葉子節(jié)點,判定分支判定條件condition是否為功能類型分支判定條件,根據(jù)以下等價關系:

定義3(程序控制流圖).程序控制流圖CFG用四元組〈N,E,entry,exit〉表示,其中,N表示該過程的節(jié)點集合,E是邊的集合,entry表示入口節(jié)點,exit表示退出節(jié)點.任一節(jié)點表示為一組連續(xù)順序執(zhí)行語句的基本塊,其中,N和entry節(jié)點包含的最后一條語句為分支語句.每條邊是一個表示從節(jié)點ni到節(jié)點nj可能存在控制流轉移的有序節(jié)點對〈ni,nj〉,并滿足:ni是nj的直接前驅,nj是ni的直接后繼.每個節(jié)點可以有多個直接前驅節(jié)點,但至多有兩個直接后繼節(jié)點.entry是一個沒有前驅的節(jié)點,exit出是一個沒有后繼的節(jié)點.

定義4(程序執(zhí)行路徑).對于一個程序控制流圖CFG,任意存在控制流轉移的有序節(jié)點對〈ni,ni+1〉,從節(jié)點ni執(zhí)行到節(jié)點ni+1必須滿足分支條件conditioni,定義為,那么對于程序執(zhí)行路徑集合Path,其任一條路徑用有限個有序節(jié)點〈n1,…,nj〉表示,定義為,并滿足:

定義5(程序執(zhí)行路徑片段).對于一個程序控制流圖CFG,其生成的路徑片段集合為PathSeg,一條執(zhí)行路徑片段用有限個有序節(jié)點〈n1,…,nj〉表示,定義為

定義6(功能標簽控制流圖).一個功能標簽控制流圖OPT-CFG可由程序控制流圖CFG遍歷生成,用四元組〈N′,E′,entry,exit〉表示,其中:N′表示該過程的節(jié)點集合,每個過程節(jié)點表示某個功能標簽激活后直接到達的基本塊;E′是邊的集合;entry表示入口節(jié)點;exit表示退出節(jié)點.每條邊用有序節(jié)點對描述,表示從節(jié)點到節(jié)點之間存在并且只存在一條功能標簽控制流.節(jié)點到節(jié)點之間存在一條功能標簽控制流邊的充要條件為:程序存在一條從的語句到達的語句的執(zhí)行路徑

定義7(功能標簽執(zhí)行流).對于一個功能標簽控制流圖OPT-CFG,功能標簽執(zhí)行路徑集合用OPT-Path表示,對于任意控制流,從節(jié)點執(zhí)行到節(jié)點必須滿足約束集合constrainti定義為,其任一條路徑用有限個有序節(jié)點表示,并滿足:

性質1(功能標簽執(zhí)行流約束集).對于節(jié)點執(zhí)行到節(jié)點的約束集合constrainti,一定滿足:

性質2(用OPT-Path 對Path 進行分類).存在一個函數(shù)Ψ,實現(xiàn)Path到OPT-Path的映射關系:

證明:由定義可知:對于給定的程序,其程序控制流圖CFG生成執(zhí)行路徑集合Path;功能標簽控制流圖OPTCFG生成功能標簽執(zhí)行路徑集合OPT-Path.對于任意一條可執(zhí)行路徑X=〈n1,…,nj〉∈Path,通過刪除其中的與功能類型分支判定條件語句無關的過程節(jié)點,得到節(jié)點有序序列,一定滿足:,由根據(jù)定義6 可知,.因此,任意一條可執(zhí)行路徑X可通過函數(shù)Ψ映射到唯一的一條功能標簽執(zhí)行流Y.□

定義8(偏序關系算子).偏序算子⊙={?,?}用來描述分支節(jié)點的后續(xù)節(jié)點的大小關系或者同一程序下任一兩條執(zhí)行路徑的大小關系,對于節(jié)點n(分支條件為condition)的true 后續(xù)節(jié)點nt和false 后續(xù)節(jié)點nf,則定義為或者〈n,nt〉?〈n,nf〉.

定義9(程序控制流執(zhí)行路徑的偏序關系).程序控制流中兩條不同執(zhí)行路徑〈n11,…,n1i〉和〈n21,…,n2j〉,偏序關系的判定定義如下:

定義9 表明,對于一個程序中任意兩條不同路徑,一定存在某個分叉節(jié)點,使得一條路徑執(zhí)行true 分支,另一條路徑執(zhí)行false 分支.那么執(zhí)行true 分支的路徑大于執(zhí)行false 分支的路徑,這樣可對一個程序中所有不同的可執(zhí)行路徑進行大小關系排序.

定義10(功能標簽執(zhí)行流的偏序關系).如果程序中任意映射到兩條功能標簽執(zhí)行流〈〈n11,…,n1i〉〉,〈〈n21,…,n2j〉〉的執(zhí)行路徑存在相同的偏序關系,那么這兩條功能標簽執(zhí)行流也存在類似的偏序關系,即滿足:

性質3.同一程序下,任意不同功能標簽執(zhí)行流存在偏序關系:

證明:設存在〈n1,…,nk〉,〈nx1,…,nxp〉,,滿足:當時,根據(jù)假設,一定存在n2y(1＜y≤j)或者n1d(1＜d≤i),n2y和n1d其中至少有一個節(jié)點具有兩個相同的功能標簽控制流前驅節(jié)點,這樣與定義6 相矛盾,假設不成立.所以,任意不同功能標簽執(zhí)行流之間存在偏序關系.□

定義11(帶制導信息的符號執(zhí)行狀態(tài)).符號執(zhí)行環(huán)境下生成的程序狀態(tài)集合為S,任一狀態(tài)S∈S用五元組〈s,ρ,σ,g,f〉表示,其中,s表示狀態(tài)S下一步執(zhí)行的語句序列,ρ表示狀態(tài)S的約束條件集合,σ表示狀態(tài)S的符號變量到符號值的映射關系,g表示狀態(tài)S下一步需要制導的基本塊信息,f表示狀態(tài)S需要制導的功能標簽流.

2 功能標簽流排序算法

功能標簽路徑生成和排序算法OptPathGenerationAndSorting第1 行～第8 行通過對每個過程內(nèi)控制流圖進行線性掃描,獲取包含功能標簽分支語句的基本塊,再通過控制流分析確定滿足功能標簽分支條件的后繼基本塊,加入到功能標簽節(jié)點集合OptNode中;第9 行通過調用OptCfgGeneration函數(shù)生成過程控制流圖對應的功能標簽控制流圖OptCfg;第10 行、第11 行對第1 條功能標簽路徑的節(jié)點數(shù)量初始化;第12 行通過調用OptPathSorting生成排序好的功能標簽路徑集合.

功能標簽路徑生成和排序算法.OptPathGenerationAndSorting.

功能標簽控制流圖生成算法OptCfgGeneration利用兩遍遍歷從程序控制流圖生成功能標簽控制流圖,算法第1 行～第13 行第1 遍深度遍歷生成功能標簽控制流圖的中間圖,該圖會出現(xiàn)某個功能標簽節(jié)點可能出現(xiàn)多個相同的前驅節(jié)點;算法第14 行～第23 行通過對每個功能標簽節(jié)點進行檢查,對于出現(xiàn)多個相同的前驅節(jié)點的功能標簽節(jié)點,復制一個別名功能標簽節(jié)點,并建立和功能標簽節(jié)點的映射關系,這樣就能確立功能標簽路徑的唯一性.圖5 給出了一個樣例.

功能標簽控制流圖生成算法.OptCfgGeneration.

Fig.5 Uniqueness generation for function label path圖5 功能標簽路徑唯一性確立

功能標簽流排序算法OptPathSorting對功能標簽控制流圖深度遍歷生成功能標簽路徑集合,根據(jù)路徑生成的先后次序正好確定了功能標簽路徑的偏序關系.

功能標簽流排序.OptPathSorting.

3 基于符號執(zhí)行的功能標簽流制導規(guī)則

以下定義了兩種功能標簽流制導規(guī)則:無排序信息的功能標簽流制導規(guī)則和帶序信息的功能標簽流制導規(guī)則.每種制導規(guī)則都實現(xiàn)了3 種指令處理語義規(guī)則:調用指令處理語義規(guī)則、分支指令處理語義規(guī)則、其他指令處理語義規(guī)則.由于分支指令處理語義涉及的情況多,表2 定義了規(guī)則中使用的部分基本符號,作為任意語義描述的前提條件,使用真值表(表3 和表4)對前置條件的取值進行描述,并對應不同的語義情況,表5 為表3、表4 中前置條件對應的輸出集合.

Table 2 Basic symbol definition of rule (as precondition for any semantic description)表2 規(guī)則基本符號定義(作為任意語義描述的前提條件)

Table 3 Precondition truth Table 2 on branch instruction processing semantics of function label flow guided rule without ordering information表3 無排序信息的功能標簽流制導規(guī)則中分支指令處理相關語義前置條件真值表2

Table 4 Precondition truth Table 3 on branch instruction processing semantics of function label flow guided rule without ordering information表4 無排序信息的功能標簽流制導規(guī)則中分支指令處理相關語義前置條件真值表3

Table 5 Precondition and related output assemble表5 前置條件和對應的輸出集合

Fig.6 Finite state machine model for guided symbolic state information conversion圖6 符號狀態(tài)制導信息轉換的有限狀態(tài)機模型

無排序信息的功能標簽流制導規(guī)則：

調用指令處理語義規(guī)則：

調用指令處理語義1 描述的是當調用一個函數(shù)時的制導符號狀態(tài)的變化情況,調用指令處理語義2 描述的是當從一個函數(shù)返回時的制導符號狀態(tài)的變化情況.

分支指令處理語義規(guī)則：

圖7 對應了分支指令處理語義規(guī)則的各種語義:語義1 和語義2 表示只有一個條件分支可滿足,并且直接跳轉到目標功能標簽流對應的相關節(jié)點;語義3 和語義4 表示只有一個條件分支可滿足,并且直接跳轉到非功能標簽節(jié)點;語義5 和語義6 表示只有一個條件分支可滿足,并且直接跳轉到與目標功能標簽流不相關的功能標簽節(jié)點;語義7～語義19 表示兩個條件分支均可滿足,分別跳轉到與目標功能標簽流不相關的功能標簽節(jié)點、與目標功能標簽流相關的功能標簽節(jié)點、非功能標簽節(jié)點的各種組合情況;語義20 表示當制導符號狀態(tài)下一步需要制導的基本塊信息g=ε時,直接刪除該制導符號狀態(tài).

Fig.7 Branch instruction processing semantics of function label flow guided rule without ordering information圖7 無排序信息的功能標簽流制導規(guī)則中分支指令處理相關語義

其他指令處理語義規(guī)則:

調用指令處理語義規(guī)則和其他指令處理語義規(guī)則與無排序信息的功能標簽流制導規(guī)則中各條語義的前置條件、輸入、輸出完全一樣;分支指令處理語義規(guī)則與無排序信息的功能標簽流制導規(guī)則下第1 條～第7 條和第10 條～第20 條共18 條語義的前置條件、輸入、輸出完全一樣;第8 條和第9 條語義更改為以下4 條語義操作:前兩條語義實現(xiàn)圖8 中的裁剪策略1,后兩條語義實現(xiàn)了圖8 中的裁剪策略2.裁剪策略1 表示當制導的兩個分支中,其中一個基本塊屬于制導的特定功能標簽之外的功能標簽時,另一個基本塊屬于非特定功能標簽,并滿足屬于制導的特定功能標簽之外的功能標簽的基本塊在外側.由于內(nèi)側的基本塊或后續(xù)基本塊仍然可能屬于特定功能標簽,所以只能裁剪掉包含屬于制導的特定功能標簽之外的功能標簽的分支.裁剪策略2 表示當制導的兩個分支中的一個基本塊屬于制導的特定功能標簽之外的功能標簽時,另一個基本塊屬于制導的特定功能標簽,并且屬于制導的特定功能標簽之外的功能標簽基本塊處于內(nèi)側.如果根據(jù)排序信息知道特定功能標簽流處于這兩側功能標簽流之間,那么可以裁剪掉這兩個分支.

Fig.8 Differece between branch instruction processing semantics of function label flow guided rule without ordering information and that with ordering information圖8 有排序信息的功能標簽流制導規(guī)則中分支指令處理語義規(guī)則與無排序信息的功能標簽流制導規(guī)則中分支指令處理語義規(guī)則區(qū)別

有排序信息的功能標簽流制導規(guī)則:

根據(jù)上述對各種指令的制導語義規(guī)則的描述,相對于KLEE 而言,OPT-SSE 在整個符號執(zhí)行過程中只會增加分支指令解釋執(zhí)行時的時間開銷,這個時間開銷主要是判定跳轉到的下一個基本塊是否包含特定功能標簽的分支語句帶來的,OPT-SSE 在靜態(tài)分析環(huán)節(jié)可以標記任意基本塊是否包含功能標簽類分支,因此在制導過程中可直接判定某節(jié)點是否為功能標簽相關節(jié)點,不會有額外的時間開銷,但需要判定某功能標簽節(jié)點是否為特定功能標簽相關節(jié)點的時間開銷上限為|f|倍(即功能標簽流f包含功能標簽的個數(shù)).對于整個程序而言,功能標簽相關節(jié)點數(shù)量只占所有節(jié)點數(shù)量的極小比例,因此對比KLEE,OPT-SSE 制導時間增加的時間開銷可以忽略.

4 測試與分析

OPT-SSE 實驗平臺在以下環(huán)境實現(xiàn):處理器:Intel(R)Xeon(R)CPU E7-4830 2.13GHz;內(nèi)存:64GB;操作系統(tǒng):Ubuntu 12.04.

OPT-SSE 包括靜態(tài)分析和動態(tài)分析兩個模塊:原型系統(tǒng)在llvm 上實現(xiàn)靜態(tài)分析環(huán)節(jié),包括生成控制流圖、標記關鍵指令、生成程序功能標簽流等工作,為動態(tài)分析提供輔助信息;整個動態(tài)分析環(huán)節(jié)在klee 上實現(xiàn),包括對上述各條制導規(guī)則的實現(xiàn).

本文從開源庫中選擇了wla_dx、Vim、Unrtf、Binutils、Sed、Wdiff、which、Findutils、Gzip、Coreutils這10 個不同的開源軟件作為測試對象,并挑選這些軟件中的20 個不同目標進行測試,基本信息見表6.

表6 描述了各個軟件對象的版本和功能、測試目標以及對應llvm IR 靜態(tài)指令數(shù)量等信息.實驗主要針對OPT-SSE 的指令覆蓋率、分支覆蓋率、代碼目標制導效率等方面的性能進行測試,并且將其與klee 進行橫向比較,體現(xiàn)本文工作的優(yōu)化能力.

表7 給出了wla-gb 等20 個軟件目標的詳細實驗數(shù)據(jù),實驗設置每次對目標的測試時間上限為10h.在OPT-SSE 上設置程序功能標簽流的最大數(shù)量為8;在klee 上對每個目標分別進行寬度、深度、隨機這3 種路徑搜索策略的測試,選取其中覆蓋率最優(yōu)的一組數(shù)據(jù).

Table 6 Basic information of subjects表6 測試軟件對象基本信息

Table 7 Experimental data for each subject表7 對各個軟件目標測試的實驗數(shù)據(jù)

表7 分別統(tǒng)計了各個目標在KLEE 和OPT-SSE 上的MinTestCaseNum、MinExeInstrNum、MaxInstrCoverage、MaxBrCoverage等指標數(shù)據(jù),其中,

?MaxInstrCoverage表示測試10h 中取得的最大指令覆蓋率.

?MaxBrCoverage表示測試10h 中取得的最大分支覆蓋率.

?MinTestCaseNum表示測試的10h 中,達到最大指令覆蓋率和最大分支覆蓋率的最小測試例生成數(shù)量.

?MinExeInstrNum表示測試10h 中,達到最大指令覆蓋率和最大分支覆蓋率的最小執(zhí)行指令數(shù)量.

圖9 描述了各個測試目標KLEE 和OPT-SSE 的MaxInstrCoverage指標對比情況,圖10 描述了各個測試目標KLEE 和OPT-SSE 的MaxBrCoverage指標對比情況.

Fig.9 Instruction coverage comparison between OPT-SSE and KLEE on different subjects圖9 OPT-SSE 和KLEE 對不同目標的指令覆蓋率比較

Fig.10 Comparison of branch coverage between OPT-SSE and KLEE on different subjects圖10 OPT-SSE 和KLEE 對不同目標的分支覆蓋率比較

可以發(fā)現(xiàn),與KLEE 相比,OPT-SSE 在指令覆蓋率和分支覆蓋率上得到了一定程度的優(yōu)化,其中,expr、unrtf、locate、vim 等目標在指令覆蓋率和分支覆蓋率提升最為顯著,大約為KLEE 的1.5 倍～3.5 倍.另外可以發(fā)現(xiàn),在wdiff、which、dircolors 等多個目標上,出現(xiàn)了OPT-SSE 的MinExeInstrNum指標比KLEE 要小的情況.其原因可能是,OPT-SSE 在不同程序功能標簽流上更早遇見較深的循環(huán)結構,使得MaxInstrCoverage和MaxBrCoverage兩個指標一直得不到改善.但在整體覆蓋率上,仍然比KLEE 有所提升.

圖11 和圖12 分別給出了wla-gb 在測試過程中指令覆蓋率和分支覆蓋率的實時變化情況.可以發(fā)現(xiàn),指令覆蓋率和分支覆蓋率從測試開始到最后,OPT-SSE 比KLEE 的優(yōu)化效果明顯.

Fig.11 Comparison of instruction coverage and time overhead between OPT-SSE and KLEE when analyzing wla-gb圖11 OPT-SSE 和KLEE 分析wla-gb 時的指令覆蓋率和執(zhí)行時間對比

Fig.12 Comparison of branch coverage and time overhead between OPT-SSE and KLEE when analyzing wla-gb圖12 OPT-SSE 和KLEE 分析wla-gb 時的分支覆蓋率和執(zhí)行時間對比

表8 給出了OPT-SSE 和KLEE 在代碼目標制導能力方面的對比情況.

Table 8 Comparison between OPT-SSE and KLEE on code goal-guided capability表8 OPT-SSE 和KLEE 在代碼目標制導能力上的對比

圖13 描述了OPT-SSE 與KLEE 相比,在代碼目標制導速度和成功率上的提升情況.針對各個測試目標,本文利用靜態(tài)分析[4-6]獲取初步脆弱性可疑點集合,然后從集合中篩選20 個脆弱點作為代碼目標集,分別利用OPT-SSE 和KLEE 進行1h 的制導分析.設置1h 的時間上限,是考慮多個目標在1h 后指令覆蓋率變化很小.表中統(tǒng)計了各個目標分別在KLEE 和OPT-SSE 上的代碼目標制導時間開銷、代碼目標制導加速比、制導成功數(shù)量以及成功率提升等指標的詳細數(shù)據(jù),其中,代碼目標制導時間開銷為KLEE 和OPT-SSE 都能成功制導的代碼目標時間開銷平均值.選擇KLEE 和OPT-SSE 都能成功制導的代碼目標,是為了更好地比較代碼目標制導加速情況.本文設定:代碼目標制導加速比=KLEE 的代碼目標制導時間開銷/OPT-SSE 的代碼目標制導時間開銷,成功率提升比例=(OPT-SSE 的制導成功數(shù)量-KLEE 的制導成功數(shù)量)/20.通過數(shù)據(jù)觀察可以發(fā)現(xiàn),在代碼目標制導加速比方面,OPT-SSE 在每個目標上都有所提升;在成功率提升比例方面,除which 外,其他目標都有顯著的提升.

Fig.13 Improvement of OPT-SSE on code goal-guided speed and success rate compared with KLEE圖13 OPT-SSE 與KLEE 相比在代碼目標制導速度和成功率上的提升情況

5 相關工作

近年來,符號執(zhí)行在程序的正確性驗證、缺陷的發(fā)現(xiàn)和重現(xiàn)、復用代碼的檢測、自動調試能力增強等方向產(chǎn)生了良好的應用,但由于存在程序路徑爆炸增長和約束求解時間開銷過大問題,制約其通用能力的發(fā)展.學術界和工業(yè)界一直把如何拓展符號執(zhí)行的應用面和提升符號執(zhí)行效率作為軟件程序分析領域的基礎性課題[7].符號執(zhí)行在程序分析上的應用能力主要體現(xiàn)在以下幾點.

(1)不同程序語言上的應用

陸續(xù)產(chǎn)生了具備分析c/c++、JAVA、JAVAscript、python 等語言能力的符號執(zhí)行原型系統(tǒng).如,斯坦福大學Cadar 等人先后開發(fā)了EXE[8]和KLEE[9],這兩個系統(tǒng)都應用于c/c++程序對象.KLEE 重寫了EXE 的符號執(zhí)行分析引擎,通過分析c/c++程序目標的llvm 字節(jié)碼,提升了路徑覆蓋率和缺陷發(fā)現(xiàn)能力.NASA 的Robust 軟件工程開發(fā)小組開發(fā)了JAVA pathfinder[10,11],通過分析JAVA 程序的字節(jié)碼,具備應用于并發(fā)性JAVA 程序分析的能力.伯克利大學的Saxena 等人設計了一種適用于字符串求解的約束語言Kaluza[12],適用于求解各種事件空間以及數(shù)值空間,在此基礎上,構建一個適用于JAVAscript 語言的符號執(zhí)行框架,具備檢測命令注入缺陷的能力.洛桑聯(lián)邦理工大學的Bucur 等人開發(fā)了Chef[13],通過對python 解釋器的相關包裹函數(shù)進行符號插樁處理,對python 語言對象和解釋器進行不同層次的符號執(zhí)行,構建了適應于python 語言的符號執(zhí)行引擎.

(2)不同系統(tǒng)平臺上的應用

主要是針對Linux 平臺及windows 平臺,直接對二進制程序進行分析,通過把二進制翻譯成符號執(zhí)行引擎可識別的中間語言,可以消除不同程序語言的影響,并且適應于閉源程序對象.如,微軟研究院的Godefroid 等人開發(fā)了DART[14]和SAGE[15],專門用于windows 平臺的應用程序分析,展現(xiàn)了顯著的效果.洛桑聯(lián)邦理工大學的Vitaly 等人開發(fā)了S2E[16,17].該系統(tǒng)利用qemu translator[18]將Linux 二進制程序翻譯成llvm 字節(jié)碼,再結合KLEE實現(xiàn)對Linux 二進制程序的分析.卡耐基梅隆大學的Sang 等人開發(fā)了Mayhem[19],通過使用Bap 平臺[20],將Linux二進制轉換成BIL 語言,再結合符號執(zhí)行引擎后端進行分析,在debian 系統(tǒng)上發(fā)現(xiàn)大量的缺陷.

(3)不同功能程序對象上的應用

包括對應用級程序、內(nèi)核級程序、設備驅動級程序、固件級程序等不同功能程序的符號執(zhí)行分析.如,經(jīng)典符號執(zhí)行引擎[4,5,10,14,21-23]只適應于應用級程序分析,S2E 通過對操作系統(tǒng)插樁處理并添加特權指令的支持,具備分析內(nèi)核級程序的能力.洛桑聯(lián)邦理工大學的Kuznetsov 等人在S2E 基礎上構建了DDT[24],通過對設備驅動程序相關接口進行有效配置,成功應用于設備驅動程序的分析.后來,康斯威星大學的Matthew 等人開發(fā)了symdrive[25].該系統(tǒng)對分析的設備中各種I/O 操作、DMA 操作、中斷操作進行符號化,并結合靜態(tài)分析裁剪設備驅動程序的無關路徑,提升了設備驅動級程序分析的有效路徑覆蓋能力.康斯威星大學Davidson 等人開發(fā)的FIE[26]以及EURECOM 大學Zaddach 等人開發(fā)的Avatar[27],這些系統(tǒng)通過對符號執(zhí)行引擎支持的運行環(huán)境對固件代碼建模,成功地用于嵌入式系統(tǒng)上的固件代碼的缺陷分析.

從符號執(zhí)行技術應用發(fā)展趨勢[28]可看出,符號執(zhí)行應用的程序語言對象多元化,從支持高級語言到二進制語言,再到解釋型語言,中間語言翻譯平臺[20,29-34]的不斷發(fā)展,逐漸加強了符號執(zhí)行在程序語言上的通用性.但是符號執(zhí)行對于各種程序語言的分析效率仍然具有較大的提升空間,尤其是復雜、大規(guī)模程序對象的應用效果一直受制于路徑空間爆炸和約束求解開銷過大,在一定程度上,通過以下方法得以優(yōu)化或緩解.

(1)路徑搜索策略的提升

符號執(zhí)行需要采用特定的路徑搜索策略進行狀態(tài)遍歷,一般經(jīng)典符號執(zhí)行引擎集成多個路徑搜索策略.如,KLEE[9]中實現(xiàn)了深度優(yōu)先、寬度優(yōu)先、隨機選擇、多策略交替選擇等路徑搜索策略.深度優(yōu)先選擇策略容易搜索到完整的執(zhí)行路徑,但對程序的整體覆蓋率較低;寬度優(yōu)先選擇策略會產(chǎn)生很多路徑片斷,很難分析到較深的路徑;隨機選擇選擇策略可以避免類似動態(tài)分析過程中由于碰見復雜外部庫無法跳出來的情況;多策略交替選擇策略通過采用交替地采用深度優(yōu)先、寬度優(yōu)先、隨機選擇策略分析一段固定的時間,結合了各自的優(yōu)勢.PEX 定義了一種適應度函數(shù),用來評估待選擇的分支離未覆蓋過分支的距離,通過這個度量值選擇最佳分支,取得的較高的覆蓋率[35].SAGE 中采用一種約束產(chǎn)生式的狀態(tài)遍歷方法(generational-based),先否定所有的路徑條件,然后逐漸將最深的路徑條件反轉回來,可以優(yōu)先遍歷到不同的深度路徑[21].Li 等人[36]提出了優(yōu)先選擇路徑分支執(zhí)行重復頻率最低的分支,可以在某些代碼場景產(chǎn)生更高的覆蓋率.

(2)約束求解優(yōu)化

KLEE 在求解模塊采用路徑預判斷、約束表達式簡化、約束集簡化、反例緩存機制等技術降低求解開銷.Romano 等人[37]建立了表達式匹配規(guī)則系統(tǒng),盡量利用歷史約束集信息確定新約束集是否可解,在一定程度上降低了對求解器的查詢次數(shù).S2PF[38]提出,避免一遇見條件分支就調用約束求解器,而是通過累積多個條件分支后再進行求解:如果約束集可解,則說明該執(zhí)行路徑上之前的約束集都可解,避免了之前的求解開銷;如果約束集不可解,則回溯到之前沒有求解的條件分支再次執(zhí)行,從一定概率上節(jié)省了總的約束求解開銷.秦曉軍等人[39]提出了一種基于懶符號執(zhí)行的約束求解算法,自動識別循環(huán)結構.通過推遲變量實例化等方法,有效地緩解了循環(huán)結構的路徑組合爆炸問題,降低了求解次數(shù).

(3)冗余狀態(tài)歸約

Li 等人針對符號狀態(tài)定義弱等價關系[40],如果一組狀態(tài)滿足該關系,那么可以用一個狀態(tài)替代該組狀態(tài).例如,某循環(huán)體中的判定條件與符號變量有關,并且某個變量依賴于外部庫的符號返回值,那么對于每次循環(huán),都會產(chǎn)生一個新的符號變量,這樣會出現(xiàn)大量呈弱等價關系的狀態(tài).這種方法在一定程度上加速了符號執(zhí)行過程.Bugrara 等人[41]提出,如果一組約束覆蓋的代碼行和另一組約束相同,則認為這組約束對應的狀態(tài)是多余的,可以消除,并利用動態(tài)切片方法[42]確定不同約束集是否覆蓋相同代碼行.該方法提升了代碼覆蓋率.

(4)狀態(tài)合并方法

如果兩條路徑在某個代碼點交匯,那么可以把兩個狀態(tài)的約束集合并成一個狀態(tài)的約束集.這樣可以大量削減狀態(tài)的總數(shù)量,但有可能出現(xiàn)對合并后約束集的求解開銷大于合并之前分別求解的總開銷,尤其容易發(fā)生在大規(guī)模程序中[43].針對這一情況,出現(xiàn)了相應的折中方法,如,

?Boonstoppel 等人[44]提出,如果兩個狀態(tài)效果相同,并且約束集中取值不同的變量與的后續(xù)路徑選擇無關,那么這兩個狀態(tài)合并后約束集在后續(xù)求解中帶來的額外開銷會降低,可以選擇合并符合該條件的狀態(tài)集合.

?Kuznetsov 等人[45]提出,針對每次狀態(tài)合并之前,評估合并后約束集中新增符號變量所增加的求解器查詢次數(shù),以此確定潛在的合并點.

(5)執(zhí)行分段和合成方法

Le 利用靜態(tài)分析根據(jù)循環(huán)體、外部庫等代碼特征將程序片段化,再通過動態(tài)執(zhí)行獲取各個片段的相關接口信息以及自動合成各個片段,可以更好地處理程序循環(huán)結構和動態(tài)庫帶來的符號化問題[46].Ramos 等人[47,48]提出,分別對各個用戶定義函數(shù)體進行符號執(zhí)行,再對觸發(fā)函數(shù)體缺陷的輸入進行合成,避免直接從主函數(shù)分析時出現(xiàn)的深度路徑不可達情況,可產(chǎn)生更高的語句覆蓋率.Sinha 等人[49]提出,通過對并發(fā)性程序進行分階段執(zhí)行,有效分離線程的過程內(nèi)和過程間操作.第1 階段獲取線程全局變量信息,對線程序列進行有效分割;第2 階段利用執(zhí)行序列的一致性把路徑片段組合成完整線程,具備并發(fā)性缺陷發(fā)現(xiàn)能力.Zamfir 等人[50]提出,對并發(fā)性程序的序列路徑合成和線程調度合成,可準確地重現(xiàn)并發(fā)性缺陷.

(6)Concolic 執(zhí)行方法

該方法需要使用種子數(shù)據(jù),即初始測試例,在對種子數(shù)據(jù)進行具體執(zhí)行的過程中,收集執(zhí)行路徑的其他分支相關符號約束,構造后續(xù)狀態(tài)集合,并在具體執(zhí)行完種子數(shù)據(jù)后,采用特定狀態(tài)選擇策略進行符號執(zhí)行.Concolic執(zhí)行方法可以借助具體執(zhí)行特定的測試例快速制導具有一定深度的代碼,可解決純符號執(zhí)行不適應復雜目標的深度路徑可達問題,在多個符號執(zhí)行引擎[8,9,14,15]中得到了體現(xiàn).如,KLEE 中利用種子數(shù)據(jù)進行符號執(zhí)行,一旦執(zhí)行完種子數(shù)據(jù),就利用特定搜索策略對種子數(shù)據(jù)的分支狀態(tài)進行遍歷;CUTE 采用不斷隨機生成測試例進行具體執(zhí)行,一旦生成的測試例不能覆蓋新的分支,將切換到符號執(zhí)行[51],這種Concolic 執(zhí)行方法提升了4 倍以上的覆蓋能力;DASE[52]構造特定輸入種子,并確定其中固定字段,在種子模式執(zhí)行分析過程中,可避免對這些固定數(shù)據(jù)的約束求解,提高了分析效率.

(7)并行化方法

Cloud9[53]在KLEE 的基礎上、MergePoint[54]在Mayhem 的基礎上分別構建了并行符號執(zhí)行框架.他們采用在集群的某個節(jié)點上啟動符號執(zhí)行,動態(tài)地選擇當前節(jié)點上產(chǎn)生的不同狀態(tài),并分離到集群上的其個節(jié)點上繼續(xù)執(zhí)行,實時保持不同節(jié)點上的負載均衡,取得了良好的效果.Junaid 等人[55]提出利用不同測試例劃分程序路徑范圍,對不同程序路徑范圍進行并行性測試,大幅度提升覆蓋率.

大部分符號執(zhí)行性能優(yōu)化方法只適應于特定的程序場景,需要結合多種優(yōu)勢才能應對程序對象多樣性、復雜性的通用測試需求.針對一個路徑數(shù)量過多的程序,不管采用何種路徑選擇策略,如果要做到全局覆蓋,很難達到理想的效果,需要其他優(yōu)化能力的不斷提升.基于符號執(zhí)行面臨的現(xiàn)狀,近幾年出現(xiàn)了一種實用性較強的應用——制導符號執(zhí)行分析方法.該方法不以程序的全局覆蓋為目標,只對程序中感興趣的程序片段或性質進行驗證,適用于補丁程序的可靠性分析、特定場景的測試例生成、特定缺陷發(fā)現(xiàn)等應用方向.制導符號執(zhí)行一般通過靜態(tài)分析或附加的限制條件信息增強其分析的導向性,利用預定義好的制導規(guī)則指導符號執(zhí)行如何進行更好的路徑搜索達到制導目的,其效果更易于提升不同代碼規(guī)模程序對象的應用.制導符號執(zhí)行分析方法出現(xiàn)了一系列應用,如,Kin 等人[56]提出一種快速的程序行可達性判定和測試例生成算法,在靜態(tài)控制流圖上計算每個程序分支和目標代碼行的距離值,每執(zhí)行分支時,選擇離目標代碼最近的程序分支,能夠快速到達目標代碼行;Paul 等人[57]通過優(yōu)先選擇程序分支到敏感指令(讀和寫)的距離最近的分支進行制導分析,發(fā)現(xiàn)很多讀寫相關的缺陷;Zhang 等人[58]提出通過有限狀態(tài)機模型對正規(guī)性質進行定義,利用符號執(zhí)行對程序正規(guī)性質進行制導分析,有效地驗證程序中內(nèi)存泄漏等路徑敏感缺陷;DiSE[59]先通過靜態(tài)分析檢查某軟件系統(tǒng)不同版本間的差異,并利用制導符號執(zhí)行產(chǎn)生差異代碼可達路徑條件,可以檢查程序更改后帶來的影響;Taneja 等人[60]通過構建程序控制流圖,確定與修改代碼區(qū)域無關的條件分支,在符號執(zhí)行過程中裁剪這些無關分支,能夠更快地產(chǎn)生回歸測試例,已驗證程序修補后的正確性;Marinescu 等人[61,62]利用制導符號執(zhí)行實現(xiàn)對已知補丁集合的進行覆蓋測試,通過計算每條指令到補丁代碼的條件數(shù)量作為度量距離值,采用最弱前置條件分析[63]確定目標不可達的基本塊,最后對多個初始種子中選擇出離補丁代碼最近的種子數(shù)據(jù),可以為后續(xù)符號執(zhí)行制導補丁代碼提供距離最近的狀態(tài);Domagoj 等人[64]先運用靜態(tài)分析確定二進制程序中的脆弱點,再借助事先在控制流邊上標記到達脆弱點的靜態(tài)跳轉次數(shù)信息對這些脆弱點集合進行制導符號執(zhí)行分析;Ge 等人[65]利用制導符號執(zhí)行分析方法對靜態(tài)分析得到的缺陷報告進行動態(tài)驗證,提高了靜態(tài)分析的準確性;Guo 等人[66]通過靜態(tài)分析確定程序正確的部分,在符號執(zhí)行過程中對這些不包含缺陷的路徑分支進行實時的裁剪,提升了分析速度.

6 結 論

本文提出了一種基于程序功能切片的符號執(zhí)行制導分析方法OPT-SSE.該方法參考程序的功能文檔,在控制流圖上把提取控制功能執(zhí)行路徑的關鍵基本塊,并標識成相應的功能標簽.OPT-SSE 利用功能標簽流對程序進行有序劃分,對于給定的代碼目標點,提取與之相關的功能標簽切片,然后根據(jù)預定義的制導規(guī)則對該切片進行制導分析.實驗結果表明,該方法能夠顯著加速代碼目標制導速度和成功率;并且通過并行的方式制導分析不同的程序功能切片,能夠避免符號執(zhí)行卡在某個循環(huán)結構體上,從而提升對整個程序的分支和指令覆蓋率.

OPT-SSE 在下一步工作中需要對以下不足進行優(yōu)化.

(1)采取靜態(tài)切片提取功能標簽受影響的基本塊.可能會分析出部分可能執(zhí)行不到的代碼片段,從而影響后續(xù)的符號執(zhí)行制導效果,在下一步工作中需要借助動態(tài)切片進一步優(yōu)化.

(2)本文把程序的選項定義為功能標簽,在今后的工作中,可以對功能標簽進行更寬泛的應用,例如,把程序中所有不可變性質歸納為相應的功能標簽,如固定輸入格式和結構.利用更多的功能標簽信息,可以進一步提升符號執(zhí)行制導效率.