基于方法調(diào)用關(guān)系的軟件測試序列生成算法

王曙燕，王超飛，孫家澤

(西安郵電大學(xué) 計(jì)算機(jī)學(xué)院，陜西 西安 710061)

0 引 言

獲取面向?qū)ο筌浖臏y試順序是面向?qū)ο筌浖y試中重要的問題之一[1]?，F(xiàn)有的面向?qū)ο筌浖y試順序生成方法以類間集成測試序列生成為主，目前針對類間集成測試順序生成方法主要有兩類：①基于遺傳算法的類間集成測試順序生成方法[2]；②基于圖論的啟發(fā)式類間集成測試順序生成算法[3]。Briand等[4]利用遺傳算法提出了生成測試順序的方法。該方法僅從類間靜態(tài)依賴關(guān)系考慮，忽略了面向?qū)ο筌浖械亩鄳B(tài)性，未對動態(tài)依賴關(guān)系考慮，導(dǎo)致測試不充分。柴玉梅等[5]對UML模型的順序圖添加了對象約束語言給出了一種測試路徑生成算法。該方法同樣忽略了面向?qū)ο筌浖械亩鄳B(tài)性，僅從UML模型順序圖中的靜態(tài)關(guān)系給出測試序列。陳建勛等[6]分析了對象關(guān)系圖中的類間依賴關(guān)系，運(yùn)用邊刪除規(guī)則去除環(huán)路，通過有向無環(huán)圖的拓?fù)湫蛄薪o出類的測試順序。該方法在解決集成測試序列問題時，也未能考慮軟件系統(tǒng)中的動態(tài)依賴關(guān)系，只抽取了靜態(tài)依賴關(guān)系導(dǎo)致功能路徑的缺失，并且忽略了重要的類和錯誤傳播概率較大的類應(yīng)該盡早被測試的問題。趙玉麗等[7]分析類節(jié)點(diǎn)的影響力和復(fù)雜性，提出一種重要節(jié)點(diǎn)度量方法來給出測試序列。但該方法在給出類間集成測試序列時，采用的節(jié)點(diǎn)重要性度量方法僅從節(jié)點(diǎn)之間的距離關(guān)系來確定影響度，忽略了節(jié)點(diǎn)自身對軟件系統(tǒng)的影響，導(dǎo)致在對類的影響度分析時不夠準(zhǔn)確，并且忽略了軟件系統(tǒng)中類的動態(tài)依賴關(guān)系，造成功能路徑的缺失，導(dǎo)致測試不充分。

軟件系統(tǒng)具有復(fù)雜網(wǎng)絡(luò)的特性，利用復(fù)雜網(wǎng)絡(luò)對軟件整體分析度量的研究已經(jīng)成為軟件工程領(lǐng)域的一個熱門方向[7]。本文結(jié)合類間集成測試序列生成思想，提出一種基于方法動態(tài)調(diào)用關(guān)系的軟件測試序列生成算法。該算法獲取軟件執(zhí)行過程中的方法調(diào)用關(guān)系，并以方法為節(jié)點(diǎn)，方法間調(diào)用關(guān)系為邊，將軌跡構(gòu)造成面向?qū)ο筌浖到y(tǒng)的方法級軟件網(wǎng)絡(luò)，綜合考慮方法的錯誤傳播影響范圍和錯誤傳播概率，給出重要方法重要度值計(jì)算算法。該算法能夠得到有效的軟件測試序列且避免了構(gòu)建測試樁，降低了測試時間，提高了測試效率。

1 方法節(jié)點(diǎn)重要度值評估算法

軟件系統(tǒng)中方法的復(fù)雜性與軟件故障呈現(xiàn)一定正相關(guān)性，在對軟件進(jìn)行更新?lián)Q代中，修改復(fù)雜性高的方法比修改復(fù)雜性低的方法引入錯誤的概率高，因此復(fù)雜方法的錯誤傾向性更高[8,9]。而錯誤在方法間的傳播范圍和對系統(tǒng)的影響力各不相同[10,11]。本文算法綜合了軟件中方法的復(fù)雜性和方法出現(xiàn)錯誤時的影響范圍兩方面因素，借鑒節(jié)點(diǎn)刪除算法[12]和信息量、結(jié)構(gòu)出度[13]思想,提出了一種復(fù)雜網(wǎng)絡(luò)理論的節(jié)點(diǎn)重要度值計(jì)算算法(Method-FNIA)。

1.1 方法級軟件網(wǎng)絡(luò)模型

