徐爛　陳磊

摘要：在軟件測試中，各種基本路徑自動(dòng)生成算法已經(jīng)在單元測試中得到充分運(yùn)用，使得單元測試的效率得到了極大提高。但是這些基本路徑自動(dòng)生成算法生成的基本路徑并不能直觀反應(yīng)它們對(duì)程序的覆蓋情況。該文提出一種算法，它采用最短路徑復(fù)用及分支結(jié)點(diǎn)逐個(gè)覆蓋法，使得生成的基本路徑最短，重要的是每條基本路徑能顯示它是為了覆蓋哪個(gè)分支結(jié)點(diǎn)而存在。它能夠減少測試者根據(jù)基本路經(jīng)集設(shè)計(jì)測試用例的時(shí)間，從而提高單元及其回歸測試效率。實(shí)踐表明，此算法具有很好的應(yīng)用效果，特別適用于自動(dòng)化生成的測試用例不能滿足覆蓋率要求需要人工生成測試用例的復(fù)雜單元。

關(guān)鍵詞：單元測試；回歸測試；基本路徑

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）12-2753-04

An Automatic Generation Algorithm of Basic Path Set— Reflect the Situation of Branch Coverage

XU Lan， CHEN Lei

（College of Computer， University of South China， Hengyang 421001， China）

Abstract： As all kinds of algorithms about the generation of basic path set have given plenty of exercise in the software testing， so that it improves the efficiency of unit testing greatly. But each basic path generated by those algorithms cant reflect which portions of the code have been covered intuitively. This article comes up with a new algorithm which can generate the shortest basic path for it adopts methods of reusing shortest path and covering branch node one by one. Whats more， the basic path generated by this algorithm can reflect which branch node it has cover. This algorithm will help us narrow the time when we design the test case based on basic paths， and improve the efficiency of unit and regression testing. The practice shows that my algorithm has a good effect especially on complex units that need generate test cases artificially for the automatic generation of test cases cannot meet the coverage requirements.

Key words： unit testing； regression testing； basic path

目前單元測試中自動(dòng)化生成測試用例的算法及測試工具已有多種，但是它們自動(dòng)生成的測試用例不盡如人意。自動(dòng)生成測試用例的算法中，遺傳性算法較為復(fù)雜且收斂性差、基于蟻群及粒子群的算法容易產(chǎn)生早熟現(xiàn)象、隨機(jī)算法因呈現(xiàn)出較大的盲目性導(dǎo)致覆蓋率低[1]。覆蓋率是單元測試重要的衡量標(biāo)準(zhǔn)，包括語句覆蓋、分支覆蓋、條件覆蓋、判定-條件覆蓋、路徑覆蓋等等。像工具C++test，它能夠?yàn)楹瘮?shù)自動(dòng)生成測試用例并執(zhí)行，但是很難達(dá)到覆蓋率要求，所以很多情況下還是得根據(jù)基本路徑人工生成測試用例的數(shù)據(jù)來進(jìn)行單元測試。

人工生成測試用例最重要的環(huán)節(jié)是基本路徑集的尋找，尋找完基本路徑集后根據(jù)每條基本路徑設(shè)計(jì)對(duì)應(yīng)測試用例。進(jìn)行單元回歸測試時(shí)，若代碼做了修改，基本路徑集就得做調(diào)整，或是增加測試用例來覆蓋某個(gè)分支達(dá)到測試覆蓋率，或是刪除某個(gè)多余的用例。當(dāng)設(shè)計(jì)某條測試用例的時(shí)候，可以在其他測試用例的基礎(chǔ)上做修改，因?yàn)樗鼈兛赡苡泄餐谋亟?jīng)分支結(jié)點(diǎn)，那么這兩條路徑有共同的參數(shù)及前置條件，可以復(fù)用這些數(shù)據(jù)來減少設(shè)計(jì)測試用例的時(shí)間。那么如何尋找這條被參考的用例呢？基本路徑與測試用例相對(duì)應(yīng)，如果能從基本路徑集中看出覆蓋必經(jīng)分支結(jié)點(diǎn)的是哪條路徑，那么就能找到參考用例，節(jié)省了尋找參考測試用例的時(shí)間。不過，這對(duì)基本路徑的生成有要求，即生成的路徑能反應(yīng)分支結(jié)點(diǎn)的覆蓋情況。

