基于函數調用的路徑集成測試模型研究

同濟大學軟件學院 馮國堯

1 引言

軟件測試是軟件開發工程中的重要階段，是保證軟件質量，提高 軟件可靠性的重要保障。路徑覆蓋測試是白盒測試的一種方法，即使是很小的程序，包含的邏輯路徑數量也非常龐大，所以在大型程序中進行完全路徑測試幾乎是不可能完成的，所以本文提出以組件為單位的集成測試，將路徑測試的級別提升到函數組件的級別上，同時找出一組基路徑集進行測試，其他路徑都可以由這組路徑集線性表示。故而減少了測試的復雜度。

2 組件的集成

組件的集成是進行路徑測試的第一步，根據函數間的調用關系，結合判斷循環將各個組件進行結合。

定義1：函數組件調用圖簡稱為調用圖，常用來描述面向對象軟件方法間的調用關系。可以提供大量的方法調用和對象類型信息。調用圖CG=(V,E,v0, vn)中的節點V表示方法。節點間的有向邊E表示方法間的調用關系,v0屬于V為起始方法或入口方法。vn代表組件集成中唯一的結束節點。對于入口和出口不唯一的程序，我們可以采取構造虛擬入口，或虛擬出口使得該組件控制流圖具有唯一的入口或出口。調用圖上從節點vi到vj的邊表示方法vi中的某個調用點調用方法vj.

函數組件之間[1]的調用圖是根據函數間的條件循環判斷分支進行集成的。四種基本的分支結構包括(1)順序結構；(2)if判斷結構；(3)循環分支；(4)swit ch分支。

一個程序函數組件調用圖就是四種分支的組合形式。它反映了各個函數之間的調用關系圖1就是一個函數組件的調用圖。

其中圖1中每一個節點代表一個函數組件或者一個判斷循環分支，節點與節點之間的路徑代表方法間的調用關系。例如：圖中main()代表主函數入口，end()代表主函數出口。E(main,add)代表主函數main()調用add()函數。

圖1 函數調用圖

3 組件基路徑集成測試

定義2：函數組件接口路徑：兩個函數之間存在某種調用關系，假設在函數組件控制流圖中ci是cj的前驅節點，cj是ci的后繼節點，那么存在一條從ci到cj的路徑Pij，稱之為組件ci到組件cj的調用接口路徑。

定義3：函數組件執行路徑：在組件控制流圖中存在一條從c0（開始節點）開始到cn（結束節點）結束的路徑，中間經過若干接口路徑，如P0,n=（c0-＞ci-＞cj-＞cm-＞cn）(i,j,m＜n)，那么稱這條路徑為函數組件集成的執行路徑。由此可見組件執行路徑是從源節點開始到匯結點結束，中間經過若干調用接口路徑的一條完整路徑。

定義4：獨立路徑[2]：是一條組件執行路徑，但是至少包含一條在其他路徑中從未包含過的邊的路徑。

雖然我們把程序系統的代碼分析粒度從語句擴展到了函數組件的級別，但是在一個龐大的系統當中，函數之間的調用還是比較復雜，從而進行集成測試也需要設計巨大的測試用例。因此，我們可以把每一條組件的執行路徑看成向量空間的一個向量，我們從中找出一組路徑，而其他路徑可以由這組路徑線性表示出來。那么我們稱這組路徑為函數集成測試的基路徑集。

基路徑[3]集中的每條路徑具有下列特點：

（1）每一條路徑都是一條獨立路徑，即每一條路徑中都包含至少一條不包含在其它路徑中的邊；

（2）程序中所有的邊都被該基本路徑集的路徑訪問過；

（3）程序中的所有的，不屬于該基路徑集的路徑都可以由該路徑集中的路徑通過線性運算得到。基路徑集中的每一條路徑稱為一條組件執行路徑。

組件集成的基路徑集求解需要根據函數調用圖計算出該調用圖的環形復雜度(此即為基路徑集合中獨立路徑的個數)。公式如下：

V（G）=E-N+2；

其中E為函數組件的接口路徑數；N為節點的個數；

結合次公式可得出圖2中的基路徑獨立路徑的個數為8-7+2=3。

然后在根據函數調用圖找出一條基礎獨立路徑。其原則上盡量經過度為2的節點，和路徑盡可能的達到最長。

4 函數組件基路徑無效路徑問題

4.1 無效路徑的判斷

