劉珊艷

(荊楚理工學(xué)院 計算機工程學(xué)院,湖北 荊門 448000)

基于謂詞的系統(tǒng)需求測試用例生成方法研究

劉珊艷

(荊楚理工學(xué)院 計算機工程學(xué)院,湖北 荊門 448000)

軟件測試是保證軟件可靠性的主要方法,為了提高測試的質(zhì)量可以在需求分析階段對測試對象進(jìn)行分析，根據(jù)需求分析規(guī)則產(chǎn)生的謂詞常?？梢杂糜谲浖z測。討論基于謂詞的測試準(zhǔn)則BOR和BRO，并使用該準(zhǔn)則檢測需求規(guī)則中所有的布爾運算符故障和關(guān)系運算符故障。結(jié)果表明，根據(jù)謂詞信息生成的測試用例集合是最小的，且每個測試用例都能從不同方面暴露各種運算符故障，從而可以對軟件需求規(guī)則進(jìn)行充分地測試，提高軟件設(shè)計的準(zhǔn)確性。

軟件測試；謂詞；測試用例生成；測試充分性

隨著軟件系統(tǒng)規(guī)模和復(fù)雜性的增加，軟件測試的任務(wù)也變得越來越復(fù)雜與繁重。為了減少測試過程的盲目性，提高測試效率，在需求分析的開始階段就對測試任務(wù)進(jìn)行明確的分析，對測試目標(biāo)進(jìn)行有效的組織，同時準(zhǔn)確地記錄測試結(jié)果尤為重要。正如需求分析是軟件系統(tǒng)設(shè)計與實現(xiàn)的基礎(chǔ)，軟件測試也應(yīng)該以準(zhǔn)確而詳盡的測試需求分析為基礎(chǔ)[1]。

基于謂詞的測試可以在早期軟件需求完成后就進(jìn)行需求正確性的驗證。在軟件的需求文檔中會存在軟件設(shè)計所需遵守規(guī)則的說明，這些規(guī)則可以成為測試集設(shè)計的依據(jù)。編程人員可能對這些規(guī)則進(jìn)行正確的編碼，也可能沒有正確編碼，導(dǎo)致程序中存在缺陷。根據(jù)謂詞產(chǎn)生的測試用例，可以確保在測試中發(fā)現(xiàn)某種類型的所有缺陷，同時由于基于謂詞的軟件測試的關(guān)鍵問題是如何產(chǎn)生與選擇高效的測試用例集，即生成與選擇的測試用例集中測試用例的數(shù)量盡可能少，可以檢測盡可能多的故障類型[2]。為此，可以使用面向謂詞的測試用例生成準(zhǔn)則，從不同角度考慮設(shè)計出存在差異的測試用例，從而提高軟件的質(zhì)量。

1 謂詞

謂詞就是需求規(guī)則形式化的表示。例如，考慮軟件需求“若打印機處于ON狀態(tài)且具備打印紙，則發(fā)送要打印的文件”，這句話包含一個條件和一個動作。下面的謂詞，記為P表示這句話的條件部分。

P:(printerstatus=ON)∧(printertray!= empty)

一個條件可以表示成簡單謂詞或復(fù)合謂詞。簡單謂詞就是一個布爾變量或關(guān)系表達(dá)式(關(guān)系表達(dá)式通過集合{<,>,≤,≥,=,≠}中的一個關(guān)系運算符連接)，其中各變量可以取非(！)。復(fù)合謂詞可以是一個簡單謂詞，或是由若干簡單謂詞通過二元布爾運算符(∧,∨)連接起來的一個表達(dá)式。

2 謂詞約束

定義對整個謂詞的約束，該謂詞由布爾變量、關(guān)系表達(dá)式通過布爾運算符連接而成。對于測試用例t，如果Pr的各組件都滿足約束C中相應(yīng)的約束，稱測試用例t滿足Pr上的約束C。謂詞上的約束C可有效指導(dǎo)測試集的設(shè)計，為Pr中變量的取值提供了清晰的線索。約束條件還被用來動態(tài)地、啟發(fā)式地產(chǎn)生測試用例。