在提出基本路徑測試法的同時(shí)McCabe就提出了兩種方法來實(shí)現(xiàn)：一是通過控制流圖求解基本路徑集；第二種是直接遍歷程序求得基本路徑集。這兩種方法被認(rèn)為是動(dòng)態(tài)白盒測試技術(shù)中嚴(yán)謹(jǐn)而有效的測試方法。針對(duì)這兩種方法，人們提出了各種基本路徑集的求解算法[1-10]，如：路徑字符串組合算法[2]、基于圖深度優(yōu)先搜索算法等[5]，基于狀態(tài)圖的測試路徑自動(dòng)生成算法[7]等。但這些算法均未體現(xiàn)對(duì)代碼的覆蓋情況，當(dāng)測試單元比較復(fù)雜、路徑比較多而測試用例由人工來根據(jù)基本路徑來生成時(shí)，這些算法生成的路徑就不能快速地幫測試員定位參考用例。 本文提出的基本路徑集生成算法，它將覆蓋同一分支的基本路徑排列到一起，并且基本路徑集中的路徑按分支編號(hào)從小到大排列，方便定位參考用例。下面將介紹此算法：endprint

1 算法介紹

1.1 基本概念

1） 結(jié)點(diǎn)的出度。從結(jié)點(diǎn)A有N條邊出來，A的出度就是N；

2）分支結(jié)點(diǎn)。流程圖中，出度>=2的結(jié)點(diǎn)；

3）獨(dú)立路徑。在程序中至少引進(jìn)一條新的語句或是一個(gè)新的條件的路徑。采用控制流圖的術(shù)語來表示，即路徑P至少包含一條在其他路徑中從未有過的邊；

P=< N0， N1 … Nf >

（N為控制流圖中的節(jié)點(diǎn)，N0代表程序入口，Nf代表程序出口）

4）程序環(huán)路復(fù)雜性或是圈復(fù)雜度。又稱McCabe復(fù)雜性度量，從圈復(fù)雜度可以導(dǎo)出基本路徑中的獨(dú)立路徑數(shù)。E為控制流圖的邊數(shù)，N為圖的節(jié)點(diǎn)數(shù)。

計(jì)算公式為：V（G） = E-N+2.

5）程序基本路徑集?；韭窂郊械拿織l獨(dú)立路徑稱為基本路徑。這些路徑具有如下特點(diǎn)：

①每一條路徑都是獨(dú)立路徑；

②程序中所有的邊都被訪問；

③程序中所有的、不屬于該基本路徑集的路徑都可以由這個(gè)基本路徑集中的路徑經(jīng)過線性運(yùn)算得到。

1.2 算法對(duì)流程圖的編號(hào)要求

1）先編開始結(jié)點(diǎn)，為0；

2）其次編分支結(jié)點(diǎn)（結(jié)點(diǎn)出度數(shù)>=2），從1往后編；

3）再編執(zhí)行語句結(jié)點(diǎn)；

4）最后編結(jié)束結(jié)點(diǎn)；

示例流程圖如圖1。

圖1 被測程序流程圖

1.3 路徑生成算法思路

1）為了體現(xiàn)基本路徑對(duì)分支結(jié)點(diǎn)的覆蓋情況，采用搜索分支結(jié)點(diǎn)的方式來生成基本路徑集。按照分支編號(hào)由小到大的方式搜索，對(duì)于搜索到的每一個(gè)分支結(jié)點(diǎn)，查看是否有未曾訪問的邊連接到其他結(jié)點(diǎn)，若有則以此為一條新邊添加到路徑，然后沿此新邊分別向上擴(kuò)展尋找到開始結(jié)點(diǎn)的通路，和向下擴(kuò)展尋找到結(jié)束結(jié)點(diǎn)的通路。這樣從開始結(jié)點(diǎn)到結(jié)束結(jié)點(diǎn)形成一條完整的通路，此通路上的結(jié)點(diǎn)連接起來就為一條基本路徑。在尋找路徑的時(shí)候有如下要求：若搜索到的分支結(jié)點(diǎn)存在多條未訪問邊連接到其它結(jié)點(diǎn)，且所有邊連接的結(jié)點(diǎn)中有未訪問結(jié)點(diǎn)，則優(yōu)先以此分支結(jié)點(diǎn)和未訪問結(jié)點(diǎn)（存在多個(gè)的話，優(yōu)先選擇編號(hào)較大者）之間的邊分別向上和向下擴(kuò)展尋找通路，其次是已訪問結(jié)點(diǎn)；

