陸 凱，姜淑娟,2+，王興亞

1.中國礦業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 徐州 221116

2.桂林電子科技大學(xué) 廣西可信軟件重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004

1 引言

現(xiàn)代工業(yè)中軟件的可靠性已經(jīng)越來越得到人們的重視，而為此花費(fèi)的代價(jià)約占軟件開發(fā)和維護(hù)成本的50%～75%[1]。自動化錯誤定位技術(shù)可以有效減少軟件調(diào)試的時(shí)間和人力消耗，提高軟件質(zhì)量。

目前的軟件錯誤定位方法按照定位過程是否需要運(yùn)行軟件劃分為兩大類，分別是基于靜態(tài)分析的故障定位和基于測試的故障定位[2]。靜態(tài)分析能夠及早地發(fā)現(xiàn)和定位軟件錯誤，減少維護(hù)成本，而且基于靜態(tài)分析的方法理論知識完備，已經(jīng)開發(fā)了一些商用或開源靜態(tài)分析工具（如JLINT、PMD、FindBugs等）。基于測試的故障定位方法主要通過運(yùn)行測試用例得到程序的執(zhí)行信息，對程序的執(zhí)行過程和結(jié)果進(jìn)行跟蹤和分析，從而進(jìn)行錯誤定位。這類方法主要有 Tarantula方法[3]、SOBER方法[4-5]、Delta Debugging方法[6]等。通常軟件錯誤定位的方法有3種定位精度，分別是類、方法和語句級別。上述大多數(shù)方法具有良好覆蓋的測試用例，通過對測試結(jié)果和程序行為特征進(jìn)行分析最終得出一個按照可疑值降序排列的語句排序結(jié)果，指導(dǎo)開發(fā)人員對錯誤進(jìn)行修復(fù)。然而最終的可疑語句列表缺少相關(guān)的上下文信息，開發(fā)人員不了解其中關(guān)聯(lián)性，給錯誤定位造成一定困難。

本文在方法粒度上，通過對一定數(shù)量的執(zhí)行軌跡和執(zhí)行結(jié)果進(jìn)行分析，提供可能包含錯誤的方法集合，從而完成錯誤定位。本文結(jié)合機(jī)器學(xué)習(xí)，對加權(quán)的軟件調(diào)用圖進(jìn)行研究。

2 相關(guān)工作

在軟件故障定位技術(shù)中，近年來研究人員利用圖挖掘技術(shù)提出了很多錯誤定位方法。Baah等人[7]對執(zhí)行程序的控制依賴和數(shù)據(jù)依賴進(jìn)行分析，在程序依賴圖的基礎(chǔ)上通過執(zhí)行測試得到概率程序依賴圖，從而對錯誤進(jìn)行定位和理解。Cheng等人[8]提出了LEAP方法，該方法首先獲得程序執(zhí)行路徑構(gòu)造加權(quán)軟件行為圖，再通過LEAP圖挖掘算法，使用信息增益作為目標(biāo)函數(shù)，從所有軟件行為圖中挖掘出Top-K個在失敗執(zhí)行中頻繁出現(xiàn)，而在正確執(zhí)行中較少出現(xiàn)的子圖，作為可疑語句序列。該方法能夠挖掘出與錯誤相關(guān)的上下文信息，幫助開發(fā)人員定位和理解軟件錯誤。然而存在的不足之處是軟件行為圖中所有控制流路徑具有相同的重要程度，未考慮執(zhí)行次數(shù)對軟件行為圖的影響。Eichinger等人[9]采用圖挖掘技術(shù)，提出了一種基于權(quán)重的錯誤定位方法，該方法在方法級別進(jìn)行錯誤定位，按照可疑度從高到低給出可疑方法序列，可以解決較為復(fù)雜的錯誤定位問題。該方法使用信息增益作為方法懷疑度排名的度量標(biāo)準(zhǔn)，但沒有考慮信息增益的內(nèi)在偏置，同時(shí)未考慮方法之間的關(guān)聯(lián)性。Liu等人[10]應(yīng)用支持向量機(jī)以封閉子圖為特征對所有執(zhí)行分類，并通過分類精度的變化度量方法的可疑度，最終生成一個可疑方法集合幫助開發(fā)人員判斷錯誤位置，然而未考慮程序中頻繁執(zhí)行方法的影響。針對這些問題，本文利用加權(quán)的軟件調(diào)用圖，運(yùn)用支持向量機(jī)進(jìn)行錯誤定位。

