黃小紅

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093)

基于路徑聚類分析的代碼缺陷定位研究

黃小紅

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093)

基于路徑分析的代碼缺陷定位所使用的方法通常分為兩類：基于路徑軌跡相似性分析的方法和基于路徑元素信息統(tǒng)計(jì)的方法。通過理論分析以及實(shí)際環(huán)境中的應(yīng)用，發(fā)現(xiàn)兩類方法有以下不足：冗余路徑的存在降低了整體定位效率；源代碼一般包含了大量對(duì)定位沒有意義的謂詞和語句，對(duì)這些無意義元素的統(tǒng)計(jì)不僅耗時(shí)耗力，而且會(huì)影響定位效率和精度。因此，提出基于路徑聚類分析的模糊聚類算法Pbtc。實(shí)驗(yàn)結(jié)果表明，該方法在一定程度上能夠提高代碼缺陷定位的效率和精度。

路徑特征；聚類算法；路徑差異；代碼缺陷定位

0 引言

近年來軟件開發(fā)工作取得了較大進(jìn)展，人們?cè)谲浖こ虒W(xué)中對(duì)軟件的開發(fā)以及維護(hù)投入了大量成本[1]，因此需要研究一些新方法來降低軟件調(diào)試成本。代碼缺陷定位和缺陷修復(fù)是程序調(diào)試過程中的兩個(gè)主要階段，相對(duì)于缺陷修復(fù)，代碼缺陷定位更為重要，只有準(zhǔn)確定位到缺陷位置才能順利將其修復(fù)。因此，如何開發(fā)出快速高效的代碼缺陷定位技術(shù)，該研究對(duì)于軟件行業(yè)的發(fā)展具有重要意義。

基于聚類分析的動(dòng)態(tài)代碼缺陷定位(Clustering Based Dynamic Fault Localization，簡稱CFL)是動(dòng)態(tài)代碼缺陷定位的重要方法。DFL的原理是通過跟蹤分析測試用例的執(zhí)行路徑信息，找到與失敗路徑最為相似的成功路徑，然后通過二者差異分析，快速定位到可疑程序位置。

基于路徑的研究已有大量成果，但仍有不足之處：①冗余路徑的存在對(duì)代碼缺陷定位幾乎無價(jià)值；②對(duì)源代碼中大量無貢獻(xiàn)意義的謂詞和語句的統(tǒng)計(jì)耗時(shí)耗力。因此本文提出新的路徑聚類算法，該算法通過去除冗余路徑，得到執(zhí)行失敗路徑與成功路徑代表，然后對(duì)兩條代表路徑作差異分析計(jì)算，最后針對(duì)差異分析生成缺陷可疑度排名報(bào)告。通過實(shí)驗(yàn)分析以及與經(jīng)典實(shí)驗(yàn)的對(duì)比可以證實(shí)，本文方法能夠提高代碼缺陷定位的效率和精確度。

1 相關(guān)工作

基于路徑分析的方法是當(dāng)前軟件代碼缺陷定位方法中的一類重要方法[2-5]?；诼窂杰壽E相似性的方法主要通過找到與執(zhí)行失敗用例路徑最接近的執(zhí)行成功路徑，然后通過計(jì)算統(tǒng)計(jì)差異信息進(jìn)行代碼缺陷定位。該方法的典型研究成果是Renieris等[6]提出的“最近鄰模型”。

基于路徑元素特征信息統(tǒng)計(jì)的方法通過統(tǒng)計(jì)兩種路徑(執(zhí)行失敗路徑和與失敗路徑最接近的成功路徑)對(duì)應(yīng)的程序元素信息，定位到缺陷相關(guān)語句或直接定位到缺陷準(zhǔn)確存在的語句。Tarantula、CBI、SOBE方法都是比較有代表性的基于元素特征統(tǒng)計(jì)的方法。三者在一定程度上都能達(dá)到代碼缺陷定位的目的，但不能被所有程序通用，有一定局限性。

