基于測試結(jié)果調(diào)整語句出錯概率方法＊

王蓁蓁

（1.金陵科技學(xué)院信息技術(shù)學(xué)院，江蘇南京211169；2.江蘇省信息分析工程實(shí)驗(yàn)室，江蘇南京211169）

1 引言

運(yùn)用從軟件測試中獲得的信息自動確定錯誤位置是很重要的一種技術(shù)手段，有關(guān)方法可以統(tǒng)稱為TBFL（Testing－Based Fault Localization）方法［1～12］。

文獻(xiàn)［3］討論了六種涉及動態(tài)定位的TBFL方法：Dicing方法（Agrawl et al，1995）、TARANTULA方法（Jones et al，2002；Jones and Harrold 2005）、Nearest Neighbor Queries方法（Renieris and Reiss 2003）、CT（Cleve and Zeller 2005）、So－BER（Liu et al，2005）和Liblit05（liblit et al，2005），發(fā)現(xiàn)它們都忽略了實(shí)施相似性的測試用例可能產(chǎn)生的問題。同樣，文獻(xiàn)［6］也指出，相似性的測試用例可能會損害TBFL方法的功效。為了解決該問題，文獻(xiàn)［3］主要是運(yùn)用模糊集合理論提出了SAFL（Similarity－Aware Fault Localization）方法。在測試實(shí)踐中，測試用例的相似性總是難以避免的，所以討論類似SAFL方法和尋找更有成效的錯誤定位方法是有價(jià)值的。

然而測試實(shí)踐里也存在這樣的問題，就是沒有充分利用原程序和測試用例本身所包含的信息去輔助測試結(jié)果尋找錯誤根源，這不僅是一種“資源浪費(fèi)”，而且有時(shí)對程序中隱蔽錯誤的揭露“無能為力”，這特別表現(xiàn)在，當(dāng)測試用例全部通過時(shí)，測試對程序中沒有被揭露出的錯誤就“無話可說”。為了解決這個(gè)問題，文獻(xiàn)［12］提出了一種新的基于隨機(jī)理論的TBFL方法，該方法對減少相似用例的傷害性方面也有成效。

文獻(xiàn)［12］認(rèn)為軟件雖然是由高度負(fù)責(zé)和有豐富專業(yè)知識的程序員編寫的，但是由于軟件的復(fù)雜性和“非物質(zhì)性”，一些“偶然”因素所導(dǎo)致的錯誤是無法避免的，所以將整個(gè)待測程序看成是一個(gè)隨機(jī)變量，把程序員或測試員在測試前關(guān)于程序中每個(gè)語句（或各個(gè)構(gòu)件）出錯的可能性的估計(jì)抽象為該隨機(jī)變量的先驗(yàn)分布。同樣，就測試用例捕捉程序的錯誤能力而言，也視測試用例集為另一個(gè)隨機(jī)變量，其分布就是它們的捕捉錯誤的能力的抽象表示。在這些信息的基礎(chǔ)上，綜合利用每個(gè)測試用例的測試結(jié)果類型（失敗或通過）和它們覆蓋語句的情況，對程序里每個(gè)語句的（先驗(yàn)）概率作“綜合性”調(diào)整，調(diào)整后的概率稱為后驗(yàn)概率，最后根據(jù)這個(gè)后驗(yàn)概率對錯誤語句進(jìn)行排序，為程序員尋找錯誤提供導(dǎo)向。

隨機(jī)TBFL算法可以用如圖1所示的流程圖（參見文獻(xiàn)［12］的圖3）表示（稍加改變）。

Figure 1 Flowchart of random TBFL algorithm圖1 隨機(jī)TBFL算法流程圖

圖1很好地闡述了文獻(xiàn)［12］提出的隨機(jī)TBFL算法的精神。算法細(xì)節(jié)請參見該文獻(xiàn)。文獻(xiàn)［12］指出，X的先驗(yàn)分布是根據(jù)程序“樣式”分析得到的，測試集的（先驗(yàn)）分布與設(shè)計(jì)測試用例的類型、意圖有關(guān)，它們分別與程序里語句的真實(shí)錯誤和測試用例具體實(shí)施結(jié)果無關(guān)，并且這些先驗(yàn)知識即使粗糙，只要大體上“正確”，當(dāng)它們和測試實(shí)踐產(chǎn)生的結(jié)果從微觀和宏觀兩個(gè)層次上進(jìn)行關(guān)聯(lián)以后，就會對語句的錯誤定位有較大幫助。文獻(xiàn)［12］在一些具體實(shí)例上，把它和前述幾個(gè)方法進(jìn)行對比，證實(shí)了這一點(diǎn)。

