?

基于半監(jiān)督學(xué)習(xí)方法的軟件故障定位研究

鄭煒，吳瀟雪，譚鑫，彭耀鵬，楊帥

(西北工業(yè)大學(xué)軟件與微電子學(xué)院，陜西西安710072)

摘要:故障定位是軟件工程中最為耗時(shí)和昂貴的活動(dòng)之一，為降低軟件故障定位的成本及提高故障定位的效率，機(jī)器學(xué)習(xí)方法被廣泛應(yīng)用于自動(dòng)化軟件故障定位中。傳統(tǒng)的監(jiān)督學(xué)習(xí)方法需要獲取大量標(biāo)記樣本，這在實(shí)際項(xiàng)目中相當(dāng)困難，且費(fèi)用高昂。針對(duì)這一問(wèn)題，提出采用半監(jiān)督學(xué)習(xí)方法進(jìn)行軟件故障定位的思想，故障定位基于語(yǔ)句級(jí)別，通過(guò)應(yīng)用程序中可執(zhí)行語(yǔ)句與測(cè)試用例執(zhí)行之間動(dòng)態(tài)屬性、以及傳統(tǒng)軟件故障定位中較有效的若干靜態(tài)屬性實(shí)現(xiàn)協(xié)同訓(xùn)練目的，得到訓(xùn)練良好的分類器，然后用該分類器對(duì)程序其余語(yǔ)句進(jìn)行分類，從而得到故障語(yǔ)句。文章最后在Siemens Suite數(shù)據(jù)集中對(duì)算法進(jìn)行驗(yàn)證，通過(guò)與傳統(tǒng)監(jiān)督學(xué)習(xí)算法進(jìn)行對(duì)比，證明半監(jiān)督學(xué)習(xí)算法在軟件故障定位中的有效性。

關(guān)鍵詞:軟件故障定位;半監(jiān)督學(xué)習(xí);協(xié)同訓(xùn)練算法;訓(xùn)練樣本

軟件故障定位是軟件調(diào)試過(guò)程中最為耗時(shí)和合耗資源的活動(dòng)之一。為了減輕程序員手工排查程序語(yǔ)句的工作量，提高代碼調(diào)試效率和可靠性，研究人員提出了一系列自動(dòng)化的故障定位方法。機(jī)器學(xué)習(xí)方法被廣泛采用?；诒O(jiān)督學(xué)習(xí)方法應(yīng)用較廣，且可靠性高。但是存在一個(gè)重要問(wèn)題，就是大量標(biāo)記樣本的獲取，因?yàn)樵趯?shí)際項(xiàng)目中大量標(biāo)記樣本的獲取極其困難且代價(jià)高昂［1］。

針對(duì)標(biāo)記樣本獲取困難這一問(wèn)題，本文提出基于半監(jiān)督學(xué)習(xí)的軟件故障定位方法，應(yīng)用Zhou等人給出的一種命名為Co-Trade的協(xié)同訓(xùn)練風(fēng)范的半監(jiān)督學(xué)習(xí)算法［2］，同時(shí)使用軟件靜態(tài)屬性和動(dòng)態(tài)屬性進(jìn)行協(xié)同訓(xùn)練分類，從而實(shí)現(xiàn)軟件故障定位。本文采用的軟件故障定位模型基于語(yǔ)句級(jí)別。

1　基于機(jī)器學(xué)習(xí)的軟件故障定位

機(jī)器學(xué)習(xí)算法是一類從數(shù)據(jù)中自動(dòng)分析獲得規(guī)律，并利用規(guī)律對(duì)未知數(shù)據(jù)進(jìn)行預(yù)測(cè)的算法，已廣泛應(yīng)用于各個(gè)領(lǐng)域。在軟件故障定位中，也已經(jīng)取得一定研究成果。

1．1基于監(jiān)督學(xué)習(xí)軟件故障定位

監(jiān)督學(xué)習(xí)是學(xué)習(xí)器通過(guò)對(duì)有標(biāo)記的訓(xùn)練樣本進(jìn)行學(xué)習(xí)，建立模型用于預(yù)測(cè)未知示例樣本的標(biāo)記。

