曹鶴玲，姜淑娟，王興亞，薛 猛,錢俊彥

(1.中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,江蘇徐州 221116； 2.河南工業(yè)大學(xué)信息科學(xué)與工程學(xué)院,河南鄭州 450001；3.桂林電子科技大學(xué)廣西可信軟件重點(diǎn)實(shí)驗(yàn)室,廣西桂林 541004)

面向有效錯(cuò)誤定位的偶然正確性識(shí)別方法

曹鶴玲1,2,3，姜淑娟1，王興亞1，薛 猛1,錢俊彥3

(1.中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,江蘇徐州 221116； 2.河南工業(yè)大學(xué)信息科學(xué)與工程學(xué)院,河南鄭州 450001；3.桂林電子科技大學(xué)廣西可信軟件重點(diǎn)實(shí)驗(yàn)室,廣西桂林 541004)

錯(cuò)誤定位是軟件調(diào)試中耗時(shí)費(fèi)力的活動(dòng)之一.針對(duì)偶然正確性影響錯(cuò)誤定位效率的問(wèn)題，提出面向錯(cuò)誤定位的偶然正確性識(shí)別方法.該方法首先識(shí)別偶然正確性元素；然后，挑選“偶然正確性特征元素”，使用該特征元素約簡(jiǎn)程序執(zhí)行軌跡；在此基礎(chǔ)上，建立基于模糊c均值聚類的偶然正確性識(shí)別模型，將其結(jié)果應(yīng)用于錯(cuò)誤定位.為驗(yàn)證該方法的有效性，基于3組測(cè)試程序開展偶然正確性識(shí)別，并將其結(jié)果應(yīng)用于Tarantula等4種錯(cuò)誤定位方法.實(shí)驗(yàn)結(jié)果表明，與基于k-means聚類的偶然正確性識(shí)別方法相比，該方法在偶然正確性識(shí)別方面具有較低的誤報(bào)率和漏報(bào)率，并且更能提高錯(cuò)誤定位的效率.

軟件調(diào)試；錯(cuò)誤定位；偶然正確性；聚類分析

1 引言

基于覆蓋信息的錯(cuò)誤定位方法深受工業(yè)界和學(xué)術(shù)界廣泛關(guān)注.偶然正確性指軟件中存在缺陷但是仍然通過(guò)測(cè)試的現(xiàn)象，它通常對(duì)基于覆蓋信息的錯(cuò)誤定位方法的效率產(chǎn)生負(fù)面的影響.并且，Hierons和Masri等人[1,2]研究了偶然正確性在軟件系統(tǒng)中存在的普遍性.Masri等人[3]研究表明程序大部分程序依賴不能傳遞任何可度量的信息，這意味著很多感染的程序狀態(tài)不能傳播到輸出，從而導(dǎo)致偶然正確性的發(fā)生.

針對(duì)偶然性正確問(wèn)題，Wang等人[4]假設(shè)調(diào)試人員能預(yù)先知道程序缺陷類型，對(duì)錯(cuò)誤觸發(fā)前后的控制流和數(shù)據(jù)流信息與特定模式匹配，提純代碼覆蓋信息，從而移除偶然正確性對(duì)錯(cuò)誤定位效率的不利影響.Bandyopadhyay[5]根據(jù)成功測(cè)試用例和失敗測(cè)試用例的相似度來(lái)識(shí)別偶然正確性，并賦予偶然正確性測(cè)試用例較低的權(quán)重，進(jìn)而根據(jù)測(cè)試用例的權(quán)重而不是測(cè)試用例數(shù)量來(lái)計(jì)算程序語(yǔ)句的懷疑度，減少偶然正確性對(duì)錯(cuò)誤定位效率的影響.陳振宇等人[6]對(duì)程序覆蓋信息進(jìn)行聚類分析，將和失敗測(cè)試用例在同一簇中的成功測(cè)試用例視為可能的偶然正確性測(cè)試用例，通過(guò)移除偶然正確性測(cè)試用例來(lái)減少其影響.上述研究可以顯著提高錯(cuò)誤定位的效率，這促使我們?nèi)パ芯扛行实呐既徽_性識(shí)別方法.