本文遵循文獻(xiàn)［12］的思路，但對其算法作了改進(jìn)。主要思想是：首先把程序X的先驗(yàn)分布從測試活動里“分離”出來，因?yàn)槌绦虻南闰?yàn)分布的不精確可能會影響“單純的”測試活動的結(jié)果，這種分離也符合當(dāng)前流行的軟件測試的主流方向。其次，測試集T的先驗(yàn)分布也從具體測試?yán)锓蛛x出來，等到估計(jì)測試結(jié)果的影響時(shí)才加入考慮。其具體思想可用圖2表示。

本文的算法稱為基于測試結(jié)果的隨機(jī)TBFL方法，為了敘述簡潔，下文簡稱它為新方法。

Figure 2 Flowchart of random TBFL algorithm based on testing results圖2 基于測試結(jié)果的隨機(jī)TBFL方法流程圖

本文的其余部分組織如下：第2節(jié)給出新算法大致框架；第3節(jié)給出TBFL算法評價(jià)標(biāo)準(zhǔn)；第4節(jié)為實(shí)例分析；第5節(jié)為結(jié)論和展望。

2 基于測試結(jié)果隨機(jī)TBFL算法模型

2.1 程序隨機(jī)變量X

用X＝｛x1，x2，…，xm｝＝｛xi｜xi是程序語句，1≤i≤m｝表示程序，它是語句的集合，其中語句xi的下標(biāo)i可按程序的書寫方式編碼。假定程序是“精心”編碼的，即是由有責(zé)任心且有熟練技能的開發(fā)人員編寫的。然而由于各種各樣不可控制的因素的影響，程序發(fā)生錯誤仍然是難免的。把程序的錯誤歸咎到語句層次上，認(rèn)為它的每個(gè)語句出錯是一種偶然現(xiàn)象。因此，視程序X為（出錯）隨機(jī)變量，用rk＝P（xk出錯）表示語句xk出錯的概率。rk（k＝1，2，…，m）是程序X隨機(jī)變量的先驗(yàn)概率質(zhì)量函數(shù)?？梢愿鶕?jù)開發(fā)人員的經(jīng)驗(yàn)、歷史資料分析各種語句類型通常犯錯誤的可能性，也就是根據(jù)程序X的“樣式”確定rk之值。當(dāng)然不同的人可能有不同的估計(jì)值，然而即使這些估計(jì)值粗糙、不精確，只要大體上反映了程序編寫時(shí)的客觀情況，它們對于語句錯誤定位算法都是有用的。如果缺少這方面的資料，可以按照統(tǒng)計(jì)學(xué)上“同等無知”原則，令rk＝1/m，k＝1，2，…，m，其中m是程序X的語句總數(shù)。

2.2 測試隨機(jī)變量T

用T＝｛t1，t2，…，tn｝表示測試用例集，其中tj（j＝1，2，…，n）表示測試用例，以下有時(shí)簡稱為用例。它們是用來對程序X進(jìn)行測試的。設(shè)計(jì)測試用例的目的是想捕獲程序錯誤，它們捕獲錯誤的可能性也是隨機(jī)現(xiàn)象，可以根據(jù)測試人員的經(jīng)驗(yàn)和軟件測試?yán)碚摯_定每個(gè)用例捕獲錯誤的概率，用pi＝P（ti發(fā)現(xiàn)錯誤）表示ti用例能檢測出錯誤的概率。若沒有這方面的資料，在算法里不妨假設(shè)pi＝1/n，其中n是T中測試用例的總數(shù)，這也是統(tǒng)計(jì)學(xué)中“同等無知”原則的應(yīng)用。

2.3 具體測試

用T測試X后，可以將T中用例分為兩類：Tp和Tf。Tp表示測試程序時(shí)沒有發(fā)現(xiàn)錯誤的所有用例組成的子集合，Tf表示測試程序時(shí)發(fā)現(xiàn)錯誤的所有測試用例組成的子集合。Tp和Tf中的用例分別稱為通過用例和失敗用例。每個(gè)用例覆蓋語句的具體信息也可從測試活動里提取出來。一般來說，從具體測試活動中可以得到上述兩類信息。

2.4 測試功效矩陣F

根據(jù)具體測試結(jié)果，構(gòu)造測試用例集T的功效矩陣F。F是一個(gè)n×m階矩陣，列對應(yīng)程序X

