何海江

長(zhǎng)沙學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)系，長(zhǎng)沙 410022

基于線性分類算法的軟件錯(cuò)誤定位模型

何海江

長(zhǎng)沙學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)系，長(zhǎng)沙 410022

基于譜的錯(cuò)誤定位（SBFL）方法能幫助程序員減小軟件調(diào)試的困難。作為一種輕量方法，SBFL只需收集測(cè)試用例的覆蓋信息和測(cè)試結(jié)果，計(jì)算程序每條語(yǔ)句的運(yùn)行特征。眾多SBFL方法，將四個(gè)運(yùn)行特征組合成不同的可疑度計(jì)算公式。然而，這些公式受固定參數(shù)的影響，無(wú)法適應(yīng)不同的程序集。因此，提出一種機(jī)器學(xué)習(xí)方法，能自動(dòng)確定特定程序集的可疑度計(jì)算公式。首先，收集已標(biāo)注錯(cuò)誤語(yǔ)句的程序舊版本；再將錯(cuò)誤語(yǔ)句與正確語(yǔ)句的運(yùn)行特征兩兩相減，構(gòu)造為訓(xùn)練集的一個(gè)樣本；最后基于Weka的分類算法，學(xué)習(xí)到線性函數(shù)，作為該程序的錯(cuò)誤定位模型。在Siemens程序包、space和gzip三個(gè)基準(zhǔn)數(shù)據(jù)集上，使用Logistic、SGD、SMO和LibLinear學(xué)習(xí)到的模型，性能都要優(yōu)于SBFL方法。

分類算法；線性模型；錯(cuò)誤定位；程序譜；軟件測(cè)試

1 引言

軟件生命周期的開(kāi)發(fā)階段和維護(hù)階段都有大量的調(diào)試活動(dòng)。程序員通常利用斷點(diǎn)、print語(yǔ)句和斷言來(lái)調(diào)試程序。比較而言，斷點(diǎn)方法更為有效，也更受歡迎。執(zhí)行引起程序故障的測(cè)試用例后，程序員先猜測(cè)可能出錯(cuò)的語(yǔ)句，設(shè)置其為斷點(diǎn)，讓程序停下來(lái)。再利用開(kāi)發(fā)工具，查看內(nèi)存中的變量值和程序的運(yùn)行結(jié)果。如與預(yù)期一致，則判為正確語(yǔ)句，再猜測(cè)其他語(yǔ)句；如不符，則判為錯(cuò)誤語(yǔ)句。如是反復(fù)，直到所有測(cè)試用例都通過(guò)。當(dāng)前流行的開(kāi)發(fā)平臺(tái)，如Visual Studio、MyEclipse等都帶有單步執(zhí)行、變量呈現(xiàn)等調(diào)試工具輔助斷點(diǎn)方法。在調(diào)試過(guò)程中，還需要不斷分析常量、變量、運(yùn)算符、函數(shù)、語(yǔ)句等之間的依賴關(guān)系。如果沒(méi)有自動(dòng)化或半自動(dòng)化的錯(cuò)誤定位工具，要想找到錯(cuò)誤代碼是一件非常困難的事情，復(fù)雜和大型的軟件尤為甚。

