基于程序譜的方法級(jí)別錯(cuò)誤定位技術(shù)

徐 遲，蘇小紅，王甜甜

（哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱150001）

0 引 言

目前基于程序譜的錯(cuò)誤定位方法［1］有很多，例如 Tarantula 方 法［2］、Ochiai方 法［3］等 等， 其 中Tarantula方法也經(jīng)常用來(lái)作為實(shí)驗(yàn)的對(duì)比方法。然而，這類方法的可疑度計(jì)算公式中的參數(shù)，其實(shí)并不適合用來(lái)進(jìn)行方法級(jí)別的定位。本文接下來(lái)首先探討了基于程序譜的錯(cuò)誤定位相關(guān)問(wèn)題，然后分析了Tarantula方法在方法級(jí)別定位上的不足之處，并且給出了Optimal Ranking錯(cuò)誤定位方法。最后，通過(guò)實(shí)驗(yàn)分析，驗(yàn)證了本文的方法能夠提高方法級(jí)別定位的效率。

1 錯(cuò)誤定位相關(guān)問(wèn)題

軟件錯(cuò)誤定位的目的就是為了找到待測(cè)程序中存在的bug，待測(cè)程序通常表示為P，P中的程序?qū)嶓w可以表示為：

其中，m表示為P中的程序?qū)嶓w數(shù)量，本文中，程序?qū)嶓w都是指待測(cè)程序中的方法。pi（1≤i≤m）表示P中的第i個(gè)方法。

待測(cè)程序P的測(cè)試用例集表示為：

其中，待測(cè)程序P的測(cè)試用例集T中的測(cè)試用例數(shù)量為n，ti（1≤i≤n）表示T中的第i個(gè)測(cè)試用例。同時(shí)，用TF表示執(zhí)行失敗的測(cè)試用例集合，TP表示執(zhí)行成功的測(cè)試用例集合。

使用測(cè)試用例去執(zhí)行待測(cè)程序得到的結(jié)果表示為：

其中，n表示測(cè)試用例的個(gè)數(shù)，ri（1≤i≤n）表示第i個(gè)測(cè)試用例的執(zhí)行結(jié)果，ri的取值有2種可能，1或者0。如果ri＝0，就表示第i個(gè)測(cè)試用例的執(zhí)行結(jié)果為成功；如果ri＝1，就表示第i個(gè)測(cè)試用例的執(zhí)行結(jié)果為失敗。

用矩陣M來(lái)表示每個(gè)測(cè)試用例的覆蓋信息，其數(shù)學(xué)表述如下：

其中，M為一個(gè)m行n列的矩陣，Mij表示測(cè)試用例tj執(zhí)行程序?qū)嶓wpi的情況。如果Mij＝1，就表示測(cè)試用例tj執(zhí)行了程序?qū)嶓wpi；如果Mij＝0，就表示測(cè)試用例tj沒(méi)有執(zhí)行到程序?qū)嶓wpi。

覆蓋信息矩陣M和結(jié)果向量R共同組成了記錄程序譜信息的0-1矩陣，0-1矩陣將作為本文研究的錯(cuò)誤定位方法的輸入。本文研究中選取的示例程序如圖1所示。

圖1 示例程序Fig.1 Sample program

研究中針對(duì)圖1的示例程序，給出了6組測(cè)試用例進(jìn)行測(cè)試得到的0-1矩陣，其最終直觀展示可見(jiàn)表1。

表1 示例程序的0-1矩陣Tab.1 0-1 matrix of sample program

0-1矩陣中的每一列表示測(cè)試用例ti是否調(diào)用了程序中的方法，最后一行表示測(cè)試用例ti的執(zhí)行結(jié)果。

2 Optimal Ranking錯(cuò)誤定位方法

2.1 方法設(shè)計(jì)流程