Wong等人［4-5］先后提出基于BP神經(jīng)網(wǎng)絡(luò)和RBF神經(jīng)網(wǎng)絡(luò)的軟件故障定位模型，在這2個(gè)模型中，每個(gè)測(cè)試用例的覆蓋信息(覆蓋了哪些語(yǔ)句)和相應(yīng)執(zhí)行結(jié)果(成功或失敗)構(gòu)建成一張二維表，用于訓(xùn)練BP/RBF神經(jīng)網(wǎng)絡(luò)。然后用這種學(xué)習(xí)了測(cè)試用例與語(yǔ)句之間覆蓋關(guān)系的神經(jīng)網(wǎng)絡(luò)模型對(duì)虛擬測(cè)試用例(每個(gè)測(cè)試用例只覆蓋一條語(yǔ)句)進(jìn)行預(yù)測(cè)，從而得到每條語(yǔ)句包含bug的可能性。

Briand等［6］采用C4．5決策樹從測(cè)試用例輸入輸出中識(shí)別出導(dǎo)致測(cè)試失敗的條件，認(rèn)為相同條件下執(zhí)行失敗的測(cè)試用例由相同原因?qū)е拢虼藢?duì)失敗測(cè)試用例覆蓋的語(yǔ)句進(jìn)行歸類和排名，從而達(dá)到對(duì)Tarantula語(yǔ)句可疑度排名的改進(jìn)。

然而，大量實(shí)驗(yàn)結(jié)果和文獻(xiàn)數(shù)據(jù)表明數(shù)據(jù)的質(zhì)量和比例是訓(xùn)練良好的分類器進(jìn)行故障定位的2個(gè)重要因素。但是，準(zhǔn)確可靠的軟件質(zhì)量標(biāo)簽只有經(jīng)過(guò)詳盡、完整的軟件測(cè)試和對(duì)錯(cuò)誤的精確定位才能得到，并且源代碼中錯(cuò)誤語(yǔ)句的比例要比正確語(yǔ)句的比例低得多，此過(guò)程耗時(shí)較長(zhǎng)且成本較高。因而，這些都限制了基于監(jiān)督學(xué)習(xí)軟件故障定位算法的發(fā)展和實(shí)際項(xiàng)目應(yīng)用。但是，如果放棄這些標(biāo)記樣本，僅僅使用無(wú)標(biāo)簽的樣本數(shù)據(jù)進(jìn)行無(wú)監(jiān)督學(xué)習(xí)又會(huì)使得標(biāo)記的樣本數(shù)據(jù)失去價(jià)值，且非監(jiān)督學(xué)習(xí)效果并不理想。因此，怎樣更好地利用這2種數(shù)據(jù)成為一個(gè)很受關(guān)注的難題。為了解決這一困難，人們提出了半監(jiān)督學(xué)習(xí)方法，該方法能夠同時(shí)利用好這2種樣本，達(dá)到更好的分類結(jié)果。

1．2半監(jiān)督學(xué)習(xí)技術(shù)在軟件故障定位中的應(yīng)用

