蔡 蕊， 張 仕，2， 余曉菲， 蔣建民，2

1(福建師范大學(xué) 數(shù)學(xué)與信息學(xué)院， 福建 350117)

2(福建師范大學(xué) 數(shù)字福建環(huán)境監(jiān)測(cè)物聯(lián)網(wǎng)實(shí)驗(yàn)室， 福建 350117)

隨著軟件項(xiàng)目的規(guī)模不斷變大， 軟件的可靠性也越來(lái)越難以保障. 精準(zhǔn)、有效的軟件缺陷定位技術(shù)則有利于發(fā)現(xiàn)軟件中潛在的問(wèn)題， 從而提高軟件的可靠性. 為修改測(cè)試中發(fā)現(xiàn)的問(wèn)題， 需要進(jìn)行程序的調(diào)試，其過(guò)程又可以分為缺陷定位和缺陷改正兩個(gè)步驟[1]. 早期的缺陷定位以人工為主， 通過(guò)在程序中設(shè)置斷點(diǎn)分析程序， 從而逐步找到缺陷發(fā)生的源頭. 人工定位缺陷的方法不僅難度大， 而且非常耗時(shí)， 對(duì)于大型、復(fù)雜的軟件則更是如此. 因此， 研究人員提出多種缺陷定位方法， 根據(jù)是否需要執(zhí)行測(cè)試用例， 又可分為靜態(tài)缺陷定位技術(shù)[2-4]和動(dòng)態(tài)缺陷定位方法[5-7]. 其中， 動(dòng)態(tài)缺陷定位方法則需要執(zhí)行被測(cè)程序， 搜集程序執(zhí)行過(guò)程的行為和執(zhí)行結(jié)果來(lái)定位缺陷. 在動(dòng)態(tài)缺陷定位方法中， 基于程序頻譜的動(dòng)態(tài)缺陷定位(SFL)具有很好的定位效果， 是目前軟件缺陷定位問(wèn)題的研究熱點(diǎn).

目前， 已經(jīng)提出很多基于頻譜的缺陷定位方法[8]:其中， Jone等人首先提出Tarantula[9]方法， 取得不錯(cuò)的缺陷定位效果； Abreu等人提出Jaccard[10]方法和Ochiai[11]方法， 其中Ochiai方法效果相比Tarantula方法有了一定的提高； Gonzalez增加了排除正確語(yǔ)句的優(yōu)化， 提出了Zoltar方法[12]； Naish等人使用自組裝映射中計(jì)算相似度計(jì)算相似度的方法來(lái)尋找缺陷語(yǔ)句，引入Kulczynski1方法和Kulczynski2方法[13]； Wong 等人[14]進(jìn)一步分析了成功測(cè)試用例數(shù)對(duì)缺陷定位的影響.他們認(rèn)為， 語(yǔ)句被成功測(cè)試用例覆蓋的次數(shù)越多， 該語(yǔ)句的覆蓋次數(shù)對(duì)可疑值的貢獻(xiàn)度越小[15]， 因此提出了Wong1(s)、Wong2(s)和Wong3(s)三個(gè)公式， 但當(dāng)成功執(zhí)行的用例數(shù)量較多時(shí)， 利用分段函數(shù)降低成功用例的影響這些是不夠的， 將對(duì)缺陷定位效果的提高不會(huì)很明顯. 隨后為了突出失敗用例的影響， 又提出D*方法[16]. 通過(guò)實(shí)證研究發(fā)現(xiàn)D*方法要優(yōu)于其他缺陷定位方法.

針對(duì)Wong1(s)、Wong2(s)和Wong3(s)分段函數(shù)不能自主適應(yīng)用例數(shù)量這一缺點(diǎn)， 本文從成功執(zhí)行用例數(shù)量調(diào)節(jié)出發(fā)， 提出EP*缺陷定位方法， 該方法具備自主調(diào)節(jié)成功測(cè)試用例覆蓋比重的能力， 以提高方法的適用性范圍和有效性. 本文把該方法與其他缺陷定位方法進(jìn)行對(duì)比， 實(shí)驗(yàn)結(jié)果表明該方法的缺陷定位效果優(yōu)于現(xiàn)有缺陷定位方法.

