基于混合測(cè)試和動(dòng)態(tài)分析的分段代碼測(cè)試

劉春宏,徐立華,顏 婷,楊宗源

(華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,上海200241)

基于混合測(cè)試和動(dòng)態(tài)分析的分段代碼測(cè)試

劉春宏,徐立華,顏 婷,楊宗源

(華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,上海200241)

傳統(tǒng)混合執(zhí)行測(cè)試方法無(wú)法對(duì)源代碼不可見(jiàn)函數(shù)進(jìn)行符號(hào)執(zhí)行。針對(duì)該問(wèn)題,將符號(hào)執(zhí)行、分段式符號(hào)執(zhí)行以及具體執(zhí)行按需結(jié)合,提出一種分段式混合執(zhí)行測(cè)試方法,將源代碼不可見(jiàn)函數(shù)以分段式分析法截取為單獨(dú)代碼片段,結(jié)合動(dòng)態(tài)執(zhí)行和回歸分析方法推導(dǎo)其相應(yīng)的程序語(yǔ)義。為驗(yàn)證該方法的有效性,實(shí)現(xiàn)sCREST原型系統(tǒng),并對(duì)5個(gè)應(yīng)用廣泛的開(kāi)源系統(tǒng)進(jìn)行測(cè)試。實(shí)驗(yàn)結(jié)果表明,該方法能夠產(chǎn)生比傳統(tǒng)方法覆蓋更多分支數(shù)的測(cè)試數(shù)據(jù)。

軟件測(cè)試;混合測(cè)試;分段式符號(hào)分析;動(dòng)態(tài)分析;測(cè)試數(shù)據(jù)生成;分支覆蓋

1 概述

混合執(zhí)行測(cè)試[1-2]是一種將具體執(zhí)行和符號(hào)執(zhí)行相結(jié)合的有效測(cè)試方法,自動(dòng)生成測(cè)試輸入來(lái)執(zhí)行程序中所有可行路徑以進(jìn)行錯(cuò)誤檢測(cè),受到廣泛關(guān)注[3-5]。CREST[3]在混合執(zhí)行中提供多種基于程序控制流圖的路徑搜索策略,以盡量生成覆蓋更多分支的測(cè)試輸入。文獻(xiàn)[4]提出一種目標(biāo)制導(dǎo)的混合執(zhí)行測(cè)試方法,只生成和執(zhí)行可能會(huì)覆蓋待檢測(cè)缺陷語(yǔ)句的測(cè)試輸入。文獻(xiàn)[5]將混合執(zhí)行測(cè)試應(yīng)用于基于污點(diǎn)指針的二進(jìn)制代碼缺陷檢測(cè)中?；旌蠄?zhí)行測(cè)試在100行～2 000行代碼的小型系統(tǒng)的單元測(cè)試中非常有效[3],但目前將其用于工業(yè)界實(shí)際軟件仍存在一些局限性[6]。本文主要專注于混合執(zhí)行測(cè)試中源代碼不可見(jiàn)的函數(shù)調(diào)用處理這一局限性(也稱為native calls,它包括源代碼不可獲得的標(biāo)準(zhǔn)庫(kù)函數(shù)或者第三方組件的使用)。文獻(xiàn)[6]實(shí)驗(yàn)表明源代碼不可見(jiàn)的函數(shù)調(diào)用是除指針外在被測(cè)軟件系統(tǒng)中出現(xiàn)頻率最高的局限性,阻礙工具產(chǎn)生高分支覆蓋的測(cè)試數(shù)據(jù)。

混合執(zhí)行測(cè)試?yán)^承于符號(hào)執(zhí)行技術(shù),無(wú)法對(duì)源代碼不可見(jiàn)的被調(diào)函數(shù)進(jìn)行符號(hào)執(zhí)行。DART[1], CUTE[2]和CREST[3]使用運(yùn)行時(shí)具體值代替符號(hào)值的“具體化”方法處理源代碼不可見(jiàn)的函數(shù)調(diào)用,但在測(cè)試生成環(huán)境下,該方法并不精確,因?yàn)殡S之產(chǎn)生的測(cè)試數(shù)據(jù)只能覆蓋某一具體輸入值可以到達(dá)的被調(diào)函數(shù)中的一條路徑,有時(shí)還可能導(dǎo)致路徑分歧[1,7]。且如果符號(hào)路徑條件中的函數(shù)調(diào)用沒(méi)有得到有效處理,也會(huì)影響生成的測(cè)試數(shù)據(jù)的完備性?；旌蠄?zhí)行測(cè)試中采用函數(shù)跟進(jìn)[1-3]和函數(shù)摘要[8]處理函數(shù)調(diào)用,但針對(duì)的是存在源代碼函數(shù)體的函數(shù),不適用于本文研究的源代碼不可見(jiàn)的函數(shù)調(diào)用;對(duì)于無(wú)法獲得源代碼的第三方組件或標(biāo)準(zhǔn)庫(kù)函數(shù)調(diào)用,如果采用函數(shù)摘要方法,則需要通過(guò)人工的編寫(xiě)完成[9]。

