基于偶然性正確測試用例發(fā)現(xiàn)的錯誤定位方法

馮潞潞，丁佐華

浙江理工大學(xué) 科學(xué)計(jì)算與軟件工程中心，杭州 310018

1 引言

基于程序譜的軟件錯誤定位方法（CFL）是通過統(tǒng)計(jì)分析程序運(yùn)行時對代碼行的覆蓋信息以及測試用例運(yùn)行結(jié)果數(shù)據(jù)來進(jìn)行軟件錯誤定位的方法。盡管CFL方法提出比較早，但是最近的研究[1]表明，CFL方法在多錯誤情況下依然有著良好的定位效果。因此，如何能提升CFL的定位效果是很有意義的。

當(dāng)某一個測試用例運(yùn)行到了錯誤行，但是其結(jié)果是pass（與標(biāo)準(zhǔn)程序輸出相同）時，稱這個測試用例為偶然性正確（coincidental correctness）測試用例。很多文獻(xiàn)[2-6]的研究都證明了偶然性正確測試用例對CFL有著嚴(yán)重的影響，并且在其文章中都提出了一些判斷偶然性正確的方法以及對懷疑度計(jì)算公式的修正方法。但是目前的判定偶然性正確測試用例的方法都有一定的局限性，比如誤判率（false positive）很高，對于CFL方法的定位效果不一定有提升，或者不具有普遍性，復(fù)雜度高。

因此本文針對CFL方法中的“偶然性正確”這個現(xiàn)象進(jìn)行了研究，發(fā)現(xiàn)了一種誤判率為0的偶然性正確測試用例的判定方法，并且改進(jìn)了文獻(xiàn)[6]中基于偶然性正確測試用例的軟件錯誤定位方法，最后通過實(shí)驗(yàn)驗(yàn)證了方法確實(shí)可以改進(jìn)CFL定位效果。

2 基本概念介紹

2.1 經(jīng)典的基于譜的錯誤定位方法介紹

盡管CFL方法有很多[7-10]，但是文獻(xiàn)[11-13]說明效果比較好的CFL方法有Tarantula[7]和Ochiai[8]等，在文獻(xiàn)[1]中也特別說明了這兩種方法，并且使用了Ochiai方法做CFL多錯誤效果實(shí)驗(yàn)分析。

這兩種方法的定義分別為：

其中符號含義如下：passed(s)：通過第s行結(jié)果為pass的用例總數(shù)；fail(s)：通過第s行結(jié)果為fail的用例總數(shù)；totalfailed：結(jié)果為fail的測試用例的總數(shù)；totalpassed：結(jié)果為pass的用例總數(shù)。

使用這兩種方法的計(jì)算結(jié)果見圖1。

圖1 Tarantula和Ochiai方法計(jì)算實(shí)例

圖1示例子中有6個測試用例，圖中的黑點(diǎn)表示這一行被對應(yīng)的測試用例運(yùn)行時所覆蓋了?？崭駝t表示這一行在測試用例運(yùn)行時沒有被覆蓋。最后T_suspiciousness和O_suspiciousness分別為用Tarantula方法和Ochiai方法所計(jì)算出來的懷疑度值。Rank為懷疑度從大到小的排序，懷疑度越高則rank值越小。排序之后從rank值為1的行開始檢查代碼看是否出錯，直到找到錯誤行為止。在找到錯誤行之前所檢查代碼的百分比，即定義為score值，用來評判錯誤定位方法的好壞程度。從本例中可以看到，使用這兩種方法所標(biāo)記的rank值為1的行正好為錯誤代碼行。

2.2 研究動機(jī)

在本文第一章中有介紹：當(dāng)某一個測試用例運(yùn)行到了錯誤行，但其結(jié)果為pass的時候，這一次測試被稱為偶然性正確。

經(jīng)典的CFL方法的提出是基于2個假設(shè)：

假設(shè)1：通過某一行，fail數(shù)量越多，那么這一行出錯的概率越高。