2）尋找通路過程中，對(duì)于遇到的結(jié)點(diǎn)若被訪問過，則復(fù)用它已經(jīng)走過的路徑；

3）在向下尋找通路的過程中，若遇到的分支結(jié)點(diǎn)存在多條未訪問邊連接到其它結(jié)點(diǎn)，且所有邊連接的結(jié)點(diǎn)中有未訪問結(jié)點(diǎn)，也是優(yōu)先將未訪問結(jié)點(diǎn)（存在多個(gè)的話，優(yōu)先選擇編號(hào)較大者）添加到路徑，其次是已訪問結(jié)點(diǎn)。

按照此算法，對(duì)于圖1尋找出來的基本路徑集應(yīng)該如下：

1.3 算法實(shí)現(xiàn)需要的數(shù)據(jù)結(jié)構(gòu)

1）BasePathCounts 基本路徑數(shù)目

2）NodeOuts 結(jié)點(diǎn)出度數(shù)（一維數(shù)組）

3）FCM流程圖矩陣（二維數(shù)組，0為無邊，1為有邊，全程不變）

4）LeftNum_Conditions_Node分支結(jié)點(diǎn)剩下的未訪問邊的數(shù)目（一維數(shù)組）

5）EVF邊訪問標(biāo)識(shí)（二維數(shù)組，2為訪問過，1為未訪問過）

6）NVF結(jié)點(diǎn)訪問標(biāo)識(shí)（一維數(shù)組，1為訪問過，0為未訪問過）

7）PrePath_Node結(jié)點(diǎn)前置最短復(fù)用路徑（二維數(shù)組）

8）PostPath_Node結(jié)點(diǎn)后置最短復(fù)用路徑（二維數(shù)組）

9）L_PrePath_Node結(jié)點(diǎn)前置復(fù)用路徑長度（一維數(shù)組）

10）L_PostPath_Node結(jié)點(diǎn)后置復(fù)用路徑長度（一維數(shù)組）

11）BasePathSet基本路經(jīng)集合（二維數(shù)組）

程序先根據(jù)FCM算出每個(gè)節(jié)點(diǎn)的NodeOuts，初始化LeftNum_Conditions_Node為NodeOuts，然后由NodeOuts算出BasePathCounts。以BasePathCounts為循環(huán)次數(shù)，每次循環(huán)找出分支未訪問完且編號(hào)最小的分支節(jié)點(diǎn)，將NVF設(shè)為1（若不為1），LeftNum_Conditions_Node減1，然后以此節(jié)點(diǎn)及未訪問的一條邊為中心分別向上和向下尋找通路，設(shè)置此邊的EVF為2。在尋找通路的過程中，對(duì)于遇到的未訪問邊將EVF設(shè)為2，遇到的未訪問節(jié)點(diǎn)將NVF設(shè)為1，對(duì)于遇到的節(jié)點(diǎn)若存在復(fù)用路徑則復(fù)用此路徑。一條路徑尋找完畢，設(shè)置此條路徑上節(jié)點(diǎn)的復(fù)用路徑（包括設(shè)置PrePath_Node及PostPath_Node，當(dāng)節(jié)點(diǎn)的L_PrePath_Node或L_PostPath_Node較當(dāng)前路徑的可復(fù)用路徑長才重新設(shè)置）。

1.5 算法實(shí)現(xiàn)流程圖

2 算法實(shí)驗(yàn)結(jié)果

利用本文介紹的算法，將流程圖轉(zhuǎn)換為矩陣存儲(chǔ)作為本算法程序的輸入，運(yùn)行程序得到的基本路徑集如圖4所示。

程序運(yùn)行的結(jié)果與預(yù)期一致，驗(yàn)證了算法的正確性。

3 結(jié)束語

路徑自動(dòng)生成算法很多，在生成基本路徑集的基礎(chǔ)上能夠幫助測試者在單元及回歸測試中減少測試用例的設(shè)計(jì)時(shí)間，才能極大地提高測試效率。實(shí)際經(jīng)驗(yàn)表明，此算法具有可操作性。路徑前的輔助提示信息，如（1-1）代表此路徑覆蓋了分支結(jié)點(diǎn)1的一條邊。這樣，測試者在設(shè)計(jì)測試用例的時(shí)候，能夠清楚的知道此路徑是為覆蓋哪個(gè)分支而存在，減少了用例設(shè)計(jì)時(shí)間，提高了測試效率。

