一種提高錯誤定位效率的測試用例選擇方法

付文豪,　虞慧群,　范貴生

(華東理工大學計算機科學與工程系,上海 200237)

?

一種提高錯誤定位效率的測試用例選擇方法

付文豪,虞慧群,范貴生

(華東理工大學計算機科學與工程系,上海 200237)

為提高錯誤定位的效率,提出了多種測試用例約簡與選擇的方法,然而,過度的約簡與不適的選擇造成了部分測試信息丟失,引起了錯誤定位有效性的損失。本文提出了一種相似測試用例選擇方法,用以約簡測試集。該方法能消除偶然測試用例對錯誤定位準確性造成的偏差,通過為每個失敗測試用例選擇執行軌跡與其相似的成功測試用例的方式,最大限度地保留測試的全部信息;基于選擇出的測試用例信息,利用已有的錯誤定位方法輸出程序語句的可疑值列表。以Siemens程序集作為實驗對象,證明了本文測試用例選擇方法能顯著提高錯誤定位的有效性。

調試; 錯誤定位; 測試用例選擇; 相似測試用例

為了節省軟件調試的開銷,研究人員提出了許多軟件錯誤自動定位的方法。這些方法利用軟件測試過程的測試用例產生的結果和執行信息,分析程序的異常并提供一組程序的可疑代碼供開發人員進一步檢測,以便快速發現軟件的缺陷。然而定位中所使用的測試用例及其執行信息直接影響了此類方法的有效性,因此如何選擇合適的測試用例集合成為錯誤定位的一個關鍵問題。為了減少錯誤定位的開銷并達到更好的錯誤定位效率,研究人員提出了多種測試用例約簡的方法,并進一步研究了測試用例約簡與錯誤定位有效性之間的關系。

Abreu等[1]研究了錯誤定位的效率與選擇的測試用例數量之間的關系。Baudry等[2]驗證了測試用例集的改變可以提高錯誤定位的準確性。Graves等[3]對多種測試用例選擇方法進行了實驗研究,并分析了它們的開銷與提高的效率。Harrold等[4]提出了一個減少測試用例規模的啟發式的算法HGS。Chen等[5]進一步規范了測試用例的約簡問題并提出了兩個啟發式的約簡算法。Hao等[6]假設相似的或冗余的測試用例會降低錯誤定位的有效性,并基于已有的錯誤定位方法,提出了3種測試用例約簡的策略。Hsu等[7]提出了一個測試集最小化框架,這個框架允許測試人員處理涉及多種測試準則的問題,并基于線性規劃計算出一個最優的解決方案。而Yu等[9]基于4種覆蓋分析方法,通過一系列的實驗,進一步研究了測試用例約簡方法對錯誤定位有效性的影響。

不同于已有的測試用例選擇或約簡的方法,本文單獨考慮失敗測試用例集中的每種可能的執行軌跡,從成功測試用例集中選取執行軌跡與失敗測試用例相似的測試用例,約簡那些執行軌跡與相應的失敗測試用例執行軌跡具有較大差異的測試用例,利用選擇出的測試用例集和現有的錯誤定位的方法,計算程序中代碼的可疑度值,并產生一個供開發人員檢測的代碼序列。以西門子程序集為實驗對象進行了研究,結果表明,該方法能顯著地提高錯誤定位的有效性,同時發現,錯誤定位的有效性會隨著相似比例的變化呈現規律性地變化。

1　基于語句的相似測試用例選擇方法

1.1基于語句的相似測試用例選擇方法框架

相似測試用例選擇的主要目標是為每個失敗測試用例單獨地挑選與其相似的成功用例,然后利用現有的錯誤定位方法計算每條語句的可疑度值。該方法基于兩個思路:

(1) 對于單個錯誤的程序而言,每一個失敗的測試用例均執行了錯誤語句;

(2) 與失敗測試用例的執行軌跡相似的成功測試用例,其對錯誤的貢獻最大。

這是因為相似的成功測試用例的執行軌跡僅在某些代碼部分與失敗測試用例存在差異,且若這些差異語句僅被包含在失敗測試用例的執行軌跡中,那么這些語句出錯的可能性更高。為每個失敗的測試用例選擇與其執行軌跡相似的成功測試用例,最終構成該失敗測試用例的相似測試用例集,用這個相似測試集可以更準確地確定出錯語句。