本文的第1節(jié)介紹了基于頻譜的缺陷定位方法的基本概念， 并通過(guò)一個(gè)簡(jiǎn)單的引例說(shuō)明了本文方法的基本原理和公式； 第2節(jié)中詳細(xì)說(shuō)明了本文實(shí)驗(yàn)所使用的測(cè)試程序集及評(píng)測(cè)指標(biāo)； 第3節(jié)中則通過(guò)對(duì)比分析， 詳細(xì)說(shuō)明了EP*的有效性； 最后1節(jié)總結(jié)全文.

1 基于頻譜的缺陷定位方法

1.1 基本概念

Reps 等人[17]首次提出程序譜概念， 后面的研究者們將程序頻譜[18-20]用于程序分析. 程序頻譜主要是指程序執(zhí)行過(guò)程中產(chǎn)生的關(guān)于程序語(yǔ)句的覆蓋信息(被覆蓋為1， 未覆蓋為0)， 以及執(zhí)行是否通過(guò)信息.

在利用測(cè)試用例集進(jìn)行程序的測(cè)試過(guò)程中， 收集程序語(yǔ)句的覆蓋情況和測(cè)試通過(guò)與否等相關(guān)信息， 將每一程序?qū)嶓ws相關(guān)的統(tǒng)計(jì)數(shù)據(jù)用一個(gè)四元組T(s)=＜Tep(s)，Tef(s)，Tnp(s)，Tnf(s)＞來(lái)表示， 其中Tep(s)和Tef(s)分別表示覆蓋程序?qū)嶓ws的成功測(cè)試用例數(shù)和失敗測(cè)試用例數(shù)，Tnp(s)和Tnf(s)分別表示未覆蓋程序?qū)嶓ws的成功測(cè)試用例數(shù)和失敗測(cè)試用例數(shù). 測(cè)試套件T中所有成功測(cè)試用例數(shù)Tp=Tep(s)+Tnp(s)， 所有失敗測(cè)試用例數(shù)Tf=Tef(s)+Tnf(s)， 所有測(cè)試用例數(shù)T=Tp+Tf.

Tep(s)的數(shù)值越大， 說(shuō)明語(yǔ)句s執(zhí)行且用例成功的次數(shù)多，s是缺陷語(yǔ)句的可能性越??；Tef(s)的數(shù)值越大，說(shuō)明語(yǔ)句s執(zhí)行且用例錯(cuò)誤的次數(shù)多，s是缺陷語(yǔ)句的可能性越大；Tnf(s)的數(shù)值越大， 則說(shuō)明語(yǔ)句s沒(méi)有被執(zhí)行到的情況下錯(cuò)誤越多， 這間接說(shuō)明s是缺陷語(yǔ)句的可能性越小.

1.2 EP*的缺陷定位方法

Wong等人[14]總結(jié)的假設(shè)5-7說(shuō)明了:可疑值與Tef(s)大小成正比， 與Tep(s)大小和Tnf(s)大小成反比，可以設(shè)Kulczynski系數(shù)為1來(lái)表示Tef/(Tnf+Tep). 基于假設(shè)8對(duì)Tef設(shè)置更高的權(quán)重， 可以設(shè)置Kulczynski系數(shù)為2來(lái)表示2*Tef/(Tnf+Tep). 但Kulczynski系數(shù)在缺陷定位的準(zhǔn)確性上不夠. 考慮到這一點(diǎn)， Wong等人提出采用*系數(shù)， 取值范圍從2～50增量為0.5. 提出D*方法， 通過(guò)實(shí)驗(yàn)驗(yàn)證該方法在缺陷定位上效果很好.

此外， 在文獻(xiàn)[21]中， 其通過(guò)預(yù)處理的方式去除部分測(cè)試用例， 也是希望減少成功執(zhí)行數(shù)量對(duì)可疑值的過(guò)度影響， 以提高定位精度. 由預(yù)處理目的[21]和Wong等人D*公式啟發(fā)， 為了有效降低Tep(s)對(duì)整體數(shù)值的影響， 本文提出EP*方法， 如公式 (1)所示. 公式采用*系數(shù)， 取值范圍與D*一樣. 在具體的應(yīng)用中，Tef數(shù)量要比Tep小很多， 在降低Tep的權(quán)重時(shí)對(duì)缺陷定位的影響會(huì)更加明顯.本文實(shí)驗(yàn)也驗(yàn)證了這個(gè)猜想， 說(shuō)明了EP*方法的缺陷定位要比D*方法更優(yōu).

1.3 引例