針對(duì)源代碼不可見(jiàn)的函數(shù),文獻(xiàn)[7]提出一種使用未解釋的函數(shù)符號(hào)表示源代碼不可獲得的函數(shù)的高階測(cè)試生成方法,比具體化方法更加精確,但實(shí)現(xiàn)代價(jià)昂貴且受限于現(xiàn)有SMT solver的求解能力。文獻(xiàn)[10]在Cloud9中手動(dòng)開(kāi)發(fā)庫(kù)模型,但每一個(gè)新的應(yīng)用程序可能會(huì)引入一個(gè)不同的庫(kù),模型并不總是可以重用。文獻(xiàn)[11]在ICSE 2013上提出的分段式符號(hào)分析是一種將靜態(tài)程序分析中無(wú)法繼續(xù)的代碼片段以動(dòng)態(tài)分析的方式推導(dǎo)相應(yīng)程序語(yǔ)義,按需對(duì)被測(cè)程序分段并交替使用動(dòng)靜態(tài)程序分析的方法,成功用于分析緩沖區(qū)溢出問(wèn)題。

據(jù)筆者所知,目前還不存在分段式符號(hào)分析[11]應(yīng)用于測(cè)試領(lǐng)域的通用方法。由于分段式符號(hào)分析中使用線性回歸分析技術(shù)匯總了源代碼不可見(jiàn)的函數(shù)代碼片段的多次運(yùn)行的動(dòng)態(tài)信息,而“具體化”方法只執(zhí)行了被調(diào)函數(shù)中某一特定的具體值所能執(zhí)行到的一條路徑,理論上,由此分析所得的轉(zhuǎn)移函數(shù)相較單純的“具體化”方法中的一次運(yùn)行的具體值更準(zhǔn)確,能更準(zhǔn)確地模擬程序的執(zhí)行情況和代表相應(yīng)程序點(diǎn)的變量的符號(hào)值。

本文針對(duì)混合執(zhí)行測(cè)試中的源代碼不可見(jiàn)的函數(shù)調(diào)用問(wèn)題,提出分段式混合執(zhí)行測(cè)試方法,把分段式分析方法[11]引入傳統(tǒng)混合執(zhí)行測(cè)試中,將符號(hào)執(zhí)行、分段式符號(hào)執(zhí)行以及具體執(zhí)行方法按需結(jié)合,針對(duì)符號(hào)執(zhí)行無(wú)法分析的代碼片段進(jìn)行動(dòng)態(tài)分析,以此替代簡(jiǎn)單使用運(yùn)行時(shí)具體值代替符號(hào)值的方法,以期進(jìn)一步緩解源代碼不可見(jiàn)的函數(shù)調(diào)用這一局限性?；贑REST開(kāi)發(fā)sCREST(segmented CREST)系統(tǒng),實(shí)現(xiàn)并評(píng)估本文提出的分段式混合執(zhí)行測(cè)試方法。

2 分段式混合執(zhí)行方法

首先給出一個(gè)例子來(lái)直觀解釋分段式混合執(zhí)行測(cè)試方法的工作方式,然后介紹本文在CREST上實(shí)現(xiàn)的分段式混合執(zhí)行測(cè)試系統(tǒng)sCREST。

2.1 分段式混合執(zhí)行方法

一個(gè)使用CREST測(cè)試,包含strcmp庫(kù)函數(shù)的示例程序如下:

其中,CREST_char(tmp1)表示把tmp1作為符號(hào)變量來(lái)處理,CREST生成一個(gè)char型數(shù)據(jù)并賦值給tmp1,再把tmp1賦值給pattern數(shù)組的元素,表明pattern數(shù)組需要CREST為其生成測(cè)試數(shù)據(jù)。程序中if條件中包含一個(gè)源代碼不可見(jiàn)的庫(kù)函數(shù)strcmp,只有當(dāng)CREST生成的測(cè)試輸入等于“test”時(shí),該if條件才會(huì)被滿足,從而覆蓋if分支。

該示例程序在CREST中很難生成覆蓋所有分支的有效測(cè)試數(shù)據(jù),只能迭代一次,覆蓋else分支。這是因?yàn)閟trcmp函數(shù)的源代碼不可見(jiàn),CREST無(wú)法對(duì)其符號(hào)執(zhí)行。CREST采取“具體化”方法,具體執(zhí)行strcmp函數(shù),使用具體值代替符號(hào)值構(gòu)造符號(hào)條件,因此雖然pattern數(shù)組聲明為符號(hào)變量,但strcmp的返回值仍然是運(yùn)行時(shí)的具體值。CREST首次運(yùn)行時(shí)的測(cè)試值是隨機(jī)生成的,隨機(jī)生成測(cè)試值“test”來(lái)滿足if分支的概率很低,且“具體化”后,符號(hào)路徑條件簡(jiǎn)化為一個(gè)具體值,不存在可被取非的某個(gè)符號(hào)分支條件,導(dǎo)致CREST只執(zhí)行一次迭代,測(cè)試過(guò)程結(jié)束。因此“具體化”方法往往只能覆蓋else分支,不能產(chǎn)生覆蓋if分支的測(cè)試輸入“test”。

本文提出的分段式混合執(zhí)行測(cè)試方法,當(dāng)遇到無(wú)法符號(hào)執(zhí)行的源代碼不可見(jiàn)的函數(shù)調(diào)用(如此處的strcmp)時(shí),使用分段式符號(hào)執(zhí)行處理:

步驟1截取與strcmp相關(guān)的代碼片段,包括2個(gè)部分:(1)strcmp函數(shù)所在的語(yǔ)句strcmp (pattern,"test")。(2)庫(kù)函數(shù)strcmp的參數(shù)變量的初始化語(yǔ)句char pattern[NUM_SYM_CHARS+1]。