半監(jiān)督學(xué)習(xí)的基本設(shè)置是給定一個(gè)來(lái)自某未知分布的有標(biāo)記示例集以L = { (x1，y1)，(x2，y2)，…，(x| L|，y| L|) }及一個(gè)未標(biāo)記示例集U = { x1，x2，…，x| U|，期望函數(shù)f∶X→Y可以準(zhǔn)確的對(duì)示例x預(yù)測(cè)其標(biāo)記y。這里xi，x'j∈X均為d維向量，yi∈Y為示例xi的標(biāo)記，| L |和| U|分別為L(zhǎng)和U的大小，即它們所包含的示例數(shù)。

在軟件故障定位中，目前尚未有基于半監(jiān)督學(xué)習(xí)進(jìn)行軟件故障定位的研究成果。本文通過(guò)對(duì)軟件故障定位技術(shù)及特點(diǎn)的分析，以及半監(jiān)督學(xué)習(xí)算法進(jìn)行學(xué)習(xí)研究，結(jié)合實(shí)際項(xiàng)目標(biāo)記樣本獲取困難且成本高昂的實(shí)際情況，提出采用一種協(xié)同風(fēng)范的半監(jiān)督學(xué)習(xí)算法——Co-Trade進(jìn)行軟件故障定位。

2　基于Co-Trade算法故障定位模型

本文采用的軟件故障定位模型中，故障定位基于語(yǔ)句級(jí)別，我們將程序中的語(yǔ)句作為樣本。假設(shè)程序P由語(yǔ)句集S構(gòu)成，對(duì)于S中的任意一條語(yǔ)句s，其分類結(jié)果有2種可能性: True或者False，我們用結(jié)果True表示該語(yǔ)句不包含任何故障，用False表示語(yǔ)句包含故障，從而確定出故障存在的位置。

2．1Co-Trade算法優(yōu)點(diǎn)

Co-Training算法在文本處理方面具有絕對(duì)優(yōu)勢(shì)，在對(duì)經(jīng)典半監(jiān)督學(xué)習(xí)算法進(jìn)行分別學(xué)習(xí)和對(duì)比后，我們選擇Co-Training作為基礎(chǔ)。Co-Trade算法是Goldman和Zhou［2］在Co-Training算法基礎(chǔ)上提出的一種基于切割邊緣權(quán)重統(tǒng)計(jì)的數(shù)據(jù)編輯技術(shù)進(jìn)行優(yōu)化的算法。該算法在測(cè)試標(biāo)記的準(zhǔn)確性、確定標(biāo)記的可信度以及確定下一迭代的新標(biāo)記數(shù)據(jù)方面進(jìn)行了改進(jìn)。在測(cè)試標(biāo)記的準(zhǔn)確性上，Co-Trade算法中采用了多次交叉十倍驗(yàn)證的方法;在確定標(biāo)記的可信度方面，使用基于切割邊緣權(quán)重統(tǒng)計(jì)的數(shù)據(jù)編輯技術(shù)。因此其分類可信度比Co-Training算法要高。

2．2Co-Trade算法描述

Co-Trade算法是Co-Training算法基礎(chǔ)上加入了可信度計(jì)算，從而達(dá)到訓(xùn)練處高可信度分類器的效果。因此，我們首先在算法1中對(duì)標(biāo)準(zhǔn)協(xié)同訓(xùn)練算法Co-Training進(jìn)行描述。Co-Training要求數(shù)據(jù)集有2個(gè)充分冗余視圖，即滿足如下條件的數(shù)據(jù)集:①每個(gè)數(shù)據(jù)集都足以描述該問(wèn)題;②每個(gè)屬性都條件獨(dú)立于第二個(gè)數(shù)據(jù)集。標(biāo)準(zhǔn)的協(xié)同算法在2個(gè)視圖上利用有標(biāo)記示例分別訓(xùn)練出一個(gè)分類器。然后，在協(xié)同訓(xùn)練過(guò)程沖，每一個(gè)分類器從無(wú)標(biāo)記示例中挑選出若干可信度較高的示例進(jìn)行標(biāo)記，并把標(biāo)記后的示例進(jìn)行更新。不斷迭代進(jìn)行，直到達(dá)到特定條件。

算法1 Co-Training算法

輸入:

標(biāo)記數(shù)據(jù)集合L

無(wú)標(biāo)記數(shù)據(jù)集合U

算法步驟:

Step1建立無(wú)標(biāo)記數(shù)據(jù)池U'，用來(lái)存放U中隨機(jī)抽取的無(wú)標(biāo)記數(shù)據(jù);

Step2循環(huán)K輪;

Step2．1利用L與x1視圖訓(xùn)練出分類器h1;

Step2．2利用L與x2視圖訓(xùn)練出分類器h2;

Step2．3利用h1從U'中標(biāo)記出p個(gè)正類和n個(gè)負(fù)類示例;

Step2．4利用h2從U'中標(biāo)記出p個(gè)正類和n個(gè)負(fù)類示例;

Step2．5將這些新標(biāo)記數(shù)據(jù)加入L;

Step2．6從U中隨機(jī)抽取2p + 2n個(gè)無(wú)標(biāo)記示例至U。

Step3退出循環(huán)。

輸出:經(jīng)過(guò)訓(xùn)練的分類器h1和h2。

Co-Trade算法的改進(jìn)核心是加入了樣本可信度計(jì)算，從而選擇可信度較高的樣本對(duì)分類器進(jìn)行訓(xùn)練，最終得到置信度較高的分類器。算法2是對(duì)可信度計(jì)算方法的具體描述。

算法2樣本標(biāo)記可信度計(jì)算

假定有一個(gè)圖G:圖的每一個(gè)頂點(diǎn)代表一個(gè)標(biāo)記示例(zp，yp)。

Step1判斷G中任意2個(gè)頂點(diǎn)zp和zq，若zp屬于zq的最近K個(gè)鄰居。若是，則進(jìn)入Step2，否則進(jìn)入Step3;

Step2在zp和zq間建立一條邊

Step5計(jì)算Jp=wpqIpq，其中Cp是點(diǎn)zq的最K鄰近集合;

Step6由大數(shù)定律推得(zp，fq)的可信度為: CFz(zp，yq) = 1－Φ()。

在確定下一迭代的新標(biāo)記數(shù)據(jù)方面，Co-Trade依舊考慮了新標(biāo)記數(shù)據(jù)的噪聲問(wèn)題。若視圖1確定的新標(biāo)記數(shù)據(jù)為(u'1)，那么加入視圖2訓(xùn)練器的噪聲率為:

最終由Angluin＆Laird噪音學(xué)習(xí)理論可以得到Co-Trade每次迭代錯(cuò)誤率的準(zhǔn)確值為:

最終我們只要求得使錯(cuò)誤率最小的新標(biāo)記數(shù)據(jù)集合，并把它加入另一個(gè)分類器的下一輪訓(xùn)練數(shù)據(jù)集合中即可。Co-Trade算法可以支持樸素貝葉斯NB、支持向量機(jī)SVM以及決策樹CART 3種分類器。

2．3故障定位特征選擇

Jones等人［7］認(rèn)為程序語(yǔ)句存在故障的可能性與它被失敗用例執(zhí)行的次數(shù)正相關(guān)，提出了用顏色可視化表示語(yǔ)句存在故障的可疑程度，并實(shí)現(xiàn)了可視化故障定位工具Tarantula。

基于Tarantula啟發(fā)，對(duì)于每條可執(zhí)行語(yǔ)句，我們給出覆蓋該語(yǔ)句的測(cè)試用例執(zhí)行成功比率和語(yǔ)句的測(cè)試用例覆蓋率2個(gè)動(dòng)態(tài)屬性，分別用Ssr，Scr表示;同時(shí)，我們選擇5個(gè)在軟件故障預(yù)測(cè)中常用的靜態(tài)屬性協(xié)同進(jìn)行故障定位，分別為:

1)語(yǔ)句所包含操作符個(gè)數(shù): Soc;

2)函數(shù)復(fù)雜度: Fcmt;