假設(shè)2：通過某一行，pass數(shù)量越多，那么這一行出錯的概率越小。

顯然，若每次運(yùn)行到錯誤行，測試結(jié)果都是FAIL，那么以上假設(shè)就可以很好地幫助定位錯誤行。而偶然性正確例子的存在卻使得以上的假設(shè)可靠性降低。偶然性正確對于CFL方法的影響在相關(guān)研究中也有說明[6]。

經(jīng)過觀察研究發(fā)現(xiàn)，在很多情況下，會出現(xiàn)同一種覆蓋軌跡（比如例子中的t1和t6，均覆蓋了1，2，3，4，6，7，13行），有些測試用例的結(jié)果是pass（如t1），但是有的會是fail（如t5）。這種情況下很明顯t1的pass是偶然性正確。圖1例子中，當(dāng)偶然性正確這一列（t1）結(jié)果設(shè)置為fail時，錯誤語句的懷疑度就可以提升為1，盡管此例中懷疑度順序沒有發(fā)生變化（因?yàn)殄e誤行已經(jīng)被準(zhǔn)確定位），但是提升了錯誤行的懷疑度，顯然有助于更好地來定位錯誤行。

3 本文方法

3.1 判定偶然性正確測試用例

基于2.2中的分析，本文提出了一種判定方法：

判定1：當(dāng)N次測試軌跡相同時，若其中有一次運(yùn)行失敗，則這N次測試中運(yùn)行結(jié)果為pass的測試用例為偶然性正確（MYCC）。

由偶然性正確的定義知道，判定偶然性正確測試用例有兩個條件：第一是其測試結(jié)果為pass；第二是其運(yùn)行時覆蓋了錯誤代碼行。對于某一種運(yùn)行軌跡，若其結(jié)果為fail，那么它一定運(yùn)行到了錯誤代碼行。那么當(dāng)另一次測試中，產(chǎn)生了相同的軌跡，但是測試結(jié)果為pass的時候，那么這次測試很明顯滿足了偶然性正確測試用例所需的兩個條件?？梢詤⒖紙D1中t1和t5的軌跡。

因此，判定1是合理的，而且這樣的判定是沒有誤判率的。

接下來需要說明這種情況的普遍性。例如，當(dāng)某些錯誤僅僅引起了數(shù)值上的錯誤，卻并沒有影響到邏輯上的變化，則運(yùn)行到錯誤行在某些情況下會出錯，但是路徑卻不會發(fā)生改變（如表1中例1所示）；或者在循環(huán)時，若循環(huán)條件出錯，那么沒有運(yùn)行到邊界值則結(jié)果不會出錯，但是這些成功的測試用例確實(shí)運(yùn)行到了錯誤行（如表2中例2所示）。

表1和表2的測試用例部分，覆蓋信息都是針對錯誤程序的，1表示覆蓋了這一行，0表示沒有覆蓋這一行。以上的2個例子均說明了判定1的存在性。

表1 偶然性正確示例一

表2 偶然性正確示例二

基于以上的分析知，在成功的測試用例中，尋找軌跡與某條失敗測試用例相同的測試用例，即為本文所判定的MYCC。下面給出判定MYCC的基本算法：

其中fail_trace_file為所有測試中運(yùn)行失敗時的程序的語句覆蓋軌跡文件，pass_trace_file為測試中所有運(yùn)行成功時程序的語句覆蓋的軌跡文件。

3.2 基于偶然性正確對CFL的改進(jìn)方法1

接下來要說明的是，在得到MYCC之后，要如何使用它才可以改進(jìn)已有CFL方法的定位效果。

在3.1節(jié)的分析中給出了一種很直觀的修正方法，就是將偶然性正確測試用例作為失敗的測試用例使用。具體的操作為將MYCC的測試結(jié)果人為地設(shè)置為fail。這么做的原因是，CFL定位方法是基于假設(shè)1和假設(shè)2的，偶然性正確測試用例覆蓋了錯誤行，顯然只有將它的運(yùn)行結(jié)果設(shè)置為失敗，才不會違背假設(shè)1和假設(shè)2。因此將偶然性正確測試用例作為失敗測試用例來使用，才可以提升錯誤語句的懷疑度。

