基于軟件節(jié)點重要性的集成測試序列生成方法

王　瑩　于　?！≈熘玖?/p>

(東北大學軟件學院　沈陽　110819)

(wangying8052@163.com)

?

基于軟件節(jié)點重要性的集成測試序列生成方法

王瑩于海朱志良

(東北大學軟件學院沈陽110819)

(wangying8052@163.com)

A Class Integration Test Order Method Based on the Node Importance of Software

Wang Ying, Yu Hai, and Zhu Zhiliang

(SoftwareCollege,NortheasternUniversity,Shenyang110819)

AbstractClass integration test order is one of the most important issues in the field of software integration testing. The different integration test orders have great influence on the testing costs and testing efficiency. In order to reduce the test costs, the traditional studies of generating class-level integration test order focused on reducing the total test stub complexities and the number of test stubs. We apply the thought of “bugs should be found as early as possible” to generate the integration test order, and propose an evaluation scheme “Class-HITS” to measure the importance of software nodes. In the proposed scheme, we firstly consider the software as a network based on the complex network theory, and with the help of proposed scheme, the circles of the network are eliminated. Finally, the integration test order is obtained by reverse sorting the nodes in acyclic links. The simulations have been carried out on open-source software, which prove the efficiency of the class integration test order obtained by the proposed scheme. The new algorithm ensures the important nodes with priority to be tested, the smaller total complexity of the test stubs.

Key wordssoftware integration testing; complex network; node importance; HITS algorithm; class integration test order

摘要集成測試序列是軟件集成測試的重要問題之一.不同的集成測試順序對測試成本以及測試效率的影響很大.為降低測試成本，傳統(tǒng)的類級集成測試順序研究策略大多圍繞如何減少構建測試樁數(shù)量和降低測試樁總體復雜度2個方面.若能將復雜程度高、出錯概率大的類和發(fā)生錯誤后傳播范圍較大的類優(yōu)先進行測試，不僅可以使得錯誤被盡早發(fā)現(xiàn)，還可以有效減小錯誤對系統(tǒng)的破壞性.為此，將上述思想應用到生成集成測試序列的算法當中，提出一種軟件節(jié)點重要度的評估方法(Class-HITS).該方法利用復雜網(wǎng)絡理論，將軟件抽象為網(wǎng)絡的形式，并結合所提出的重要度評估方法，打破軟件網(wǎng)絡中的環(huán)路，然后針對網(wǎng)絡的無環(huán)鏈路逆向拓撲排序，最終得到類的集成測試序列.通過實驗分析證明，利用該方法得出的集成測試序列既能夠保證重要節(jié)點優(yōu)先被測試，又確保了構造的測試樁的總復雜度較小.

關鍵詞軟件集成測試；復雜網(wǎng)絡；節(jié)點重要性；HITS算法；類級測試序列

尋找類的測試順序(class integration test order, CITO)是面向對象軟件集成測試中重要的問題之一，類的先后測試順序關系到錯誤發(fā)現(xiàn)的時間和構建測試樁所花費的測試成本[1].如果軟件系統(tǒng)的類間依賴關系不存在環(huán)路，則可以通過簡單的逆向拓撲排序生成集成測試序列，但事實上，軟件的復雜性使得測試人員需要通過刪除類間的依賴關系來進行破環(huán)操作，同時引入軟件測試樁來模擬被刪除邊所連接的2個類之間的對象相互行為[2].

傳統(tǒng)的類級集成測試順序研究策略大多圍繞如何減少構建測試樁的數(shù)量和降低測試樁的總體復雜度2個方面.Briand等人[3]利用遺傳算法提出了生成測試順序的方法，并基于類間的耦合度量給出了估算測試樁復雜度的公式.Le等人[4]采用基于測試依賴圖模型的方法進行集成測試，在不區(qū)分邊的依賴類型的情況下，減少樁的數(shù)量，但是該算法在生成測試順序時具有不確定性，導致不同的檢索方式下，構造的測試樁數(shù)目差異較大.而Tai等人[5]利用權重來選擇移除能夠打破最多環(huán)路的關聯(lián)邊，從而生成最佳測試序列.在此基礎上，Briand等人[1]為繼承邊、聚合邊和關聯(lián)邊賦予不同的權重，然后根據(jù)權重決定移除哪些依賴關系.姜淑娟等人[6]結合類間耦合度量與圖啟發(fā)式算法，在打破環(huán)路的同時保證測試樁的總復雜度盡量小.張艷梅等人[7]提出了一種基于動態(tài)依賴關系的類集成測試方法，分析了類之間的靜態(tài)依賴關系和動態(tài)依賴關系，然后在保證測試樁數(shù)據(jù)盡可能小的前提下，消除環(huán)路，并開發(fā)了類測試序列的自動生成工具.上述研究在生成測試序列的同時，均未考慮軟件系統(tǒng)中類節(jié)點的測試重要性問題，存在一定的局限性.若將易發(fā)生錯誤的重要測試節(jié)點排在較后位置測試，則會導致錯誤延遲被發(fā)現(xiàn)，影響軟件的測試效率.因此，一組高效的集成測試序列的生成方法在軟件測試研究領域具有重要的價值.

復雜性高的類引入錯誤的概率相對較高，應該被重點測試[8].Zhou等人[9]利用面向對象軟件復雜性的度量指標對軟件缺陷進行預測，研究表明軟件的復雜性與軟件錯誤的數(shù)量、分布和嚴重級別有著密切的關系.然而，軟件缺陷在系統(tǒng)中并不是均勻分布的，一些簡單的底層代碼片段也可能出錯，并且如果其在系統(tǒng)的多處被直接或間接調用，則會導致整個軟件網(wǎng)絡的崩潰.因此，集成測試時還應該重點考慮錯誤的傳播影響問題[10].

