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

1 引言

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

2 組件的集成

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

定義1：函數(shù)組件調(diào)用圖簡(jiǎn)稱為調(diào)用圖，常用來(lái)描述面向?qū)ο筌浖椒ㄩg的調(diào)用關(guān)系?？梢蕴峁┐罅康姆椒ㄕ{(diào)用和對(duì)象類(lèi)型信息。調(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)。對(duì)于入口和出口不唯一的程序，我們可以采取構(gòu)造虛擬入口，或虛擬出口使得該組件控制流圖具有唯一的入口或出口。調(diào)用圖上從節(jié)點(diǎn)vi到vj的邊表示方法vi中的某個(gè)調(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分支。

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

其中圖1中每一個(gè)節(jié)點(diǎn)代表一個(gè)函數(shù)組件或者一個(gè)判斷循環(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 組件基路徑集成測(cè)試

定義2：函數(shù)組件接口路徑：兩個(gè)函數(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（開(kāi)始節(jié)點(diǎn)）開(kāi)始到cn（結(jié)束節(jié)點(diǎn)）結(jié)束的路徑，中間經(jīng)過(guò)若干接口路徑，如P0,n=（c0-＞ci-＞cj-＞cm-＞cn）(i,j,m＜n)，那么稱這條路徑為函數(shù)組件集成的執(zhí)行路徑。由此可見(jiàn)組件執(zhí)行路徑是從源節(jié)點(diǎn)開(kāi)始到匯結(jié)點(diǎn)結(jié)束，中間經(jīng)過(guò)若干調(diào)用接口路徑的一條完整路徑。

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

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

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

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

（2）程序中所有的邊都被該基本路徑集的路徑訪問(wèn)過(guò)；

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

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

V（G）=E-N+2；

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

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

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

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

4.1 無(wú)效路徑的判斷

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

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

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

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

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

(2)在P上除了Ci,Cj外的每個(gè)節(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í)行的對(duì)應(yīng)節(jié)點(diǎn)，f()為一個(gè)函數(shù)，若b節(jié)點(diǎn)執(zhí)行f()或?qū)()定義賦值，且c節(jié)點(diǎn)使用了這個(gè)賦值，或者重新進(jìn)行定義賦值，則b控制依賴于a,則c函數(shù)控制依賴于b。

4.2 無(wú)效路徑的改造

假設(shè)有如下問(wèn)題，只關(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();其對(duì)應(yīng)的函數(shù)調(diào)用圖如圖2所示。

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

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

根據(jù)組件函數(shù)基路徑測(cè)試可得出路徑集有四條獨(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á)的。如果簡(jiǎn)單的將不可達(dá)路徑從路徑集中簡(jiǎn)單的去除，由于基路徑的不唯一性，會(huì)造成有些可達(dá)邊沒(méi)有被包含到基路徑集中。仔細(xì)分析，可以知道函數(shù)節(jié)點(diǎn)4的判定與節(jié)點(diǎn)2和節(jié)點(diǎn)3存在函數(shù)依賴關(guān)系。所以需要將節(jié)點(diǎn)4分割成兩個(gè)節(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á)的路徑。不存在無(wú)效路徑的問(wèn)題，該方法不僅適用于函數(shù)調(diào)用圖的基路徑無(wú)效路徑的判定，而且適用于單元程序圖的基路徑判定。

5 總結(jié)

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

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

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

[3]安金霞,王國(guó)慶,李樹(shù)芳,等.基于多維度覆蓋率的軟件測(cè)試動(dòng)態(tài)評(píng)價(jià)方法[J].軟件學(xué)報(bào),2010,21(9):2135-2147.

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