Optimal Ranking方法的整體設(shè)計(jì)流程如圖2所示。首先基于待測(cè)程序的抽象語(yǔ)法樹(shù)，進(jìn)行方法級(jí)別的程序插樁。然后使用測(cè)試用例去執(zhí)行插樁后的程序得到方法的調(diào)用序列。接下來(lái)根據(jù)方法的調(diào)用序列，統(tǒng)計(jì)方法的調(diào)用信息，使用Optimal Ranking的可疑度數(shù)學(xué)公式來(lái)計(jì)算每個(gè)方法的可疑度。最后對(duì)每個(gè)方法根據(jù)可疑度的大小進(jìn)行降序排列，得到方法可疑度的排序列表，用于對(duì)此后定位結(jié)果的研究與分析。

圖2 方法的整體流程圖Fig.2 The overall flow chart of the method

2.2 方法級(jí)別定位和語(yǔ)句級(jí)別定位的區(qū)別

方法級(jí)別定位和語(yǔ)句級(jí)別定位主要的不同之處，就在于程序的執(zhí)行路徑和其相對(duì)應(yīng)的執(zhí)行結(jié)果上。下面將以圖1中的示例程序來(lái)進(jìn)行闡釋說(shuō)明。

圖1（a）所示的是一段含有bug語(yǔ)句的代碼，bug語(yǔ)句所在的方法為f3。 圖1（b）中，給出了含有bug語(yǔ)句的方法f3的具體功能?？梢钥吹剑琭3方法的第5行代碼出現(xiàn)了錯(cuò)誤，程序的本意是想輸出c的值，但是卻誤寫(xiě)成了輸出-c的值。

如果采用的是語(yǔ)句級(jí)別的錯(cuò)誤定位方法，那么給定測(cè)試用例t的前提下，該研發(fā)代碼片段只有執(zhí)行到了f3的第5行語(yǔ)句的時(shí)候，測(cè)試用例t的執(zhí)行結(jié)果才可能是失?。ú豢紤]偶然正確性測(cè)試用例的前提下）。

而對(duì)于方法級(jí)別的錯(cuò)誤定位來(lái)說(shuō)，研究中插樁的粒度是方法級(jí)別，因此程序的執(zhí)行路徑不會(huì)考慮到方法中具體的某一條語(yǔ)句是否執(zhí)行。那么，當(dāng)使用測(cè)試用例t執(zhí)行這段代碼時(shí)，如果沒(méi)有執(zhí)行到f3中的第5行錯(cuò)誤語(yǔ)句，那么測(cè)試用例t的執(zhí)行結(jié)果就是成功的。這樣，根據(jù)基于覆蓋的錯(cuò)誤定位方法的理論，被成功的測(cè)試用例執(zhí)行到的程序體應(yīng)該更少的懷疑，同時(shí)想定位到的包含bug語(yǔ)句的f3方法的懷疑度就會(huì)降低。而研究中設(shè)定的理想情況是，只要執(zhí)行到了包含bug語(yǔ)句的方法（f3），那么測(cè)試用例的執(zhí)行結(jié)果應(yīng)該就是失敗的。

例如，圖1（a）中的程序輸入測(cè)試用例t＝｛2，1，-1｝。顯然這個(gè)測(cè)試用例的執(zhí)行結(jié)果是成功的。對(duì)于語(yǔ)句級(jí)別的定位來(lái)說(shuō)，測(cè)試用例t并沒(méi)有執(zhí)行f3中第5行的錯(cuò)誤語(yǔ)句；而對(duì)于方法級(jí)別的定位來(lái)說(shuō)，測(cè)試用例t卻調(diào)用了f3。這樣，因?yàn)槌绦驁?zhí)行了f3，且得到了正確的輸出結(jié)果，那么f3的懷疑度明顯就會(huì)降低。

2.3 可疑度計(jì)算公式

根據(jù)2.2節(jié)所述，在方法級(jí)別的錯(cuò)誤定位上，測(cè)試用例雖然調(diào)用了包含錯(cuò)誤語(yǔ)句的方法，但實(shí)際上卻沒(méi)有執(zhí)行到具體的錯(cuò)誤語(yǔ)句，所以就會(huì)導(dǎo)致研究擬設(shè)的執(zhí)行結(jié)果是失敗的測(cè)試用例，而實(shí)際的執(zhí)行結(jié)果卻是成功的。這樣必定會(huì)影響錯(cuò)誤定位的精度。

