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

（1.中國(guó)礦業(yè)大學(xué) 圖書館，江蘇 徐州221116；2.中國(guó)礦業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 徐州221116）

0 引 言

軟件自動(dòng)化錯(cuò)誤定位是一種結(jié)合程序行為與運(yùn)行結(jié)果對(duì)產(chǎn)生錯(cuò)誤的語(yǔ)句進(jìn)行定位的程序分析技術(shù)。隨著軟件規(guī)模的擴(kuò)大和軟件復(fù)雜度的提高，軟件錯(cuò)誤定位的實(shí)現(xiàn)也越來越困難。

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

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

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

1 基本概念

1.1 程序切片相關(guān)概念

（1）控制流圖

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

（2）控制依賴

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

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

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

（4）程序切片

程序切片定義請(qǐng)參見文獻(xiàn) ［1］。

1.2 貝葉斯定理

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

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

2 實(shí)例程序

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

表1 實(shí)例程序

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

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

3 錯(cuò)誤定位方法

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

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

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

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

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

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

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

4 實(shí) 驗(yàn)

為了驗(yàn)證我們所提出的方法的有效性，我們選取了4組開源程序作為實(shí)驗(yàn)?zāi)繕?biāo)程序。

4.1 實(shí)驗(yàn)對(duì)象

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

表2 實(shí)驗(yàn)?zāi)繕?biāo)程序

4.2 實(shí)驗(yàn)結(jié)果

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

圖2 實(shí)驗(yàn)結(jié)果

4.3 實(shí)驗(yàn)分析

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

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

5 相關(guān)工作

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

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

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

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

6 結(jié)束語(yǔ)

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

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

［1］HUANG Yajing，GAO Jianhua.Refactoring location method based on coarse－grained slice metrics ［J］.Computer Engineering，2011，37 （11）：80－82 （in Chinese）. ［黃雅菁，高建華.基于粗粒度切片度量的重構(gòu)定位方法 ［J］.計(jì)算機(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）.［文萬(wàn)志，李必信，孫小兵，等.一種基于層次切片譜的軟件錯(cuò)誤定位技術(shù) ［J］.軟件學(xué)報(bào)，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.