基于互信息的缺陷定位方法

李倩倩，牟永敏，崔展齊

(北京信息科技大學 網絡文化與數字傳播北京市重點實驗室，北京 100101)

0 引 言

軟件缺陷定位[1](software fault location)是指當軟件發生失效時，程序人員通過分析源碼找到引發該失效的缺陷代碼的行為。傳統的缺陷定位技術采用手動設置斷點的方式進行調試，但這類方法借助于手工的方法，定位缺陷語句的代價高，同時未能充分利用測試用例的執行行為和執行結果的信息。

目前，缺陷定位方法根據是否需要執行測試用例可以分為：靜態定位方法和動態定位方法[2,3]；靜態定位方法主要采用代碼審查的方式，通過對被測程序的內部結構(控制流與數據流等)進行分析從而定位出缺陷的具體位置，動態定位方法則依賴于執行信息進行檢測。動態錯誤定位方法主要包括：基于謂詞[4,5]、基于程序切片[6,7]、基于模型[8]、基于數據挖掘[9-12]以及基于頻譜的方法等。然而前4種方法由于對測試用例需求量大、時間或空間復雜度高、模型構建復雜等缺點在實際應用中不及基于頻譜的缺陷定位方法(spectrum-based fault localization，SFL)。SFL對于測試用例的規模與測試用例覆蓋程度十分敏感，同時易受可疑度公式的影響，由此充分挖掘程序頻譜和執行結果之間存在的潛在關系，構造合適的可疑度計算公式十分重要。基于此提出了一種基于互信息的缺陷定位方法——MIStar，同時使用西門子數據集進行驗證，探究缺陷定位效率，與已有的經典可疑度公式進行對比，實驗結果表明，該方法具有良好的定位效果。

1 相關工作

程序頻譜是程序在執行測試用例時對于語句的覆蓋信息，SFL方法常采用插樁的方法獲取程序中語句的覆蓋信息，通過分析成功測試用例和失敗測試用例在語句或語句塊上的覆蓋信息，獲取語句的可疑度信息或者可疑度的集合。Jones等認為被失敗測試用例覆蓋的實體較被成功測試用例覆蓋的實體有更大存在缺陷的可能性，由此提出了Tarantula懷疑度計算公式，Chen受聚類分析的影響提出了Jaccard懷疑度計算公式，基于分子生物學的研究，Ochiai公式被提出，而后Wong等通過修改Kulczynski系數提出了一種基于相似系數的DStar懷疑率計算公式[2]；Yoo等則將遺傳規劃應用其中，推導出了30個不同的懷疑度計算公式，黃晴雁等[13]通過分析執行信息與執行結果之間的關系，提出了基于條件概率的缺陷定位方法CPStar，取得了良好的定位效果；在使用SFL中，大部分研究員通常使用成功測試用例和失敗測試用例二者執行信息，馮潞潞等[14]考慮到SFL算法中偶然性正確測試用例對實驗結果的影響，由此提出了一種沒有誤判率的缺陷定位方法，由此提高了缺陷定位的準確度；王贊等[15]將啟發式搜索應用到缺陷定位中，提出了一種基于遺傳算法的多缺陷定位方法，并擴展Ochiai系數來計算個體的適應度值從而搜索出具有最高適應度值缺陷分布情況；舒挺等[16]則借助于統計學的條件概率思想，構建了用以量化分析程序頻譜和執行結果之間的關系的P模型，由此定位缺陷位置；葉俊民等[17]考慮到語句塊的篩序機制會對定位準確度造成影響，提出了一種分層程序頻譜的缺陷定位方法，先定位到函數再定位到語句。Chen等[18]特設計了一套理論來評價可疑度公式的優劣；Le等[19]提出了一種多模式技術，同時考慮到錯誤報告和程序頻譜，提出了一種基于信息搜索與程序頻譜的缺陷定位方法。