近年來通過對(duì)基于聚類分析的方法的探究，學(xué)者們已經(jīng)取得了許多研究成果。Renieris[2]提出了“近鄰模型”策略；Yates[7]提出了“謂詞最少化”策略；Bertolino[8]提出了“控制流分析”策略；Agrawal[9]提出統(tǒng)計(jì)執(zhí)行失敗與執(zhí)行成功路徑程序切片的策略；Wong[10]在Agrawal基礎(chǔ)上提出改進(jìn)的執(zhí)行路徑切片以及內(nèi)嵌數(shù)據(jù)依賴分析的策略。本文在路徑篩選時(shí)引進(jìn)了聚類分析技術(shù)，把現(xiàn)有的聚類分析技術(shù)運(yùn)用到路徑篩選中，并且對(duì)原有技術(shù)加以改進(jìn)，以適應(yīng)路徑分析的特殊性。

2 基本概念

以下為本文展示的一個(gè)示例程序，該程序是求3個(gè)數(shù)的最大值，S8是缺陷所在位置。借助該程序，將從以下角度闡述本文的研究動(dòng)機(jī)：如果從人的角度出發(fā)，定位到基本分支塊即可找到問題所在，從而省去對(duì)大量謂詞、語句的無意義統(tǒng)計(jì)，是否可以更高效；把路徑執(zhí)行的次數(shù)和順序信息加入定位考慮范圍內(nèi)，是否可以更加快速精確。

/* S8是錯(cuò)誤的.正確的應(yīng)該是:a>max; */

#include

#include

#define N 3

S1int main(){

S2int i,a;

S3int max;

S4scanf(＂%d”,&a);

S5max=a;

S6for(i=0;i

S7scanf(＂%d＂,&a);

S8if(a<=max)

S9max=a;}

S10printf(＂max=%d＂,max);

S11return 0;}

本文涉及以下幾個(gè)概念：

定義1：路徑覆蓋向量(PV)，即程序在對(duì)應(yīng)測試用例下動(dòng)態(tài)執(zhí)行時(shí)所有運(yùn)行步驟對(duì)語句的覆蓋情況。程序每一步執(zhí)行覆蓋到的語句組成一個(gè)集合，記為路徑覆蓋向量。不僅考慮語句覆蓋信息，而且還考慮語句的執(zhí)行順序以及執(zhí)行次數(shù)。以測試用例(5,4,3)為例，其路徑覆蓋向量為：{1,2,3,4,5,6,7,8,9,6,7,8,9,6,10,11}。

定義2：路徑分支執(zhí)行序列(PBS)。測試用例動(dòng)態(tài)執(zhí)行時(shí)各路徑分支語句執(zhí)行狀態(tài)的集合。

設(shè)Bi是程序P中的第i個(gè)分支，一個(gè)測試用例執(zhí)行結(jié)束后，該條路徑對(duì)應(yīng)的分支執(zhí)行序列由Bi的執(zhí)行順序和執(zhí)行次數(shù)所唯一表示。如示例程序的執(zhí)行情況所示，語句6和語句8為執(zhí)行路徑的分支語句；以測試用例(5,4,3)為例，其路徑分支執(zhí)行序列表示為：{6,8,6,8,6}。

定義3：路徑分支軌跡特征(BC)。路徑分支軌跡特征由路徑分支執(zhí)行序列中路徑分支動(dòng)態(tài)運(yùn)行之后各路徑分支取真和取假的個(gè)數(shù)決定。

如示例程序的執(zhí)行情況所示，以測試用例(5,4,3)為例，其路徑分支分別為S6和S8，其中S6共執(zhí)行3次，取值分別為“真真假”，則BCS6=2/3；S8共執(zhí)行2次，取值分別為“真真”，則BCS8=1。

定義4：路徑執(zhí)行軌跡矩陣(PM)。PM用m*(n+1)階矩陣表示。矩陣元素PMij(1≤i≤m,1<≤j≤n)表示程序P在執(zhí)行第i個(gè)測試用例時(shí)，第j個(gè)分支的路徑分支軌跡特征值BCi。m為本次路徑執(zhí)行所用的測試用例總數(shù)，n為本次路徑執(zhí)行軌跡包含的分支總數(shù)。