為解決錯(cuò)誤定位難題，人們提出了許多方法，自動(dòng)搜索導(dǎo)致程序發(fā)生故障的代碼，將搜索結(jié)果呈現(xiàn)出來(lái)，由程序員決定如何修改代碼。在這些方法中，基于譜的錯(cuò)誤定位（Spectrum-Based Fault Localization，SBFL）[1]最受關(guān)注，是近年來(lái)的研究熱點(diǎn)。SBFL方法計(jì)算簡(jiǎn)單，消耗資源少，只要收集測(cè)試過(guò)程程序?qū)嶓w的覆蓋信息和測(cè)試用例執(zhí)行結(jié)果，無(wú)需額外的處理，故而適應(yīng)于大規(guī)模軟件。SBFL方法的程序?qū)嶓w，可以是語(yǔ)句、分支、代碼片段，也可以是謂詞、函數(shù)、類等。不失一般性，本文以語(yǔ)句作為程序?qū)嶓w。每條語(yǔ)句只用少量運(yùn)行特征，形式上可用四元組 ＜aep,aef,anp,anf＞表示。aep是覆蓋該語(yǔ)句，其程序運(yùn)行結(jié)果為成功的測(cè)試用例數(shù)；aef則是覆蓋該語(yǔ)句，其程序運(yùn)行結(jié)果為失敗的測(cè)試用例數(shù)；測(cè)試用例執(zhí)行未覆蓋該語(yǔ)句時(shí)，anp是其程序運(yùn)行結(jié)果為成功的測(cè)試用例數(shù)，anf則是其程序運(yùn)行結(jié)果為失敗的測(cè)試用例數(shù)。顯然，每條語(yǔ)句的四特征數(shù)值之和等于程序的測(cè)試用例數(shù)目。由四元組計(jì)算每條語(yǔ)句的可疑度，按照可疑度從大到小排序，排在前面的語(yǔ)句，包含錯(cuò)誤代碼的概率較大，程序員依此順序檢查代碼。人們提出來(lái)許多的SBFL方法，將四個(gè)特征組合成不同的語(yǔ)句可疑度計(jì)算公式，組合方式可看作一個(gè)映射函數(shù)，將可執(zhí)行語(yǔ)句的運(yùn)行特征映射成一個(gè)實(shí)數(shù)值。不過(guò)，這些方法存在明顯的缺陷：（1）針對(duì)所有程序，采用固定的可疑度公式。而特定的程序，受軟件規(guī)模、測(cè)試套件、編程語(yǔ)言、程序員開(kāi)發(fā)水平等因素的影響，可能出錯(cuò)方式與其他程序迥異。（2）若軟件開(kāi)發(fā)過(guò)程、維護(hù)過(guò)程還收集到其他有用信息，很難集成到已有公式中。

為克服SBFL的缺點(diǎn)，提出一種基于分類算法的錯(cuò)誤定位方法。針對(duì)特定的程序，先收集標(biāo)注了錯(cuò)誤語(yǔ)句的程序舊版本；再將錯(cuò)誤語(yǔ)句、正確語(yǔ)句兩兩配對(duì)，特征值相減，組合成分類算法訓(xùn)練集的一個(gè)樣本；最后使用線性模型分類算法，從訓(xùn)練集學(xué)習(xí)到該程序獨(dú)有的映射函數(shù)。此后，每當(dāng)定位這個(gè)程序的軟件錯(cuò)誤時(shí)，使用它特有的映射函數(shù)逐條計(jì)算語(yǔ)句的可疑度。另外，算法很容易擴(kuò)展，集成其他程序特征。增加描述可執(zhí)行語(yǔ)句的特征數(shù)目，四元組擴(kuò)充為五元組、六元組等等，算法無(wú)需改變。

本文第2章介紹了分類算法和SBFL的相關(guān)研究工作。第3章舉一個(gè)例子描述基于譜的軟件錯(cuò)誤定位方法。第4章介紹了技術(shù)路線及實(shí)現(xiàn)策略。第5章列出實(shí)驗(yàn)結(jié)果，證實(shí)新方法的有效性。最后一章給出結(jié)論。

2 相關(guān)研究工作

本文的工作與兩方面研究?jī)?nèi)容相關(guān)。

在軟件錯(cuò)誤定位方法中，基于程序譜的技術(shù)最受關(guān)注。Jones等人考慮測(cè)試用例覆蓋信息、多種程序?qū)嶓w等相關(guān)因素，提出Tarantula方法[2]，取得了不錯(cuò)的效果。與Tarantula相似，人們開(kāi)發(fā)了一系列技術(shù)，不斷提高軟件錯(cuò)誤定位能力。Ample方法被集成到Eclipse插件中，用以分析Java軟件的錯(cuò)誤代碼[3]。Abreu等人[1]使用生物學(xué)領(lǐng)域的公式Ochiai計(jì)算程序?qū)嶓w的可疑度，效果要優(yōu)于Tarantula、Jaccard等技術(shù)。Lucia等人[4]也通過(guò)大量實(shí)驗(yàn)證實(shí)，無(wú)論在單個(gè)錯(cuò)誤程序，還是在多錯(cuò)誤程序中定位錯(cuò)誤，Ochiai的能力都很突出。有趣的是，他們使用了將近40種數(shù)據(jù)挖掘和統(tǒng)計(jì)領(lǐng)域的關(guān)聯(lián)測(cè)度與Tarantula、Ochiai相比。同時(shí)，這些實(shí)驗(yàn)數(shù)據(jù)也揭示，40種方法中任何一種都無(wú)法在所有程序中勝出。Wong等人也提出許多SBFL方法，其中較有代表性的是Wong1、Wong2和Wong3[5]。特別是Wong3，根據(jù)不同的aep個(gè)數(shù)，給予不同的可疑度計(jì)算，公式本質(zhì)上是一個(gè)分梯度的帶權(quán)計(jì)算方法。丁暉等人[6]則依據(jù)信息論，用事件的發(fā)生概率代替梯度閾值，構(gòu)造了更平滑的可疑度計(jì)算公式。