無效路徑[4]是指無論在什么樣的情況下，沒有任何輸入能完整的執行這條路徑。導致函數調用圖中路徑無效的一個主要原因是函數條件分支語句的相關性，即函數語句F1的值能直接決定其后續函數F2分支語句的取值結果或函數分支F2的值直接由該分支入口前的函數語句所確定。

我們在選擇路徑后，需要判定被選定的路徑是否是有效的路徑。或者在選擇的同時就要判斷節點會不會導致無效路徑的產生。這樣才能生成一條可執行的路徑來對此設計測試用例。

定義5 函數依賴：在被測試的函數調用圖當中，如果存在函數節點Ci與Cj，從節點Ci到節點Cj存在路徑Pij，且節點Ci對特定的函數f()或者變量B進行了定義并初始化，則存在以下情況：如果Cj節點引用了變量B或者函數f()或者對變量B和函數重新進行了賦值或計算，并且在此路徑上的其他節點沒有對變量和函數重新定義或賦值，那么節點Cj函數依賴于節點Ci。

定義6 控制依賴：設Ci、Cj為函數調用圖中的兩個節點，若下列條件滿足，則Ci控制依賴Cj,記為Ci—＞Cj。

(1)從Ci到Cj之間存在一條可執行路徑P;

(2)在P上除了Ci,Cj外的每個節點Ck,節點Cj都是它的后必經節點。

設節點a,c為程序分支判斷節點，b為函數賦值或執行的對應節點，f()為一個函數，若b節點執行f()或對f()定義賦值，且c節點使用了這個賦值，或者重新進行定義賦值，則b控制依賴于a,則c函數控制依賴于b。

4.2 無效路徑的改造

假設有如下問題，只關注函數的調用關系，不關注實際的業務。

(1) if(*)

(2) c=add(a,b);

el se

(3) c=min(a,b);

(4) if(c==add(a,b)){

(5) if(**){

(6) s1();}

el se{

(7) s2(); } }

el se

(8)makeIt();其對應的函數調用圖如圖2所示。

圖2 函數調用圖

圖3 改進后函數調用圖

根據組件函數基路徑測試可得出路徑集有四條獨立路徑：{1-＞2-＞4-＞5-＞6-＞End,1-＞3-＞4-＞5-＞6-＞End,1-＞2-＞4-＞8-＞End, 1-＞2-＞4-＞5-＞7-＞End}

由于節點4函數控制依賴于節點2和節點3，存在1-＞3-＞4-＞5＞6-＞End這樣的路徑是不可達的。如果簡單的將不可達路徑從路徑集中簡單的去除，由于基路徑的不唯一性，會造成有些可達邊沒有被包含到基路徑集中。仔細分析，可以知道函數節點4的判定與節點2和節點3存在函數依賴關系。所以需要將節點4分割成兩個節點為4和4’，4’為4的相反判定即4的el se分支。那么就排除了函數不可達路徑。改進后的函數調用圖如圖3所示。

由此改進后的函數調用圖可得出基路徑中獨立路徑的條數為4條，分別是：1-＞2-＞4-＞5-＞6-＞end,1-＞3-＞4’-＞8-＞end,1-＞2-＞4-＞8-＞end,1-＞2-＞5-＞7-＞end.這四條路徑全部是可達的路徑。不存在無效路徑的問題，該方法不僅適用于函數調用圖的基路徑無效路徑的判定，而且適用于單元程序圖的基路徑判定。

5 總結

我們首先要對函數的控制流分支進行插裝分析，對被測的程序進行預處理，生成相應的帶有控制邏輯的函數調用圖，并獲取全部的函數調用路徑，然后結合基路徑的測試思想生成獨立路徑集。接著對路徑中的節點就行函數依賴和控制依賴分析，找出無效路徑。然后用構造無效節點的副節點的方法對無效路徑進行改造。最終生成可執行路徑，找出可執行路徑的路徑集合。這樣就生成了基于調用圖的集成測試模型。

[1]崔霞,高建華.一種新的測試集簡化的測試覆蓋準則[J].計算機科學,2009,36(1):244-246.

[2]倫立軍,孔慶彥,孫鵬飛,宋益波.一種軟件體系結構級路徑覆蓋方法[J].小型微型計算機系統,2010,11(11):2166-2168.

[3]安金霞,王國慶,李樹芳,等.基于多維度覆蓋率的軟件測試動態評價方法[J].軟件學報,2010,21(9):2135-2147.

[4]杜慶峰.高級軟件測試技術[M].北京:清華大學出版社,2011:108-112.