路徑分支軌跡特征向量BV構(gòu)成矩陣PM的行，路徑的分支構(gòu)成矩陣的列。第n+1列表示該條測試用例的執(zhí)行結(jié)果，若執(zhí)行成功，則PMi(n+1)=1；若執(zhí)行失敗，則PMi(n+1)=0。如示例程序的執(zhí)行情況所示，若干測試用例執(zhí)行后，該程序路徑執(zhí)行軌跡矩陣如下：

3 基于聚類分析的計(jì)算方法

本文解決的主要問題是如何通過聚類分析實(shí)現(xiàn)代碼缺陷定位，本節(jié)首先給出路徑分支軌跡模糊聚類的算法，然后根據(jù)聚類結(jié)果得到的最優(yōu)成功代表集和最優(yōu)失敗代表集給出路徑差異對(duì)比分析的方法，最后介紹了差異統(tǒng)計(jì)代碼缺陷定位的實(shí)現(xiàn)方法。

3.1 路徑聚類算法

路徑分支軌跡模糊聚類算法是在模糊C均值算法基礎(chǔ)上對(duì)傳統(tǒng)等劃分缺陷進(jìn)行改進(jìn)，在歐式距離度量中使用了調(diào)節(jié)因子，提出一種基于分支路徑特征改進(jìn)的矩陣方法代替?zhèn)鹘y(tǒng)距離度量矩陣。

成功執(zhí)行路徑聚類時(shí)樣本集為PMs，失敗執(zhí)行路徑聚類時(shí)樣本集為PMf，本節(jié)以成功執(zhí)行路徑聚類PMs為例進(jìn)行詳細(xì)說明，對(duì)PMf作聚類分析時(shí)原理相同。將待聚類矩陣PMs= {PMs1，PMs2，…，PMsn}作為一個(gè)給定的聚類樣本集，本文將用U(PMs)表示它的分塊矩陣，按照特定規(guī)則把PMs劃分為c個(gè)聚類子集Fi(F1，F(xiàn)2，…，F(xiàn)c)，c表示聚類數(shù)目，每個(gè)分塊矩陣c×n的大小可以表示為P=[μij]c*n ,i=1,2...c，j=1,2...n，μij∈[0,1]。用V= {v1，v2，…，vc} 表示c個(gè)子集的聚類中心，μFi(PMsj)表示PMsj對(duì)Fi的隸屬度。

聚類算法的優(yōu)化目標(biāo)函數(shù)為:

(1)

其中‖PMsj-vi‖表示PMsj和vi的歐式距離,變量m用于控制矩陣的模糊程度。在實(shí)際應(yīng)用場景中，m值的最佳取值范圍為(1.5,2.5)[11-12]。本文經(jīng)實(shí)驗(yàn)驗(yàn)證，在路徑聚類中取1.8。

步驟1：初始化矩陣PMs=[μij]c*n，PMs∈Fi，設(shè)誤差值為θ，得到以下公式：

(2)

步驟2：計(jì)算模糊聚類中心：

(3)

步驟3：算法迭代操作。該聚類算法停止迭代的條件是：Jm<θ。如果Jm<θ，則認(rèn)為函數(shù)已收斂，可以得到需求的聚類子集，否則繼續(xù)執(zhí)行步驟2。

步驟4：分別得到成功路徑和失敗路徑代表集作差異分析。

步驟5：得到缺陷可疑度排名。

3.2 可疑度分析

由于Abreu等[13]提出的Jaccard方法是受聚類分析方法啟發(fā)而來，而本文正是基于路徑分支軌跡聚類分析的基礎(chǔ)進(jìn)行代碼缺陷定位研究，因此選擇Jaccard可疑度計(jì)算公式作為可疑度分析比較有研究意義。該公式如下：

(4)