文獻(xiàn)[7]采用k-means聚類分析來(lái)識(shí)別偶然正確性測(cè)試用例，而k-means聚類屬于硬分類方法，每個(gè)程序執(zhí)行軌跡信息只能屬于所有類別中的某一類，非此即彼.這樣帶來(lái)的問(wèn)題是：所有程序執(zhí)行軌跡信息對(duì)計(jì)算聚類中心貢獻(xiàn)度相同.而模糊理論允許數(shù)據(jù)對(duì)象屬于任何一類(簇)，不同的是它們屬于某類(簇)的可能性大小不同.為此，我們引入模糊c均值聚類(Fuzzy C-Means，F(xiàn)CM)來(lái)識(shí)別偶然正確性測(cè)試用例.將去除偶然正確性測(cè)試用例后的測(cè)試用例集應(yīng)用于錯(cuò)誤定位，則可以提高錯(cuò)誤定位方法的效率.

本文貢獻(xiàn)在于：

(1)提出了偶然正確性特征元素挑選策略，使用該特征元素對(duì)程序執(zhí)行軌跡信息進(jìn)行維度約簡(jiǎn).

(2)提出面向錯(cuò)誤定位的偶然正確性識(shí)別方法，該方法使用基于Fuzzyc-means聚類來(lái)識(shí)別偶然正確性測(cè)試用例，從而提高錯(cuò)誤定位效率.

2 預(yù)備知識(shí)

2.1 偶然正確性

定義1 偶然正確性元素cce[7].給定一個(gè)程序元素e，P(TF,e)為失敗測(cè)試用例TF執(zhí)行e的概率，P(TP,e)為成功測(cè)試用例TP執(zhí)行e的概率，e出現(xiàn)在所有失敗測(cè)試中，即P(TF,e)=1，而出現(xiàn)在成功測(cè)試中的概率為0

cce={e|P(TF,e)=1∧0

(1)

定義2 偶然正確性特征元素fcce.使用某懷疑度計(jì)算式計(jì)算偶然正確性元素的懷疑度，并對(duì)其按懷疑度從大到小排序得到序列rank(cce)，取序列的前θ(0<θ<1)部分為偶然正確性特征元素.

fcce={e|e∈cce∧θ*rank(cce)}

(2)

定義3 偶然正確性測(cè)試用例TCC[7].一個(gè)測(cè)試用例T執(zhí)行了偶然正確性元素cce，而沒(méi)有導(dǎo)致程序執(zhí)行結(jié)果失敗，則該測(cè)試用例為偶然正確性測(cè)試用例TCC.

定義4 偶然正確性(Coincidental Correctness,CC)[7].指的是程序執(zhí)行了缺陷語(yǔ)句，而缺陷語(yǔ)句的錯(cuò)誤狀態(tài)并沒(méi)有傳播到程序輸出結(jié)果，而使程序執(zhí)行成功或沒(méi)有拋出異常.

下面以函數(shù)foo()為例說(shuō)明偶然正確性存在.函數(shù)foo()中的錯(cuò)誤在語(yǔ)句s5，正確語(yǔ)句為：ret=x+y.我們?cè)O(shè)計(jì)了以下6個(gè)測(cè)試用例：t1(6,3,9)，t2(2,4,6)，t3(4,0,3)，t4(5,2,0)，t5(5,4,2)和t6(5,0,2)來(lái)測(cè)試程序.獲取6個(gè)測(cè)試用例執(zhí)行的覆蓋信息及執(zhí)行結(jié)果如表1所示，其中，“·”和“°”分別表示語(yǔ)句被覆蓋和未被覆蓋，T和F分別表示程序執(zhí)行成功和失敗.由定義4可知，測(cè)試用例t3和t6執(zhí)行了錯(cuò)誤語(yǔ)句s5而程序沒(méi)有報(bào)錯(cuò)，則說(shuō)明在程序的執(zhí)行過(guò)程中存在偶然正確性.根據(jù)定義3可知，測(cè)試用例t3、t6為偶然正確性測(cè)試用例.

表1 偶然正確性示例

2.2 模糊c均值聚類