3 技術(shù)背景

3.1 圖挖掘技術(shù)

圖是最常用的數(shù)據(jù)結(jié)構(gòu)之一，描述事物之間的復(fù)雜關(guān)系，對其進(jìn)行挖掘能夠得到很多潛在信息，將圖挖掘技術(shù)與錯誤定位結(jié)合已經(jīng)成為研究熱點(diǎn)。

頻繁子圖挖掘是圖挖掘中一個研究熱點(diǎn)，它是從大量的圖中挖掘出一些滿足給定支持度的頻繁圖，當(dāng)一個子圖在整個圖集合中出現(xiàn)的比率滿足指定的支持度，那么這個子圖就是頻繁子圖。傳統(tǒng)的頻繁子圖挖掘算法有 AGM（Apriori-based graph mining）[11]、FSG（frequent subgraph）[12]、gSpan[13]和 CloseGraph[14]。

AGM[11]和FSG[12]挖掘算法都是基于Apriori思想的頻繁結(jié)構(gòu)挖掘方法，AGM[11]采用寬度優(yōu)先搜索（breadth first search，BFS），逐步增加節(jié)點(diǎn)擴(kuò)展子結(jié)構(gòu)逐層產(chǎn)生候選子圖。FSG[12]改進(jìn)了AGM[11]每次添加邊加強(qiáng)剪枝，采取優(yōu)化措施計(jì)算支持度，提高執(zhí)行效率。然而這兩種挖掘算法系統(tǒng)開銷大，不夠靈活。

gSpan[13]和CloseGraph[14]都是基于模式增長的頻繁結(jié)構(gòu)挖掘算法，采用深度優(yōu)先搜索策略，逐步生成擴(kuò)展圖，與gSpan[13]算法相比，CloseGraph[14]算法減少了不必要的子圖生成，避免了子圖同構(gòu)，挖掘出封閉子圖，有效減少冗余，效率更高。

3.2 支持向量機(jī)

支持向量機(jī)（SVM）是AT&TBell實(shí)驗(yàn)室的Vapnik等人提出的一種全新機(jī)器學(xué)習(xí)算法。到目前為止，支持向量機(jī)廣泛應(yīng)用于性別分類、基因分類、數(shù)據(jù)挖掘、非線性系統(tǒng)控制等各個領(lǐng)域的實(shí)際問題中。

SVM的主要思想是針對兩類分類問題，把訓(xùn)練數(shù)據(jù)集非線性映射到一個高維特征空間，隨后在特征空間尋找一個最優(yōu)分隔超平面。在線性可分的情況下，存在一個或多個超平面使得訓(xùn)練樣本完全分開，SVM的目標(biāo)是找到其中的最優(yōu)超平面，最優(yōu)超平面是使得每一類數(shù)據(jù)與超平面距離最近的向量與超平面之間的距離最大的平面。

支持向量機(jī)能夠?qū)τ邢迾颖具M(jìn)行分類，將其與錯誤定位結(jié)合提出一種錯誤定位方法有一定的研究意義。

4 本文方法

4.1 方法概述

為待測程序插樁，運(yùn)行相應(yīng)測試用例監(jiān)控程序執(zhí)行，獲取正確和錯誤用例的執(zhí)行軌跡，將其作為下一步錯誤定位的基礎(chǔ)。本文方法框架如圖1所示。

（1）加權(quán)行為圖構(gòu)建。將收集的程序執(zhí)行軌跡建模成程序調(diào)用關(guān)系圖，對初始調(diào)用圖集合進(jìn)行約簡，得到加權(quán)調(diào)用圖集合。

（2）封閉子圖挖掘。對調(diào)用圖集合進(jìn)行封閉子圖挖掘，提取封閉子圖或者頻繁邊作為特征，記錄每個調(diào)用圖包含的頻繁邊信息。

（3）以頻繁邊或封閉子圖作為特征，訓(xùn)練建立支持向量機(jī)對所有執(zhí)行分類，記錄每個方法的分類結(jié)果。