參考文獻(xiàn)：

[1] 聶鵬，耿技，秦志光.軟件測試用例自動(dòng)生成算法綜述[J].計(jì)算機(jī)用研究，2012（2）： 401-405.

[2] 王敏，陳亞光.用于基本路徑測試的路徑字符串組合算法[J].計(jì)算機(jī)工程與科學(xué)，2013（12）：134-140.

[3] 解圣霞.基于基本路徑測試的程序圖自動(dòng)生成的應(yīng)用研究[J].通化師范學(xué)院院報(bào)，2009（12）：38-41.

[4]毛澄映，盧炎生.分支測試中測試路徑用例的簡化生成方法[J].計(jì)算機(jī)研究與發(fā)展，2006（2）：175-178.

[5] 吳取勁，陽小華，鹿江春，等.一種基于圖深度優(yōu)先搜索的基本路徑集自動(dòng)生成優(yōu)算法[J]. 南華大學(xué)學(xué)報(bào)：自然科學(xué)版，2012（12）：87-90.

[6] 韓寒，姜淑娟.路徑測試中基本路徑集自動(dòng)生成方法的研究[J].微電子學(xué)與計(jì)算機(jī)，2013（1）：104-109.

[7] 李鵬，彭祥偉，周喜，等.基于狀態(tài)圖的測試路徑自動(dòng)生成[J].計(jì)算機(jī)工程，2011（1）：25-29.

[8] 杜慶峰，李娜.白盒測試基路徑算法[J].計(jì)算機(jī)工程，2009（1）：100-102，123.

[9] 孫曉東，黃松.用于軟件測試的路徑測試方法[J].指揮信息系統(tǒng)與技術(shù)，2011（8）：79-82.

[10] 張廣梅，李曉維，韓叢英.路徑測試中基本路徑集的自動(dòng)生成[J].計(jì)算機(jī)工程，2012（6）：80-83.

[11] 朱少民.軟件測試方法和技術(shù)[M].北京：清華大學(xué)出版社，2005.

[12] Na Zhang， Xiaoan Bao，Zuohua Ding.Unit Testing：Static Analysis and Dynamic Analysis[J].Computer Sciences and Convergence Information Technology，2009.

1 算法介紹

1.1 基本概念

1） 結(jié)點(diǎn)的出度。從結(jié)點(diǎn)A有N條邊出來，A的出度就是N；

2）分支結(jié)點(diǎn)。流程圖中，出度>=2的結(jié)點(diǎn)；

3）獨(dú)立路徑。在程序中至少引進(jìn)一條新的語句或是一個(gè)新的條件的路徑。采用控制流圖的術(shù)語來表示，即路徑P至少包含一條在其他路徑中從未有過的邊；

P=< N0， N1 … Nf >

（N為控制流圖中的節(jié)點(diǎn)，N0代表程序入口，Nf代表程序出口）

4）程序環(huán)路復(fù)雜性或是圈復(fù)雜度。又稱McCabe復(fù)雜性度量，從圈復(fù)雜度可以導(dǎo)出基本路徑中的獨(dú)立路徑數(shù)。E為控制流圖的邊數(shù)，N為圖的節(jié)點(diǎn)數(shù)。

計(jì)算公式為：V（G） = E-N+2.

5）程序基本路徑集。基本路徑集中的每條獨(dú)立路徑稱為基本路徑。這些路徑具有如下特點(diǎn)：

①每一條路徑都是獨(dú)立路徑；

②程序中所有的邊都被訪問；

③程序中所有的、不屬于該基本路徑集的路徑都可以由這個(gè)基本路徑集中的路徑經(jīng)過線性運(yùn)算得到。

1.2 算法對(duì)流程圖的編號(hào)要求

1）先編開始結(jié)點(diǎn)，為0；

2）其次編分支結(jié)點(diǎn)（結(jié)點(diǎn)出度數(shù)>=2），從1往后編；

3）再編執(zhí)行語句結(jié)點(diǎn)；

4）最后編結(jié)束結(jié)點(diǎn)；

示例流程圖如圖1。

圖1 被測程序流程圖

1.3 路徑生成算法思路