為了更好的理解， 我們通過(guò)一個(gè)實(shí)例[16]來(lái)說(shuō)明EP*缺陷定位方法. 在表1中， S表示待測(cè)程序的語(yǔ)句集， S={s1，s2，s3，s4，s5，s6，s7，s8，s9}， si表示具體的程序語(yǔ)句；P表示被測(cè)程序?qū)嶓w， 其中缺陷語(yǔ)句是s3；ti表示第i個(gè)測(cè)試用例執(zhí)行對(duì)程序的覆蓋向量， 其中黑點(diǎn)代表該語(yǔ)句被執(zhí)行， 反之未執(zhí)行； 表1中最后一行的P/F表示執(zhí)行成功與否， 0表示測(cè)試用例執(zhí)行成功， 反之失??；susp1表示測(cè)試用例基于Ochiai技術(shù)計(jì)算的可疑值；rank1表示程序中可疑值大于等于該語(yǔ)句的數(shù)量(含該語(yǔ)句本身). 從表1中可以看出， 缺陷語(yǔ)句s3的排名與語(yǔ)句s4并列第3， 表示為確保測(cè)試人員找到缺陷語(yǔ)句，最多需要檢查3條程序語(yǔ)句.

表1 示例程序表

表2對(duì)比了D*方法和EP*方法中的Kulczynski系數(shù)取為1、2、3時(shí)的示例程序排名情況. 結(jié)合表1， 可以發(fā)現(xiàn)， 當(dāng)Kulczynski系數(shù)取 1時(shí)， 缺陷語(yǔ)句排名rank2=4；Ochiai方法的缺陷語(yǔ)句排名rank1=3， 則Kulczynski1方法的定位效果不如Ochiai方法. 當(dāng)Kulczynski系數(shù)取2時(shí)，D*方法的缺陷語(yǔ)句排名rank3=3；EP*方法的缺陷語(yǔ)句排名rank5=2， 提升兩名，則EP*方法的定位效果比D*方法和Ochiai方法好. 當(dāng)Kulczynski系數(shù)取3時(shí)，D*方法的缺陷語(yǔ)句排名rank4=2， 提升一名；EP*方法的缺陷語(yǔ)句排名rank6=2保持不變. 從該例中可以看出，EP*方法在取相同系數(shù)時(shí)， 能夠更快逼近最優(yōu)值. 同時(shí)也可以發(fā)現(xiàn)， 由于s3和s4具有相同的覆蓋情況， 任何可疑度計(jì)算都無(wú)法區(qū)分二者， 即當(dāng)Kulczynski系數(shù)取2和3時(shí)，rank5=2、rank6=2已經(jīng)達(dá)到最佳缺陷定位效果.

在表2中， 語(yǔ)句s1、s3和s6的執(zhí)行通過(guò)語(yǔ)句數(shù)分別是Tep=8、Tep=7和Tep=2.在Kulczynski1方法中不同的語(yǔ)句的覆蓋次數(shù)對(duì)懷疑率的貢獻(xiàn)度是一樣的， 但語(yǔ)句s1和s3的Tep值要比s6大很多， 所以s1和s3的排名都在s6后面， 而s1和s3的排名很接近. 在EP2方法中， 不同的語(yǔ)句的覆蓋次數(shù)對(duì)懷疑率的貢獻(xiàn)度不同， 其中Tep值越大， 貢獻(xiàn)度越低. 這樣就減弱了執(zhí)行通過(guò)語(yǔ)句數(shù)Tep對(duì)語(yǔ)句s1、s3與s6的影響. 但s3中的Tef比s1和s6大， 所以s3的排名都在s1和s6前面. 因此EP*方法能夠減弱執(zhí)行通過(guò)語(yǔ)句數(shù)Tep對(duì)可疑值的過(guò)度影響.

表2 可疑值計(jì)算對(duì)比表

基于上述分析， 簡(jiǎn)要說(shuō)明了本文提出的EP*方法在缺陷定位中的應(yīng)用， 在該實(shí)例中，EP*方法顯著減弱了執(zhí)行通過(guò)語(yǔ)句數(shù)Tep對(duì)可疑值的過(guò)度影響， 使其缺陷定位效果比Ochiai和D*方法好. 當(dāng)系數(shù)取2時(shí)，EP*方法中的缺陷語(yǔ)句排名已經(jīng)達(dá)到D3方法的缺陷語(yǔ)句排名，從中可以看出，EP*方法比D*方法收斂更快. 在下一節(jié)中將通過(guò)實(shí)驗(yàn)對(duì)比分析EP*缺陷定位方法與其他缺陷定位方法的實(shí)驗(yàn)結(jié)果.

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