現(xiàn)有的針對集成測試序列生成的研究大多是基于類之間的依賴關(guān)系形成的對象關(guān)系圖。本文是基于軟件動態(tài)執(zhí)行過程中方法的調(diào)用關(guān)系形成的方法調(diào)用關(guān)系圖。由于代碼只有在運(yùn)行時才表現(xiàn)出軟件故障與失效，這與程序動態(tài)執(zhí)行過程中方法的調(diào)用關(guān)系密切相關(guān)。如何獲取軟件動態(tài)執(zhí)行過程中方法的調(diào)用關(guān)系圖是首要解決問題。傳統(tǒng)方式是以人為添加代碼的方式進(jìn)行“插樁”，對于代碼量過大的程序，工作量巨大，修改不便，不夠靈活。鑒于傳統(tǒng)插樁方法的這些局限，本文采用了應(yīng)用操作簡單、實(shí)用的面向切面的框架AspectJ，來獲取軟件方法動態(tài)調(diào)用關(guān)系圖。通過AspectJ獲取到的方法抽象為節(jié)點(diǎn)集合V={v1,v2,v3,…,vn}，方法間的調(diào)用關(guān)系抽象為邊集合E={vi,vj∈V}，將軟件動態(tài)方法調(diào)用關(guān)系圖表示為G(V,E),其中n為節(jié)點(diǎn)個數(shù)。圖1是一個簡單程序的方法調(diào)用關(guān)系圖。

圖1 程序方法調(diào)用關(guān)系

1.2 方法調(diào)用關(guān)系圖約簡方法

由于有些程序規(guī)模大，方法調(diào)用圖可能會產(chǎn)生很多冗余的節(jié)點(diǎn)和邊，比如A方法被B方法多次調(diào)用，導(dǎo)致方法A與方法B之間產(chǎn)生許多重邊。為此本文采用了子樹約簡算法來對類軌跡圖進(jìn)行約簡，將冗余的邊或節(jié)點(diǎn)去除掉，只留一個相同的邊，并在這條邊上記錄下相同邊的調(diào)用次數(shù)，作為邊的權(quán)值，以此來獲取有效的加權(quán)方法調(diào)用關(guān)系圖，具體如圖2所示，節(jié)點(diǎn)代表方法，邊代表方法間的調(diào)用關(guān)系。

圖2 子樹約簡法

1.3 重要方法節(jié)點(diǎn)優(yōu)先測試的關(guān)鍵因素

一個復(fù)雜的方法，或者由于出錯對系統(tǒng)造成的破壞性大的方法應(yīng)該被優(yōu)先測試，即重要方法節(jié)點(diǎn)。因此，在分析影響重要方法節(jié)點(diǎn)的關(guān)鍵因素時，本文主要從方法的自身、不同方法之間對系統(tǒng)造成的影響，即方法節(jié)點(diǎn)影響度，以及重要方法節(jié)點(diǎn)自身錯誤傳播能力，即節(jié)點(diǎn)錯誤傳播率兩個方面來考慮。

1.3.1 方法節(jié)點(diǎn)影響度

軟件動態(tài)方法調(diào)用關(guān)系圖是一個有向圖，每個節(jié)點(diǎn)對整個軟件動態(tài)執(zhí)行圖的影響并不僅僅局限于其鄰居節(jié)點(diǎn)，而會是一種連鎖式的影響[12]。為了能夠精確地反映節(jié)點(diǎn)出錯后對系統(tǒng)造成的影響,本文引入方法節(jié)點(diǎn)影響度的概念。對方法調(diào)用關(guān)系圖而言，方法節(jié)點(diǎn)的影響度越大，即通過該節(jié)點(diǎn)傳遞信息能夠到達(dá)軟件動態(tài)執(zhí)圖中更多的節(jié)點(diǎn)，一旦該節(jié)點(diǎn)出現(xiàn)故障，其造成的影響要遠(yuǎn)大于影響度小的節(jié)點(diǎn)給系統(tǒng)造成的影響，這樣的方法應(yīng)該優(yōu)先被重點(diǎn)測試[14]。

對方法節(jié)點(diǎn)影響度度量主要從直接和間接影響兩方面考慮：直接影響為被刪除的節(jié)點(diǎn)不能分別再與剩余節(jié)點(diǎn)相互連通；間接影響為剩余節(jié)點(diǎn)中部分節(jié)點(diǎn)之間的路徑，可能由于被刪節(jié)點(diǎn)原來所起到的橋梁作用喪失而不再連通[12]。直接影響與間接影響之和稱為方法節(jié)點(diǎn)影響度，如式(1)所示

TOIi=DOIi+IDOIi

(1)

