張 卓,譚慶平,毛曉光,雷 晏,常 曦,薛建新,

1(國(guó)防科技大學(xué) 計(jì)算機(jī)學(xué)院,湖南 長(zhǎng)沙 410072)

2(重慶大學(xué) 大數(shù)據(jù)與軟件學(xué)院,重慶 400044)

3(信息物理社會(huì)可信服務(wù)計(jì)算教育部重點(diǎn)實(shí)驗(yàn)室(重慶大學(xué)),重慶 400044)

4(上海第二工業(yè)大學(xué) 計(jì)算機(jī)與信息工程學(xué)院,上海 200127)

軟件調(diào)試是軟件開發(fā)過(guò)程中非常耗時(shí)的活動(dòng).為了提升軟件調(diào)試的性能,研究人員提出了許多錯(cuò)誤定位方法(例如文獻(xiàn)[1-6]).其中,基于頻譜的錯(cuò)誤定位方法(spectrum-based fault localization,簡(jiǎn)稱SFL)[2]是被廣泛研究和使用的錯(cuò)誤定位方法,展示了其在減少檢測(cè)到錯(cuò)誤代碼的百分比方面的有效性[1,5,7,8].SFL嘗試通過(guò)度量每個(gè)錯(cuò)誤語(yǔ)句的可疑值來(lái)識(shí)別錯(cuò)誤語(yǔ)句.首先,SFL利用插樁工具來(lái)對(duì)程序進(jìn)行插樁,自動(dòng)收集語(yǔ)句在測(cè)試用例執(zhí)行中的覆蓋數(shù)據(jù),以此構(gòu)建程序譜;然后,基于程序譜,SFL利用不同的度量公式來(lái)評(píng)估語(yǔ)句為錯(cuò)誤的可疑性;最后,SFL輸出以可疑性為排名的語(yǔ)句列表.

然而,SFL關(guān)注語(yǔ)句選擇和排名,卻忽略調(diào)試工程師所需要關(guān)心的上下文信息和可疑語(yǔ)句之間的傳播關(guān)系,這些關(guān)系可以方便其理解和分析失效原因.研究[9,10]表明,缺乏上下文信息可能會(huì)降低錯(cuò)誤定位性能.因此,有必要構(gòu)建上下文信息來(lái)優(yōu)化錯(cuò)誤定位.

為了構(gòu)建上下文信息,本文發(fā)現(xiàn),程序切片技術(shù)[11,12]可能成為解決這個(gè)問(wèn)題的候選者.程序切片技術(shù)提取程序語(yǔ)句的數(shù)據(jù)與控制依賴關(guān)系,以選出影響程序輸出的語(yǔ)句子集.它將這個(gè)語(yǔ)句子集命名為切片.可以發(fā)現(xiàn),切片可以顯示切片中語(yǔ)句之間的數(shù)據(jù)與控制依賴關(guān)系,以及如何傳播到輸出的過(guò)程.也就是說(shuō),切片顯示影響程序輸出的相關(guān)語(yǔ)句相互作用的上下文信息.這意味著錯(cuò)誤定位可以利用切片來(lái)提供上下文信息.現(xiàn)有的程序切片技術(shù)大致可分為靜態(tài)切片和動(dòng)態(tài)切片兩大類:靜態(tài)切片根據(jù)數(shù)據(jù)和控制依賴關(guān)系分析程序,而不運(yùn)行程序;動(dòng)態(tài)切片沿著執(zhí)行路徑的依賴關(guān)系進(jìn)行分析.在實(shí)際應(yīng)用中,靜態(tài)切片具有更高的時(shí)間復(fù)雜度,切片體積較大,可能會(huì)包含過(guò)多與具體錯(cuò)誤行為無(wú)關(guān)的語(yǔ)句;動(dòng)態(tài)切片則具有較高的空間復(fù)雜度,切片體積較小,可能會(huì)出現(xiàn)切片丟失錯(cuò)誤語(yǔ)句的情況[3,13].由于動(dòng)態(tài)切片體積較小且與具體執(zhí)行相關(guān)聯(lián),與靜態(tài)切片相比,動(dòng)態(tài)切片使用更為廣泛.因此,本文將動(dòng)態(tài)切片納入研究.

雖然程序切片提供了上下文信息,但是它對(duì)切片內(nèi)的語(yǔ)句賦予相同的可疑度.換言之,即使與原始程序大小相比,在切片體積明顯變小的情況下,它也不能區(qū)分切片中的哪個(gè)語(yǔ)句更可疑.然而,切片仍然包含許多語(yǔ)句,特別是當(dāng)程序規(guī)模較大時(shí),需要進(jìn)行大量的人工查找.因此,衡量一個(gè)片段中的語(yǔ)句的可疑性至關(guān)重要.

基于上述分析,本文試圖將程序切片融入錯(cuò)誤定位中,自動(dòng)獲取調(diào)試工程師所需的上下文信息,并進(jìn)一步將可疑性度量引入其中.因此,在前期研究[10]的基礎(chǔ)上,本文提出了Context-FL,通過(guò)使用動(dòng)態(tài)切片來(lái)構(gòu)建上下文信息,以及基于SFL的可疑性度量來(lái)評(píng)估上下文中語(yǔ)句的可疑性.本文在14個(gè)開源程序的大量錯(cuò)誤版本上展開了實(shí)驗(yàn),與8種個(gè)典型錯(cuò)誤定位方法進(jìn)行了對(duì)比.實(shí)驗(yàn)結(jié)果表明,與8種典型錯(cuò)誤方法相比,Context-FL的檢查代碼的平均成本降低最多可達(dá)52.79%.

本文第 1節(jié)介紹基于頻譜的錯(cuò)誤定位和動(dòng)態(tài)切片.第 2節(jié)具體描述本文方法 Context-FL.第 3節(jié)給出Context-FL的實(shí)現(xiàn).第4節(jié)描述實(shí)驗(yàn)以及結(jié)果分析.第5節(jié)介紹相關(guān)工作.第6節(jié)總結(jié)本文.

1 相關(guān)背景

1.1 基于頻譜的錯(cuò)誤定位