除了這些方法外，還有非常多的可疑度計(jì)算公式，它們也都是將表征程序?qū)嶓w的四個(gè)特征組合成不同形式。這些方法的效果也只能在一個(gè)有限的程序集中得到驗(yàn)證。由此可見(jiàn)，理論分析必不可少。Naish等人[7]構(gòu)造了一段具代表性的選擇型代碼，代碼只包含一條錯(cuò)誤語(yǔ)句，并且定義了所有可執(zhí)行序列的平均測(cè)度作為SBFL性能的評(píng)價(jià)指標(biāo)。在此框架下，比較了30余種SBFL技術(shù)的優(yōu)劣。最后，經(jīng)過(guò)理論證明，NaishO和NaishOp在該框架下最優(yōu)。前述框架限制太多，Xie等人[8]討論了更一般的情況，只要求程序包含單個(gè)錯(cuò)誤，并且使用Exam值為評(píng)價(jià)指標(biāo)。經(jīng)理論證明，在30種SBFL方法中，NaishO 和NaishOp等價(jià)，Wong1和另兩個(gè)可疑度計(jì)算公式等價(jià)，NaishO和Wong1無(wú)法直接比較，但NaishO優(yōu)于其余25種模型。與這些工作使用固定模型不同的是，采取機(jī)器學(xué)習(xí)技術(shù)，從程序集舊版本學(xué)習(xí)錯(cuò)誤定位模型，不同的程序集，能訓(xùn)練出特有的模型。

為了提高軟件錯(cuò)誤定位效率，人們還做了許多其他工作。測(cè)試用例能執(zhí)行到錯(cuò)誤位置，但卻不會(huì)觸發(fā)錯(cuò)誤，排除這些偶然正確的測(cè)試用例能夠提高SBFL技術(shù)的性能[9]。內(nèi)存或CPU等資源受限，動(dòng)態(tài)調(diào)整程序?qū)嶓w的粒度，Java程序可以先在包或類等粗粒度上定位[10]?？偨Y(jié)研究人員的大量工作后，陳翔等人定義了缺陷定位研究框架[11]，王克朝等人定義了“失效-錯(cuò)誤定位-理解”模型[12]，各自從多個(gè)方面分析了軟件錯(cuò)誤定位的影響因素、關(guān)鍵問(wèn)題和研究進(jìn)展。

分類算法廣泛應(yīng)用于軟件缺陷預(yù)測(cè)、垃圾郵件過(guò)濾、文檔分類、生物序列識(shí)別、網(wǎng)絡(luò)攻擊檢測(cè)和圖像處理[13]等領(lǐng)域。將分類算法，甚至是機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘方法應(yīng)用于軟件錯(cuò)誤定位的報(bào)道還不多見(jiàn)。