軟件錯(cuò)誤定位場(chǎng)景中的聚類分析從數(shù)學(xué)模型角度刻畫如下：X=(x1,x2,…,xj,…,xn)表示聚類分析的數(shù)據(jù)對(duì)象(程序執(zhí)行軌跡信息)，即測(cè)試用例(t1,t2,…,tj,…,tn)執(zhí)行程序的軌跡信息，其中xj表示第tj個(gè)測(cè)試用例的執(zhí)行軌跡信息.對(duì)給定數(shù)據(jù)對(duì)象X進(jìn)行聚類分析就是將其劃分成c簇，對(duì)于識(shí)別偶然性正確測(cè)試用例來(lái)說(shuō)就是將成功測(cè)試用例集TP劃分成偶然正確性測(cè)試用例集和真正成功測(cè)試用例集.我們采用歐幾里德距離dij如式(3)所示，來(lái)度量?jī)蓚€(gè)程序執(zhí)行軌跡的相似度.

(3)

FCM聚類就是通過(guò)找到使用的最佳組對(duì)(U,V)來(lái)求解目標(biāo)函數(shù)J(U,V)的過(guò)程，從而將聚類問(wèn)題轉(zhuǎn)換成一個(gè)帶約束的非線性規(guī)劃問(wèn)題，通過(guò)不斷迭代求解得到數(shù)據(jù)集的最優(yōu)劃分，其中，U表示隸屬度矩陣，V表示聚類中心點(diǎn).FCM聚類將數(shù)據(jù)對(duì)象X分為c個(gè)模糊簇，并求每簇的聚類中心點(diǎn)vi，i=1,2,…,c,使得目標(biāo)函數(shù)J(U,V)達(dá)到最小值.目標(biāo)函數(shù)定義如下:

J(U,V) =J(U,v1,v2,…,vc;X)

(4)

且滿足下列等式：

(5)

對(duì)于所有輸入的參數(shù)求導(dǎo)數(shù)，使得J(U,V)達(dá)到最小值且滿足等式(5)的必要條件為式(6)和(7).其中，式(6)是最佳聚類中心點(diǎn)，式(7)是最佳隸屬度函數(shù).

(6)

(7)

3 本文方法

3.1 方法概述

針對(duì)偶然正確性影響錯(cuò)誤定位效率的問(wèn)題，提出面向有效錯(cuò)誤定位的偶然正確性識(shí)別方法，并建立基于模糊c均值聚類的偶然正確性測(cè)試用例識(shí)別模型CC-FCM(cleansing Coincidental Correctness test cases based on Fuzzy C-Means)如圖1所示.該模型的目標(biāo)是識(shí)別測(cè)試用例集中的偶然正確性測(cè)試用例，移除后應(yīng)用于錯(cuò)誤定位，能提高其效率.

該模型主要步驟如下：

(1)獲取執(zhí)行軌跡信息.通過(guò)插樁程序獲取程序執(zhí)行軌跡信息，根據(jù)測(cè)試諭言將其分為成功和失敗測(cè)試用例的執(zhí)行軌跡信息.

(2)根據(jù)定義1識(shí)別偶然正確性元素cce.

(3)特征元素挑選.采用Tarantula方法對(duì)cce進(jìn)行懷疑度計(jì)算，將懷疑度的大小作為偶然正確性元素的權(quán)重，對(duì)偶然正確性元素進(jìn)行排序，設(shè)置參數(shù)θ作為選擇偶然正確性元素的比例，挑選出特征元素.

(4)維度約簡(jiǎn).根據(jù)挑選的特性元素對(duì)步驟(1)中獲得的程序執(zhí)行軌跡信息進(jìn)行維度約簡(jiǎn).

(5)識(shí)別偶然正確性.對(duì)降維后的程序執(zhí)行軌跡信息采用Fuzzyc-means聚類算法將其分為兩簇，一般認(rèn)為偶然正確性測(cè)試用例的執(zhí)行軌跡和失敗測(cè)試用例的執(zhí)行軌跡最相似[7]，因此，將包含失敗測(cè)試用例較多的那個(gè)簇中的成功測(cè)試用例視為偶然正確性測(cè)試用例，另外一個(gè)簇中的成功測(cè)試用例為真正成功測(cè)試用例.