基于頻譜的錯(cuò)誤定位技術(shù)(spectrum-based fault localization,簡(jiǎn)稱SFL)意在構(gòu)建程序譜,并使用可疑評(píng)估公式來(lái)衡量每個(gè)語(yǔ)句的可疑值.程序譜是數(shù)據(jù)的集合,包括語(yǔ)句執(zhí)行覆蓋信息以及測(cè)試用例是否通過(guò)的信息,是程序動(dòng)態(tài)行為的一種具體視圖[5].

SFL基于程序譜定義了 4個(gè)參數(shù),并以此構(gòu)建可疑評(píng)估公式.4個(gè)參數(shù)anp、anf、aep、aef與具體語(yǔ)句綁定,分別表示執(zhí)行或者未執(zhí)行該語(yǔ)句的通過(guò)或者失敗測(cè)試用例數(shù).下標(biāo)的第 1部分表示該語(yǔ)句是否被測(cè)試用例所執(zhí)行(e)或者未被執(zhí)行(n),而第2部分則表示測(cè)試用例結(jié)果是通過(guò)(p)或失敗(f).

表1給出了5個(gè)測(cè)試用例{T1,T2,...,T5}的示例,以表明如何計(jì)算每個(gè)語(yǔ)句的4個(gè)參數(shù).如表1所示,前3行表示3個(gè)程序語(yǔ)句,最后一行為結(jié)果(0表示通過(guò),1表示失敗).左5列表示5個(gè)測(cè)試用例,每個(gè)單元格表示語(yǔ)句在對(duì)應(yīng)測(cè)試用例的執(zhí)行情況(1為執(zhí)行,0為未執(zhí)行).例如,語(yǔ)句 1中的T1值為 1表示測(cè)試用例T1運(yùn)行時(shí)執(zhí)行了Statement 1.對(duì)于語(yǔ)句1,aep的值為2表示執(zhí)行了Statement 1的通過(guò)測(cè)試用例有2個(gè),aef的值為1表示執(zhí)行了Statement 1的失敗測(cè)試用例有1個(gè),anp的值為0表示結(jié)果通過(guò)但未執(zhí)行Statement 1的測(cè)試用例不存在.

Table 1 An example illustrating program spectra表1 程序譜示例

假設(shè)程序P={s1,s2,...,sn},這表明P包含n個(gè)語(yǔ)句.該程序被測(cè)試套件T={T1,T2,...,Tm}執(zhí)行,T包含m個(gè)不同測(cè)試用例且至少包含1個(gè)失敗測(cè)試用例(參見圖1).如圖1所示,測(cè)試用例運(yùn)行完畢后,語(yǔ)句覆蓋情況與測(cè)試結(jié)果組成M×(N+1)的矩陣.左邊M×N矩陣表示語(yǔ)句執(zhí)行情況.如果語(yǔ)句sj由測(cè)試用例ti執(zhí)行,則xij為 1;否則為 0.矩陣最右側(cè)的結(jié)果向量e表示測(cè)試結(jié)果.如果ti是失敗測(cè)試用例,則ei為1;否則為0.

Fig.1 Coverage ofMtest cases after executed圖1M個(gè)測(cè)試用例執(zhí)行后的覆蓋信息

基于圖1矩陣,SFL計(jì)算出每個(gè)語(yǔ)句的4個(gè)參數(shù)anp、anf、aep、aef,然后使用可疑性度量公式來(lái)計(jì)算每個(gè)語(yǔ)句的可疑值.SFL構(gòu)建可疑性度量公式的基本思想:希望錯(cuò)誤語(yǔ)句具有相對(duì)較高的aef值、較低的aep值.其理想情況是錯(cuò)誤語(yǔ)句的aef值為最大,而aep值為最小.這意味著錯(cuò)誤語(yǔ)句在所有失敗測(cè)試用例中被執(zhí)行得最多,而通過(guò)的測(cè)試用例中被執(zhí)行得最少.可疑性度量公式會(huì)賦予錯(cuò)誤語(yǔ)句最大可疑值.一般來(lái)說(shuō),不同度量公式賦予通過(guò)和失敗測(cè)試用例的不同權(quán)值,從而產(chǎn)生不同的排名.研究人員對(duì)他們提出的方法進(jìn)行了實(shí)證調(diào)查,其中,Xie等人[2,14]理論分析了大量SFL度量公式,總結(jié)出了5種較優(yōu)公式.除了這5種公式,Ochiai、Barinel和D*是最新錯(cuò)誤定位評(píng)價(jià)研究[4]中排名前3的錯(cuò)誤定位方法.表2給出了這8種方法的可疑性度量公式.需要說(shuō)明的是,D*公式中的*通常被賦值為2[4],這也是本文實(shí)驗(yàn)所采取的賦值.

Table 2 Maximal formulas of SFL表2 最優(yōu)SFL公式

SFL信息收集和工作原理比較簡(jiǎn)單,并能準(zhǔn)確定位錯(cuò)誤語(yǔ)句,因而得到了廣泛的研究和應(yīng)用.然而它并沒(méi)有給出執(zhí)行程序的上下文信息,也沒(méi)有考慮到語(yǔ)句之間的依賴關(guān)系.其產(chǎn)生的語(yǔ)句排名列表沒(méi)有顯示語(yǔ)句之間依賴關(guān)系,有不少可疑性較高的語(yǔ)句與程序錯(cuò)誤輸出并沒(méi)有關(guān)聯(lián).這種語(yǔ)句孤立與割裂,加重了開發(fā)人員理解和搜索問(wèn)題的難度.當(dāng)程序規(guī)模大時(shí),不相關(guān)的語(yǔ)句將迅速增加,這可能對(duì)軟件調(diào)試有很大的干擾.因此,需要構(gòu)建與錯(cuò)誤輸出相關(guān)聯(lián)的可疑上下文,以便更好地了解錯(cuò)誤問(wèn)題,并進(jìn)一步減少手動(dòng)查找范圍.

1.2 動(dòng)態(tài)切片

