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

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

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

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

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

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

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

1 概述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 sCREST系統(tǒng)

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

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

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

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

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

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

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

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

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

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

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

3 實驗與評估

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

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

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

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

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

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

表2中分別對CREST和sCREST的分支覆蓋率進行對比,除replace外,其他被測程序,無論是相對分支覆蓋率還是絕對分支覆蓋率,sCREST比CREST都有所提高。

表1和表2中的數(shù)據(jù)是實驗總體情況,下面對具代表性的被測程序做詳細說明。

3.1 tcas程序

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

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

圖3 tcas程序的分支覆蓋情況對比

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

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

3.2 gzip-1.2.4程序

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

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

3.3 grep-2.2程序

grep是一個開源C程序,用于使用正則表達式進行文本搜索。本文把程序中正則表達式設(shè)置為長度為5的符號字符數(shù)組,被搜索的文本設(shè)置為長度為40的符號字符數(shù)組,使用默認的匹配選項。為方便實驗對比,此處設(shè)置與文獻[3]中對grep-2.2程序的設(shè)置相同。

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

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

[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] 崔展齊,王林章,李宣東.一種目標制導(dǎo)的混合執(zhí)行測試方法[J].計算機學(xué)報,2011,34(6):953-964.

[5] 劉 杰,王嘉捷,歐陽永基,等.基于污點指針的二進制代碼缺陷檢測[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] 林錦濱,張曉菲,劉暉.符號執(zhí)行技術(shù)研究[C]//全國計算機安全學(xué)術(shù)交流會論文集.麗江:[出版者不詳], 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

劉春宏,徐立華,顏 婷,等.基于混合測試和動態(tài)分析的分段代碼測試[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é)基金資助項目(13ZR1413000)。

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

2014-03-12

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