?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2．2Co-Trade算法描述

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

算法1 Co-Training算法

輸入:

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

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

算法步驟:

Step1建立無標(biāo)記數(shù)據(jù)池U'，用來存放U中隨機(jī)抽取的無標(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個正類和n個負(fù)類示例;

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

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

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

Step3退出循環(huán)。

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

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

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

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

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

Step2在zp和zq間建立一條邊

Step5計算Jp=wpqIpq，其中Cp是點zq的最K鄰近集合;

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

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

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

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

2．3故障定位特征選擇

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

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

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

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

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

4)最大深度: Fmd;

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

2．4評價指標(biāo)

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

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

3　實驗及結(jié)果分析

3．1Siemens Suite實驗數(shù)據(jù)集

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

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

3．2實驗?zāi)Ｐ驮O(shè)計

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

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

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

2)樣本分配

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

3)屬性劃分

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

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

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

3．3實驗結(jié)果分析

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

表4　實驗結(jié)果數(shù)據(jù)

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

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

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

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

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

4　結(jié)論

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

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

參考文獻(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

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

收稿日期:2014-10-28

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

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

中圖分類號:TP311．5