增強上下文的錯誤定位技術?

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

1(國防科技大學 計算機學院,湖南 長沙 410072)

2(重慶大學 大數據與軟件學院,重慶 400044)

3(信息物理社會可信服務計算教育部重點實驗室(重慶大學),重慶 400044)

4(上海第二工業大學 計算機與信息工程學院,上海 200127)

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

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

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

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

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

本文第 1節介紹基于頻譜的錯誤定位和動態切片.第 2節具體描述本文方法 Context-FL.第 3節給出Context-FL的實現.第4節描述實驗以及結果分析.第5節介紹相關工作.第6節總結本文.

1 相關背景

1.1 基于頻譜的錯誤定位

基于頻譜的錯誤定位技術(spectrum-based fault localization,簡稱SFL)意在構建程序譜,并使用可疑評估公式來衡量每個語句的可疑值.程序譜是數據的集合,包括語句執行覆蓋信息以及測試用例是否通過的信息,是程序動態行為的一種具體視圖[5].

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

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

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

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

Fig.1 Coverage ofMtest cases after executed圖1M個測試用例執行后的覆蓋信息

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

Table 2 Maximal formulas of SFL表2 最優SFL公式

SFL信息收集和工作原理比較簡單,并能準確定位錯誤語句,因而得到了廣泛的研究和應用.然而它并沒有給出執行程序的上下文信息,也沒有考慮到語句之間的依賴關系.其產生的語句排名列表沒有顯示語句之間依賴關系,有不少可疑性較高的語句與程序錯誤輸出并沒有關聯.這種語句孤立與割裂,加重了開發人員理解和搜索問題的難度.當程序規模大時,不相關的語句將迅速增加,這可能對軟件調試有很大的干擾.因此,需要構建與錯誤輸出相關聯的可疑上下文,以便更好地了解錯誤問題,并進一步減少手動查找范圍.

1.2 動態切片

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

動態切片標準可以表示為元組C=(Sk,V,I),其中,Sk表示語句變量為V的輸入I上的語句S的k次出現.如圖2所示,標準(n=91,v,2),其中,91表示第1次出現的語句9.由于輸入n=2,這表明該循環執行了2次,即v=5和v=6分別執行1次.因為通過在第2個循環中分配5到v而使第1個循環中的變量v的賦值發生位移,所以可以從動態切片中省略if語句的else分支.而標準(9,v)下的程序的靜態切片包括了整個程序.顯然,動態切片更有利于縮小查找范圍,且與具體執行相關,更具有針對性.

Fig.2 Examples of dynamic slice and static slice圖2 動態切片與靜態切片的例子

2 CONTEXT-FL算法設計

2.1 算法設計

Context-FL的基本思想是:將動態切片技術應用于 SFL,構建可疑上下文及其元素.Context-FL首先構建上下文,顯示語句在程序執行過程中如何影響和被影響;然后,利用SFL評估上下文中元素的可疑值.

算法1和算法2描述了Context-FL方法的關鍵部分.

算法1.Get suspicious context.

算法2.Get statements suspiciousness in the context.

首先對算法1和算法2進行解釋.本節采用第1節定義的程序P和測試用例套件T.即程序P由一組表示為{s1,s2,...,sm}的語句組成,相應的測試套件T={T1,T2,...,Tn}.Context{s1,s2,...,sn}表示與錯誤輸出相關的語句的集合.EnhancedContext{s1,s2,...,sn}表示帶可疑值標記的上下文語句的集合.接下來,將討論 Context-FL算法中的每個步驟.

· 步驟1:構建可疑片段和他們的元素.

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

· 步驟2:計算可疑片段中每個元素的可疑值.

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

· 步驟3:輸出錯誤定位結果.

此步驟將定制本地化結果輸出.該定位包含一個增強的上下文,其語句以SFL給出的可疑值降序排列.定位結果可以幫助開發人員了解和定位錯誤,將一些信息附加到每個語句上,如可疑值和行號.

2.2 例子演示

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

Fig.3 An example illustrating Context-FL圖3 Context-FL例子說明