給定謂詞Pr的約束C，任意滿足C的測試用例將使Pr取值為true或false。用Pr(C)表示Pr對所有滿足約束C的測試用例的取值。將使得Pr(C)=true的約束C稱為“真”約束，而將使得Pr(C)=false的約束C稱為“假”約束。這樣，就將約束集合S劃分為2個子集St和Sf,有S=St∪Sf。其中，對于任意C∈St,有Pr(C)=true；對于C∈Sf，有Pr(C)=false。

3 生成充分性測試用例

我們最關(guān)心的是如何從給定的謂詞Pr生成測試集T，使其滿足：①T是最小集合；②T保證能夠檢測出Pr實現(xiàn)中存在的所有布爾運算符故障和關(guān)系運算符故障。為了獲取這樣的測試集，定義2個檢測布爾運算符的準(zhǔn)則，通常稱為BOR、BRO測試準(zhǔn)則[3-5]，名稱BOR、BRO分別對應(yīng)于布爾運算符、布爾關(guān)系運算符，2個準(zhǔn)則的形式化定義如下：

1)對于復(fù)合謂詞Pr，如果測試集T確保能夠檢測出Pr實現(xiàn)中存在的所有單/多布爾運算符故障，則T滿足BOR測試準(zhǔn)則，稱T為BOR充分測試集，記為TBOR。

2)對于復(fù)合謂詞Pr，如果測試集T確保能夠檢測出Pr實現(xiàn)中存在的所有單/多布爾運算符故障關(guān)系運算符故障，則T滿足BRO測試準(zhǔn)則，稱T為BRO充分測試集，記為TBRO。

設(shè)Tx為從謂詞Pr導(dǎo)出的測試集，其中x∈{BOR,BRO}。設(shè)Pf為通過向謂詞Pr注入單/多故障而得到的另一謂詞，注入的故障屬于布爾運算符故障、關(guān)系運算符故障。若存在t∈Tx，使得Pr(t)≠Pf(t)，則稱Tx確保能夠檢測出Pf中的故障。

首先，給出關(guān)于笛卡兒積的2個定義描述。

有限集合A和B的笛卡兒積記為A×B，定義如下:A×B={(a,b)|a∈A and b∈B}。

為了能生成最小的測試約束集，還需要另一種集合積的計算方法。集合的onto積(其運算符號記為?)定義如下：對于有限集合A和B，A?B為二元偶(u,v)構(gòu)成的最小集合，其中u∈A、v∈B，且A中的各個元素至少出現(xiàn)一次，B中的各個元素也至少出現(xiàn)一次。根據(jù)該定義，當(dāng)集合A、B包含2個或2個以上元素時，A?B的計算結(jié)果不是唯一的。

A?B={(u,v)|u∈A, v∈B, u 至少出現(xiàn)一次，v至少出現(xiàn)一次。}

下面給出檢測布爾運算符故障和關(guān)系運算符故障測試用例集的生成算法。

3.1生成BOR約束集

圖1 謂詞Pr的抽象語法樹

下面的算法用于生成BOR的約束集(CSET)。

由謂詞Pr的抽象語法樹生成最小BOR約束集的算法BOR-CSET。

輸入：謂詞Pr的抽象語法樹AST(Pr)。Pr只包含奇異表達(dá)式。

輸出：謂詞Pr的BOR約束集，放置在抽象語法樹AST(Pr)的根結(jié)點處。

算法開始:

步驟2:以自底向上的方式遍歷AST(Pr)的每個非葉結(jié)點(內(nèi)部結(jié)點)。如果結(jié)點N是一個and結(jié)點或or結(jié)點，設(shè)N1,N2是其直接后繼。如果結(jié)點N是一個not結(jié)點，設(shè)N1是其直接后繼。SN1,SN2分別代表結(jié)點N1,N2的BOR約束集。對每個非葉結(jié)點N，計算SN如下：

1)N是or結(jié)點：

2)N是and結(jié)點：

3)N是not結(jié)點：

步驟3:AST(Pr)根結(jié)點的BOR約束集就是謂詞Pr的BOR約束集。

算法結(jié)束。