決策樹(shù)[14]、線性回歸[15]和馬爾科夫鏈[16]可作為構(gòu)造錯(cuò)誤定位模型的學(xué)習(xí)算法。但是，這些方法需要額外的信息。有的將程序輸入條件按類別劃分，產(chǎn)生大量的抽象測(cè)試用例[14]；有的針對(duì)特定程序，定義為數(shù)不少的謂詞[15]；有的需要收集程序靜態(tài)結(jié)構(gòu)，以及與程序故障相關(guān)的先驗(yàn)知識(shí)[16]?；谏窠?jīng)網(wǎng)絡(luò)的軟件錯(cuò)誤定位方法倒是僅僅需要語(yǔ)句覆蓋信息和測(cè)試用例執(zhí)行結(jié)果。但是與SBFL相比，有兩個(gè)缺點(diǎn)，無(wú)論使用反向傳播神經(jīng)網(wǎng)絡(luò)[17]，還是徑向基函數(shù)神經(jīng)網(wǎng)絡(luò)[18]，都存在：（1）學(xué)習(xí)速度慢，很難在線訓(xùn)練；（2）程序每個(gè)版本的語(yǔ)句不同，導(dǎo)致神經(jīng)網(wǎng)絡(luò)輸入層不同，在一個(gè)版本上學(xué)到的錯(cuò)誤定位模型無(wú)法應(yīng)用到其他版本。Ali等人[19]將單個(gè)測(cè)試用例作為分類算法的一個(gè)樣本，每條語(yǔ)句被測(cè)試用例覆蓋的次數(shù)定義為樣本特征，測(cè)試用例成功與否為樣本類別。他們的實(shí)驗(yàn)表明，分類算法表現(xiàn)很差，計(jì)算采用代價(jià)敏感的分類算法處理類別不平衡問(wèn)題，也無(wú)法超過(guò)Tarantula。本文方法與Ali等人的工作一樣，無(wú)需收集額外數(shù)據(jù)，相比其他機(jī)器學(xué)習(xí)技術(shù)，并不增加建模負(fù)擔(dān)。與Ali等人工作不同的是，在語(yǔ)句對(duì)上建立訓(xùn)練集樣本，自然效果也好得多。

圖1 錯(cuò)誤定位技術(shù)舉例

3 基于譜的錯(cuò)誤定位方法

SBFL方法只需要收集兩類信息：（1）測(cè)試用例的執(zhí)行結(jié)果，即成功或失敗。（2）程序運(yùn)行時(shí)，語(yǔ)句的覆蓋程度，最為常見(jiàn)的是布爾值，即語(yǔ)句被覆蓋或語(yǔ)句未被覆蓋。以圖1為例，可理解SBFL的實(shí)現(xiàn)步驟。函數(shù)middle有三個(gè)整型參數(shù)，從中找到中間值，作為函數(shù)返回值。該函數(shù)共有18行代碼，其中15行可執(zhí)行。測(cè)試套件有10個(gè)測(cè)試用例。依據(jù)路徑覆蓋策略，設(shè)計(jì)了t1～t6六個(gè)測(cè)試用例?？紤]到程序員編寫代碼時(shí)，遇到＞、＞=、〈和〈=容易出錯(cuò)，另設(shè)計(jì)了t7～t10。程序中存在一處錯(cuò)誤，在可執(zhí)行語(yǔ)句4，正確形式為else if（x〈z），〈被敲成了＞。圖1的最后一行表示各測(cè)試用例的執(zhí)行結(jié)果，P表成功，F(xiàn)表失敗，共有7個(gè)成功測(cè)試用例，3個(gè)失敗測(cè)試用例。黑圓圈表示執(zhí)行測(cè)試用例時(shí)語(yǔ)句被覆蓋，空白則表示未運(yùn)行該語(yǔ)句。以t1為例，當(dāng)x=5，y=3，z=2測(cè)試middle時(shí)，語(yǔ)句1、8、9、10和15被覆蓋，而其他語(yǔ)句不會(huì)運(yùn)行。有了這些信息，容易統(tǒng)計(jì)出可執(zhí)行語(yǔ)句的四個(gè)特征。顯然，各語(yǔ)句的aep+aef+anp+anf=10,aep+anp=7,aef+anf=3。