3)語(yǔ)句行數(shù): Flc;

4)最大深度: Fmd;

5)內(nèi)部函數(shù)調(diào)用次數(shù): Ffc。

2．4評(píng)價(jià)指標(biāo)

本文算法應(yīng)用中，將正確程序語(yǔ)句稱為正樣本，錯(cuò)誤語(yǔ)句稱為負(fù)樣本，測(cè)試程序集中所有可招待語(yǔ)句最終都會(huì)得到一個(gè)分類結(jié)果，即為正或者為負(fù)。因此，可以采用機(jī)器學(xué)習(xí)分類中的2個(gè)衡量指標(biāo)對(duì)故障預(yù)測(cè)性能進(jìn)行評(píng)價(jià)，即分類準(zhǔn)確率和查全率:

式中，tp表示分類結(jié)果為正且預(yù)期結(jié)果也為正(True Positive) ; tn表示實(shí)際分類結(jié)果為負(fù)且預(yù)期結(jié)果也為負(fù)(True Negtive) ; fp表示實(shí)際分類結(jié)果為正而預(yù)期結(jié)果為負(fù)的(False Positive) ; fn表示實(shí)際分類結(jié)果為負(fù)且預(yù)期結(jié)果亦為負(fù)的(False Negtive)。

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

3．1Siemens Suite實(shí)驗(yàn)數(shù)據(jù)集

本文采用Siemens Suite作為算法評(píng)價(jià)數(shù)據(jù)集。Siemens Suite是一組開源的用于評(píng)測(cè)軟件故障定位方法和工具的數(shù)據(jù)集，自從2003年被引入用于評(píng)價(jià)NNQ法的有效性后，被廣泛采用以評(píng)估錯(cuò)誤定位技術(shù)的有效性。本次實(shí)驗(yàn)中我們選擇了其中3個(gè)程序，具體信息如表1所示:

表1　Siemens Suite數(shù)據(jù)集信息

3．2實(shí)驗(yàn)?zāi)Ｐ驮O(shè)計(jì)

我們將所選擇的3個(gè)程序在matlab中分別在監(jiān)督學(xué)習(xí)算法和Co-Trade算法中進(jìn)行實(shí)驗(yàn)，獲得各自分類準(zhǔn)確率和錯(cuò)誤定位準(zhǔn)確率。

1)數(shù)據(jù)處理

由于實(shí)際項(xiàng)目中的正確樣本和錯(cuò)誤樣本比例較高，Siemens Suite也不例外，即數(shù)據(jù)挖掘中的數(shù)據(jù)傾斜較嚴(yán)重，這會(huì)嚴(yán)重影響分類器訓(xùn)練效果，因此，本次實(shí)驗(yàn)中我們采取規(guī)避的方法，對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行預(yù)處理，所有錯(cuò)誤語(yǔ)句全部保留，而正確語(yǔ)句按照正負(fù)比例5: 1隨機(jī)選擇其中一部分納入實(shí)驗(yàn)。

2)樣本分配

用L－data表示標(biāo)記樣本，U－data表示未標(biāo)記樣本，T－data表示測(cè)試樣本;為了達(dá)到半監(jiān)督學(xué)習(xí)效果，在CoTrade算法應(yīng)用中，未標(biāo)記樣本的數(shù)量我們按照L－data∶U－data＜1∶7的規(guī)則進(jìn)行未標(biāo)記樣本數(shù)量控制;而測(cè)試樣本與標(biāo)記樣本的比率按照L－data∶T－data＜1∶2規(guī)則控制。

3)屬性劃分

協(xié)同訓(xùn)練中，需要同時(shí)訓(xùn)練兩個(gè)分類器，我們將動(dòng)態(tài)屬性分為一組，靜態(tài)屬性分為另外一組。Tcas實(shí)驗(yàn)數(shù)據(jù)的標(biāo)記樣本如表2、表3所示:

表2　Tcas標(biāo)記樣本動(dòng)態(tài)屬性矩陣

表3　Tcas標(biāo)記樣本靜態(tài)屬性矩陣

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

實(shí)驗(yàn)中，對(duì)同一組數(shù)據(jù)集，我們?cè)贑o-Trade算法和相應(yīng)監(jiān)督學(xué)習(xí)分類算法中所采用的標(biāo)記樣本和測(cè)試樣本相同，3組程序所獲得的試驗(yàn)結(jié)果如表4所示:

表4　實(shí)驗(yàn)結(jié)果數(shù)據(jù)

根據(jù)在Siemens Suite數(shù)據(jù)集中的實(shí)驗(yàn)結(jié)果，我們可以得到如下結(jié)論:

1)在標(biāo)記樣本數(shù)量相同情況下，采用相同分類器，Co-Trade算法的分類準(zhǔn)確率整體高于監(jiān)督學(xué)習(xí)算法;

2)在故障查全率指標(biāo)中，Co-Trade算法在schedule和tcas中均可以達(dá)到100%，沒(méi)有錯(cuò)誤語(yǔ)句的遺漏;在tot－info中，也達(dá)到90．91%，故障查全率非常穩(wěn)定。而監(jiān)督學(xué)習(xí)算法，由于標(biāo)記樣本數(shù)量較少，其預(yù)測(cè)準(zhǔn)確率和故障查全率平均水平都比較低，穩(wěn)定性也比較差。

3) SVM分類器在本次實(shí)驗(yàn)監(jiān)督學(xué)習(xí)過(guò)程中，由于標(biāo)記樣本數(shù)量過(guò)少，無(wú)法達(dá)到訓(xùn)練分類器效果，因此沒(méi)有得到監(jiān)督學(xué)習(xí)實(shí)驗(yàn)數(shù)據(jù)。

4)在同一組實(shí)驗(yàn)中，Co-Trade算法采用決策樹分類器(CART)效果最優(yōu)，樸素貝葉斯(NB)其次，支持向量機(jī)表現(xiàn)最差。

4　結(jié)論

