基于關聯規(guī)則的軟件多故障定位技術

張澤林++趙洋

摘 要： 為了提高軟件故障的定位效率，提出一種基于關聯規(guī)則的軟件多故障定位技術。通過使用聚類方法把失敗的測試用例分成針對特定錯誤的聚類，使用基于交叉表的軟件故障定位方法發(fā)現軟件中的故障，在定位過程中使用關聯規(guī)則挖掘高可疑代碼與軟件故障的關系，提高故障定位的效率，最后對Siemens用例集和Tarantula方法進行對比。實驗表明基于關聯規(guī)則的軟件多故障定位技術在軟件多故障定位方面效率優(yōu)于Tarantula方法。

關鍵詞： 關聯規(guī)則； 多故障定位； 提高定位效率； 聚類方法

中圖分類號： TN911?34 文獻標識碼： A 文章編號： 1004?373X（2015）12?0039?05

0 引 言

隨著軟件產品的發(fā)展，軟件規(guī)模以及軟件復雜度的不斷增大使得軟件調試過程越發(fā)困難。軟件故障定位是調試過程中成本最高同時耗時最長的一項[1]。在軟件自動化調試領域，出現了許多相應的方法，Jones和Harrold提出了Tarantula[2]方法，該方法通過對比程序實體在失敗測試用例和成功測試用例之間的差別，計算程序實體的懷疑度實現故障定位。C.Liu提出了SOBER[3]方法，該方法使用謂詞在測試用例中取值為真對程序故障出現的影響實現故障定位。其他還有一些定位方法[4?6]比如CBI、NNQ、SBI等。這些方法大多使用程序實體的覆蓋信息來計算每一個程序實體的可疑度，然后通過可疑度排名列表去發(fā)現軟件故障。這些方法雖然在單故障的情況下取得了很好的效果，但是在多故障的情況下，效果都不是很理想。他們大多都采用one?bug?at?a?time的方式實現多故障的定位，但是這種方式弊端明顯：時間效率低，同時需要重復測試。

Jones和Harrold提出了一種并行調試技術[7]，通過對可能導致同一個故障的測試用例進行分類，然后結合成功執(zhí)行的測試用例構造用以測試每個故障的測試用例子集，來同時定位不同的軟件故障。但現有的基于覆蓋率的錯誤定位（Coverage Based Fault Localization，CBFL）方法只是統(tǒng)計代碼語句或代碼基本塊的覆蓋率，并沒有考慮程序執(zhí)行的數據依賴和控制依賴，因此會出現定位不準確的情況。結合以上兩點，本文將在并行的基礎上使用關聯規(guī)則挖掘軟件故障。

1 相關工作

許多該領域的學者提出了不同的軟件故障定位技術。這些技術大多通過收集語句或者謂詞等程序實體的覆蓋信息，然后對收集到的信息利用相應的懷疑度公式計算每條語句的懷疑度，據此找出軟件中的故障。本文也使用這種方式，同時，結合關聯規(guī)則的思想來提高軟件的多故障定位效率。

1.1 基于交叉表的故障定位技術

W.Eric提出了一種基于交叉表的技術進行軟件故障定位的方法[4，8]。該方法的主要思路是：針對每個測試用例的每一條語句構造一個交叉表，通過該交叉表收集語句的覆蓋信息和執(zhí)行結果。然后，利用每條語句的統(tǒng)計信息計算該語句的懷疑度（Suspiciousness）。通過這種方式，所有的語句都可以根據計算出的懷疑度來降序排名。語句的懷疑度越高，該語句越會被優(yōu)先檢查，可以通過排名依次檢查語句，直至發(fā)現軟件的故障。

該技術通過引用一個名為Chi?square test的假設測試來檢查測試用例執(zhí)行結果和語句覆蓋信息之間的依賴關系。Chi?square 的數據通過交叉表中的數據計算而來，同時與Chi?square中的關鍵值進行對比，決定這個假設（即執(zhí)行結果獨立于與語句的覆蓋信息）被接受還是被拋棄，然后，通過計算語句的懷疑度數值[ζ]進行故障定位。[ζ]的數值越大表示語句的懷疑度越高，懷疑度越高則會被優(yōu)先檢查?；诮徊姹淼能浖收隙ㄎ患夹g通過計算語句的懷疑度來預測語句包含故障的可能性。其實驗結果表明基于交叉表的軟件故障定位技術相比于絕大多數的軟件故障定位技術，如Tarantula、Liblit05、SOBER等方法，效果更好。

1.2 并行調試