1）為了體現(xiàn)基本路徑對(duì)分支結(jié)點(diǎn)的覆蓋情況，采用搜索分支結(jié)點(diǎn)的方式來生成基本路徑集。按照分支編號(hào)由小到大的方式搜索，對(duì)于搜索到的每一個(gè)分支結(jié)點(diǎn)，查看是否有未曾訪問的邊連接到其他結(jié)點(diǎn)，若有則以此為一條新邊添加到路徑，然后沿此新邊分別向上擴(kuò)展尋找到開始結(jié)點(diǎn)的通路，和向下擴(kuò)展尋找到結(jié)束結(jié)點(diǎn)的通路。這樣從開始結(jié)點(diǎn)到結(jié)束結(jié)點(diǎn)形成一條完整的通路，此通路上的結(jié)點(diǎn)連接起來就為一條基本路徑。在尋找路徑的時(shí)候有如下要求：若搜索到的分支結(jié)點(diǎn)存在多條未訪問邊連接到其它結(jié)點(diǎn)，且所有邊連接的結(jié)點(diǎn)中有未訪問結(jié)點(diǎn)，則優(yōu)先以此分支結(jié)點(diǎn)和未訪問結(jié)點(diǎn)（存在多個(gè)的話，優(yōu)先選擇編號(hào)較大者）之間的邊分別向上和向下擴(kuò)展尋找通路，其次是已訪問結(jié)點(diǎn)；

2）尋找通路過程中，對(duì)于遇到的結(jié)點(diǎn)若被訪問過，則復(fù)用它已經(jīng)走過的路徑；

3）在向下尋找通路的過程中，若遇到的分支結(jié)點(diǎn)存在多條未訪問邊連接到其它結(jié)點(diǎn)，且所有邊連接的結(jié)點(diǎn)中有未訪問結(jié)點(diǎn)，也是優(yōu)先將未訪問結(jié)點(diǎn)（存在多個(gè)的話，優(yōu)先選擇編號(hào)較大者）添加到路徑，其次是已訪問結(jié)點(diǎn)。

按照此算法，對(duì)于圖1尋找出來的基本路徑集應(yīng)該如下：

1.3 算法實(shí)現(xiàn)需要的數(shù)據(jù)結(jié)構(gòu)

1）BasePathCounts 基本路徑數(shù)目

2）NodeOuts 結(jié)點(diǎn)出度數(shù)（一維數(shù)組）

3）FCM流程圖矩陣（二維數(shù)組，0為無邊，1為有邊，全程不變）

4）LeftNum_Conditions_Node分支結(jié)點(diǎn)剩下的未訪問邊的數(shù)目（一維數(shù)組）

5）EVF邊訪問標(biāo)識(shí)（二維數(shù)組，2為訪問過，1為未訪問過）

6）NVF結(jié)點(diǎn)訪問標(biāo)識(shí)（一維數(shù)組，1為訪問過，0為未訪問過）

7）PrePath_Node結(jié)點(diǎn)前置最短復(fù)用路徑（二維數(shù)組）

8）PostPath_Node結(jié)點(diǎn)后置最短復(fù)用路徑（二維數(shù)組）

9）L_PrePath_Node結(jié)點(diǎn)前置復(fù)用路徑長度（一維數(shù)組）

10）L_PostPath_Node結(jié)點(diǎn)后置復(fù)用路徑長度（一維數(shù)組）

11）BasePathSet基本路經(jīng)集合（二維數(shù)組）

程序先根據(jù)FCM算出每個(gè)節(jié)點(diǎn)的NodeOuts，初始化LeftNum_Conditions_Node為NodeOuts，然后由NodeOuts算出BasePathCounts。以BasePathCounts為循環(huán)次數(shù)，每次循環(huán)找出分支未訪問完且編號(hào)最小的分支節(jié)點(diǎn)，將NVF設(shè)為1（若不為1），LeftNum_Conditions_Node減1，然后以此節(jié)點(diǎn)及未訪問的一條邊為中心分別向上和向下尋找通路，設(shè)置此邊的EVF為2。在尋找通路的過程中，對(duì)于遇到的未訪問邊將EVF設(shè)為2，遇到的未訪問節(jié)點(diǎn)將NVF設(shè)為1，對(duì)于遇到的節(jié)點(diǎn)若存在復(fù)用路徑則復(fù)用此路徑。一條路徑尋找完畢，設(shè)置此條路徑上節(jié)點(diǎn)的復(fù)用路徑（包括設(shè)置PrePath_Node及PostPath_Node，當(dāng)節(jié)點(diǎn)的L_PrePath_Node或L_PostPath_Node較當(dāng)前路徑的可復(fù)用路徑長才重新設(shè)置）。

