基于錯誤傳播網(wǎng)絡的回歸測試用例排序方法

潘偉豐　李　兵　周曉燕　何　鵬

1(浙江工商大學計算機與信息工程學院　杭州　310018)

2(武漢大學國際軟件學院　武漢　430072)

3　　　(軟件工程國家重點實驗室(武漢大學)　武漢　430072)

(wfpan1982@163.com)

?

基于錯誤傳播網(wǎng)絡的回歸測試用例排序方法

潘偉豐1李兵2周曉燕3何鵬3

1(浙江工商大學計算機與信息工程學院杭州310018)

2(武漢大學國際軟件學院武漢430072)

3(軟件工程國家重點實驗室(武漢大學)武漢430072)

(wfpan1982@163.com)

Regression Test Case Prioritization Based on Bug Propagation Network

Pan Weifeng1, Li Bing2, Zhou Xiaoyan3, and He Peng3

1(SchoolofComputerScienceandInformationEngineering,ZhejiangGongshangUniversity,Hangzhou310018)

2(InternationalSchoolofSoftware,WuhanUniversity,Wuhan430072)

3(StateKeyLaboratoryofSoftwareEngineering(WuhanUniversity),Wuhan430072)

AbstractTest case prioritization (TCP), as one of the regression testing techniques, can greatly improve the efficiency of regression testing. Considering that most of the existing TCP techniques neglect to use software structure information, this paper proposes a new regression test case prioritization technique based on bug propagation network. It uses weighted class dependency network (WCDN) to represent the topological structure of a piece of software at the class level of granularity, and then analyzes the propagation process of bugs on WCDN to construct the BPN. When performing regression test case prioritization, it first locates the modified classes and the potential impacted classes. Then it calculates the test influence for each class. Finally, the test importance for each test case, the sum of the test importance of all classes it covered, is calculated as the criteria to prioritize regression test cases. Case studies on several real world open-source software systems show that, compared with other test case prioritization techniques, the proposed technique has better effectiveness and comparable stability.

Key wordsbug propagation; test case prioritization (TCP); complex network; software network; regression testing

摘要測試用例排序技術通過對測試用例進行排序以提高回歸測試的效率.針對現(xiàn)有方法未能充分利用軟件結構信息的不足，提出了基于錯誤傳播網(wǎng)絡的測試用例排序方法.該方法在類粒度將軟件抽象成加權類依賴網(wǎng)絡(weighted class dependency network，WCDN)模型，并基于WCDN分析錯誤在網(wǎng)絡上的傳播行為，構造錯誤傳播網(wǎng)絡(bug propagation network，BPN).測試用例排序時，首先在BPN中定位變更類和可能受變更類波及的類，從而計算類的測試重要性，最后以測試用例覆蓋類的測試重要性總和作為最終的排序依據(jù).實例研究表明，基于錯誤傳播網(wǎng)絡的測試用例排序方法在錯誤檢出率上相比于其他經(jīng)典方法有一定的提高，并且具有較好的穩(wěn)定性.

關鍵詞錯誤傳播；測試用例排序；復雜網(wǎng)絡；軟件網(wǎng)絡；回歸測試

軟件測試是軟件開發(fā)的重要過程之一，目的是盡可能多地發(fā)現(xiàn)軟件中的錯誤.它是保證軟件質量的重要手段.然而軟件測試工作量往往比較大，測試成本高.因此，如何提高測試效率、保證軟件質量已經(jīng)成為軟件工程領域研究的熱點與難點[1].

回歸測試是軟件測試的重要過程，用于檢測代碼修改是否引入新的錯誤.為了提高測試效率，人們提出了測試用例排序[1]、測試用例選擇[2]等方法.測試用例排序把優(yōu)先級最高的測試用例放在最早運行以達到某種目標(如盡早提供測試反饋信息、盡早檢測出錯誤等).研究表明，測試用例排序可以提高測試集的錯誤檢出率[3].然而，當前測試用例排序技術的研究大多針對面向過程語言開發(fā)的系統(tǒng)，針對面向對象語言開發(fā)的系統(tǒng)的研究還比較少.與此同時，軟件內部結構對軟件質量和缺陷的傳播有重要的影響[4].因此，測試用例排序研究也應融入軟件結構信息，而這一點往往為人們所忽視.

