余曉菲，張 仕，蔡 蕊，陳慧峰，蔣建民

(福建師范大學(xué)數(shù)學(xué)與信息學(xué)院，福建 福州 350007)

1 引言

計算機軟件的失敗(Failure)[1]是指一個服務(wù)偏離了它正確的行為，即實際輸出不等于期望輸出；錯誤(Error)[1]是指可能導(dǎo)致失敗的系統(tǒng)狀態(tài)；故障(Fault)[1]則是指系統(tǒng)錯誤的原因，即我們通常意義上的bug。故障會導(dǎo)致錯誤，從而會造成計算機系統(tǒng)功能減弱或消失，為了找出軟件故障的位置，手工調(diào)試需要投入大量的人力，成本極高，所以希望利用自動診斷技術(shù)幫助定位故障位置，從而輔助程序員快速定位錯誤，訂正程序錯誤代碼。

軟件故障定位大致可分為基于靜態(tài)分析的故障定位和基于測試的故障定位TBFL(Test-Based Fault Localization)，其中，基于靜態(tài)分析的故障定位是通過分析程序代碼找出故障位置而不運行程序；而基于測試的故障定位則是通過執(zhí)行大量的測試用例，從而利用執(zhí)行過程數(shù)據(jù)進行故障定位?；跍y試的故障定位方法又可分為基于執(zhí)行覆蓋的故障定位、基于依賴關(guān)系的故障定位與基于模型的故障定位，本文對基于執(zhí)行覆蓋的故障定位方法進行改良，并進行優(yōu)化實驗，從而論證本文方法的有效性。

近年來，利用程序譜進行故障定位的方法層出不窮，Renieris和Reisst[2]提出了最近鄰查詢方法NNQ(Nearest Neighbor Queries)，對比成功執(zhí)行的覆蓋和失敗執(zhí)行覆蓋之間的相似度差異，但卻只考慮了程序?qū)嶓w的執(zhí)行與否，沒有真正反映兩個覆蓋的相似性。Jones等人[3]提出了Tarantula技術(shù)，讀取出每個程序版本的覆蓋情況和運行結(jié)果(執(zhí)行通過或不通過)，從而計算每一個語句錯誤的可能性—可疑度，再根據(jù)可疑度進行排名。在此基礎(chǔ)上，Aberu等人[1,4]受聚類分析影響提出了Jaccard公式，受分子生物學(xué)影響又提出了Ochilai公式，提高了故障定位的有效性，并驗證出Ochilai公式的故障定位效果比Tarantula公式和Jaccard公式更好。Hao等人[5]提出了相知相似度故障定位方法SAFL(Similarity Aware Fault Localization)，通過消除大量相似的測試用例來提高故障定位的檢查率。Wong 等人[6]認為應(yīng)該關(guān)注錯誤用例的影響，他們認為當執(zhí)行測試用例時，執(zhí)行成功的測試用例數(shù)量越多,它對計算可疑度的貢獻就越小。

雖然上述方法都利用測試用例的執(zhí)行情況分析了測試用例與故障間的聯(lián)系，但是卻沒有針對執(zhí)行失敗的測試用例的覆蓋情況進行分析。本文針對單錯誤問題對已有方法進行改進，基于測試用例執(zhí)行失敗的程序語句覆蓋提出了故障基概念。由于每一個執(zhí)行失敗的測試用例都必然執(zhí)行了錯誤語句，即錯誤語句必然被覆蓋，那么在單錯誤情況下，將所有執(zhí)行失敗的測試用例的覆蓋情況取交集，則會縮小故障語句的覆蓋范圍，從而提高查找效率。本文利用故障基的想法對Tarantula方法、Jaccard方法和Ochiai方法進行改良，并進行實驗比較，以說明利用故障基改良基于程序譜的故障定位方法可以有效提高故障定位效果。

本文第2節(jié)詳細介紹了程序譜的概念以及涉及到的故障定位技術(shù)；第3節(jié)通過實例介紹了改良程序譜的故障定位方法；第4節(jié)是實驗驗證，將本文提出的方法同現(xiàn)有方法相比較，以驗證結(jié)果的顯著性差異；第5節(jié)是總結(jié)和對未來工作的展望。

2 故障定位技術(shù)

2.1 程序譜