圖1示出了測試用例選擇方法的基本框架。該框架包括3個階段:測試用例約簡階段、相似測試用例選擇階段和語句排序計算階段。整個方法的輸入包含一個單個錯誤的程序以及一組測試套件,使用程序的執行結果和執行過程中收集的語句覆蓋信息,利用現有的錯誤定位的方法,輸出程序中所有可執行語句的可疑度列表。在測試用例約簡階段,通過提取程序中的高可疑語句,排除了測試集中的偶然成功測試用例。在測試用例選擇階段,一個測試用例被選擇,當且僅當其執行軌跡與對應的失敗測試用例的軌跡相似度達到一定值時,每一個失敗測試用例的相似測試用例集被選擇并產生。在語句排序計算階段,語句的最終可疑度值通過給定的錯誤定位方法與每一個相似測試用例集中的頻譜信息計算得出。

1.2測試用例約簡

測試用例約簡階段的主要目的是將一部分偶然成功測試用例從原有的成功測試集中刪除,得到一個優化的新成功測試用例集。對于單個錯誤的程序而言,成功測試用例中也可能執行了錯誤語句,這類成功測試用例被歸為偶然成功測試用例。偶然成功測試用例是指那些執行了錯誤語句但卻得到正確結果的測試用例。由于本文方法利用失敗測試用例與成功測試用例之間的軌跡差異來指導錯誤定位,若選擇了偶然成功測試用例,那么它的執行軌跡將使得某些語句的頻譜發生變化,最終必然會影響語句的可疑度值排序,直接影響錯誤定位的準確性,因此消除這類成功測試用例是該方法中一個重要的階段。在包含單個錯誤的程序中,每個失敗測試用例必然包含了錯誤語句,因此,被所有失敗測試用例執行過的語句必然具有較高出錯的可能性,定義為高可疑語句(HSS)。由于程序錯誤語句未知,偶然成功測試用例無法完全確定,但可以肯定的是,包含所有HSS的成功測試用例必然為偶然成功測試用例。

根據測試用例的執行結果,原有的測試套件可以分為失敗測試集合FT={f1,f2,…,fx}和成功測試集合PT= {p1,p2,…,py},測試用例t的執行軌跡可以表示為et(t)={s1,s2,…,sn},其中n表示程序P中可執行語句的數目。

(1)

如前所述,由于錯誤語句是未知的,所以我們定義包含所有高可疑語句(HSS)的成功測試用例為偶然成功測試用例。因此需要從所有失敗測試用例中提取出HHS。如果語句被所有失敗測試用例覆蓋,即在所有失敗測試用例的執行軌跡et中,si=1或si=0 (1≤i≤n)分別表示語句為高可疑語句或普通語句,那么高可疑語句可以表示為

圖1　基于語句的測試用例選擇方法Fig.1　Statement-based test suite selection approach

(2)

在確定高可疑語句之后,需逐一檢測PT中的偶然成功測試用例。依據之前的定義,若HSS ?et(pj) (1 ≤j≤y),即意味著測試用例pj的執行軌跡中包含了所有的高可疑語句,那么測試用例pj被認為是偶然成功測試用例,需從原PT中將其刪除。遍歷PT中的所有測試用例,直到將所有此類偶然成功測試用例刪除,得到新的成功測試集NPT。

1.3測試用例選擇

測試用例選擇階段的主要目標是為每個失敗測試用例選擇與其執行軌跡最為相近的成功測試用例,得到僅包含該失敗測試用例和若干成功測試用例的相似用例集。定義一個相似比例(Similar Proportion,SP)作為選擇的標準。相似比例表示了兩個測試用例共同執行的語句占待檢測語句的比例。給定兩個測試用例f和p,其執行軌跡分別為et(f)= {a1,a2,…,an} 和et(p) = {b1,b2,…,bm},定義E={e1,e2,…,en}為一個一維數組,對于ek∈E,

(3)

(4)

