黃小紅

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

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

黃小紅

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

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

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

0 引言

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

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

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

1 相關工作

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

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

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

2 基本概念

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

/* S8是錯誤的.正確的應該是: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;}

本文涉及以下幾個概念：

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

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

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

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

如示例程序的執(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個測試用例時，第j個分支的路徑分支軌跡特征值BCi。m為本次路徑執(zhí)行所用的測試用例總數，n為本次路徑執(zhí)行軌跡包含的分支總數。

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

3 基于聚類分析的計算方法

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

3.1 路徑聚類算法

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

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

聚類算法的優(yōu)化目標函數為:

(1)

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

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

(2)

步驟2：計算模糊聚類中心：

(3)

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

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

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

3.2 可疑度分析

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

(4)

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

4 實驗

4.1 實驗對象

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

表1 試驗程序基本信息

4.2 實驗步驟

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

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

4.3 實驗結果及分析

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

表2 缺陷位置排序

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

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

5 結語

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

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

[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] 肖滿生,陽娣蘭，張居武，等.基于模糊相關度的模糊C均值聚類加權指數研究[J]．計算機應用,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.

(責任編輯：黃 健)

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-)，女，河南平頂山人，上海理工大學光電信息與計算機工程學院碩士研究生，研究方向為軟件工程、缺陷定位。

10.11907/rjdk.161813

TP301

A

1672-7800(2017)003-0003-04