一個(gè)當(dāng)然的想法是：aep越大，語(yǔ)句包含錯(cuò)誤的可能性越??；aef越大，語(yǔ)句包含錯(cuò)誤的可能性越大。相比而言，anp和anf的大小與錯(cuò)誤可能性關(guān)聯(lián)程度小一些。但仍然可以推斷：anp越大，語(yǔ)句包含錯(cuò)誤的可能性越小；anf越小，語(yǔ)句包含錯(cuò)誤的可能性越大。SBFL方法就是基于以上樸素想法而提出，構(gòu)造一個(gè)映射函數(shù)，將四個(gè)特征映射為一個(gè)實(shí)數(shù)值。Jaccard=aef/(aep+aef+anf)和 Wong1=aef已被證實(shí)能有效定位錯(cuò)誤語(yǔ)句。依照Wong1，語(yǔ)句1、2、4、15是最可能的錯(cuò)誤語(yǔ)句，可疑度為3。依照J(rèn)accard，可疑度0.75的語(yǔ)句4最可能出錯(cuò)。依Jaccard，只需檢查1條語(yǔ)句，也就是6.67%的代碼就可找到錯(cuò)誤。在SBFL研究社區(qū)，Exam值是最為常見(jiàn)的評(píng)估測(cè)度，當(dāng)發(fā)現(xiàn)第一條錯(cuò)誤語(yǔ)句時(shí)，所需檢查的代碼百分比定義為Exam值。其他條件相同，Exam值越小，對(duì)應(yīng)的方法越有效。Jaccard的Exam值=6.67%。而依Wong1方法，四條語(yǔ)句的可疑度都處于最高。最理想的情況，語(yǔ)句4最先檢查，這種策略被稱為Best，也就是Wong1 Best的Exam值=6.67%。另一種策略Worst，最壞的情況，語(yǔ)句4最后才被檢查，這樣需要檢查4條語(yǔ)句，也就是26.67%的代碼才能發(fā)現(xiàn)錯(cuò)誤，Wong1 Worst的Exam值=26.67%。

當(dāng)然，Best和Worst都是假設(shè)情況，簡(jiǎn)易可行的策略是 SOS（statement order based）[20]。程序員按照語(yǔ)句的順序檢查代碼，依次檢查語(yǔ)句1和2后，再檢查語(yǔ)句4，此時(shí)Wong1 SOS的Exam值=20%。Wong1強(qiáng)調(diào)aef的作用，故語(yǔ)句1、2、4、15是錯(cuò)誤語(yǔ)句的可疑度同為最高，而Jaccard綜合考慮 anf、aep、aef的作用，語(yǔ)句4就變得最為可疑。在這個(gè)例子中，Jaccard要優(yōu)于Wong1。但是一旦測(cè)試用例發(fā)生變化，又或者換做其他程序，Jaccard和Wong1各有千秋。

4 線性錯(cuò)誤定位模型

Weka是一個(gè)開(kāi)源平臺(tái)，實(shí)現(xiàn)了眾多的機(jī)器學(xué)習(xí)算法和數(shù)據(jù)挖掘工具[21]?？紤]到錯(cuò)誤定位模型需要適應(yīng)大型軟件，只選取那些能輸出線性模型的分類算法，共找到四個(gè)算法完成實(shí)驗(yàn)。

要學(xué)習(xí)程序的錯(cuò)誤定位模型，先收集其標(biāo)注錯(cuò)誤代碼的舊版本，所有可執(zhí)行語(yǔ)句都采集了aep、aef、anp和anf。在這些數(shù)據(jù)上構(gòu)建訓(xùn)練集，具體策略如下：

訓(xùn)練集生成算法

輸入 程序的舊版本集{V1,V2,…,VQ}。

輸出 訓(xùn)練集LCtrain。

Begin

LCtrain=?；

index=0；//保持樣本類別的平衡

Fori=1toQ

/*UFault是Vi錯(cuò)誤語(yǔ)句的集合，M是其語(yǔ)句條數(shù)。UOK是Vi正確語(yǔ)句的集合，N是其語(yǔ)句條數(shù)。F(j)或F(k)是第j（或 k）條語(yǔ)句的特征，j（或 k）=1，2，…，M(N)。*/

Forj=1toM

Fork=1toN

label=true； //樣本的類別

Sample=F(j)-F(k)；

Ifindex%2==0

/*保證兩種類別的樣本個(gè)數(shù)相同*/

Sample=Sample*（-1）；

label=false；

End If

LCtrain=LCtrain+(Sample,label)；

index=index+1；

End For

End For

End For

End

將訓(xùn)練集輸入Weka，經(jīng)分類算法學(xué)習(xí)后，優(yōu)化目標(biāo)位使得LCtrain的誤分類個(gè)數(shù)最少，便可獲得線性模型w。若新版本程序有特征為F的語(yǔ)句，其錯(cuò)誤可疑度=w1F1+w2F2+…+wDFD，D是特征維數(shù)。