程序頻譜詳細描述了程序的執(zhí)行信息[7]，可以被用于追蹤程序的行為[8]。本文的程序譜是指程序執(zhí)行的過程信息，不但包含程序運行軌跡，也包含了程序運行過程的狀態(tài)變化。早期，Collofello和Cousins[9]便提出程序譜可以用于定位軟件的故障，即當程序執(zhí)行失敗時，程序譜信息可以用于查找可能導(dǎo)致執(zhí)行失敗的可疑代碼，從而縮小程序員查找故障位置的范圍。

本文利用一個文件記錄需要的程序譜信息，其中包括0/1形式的矩陣用于指示程序運行時哪些代碼被執(zhí)行，以及程序輸出結(jié)果正確與否的一維矩陣。

2.2 基于程序譜的故障定位技術(shù)

基于頻譜的故障定位SBFL(Spectrum-Based Fault Localization)技術(shù)一直是個熱門研究方向，其中Tarantula方法最為典型。該方法通過在gcc編譯時添加參數(shù)，以便能夠在程序運行過程中生成程序的運行覆蓋情況；再分析運行覆蓋并輸出覆蓋矩陣，并以此為依據(jù)計算每個執(zhí)行語句的可疑度分數(shù)；最后以可疑度值為依據(jù)排序，可疑度分數(shù)越高的語句排名越靠前，程序員查錯時先檢查排名靠前的語句。

基于程序譜的故障定位技術(shù)主要利用了如下四個反映程序執(zhí)行覆蓋情況的指標：

N(s)=〈nep(e),nef(e),nnp(e),nnf(e)〉

其中,e表示程序?qū)嶓w；nep(e)表示執(zhí)行了程序?qū)嶓w并且成功的測試用例數(shù)；nef(e)表示執(zhí)行了程序?qū)嶓w并且失敗的測試用例數(shù)；np為套件中所有執(zhí)行成功的測試用例數(shù)且有np=nep(e)+nnp(e)；nnp(e)表示未執(zhí)行程序?qū)嶓w并且成功的測試用例數(shù)；nnf(e)表示未執(zhí)行程序?qū)嶓w并且失敗的測試用例數(shù)；nf為套件中所有執(zhí)行失敗的測試用例數(shù)且有nf=nef(e)+nnf(e)；n為套件中所有的測試用例數(shù)且有n=np+nf。

Tarantula技術(shù)根據(jù)每個測試用例覆蓋執(zhí)行語句的軌跡信息和相應(yīng)的執(zhí)行結(jié)果(成功和失效)來計算每條語句的可疑度,其計算公式如下：

(1)

近年來，研究者提出了很多類似的技術(shù)，有些效果相差不大，有些效果要優(yōu)于Tarantula，其中Aberu等人就相繼提出了Jaccard技術(shù)和Ochilai技術(shù)，并實驗證明了Ochilai技術(shù)進行故障定位的效果要優(yōu)于Tarantula和Jaccard的。

Jaccard懷疑率計算公式如下：

(2)

Ochilai懷疑率計算公式如下：

(3)

3 改良程序譜

3.1 一個例子

圖1中展示了一個程序?qū)嵗齮est函數(shù)和一組由5個測試用例組成的測試套件，我們將通過該實例說明改良程序譜方法的基本思路。

Figure 1 Examples of improved program spectra圖1 改良程序譜例子

函數(shù)test接受三個整數(shù)輸入x,y,z，輸出結(jié)果為三個數(shù)中的中間值，該程序故障處S4，其中的“x>y”應(yīng)該為“x

所謂的故障基，是將執(zhí)行失敗的測試用例的語句覆蓋做交運算，從而得到的程序語句集合。作為引例，圖中未列出用其他計算公式計算可疑率的情況，而是以Tarantula為例，先計算了Tarantula公式不引入故障基時的可疑率，再計算引入故障基后Tarantula的可疑率(可疑率表示每一行語句用公式計算出的可疑分數(shù)，可疑值最大為1，值越大則排名越靠前，表示語句越可能包含故障)，當幾個程序的可疑度相同時，所有語句排名都取排名的最大值。