(6)將移除偶然正確性測(cè)試用例后的測(cè)試用例集應(yīng)用于錯(cuò)誤定位，從而提高其效率.

3.2 算法

算法1描述了基于Fuzzyc-means聚類的偶然正確性測(cè)試用例識(shí)別算法，主要實(shí)現(xiàn)3.1節(jié)偶然正確性識(shí)別模型中的步驟2～5.第1～5行識(shí)別偶然正確性元素cce，其中第1行初始化偶然正確性元素為φ.第2、3行根據(jù)計(jì)算偶然正確性元素，其中L(t)表示程序執(zhí)行軌跡中所有元素.第4行計(jì)算偶然正確性元素集合.第6、7行，特征元素選擇，使用Tarantula計(jì)算懷疑度，對(duì)偶然正確性元素cce按懷疑度從大到小排序，設(shè)置挑選高可疑偶然正確性元素比例θ，來(lái)挑選特征元素.第8行執(zhí)行軌跡維度約簡(jiǎn)，按挑選出的特征元素對(duì)所有程序執(zhí)行軌跡進(jìn)行維度約簡(jiǎn)，約簡(jiǎn)后程序執(zhí)行軌跡信息作為Fuzzyc-means聚類的輸入.第9～15行為Fuzzyc-means聚類過(guò)程，第9行為初始化隸屬度矩陣U0且矩陣滿足式(5).第10～12行為聚類迭代求解過(guò)程，根據(jù)式(6)和式(7)迭代求解最優(yōu)(Uf,Vf)，其中Uf表示最優(yōu)隸屬度矩陣，Vf表示最優(yōu)聚類中心點(diǎn)，第14、15行根據(jù)最優(yōu)(Uf,Vf)生成最終簇Cluster1，Cluster2，其中一個(gè)簇中包含偶然正確性測(cè)試用例.

算法1 基于Fuzzyc-means聚類的偶然正確性測(cè)試用例識(shí)別算法

輸入：k； //聚類的簇?cái)?shù)k=2

T； //所有程序執(zhí)行軌跡信息

m； //聚類迭代次數(shù)最大值

θ； //偶然正確性元素挑選閾值

ε； //聚類分析終止閾值，ε>0

輸出：Cluster1,Cluster2

begin

1. cce←φ;

2. for eachein∪t∈Trace(L(t))