此時(shí)，研究是否可以換個(gè)角度，考慮那些沒(méi)有被失敗測(cè)試用例Tf執(zhí)行到的方法。因?yàn)檫@些方法沒(méi)有被失敗測(cè)試用例Tf執(zhí)行到，就意味著，導(dǎo)致測(cè)試用例執(zhí)行失敗的錯(cuò)誤語(yǔ)句，一定不會(huì)在這些方法中。因此，可以給這些方法賦一個(gè)比較低的可疑度值。

基于上文分析，研究給出了針對(duì)方法級(jí)別錯(cuò)誤定位的Optimal Ranking方法（簡(jiǎn)稱O方法）。O方法的可疑度的計(jì)算公式為：

其中，a表示待測(cè)程序中的某個(gè)方法。方法a的第一個(gè)下角標(biāo)表示a是否被測(cè)試用例執(zhí)行，n表示沒(méi)被執(zhí)行，e表示被執(zhí)行。方法a的第二個(gè)下角標(biāo)表示測(cè)試用例的執(zhí)行是否成功，p表示成功，f表示失敗。因此anf就表示沒(méi)有調(diào)用到方法a的失敗測(cè)試用例個(gè)數(shù)，anp表示沒(méi)有執(zhí)行到方法a的成功測(cè)試用例個(gè)數(shù)。

從公式（5）中可以看到，O方法的可疑度計(jì)算公式相比于其它的可疑度計(jì)算方法，使用了anf和anp這2個(gè)在其它方法中并未居于重要位置的變量。如果所有沒(méi)執(zhí)行到方法a的測(cè)試用例中有失敗的測(cè)試用例，即anf＞0，就可給這些方法的可疑度賦值為-1。此外，如果2個(gè)方法的anf＝0，則這兩者一定有相同的aef，因?yàn)閍nf+aef是所有失敗測(cè)試用例的總數(shù)。同理，anp+aep是所有成功測(cè)試用例的總數(shù)。分析至此可以推知，對(duì)于包含錯(cuò)誤語(yǔ)句的方法，只有小部分執(zhí)行到此方法的測(cè)試用例是成功的，即aep的值很小，因此anp的值就會(huì)相對(duì)較大。所以對(duì)于那些anf值不為0的方法，用anp來(lái)表示其對(duì)應(yīng)的可疑度是非常合理的。

2.4 實(shí)例分析

研究中設(shè)計(jì)選取的示例程序使用Tarantula方法和O方法的方法級(jí)別錯(cuò)誤定位結(jié)果可見(jiàn)表2?？梢钥吹剑褂肨arantula方法計(jì)算方法的可疑度，包含錯(cuò)誤語(yǔ)句的方法f3的可疑值并沒(méi)有排在第一位；而是用O方法計(jì)算方法的可疑度，f3方法的可疑度值則是最大的。 顯然，對(duì)于示例程序，O方法的定位效果要優(yōu)于Tarantula方法的定位效果。接下來(lái)將詳盡分析為何會(huì)得到這樣的結(jié)果。

首先，研究中將給出Tarantula方法的可疑度計(jì)算公式的數(shù)學(xué)表述如下：

其中，各符號(hào)表示的含義和公式（5）中各符號(hào)的含義相同。

表2 示例程序的方法級(jí)別定位結(jié)果對(duì)比Tab.2 Comparison of function-level location results for sample program