以故障語句S4作為例子，使用Tarantula計算語句可疑度。未引入故障基之前，總的測試用例數(shù)為5;分子為執(zhí)行失敗測試用例數(shù)與所有失敗測試用例數(shù)的比值，計算得1;分母為執(zhí)行成功測試用例數(shù)占所有成功測試用例數(shù)的百分比與分子之和，計算得1；故語句S4可疑率為1，但有四個語句計算得到的可疑度都為1，所以排名同為4。當引入故障基后，測試用例變成3個程序執(zhí)行通過的測試用例與1個故障基，即4個測試用例數(shù)進行可疑度計算。同理，在計算故障語句S4時，分子分母都為1，故可疑率為1，排名為1。從例子中可以發(fā)現(xiàn)，引入故障基后，故障語句S4的排名從4變成1，且增加了可疑率為0的語句，說明其有效縮小了查找范圍，大大提高了查找效率。

3.2 故障基

對基于頻譜的故障定位方法而言，故障定位的效果和效率都高度依賴于測試用例，所以測試用例的選取以及使用測試用例的多少都對實驗有至關(guān)重要的影響。針對測試用例的研究，本文提出的方法充分利用了執(zhí)行失敗測試用例的程序語句覆蓋情況，縮減了運行時的執(zhí)行失敗測試用例數(shù)量，極大提高了軟件故障定位的效率和有效性。

在程序運行時，每一個執(zhí)行失敗的測試用例都必然執(zhí)行了錯誤語句(否則程序運行結(jié)果正確，不會產(chǎn)生失敗執(zhí)行的情況)，即錯誤語句必然被覆蓋。那么在單錯誤的情況下，將所有執(zhí)行失敗的測試用例的覆蓋情況取交集，則會縮小故障語句的覆蓋范圍，并且交集一定會包含故障語句的覆蓋，文中將交集取得的覆蓋情況集合稱為故障基。

將執(zhí)行失敗測試用例的覆蓋情況設(shè)為集合vi,vi={vi1,vi2,…,vij,…,v(in-1),vin}，我們稱它為失敗執(zhí)行覆蓋，其中i為執(zhí)行失敗測試用例編號，j為語句行號，n為總語句數(shù)，vi為第i個執(zhí)行失敗測試用例的執(zhí)行情況，vij為第i個執(zhí)行失敗測試用例的第j條語句的覆蓋情況，覆蓋情況取值為0或1，覆蓋為1，未覆蓋為0。

失敗測試用例集的覆蓋V={v1,…,vi,…,vm}，其中vi為第i個執(zhí)行失敗測試用例的執(zhí)行情況，故障基FaultBase={f1,…,fk,…,fn},其中：

以圖1中函數(shù)test為例，執(zhí)行失敗測試用例數(shù)為2，語句數(shù)為12，所以圖1中共有兩個失敗執(zhí)行覆蓋v1和v2，其中，v1={1,1,1,1,0,1,1,0,0,0,0,1},v2={1,1,1,1,1,0,0,0,0,0,0,1}。

利用故障基定義，可以計算得到該例子中的故障基為FaultBase={1,1,1,1,0,0,0,0,0,0,0,1}。

4 實驗準備

4.1 實驗基礎(chǔ)

大多數(shù)的故障定位研究都使用開源的評測程序[10]進行實驗，本文使用SIR(Software artifact Infrastructure Repository)中的Siemens suite測試套件[11]，Siemens suite包含七個小規(guī)模程序，代碼行數(shù)在174～573，分別是tcas、shedule、schedule2、print_tokens、print_tokens2、replace和tot_info，由C語言編寫而成，其具體情況如表1所示。

這七個程序共有132個版本，每個版本的程序都被人工注入單個錯誤。本實驗用到了132個版本中的118個，其中，8個版本由于虛擬機運行時出現(xiàn)“core dumped”故障，所以無法獲取cover文件，分別是replace的第27個版本，print_tokens2的第10個版本，schedule的第1、5、6、9版本，print_tokens2的第10個版本以及schedule2的第8個版本；而print_tokens的第4個和第6個版本由于C文件中沒有出現(xiàn)語句錯誤，錯誤出現(xiàn)在.h文件中，實驗系統(tǒng)無法獲取其完整的執(zhí)行軌跡信息，故不考慮；此外，schedule2的第9個版本、replace的第8個和第14個版本、tcas的第38個版本由于沒有測試用例失敗，所以不會顯示故障。

Table 1 Description of the Simense suite

4.2 實驗流程

