基于貝葉斯的軟件錯誤定位方法

姜元鵬，李 威，于 巧，姜淑娟

（1.中國礦業(yè)大學 圖書館，江蘇 徐州221116；2.中國礦業(yè)大學 計算機科學與技術學院，江蘇 徐州221116）

0 引 言

軟件自動化錯誤定位是一種結合程序行為與運行結果對產(chǎn)生錯誤的語句進行定位的程序分析技術。隨著軟件規(guī)模的擴大和軟件復雜度的提高，軟件錯誤定位的實現(xiàn)也越來越困難。

基于程序執(zhí)行錯誤定位方法的關鍵是獲取程序的執(zhí)行軌跡信息，在獲取程序執(zhí)行信息基礎上，利用概率統(tǒng)計、關聯(lián)分析等模型建立自動化分析工具，可以在一定程度上提高軟件錯誤定位效率。目前用于獲取程序執(zhí)行軌跡的方式主要有3種：①獲取程序日志；②插裝技術；③依賴程序運行平臺接口。其中，第一種方式會受到程序日志信息粒度的影響，導致獲取完整正確的執(zhí)行路徑比較困難；第二種方式需要修改程序源碼或目標代碼，對程序的侵入性較高，存在很多不穩(wěn)定的因素；第三種方式實現(xiàn)比較靈活且對程序的侵入性較低，已逐步得到廣泛的應用。

在程序自動化調(diào)試及軟件錯誤定位方面，根據(jù)是否需要運行程序可以分為：基于靜態(tài)分析的錯誤定位方法和基于測試的錯誤定位方法。其中，靜態(tài)分析無法獲取錯誤發(fā)生時的上下文信息，而基于測試等動態(tài)分析方法在收集動態(tài)信息時會產(chǎn)生較大的代價?？偟膩碚f，當前錯誤定位方法中存在2 個重大的缺陷，一個是錯誤定位不準確，漏掉錯誤語句或者包含的語句數(shù)量過多等；另一個是計算的難度過高，處理大型程序時的時間和空間消耗過大。

針對目前軟件錯誤定位技術的研究現(xiàn)狀及存在的問題，本文提出了一種將動態(tài)切片技術和覆蓋統(tǒng)計相結合的錯誤定位方法。針對能夠確定切片準則的程序計算其執(zhí)行過程中的動態(tài)切片；然后根據(jù)貝葉斯公式計算后驗概率；最后以第二步中計算得到的后驗概率作為語句的可疑度值，按照該值降序排列。通過實驗驗證本文方法可在一定程度上提高了軟件錯誤定位的效率與精度。

1 基本概念

1.1 程序切片相關概念

（1）控制流圖

控制流圖G 是程序中語句邏輯執(zhí)行的一種圖形化表示，可由四元組 （N，E，entry，exit）表示。其中，N 為節(jié)點的集合，代表程序中的語句；EN×N 為邊的集合，代表程序中語句間的控制關系；entry為程序的入口節(jié)點；exit為程序的出口節(jié)點。

（2）控制依賴

n1，n2是控制流圖G 中的2 個節(jié)點，如n1，n2 滿足以下3個條件則稱n2控制依賴于n1，記為CD （n2，n1）：①存在一條從n2到n1的可執(zhí)行路徑Path；②節(jié)點n2是路徑Path中除去n1，n2的其它節(jié)點的后必經(jīng)節(jié)點；③n2不是n1的后必經(jīng)節(jié)點。

（3）數(shù)據(jù)依賴

n1，n2是控制流圖G 中的2 個節(jié)點，變量v在n2 中被定值，如果n1，n2，v滿足以下2個條件，則稱n1數(shù)據(jù)以來n2記做DD （n1，n2）：①變量v被節(jié)點n1引用；②存在一條從n1到n2的非空路徑，并且該路徑上沒有對變量v重定值的節(jié)點。

（4）程序切片

程序切片定義請參見文獻 ［1］。

1.2 貝葉斯定理

貝葉斯定理是指對于隨機事件A 和B，在事件B 發(fā)生的情況下事件A 發(fā)生的概率

式中：P（A）——A 的先驗概率或邊緣概率；P（B｜A）——已知A 發(fā)生后B的條件概率，也由于得自A 的取值而被稱作B的先驗概率；P（B）——B的先驗概率或邊緣概率，也作標準化常量 （normalized constant）；P（A｜B）——已知B發(fā)生后A 的條件概率，也被稱作A 的后驗概率。另外，貝葉斯也適用于多個事件的情況，假設Ai表示一個事件集合，那么則有

2 實例程序