（4）分析分類結(jié)果，當(dāng)加入某個方法精度明顯提升時(shí)把該方法加入可疑方法集合。

（5）將可疑方法集合提供給開發(fā)人員判斷錯誤位置并修復(fù)。

Fig.1 Framework of fault localization of combining graph mining and SVM圖1 結(jié)合圖挖掘和支持向量機(jī)的錯誤定位框架

4.2 加權(quán)行為圖構(gòu)建

本文首先實(shí)現(xiàn)方法級別的程序插樁，跟蹤執(zhí)行程序中方法的執(zhí)行信息，通過獲取程序的執(zhí)行路徑得到進(jìn)行圖挖掘的原始圖集合，對圖集合進(jìn)行約簡去除冗余的數(shù)據(jù)，然后在圖集合中挖掘封閉子圖提取頻繁邊，為下一步以頻繁邊為特征訓(xùn)練SVM分類器做準(zhǔn)備。最初得到的軟件調(diào)用圖只包含了方法的調(diào)用信息，而忽視了程序執(zhí)行的統(tǒng)計(jì)信息，因而在此基礎(chǔ)上，需要約簡圖集合，將無權(quán)的圖轉(zhuǎn)化為帶權(quán)值的圖。Liu等人[10]采用了總約簡方法，刪去了圖的所有重邊，使得整個圖更加簡單，然而忽略了方法的調(diào)用次數(shù)，對圖壓縮過于嚴(yán)重，失去了大量信息。Di Fatta等人[15]提出了無序迭代約簡方法，保留了多次執(zhí)行的圖的子結(jié)構(gòu)，與總約簡方法相比包含了更多的信息，但會出現(xiàn)圖重構(gòu)，圖的尺寸也更加龐大。Eichinger等人[16]提出了子樹約簡方法，只保留圖中一個執(zhí)行的子結(jié)構(gòu)，在邊上記錄相同的同構(gòu)子結(jié)構(gòu)調(diào)用次數(shù)作為權(quán)值，將無權(quán)圖轉(zhuǎn)化為帶權(quán)圖，與無序迭代約簡相比，得到的圖尺寸更小。綜上所述本文采用子樹約簡方法對圖集合進(jìn)行約簡，獲得更加簡潔的帶權(quán)值的調(diào)用圖。

子樹約簡方法采用的策略是自底向上逐層約簡該層的相同邊，如算法1所示，該算法以未約簡的n層調(diào)用圖為輸入，以約簡后的調(diào)用圖作為輸出。該算法主要分兩步：第1步，刪除該層重邊，僅僅保留一條邊，同時(shí)將重邊的數(shù)目作為邊的權(quán)值。當(dāng)某一條邊的數(shù)目只有一條時(shí)，該邊的權(quán)值設(shè)為1。第2步，對邊進(jìn)行約簡的同時(shí)，刪除相同的子節(jié)點(diǎn)。不斷重復(fù)直到約簡到頂層。圖2為子樹約簡方法的實(shí)例，（a）為未約簡圖，（b）為子樹約簡后的圖。

算法1子樹約簡算法

輸入：n層調(diào)用圖。

輸出：加權(quán)調(diào)用圖。

1.for level=n-1to 1 do

2.for each node in level do

3. merge all identical child-suntrees of node,sum up corresponding edge weights

4.end for

5.end for

Fig.2 Subtree reduction example圖2 子樹約簡實(shí)例

4.3 封閉子圖挖掘

對于大型的程序，將調(diào)用圖約簡之后，程序行為圖仍具有較大的規(guī)模，難以對這些邊進(jìn)行逐一計(jì)算和分析，并且存在一些邊代表的方法沒有考慮價(jià)值。通常情況下，僅考慮在所有的圖中出現(xiàn)次數(shù)較多的邊，因此有必要對圖集合進(jìn)行特征選擇，取出出現(xiàn)次數(shù)較高的邊進(jìn)行分析，錯誤往往包含在這些邊中。