1.5 算法實(shí)現(xiàn)流程圖

2 算法實(shí)驗(yàn)結(jié)果

利用本文介紹的算法，將流程圖轉(zhuǎn)換為矩陣存儲(chǔ)作為本算法程序的輸入，運(yùn)行程序得到的基本路徑集如圖4所示。

程序運(yùn)行的結(jié)果與預(yù)期一致，驗(yàn)證了算法的正確性。

3 結(jié)束語

路徑自動(dòng)生成算法很多，在生成基本路徑集的基礎(chǔ)上能夠幫助測試者在單元及回歸測試中減少測試用例的設(shè)計(jì)時(shí)間，才能極大地提高測試效率。實(shí)際經(jīng)驗(yàn)表明，此算法具有可操作性。路徑前的輔助提示信息，如（1-1）代表此路徑覆蓋了分支結(jié)點(diǎn)1的一條邊。這樣，測試者在設(shè)計(jì)測試用例的時(shí)候，能夠清楚的知道此路徑是為覆蓋哪個(gè)分支而存在，減少了用例設(shè)計(jì)時(shí)間，提高了測試效率。

參考文獻(xiàn)：

[1] 聶鵬，耿技，秦志光.軟件測試用例自動(dòng)生成算法綜述[J].計(jì)算機(jī)用研究，2012（2）： 401-405.

[2] 王敏，陳亞光.用于基本路徑測試的路徑字符串組合算法[J].計(jì)算機(jī)工程與科學(xué)，2013（12）：134-140.

[3] 解圣霞.基于基本路徑測試的程序圖自動(dòng)生成的應(yīng)用研究[J].通化師范學(xué)院院報(bào)，2009（12）：38-41.

[4]毛澄映，盧炎生.分支測試中測試路徑用例的簡化生成方法[J].計(jì)算機(jī)研究與發(fā)展，2006（2）：175-178.

[5] 吳取勁，陽小華，鹿江春，等.一種基于圖深度優(yōu)先搜索的基本路徑集自動(dòng)生成優(yōu)算法[J]. 南華大學(xué)學(xué)報(bào)：自然科學(xué)版，2012（12）：87-90.

[6] 韓寒，姜淑娟.路徑測試中基本路徑集自動(dòng)生成方法的研究[J].微電子學(xué)與計(jì)算機(jī)，2013（1）：104-109.

[7] 李鵬，彭祥偉，周喜，等.基于狀態(tài)圖的測試路徑自動(dòng)生成[J].計(jì)算機(jī)工程，2011（1）：25-29.

[8] 杜慶峰，李娜.白盒測試基路徑算法[J].計(jì)算機(jī)工程，2009（1）：100-102，123.

[9] 孫曉東，黃松.用于軟件測試的路徑測試方法[J].指揮信息系統(tǒng)與技術(shù)，2011（8）：79-82.

[10] 張廣梅，李曉維，韓叢英.路徑測試中基本路徑集的自動(dòng)生成[J].計(jì)算機(jī)工程，2012（6）：80-83.

[11] 朱少民.軟件測試方法和技術(shù)[M].北京：清華大學(xué)出版社，2005.

[12] Na Zhang， Xiaoan Bao，Zuohua Ding.Unit Testing：Static Analysis and Dynamic Analysis[J].Computer Sciences and Convergence Information Technology，2009.

1 算法介紹

1.1 基本概念

1） 結(jié)點(diǎn)的出度。從結(jié)點(diǎn)A有N條邊出來，A的出度就是N；

2）分支結(jié)點(diǎn)。流程圖中，出度>=2的結(jié)點(diǎn)；

3）獨(dú)立路徑。在程序中至少引進(jìn)一條新的語句或是一個(gè)新的條件的路徑。采用控制流圖的術(shù)語來表示，即路徑P至少包含一條在其他路徑中從未有過的邊；

P=< N0， N1 … Nf >

（N為控制流圖中的節(jié)點(diǎn)，N0代表程序入口，Nf代表程序出口）

4）程序環(huán)路復(fù)雜性或是圈復(fù)雜度。又稱McCabe復(fù)雜性度量，從圈復(fù)雜度可以導(dǎo)出基本路徑中的獨(dú)立路徑數(shù)。E為控制流圖的邊數(shù)，N為圖的節(jié)點(diǎn)數(shù)。

計(jì)算公式為：V（G） = E-N+2.