為了解決這個問題,Context-FL通過使用切片標準(t1,s14,d1)來構建錯誤輸出的動態切片.該切片包括與失敗測試用例t1的輸出有直接關系的語句{s1,s3,s7,s14}.最后,GP02生成新的排名列表:{s7,s14,s3,s1},其中,s3被排在第3且{s8,s9,s12,s10,s11,s2,s13,s4,s6,s5,s15,s16}不包括在上下文中,因為它們與失敗測試用例t1和t6的錯誤輸出沒有關系.因此,Context-FL比原來的GP02更有效.

3 CONTEXT-FL實現框架

3.1 實現框架

本節將詳細介紹錯誤定位方法Context-FL的實現框架.如圖4所示,Context-FL主要架構由3個主要功能模塊組成,分別是程序信息提取模塊、可疑上下文生成模塊、可疑計算模塊.

程序信息提取模塊的主要功能是在執行測試用例后提取程序覆蓋信息.第 1個不可或缺的步驟是程序插樁,其目的是捕獲程序的運行信息.插樁點的選擇由錯誤定位方法確定.因為收集足夠的和非冗余的信息非常重要,所以需要采用適當的插樁技術,以此控制插樁的代碼量,并且不會產生大量的冗余信息引起干擾.第2步是收集數據.因為在插樁之后,程序會產生大量的運行信息,必須以適當的方式收集數據進行抽象和恢復,以便于下一步的分析和計算工作.由于數據量相對較大,需要對數據進行簡化.接下來是對每個測試用例生成的數據進行分類,使得所需數據以統一的方式存儲.最后生成SFL計算的矩陣信息文件.由于軟件的復雜性和規模日益增加,程序的運行數據顯著增加.雖然采取了各種措施來壓縮或減少在收集階段收集的數據量,但需要分析的數據量仍然很大.因此,有效的數據分析方法是絕對必要的.程序切片信息、狀態信息和統計信息是分析的 3個主要數據表現形式.Context-FL使用統計信息來查找與錯誤相關聯的位置,這種類型的信息是通過分析程序的統計數據和提取特定模型來生成的.該方法通常使用語句、分支、預測信息、基本塊和功能等程序覆蓋信息,比較失敗測試用例和成功測試用例并分析其差異性.最后,在不同要素之間的聯系的基礎上,產生了可疑值.

Fig.4 Architecture of Context-FL圖4 Context-FL框架結構

可疑上下文生成模塊的主要功能是找到與錯誤語句相關聯的一組語句片段,該片段包含了錯誤語句且又大幅小于源代碼量.其目的是通過縮小搜索范圍來提高錯誤定位的效率.程序切片技術是一種分解技術,根據具體計算提取相關語句.它可以分析元素之間的依賴關系并縮小搜索范圍.與其他可疑上下文提取技術相比,程序切片提供了一種有效的方法來了解程序執行是否影響輸出.根據第 1.2節切片技術的分析,本框架采用動態切片技術提取可疑片段.雖然切片技術在語句關聯分析中具有很強的能力,但是由于程序切片生成的可疑上下文中的語句不能區分,因此這些語句的可疑值是相同的.由于目前軟件的規模不斷擴大,所以片段的規模將會大為增加.如果只從片段中找出錯誤的位置,效率會很低,效果也會大為降低.可疑計算模塊的主要功能是根據可疑環境,按照可疑值的大小順序對片段中的語句進行排序.

受SFL技術的啟發,當語句的執行影響了失敗的測試用例的輸出時,語句的可疑值會增加.另一方面,如果程序語句的執行影響成功測試用例的輸出,則其可疑值會降低.因此,可疑計算模塊定義了新的統計變量.

3.2 Context-FL使用的工具

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

如圖5所示,88行的深色表示在執行測試用例時沒有執行該行,83行和92行的淺色表示該行只有一部分被執行,其余標深色的行完全被執行.本文過濾覆蓋信息并擺脫其他不相關的信息.由于大型程序的文件數量眾多,因此需要根據測試用例的順序對覆蓋信息文件進行重新編號、分類和存儲.在運行所有測試用例之后,覆蓋信息文件以矩陣的形式進行存儲,如圖1所示.

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

Fig.5 EMMA coverage report圖5 EMMA覆蓋報告

4 實 驗

4.1 實驗設計

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

Table 3 Subject programs表3 實驗對象