3. if (P(TF,e)=1∧0

4. cce←cce∪{e};

5. end for

6. calculate the suspiciousness of ccewith Tarantula;

7. pick the most suspicious ccewith suspiciousness sorted by Tarantula setting parameterθ;

8. reduce traceTusing ccebeing picked;

9. randomly generate membership matricU0and makeuijsatisfy formula(5);

11. calcalate the center of clusterVtwithUtand formula(6);

12. calcalate membership matricUtwithVt-1and formula(7);

13.end while

14. produce optimal (Uf,Vf)=(Ut,Vt)；

15. generate Cluster1 and Cluster2 according to (Uf,Vf);

end

4 實(shí)驗(yàn)評(píng)估

為評(píng)估偶然正確性對(duì)錯(cuò)誤定位效率的影響，選取Tarantula[8]、Ochiai[9]、Naish2[10]和Russel&Rao[10]共4種錯(cuò)誤定位方法進(jìn)行對(duì)比實(shí)驗(yàn).運(yùn)行環(huán)境:Ubuntu 64位操作系統(tǒng)，版本12.04，2核CPU 3.07GHz Intel(R)，內(nèi)存16GB.

4.1 實(shí)驗(yàn)對(duì)象

實(shí)驗(yàn)采用西門子套件C版本中的3個(gè)程序print_tokens2，schedule2和tcas作為代碼較小規(guī)模的程序代表；西門子套件目前使用廣泛，但程序規(guī)模較小，為保障實(shí)驗(yàn)結(jié)論更具一般性，選取了代碼中等規(guī)模的Nanoxml程序中版本v1、v2和v5；另外選取了Unix工具程序(gzip、grep、sed、flex).實(shí)驗(yàn)對(duì)象詳細(xì)信息見表2，從SIR(Subject Infrastructure Repository)(SIR網(wǎng)址：http://sir.unl.edu/portal /index.html)下載.

表2 實(shí)驗(yàn)對(duì)象

4.2 評(píng)測(cè)指標(biāo)

(1)漏報(bào)率(False Negatives,FN).主要用于評(píng)估某種方法未準(zhǔn)確識(shí)別偶然正確性測(cè)試用例的比率[7]，見式(8)，其中，true CC NO.表示的是真實(shí)的偶然正確測(cè)試用例數(shù)，CC identifed NO.表示的是通過(guò)聚類分析技術(shù)判別出來(lái)的偶然正確性測(cè)試用例數(shù).

(8)

(2) 誤報(bào)率(False Positives,FP).主要用于評(píng)估某種方法將非偶然正確性測(cè)試用例判別為偶然正確性測(cè)試用例的比率，見式(9)，其中，Tp表示成功測(cè)試用例數(shù).

(9)

(3)錯(cuò)誤定位代價(jià)(cost).為找到缺陷時(shí)需要檢查的語(yǔ)句數(shù)與程序的總語(yǔ)句數(shù)的比率[11]，見式(10).

(10)

(4)檢查得分(EXAM)[11].為錯(cuò)誤檢出率(% of faults located)與代碼檢查率(% of code examined)的比率.

(11)

4.3 實(shí)驗(yàn)評(píng)估

為評(píng)估方法有效性，進(jìn)行以下3個(gè)方面的實(shí)驗(yàn).

(1)偶然正確性存在的普遍性

通過(guò)程序插樁來(lái)檢測(cè)成功測(cè)試用例的執(zhí)行過(guò)程中缺陷語(yǔ)句是否被執(zhí)行到，若被執(zhí)行到，則為偶然正確性測(cè)試用例；否則為真正成功測(cè)試用例.圖2展示了測(cè)試的136個(gè)程序錯(cuò)誤版本(見表1)中普遍存在偶然正確性現(xiàn)象.其中，橫坐標(biāo)為成功測(cè)試用例中包含偶然正確性百分比；縱坐標(biāo)為包含一定比例偶然正確性測(cè)試用例的錯(cuò)誤版本數(shù)比率.

(2)識(shí)別偶然正確性的誤報(bào)率(FN)和漏報(bào)率(FP)

由表3可見，CC-FCM模型的誤報(bào)率和漏報(bào)率都稍低于對(duì)比方法Tech-I.由于真正成功和偶然正確性測(cè)試用例較難區(qū)分，且聚類分析對(duì)數(shù)據(jù)對(duì)象的識(shí)別存在一定的偏差，導(dǎo)致這兩種方法都有一定程度的誤報(bào)和漏報(bào).

表3 平均誤報(bào)率和漏報(bào)率

(3)去除偶然正確性前后錯(cuò)誤定位效率的對(duì)比

本文主要采用4種錯(cuò)誤定位方法Tarantula，Ochiai，Naish2和Russel&Rao進(jìn)行對(duì)比實(shí)驗(yàn).在下面3種情況下比較其錯(cuò)誤定位的效率：①不考慮偶然正確性，在原始測(cè)試用例集上進(jìn)行錯(cuò)誤定位，記為Orig.②在文獻(xiàn)[7]中Tech-I方法去除偶然正確性的測(cè)試用例集上進(jìn)行錯(cuò)誤定位，記為Tech-I.③在CC-FCM模型識(shí)別并移除偶然正確性的測(cè)試用例集上進(jìn)行錯(cuò)誤定位，記為CC-FCM.

對(duì)于某方法來(lái)說(shuō)，錯(cuò)誤定位代價(jià)越小說(shuō)明其效率越高.實(shí)驗(yàn)結(jié)果如表4中所示，在CC-FCM和Tech-I移除偶然正確性的基礎(chǔ)上，4種方法的錯(cuò)誤定位代價(jià)均低于在原始測(cè)試用例集上(Orig.)的錯(cuò)誤定位代價(jià).大多數(shù)情況下，在CC-FCM識(shí)別偶然正確性的基礎(chǔ)上的錯(cuò)誤定位代價(jià)低于在Tech-I識(shí)別偶然正確性基礎(chǔ)上的錯(cuò)誤定位代價(jià)；但在個(gè)別情況下，在CC-FCM基礎(chǔ)上的錯(cuò)誤定位代價(jià)稍高于或等于在Tech-I基礎(chǔ)上的錯(cuò)誤定位代價(jià)，如表4中陰影所示.例如，對(duì)于schedule2程序，Russel&Rao方法在CC-FCM基礎(chǔ)上的錯(cuò)誤定位代價(jià)18.32%稍高于在Tech-I基礎(chǔ)上的錯(cuò)誤定位代價(jià)18.23%.其原因在于：這些測(cè)試程序不盡相同，程序特征及錯(cuò)誤分布可能不同，這使得本文方法的效果可能受到一定程度的影響，在個(gè)別情況下，效率提升不明顯.

接下來(lái)比較在CC-FCM與Tech-I、Orig.基礎(chǔ)上錯(cuò)誤定位的檢查得分.圖3分別展現(xiàn)了在3種情況下4種錯(cuò)誤定位方法的檢查得分.其中，橫坐標(biāo)代表代碼檢查率，縱坐標(biāo)代表在一定代碼檢查率下的錯(cuò)誤檢出率.相同代碼檢查率下，某方法定位出的錯(cuò)誤比例越高則該方法越有效.從圖3可以看出，4種錯(cuò)誤定位方法在CC-FCM識(shí)別偶然正確性情況下檢查得分高于在Tech-I識(shí)別偶然正確性情況下的檢查得分；并且CC-FCM和Tech-I識(shí)別并移除偶然正確性后，錯(cuò)誤定位方法的檢查得分都高于不考慮偶然正確性測(cè)試用例Orig.情況下的檢查得分.

表4 去除偶然正確性前后各錯(cuò)誤定位方法的錯(cuò)誤定位代價(jià)

本文方法與Tech-I方法相比的優(yōu)勢(shì)在于：①引入Fuzzyc-means聚類分析，該聚類允許數(shù)據(jù)對(duì)象屬于任何一簇，只是它們屬于某簇的可能性大小不同；而Tech-I方法使用的k-means聚類屬于硬分類，使得每個(gè)程序執(zhí)行軌跡只能屬于所有類別中的某一類，對(duì)聚類中心點(diǎn)的貢獻(xiàn)度相同.②設(shè)計(jì)了偶然正確性特征元素挑選策略，這些特征元素更能反映程序執(zhí)行軌跡信息的偶然正確性特征.

5 結(jié)論

針對(duì)偶然正確性問(wèn)題，提出一種面向有效錯(cuò)誤定位的偶然正確性識(shí)別方法.首先,識(shí)別出偶然正確性元素;其次，對(duì)偶然正確性元素排序，挑選出高可疑偶然正確性元素作為特征元素，利用其對(duì)程序執(zhí)行軌跡進(jìn)行維度約簡(jiǎn)；最后，使用模糊c均值聚類對(duì)維度約簡(jiǎn)后程序執(zhí)行軌跡進(jìn)行聚類，識(shí)別出偶然正確性測(cè)試用例，將其移除偶然正確性后的結(jié)果應(yīng)用于錯(cuò)誤定位.實(shí)驗(yàn)表明：與Tech-I方法相比，CC-FCM識(shí)別偶然正確性的誤報(bào)率和漏報(bào)率有所下降；移除偶然正確性測(cè)試用例后，錯(cuò)誤定位方法的定位效率有一定程度的提升.

[1]Hierons R M.Avoiding coincidental correctness in boundary value analysis[J].ACM Transactions on Software Engineering and Methodology,2006,15(3):227-241.

[2]Masri W,Assi R A.Cleansing test suites from coincidental correctness to enhance fault-localization[A].Proceedings of the 3rd International Conference on Software Testing,Verification and Validation[C].Paris,France:IEEE,2010.165-174.

[3]Masri W,Podgurski A.Measuring the strength of information flows in programs[J].ACM Transactions on Software Engineering and Methodology,2009,19(2):5-37.

[4]Wang X,Cheung S C,et al.Taming coincidental correctness:coverage refinement with context patterns to improve fault localization[A].Proceedings of the 31th International Conference on Software Engineering[C].Los Alamitos,CA:IEEE Computer Society,2009.45-55.

[5]Bandyopadhyay A.Mitigating the effect of coincidental correctness in spectrum based fault localization[A].Proceedings of the 5th International Conference on Software Testing,Verification and Validation[C].Montreal,QC:IEEE,2012.479-482.

[6]Miao Y,Chen Z,Li S,et al.A Clustering-based strategy to identify coincidental correctness in fault localization[J].International Journal of Software Engineering and Knowledge Engineering,2013,23(05):721-741.

[7]Masri W,Assi R A.Prevalence of coincidental correctness and mitigation of its impact on fault localization[J].ACM Transactions on Software Engineering and Methodology,2014,23(1):1-28.

[8]Jones J A,Harrold M J,Stasko J.Visualization of test information to assist fault localization[A].Proceedings of the 24th International Conference on Software Engineering[C].Los Alamitos,CA:IEEE Computer Society,2002.467-477.

[9]Rui A,Peter Z,et al.An evaluation of similarity coefficients for software fault localization[A].Proceedings of the 12th Pacific Rim International Symposium on Dependable Computing[C].Riverside,CA:IEEE,2006.39-46.

[10]Naish L,Lee H J,et al.A model for spectra-based software diagnosis[J].ACM Transactions on Software Engineering and Methodology,2011,20(3):11-43.

[11]Renieris M,Reiss S P.Fault localization with nearest neighbor queries[A].Proceedings of the 18th IEEE International Conference on Automated Software Engineering[C].New York,USA:ACM,2003.30-39.

曹鶴玲 女，1980年5月出生于河南南陽(yáng).中國(guó)礦業(yè)大學(xué)博士生，CCF會(huì)員.主要研究領(lǐng)域?yàn)檐浖治雠c測(cè)試、數(shù)據(jù)挖掘.

E-mail:caohl410@cumt.edu.cn

姜淑娟(通信作者) 女，1966年12月出生于山東萊陽(yáng).現(xiàn)為中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院教授、博士生導(dǎo)師，CCF會(huì)員.主要研究領(lǐng)域?yàn)榫幾g技術(shù)、軟件工程等.