程序切片技術(shù)通過(guò)提取程序語(yǔ)句的數(shù)據(jù)和控制依賴關(guān)系,選擇影響錯(cuò)誤輸出的語(yǔ)句的子集來(lái)構(gòu)建上下文信息.程序切片技術(shù)首先由Weiser引入[11],已經(jīng)在程序測(cè)試、程序理解和軟件維護(hù)方面得到廣泛應(yīng)用.給定一個(gè)程序P和輸入I,當(dāng)P根據(jù)I執(zhí)行時(shí)(例如文獻(xiàn)[15-17]),切片技術(shù)切出直接或間接地影響一些變量出現(xiàn)的值的語(yǔ)句集合.靜態(tài)程序切片由程序P中可能會(huì)影響變量v在某個(gè)點(diǎn)p[11,18]的值的所有語(yǔ)句組成,但它涉及所有可能的程序執(zhí)行.然而,調(diào)試常處理特定的錯(cuò)誤執(zhí)行,以此查找導(dǎo)致該執(zhí)行不正確的原因.因此,本文使用保留特定程序輸入的程序行為切片,而不是針對(duì)所有輸入的集合的靜態(tài)切片.這種切片被稱為動(dòng)態(tài)切片[12].動(dòng)態(tài)切片沿著執(zhí)行路徑收集運(yùn)行時(shí)的信息,與靜態(tài)切片相比可以顯著地減少切片的大小[19,20].靜態(tài)切片基于靜態(tài)數(shù)據(jù)相關(guān)性計(jì)算,其切片中的語(yǔ)句數(shù)量很多,且通常根據(jù)對(duì)象在程序中的存在和指針進(jìn)行保護(hù).相對(duì)而言,動(dòng)態(tài)切片針對(duì)具體執(zhí)行捕獲動(dòng)態(tài)數(shù)據(jù)和控制依賴關(guān)系,更有針對(duì)性且精度較高,有助于調(diào)試人員理解和縮小其搜索范圍.因此,本文采用動(dòng)態(tài)切片技術(shù)來(lái)構(gòu)建上下文.

動(dòng)態(tài)切片標(biāo)準(zhǔn)可以表示為元組C=(Sk,V,I),其中,Sk表示語(yǔ)句變量為V的輸入I上的語(yǔ)句S的k次出現(xiàn).如圖2所示,標(biāo)準(zhǔn)(n=91,v,2),其中,91表示第1次出現(xiàn)的語(yǔ)句9.由于輸入n=2,這表明該循環(huán)執(zhí)行了2次,即v=5和v=6分別執(zhí)行1次.因?yàn)橥ㄟ^(guò)在第2個(gè)循環(huán)中分配5到v而使第1個(gè)循環(huán)中的變量v的賦值發(fā)生位移,所以可以從動(dòng)態(tài)切片中省略if語(yǔ)句的else分支.而標(biāo)準(zhǔn)(9,v)下的程序的靜態(tài)切片包括了整個(gè)程序.顯然,動(dòng)態(tài)切片更有利于縮小查找范圍,且與具體執(zhí)行相關(guān),更具有針對(duì)性.

Fig.2 Examples of dynamic slice and static slice圖2 動(dòng)態(tài)切片與靜態(tài)切片的例子

2 CONTEXT-FL算法設(shè)計(jì)

2.1 算法設(shè)計(jì)

Context-FL的基本思想是:將動(dòng)態(tài)切片技術(shù)應(yīng)用于 SFL,構(gòu)建可疑上下文及其元素.Context-FL首先構(gòu)建上下文,顯示語(yǔ)句在程序執(zhí)行過(guò)程中如何影響和被影響;然后,利用SFL評(píng)估上下文中元素的可疑值.

算法1和算法2描述了Context-FL方法的關(guān)鍵部分.

算法1.Get suspicious context.

算法2.Get statements suspiciousness in the context.

首先對(duì)算法1和算法2進(jìn)行解釋.本節(jié)采用第1節(jié)定義的程序P和測(cè)試用例套件T.即程序P由一組表示為{s1,s2,...,sm}的語(yǔ)句組成,相應(yīng)的測(cè)試套件T={T1,T2,...,Tn}.Context{s1,s2,...,sn}表示與錯(cuò)誤輸出相關(guān)的語(yǔ)句的集合.EnhancedContext{s1,s2,...,sn}表示帶可疑值標(biāo)記的上下文語(yǔ)句的集合.接下來(lái),將討論 Context-FL算法中的每個(gè)步驟.

· 步驟1:構(gòu)建可疑片段和他們的元素.

如算法1所示,該步驟迭代地構(gòu)造可疑上下文,直到遍歷完所有失敗測(cè)試用例為止.第2行～第4行表示算法1所需要的輸入變量,E表示輸出錯(cuò)誤結(jié)果的輸出語(yǔ)句,V是語(yǔ)句中變量之一或變量集合,T表示測(cè)試用例套件.第5行是算法1的輸出,即上下文,由一組至少影響1個(gè)錯(cuò)誤輸出的語(yǔ)句集合組成.由于上下文由導(dǎo)致程序錯(cuò)誤輸出的執(zhí)行軌跡構(gòu)成,它包含了導(dǎo)致失敗的測(cè)試用例的錯(cuò)誤語(yǔ)句.在第7行中,上下文初始化為空集.第8行和第9行表示循環(huán)依次遍歷完每個(gè)失敗測(cè)試用例.第10行獲取可疑上下文片段,即每個(gè)失敗測(cè)試用例錯(cuò)誤輸出的切片并集.最后,算法1返回可疑上下文片段Context.

· 步驟2:計(jì)算可疑片段中每個(gè)元素的可疑值.

如算法2所示,第2行和第3行顯示輸入變量,S(S={s1,s2,...,sn})表示由算法1生成的可疑上下文片段.M是可用于SFL公式計(jì)算的輸入矩陣,結(jié)構(gòu)如圖1所示.第4行是輸出,并且包含由標(biāo)記著可疑值的增強(qiáng)型可疑上下文.在第 6行中,增強(qiáng)的上下文初始化為空.第 7行搜索上下文S中的每個(gè)元素.在第 8行和第 9行中,函數(shù)SearchElementInfo(si,M)分析測(cè)試用例T的語(yǔ)句覆蓋信息和測(cè)試結(jié)果,函數(shù)GetSuspiciousness(si,ElementInfo(si))采用SFL公式計(jì)算S中每個(gè)語(yǔ)句的可疑值.語(yǔ)句覆蓋信息的格式和測(cè)試用例的測(cè)試結(jié)果是一個(gè)矩陣,如圖1所示.由于一些語(yǔ)句的可疑值可能相同,所以O(shè)rder(EnhancedContext)函數(shù)按照它們的降序?qū)φZ(yǔ)句進(jìn)行排序.在本研究中,SFL以源代碼中的行號(hào)降序排列具有相同可疑值的語(yǔ)句.

