因果圖法的改進(jìn)及算法實(shí)現(xiàn)

張 志,王 敏

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

0 引 言

提高開發(fā)效率、降低軟件成本是軟件工程追求的目標(biāo)。作為軟件開發(fā)過程的重要組成部分，軟件測試是軟件質(zhì)量保證的重要手段，在大型軟件開發(fā)項(xiàng)目中，軟件測試甚至?xí)紦?jù)整個(gè)項(xiàng)目周期的一半時(shí)間[1]。軟件測試的效率將直接影響軟件項(xiàng)目的效率和成本，因此如何提高軟件測試效率是研究者們一直探索的問題[2-10]。

針對(duì)多條件組合問題常常采用因果圖法進(jìn)行測試用例設(shè)計(jì)，但當(dāng)組合條件太多，存在較復(fù)雜的因果關(guān)系和約束的情況下，測試用例設(shè)計(jì)過程較復(fù)雜、設(shè)計(jì)效率較低下，故人們對(duì)因果圖法的測試用例自動(dòng)生成進(jìn)行了一系列的研究。20世紀(jì)90年代曾提出依據(jù)因果圖得出關(guān)系或約束的邏輯表達(dá)式來自動(dòng)生成測試用例[11]，以及用條件公式和卡若圖來化簡決策表等[12]，在一定程度上實(shí)現(xiàn)了測試用例設(shè)計(jì)的自動(dòng)化。隨著軟件工程和可視化編程技術(shù)的發(fā)展，早期的這些方法在可操作性和易用性上已不能滿足測試用例設(shè)計(jì)者的需求。為此，人們又提出了采用逐級(jí)模式轉(zhuǎn)換的方式生成測試用例[13]，根據(jù)人工分析得到條件組合表達(dá)式來實(shí)現(xiàn)決策表的化簡等方法[14]。但迄今為止的成果尚局限于因果圖法的思路,且未實(shí)現(xiàn)測試用例設(shè)計(jì)全過程的自動(dòng)化。為此，拋開傳統(tǒng)的因果圖法設(shè)計(jì)思路，提出采用符號(hào)機(jī)制[15],用由字符組成的因果表達(dá)式取代因果圖來進(jìn)行測試用例設(shè)計(jì)。

為實(shí)現(xiàn)上述目標(biāo)，需要定義能取代因果圖的因果表達(dá)式的語法規(guī)則，并設(shè)計(jì)一種數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)和操作決策表，在此基礎(chǔ)上結(jié)合測試用例設(shè)計(jì)的需求實(shí)現(xiàn)基于因果表達(dá)式的測試用例設(shè)計(jì)工具。

1 因果表達(dá)式

在軟件工程領(lǐng)域，很多設(shè)計(jì)均以圖形化的方式呈現(xiàn)，其優(yōu)點(diǎn)是直觀、易于理解，但將圖形化呈現(xiàn)的數(shù)據(jù)作為計(jì)算機(jī)處理的輸入，其處理復(fù)雜度將會(huì)高于對(duì)線性字符的處理。于是本文設(shè)想將因果圖演變?yōu)橐蚬磉_(dá)式來描述關(guān)系和約束，將對(duì)復(fù)雜圖形的處理轉(zhuǎn)化為對(duì)字符表達(dá)式的分析處理，可以降低算法實(shí)現(xiàn)的復(fù)雜程度。為此，首先需確立能替代因果圖的因果表達(dá)式的語法規(guī)則。

因果圖含4種關(guān)系圖(如圖1所示)和5種約束圖(如圖2所示)[16]，因此需要定義若干表達(dá)式來描述這9類因果圖。

圖1 因果圖的關(guān)系圖

圖2 因果圖的約束圖

首先給出因果表達(dá)式的定義：

定義1采用字符、數(shù)字來表示因果圖中的各種關(guān)系和約束的表達(dá)式，叫做因果表達(dá)式。其中表示約束語義的為約束表達(dá)式，表示關(guān)系語義的為關(guān)系表達(dá)式。