本節(jié)首先介紹目標(biāo)程序信息， 再通過(guò)實(shí)驗(yàn)說(shuō)明EP*方法的缺陷定位效果.

2.1 測(cè)試程序集

實(shí)驗(yàn)使用了SIR中的Siemens suite測(cè)試套件和space 程序[22]， Siemens suite 包含 7 個(gè)程序， 它是由實(shí)現(xiàn)不同功能的C 程序組成， 每組程序通過(guò)人工注入的方式植入缺陷. space程序測(cè)試包含的多個(gè)版本都是實(shí)際的缺陷， 其詳細(xì)信息如表3所示. 表3中各列分別表示程序名、每個(gè)程序缺陷版本數(shù)、程序代碼行數(shù)、測(cè)試用例個(gè)數(shù)、程序功能的簡(jiǎn)要描述. 該測(cè)試集涉及各種缺陷類(lèi)型， 以模擬實(shí)際可能存在的缺陷. 本實(shí)驗(yàn)用到了Siemens suite測(cè)試套件中的121個(gè)版本和space程序的20個(gè)版本. 其中， 去除某些缺陷版本的原因有:“Core dumped”錯(cuò)誤無(wú)法生成覆蓋文件、宏定義錯(cuò)誤和頭文件缺陷等.

表3 實(shí)驗(yàn)程序信息

2.2 缺陷定位評(píng)測(cè)指標(biāo)

基于語(yǔ)句排名的評(píng)測(cè)采用了Score評(píng)測(cè)指標(biāo). 按照可疑值Suspiciousness的取值從高到低進(jìn)行排序， 值越高代表該語(yǔ)句為缺陷語(yǔ)句的可能性越大， 反之， 則代表該語(yǔ)句是缺陷語(yǔ)句的可能性越小. 假設(shè)排查程序P={s1，s2，…，sn}， 其中 sf為缺陷語(yǔ)句，n為程序 P 的語(yǔ)句數(shù).衡量缺陷定位方法優(yōu)劣的指標(biāo)是看在該方法中， 按可疑率排序缺陷語(yǔ)句被檢查到的位序(Rank). 當(dāng)存在m(m＞0)個(gè)語(yǔ)句與缺陷語(yǔ)句sf的可疑值取值相等時(shí)， 目前有兩種方法計(jì)算Rank值. 假設(shè)可疑值高于sf的程序語(yǔ)句個(gè)數(shù)為t， 則方法一: 考慮最壞情況， 即設(shè)缺陷語(yǔ)句的Rank=m+t， 本實(shí)驗(yàn)采用該方法計(jì)算Rank值； 方法二:考慮平均情況， 即設(shè)缺陷語(yǔ)句的Rank=t+m/2. 基于缺陷語(yǔ)句的Rank值， 常用的評(píng)測(cè)指標(biāo)為Score如公式(2)所示， 其表示不用檢查的語(yǔ)句占所有語(yǔ)句的百分比.Score值越高， 則說(shuō)明程序員在缺陷定位時(shí)不用檢查的語(yǔ)句越多， 需要檢查的代碼行數(shù)越少， 也就說(shuō)明了缺陷定位的效果越好， 反之， 則說(shuō)明缺陷定位方法效果差.

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

為了能夠清晰對(duì)比本文所提出的缺陷定位方法EP*對(duì)缺陷定位的影響， 本節(jié)通過(guò)實(shí)驗(yàn)對(duì)比Tarantula方法、Jaccard方法、Ochiai方法和D*方法的Score評(píng)價(jià)指標(biāo)來(lái)說(shuō)明該方法的有效性， 實(shí)驗(yàn)設(shè)置系數(shù)(*)分別為3、5和10. 表4是基于西門(mén)子套件的每個(gè)分?jǐn)?shù)范圍運(yùn)行百分比， 而表5是基于space程序的每個(gè)分?jǐn)?shù)范圍運(yùn)行百分比.

表4 西門(mén)子套件中的每個(gè)分?jǐn)?shù)范圍運(yùn)行百分比

