基本路徑測(cè)試用例設(shè)計(jì)的改進(jìn)方法

王 敏 馬 敏 張 志

(湖北廣播電視大學(xué)軟件工程學(xué)院 湖北 武漢 430074)

0 引 言

研究表明，軟件測(cè)試是軟件質(zhì)量保證的重要手段。雖然早在20世紀(jì)70年代軟件測(cè)試的基礎(chǔ)理論和方法體系就已初步建立，但迄今為止軟件測(cè)試的很多理論和方法仍然停留在早期的狀態(tài)，已不能滿足實(shí)際應(yīng)用中對(duì)測(cè)試效率和實(shí)用性的需求。尋找新的測(cè)試技術(shù)以應(yīng)對(duì)軟件的測(cè)試需求依然是軟件工程研究者們需要探索的問(wèn)題。

軟件測(cè)試過(guò)程中的單元測(cè)試可以發(fā)現(xiàn)大約80%的軟件缺陷，同時(shí)，由于軟件缺陷的放大效應(yīng)，單元測(cè)試階段的動(dòng)態(tài)白盒測(cè)試對(duì)盡早發(fā)現(xiàn)軟件缺陷、降低項(xiàng)目風(fēng)險(xiǎn)起著重要的作用。McCabe提出基本路徑測(cè)試法被認(rèn)為是動(dòng)態(tài)白盒測(cè)試技術(shù)中嚴(yán)謹(jǐn)而有效的測(cè)試方法，其基本思想是在程序控制流圖的基礎(chǔ)上, 通過(guò)分析控制結(jié)構(gòu)的環(huán)路復(fù)雜度導(dǎo)出基本路徑集,以此作為設(shè)計(jì)測(cè)試用例的依據(jù)。但是當(dāng)程序邏輯結(jié)構(gòu)較為復(fù)雜時(shí)，人工實(shí)現(xiàn)變得比較困難，進(jìn)而對(duì)測(cè)試用例設(shè)計(jì)的效率和正確性都有較大的影響。

人們針對(duì)基本路徑集求解問(wèn)題提出了各種算法[1-5]，但迄今為止都是拘泥于McCabe的基本思想進(jìn)行的一系列基本路徑集求解算法的改進(jìn)，仍然不能完滿地對(duì)應(yīng)各種程序結(jié)構(gòu)。近期的研究提出了基于路徑字符串組合的基本路徑集求解算法[6-7]，該算法較好地實(shí)現(xiàn)了基本路徑的自動(dòng)生成，但此方法未對(duì)應(yīng)條件拆分的問(wèn)題。因此，本文擬借助決策表解決基本路徑集求解中的條件拆分問(wèn)題。

1 條件拆分問(wèn)題的對(duì)應(yīng)思路

研究發(fā)現(xiàn)[6-7]：所有程序都是由若干基本程序結(jié)構(gòu)(順序、分支和循環(huán))構(gòu)成，提出了基于Z路徑覆蓋的基本單元圖，從而可得到構(gòu)成基本單元圖的基本子路徑。程序基本單元通過(guò)嵌套(并聯(lián))組合或順序(串聯(lián))組合形成各種應(yīng)用程序的控制流圖，由此探索出了基本子路徑按照一定方式組合生成基本路徑集的算法。但該算法將所有分支結(jié)構(gòu)的判斷語(yǔ)句視為一個(gè)節(jié)點(diǎn)，沒(méi)考慮判定語(yǔ)句中含多個(gè)條件的情況，這將導(dǎo)致程序中含多條件的判斷語(yǔ)句時(shí)，測(cè)試用例的條件覆蓋率不夠充分。為此借鑒決策表法，將決策表融入基本路徑集求解方法中，以解決基本路徑測(cè)試中的條件覆蓋不充分的問(wèn)題。

文獻(xiàn)[8]為實(shí)現(xiàn)多條件組合問(wèn)題的自動(dòng)化測(cè)試用例設(shè)計(jì)，提出了一種用于表示關(guān)系和約束的因果表達(dá)式，根據(jù)因果表達(dá)式可實(shí)現(xiàn)決策表的簡(jiǎn)化，從而按簡(jiǎn)化后的規(guī)則自動(dòng)生成測(cè)試用例。