· 步驟3:輸出錯(cuò)誤定位結(jié)果.

此步驟將定制本地化結(jié)果輸出.該定位包含一個(gè)增強(qiáng)的上下文,其語(yǔ)句以SFL給出的可疑值降序排列.定位結(jié)果可以幫助開發(fā)人員了解和定位錯(cuò)誤,將一些信息附加到每個(gè)語(yǔ)句上,如可疑值和行號(hào).

2.2 例子演示

如圖3所示,本節(jié)通過(guò)包含錯(cuò)誤語(yǔ)句s3的程序P,以此說(shuō)明如何應(yīng)用Context-FL.這個(gè)例子選擇GP02來(lái)計(jì)算16個(gè)語(yǔ)句的可疑值.每個(gè)語(yǔ)句之下的單元格表示該語(yǔ)句是否被測(cè)試用例執(zhí)行(1表示執(zhí)行,0表示未執(zhí)行),而最右側(cè)的單元格表示測(cè)試用例的執(zhí)行是否失敗(1表示失敗,0為通過(guò)).由GP02根據(jù)覆蓋信息和測(cè)試用例結(jié)果得出排序:{s7,s8,s9,s12,s14,s10,s11,s2,s3,s1,s13,s4,s6,s5,s15,s16}.這個(gè)集合不能表示可疑語(yǔ)句之間的關(guān)系,也不能區(qū)分影響錯(cuò)誤輸出的語(yǔ)句.例如,s3和s8都被全部失敗測(cè)試用例所執(zhí)行,s3是錯(cuò)誤的語(yǔ)句而s8不是.然而與s8相比,s3被更多地通過(guò)測(cè)試用例執(zhí)行.因此,s3的可疑值要比s8低.但事實(shí)是,s8并不在導(dǎo)致錯(cuò)誤輸出的執(zhí)行序列當(dāng)中.這就解釋為什么s3排名第9,并且可疑值比一些與錯(cuò)誤輸出無(wú)關(guān)語(yǔ)句的可疑值低.

Fig.3 An example illustrating Context-FL圖3 Context-FL例子說(shuō)明

為了解決這個(gè)問(wèn)題,Context-FL通過(guò)使用切片標(biāo)準(zhǔn)(t1,s14,d1)來(lái)構(gòu)建錯(cuò)誤輸出的動(dòng)態(tài)切片.該切片包括與失敗測(cè)試用例t1的輸出有直接關(guān)系的語(yǔ)句{s1,s3,s7,s14}.最后,GP02生成新的排名列表:{s7,s14,s3,s1},其中,s3被排在第3且{s8,s9,s12,s10,s11,s2,s13,s4,s6,s5,s15,s16}不包括在上下文中,因?yàn)樗鼈兣c失敗測(cè)試用例t1和t6的錯(cuò)誤輸出沒(méi)有關(guān)系.因此,Context-FL比原來(lái)的GP02更有效.

3 CONTEXT-FL實(shí)現(xiàn)框架

3.1 實(shí)現(xiàn)框架

本節(jié)將詳細(xì)介紹錯(cuò)誤定位方法Context-FL的實(shí)現(xiàn)框架.如圖4所示,Context-FL主要架構(gòu)由3個(gè)主要功能模塊組成,分別是程序信息提取模塊、可疑上下文生成模塊、可疑計(jì)算模塊.

程序信息提取模塊的主要功能是在執(zhí)行測(cè)試用例后提取程序覆蓋信息.第 1個(gè)不可或缺的步驟是程序插樁,其目的是捕獲程序的運(yùn)行信息.插樁點(diǎn)的選擇由錯(cuò)誤定位方法確定.因?yàn)槭占銐虻暮头侨哂嗟男畔⒎浅Ｖ匾?所以需要采用適當(dāng)?shù)牟鍢都夹g(shù),以此控制插樁的代碼量,并且不會(huì)產(chǎn)生大量的冗余信息引起干擾.第2步是收集數(shù)據(jù).因?yàn)樵诓鍢吨?程序會(huì)產(chǎn)生大量的運(yùn)行信息,必須以適當(dāng)?shù)姆绞绞占瘮?shù)據(jù)進(jìn)行抽象和恢復(fù),以便于下一步的分析和計(jì)算工作.由于數(shù)據(jù)量相對(duì)較大,需要對(duì)數(shù)據(jù)進(jìn)行簡(jiǎn)化.接下來(lái)是對(duì)每個(gè)測(cè)試用例生成的數(shù)據(jù)進(jìn)行分類,使得所需數(shù)據(jù)以統(tǒng)一的方式存儲(chǔ).最后生成SFL計(jì)算的矩陣信息文件.由于軟件的復(fù)雜性和規(guī)模日益增加,程序的運(yùn)行數(shù)據(jù)顯著增加.雖然采取了各種措施來(lái)壓縮或減少在收集階段收集的數(shù)據(jù)量,但需要分析的數(shù)據(jù)量仍然很大.因此,有效的數(shù)據(jù)分析方法是絕對(duì)必要的.程序切片信息、狀態(tài)信息和統(tǒng)計(jì)信息是分析的 3個(gè)主要數(shù)據(jù)表現(xiàn)形式.Context-FL使用統(tǒng)計(jì)信息來(lái)查找與錯(cuò)誤相關(guān)聯(lián)的位置,這種類型的信息是通過(guò)分析程序的統(tǒng)計(jì)數(shù)據(jù)和提取特定模型來(lái)生成的.該方法通常使用語(yǔ)句、分支、預(yù)測(cè)信息、基本塊和功能等程序覆蓋信息,比較失敗測(cè)試用例和成功測(cè)試用例并分析其差異性.最后,在不同要素之間的聯(lián)系的基礎(chǔ)上,產(chǎn)生了可疑值.

Fig.4 Architecture of Context-FL圖4 Context-FL框架結(jié)構(gòu)