為了獲取足夠的信息完成本文的實驗，我們需要獲取三個方面的信息：程序錯誤代碼的實際位置、每個測試用例運行結(jié)果的正確與否、程序譜。

為了獲取程序錯誤代碼的實際位置，本文將故障版本和正確版本相比較，檢查代碼的不同之處，并標記故障。對于單錯誤程序，其故障位置可能不是單一的，例如，語句缺失錯誤，只需要在缺失位置所在的語句塊中加入該語句便可修正該錯誤，在這種情況下，我們把該語句塊的任一位置均看作故障位置，那么一個故障版本可能存在多個故障位置，但在比較實驗效果時只能有一個故障位置。據(jù)此，我們將最快定位到故障語句的位置作為本實驗觀察效果的故障位置，相當于找到一個錯誤就找到錯誤位置。最后，比較輸出的不同，將其標記為故障位置。此外，本實驗不考慮空白行、注釋、函數(shù)及變量聲明。

為了判定每個測試用例運行結(jié)果的正確與否，區(qū)分執(zhí)行失敗的測試用例和執(zhí)行成功的測試用例。首先，對正確版本的程序運行所有測試用例，將獲得的輸出記錄為期望輸出；其次，對故障版本的程序運行所有的測試用例，將這些輸出定義為實際輸出；最后，對比期望輸出和實際輸出，把兩種輸出不同的測試用例均定義為失敗運行。

為獲取程序譜，我們利用gcc編譯器實現(xiàn)編譯時的插樁，以便記錄程序運行情況。再利用gcov工具提取覆蓋情況，并生成0-1矩陣反映代碼執(zhí)行覆蓋。在讀取并解析gcov文件過程中，若程序語句出現(xiàn)宏定義、注釋、空白行等，此時覆蓋中的“-”讀成從不覆蓋，“####”讀成未覆蓋，其余字數(shù)都為該執(zhí)行語句的執(zhí)行次數(shù)，讀為具體覆蓋次數(shù)。

5 實驗評估

5.1 實驗結(jié)果

為了能夠統(tǒng)一評價標準，本文利用檢查率作為實驗效果評估標準。所謂檢查率，是指程序員按照可疑率排序逐個檢查相關(guān)程序，直到發(fā)現(xiàn)錯誤代碼所需要檢查的代碼數(shù)量占程序總代碼行數(shù)的百分比。檢查率越低，說明程序員在故障定位時需要檢查的代碼行數(shù)越少，說明故障定位的效果越好，反之，則說明故障定位方法效果差。

表2和圖2～圖4體現(xiàn)了基于改良程序譜的故障定位方法實驗效果，其列出了每個分數(shù)范圍內(nèi)所有的故障版本百分比。為了更好地對比，本文采用和文獻[12，13]相同的分段方法，除了0%～60%與99%～100%，其余都以10%為間距進行分段。

將Tarantula、Jaccard、Ochilai這三種技術(shù)的運行結(jié)果與改良后的運行結(jié)果比較。其中的分數(shù)表示不需要檢查的代碼數(shù)占所有代碼的百分比(對應(yīng)圖2～圖4的橫坐標)，在分數(shù)段99%～100%則說明是最能精準定位到故障語句，即檢查的代碼數(shù)量最少。從表2可以看出，在分數(shù)為99%～100%區(qū)間內(nèi)，即檢查代碼數(shù)量在1%內(nèi)便可確定故障代碼位置，改良后使Tarantula與Jaccard的測試運行提升了7.63%，說明改良程序譜后只需檢查更少量的代碼行就可以找出故障位置。在檢查率為60%～70%區(qū)間內(nèi)，Tarantula與Jaccard的測試運行在改良后減少了8.48%，說明需要檢查的代碼比例為30%～40%的故障版本在減少，它們不需要檢查這么多的代碼就可以找到故障位置，很顯然，表2中的數(shù)據(jù)說明了改良程序譜后這三個技術(shù)的效果都相較之前有很大的提升。

Table 2 Percentage of test runs at each score level

Figure 2 Comparison of inspection rates of ordinary Tarantula technology with improved one圖2 Tarantula技術(shù)改良前后的檢查率對比

Figure 3 Comparison of inspection rates of ordinary Jaccard technology with improved one圖3 Jaccard技術(shù)改良前后的檢查率對比