令L=M×N ，訓(xùn)練集LCtrain的樣本集合{（Sample，label）}形式化為{(xi,yi)},i=1,2,…,L,xi∈Rn,yi∈{-1,+1}。LibLinear是機(jī)器學(xué)習(xí)社區(qū)知名的線性分類算法，用于解決擁有巨量特征和大規(guī)模樣本的分類問(wèn)題。LibLinear的SVMType選擇1，其余參數(shù)全部采用缺省值，算法解決無(wú)約束優(yōu)化問(wèn)題1[22]：

其中T表示矩陣的轉(zhuǎn)置，C是懲罰因子。

Logistic是線性分類的logistic回歸，在一個(gè)經(jīng)轉(zhuǎn)換的目標(biāo)變量上建立線性模型。Logistic回歸是非常經(jīng)典的分類算法，在眾多領(lǐng)域都有成熟的應(yīng)用，其解決優(yōu)化問(wèn)題2[19]：

其中l(wèi)n表示自然對(duì)數(shù)，exp表示自然指數(shù)。算法采用Weka的缺省參數(shù)。

SGD（Stochastic Gradient Descent）能學(xué)習(xí)不同的線性分類模型，包括兩類別的支持向量機(jī)、兩類別的logistic回歸等。而SMO（Sequential Minimal Optimization）只能訓(xùn)練支持向量機(jī)的分類模型。兩者的優(yōu)化問(wèn)題都與LibLinear相同[21]，但使用不同策略解決優(yōu)化問(wèn)題。LibLinear用了坐標(biāo)下降法和信賴域牛頓方法，SGD使用隨機(jī)梯度下降方法，SMO則采用序貫最小優(yōu)化策略。SGD和SMO用Weka的缺省參數(shù)。

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

本文的方法與九種SBFL技術(shù)的實(shí)驗(yàn)比較結(jié)果。所有實(shí)驗(yàn)在一臺(tái)配置Intel Core i3-3220 3.3 GHz CPU和4 GB物理內(nèi)存的計(jì)算機(jī)上完成，操作系統(tǒng)是Windows Server 2003，調(diào)用MinGW5.1的gcc和gcov編譯程序和收集覆蓋信息。

5.1 實(shí)驗(yàn)數(shù)據(jù)集

Siemens套件、程序集space和gzip很受歡迎，成為軟件錯(cuò)誤定位領(lǐng)域的基準(zhǔn)數(shù)據(jù)集，許多研究者在論文中使用它說(shuō)明新算法的有效性。Siemens共有7個(gè)程序集：print_tokens、print_tokens2、replac、tcas、tot_info、schedule和schedule2。

原replace共有32個(gè)缺陷版本，其v27無(wú)失敗的測(cè)試用例，無(wú)法比較各種算法，故而將該缺陷版本排除在外，剩下31個(gè)缺陷版本。同樣的原因，還去掉了schedule2的一個(gè)版本v9。原space有38個(gè)缺陷版本，其v1、v2、v32、v34無(wú)失敗的測(cè)試用例；v25和v30的錯(cuò)誤代碼是指針問(wèn)題，測(cè)試用例執(zhí)行后，導(dǎo)致程序崩潰，MinGW的gcov無(wú)法記錄覆蓋信息；將這6個(gè)版本排除在外，剩下32個(gè)缺陷版本。另外，修改了space的v26和v35，在錯(cuò)誤的指針語(yǔ)句前，加了判斷指針是否為空的語(yǔ)句，避免程序崩潰。SIR軟件項(xiàng)目基礎(chǔ)資源庫(kù)為每個(gè)程序集提供了多種測(cè)試覆蓋類型：bigcov、bigrand、universe、cov和rand等，本文選擇universe完成所有實(shí)驗(yàn)。表1是所有實(shí)驗(yàn)程序的基本信息。

5.2 特征選擇及實(shí)驗(yàn)驗(yàn)證策略