通過一個實例程序來闡述我們的方法。表1左側為求3個數(shù)中間值的函數(shù)mid，在該函數(shù)的第二行引入了一個錯誤：語句 “ret＝z”誤寫成了 “ret＝x”。然后我們設計了六組測試用例對其進行測試，覆蓋情況如表1 中 “切片前”列數(shù)據(jù)所示，其中標記 ［√］表示對應的左側語句被該測試用例執(zhí)行覆蓋。表1的底部展示測試結果，其中T 代表成功執(zhí)行，F(xiàn)代表失敗執(zhí)行。

表1 實例程序

根據(jù)測試的覆蓋情況和執(zhí)行結果信息，我們引用了Tarantula［2，3］，Ochiai［4］，DStar［5］這3種基于覆蓋統(tǒng)計的錯誤定位方法來定位錯誤語句。實驗結果顯示，需要檢查超過27%的代碼才能定位出錯誤語句。

實際上，在成功的測試中目標變量ret在重新賦值之前都沒有被使用，而在失敗執(zhí)行中函數(shù)mid的最終返回值直接數(shù)據(jù)依賴于第二行代碼。第二行代碼出現(xiàn)在所有的測試執(zhí)行中，但是它并不總是對最終結果產(chǎn)生影響。如果去除那些和目標變量沒有關系的代碼，然后再使用現(xiàn)有的一些可疑度度量方法將會得到更加精確的定位結果。實際上，錯誤的運行結果可能是由于執(zhí)行了錯誤的分支，因此控制依賴關系也應該作為語句間關系進行分析。我們針對函數(shù)mid每次執(zhí)行路徑計算動態(tài)切片，然后再使用貝葉斯公式來計算語句的可疑度，計算結果如表1 中右側部分顯示，表明針對函數(shù)mid我們只需要檢查10%的代碼就可以定位到錯誤語句。由此顯示我們的方法能夠在一定程度上提高程序錯誤定位的效率和精度。

3 錯誤定位方法

為了獲取程序執(zhí)行軌跡，我們通過JDI［6］的事件機制實現(xiàn)了Java程序運行軌跡自動收集工具。該工具采用監(jiān)聽方式，等待目標程序的鏈接。在運行目標程序時只需要添加調(diào)試運行參數(shù)，即可實現(xiàn)執(zhí)行路徑的自動收集，程序執(zhí)行軌跡算法如圖1所示。

圖1 程序執(zhí)行軌跡算法

程序切片只分析與興趣變量相關的語句，這樣很容易縮小程序檢查范圍，去除不相關語句對錯誤定位的影響。本文針對給定的執(zhí)行路徑，在程序依賴圖的基礎上，利用圖的可達性算法來計算程序的切片，大大縮小了檢查語句的范圍。

我們可得到程序執(zhí)行結果和其精簡后覆蓋信息，然后使用Bayesian公式來估計語句的懷疑度。通過將語句的懷疑度轉化為在語句X 出現(xiàn)情況下該次執(zhí)行失敗的概率 （記為P（H｜X），其中P（H｜X）中H 表示執(zhí)行失敗事件），而執(zhí)行結果事件概率是根據(jù)統(tǒng)計信息獲得，充當先驗概率P（X｜H），P（H｜X）為后驗概率。由貝葉斯公式我們可以獲得以下計算公式

由于執(zhí)行成功和執(zhí)行失敗事件共同組成全體執(zhí)行事件，根據(jù)全概率公式將上述公式轉換為

式中：H——執(zhí)行失敗事件，－ H——執(zhí)行成功事件，X——程序語句。

當?shù)玫秸Z句懷疑度后，根據(jù)懷疑度值降序排列語句，然后調(diào)試人員根據(jù)該排序依次判斷相應的語句是否為真正的錯誤語句。

4 實 驗

為了驗證我們所提出的方法的有效性，我們選取了4組開源程序作為實驗目標程序。

4.1 實驗對象

表2中列出了選取的4組實驗對象，并給出了程序名稱、功能描述、目標程序的代碼行數(shù)、測試用例數(shù)和包含的錯誤數(shù)目。這4組實驗目標程序都是Siemens suite中提供的程序，我們只選取了其中部分可測的錯誤。為驗證提出方法的有效性，我們選擇了基于頻譜的錯誤定位方法Tarantula，Ochiai和Dstar作為比較對象來判定我們方法的優(yōu)劣。

表2 實驗目標程序

4.2 實驗結果