本文將錯誤應被盡早發(fā)現(xiàn)的思想應用到軟件集成測試序列中，利用復雜網(wǎng)絡理論[11]，提出了一種基于軟件節(jié)點重要性的集成測試序列生成方案.在集成測試前，首先對類的測試重要性進行度量，得到出錯傾向性大、一旦發(fā)生錯誤對整個軟件系統(tǒng)傳播影響力強的類；在破環(huán)操作時，既要保證上述重要節(jié)點優(yōu)先被測試，又要保證構造的測試樁總復雜度較小.

1軟件重要測試節(jié)點度量方法

類的復雜性與軟件缺陷呈現(xiàn)一定正相關性，并且在版本演化過程中，修改結構復雜性高的類比修改復雜性低的類引入錯誤的概率更高，可見復雜類的錯誤傾向性更高[12-13].此外，錯誤在不同的類中傳播的范圍以及對系統(tǒng)的影響力也各不相同[14-15].本文綜合評估了軟件中類的復雜性以及當類自身發(fā)生錯誤時對整個系統(tǒng)的影響力2個方面的因素，借鑒傳統(tǒng)對超鏈接排序的HITS算法[16]思想，提出了一種復雜網(wǎng)絡理論的節(jié)點測試重要性度量算法——Class-HITS.

1.1類級依賴網(wǎng)絡模型

現(xiàn)有的針對類級測試順序的研究大多是基于類簇之間的依賴關系形成的對象關系圖(object relation diagram, ORD)，但是ORD只包含類之間的繼承、關聯(lián)和聚合等靜態(tài)依賴關系，而事實上在軟件系統(tǒng)中還存在著動態(tài)依賴關系.動態(tài)依賴即在程序運行期間才形成的一種依賴關系.若類Xchild繼承于類Ysuper，且重寫了Ysuper中的虛函數(shù)(抽象函數(shù))，而類Zother調用了Ysuper中被重寫的虛函數(shù)(抽象函數(shù))，則在代碼運行時，類Zother可能會與Ysuper的子類Xchild動態(tài)綁定，形成Zother依賴于Xchild的一條有向關系[7].

由于代碼只有在運行時才能表現(xiàn)出軟件故障與失效，這與類之間的動態(tài)依賴密切相關，只抽取靜態(tài)依賴關系會造成功能路徑的缺失，導致測試不充分[17].因此，本文在對軟件系統(tǒng)進行建模時，將所有的類抽象為節(jié)點集合V={v1,v2,…,v|NC|}，節(jié)點之間的所有靜態(tài)和動態(tài)依賴關系抽象為連邊集合E={v1,v2|v1,v2∈V}，將軟件結構表示為有向網(wǎng)絡G(V,E)的拓撲形式，其中，NC為系統(tǒng)中類的總數(shù).

以圖1(a)的代碼為例，該系統(tǒng)由VA至VN的14個類構成，它們彼此之間存在17條依賴邊，抽象出有向網(wǎng)絡如圖1(b)所示，其中，類VG與類VF之間為動態(tài)依賴關系.

classVA{VGG=newVG();inta;voidMethodA(){G.MethodG1()};}classVB{VAA=newVA();intb=A.a+1;}classVC{VAA=newVA();intc;voidMethodC(){A.a++;};}classVD{VAA=newVA();intd;voidMethodD(){A.MethodA();};}abstractclassVE{inte;abstractvoidMethodE(){};}classVFextendsclassVE{intf;voidMethodE(){f++;};}classVG{VDD=newVD();VEE=newVF();VHH=newVH();VII=newVI();VJJ=newVJ();intg=D.d;voidMethodG1(){E.e++;};voidMethodG2(){I.i++;J.j=I.i+g;};voidMethodG3(){H.MethodH2();};voidMethodG4(){I.MethodI();};voidMethodG5(){E.MethodE();};}classVH{VEE=newVE();VII=newVI();VNN=newVN();VKK=newVK();VLL=newVL();VMM=newVM();inth;voidMethodH1(){E.e++;};voidMethodH2(){I.i++;N.n=I.i+g;};voidMethodH3(){K.k=L.l+M.m;};}classVI{ inti; ?}classVJ{ intj; ?}classVK{ intk; ?}classVL{ intl; ?}classVM{ intm; ?}classVN{ intn; ?}

(b) The directed network of the example code

(a) The example code

Fig. 1The example code and the corresponding directed network.
圖1示例代碼和相應的有向網(wǎng)絡

1.2重要測試節(jié)點的特性

顯然1個類容易出錯，或者一旦發(fā)生錯誤對系統(tǒng)的破壞性較大就應該優(yōu)先被重點測試.因此，在分析重要節(jié)點的特征時，本文主要考慮類的影響力和類的復雜性2個方面：

