面向有效錯誤定位的偶然正確性識別方法

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

(1.中國礦業(yè)大學計算機科學與技術學院,江蘇徐州 221116； 2.河南工業(yè)大學信息科學與工程學院,河南鄭州 450001；3.桂林電子科技大學廣西可信軟件重點實驗室,廣西桂林 541004)

面向有效錯誤定位的偶然正確性識別方法

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

(1.中國礦業(yè)大學計算機科學與技術學院,江蘇徐州 221116； 2.河南工業(yè)大學信息科學與工程學院,河南鄭州 450001；3.桂林電子科技大學廣西可信軟件重點實驗室,廣西桂林 541004)

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

軟件調試；錯誤定位；偶然正確性；聚類分析

1 引言

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

針對偶然性正確問題，Wang等人[4]假設調試人員能預先知道程序缺陷類型，對錯誤觸發(fā)前后的控制流和數據流信息與特定模式匹配，提純代碼覆蓋信息，從而移除偶然正確性對錯誤定位效率的不利影響.Bandyopadhyay[5]根據成功測試用例和失敗測試用例的相似度來識別偶然正確性，并賦予偶然正確性測試用例較低的權重，進而根據測試用例的權重而不是測試用例數量來計算程序語句的懷疑度，減少偶然正確性對錯誤定位效率的影響.陳振宇等人[6]對程序覆蓋信息進行聚類分析，將和失敗測試用例在同一簇中的成功測試用例視為可能的偶然正確性測試用例，通過移除偶然正確性測試用例來減少其影響.上述研究可以顯著提高錯誤定位的效率，這促使我們去研究更有效率的偶然正確性識別方法.

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

本文貢獻在于：

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

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

2 預備知識

2.1 偶然正確性

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

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

(1)

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

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

(2)

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

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

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

表1 偶然正確性示例

2.2 模糊c均值聚類

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

(3)

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

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

(4)

且滿足下列等式：

(5)

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

(6)

(7)

3 本文方法

3.1 方法概述

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

該模型主要步驟如下：

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

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

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

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

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

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

3.2 算法

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

算法1 基于Fuzzyc-means聚類的偶然正確性測試用例識別算法

輸入：k； //聚類的簇數k=2

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

m； //聚類迭代次數最大值

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

ε； //聚類分析終止閾值，ε>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 實驗評估

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

4.1 實驗對象

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

表2 實驗對象

4.2 評測指標

(1)漏報率(False Negatives,FN).主要用于評估某種方法未準確識別偶然正確性測試用例的比率[7]，見式(8)，其中，true CC NO.表示的是真實的偶然正確測試用例數，CC identifed NO.表示的是通過聚類分析技術判別出來的偶然正確性測試用例數.

(8)

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

(9)

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

(10)

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

(11)

4.3 實驗評估

為評估方法有效性，進行以下3個方面的實驗.

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

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

(2)識別偶然正確性的誤報率(FN)和漏報率(FP)

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

表3 平均誤報率和漏報率

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

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

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

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

表4 去除偶然正確性前后各錯誤定位方法的錯誤定位代價

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

5 結論

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

[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è)大學博士生，CCF會員.主要研究領域為軟件分析與測試、數據挖掘.

E-mail:caohl410@cumt.edu.cn

姜淑娟(通信作者) 女，1966年12月出生于山東萊陽.現為中國礦業(yè)大學計算機科學與技術學院教授、博士生導師，CCF會員.主要研究領域為編譯技術、軟件工程等.

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;責任編輯：覃懷銀

國家自然科學基金(No.61202006，No.61340037，No.61502497，No.61562015,No.61602154);廣西可信軟件重點實驗室研究課題資助(No.kx201616,No.kx201532);河南省高等學校重點科研項目計劃資助(No.16A520005)

TP311

A

0372-2112 (2016)12-3026-06

??學報URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.12.030