基于函數(shù)調(diào)用的路徑集成測試模型研究

同濟(jì)大學(xué)軟件學(xué)院 馮國堯

1 引言

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

2 組件的集成

組件的集成是進(jìn)行路徑測試的第一步，根據(jù)函數(shù)間的調(diào)用關(guān)系，結(jié)合判斷循環(huán)將各個組件進(jìn)行結(jié)合。

定義1：函數(shù)組件調(diào)用圖簡稱為調(diào)用圖，常用來描述面向?qū)ο筌浖椒ㄩg的調(diào)用關(guān)系?？梢蕴峁┐罅康姆椒ㄕ{(diào)用和對象類型信息。調(diào)用圖CG=(V,E,v0, vn)中的節(jié)點(diǎn)V表示方法。節(jié)點(diǎn)間的有向邊E表示方法間的調(diào)用關(guān)系,v0屬于V為起始方法或入口方法。vn代表組件集成中唯一的結(jié)束節(jié)點(diǎn)。對于入口和出口不唯一的程序，我們可以采取構(gòu)造虛擬入口，或虛擬出口使得該組件控制流圖具有唯一的入口或出口。調(diào)用圖上從節(jié)點(diǎn)vi到vj的邊表示方法vi中的某個調(diào)用點(diǎn)調(diào)用方法vj.

函數(shù)組件之間[1]的調(diào)用圖是根據(jù)函數(shù)間的條件循環(huán)判斷分支進(jìn)行集成的。四種基本的分支結(jié)構(gòu)包括(1)順序結(jié)構(gòu)；(2)if判斷結(jié)構(gòu)；(3)循環(huán)分支；(4)swit ch分支。

一個程序函數(shù)組件調(diào)用圖就是四種分支的組合形式。它反映了各個函數(shù)之間的調(diào)用關(guān)系圖1就是一個函數(shù)組件的調(diào)用圖。

其中圖1中每一個節(jié)點(diǎn)代表一個函數(shù)組件或者一個判斷循環(huán)分支，節(jié)點(diǎn)與節(jié)點(diǎn)之間的路徑代表方法間的調(diào)用關(guān)系。例如：圖中main()代表主函數(shù)入口，end()代表主函數(shù)出口。E(main,add)代表主函數(shù)main()調(diào)用add()函數(shù)。

圖1 函數(shù)調(diào)用圖

3 組件基路徑集成測試

定義2：函數(shù)組件接口路徑：兩個函數(shù)之間存在某種調(diào)用關(guān)系，假設(shè)在函數(shù)組件控制流圖中ci是cj的前驅(qū)節(jié)點(diǎn)，cj是ci的后繼節(jié)點(diǎn)，那么存在一條從ci到cj的路徑Pij，稱之為組件ci到組件cj的調(diào)用接口路徑。

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

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

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

基路徑[3]集中的每條路徑具有下列特點(diǎn)：

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

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

（3）程序中的所有的，不屬于該基路徑集的路徑都可以由該路徑集中的路徑通過線性運(yùn)算得到?；窂郊械拿恳粭l路徑稱為一條組件執(zhí)行路徑。

組件集成的基路徑集求解需要根據(jù)函數(shù)調(diào)用圖計(jì)算出該調(diào)用圖的環(huán)形復(fù)雜度(此即為基路徑集合中獨(dú)立路徑的個數(shù))。公式如下：

V（G）=E-N+2；

其中E為函數(shù)組件的接口路徑數(shù)；N為節(jié)點(diǎn)的個數(shù)；

結(jié)合次公式可得出圖2中的基路徑獨(dú)立路徑的個數(shù)為8-7+2=3。

然后在根據(jù)函數(shù)調(diào)用圖找出一條基礎(chǔ)獨(dú)立路徑。其原則上盡量經(jīng)過度為2的節(jié)點(diǎn)，和路徑盡可能的達(dá)到最長。

4 函數(shù)組件基路徑無效路徑問題

4.1 無效路徑的判斷

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

我們在選擇路徑后，需要判定被選定的路徑是否是有效的路徑。或者在選擇的同時就要判斷節(jié)點(diǎn)會不會導(dǎo)致無效路徑的產(chǎn)生。這樣才能生成一條可執(zhí)行的路徑來對此設(shè)計(jì)測試用例。

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

定義6 控制依賴：設(shè)Ci、Cj為函數(shù)調(diào)用圖中的兩個節(jié)點(diǎn)，若下列條件滿足，則Ci控制依賴Cj,記為Ci—＞Cj。

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

(2)在P上除了Ci,Cj外的每個節(jié)點(diǎn)Ck,節(jié)點(diǎn)Cj都是它的后必經(jīng)節(jié)點(diǎn)。

設(shè)節(jié)點(diǎn)a,c為程序分支判斷節(jié)點(diǎn)，b為函數(shù)賦值或執(zhí)行的對應(yīng)節(jié)點(diǎn)，f()為一個函數(shù)，若b節(jié)點(diǎn)執(zhí)行f()或?qū)()定義賦值，且c節(jié)點(diǎn)使用了這個賦值，或者重新進(jìn)行定義賦值，則b控制依賴于a,則c函數(shù)控制依賴于b。

4.2 無效路徑的改造

假設(shè)有如下問題，只關(guān)注函數(shù)的調(diào)用關(guān)系，不關(guān)注實(shí)際的業(yè)務(wù)。

(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();其對應(yīng)的函數(shù)調(diào)用圖如圖2所示。

圖2 函數(shù)調(diào)用圖

圖3 改進(jìn)后函數(shù)調(diào)用圖

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

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

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

5 總結(jié)

我們首先要對函數(shù)的控制流分支進(jìn)行插裝分析，對被測的程序進(jìn)行預(yù)處理，生成相應(yīng)的帶有控制邏輯的函數(shù)調(diào)用圖，并獲取全部的函數(shù)調(diào)用路徑，然后結(jié)合基路徑的測試思想生成獨(dú)立路徑集。接著對路徑中的節(jié)點(diǎn)就行函數(shù)依賴和控制依賴分析，找出無效路徑。然后用構(gòu)造無效節(jié)點(diǎn)的副節(jié)點(diǎn)的方法對無效路徑進(jìn)行改造。最終生成可執(zhí)行路徑，找出可執(zhí)行路徑的路徑集合。這樣就生成了基于調(diào)用圖的集成測試模型。

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

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

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

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