在以上研究成果的基礎(chǔ)上，本文提出基本路徑集求解問(wèn)題中條件拆分的對(duì)應(yīng)方法，基本思路是：采用路徑字符串組合法[6]，在基本單元信息提取的同時(shí)提取分支節(jié)點(diǎn)的判斷語(yǔ)句信息，若判斷語(yǔ)句為含多個(gè)條件的邏輯表達(dá)式，則賦予分支節(jié)點(diǎn)特殊的標(biāo)志；然后對(duì)含多個(gè)條件的判斷語(yǔ)句進(jìn)行分析，形成因果表達(dá)式[8]，借助于因果表達(dá)式生成并簡(jiǎn)化決策表；最后將精簡(jiǎn)后的規(guī)則形成規(guī)則路徑集組合到對(duì)應(yīng)的基本路徑集中，從而形成含滿足條件覆蓋的基本路徑集。

2 決策表在基本路徑集求解中的應(yīng)用

按照以上思路，首先用常規(guī)方法結(jié)合實(shí)例對(duì)含多條件的判斷語(yǔ)句進(jìn)行人工條件拆分，求得基本路徑集；然后將決策表應(yīng)用于條件拆分問(wèn)題，尋找基本路徑求解方法；最后將人工拆分條件的方法與決策表法進(jìn)行比較，驗(yàn)證方法的正確性。

2.1 基本路徑集求解中的條件拆分

為便于描述，借用文獻(xiàn)[6]中的偽代碼進(jìn)行說(shuō)明，該偽代碼中的“條件表達(dá)式”默認(rèn)為僅含一個(gè)條件(關(guān)系運(yùn)算)，對(duì)該代碼進(jìn)行修改，將條件表達(dá)式2替換為含2個(gè)條件邏輯與運(yùn)算的多條件表達(dá)式，修改后的偽代碼如下：

例1：

1. while (條件表達(dá)式1)

//含1個(gè)關(guān)系運(yùn)算

2. {

3. 語(yǔ)句1

4. }

5. if (條件表達(dá)式21 && 條件表達(dá)式22)

//含2個(gè)關(guān)系運(yùn)算

6. {

7. if (條件表達(dá)式3)

//含1個(gè)關(guān)系運(yùn)算

8. {

9. 語(yǔ)句3；

10. }

11. else

12. {

13. 語(yǔ)句4；

14. }

15. }

16. else

17. {

18. 語(yǔ)句5

19. }

若不考慮條件拆分，采用文獻(xiàn)[6]中路徑字符串組合算法，其基本路徑集P1為：

路徑1：1→4→5→18→19

路徑2：1→4→5→7→9→14→19

路徑3：1→3→4→5→7→13→14→19

由于節(jié)點(diǎn)5含多個(gè)條件，為滿足條件覆蓋需要進(jìn)行條件拆分，分析例1的代碼可知，條件表達(dá)式結(jié)果為TRUE進(jìn)入第7行語(yǔ)句，否則進(jìn)入第18行語(yǔ)句，對(duì)例1進(jìn)行條件拆分，其代碼改寫為：

1. while (條件表達(dá)式1)

2. {

3. 語(yǔ)句1

4. }

5. if (條件表達(dá)式21)

5.1. {

5.2. if(條件表達(dá)式22)

6. {

7. if (條件表達(dá)式3)

8. {

9. 語(yǔ)句3；

10. }

11. else

12. {

13. 語(yǔ)句4；

14. }

15. }

15.1. else

15.2. {

15.3. 語(yǔ)句5

15.4. }

15.5. }

16. else

17. {

18. 語(yǔ)句5

19. }

按照文獻(xiàn)[6]提出的基本單元圖，改寫代碼段對(duì)應(yīng)的控制流圖如圖1(a)所示，按路徑字符串組合算法，其可能的一組基本路徑集P2為：

路徑1：1→4→5→18→19

路徑2：1→4→5→5.2→15.3→15.5→19

路徑3：1→3→4→5→5.2→7→9→14→15.5→19

路徑4：1→3→4→5→5.2→7→13→14→15.5→19

圖1 條件拆分代碼的控制流圖