可疑上下文生成模塊的主要功能是找到與錯(cuò)誤語(yǔ)句相關(guān)聯(lián)的一組語(yǔ)句片段,該片段包含了錯(cuò)誤語(yǔ)句且又大幅小于源代碼量.其目的是通過(guò)縮小搜索范圍來(lái)提高錯(cuò)誤定位的效率.程序切片技術(shù)是一種分解技術(shù),根據(jù)具體計(jì)算提取相關(guān)語(yǔ)句.它可以分析元素之間的依賴關(guān)系并縮小搜索范圍.與其他可疑上下文提取技術(shù)相比,程序切片提供了一種有效的方法來(lái)了解程序執(zhí)行是否影響輸出.根據(jù)第 1.2節(jié)切片技術(shù)的分析,本框架采用動(dòng)態(tài)切片技術(shù)提取可疑片段.雖然切片技術(shù)在語(yǔ)句關(guān)聯(lián)分析中具有很強(qiáng)的能力,但是由于程序切片生成的可疑上下文中的語(yǔ)句不能區(qū)分,因此這些語(yǔ)句的可疑值是相同的.由于目前軟件的規(guī)模不斷擴(kuò)大,所以片段的規(guī)模將會(huì)大為增加.如果只從片段中找出錯(cuò)誤的位置,效率會(huì)很低,效果也會(huì)大為降低.可疑計(jì)算模塊的主要功能是根據(jù)可疑環(huán)境,按照可疑值的大小順序?qū)ζ沃械恼Z(yǔ)句進(jìn)行排序.

受SFL技術(shù)的啟發(fā),當(dāng)語(yǔ)句的執(zhí)行影響了失敗的測(cè)試用例的輸出時(shí),語(yǔ)句的可疑值會(huì)增加.另一方面,如果程序語(yǔ)句的執(zhí)行影響成功測(cè)試用例的輸出,則其可疑值會(huì)降低.因此,可疑計(jì)算模塊定義了新的統(tǒng)計(jì)變量.

3.2 Context-FL使用的工具

首先介紹 EMMA[21]和 JSlice[22].EMMA是用于測(cè)量和報(bào)告 Java代碼覆蓋率的開源工具包.它是 100%純Java且沒(méi)有依賴外部庫(kù),可以在任何Java 2 JVM中工作.它支持4種不同的覆蓋類型:類、方法、行和基本塊.此外,它可以檢測(cè)單個(gè)源代碼行何時(shí)被部分覆蓋.EMMA的輸出報(bào)告類型包括純文本、HTML和XML.特別地,HTML報(bào)告支持源代碼鏈接.本文Context-FL主要使用行覆蓋類型和HTML輸出類型,如圖5所示.

如圖5所示,88行的深色表示在執(zhí)行測(cè)試用例時(shí)沒(méi)有執(zhí)行該行,83行和92行的淺色表示該行只有一部分被執(zhí)行,其余標(biāo)深色的行完全被執(zhí)行.本文過(guò)濾覆蓋信息并擺脫其他不相關(guān)的信息.由于大型程序的文件數(shù)量眾多,因此需要根據(jù)測(cè)試用例的順序?qū)Ω采w信息文件進(jìn)行重新編號(hào)、分類和存儲(chǔ).在運(yùn)行所有測(cè)試用例之后,覆蓋信息文件以矩陣的形式進(jìn)行存儲(chǔ),如圖1所示.

JSlice是Java程序的動(dòng)態(tài)切片工具.給定一個(gè)程序P,切片工具執(zhí)行一個(gè)切片標(biāo)準(zhǔn)(I,L,V),其中,I是一個(gè)輸入,L表示在程序P執(zhí)行期間根據(jù)輸入I執(zhí)行的一些語(yǔ)句的集合,V是由L引用的一組變量[22,23].由切片工具生成切片的目的是:在執(zhí)行P期間找到影響語(yǔ)句L中的變量V的一組語(yǔ)句的集合,這些語(yǔ)句與L及其變量V是動(dòng)態(tài)相關(guān)的.首先,將Java程序的執(zhí)行路徑轉(zhuǎn)換為與執(zhí)行跟蹤相關(guān)聯(lián)的字節(jié)流,并以簡(jiǎn)潔的形式進(jìn)行壓縮.Jslice使用的動(dòng)態(tài)切片算法是直接在壓縮程序跟蹤上運(yùn)行的算法,可以找到被忽略的錯(cuò)誤語(yǔ)句.一般動(dòng)態(tài)切片算法只給出 1組影響語(yǔ)句L中變量執(zhí)行的語(yǔ)句,而Jslice除了發(fā)現(xiàn)通用算法發(fā)現(xiàn)的語(yǔ)句之外,還可能會(huì)發(fā)現(xiàn)一些影響語(yǔ)句L中的變量V的隱藏語(yǔ)句.本文在Context-FL中使用的JSlice的版本是JSlice v1.0,支持本文實(shí)驗(yàn)的程序都是順序程序.JSlice可以使用的是Fedora Core 3/4或類似的系統(tǒng).下一節(jié)的實(shí)驗(yàn)是在Fedora Core 3上運(yùn)行的.

Fig.5 EMMA coverage report圖5 EMMA覆蓋報(bào)告

4 實(shí) 驗(yàn)

4.1 實(shí)驗(yàn)設(shè)計(jì)

實(shí)驗(yàn)將表2中的8種錯(cuò)誤定位方法與Context-FL對(duì)比.對(duì)比基準(zhǔn)程序集為14組Java程序.表3描述了這些實(shí)驗(yàn)程序,依次為簡(jiǎn)要描述(第2列)、實(shí)驗(yàn)使用的錯(cuò)誤版本數(shù)量(第3列)、語(yǔ)句行數(shù)(第4列)和測(cè)試用例數(shù)(第5列).這些從SIR[24]和Defect4J[25]獲取的程序被廣泛使用.

Table 3 Subject programs表3 實(shí)驗(yàn)對(duì)象