步驟2分析上下文,提煉分段式符號(hào)執(zhí)行所需的輸入變量與輸出變量在被測(cè)程序和庫(kù)函數(shù)中對(duì)應(yīng)的變量,這里提煉出的輸入變量是pattern,輸出變量是strcmp的返回值。

步驟3動(dòng)態(tài)執(zhí)行步驟1中得到的代碼片段,并結(jié)合步驟2中提煉的輸入變量與輸出變量進(jìn)行回歸分析。

步驟4將回歸分析推導(dǎo)出的輸入變量與輸出變量之間的符號(hào)表達(dá)式或者與被處理的函數(shù)strcmp等價(jià)的代碼片段,代入程序體,使用混合執(zhí)行測(cè)試產(chǎn)生系統(tǒng)的測(cè)試輸入,使混合執(zhí)行測(cè)試過(guò)程繼續(xù)下去。

本文提出的分段式混合執(zhí)行測(cè)試方法可以產(chǎn)生覆蓋if和else兩個(gè)分支的測(cè)試數(shù)據(jù),而CREST中的“具體化”方法只能覆蓋else分支的測(cè)試數(shù)據(jù)。由此可見(jiàn),分段式混合執(zhí)行測(cè)試方法比傳統(tǒng)混合執(zhí)行測(cè)試中使用具體值簡(jiǎn)化復(fù)雜符號(hào)條件的“具體化”方法更加準(zhǔn)確,生成的測(cè)試數(shù)據(jù)能夠覆蓋“具體化”方法不能覆蓋到的路徑(或分支),因而執(zhí)行更多系統(tǒng)路徑,提高系統(tǒng)的分支覆蓋。

2.2 sCREST系統(tǒng)

sCREST是在CREST上實(shí)現(xiàn)的分段式混合執(zhí)行測(cè)試系統(tǒng),將符號(hào)執(zhí)行、分段式符號(hào)執(zhí)行和具體執(zhí)行按需結(jié)合。選擇CREST基于以下原因:(1)CREST是針對(duì)C程序一個(gè)廣泛認(rèn)可的代碼開(kāi)源的工具;它對(duì)源程序靜態(tài)插樁實(shí)現(xiàn)在運(yùn)行時(shí)從具體執(zhí)行抽取符號(hào)路徑條件以實(shí)現(xiàn)混合執(zhí)行,該方法的實(shí)現(xiàn)相對(duì)簡(jiǎn)單,因此相對(duì)方便在CREST上應(yīng)用新的技術(shù)[12]。 (2)CREST只能對(duì)源代碼已經(jīng)被插樁過(guò)的函數(shù)進(jìn)行符號(hào)執(zhí)行,對(duì)于在編譯時(shí)源代碼不可見(jiàn)的函數(shù),無(wú)法對(duì)其靜態(tài)插樁導(dǎo)致無(wú)法對(duì)其符號(hào)執(zhí)行。CREST使用“具體化”方法處理這類(lèi)函數(shù),但如果某源代碼不可見(jiàn)的函數(shù)直接的出現(xiàn)在某個(gè)符號(hào)分支條件中,或間接影響到某個(gè)符號(hào)分支的真值,該方法有可能會(huì)導(dǎo)致不能產(chǎn)生到達(dá)某一特定分支的測(cè)試輸入,或者會(huì)導(dǎo)致“路徑分歧”現(xiàn)象迫使測(cè)試中止,這些會(huì)降低測(cè)試數(shù)據(jù)的分支覆蓋。(3)在實(shí)際使用CREST測(cè)試大型程序時(shí),時(shí)常需要手動(dòng)添加常用的libc庫(kù)函數(shù)的自定義代碼[13-14],以便這些源代碼不可見(jiàn)的函數(shù)可被靜態(tài)插樁,從而被符號(hào)執(zhí)行,產(chǎn)生到達(dá)與這些函數(shù)調(diào)用相關(guān)的分支(或路徑)的測(cè)試數(shù)據(jù),以此提高測(cè)試覆蓋。但這種手動(dòng)添加代碼不可見(jiàn)的函數(shù)的自定義代碼的方式效率不高,且也不容易確定需要添加哪些庫(kù)函數(shù)的自定義的代碼。

現(xiàn)階段sCREST針對(duì)的是源代碼不可見(jiàn)的庫(kù)函數(shù)調(diào)用,sCREST是基于CREST實(shí)現(xiàn)的,重用CREST的3個(gè)主要模塊:源代碼插樁模塊,進(jìn)行動(dòng)態(tài)符號(hào)執(zhí)行的引擎組件(C++library)和搜索策略模塊,本文對(duì)動(dòng)態(tài)符號(hào)執(zhí)行引擎中的Symbolic-Interpreter類(lèi)做部分修改,并增加分段式符號(hào)分析組件。sCREST的概要執(zhí)行流程如圖1所示。

圖1 sCREST系統(tǒng)的概要執(zhí)行流程