復雜系統(tǒng)和復雜性科學被國內外許多科學家認為是21世紀科學發(fā)展的前沿.近年來以復雜網(wǎng)絡為代表的復雜系統(tǒng)研究興起.復雜網(wǎng)絡為我們從整體和全局的角度研究復雜系統(tǒng)的結構和行為提供了一種有力的工具.軟件系統(tǒng)是一類人工復雜系統(tǒng)，也可以從復雜網(wǎng)絡的角度研究.從不同粒度看，軟件系統(tǒng)可以看成是由服務、數(shù)據(jù)對象、操作、模塊、類、構件、子系統(tǒng)等元素所組成，通過這些元素的交互實現(xiàn)預期的計算功能.在軟件的復雜網(wǎng)絡(簡稱軟件網(wǎng)絡)中，節(jié)點代表軟件的各組成元素；邊代表組成元素間的相互作用關系，如數(shù)據(jù)交換、消息傳遞、語義關聯(lián)等[5].近年來，軟件網(wǎng)絡研究不斷興起，成為將軟件工程從傳統(tǒng)的經(jīng)驗型推廣為計算型方法的橋梁[6].

軟件缺陷通常是由軟件中錯誤的傳播引起的[7]，表現(xiàn)為錯誤通過軟件網(wǎng)絡的傳播和擴散.為了在測試用例排序時，綜合考慮錯誤傳播行為及軟件結構等因素的影響，我們提出了一種基于錯誤傳播網(wǎng)絡的測試用例排序方法(regression test case prioritization based on bug propagation network, RTCP-BPN).RTCP-BPN結合復雜網(wǎng)絡理論，構造錯誤傳播網(wǎng)絡，研究錯誤在面向對象軟件中的傳播過程，進而量度類及測試用例的測試重要性，并依據(jù)測試用例的測試重要性對回歸測試用例進行排序，以提高測試效率.最后，我們以3個包含JUnit測試集的Java軟件及其多個版本為研究對象，運用RTCP-BPN實施測試用例排序，并通過與其他方法的比較，驗證了RTCP-BPN的有效性和穩(wěn)定性，并揭示了RTCP-BPN的有效性與軟件結構的關系.

1研究背景和相關工作

1.1測試用例排序

測試用例優(yōu)先級排序問題可以形式化地定義如下：

定義1. 測試用例優(yōu)先級排序問題[1].給定測試用例集T；T的全排列組合PT；從PT到實數(shù)的函數(shù)f.求一個T′∈PT,使得(?T"∈PT)(T″≠T′)[f(T″)≥f(T′)].其中，PT包括了測試用例的所有可能的執(zhí)行順序，函數(shù)f的值代表對測試結果的評價.

根據(jù)程序和測試用例的信息，可以把測試用例排序方法分成不同種類[8-9].1)根據(jù)所用的代碼覆蓋信息：按照測試用例覆蓋的在前一個軟件版本中執(zhí)行的語句數(shù)、方法數(shù)等排序；2)根據(jù)反饋信息的使用：在排列測試用例的時候，如果選擇了一個測試用例，則關于這個測試用例的信息可用于重新計算尚未被選擇的測試用例的值；3)根據(jù)代碼的修改信息：例如代碼修改的數(shù)量可以作為排序的依據(jù).

早期測試用例排序方面的研究主要關注排序方法的效率和代價、性能的評估以及各方法間的比較研究[3].研究發(fā)現(xiàn)，排序方法的性能取決于被測程序的特征、所用的測試用例集和程序的修改情況.當前的研究主要關注影響排序方法效率的因素，如：Rothermel等人[1]研究測試用例集的設計對測試用例排序方法的影響；Elbaum等人[3]研究程序結構特征、測試用例組合和排序的變化等因素對于排序方法性能的影響；Do等人[10]研究了不同編程語言對測試用例排序方法有效性的影響.