1) 類的影響力(impact of class, IC)通常在分析面向對象軟件中類的傳播影響力時，都是用節(jié)點的入度值來衡量，即如果1個類被越多的類所直接依賴，則當該類發(fā)生錯誤時對軟件系統(tǒng)的影響力越大.但是僅僅以入度值來評估類的影響力具有片面性，忽略了依賴這個類的其他類的復雜程度.類越復雜，其越有可能是網(wǎng)絡中的“Hub”節(jié)點，與之存在耦合關系的類可能越多，其自身承擔的功能也可能會越強大[11].如果1個類被多個復雜的類所依賴，則當這個類出錯時，可能會導致網(wǎng)絡的“漣漪效應”，從而造成錯誤的波及范圍變大，這樣的類應該優(yōu)先被重點測試[18].圖1(a)所示，節(jié)點VA和VE入度同為3，在網(wǎng)絡中具有一定的傳播影響力，區(qū)別在于節(jié)點VA只是被3個復雜性較低的VB，VC，VD所調用，而調用節(jié)點VE的類中包含復雜性高、功能強大的VG和VH，所以當VE發(fā)生錯誤時就可能會傳播到VF，VG，VH，VA，VD等距離更遠的節(jié)點，導致不能順利運行的功能路徑更多，且影響的功能也會更加重要.

2) 類的復雜性(complexity of class, CC)研究表明類的復雜性與面向對象軟件類的錯誤傾向性具有密切聯(lián)系，且大多使用C&K等復雜性度量指標來衡量[19-20].卻忽略了該類依賴的其他類的傳播影響力和結構復雜性，如果1個類依賴了越多錯誤傳播性強、影響力大的類，那么由于耦合關系將錯誤間接傳遞到該類自身的傾向性就會越大，其測試重要性和優(yōu)先級也就越高.例如圖1(b)中，節(jié)點VG和VH的出度同為6，為網(wǎng)絡中的“Hub”節(jié)點，具有一定的樞紐性，且較為復雜的節(jié)點，但是VG調用了VH的函數(shù)MethodH2()，而VH的函數(shù)MethodH2()又調用了VI和VN的屬性，導致VH的復雜性和傳播影響力直接或間接地傳遞到了VG中，所以VG的錯誤傾向性實質上高于VH.

由此可見，類的復雜性和錯誤傳播影響力相互作用、相互影響.類的復雜性與該類依賴的其他類的錯誤傳播影響力相關，而類的錯誤傳播影響力與所有依賴該類的其他類的結構復雜性相關.

1.3Class-HITS算法描述

通過分析可以發(fā)現(xiàn)，上述重要測試節(jié)點的2個特性：影響力和復雜性與計算超鏈接重要性的HITS算法思想中刻畫網(wǎng)頁重要性的2個指標——權威值和樞紐值極為相似.在HITS算法中，權威值受入度因素影響，而樞紐值受出度因素影響.一般地1個頁面的權威值由指向該頁面的其他頁面的樞紐值來決定：如果1個頁面被多個具有高樞紐值的頁面所指向，那么該頁面就具有較高的權威值.另一方面，1個頁面的樞紐值，由它所指向的頁面的權威值來刻畫：如果1個頁面指向多個具有高權威值的頁面，那么該頁面就具有高樞紐值[16,20-21].將上述理論中的頁面權威值和樞紐值分別使用類的復雜性和傳播影響力來替換，同樣可以適用于軟件測試節(jié)點重要性的計算.本文對HITS算法進行修改，提出了一種基于復雜網(wǎng)絡的節(jié)點重要性度量算法Class-HITS：

1) 將網(wǎng)絡G(V,E)中任意類節(jié)點vi∈V，1≤i≤|V|的復雜性和影響力的初始值設置為該類自身的復雜性度量值Ci.類自身的復雜性由多種因素共同決定，研究表明，類的規(guī)模、耦合性和結構復雜性是最重要的3個方面[8-9]，而C&K度量套件中的上述指標也經(jīng)常被用來預測類的錯誤傾向性[12-13,19-20].本文類的規(guī)模使用代碼行數(shù)和特征總數(shù)來度量，特征總數(shù)為類中所有屬性和方法數(shù)目的總和，耦合性用與該類存在耦合關系的類的數(shù)目來描述，結構復雜性表示為類中所有方法的圈復雜度之和[22]，最后，求出4種度量值歸一化后結果的加權之和即為初值Ci，如式(1)所示.這里令α+β+ω+δ=1，α，β，ω，δ∈，1≤i≤NC，WMCi，CBOi，LOCi，NOFi分別為類vi的結構復雜性、耦合度、代碼行數(shù)、特征總數(shù)值.

(1)

2) 由于類并不是軟件中最基本的元素，那么在有向類級軟件網(wǎng)絡中，節(jié)點之間的連邊表示的也并不是2個類之間100%的依賴關系.若用call(i,j)表示節(jié)點vi依賴類節(jié)點vj的特征數(shù)目，NOFj表示vj中所有屬性和方法數(shù)目的總和，則vi與vj的依賴比例值γij定義為

(2)

3) 節(jié)點測試重要性Wi的計算要綜合考慮該類vi的傳播影響力ICi和錯誤傾向性CCi.如式(3)所示，取二者的加權之和，即：

(3)

經(jīng)過上述改動的目的是：1)將類自身的復雜性融入到類的傳播影響力和復雜性的迭代計算中，使得類的復雜性不僅與該類自身的結構復雜性相關，而且與該類依賴的其他類的復雜性和傳播影響力相關，隨著迭代次數(shù)的增加，通過與該類的直接或間接依賴關系以一定概率γ累加到該類復雜性CCi的計算中；2)類的傳播影響力不僅與直接或間接調用這個類的其他類的個數(shù)相關，也與這些類的復雜性相關，該類被越多結構復雜性和錯誤傾向性高的類所依賴，則這個類發(fā)生錯誤時，錯誤通過與該類直接或間接的依賴關系以概率γ影響到的類以及功能路徑的范圍就越廣，影響到的系統(tǒng)功能也可能越重要.Class-HITS算法表述如下：