在測試用例選擇階段,給定一個失敗用例,當且僅當成功測試用例與其相似比例滿足SP(pj|fi) ≥θ(1≤j≤y,1≤l≤x)時,該成功測試用例才能被選擇。θ為給定閾值,表示了選擇標準需達到的最小值,θ在0與1之間。根據式(4)的要求,最終得到每個失敗測試用例的相似測試用例集。在相似測試用例集中僅包含一個失敗測試用例和若干個與該失敗測試用例執行軌跡相似的成功測試用例。

1.4語句排序

語句排序階段的主要目標是利用現有的錯誤定位技術(如Tarantula[10]方法等)與選擇產生的相似測試集,計算得出每條語句的最終可疑值,并按照從高到底的順序輸出。該階段主要分為兩個部分:可疑值分組計算和組合調整。在計算語句可疑值時,應利用每個相似測試集中的語句頻譜信息,計算出語句的可疑值,最終,對所有組計算的結果進行調整,得到語句最終的可疑值。

以Tarantula 方法為例,各組中語句的可疑值計算見式(5)。

(5)

其中:suspi(s)表示語句s由測試用例fi與其相似測試集計算得出的可疑度值;tp(s)表示相似測試集中覆蓋了語句s的成功測試用例數量;tp表示該相似測試集中的成功測試用例總數量。

根據式(5)計算出程序語句在每個相似測試集中的可疑度值,對各組中的語句可疑度值進行統計分析,得到語句的最終可疑度值,見式(6)。

(6)

其中:score(s)表示語句s最終的可疑度值;x表示失敗測試用例的數量,即相似測試集的數量。基于所有語句的最終可疑度值,本文方法最終提供了程序語句的可疑度值的排序列表。

2　實驗研究與分析

2.1評測標準

錯誤定位的有效性可以定義為當檢測到錯誤語句時,已檢測的語句(或未被檢測的語句)占待檢測的總語句的百分比,這個標準被定義為Expense。但為了進一步驗證測試用例選擇方法對錯誤定位有效性的影響,本文定義了一個評價標準ExpenseDecrease。

ExpenseDecrease=

(7)

ExpenseDecrease表示錯誤定位方法在應用原有測試用例與選擇出的測試用例上的效率的差值,若ExpenseDecrease的值為正,表明測試用例選擇的方法提高了錯誤定位的效率; 若為負值,則表明該方法使得錯誤定位的效率降低。使用ExpenseDecrease衡量測試用例選擇方法對錯誤定位有效性的影響,可以規范不同規模程序的錯誤定位有效性的判定。

2.2實驗結果與分析

為了評估測試用例選擇方法對錯誤定位有效性的影響,本文設計并實施了一系列實驗來解決以下兩個問題:

(1) 相似測試用例選擇的方法是否能提高錯誤定位的有效性？

(2) 在實驗中,測試用例選擇的標準θ值的改變,會對錯誤定位的有效性產生怎么樣的影響？

本文選擇Siemens程序集作為實驗對象。Siemens程序包含7組實現不同功能的C程序,每組程序通過人工注入的方式創建了132個不同的錯誤版本,每個版本中包含1個錯誤。Siemens程序集被廣泛地應用于錯誤定位方法的研究中,排除不可用版本,實驗中僅用了123個版本。在用測試用例選擇方法之前,需要完成一些基本實驗來獲取測試用例的執行結果及軌跡信息。依據測試用例的執行結果,將測試用例劃分為成功測試集和失敗測試集。為了使實驗結果更具有說服性,選取了3種被普遍研究的錯誤定位技術:Tarantula、Ochiai[11]、Naish[12]。

圖2 (a)示出了采用Tarantula方法,錯誤定位的效率在原有測試集和本文方法(θ為0.50,0.60,0.70,0.80)上的比較結果。圖中橫坐標表示當定位出錯誤時已檢測的語句占程序總語句的比例,縱坐標表示已檢測出的程序版本占錯誤總版本數的比例。被檢測的語句所占的比例越低,表示錯誤定位的效率越高。將本文方法中的θ取不同值時,相應的相似選擇方法定義為S(θ) (θ=0.50,0.60,0.70,0.80)。從圖2(a)中可以看出,利用測試用例選擇的方法進行錯誤定位的效率比使用原有測試用例集的效率要好。在同一程序中,當檢測相同比例的程序語句時,使用測試用例選擇方法能定位出更多的錯誤版本。例如,當少于10%的語句被檢測時,能確定錯誤語句的錯誤版本所占的比例依次為53.28%、 54.1%、 63.12% 、66.39%,高于使用原測試集時的效率(40.98%)。當檢測更多比例的錯誤語句時,這一趨勢保持不變。得出這樣一個簡單的結論:在相似測試用例選擇的方法中,隨著相似比例的增大,錯誤定位的有效性也不斷提高。此外,當θ≥0.85時,某些程序錯誤版本無法為失敗的測試用例選擇出達到條件的相似成功測試用例。對于進行選擇操作的其他錯誤程序,錯誤定位的效率仍然得到了大幅的提高,如圖2(b)所示。