設(shè)被測對(duì)象的規(guī)格說明中含n個(gè)原因、m個(gè)結(jié)果、k個(gè)約束、q個(gè)關(guān)系，對(duì)應(yīng)的語法規(guī)則為：C[i](i為原因編號(hào)，1≦i≦n)表示編號(hào)為i的原因，E[i](i為結(jié)果編號(hào)，1≦i≦m)表示編號(hào)為i的結(jié)果，Y[i](i為約束編號(hào)，1≦i≦k)表示編號(hào)為i的約束表達(dá)式，R[i](i為關(guān)系編號(hào)，1≦i≦q)表示編號(hào)為i的關(guān)系表達(dá)式。

與圖1(a)～圖1(d)對(duì)應(yīng)，制定關(guān)系表達(dá)式的語法規(guī)則如下：

1)恒等。記為C[i]=E[j]，表示原因C[i]成立，則有結(jié)果E[j],對(duì)應(yīng)圖1(a)。

2)非。記為NEG(C[i])=E[j]，可表示2層意思：①原因C[i]不成立，則有結(jié)果E[j]；②原因C[i]成立，則沒有結(jié)果E[j]。為了方便后續(xù)編程實(shí)現(xiàn)，表達(dá)式均要求以有對(duì)應(yīng)結(jié)果的方式進(jìn)行描述，故這里取意思①，對(duì)應(yīng)圖1(b)，NEG為非運(yùn)算符。

3)或。記為OR(C[i]，…,C[n])=E[j]，表示參與運(yùn)算的任一原因成立，則有結(jié)果E[j],對(duì)應(yīng)圖1(c)，OR為或運(yùn)算符。

4)與。記為AND(C[i]，…,C[n])=E[j],表示參與運(yùn)算的原因全部成立，則有結(jié)果E[j],對(duì)應(yīng)圖1(d)，AND為與運(yùn)算符。

以上為與因果圖中的關(guān)系圖對(duì)應(yīng)的關(guān)系表達(dá)式，為表達(dá)式描述更加直觀、簡潔且便于后續(xù)實(shí)現(xiàn)，在此定義2種擴(kuò)展的語法規(guī)則：①允許對(duì)AND和OR運(yùn)算內(nèi)的參數(shù)進(jìn)行NEG運(yùn)算來表示原因不成立的語義，如：AND(NEG(C[i]),C[k])=E[j]，其語義為C[i]不成立且C[k]成立，則有結(jié)果E[j]；②允許關(guān)系表達(dá)式等號(hào)右側(cè)為多個(gè)結(jié)果的列表,將多個(gè)結(jié)果用逗號(hào)分隔置于單括弧中，表示由某些原因組合可有多個(gè)結(jié)果，如：AND(C[i]，C[n])=(E[j],E[m]),表示原因C[i]和C[n]同時(shí)成立，則有E[j]和E[m]這2個(gè)結(jié)果。

與圖2(a)～圖2(e)對(duì)應(yīng)，制定約束表達(dá)式的語法規(guī)則如下：

1)互斥。記為E(C[i],…，C[j]，…,C[n]),表示括弧內(nèi)的原因最多只有一個(gè)成立，對(duì)應(yīng)圖2(a)。

2)包含。記為I(C[i],…，C[j]，…,C[n]),表示括弧內(nèi)的原因至少有一個(gè)必須成立，對(duì)應(yīng)圖2(b)。

3)唯一。記為O(C[i],…，C[j]，…,C[n]),表示括弧內(nèi)的原因有且僅有一個(gè)成立，對(duì)應(yīng)圖2(c)。

4)要求。記為R(C[i],C[j]),表示C[i]成立則C[j]也必須成立，對(duì)應(yīng)圖2(d)。

5)強(qiáng)制。記為M(E[i],E[j]),表示若有結(jié)果E[i]，則不可能有結(jié)果E[j]，對(duì)應(yīng)圖2(e)。

確立了與因果圖對(duì)應(yīng)的因果表達(dá)式及其擴(kuò)展表達(dá)式的語法規(guī)則，即可將測試用例設(shè)計(jì)條件以字符表達(dá)式的方式輸入計(jì)算機(jī)，接下來探索測試用例設(shè)計(jì)的實(shí)現(xiàn)方法。