的語句，行對應(yīng)測試集T里的用例。即第i行為：ti＝ti1ti2ti3ti4…tim，i＝1，2，…，n

其中，tij（j＝1，2，…，m）表示第i個(gè)用例測試結(jié)果對語句xj出錯概率“純粹功效”。我們建議：

其中，i＝1，2，…，n；j＝1，2，…，m；c1、c2都是大于1的正數(shù)。

設(shè)計(jì)tij的思想是，如果ti是失敗用例，則它覆蓋語句應(yīng)承擔(dān)較多責(zé)任。用α表示ti覆蓋的語句可能犯錯誤的概率，β表示ti未覆蓋的語句出錯的概率，令α＝c1β，c1＞1是合理的。于是，由αl＋β（m－l）＝1，α＝c1β，可得：

若ti是通過用例，則它未覆蓋的語句對程序出錯應(yīng)承擔(dān)較多責(zé)任。同樣，用α表示ti覆蓋的語句可能犯錯誤的概率，β表示ti未覆蓋的語句出錯的概率，這時(shí)令β＝c2α，c2＞1是合理的。于是，由αl＋β（m－l）＝1，α＝c2β，可得：

為了計(jì)算簡單起見，下面算法皆采用c1＝c2＝2。即：

其中，i＝1，2，…，n；j＝1，2，…，m。

以公式（2）產(chǎn)生的tij（i＝1，2，…，n；j＝1，2，…，m）為元素的矩陣稱為（測試集）功效矩陣，記為：

2.5 修正系數(shù)

計(jì)算向量b＝（b1b2…bm），其中bi表示對程序X第i個(gè)語句xi出錯概率進(jìn)行調(diào)整的修正系數(shù)，其定義如下：

固定xi，我們知道tji是從用例tj的觀點(diǎn)看待語句xi出錯的可能性，而pj是用例tj捕獲錯誤的能力，因此對于語句xi而言，把t1i，t2i，…，tni按照p1，p2，…，pn加權(quán)求和得到xi出錯的修正系數(shù)是合理的。

今后稱向量b為修正向量，其中i＝1，2，…，m，元素bi稱為xi的修正系數(shù)。

2.6 后驗(yàn)概率

用向量f＝（f1f2…fm）表示（準(zhǔn)）隨機(jī)分布，其中fi定義如下：稱向量f為原程序X的（準(zhǔn)）后驗(yàn)概率分布。也可以將f“標(biāo)準(zhǔn)化”，即令a＝f1＋f2＋…＋fm，則由fi←fi/a得到的序列是“真正”概率分布，記如此分布的隨機(jī)變量為XT。

然而就對語句出錯的排序而言，未標(biāo)準(zhǔn)化的f和標(biāo)準(zhǔn)化后的f作用是一樣的，今后我們就用未標(biāo)準(zhǔn)化的f作為XT的（準(zhǔn)）概率分布，并省略“準(zhǔn)”字，它與標(biāo)準(zhǔn)化后的概率不難從上下文中分辨出來。

2.7 語句出錯排序

根據(jù)fi（i＝1，2，…，m）的值，從大到小排序，如果有若干個(gè)值相等，則按它們相應(yīng)的語句出現(xiàn)的次序排序（語句編號較小的排列在前），得到：

把式（6）中具有相等值的fij歸為一類，然后把fij換成對應(yīng)的語句xij，這樣就把程序語句按出錯可能性從大到小排列成若干個(gè)等級。假如是k個(gè)等級，則寫成表格形式，如表1所示。

Table 1 Rank of faulty statements表1 出錯語句排列等級

程序員可以按照上面次序?qū)ふ页鲥e語句，一般地，找到真實(shí)錯誤以后，就重新用測試集T測試，若仍有失敗用例，再按表1（或者式（6））尋找下一個(gè)錯誤語句，……，如此進(jìn)行下去，直到用例全部通過為止。當(dāng)然中途也可以更改測試用例（增添或修改）。

3 TBFL算法評價(jià)標(biāo)準(zhǔn)

假如某個(gè)TBFL算法已把程序語句出錯可能性排列成類似于表1的等級，它也可看作是語句出錯可能性的排序式（6）。設(shè)程序X真實(shí)錯誤語句為xi，xi，…，xi，定義三個(gè)評價(jià)標(biāo)準(zhǔn)：12s

D1＝真實(shí)錯誤語句出現(xiàn)在表1中的等級之和，

D2＝真實(shí)錯誤語句出現(xiàn)在表1中的次序（即xi1次序?yàn)?，…，xim次序?yàn)閙）之和，