式中：TOIi為方法節(jié)點(diǎn)i影響度，IDOIi為方法節(jié)點(diǎn)i的間接影響，DOIi為方法節(jié)點(diǎn)i的直接影響。

1.3.2 方法節(jié)點(diǎn)錯誤傳播率

方法的復(fù)雜性研究表明方法的復(fù)雜性與面向?qū)ο筌浖椒ǖ腻e誤傾向性具有密切關(guān)系[14]。很多的復(fù)雜性度量指標(biāo)忽略了方法的錯誤傳播能力和結(jié)構(gòu)復(fù)雜性。為了更準(zhǔn)確的度量方法節(jié)點(diǎn)復(fù)雜性，本文基于結(jié)構(gòu)度與信息量，引入方法節(jié)點(diǎn)錯誤傳播率。對方法的調(diào)用關(guān)系圖而言，方法節(jié)點(diǎn)錯誤傳播率越高，該節(jié)點(diǎn)的復(fù)雜性就越高，錯誤傳播的能力就越強(qiáng)；將錯誤間接傳遞到該方法自身的傾向性就越大，其測試的優(yōu)先級就越高[7]。

對方法節(jié)點(diǎn)錯誤傳播率的度量主要從結(jié)構(gòu)出度占比和信息量權(quán)重兩方面考慮：

(1)結(jié)構(gòu)出度占比為方法調(diào)用關(guān)系圖中節(jié)點(diǎn)的結(jié)構(gòu)出度在該節(jié)點(diǎn)結(jié)構(gòu)度中的占有率，如式(2)所示

(2)

(2)信息量權(quán)重為方法節(jié)點(diǎn)的信息量在整個方法調(diào)用關(guān)系圖信息總量中的占有率，如式(3)所示

(3)

1.4 Method-FNIA算法描述

通過分析發(fā)現(xiàn)，方法節(jié)點(diǎn)的影響度與方法節(jié)點(diǎn)的錯誤傳播率與面向?qū)ο筌浖椒ǖ腻e誤傾向具有密切的聯(lián)系。因此，將兩者結(jié)合得到方法節(jié)點(diǎn)的重要度值評計(jì)算方法，如式(4)所示

(4)

這里的α、β、λ為可變參數(shù)分別表示影響度、結(jié)構(gòu)出度占比和節(jié)點(diǎn)信息量權(quán)重且滿足α+β+λ=1。在確定指標(biāo)的權(quán)重參數(shù)時，不同軟件得到的拓?fù)浣Y(jié)構(gòu)不同，它們所表達(dá)的側(cè)重點(diǎn)也不同，對應(yīng)的參數(shù)取值也不同。在軟件測試過程中，測試用例會產(chǎn)生差異或大或小的類調(diào)用關(guān)系執(zhí)行圖，它們之間的權(quán)重大小很難統(tǒng)一確定。因此，本文采用信息量權(quán)重法自動確定參數(shù)大小。

根據(jù)上述理論Method-FNIA，(Method-FirstNodeImportance)算法表述如下：

算法1：Method-FNIA

輸入：約簡后的有向加權(quán)軟件網(wǎng)絡(luò)鄰接矩陣A；

輸出：方法節(jié)點(diǎn)測試重要性結(jié)果。

步驟1 計(jì)算方法節(jié)點(diǎn)影響度。通過鄰接矩陣A，求取A的距離矩陣D。

(1)將節(jié)點(diǎn)i刪除后，通過距離矩陣D，計(jì)算與節(jié)點(diǎn)i直接相鄰的節(jié)點(diǎn)j的距離dij，對節(jié)點(diǎn)i的所有dij求和得到節(jié)點(diǎn)i的直接影響DOIi；

步驟2 計(jì)算方法節(jié)點(diǎn)錯誤傳播率，錯誤傳播率包括結(jié)構(gòu)出度占比和信息量權(quán)重兩方面。首先通過鄰接矩陣A，得到節(jié)點(diǎn)i的結(jié)構(gòu)出度與其結(jié)構(gòu)度，求得節(jié)點(diǎn)i的結(jié)構(gòu)出度占比；隨后，通過權(quán)值求得節(jié)點(diǎn)i的信息量以及整個網(wǎng)絡(luò)的總信息量，最終計(jì)算出節(jié)點(diǎn)i的信息量權(quán)重。

步驟3 確定可變參數(shù)α、β、λ。根據(jù)步驟1與步驟2得到的數(shù)據(jù)，計(jì)算得到信息量權(quán)重法所需的變異系數(shù)CV,然后對得到的數(shù)據(jù)進(jìn)行歸一化處理，得到可變參數(shù)值。