E-mail:shjjiang@cumt.edu.cn

Identifying Coincidental Correctness for Effective Fault Localization

CAO He-ling1,2,3,JIANG Shu-juan1,WANG Xing-ya1,XUE Meng1,QIAN Jun-yan3

(1.SchoolofComputerScienceandTechnology,ChinaUniversityofMiningandTechnology,Xuzhou,Jiangshu221116,China; 2.CollegeofInformationScienceandEngineering,HenanUniversityofTechnology,Zhengzhou,Henan450001,China; 3.GuangxiKeyLaboratoryofTrustedSoftware,GuilinUniversityofElectronicTechnology,Guilin,Guangxi541004,China)

Fault localization is one of the most time-consuming activities in software debugging.An identifying coincidental correctness approach for effective fault localization is proposed to decrease the effect of coincidental correctness on the effectiveness of fault localization.First,the elements of coincidental correctness are computed.Second,the higher suspicious coincidental correctness elements are selected as feature elements of coincidental correctness,and then program execution traces are reduced in terms of feature elements.Finally,fuzzyc-means based coincidental correctness identification model is created based on the reduced execution traces to locate faults.It was applied to analyze three groups of programs,and test cases removing coincidental correctness were used as input for four popular fault localization approaches,such as Tarantula.The experimental results show that our approach had low false positives and false negatives,and performed well in terms of the effectiveness.

software debugging;fault localization;coincidental correctness;clustering

2015-03-19;

2015-08-19;責(zé)任編輯：覃懷銀

國(guó)家自然科學(xué)基金(No.61202006，No.61340037，No.61502497，No.61562015,No.61602154);廣西可信軟件重點(diǎn)實(shí)驗(yàn)室研究課題資助(No.kx201616,No.kx201532);河南省高等學(xué)校重點(diǎn)科研項(xiàng)目計(jì)劃資助(No.16A520005)

TP311

A

0372-2112 (2016)12-3026-06

??學(xué)報(bào)URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.12.030