若有兩個(gè)TBFL算法，可以分別計(jì)算它們相應(yīng)的D1、D2、D3之值，一般地，D1與D2越小越好，D3越大越好，D1、D2之值越小越好是明顯的，而D3越大表示該TBFL算法辨別能力較強(qiáng)，區(qū)分語句的精度較高，所以相應(yīng)的算法就比較優(yōu)越。

4 實(shí)例分析

為了和Dicing方法、TARANTULA方法、SAFL方法以及文獻(xiàn)［12］提出的方法（下面簡稱Wang方法）作比較，我們采用的實(shí)例和文獻(xiàn)［12］中的實(shí)例一致。

本文主要用文獻(xiàn)［12］中圖1（該圖來源于文獻(xiàn)［3］）里給出的程序和測試用例。為了閱讀方便，把它復(fù)制于下，在本文中標(biāo)記為圖3。

在下面的討論中，稱圖3中的程序?yàn)槌绦騃，該程序的錯誤語句是x2（x2應(yīng)為：m＝z）和x7（x7應(yīng)為：m＝x）。

把程序I中的錯誤語句x2：“m＝x”改為正確語句x2：“m＝z”，其余語句保留不變，稱這個(gè)變體為程序II。程序II中有一個(gè)錯誤語句x7（m＝y(tǒng)）。

Figure 3 A faulty program and relative test cases圖3 錯誤程序和相關(guān)測試用例集信息

將程序I的x2（m＝x）改為x2（m＝z），x11（else if（x＞z））改為x11（else if（x＜z）），其余語句不變，稱這樣的變體為程序III。

將程序I的錯誤語句x7（m＝y(tǒng)）改為正確語句x7（m＝x），其余語句不變，稱這個(gè)變體為程序IV。

顯然上述四個(gè)程序的真實(shí)錯誤語句不盡相同，但它們“樣式”完全相同，所以估計(jì)每個(gè)語句出錯的（先驗(yàn)）可能性是一樣的，它們都是“客觀”存在的?，F(xiàn)在不管是哪個(gè)程序，我們都用X＝｛x1，x2，…，x13｝這個(gè)程序變量表示它，并且它的先驗(yàn)分布為：

這個(gè)先驗(yàn)分布是文獻(xiàn)［12］中采用的，關(guān)于它的詳情，請參看該文獻(xiàn)。在理論上，上述四個(gè)程序語句出錯情況是這個(gè)隨機(jī)變量X的四個(gè)“具體實(shí)現(xiàn)”。

在下面的討論中，稱圖3中的全部八個(gè)用例（即Test suite1＋Test suite2）組成的測試集為T，其中前四個(gè)用例（即Test suite1）組成的測試集為T＊。沿用文獻(xiàn)［12］中的術(shù)語，T為冗余測試集，T＊為無冗余測試集。粗略地說，在文獻(xiàn)［12］中，術(shù)語冗余指用例覆蓋的語句至少幾乎是完全相同的。詳情請見文獻(xiàn)［12］。

測試隨機(jī)變量T的先驗(yàn)分布為：

測試隨機(jī)變量T＊的先驗(yàn)分布為：

這些分布都是文獻(xiàn)［12］采用的，詳情也請參看文獻(xiàn)［12］。

例1 用T、T＊兩測試集測試程序I。

用T測試集測試程序I，結(jié)果是：Tp＝｛t3，t4，t5，t6，t7，t8｝，Tf＝｛t1，t2｝，其覆蓋語句情況可從圖3中看出。

利用公式（2）計(jì)算功效矩陣F中的諸元素tij，i＝1，2，…，n；j＝1，2，…，m。由它們組成的測試功效矩陣F如下（為了清楚起見，列用語句xi標(biāo)出，中間的虛線是為了區(qū)分Test suite1和Test suite2畫的）：

由F矩陣和T的分布（式（9）），利用公式（4）計(jì)算修正系數(shù)如下：

如果令P＝（p1p2…pn）為T測試集概率分布向量，則修正系數(shù)向量b＝（b1b2…bm）可以由下面矩陣乘法得出：

由式（12）計(jì)算出的修正系數(shù)向量和X的先驗(yàn)分布（式（8）），利用公式（5）即fi＝biri（i＝1，2，…，m），可以求出程序X的（未標(biāo)準(zhǔn)化的）后驗(yàn)概率如下（其中因子N＝1/220）：

最后，根據(jù)fi的值，按從大到小排序，并根據(jù)表1劃分成等級排列如表2第二行（上面標(biāo)號為等級標(biāo)號）。