算法1. Class-HITS.

輸入：類級有向軟件網(wǎng)絡鄰接矩陣A=(aij)NC×NC；

輸出：節(jié)點測試重要性向量W=(W1,W2,…,WNC).

步驟1. 設定網(wǎng)絡中每個節(jié)點的影響力和復雜性初始值皆為類自身復雜性Ci的值, x(0)=(C1,C2, …,CNC)T,y(0)=(C1,C2,…,CNC)T.

步驟2. 節(jié)點影響力和復雜性向量的校正.節(jié)點的影響力和復雜性向量重復執(zhí)行步驟2.1～2.3的k次迭代，直到2組向量趨于穩(wěn)定，退出迭代.這里假設2組向量趨于穩(wěn)定的條件是‖xi(k)-xi(k-1)‖+‖yi(k)-yi(k-1)‖<ε.

步驟2.1. 節(jié)點影響力校正規(guī)則：每一個類節(jié)點的影響力校正為指向它的節(jié)點的復雜性乘以這2個節(jié)點間的依賴比例所得結果之和，即:

當且僅當有1條從節(jié)點vi指向節(jié)點vj的有向邊，aij=1，否則aij=0.

步驟2.2. 節(jié)點復雜性校正規(guī)則：每一個類節(jié)點的復雜性校正為它所指向的節(jié)點的影響力乘以這2個節(jié)點間的依賴比例所得結果之和，即

步驟2.3. 歸一化：

步驟3. 令W=0.5×x(k)+0.5×y(k)，輸出W.

同樣以圖1(b)所示的軟件網(wǎng)絡為例，加權鄰接矩陣A′和類的影響力及其復雜性的初始向量x(0)和y(0)如下，由于缺乏詳細信息，初始向量中的Ci值只用耦合度CBOi和特征數(shù)NOFi這2種度量指標，經(jīng)歷大約10次迭代后，2組向量趨于穩(wěn)定，從而得出最終的影響力和復雜性的結果向量如向量x(k)，y(k)，W所示，其中A表示類節(jié)點VA至VN的鄰接矩陣：

節(jié)點VG和VH的CC值分別為1.846 2，1.321 4，VG的復雜性大于VH，節(jié)點VA和節(jié)點VE的IC值分別為0.179 0，0.473 3，VA的傳播影響力小于VE.綜合來看，節(jié)點測試重要性排名前3的分別為VG，VH，VF3個節(jié)點，分別具有較高的錯誤傾向性和傳播影響力，且VG的CC值高于VH，應當被重點測試.綜上，通過Class-HITS計算出的節(jié)點測試重要性值，與上文的分析結果一致.

2集成測試序列生成方法

通過1.2節(jié)分析，在軟件系統(tǒng)中錯誤傾向性較高和傳播影響力較大的類，對軟件的穩(wěn)定性起著決定性作用[10,15]，因此本文綜合考慮重要測試節(jié)點優(yōu)先和降低測試樁復雜度2個因素，給出一種生成集成測試序列的算法，在保證錯誤盡早發(fā)現(xiàn)的同時，又縮減了測試成本.

2.1測試樁復雜度度量

測試樁，即用來開發(fā)或者測試一個依賴樁的組件，它是軟件模塊的一種概括或者基于某種特殊目的的實現(xiàn)[6,12].假設類VA依賴類VB，集成測試時，如果當測試類VA時，類VB尚未被測試，此時就需要為類VA模擬一個類VB的對象，這個模擬出來的Stub(VA,VB)就是測試樁，測試樁可以為待測類提供調用的屬性和方法[1].但是，在面向對象軟件系統(tǒng)中，模擬一個對象構造測試樁的代價很大.因此，在集成測試時，要盡量減少測試樁的復雜度以及避免給過于復雜的類模擬測試樁[3].

構建測試樁的代價可以用樁復雜度來估算.本文測量樁復雜度的方法利用文獻[3]的公式：

(4)

2.2集成測試順序

生成集成測試序列的目標是類級測試順序要最大程度地保證在每一個類測試之前，它所依賴的類都已經(jīng)測試完畢，即沿著類的依賴關系方向逆向排序，這樣既可以減少測試樁的數(shù)目，同時確保了集成測試的完整性[7,23].由此，可利用軟件網(wǎng)絡拓撲結構，找出類間關系構成的所有環(huán)路，隨之通過刪除連邊對軟件網(wǎng)絡進行破環(huán)操作，使其從有環(huán)圖轉為無環(huán)圖，這里每刪除1條邊，就需要為其建立1個測試樁，即刪除邊數(shù)等于測試樁數(shù)目.在不存在環(huán)路的情況下，類的測試順序很容易根據(jù)依賴關系逆向排列.

本文在執(zhí)行破環(huán)操作時要同時達到2個目標：既要滿足錯誤傾向性高、傳播影響力大的節(jié)點被優(yōu)先測試，又要滿足構造的測試樁總復雜度較低.

定義1. 依賴路徑PathD.假設SV為網(wǎng)絡中所有入度為0且出度不為0的類節(jié)點集合，EV為網(wǎng)絡中所有出度為0且入度不為0的節(jié)點集合，若有任意類節(jié)點vs∈SV，ve∈EV，且其之間可達，則稱PathD為一條vs與ve之間的依賴路徑.