5）程序基本路徑集?；韭窂郊械拿織l獨(dú)立路徑稱為基本路徑。這些路徑具有如下特點(diǎn)：

①每一條路徑都是獨(dú)立路徑；

②程序中所有的邊都被訪問；

③程序中所有的、不屬于該基本路徑集的路徑都可以由這個(gè)基本路徑集中的路徑經(jīng)過線性運(yùn)算得到。

1.2 算法對(duì)流程圖的編號(hào)要求

1）先編開始結(jié)點(diǎn)，為0；

2）其次編分支結(jié)點(diǎn)（結(jié)點(diǎn)出度數(shù)>=2），從1往后編；

3）再編執(zhí)行語句結(jié)點(diǎn)；

4）最后編結(jié)束結(jié)點(diǎn)；

示例流程圖如圖1。

圖1 被測程序流程圖

1.3 路徑生成算法思路

1）為了體現(xiàn)基本路徑對(duì)分支結(jié)點(diǎn)的覆蓋情況，采用搜索分支結(jié)點(diǎn)的方式來生成基本路徑集。按照分支編號(hào)由小到大的方式搜索，對(duì)于搜索到的每一個(gè)分支結(jié)點(diǎn)，查看是否有未曾訪問的邊連接到其他結(jié)點(diǎn)，若有則以此為一條新邊添加到路徑，然后沿此新邊分別向上擴(kuò)展尋找到開始結(jié)點(diǎn)的通路，和向下擴(kuò)展尋找到結(jié)束結(jié)點(diǎn)的通路。這樣從開始結(jié)點(diǎn)到結(jié)束結(jié)點(diǎn)形成一條完整的通路，此通路上的結(jié)點(diǎn)連接起來就為一條基本路徑。在尋找路徑的時(shí)候有如下要求：若搜索到的分支結(jié)點(diǎn)存在多條未訪問邊連接到其它結(jié)點(diǎn)，且所有邊連接的結(jié)點(diǎn)中有未訪問結(jié)點(diǎn)，則優(yōu)先以此分支結(jié)點(diǎn)和未訪問結(jié)點(diǎn)（存在多個(gè)的話，優(yōu)先選擇編號(hào)較大者）之間的邊分別向上和向下擴(kuò)展尋找通路，其次是已訪問結(jié)點(diǎn)；

2）尋找通路過程中，對(duì)于遇到的結(jié)點(diǎn)若被訪問過，則復(fù)用它已經(jīng)走過的路徑；

3）在向下尋找通路的過程中，若遇到的分支結(jié)點(diǎn)存在多條未訪問邊連接到其它結(jié)點(diǎn)，且所有邊連接的結(jié)點(diǎn)中有未訪問結(jié)點(diǎn)，也是優(yōu)先將未訪問結(jié)點(diǎn)（存在多個(gè)的話，優(yōu)先選擇編號(hào)較大者）添加到路徑，其次是已訪問結(jié)點(diǎn)。

按照此算法，對(duì)于圖1尋找出來的基本路徑集應(yīng)該如下：

1.3 算法實(shí)現(xiàn)需要的數(shù)據(jù)結(jié)構(gòu)

1）BasePathCounts 基本路徑數(shù)目

2）NodeOuts 結(jié)點(diǎn)出度數(shù)（一維數(shù)組）

3）FCM流程圖矩陣（二維數(shù)組，0為無邊，1為有邊，全程不變）

4）LeftNum_Conditions_Node分支結(jié)點(diǎn)剩下的未訪問邊的數(shù)目（一維數(shù)組）

5）EVF邊訪問標(biāo)識(shí)（二維數(shù)組，2為訪問過，1為未訪問過）

6）NVF結(jié)點(diǎn)訪問標(biāo)識(shí)（一維數(shù)組，1為訪問過，0為未訪問過）

7）PrePath_Node結(jié)點(diǎn)前置最短復(fù)用路徑（二維數(shù)組）

8）PostPath_Node結(jié)點(diǎn)后置最短復(fù)用路徑（二維數(shù)組）

9）L_PrePath_Node結(jié)點(diǎn)前置復(fù)用路徑長度（一維數(shù)組）

10）L_PostPath_Node結(jié)點(diǎn)后置復(fù)用路徑長度（一維數(shù)組）

11）BasePathSet基本路經(jīng)集合（二維數(shù)組）