本文將半監(jiān)督學(xué)習(xí)方法應(yīng)用于軟件故障定位中，為軟件故障定位給出了一種新思路。實(shí)驗(yàn)表明，在標(biāo)記樣本數(shù)量較少的情況下，使用Co-Trade算法進(jìn)行軟件故障定位的準(zhǔn)確率和故障查全率都高于傳統(tǒng)監(jiān)督學(xué)習(xí)方法，且錯(cuò)誤遺漏情況極少。

我們的后期工作將主要集中在兩個(gè)方面: 1)研究半監(jiān)督學(xué)習(xí)領(lǐng)域解決數(shù)據(jù)傾斜的算法，找到解決軟件故障定位中正負(fù)樣本嚴(yán)重不平衡問(wèn)題的有效方法; 2)將半監(jiān)督學(xué)習(xí)算法應(yīng)用于更多數(shù)據(jù)集以及不同領(lǐng)域?qū)嶋H項(xiàng)目(如電子商務(wù)系統(tǒng)，Web服務(wù)等)的軟件故障定位中，驗(yàn)證其適用范圍和有效性。

參考文獻(xiàn):

［1］Binkley D．Source Code Analysis: a Road Map［C］∥Proceedings of Future of Software Engineering，Minneapolis，USA，2007: 104-119

［2］Zhang M L，Zhou Z H．CoTrade: Confident Co-Training with Data Editing［J］．IEEE Trans on Systems，Man，and Cybernetics，Part B: Cybernetics，2011，41(6) : 1612-1626

［3］Ali S，Andrews J H，Dhandapani T，et al．Evaluating the Accuracy of Fault Localization Techniques［C］∥Proceedings of the 2009 IEEE/ACM International Conference on Automated Software Engineering，2009: 76-87

［4］Wong W E，Debroy V，Golden R，et al．Effective Software Fault Localization Using an RBF Neural Network［J］．IEEE Trans on Reliability，2012，61(1) : 149-169

［5］Wong W E，Qi Y．BP Neural Network-Based Effective Fault Localization［J］．International Journal of Software Engineering and Knowl6edge Engineering，2009，19(4) : 573-597

［6］Briand L C，Labiche Y，Liu X．Using Machine Learning to Support Debugging with Tarantula［C］∥The 18th IEEE International Symposium on Software Reliability，2007: 137-146

［7］Jones J A，Harrold M J，Stasko J．Visualization of Test Information to Assist Fault Localization［C］∥Proceedings of the 24th International Conference on Software Engineering，2002: 467-477

Software Fault Localization Using Semi-Supervised Learning

Zheng Wei，Wu Xiaoxue，Tan Xin，Peng Yaopeng，Yang Shuai

(Department of Software and Microelectronic Engineering，Northwestern Polytechnical University，Xi'an 710072，China)

Abstract:In order to improve the efficiency of software fault localization，supervised learning methods are widely used in automatic software fault localization．But these methods mostly ignore a very important fact: in order to train a good performance of the classifier through supervised learning method，there must be a large number of labeled samples．While in the actual project，to obtain a large number of labeled samples is quite difficult; even if it can be done，the cost is very high．In order to solve this problem，we propose a semi supervised learning algorithm for software fault location．We adopt a high-creditability and collaborative style of semi supervised learning algorithm named Co-Trade，which uses the dynamic attributes between the programs' executable statements and test case execution as well as some effective static attributes of traditional software fault localization to achieve the purpose of cooperative training．Finally，selecting the Siemens Suite as the test data，we prove the validity of Co-Trade algorithm in software fault localization by comparing it with the traditional supervised learning methods．

Key words:backpropagation algorithms，classification (of information)，classifiers，cost reduction，decision trees，errors，fault detection，MATLAB，software engineering，software testing，support vector machines; Co-Trade，dynamic attributes between the programs' executable statements and test case execution，semi-supervised learning，software fault localization，training data

作者簡(jiǎn)介:鄭煒(1975—)，西北工業(yè)大學(xué)副教授，主要從事軟件工程、軟件測(cè)試的研究。

收稿日期:2014-10-28

文章編號(hào):1000-2758(2015) 02-0332-05

文獻(xiàn)標(biāo)志碼:A

中圖分類號(hào):TP311．5