2 決策表的數(shù)據(jù)結(jié)構(gòu)

多條件組合問題的測試用例設(shè)計(jì)最終要轉(zhuǎn)化為決策表，通過對(duì)因果圖約束的分析可以確定決策表中不可能存在的規(guī)則，從而減少?zèng)Q策表的規(guī)則數(shù)，即減少測試用例數(shù)。因此，探索基于因果表達(dá)式的測試用例生成算法，首先需要確定決策表的數(shù)據(jù)結(jié)構(gòu)。

2.1 決策表的數(shù)據(jù)存儲(chǔ)

相較于傳統(tǒng)的因果圖法，采用因果表達(dá)式不再需要中間狀態(tài)作為過渡。在此定義新的決策表結(jié)構(gòu)，假設(shè)被測對(duì)象含3個(gè)原因、4個(gè)結(jié)果，其決策表結(jié)構(gòu)如表1所示(表中數(shù)據(jù)為初始數(shù)據(jù))。與因果圖法的決策表結(jié)構(gòu)相比，減少了中間狀態(tài)，增加了一行有效性數(shù)據(jù)，此行數(shù)據(jù)用于在生成測試用例過程中標(biāo)識(shí)規(guī)則的有效性(1表示有效規(guī)則,非1表示被約束排除或合并化簡的無效規(guī)則)。

表1 新決策表結(jié)構(gòu)

規(guī)則編號(hào)12345678有效性11111111C[1]00001111C[2]00110011C[3]01010101E[1]00000000E[2]00000000E[3]00000000E[4]00000000

為此，給出新的決策表定義：

定義2將以規(guī)則編號(hào)、有效性、原因和結(jié)果為行，規(guī)則為列，用于存儲(chǔ)規(guī)則編號(hào)、規(guī)則有效性、原因值和結(jié)果值的二維數(shù)據(jù)表，叫決策表。

若某被測對(duì)象含有n個(gè)原因(條件)、m個(gè)結(jié)果，則決策表為(m+n+2)×(2n+1)的二維數(shù)據(jù)表(如表1之標(biāo)注所示)。確立了決策表的數(shù)據(jù)結(jié)構(gòu)，測試用例的設(shè)計(jì)即演化為對(duì)二維數(shù)據(jù)表的操作。

2.2 決策表的數(shù)據(jù)操作

利用決策表進(jìn)行測試用例設(shè)計(jì)含以下操作步驟：

Step1根據(jù)規(guī)格說明確定原因和結(jié)果；

Step2根據(jù)規(guī)格說明列出因果(關(guān)系和約束)表達(dá)式；

Step3生成初始決策表；

Step4根據(jù)關(guān)系表達(dá)式確定結(jié)果值；

Step5根據(jù)約束表達(dá)式排除不可能規(guī)則；

Step6合并化簡；

Step7測試用例生成。

傳統(tǒng)因果圖法的化簡是指“如果2條或多條規(guī)則的結(jié)果(動(dòng)作項(xiàng))完全相同，原因(條件項(xiàng))只有一項(xiàng)不同，則可以將這些規(guī)則合并為一條規(guī)則”,化簡實(shí)際上就是合并相似規(guī)則的操作，可減少規(guī)則數(shù)，也即減少測試用例數(shù)。根據(jù)約束排除不可能規(guī)則也是為了減少測試用例數(shù)，因此，對(duì)化簡做以下擴(kuò)展定義。

定義3根據(jù)約束表達(dá)式排除決策表中不可能存在的規(guī)則，或合并決策表相似規(guī)則的處理，叫做化簡。

根據(jù)化簡方式的不同，將化簡分為約束化簡和合并化簡。根據(jù)約束表達(dá)式排除不可能規(guī)則的化簡叫約束化簡；合并決策表相似規(guī)則的化簡叫合并化簡。

以上7個(gè)步驟中Step1～Step2可通過對(duì)規(guī)格說明書的分析將測試輸入直接通過鍵盤輸入到計(jì)算機(jī)，Step3即按表1的規(guī)則初始化決策表數(shù)據(jù)，步驟Step4～Step6是測試用例自動(dòng)生成的核心步驟，實(shí)現(xiàn)將初始決策表精簡為少量有效規(guī)則，Step7將化簡后的決策表轉(zhuǎn)換為描述性的測試用例。對(duì)決策表的操作主要著眼于Step3～Step7。