由于15.3行語(yǔ)句與18行語(yǔ)句等價(jià)，節(jié)點(diǎn)15.5可合并為節(jié)點(diǎn)19，因此圖1(a)等價(jià)于圖1(b)，假設(shè)第5行代碼包含的兩個(gè)條件用C1、C2表示，其組合值(C1,C2)有(0,0)、(0,1)、(1,0)、(1,1)四對(duì)取值，圖1(b)對(duì)應(yīng)的基本路徑集和條件組合如下：

路徑1：1→4→5→18→19 對(duì)應(yīng)條件組合(0,1)和(0,0)

路徑2：1→4→5→5.2→18→19 對(duì)應(yīng)條件組合(1,0)

路徑3：1→3→4→5→5.2→7→9→14→19 對(duì)應(yīng)條件組合(1,1)

路徑4：1→3→4→5→5.2→7→13→14→19 對(duì)應(yīng)條件組合(1,1)

以上是通過(guò)人工進(jìn)行條件拆分(代碼改寫)求得的基本路徑集，代碼改寫過(guò)程較為復(fù)雜，不便于通過(guò)算法自動(dòng)生成基本路徑集。因此需要尋找便于算法實(shí)現(xiàn)的方法對(duì)應(yīng)條件拆分的問(wèn)題。

2.2 決策表的應(yīng)用

在黑盒測(cè)試中，多條件組合問(wèn)題常常采用決策表法進(jìn)行測(cè)試用例設(shè)計(jì)，針對(duì)多條件組合的測(cè)試用例設(shè)計(jì)已有算法實(shí)現(xiàn)測(cè)試用例的自動(dòng)生成[8]，因此，擬嘗試引入決策表法應(yīng)對(duì)多條件判斷語(yǔ)句的條件拆分問(wèn)題。

(1) 含決策表節(jié)點(diǎn)的基本路徑集 若不考慮條件拆分，例1對(duì)應(yīng)的控制流圖如圖2(a)所示。當(dāng)考慮條件拆分時(shí)，將含多個(gè)條件的判斷節(jié)點(diǎn)轉(zhuǎn)化為一個(gè)決策表節(jié)點(diǎn)，即將圓形節(jié)點(diǎn)5轉(zhuǎn)化為一個(gè)方形的決策表節(jié)點(diǎn)，如圖2(a)的控制流圖改造為圖2(b)。為與最終產(chǎn)生的基本路徑集進(jìn)行區(qū)分，將含決策表節(jié)點(diǎn)的基本路徑集稱為“T基本路徑集”，集合中的路徑稱為“T基本路徑”，對(duì)應(yīng)的基本路徑集P3記為T基本路徑集Pt：

路徑1：1→4→T5→18→19

路徑2：1→4→T5→7→9→14→19

路徑3：1→3→4→T5→7→13→14→19

圖2 例1對(duì)應(yīng)的控制流圖

(2) 決策表與規(guī)則路徑 針對(duì)例1的決策表T5如表1所示，將T5的動(dòng)作樁設(shè)定為“進(jìn)入”T5節(jié)點(diǎn)后繼的分支節(jié)點(diǎn)，例1中，決策表節(jié)點(diǎn)T5的后繼分支節(jié)點(diǎn)有節(jié)點(diǎn)7和節(jié)點(diǎn)18，因此動(dòng)作樁設(shè)為“進(jìn)入18”(表示程序進(jìn)入第18行執(zhí)行)和 “進(jìn)入7”(表示程序進(jìn)入第7行代碼執(zhí)行)，如此描述動(dòng)作樁既直觀又便于后續(xù)規(guī)則路徑的生成及與基本路徑的組合。

表1 T5對(duì)應(yīng)的決策表

我們將每一條規(guī)則轉(zhuǎn)化為一條“規(guī)則路徑”，定義規(guī)則路徑的語(yǔ)法格式為：

Tn(C1，C2，…,Cm)-pe

式中：Tn為判定節(jié)點(diǎn)；(C1，C2，…,Cm)為條件組合值；pe為Tn的某一后繼節(jié)點(diǎn)。故可得例1中T5的規(guī)則路徑集Pr如下：

Pr={T5(0,0)-18，T5(0,1)-18，T5(1,0)-18，T5(1,1)-7}