頻繁子圖挖掘是從圖集合中挖掘滿足支持度的頻繁圖，存在多種頻繁子圖挖掘算法[11-14]，考慮到CloseGraph[14]挖掘效率高且避免了子圖同構(gòu)，本文選擇CloseGraph[14]進(jìn)行子圖挖掘，CloseGraph[14]算法以DFS編碼、圖集合和最小支持度為輸入，以封閉子圖集合為輸出。該算法主要分為3步：第1步，生成一個頻繁子圖。第2步，封閉子圖判斷。根據(jù)是否存在與生成子圖有相同支持度的超圖檢查第1步生成子圖是否為封閉子圖。第3步，剪枝擴(kuò)展。檢查提前終止的條件和任何可能導(dǎo)致提前終止失敗的情況，依此決定是否擴(kuò)展生成子圖。如算法2所示。

算法2CloseGraph

輸入：A DFS codes,its parent’sp,a graph datasetD,andmin_sup.

輸出：The closed frequent graph setS.

1.ifs≠min(s),then

2.return;

3.if ?e′,g′=gp?xe′andg′

4.return;

5.setC=Null

6.ScanDonce,finding every edgeesuch thatscan be extended to frequents?xe;Inserts?xeintoC;

7.detect any possible failure of early termination ins;

8.if??s?xe∈C,support(s)support(s?xe)then;

9.insertsintoS;

10.removes?xefromCwhich cannot be right-most extended forms;

11.sortCin DFS lexicographic order;

12.for eachs?reinCdo

13.CloseGraph(s?re,s,D,min_sup,S)

14.return

在封閉子圖挖掘時(shí)，由于圖集合中圖都帶有權(quán)重，而在不同的圖中如果一條邊擁有不同的權(quán)值，則會被認(rèn)為是不同邊，得到大量的頻繁子圖。因此在進(jìn)行挖掘時(shí)排除權(quán)值的干擾，挖掘出最大的頻繁子圖，得到頻繁邊。得到頻繁邊之后將其對應(yīng)到每一個調(diào)用圖中，每個調(diào)用圖代表一次程序執(zhí)行。通過表格記錄挖掘到的所有頻繁邊，依此訓(xùn)練以頻繁邊為特征的支持向量機(jī)，如表1所示。

Table 1 Frequent sides record table表1 頻繁邊記錄表

表1記錄了封閉子圖挖掘得到的頻繁邊信息，第1列是每次程序執(zhí)行構(gòu)建的程序行為圖，最后1列是該次執(zhí)行所屬的分類，用Class表示。其余列是封閉子圖具有的頻繁邊，對應(yīng)的值為該頻繁邊代表的方法執(zhí)行的次數(shù)。

4.4 運(yùn)用支持向量機(jī)錯誤定位

支持向量機(jī)是一種監(jiān)督式學(xué)習(xí)的方法，可廣泛地應(yīng)用于統(tǒng)計(jì)分類以及回歸分析。本文利用SVM對擁有標(biāo)簽的調(diào)用圖進(jìn)行分類，當(dāng)程序中某個方法執(zhí)行后，分類器對錯誤執(zhí)行和正確執(zhí)行的分類精度提升很大，這個方法就屬于可疑方法，可能與錯誤相關(guān)?；谶@個原理，在方法的返回處訓(xùn)練一個分類器，檢測分類精度。分類步驟主要分為3步：（1）從調(diào)用圖集合中提取特征；（2）使用特征訓(xùn)練SVM分類器；（3）對調(diào)用圖進(jìn)行分類。

為了在調(diào)用圖分類中使用SVM，把所有調(diào)用圖轉(zhuǎn)化為特征向量，一般以頻繁邊或封閉子圖作為特征，每個調(diào)用圖作為特征向量。向量有0、1這兩個值，如果一個調(diào)用圖包含某個特征，那么該位的值為1，否則為0。

Liu等人[10]提出了利用SVM分類的方法，以封閉子圖為特征，對所有執(zhí)行進(jìn)行分類，當(dāng)獲得越來越多的執(zhí)行信息時(shí)，分類的精度不會減小，特別當(dāng)執(zhí)行包含錯誤的程序后，分類的精度會提升。如圖3所示。