如圖1所示,傳統(tǒng)混合執(zhí)行測(cè)試方法中具體執(zhí)行和符號(hào)執(zhí)行同時(shí)進(jìn)行,首先以一些隨機(jī)輸入值具體執(zhí)行程序,同時(shí)進(jìn)行動(dòng)態(tài)符號(hào)執(zhí)行,沿著具體執(zhí)行路徑收集符號(hào)路徑條件,使用搜索策略選取符號(hào)條件的某個(gè)分支取非,調(diào)用約束求解器求解新的符號(hào)條件,產(chǎn)生執(zhí)行新路徑的測(cè)試輸入。在混合執(zhí)行測(cè)試產(chǎn)生測(cè)試輸入的過(guò)程中,sCREST在遇到靜態(tài)符號(hào)執(zhí)行無(wú)法繼續(xù)的源代碼不可見(jiàn)的庫(kù)函數(shù)時(shí),使用分段式符號(hào)分析處理,推導(dǎo)出關(guān)聯(lián)模型,將其代入到相應(yīng)的截取點(diǎn),使用混合執(zhí)行測(cè)試產(chǎn)生系統(tǒng)的測(cè)試輸入;同時(shí),具體執(zhí)行指導(dǎo)系統(tǒng)的執(zhí)行路徑,使混合執(zhí)行測(cè)試過(guò)程進(jìn)行下去。圖2顯示了sCREST的詳細(xì)流程,突出說(shuō)明分段式符號(hào)分析,其中的傳統(tǒng)混合執(zhí)行測(cè)試的內(nèi)部細(xì)節(jié)與圖1中的傳統(tǒng)混合執(zhí)行測(cè)試相同。

圖2 sCREST系統(tǒng)的詳細(xì)執(zhí)行流程

在sCREST系統(tǒng)的詳細(xì)執(zhí)行流程中,不同組件對(duì)源程序進(jìn)行處理的過(guò)程如下:

步驟1首先對(duì)被測(cè)程序進(jìn)行預(yù)處理,識(shí)別出被測(cè)程序中接收輸入的代碼,把這些代碼替換為CREST_int,CREST_char等調(diào)用,使被測(cè)程序可以接收symbolic inputs(使用CREST需要做的前期工作);然后使用插樁模塊crestc對(duì)程序編譯生成完成插樁的可執(zhí)行文件;最后使用run_crest進(jìn)行測(cè)試執(zhí)行,生成測(cè)試數(shù)據(jù)。sCREST系統(tǒng)通過(guò)對(duì)CREST源代碼中的SymbolicInterpreter類(lèi)進(jìn)行部分修改,使之輸出測(cè)試中遇到的源代碼不可見(jiàn)的函數(shù)的信息statement-id號(hào)。

步驟2sCREST系統(tǒng)的片段截取組件,實(shí)現(xiàn)對(duì)源代碼不可見(jiàn)的函數(shù)相關(guān)的代碼片段的截取以及函數(shù)名稱的識(shí)別。代碼片段包括2個(gè)部分:(1)源代碼不可見(jiàn)的庫(kù)函數(shù)所在的程序語(yǔ)句;(2)源代碼不可見(jiàn)的庫(kù)函數(shù)的參數(shù)變量的初始化語(yǔ)句。因?yàn)樵闯绦?.c文件)在被crestc編譯后會(huì)產(chǎn)生插樁后的文件(.cil.c文件),步驟1中輸出的庫(kù)函數(shù)的statementid號(hào)在其對(duì)應(yīng)的.cil.c文件中是唯一的,所以通過(guò)編寫(xiě)perl程序在相應(yīng)的.cil.c文件中查找該statementid號(hào),確定此代碼不可見(jiàn)的函數(shù)名稱以及其在程序中所在的行號(hào),得出代碼片段的第(1)部分;第(2)部分則通過(guò)編寫(xiě)perl程序分析識(shí)別出庫(kù)函數(shù)的參數(shù)變量,然后識(shí)別出參數(shù)變量的相應(yīng)的初始化語(yǔ)句而獲得。

步驟3根據(jù)步驟2識(shí)別出的源代碼不可見(jiàn)的函數(shù)名稱,在函數(shù)“摘要”庫(kù)中查找,是否已存在該函數(shù)的“摘要”,如果已存在,則直接提取調(diào)用其“摘要”;否則,進(jìn)入步驟4。

步驟4通過(guò)提煉輸入與輸出變量組件,分析上下文,提煉需要分段式符號(hào)分析的庫(kù)函數(shù)代碼片段的輸入變量與輸出變量在被測(cè)程序中對(duì)應(yīng)的變量(輸入變量一般是源代碼不可見(jiàn)的庫(kù)函數(shù)的輸入?yún)?shù),輸出變量是庫(kù)函數(shù)的返回值變量)。動(dòng)態(tài)執(zhí)行步驟2得到的源代碼不可見(jiàn)的庫(kù)函數(shù)的代碼片段的測(cè)試單元,并結(jié)合當(dāng)前步驟提煉的分段式符號(hào)分析的輸入變量與輸出變量,進(jìn)入下一步的回歸分析。動(dòng)態(tài)執(zhí)行的具體過(guò)程是,首先根據(jù)輸入與輸出變量以及步驟2得到的代碼片段,構(gòu)建一個(gè)可以獨(dú)立運(yùn)行的測(cè)試單元,然后自動(dòng)生成輸入變量的具體值集合,多次實(shí)際動(dòng)態(tài)運(yùn)行構(gòu)建的測(cè)試單元,同時(shí)記錄下每次運(yùn)行的測(cè)試輸入值及其相應(yīng)的輸出值[11]。