(3) T基本路徑集與規(guī)則路徑集的組合規(guī)則 同樣以例1為例，當(dāng)條件值滿足規(guī)則1、規(guī)則2和規(guī)則3時(shí)，程序?qū)⒀豑基本路徑1執(zhí)行，條件值滿足規(guī)則4時(shí)，程序?qū)⒀豑基本路徑2或3執(zhí)行。若要求基本路徑覆蓋所有條件(規(guī)則)，T基本路徑1需與T5(0,0)-18、T5(0,1)-18、T5(1,0)-18三條規(guī)則路徑組合，規(guī)則路徑T5(1,1)-7需與T基本路徑2和3組合。而T基本路徑集Pt與規(guī)則路徑集Pr如何組合，是需要進(jìn)一步分析的問(wèn)題。

將規(guī)則路徑Tn(C1，C2，…,Cm)-pe中條件組合(C1，C2，…,Cm)用通配符“*”代替，我們將“Tn*-px”相同的規(guī)則路徑組成集合Rni(針對(duì)Tn決策表，含i條規(guī)則路徑的路徑集合)，將T基本路徑集中包含相同“Tm-py”子路徑的路徑組成集合Pnj(針對(duì)Tn決策表，含j條T基本路徑的路徑集合)，若Tn=Tm，且px=py，則規(guī)則路徑集Rni與T基本路徑集Pnj是具有組合關(guān)系的一對(duì)路徑集。下面進(jìn)一步討論規(guī)則路徑集Rni與T基本路徑集Pnj的組合規(guī)則。

假設(shè)規(guī)則路徑集Rni與路徑集Pnj具有組合關(guān)系，則二者組合形成的路徑數(shù)為Max(i，j)。若i≥j，則按一定的順序?qū)條規(guī)則與j條路徑一對(duì)一組合，余下的i-j條規(guī)則隨機(jī)與j條路徑中任意路徑隨機(jī)組合；若i

按以上組合規(guī)則例1將形成5條基本路徑，路徑組合的結(jié)果不唯一，以下路徑集P4為可能的組合之一：

路徑1：1→4→T5(0，0)→18→19

路徑2：1→4→T5(0，1)→18→19

路徑3：1→4→T5(1，0)→18→19

路徑4：1→4→T5(1,1)→7→9→14→19

路徑5：1→3→4→T5(1,1)→7→13→14→19

(4) 測(cè)試用例的精簡(jiǎn) 在組合條件數(shù)較少的情況下，覆蓋所有條件組合較容易實(shí)現(xiàn)，由于條件數(shù)n與其組合規(guī)則數(shù)2n呈指數(shù)關(guān)系，當(dāng)條件數(shù)較多時(shí)，規(guī)則數(shù)將是一個(gè)較大的數(shù)值，因此，有必要對(duì)決策表進(jìn)行化簡(jiǎn)。對(duì)決策表1進(jìn)行化簡(jiǎn)得決策表2，可得規(guī)則路徑集Pr如下：

Pr={T5(0,-)-18，T5(1,0)-18，T5(1,1)-7}

式中：“-”代表0和1中的任意值，按規(guī)則路徑集與T基本路徑集的組合規(guī)則，得基本路徑集P5如下：

路徑1：1→4→T5(0，-)→18→19

路徑2：1→4→T5(1，0)→18→19

路徑3：1→4→T5(1,1)→7→9→14→19

路徑4：1→3→4→T5(1,1)→7→13→14→19

表2 決策表T5簡(jiǎn)化結(jié)果

采用決策表法得到基本路徑集P5與人工進(jìn)行代碼拆分后形成的基本路徑集P2相吻合。實(shí)驗(yàn)借助其他經(jīng)典代碼進(jìn)行了驗(yàn)證，證實(shí)采用決策表法形成的基本路徑集與通過(guò)人工代碼拆分形成的基本路徑集一致，因此，采用決策表對(duì)應(yīng)條件拆分問(wèn)題是可行的。

文獻(xiàn)[6-7]以及文獻(xiàn)[8]分別實(shí)現(xiàn)了基本路徑集的自動(dòng)求解和決策表的自動(dòng)簡(jiǎn)化及用例生成，因此將二者結(jié)合便能通過(guò)算法對(duì)應(yīng)基本路徑集求解中條件拆分的問(wèn)題。

3 測(cè)試工具設(shè)計(jì)