表中前10個程序[24]原本包含102個錯誤版本.實驗沒有采用schedule 1的版本1、schedule 2的版本2、版本4、版本9、版本10、版本12、版本14和Tot_info的版本4、版本10、版本12、版本14.因為它們沒有失敗的測試用例,至少有 1個失敗的測試用例是執行動態切片所必需的.實驗還排除了執行動態切片失敗的Tot_ info的版本11,以及錯誤語句在依賴庫中的版本19.對于Jtcas,實驗使用了14個代表性的錯誤.后3個程序選自Defect4J[25],Defect4J是一個真實錯誤的數據集.在Defect4J中,實驗選取了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個單錯誤版本的18個.其他錯誤版本沒有被采用的原因:一是本文研究主要是針對單錯誤,而其他版本為多錯誤;二是沒有編譯運行成功.因此如表3所示,實驗最終采用了129個錯誤版本.

4.2 結果分析

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

由于對比方法較多,圖6將以分組的方式來更好地顯示 Context-FL和對比方法的 Acc值.對于每個子圖——圖6(a)和圖6(b),橫坐標表示在所有程序中檢查的可執行語句的百分比.縱坐標表示定位方法找出錯誤的比例.圖6中的每一個點表示在檢查可執行語句的百分比時,定位到的錯誤的百分比.

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

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

由于對比方法較多,圖7也分為圖7(a)和圖7(b)兩個子圖,顯示了Context-FL在每個程序上的 RImp值.采用Context-FL方法后,需要檢查的語句數明顯減少,從Nanoxml_v3的GP03的20.22%(最優值)到chart的D*的88.63%(最差值).這意味著Context-FL只需要檢查SFL所需檢查的執行語句數的20.22%～88.63%,就能定位到錯誤.從圖7(a)和圖7(b)可以發現,Context-FL更加有效和穩定,特別是當程序規模大時效果則更為顯著.

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

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

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

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

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

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

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

表4描述了這些實驗程序的時間開銷的對比情況.表中數據的分子為使用Context-FL時的時間開銷情況,分母為未使用 Context-FL的時間開銷情況.可以看出,隨著程序規模的擴大,由于采用動態切片的原因,使用Context-FL的時間成本會有所增加.

Table 4 Comparison of experimental time cost (s)表4 實驗時間開銷對比 (秒)

4.3 有效性威脅

本文實驗有如下有效性威脅.

· 實驗采用了JSlice的動態切片工具.然而,由于切片技術與JSlice工具局限性,與系統庫相關的依賴無法提取.這時,錯誤語句很有可能不包含在切片結果中,如Tot_info的版本11.動態切片技術的另一個缺點是對某些類型的錯誤無法實施切片,例如,遺漏類型的錯誤語句無法產生執行信息,動態切片無法切到該類型的錯誤語句.這些缺點是由動態切片技術自身特點所引起的.

· 實驗有一個潛在假設:當一個失敗的測試用例運行時,錯誤的語句應該被執行.這個假設通常成立,實驗結果也證實了假設的合理性.然而在某些情況下,如程序中出現多重錯誤時,則假設可能不成立.但是對于單一錯誤進行研究是必要的,因為它們是對多個錯誤進行定位的研究基礎.這就是為什么大多數現有的研究集中在單一錯誤情景的原因.

· 實驗對象也是有效性威脅之一.實驗選擇廣泛應用于錯誤定位領域的代表性程序.然而現實調試中存在許多未知因素,說明它們不能覆蓋并適用于現實中的所有情況.因此,未來工作使用更多的真實大型程序將會是本文研究的重點.

5 相關工作

有許多研究人員根據覆蓋信息或切片信息研究錯誤定位技術.本節簡要介紹這些研究.更多的錯誤定位工作可參考Wong等人近期發表的綜述[1].

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

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

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

6 結 論

本文提出了一種基于上下文的錯誤定位方法 Context-FL.該方法結合動態切片和可疑性度量方法,構建可疑值標記的上下文.實驗結果表明,與5種典型定位方法對比,Context-FL顯著優于這些方法,有效縮減了代碼檢查的范圍,大幅度提升了錯誤定位性能.未來的工作包括方法優化,以提高其準確性.此外,我們還會研究將Context-FL擴展到多錯誤場景下的定位.