Table 2 Rank of statements of program I under test suite T and under test suite T＊表2 程序I分別在測試集T和在測試集T＊下的出錯語句排序

用測試集T＊測試程序I，T＊測試結(jié)果即為前面的Test suite1的測試結(jié)果。因此T＊測試功效矩陣F＊即由公式（11）中前四行（虛線以上部分）組成。設(shè)T＊的先驗(yàn)分布向量為P＊，由式（10）得到，于是由T＊測試得到的修正系數(shù)向量b＊，可由式（12）即b＊＝P＊·F＊計(jì)算，再由b＊和X的先驗(yàn)分布（式（8）），利用公式（5）得到程序X的（未標(biāo)準(zhǔn)化的）后驗(yàn)概率如下（具體計(jì)算步驟省略）：

按照上面的值，把語句出錯可能性從大到小排成等級，見表2第三行。

現(xiàn)將本文算法（下面簡稱為新算法）與文獻(xiàn)［12］中的算法（記為Wang方法）以及Dicing方法、TARANTULA方法、SAFL方法進(jìn)行比較，除了本文算法以外，其余算法的資料都摘自于文獻(xiàn)［12］。

關(guān)于可能出錯語句的（等級）排序：

分析式（13）中數(shù)據(jù)，正如文獻(xiàn)［12］指出，無論測試集是否冗余，Wang方法除了在T測試時(shí)，把正確語句x10排在錯誤語句x7前，與T＊測試時(shí)“正確排序”有些差異以外，就這個(gè)具體例子而言，Wang方法比前幾種方法都優(yōu)。同樣，從式（13）中也可看出，本文算法和Wang方法的排序在T下幾乎一樣，在T＊下是完全一致。現(xiàn)在我們在T測試下，用式（7）給出的標(biāo)準(zhǔn)比較一下這兩個(gè)算法（回憶x2、x7有錯）：

Wang：D1＝1＋3＝4，D2＝1＋3＝4，D3＝7；

新算法：D1＝1＋3＝4，D2＝1＋3＝4，D3＝9。

雖然它們的D1和D2都相同，但是本文的算法比Wang方法精細(xì)，所以本文算法較優(yōu)。

例2 用T＊測試集測試程序II

程序變量X和測試集T＊變量的先驗(yàn)分布同前，分別由式（8）、式（10）表示。用測試集T＊測試程序II時(shí)，每個(gè)用例覆蓋語句的情況和前例中一樣，沒有變化，但t2在前例中是失敗用例，在本例中是通過用例，其他用例的結(jié)果類型未變，即在本例中Tf＝｛t1｝，Tp＝｛t2，t3，t4｝。

利用測試資料，可以構(gòu)造T＊測試功效矩陣，然后算出修正系數(shù)，從而得到X的后驗(yàn)分布（中間過程省略）fi值，由fi值可把程序語句依出錯可能性從大到小排成等級，并與Wang方法對比，如表3所示。

Table 3 Rank of program II’s statements under test suite T＊and comparison with Wang approach表3 程序II在測試集T＊下語句排序及和Wang方法對比

由于排序完全一樣，所以它們的功能在這個(gè)具體例子中是一樣的。

例3 用測試集T＊測試程序III

程序變量X和測試集變量T＊的分布同前，分別由式（8）、式（10）表示。用T＊測試程序III，結(jié)果類型為：Tf＝｛t1，t2，t3｝，Tp＝｛t4｝。至于覆蓋語句方面，t1、t4覆蓋的語句和它們在例1中覆蓋的語句情況一樣，t2、t3覆蓋語句情況有所變動，t2覆蓋x1x2x3x8x9x11x12x13；t3覆蓋x1x2x3x8x9x11x13，因此測試集T＊的功效矩陣需要重新計(jì)算。具體計(jì)算省略，同樣修改系數(shù)和后驗(yàn)概率的計(jì)算過程也省略，按照后驗(yàn)概率的值，把程序III中的語句按出錯可能性大小排成等級并與Wang方法比較，如表4所示。

Table 4 Rank of program III’s statements under test suite T＊and comparison with Wang approach表4 程序III在測試集T＊下語句排序及和Wang方法對比

根據(jù)文獻(xiàn)［12］的分析，程序III有嚴(yán)重的邏輯錯誤，它是由于語句x11的錯誤選擇導(dǎo)致的，具體表現(xiàn)在x2語句的設(shè)置上，即程序流程中有的路徑要求語句x2為“m＝z”，有的路徑要求語句x2為“m＝x”。因此，程序III的錯誤語句可以歸結(jié)為x2、x7、x11、x12。詳細(xì)分析請見文獻(xiàn)［12］。