下面以一個(gè)經(jīng)典案例來分析采用因果表達(dá)式進(jìn)行測試用例設(shè)計(jì)的決策表操作。

案例1某軟件規(guī)格說明要求：第一個(gè)字符必須是#或*，第二個(gè)字母必須是數(shù)字，在此情況下進(jìn)行文件的修改，如果第一個(gè)字符不是#或*，則輸出信息“N”，如果第二個(gè)字符不是數(shù)字，則給出信息“M”。

根據(jù)以上規(guī)格說明,按上述步驟進(jìn)行測試用例設(shè)計(jì):

1)根據(jù)規(guī)格說明確定原因和結(jié)果。

C[1]：第一個(gè)字符是#；

C[2]：第一個(gè)字符是*；

C[3]：第二個(gè)字母必須是數(shù)字。

E[1]：進(jìn)行文件的修改；

E[2]：輸出信息“N”；

E[3]：輸出信息“M”。

算法實(shí)現(xiàn)：定義原因數(shù)組C和結(jié)果數(shù)組E。

2)根據(jù)規(guī)格說明列出因果表達(dá)式。

約束表達(dá)式：

Y[1]：E(C[1]，C[2])

算法實(shí)現(xiàn)：定義約束表達(dá)式數(shù)組Y。

關(guān)系表達(dá)式：

R[1]：AND(C[1]，C[3])=E[1]

R[2]：AND(C[2]，C[3])=E[1]

R[3]：AND(NEG(C[1])，NEG(C[2]))=E[2]

R[4]：NEG(C[3])=E[3]

算法實(shí)現(xiàn)：定義關(guān)系表達(dá)式數(shù)組R。

3)生成初始決策表，即決策表的初始化。第1行數(shù)據(jù)初始化為規(guī)則編號(hào)；第2行數(shù)據(jù)初始化為“1”，表示全部規(guī)則有效；假設(shè)有n個(gè)原因，則n行原因數(shù)據(jù)的初始化規(guī)則為：將0～(2n-1)的2n個(gè)數(shù)值轉(zhuǎn)換為二進(jìn)制數(shù)，以“0”和“1”逐位填寫到對(duì)應(yīng)行列中。案例含3個(gè)原因，則將0～7的二進(jìn)制代碼一次填入表2的3～5列；結(jié)果行數(shù)據(jù)初始化為0，表示無結(jié)果。如表2所示。

表2 初始決策表

規(guī)則12345678有效性11111111C[1]00001111C[2]00110011C[3]01010101E[1]00000000E[2]00000000E[3]00000000

4)根據(jù)關(guān)系表達(dá)式確定結(jié)果值。

如圖3所示，設(shè)關(guān)系表達(dá)式數(shù)組R的下標(biāo)變量為k，決策表D的列下標(biāo)變量分別為j；以關(guān)系表達(dá)式作為外循環(huán)，規(guī)則作為內(nèi)循環(huán)，逐一進(jìn)行結(jié)果值設(shè)定，判斷決策表規(guī)則的原因值是否滿足關(guān)系表達(dá)式左邊原因值，若滿足則依據(jù)關(guān)系表達(dá)式右邊的結(jié)果列表，將該規(guī)則對(duì)應(yīng)的結(jié)果值設(shè)為“1”。如案例1，當(dāng)關(guān)系R[1]對(duì)規(guī)則進(jìn)行循環(huán)時(shí)，若規(guī)則C[1]=“1”，C[3]=“1”，則將對(duì)應(yīng)規(guī)則的結(jié)果值E[1]設(shè)為“1”，如表3所示。

圖3 結(jié)果值設(shè)定處理流程

5)根據(jù)約束表達(dá)式進(jìn)行約束化簡。