程序中方法A、B、C按照順序執(zhí)行，方法B中包含錯誤，在方法A的返回處訓(xùn)練分類器A，對正確執(zhí)行和失敗執(zhí)行進(jìn)行分類，此時(shí)分類精度不會有大的變化。在方法B的返回處訓(xùn)練分類器B，對正確執(zhí)行和失敗執(zhí)行進(jìn)行分類，因?yàn)閳?zhí)行了包含錯誤的方法B，所以分類器B分類的精度比分類器A得到的精度高，因?yàn)榉诸惥忍嵘?，所以錯誤更加可能在方法B中。

Fig.3 Classification principle圖3 分類原理

因此，對程序中的所有方法，在方法的入口和出口設(shè)置監(jiān)測點(diǎn)，利用上文提出的分類方法在每個監(jiān)測點(diǎn)訓(xùn)練分類器，記錄每個監(jiān)測點(diǎn)的分類精度。當(dāng)某個方法使得精度明顯提升時(shí)，將這個方法加入錯誤相關(guān)方法的集合，把整個集合提供給開發(fā)人員進(jìn)行錯誤定位和修復(fù)。本文以頻繁邊為特征建立支持向量機(jī)，對所有執(zhí)行分類獲取精度對其分析，從而進(jìn)行錯誤定位。

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

5.1 實(shí)驗(yàn)建立

本文采用NanoXML數(shù)據(jù)集作為測試數(shù)據(jù)，NanoXML是一個包括7646行代碼的XML文件解析器，包括V0至V5共6個不同的版本，實(shí)驗(yàn)使用V5版本。同時(shí)在該版本中每次植入一個錯誤，這些錯誤由software-artifact infrastructure repository（SIR）提供，本文從總共9個錯誤中選擇4個不同類型與實(shí)際貼切的錯誤植入，如表2所示。

為了驗(yàn)證本文方法的有效性，以將封閉子圖作為特征分類后的結(jié)果作為實(shí)驗(yàn)對比對象。NanoXML包含了141個測試用例，由于相似的輸入可能會得出相同的程序調(diào)用圖，為了保證分類效果，本文去除了圖集合中重復(fù)的程序調(diào)用圖，對刪去重復(fù)調(diào)用圖的圖集合進(jìn)行圖挖掘獲取封閉子圖。

實(shí)驗(yàn)使用LibSVM[17]進(jìn)行分類，由于其具有簡單易使用，且快速高效的特點(diǎn)，廣泛用于解決通用的分類問題。在進(jìn)行分類時(shí)，實(shí)驗(yàn)選擇使用頻繁邊和封閉子圖作為特征，然后訓(xùn)練支持向量機(jī)進(jìn)行分類，最終得到各個方法的精度。實(shí)驗(yàn)的運(yùn)行環(huán)境是CPU Intel?Duo 2-Core 2.94 GHz；內(nèi)存 2 GB；Windows 732位操作系統(tǒng)。

Table 2 Description of implanted faults表2 植入錯誤說明

Fig.4 Classification accuracy comparison of single fault圖4 單個錯誤分類精度比較

5.2 評價(jià)標(biāo)準(zhǔn)

實(shí)驗(yàn)采用查準(zhǔn)率（Precision）和查全率（Recall）評價(jià)將頻繁邊與封閉子圖作為特征，訓(xùn)練支持向量機(jī)進(jìn)行分類的結(jié)果。Recall表示被正確分類的錯誤執(zhí)行的比率，Precision表示被分類的錯誤執(zhí)行是真正的錯誤執(zhí)行的比率。查全率越高，遺漏不正確執(zhí)行的概率越低，查準(zhǔn)率越高，正確率就越高。高查全率和高查準(zhǔn)率表示該分類特征區(qū)分正確執(zhí)行和錯誤執(zhí)行的能力越強(qiáng)。

本文使用頻繁邊作為特征訓(xùn)練支持向量機(jī)進(jìn)行分類，與已有的使用封閉子圖作為特征訓(xùn)練支持向量機(jī)進(jìn)行分類的方法進(jìn)行對比。實(shí)驗(yàn)設(shè)置進(jìn)行5次交叉驗(yàn)證，并用折線圖將每個方法的分類結(jié)果表示出來。在折線圖中，某個方法的查全率和查準(zhǔn)率越高，越趨于右上方，分類效果越好。

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