使用燃?xì)鈭缶鬟@種對安全性要求較高的系統(tǒng)得到的需求說明進(jìn)行測試。燃?xì)鈭缶魇且环N氣體泄露檢測報警儀器。當(dāng)工業(yè)環(huán)境或家庭生活環(huán)境中燃?xì)鈿怏w泄露，燃?xì)鈭缶鳈z測到氣體濃度達(dá)到爆炸或中毒報警器設(shè)置的臨界點時，燃?xì)鈭缶骶蜁l(fā)出報警信號，以提醒工作人員采取安全措施。燃?xì)鈭缶飨到y(tǒng)是一種典型的實時系統(tǒng)，該系統(tǒng)為了保證安全性，不僅要求所產(chǎn)生的結(jié)果在邏輯上是正確的，而且要求執(zhí)行時間必須滿足規(guī)定的時間約束，任何動作出現(xiàn)時間上的延遲都會造成災(zāi)難性的后果。開發(fā)這類系統(tǒng)的成本較高，如果能夠在系統(tǒng)開發(fā)過程中越早發(fā)現(xiàn)問題，就可以避免很多人力物力資源的浪費[6]。我們在需求分析階段定義燃?xì)鈭缶靼踩珬l件的需求規(guī)則為：報警器在一個時間周期pertime內(nèi)探測空氣中燃?xì)獾臐舛龋籼綔y的值不高于標(biāo)準(zhǔn)值stdvalue，可以判定為安全，用謂詞Pr來表示安全條件，上述的燃?xì)鈭缶靼踩珬l件需求規(guī)則可以用謂詞Pr：gas

現(xiàn)在生成安全條件謂詞Pr的BOR約束集。

輸入：謂詞Pr的抽象語法樹AST(Pr)。

輸出：謂詞Pr的約束集，放置在抽象語法樹AST(Pr)的根結(jié)點。

首先根據(jù)各葉點的類型標(biāo)識其約束集如下：

然后自底向上，廣度優(yōu)先遍歷AST(Pr)，從其直接后繼結(jié)點的約束集計算各非葉結(jié)點的約束集。

SN3={(t,t),(f,t)(t,f)}。

得到謂詞Pr的BOR約束集如圖2所示(約束集放置在謂詞抽象語法樹的根結(jié)點旁)：

圖2 謂詞Pr的BOR約束集

根據(jù)圖2中謂詞Pr的BOR約束集，設(shè)計滿足以上3個BOR約束的測試集T1：

T1={t1∶,滿足(t,t)；t2∶，滿足(f,t)；t3∶,滿足(t,f)}。

說明：對于測試集T1中g(shù)as=stdvalue±1及time=pertime±1是指標(biāo)準(zhǔn)值加上或者減去一個很小的值，不代表具體的數(shù)。

由于T1滿足BOR測試準(zhǔn)則，從而確保能夠檢測出Pr中存在的所有單/多布爾運算符故障。通過針對測試集T1，計算Pr及其注入布爾運算符故障后得到的變體的真值，就能驗證這一點。

謂詞 Pr以及經(jīng)注入單/多布爾運算符故障后得到的7個故障謂詞見表1。對于每個謂詞，都使用T1中的3個測試用例分別進(jìn)行計算。

表1 燃?xì)鈭缶靼踩珬l件的謂詞BOR充分測試集對單/多布爾運算符故障的檢測能力

注：故障謂詞與安全條件謂詞的計算結(jié)果的差異用斜體加粗標(biāo)識。

1)驗證測試集合T1最小。

刪去測試用例t1，對于故障謂詞6剩余的測試用例t2、t3其執(zhí)行結(jié)果與正確謂詞Pr的預(yù)期結(jié)果相同，無法暴露錯誤。

刪去測試用例t2，對于故障謂詞5剩余的測試用例t1、t3其執(zhí)行結(jié)果與正確謂詞Pr的預(yù)期結(jié)果相同，無法暴露錯誤。

刪去測試用例t3，對于故障謂詞4剩余的測試用例t1、t2其執(zhí)行結(jié)果與正確謂詞Pr的預(yù)期結(jié)果相同，無法暴露錯誤。

綜上所述，如果從表中刪去任意一個測試用例，則至少存在一個故障謂詞對于剩余的2個測試用例，其真值與謂詞Pr的真值相同，故測試集合T1是最小的。

2)驗證測試集合T1能檢測出謂詞中所有布爾運算符故障。

從表1中可以得到，對于7種單/多布爾運算符故障，至少存在1個測試用例，能夠使其真值與正確謂詞Pr不同。