步驟5 經(jīng)過(guò)回歸分析組件,推導(dǎo)出輸入變量與輸出變量之間的符號(hào)表達(dá)式,或者推導(dǎo)出與被處理的源代碼不可見(jiàn)的函數(shù)等價(jià)的代碼片段(通過(guò)對(duì)步驟4得到的多個(gè)輸入變量值與其對(duì)應(yīng)的輸出變量值,經(jīng)過(guò)回歸分析推導(dǎo)出輸入變量與輸出變量之間的關(guān)聯(lián)模型[11]),并將其代入到程序中,使混合執(zhí)行測(cè)試過(guò)程得以繼續(xù)進(jìn)行下去。同時(shí)將分段式符號(hào)分析自動(dòng)生成的結(jié)果作為該函數(shù)的摘要保存到函數(shù)摘要數(shù)據(jù)庫(kù)中。

3 實(shí)驗(yàn)與評(píng)估

為評(píng)估本文的分段式混合執(zhí)行測(cè)試方法的性能,將sCREST應(yīng)用于5個(gè)不同規(guī)模的開(kāi)源應(yīng)用程序的測(cè)試數(shù)據(jù)生成中。選取Siemens Benchmark Suite[15]中2個(gè)程序tcas和replace,其中,tcas是一個(gè)飛機(jī)防撞系統(tǒng);replace是其中最大的測(cè)試程序,還有3個(gè)應(yīng)用廣泛的開(kāi)源應(yīng)用程序:gzip-1.2.4,grep-2.2,vim-5.7。所有的實(shí)驗(yàn)運(yùn)行在VMware Workstation 8.0(RAM 2 GB)的ubuntu10.04上,使用的是CREST 0.1.1 (revision132)。宿主配置是Intel Pentium CPU,2.30 GHZ,內(nèi)存8 GB。

針對(duì)每一個(gè)被測(cè)程序,在設(shè)置相同的迭代次數(shù)(即插樁程序的運(yùn)行次數(shù))和使用相同的搜索策略(本文使用深度優(yōu)先策略dfs)前提下,分別使用sCREST與CREST系統(tǒng)對(duì)相同設(shè)置的同一程序進(jìn)行測(cè)試,并對(duì)比測(cè)試情況,以評(píng)估本文方法。

本文實(shí)驗(yàn)的目的在于檢驗(yàn)本文的分段式混合執(zhí)行測(cè)試方法是否能提高測(cè)試數(shù)據(jù)的分支覆蓋。采用2個(gè)評(píng)估指標(biāo)是sCREST以及CRSET最終能夠達(dá)到的分支覆蓋數(shù)和各自的執(zhí)行時(shí)間。由于CREST中存在隨機(jī)因素,使得同一測(cè)試生成命令在不同的時(shí)刻運(yùn)行,最終得到的覆蓋分支數(shù)有所不同,因此,本文實(shí)驗(yàn)把CREST源代碼中的隨機(jī)數(shù)發(fā)生器的初始化函數(shù)srand函數(shù)注釋掉,使得每次調(diào)用rand函數(shù)生成的偽隨機(jī)數(shù)序列都是一樣的,從而使得同一測(cè)試命令在不同的時(shí)刻運(yùn)行最終得到的分支覆蓋數(shù)相同;由于CREST中同一個(gè)測(cè)試生成命令在不同時(shí)刻運(yùn)行的執(zhí)行時(shí)間有所不同,因此這里的執(zhí)行時(shí)間記錄的是5次運(yùn)行的平均執(zhí)行時(shí)間。CREST和sCREST的實(shí)驗(yàn)對(duì)比結(jié)果如表1和表2所示。在表1中,dfs后面括號(hào)中的數(shù)字表示設(shè)置的搜索深度;在表2中,相對(duì)分支覆蓋率=覆蓋的分支數(shù)/到達(dá)的分支數(shù);絕對(duì)分支覆蓋率=覆蓋的分支數(shù)/總分支數(shù)。

表1 CREST和sCREST系統(tǒng)的分支覆蓋數(shù)與執(zhí)行時(shí)間對(duì)比

表2 CREST和sCREST系統(tǒng)的分支覆蓋率對(duì)比%

由表1可以看出,本文的分段式混合執(zhí)行測(cè)試方法比傳統(tǒng)的混合執(zhí)行測(cè)試達(dá)到更高的分支覆蓋,而且所有被測(cè)程序的測(cè)試過(guò)程都在一個(gè)合理的時(shí)間內(nèi)完成。tcas在花費(fèi)一些迭代次數(shù)生成有效范圍內(nèi)的測(cè)試數(shù)據(jù)后,CREST只執(zhí)行了tcas中的一條路徑,混合執(zhí)行測(cè)試就被迫中止,執(zhí)行時(shí)間不足1s,因此,表1中記為“-”,sCREST執(zhí)行了tcas程序中的更多條路徑,執(zhí)行時(shí)間增加到35 s。

表2中分別對(duì)CREST和sCREST的分支覆蓋率進(jìn)行對(duì)比,除replace外,其他被測(cè)程序,無(wú)論是相對(duì)分支覆蓋率還是絕對(duì)分支覆蓋率,sCREST比CREST都有所提高。

表1和表2中的數(shù)據(jù)是實(shí)驗(yàn)總體情況,下面對(duì)具代表性的被測(cè)程序做詳細(xì)說(shuō)明。

3.1 tcas程序

tcas需要從程序外部接收12個(gè)輸入?yún)?shù),每一個(gè)輸入?yún)?shù)都需使用atoi函數(shù)進(jìn)行類(lèi)型轉(zhuǎn)換。本文將每一個(gè)輸入?yún)?shù)設(shè)定為固定長(zhǎng)度的符號(hào)字符數(shù)組,并添加限制條件使CREST和sCREST生成有效范圍內(nèi)的符號(hào)變量,提高測(cè)試數(shù)據(jù)的有效性。