與上面測試用例設(shè)計(jì)4的處理類似，以約束表達(dá)式作為外循環(huán)，規(guī)則作為內(nèi)循環(huán)，逐一判斷決策表規(guī)則的原因值或結(jié)果值(強(qiáng)制)是否滿足約束表達(dá)式的制約，若滿足則將該規(guī)則的有效性設(shè)為對(duì)應(yīng)約束編號(hào)“Y[i]”。如案例中的Y[1]，規(guī)則7,8的C[1]=“1”，C[2]=“1”，滿足Y[1]制約，則將其有效性設(shè)為“Y[1]”，如表3所示。

表3 化簡后的決策表

規(guī)則12345678有效性111111Y[1]Y[1]C[1]00001111C[2]00110011C[3]01010101E[1]00010101E[2]11000000E[3]10101010

6)合并化簡。

按結(jié)果值進(jìn)行篩選，結(jié)果值一致的規(guī)則分為一組，然后按組進(jìn)行循環(huán)，同一組數(shù)據(jù)中，按冒泡方式進(jìn)行合并，若滿足合并條件，則將規(guī)則編號(hào)較大規(guī)則的有效性設(shè)為“H”，表示合并化簡操作被合并的規(guī)則，并將不同的原因(條件項(xiàng))項(xiàng)設(shè)為“-”，該規(guī)則可繼續(xù)參與冒泡合并。

案例不存在可合并的規(guī)則，故決策表不能被進(jìn)一步化簡。于是得到化簡后的最終決策表，如表3所示，規(guī)則1～6為有效規(guī)則。

7)測試用例生成。

根據(jù)化簡后的決策表，1條有效規(guī)則對(duì)應(yīng)生成1條測試用例。

3 算法的工具化實(shí)現(xiàn)

確立了因果表達(dá)式及決策表的數(shù)據(jù)結(jié)構(gòu)，便可實(shí)現(xiàn)包含測試條件輸入、測試用例自動(dòng)生成以及測試用例維護(hù)功能的基于多條件組合的測試用例自動(dòng)生成工具。在此，選用C#,.Net可視化編程平臺(tái)，將決策表定義為該平臺(tái)現(xiàn)有的數(shù)據(jù)類型DataTable類型，并通過與DataGridView控件綁定，來直觀地呈現(xiàn)數(shù)據(jù)。

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

將工具設(shè)計(jì)為2個(gè)界面：設(shè)計(jì)界面和設(shè)計(jì)過程顯示界面。設(shè)計(jì)界面如圖4所示，界面分為2個(gè)區(qū)域：測試輸入編輯區(qū)如圖4(a)所示、測試用例顯示及編輯區(qū)如圖4(b)所示，為簡化描述，將部分控件Text屬性的初始值設(shè)成控件類型，設(shè)計(jì)采用了數(shù)組型列表框控件(ListBox)來顯示原因、結(jié)果、約束表達(dá)式和關(guān)系表達(dá)式列表，既方便查看系列數(shù)據(jù)又便于在編程中利用index屬性作為循環(huán)變量和使用列表框中的元素。

(a) 測試輸入編輯區(qū) (b) 測試用例顯示及編輯區(qū)圖4 測試用例設(shè)計(jì)界面

通過單擊圖4的【過程查看】按鈕打開設(shè)計(jì)過程顯示界面(如圖5為案例執(zhí)行的過程數(shù)據(jù))。

圖5 設(shè)計(jì)過程顯示界面

3.2 功能設(shè)計(jì)

工具含測試輸入編輯、測試用例生成、測試信息維護(hù)和測試用例編輯功能，詳細(xì)設(shè)計(jì)如下：

1)測試輸入編輯功能。

實(shí)現(xiàn)被測對(duì)象原因、結(jié)果和因果表達(dá)式的輸入和編輯。在輸入編輯框(TextBox)對(duì)原因、結(jié)果和因果表達(dá)式的內(nèi)容進(jìn)行編輯，可對(duì)列表框(ListBox)中的內(nèi)容進(jìn)行追加、更新和刪除處理。

例如：輸入原因“投入2元硬幣”，單擊【追加】按鈕會(huì)自動(dòng)生成原因標(biāo)識(shí)C[n](n為原因編號(hào)值)，并以“C[n]：投入2元硬幣”的形式向列表框中追加一條數(shù)據(jù)。