在文獻(xiàn)[11]中對于偶然性正確的現(xiàn)象進(jìn)行了分析，并且將這種處理偶然性正確的方法用公式來表現(xiàn)。經(jīng)過其修正后的公式如下：

MyTarantula：

需要說明的是，盡管本文只是用tarantula和ochiai算法對本方法的應(yīng)用，事實(shí)上對其他的CFL方法也可以使用類似的改進(jìn)公式來處理。因此尋找偶然性正確測試用例對于改進(jìn)CFL方法有著普遍適用性。

3.3 基于偶然性正確對CFL的改進(jìn)方法2

以上提出的方法1確實(shí)可以提升錯誤語句的懷疑度，但是在提升錯誤語句懷疑度的同時，偶然性正確測試用例所覆蓋的正確語句的懷疑度也同時被提升了。因此需要分析相關(guān)正確語句對于錯誤語句是否會有影響。

經(jīng)過實(shí)驗(yàn)研究發(fā)現(xiàn)，方法1的修正公式對于MYCC并不是單調(diào)的。即會有以下現(xiàn)象的存在：盡管sus(s1)＞sus(s2),mycc(s1)＞mycc(s2)，但是sus′(s1)＜sus′(s2)。

這個現(xiàn)象表明，即使在尋找偶然性正確測試用例時沒有誤判率，某些情況下正確語句懷疑度的提高會比錯誤語句的懷疑度提高的更多，這種情況就會影響到方法1的實(shí)際的錯誤定位效果。

因此，在提升了錯誤語句懷疑度的同時，還需要考慮如何來降低相關(guān)正確語句的懷疑度。

在實(shí)驗(yàn)研究中發(fā)現(xiàn)，只有當(dāng)某條語句failed(s)/totalfailed非常小的時候，才會出現(xiàn)正確語句的懷疑度提升比錯誤語句的懷疑度提升的更多，甚至影響到最終的懷疑度序列。依據(jù)假設(shè)1，當(dāng)failed(s)/totalfailed非常小的時候，這一行是錯誤行的概率也會很小。因此本文對θ進(jìn)行了分析篩選，希望可以改進(jìn)以上方法1的定位效果。

令MYCC(i)/MYCC=θ，則由公式所代表的含義知，θ值越小，則這一行是錯誤行的可能性越小。類似于文獻(xiàn)[11]的分析，對于錯誤行，θ的期望應(yīng)該屬于[0.6 1]。因此首先選定某個θ值，當(dāng)某一行滿足θ=0.8時，才提升s語句的懷疑度，否則不進(jìn)行提升。通過這樣的方法來盡量避免將正確語句的懷疑度提高。以tarantula方法為例，具體修正方法如下：

對ochiai方法以及別的CFL方法也可以用相似的方式改進(jìn)。

4 實(shí)驗(yàn)相關(guān)

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

本文的實(shí)驗(yàn)使用了經(jīng)典的siemens[14]數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。siemens數(shù)據(jù)集可以從 SIR（http：//sir.unl.edu/content/sir.html）網(wǎng)站上免費(fèi)獲得，其包含內(nèi)容如圖2所示。本文中實(shí)驗(yàn)在錯誤版本的選擇方面與文獻(xiàn)[11]是一致的，一共選擇了122個可用的錯誤版本來進(jìn)行實(shí)驗(yàn)。本文的方法對于一般的CFL方法都有效，在本文實(shí)驗(yàn)時僅選取了具有代表性的tarantula方法以及ochiai方法進(jìn)行了分析。

圖2 siemens實(shí)驗(yàn)集

4.2 實(shí)驗(yàn)結(jié)果與分析