綜上所述，已有的方法或是引用其它領域的計算方法進行實驗驗證可疑度公式，或者挖掘程序本身涵蓋的規律，對于可疑度公式的優化中，大多數研究者將重點著眼于執行結果與覆蓋信息的關聯分析，而忽略不同語句之間存在缺陷可能性的差異，為繼續量化程序缺陷可能性，采用分層的思維方式，為每條語句增加權重值，同時引入互信息量優化缺陷定位模型。

2 基于互信息的缺陷定位方法

為了挖掘出程序頻譜與執行結果之間的關系，本文將程序實體s的統計信息由一個4元組表示：N(s)=(n10(s),n11(s),n00(s),n01(s))， 其中n10(s)，n11(s) 分別表示覆蓋程序實體的成功測試用例和失敗測試用例，n00(s)，n01(s) 表示未覆蓋程序實體的成功測試用例和失敗測試用例，通過分析各參數的含義，研究人員證明n11(s)，n01(s) 越大，語句可疑度越高，n10(s)，n00(s) 越大，語句的可疑度越低[2]。

2.1 互信息模型

互信息(mutual information)反映了一個事件的出現對于另外一個事件出現所貢獻的信息量，設離散隨機變量X=ai,Y=bj，PX(ai),PY(bj)， 為其發生的概率，P(ai,bj) 為二者的聯合概率，則兩個事件之間的互信息量為

(1)

設事件X為語句s是否被執行，X=1表示該條語句被覆蓋，X=0，表示語句未被覆蓋；事件Y表示執行結果，其中Y=1表示該測試用例為失敗測試用例，Y=0，為成功測試用例?；バ畔⒌膬炔亢瘮蹬c外部函數具有相同的單調性，同時對數函數定義域為(0，+∞)，所以將新的公式抽象為以下形式：

定義1 在程序運行失敗的情況下，語句s被覆蓋

(2)

定義2 在程序運行失敗的情況下，語句s未被覆蓋

(3)

定義3 程序在運行成功的情況下，語句s被覆蓋

(4)

定義4 程序在運行成功的情況下，語句s未被覆蓋

(5)

以上4種模型為程序頻譜和執行結果在具體情況下的互信息量的變形公式，由于本文研究建立在既有成功測試用例又有失敗測試用例，所以n00+n10≠0，n11+n01≠0； 當n00+n01=0成功測試用例和失敗測試用例均未覆蓋該語句，n11+n10=0表示所有成功和失敗測試用例均覆蓋該語句，這兩種情況下，該語句的頻譜信息均無法幫助缺陷定位，所以不再本文的考慮范圍之內。

2.2 示例分析

為直觀分析程序頻譜與執行結果之間的關系，以一個具體實例進行計算分析見表1，改程序主要功能是求取3個數的最大值，其中代碼s2為錯誤語句，測試用例為t1～t7，表格中1表示該語句被執行，0表示未被執行。通過運行測試用例獲得程序的頻譜信息，并利用該頻譜矩陣統計出四元組信息N(s)=(n10(s),n11(s),n00(s),n01(s))， 統計結果見表2。

表1 實例程序頻譜信息

表2 四元組統計結果

根據表2的統計信息，利用M模型可以計算得出相應的量化結果，見表3，其中對應的橫杠表示對應的語句該模型無意義。

表3 M模型統計結果

互信息反映了一個隨機變量由于已知另一個隨機變量而減小的不確定性，同時基于頻譜方法的假設提出：若語句在失敗測試用例中執行較多，則存在缺陷的可能性越大[2]，由此提出假設：語句缺陷與M(1,1)，M(0,0) 呈現出正相關，與M(1,0)，M(0,1) 呈現負相關。具體量化關系通過更權威的數據集進行驗證，本文隨機選擇西門子數據集中部分版本進行實驗，計算M模型值，同時以降序對數據進行排序，分析4種M模型值與缺陷語句之間的關系，如圖1所示。

圖1 Siemens套件錯誤語句M模型結果