在實驗中，我們把定位出錯誤時所有需要檢測的語句占總語句的百分比作為錯誤定位代價，把在不同的代價開銷下定位出的錯誤占總錯誤的百分比作為錯誤定位方法有效性指標，記為LV。為了驗證我們提出方法的有效性，我們分別統(tǒng)計了各個方法的最好情況、最壞情況和平均情況下的LV 值。圖2中，x軸表示檢查代碼的百分比，y軸表示定位出的錯誤的百分比，折線上的點表示在對應x軸的代碼檢查百分比的情況下，定位出錯誤的百分比。圖2 （a）顯示在最好的情況下，采用我們的方法只需檢查35%的代碼即可定位所有錯誤，其它3種方法則需要檢查45%的代碼，而在代碼檢查率小于35%時，我們的方法檢查出的錯誤率均比其它3種方法稍微高一些。圖2 （b）中可以看出在最壞的情況下，檢查出所有錯誤時采用我們的方法其代碼檢查率仍然低于其它3種方法，且在檢查出相同錯誤率下，我們的方法代碼檢查率要遠低于其它3 種方法。圖2（c）顯示了我們的方法的最壞定位效果和Tarantula，Ochiai差不多，比Dstar略差一些。圖2 （d）可以看出我們的方法均比其它3種方法的整體定位效果顯著。

圖2 實驗結果

4.3 實驗分析

本文方法通過計算程序切片縮小可以代碼范圍，然后在精簡后的可疑代碼集上做覆蓋統(tǒng)計分析，而其它3種方法則是直接針對執(zhí)行軌跡的覆蓋信息進行統(tǒng)計分析，因此其它3種方法受到了不相關代碼的影響。其中，對定位結果影響最大的不相關代碼是那些和錯誤語句處在動態(tài)基本塊中的語句或者是那些受錯誤語句影響的分支中的語句，而那些和錯誤語句處在動態(tài)基本塊中的語句占有的比例相對大些，并且他們的可疑度值和錯誤語句的可疑度值相同，因此這些語句對最好的情況影響不大，而對最壞情況的影響比較大，因此造成圖2 （a）、（b）中顯示的最好情況下我們提出的方法定位效果提升的不大，而在最壞情況下卻提升幅度很大的現(xiàn)象。

盡管圖2 （a）、（b）、（d）中顯示的是我們提出的方法的定位效果總是比其它3種方法好，但實際上在某些版本中定位效果不僅沒有提升，甚至稍微差一些。造成這種現(xiàn)象是因為該數(shù)值是針對4 組程序的多個版本的匯總結果，再者由于x軸采用的是代碼的檢查率，我們只針對了10%，20%...90%這樣的點進行了采樣，每相差10百分點時代碼數(shù)可能相差很大，盡管很多情況下提升幅度不大，但正好處在分界點上下區(qū)域。

5 相關工作

程序切片是一種比較主流的軟件錯誤定位技術。目前，將程序切片技術應用到錯誤定位中的方法有：Sun［7］等提出了一種根據(jù)代碼優(yōu)先級策略和程序切片技術進行程序錯誤定位的啟發(fā)式方法。文萬志等人［8］提出了一種基于層次切片譜的錯誤定位技術，該方法通過分析分析程序不同粒度層次元素 （包、類、方法以及語句）之間的依賴信息，逐層對可能發(fā)生錯誤的元素進行篩選，縮小錯誤查找范圍，提高了面向對象程序中的錯誤定位效率。Jiang等人［9］基于程序切片、動態(tài)信息和靜態(tài)信息相結合，提出了一種空指針異常的錯誤定位方法。該方法在實時堆棧的指導下進行程序切片，在切片后的程序上進行空指針和別名分析，解決了空指針異常的錯誤定位問題。

Zhang等人［10］提出了只使用失效運行的FOnly錯誤定位方法。錯誤定位一般是基于成功和失效運行兩類，而FOnly只關注失敗運行，從統(tǒng)計趨勢 （方差）上估計分析失敗運行，并錯誤定位。Zhang等人［11］在分析錯誤與征兆的非確定性關系及后驗概率的基礎上，以概率加權二分圖構造錯誤的傳播模型，提出了基于貝葉斯疑似度的啟發(fā)式錯誤定位方法。

Tarantula是一種基于代碼覆蓋的錯誤定位方法，根據(jù)語句塊在成功和失敗執(zhí)行中出現(xiàn)的次數(shù)，計算語句塊的可疑度，按照可疑度對程序語句排序的方法，調(diào)試人員依懷疑度降序檢查語句，直到找到真正錯誤。在Tarantula基本思想的基礎上一些研究人員對懷疑度計算公式進行了改進，Abreu等人［5］提出了Ochiai錯誤定位方法。Chen等人［4］提出了Jaccard錯誤定位方法。Wong等人［12］基于Kulczynski系數(shù)提出DStar（D＊）錯誤定位方法。該方法可定位單錯誤 和 多 錯 誤 程 序。Artzi 等 人［13］將Tarantula、Jaccard、Ochiai這3種錯誤定位技術應用到WEB 錯誤定位中，效果良好。