其中，nef(si)為語句si被覆蓋且執(zhí)行失敗的測試用例個(gè)數(shù)，nep(si)為語句si被覆蓋且執(zhí)行成功的測試用例個(gè)數(shù)，nf為所有執(zhí)行失敗的測試用例總數(shù)。

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

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

為了直觀地與其它代碼缺陷定位方法的優(yōu)劣作對(duì)比，本文使用國內(nèi)外比較有權(quán)威的Siemens程序組件進(jìn)行實(shí)驗(yàn)分析,試驗(yàn)程序的基本信息如表1所示。

表1 試驗(yàn)程序基本信息

4.2 實(shí)驗(yàn)步驟

本文在Ubuntu環(huán)境下使用GCC4.7.0編譯器對(duì)所選取的各個(gè)西門子組件版本進(jìn)行編譯處理，然后使用gcov組件記錄各條語句執(zhí)行情況，最后在VS 2010平臺(tái)下編寫算法進(jìn)行實(shí)驗(yàn)。

實(shí)驗(yàn)具體流程如下：①使用gcc對(duì)西門子組件的各個(gè)版本作編譯處理；②使用gcov組件記錄各條語句執(zhí)行情況，對(duì)測試用例的執(zhí)行軌跡進(jìn)行收集存儲(chǔ)；③執(zhí)行Pbtc、Tarantula、Ochiai、Jaccard和Wong五種經(jīng)典的可疑度算法，使用收集的用例執(zhí)行信息分別對(duì)程序作可疑度排名；④計(jì)算5種算法下該程序版本缺陷所在基本分支塊的排名，以及為了找到缺陷所在位置需要檢查的代碼數(shù)占總代碼數(shù)的百分比；⑤根據(jù)得到的數(shù)據(jù)，比較上述5種可疑度排序算法的性能。

4.3 實(shí)驗(yàn)結(jié)果及分析

通過Siemens程序集中Printtokens2程序的具體運(yùn)行給出實(shí)驗(yàn)結(jié)果分析。數(shù)據(jù)取自Printtokens2中的版本4，共運(yùn)行了4 115個(gè)有效測試用例，實(shí)驗(yàn)結(jié)果如表2所示。已知版本4的缺陷存在于S355。

表2 缺陷位置排序

執(zhí)行Pbtc算法后得到基本塊可疑度的排序結(jié)果。表2還給出了執(zhí)行Tarantula、Ochiai、Jaccard和Wong算法后得出的基本分支塊可疑度排序結(jié)果。

從5種缺陷定位算法的實(shí)驗(yàn)結(jié)果可以看出，本實(shí)驗(yàn)方法可以準(zhǔn)確定位出缺陷所在位置S355。Tarantula方法和Wong方法將該位置排到第2位；Ochiai和Jaccard方法均將缺陷位置排到第5位。本文在對(duì)Siemens其它6個(gè)程序集的定位試驗(yàn)中發(fā)現(xiàn)，本文方法對(duì)程序中90%以上的缺陷定位效果都比較明顯，在給出的缺陷位置序列中，90%以上缺陷被排列到前3位的平均概率為88%，而其它4種對(duì)應(yīng)的概率分別為65%、73%、81%和80%。因此，本實(shí)驗(yàn)方法在對(duì)缺陷的定位中是有效且準(zhǔn)確的。

5 結(jié)語

基于聚類分析的代碼缺陷定位方法已日趨成熟。本文通過對(duì)各種定位方法的研究，提出一種基于聚類分析的路徑聚類算法Pbtc。Pbtc算法從人的角度出發(fā)，以分支基本塊為粒度劃分待定位程序，通過程序動(dòng)態(tài)執(zhí)行過程中路徑分支的執(zhí)行次數(shù)和執(zhí)行順序進(jìn)行統(tǒng)計(jì)計(jì)算，并利用算法Pbtc去除冗余路徑，篩選出重要信息，最后通過差異分析對(duì)比得到缺陷可疑度排名報(bào)告。該方法一定程度上提高了軟件代碼缺陷定位的精度，并且大大提高了定位效率和資源利用率。