上述方法大多是根據(jù)面向過程語言的特點，以測試用例和代碼的信息作為標準進行測試用例排序.對于應用越來越廣泛的面向對象語言(如Java)，還缺乏根據(jù)面向對象特點的測試用例排序研究.本文將面向對象軟件抽象成網(wǎng)絡模型——軟件網(wǎng)絡，應用復雜網(wǎng)絡最新研究成果，分析錯誤在軟件網(wǎng)絡中的傳播行為，提出了基于錯誤傳播網(wǎng)絡的測試用例排序方法.

1.2基于復雜網(wǎng)絡的軟件結構分析

軟件網(wǎng)絡可以描述軟件系統(tǒng)的骨架，從較高層次描述軟件的結構，強調軟件系統(tǒng)的拓撲結構特征.用復雜網(wǎng)絡的觀點來審視、研究軟件系統(tǒng)的軟件網(wǎng)絡觀，得到了越來越多軟件工程領域研究者的認同和重視.1)在軟件網(wǎng)絡拓撲結構特性研究方面，文獻[6,11]在不同層次(方法、類和包等)對大量開源軟件的依賴網(wǎng)絡進行了分析，發(fā)現(xiàn)這些網(wǎng)絡都具有“小世界”和“無標度”特性.2)在軟件網(wǎng)絡演化機理研究方面，文獻[12]提出了一種基于復制和分岔規(guī)則的軟件演化模型；He等人[13]從設計模式的角度提出了基于模式冷凍部分的軟件演化生長模型；Pan等人[14]根據(jù)軟件網(wǎng)絡中節(jié)點和邊之間的交互與動態(tài)變化，提出了一種基于軟件網(wǎng)絡的軟件演化模型.3)在軟件復雜性度量和評估方面，文獻[15]提出了一套度量指標來檢測軟件開發(fā)過程中軟件結構的穩(wěn)定性變化；Ma等人[16]提出了一個層次型的度量體系，從不同層次、不同角度度量大規(guī)模軟件系統(tǒng)的各種結構特性；Pan等人[17]提出了一種量度軟件質量實現(xiàn)軟件結構優(yōu)選的方法.

盡管軟件網(wǎng)絡研究有了一定的發(fā)展，但是現(xiàn)有的研究側重于分析和發(fā)現(xiàn)軟件網(wǎng)絡共有的結構特征及其形成規(guī)律，離工程實踐相距甚遠.如何用軟件網(wǎng)絡解決實際問題(如軟件測試)仍是一個很值得研究的問題.

2加權軟件網(wǎng)絡及錯誤傳播網(wǎng)絡

2.1加權軟件網(wǎng)絡

我們曾在文獻[17]提出了面向對象軟件系統(tǒng)的加權依賴網(wǎng)絡模型(加權特征依賴網(wǎng)絡和加權類依賴網(wǎng)絡)，本文將延用該模型.下面首先對該模型做簡要介紹.

定義2. 加權特征依賴網(wǎng)絡(weighted feature dependency network,WFDN)：

(1)

其中，Nf表示軟件系統(tǒng)中所有特征(方法和屬性)節(jié)點的集合，Ef表示特征間依賴關系的有向邊集合.依賴關系主要指方法間的調用關系和方法使用屬性的關系，即如果方法M1調用了方法M2(或方法M1使用了屬性M2)，則在WFDN中有一條有向邊從代表方法M1的節(jié)點指向代表方法(或屬性)M2的節(jié)點.Pf是一個矩陣.如果在WFDN中有一條有向邊j,i(表示一個有序對)，從節(jié)點j指向節(jié)點i，則該邊權Pf(i,j)=1，否則Pf(i,j)=0.Pf(i,j)表示如果節(jié)點i出錯了，錯誤會以Pf(i,j)的概率傳播至節(jié)點j.Nf，Ef，Pf中的下標f代表WFDN是在特征粒度構建的.圖1給出了WFDN的一個例子.