對(duì)應(yīng)條件拆分的基本路徑集求解工具將在文獻(xiàn)[7]工具的基礎(chǔ)上進(jìn)行功能擴(kuò)展。追加功能主要包含以下幾點(diǎn)：

(1) 多條件信息的提取。在進(jìn)行代碼掃描提取程序基本信息時(shí)，對(duì)判斷語(yǔ)句信息進(jìn)行分析，若判斷語(yǔ)句含多個(gè)條件，則將判斷語(yǔ)句提取出來(lái)用于條件拆分處理使用；同時(shí)將含多條件判斷語(yǔ)句的節(jié)點(diǎn)標(biāo)識(shí)為“T+行號(hào)”，以便規(guī)則路徑與T基本路徑組合時(shí)識(shí)別。

(2) 決策表化簡(jiǎn)。根據(jù)提取的判斷語(yǔ)句信息，采用文獻(xiàn)[8]中的因果表達(dá)式描述多條件的邏輯關(guān)系，利用文獻(xiàn)[8]中“因果表達(dá)式法測(cè)試用例設(shè)計(jì)”工具化簡(jiǎn)決策表，得到精簡(jiǎn)后的有效規(guī)則。

(3) 規(guī)則路徑生成。根據(jù)化簡(jiǎn)后的決策表，將有效規(guī)則生成規(guī)則路徑。

(4) 規(guī)則路徑與T基本路徑的組合。按規(guī)則路徑與T基本路徑的組合規(guī)則進(jìn)行路徑組合，形成達(dá)到一定條件覆蓋的基本路徑集。

3.1 界面設(shè)計(jì)

工具主界面設(shè)計(jì)如圖3所示，復(fù)選框【條件拆分】選中時(shí)，將對(duì)應(yīng)多條件拆分的測(cè)試用例設(shè)計(jì)。單擊【多條件對(duì)應(yīng)】按鈕，將生成含決策表節(jié)點(diǎn)的T基本路徑集，同時(shí)輸出含多條件的判斷語(yǔ)句。隨后啟動(dòng)“因果表達(dá)式法測(cè)試用設(shè)計(jì)”界面，界面設(shè)計(jì)如圖4所示。在該界面完成因果表達(dá)式輸入，生成精簡(jiǎn)后的有效規(guī)則及規(guī)則路徑，關(guān)閉“因果表達(dá)式法測(cè)試用設(shè)計(jì)”界面，返回主界面，單擊【基本路徑生成】將完成規(guī)則路徑與T基本路徑的組合，形成滿足條件覆蓋的基本路徑集。

(a) 初始界面

(b) 執(zhí)行結(jié)果界面圖3 工具主界面

圖4 因果表達(dá)式法測(cè)試用例設(shè)計(jì)界面

3.2 工具實(shí)現(xiàn)流程

當(dāng)【條件拆分】勾選時(shí)，【多條件對(duì)應(yīng)】按鈕可用，單擊該按鈕的處理流程與文獻(xiàn)[7]基本路徑集構(gòu)造流程圖基本一致。如圖5所示，本工具的區(qū)別在于：① 在基本信息提取處理中，追加了對(duì)條件語(yǔ)句是否為多條件的判斷，若為多條件語(yǔ)句，則在節(jié)點(diǎn)編號(hào)前加標(biāo)志“T”，同時(shí)提取出該判斷語(yǔ)句的條件信息；② 后續(xù)的基本路徑生成算法不變，但含多條件的節(jié)點(diǎn)在路徑中表示為“Tn”(n為節(jié)點(diǎn)編號(hào))；③ 輸出結(jié)果中增加了多條件語(yǔ)句信息，用于編輯因果表達(dá)式，生成決策表和對(duì)決策表進(jìn)行化簡(jiǎn)。

圖5 T基本路徑集生成流程圖

單擊主界面的【基本路徑生成】，若不勾選【條件拆分】，將按文獻(xiàn)[7]進(jìn)行基本路徑集求解，若勾選【條件拆分】，則完成規(guī)則路徑集與T基本路徑集的組合，形成基本路徑集。

3.3 工具在智能機(jī)器人控制軟件中的應(yīng)用

進(jìn)行智能機(jī)器人控制軟件的研發(fā)過(guò)程中，對(duì)軟件的維護(hù)頻率高、測(cè)試效率比較低下，將本工具應(yīng)用于該系統(tǒng)的白盒測(cè)試，有效提高了測(cè)試效率。