但是本文實(shí)驗(yàn)仍有不足，西門子程序集具有代表意義，但是版本過少，實(shí)驗(yàn)中植入的缺陷比較簡單，而在實(shí)際應(yīng)用中可能較為復(fù)雜。因此，后續(xù)將在實(shí)際應(yīng)用中考驗(yàn)本文方法的可行性，并通過不斷改進(jìn)，使代碼缺陷定位方法更加智能、精確。

[1] JAMES ARTHUR JONES.Empirical evaluation of the tarantula automatic fault-localization technique[C].Proceeding of the 20th IEEE/ACM International Conference on Automated Software Engineering,2005:273-282.

[2] BEN LIBIT,MAYUR NAIK,ALICE X.Scalable statistical bug isolation[C].Proceedings of the 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation,2005:15-26.

[3] ZHANG LI,CAI MING,CHAI HUI.Improvement of relevant predicate evaluation bias method for sober-based fault localization[J].Journal of Fudan University (Natural Science),2009,48(6):815-822.

[4] LIANG GUO,ABHIK ROYCHOUDHURY,TAO WANG.Accurately choosing execution runs for software fault localization[C].Compiler Construction.International Conference, 2006:80-95.

[5] STEVEV P REISS,MANOS RENIERIS.Encoding program executions[J].IEEE Computer Society,2001:221-230.

[6] STEVEV P REISS,MANOS RENIERIS.Fault localization with nearest neighbor queries [C].18th IEEE International Conference on Automated Software Engineering,2003:30-39.

[7] D YATES,N MALEVRIS VENUE.Reducing the effects of infeasible paths in branch testing[J].ACM SIGSOFT Software Engineering Notes,1989,14(8):48-54.

[8] A BERTOLINO,M MARRE.Automatic generation of path covers based on the control flow analysis of computer programs[J].IEEE Transactions on Software Engineering, 1994,20(12):885-899.

[9] H AGRAWAL,J R HORGAN,S LONDON,et al.Fault localization using execution slices and data-flow test[C].In the Proceedings of the 6th International Symposium on Software Reliability Engineering,1995:143-151.

[10] W E WONG,Y QI.Effective program debugging based on execution slices and inter-block data dependency[J].The Journal of System and Software,2006:891-903.

[11] JIAN YU,QIANSHENG CHENG,HOUKUAN HUANG.Analysis of the weighting exponent in the FCM[J].IEEE Transactions on System，Man and Cybernetics,2004，34(1):634-639．

[12] 肖滿生,陽娣蘭，張居武，等.基于模糊相關(guān)度的模糊C均值聚類加權(quán)指數(shù)研究[J]．計(jì)算機(jī)應(yīng)用,2010,30(12):3388-3390.

[13] BIRGIT HOFER,ALEXANDRE PEREZ,RUI ABREU,et al.An evaluation of similarity coefficients for software fault localization[J].Pacific Rim International Symposium on Dependab Computing,2006.

(責(zé)任編輯：黃 健)

Fault Localization Method Based on Path Clustering

Similar path analysis method and statistical method based on the element information are two basic methods for program fault localization.Through theoretical and environmental analyzing of the above two methods, we found the they have the following problems: the existence of the redundant path will reduce the efficiency of the overall localization;statistical method based on the element information consider the suspicious degree rank of predicate or statements, but the program generally includes plenty of predicate and statement which have no contribution to fault localization,this method ignore the meaningless elements time-consuming statistics.To solve the above problems, path clustering is added to the algorithm,so a fault localization algorithm Pbtc is provided. In this paper,we build experiment based on theoretical research.By comparing with three other classic fault localization methods,the effectiveness of the proposed method is verified in improving the accuracy of the fault localization.

Path Characteristics;Clustering Algorithm;Path Difference;Fault Localization

黃小紅(1989-)，女，河南平頂山人，上海理工大學(xué)光電信息與計(jì)算機(jī)工程學(xué)院碩士研究生，研究方向?yàn)檐浖こ?、缺陷定位?/p>

10.11907/rjdk.161813

TP301

A

1672-7800(2017)003-0003-04