定義2. 依賴深度D.設類節(jié)點vs∈SV，ve∈EV，若vs到ve存在一條依賴路徑PathD={v1,v2,…,vk,vk+1,…,vn}，則節(jié)點vk的依賴深度滿足Dk=|n-k|+1.

若Wi表示有向環(huán)路邊vi,vj起始節(jié)點vi的重要度值，Wi為Wi歸一化后的結果，，其中，Wmin和Wmax分別表示表示當前網(wǎng)絡中所有邊的Wi最小值和最大值，Loops(i,j)表示包含邊vi,vj在內(nèi)的環(huán)路總數(shù)，Loops′為Loops(i,j)歸一化后的結果，，Loopsmin和Loopsmax分別表示表示當前網(wǎng)絡中所有邊的Loops(i,j)最小值和最大值，SCplx(i,j)表示如果刪除了邊vi,vj后，需要為節(jié)點vi構建的節(jié)點vj的測試樁復雜度，則提出測試優(yōu)先度We(i,j)的定義如下：

定義4. 測試優(yōu)先度We(i,j)表示為構成環(huán)路的邊vi,vj賦予的權值，vi和vj分別為連接環(huán)路邊vi,vj2端的一類節(jié)點，1≤i,j≤NC,則有：

(5)

We(i,j)的含義是不但要保證重要度較高的節(jié)點vi可以優(yōu)先被測試，且刪除邊vi,vj的同時打破的環(huán)路數(shù)較多，即確保構造的測試樁數(shù)目較低，更要使得構造的測試樁復雜度SCplx(i,j)較小.測試優(yōu)先度為本文算法的核心思想，按照測試優(yōu)先度值的高低選擇將要刪除的邊vi,vj，并為該邊vi,vj構造測試樁，同時，本文也以We(i,j)作為破環(huán)優(yōu)劣的評價指標，生成集成測試序列的步驟如下：

1) 使用Tarjan算法深度優(yōu)先遍歷類級有向網(wǎng)絡G中的每一個節(jié)點，尋找到G中的每一個強連通分量SCC,由強連通分量的定義可知，有向圖的環(huán)路一定存在于SCC中.

2) 依次遍歷每一個SCC，在每個SCC中查找環(huán)路，接下來遍歷每一個環(huán)路，然后將每個環(huán)路中的每條邊按照式(5)賦予邊權值.

3) 刪邊操作，在刪除邊時，遵循4個原則：

① 當環(huán)路中邊權值最大的邊只有一條時，刪除環(huán)路中邊權值最高的邊；

② 如果邊權值最大的邊不止一條，則計算環(huán)路中所有邊終止節(jié)點的測試樁復雜度，選擇測試樁復雜度最小的邊刪除；

③ 如果邊權值最大的邊不止一條，且這幾條邊終止節(jié)點的測試樁復雜度也相等，那么刪除任意一條以重要度值最大的節(jié)點為起始節(jié)點的邊；

④ 直到有向圖中再無環(huán)路時，刪邊結束.

4) 過濾掉無環(huán)網(wǎng)絡的孤立節(jié)點，并對其剩余節(jié)點依次遍歷，計算每個節(jié)點的最大依賴深度Dmax，對Dmax相同的節(jié)點按照節(jié)點的重要度值Wi降序排序，對Dmax不同的節(jié)點按照節(jié)點的Dmax值升序排序.

5) 軟件網(wǎng)絡中的孤立節(jié)點大多是為后續(xù)功能擴展而預留的接口，故隨機排在最后，由此得到的節(jié)點順序即為最后總的集成測試序列O，O為有序集合.

對軟件源代碼掃描過后，將節(jié)點重要度評估的Class-HITS算法與網(wǎng)絡逆向拓撲排序相結合，得出最終結果.生成類級集成測試序列的算法如圖2所示:

Fig. 2　The diagram of generating integration test order algorithm.圖2　本文生成集成測試序列算法示意圖

3實驗分析

本文采用DNS 1.2.0①，ANT 1.9.4②，BCEL 5.0③這3款軟件作為實驗數(shù)據(jù)來驗證本文算法的有效性.選擇這3個系統(tǒng)的原因是:包括文獻[1,3,6-7]在內(nèi)的多個軟件集成測試實證研究中，這DNS，ANT，BCEL均被用作實驗測試對象.這3個系統(tǒng)的類數(shù)目從25～61不等，環(huán)路數(shù)目從16～416 091差異較大，因此可以從不同規(guī)模、復雜性以及環(huán)路密度等角度來共同驗證集成測試算法.類的序號順序與上述文獻的順序完全一致，在文獻[3]的附錄已經(jīng)詳細列出.

3.1重要測試節(jié)點實驗分析

Fig. 3　The software networks obtained by the dependency finder.圖3 Dependency Finder 抽象出的軟件網(wǎng)絡

Fig. 4　The node importance distribution diagram.圖4　節(jié)點重要度值分布圖

SoftwareNnodeWmaxWminWICmaxICminICCCmaxCCminCCDNS610.44210.00150.08270.702400.06730.262100.0982ANT250.46310.00070.13920.489300.14440.632000.1341BCEL450.32150.00640.10330.328600.12690.643000.0797

Fig. 5　The comparison of the node importance in the test order.圖5　測試序列節(jié)點重要度情況對比