現(xiàn)在評價(jià)在這個(gè)具有隱蔽邏輯錯誤的程序上兩個(gè)算法的功效：

因?yàn)閤2是個(gè)“設(shè)置語句”，要求程序員有較高的編程技巧，但是一旦檢查出x2語句在設(shè)置上的“邏輯”困境，就可以發(fā)現(xiàn)是語句x11的設(shè)計(jì)問題以及連帶產(chǎn)生的語句x12的錯誤，所以實(shí)質(zhì)上是要考察x2、x7。然而就這種考察而言兩個(gè)算法的功效幾乎一致，如果就x2、x7、x12的考察而言（因?yàn)榭疾炝诉@3個(gè)語句，肯定就會發(fā)現(xiàn)x11有錯），則兩個(gè)算法在它們的“線性”次序上完全一致。

例4 用例全部通過的測試

仍然考慮程序I，它有兩個(gè)錯誤語句x2、x7，程序變量X的先驗(yàn)分布由式（8）表示。

現(xiàn)在用測試集To＝｛o1，o2，o3，o4｝對程序I進(jìn)行測試，其中用例的設(shè)計(jì)為：o1＝｛10，13，15｝，o2＝｛8，6，4｝，o3＝｛5，9，2｝，o4＝｛17，19，2｝。To的先驗(yàn)分布為均勻分布，即P1＝P2＝P3＝P4＝1/4，也就是說每個(gè)用例捕獲錯誤的可能性相同。

用To測試發(fā)現(xiàn)它們都是通過用例。它們覆蓋語句情況是：o1覆蓋6個(gè)語句（x1，x2，x3，x4，x5，x13）；o2覆蓋7個(gè)語句（x1，x2，x3，x8，x9，x10，x13）；o3覆蓋8個(gè)語句（x1，x2，x3，x8，x9，x11，x12，x13），o4覆蓋情況和o1相同。

利用上述數(shù)據(jù)可以計(jì)算To測試功效矩陣、修正系數(shù)和后驗(yàn)概率，具體計(jì)算省略，根據(jù)后驗(yàn)概率把語句排序結(jié)果與Wang方法的結(jié)果并列如表5。

Table 5 Rank of program I’s statements when test cases are passed and comparison with Wang approach表5 程序I在測試用例全部通過情況下出錯語句排序及和Wang方法比較

顯然，無論采用哪個(gè)標(biāo)準(zhǔn)（D1、D2還是D3），本文算法都比Wang方法好！一般來說，測試員只能報(bào)告軟件缺陷存在，卻不能報(bào)告軟件缺陷不存在。通常的測試在所有用例都通過時(shí)，對于軟件缺陷都“無話可說”。因此，文獻(xiàn)［12］的算法和本文的算法在這種情況下更有價(jià)值，特別是在這個(gè)例子里，本文算法竟然把x2x7排在最前面，更使人相信新算法的優(yōu)越性。

例5 先驗(yàn)概率未知情況

取程序I，但程序變量X的先驗(yàn)分布未知，這時(shí)令X服從均勻分布，即rk＝1/13，k＝1，2，…，13。取測試集T＊，但測試集變量T＊的先驗(yàn)概率未知，這時(shí)令T＊服從均勻分布，即pj＝1/4，j＝1，2，3，4。用測試集T＊測試程序I，結(jié)果與例1中的測試結(jié)果完全相同。所以，這里測試集T＊的功效矩陣與例1中用T＊測試的功效矩陣相同。但修改系數(shù)，進(jìn)而后驗(yàn)概率的數(shù)值不同，計(jì)算方法同前，省略。

茲將Wang方法和本文算法在這個(gè)例子中關(guān)于語句出錯可能性從大到小排序，如表6所示。

Table 6 Rank of statements under unkonwn prior probability and comparison with Wang approach表6 先驗(yàn)概率未知情況下出錯語句排序及與Wang方法比較