步驟4 根據(jù)式(4)計(jì)算得到重要方法節(jié)點(diǎn)指標(biāo)結(jié)果。

2 軟件測試序列生成方法與實(shí)例分析

2.1 軟件測試序列生成方法

通過前文分析，在軟件系統(tǒng)中錯誤傾向性較高，錯誤傳播影響范圍大，傳播率高的類，對軟件的穩(wěn)定性和安全性起著決定性作用[11,15]。因此本文基于重要方法節(jié)點(diǎn)優(yōu)先測試因素，給出一種基于方法動態(tài)調(diào)用關(guān)系的軟件測試序列生成方法。該方法生成軟件測試序列的步驟如下：①通過AspectJ框架，運(yùn)行源碼來獲取調(diào)用關(guān)系圖；②采用Subtree算法對調(diào)用關(guān)系圖進(jìn)行約簡，得到約簡后的加權(quán)調(diào)用關(guān)系圖；③運(yùn)用本文算法Method-FNIA，計(jì)算方法節(jié)點(diǎn)重要度值。影響度和錯誤傳播率，通過信息量權(quán)重法確定兩者的權(quán)重；④對方法節(jié)點(diǎn)的重要度值排序，獲取軟件測試序列。

具體流程如圖3所示。

2.2 實(shí)例分析

Siemens程序集經(jīng)常被用作實(shí)驗(yàn)對象，并且程序差異較大，可以從不同規(guī)模、復(fù)雜性等角度來共同驗(yàn)證測試方法。本節(jié)以Siemens實(shí)驗(yàn)平臺程序集合中print Tokens源程序P為例，該程序?yàn)樵~法分析器的源程序，詳細(xì)介紹Method-FNIA算法的實(shí)現(xiàn)步驟，并以此說明該算法的有效性。

根據(jù)本文方法，源程序P的方法調(diào)用關(guān)系圖G如圖4所示。其中1號標(biāo)簽為起始節(jié)點(diǎn)，38號為終止節(jié)點(diǎn)。

圖3 測試序列生成方法流程

通過Method-FNIA算法得到重要方法節(jié)點(diǎn)指標(biāo)結(jié)果后，得到軟件測試序列，如圖6所示。

3 實(shí) 驗(yàn)

3.1 實(shí)驗(yàn)對象

為驗(yàn)證該方法的有效性，本文選用實(shí)驗(yàn)平臺程序集合Siemens中的4個程序，選這4個程序的原因：軟件測試實(shí)證研究中，Siemens程序集經(jīng)常被用作實(shí)驗(yàn)對象，并且程序差異較大，可以從不同規(guī)模、復(fù)雜性等角度來共同驗(yàn)證測試方法，具體介紹見表1。

圖4 方法調(diào)用關(guān)系圖G

圖5 print tokens重要性結(jié)果

圖6 print tokens方法測試序列

3.2 實(shí)驗(yàn)結(jié)果與分析

利用本文提出的Method-FNIA算法計(jì)算4種程序的方法節(jié)點(diǎn)重要性，排序后結(jié)果如圖7所示。由圖7分析得到4種程序中只有少數(shù)節(jié)點(diǎn)的重要度值非常高，以REPLACE為例，節(jié)點(diǎn)的重要值分布在[0.18673,2.20689]之間，重要值超過1.2038的節(jié)點(diǎn)只有4個，而在其以下的有24，約占節(jié)點(diǎn)總數(shù)的85%。該數(shù)據(jù)表明，軟件系統(tǒng)中只有少數(shù)節(jié)點(diǎn)具有錯誤傳播影響大、錯誤傳播率高的特性，這些節(jié)點(diǎn)所產(chǎn)生的錯誤嚴(yán)重性將遠(yuǎn)高于其它節(jié)點(diǎn)所產(chǎn)生的錯誤，應(yīng)盡早優(yōu)先被測試。

表1 測試程序信息

分析表2、表3可知，4種程序中節(jié)點(diǎn)重要度值排名前4的方法節(jié)點(diǎn)均具很高的被調(diào)用次數(shù)，與其它節(jié)點(diǎn)具有復(fù)雜的調(diào)用關(guān)系，并且節(jié)點(diǎn)自身的結(jié)構(gòu)度很高，結(jié)構(gòu)復(fù)雜性較高，同時這些節(jié)點(diǎn)也具有較高的直接和間接影響，節(jié)點(diǎn)缺失后對整個軟件系統(tǒng)造成的影響較高，進(jìn)一步驗(yàn)證了重要度值越高的節(jié)點(diǎn)具有較高的錯誤影響力和錯誤傳播率，應(yīng)優(yōu)先被測試。