如表2所示，分別為重要度值排名前5和后5的類節(jié)點結構度量值，本文分別使用節(jié)點的入度Kin、特征被調用次數(shù)Pce、出度Kout、特征總數(shù)NOF、調用特征次數(shù)Pc、結構復雜性WMC、代碼規(guī)模LOC表征類在系統(tǒng)中的重要程度，這些指標皆與本文提出的節(jié)點影響力、復雜性和節(jié)點重要度值成一定正相關性.在軟件DNS中，重要度值排名第1的21號類節(jié)點org.xbill.DNS.Name，內(nèi)部含有33個特征，擁有系統(tǒng)最大的入度值，被除自身以外的其他40個類調用了135次，調用其他5個類的特征48次，雖然其特征被調用次數(shù)小于重要度值排名第2的8號類org.xbill.DNS.Compression，但是由于直接或間接調用21號類的其他類的結構復雜性和錯誤傾向性較高，導致它具有較高的影響力.軟件ANT重要度值最大的是16號類org.apache.tools.ant.Project，內(nèi)部含有131個特征，其結構復雜性(WMC值)、代碼規(guī)模(LOC值)、入度值、特征被調用次數(shù)、和調用次數(shù)分別是37，2300，14，125，98，而這些指標皆為系統(tǒng)中最高值.軟件BCEL中，重要度值排名第1的為第23號類節(jié)點org.apache.bcel.classfile.DescendingVisitor，雖然它的入度值為0，但是其擁有最大的出度值、結構復雜性(WMC值)和碼規(guī)模(LOC值)，平均每個特征調用其他類的特征4.4次，也就是說，其他類的錯誤傾向性和結構復雜性隨著依賴關系大大加重了23號類的復雜性，這些類一旦發(fā)生錯誤也極易傳播進23號類中.排名靠前的其他節(jié)點與表格列出節(jié)點類似，均具有較高的入度、出度、被調用次數(shù)或者調用其他類特征次數(shù)，相應地也就擁有較高的復雜性因子或者影響力因子，應該被盡早測試.在排名后5的節(jié)點中，很多節(jié)點的入度值或出度值為0，缺乏由于直接或間接調用其他類的特征而產(chǎn)生的復雜性，以及直接或間接被其他類的特征調用而產(chǎn)生的傳播影響力.與系統(tǒng)中其他類相比，較為簡單且出錯概率小，且一旦出錯也不會傳播到軟件系統(tǒng)的其他類中，對于這樣的類，測試的優(yōu)先級理應靠后.綜上，本文提出的針對軟件網(wǎng)絡節(jié)點測試重要性評估的Class-HITS算法正確有效，排序結果也可以應用到后續(xù)的生成集成測試序列中.

Table 2　The Statistic of the Top Five Nodes And Last Five Nodes

3.2生成集成測試序

得到軟件網(wǎng)絡所有節(jié)點的測試重要度值后，再根據(jù)2.2節(jié)提出的方法，求出3種軟件的集成測試序列，并與文獻[1,3-4,6-7]進行對比分析.其中，文獻[1,3-4,6]的系統(tǒng)模型只考慮了類間靜態(tài)依賴關系，而文獻[7]加入了動態(tài)依賴的分析.為了保證對比的公平性，本文分為2種情況討論，首先忽略掉動態(tài)依賴邊，與前4種算法比較，然后加入動態(tài)依賴邊與文獻[7]進行對比分析.此外，文獻[1,4,7]算法得到的測試序列均是以減少測試樁數(shù)目為前提；而文獻[3,6]是以降低測試樁的總復雜度為目的.這里，測試優(yōu)先度的計算式(5)中η，μ的值皆暫取為0.5.為方便對照，本文類的序號順序、測試樁復雜度的公式均與文獻[3,7]相同，即λ=τ=0.5.

首先，使用Tarjan算法在網(wǎng)絡中查找強連通分量SSC，然后進行破環(huán)操作.軟件DNS在加入動態(tài)依賴邊的同時，并沒有增加網(wǎng)絡的環(huán)路個數(shù).所以，在2種情況下，系統(tǒng)內(nèi)均包含2個強連通分量，分別為{33,38,52}以及{58,48,32,25,11,8,21}，共形成了16個環(huán)路，在靜態(tài)依賴結構下，應用本文算法與文獻[3]在破環(huán)的過程中均刪除了6條邊{21→11,21→8,32→48,32→58,38→33,52→33}，需要建立的測試樁總復雜度為1.47，均低于文獻[1,4]，相應地在建立測試樁的同時，平均能夠比文獻[4]少建立39個屬性和71個方法.而在加入動態(tài)依賴的模型中，本文的測試樁總復雜度與文獻[7]相同.

在靜態(tài)依賴結構下，軟件ANT中包含1個強連通分量，其內(nèi)部含有12個節(jié)點{4，22，23，19，21，10，18，20，17，16，24}，形成654個環(huán)路.雖然文獻[1,3,6]分別刪除了11，12和10條就破除了所有環(huán)路，而本文在破環(huán)過程中共刪除了18條邊，但是應用本文算法所建立的樁總復雜度分別比文獻[1,3-4,6]的結果少了0.03，0.31，0.44，0.02.文獻[1,3-4,6]在建立測試樁的同時需要為所有的測試樁模擬屬性和方法總和分別為175.5，367.7，205，172，而本文構造測試樁的屬性和方法總和僅為147，節(jié)約了測試開銷.加入動態(tài)依賴的20條邊后，軟件ANT系統(tǒng)內(nèi)的強連通分量為{1,16,2,4,5,10,18,19,20,21,22,23,24,25,17}，環(huán)路數(shù)增加至8 894，在生成測試序列時文獻[7]共刪除了23條邊，而本文刪除了30條.但是，本文算法建立的樁總復雜度較低，且建立樁的方法和屬性綜合相比文獻[7]少了140個.