Fig. 1　Illustration of WFDN.圖1　WFDN示例

定義3. 加權類依賴網(wǎng)絡(weighted class dependency network,WCDN)：

(2)

其中，Nc表示軟件系統(tǒng)中所有類和接口的節(jié)點集合，Ec是有向邊的集合.Ec(i,j)表示節(jié)點i和節(jié)點j存在邊，方向從節(jié)點i指向節(jié)點j，表示類之間的依賴關系.Pc是一個矩陣.Nc，Ec，Pc中的下標c代表WCDN是在類粒度構建的.如果i,j∈Ec，則邊權Pc(j,i)表示錯誤在類節(jié)點j和類節(jié)點i之間傳播的概率，計算為

(3)

其中，|s|返回集合s中元素的個數(shù)，GCF(j)返回類j的特征集合，類內傳播域ICRB(i,j)表示類j中直接或間接為類i中的方法使用的特征集合.類i中方法a1直接或間接使用類j中特征an，當且僅當存在一條有向路徑a1→a2→…→an，ai∈GCF(i)或ai∈GCF(j).影響概率Pc(j,i)的值在0～1之間，值越大，表明如果類j中的特征出錯，則影響到類i的概率越大.圖2是圖1所示W(wǎng)FDN相應的WCDN.圖3給出了一個計算類間錯誤傳播概率的例子.

Fig. 2　Illustration of WCDN.圖2　WCDN示例

Fig. 3　Illustration of error propagation probability calculation.圖3　錯誤傳播概率計算示例

如圖3所示，C.d()→C.a()→B.d()，C.a()→B.d()，所以類B中被類C中方法使用的特征集合為{B.d()}，即ICRB(C,B)={B.d()}.同時，GCF(B)={B.a,B.b(),B.c(),B.d()}.因此，Pc(B,C)=|ICRB(C,B)||GCF(B)|=0.25，即如果類B發(fā)生錯誤，可能有0.25的概率影響依賴它的類C.同理，我們可以求得Pc(C,B)=0.5.

2.2錯誤傳播網(wǎng)絡

定義4. 錯誤傳播網(wǎng)絡(bug propagation network,BPN)：

(4)

BPN的節(jié)點集Nb和WCDN一樣.邊集Eb是由Ec修改得到的，即若WCDN中節(jié)點i和節(jié)點j間不存在直接的依賴關系，但是若存在有向路徑i→t1→t2→…→tn→j，則BPN中節(jié)點i和節(jié)點j間也將存在一條有向邊Eb(i,j)，邊權等于所有這些有向路徑邊權之和(單條路徑的邊權為該路徑上所有邊的邊權乘積之和)，即：

(5)

若WCDN中節(jié)點i和節(jié)點j間已存在直接的依賴關系，但是又存在有向路徑i→t1→t2→…→tn→j，則節(jié)點i和節(jié)點j間的邊權等于所有這些有向路徑邊權之和(單條路徑的邊權為該路徑上所有邊的邊權乘積之和)與這2個節(jié)點間直接依賴的邊權之和，即：

(6)

若WCDN中節(jié)點C沒有邊指向節(jié)點A，但是存在有向路徑C→B→A，則節(jié)點C和節(jié)點A間也將存在一條有向邊Eb(C,A)，邊權等于該路徑上所有邊的邊權乘積之和，即Pb(C,A)=0.25×0.33=0.08.WCDN中又存在有向路徑C→E→A和C→B→E→A，則節(jié)點B和節(jié)點A間的邊權等于所有這些有向路徑邊權之和與這2節(jié)點間直接依賴的邊權之和，即Pb(C,A)=0.08+0.5×0.67+ 0.25×0.5×0.67=0.08+0.335+0.08375=0.5.同理可以得到其他節(jié)點對之間的邊及其邊權，從而得到與圖2中WCDN相應的BPN,如圖4所示:

Fig. 4　Corresponding BPN of WCDN in Fig. 2.圖4　WCDN相應的BPN

3RTCP-BPN方法

3.1指標定義

