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

劉珊艷

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

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

劉珊艷

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

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

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

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

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

1 謂詞

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

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

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

2 謂詞約束

定義對整個謂詞的約束，該謂詞由布爾變量、關系表達式通過布爾運算符連接而成。對于測試用例t，如果Pr的各組件都滿足約束C中相應的約束，稱測試用例t滿足Pr上的約束C。謂詞上的約束C可有效指導測試集的設計，為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 生成充分性測試用例

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

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

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

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

首先，給出關于笛卡兒積的2個定義描述。

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

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

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

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

3.1生成BOR約束集

圖1 謂詞Pr的抽象語法樹

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

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

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

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

算法開始:

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

1)N是or結點：

2)N是and結點：

3)N是not結點：

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

算法結束。

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

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

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

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

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

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

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

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

圖2 謂詞Pr的BOR約束集

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

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

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

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

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

表1 燃氣報警器安全條件的謂詞BOR充分測試集對單/多布爾運算符故障的檢測能力

注：故障謂詞與安全條件謂詞的計算結果的差異用斜體加粗標識。

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

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

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

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

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

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

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

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

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

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

3.2生成BRO約束集

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

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只包含奇異表達式。

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

算法開始：

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

1)N是or結點：

2)N是and結點：

3)N是not結點

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

算法結束。

對于燃氣報警器安全情況下的謂詞Pr：gas

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

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

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

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

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

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

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

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

圖3 謂詞Pr的BRO約束集

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

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

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

表2 燃氣報警器安全條件的謂詞BRO充分測試集對單/多關系運算符故障的檢測能力

注：故障謂詞與安全條件謂詞的計算結果的差異用斜體加粗標識。

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

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

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

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

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

4 總結

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

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

[2] 孫昌愛,程慶順.基于故障的布爾表達式測試技術綜述[J].計算機科學,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的燃氣報器的建模與驗證[J].荊楚理工學院學報,2015,30(4):16-21.

(責任編輯高嵩)

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

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

劉珊艷，講師，碩士。

10.3969/j.issn.2095-4565.2017.04.008

TP312

：A

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