2)測試用例生成功能。

測試用例生成功能是工具實(shí)現(xiàn)的核心，它由決策表數(shù)據(jù)結(jié)構(gòu)對(duì)應(yīng)的操作來完成，包含根據(jù)測試輸入初始化決策表、結(jié)果值設(shè)定、化簡(約束化簡和合并化簡)和測試用例生成。

3)測試信息維護(hù)功能。

設(shè)計(jì)圖4(a)的功能按鈕【用例導(dǎo)入】和【用例導(dǎo)出】單擊事件實(shí)現(xiàn)測試用例設(shè)計(jì)信息和結(jié)果信息的導(dǎo)入和導(dǎo)出。其中導(dǎo)出功能實(shí)現(xiàn)將界面中的信息保存于XML格式的文件中，保存的信息可用于后續(xù)測試用例的維護(hù)；導(dǎo)入功能實(shí)現(xiàn)將現(xiàn)存XML文件中的測試信息導(dǎo)入到界面，通過界面對(duì)測試信息進(jìn)行編輯，實(shí)現(xiàn)測試用例的維護(hù)。

XML文件中可保存含原因、結(jié)果、約束、關(guān)系和測試用例的相關(guān)數(shù)據(jù)，采用XML的文件格式保存測試信息，既便于測試用例的維護(hù)又方便測試用例數(shù)據(jù)在不同平臺(tái)間的傳送和呈現(xiàn)。其基本格式設(shè)計(jì)如下：

…

…

在根節(jié)點(diǎn)對(duì)之間包含,,,,這5組分類節(jié)點(diǎn)，對(duì)應(yīng)原因、結(jié)果、約束、關(guān)系和測試用例信息，其中原因、結(jié)果、約束和關(guān)系節(jié)點(diǎn)內(nèi)含由編號(hào)和內(nèi)容組成的多條數(shù)據(jù)記錄，測試用例節(jié)點(diǎn)內(nèi)含由編號(hào)、輸入原因和預(yù)期結(jié)果組成的多條數(shù)據(jù)記錄。

4)測試用例編輯功能。

考慮到采用任何測試用例設(shè)計(jì)方法設(shè)計(jì)的測試用例都是測試用例全集(窮舉測試)的子集，均需要人工進(jìn)行測試用例的補(bǔ)充設(shè)計(jì)，因此，圖4(b)除了用于呈現(xiàn)自動(dòng)生成的測試用例外，還設(shè)計(jì)了測試用例編輯功能，用于編輯人工追加的測試用例。

3.3 結(jié)果驗(yàn)證

在此，通過2個(gè)因果法的經(jīng)典案例來驗(yàn)證采用因果表達(dá)式算法的正確性。

案例2“自動(dòng)販賣機(jī)”軟件的測試用例設(shè)計(jì)

圖6(a)為設(shè)計(jì)輸入和測試用例生成界面，圖6(b)為設(shè)計(jì)過程顯示界面。

(a) 測試輸入和生成的測試用例

(b) 設(shè)計(jì)過程數(shù)據(jù)圖6 案例2驗(yàn)證結(jié)果

導(dǎo)出測試用例的XML文件如下(鑒于文件過長，省略了部分相似內(nèi)容)：

…

…

…

…

案例3“中國象棋中走馬”的測試用例設(shè)計(jì)

圖7(a)為設(shè)計(jì)輸入和測試用例生成界面，測試輸入編輯區(qū)因界面篇幅的原因，關(guān)系表達(dá)式未能全部顯示，關(guān)系ListBox的實(shí)際內(nèi)容如下：

R[1]：OR(C[1]，C[2]，C[3]，C[4])=E[1]

R[2]：AND(NEG(C[1])，NEG(C[2])，NEG(C[3])，NEG(C[4])，C[5])=E[2]

R[3]：AND(NEG(C[1])，NEG(C[2])，NEG(C[3])，NEG(C[4])，C[6])=(E[2]，E[3])

R[4]：AND(NEG(C[1])，NEG(C[2])，NEG(C[3])，NEG(C[4])，C[7])=(E[2]，E[4])