本文提出的方法依據(jù)的排序標準是每個測試用例覆蓋的修改類的測試重要性總和.在具體描述本文方法的過程之前，我們首先給出類的測試重要性和測試用例的測試重要性的定義.

定義5. 類測試重要性(testing importance of classes,TIC).數(shù)值上第j個類的測試重要性TIC(j)等于BPN中指向這個節(jié)點邊的邊權和，即：

(7)

定義6. 測試用例測試重要性(testing impor-tance of test cases,TITC).測試用例的測試重要性由其覆蓋的被修改類的測試重要性定義.若GTC(i)表示返回第i個測試用例覆蓋的被修改類的集合，則第i個測試用例的測試重要性TITC(i)定義為其覆蓋的所有被修改類的測試重要性的總和，即：

(8)

3.2RTCP-BPN方法框架

圖5給出了RTCP-BPN方法的框架，具體如：

1) 構建軟件的BPN.可以使用代碼分析工具SSQAT[17]分析Java軟件的字節(jié)碼，得到代碼的依賴關系，計算WFDN和WCDN，最終構造出BPN.

2) 分析軟件連續(xù)2個版本間的差異，定位修改部分的代碼及其所在的類.

3) 在BPN中定位被修改的類，計算它們的測試重要性.

4) 計算所有測試用例的測試重要性，并依據(jù)測試用例的測試重要性降序排列所有測試用例(如果2個測試用例的值相同則隨機排序)，最終得出一個測試用例序列.

Fig. 5　Framework of RTCP-BPN.圖5　RTCP-BPN方法框架

3.3測試用例排序方法有效性評價指標

由于測試的目標之一是檢測錯誤，因此測試用例排序方法的錯誤檢測能力成為一個重要的度量標準，即(average of the percentage of faults detected,APFD)錯誤檢出率[1]為

(9)

其中，n為測試用例數(shù)；m為錯誤數(shù)；TFi表示排序后的測試用例集T′中第1個檢測出錯誤i的測試用例的位置.APFD計算一個測試集的平均加權錯誤檢出率，取值范圍是0～100%，值越高表示越快檢測出錯誤，即錯誤檢測的效率越高.

3.4實驗與分析

為了驗證RTCP-BPN在面向對象的Java軟件測試用例排序中的有效性，以及與已有的排序方法進行比較，我們設計了以下實驗.

3.4.1實驗對象

對于測試用例排序方法，合適的實驗對象應當包括程序、連續(xù)版本、測試用例和錯誤數(shù)據(jù)[1].本文選取3個面向對象Java開源軟件進行實驗分析，其中：jtopas是用于轉換文本數(shù)據(jù)的Java庫[18]，phex是點對點的文件共享客戶端[19]，jmeter是用于負載測試及衡量性能的桌面應用[20].選取的軟件都是文獻[10]列出的用于測試用例排序實驗的實驗對象，附帶了JUnit的測試用例集.表1列出了3個軟件的類總數(shù)#c(class number)、JUnit測試類的總數(shù)#t_c(test class number)、JUnit測試方法的總數(shù)#t_m(test method number)、版本數(shù)#v(version number)以及包含的錯誤數(shù)#e(error number).

Table 1　Statistics of Subjects

3.4.2對比的方法

為了驗證RTCP-BPN的有效性，我們共選取了1.1節(jié)中描述的3種分類中的共6種排序方法[3]：

1) 最優(yōu)排序方法(optimal prioritization, Optimal).為了量度排序方法的效率，使用包含已知錯誤的軟件進行實驗，從而可以得知哪個測試用例檢測出哪個錯誤，通過計算得出一個使錯誤檢出率最大的排列順序.這個順序在實際上是不能達到的，但是它可以作為各種排序方法有效性的一個上限.

2) 總體類覆蓋排序方法(total class coverage prioritization, Class-tl).計算每個測試用例覆蓋的類數(shù)，并根據(jù)類數(shù)從大到小排序.如果多個測試用例覆蓋的類數(shù)目相同，則隨機排序.