通常狀況下，一個軟件出現失效狀況下，軟件中會包含多個故障，同時軟件調試的人員也會不止一個，因此可以通過并行的方式實現軟件故障的定位工作，相比于one?bug?at?a?time的方式，并行故障定位會更加高效，通過構造并行工作流，不同的工作人員可以專注于不同的軟件故障。要實現并行的軟件故障定位，最重要的問題是如何對任務進行劃分和分派，這就需要一種可以把錯誤的測試用例集從新分配成多個小的與特定故障相關的錯誤測試用例子集的技術。Jones和Harrold提出了一種并行調試的技術[7]用以實現解決這個問題。這種技術會自動把失敗的測試用例集分割為針對不同軟件故障的測試用例子集。通過使用測試用例動態(tài)運行獲取執(zhí)行結果的行為模型和信息，該技術可以生成一個針對不同錯誤的失敗測試用例子集。通過把失敗測試用例子集和成功的測試用例結合，就得到了一個專注于特定單錯誤的測試用例集。這些單錯誤測試用例集的個數就是對程序中故障個數的預測。

2 關聯規(guī)則在軟件故障定位中的應用

在基于覆蓋的軟件故障定位技術中，現有技術通過收集測試用例執(zhí)行的覆蓋信息計算語句可疑度，進而定位軟件故障。在現有的技術中，往往沒有考慮語句間的數據依賴和控制依賴關系，不同語句的覆蓋統(tǒng)計是相互獨立的，這導致定位的不準確，CBFL方法經常能定位到程序失效時的執(zhí)行代碼，而這些失效時的執(zhí)行代碼多數情況下并不是錯誤代碼[9]，文獻[9]表明，基于覆蓋的軟件故障定位計算可疑度得出的高可疑度語句主要分一下幾種情況：

（1） 該語句基本塊本身就是故障語句，并且該基本塊出現在錯誤測試用例的概率高于出現在成功測試用例的概率。

（2） 該語句基本塊本身不是故障語句，但是該基本塊的執(zhí)行會導致故障語句的執(zhí)行，進而發(fā)生故障。這表明高可疑語句塊或者是故障或者會導致故障，因此考慮通過關聯規(guī)則挖掘高可疑代碼與軟件故障的關系，提高故障定位的效率。

測試用例的執(zhí)行路徑能夠反映出故障代碼與高可疑代碼之間的關聯，即高可疑代碼的執(zhí)行導致故障語句的執(zhí)行，進而出現故障。故障語句與高可疑語句表現出了在執(zhí)行路徑上覆蓋信息的一致性，然而執(zhí)行軌跡的路徑表示十分復雜和耗時[10]，因此采用相對輕量級的覆蓋向量來近似表示路徑的覆蓋信息。

2.1 路徑覆蓋向量的表示

定義1：中間不存在控制跳轉的連續(xù)代碼語句構成一個代碼基本塊，簡稱為基本塊。

定義2：覆蓋向量值指代碼基本快在每次執(zhí)行中的覆蓋信息構成的向量[pathi=（b1，b2，…，bn）]。其中：[pathi]表示覆蓋向量；[bi]表示程序中代碼基本塊，[bi]=0表示該代碼基本塊沒有被覆蓋，[bi]=1表示該代碼基本塊被覆蓋。

定義3：一個函數在測試用例集下的執(zhí)行軌跡符號化表示為[EXEM（fi）={B，T，PATH}]。其中：[B]表示函數[fi]的基本塊集合；[T]表示測試用例集的所有測試用例集合，[PATH={path0，path1，…，pathm}]表示針對每個測試用例的覆蓋向量集合。根據程序執(zhí)行的結果可以將執(zhí)行軌跡分為成功執(zhí)行和失敗執(zhí)行，即[EXEMp]和[EXEMf]。

2.2 求解頻繁集

根據故障語句與高可疑代碼之間表現出的覆蓋一致性，可以求解故障語句的“頻繁集”來表現這種關聯[11?12]，軟件故障或者存在于高可疑代碼中，或者存在于高可疑代碼的頻繁集中，因此通過頻繁集來提高軟件故障定位的效率。只需求出與高可疑代碼保持覆蓋一致的分量對應的基本塊，即可通過頻繁集提高故障定位的效率。

求解頻繁集的算法如下：

[輸入：OBS，EXEMf輸出：FG（頻繁集集合）符號表示：fg（bk）：以bk為目標代碼的頻繁集，k表示bk在OBS中的索引u∧v：向量與操作I：單位向量，維度為基本塊個數初始化：FG←NULL1. for each bk∈OBS2. fg（bk）←I3. for each pathi∈PATH4. if pathi（bk）>0 then5. fg（bk）←fg（bk）∧pathi6. end if7. end for8. FG←FG?fg（bk）9. end for]