本文的方法，表示可執(zhí)行語(yǔ)句的特征個(gè)數(shù)不受限制。為了與SBFL公平比較。使用了與四元組 ＜aep,aef,anp,anf＞有關(guān)的四個(gè)特征：aef/AF,aep/AP,anf/(AF+aep),anp/(anp+anf),其中AF=aef+anf,AP=aep+anp。顯然，這些特征的值在實(shí)數(shù)區(qū)間[0，1]，當(dāng)錯(cuò)誤語(yǔ)句與正確語(yǔ)句特征值相減，訓(xùn)練集樣本的特征值處于[-1，+1]。這樣就省去了Weka的數(shù)據(jù)預(yù)處理步驟。

使用十折交叉驗(yàn)證的策略完成所有實(shí)驗(yàn)。對(duì)每個(gè)程序集，將其版本平均分為10份，9份作舊版本集構(gòu)造訓(xùn)練集，1份作新版本測(cè)試集。使用四個(gè)分類算法在訓(xùn)練集學(xué)習(xí)到模型后，計(jì)算出測(cè)試集的錯(cuò)誤定位性能。不足10份的程序集，如print_tokens、schedule和schedule2，部分版本重復(fù)填入測(cè)試集，但保證一個(gè)版本不會(huì)同時(shí)出現(xiàn)在訓(xùn)練集和測(cè)試集。所有試驗(yàn)結(jié)果都是10折的平均值。

5.3 實(shí)驗(yàn)結(jié)果對(duì)比

Siemens的實(shí)驗(yàn)數(shù)據(jù)是七個(gè)對(duì)象的平均值。表2、表3和表4是九種常見(jiàn)SBFL方法和Logistic分別在Siemens、space和gzip上的Exam值比較。表現(xiàn)最好的數(shù)據(jù)用黑體字標(biāo)示，表中Exam值省略了百分符號(hào)。Wong1只與aef有關(guān)，在那些只有一條錯(cuò)誤語(yǔ)句的程序上，依Best策略，Wong1一定優(yōu)于其他技術(shù)。在Siemens和gzip上，Wong1 Best都顯著優(yōu)于其他技術(shù)的Best策略。除此之外，依三種策略Logistic都優(yōu)于其他方法，特別在程序集space表現(xiàn)出顯著優(yōu)勢(shì)。Ochiai盡管在Siemens和gzip表現(xiàn)不佳，在space上卻僅次于Logistic。Lucia等人[4]在比較40種SBFL技術(shù)后，發(fā)現(xiàn)Ochiai在許多程序上表現(xiàn)優(yōu)異。另外，NaishO、NaishOp和Wong3在 Siemens和gzip上，Kulczynski2[7]在 Siemens上，也都有好的性能。相比而言，其他方法無(wú)法顯示競(jìng)爭(zhēng)性。

Weka另外三種算法也都不輸給Logistic。調(diào)試軟件的實(shí)際過(guò)程中，SOS可用，而B(niǎo)est和Worst不可用，因此后文只比較SOS策略。表5是三種算法與Logistic算法依SOS策略，在三個(gè)數(shù)據(jù)集上的Exam值比較。表中的正值表示對(duì)應(yīng)算法弱于Logistic，負(fù)值則強(qiáng)于Logistic。以LibLinear為例，在Siemens上，它比Logistic差，要多檢查0.27%的語(yǔ)句，才能找到第一條錯(cuò)誤語(yǔ)句；在space上，則略好于Logistic；在gzip上，兩者打成平手。綜合來(lái)看，四種算法中，SGD表現(xiàn)最好，SMO表現(xiàn)最差。

表1 實(shí)驗(yàn)程序的基本信息

表2 Siemens程序包上的Exam值比較

表3 程序集space上的Exam值比較

表4 程序集gzip上的Exam值比較

當(dāng)程序較大，而錯(cuò)誤語(yǔ)句的可疑度靠后，程序員檢查較多語(yǔ)句后，仍未能定位到錯(cuò)誤代碼，會(huì)產(chǎn)生厭煩情緒。通常，SBFL研究社區(qū)會(huì)限制檢查比例Pcheck（已檢查語(yǔ)句數(shù)占程序語(yǔ)句總數(shù)的比率），計(jì)算出PbugVers（能發(fā)現(xiàn)錯(cuò)誤版本數(shù)占程序版本總數(shù)的比率），來(lái)比較各類技術(shù)的優(yōu)劣。圖2和圖3分別在Siemens和gzip上比較各類方法，Pcheck從1%到20%，步長(zhǎng)1%。圖中所有技術(shù)都依SOS策略。

