基于方法調用關系的軟件測試序列生成算法

王曙燕，王超飛，孫家澤

(西安郵電大學 計算機學院，陜西 西安 710061)

0 引 言

獲取面向對象軟件的測試順序是面向對象軟件測試中重要的問題之一[1]。現有的面向對象軟件測試順序生成方法以類間集成測試序列生成為主，目前針對類間集成測試順序生成方法主要有兩類：①基于遺傳算法的類間集成測試順序生成方法[2]；②基于圖論的啟發式類間集成測試順序生成算法[3]。Briand等[4]利用遺傳算法提出了生成測試順序的方法。該方法僅從類間靜態依賴關系考慮，忽略了面向對象軟件中的多態性，未對動態依賴關系考慮，導致測試不充分。柴玉梅等[5]對UML模型的順序圖添加了對象約束語言給出了一種測試路徑生成算法。該方法同樣忽略了面向對象軟件中的多態性，僅從UML模型順序圖中的靜態關系給出測試序列。陳建勛等[6]分析了對象關系圖中的類間依賴關系，運用邊刪除規則去除環路，通過有向無環圖的拓撲序列給出類的測試順序。該方法在解決集成測試序列問題時，也未能考慮軟件系統中的動態依賴關系，只抽取了靜態依賴關系導致功能路徑的缺失，并且忽略了重要的類和錯誤傳播概率較大的類應該盡早被測試的問題。趙玉麗等[7]分析類節點的影響力和復雜性，提出一種重要節點度量方法來給出測試序列。但該方法在給出類間集成測試序列時，采用的節點重要性度量方法僅從節點之間的距離關系來確定影響度，忽略了節點自身對軟件系統的影響，導致在對類的影響度分析時不夠準確，并且忽略了軟件系統中類的動態依賴關系，造成功能路徑的缺失，導致測試不充分。

軟件系統具有復雜網絡的特性，利用復雜網絡對軟件整體分析度量的研究已經成為軟件工程領域的一個熱門方向[7]。本文結合類間集成測試序列生成思想，提出一種基于方法動態調用關系的軟件測試序列生成算法。該算法獲取軟件執行過程中的方法調用關系，并以方法為節點，方法間調用關系為邊，將軌跡構造成面向對象軟件系統的方法級軟件網絡，綜合考慮方法的錯誤傳播影響范圍和錯誤傳播概率，給出重要方法重要度值計算算法。該算法能夠得到有效的軟件測試序列且避免了構建測試樁，降低了測試時間，提高了測試效率。

1 方法節點重要度值評估算法

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

1.1 方法級軟件網絡模型

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

圖1 程序方法調用關系

1.2 方法調用關系圖約簡方法

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

圖2 子樹約簡法

1.3 重要方法節點優先測試的關鍵因素

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

1.3.1 方法節點影響度

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

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

TOIi=DOIi+IDOIi

(1)

式中：TOIi為方法節點i影響度，IDOIi為方法節點i的間接影響，DOIi為方法節點i的直接影響。

1.3.2 方法節點錯誤傳播率

方法的復雜性研究表明方法的復雜性與面向對象軟件方法的錯誤傾向性具有密切關系[14]。很多的復雜性度量指標忽略了方法的錯誤傳播能力和結構復雜性。為了更準確的度量方法節點復雜性，本文基于結構度與信息量，引入方法節點錯誤傳播率。對方法的調用關系圖而言，方法節點錯誤傳播率越高，該節點的復雜性就越高，錯誤傳播的能力就越強；將錯誤間接傳遞到該方法自身的傾向性就越大，其測試的優先級就越高[7]。

對方法節點錯誤傳播率的度量主要從結構出度占比和信息量權重兩方面考慮：

(1)結構出度占比為方法調用關系圖中節點的結構出度在該節點結構度中的占有率，如式(2)所示

(2)

(2)信息量權重為方法節點的信息量在整個方法調用關系圖信息總量中的占有率，如式(3)所示

(3)

1.4 Method-FNIA算法描述

通過分析發現，方法節點的影響度與方法節點的錯誤傳播率與面向對象軟件方法的錯誤傾向具有密切的聯系。因此，將兩者結合得到方法節點的重要度值評計算方法，如式(4)所示

(4)

這里的α、β、λ為可變參數分別表示影響度、結構出度占比和節點信息量權重且滿足α+β+λ=1。在確定指標的權重參數時，不同軟件得到的拓撲結構不同，它們所表達的側重點也不同，對應的參數取值也不同。在軟件測試過程中，測試用例會產生差異或大或小的類調用關系執行圖，它們之間的權重大小很難統一確定。因此，本文采用信息量權重法自動確定參數大小。

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

算法1：Method-FNIA

輸入：約簡后的有向加權軟件網絡鄰接矩陣A；

輸出：方法節點測試重要性結果。

步驟1 計算方法節點影響度。通過鄰接矩陣A，求取A的距離矩陣D。

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

步驟2 計算方法節點錯誤傳播率，錯誤傳播率包括結構出度占比和信息量權重兩方面。首先通過鄰接矩陣A，得到節點i的結構出度與其結構度，求得節點i的結構出度占比；隨后，通過權值求得節點i的信息量以及整個網絡的總信息量，最終計算出節點i的信息量權重。

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

步驟4 根據式(4)計算得到重要方法節點指標結果。

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

2.1 軟件測試序列生成方法

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

具體流程如圖3所示。

2.2 實例分析

Siemens程序集經常被用作實驗對象，并且程序差異較大，可以從不同規模、復雜性等角度來共同驗證測試方法。本節以Siemens實驗平臺程序集合中print Tokens源程序P為例，該程序為詞法分析器的源程序，詳細介紹Method-FNIA算法的實現步驟，并以此說明該算法的有效性。

根據本文方法，源程序P的方法調用關系圖G如圖4所示。其中1號標簽為起始節點，38號為終止節點。

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

通過Method-FNIA算法得到重要方法節點指標結果后，得到軟件測試序列，如圖6所示。

3 實 驗

3.1 實驗對象

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

圖4 方法調用關系圖G

圖5 print tokens重要性結果

圖6 print tokens方法測試序列

3.2 實驗結果與分析

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

表1 測試程序信息

分析表2、表3可知，4種程序中節點重要度值排名前4的方法節點均具很高的被調用次數，與其它節點具有復雜的調用關系，并且節點自身的結構度很高，結構復雜性較高，同時這些節點也具有較高的直接和間接影響，節點缺失后對整個軟件系統造成的影響較高，進一步驗證了重要度值越高的節點具有較高的錯誤影響力和錯誤傳播率，應優先被測試。

圖7 程序節點重要值

表2 方法節點各項統計指標

表3 節點重要度排名前4節點各項指標

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

3.3 軟件測試序列結果對比分析

對得到的節點重要度值進行排序，求出4種程序的測試序列，見表4。然后采用文獻[7]提出的方法，得到4種程序的類間集成測試序列，并和本文方法進行對比分析，實驗結果見表5。

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

表5 對比實驗結果

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

4 結束語

本文利用復雜網絡理論將軟件方法動態調用關系抽象為網絡，根據方法間錯誤傳播影響范圍及方法自身的錯誤傳播能力，給出方法節點的重要度衡量指標，并借鑒類間集成測試序列生成思想，設計了一種通過分析軟件動態執行過程中方法調用關系來生成軟件測試序列的方法。該方法得到的軟件測試序列能夠保證重要節點優先被測試且避免構造測試樁，測試序列生成時間平均降低了33.45%，并且這種優勢隨著軟件規模的擴大而增大，又保證了軟件動態依賴關系和方法自身重要性的因素。