圖7 程序節(jié)點(diǎn)重要值

表2 方法節(jié)點(diǎn)各項(xiàng)統(tǒng)計(jì)指標(biāo)

表3 節(jié)點(diǎn)重要度排名前4節(jié)點(diǎn)各項(xiàng)指標(biāo)

綜上，本文提出的針對節(jié)點(diǎn)重要度值計(jì)算方法(Method-FNIA)正確有效，排序結(jié)果也可應(yīng)用到軟件測試序列生成方法中。

3.3 軟件測試序列結(jié)果對比分析

對得到的節(jié)點(diǎn)重要度值進(jìn)行排序，求出4種程序的測試序列，見表4。然后采用文獻(xiàn)[7]提出的方法，得到4種程序的類間集成測試序列，并和本文方法進(jìn)行對比分析，實(shí)驗(yàn)結(jié)果見表5。

表4 本文算法得出的測試序列

表5 對比實(shí)驗(yàn)結(jié)果

表5中Nump表示當(dāng)測試完節(jié)點(diǎn)總數(shù)50%的時，測試序列排名前30%的節(jié)點(diǎn)已經(jīng)被測試的數(shù)目，Numm表示文獻(xiàn)[7]中Nump個類節(jié)點(diǎn)含有本文測試序列排名前50%方法節(jié)點(diǎn)的數(shù)目，Numn表示本文測試序列排名前50%方法的數(shù)目，Nums表示文獻(xiàn)[7]中Nump個類中包含的方法總數(shù),Timein表示構(gòu)造測全部試樁所花費(fèi)的時間,Timec表示生成測試序列所花費(fèi)的時間，Timep表示本文方法在時間上與文獻(xiàn)[7]的降低率。通過分析表5中4組實(shí)驗(yàn)的Nump、Numm、Numn、Nums這4項(xiàng)數(shù)據(jù)，4種程序在文獻(xiàn)[7]中的方法節(jié)點(diǎn)數(shù)目Numm均小于本文中的方法節(jié)點(diǎn)數(shù)目Numn，并且文獻(xiàn)[7]中的Numm也均小于自身的Nums，通過跟蹤源碼發(fā)現(xiàn)導(dǎo)致這種差距的來源有兩方面：文獻(xiàn)[7]中排名低于30%的類中具有錯誤傳播范圍廣、錯誤傳播率高的方法，但由于類的排名靠后，導(dǎo)致方法靠后；此外，有些依賴關(guān)系只在代碼運(yùn)行中才會表現(xiàn)出來，由于文獻(xiàn)[7]的測試序列僅從類間靜態(tài)依賴關(guān)系考慮，忽略了動態(tài)依賴關(guān)系，導(dǎo)致測試序列不夠準(zhǔn)確，本文方法是基于軟件動態(tài)執(zhí)行中的方法間調(diào)用關(guān)系生成的測試序列，確保了動態(tài)依賴關(guān)系。以上數(shù)據(jù)說明本文提出的方法能夠很好地解決面向?qū)ο筌浖杏捎诙鄳B(tài)性所產(chǎn)生的動態(tài)依賴關(guān)系問題，比文獻(xiàn)[7]提出的方法所產(chǎn)生的測試序列更為充分、準(zhǔn)確。此外，4組實(shí)驗(yàn)利用本文生成測試序列在不需要構(gòu)造測試樁的前提下花費(fèi)的時間Timec值均小于文獻(xiàn)[7]中的結(jié)果，且從Timep分析得到隨著程序的規(guī)模變大這種優(yōu)勢也隨之增大，因此本文從時間效率上優(yōu)于文獻(xiàn)[7]。綜上，本文提出的方法能夠生成有效的軟件測試序列。

4 結(jié)束語

本文利用復(fù)雜網(wǎng)絡(luò)理論將軟件方法動態(tài)調(diào)用關(guān)系抽象為網(wǎng)絡(luò)，根據(jù)方法間錯誤傳播影響范圍及方法自身的錯誤傳播能力，給出方法節(jié)點(diǎn)的重要度衡量指標(biāo)，并借鑒類間集成測試序列生成思想，設(shè)計(jì)了一種通過分析軟件動態(tài)執(zhí)行過程中方法調(diào)用關(guān)系來生成軟件測試序列的方法。該方法得到的軟件測試序列能夠保證重要節(jié)點(diǎn)優(yōu)先被測試且避免構(gòu)造測試樁，測試序列生成時間平均降低了33.45%，并且這種優(yōu)勢隨著軟件規(guī)模的擴(kuò)大而增大，又保證了軟件動態(tài)依賴關(guān)系和方法自身重要性的因素。