程序先根據(jù)FCM算出每個(gè)節(jié)點(diǎn)的NodeOuts，初始化LeftNum_Conditions_Node為NodeOuts，然后由NodeOuts算出BasePathCounts。以BasePathCounts為循環(huán)次數(shù)，每次循環(huán)找出分支未訪問完且編號(hào)最小的分支節(jié)點(diǎn)，將NVF設(shè)為1（若不為1），LeftNum_Conditions_Node減1，然后以此節(jié)點(diǎn)及未訪問的一條邊為中心分別向上和向下尋找通路，設(shè)置此邊的EVF為2。在尋找通路的過程中，對(duì)于遇到的未訪問邊將EVF設(shè)為2，遇到的未訪問節(jié)點(diǎn)將NVF設(shè)為1，對(duì)于遇到的節(jié)點(diǎn)若存在復(fù)用路徑則復(fù)用此路徑。一條路徑尋找完畢，設(shè)置此條路徑上節(jié)點(diǎn)的復(fù)用路徑（包括設(shè)置PrePath_Node及PostPath_Node，當(dāng)節(jié)點(diǎn)的L_PrePath_Node或L_PostPath_Node較當(dāng)前路徑的可復(fù)用路徑長才重新設(shè)置）。

1.5 算法實(shí)現(xiàn)流程圖

2 算法實(shí)驗(yàn)結(jié)果

利用本文介紹的算法，將流程圖轉(zhuǎn)換為矩陣存儲(chǔ)作為本算法程序的輸入，運(yùn)行程序得到的基本路徑集如圖4所示。

程序運(yùn)行的結(jié)果與預(yù)期一致，驗(yàn)證了算法的正確性。

3 結(jié)束語

路徑自動(dòng)生成算法很多，在生成基本路徑集的基礎(chǔ)上能夠幫助測試者在單元及回歸測試中減少測試用例的設(shè)計(jì)時(shí)間，才能極大地提高測試效率。實(shí)際經(jīng)驗(yàn)表明，此算法具有可操作性。路徑前的輔助提示信息，如（1-1）代表此路徑覆蓋了分支結(jié)點(diǎn)1的一條邊。這樣，測試者在設(shè)計(jì)測試用例的時(shí)候，能夠清楚的知道此路徑是為覆蓋哪個(gè)分支而存在，減少了用例設(shè)計(jì)時(shí)間，提高了測試效率。

參考文獻(xiàn)：

[1] 聶鵬，耿技，秦志光.軟件測試用例自動(dòng)生成算法綜述[J].計(jì)算機(jī)用研究，2012（2）： 401-405.

[2] 王敏，陳亞光.用于基本路徑測試的路徑字符串組合算法[J].計(jì)算機(jī)工程與科學(xué)，2013（12）：134-140.

[3] 解圣霞.基于基本路徑測試的程序圖自動(dòng)生成的應(yīng)用研究[J].通化師范學(xué)院院報(bào)，2009（12）：38-41.

[4]毛澄映，盧炎生.分支測試中測試路徑用例的簡化生成方法[J].計(jì)算機(jī)研究與發(fā)展，2006（2）：175-178.

[5] 吳取勁，陽小華，鹿江春，等.一種基于圖深度優(yōu)先搜索的基本路徑集自動(dòng)生成優(yōu)算法[J]. 南華大學(xué)學(xué)報(bào)：自然科學(xué)版，2012（12）：87-90.

[6] 韓寒，姜淑娟.路徑測試中基本路徑集自動(dòng)生成方法的研究[J].微電子學(xué)與計(jì)算機(jī)，2013（1）：104-109.

[7] 李鵬，彭祥偉，周喜，等.基于狀態(tài)圖的測試路徑自動(dòng)生成[J].計(jì)算機(jī)工程，2011（1）：25-29.

[8] 杜慶峰，李娜.白盒測試基路徑算法[J].計(jì)算機(jī)工程，2009（1）：100-102，123.

[9] 孫曉東，黃松.用于軟件測試的路徑測試方法[J].指揮信息系統(tǒng)與技術(shù)，2011（8）：79-82.

[10] 張廣梅，李曉維，韓叢英.路徑測試中基本路徑集的自動(dòng)生成[J].計(jì)算機(jī)工程，2012（6）：80-83.

[11] 朱少民.軟件測試方法和技術(shù)[M].北京：清華大學(xué)出版社，2005.

[12] Na Zhang， Xiaoan Bao，Zuohua Ding.Unit Testing：Static Analysis and Dynamic Analysis[J].Computer Sciences and Convergence Information Technology，2009.