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

李倩倩，牟永敏，崔展齊

(北京信息科技大學(xué) 網(wǎng)絡(luò)文化與數(shù)字傳播北京市重點實驗室，北京 100101)

0 引 言

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

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

1 相關(guān)工作

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

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

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

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

2.1 互信息模型

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

(1)

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

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

(2)

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

(3)

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

(4)

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

(5)

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

2.2 示例分析

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

表1 實例程序頻譜信息

表2 四元組統(tǒng)計結(jié)果

根據(jù)表2的統(tǒng)計信息，利用M模型可以計算得出相應(yīng)的量化結(jié)果，見表3，其中對應(yīng)的橫杠表示對應(yīng)的語句該模型無意義。

表3 M模型統(tǒng)計結(jié)果

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

圖1 Siemens套件錯誤語句M模型結(jié)果

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

2.3 使用M模型評價經(jīng)典公式

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

Ochiai

(6)

Tarantula

(7)

Kulczynski2

(8)

Ample

(9)

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

2.4 新可疑度公式

2.4.1 新可疑度公式提出

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

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

MIStar

(10)

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

2.4.2 公式邊界情況

分母為零情況分析：

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

語句s總是被執(zhí)行：

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

(11)

此時執(zhí)行信息與否已經(jīng)無法對定位產(chǎn)生影響，語句的可疑度轉(zhuǎn)化為win11的相應(yīng)值，每個函數(shù)級下的語句無法區(qū)分可疑度。

語句s總是不被執(zhí)行：

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

3 實驗及結(jié)果分析

3.1 實驗數(shù)據(jù)集

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

表4 Siemens數(shù)據(jù)集信息

3.2 實驗設(shè)計與結(jié)果分析

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

3.2.1 Star值對定位效果的影響

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

圖2 不同Star的定位效果

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

3.2.2 MIStar實驗驗證

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

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

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

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

表5 統(tǒng)計結(jié)果對比

4 結(jié)束語

基于頻譜的缺陷定位方法由于其自身易于實現(xiàn)，時間復(fù)雜度低，同時易于開發(fā)人員理解等特性，在缺陷定位領(lǐng)域廣受研究人員的喜愛。通過探究與量化程序頻譜與執(zhí)行結(jié)果之間的關(guān)聯(lián)同時設(shè)計出高效的可疑度計算公式，提高定位的準確性是缺陷定位研究的重點。

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

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