圖4給出了f1、f2和f4使用本文方法將頻繁邊作為特征和已有方法將封閉子圖作為特征的分類結(jié)果折線圖。對于f1，大多數(shù)方法使用頻繁邊作為特征分類后的精度與使用封閉子圖作為特征分類的精度相同，甚至提高了精度，查全率和查準(zhǔn)率都有提升。對于f2，使用兩種特征取得的結(jié)果相似，只有單個方法的精度變高，其他相同。f2與f3的結(jié)果相似，使用頻繁邊與封閉子圖作為特征取得了相同的結(jié)果，只有單個方法的精度改變。對于f4，大多數(shù)方法使用頻繁邊作為特征分類后的精度都有提升或不變。

圖4表明了與已有的使用封閉子圖作為特征分類的方法相比，使用頻繁邊作為特征進(jìn)行分類取得效果多數(shù)情況下都優(yōu)于使用封閉子圖作為特征分類，而且查全率和查準(zhǔn)率都有提升，這表明使用頻繁邊作為特征比封閉子圖更能提高分類質(zhì)量，提升精度。

運(yùn)行時(shí)間消耗主要是封閉子圖挖掘和訓(xùn)練SVM。提取頻繁邊和封閉子圖作為特征需要對圖集合進(jìn)行封閉子圖挖掘，本文使用的圖挖掘算法總時(shí)間復(fù)雜度為O(2n×2n)。由于頻繁邊從封閉子圖中提取，因此本文方法與已有方法進(jìn)行圖挖掘時(shí)間消耗相同。SVM時(shí)間復(fù)雜度與訓(xùn)練樣本和向量維數(shù)有關(guān)。在訓(xùn)練時(shí)間上，使用頻繁邊作為特征的向量維數(shù)比封閉子圖特征多，因此訓(xùn)練時(shí)間略多于已有方法，但本文方法與已有方法訓(xùn)練時(shí)間消耗均在0.1 s內(nèi)。

分類完成后利用上文提出的方法進(jìn)行錯誤定位，以f2為例，以一張表記錄所有方法出口與入口的分類精度，如表3所示。

Table 3 f2method classification accuracy表3 f2方法分類精度

從表3中可以看出main方法、processSpecialTag方法和processCDATA方法的分類精度明顯提高，依此認(rèn)為是可疑方法，最終將這些可疑方法提交開發(fā)人員進(jìn)行錯誤定位和修復(fù)。由于main是程序的入口，main方法進(jìn)行分類時(shí)包含了所有的執(zhí)行信息，因此main方法始終與錯誤相關(guān)。源程序執(zhí)行時(shí)所有失敗執(zhí)行都執(zhí)行了processCDATA方法。源程序執(zhí)行完processCDATA方法后執(zhí)行checkLiteral方法，checkLiteral方法的精度會降低說明分類包含了正確的執(zhí)行，由于這些方法在程序中有一定的執(zhí)行順序，因此能夠提供上下文信息，更加利于開發(fā)人員找到錯誤所在并修復(fù)。

5.4 討論

雖然實(shí)驗(yàn)結(jié)果表明本文方法在以上4種錯誤中均取得了較好的結(jié)果，但是不能表明本文方法對所有程序錯誤都有效。本文方法利用圖挖掘和支持向量機(jī)以頻繁邊為特征對所有執(zhí)行分類，最終得到可疑方法集合幫助開發(fā)人員判斷錯誤位置，給出了上下文信息。然而本文只是提供了可疑方法集合，不能很快定位錯誤位置，仍然需要開發(fā)人員花費(fèi)精力查看源代碼判斷錯誤位置對其修復(fù)。本文方法涉及程序插樁，仍需要人工參與。

6 結(jié)束語

本文結(jié)合數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)技術(shù)，改進(jìn)了基于圖挖掘和支持向量機(jī)的軟件錯誤定位方法，以對程序方法調(diào)用圖分類的方式進(jìn)行故障定位，通過實(shí)驗(yàn)表明了本文方法的有效性。

未來如何將該方法運(yùn)用到更大型的程序上，如何與其他軟件錯誤定位方法結(jié)合以及如何在不同粒度上實(shí)現(xiàn)本文方法都值得進(jìn)一步研究。