仔細(xì)觀察表2中的數(shù)據(jù)可以發(fā)現(xiàn)，t3、t4、t6這3組測(cè)試用例雖然調(diào)用了方法f3，但是因?yàn)闆](méi)有執(zhí)行f3中的錯(cuò)誤語(yǔ)句，因此，這3組測(cè)試用例得到的執(zhí)行結(jié)果都是正確的，這樣就會(huì)導(dǎo)致aep的值變大，Tarantula方法計(jì)算的可疑度值就會(huì)變小。而理想情況下，研究希望t3、t4、t6這3組測(cè)試用例的執(zhí)行結(jié)果都是失敗的，這樣aef的值就會(huì)變大，Tarantula方法計(jì)算的可疑度值也會(huì)變大。此消彼長(zhǎng)，就會(huì)導(dǎo)致Tarantula方法計(jì)算的f3方法的可疑值變小。

如果使用O方法計(jì)算可疑度，分析得知f2、f4、f5這3個(gè)方法的anf值都是大于零的，因此根據(jù)公式（5），就將被賦予最小的可疑度值。而f3方法的anf值是等于零的，因此隨即會(huì)被賦予更大的可疑度值。

3 實(shí)驗(yàn)分析

為了進(jìn)一步驗(yàn)證在方法級(jí)別的錯(cuò)誤定位上O方法的定位效果，本文使用了Siemens測(cè)試集［4］進(jìn)行實(shí)驗(yàn)，并且將Tarantula方法作為本文實(shí)驗(yàn)的對(duì)比方法。實(shí)驗(yàn)的評(píng)價(jià)指標(biāo)選擇的是成功定位百分比（PSD）［5］，表示通過(guò)檢查待測(cè)程序中特定百分比的方法，成功檢查到包含錯(cuò)誤語(yǔ)句方法的程序占總程序的百分比。研究推得其計(jì)算公式為：

其中，a%表示檢測(cè)待測(cè)程序中a%的方法；program_total_num表示待測(cè)程序的總數(shù)；successful_findbug_num表示所有待測(cè)程序中，可疑度排名前a%的方法中可以找到包含錯(cuò)誤語(yǔ)句的方法的程序數(shù)。

基于如上分析，仿真運(yùn)行得到在Siemens測(cè)試集上，本文的方法和Tarantula方法在方法級(jí)別錯(cuò)誤定位上的定位精度折線圖的展示效果如圖3所示。橫軸表示的是檢查的方法百分比，縱軸表示的是檢查相應(yīng)百分比的方法時(shí)，成功定位到包含錯(cuò)誤語(yǔ)句方法的程序數(shù)占總程序數(shù)的百分比。研究中，測(cè)試集的方法數(shù)都小于20，因此橫軸從10%開(kāi)始。從圖3中可以看到，檢查相同百分比的方法時(shí)，O方法相比于Tarantula方法，能夠定位到更多的錯(cuò)誤。此外，O方法想要定位到全部的錯(cuò)誤需要檢查90%左右的方法，而Tarantula方法則需要檢查全部的方法。

綜合如上實(shí)驗(yàn)分析結(jié)果，可以得出如下研究結(jié)論：在方法級(jí)別的錯(cuò)誤定位上，O方法的定位效果相比于Tarantula方法的定位效果要更好一些。

圖3 方法級(jí)別錯(cuò)誤定位結(jié)果Fig.3 Results of function-level fault location

4 結(jié)束語(yǔ)

針對(duì)語(yǔ)句級(jí)別定位效率不高的問(wèn)題，本文提出了方法級(jí)別的錯(cuò)誤定位方法。并且通過(guò)分析基于程序譜的方法級(jí)別錯(cuò)誤定位和語(yǔ)句級(jí)別錯(cuò)誤定位的不同，進(jìn)一步重點(diǎn)說(shuō)明了有些錯(cuò)誤定位方法的可疑度計(jì)算公式不適合應(yīng)用在方法級(jí)別的錯(cuò)誤定位上。最后通過(guò)實(shí)驗(yàn)驗(yàn)證了O方法在方法級(jí)別定位上有相對(duì)更好的定位效果。

此外，除了基于程序譜的方法級(jí)別錯(cuò)誤定位方法，某些非程序譜的錯(cuò)誤定位方法也可以應(yīng)用于方法級(jí)別的錯(cuò)誤定位上，這些均有待未來(lái)的深入探討與研究。