例如故障謂詞1，測試用例t2、t3均可發(fā)現(xiàn)錯誤。分別執(zhí)行測試用例t2、t3，預(yù)期結(jié)果分別是false、false，而實際的執(zhí)行結(jié)果卻是true、true，測試執(zhí)行結(jié)果與預(yù)期結(jié)果不同，暴露錯誤。

例如故障謂詞4，測試用例t3可發(fā)現(xiàn)錯誤。執(zhí)行測試用例t3，預(yù)期結(jié)果是false，而實際的執(zhí)行結(jié)果卻是true，測試執(zhí)行結(jié)果與預(yù)期結(jié)果不同，暴露錯誤。

因此，可以肯定，測試集T1最小且滿足BOR的充分性。

3.2生成BRO約束集

對于關(guān)系運算符連接的表達(dá)式e1 rel e2的BRO約束集S={(>),(=),(<)}。如下所述，根據(jù)rel的不同，S的“真”約束集、“假”約束集的劃分結(jié)果也不一樣：

rel為>∶St={(>)}，Sf={(=),(<)}；

rel為≥∶St={(>),(=)}，Sf={(<)};

rel為=∶St={{=}},Sf={(<),(>)}；

rel為<∶St={(<)}，Sf={(=),(>)};

rel為≤∶St={(<),(=)},Sf={(>)}。

現(xiàn)在，修改前面介紹的用于生成謂詞BOR約束集的算法BOR-CSET，以生成最小BRO約束集。修改后的算法如下：

輸入：謂詞Pr的抽象語法樹AST(Pr)。Pr只包含奇異表達(dá)式。

輸出：謂詞Pr的BRO約束集，放置在抽象語法樹AST(Pr)的根結(jié)點處。

算法開始：

步驟2:以自底向上的方式遍歷AST(Pr)的每個非葉結(jié)點(內(nèi)部結(jié)點)。如果結(jié)點N是一個and結(jié)點或or結(jié)點，設(shè)N1,N2是其直接后繼。如果結(jié)點N是一個not結(jié)點，設(shè)N1是其直接后繼。SN1,SN2分別代表結(jié)點N1、N2的BRO約束集。對每個非葉結(jié)點N，計算SN如下：

1)N是or結(jié)點：

2)N是and結(jié)點：

3)N是not結(jié)點

步驟3:AST(Pr)根結(jié)點的BOR約束集就是謂詞Pr的BOR約束集。

算法結(jié)束。

對于燃?xì)鈭缶靼踩闆r下的謂詞Pr：gas

首先根據(jù)各葉點的類型標(biāo)識其BRO約束集如下：

然后自底向上，廣度優(yōu)先遍歷AST(pr)，從其直接后繼結(jié)點的BRO約束集計算各非葉結(jié)點的BRO約束集如下：

={(<)}?{(<),(=)}

={(<,<),(<,=)}；

=({(>),(=)}×{(<)})∪({(<)}×{(>)})

={(>,<),(=,<),(<,>)}；

SN3={(<,<),(<,=),(>,<),(=,<),(<,>)}。

得到謂詞Pr的BOR約束集如圖3所示(約束集放置在謂詞抽象語法樹的根結(jié)點旁)。

圖3 謂詞Pr的BRO約束集

根據(jù)得到謂詞Pr的BRO約束集，設(shè)計滿足以上5個BRO約束的測試集T2：

T2={t1∶，滿足(<,<)；t2∶,滿足(<,=)；t3∶，滿足(>,<)；t4∶,滿足(=,<);t5∶,滿足(<,>)}。 T2集合中的t1，t3，t5與T1中的t1，t3，t2的測試用例完全相同，故測試集T2?T1。由于T1滿足BOR測試準(zhǔn)則，能夠檢測出Pr中存在的所有單/多布爾運算符故障，所以針對測試集T2，可以省略計算Pr及其注入布爾運算符故障后得到的變體的真值，只需計算關(guān)系運算符故障和組合故障來驗證測試集對BRO測試準(zhǔn)則的充分性。

謂詞Pr以及經(jīng)注入單/多關(guān)系運算符故障后得到的10個故障謂詞見表2。對于每個謂詞，都使用T2中的5個測試用例分別進(jìn)行計算。

