王 敏 馬 敏 張 志

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

0 引 言

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

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

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

1 條件拆分問題的對應思路

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

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

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

2 決策表在基本路徑集求解中的應用

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

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

為便于描述，借用文獻[6]中的偽代碼進行說明，該偽代碼中的“條件表達式”默認為僅含一個條件(關系運算)，對該代碼進行修改，將條件表達式2替換為含2個條件邏輯與運算的多條件表達式，修改后的偽代碼如下：

例1：

1. while (條件表達式1)

//含1個關系運算

2. {

3. 語句1

4. }

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

//含2個關系運算

6. {

7. if (條件表達式3)

//含1個關系運算

8. {

9. 語句3；

10. }

11. else

12. {

13. 語句4；

14. }

15. }

16. else

17. {

18. 語句5

19. }

若不考慮條件拆分，采用文獻[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é)點5含多個條件，為滿足條件覆蓋需要進行條件拆分，分析例1的代碼可知，條件表達式結果為TRUE進入第7行語句，否則進入第18行語句，對例1進行條件拆分，其代碼改寫為：

1. while (條件表達式1)

2. {

3. 語句1

4. }

5. if (條件表達式21)

5.1. {

5.2. if(條件表達式22)

6. {

7. if (條件表達式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. }

按照文獻[6]提出的基本單元圖，改寫代碼段對應的控制流圖如圖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é)點15.5可合并為節(jié)點19，因此圖1(a)等價于圖1(b)，假設第5行代碼包含的兩個條件用C1、C2表示，其組合值(C1,C2)有(0,0)、(0,1)、(1,0)、(1,1)四對取值，圖1(b)對應的基本路徑集和條件組合如下：

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

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

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

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

以上是通過人工進行條件拆分(代碼改寫)求得的基本路徑集，代碼改寫過程較為復雜，不便于通過算法自動生成基本路徑集。因此需要尋找便于算法實現的方法對應條件拆分的問題。

2.2 決策表的應用

在黑盒測試中，多條件組合問題常常采用決策表法進行測試用例設計，針對多條件組合的測試用例設計已有算法實現測試用例的自動生成[8]，因此，擬嘗試引入決策表法應對多條件判斷語句的條件拆分問題。

(1) 含決策表節(jié)點的基本路徑集 若不考慮條件拆分，例1對應的控制流圖如圖2(a)所示。當考慮條件拆分時，將含多個條件的判斷節(jié)點轉化為一個決策表節(jié)點，即將圓形節(jié)點5轉化為一個方形的決策表節(jié)點，如圖2(a)的控制流圖改造為圖2(b)。為與最終產生的基本路徑集進行區(qū)分，將含決策表節(jié)點的基本路徑集稱為“T基本路徑集”，集合中的路徑稱為“T基本路徑”，對應的基本路徑集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對應的控制流圖

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

表1 T5對應的決策表

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

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

式中：Tn為判定節(jié)點；(C1，C2，…,Cm)為條件組合值；pe為Tn的某一后繼節(jié)點。故可得例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為例，當條件值滿足規(guī)則1、規(guī)則2和規(guī)則3時，程序將沿T基本路徑1執(zhí)行，條件值滿足規(guī)則4時，程序將沿T基本路徑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如何組合，是需要進一步分析的問題。

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

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

按以上組合規(guī)則例1將形成5條基本路徑，路徑組合的結果不唯一，以下路徑集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) 測試用例的精簡 在組合條件數較少的情況下，覆蓋所有條件組合較容易實現，由于條件數n與其組合規(guī)則數2n呈指數關系，當條件數較多時，規(guī)則數將是一個較大的數值，因此，有必要對決策表進行化簡。對決策表1進行化簡得決策表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簡化結果

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

文獻[6-7]以及文獻[8]分別實現了基本路徑集的自動求解和決策表的自動簡化及用例生成，因此將二者結合便能通過算法對應基本路徑集求解中條件拆分的問題。

3 測試工具設計

對應條件拆分的基本路徑集求解工具將在文獻[7]工具的基礎上進行功能擴展。追加功能主要包含以下幾點：

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

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

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

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

3.1 界面設計

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

(a) 初始界面

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

圖4 因果表達式法測試用例設計界面

3.2 工具實現流程

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

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

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

3.3 工具在智能機器人控制軟件中的應用

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

圖6為一個機器手臂尋跡處理軟件代碼文件MainWindow.xaml.cs中的被測代碼段截圖。代碼掃描提取出了多條件信息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 被測程序代碼段

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

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

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

E[1]:進入44；

E[2]:進入49。

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

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

原因C[1]和C[2]之間為“或”關系，可得關系表達式：

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

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

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

(a) 用例生成結果

(b) 簡化過程表圖7 因果表達式法測試用例設計運行結果

依據決策表可形成規(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。

對應條件拆分后，基本路徑數由原來的3條變成了4條。這與采用人工拆分代碼生成的測試用例一致。

3.4 工具算法分析

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

4 結 語

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