何海江
長沙學院 數(shù)學與計算機科學系,長沙 410022
基于線性分類算法的軟件錯誤定位模型
何海江
長沙學院 數(shù)學與計算機科學系,長沙 410022
基于譜的錯誤定位(SBFL)方法能幫助程序員減小軟件調試的困難。作為一種輕量方法,SBFL只需收集測試用例的覆蓋信息和測試結果,計算程序每條語句的運行特征。眾多SBFL方法,將四個運行特征組合成不同的可疑度計算公式。然而,這些公式受固定參數(shù)的影響,無法適應不同的程序集。因此,提出一種機器學習方法,能自動確定特定程序集的可疑度計算公式。首先,收集已標注錯誤語句的程序舊版本;再將錯誤語句與正確語句的運行特征兩兩相減,構造為訓練集的一個樣本;最后基于Weka的分類算法,學習到線性函數(shù),作為該程序的錯誤定位模型。在Siemens程序包、space和gzip三個基準數(shù)據集上,使用Logistic、SGD、SMO和LibLinear學習到的模型,性能都要優(yōu)于SBFL方法。
分類算法;線性模型;錯誤定位;程序譜;軟件測試
軟件生命周期的開發(fā)階段和維護階段都有大量的調試活動。程序員通常利用斷點、print語句和斷言來調試程序。比較而言,斷點方法更為有效,也更受歡迎。執(zhí)行引起程序故障的測試用例后,程序員先猜測可能出錯的語句,設置其為斷點,讓程序停下來。再利用開發(fā)工具,查看內存中的變量值和程序的運行結果。如與預期一致,則判為正確語句,再猜測其他語句;如不符,則判為錯誤語句。如是反復,直到所有測試用例都通過。當前流行的開發(fā)平臺,如Visual Studio、MyEclipse等都帶有單步執(zhí)行、變量呈現(xiàn)等調試工具輔助斷點方法。在調試過程中,還需要不斷分析常量、變量、運算符、函數(shù)、語句等之間的依賴關系。如果沒有自動化或半自動化的錯誤定位工具,要想找到錯誤代碼是一件非常困難的事情,復雜和大型的軟件尤為甚。
為解決錯誤定位難題,人們提出了許多方法,自動搜索導致程序發(fā)生故障的代碼,將搜索結果呈現(xiàn)出來,由程序員決定如何修改代碼。在這些方法中,基于譜的錯誤定位(Spectrum-Based Fault Localization,SBFL)[1]最受關注,是近年來的研究熱點。SBFL方法計算簡單,消耗資源少,只要收集測試過程程序實體的覆蓋信息和測試用例執(zhí)行結果,無需額外的處理,故而適應于大規(guī)模軟件。SBFL方法的程序實體,可以是語句、分支、代碼片段,也可以是謂詞、函數(shù)、類等。不失一般性,本文以語句作為程序實體。每條語句只用少量運行特征,形式上可用四元組 <aep,aef,anp,anf>表示。aep是覆蓋該語句,其程序運行結果為成功的測試用例數(shù);aef則是覆蓋該語句,其程序運行結果為失敗的測試用例數(shù);測試用例執(zhí)行未覆蓋該語句時,anp是其程序運行結果為成功的測試用例數(shù),anf則是其程序運行結果為失敗的測試用例數(shù)。顯然,每條語句的四特征數(shù)值之和等于程序的測試用例數(shù)目。由四元組計算每條語句的可疑度,按照可疑度從大到小排序,排在前面的語句,包含錯誤代碼的概率較大,程序員依此順序檢查代碼。人們提出來許多的SBFL方法,將四個特征組合成不同的語句可疑度計算公式,組合方式可看作一個映射函數(shù),將可執(zhí)行語句的運行特征映射成一個實數(shù)值。不過,這些方法存在明顯的缺陷:(1)針對所有程序,采用固定的可疑度公式。而特定的程序,受軟件規(guī)模、測試套件、編程語言、程序員開發(fā)水平等因素的影響,可能出錯方式與其他程序迥異。(2)若軟件開發(fā)過程、維護過程還收集到其他有用信息,很難集成到已有公式中。
為克服SBFL的缺點,提出一種基于分類算法的錯誤定位方法。針對特定的程序,先收集標注了錯誤語句的程序舊版本;再將錯誤語句、正確語句兩兩配對,特征值相減,組合成分類算法訓練集的一個樣本;最后使用線性模型分類算法,從訓練集學習到該程序獨有的映射函數(shù)。此后,每當定位這個程序的軟件錯誤時,使用它特有的映射函數(shù)逐條計算語句的可疑度。另外,算法很容易擴展,集成其他程序特征。增加描述可執(zhí)行語句的特征數(shù)目,四元組擴充為五元組、六元組等等,算法無需改變。
本文第2章介紹了分類算法和SBFL的相關研究工作。第3章舉一個例子描述基于譜的軟件錯誤定位方法。第4章介紹了技術路線及實現(xiàn)策略。第5章列出實驗結果,證實新方法的有效性。最后一章給出結論。
本文的工作與兩方面研究內容相關。
在軟件錯誤定位方法中,基于程序譜的技術最受關注。Jones等人考慮測試用例覆蓋信息、多種程序實體等相關因素,提出Tarantula方法[2],取得了不錯的效果。與Tarantula相似,人們開發(fā)了一系列技術,不斷提高軟件錯誤定位能力。Ample方法被集成到Eclipse插件中,用以分析Java軟件的錯誤代碼[3]。Abreu等人[1]使用生物學領域的公式Ochiai計算程序實體的可疑度,效果要優(yōu)于Tarantula、Jaccard等技術。Lucia等人[4]也通過大量實驗證實,無論在單個錯誤程序,還是在多錯誤程序中定位錯誤,Ochiai的能力都很突出。有趣的是,他們使用了將近40種數(shù)據挖掘和統(tǒng)計領域的關聯(lián)測度與Tarantula、Ochiai相比。同時,這些實驗數(shù)據也揭示,40種方法中任何一種都無法在所有程序中勝出。Wong等人也提出許多SBFL方法,其中較有代表性的是Wong1、Wong2和Wong3[5]。特別是Wong3,根據不同的aep個數(shù),給予不同的可疑度計算,公式本質上是一個分梯度的帶權計算方法。丁暉等人[6]則依據信息論,用事件的發(fā)生概率代替梯度閾值,構造了更平滑的可疑度計算公式。
除了這些方法外,還有非常多的可疑度計算公式,它們也都是將表征程序實體的四個特征組合成不同形式。這些方法的效果也只能在一個有限的程序集中得到驗證。由此可見,理論分析必不可少。Naish等人[7]構造了一段具代表性的選擇型代碼,代碼只包含一條錯誤語句,并且定義了所有可執(zhí)行序列的平均測度作為SBFL性能的評價指標。在此框架下,比較了30余種SBFL技術的優(yōu)劣。最后,經過理論證明,NaishO和NaishOp在該框架下最優(yōu)。前述框架限制太多,Xie等人[8]討論了更一般的情況,只要求程序包含單個錯誤,并且使用Exam值為評價指標。經理論證明,在30種SBFL方法中,NaishO 和NaishOp等價,Wong1和另兩個可疑度計算公式等價,NaishO和Wong1無法直接比較,但NaishO優(yōu)于其余25種模型。與這些工作使用固定模型不同的是,采取機器學習技術,從程序集舊版本學習錯誤定位模型,不同的程序集,能訓練出特有的模型。
為了提高軟件錯誤定位效率,人們還做了許多其他工作。測試用例能執(zhí)行到錯誤位置,但卻不會觸發(fā)錯誤,排除這些偶然正確的測試用例能夠提高SBFL技術的性能[9]。內存或CPU等資源受限,動態(tài)調整程序實體的粒度,Java程序可以先在包或類等粗粒度上定位[10]??偨Y研究人員的大量工作后,陳翔等人定義了缺陷定位研究框架[11],王克朝等人定義了“失效-錯誤定位-理解”模型[12],各自從多個方面分析了軟件錯誤定位的影響因素、關鍵問題和研究進展。
分類算法廣泛應用于軟件缺陷預測、垃圾郵件過濾、文檔分類、生物序列識別、網絡攻擊檢測和圖像處理[13]等領域。將分類算法,甚至是機器學習、數(shù)據挖掘方法應用于軟件錯誤定位的報道還不多見。
決策樹[14]、線性回歸[15]和馬爾科夫鏈[16]可作為構造錯誤定位模型的學習算法。但是,這些方法需要額外的信息。有的將程序輸入條件按類別劃分,產生大量的抽象測試用例[14];有的針對特定程序,定義為數(shù)不少的謂詞[15];有的需要收集程序靜態(tài)結構,以及與程序故障相關的先驗知識[16]?;谏窠浘W絡的軟件錯誤定位方法倒是僅僅需要語句覆蓋信息和測試用例執(zhí)行結果。但是與SBFL相比,有兩個缺點,無論使用反向傳播神經網絡[17],還是徑向基函數(shù)神經網絡[18],都存在:(1)學習速度慢,很難在線訓練;(2)程序每個版本的語句不同,導致神經網絡輸入層不同,在一個版本上學到的錯誤定位模型無法應用到其他版本。Ali等人[19]將單個測試用例作為分類算法的一個樣本,每條語句被測試用例覆蓋的次數(shù)定義為樣本特征,測試用例成功與否為樣本類別。他們的實驗表明,分類算法表現(xiàn)很差,計算采用代價敏感的分類算法處理類別不平衡問題,也無法超過Tarantula。本文方法與Ali等人的工作一樣,無需收集額外數(shù)據,相比其他機器學習技術,并不增加建模負擔。與Ali等人工作不同的是,在語句對上建立訓練集樣本,自然效果也好得多。
圖1 錯誤定位技術舉例
SBFL方法只需要收集兩類信息:(1)測試用例的執(zhí)行結果,即成功或失敗。(2)程序運行時,語句的覆蓋程度,最為常見的是布爾值,即語句被覆蓋或語句未被覆蓋。以圖1為例,可理解SBFL的實現(xiàn)步驟。函數(shù)middle有三個整型參數(shù),從中找到中間值,作為函數(shù)返回值。該函數(shù)共有18行代碼,其中15行可執(zhí)行。測試套件有10個測試用例。依據路徑覆蓋策略,設計了t1~t6六個測試用例??紤]到程序員編寫代碼時,遇到>、>=、〈和〈=容易出錯,另設計了t7~t10。程序中存在一處錯誤,在可執(zhí)行語句4,正確形式為else if(x〈z),〈被敲成了>。圖1的最后一行表示各測試用例的執(zhí)行結果,P表成功,F(xiàn)表失敗,共有7個成功測試用例,3個失敗測試用例。黑圓圈表示執(zhí)行測試用例時語句被覆蓋,空白則表示未運行該語句。以t1為例,當x=5,y=3,z=2測試middle時,語句1、8、9、10和15被覆蓋,而其他語句不會運行。有了這些信息,容易統(tǒng)計出可執(zhí)行語句的四個特征。顯然,各語句的aep+aef+anp+anf=10,aep+anp=7,aef+anf=3。
一個當然的想法是:aep越大,語句包含錯誤的可能性越?。籥ef越大,語句包含錯誤的可能性越大。相比而言,anp和anf的大小與錯誤可能性關聯(lián)程度小一些。但仍然可以推斷:anp越大,語句包含錯誤的可能性越?。籥nf越小,語句包含錯誤的可能性越大。SBFL方法就是基于以上樸素想法而提出,構造一個映射函數(shù),將四個特征映射為一個實數(shù)值。Jaccard=aef/(aep+aef+anf)和 Wong1=aef已被證實能有效定位錯誤語句。依照Wong1,語句1、2、4、15是最可能的錯誤語句,可疑度為3。依照Jaccard,可疑度0.75的語句4最可能出錯。依Jaccard,只需檢查1條語句,也就是6.67%的代碼就可找到錯誤。在SBFL研究社區(qū),Exam值是最為常見的評估測度,當發(fā)現(xiàn)第一條錯誤語句時,所需檢查的代碼百分比定義為Exam值。其他條件相同,Exam值越小,對應的方法越有效。Jaccard的Exam值=6.67%。而依Wong1方法,四條語句的可疑度都處于最高。最理想的情況,語句4最先檢查,這種策略被稱為Best,也就是Wong1 Best的Exam值=6.67%。另一種策略Worst,最壞的情況,語句4最后才被檢查,這樣需要檢查4條語句,也就是26.67%的代碼才能發(fā)現(xiàn)錯誤,Wong1 Worst的Exam值=26.67%。
當然,Best和Worst都是假設情況,簡易可行的策略是 SOS(statement order based)[20]。程序員按照語句的順序檢查代碼,依次檢查語句1和2后,再檢查語句4,此時Wong1 SOS的Exam值=20%。Wong1強調aef的作用,故語句1、2、4、15是錯誤語句的可疑度同為最高,而Jaccard綜合考慮 anf、aep、aef的作用,語句4就變得最為可疑。在這個例子中,Jaccard要優(yōu)于Wong1。但是一旦測試用例發(fā)生變化,又或者換做其他程序,Jaccard和Wong1各有千秋。
Weka是一個開源平臺,實現(xiàn)了眾多的機器學習算法和數(shù)據挖掘工具[21]??紤]到錯誤定位模型需要適應大型軟件,只選取那些能輸出線性模型的分類算法,共找到四個算法完成實驗。
要學習程序的錯誤定位模型,先收集其標注錯誤代碼的舊版本,所有可執(zhí)行語句都采集了aep、aef、anp和anf。在這些數(shù)據上構建訓練集,具體策略如下:
訓練集生成算法
輸入 程序的舊版本集{V1,V2,…,VQ}。
輸出 訓練集LCtrain。
Begin
LCtrain=?;
index=0;//保持樣本類別的平衡
Fori=1toQ
/*UFault是Vi錯誤語句的集合,M是其語句條數(shù)。UOK是Vi正確語句的集合,N是其語句條數(shù)。F(j)或F(k)是第j(或 k)條語句的特征,j(或 k)=1,2,…,M(N)。*/
Forj=1toM
Fork=1toN
label=true; //樣本的類別
Sample=F(j)-F(k);
Ifindex%2==0
/*保證兩種類別的樣本個數(shù)相同*/
Sample=Sample*(-1);
label=false;
End If
LCtrain=LCtrain+(Sample,label);
index=index+1;
End For
End For
End For
End
將訓練集輸入Weka,經分類算法學習后,優(yōu)化目標位使得LCtrain的誤分類個數(shù)最少,便可獲得線性模型w。若新版本程序有特征為F的語句,其錯誤可疑度=w1F1+w2F2+…+wDFD,D是特征維數(shù)。
令L=M×N ,訓練集LCtrain的樣本集合{(Sample,label)}形式化為{(xi,yi)},i=1,2,…,L,xi∈Rn,yi∈{-1,+1}。LibLinear是機器學習社區(qū)知名的線性分類算法,用于解決擁有巨量特征和大規(guī)模樣本的分類問題。LibLinear的SVMType選擇1,其余參數(shù)全部采用缺省值,算法解決無約束優(yōu)化問題1[22]:
其中T表示矩陣的轉置,C是懲罰因子。
Logistic是線性分類的logistic回歸,在一個經轉換的目標變量上建立線性模型。Logistic回歸是非常經典的分類算法,在眾多領域都有成熟的應用,其解決優(yōu)化問題2[19]:
其中l(wèi)n表示自然對數(shù),exp表示自然指數(shù)。算法采用Weka的缺省參數(shù)。
SGD(Stochastic Gradient Descent)能學習不同的線性分類模型,包括兩類別的支持向量機、兩類別的logistic回歸等。而SMO(Sequential Minimal Optimization)只能訓練支持向量機的分類模型。兩者的優(yōu)化問題都與LibLinear相同[21],但使用不同策略解決優(yōu)化問題。LibLinear用了坐標下降法和信賴域牛頓方法,SGD使用隨機梯度下降方法,SMO則采用序貫最小優(yōu)化策略。SGD和SMO用Weka的缺省參數(shù)。
本文的方法與九種SBFL技術的實驗比較結果。所有實驗在一臺配置Intel Core i3-3220 3.3 GHz CPU和4 GB物理內存的計算機上完成,操作系統(tǒng)是Windows Server 2003,調用MinGW5.1的gcc和gcov編譯程序和收集覆蓋信息。
Siemens套件、程序集space和gzip很受歡迎,成為軟件錯誤定位領域的基準數(shù)據集,許多研究者在論文中使用它說明新算法的有效性。Siemens共有7個程序集:print_tokens、print_tokens2、replac、tcas、tot_info、schedule和schedule2。
原replace共有32個缺陷版本,其v27無失敗的測試用例,無法比較各種算法,故而將該缺陷版本排除在外,剩下31個缺陷版本。同樣的原因,還去掉了schedule2的一個版本v9。原space有38個缺陷版本,其v1、v2、v32、v34無失敗的測試用例;v25和v30的錯誤代碼是指針問題,測試用例執(zhí)行后,導致程序崩潰,MinGW的gcov無法記錄覆蓋信息;將這6個版本排除在外,剩下32個缺陷版本。另外,修改了space的v26和v35,在錯誤的指針語句前,加了判斷指針是否為空的語句,避免程序崩潰。SIR軟件項目基礎資源庫為每個程序集提供了多種測試覆蓋類型:bigcov、bigrand、universe、cov和rand等,本文選擇universe完成所有實驗。表1是所有實驗程序的基本信息。
本文的方法,表示可執(zhí)行語句的特征個數(shù)不受限制。為了與SBFL公平比較。使用了與四元組 <aep,aef,anp,anf>有關的四個特征:aef/AF,aep/AP,anf/(AF+aep),anp/(anp+anf),其中AF=aef+anf,AP=aep+anp。顯然,這些特征的值在實數(shù)區(qū)間[0,1],當錯誤語句與正確語句特征值相減,訓練集樣本的特征值處于[-1,+1]。這樣就省去了Weka的數(shù)據預處理步驟。
使用十折交叉驗證的策略完成所有實驗。對每個程序集,將其版本平均分為10份,9份作舊版本集構造訓練集,1份作新版本測試集。使用四個分類算法在訓練集學習到模型后,計算出測試集的錯誤定位性能。不足10份的程序集,如print_tokens、schedule和schedule2,部分版本重復填入測試集,但保證一個版本不會同時出現(xiàn)在訓練集和測試集。所有試驗結果都是10折的平均值。
Siemens的實驗數(shù)據是七個對象的平均值。表2、表3和表4是九種常見SBFL方法和Logistic分別在Siemens、space和gzip上的Exam值比較。表現(xiàn)最好的數(shù)據用黑體字標示,表中Exam值省略了百分符號。Wong1只與aef有關,在那些只有一條錯誤語句的程序上,依Best策略,Wong1一定優(yōu)于其他技術。在Siemens和gzip上,Wong1 Best都顯著優(yōu)于其他技術的Best策略。除此之外,依三種策略Logistic都優(yōu)于其他方法,特別在程序集space表現(xiàn)出顯著優(yōu)勢。Ochiai盡管在Siemens和gzip表現(xiàn)不佳,在space上卻僅次于Logistic。Lucia等人[4]在比較40種SBFL技術后,發(fā)現(xiàn)Ochiai在許多程序上表現(xiàn)優(yōu)異。另外,NaishO、NaishOp和Wong3在 Siemens和gzip上,Kulczynski2[7]在 Siemens上,也都有好的性能。相比而言,其他方法無法顯示競爭性。
Weka另外三種算法也都不輸給Logistic。調試軟件的實際過程中,SOS可用,而Best和Worst不可用,因此后文只比較SOS策略。表5是三種算法與Logistic算法依SOS策略,在三個數(shù)據集上的Exam值比較。表中的正值表示對應算法弱于Logistic,負值則強于Logistic。以LibLinear為例,在Siemens上,它比Logistic差,要多檢查0.27%的語句,才能找到第一條錯誤語句;在space上,則略好于Logistic;在gzip上,兩者打成平手。綜合來看,四種算法中,SGD表現(xiàn)最好,SMO表現(xiàn)最差。
表1 實驗程序的基本信息
表2 Siemens程序包上的Exam值比較
表3 程序集space上的Exam值比較
表4 程序集gzip上的Exam值比較
當程序較大,而錯誤語句的可疑度靠后,程序員檢查較多語句后,仍未能定位到錯誤代碼,會產生厭煩情緒。通常,SBFL研究社區(qū)會限制檢查比例Pcheck(已檢查語句數(shù)占程序語句總數(shù)的比率),計算出PbugVers(能發(fā)現(xiàn)錯誤版本數(shù)占程序版本總數(shù)的比率),來比較各類技術的優(yōu)劣。圖2和圖3分別在Siemens和gzip上比較各類方法,Pcheck從1%到20%,步長1%。圖中所有技術都依SOS策略。
表5 三種算法與Logistic算法SOS策略的Exam值比較
圖2 Siemens程序包的PbugVers比較
圖3 gzip程序集的PbugVers比較
如圖2所示,在Siemens上,Logistic表現(xiàn)最好,只在 Pcheck=1%處略差外,其余點都優(yōu)于其他方法。Kulczynski2、SMO、NashiO和Wong3差不多,Tarantula則遜色不少。使圖清晰起見,未列出另外五種SBFL和兩種分類算法的結果。實際上,LibLinear與SMO相似,SGD略好于Logistic,NashiOp與NashiO相同,其余四種SBFL顯著落后于SMO。如圖3所示,在gzip上,LibLinear和NashiOp表現(xiàn)最好,相比它們,SGD和Wong3略差一點,Jaccard和Ochiai則差了很多??疾煳戳谐龅奈宸NSBFL方法和兩種分類算法,Logistic和LibLinear完全相同,SMO略差于SGD,NashiO與NashiOp完全相同,其余四種SBFL顯著落后于SGD。在space上,檢查同樣比例的代碼,四種分類算法找出錯誤的版本數(shù)目都顯著多于九類SBFL方法??偟膩砜?,以PbugVers為評價指標,本文的方法無疑最有競爭力。
為輔助程序員盡快定位軟件的錯誤代碼,人們提出來許多的SBFL方法,利用測試結果,逐條計算語句的錯誤可疑度。不過,各種SBFL無外乎將四個運行特征組合成不同的映射函數(shù),將可執(zhí)行語句的運行特征映射成一個實數(shù)值。這些映射函數(shù)采用固定形式,無法適應程序規(guī)模、測試用例分布、程序員開發(fā)習慣等迥異的各類情況。如果軟件開發(fā)過程、維護過程還收集到其他有用信息,如何修改映射函數(shù)是一個難題。相比而言,設計了巧妙的訓練集生成算法,采用機器學習方法,能從程序舊版本學習到該程序獨有的可疑度計算公式,算法也容易集成其他程序特征。
選取了Weka中能輸出線性模型的四個分類算法,Logistic、SGD、SMO和LibLinear檢驗方法的有效性。在Siemens程序包、space和gzip三個基準數(shù)據集上,實驗結果證實,無論是比較Exam值,還是限制Pcheck比較PbugVers,它們的性能都要優(yōu)于SBFL方法。
[1]Abreu R,Zoeteweij P,Golsteijn R,et al.A practical evaluation of spectrum-based fault localization[J].Journal of Systems and Software,2009,82(11):1780-1792.
[2]Jones J A,Harrold M J.Empirical evaluation of the tarantula automatic fault-localization technique[C]//Proceedings of the 20th IEEE/ACM International Conference on Automated Software Engineering.New York:ACM,2005:273-282.
[3]Dallmeier V,Lindig C,Zeller A.Lightweight defect localization for Java[C]//European Conference on Objectoriented Programming,2005,3586:528-550.
[4]Lucia L,Lo D,Jiang Lingxiao,et al.Extended comprehensive study of association measures for fault localization[J].Journal of Software Evolution and Process,2014,26(4):172-219.
[5]Wong W E,Debroy V,Choi B.A family of code coveragebased heuristics for effective fault localization[J].Journal of Systems and Software,2010,83(2):188-208.
[6]丁暉,陳林,錢巨,等.一種基于信息量的缺陷定位方法[J].軟件學報,2013,24(7):1484-1494.
[7]Naish L,Lee H J,Ramamohanarao K.A model for spectrabased software diagnosis[J].ACM Transactions on Software Engineering and Methodology,2011,20(3):1-32.
[8]Xie Xiaoyuan,Chen T Y,Kuo F,et al.A theoretical analysis of the risk evaluation formulas for spectrumbased fault localization[J].ACM Transactions on Software Engineering and Methodology,2013,22(4):31.
[9]Miao Yi,Chen Zhenyu,Li Sihan,et al.A clustering-based strategy to identify coincidental correctnessin fault localization[J].International Journal of Software Engineering and Knowledge Engineering,2013,23(5):721-741.
[10]Perez A,Abreu R,Riboira A.A dynamic code coverage approach to maximize fault localization efficiency[J].Journal of Systems and Software,2014,90:18-28.
[11]陳翔,鞠小林,文萬志,等.基于程序頻譜的動態(tài)缺陷定位方法研究[J].軟件學報,2015,26(2):390-412.
[12]王克朝,王甜甜,蘇小紅,等.軟件錯誤自動定位關鍵科學問題及研究進展[J].計算機學報,2015,38(11):2262-2278.
[13]羅三定,彭瓊,李婷.瓷磚圖像的紋理特征分類研究[J].計算機工程與應用,2016,52(8):196-200.
[14]BriandL C,Labiche Y,LiuXuetao.Usingmachine learning to support debugging with tarantula[C]//Proceedings of the 18th IEEE International Symposium on Software Reliability.Piscataway,NJ:IEEE,2007:137-146.
[15]Gore R,Reynolds P F.Reducing confounding bias in predicate-level statistical debugging metrics[C]//Proceedings of the 2012 International Conference on Software Engineering.Piscataway,NJ:IEEE,2012:463-473.
[16]Zhang Sai,Zhang C.Softwre bug localization with Markov logic[C]//Proceedings of the 36th International Conference on Software Engineering NIER Track.Piscataway,NJ:IEEE,2014.
[17]Wong W E,Qi Yu.BP neural network-based effective faultlocalization[J].InternationalJournalofSoftware Engineering and Knowledge Engineering,2009,19(4):573-597.
[18]Wong W E,Debroy V,Golden R,et al.Effective software fault localization using an RBF neural network[J].IEEE Transactions on Reliability,2012,61(1):149-169.
[19]Ali S,Andrews J A,Dhandapani T,et al.Evaluating the accuracy offaultlocalization techniques[C]//IEEE/ACM International Conference on Automated Software Engineering.Piscataway,NJ:IEEE,2009:76-87.
[20]Xu Xiaofeng,Debroy V,Wong W E,et al.Ties within fault localization rankings:Exposing and addressing the problem[J].International Journal of Software Engineering and Knowledge Engineering,2011,21(6):803-827.
[21]Hall M,F(xiàn)rank E,Holmes G,et al.The WEKA data mining software:An update[J].SIGKDD Explorations,2009,11(1).
[22]Fan R E,Chang K W,Hsieh C J,et al.LIBLINEAR:A library for large linear classification[J].Journal of Machine Learning Research,2008,9(9):1871-1874.
HE Haijiang
Department of Mathematics and Computer Science,Changsha University,Changsha 410022,China
Software fault localization model based on linear classification algorithm.Computer Engineering and Applications,2017,53(21):42-48.
Spectrum-Based Fault Localization(SBFL)techniques aid developers to reduce the debugging effort.As a light-weight promising approach,SBFL only collects the testing result of passed or failed,and the corresponding coverage information.Based on these data,SBFL can then calculate a runtime spectra for each program statement.SBFL approaches apply various functions to map four profile features to a suspiciousness score.However,existing functions don’t give good accuracy due to the influence of the fixed parameters.Therefore,a machine learning method is proposed that can automatically construct a suspiciousness function of the specific program set.First,the old versions of a program having fault code are collected.Next,it is mapped from the feature difference in a pair of faulty statement and non-faulty statement to an instance in training dataset.Finally the linear classification algorithm of Weka is applied to learn a mapping function.The function learned from old versions is defined as the fault localization model of the program.To assess the validity of the proposed method,an experiment is performed on three benchmark datasets:Siemens suite,space and gzip.Experimental result demonstrates that the proposed method reduces fault localization cost that exists in SBFL approaches.
classification algorithm;linear model;fault localization;program spectra;software testing
A
TP311
10.3778/j.issn.1002-8331.1606-0176
湖南省科技計劃項目(No.2015GK3071);長沙市科技計劃項目(No.K1509011-11)。
何海江(1970—),男,副教授,主要從事機器學習、軟件測試的研究,E-mail:haijianghe@sohu.com。
2016-06-13
2016-07-29
1002-8331(2017)21-0042-07
CNKI網絡優(yōu)先出版:2016-11-21,http://www.cnki.net/kcms/detail/11.2127.TP.20161121.2049.086.html