表2 燃?xì)鈭缶靼踩珬l件的謂詞BRO充分測試集對單/多關(guān)系運算符故障的檢測能力

注：故障謂詞與安全條件謂詞的計算結(jié)果的差異用斜體加粗標(biāo)識。

驗證測試集合T1能檢測出謂詞中所有布爾運算符故障。

從表2中可以得到，對于10個故障謂詞，至少存在一個測試用例，使其執(zhí)行結(jié)果與正確謂詞Pr的執(zhí)行結(jié)果不同。

例如故障謂詞1，測試用例t1，t2，t3均可發(fā)現(xiàn)錯誤。分別執(zhí)行測試用例t1，t2，t3，預(yù)期結(jié)果分別是true，ture，false，而實際的執(zhí)行結(jié)果卻是false，false，true，測試執(zhí)行結(jié)果與預(yù)期結(jié)果不同，暴露錯誤。

例如故障謂詞8，測試用例t5可發(fā)現(xiàn)錯誤。執(zhí)行測試用例t5，預(yù)期結(jié)果是false，而實際的執(zhí)行結(jié)果卻是true，測試執(zhí)行結(jié)果與預(yù)期結(jié)果不同，暴露錯誤。

因此，可以肯定，測試集T2針對BRO測試準(zhǔn)則是充分的。

4 總結(jié)

本文討論使用謂詞對軟件的需求規(guī)則進(jìn)行測試的方法，并根據(jù)該方法生成充分的測試用例集。為說明該方法的有效性，使用該方法對燃?xì)鈭缶鬟@種安全性要求較高的系統(tǒng)需求進(jìn)行測試。定義燃?xì)鈭缶飨到y(tǒng)需求安全條件的謂詞，生成該謂詞的BOR充分測試集及BRO充分測試集，并驗證安全條件謂詞的BOR測試集是充分檢測出所有布爾運算符故障的最小集合，也驗證了安全條件謂詞的BRO測試集合的充分性?；谥^詞的測試方法在提高測試效率的同時，保證了測試的充分性，是一種進(jìn)行軟件測試的有效方法。

[1] 楊波,吳際,徐珞,等.一種軟件測試需求建模及測試用例生成方法[J].計算機學(xué)報,2014,37(3):522-538.

[2] 孫昌愛,程慶順.基于故障的布爾表達(dá)式測試技術(shù)綜述[J].計算機科學(xué),2013,40(3):16-23.

[3] Burnim J,Sen K.Heuristics for scalable dynamic test generation[C].IEEE/ACM Internation Conference on Automated Software Engineering,2008:443-446.

[4] Tai KC.Predicate-based test generation for computer programs[C].International Conference on Software Engineering,2002:267-276.

[5] Ball T.A Theory of Predicate-Complete Test Coverage and Generation[C].International Conference on Formal Methods for Components and Objects,2004:1-22.

[6] 劉珊艷.基于UPPAAL的燃?xì)鈭笃鞯慕Ｅc驗證[J].荊楚理工學(xué)院學(xué)報,2015,30(4):16-21.

(責(zé)任編輯高嵩)

Generating Test Case for System Requirement Based on Predicate

LiuShanyan

(Department of Computer Engineering,Jingchu University of Technology,Jingmen Hubei 448000)

For the sake of improving the test quality,Software testing,a main method of guaranteeing the software reliability,can be carried out in the stage of software analysis.Predicates,generated on the basis of the rules of the analysis,tend to be applicable to the testing.The paper,on the one hand,probes into BOR and BRO based on the predicate test criteria,on the other hand it exploits the criteria in the detection of all the malfunctions of the Boolean operators and the relational operators in the rules of analysis.The results indicate that the aggregate of the test case generated by the predicate information is minimal,and that each test case tends to expose the various faults of operators from different aspects.Thus,the paper suggests that the analysis rule can be tested fully for the purpose of raising the accuracy of the software design.

software testing;predicate;test case generation;test adequacy

2017-03-22

荊楚理工學(xué)院校級科學(xué)研究項目(項目編號：ZR201311)。

劉珊艷，講師，碩士。

10.3969/j.issn.2095-4565.2017.04.008

TP312

：A

：2095-4565(2017)04-0039-06