基本路徑測(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è)試需求依然是軟件工程研究者們需要探索的問題。

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

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

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

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

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

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

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

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

為便于描述，借用文獻(xiàn)[6]中的偽代碼進(jìn)行說明，該偽代碼中的“條件表達(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. 語句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. 語句3；

10. }

11. else

12. {

13. 語句4；

14. }

15. }

16. else

17. {

18. 語句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行語句，否則進(jìn)入第18行語句，對(duì)例1進(jìn)行條件拆分，其代碼改寫為：

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

2. {

3. 語句1

4. }

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

5.1. {

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

6. {

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

8. {

9. 語句3；

10. }

11. else

12. {

13. 語句4；

14. }

15. }

15.1. else

15.2. {

15.3. 語句5

15.4. }

15.5. }

16. else

17. {

18. 語句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行語句與18行語句等價(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)

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

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

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

(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ī)則路徑的語法格式為：

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)一步分析的問題。

將規(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è)試用例的精簡 在組合條件數(shù)較少的情況下，覆蓋所有條件組合較容易實(shí)現(xiàn)，由于條件數(shù)n與其組合規(guī)則數(shù)2n呈指數(shù)關(guān)系，當(dāng)條件數(shù)較多時(shí)，規(guī)則數(shù)將是一個(gè)較大的數(shù)值，因此，有必要對(duì)決策表進(jìn)行化簡。對(duì)決策表1進(jì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é)果

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

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

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

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

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

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

(3) 規(guī)則路徑生成。根據(jù)化簡后的決策表，將有效規(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í)輸出含多條件的判斷語句。隨后啟動(dòng)“因果表達(dá)式法測(cè)試用設(shè)計(jì)”界面，界面設(shè)計(jì)如圖4所示。在該界面完成因果表達(dá)式輸入，生成精簡后的有效規(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ì)條件語句是否為多條件的判斷，若為多條件語句，則在節(jié)點(diǎn)編號(hào)前加標(biāo)志“T”，同時(shí)提取出該判斷語句的條件信息；② 后續(xù)的基本路徑生成算法不變，但含多條件的節(jié)點(diǎn)在路徑中表示為“Tn”(n為節(jié)點(diǎn)編號(hào))；③ 輸出結(jié)果中增加了多條件語句信息，用于編輯因果表達(dá)式，生成決策表和對(duì)決策表進(jìn)行化簡。

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

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

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

進(jìn)行智能機(jī)器人控制軟件的研發(fā)過程中，對(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á)式的語法規(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)所示，可觀察決策表簡化信息如圖7(b)所示，因Y[1]約束制約，規(guī)則4為不存在的規(guī)則，規(guī)則1-規(guī)則3均為有效規(guī)則。

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

(b) 簡化過程表圖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ù)由原來的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é) 語

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