從圖3可見(jiàn),tcas在CREST中只執(zhí)行17次迭代測(cè)試過(guò)程中止,最終覆蓋59個(gè)分支(tcas在CREST中的分支覆蓋情況如圖4所示);而tcas在sCREST中可以執(zhí)行設(shè)定的2 000次迭代,最終覆蓋93個(gè)分支。這是因?yàn)閠cas的每一個(gè)輸入?yún)?shù)必須經(jīng)atoi函數(shù)進(jìn)行類(lèi)型轉(zhuǎn)換,且符號(hào)路徑條件中只有這一個(gè)源代碼不可見(jiàn)的函數(shù)atoi,atoi對(duì)輸入?yún)?shù)的測(cè)試數(shù)據(jù)的生成有非常重要的作用。CREST首先花費(fèi)一些迭代用來(lái)生成在有效范圍內(nèi)的測(cè)試數(shù)據(jù),由于atoi的源代碼在程序中不可見(jiàn),CREST無(wú)法對(duì)其符號(hào)執(zhí)行,使用atoi的具體運(yùn)行值代替符號(hào)值后,使得符號(hào)路徑條件簡(jiǎn)化為一個(gè)具體值,導(dǎo)致測(cè)試過(guò)程中止; sCREST使用分段式符號(hào)分析方法對(duì)atoi處理后,使CREST中原本中止的測(cè)試過(guò)程繼續(xù)進(jìn)行,明顯提高了被測(cè)程序的分支覆蓋數(shù)。

圖3 tcas程序的分支覆蓋情況對(duì)比

圖4 tcas程序在CREST系統(tǒng)中的分支覆蓋情況

表1表明,tcas在sCREST中所需的測(cè)試執(zhí)行時(shí)間比CREST有所增加,是因?yàn)閠cas在CREST中使用“具體化”方法后,符號(hào)路徑條件被簡(jiǎn)化為一個(gè)具體值,迫使只執(zhí)行一條路徑就結(jié)束了;sCREST使原本異常中止的混合執(zhí)行過(guò)程繼續(xù)進(jìn)行,執(zhí)行更多次迭代,生成更多的測(cè)試數(shù)據(jù),使得測(cè)試時(shí)間有所增加。

3.2 gzip-1.2.4程序

gzip是一個(gè)開(kāi)源的文件壓縮程序。本文把gzip-1.2.4中的被解壓縮的文件參數(shù)設(shè)置為某一固定文件,把gzip-1.2.4程序接收的命令行選項(xiàng)參數(shù)設(shè)置為符號(hào)變量,使工具為這些變量生成測(cè)試數(shù)據(jù),并添加額外的限制條件使工具生成有效合理的測(cè)試數(shù)據(jù)。由圖5可以看出,隨著迭代次數(shù)的增加, sCREST系統(tǒng)可以顯著提高被測(cè)程序的分支覆蓋數(shù)。

圖5 gzip-1.2.4程序的分支覆蓋情況對(duì)比

3.3 grep-2.2程序

grep是一個(gè)開(kāi)源C程序,用于使用正則表達(dá)式進(jìn)行文本搜索。本文把程序中正則表達(dá)式設(shè)置為長(zhǎng)度為5的符號(hào)字符數(shù)組,被搜索的文本設(shè)置為長(zhǎng)度為40的符號(hào)字符數(shù)組,使用默認(rèn)的匹配選項(xiàng)。為方便實(shí)驗(yàn)對(duì)比,此處設(shè)置與文獻(xiàn)[3]中對(duì)grep-2.2程序的設(shè)置相同。

從圖6中可見(jiàn),sCREST比CREST能夠覆蓋更多的分支。但sCREST對(duì)grep-2.2的分支覆蓋的提高幅度不如tcas程序明顯,是因?yàn)殡m然在測(cè)試grep-2.2時(shí)符號(hào)路徑條件中出現(xiàn)一些庫(kù)函數(shù),但是在CREST中使用“具體值”簡(jiǎn)化后,符號(hào)路徑條件中仍然存在其他的分支可以被取非,混合執(zhí)行測(cè)試過(guò)程可以繼續(xù)進(jìn)行,沒(méi)有出現(xiàn)中止的情況。

圖6 grep-2.2程序的分支覆蓋情況對(duì)比

在sCREST系統(tǒng)中,對(duì)grep-2.2中的源代碼不可見(jiàn)的庫(kù)函數(shù)進(jìn)行分段式符號(hào)執(zhí)行,因而庫(kù)函數(shù)使用具體值代替符號(hào)值的次數(shù)有所減少,提高了符號(hào)路徑條件的準(zhǔn)確性,但是被分段式符號(hào)分析的庫(kù)函數(shù)對(duì)被測(cè)系統(tǒng)行為的影響程度以及對(duì)測(cè)試數(shù)據(jù)的生成的影響程度不是很大,所以,分支覆蓋數(shù)并沒(méi)有得到非常明顯的提高。

在replace程序以及大型開(kāi)源程序vim-5.7[3]上進(jìn)行實(shí)驗(yàn),結(jié)果如表1所示?？梢钥闯?sCREST也能夠比CREST系統(tǒng)覆蓋更多的分支。但由于篇幅限制,其分支覆蓋變化不在此給出。