表5 三種算法與Logistic算法SOS策略的Exam值比較

圖2 Siemens程序包的PbugVers比較

圖3 gzip程序集的PbugVers比較

如圖2所示，在Siemens上，Logistic表現(xiàn)最好，只在 Pcheck=1%處略差外，其余點(diǎn)都優(yōu)于其他方法。Kulczynski2、SMO、NashiO和Wong3差不多，Tarantula則遜色不少。使圖清晰起見(jiàn)，未列出另外五種SBFL和兩種分類算法的結(jié)果。實(shí)際上，LibLinear與SMO相似，SGD略好于Logistic，NashiOp與NashiO相同，其余四種SBFL顯著落后于SMO。如圖3所示，在gzip上，LibLinear和NashiOp表現(xiàn)最好，相比它們，SGD和Wong3略差一點(diǎn)，Jaccard和Ochiai則差了很多?？疾煳戳谐龅奈宸NSBFL方法和兩種分類算法，Logistic和LibLinear完全相同，SMO略差于SGD，NashiO與NashiOp完全相同，其余四種SBFL顯著落后于SGD。在space上，檢查同樣比例的代碼，四種分類算法找出錯(cuò)誤的版本數(shù)目都顯著多于九類SBFL方法?？偟膩?lái)看，以PbugVers為評(píng)價(jià)指標(biāo)，本文的方法無(wú)疑最有競(jìng)爭(zhēng)力。

6 結(jié)論

為輔助程序員盡快定位軟件的錯(cuò)誤代碼，人們提出來(lái)許多的SBFL方法，利用測(cè)試結(jié)果，逐條計(jì)算語(yǔ)句的錯(cuò)誤可疑度。不過(guò)，各種SBFL無(wú)外乎將四個(gè)運(yùn)行特征組合成不同的映射函數(shù)，將可執(zhí)行語(yǔ)句的運(yùn)行特征映射成一個(gè)實(shí)數(shù)值。這些映射函數(shù)采用固定形式，無(wú)法適應(yīng)程序規(guī)模、測(cè)試用例分布、程序員開(kāi)發(fā)習(xí)慣等迥異的各類情況。如果軟件開(kāi)發(fā)過(guò)程、維護(hù)過(guò)程還收集到其他有用信息，如何修改映射函數(shù)是一個(gè)難題。相比而言，設(shè)計(jì)了巧妙的訓(xùn)練集生成算法，采用機(jī)器學(xué)習(xí)方法，能從程序舊版本學(xué)習(xí)到該程序獨(dú)有的可疑度計(jì)算公式，算法也容易集成其他程序特征。

選取了Weka中能輸出線性模型的四個(gè)分類算法，Logistic、SGD、SMO和LibLinear檢驗(yàn)方法的有效性。在Siemens程序包、space和gzip三個(gè)基準(zhǔn)數(shù)據(jù)集上，實(shí)驗(yàn)結(jié)果證實(shí)，無(wú)論是比較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].軟件學(xué)報(bào)，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]陳翔，鞠小林，文萬(wàn)志，等.基于程序頻譜的動(dòng)態(tài)缺陷定位方法研究[J].軟件學(xué)報(bào)，2015，26（2）：390-412.

[12]王克朝，王甜甜，蘇小紅，等.軟件錯(cuò)誤自動(dòng)定位關(guān)鍵科學(xué)問(wèn)題及研究進(jìn)展[J].計(jì)算機(jī)學(xué)報(bào)，2015，38（11）：2262-2278.

[13]羅三定，彭瓊，李婷.瓷磚圖像的紋理特征分類研究[J].計(jì)算機(jī)工程與應(yīng)用，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

湖南省科技計(jì)劃項(xiàng)目（No.2015GK3071）；長(zhǎng)沙市科技計(jì)劃項(xiàng)目（No.K1509011-11）。

何海江（1970—），男，副教授，主要從事機(jī)器學(xué)習(xí)、軟件測(cè)試的研究，E-mail：haijianghe@sohu.com。

2016-06-13

2016-07-29

1002-8331（2017）21-0042-07

CNKI網(wǎng)絡(luò)優(yōu)先出版：2016-11-21,http://www.cnki.net/kcms/detail/11.2127.TP.20161121.2049.086.html