Yu等[9]研究了使用了10種基于語句的測試用例約簡方法(SA)時Tarantula方法的效率,Gong等[8]也使用Tarantula方法對他們提出的測試用例約簡方法(CRV+PRV)進行了研究。為了進一步比較方法的有效性,對實驗數據進行了對比,見表1。在表1中,我們發現,SA方法的ExpenseDecrease值均為負,由此表明,SA約簡策略降低了錯誤定位方法的效率;CRV+PRV方法的ExpenseDecrease均為正值,但普遍偏小,說明錯誤定位的效率提高不明顯; 而使用本文方法,不管θ取何值,計算得出的ExpenseDecrease值均為正,且數值偏大,錯誤定位的效率提高明顯。ExpenseDecrease值的變化趨勢也證明了θ值影響錯誤定位效率的結論。

圖2　使用被選擇的測試用例與原測試集時Tarantula方法的錯誤定位效率Fig.2　Comparison of Tarantula between selected test suite and unselected test suite 表1　利用Tarantula方法,各測試用例約簡方法的平均ExpenseDecrease值 Table 1　Mean ExpenseDecrease using Tarantula on test suite selection

ProgramExpenseDecreaseS(0.50)S(0.60)S(0.70)S(0.80)CRV+PRVSAprint_tokens9.0709.0709.0709.0702.077-4.93print_tokens28.7098.4088.4089.0091.723-4.60replace2.5912.7333.1332.68231.172-4.76schedule3.7533.7533.7533.6145.022-8.81schedule23.3010.92516.91826.1693.322-6.08tcas1.4472.64610.41710.4170.921-6.85totinfo10.26710.73111.99612.0380.614-4.90Average5.5926.8969.099310.4292.122-5.85

本文還使用Ochiai和Naish方法對測試用例選擇方法進行了實驗研究。圖3 示出了語句檢測率與錯誤版本定位率之間的關系圖。結果表明,使用測試用例選擇方法,Ochiai和Naish方法得出的錯誤定位的有效性得以提高,并且當θ達到可取的最大值時,錯誤定位的效率也是最高的。這一結果與Tarantula方法計算出的結果保持一致。表2和表3分別給出了利用Ochiai和Naish方法,結合測試用例約簡方法計算出的錯誤定位有效性的變化值。表中的數據表明了本文提出的相似測試用例選擇方法提高了錯誤定位的有效性。在表中,“replace”程序的錯誤定位效率有少許降低,但從程序總體看,錯誤定位的有效性得到了明顯的提高。

圖3　使用測試用例選擇方法與原測試集時,Ochiai和Naish的錯誤定位效率Fig.3　Comparison of Ochiai and Naish between selected test suite and unselected test suite

3　結束語

本文提出了一種相似測試用例選擇的方法用以提高錯誤定位的有效性。該方法的主要思想是為每一個失敗測試用例選擇與其執行軌跡最為相似的成功測試用例,利用選擇出的相似測試用例及其執行軌跡信息,用現有的錯誤定位方法計算出語句的最終可疑度值,輸出最終的語句可疑值列表。對待選擇的成功測試集中的偶然成功測試用例進行了排除操作,提高了本文方法在錯誤定位上的準確性。最終,Siemens程序集上的實驗研究證明了相似測試用例選擇的方法能提高錯誤定位的有效性,并且,隨著相似比例的提高,錯誤定位的有效性提高更為明顯。

表2　Ochiai方法的平均

表3　Naish方法的平均