算法中：[bk]代表目標代碼；[fg（bk）]表示與[bk]保持頻繁一致性的分量集，即求解出的以[bk]為目標的頻繁集。算法過程為：遍歷[bk]不等于0的分量進行與操作，即得到所有的[bk]的頻繁集。通過計算每一條語句塊的可疑度，按照可疑度降序檢查發(fā)現錯誤，若語句塊中不存在錯誤則檢查語句塊的頻繁集（依據可疑度排序）查找錯誤，這種方式可提高定位效率。

3 基于交叉表的軟件多故障定位技術

下面對基于交叉表的軟件多故障定位技術進行具體介紹。

圖1的程序中包含兩個錯誤，分別是語句行6和語句行9，使用在測試用例集中10組參數組合分別為T1～T10。圖中“√”代表了每條測試用例的語句覆蓋信息；在最后一行給出了每個測試用例的執(zhí)行結果：P代表成功，F代表失敗。

由圖1可知，導致失敗的測試用例往往具有相同或者相似的語句覆蓋信息。因此可以通過聚類方法將測試用例進行分類，將錯誤測試用例中語句覆蓋路徑相同或者相似的路徑分為一類，這些被分為不同類的失敗測試用例子集就是專注于不同錯誤的測試用例集。在mid函數中，測試用例7～10失敗了。而且，測試用例7，8有相同的覆蓋信息，這意味著測試用例7，8可能會導致同樣的軟件故障。同時，測試用例9，10也具有相同的覆蓋信息，同理，它們也可能導致同樣的軟件故障。通過上述分類原理和觀察到的現象，下面把失敗的測試用例分為兩組針對不同錯誤的失敗測試用例子集。然后通過使用Jones和Harrold的并行調試的方法，將失敗的測試用例子集分別與成功測試用例結合，形成兩組不同的測試用例子集。兩組測試用例子集如圖2和圖3所示。

圖4所示交叉表是一個表示測試用例執(zhí)行情況和測試用例是否被覆蓋的二維表。表中各個變量的含義分別是：[w]代表程序中的一條語句；[NCS（w）]代表覆蓋[w]的成功的測試用例數；[NUS（w）]代表沒有覆蓋[w]的成功測試用例數；[NS]代表成功的測試用例數；[NCF（w）]代表覆蓋了語句[w]的失敗測試用例數；[NUF（w）]代表沒有覆蓋語句[w]的失敗測試用例數；[NF]代表失敗的測試用例數；[NC（w）]代表覆蓋了的測試[w]用例總數；[NU（w）]代表沒有覆蓋[w]的測試用例數；[N]代表總的測試用例數。

使用圖4提供的模板和文獻[4]中提供的公式計算每條語句的懷疑度。針對圖2和圖3兩個測試用例集分別計算懷疑度，給出懷疑度列表降序排名如表1所示。

表1中，語句9的懷疑度最高，會最先被檢測。在表2中語句6的懷疑度最高，會最先被檢測。這表明通過構造針對不同錯誤的測試用例子集并行的進行故障定位是可以實現的，這將有利于提高軟件故障定位的效率。在此計算驗證了通過并行的方式進行軟件故障定位的有效性。進行并行的故障定位有一個前提就是構造針對不同錯誤的測試用例。通過使用二分法構造針對不同的測試用例，針對不同的待測函數，可以根據函數的輸入集合和函數的功能創(chuàng)造出不同的二分法條件。在上面例子中，mid函數是用作求取輸入的3個數的中間值的函數，因此中間的參數最有可能導致軟件故障。所以中間的參數作為分類條件，在mid函數中使用“中間的參數是不是在第一個出現”作為分類的條件，如果一個失敗測試用例滿足這個條件則把它放在一個類別中，不滿足則放在另一個類別，同樣以圖1的測試用例為例，發(fā)現T9和T10滿足這個條件，所以把他們分為一類，T7和T8分為另一類，這樣即可進行并行軟件故障定位。

同時，給出一個終止條件，用于判斷分類是否完成，即針對不同錯誤的測試用例是否已經被分配到了各自相應的類別下。聚類的相似性系數可以提供判斷不同對象之間相似程度的度量，因此可以使用相似系數來判斷每個類別中的對象是否足夠相似，不同類別間的對象是否足夠相異來判斷分類是否完成。相關系數公式如下：

[rXY=i=1N（Xi-X）（Yi-Y）i=1N（Xi-X）2i=1N（Yi-Y）2]