綜上,從表1、表2及各個(gè)被測(cè)程序的分支覆蓋變化曲線圖(圖3～圖6)中可以發(fā)現(xiàn),分支覆蓋數(shù)提高的幅度并不是與被測(cè)程序的代碼規(guī)模成正比。被分段符號(hào)分析處理的源代碼不可見(jiàn)的庫(kù)函數(shù)對(duì)整個(gè)程序行為的影響程度對(duì)分支數(shù)目的提高幅度起到重要的作用。庫(kù)函數(shù)對(duì)程序行為的影響包括該該庫(kù)函數(shù)是否對(duì)測(cè)試數(shù)據(jù)生成有影響(CREST為被定義為符號(hào)變量的變量生成測(cè)試數(shù)據(jù),庫(kù)函數(shù)是否直接或間接地對(duì)符號(hào)變量進(jìn)行操作)以及庫(kù)函數(shù)在程序中出現(xiàn)的次數(shù)。如果某個(gè)庫(kù)函數(shù)在程序中出現(xiàn)多次,更重要的是它對(duì)符號(hào)變量的測(cè)試數(shù)據(jù)的生成具有影響作用,那么sCREST用分段式符號(hào)分析方法對(duì)這些庫(kù)函數(shù)進(jìn)行處理后,分支覆蓋數(shù)可以得到明顯的提高。

總之,分段式混合執(zhí)行測(cè)試方法提高分支覆蓋的幅度取決于被分段式符號(hào)分析的函數(shù)對(duì)被測(cè)系統(tǒng)行為的影響程度以及其對(duì)測(cè)試數(shù)據(jù)的生成的影響程度,影響程度越大,分支覆蓋數(shù)提高越明顯。

從表1中可見(jiàn),sCREST系統(tǒng)所需的執(zhí)行時(shí)間比CREST有所增加,經(jīng)分析原因有2個(gè):

(1)當(dāng)CREST中的“具體化”方法處理源代碼不可見(jiàn)的函數(shù)導(dǎo)致混合執(zhí)行測(cè)試中止時(shí),sCREST會(huì)使這些異常中止的混合執(zhí)行繼續(xù)進(jìn)行,執(zhí)行更多次迭代,致使執(zhí)行時(shí)間增加(CREST使用“具體化”處理源代碼不可見(jiàn)的函數(shù)導(dǎo)致測(cè)試中止一般有2種情況:1)“具體化”后的極端情況是符號(hào)路徑條件被簡(jiǎn)化為一個(gè)具體值;2)由于“具體化”方法只對(duì)源代碼不可見(jiàn)的被調(diào)函數(shù)進(jìn)行具體執(zhí)行,計(jì)算其運(yùn)行時(shí)的具體值,無(wú)法對(duì)其跟進(jìn)符號(hào)執(zhí)行,導(dǎo)致沒(méi)有考慮被調(diào)函數(shù)的表達(dá)式,因此得到的符號(hào)路徑條件不完備,有可能使下次迭代程序的實(shí)際執(zhí)行路徑與預(yù)期執(zhí)行路徑不一致,導(dǎo)致路徑分歧,出現(xiàn)“Predicate failure”錯(cuò)誤,迫使CREST測(cè)試過(guò)程中止)。

(2)當(dāng)CREST中使用“具體化”方法處理源代碼不可見(jiàn)函數(shù)未導(dǎo)致測(cè)試過(guò)程異常中止時(shí),由于在sCREST中對(duì)源代碼不可見(jiàn)的函數(shù)進(jìn)行分段式符號(hào)分析,比直接使用源代碼不可見(jiàn)的庫(kù)函數(shù)的某一具體運(yùn)行值代替符號(hào)值需要更多的時(shí)間,因此sCREST的執(zhí)行時(shí)間會(huì)增加。實(shí)驗(yàn)數(shù)據(jù)也表明,雖然sCREST的測(cè)試執(zhí)行時(shí)間有所增加,但都是在可以接受的范圍內(nèi)。

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

本文針對(duì)混合執(zhí)行測(cè)試中的源代碼不可見(jiàn)函數(shù)調(diào)用問(wèn)題,提出分段式混合執(zhí)行測(cè)試方法,將分段式分析引入傳統(tǒng)混合執(zhí)行測(cè)試,按需結(jié)合符號(hào)執(zhí)行、分段式符號(hào)執(zhí)行以及具體執(zhí)行,針對(duì)符號(hào)執(zhí)行無(wú)法分析的源代碼不可見(jiàn)函數(shù)代碼片段進(jìn)行動(dòng)態(tài)分析,緩解了傳統(tǒng)混合執(zhí)行測(cè)試中的源代碼不可見(jiàn)的函數(shù)調(diào)用處理的局限性;在CREST上實(shí)現(xiàn)sCREST系統(tǒng),對(duì)本文提出的分段式混合執(zhí)行測(cè)試方法與傳統(tǒng)混合執(zhí)行方法進(jìn)行對(duì)比,結(jié)果顯示本文方法提高了測(cè)試數(shù)據(jù)的分支覆蓋數(shù),驗(yàn)證了其可行性和有效性。