這兩個(gè)算法功效基本上相同，但是都不怎么好。正如文獻(xiàn)［12］指出，隨機(jī)算法的精神是挖掘程序中和測試集中包含的固有信息，并把它們摻合進(jìn)具體測試實(shí)施中，才能發(fā)揮更大的功效。本文算法和文獻(xiàn)［12］算法都是隨機(jī)算法，只是利用先驗(yàn)知識這個(gè)豐富“資源“的方法不同罷了。所以，當(dāng)這些先驗(yàn)知識缺乏時(shí)，功效降低甚至喪失，也就不難理解了。然而把這里的結(jié)果和式（13）比較就可以發(fā)現(xiàn)，在“最壞”（即沒有挖掘出程序和測試集里的信息）的情況下，本文算法也和上述三個(gè)方法相當(dāng)，而且僅就錯誤語句x2來說，本文算法重視程度較遜于TARANTULA方法，但比Dicing方法、SAFL方法的重視程度高。

例6 測試用例設(shè)計(jì)較好的情況

在前面的實(shí)例中，對程序I等的測試所用的測試集，無論是T、T＊還是To都設(shè)計(jì)得不好?，F(xiàn)在根據(jù)軟件測試經(jīng)驗(yàn)，應(yīng)該設(shè)計(jì)用例集，使得它們執(zhí)行時(shí)能覆蓋程序I（等程序）的每一條路徑。為此引入新的測試集：

其中，e1＝｛6，7，9｝，即輸入x＝6，y＝7，z＝9，e2＝｛8，7，9｝，e3＝｛10，7，9｝，e4＝｛11，10，7｝，e5＝｛9，10，7｝，e6＝｛8，10，9｝。因?yàn)槌绦騃和它的變體都是求三個(gè)輸入整數(shù)中的中位數(shù)，而三個(gè)數(shù)按“小、中、大”不同方式排列共有六種排列，所以如上設(shè)計(jì)的測試用例集可以通過程序I等程序的每條路徑，它是比較好的用例設(shè)計(jì)。當(dāng)然，對于現(xiàn)在討論的程序來說，設(shè)計(jì)好的測試集至少還應(yīng)該包括輸入的三個(gè)數(shù)中有若干個(gè)相等的用例，以及比較大的整數(shù)用例，關(guān)于后者并不是本質(zhì)問題，至于前者，由于前面的測試集T、T＊都包含了這種用例。我們已經(jīng)看到算法對這些用例的適應(yīng)程度，所以為了說明問題，設(shè)計(jì)了T′。

下面用T′測試程序I、程序II和程序IV，無論用T′測試哪個(gè)程序，根據(jù)設(shè)計(jì)它的意圖來看，每個(gè)用例捕獲錯誤的可能性相同，即pi＝P（ei）＝1/6，i＝1，2，…，6。注意T′的均勻分布是“客觀”的先驗(yàn)分布，并不是由于“同等無知”得到的。

由于算法與上面一樣，因此計(jì)算過程省略不寫。只把在T′測試下，新算法和文獻(xiàn)［12］中算法對語句排序的結(jié)果對比列出，如表7～表9所示。

Table 7 Rank of program I’s statements under test suite T′and comparison with Wang approach表7 用T′測試程序I語句可能出錯排序及和Wang方法比較

兩個(gè)算法排序完全一致，且把有錯語句x2、x7排在前兩位，但新算法D3＝9比Wang方法D3＝7大，所以更精細(xì)。

Table 8 Rank of program II’s statements under test suite T′and comparison with Wang approach表8 用T′測試程序II語句可能出錯排序及和Wang方法比較

除了排在前兩位的x2、x7的次序不同外，其他次序完全一樣，就錯誤語句x7的排列而言，Wang方法好，就排列的精細(xì)而言，新算法為好。

Table 9 Rank of program IV’s statements under test suite T′and comparison with Wang approach表9用T′測試程序IV語句可能出錯排序及和Wang方法比較

兩個(gè)算法的排序完全一致且把錯誤語句x2排在第一位，但是新算法顯然比Wang方法精細(xì)。

5 結(jié)束語