首先，使用3.1節(jié)中提出的判定算法在siemens實(shí)驗(yàn)集上對于本文提出的尋找MYCC的方法進(jìn)行了驗(yàn)證，證明了MYCC的存在性（見表3），驗(yàn)證了此判定方法確實(shí)沒有誤判率（見表4），以及計(jì)算了使用方法1之后，對于錯誤語句懷疑度的提升效果（見表5）。

接下來，使用了3.2節(jié)的方法1，對tarantula方法和ochiai方法分別進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表6所示。

從表6中可以看出，方法1確實(shí)可以提升錯誤語句的懷疑度數(shù)值。具體分析有如下結(jié)論：（1）score值為same的情況有2種。第一種為沒有找到偶然性正確測試用例，因此score值不會發(fā)生變化；第二種為，盡管找到了偶然性正確測試用例，但是由于相關(guān)的正確語句的懷疑度也提升了，并沒有引起懷疑度序列的變化，因此此時score值也不會發(fā)生變化。（2）score值為better的情況表明，將MYCC設(shè)置為FALSE會使得定位效果提升。（3）score值為worse的情況說明，會有某些正確語句懷疑度提升比錯誤語句懷疑度提升還高。其中，（3）的現(xiàn)象的存在正好印證了3.3節(jié)中所說的現(xiàn)象，單純地尋到偶然性正確測試用例并不能很好地提升錯誤定位效果。

接下來使用3.3節(jié)中的方法2進(jìn)行實(shí)驗(yàn)，分別選擇了θ=0.6和θ=0.8兩種情況進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖3，圖4所示。

表3 siemens實(shí)驗(yàn)集中MYCC數(shù)量

表4 理論MYCC數(shù)量與實(shí)驗(yàn)MYCC數(shù)量比較

表5 錯誤語句提升效果

表6 使用方法1定位效果分別與tarantula方法和ochiai方法的比較

圖3 綜合比較圖-tarantula

圖4 綜合比較圖-ochiai

從圖3可以看出，方法2對于方法1的修正效果還是很明顯的，可以有效地提升tanrantula和ochiai的定位效果。

另外還可以看出，盡管對于本文的方法來說，θ=1的時候會取到最優(yōu)解，但是對于θ=0.6的情況，也可以很大程度上減少正確語句對錯誤語句的干擾。因此其他尋找偶然性正確的方法也可是使用本方法進(jìn)行改進(jìn)。

4.3 算法復(fù)雜度分析

從步驟上來說，在運(yùn)行完成測試用例之后，需要先使用3.1節(jié)中的算法對測試用例集進(jìn)行一個處理，然后再按照公式來進(jìn)行計(jì)算。

從時間上來說，假設(shè)fail測試用例有m個，pass測試用例有n個，那么本文中算法復(fù)雜度為O(m×n)。對于經(jīng)典的CFL算法中，不論運(yùn)行測試用例的時間還是經(jīng)典算法本身的復(fù)雜度都要遠(yuǎn)高于這個值，因此這點(diǎn)時間基本可以忽略。另外對于公式的修正也沒有增加公式本身的復(fù)雜度。

從空間上來說，只需要儲存少量的數(shù)據(jù)，也可以忽略。

因此只要搭建好自動化實(shí)驗(yàn)框架之后，提出的方法與經(jīng)典的CFL方法的復(fù)雜度一致，并沒有提升其復(fù)雜度。

5 相關(guān)工作

首先與Tanrantula和ochiai方法比較，從以上的結(jié)果可以看出來，本文提出的方法可以有效提高懷疑度。因?yàn)門anrantula和ochiai這兩種方法本身是沒有考慮偶然性正確因素。