表中前10個(gè)程序[24]原本包含102個(gè)錯(cuò)誤版本.實(shí)驗(yàn)沒(méi)有采用schedule 1的版本1、schedule 2的版本2、版本4、版本9、版本10、版本12、版本14和Tot_info的版本4、版本10、版本12、版本14.因?yàn)樗鼈儧](méi)有失敗的測(cè)試用例,至少有 1個(gè)失敗的測(cè)試用例是執(zhí)行動(dòng)態(tài)切片所必需的.實(shí)驗(yàn)還排除了執(zhí)行動(dòng)態(tài)切片失敗的Tot_ info的版本11,以及錯(cuò)誤語(yǔ)句在依賴庫(kù)中的版本19.對(duì)于Jtcas,實(shí)驗(yàn)使用了14個(gè)代表性的錯(cuò)誤.后3個(gè)程序選自Defect4J[25],Defect4J是一個(gè)真實(shí)錯(cuò)誤的數(shù)據(jù)集.在Defect4J中,實(shí)驗(yàn)選取了chart的版本1、版本3、版本6、版本7、版本12、版本13、版本17、版本20、版本23和版本24,mockito的版本1、版本5、版本7、版本8、版本26、版本28、版本29、版本34和版本38,time的版本4、版本16和版本19,math的35個(gè)單錯(cuò)誤版本的18個(gè).其他錯(cuò)誤版本沒(méi)有被采用的原因:一是本文研究主要是針對(duì)單錯(cuò)誤,而其他版本為多錯(cuò)誤;二是沒(méi)有編譯運(yùn)行成功.因此如表3所示,實(shí)驗(yàn)最終采用了129個(gè)錯(cuò)誤版本.

4.2 結(jié)果分析

為了評(píng)估本文提出的錯(cuò)誤定位方法的有效性,實(shí)驗(yàn)采用錯(cuò)誤定位精度(稱為Acc)和相對(duì)改進(jìn)值(稱為RImp)作為評(píng)價(jià)標(biāo)準(zhǔn)[26].Acc被定義為在找到真正的錯(cuò)誤語(yǔ)句之前要檢查的可執(zhí)行語(yǔ)句的百分比.RImp是使用Context-FL找到所有錯(cuò)誤需要檢查的語(yǔ)句總數(shù)除以使用對(duì)比方法需要檢查的語(yǔ)句總數(shù).Rimp的值越低,代表定位效果越好[27].

由于對(duì)比方法較多,圖6將以分組的方式來(lái)更好地顯示 Context-FL和對(duì)比方法的 Acc值.對(duì)于每個(gè)子圖——圖6(a)和圖6(b),橫坐標(biāo)表示在所有程序中檢查的可執(zhí)行語(yǔ)句的百分比.縱坐標(biāo)表示定位方法找出錯(cuò)誤的比例.圖6中的每一個(gè)點(diǎn)表示在檢查可執(zhí)行語(yǔ)句的百分比時(shí),定位到的錯(cuò)誤的百分比.

Fig.6 Acc comparison between SFL and Context-FL圖6 SFL和Context-FL的Acc對(duì)比

從圖6(a)和圖6(b)可以看出,除了 ER5和 GP19之外,檢查可執(zhí)行語(yǔ)句到 5%時(shí)則出現(xiàn)了明顯的效果提升.即使是ER5和GP19,在橫坐標(biāo)百分比分別為15%和10%時(shí)也出現(xiàn)了明顯的效果提升.因此,Context-FL方法提高了8種定位方法的有效性.

由于對(duì)比方法較多,圖7也分為圖7(a)和圖7(b)兩個(gè)子圖,顯示了Context-FL在每個(gè)程序上的 RImp值.采用Context-FL方法后,需要檢查的語(yǔ)句數(shù)明顯減少,從Nanoxml_v3的GP03的20.22%(最優(yōu)值)到chart的D*的88.63%(最差值).這意味著Context-FL只需要檢查SFL所需檢查的執(zhí)行語(yǔ)句數(shù)的20.22%～88.63%,就能定位到錯(cuò)誤.從圖7(a)和圖7(b)可以發(fā)現(xiàn),Context-FL更加有效和穩(wěn)定,特別是當(dāng)程序規(guī)模大時(shí)效果則更為顯著.

Fig.7 RImp of our approach圖7 本文方法的RImp

為了對(duì)改進(jìn)效果進(jìn)行更詳細(xì)的描述,圖8顯示了 RImp的分布,分別為 0～20%,20%～40%,40%～60%,60%～80%和 80%～100%.每個(gè)間隔代表分布在此區(qū)間的 RImp值的百分比.例如,GP02在 20%～40%區(qū)間的值為50.00%.這意味著在 50%的錯(cuò)誤版本中,使用本文的方法定位到錯(cuò)誤,它所需檢查的語(yǔ)句數(shù)為使用 GP02所需檢查的語(yǔ)句數(shù)的20%～40%.從圖8可以看出,RImp值主要分布在40%和60%之間,其次是20%～40%.這表明,本文的方法對(duì)于提高定位效果還是非常明顯的.

Fig.8 RImp distribution of our approach圖8 本文方法的RImp分布

如圖9所示,最大節(jié)約量(Saving=100%-RImp)為GP03的79.78%,最低節(jié)約量為D*的11.37%,平均節(jié)約范圍為40.56%～52.79%.這意味著在使用Context-FL檢查語(yǔ)句的數(shù)量時(shí),可以減少11.37%～79.78%.總而言之,與實(shí)驗(yàn)中的8種定位方法相比,Context-FL明顯減少了語(yǔ)句的檢查數(shù)量.因此,Context-FL定位能力更強(qiáng).

Fig.9 Saving of our approach over SFL圖9 本文方法和SFL的Saving對(duì)比

Lei等人[27,28]以靜態(tài)反向切片和執(zhí)行切片的交集構(gòu)建信息矩陣,并基于該矩陣提出重新定義語(yǔ)句懷疑度計(jì)算公式的方法(本文簡(jiǎn)稱Lei-FL).為了進(jìn)一步說(shuō)明Context-FL的有效性,實(shí)驗(yàn)將Context-FL和Lei-FL進(jìn)行了比較.Lei-FL使用的程序集為C程序,與實(shí)驗(yàn)所使用JAVA版本的Print tokens 1、Print tokens 2、Schedule 1、Schedule 2、Tot info和 Jtcas為一組程序,錯(cuò)誤版本也相同.因此,實(shí)驗(yàn)選取在這些程序上效力較好的 5種公式(即 ER5,Barinel,GP02,GP19和 D*),分別應(yīng)用 Context-FL和 Lei-FL,并對(duì)比它們的效力.如圖10所示,在所有 5種公式上,Context-FL曲線一直高于Lei-FL曲線.這說(shuō)明Context-FL的定位效力高于Lei-FL.