本文工作是分段式符號(hào)分析應(yīng)用于混合執(zhí)行測(cè)試的初步探索,現(xiàn)階段sCREST系統(tǒng)針對(duì)的是源代碼不可見(jiàn),且分段式符號(hào)分析能夠處理的標(biāo)準(zhǔn)庫(kù)函數(shù)調(diào)用,但理論上,對(duì)于其他工作在源代碼層的、通過(guò)對(duì)源程序靜態(tài)插樁以實(shí)現(xiàn)從具體執(zhí)行獲取符號(hào)路徑條件的混合執(zhí)行測(cè)試工具,該方法也具有可行性。對(duì)分段式混合執(zhí)行測(cè)試方法產(chǎn)生的測(cè)試數(shù)據(jù)進(jìn)行檢錯(cuò)能力評(píng)估,是下一步的工作。

[1] Godefroid P,KlarlundN,SenK.DART:Directed Automated RandomTesting[J].ACMSIGPLAN Notices,2005,40(6):213-223.

[2] Sen K,Marinov D,Agha G.CUTE:A Concolic Unit Testing Engine for C[J].ACM SIGSOFT Software Engineering Notes,2005,30(5):263-272.

[3] Burnim J,Sen K.Heuristics for Scalable Dynamic Test Generation[C]//Proceedings of ASE’08.L’aquila, Italy:[s.n.],2008:443-446.

[4] 崔展齊,王林章,李宣東.一種目標(biāo)制導(dǎo)的混合執(zhí)行測(cè)試方法[J].計(jì)算機(jī)學(xué)報(bào),2011,34(6):953-964.

[5] 劉 杰,王嘉捷,歐陽(yáng)永基,等.基于污點(diǎn)指針的二進(jìn)制代碼缺陷檢測(cè)[J].計(jì)算機(jī)工程,2012,38(24): 46-49.

[6] Qu Xiao,Robinson B.A Case Study of Concolic Testing ToolsandTheirLimitations[C]//Proceedingsof ESEM’11.Banff,Canada:IEEE Press,2011:117-126.

[7] Godefroid P.Higher-order Test Generation[C]//Proceedings of PLDI’11.San Jose,USA:ACM Press,2011: 258-269.

[8] Godefroid P.CompositionalDynamicTestGeneration[C]//Proceedings of POPL’07.Nice,France: ACM Press,2007:47-54.

[9] 林錦濱,張曉菲,劉暉.符號(hào)執(zhí)行技術(shù)研究[C]//全國(guó)計(jì)算機(jī)安全學(xué)術(shù)交流會(huì)論文集.麗江:[出版者不詳], 2009:404-408.

[10] Chipounov V,Kuznetsov V,Candea G.S2E:A Platform for In-vivo Multi-Path Analysis of Software Systems[J]. ACM Transactions on Computer Systems,2012,30(1):1-49.

[11] Le W.Segmented Symbolic Analysis[C]//Proceedings of ICSE’13.San Francisco,USA:IEEE Press,2013: 212-221.

[12] Kim M,Kim Y,Jang Y.Industrial Application of Concolic TestingonEmbeddedSoftware:CaseStudies[C]// Proceedings of ICST’12.Montreal,Canada:IEEE Press, 2012:390-399.

[13] Kim Y,Kim M,Kim Y J,et al.Industrial Application of Concolic Testing Approach:A Case Study on Libexif by Using CREST-BV and KLEE[C]//Proceedings of ICSE’12.Zurich,Switzerland:IEEEPress,2012: 1143-1152.

[14] Jacob B.External Function Support[EB/OL].(2010-07-07).https://groups.google.com/forum/#1topic/ crest-users/UxRhhbSqNlk.

[15] Harrold J,Rothermel G.Siemens Programs,HR Variants [EB/OL].[2014-02-16].http://www.cc.gatech.edu/ aristotle/Tools/subjects/.

編輯 金胡考

Segmented Code Testing Based on Concolic Testing and Dynamic Analysis

LIU Chunhong,XU Lihua,YAN Ting,YANG Zongyuan
(Department of Computer Science and Technology,East China Normal University,Shanghai 200241,China)

Function calls with unavailable source codes can not be appropriately handled by symbolic execution in traditional concolic testing.To solve this problem,this paper proposes a segmented concolic testing method,which weaves,by demand,symbolic execution,segmented symbolic execution and concrete execution throughout the testing process.These function calls are treated as separate code segments,dynamically executed and analyzed to derive their corresponding program semantics.To demonstrate the effectiveness of the proposed method,this paper implements sCREST,a segmented concolic testing system based on CREST,and experiments with five open source systems. Experimental results show that segmente concolic testing is able to generate test data that covers more branches than that of the traditional approaches.

software testing;concolic testing;segmented symbolic analysis;dynamic analysis;test data generation; branch coverage

劉春宏,徐立華,顏 婷,等.基于混合測(cè)試和動(dòng)態(tài)分析的分段代碼測(cè)試[J].計(jì)算機(jī)工程, 2015,41(2):63-69,80.

英文引用格式:Liu Chunhong,Xu Lihua,Yan Ting,et al.Segmented Code Testing Based on Concolic Testing and Dynamic Analysis[J].Computer Engineering,2015,41(2):63-69,80.

1000-3428(2015)02-0063-07

:A

:TP311.5

10.3969/j.issn.1000-3428.2015.02.013

上海市自然科學(xué)基金資助項(xiàng)目(13ZR1413000)。

劉春宏(1988-),女,碩士研究生,主研方向:軟件測(cè)試;徐立華(通訊作者),副教授、博士;顏 婷,碩士研究生;楊宗源,教授、博士生導(dǎo)師。

2014-03-12

:2014-04-15E-mail:lhxu@cs.ecnu.edu.cn