靜態(tài)結構下的軟件BCEL中包含1個強連通分量，其內(nèi)部含有40個節(jié)點.也就是說，網(wǎng)絡中除節(jié)點1，3，23，24，42外，皆構成強連通分量，雖然該軟件網(wǎng)絡節(jié)點總數(shù)較低，但卻形成了416 091個環(huán)路，文獻[1,3-4,6]在破環(huán)過程中平均刪除70，67.5，71，73條邊，而本文刪除的邊數(shù)為94，雖然刪邊數(shù)較多，但是建立的樁總復雜度較文獻[3-4,6]分別降低了2.36，1.93，0.53，本文為所有的測試樁模擬屬性和方法總和與文獻[3-4,6]相比，分別少了177，115，54.而增加了138條動態(tài)依賴邊后，BCEL的環(huán)路數(shù)目變?yōu)?26 826個，本文需要刪除96條邊才能夠打破所有環(huán)路，而文獻[7]的算法只建立了87個測試樁，但是，本文的測試樁總復雜度較文獻[7]減少了0.98，需要模擬的屬性和方法總數(shù)比文獻[7]減少了106個，大大降低了測試成本.

Table 3　The Test Orders Obtained by the Proposed Algorithm

表4中NUMp表示當測試完節(jié)點總數(shù)50%的時候，重要度排名前30%的節(jié)點就已經(jīng)被測試完畢的數(shù)目.3組實驗中利用本文算法得出的NUMp值均大于文獻[1,3-4,6-7]的結果，并且這種優(yōu)勢隨著軟件網(wǎng)絡節(jié)點數(shù)的增加而增大，例如在靜態(tài)結構下，具有25個節(jié)點的軟件ANT，本文算法與文獻[1,3-4,6]的NUMp的差值分別為3，2，2，3.加入動態(tài)依賴關系后，本文算法與文獻[7]得到的NUMp差值是3.靜態(tài)結構下具有45個節(jié)點的BCEL軟件，本文算法與文獻[1,3-4,6]NUMp的差值為6，7，6，6.加入動態(tài)依賴關系后，本文與文獻[7]的NUMp差值是3.靜態(tài)結構下，具有61個節(jié)點的DNS軟件，本文算法與文獻[1,3-4,6]的NUMp的差值最大，分別為9，8，7，8.加入動態(tài)依賴關系后，本文與文獻[7]的NUMp差值是6.