測試用例顯示及編輯區(qū)，工具設(shè)計(jì)考慮了案例描述方式的不同需求，這里與案例2不同，選勾了“全輸入描述”，輸入原因被全部描述，描述中用“√”代表原因成立，“×”代表原因不成立，“○”代表原因取任意值，圖7(b)為測試用例滾動(dòng)顯示結(jié)果。

圖7(c)為設(shè)計(jì)過程的部分?jǐn)?shù)據(jù)，由于案例3包含7個(gè)原因，因此初始決策表含128(27)條規(guī)則，界面中未能完全顯示，勾選“僅顯示有效規(guī)則”，結(jié)果如圖7(d)所示。

采用因果表達(dá)式的方法自動(dòng)生成的測試用例與人工采用傳統(tǒng)的因果圖法設(shè)計(jì)的結(jié)果一致。由于算法實(shí)現(xiàn)主要針對(duì)由原因組合而成的規(guī)則進(jìn)行處理，算法分析中通過對(duì)3原因8規(guī)則、4原因16規(guī)則、5原因32規(guī)則關(guān)系和約束類似的模擬被測對(duì)象進(jìn)行了測試用例設(shè)計(jì)，平均耗時(shí)分別為11.88 ms,16.18 ms,25.57 ms。假設(shè)一個(gè)單位時(shí)間(ms)執(zhí)行一次循環(huán)，設(shè)被測對(duì)象規(guī)則規(guī)模為n，可得該算法的時(shí)間復(fù)雜度T(n)為O(n)。

(a) 測試輸入和生成的測試用例

(b) 測試用例滾動(dòng)顯示結(jié)果

(c) 設(shè)計(jì)過程數(shù)據(jù)

(d) 設(shè)計(jì)過程數(shù)據(jù)的有效規(guī)則圖7 案例3驗(yàn)證結(jié)果

3.4 方法比較

采用因果表達(dá)式進(jìn)行測試用例設(shè)計(jì)與因果圖法具有同樣的結(jié)果，但采用因果表達(dá)式有以下優(yōu)勢(shì)：

1)采用因果表達(dá)式降低了設(shè)計(jì)難度。

采用因果表達(dá)式不用繪制因果圖，因此不用分析復(fù)雜條件組合的中間狀態(tài)，只需要書寫約束和關(guān)系表達(dá)式，減少了測試用例設(shè)計(jì)的工作量和設(shè)計(jì)難度。

作為對(duì)比，因果圖法較為繁瑣，中間狀態(tài)的分析及因果圖的繪制增加了測試用例設(shè)計(jì)人員的負(fù)擔(dān)，尤其是對(duì)較復(fù)雜的因果關(guān)系，設(shè)計(jì)難度較大。

2)采用因果表達(dá)式易于算法實(shí)現(xiàn)。

表達(dá)式由鍵盤符號(hào)構(gòu)成，便于向計(jì)算機(jī)輸入，通過對(duì)表達(dá)式進(jìn)行語法分析，采用基本數(shù)據(jù)類型就能實(shí)現(xiàn)測試用例設(shè)計(jì)。而因果圖輸入計(jì)算機(jī)困難，測試用例設(shè)計(jì)需要進(jìn)行圖的遍歷，需要自定義較復(fù)雜的數(shù)據(jù)類型來分析因果圖，算法實(shí)現(xiàn)難度較大。

3)采用因果表達(dá)式設(shè)計(jì)效率高。

因果表達(dá)式法易于向算法轉(zhuǎn)化，能實(shí)現(xiàn)測試用例自動(dòng)生成工具，實(shí)現(xiàn)含測試用例設(shè)計(jì)和維護(hù)全過程的自動(dòng)化，使測試用例設(shè)計(jì)和維護(hù)效率得以提高。

但迄今為止，還沒有基于因果圖法的、能實(shí)現(xiàn)測試用例設(shè)計(jì)全過程自動(dòng)化的工具，現(xiàn)有成果針對(duì)因果圖的部分操作尚需要人工完成，設(shè)計(jì)效率較低。

4 結(jié)束語