Figure 4 Comparison of inspection rates of ordinary Ochilai technology with improved one圖4 Ochilai技術(shù)改良前后的檢查率對比

從表2中我們也可以看出，不論是Tarantula、Jaccard、還是Ochilai，在經(jīng)過改良程序譜后，每個檢查率區(qū)間都會出現(xiàn)相近的故障版本數(shù)，即故障版本占全部版本百分比的數(shù)量差不多。文獻[1,4]已經(jīng)證明Ochilai效果要優(yōu)于Tarantula和Jaccard，由表中三種改良前的技術(shù)所對應(yīng)的故障版本百分比容易得出：在99%～100%范圍內(nèi)Ochilai所占的故障版本數(shù)都要更多，此時需要檢查更少代碼便能發(fā)現(xiàn)故障的故障版本數(shù)量增多，但是在改良了程序譜后，三者出現(xiàn)了同樣的故障版本百分比17.80%。同樣，在分數(shù)段90%～99%時，故障版本百分比數(shù)量分數(shù)大致平穩(wěn)在50.80%。同理可以發(fā)現(xiàn)，改良程序譜后Ochilai對檢查率值并沒有相較于Tarantula、Jaccard有顯著提升，Tarantula技術(shù)雖然效果沒有Ochilai的效果好，但是在改良程序譜后，兩者出現(xiàn)了極其相近的效果。

圖2～圖4分別展示了Tarantula、Jaccard、Ochilai這三種技術(shù)改良前后對應(yīng)分數(shù)水平的故障版本百分比。橫坐標為分數(shù)水平(不需要檢查的代碼數(shù)占所有代碼的百分比)，因為60%～70%分數(shù)段內(nèi)測試運行百分比已達到100%，0%～60%也必然達到100%，所以0%～60%區(qū)間不在圖中重復(fù)出現(xiàn)。縱坐標表示橫坐標上某一分數(shù)值對應(yīng)的故障版本的百分比，圖2中90%～99%區(qū)間曲線最陡，在90%時已達到約68.7%，說明在這區(qū)間內(nèi)故障版本數(shù)量占總版本數(shù)最多，即查找率在1%～10%的故障版本數(shù)量最多。在本文所研究的技術(shù)中,每個錯誤的版本來自同一個測試套件，所以縱坐標不僅代表測試運行的百分比,而且還表示故障版本的百分比。

在每個分數(shù)階段，畫出點并連線后形成圖2～圖4中所示的折線圖，表示在該分數(shù)段或更高分數(shù)段內(nèi)找到的故障版本百分比。例如圖2中Tarantula技術(shù)，存在約53.4%的故障版本，只需要檢查小于或等于10%的代碼就可以發(fā)現(xiàn)故障語句，即可以達到90%甚至更高的分數(shù)。圖2～圖4都很直觀地顯示了技術(shù)改良后的檢查率要明顯高于改良前的，很顯然改良程序譜后有效提升了檢查率，可以更好地幫助程序員精準定位故障位置。

5.2 實驗影響因素

本文的改良程序譜想法是針對執(zhí)行失敗的測試用例而言，而具體測試用例及其數(shù)量對結(jié)果有很重要的影響，由于使用的Siemens suite 自帶了實驗所需測試用例，所以我們排除它對實驗的影響。由表2可知，執(zhí)行失敗測試用例數(shù)最多的是print_tokens2的版本，執(zhí)行失敗測試用例數(shù)最少的是schedule2的版本，所以，本文使用Tarantula經(jīng)典算法，比較執(zhí)行失敗測試用例的多少對實驗效果的影響，并對計算出的可疑度進行排名，計算出檢查率。

表3和表4中的排名1和檢查率1代表Tarantula技術(shù)的排名和檢查率，排名2和檢查率2代表改良程序譜后的Tarantula技術(shù)的排名和檢查率。由表3可以看出，print_tokens2版本經(jīng)改良程序譜后排名提升很多，檢查率也大大減小，效果最佳，這說明執(zhí)行失敗的測試用例越多，實驗的效果就越好，故障定位效果越顯著。而從表4可以看出，雖然在改良程序譜后排名也在靠前，可疑度也有減小，但效果提升卻不夠明顯，這說明執(zhí)行失敗的測試用例越少，取得的效果越不顯著。