文獻(xiàn)[4]是通過分析覆蓋矩陣，依據(jù)“若所有的錯誤的測試用例中都覆蓋了第i行，并且運(yùn)行正確的測試用例中只有小于等于θ的測試用例覆蓋了第i行”，則把這樣的行作為CC因子，再通過尋找包含CC因子的測試用例來斷定其是否為偶然性正確。與此文章相比，本文尋找偶然性正確的方法誤判率為0，而他的文章中誤判率在查全率比較高的時候一般有40%的誤判率，甚至有些時候會高達(dá)100%，因此這點(diǎn)是本文提出的方法的一個很大的優(yōu)點(diǎn)。但是本文的方法只針對于某種特定類型的偶然性正確，因此查全率不夠高，這點(diǎn)比其他方法的最好情況要差一些。從定位效果上看，本文在單錯誤情況下可以有效提高錯誤語句的懷疑度，尤其是在經(jīng)過方法2的處理之后，可以更好地提升錯誤定位效果。在這點(diǎn)上，CC文章中對于定位效果的實(shí)際提升并不好，僅有約不到一半的version定位效果有提升，有少量與tarantula效果相同，還有約一半的情況下比原有方法效果還差。經(jīng)過試驗(yàn)分析發(fā)現(xiàn)，CC誤判情況的出現(xiàn)會很容易影響錯誤定位的效果。

文獻(xiàn)[3]是通過概括分析了一系列軟件行為，用EFSM生成了一些可以判斷偶然性正確的模式，并且使用模型匹配的方法來尋找偶然性正確測試用例。與此文章相比，本文的方法通用性比較高，因?yàn)榇宋恼轮兄惶峁┝四硯追N模式，若程序中不能完全匹配這些模式，則無法判斷偶然性正確。其方法的復(fù)雜度要高出本方法很多，并且他的方法不能很好地與現(xiàn)有的CFL方法相結(jié)合。

與文獻(xiàn)[15]相比較，本文的方法與他的方法同樣是通過對test的軌跡進(jìn)行分析，并且用修正的公式來計(jì)算懷疑度。但是本文方法與他的方法的根本區(qū)別是，他假定相同的軌跡，若結(jié)果為PASS的情況比較多，那么這種軌跡不包含錯誤語句的可能性更大，因此在計(jì)算的時候給它更高的正確權(quán)重，從而減少正確語句的懷疑度。本文則是通過程序軌跡來分析出一種很好的尋找偶然性正確的方法，對公式進(jìn)行修正，從而提高錯誤語句的懷疑度。由于本文方法的目的是提升錯誤語句懷疑度，而他的目標(biāo)是降低相關(guān)錯誤語句懷疑度，并且都是基于軌跡的分析，因此有著很好的互補(bǔ)作用。但是很可惜，他提出的方法對于Lower Threshold和Upper Threshold這兩個值的依賴比較高，盡管在最優(yōu)的情況下可以對ochiai方法進(jìn)行改進(jìn)，但是對于某一對特定的L和U值并不能很好地提升定位效果。由于其不穩(wěn)定，所以本文在嘗試結(jié)合后發(fā)現(xiàn)某些情況會影響本方法的定位效果。若有更好的減少正確語句懷疑度的方法與本文方法結(jié)合起來應(yīng)該會有更好的效果。

6 結(jié)束語

本文最大的貢獻(xiàn)為提出了一種沒有誤判率的尋找偶然性正確測試用例的方法并且提出了一種效果不錯的改進(jìn)CFL效果的軟件錯誤定位方法。

但是本文方法也有不完善的地方，例如對于偶然性正確測試用例的查全度并不高，只是某一些類型的偶然性正確測試用例，以及對于如何降低正確語句的懷疑度還需要進(jìn)一步考慮。

本文提出的尋找偶然性正確測試用例的方法因?yàn)闆]有誤判率，所以對于已有的尋找偶然性正確測試用例方法有著很好的意義，如果可以提升其查全率，應(yīng)該會有更廣泛的應(yīng)用并且可以更好地提升軟件錯誤定位效果。另外本文提出的改進(jìn)CFL定位效果的方法可以普遍適用于已有的CFL方法，對其定位效果進(jìn)行提升。