本文提出了一種因果圖法測試用例設(shè)計(jì)的改進(jìn)方法,把對(duì)圖的處理轉(zhuǎn)化為對(duì)由字符組成的因果表達(dá)式的處理，簡化了算法實(shí)現(xiàn)的復(fù)雜程度。將傳統(tǒng)的決策表采用數(shù)組型數(shù)據(jù)表來存儲(chǔ)，把對(duì)規(guī)則的化簡處理轉(zhuǎn)化為數(shù)組型數(shù)據(jù)的處理，給算法實(shí)現(xiàn)和數(shù)據(jù)呈現(xiàn)都帶來了方便。通過XML文件來存儲(chǔ)測試用例，既便于測試用例的維護(hù)，還能跨平臺(tái)使用數(shù)據(jù)，且可以定義不同的CSS樣式在不同平臺(tái)呈現(xiàn)數(shù)據(jù)。本文研究著眼于測試用例設(shè)計(jì)的自動(dòng)化技術(shù)，后續(xù)將在此基礎(chǔ)上針對(duì)多條件組合問題測試用例的自動(dòng)執(zhí)行進(jìn)行研究，以進(jìn)一步提高多條件組合問題的測試效率。

[1] 解筱夢(mèng). 面向云測試的并行測試用例自動(dòng)生成方法研究[D]. 上海:東華大學(xué)， 2015.

[2] Son H S, Kim W Y, Kim J S, et al. Automatic test case generation using multiple condition control flow graph[J]. Information Technology and Computer Science, 2012(13):105-109.

[3] 王敏,陳少敏,陳亞光. 基本路徑測試用例設(shè)計(jì)算法[J]. 計(jì)算機(jī)應(yīng)用, 2013,33(11):3262-3266.

[4] 張衛(wèi)祥,劉文紅. 基于故障樹分析與組合測試的測試用例生成方法[J]. 計(jì)算機(jī)科學(xué), 2014,41(S2):375-378.

[5] 宋蕾. 基于場景的測試用例自動(dòng)生成方法[J]. 計(jì)算機(jī)與數(shù)字工程, 2015,43(5):844-848.

[6] 王敏,陳亞光. 用于基本路徑測試的路徑字符串組合算法[J]. 計(jì)算工程與科學(xué), 2013,35(12):134-140.

[7] 王敏,王智超,余楊. 基于QTP的數(shù)據(jù)庫系統(tǒng)測試框架[J]. 計(jì)算機(jī)與數(shù)字工程, 2014,42(1):117-121.

[8] 王敏,張莉萍,王一平. 用于GUI軟件的測試工具[J]. 計(jì)算機(jī)與數(shù)字工程, 2014,42(2):346-350.

[9] Lemos O A L, Ferrari F C, Eler M M, et al. Evaluation studies of software testing research in the brazilian symposium on software engineering[C]// Proceedings of 2011 the 25th Brazilian Symposium on Software Engineering. 2011:56-65.

[10] 張偉,吳黎明. 基于因果圖的軟件自動(dòng)化測試方法研究[J]. 計(jì)算機(jī)與現(xiàn)代化, 2011(12):78-81.

[11] 張福源,楊云. 基于因果圖的軟件測試工具的研究與設(shè)計(jì)[J]. 計(jì)算機(jī)學(xué)報(bào), 1993(3):219-224.

[12] 韓堅(jiān)華. 一種化簡判定表的方法[J]. 計(jì)算機(jī)工程與應(yīng)用, 1995(4):36-40.

[13] Son H S, Kim R Y C, Park Y B. Test case generation from cause-effect graph based on model transformation[C]// 2014 International Conference on Information Science and Applications(ICISA). 2014:1891-1894.

[14] 毛養(yǎng)紅. 測試用例設(shè)計(jì)中的判定表自動(dòng)生成研究[J]. 無線互聯(lián)科技, 2015(16):114-115.

[15] 王江晴. 符號(hào)智能與計(jì)算智能[M]. 武漢:湖北科學(xué)技術(shù)出版社, 2002.

[16] 宮云戰(zhàn),趙瑞蓮,張威,等. 軟件測試教程[M]. 北京:機(jī)械工業(yè)出版社, 2016.