利用3種算法生成的測試序列，其節(jié)點重要度的統(tǒng)計情況如圖5所示，橫坐標代表不同算法的測試序列O，縱坐標代表已完成測試節(jié)點的重要度累加和所占全部節(jié)點重要度總和的百分比(圖5(a)～(c)和圖5(d)～(f)分別表示靜態(tài)結構和動態(tài)結構下3個軟件系統(tǒng)重要度值的統(tǒng)計結果.從圖5中可以觀察出，由本文算法得出的測試序列，無論是靜態(tài)依賴網(wǎng)絡模型還是加入動態(tài)依賴關系后的網(wǎng)絡模型，在整個集成測試過程的前半部分，其測試節(jié)點的重要度累加曲線變化率明顯大于文獻[1,3-4,6-7]，即對相對重要的節(jié)點進行了優(yōu)先測試.

Table 4　The Comparison of the Experiment Results

由于本文使用測試優(yōu)先度We(i,j)為每一條邊賦予權值，然后按照權值的高低排序來選擇將要刪除的邊，從而進行破環(huán)操作.如果單純將結構復雜的類優(yōu)先測試，由于其出度較大，可能會引起測試樁復雜度的激增，但是本文的節(jié)點重要度由類的錯誤傾向性和傳播影響力2個因素構成，其中，類的錯誤傾向性雖然與類的出度因素相關，同時也受該節(jié)點的耦合度，結構復雜性，特征總數(shù)和代碼規(guī)模等指標以及它所指向的其他類的傳播影響力和結構復雜性等多種因素影響.并且We(i,j)除了由節(jié)點重要度條件決定以外，還與樁復雜度和測試樁數(shù)目等因素相關.綜合上述實驗結果可以得出結論，由本文算法生成的測試序列，不僅重要的類節(jié)點被優(yōu)先測試，且可以保證測試樁復雜度較小，提高測試效率的同時，節(jié)約了測試成本.

4結論

本文將軟件系統(tǒng)中重要測試節(jié)點的2個特性——類的復雜性和類的影響力——結合起來，提出一種新的針對軟件網(wǎng)絡節(jié)點測試重要性評估的Class-HITS算法.從而將系統(tǒng)中容易出錯的類，以及發(fā)生錯誤后波及范圍較大的類視為重要測試節(jié)點.以盡早發(fā)現(xiàn)軟件缺陷和有效控制錯誤的傳播范圍作為測試目標，結合上述Class-HITS算法打破網(wǎng)絡中的環(huán)路，生成類級集成測試序列.通過與現(xiàn)有算法的實驗對比分析，證明了本文算法生成的類級集成測試序列，既保證了重要度值高的節(jié)點優(yōu)先被測試，又降低了構造的測試樁總復雜度，減少測試代價，可被應用于軟件集成測試領域中.

參考文獻

[1]Briand L C, Yvan L, Wang Yihong. An investigation of graph-based class integration test order strategies[J]. IEEE Trans on Software Engineering, 2003, 29(7): 594-607

[2]Kung D C, Gao J, Hsia P. On regression testing of object-oriented programs[J]. Journal of Systems and Software, 1996, 32(1): 21-40

[3]Briand L C, Feng J, Labiche Y. Experimenting with genetic algorithms to devise optimal integration test orders[J]. Software Engineering with Computational Intelligence, 2003, 73: 204-234

[4]Le T Y，Jéron T，Jézéquel J. Efficient object-oriented integration and regression testing[J]. IEEE Trans on Reliability, 2000, 49(1)：12-25

[5]Tai K C, Daniels F J. Interclass test order for object-oriented software[J]. Object-Oriented Programming, 1999, 12(4): 18-25

[6]Jiang Shujuan, Zhang Yanmei, Li Haiyang, et al. An approach for inter-class integration test order determination based on coupling measures[J]. Chinese Journal of Computers, 2011, 34(6): 1062-1074 (in Chinese)(姜淑娟, 張艷梅, 李海洋, 等. 一種基于耦合度量的類間集成測試序的確定方法[J]. 計算機學報, 2011, 34(6): 1062-1074)

[7]Zhang Yanmei, Jiang Shujuan, Zhang Hongchang. An approach for class integration testing based on dynamic dependency relations[J]. Chinese Journal of Computers, 2011, 34(6): 1075-1089 (in Chinese)(張艷梅, 姜淑娟, 張紅昌. 一種基于動態(tài)依賴關系的類集成測試方法[J]. 計算機學報, 2011, 34(6): 1075-1089)

[8]Munson J C M, Khoshgoftaar T M. The detection of fault-prone programs[J]. IEEE Trans on Software Engineering, 1992, 18(5): 423-433

[9]Zhou Yuming, Hareton L. 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

[10]Pan Weifeng, Li Bing, Ma Yutao, et al. Test case prioritization based on complex software networks[J]. Acta Electronica Sinica, 2012, 40(12): 2456-2465 (in Chinese)(潘偉豐, 李兵, 馬于濤, 等. 基于復雜軟件網(wǎng)絡的回歸測試用例優(yōu)先排序[J]. 電子學報, 2012, 40(12): 2456-2465)

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

[12]Zhou Yuming, Xu Baowe, Hareton L. On the ability of complexity metrics to predict fault-prone classes in object-oriented systems[J]. Journal of Systems and Software, 2010, 83(4): 660-674

[13]Zhou Yuming, Xu Baowe, Hareton L, et al. An in-depth study of the potentially confounding effect of class size in fault prediction[J]. ACM Trans on Software Engineering and Methodology, 2014, 23(1): 1-51

[14]Damien C, Andrea L. Bug propagation and debugging in asymmetric software structures[J]. Physical Review E, 2004, 70(4): 046109

[15]Jing Liu, Lu Jinhu, He Keqing, et al. Characterizing the structural quality of general complex software networks[J]. International Journal of Bifurcation and Chaos, 2008, 18(2): 605-613

[16]Kleinberg J. Authoritative sources in a hyperlinked environment[J]. Journal of the ACM, 1999, 46(5): 604-632

[17]Xie Bing, Zhang Chendong. A test script generating method and tool for OO test model[J]. Journal of Computer Research and Development, 2008, 45(Supp1): 336-340 (in Chinese)(謝冰, 張晨東. 一種基于面向對象測試模型的測試代碼生成方法與工具[J]. 計算機研究與發(fā)展, 2008, 45(增刊): 336-340)

[18]Potanin A, Noble J, Frean M. Scale-free geometry in object-oriented software programs[J]. Communications of the ACM, 2005, 48(5): 99-103

[19]Ramanath S, Krishnan M. Empirical analysis of CK metrics for object-oriented design complexity: Implication for software defects[J]. IEEE Trans on Software Engineering, 2003, 29(4): 297-310

[20]Hector M O, Letha H E, Sherri L M, et al. An empirical validation of object-oriented class complexity to predict error-prone classes in highly iterative, or agile, software: A case study[J]. Journal of Software Maintenance and Evolution: Research and Practice, 2008, 20(3): 171-197

[21]Wang Xiaofan, Li Xiang, Chen Guanrong. Network Science: An Introduction[M]. Beijing: Higher Education Press, 2012: 158-176 (in Chinese)(汪小帆, 李翔, 陳關榮. 網(wǎng)絡科學導論[M]. 北京: 高等教育出版社, 2012, 158-176)

[22]McCabe T. A complexity measure[J]. IEEE Trans on Software Engineering, 1976, 2(4): 308-320

[23]Abdurazik A, Offutt A J. Using coupling-based weights for the class integration and test order problem[J]. The Computer Journal, 2009, 52(5): 557-570

Wang Ying, born in 1987. PhD candidate. Her main research interests include software refactoring, complex networks, software networks and software testing.

Yu Hai, born in 1971. PhD, associate professor. His research interests include software refactoring, software testing, multimedia security and secure chaos-based communications, information hiding, video coding, digital chaotic cipher, network coding, channel coding and applications of complex-network theories.

Zhu Zhiliang, born in 1962. PhD, professor and PhD supervisor. His main research interests include information integrate, complexity software system, network coding and communication security, chaos-baseddigital communications, applications of complex-network theories and cryptography (zzl@mail.neu.edu.cn).

中圖法分類號TP311.5

通信作者：于海(yuhai@mail.neu.edu.cn)

基金項目：國家自然科學基金項目(61374178，61402092)

收稿日期：2014-12-05；修回日期：2015-07-21

This work was supported by the National Natural Science Foundation of China (61374178，61402092).