因此，有待進(jìn)一步研究的方向?yàn)椋旱谝?，本文方法二中對于MYCC（s）/MYCC的處理比較簡單，單錯誤情況下θ值比較容易選擇，但是多錯誤情況下可能會需要考慮更多的因素來尋找合適的值；同時，還可以結(jié)合考慮fail/Tfail的比例入手，來判斷是否使用修正后的語句懷疑度；第二，可以考慮提出新的合理的假設(shè)，并且分析程序譜，找出偶然性正確測試用例所表現(xiàn)出的其他的特點(diǎn)，來更好地提升錯誤語句的懷疑度；第三，可以重點(diǎn)研究如何減少正確語句懷疑度的方法，例如在文獻(xiàn)[15]方法基礎(chǔ)上來尋找穩(wěn)定提升CFL定位效果的方法。

[1]DiGiuseppe N，Jones J A.On the influence of multiple faults on coverage-based fault localization[C]//Proceedings of the 2011 International Symposium on Software Testing and Analysis.ACM，2011：210-220.

[2]Wong W E，Debroy V.A survey of software fault localization[R].Dallas：University of Texas at Dallas：Department of Copmputer Science，2009.

[3]Wang X，Cheung S C，Chan W K，et al.Taming coincidental correctness：Coverage refinement with context patterns to improve fault localization[C]//Proceedings of the 31st International Conference on Software Engineering.IEEE Computer Society，2009：45-55.

[4]Masri W，Assi R A.Cleansing test suites from coincidental correctnessto enhance fault-localization[C]//2010 Third International Conference on Software Testing，Verification and Validation（ICST）.IEEE，2010：165-174.

[5]Masri W，Podgurski A.An empirical study of the strength of information flows in programs[C]//Proceedings of the 2006 International Workshop on Dynamic Systems Analysis，ACM，2006：73-80.

[6]Masri W，Abou-Assi R，El-Ghali M，et al.An empirical study of the factors that reduce the effectiveness of coveragebased fault localization[C]//Proceedings of the 2nd International Workshop on Defects in Large Software Systems：Held in conjunction with the ACM SIGSOFT International Symposium on Software Testing and Analysis（ISSTA 2009）.ACM，2009：1-5.

[7]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.ACM，2002：467-477.

[8]Abreu R，Zoeteweij P，van Gemund A J C.An evaluation of similarity coefficients for software fault localization[C]//12th Pacific Rim International Symposium on Dependable Computing，2006.PRDC’06.IEEE，2006：39-46.

[9]Wong W E，Debroy V，Xu D.Towards better fault localization：A crosstab-based statistical approach[J].IEEE Transactions on Systems，Man，and Cybernetics，Part C：Applications and Reviews，2012，42（3）：378-396.

[10]Liu C，F(xiàn)ei L，Yan X，et al.Statistical debugging：A hypothesis testing-based approach[J].IEEE Transactions on Software Engineering，2006，32（10）：831-848.

[11]Jones J A，Harrold M J.Empirical evaluation of the tarantula automatic fault-localization technique[C]//Proceedings ofthe20th IEEE/ACM InternationalConferenceon Automated Software Engineering.ACM，2005：273-282.

[12]Abreu R，Zoeteweij P，Golsteijn R，et al.A practical evaluation of spectrum-based fault localization[J].Journal of Systems and Software，2009，82（11）：1780-1792.

[13]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.IEEE，2007：89-98.

[14]Hutchins M，F(xiàn)oster H，Goradia T，et al.Experiments of the effectiveness of dataflow-and controlflow-based test adequacy criteria[C]//Proceedings of the 16th International Conference on Software Engineering.[S.l.]：IEEE Computer Society Press，1994：191-200.

[15]Bandyopadhyay A，Ghosh S.Proximity based weighting of test cases to improve spectrum based fault localization[C]//2011 26th IEEE/ACM International Conference on Automated Software Engineering（ASE）.IEEE，2011：420-423.