張澤林++趙洋

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

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

中圖分類號(hào)： TN911?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2015）12?0039?05

0 引 言

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

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

1 相關(guān)工作

許多該領(lǐng)域的學(xué)者提出了不同的軟件故障定位技術(shù)。這些技術(shù)大多通過收集語句或者謂詞等程序?qū)嶓w的覆蓋信息，然后對(duì)收集到的信息利用相應(yīng)的懷疑度公式計(jì)算每條語句的懷疑度，據(jù)此找出軟件中的故障。本文也使用這種方式，同時(shí)，結(jié)合關(guān)聯(lián)規(guī)則的思想來提高軟件的多故障定位效率。

1.1 基于交叉表的故障定位技術(shù)

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

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

1.2 并行調(diào)試

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

2 關(guān)聯(lián)規(guī)則在軟件故障定位中的應(yīng)用

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

（1） 該語句基本塊本身就是故障語句，并且該基本塊出現(xiàn)在錯(cuò)誤測(cè)試用例的概率高于出現(xiàn)在成功測(cè)試用例的概率。

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

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

2.1 路徑覆蓋向量的表示

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

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

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

2.2 求解頻繁集

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

求解頻繁集的算法如下：

[輸入：OBS，EXEMf輸出：FG（頻繁集集合）符號(hào)表示：fg（bk）：以bk為目標(biāo)代碼的頻繁集，k表示bk在OBS中的索引u∧v：向量與操作I：?jiǎn)挝幌蛄浚S度為基本塊個(gè)數(shù)初始化：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]代表目標(biāo)代碼；[fg（bk）]表示與[bk]保持頻繁一致性的分量集，即求解出的以[bk]為目標(biāo)的頻繁集。算法過程為：遍歷[bk]不等于0的分量進(jìn)行與操作，即得到所有的[bk]的頻繁集。通過計(jì)算每一條語句塊的可疑度，按照可疑度降序檢查發(fā)現(xiàn)錯(cuò)誤，若語句塊中不存在錯(cuò)誤則檢查語句塊的頻繁集（依據(jù)可疑度排序）查找錯(cuò)誤，這種方式可提高定位效率。

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

下面對(duì)基于交叉表的軟件多故障定位技術(shù)進(jìn)行具體介紹。

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

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

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

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

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

同時(shí)，給出一個(gè)終止條件，用于判斷分類是否完成，即針對(duì)不同錯(cuò)誤的測(cè)試用例是否已經(jīng)被分配到了各自相應(yīng)的類別下。聚類的相似性系數(shù)可以提供判斷不同對(duì)象之間相似程度的度量，因此可以使用相似系數(shù)來判斷每個(gè)類別中的對(duì)象是否足夠相似，不同類別間的對(duì)象是否足夠相異來判斷分類是否完成。相關(guān)系數(shù)公式如下：

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

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

4 實(shí)驗(yàn)及結(jié)果分析

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

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

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

5 結(jié) 語

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

參考文獻(xiàn)

[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.