我們的工作是首先利用程序切片技術來縮小查找的范圍，然后基于切片后的執(zhí)行軌跡統(tǒng)計語句覆蓋信息，再利用貝葉斯公式來計算語句的可疑度。

6 結束語

本文提出了一種有效的錯誤定位方法，該方法結合了現(xiàn)有的程序切片和覆蓋統(tǒng)計的錯誤定位技術。首先針對程序執(zhí)行軌跡計算程序動態(tài)切片，減少了搜索空間；然后基于切片后的執(zhí)行軌跡統(tǒng)計語句覆蓋信息，利用貝葉斯公式計算語句的可疑度；最后根據(jù)語句可疑度降序排列語句，依次檢查直至找出真正的錯誤語句。本文方法在程序切片的基礎上給出了參照檢查順序，提高了傳統(tǒng)的基于程序切片錯誤定位技術的效率；另外，相對于其它的基于覆蓋的錯誤定位方法，使用程序切片技術在很大程度上減小了不相關語句對定位結果造成的影響。實驗結果表明，該方法與以往的方法相比能夠達到更好的效果。

盡管實驗證明我們的方法取得了較好的錯誤定位效果，但也存在一些不足，仍需要進一步的完善與提高。首先該方法是在能夠確定切片的準則的基礎上進行研究，而在實際應用中大部分程序很難確定切片準則，因此還需要進一步定義切片準則。然后，我們的實驗針對單錯誤定位效果較好，而對于多錯誤定位效果一般，下一步我們將研究使用數(shù)據(jù)挖掘的技術來對多錯誤進行聚類分析，然后在聚類的基礎上進行錯誤定位。最后，針對實驗分析中統(tǒng)計方法造成的實驗誤差問題，我們將從多角度對實驗結果進行綜合分析，以達到更準確的錯誤定位效果。

［1］HUANG Yajing，GAO Jianhua.Refactoring location method based on coarse－grained slice metrics ［J］.Computer Engineering，2011，37 （11）：80－82 （in Chinese）. ［黃雅菁，高建華.基于粗粒度切片度量的重構定位方法 ［J］.計算機工程，2011，37 （11）：80－82.］

［2］Artzi S，Dolby J，Tip F，et al.Practical fault localization for dynamic Web applications ［C］／／Proceedings of the 32nd ACM／IEEE International Conference on Software Engineering－Volume 1.ACM，2010：265－274.

［3］Shay Artzi，Adam Kiezun，Julian Dolby，et al.Finding bugs in web applications using dynamic test generation and explicitstate model checking ［J］.IEEE Transactions on Software Engineering，2010，36 （4）：474－494.

［4］Arumuga Nainar P，Chen T，Rosin J，et al.Statistical debugging using compound Boolean predicates［C］／／Proceedings of the International Symposium on Software Testing and Analysis.ACM，2007：5－15.

［5］Abreu R，Zoeteweij P，Van Gemund A J C.On the accuracy of spectrum－based fault localization ［C］／／Academic and Industrial Conference Practice and Research Techniques－MUTATION.IEEE，2007：89－98.

［6］Javadebug interface［EB／OL］.［2014－04－05］.http：／／www.ibm.com／developerworks／cn／java／j－lo－jpda4／.

［7］Sun J，Li Z，Ni J，et al.Software fault localization based on testing requirement and program slice ［C］／／International Conference on Networking， Architecture，and Storage.IEEE，2007：168－176.

［8］WEN Wanzhi，LI Bixin，SUN Xiaobing，et al.Technique of software fault localization based on hierarchical slicing spectrum［J］.Journal of Software，2013，24 （5）：977－992 （in Chinese）.［文萬志，李必信，孫小兵，等.一種基于層次切片譜的軟件錯誤定位技術 ［J］.軟件學報，2013，24 （5）：977－992.］

［9］Jiang S，Li W，Li H，et al.Fault localization for null pointer exception based on stack trace and program slicing ［C］／／12th International Conference on Quality Software.IEEE，2012：9－12.

［10］Zhang Z，Chan W K，Tse T H.Fault localization based only on failed runs［J］.IEEE Computer，2012，45 （6）：64－71.

［11］Zhang C，Liao JX，Zhu XM.Heuristic fault localization algorithm based on Bayesian suspected degree ［J］.Journal of Software，2010，21 （10）：2610－2621.

［12］Wong W E，Debroy V，Li Y，et al.Software fault localization using DStar（D＊）［C］／／IEEE Sixth International Conference on Software Security and Reliability.IEEE，2012：21－30.

［13］Artzi S，Dolby J，Tip F，et al.Fault localization for dynamic Web applications［J］.IEEE Transactions on Software Engineering，2012，38 （2）：314－335.