本文突出考慮每一種失敗執行軌跡,對于單個錯誤的程序而言,每一個失敗測試用例必然執行了錯誤語句,因此,失敗測試用例對錯誤定位的貢獻最大,通過分析比較與失敗測試用例的執行信息相似的成功測試用例,將差異語句突顯出來,成為了提高錯誤定位有效性的關鍵。在未來的工作中,我們將進一步研究基于其他粒度(分支,方法等)的測試用例的約簡策略。本文的研究重點關注在小規模單錯誤的程序上,未來將考慮大規模多錯誤的程序中測試用例選擇方法的研究。

[1]ABREU R,ZOETEWEIJ P,VAN GEMUND A J C.On the accuracy of spectrum-based fault localization[C]//Testing:Academic and Industrial Conference Practice and Research Techniques,MUTATION 2007.Windsor:IEEE,2007:89-98.

[2]BAUDRY B,FLEUREY F,TRAONY LE.Improving test suites for efficient fault localization[C]//Proceedings of the 28th International Conference on Software Engineering.Shanghai:ACM,2006:82-91.

[3]GRAVES T L,HARROLD M J,KIM J M,etal.An empirical study of regression test selection techniques[J].ACM Transactions on Software Engineering and Methodology (TOSEM),2001,10(2):184-208.

[4]HARROLD M J,GUPTA R,SOFFA M L.A methodology for controlling the size of a test suite[J].ACM Transactions on Software Engineering and Methodology (TOSEM),1993,2(3):270-285.

[5]CHEN T Y,LAU M F.A new heuristic for test suite reduction[J].Information and Software Technology,1998,40(5):347-354.

[6]HAO Dan,XIE Tao,ZHANG Lu,etal.Test input reduction for result inspection to facilitate fault localization[J].Automated Software Engineering,2010,17(1):5-31.

[7]HSU H Y,ORSO A.MINTS:A general framework and tool for supporting test-suite minimization[C]//IEEE 31st International Conference on Software Engineering.USA:IEEE,2009:419-429.

[8]DANDAN G,TIANTIAN W,XIAOHONGS,etal.A test-suite reduction approach to improving fault-localization effectiveness[J].Computer Languages,Systems & Structures,2013,39(3):95-108.

[9]YU YANBIN,JONES J A,HARROLD M J.An empirical study of the effects of test-suite reduction on fault localization[C]//Proceedings of the 30th International Conference on Software Engineering.Leipzig,Germany:ACM,2008:201-210.

[10]JONES J A,HARROLD M J,STASKO J.Visualization of test information to assist fault localization[C]//Proceedings of the 24th International Conference on Software Engineering.New York:ACM,2002:467-477.

[11]CAMPOS J,ABREU R.Leveraging a constraint solver for minimizing test suites[C]//2013 13th International Conference on Quality Software (QSIC).Nanjing:IEEE,2013:253-259.

[12]LEE NAISH,LEE H J,RAMAMOHANARAO K.A model for spectra-based software diagnosis[J].ACM Transactions on Software Engineering and Methodology (TOSEM),2011,20(3):11.

A Test Suite Selection Approach to Improving the Effectiveness of Fault Localization

FU Wen-hao,YU Hui-qun,FAN Gui-sheng

(Department of Computer Science and Engineering,East China University of Science and Technology,Shanghai 200237,China)

In order to improve the effectiveness of fault localization,various test suite reduction and selection methods have been proposed in recent years.However,excessive reduction or improper selection on test cases may result in the loss of some testing information and affect the fault localization.In this paper,a new test suite selection approach is proposed to improve spectrum-based fault localization (SFL).The proposed approach can eliminate the deviation in the accuracy of fault localization caused by coincidental passed test cases.By selecting similar test cases for each failed test case from the past test set,testing information is retained as more as possible.Besides,a ranking list is constructed by using an SFL technique with the new spectra.Finally,it is shown via experimental results on Siemens programs that the proposed approach can improve fault-localization effectiveness significantly.

debugging; fault localization; test suite selection; similar test case

1006-3080(2016)04-0557-06

10.14135/j.cnki.1006-3080.2016.04.018

2015-11-06

付文豪(1990-),女,博士生,主要研究方向為軟件調試、錯誤定位等。E-mail:whfu2012@163.com

通信聯系人：虞慧群,E-mail:yhq@ecust.edu.cn

TP312

A