從表 4 中可以看出，D3、D5、D10、EP3、EP5和EP10的所有缺陷語(yǔ)句均能在不用檢查的語(yǔ)句占所有語(yǔ)句的 65% 內(nèi)被發(fā)現(xiàn)， 但Tarantula、Jaccard、Ochiai和Kulczynski1在檢查35%代碼后還有少部分缺陷語(yǔ)句是無(wú)法排查到. 查看Score在99-100%區(qū)間內(nèi)， 即， 檢查代碼數(shù)量在1%內(nèi)便可確定缺陷代碼位置的情況. 其中EP3、EP5和EP10在檢查代碼數(shù)量的1% 內(nèi)可排查缺陷占 10%， 分別比Kulczynski1、Jaccard、Tarantula、D10、D5、D3、Ochiai的準(zhǔn)確率提升了 4.55、4.55、4.55、1.82、2.73、2.73、3.64 個(gè)百分點(diǎn). 圖1(a)對(duì)應(yīng)于表4數(shù)據(jù)， 表示基于西門(mén)子套件的Score值的缺陷定位效果對(duì)比圖. 從圖中可以發(fā)現(xiàn)EP3、EP5和EP10曲線均在其它方法的曲線上面， 然后是D10、D5和D3曲線， 最下面的曲線是Tarantula. 由此可知: 在缺陷定位效果上， 基于西門(mén)子套件中EP*方法只需檢查更少量的代碼行就可以找出缺陷位置， 即，EP3、EP5和EP10比其它方法好， 其中Tarantula方法最差.

圖1 基于Score值的缺陷定位效果對(duì)比圖

從表 5 中可以看出，D3、D5、D10、EP3、EP5、EP10和Ochiai的所有缺陷語(yǔ)句均能在不用檢查的語(yǔ)句占所有語(yǔ)句的90%內(nèi)被發(fā)現(xiàn)， 但Tarantula、Jaccard和Kulczynski1在檢查10%代碼后還有部分缺陷語(yǔ)句是無(wú)法排查到.其中EP3、EP5和EP10在檢查代碼數(shù)量的 1% 內(nèi)可排查缺陷占 85%， 比D10、D5、D3和Ochiai提升了5個(gè)百分點(diǎn)； 比Kulczynski1和Jaccard準(zhǔn)確率提升了15個(gè)百分點(diǎn)； 比Tarantula準(zhǔn)確率提升了25個(gè)百分點(diǎn). 圖1(b)對(duì)應(yīng)于表5數(shù)據(jù)， 表示基于space程序的Score值的缺陷定位效果對(duì)比圖. 從圖中可以發(fā)現(xiàn)EP3、EP5和EP10曲線均在其它方法的曲線上面， 然后是D10、D5和D3曲線， 最下面的曲線是Tarantula. 由此可知: 在缺陷定位效果上， 對(duì)space程序，EP*方法只需檢查更少量的代碼行就可以找出缺陷位置， 即，EP3、EP5和EP10比其它方法好， 其中Tarantula方法最差.

從收斂性上分析表4數(shù)據(jù)， 分?jǐn)?shù)范圍運(yùn)行百分比為99%時(shí)EP3、EP5和EP10已經(jīng)收斂達(dá)到最佳定位效果Score值為 10， 但D3、D5和D10的Score值分別為7.27、7.27 和 8.18， 顯然比EP*低. 再查看Score值在90～100%之間的情況(即發(fā)現(xiàn)缺陷需檢查代碼在10% 范圍內(nèi))，EP3、EP5和EP10值均達(dá)到 59.09， 而D3、D5和D10的值分別為55.45、57.27和57.27. 從中可以明顯看出， 隨著系數(shù)增大，EP*比.D*更快接近最佳定位效果. 所以EP*方法的收斂性比D*方法好.

通過(guò)上述實(shí)驗(yàn)及分析可以發(fā)現(xiàn)， 在目標(biāo)測(cè)試程序中，EP*方法表現(xiàn)出很好的缺陷定位效果， 比現(xiàn)有的缺陷定位方法都要好很多.

4 結(jié)果與展望

通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)， 基于EP*的缺陷定位方法有利于提高缺陷定位效果， 實(shí)驗(yàn)結(jié)果表明，EP*方法的缺陷定位效果比現(xiàn)有的方法好， 而且能夠有效調(diào)整成功執(zhí)行用例數(shù)， 以避免成功用例數(shù)量對(duì)缺陷定位效果的影響.