3) 基于反饋的類覆蓋排序方法(additional class coverage, Class-al).結合反饋信息和覆蓋信息.首先選擇覆蓋類數(shù)目最大的測試用例，然后修改其余的測試用例包含的未覆蓋的類信息，重復這一過程直到所有類至少被1個測試用例覆蓋.如果有多個測試用例覆蓋類的數(shù)目相同則隨機選擇.如果所有的類都被覆蓋，在其余的測試用例中重復這個過程直到所有的測試用例都排序完畢.

4) 總體差異覆蓋排序方法(total difference coverage, Diff-tl).計算每個測試用例覆蓋的不同的類的總數(shù)，根據(jù)數(shù)目從大到小排序.如果有多個測試用例覆蓋的類數(shù)目相同，則隨機排序.

5) 基于反饋的差異覆蓋排序方法(additional difference coverage， Diff-al).類似Class-al，結合反饋信息和覆蓋的不同類數(shù)目排序.

Fig. 6　Distribution of the APFD of jtopas.圖6　jtopas的APFD值分布

6) 隨機排序(random prioritization, Random).對測試用例進行隨機排序，然后按照排序后的順序執(zhí)行測試用例.

3.4.3實驗結果及分析

使用3.4.2節(jié)中的6種方法和RTCP-BPN方法進行測試用例排序實驗，并計算相應的APFD(結果見表2～4).實驗中涉及1個軟件的多個版本，而1次測試用例排序實驗是針對同一軟件連續(xù)的2個版本進行的.因此，針對同一軟件的多次實驗，我們分別計算了平均值(mean,M)、標準差(standard deviation,SD)、最大值(maximum,max)和最小值(minimum,min).圖6～8是各表相應的箱線圖.同時，因為Random方法每次所得隨機序列都會不同，導致APFD值在多次實驗中不穩(wěn)定，不利于比較.因此，后續(xù)表中Random方法的APFD值都是20次獨立運行所得APFD的平均值.

Table 2　APFD of jtopas

Table 3　APFD of phex

Table 4　APFD of jmeter

Fig. 7　Distribution of the APFD of phex.圖7　phex的APFD值分布

Fig. 8　Distribution of the APFD of jmeter.圖8　jmeter的APFD值分布

1) RTCP-BPN有效性評估

為了分析RTCP-BPN的有效性，我們分別針對不同的軟件，以APFD值為依據(jù)，比較了RTCP-BPN與其他6種排序方法的性能.從表2～4可以發(fā)現(xiàn)：在jtopas中，RTCP-BPN的APFD最接近Optimal，并且其APFD平均值都高于其他5種排序方法，比Class-tl的APFD平均提高了約9.9%，比Class-al的APFD平均提高了約6.6%，比Diff-tl的APFD平均提高了約1.1%，比Diff-al的APFD平均提高了約1.1%，比Random的APFD平均提高了約32.9%.

在phex中，RTCP-BPN的APFD最接近Optimal，并且其APFD平均值都高于其他5種排序方法，比Class-tl的APFD平均提高了約6.7%，比Class-al的APFD平均提高了約6.4%，比Diff-tl的APFD平均提高了約4.3%，比Diff-al的APFD平均提高了約4.6%，比Random的APFD平均提高了約24.2%.在jmeter中，RTCP-BPN的APFD最接近Optimal，并且其APFD平均值都高于其他5種排序方法，比Class-tl的APFD平均提高了約1.7%，比Class-al的APFD平均提高了約2.0%，比Diff-tl的APFD平均提高了約1.2%，比Diff-al的APFD平均提高了約0.7%，比Random的APFD平均提高了約13.7%.

RTCP-BPN沒有利用反饋信息，也不是基于差異覆蓋的排序方法，但是從實驗的軟件系統(tǒng)看來，卻比使用了反饋信息的排序方法Class-al和Diff-al，以及基于差異覆蓋的排序方法Diff-tl和Diff-al獲得了更高的錯誤檢出率.可見，考慮了軟件結構信息及錯誤傳播的排序方法確實能提高錯誤的檢出率.

