結(jié)合圖挖掘和支持向量機(jī)的錯(cuò)誤定位*

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

1.中國(guó)礦業(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]。自動(dòng)化錯(cuò)誤定位技術(shù)可以有效減少軟件調(diào)試的時(shí)間和人力消耗，提高軟件質(zhì)量。

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

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

2 相關(guān)工作

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

3 技術(shù)背景

3.1 圖挖掘技術(shù)

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

頻繁子圖挖掘是圖挖掘中一個(gè)研究熱點(diǎn)，它是從大量的圖中挖掘出一些滿足給定支持度的頻繁圖，當(dāng)一個(gè)子圖在整個(gè)圖集合中出現(xiàn)的比率滿足指定的支持度，那么這個(gè)子圖就是頻繁子圖。傳統(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]都是基于模式增長(zhǎng)的頻繁結(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)控制等各個(gè)領(lǐng)域的實(shí)際問題中。

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

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

4 本文方法

4.1 方法概述

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

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

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

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

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

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

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

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

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

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

算法1子樹約簡(jiǎn)算法

輸入：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 子樹約簡(jiǎn)實(shí)例

4.3 封閉子圖挖掘

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

頻繁子圖挖掘是從圖集合中挖掘滿足支持度的頻繁圖，存在多種頻繁子圖挖掘算法[11-14]，考慮到CloseGraph[14]挖掘效率高且避免了子圖同構(gòu)，本文選擇CloseGraph[14]進(jìn)行子圖挖掘，CloseGraph[14]算法以DFS編碼、圖集合和最小支持度為輸入，以封閉子圖集合為輸出。該算法主要分為3步：第1步，生成一個(gè)頻繁子圖。第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)值，則會(huì)被認(rèn)為是不同邊，得到大量的頻繁子圖。因此在進(jìn)行挖掘時(shí)排除權(quán)值的干擾，挖掘出最大的頻繁子圖，得到頻繁邊。得到頻繁邊之后將其對(duì)應(yīng)到每一個(gè)調(diào)用圖中，每個(gè)調(diào)用圖代表一次程序執(zhí)行。通過表格記錄挖掘到的所有頻繁邊，依此訓(xùn)練以頻繁邊為特征的支持向量機(jī)，如表1所示。

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

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

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

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

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

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

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

Fig.3 Classification principle圖3 分類原理

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

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

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

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

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

實(shí)驗(yàn)使用LibSVM[17]進(jìn)行分類，由于其具有簡(jiǎn)單易使用，且快速高效的特點(diǎn)，廣泛用于解決通用的分類問題。在進(jìn)行分類時(shí)，實(shí)驗(yàn)選擇使用頻繁邊和封閉子圖作為特征，然后訓(xùn)練支持向量機(jī)進(jìn)行分類，最終得到各個(gè)方法的精度。實(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 植入錯(cuò)誤說明

Fig.4 Classification accuracy comparison of single fault圖4 單個(gè)錯(cuò)誤分類精度比較

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

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

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

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

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

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

運(yùn)行時(shí)間消耗主要是封閉子圖挖掘和訓(xùn)練SVM。提取頻繁邊和封閉子圖作為特征需要對(duì)圖集合進(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)行錯(cuò)誤定位，以f2為例，以一張表記錄所有方法出口與入口的分類精度，如表3所示。

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

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

5.4 討論

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

6 結(jié)束語(yǔ)

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

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