由上可知，執(zhí)行失敗的測試用例數(shù)的數(shù)量對實驗結(jié)果有至關(guān)重要的影響，且執(zhí)行失敗測試用例數(shù)的數(shù)量越多，效果越好。

Table 3 Comparison of print_tokens2

Table 4 Comparison of schedule2

6 結(jié)束語

基于頻譜的故障定位一直是軟件故障定位的熱門研究方向，Tarantula算法被提出后，很多研究者提出了新的改進公式的方法，和Tarantula技術(shù)一樣根據(jù)可疑度進行排名，幫助程序員定位故障。本文通過引入故障基的概念，對算法Tarantula、Jaccard、Ochilai進行改良；最后通過實驗結(jié)果的比較，說明了改良方法的有效性，并分析了測試用例數(shù)量對實驗效果的影響。此外，本文還分析了執(zhí)行失敗的測試用例數(shù)量對該方法的影響，即執(zhí)行失敗的測試用例數(shù)量越多，效果越顯著。

本文基于對程序譜的分析和改良，雖然取得了很好的效果，但這是限定在單錯誤情況下，后續(xù)將深入研究多錯誤情況下故障定位的有效性。本文實驗表明，在程序語句數(shù)越多或測試用例數(shù)越多時，其效果也會更加顯著。但是，本文只利用Siemens suite套件進行實驗，在后繼工作中將針對多種程序體量、不同測試數(shù)據(jù)進行更加詳細的比較。此外，本文主要是考慮執(zhí)行失敗測試用例對基于程序譜定位方法的影響，以后的工作中將結(jié)合考慮執(zhí)行失敗的測試用例和執(zhí)行成功的測試用例，探索更加高效的方法。

[1] Abreu R,Zoeteweij P,Gemund A J C V.On the accuracy of spectrum-based fault localization[C]∥Proc of the Testing: Academic and Industrial Conference on Practice and Research Techniques,2007: 89-98.

[2] Renieris M,Reiss S.Fault localization with nearest neighbor queries[C]∥Proc of the International Conference on Automated Software Engineering,2003: 30-39.

[3] Jones J A,Harrold M J, Stasko J.Visualization of test information to assist fault localization[C]∥Proc of ICSE’02,2002: 467-477.

[4] Abreu R, Zoeteweij P,Gemund A J C V.An evaluation of similarity coefficients for software fault localization[C]∥Proc of the Pacific Rim International Symposium on Dependable Computing,2006: 39-46.

[5] Hao Dan,Zhang Lu,Pan Ying,et al.On similarity-awareness in testing-based fault localization [J].Automated Software Engineering,2008,15(2): 207-249.

[6] Wong W E,Qi Y,Zhao L,et al.Effective fault localization using code coverage[C]∥Proc of the Annual International Computer Software and Applications Conference,2007: 449-456.

[7] Wong W E,Gao R,Li Y,et al.A survey on software fault localization[J].IEEE Transactions on Software Engineering,2016,42(8):707-740.

[8] Reps T,Ball T,Das M,et al.The use of program proling for software maintenance with appli-cations to the year 2000 problem[C]∥Proc of ESEC’97,1997: 432-449.

[9] Collofello J S,Cousins L.Towards automatic software fault localization through decision-to-decision path analysis[C]∥Proc of International Workshop on Managing Requirements Knowledge,1987: 539-544.

[10] Chen Xiang, Ju Xiao-lin, Wen Wan-zhi, et al.Review of dynamic fault localization approaches based on program spectrum[J].Journal of Software,2015,26(2): 390-412.(in Chinese)

[11] Harrold M J,Rothermel G,Wu R,et al.An empirical investigation of program spectra[C]∥Proc of the SIGPLAN/SIGSOFT Workshop on Program Analysis for Software Tools and Engineering,1998: 83-90.

[12] Cleve H,Zeller A.Locating causes of program failures[C]∥Proc of the International Conference on Software Engineering,2005: 342-351.

[13] Renieris M,Reiss S.Fault localization with nearest neighbor queries[C]∥Proc of the International Conference on Automated Software Engineering,2003: 30-39.

附中文參考文獻：

[10] 陳翔，鞠小林，文萬志，等.基于程序頻譜的動態(tài)缺陷定位方法研究[J].軟件學(xué)報,2015,26(2):390-412.