Fig.10 Acc comparison between Context-FL and Lei-FL圖10 Context-FL和Lei-FL的Acc對(duì)比

表4描述了這些實(shí)驗(yàn)程序的時(shí)間開銷的對(duì)比情況.表中數(shù)據(jù)的分子為使用Context-FL時(shí)的時(shí)間開銷情況,分母為未使用 Context-FL的時(shí)間開銷情況.可以看出,隨著程序規(guī)模的擴(kuò)大,由于采用動(dòng)態(tài)切片的原因,使用Context-FL的時(shí)間成本會(huì)有所增加.

Table 4 Comparison of experimental time cost (s)表4 實(shí)驗(yàn)時(shí)間開銷對(duì)比 (秒)

4.3 有效性威脅

本文實(shí)驗(yàn)有如下有效性威脅.

· 實(shí)驗(yàn)采用了JSlice的動(dòng)態(tài)切片工具.然而,由于切片技術(shù)與JSlice工具局限性,與系統(tǒng)庫(kù)相關(guān)的依賴無(wú)法提取.這時(shí),錯(cuò)誤語(yǔ)句很有可能不包含在切片結(jié)果中,如Tot_info的版本11.動(dòng)態(tài)切片技術(shù)的另一個(gè)缺點(diǎn)是對(duì)某些類型的錯(cuò)誤無(wú)法實(shí)施切片,例如,遺漏類型的錯(cuò)誤語(yǔ)句無(wú)法產(chǎn)生執(zhí)行信息,動(dòng)態(tài)切片無(wú)法切到該類型的錯(cuò)誤語(yǔ)句.這些缺點(diǎn)是由動(dòng)態(tài)切片技術(shù)自身特點(diǎn)所引起的.

· 實(shí)驗(yàn)有一個(gè)潛在假設(shè):當(dāng)一個(gè)失敗的測(cè)試用例運(yùn)行時(shí),錯(cuò)誤的語(yǔ)句應(yīng)該被執(zhí)行.這個(gè)假設(shè)通常成立,實(shí)驗(yàn)結(jié)果也證實(shí)了假設(shè)的合理性.然而在某些情況下,如程序中出現(xiàn)多重錯(cuò)誤時(shí),則假設(shè)可能不成立.但是對(duì)于單一錯(cuò)誤進(jìn)行研究是必要的,因?yàn)樗鼈兪菍?duì)多個(gè)錯(cuò)誤進(jìn)行定位的研究基礎(chǔ).這就是為什么大多數(shù)現(xiàn)有的研究集中在單一錯(cuò)誤情景的原因.

· 實(shí)驗(yàn)對(duì)象也是有效性威脅之一.實(shí)驗(yàn)選擇廣泛應(yīng)用于錯(cuò)誤定位領(lǐng)域的代表性程序.然而現(xiàn)實(shí)調(diào)試中存在許多未知因素,說(shuō)明它們不能覆蓋并適用于現(xiàn)實(shí)中的所有情況.因此,未來(lái)工作使用更多的真實(shí)大型程序?qū)?huì)是本文研究的重點(diǎn).

5 相關(guān)工作

有許多研究人員根據(jù)覆蓋信息或切片信息研究錯(cuò)誤定位技術(shù).本節(jié)簡(jiǎn)要介紹這些研究.更多的錯(cuò)誤定位工作可參考Wong等人近期發(fā)表的綜述[1].

基于覆蓋的錯(cuò)誤定位技術(shù)將程序譜數(shù)據(jù)從測(cè)試執(zhí)行轉(zhuǎn)換為程序?qū)嶓w的可疑值,并使用諸如基于程序譜的錯(cuò)誤定位(SFL)等統(tǒng)計(jì)公式對(duì)其進(jìn)行排序.當(dāng)使用這些技術(shù)時(shí),本文不需要知道程序的詳細(xì)信息,只需運(yùn)行通過(guò)和失敗的測(cè)試用例.Chen等人[29]提出了Jaccard技術(shù),這是一種統(tǒng)計(jì)錯(cuò)誤定位算法.Jones等人[30]提出了Tarantula技術(shù),計(jì)算每個(gè)語(yǔ)句的可疑值,并根據(jù)他們的可疑值進(jìn)行排名.Tarantula在后續(xù)研究中是廣泛使用和比較的技術(shù).Abreu等人[31]應(yīng)用Ochiai定位單一錯(cuò)誤.他們指出:他們的技術(shù)Ochiai一直優(yōu)于Tarantula,并且在EXAM得分方面平均提高了5%.Abreu等人[32]在后來(lái)的研究中評(píng)估了Tarantula的有效性以及其他技術(shù),并指出,Ochiai對(duì)測(cè)試用例進(jìn)行了最佳的評(píng)估.Wong等人[33]利用數(shù)據(jù)和控制流程,并提出了幾個(gè)指標(biāo),如Wong1-3,Wong3′.它們都是計(jì)算具有失敗測(cè)試用例的程序?qū)嶓w的可疑值的統(tǒng)計(jì)公式.雖然Wong等人[8]提出了一種基于代碼覆蓋的方法,可以通過(guò)測(cè)試執(zhí)行自動(dòng)調(diào)整可疑語(yǔ)句的權(quán)重,還提供了一些減少搜索域的方法.Wong等人[34,35]還提出了一種基于交叉表的方法,利用語(yǔ)句的覆蓋和執(zhí)行信息,并提出了一種名為 DStar(D*)的技術(shù).該方法計(jì)算了修改語(yǔ)句的可疑值.最近,Xie等人[14]在理論上研究了GP進(jìn)化公式.