從圖1中可以看出，除去少數離群點外，大多數錯誤版本中M(1,1) 的統計值錯誤定位集中在20%左右，M(0,1) 與M(1,0) 則與錯誤定位值呈現出了負相關，且值大體分布在70%～90%之前，而M(0,0) 的值分布較為分散，分布在20%～60%之間，且分布不是很穩定，原因是：測試用例成功執行，但并非觸發了錯誤語句發生的條件，由此導致結果仍然成功，從而使得M(0,0) 的結果出現波動，未呈現規律性。通過對上述實驗的驗證，獲取了M模型的整體特性，從而為更好挖掘程序頻譜與執行結果的關聯關系打下基礎。

2.3 使用M模型評價經典公式

M模型從更加抽象的角度分析了程序頻譜與執行結果的關系，本文選擇4個比較經典的懷疑度計算公式進行分析，并將其進行變形，等價于相應的M模型的組合，具體結果如下所示

Ochiai

(6)

Tarantula

(7)

Kulczynski2

(8)

Ample

(9)

通過對公式進行變形可以發現：Ochiai值為M(1,1) 與n11的乘積，由M模型的特性可知M(1,1) 在錯誤語句的排名呈現正相關，同時n11越大可疑度越高，所以Ochiai可以有效定位缺陷，其次M(1,0) 與缺陷語句呈現負相關，所以Tarantula也得到較好驗證；n00越小，存在缺陷的可能越大，所以Kulczynski2表現較好；然而n10越大，存在缺陷的可能性越小，Ample算法進行變形之后，加入負相關元素n10,由此導致整個公式的計算效果表現略遜色于其它3類。

2.4 新可疑度公式

2.4.1 新可疑度公式提出

基于對M模型的分析和實驗驗證，同時使用該模型對經典可疑度公式進行解釋，選擇了M(1,1) ——該值與缺陷語句可疑度呈現正相關以及與缺陷語句呈現負相關的M(1,0) 作為新可疑度公式的研究基礎。通過對經典可疑度公式進行分析，同時結合Wong等[14]提出的n11在可疑度公式應當賦予更高的權重這一假設，受DStar公式的影響，提出了新的公式MIStar(MI*)，其中*表示n11的指數范圍，取值范圍為0～30，實際缺陷定位過程中，傳統的缺陷定位方法將所有的語句存在缺陷的概率看作是相同的，然而根據實際的執行情況，每條語句應賦予不同的權值。

目前不少的研究者提出了在函數級別上的缺陷定位，依據分而治之的思想，可以將程序在函數級別上缺定位效果轉化每條語句存在缺陷的權重屬性，即相同函數下的語句存在缺陷的可能性相同，用wi表示，其中i取值是該程序中函數的個數，新的懷疑度公式表示為

MIStar

(10)

在實際應用中發現測試用例會影響可疑度公式的準確度，由此選擇*系數，增加n11的權重，根據具體問題設定相應參數值，在同一函數中的語句wi的取值相同，即為該函數存在缺陷的概率或者函數的可疑度。

2.4.2 公式邊界情況

分母為零情況分析：

若語句n10為0且n11為0，則代表該條語句及沒被成功測試用例覆蓋又沒有被失敗測試用例覆蓋，該情況不成立，所以二者不可能同時為0，當某一取值為0時，在公式中以1代替，進行計算。

語句s總是被執行：

在該情況下，n00,n01均為0，則公式變形為

(11)

此時執行信息與否已經無法對定位產生影響，語句的可疑度轉化為win11的相應值，每個函數級下的語句無法區分可疑度。

語句s總是不被執行：

在該情況下n11,n10為0，可疑度結果為0，符合常識。

3 實驗及結果分析

3.1 實驗數據集