2) RTCP-BPN穩(wěn)定性評估

此外，對于每個軟件的不同版本都進行了多次實驗，并且計算了標準差，如表2～4所示.對于jtopas，RTCP-BPN的標準差較大，僅低于Class-al和Random，但是其排序的效果是最好的；對于phex，RTCP-BPN方法的標準差僅高于Optimal，說明相比于其他方法，RTCP-BPN方法的穩(wěn)定性較好；對于jmeter，RTCP-BPN方法的標準差僅高于Optimal和Class-al，說明相比于其他方法，RTCP-BPN方法的穩(wěn)定性較好.

3) RTCP-BPN有效性與軟件結構特征的關系

RTCP-BPN所依賴的BPN的構建，以及類測試重要性的測度都依賴于軟件的內部結構.為了分析RTCP-BPN方法的有效性與軟件結構特征的內在關系.我們統(tǒng)計了這3個軟件的常用復雜網(wǎng)絡參數(shù)，包括網(wǎng)絡規(guī)模(network scale,NS)(類數(shù))、平均最短路徑(average path length,L)、網(wǎng)絡直徑(diameter,D)和聚集系數(shù)(clustering coefficient,C)，結果如表5所示.在計算一個軟件相應網(wǎng)絡參數(shù)時，我們計算的是該軟件多個版本的平均值.

Table 5　Complex Network Parameters of Subjects

同時，我們將RTCP-BPN方法的APFD與Optimal方法APFD的比值定義為APFD最優(yōu)比(APFDoptimal ratio,AOR)，以測度RTCP-BPN方法相比于Optimal方法的相對有效性.在jtopas, phex, jmeter這3個系統(tǒng)中，AOR分別是0.857，0.904，0.921.我們分析了AOR與復雜網(wǎng)絡參數(shù)間的Pearson相關性，結果如表6所示：

Table 6Correlation Analysis ofAORand Software Complex

Network Parameters

表6　AOR與軟件復雜網(wǎng)絡參數(shù)的相關性分析

數(shù)據(jù)顯示，AOR與網(wǎng)絡規(guī)模、平均最短路徑、網(wǎng)絡直徑存在弱正相關性，而與聚類系數(shù)存在弱負相關性.這說明，隨著軟件網(wǎng)絡規(guī)模、平均最短路徑和網(wǎng)絡直徑的增長，以及網(wǎng)絡聚集系數(shù)的降低，RTCP-BPN排序方法的效果將更好.不難想象，隨著網(wǎng)絡規(guī)模即網(wǎng)絡中類節(jié)點數(shù)目的增加，網(wǎng)絡的不均勻性增加，聚集系數(shù)變小，連通的節(jié)點之間的路徑長度越小，缺陷的傳播越容易，其影響范圍也越大，因此phex和jmeter采用錯誤傳播網(wǎng)絡BPN的實驗結果比jtopas的實驗結果好.

4總結與展望

從軟件內部結構出發(fā)，加入以錯誤在軟件中傳播的概率作為邊權構造錯誤傳播網(wǎng)絡，計算軟件中被修改類的測試重要性，并以測試用例覆蓋的修改類測試重要性總和作為排序標準，用于測試用例排序.實例研究表明，考慮軟件結構及錯誤傳播影響的測試用例排序方法對于提高錯誤檢出率很有幫助，優(yōu)于已有的基于覆蓋和基于修改信息的排序方法，并且具有較好的穩(wěn)定性.同時，排序方法有效性與軟件結構的相關性分析顯示，隨著軟件網(wǎng)絡規(guī)模、平均最短路徑和網(wǎng)絡直徑的增長，以及網(wǎng)絡聚集系數(shù)的降低，本文排序方法的效果將更明顯.

在未來研究過程中，將選擇更多不同類型、不同規(guī)模、不同語言的軟件，驗證本文測試用例排序方法的有效性，進一步完善和改進采用錯誤傳播網(wǎng)絡的測試用例排序方法.

參考文獻