程序切片算法(靜態(tài)和動(dòng)態(tài))的應(yīng)用也被許多研究人員廣泛研究用于程序調(diào)試.Lei等人[27,28]采用靜態(tài)切片對(duì)每個(gè)測(cè)試用例的輸出進(jìn)行切片,以此構(gòu)建輸入矩陣,并基于這個(gè)矩陣重新定義可疑值計(jì)算方法.本文方法僅對(duì)失敗測(cè)試用例的輸出進(jìn)行動(dòng)態(tài)切片,其針對(duì)性強(qiáng),避免了成功測(cè)試用例可能帶來(lái)的不確定影響.同時(shí),動(dòng)態(tài)切片體積小于靜態(tài)切片體積,搜索范圍更小.本文實(shí)驗(yàn)結(jié)果也表明,Context-FL優(yōu)于 Lei等人的方法.Zhang等人[36,37]研究了動(dòng)態(tài)切片在定位錯(cuò)誤中的有效性,并開發(fā)了一種采用動(dòng)態(tài)切片的策略,通過(guò)計(jì)算從0到1的置信度值,來(lái)識(shí)別可能影響輸出以產(chǎn)生不正確值的語(yǔ)句的子集.Zhang等人[38]還提出了一種類似切片的技術(shù),以便從許多事件中剪除不相關(guān)的事件.Jones等人[30]使用動(dòng)態(tài)切片和執(zhí)行切片來(lái)減少搜索域.Alves等人[39]將變化影響分析納入動(dòng)態(tài)切片,以進(jìn)一步優(yōu)化動(dòng)態(tài)切片.Wen等人[40]提出了利用混合切片譜的統(tǒng)計(jì)方法,以提高錯(cuò)誤定位的有效性.與這些方法不同,本文方法使用的是動(dòng)態(tài)切片,對(duì)程序的動(dòng)態(tài)執(zhí)行軌跡進(jìn)行了分析,顯示了如何捕獲動(dòng)態(tài)數(shù)據(jù)和控制依賴關(guān)系.Wong等人[41]提出了一種基于執(zhí)行切片和塊之間的數(shù)據(jù)依賴關(guān)系,在小范圍代碼內(nèi)實(shí)現(xiàn)高效準(zhǔn)確的錯(cuò)誤定位的方法.我們的方法與它不同.我們利用動(dòng)態(tài)切片來(lái)構(gòu)建語(yǔ)句的上下文關(guān)系.

偶然正確性(coincidental correctness)問(wèn)題是錯(cuò)誤定位研究的一個(gè)熱點(diǎn).當(dāng)測(cè)試用例執(zhí)行了錯(cuò)誤語(yǔ)句,卻并沒(méi)有導(dǎo)致程序失效時(shí),就產(chǎn)生了偶然正確性問(wèn)題.偶然正確性問(wèn)題存在于成功測(cè)試用例中,對(duì)錯(cuò)誤定位性能有負(fù)效應(yīng).為了解決偶然正確性問(wèn)題,如何識(shí)別存在偶然正確性問(wèn)題的成功測(cè)試用例成是關(guān)鍵.Wang等人[42]提出了上下文模型(context pattern),通過(guò)是否匹配上下文模型來(lái)識(shí)別存在偶然正確性問(wèn)題的成功測(cè)試用例,并以此優(yōu)化覆蓋矩陣,從而提升錯(cuò)誤定位性能.Masri等人[43]定義了基于缺陷的失效,以此描述具有偶然正確性問(wèn)題的成功測(cè)試用例,從而更有利于緩解偶然正確性問(wèn)題.隨后,Masri等人[44]對(duì)偶然正確性問(wèn)題進(jìn)一步研究,采用Euclidean標(biāo)準(zhǔn)度量出成功測(cè)試用例與失敗測(cè)試用例之間的相似度,以此移除具有偶然正確性問(wèn)題的成功測(cè)試用例.Miao等人[45]基于偶然正確性的成功測(cè)試用例與失敗測(cè)試用例有相似行為的思想,采用聚類方法對(duì)測(cè)試用例進(jìn)行分類.當(dāng)成功測(cè)試用例被劃分到包含失敗測(cè)試用例的類別時(shí),該成功測(cè)試用例存在偶然正確性問(wèn)題的可能性較大.Bandyopadhyay[46]基于成功測(cè)試用例與失敗測(cè)試用例之間執(zhí)行語(yǔ)句的相似度來(lái)定義權(quán)重,并以此預(yù)測(cè)可能具有偶然正確性問(wèn)題的成功測(cè)試用例,最后,根據(jù)預(yù)測(cè)來(lái)優(yōu)化錯(cuò)誤定位性能.Lei等人[47]系統(tǒng)分析和總結(jié)了測(cè)試用例集的錯(cuò)誤定位效能,從理論和實(shí)驗(yàn)證明了偶然正確性問(wèn)題是成功測(cè)試用例對(duì)錯(cuò)誤定位效能影響最大的因素.他們的研究還明確失敗測(cè)試用例對(duì)錯(cuò)誤定位效能具有正效應(yīng)作用.與成功測(cè)試用例的偶然正確性問(wèn)題相比,失敗測(cè)試用例的信息更加直接有效.因此,本文方法關(guān)注于失敗測(cè)試用例,通過(guò)動(dòng)態(tài)切片提取更精確信息,大幅度縮小錯(cuò)誤搜索范圍,以此為基礎(chǔ)來(lái)實(shí)現(xiàn)錯(cuò)誤定位性能提升,也印證了 Lei等人[47]對(duì)失敗測(cè)試用例的結(jié)論.雖然本文方法不關(guān)注優(yōu)化具有偶然正確性問(wèn)題的成功測(cè)試用例,且采用的動(dòng)態(tài)切片不能根除偶然正確性,但是通過(guò)動(dòng)態(tài)切片對(duì)失敗測(cè)試用例的優(yōu)化,大幅度縮小錯(cuò)誤搜索范圍,抑制了具有偶然正確性問(wèn)題的成功測(cè)試用例發(fā)揮負(fù)效應(yīng)的空間,間接地緩解了偶然正確性問(wèn)題.

6 結(jié) 論

本文提出了一種基于上下文的錯(cuò)誤定位方法 Context-FL.該方法結(jié)合動(dòng)態(tài)切片和可疑性度量方法,構(gòu)建可疑值標(biāo)記的上下文.實(shí)驗(yàn)結(jié)果表明,與5種典型定位方法對(duì)比,Context-FL顯著優(yōu)于這些方法,有效縮減了代碼檢查的范圍,大幅度提升了錯(cuò)誤定位性能.未來(lái)的工作包括方法優(yōu)化,以提高其準(zhǔn)確性.此外,我們還會(huì)研究將Context-FL擴(kuò)展到多錯(cuò)誤場(chǎng)景下的定位.