式中：[Xi]為第i條語句在失敗測試用例[X]中的覆蓋情況，[Xi]為1代表覆蓋，0代表未覆蓋；[X]表示失敗測試用例[Xi]的覆蓋比例；相應的[Y]的含義和[X]相同。利用圖1中的例子可以將失敗的測試用例集分類。給定一個相關性系數的值，比如0.8，當兩個失敗測試用例的關聯系數小于0.8時說明它們關聯性不大，即它們針對不同的錯誤。計算[r78]=1，這表明T7和T8關聯性非常大，針對相同的錯誤，對T9和T10計算結果也是1，說明它們應該分為一組。通過循環(huán)計算每兩個測試用例之間的相關系數，直到類別內任意兩個測試用例的相關系數大于0.8時，就說明分類完成。本文給出的上述方法雖然能夠對針對不同錯誤的測試用例進行分類，但需要對每兩個錯誤測試用例進行計算，所以這個過程相當耗時，開銷也是很大。

4 實驗及結果分析

下面使用本文給出的基于關聯規(guī)則的軟件多故障定位技術和Tarantula方法進行對比來驗證本文方法的定位效果。在此使用Siemens程序集來進行試驗的對比工作。程序集中tacas程序包含的故障版本數最多，同時可執(zhí)行的語句數最少，這意味著tacas程序有可能包含多故障，因此選用該程序驗證本文的方法。對文獻[4]中的EXAM度量進行擴展，將針對每個故障的[EXAM]相加，形成[EXAMtotal]作為度量的標準。

基于關聯規(guī)則的軟件多故障定位方法與Tarantula方法的對比如圖5所示。

圖5分別給出了在不同的故障版本比例下兩種方法的[EXAMtotal]得分。其中“1”代表20%的故障，“2”代表40%的故障，“3”代表60%的故障，“4”代表80%的故障?？梢钥吹皆诠收媳壤^低的環(huán)境下，本文的方法效率明顯優(yōu)于Tarantula方法。

5 結 語

本文提出了基于關聯規(guī)則的軟件多故障定位方法，并且與Tarantula方法進行了對比，結果表明本文的方法效率較高。不過本文提出的方法也存在一些不足，并沒有考慮把測試用例劃分為針對不同故障的測試用例的效率，同時也沒有考慮失敗測試用例分類的效果進行驗證。在Siemens測試集上通過實驗驗證了基于關聯規(guī)則的軟件多故障定位的效率，結果證明本文的方法能有效地發(fā)現軟件的故障。

參考文獻

[1] JONES J A. Semi?automatic fault localization [D]. USA： Georgia Institute of Technology， 2008.

[2] JONES J A. HARROLD M J. Empirical evaluation of the Tarantula automatic fault?localization technique [C]// Proceedings of the 20th IEEE/ACM international Conference on Automated Software Engineering. Long Beach， CA， USA： IEEE， 2005： 273?282.

[3] LIU C， FEI L， YAN X， et al. Statistical debugging： A hypothesis testing?based approach [J]. IEEE Transactions on Software Engineering， 2006， 32（10）： 831?848.

[4] RENIERES M， REISS S P. Fault localization with nearest neighbor queries [C]// Proceedings of the 18th IEEE/ACM International Conference on Automated Software Engineering. Montreal， Canada： IEEE， 2003： 30?39.

[5] LIBLIT B， NAIK M， ZHENG A X. Scalable statistical bug isolation [C]// Proceedings of the 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation. 2005： 15?16.

[6] HAO D， ZHANG L， PAN Y， et al. On similarity?awareness in testing?based fault localization [J]. Automated Software Engineering， 2008， 15（2）： 207?249.

[7] JONES J A， BOWRING J F， HARROLD M J. Debugging in Parallel [D]. London， UK： Georgia Institute of Technology， 2007.

[8] WONG E， WEI T， QI Y， et al. Crosstab?based statistical method for effective fault localization [C]// Proceedings of the 2008 International Conference on Software Testing， Verification， and Validation. Lillehammer， Norway， 2008： 42?51.

[9] ZHANG Z， CHAN W K， TSE T H. Capturing propagation of infected program states [C]// Proceedings of the 17th International Conference on Foundation of Software Engineering. Amsterdam， Netherl： [s.n.]， 2009： 43?52.

[10] BALL T， LARUS J R. Efficient path profiling [C]// Proceedings of the International Symposium on Microarchitecture. Paris， France： [s.n.]， 1996： 46?57.

[11] WONG E， QI Y. Effiective program debugging based on execution slices and inter?block data dependency [J]. Journal of Systems and Software， 2006， 79（2）： 891?903.

[12] JIANG L， SU Z. Context?aware statistical debugging： From bug prediceors to faulty control flow paths [C]// Proceedings of the 22th IEEE International Conference on Automated Software Engineering. Atlanta， USA： IEEE， 2007： 184?193.