[1]Rothemel G, Untch R H, Chu C Y, et al. Prioritizing test cases for regression testing [J]. IEEE Trans on Software Engineering, 2001, 27(10): 929-948

[2]Jeffrey D, Gupta N. Improving fault detection capability by selectively retaining test cases during test suite reduction [J]. IEEE Trans on Software Engineering, 2007, 33(2): 108-123

[3]Elbaum S, Malishevsky A G, Rothermel G. Test case prioritization: A family of empirical studies [J]. IEEE Trans on Software Engineering, 2002, 28(2): 159-182

[4]Zhou Y M, Leung H. Empirical analysis of object-oriented design metrics for predicting high and low severity faults [J]. IEEE Trans on Software Engineering, 2006, 32(10): 771-789

[5]Li Bing, Ma Yutao, Liu Jing, et al. Advances in the studies on complex networks of software systems [J]. Advances in Mechanics, 2008, 38(6): 805-814 (in Chinese)(李兵, 馬于濤, 劉婧, 等. 軟件系統(tǒng)的復雜網(wǎng)絡研究進展 [J]. 力學進展, 2008, 38(6): 805-814)

[6]Myers C R. Software systems as complex networks: Structure, function, and evolvability of software collaboration graphs [J]. Physical Review E, 2003, 68(4): 046116

[7]Maggie H, Katerina G P. Common trends in software fault and failure data [J]. IEEE Trans on Software Engineering, 2009, 35(4): 484-496

[8]Srivastava A, Thiagarajan J. Effectively prioritizing tests in development environment [C]Proc of the 2002 ACM SIGSOFT Int Symp on Software Testing and Analysis (ISSTA’02). New York: ACM, 2002: 97-106

[9]Rothermel G, Elbaum S, Malishevsky A G, et al. On the test suite composition and cost-effective regression testing [J]. ACM Trans on Software Engineering and Methodology, 2004, 13(3): 277-331

[10]Do H, Rothermel G, Kinneer A. Prioritizing JUnit test cases: An empirical assessment and cost-benefit analysis [J]. Empirical Software Engineering, 2006, 11(1): 33-70

[11]Pan W F, Li B, Ma Y T, et al. Multi-granularity evolution analysis of software using complex network theory [J]. Journal of Systems Science and Complexity, 2011, 24(6): 1068-1082

[12]Krapivsky P L, Redner S. Network growth by copying [J]. Physical Review E, 2005, 71(3): 036118

[13]He K Q, Peng R, Liu J, et al. Design methodology of networked software evolution growth based on software patterns [J]. Journal of Systems Science and Complexity, 2006, 19(2): 157-181

[14]Pan W F, Li B, Ma Y T, et al. A novel software evolution model based on software networks [C]Proc of the 1st Int Conf of Complex Networks (Complex’09). Berlin: Springer, 2009: 1281-1291

[15]Vasa R, Schneider J G, Nierstrasz O. The inevitable stability of software change [C]Proc of the 23rd IEEE Int Conf on Software Maintenance (ICSM 2007). Piscataway, NJ: IEEE, 2007: 4-13

[16]Ma Y T, He K Q, Du D H, et al. A complexity metrics set for large-scale object-oriented software systems [C]Proc of the 6th IEEE Int Conf on Computer and Information Technology (CIT’06). Piscataway, NJ: IEEE, 2006: 189-194

[17]Pan W, Li B, Ma Y, et al. Measuring structural quality of object-oriented softwares via bug propagation analysis on

中圖法分類號TP311

通信作者：李兵(bingli@whu.edu.cn)

基金項目：國家自然科學基金項目(61202048,61273216,61272111)；浙江省自然科學基金項目(LY15F020004,LY13F020010)；浙江省科技廳公益技術研究項目(2014C23008)

收稿日期：2014-12-08；修回日期：2015-03-10

This work was supported by the National Natural Science Foundation of China (61202048, 61273216,61272111), the Natural Science Foundation of Zhejiang Province of China (LY15F020004, LY13F020010) and the Commonweal Project of Science and Technology Department of Zhejiang Province (2014C23008).