本文使用經典的Siemens數據集進行實驗，該數據集下載地址為SIR(http://sir.csc.ncsu.edu/portal/index.php)，表4中是其信息的具體介紹，包括實驗對象名稱、功能描述、代碼行數、每個對象的錯誤版本數，以及測試用例的個數。

表4 Siemens數據集信息

3.2 實驗設計與結果分析

實驗設計主要包括兩個部分，第一部分是對不確定性參數Star進行選擇，確定最優值進行實驗；第二部分將MIStar算法與其它經典算法進行對比實驗，對定位結果進行分析。評價指標為EXAM，即定位出缺陷語句時需要檢查的語句占程序中可執行語句的百分比，根據EXAM指標可知，在相同版本下，EXAM越小，定位的代價越小，效率越高。

3.2.1 Star值對定位效果的影響

本節中，對于Star值的設定范圍為0～30，通過采用網格搜索的方式，以0.5為增量進行實驗，以每個具體Star值的平均EXAM評價定位效果，實驗結果如圖2所示。

圖2 不同Star的定位效果

從圖2中可以觀察到，檢測到錯誤語句需要檢測的代碼函數隨著Star值增加不斷降低，最終趨于穩定。原因在于測試用例的選擇會對實驗結果產生一定的影響，n11值未能充分反應出缺陷程序的執行信息，由此需要增大n11的比重將錯誤語句與正確的語句做區分，當*不斷增大的過程中，n11的信息與nf(nf表示該測試套件中的全部失敗測試用例數目)中的信息逐漸趨于均衡，由此實驗效果將不再改變。該次實驗中，Star值在3.5時達到平衡，由此選擇該值進行實驗分析。

3.2.2 MIStar實驗驗證

為了能夠更好分析MIStar的性能，本文選擇了6個主流的基于頻譜的缺陷定位方法進行實驗，其中對于權重值wi的計算依據函數缺陷定位效果中每個函數可疑度排名位置的倒數(排在前面的函數存在缺陷的概率大于后面的函數)，本文wi的實驗取值參考文獻[10]中對于函數級別的缺陷定位實驗方法和實驗結果，Wong等實驗結果表明Dstar算法D3找到第一個故障的效果最好，所以對Dstar算法選擇的為D3，實驗運行結果如圖3所示，其中X軸代表檢查的平均代碼行數占總代碼的百分比，Y軸表示平均發現缺陷的版本數占總版本數的百分比(即錯誤檢出率)。

圖3 各種方法缺陷定位效果

根據圖像可以看出，在初期小于5%的排查量時，MIStar、Kulczynski2的錯誤檢出率最高，其次是D3、Ochiai，而Tarantula和Jaccard表現略次之；在代碼排查量在15%左右時，MIStar明顯處于領先地位，在代碼排查量在30%左右時MIStar、Kulczynski2，D3、Ochiai，Kulczynski1的定位效果都比較接近，同時MIStar在代碼排查量35%～40%基本上可定位出全部缺陷，隨后其它定位方法隨著代碼排查量的增加，錯誤檢出率逐漸持平。

為了驗證實驗的有效性，驗證不同方法的平穩性以及平均性能，我們統計了各種方法在實驗檢測到錯誤語句時EXAM值的最優值、最劣值、平均值、標準差，見表5。根據統計結果可以發現，Kulczynski2的最劣值達到了最優，MIStar次之，同時MIStar的平均水平僅次于Kulczynski2，然而MIStar的方差較其它缺陷定位方法最小，由此該方法有較好的穩定性。

表5 統計結果對比

4 結束語

基于頻譜的缺陷定位方法由于其自身易于實現，時間復雜度低，同時易于開發人員理解等特性，在缺陷定位領域廣受研究人員的喜愛。通過探究與量化程序頻譜與執行結果之間的關聯同時設計出高效的可疑度計算公式，提高定位的準確性是缺陷定位研究的重點。

本文通過引入信息論中互信息量這一概念，挖掘執行信息與執行結果之間的關聯關系，同時引入不確定性參數Star來修正n11的權重,考慮到分層策略，引入權重值為每條語句賦值，由此提出了基于互信息的缺陷定位模型——MIStar，在第3章節通過不斷修正Star值，同時與經典的缺陷定位方法作對比，展現出來MIStar良好的定位效果和穩定性。

雖然該方法在基準測試程序中展現了良好的表現，但本文中實驗對象為中小型程序且為單缺陷環境，實際的開發環境中存在更多多缺陷情形，所以所提方法在實際使用中需要進一步的實驗驗證和觀察。