圖6為一個(gè)機(jī)器手臂尋跡處理軟件代碼文件MainWindow.xaml.cs中的被測(cè)代碼段截圖。代碼掃描提取出了多條件信息T34：(obj.Name==″sld1″ || obj.Name==″sldAcc″)，生成的T基本路徑集如下：

路徑1：34-35-50；

路徑2：34-42-T43-49-50；

路徑3：34-42-T43-44-49-50。

圖6 被測(cè)程序代碼段

根據(jù)多條件信息T34：(obj.Name == ″sld1″ || obj.Name == ″sldAcc″)，可得條件和結(jié)果信息如下：

C[1]:obj.Name == ″sld1″；

C[2]:obj.Name == ″sldAcc″;

E[1]:進(jìn)入44；

E[2]:進(jìn)入49。

根據(jù)關(guān)系表達(dá)式和約束表達(dá)式的語(yǔ)法規(guī)則[7]，由于obj.Name不可能同時(shí)等于″sld1″和″sldAcc″，因此有約束表達(dá)式：

Y[1]:E(C[1]，C[2])；

原因C[1]和C[2]之間為“或”關(guān)系，可得關(guān)系表達(dá)式：

R[1]:OR(C[1]，C[2])=E[1]；

R[2]:AND(NEG(C[1])，NEG(C[2]))=E[2]。

采用因果表達(dá)式法測(cè)試用例設(shè)計(jì)工具，輸入以上條件、結(jié)果、約束和關(guān)系表達(dá)式，生成測(cè)試用例如圖7(a)所示，可觀察決策表簡(jiǎn)化信息如圖7(b)所示，因Y[1]約束制約，規(guī)則4為不存在的規(guī)則，規(guī)則1-規(guī)則3均為有效規(guī)則。

(a) 用例生成結(jié)果

(b) 簡(jiǎn)化過(guò)程表圖7 因果表達(dá)式法測(cè)試用例設(shè)計(jì)運(yùn)行結(jié)果

依據(jù)決策表可形成規(guī)則路徑：

規(guī)則路徑1：T43(0,0)-49；

規(guī)則路徑2：T43(0,1)-44；

規(guī)則路徑3：T43(1,0)-44。

返回主界面單擊【基本路徑生成】，完成規(guī)則路徑與T基本路徑的組合，得基本路徑集如下：

路徑1：34-35-50；

路徑2：34-42-T43(0,0)-49-50；

路徑3：34-42-T43(0,1)-44-49-50；

路徑4：34-42-T43(1,0)-44-49-50。

對(duì)應(yīng)條件拆分后，基本路徑數(shù)由原來(lái)的3條變成了4條。這與采用人工拆分代碼生成的測(cè)試用例一致。

3.4 工具算法分析

工具實(shí)現(xiàn)借鑒了文獻(xiàn)[6-8]中的基本算法，其中追加的規(guī)則路徑與T基本路徑的組合算法與文獻(xiàn)[6]中的串聯(lián)組合一致，因此，工具的算法時(shí)間復(fù)雜度與文獻(xiàn)[6]一致，T(n)=O(n)。

4 結(jié) 語(yǔ)

本文提出的基本路徑集求解方法，借鑒路徑字符串組合算法，在掃描被測(cè)代碼獲取基本路徑信息的同時(shí)對(duì)判斷節(jié)點(diǎn)的條件信息進(jìn)行判斷，獲取含多條件組合的判斷語(yǔ)句信息，并生成字符串形式的T基本路徑集。采用因果表達(dá)式描述多條件間的邏輯關(guān)系，依據(jù)因果表達(dá)式生成并化簡(jiǎn)決策表，形成字符串形式的有效規(guī)則路徑集。將T基本路徑集與有效規(guī)則路徑集進(jìn)行組合即可得到滿足條件覆蓋的基本路徑集。該方法對(duì)應(yīng)了文獻(xiàn)[7]基本路徑集求解算法中的條件拆分問(wèn)題。在后續(xù)研究中，我們將繼續(xù)采用適當(dāng)?shù)乃惴ń鉀Q不可達(dá)路徑問(wèn)題，以較完滿地實(shí)現(xiàn)基本路徑集的自動(dòng)求解。