就我們所知，文獻(xiàn)［12］為TBFL方法引入了一個(gè)新類型，其精神是用隨機(jī)理論考察軟件測試問題。本文對文獻(xiàn)［12］中的算法做了一點(diǎn)改進(jìn)。正如引言里所說，主要是把程序X的先驗(yàn)分布和測試集T的先驗(yàn)分布從測試活動中分離出來，這種分離是有好處的。因?yàn)闇y試活動和它的結(jié)果都是“客觀”的，它是這種類型算法中的科學(xué)成分，而程序變量X和測試集變量T的先驗(yàn)分布是“主觀”的，它是這種類型算法里的藝術(shù)成份。文獻(xiàn)［13］認(rèn)為，在最嚴(yán)格的數(shù)學(xué)學(xué)科里，數(shù)學(xué)思維也包含這兩種成份。另外，文獻(xiàn)［14］用樸素模糊邏輯闡述了許多中醫(yī)問題，說明了定性推理的重要性以及它和邏輯（或說是定量）推理的關(guān)系?？梢哉J(rèn)為X和T的先驗(yàn)分布這個(gè)藝術(shù)部分屬于定性推理，這一點(diǎn)可以從它們分別是從分析程序“樣式”和設(shè)計(jì)用例的“意圖”得到的看出。現(xiàn)在我們的算法把文獻(xiàn)［12］算法中包含的科學(xué)（邏輯）成份和藝術(shù)（定性）成份分離，就可以讓測試結(jié)果交給不同的人處理，不同的人可以根據(jù)他們的經(jīng)驗(yàn)對這些客觀資料作創(chuàng)造性處理。如果若干個(gè)測試員或程序員平行處理這些測試結(jié)果，就可能會得到不同的排序情況，綜合他們的結(jié)論，對修正較大較重要的軟件缺陷是有益的。這和許多醫(yī)學(xué)專家會診一個(gè)疑難病癥，對醫(yī)療是有幫助的一樣。

本文提出的算法只是對文獻(xiàn)［12］引入的隨機(jī)TBFL方法的一種改進(jìn)，今后，我們將努力開發(fā)新的隨機(jī)TBFL方法，并將其應(yīng)用到實(shí)際的測試活動中去。

致謝：衷心感謝徐寶文教授、邢漢承教授、周毓明教授對本文工作的支持。審稿人對本文提出了有價(jià)值的修改意見，在此表示衷心感謝！

［1］ Agrawal H，Horgan J，London S，et al.Fault localization using execution slices and dataflow tests［C］∥Proc of the 6th International Symposium on Software Reliability Engineering，1995：143－151.

［2］ Cleve H，Zeller A.Locating causes of program failures［C］∥Proc of the 27th International Conference on Software Engineering，2005：342－351.

［3］ 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.

［4］ Kyriazis A，Mathioudakis K.Enhance of fault localization using probabilistic fusion with gas path analysis algorithms［J］.Journal of Engineering for Gas Turbines and Power，2009，131（5）：51601－51609.

［5］ Jones J A，Harrold M J，Stasko J.Visualization of test information to assist fault localization［C］∥Proc of the 24th International Conference on Software Engineering，2002：467－477.

［6］ Jones J A，Harrold M J.Empirical evaluation of the tarantula automatic fault－localization technique［C］∥Proc of the 20th IEEE/ACM International Conference on Automated Software Engineering，2005：273－282.

［7］ Liblit B，Naik M，Zheng A X，et al.Scalable statistical bug isolation［C］∥Proc of the ACM SIGPLAN Conference on Programming Language Design and Implementation（PLDI），2005：15－16.

［8］ Schach S R.Object－oriented classical software engineering［M］.Beijing：China Machine Press，2007.

［9］ Liu C，Yan X，F(xiàn)ei L，et al.SOBER：Statistical model－based bug localization［C］∥Proc of the 13th ACM SIGSOFT Symposium on Foundations of Software Engineering，2005：286－295.

［10］ Renieris M，Reiss S P.Fault localization with nearest neighbor queries［C］∥Proc of the 18th International Conference on Automated Software Engineering，2003：30－39.

［11］ Zeller A.Isolating cause－effect chains from computer programs［C］∥Proc of the 10th ACM SIGFOFT Symposium on Foundations of Software Engineering，2002：1－10.

［12］ Wang Zhen－zhen，Xu Bao－wen，Zhou Yu－ming，et al.New random testing－based fault localization approach［J］.Computer Science，2013，40（1）：5－14.（in Chinese）

［13］ Wang Jian－wu.Introduction to mathematical thinking method［M］.Hefei：Anhui Education Press，1996.（in Chinese）［14］ Wang Zhen－zhen.Construction of knowledge database of na?ve fuzzy description logic and na?ve reasoning［J］.Applied Science and Technology，2012，39（6）：18－29.（in Chinese）

附中文參考文獻(xiàn)：

［12］ 王蓁蓁，徐寶文，周毓明，等.一種隨機(jī)TBFL方法［J］.計(jì)算機(jī)科學(xué)，2013，40（1）：5－14.

［13］ 王健吾.數(shù)學(xué)思維方法引論［M］.第1版.合肥：安徽教育出版社，1996.

［14］ 王蓁蓁.樸素模糊描述邏輯知識庫構(gòu)造及其樸素推理［J］.應(yīng)用科技，2012，39（6）：18－29.