基于半監督學習方法的軟件故障定位研究

?

基于半監督學習方法的軟件故障定位研究

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

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

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

關鍵詞:軟件故障定位;半監督學習;協同訓練算法;訓練樣本

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

針對標記樣本獲取困難這一問題，本文提出基于半監督學習的軟件故障定位方法，應用Zhou等人給出的一種命名為Co-Trade的協同訓練風范的半監督學習算法［2］，同時使用軟件靜態屬性和動態屬性進行協同訓練分類，從而實現軟件故障定位。本文采用的軟件故障定位模型基于語句級別。

1　基于機器學習的軟件故障定位

機器學習算法是一類從數據中自動分析獲得規律，并利用規律對未知數據進行預測的算法，已廣泛應用于各個領域。在軟件故障定位中，也已經取得一定研究成果。

1．1基于監督學習軟件故障定位

監督學習是學習器通過對有標記的訓練樣本進行學習，建立模型用于預測未知示例樣本的標記。

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

Briand等［6］采用C4．5決策樹從測試用例輸入輸出中識別出導致測試失敗的條件，認為相同條件下執行失敗的測試用例由相同原因導致，因此對失敗測試用例覆蓋的語句進行歸類和排名，從而達到對Tarantula語句可疑度排名的改進。

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

1．2半監督學習技術在軟件故障定位中的應用

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

在軟件故障定位中，目前尚未有基于半監督學習進行軟件故障定位的研究成果。本文通過對軟件故障定位技術及特點的分析，以及半監督學習算法進行學習研究，結合實際項目標記樣本獲取困難且成本高昂的實際情況，提出采用一種協同風范的半監督學習算法——Co-Trade進行軟件故障定位。

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

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

2．1Co-Trade算法優點

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

2．2Co-Trade算法描述

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

算法1 Co-Training算法

輸入:

標記數據集合L

無標記數據集合U

算法步驟:

Step1建立無標記數據池U'，用來存放U中隨機抽取的無標記數據;

Step2循環K輪;

Step2．1利用L與x1視圖訓練出分類器h1;

Step2．2利用L與x2視圖訓練出分類器h2;

Step2．3利用h1從U'中標記出p個正類和n個負類示例;

Step2．4利用h2從U'中標記出p個正類和n個負類示例;

Step2．5將這些新標記數據加入L;

Step2．6從U中隨機抽取2p + 2n個無標記示例至U。

Step3退出循環。

輸出:經過訓練的分類器h1和h2。

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

算法2樣本標記可信度計算

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

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

Step2在zp和zq間建立一條邊

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

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

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

最終由Angluin＆Laird噪音學習理論可以得到Co-Trade每次迭代錯誤率的準確值為:

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

2．3故障定位特征選擇

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

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

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

2)函數復雜度: Fcmt;

3)語句行數: Flc;

4)最大深度: Fmd;

5)內部函數調用次數: Ffc。

2．4評價指標

本文算法應用中，將正確程序語句稱為正樣本，錯誤語句稱為負樣本，測試程序集中所有可招待語句最終都會得到一個分類結果，即為正或者為負。因此，可以采用機器學習分類中的2個衡量指標對故障預測性能進行評價，即分類準確率和查全率:

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

3　實驗及結果分析

3．1Siemens Suite實驗數據集

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

表1　Siemens Suite數據集信息

3．2實驗模型設計

我們將所選擇的3個程序在matlab中分別在監督學習算法和Co-Trade算法中進行實驗，獲得各自分類準確率和錯誤定位準確率。

1)數據處理

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

2)樣本分配

用L－data表示標記樣本，U－data表示未標記樣本，T－data表示測試樣本;為了達到半監督學習效果，在CoTrade算法應用中，未標記樣本的數量我們按照L－data∶U－data＜1∶7的規則進行未標記樣本數量控制;而測試樣本與標記樣本的比率按照L－data∶T－data＜1∶2規則控制。

3)屬性劃分

協同訓練中，需要同時訓練兩個分類器，我們將動態屬性分為一組，靜態屬性分為另外一組。Tcas實驗數據的標記樣本如表2、表3所示:

表2　Tcas標記樣本動態屬性矩陣

表3　Tcas標記樣本靜態屬性矩陣

3．3實驗結果分析

實驗中，對同一組數據集，我們在Co-Trade算法和相應監督學習分類算法中所采用的標記樣本和測試樣本相同，3組程序所獲得的試驗結果如表4所示:

表4　實驗結果數據

根據在Siemens Suite數據集中的實驗結果，我們可以得到如下結論:

1)在標記樣本數量相同情況下，采用相同分類器，Co-Trade算法的分類準確率整體高于監督學習算法;

2)在故障查全率指標中，Co-Trade算法在schedule和tcas中均可以達到100%，沒有錯誤語句的遺漏;在tot－info中，也達到90．91%，故障查全率非常穩定。而監督學習算法，由于標記樣本數量較少，其預測準確率和故障查全率平均水平都比較低，穩定性也比較差。

3) SVM分類器在本次實驗監督學習過程中，由于標記樣本數量過少，無法達到訓練分類器效果，因此沒有得到監督學習實驗數據。

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

4　結論

本文將半監督學習方法應用于軟件故障定位中，為軟件故障定位給出了一種新思路。實驗表明，在標記樣本數量較少的情況下，使用Co-Trade算法進行軟件故障定位的準確率和故障查全率都高于傳統監督學習方法，且錯誤遺漏情況極少。

我們的后期工作將主要集中在兩個方面: 1)研究半監督學習領域解決數據傾斜的算法，找到解決軟件故障定位中正負樣本嚴重不平衡問題的有效方法; 2)將半監督學習算法應用于更多數據集以及不同領域實際項目(如電子商務系統，Web服務等)的軟件故障定位中，驗證其適用范圍和有效性。

參考文獻:

［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—)，西北工業大學副教授，主要從事軟件工程、軟件測試的研究。

收稿日期:2014-10-28

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

文獻標志碼:A

中圖分類號:TP311．5