《電子技術應用》
您所在的位置:首頁 > 測試測量 > 設計應用 > 采用矩陣遞歸的最小測試用例集生成算法
采用矩陣遞歸的最小測試用例集生成算法
2020年電子技術應用第4期
黃孝倫,王 東
重慶市衛生信息中心,重慶401120
摘要: 符合MC/DC準則的最小測試用例集算法具有重要的實用價值。首先將布爾表達式轉換為語法二叉樹,然后采用矩陣組合邏輯運算方法逐層遞歸,從而獲得完備的MC/DC最小測試用例集。經驗證,矩陣組合邏輯運算方法是合理的、正確的。該方法對于非平凡布爾表達式可快速獲取完備的MC/DC最小測試用例集,同時也可以處理帶耦合條件的復雜布爾表達式。
中圖分類號: TN06;TP301.6
文獻標識碼: A
DOI:10.16157/j.issn.0258-7998.191029
中文引用格式: 黃孝倫,王東. 采用矩陣遞歸的最小測試用例集生成算法[J].電子技術應用,2020,46(4):71-74.
英文引用格式: Huang Xiaolun,Wang Dong. Algorithm of minimum test case set generation using matrix recursion[J]. Application of Electronic Technique,2020,46(4):71-74.
Algorithm of minimum test case set generation using matrix recursion
Huang Xiaolun,Wang Dong
Chongqing Health Information Center,Chongqing 401120,China
Abstract: The algorithm of minimum test case set conforming to MC/DC criterion has important practical value.Firstly,the Boolean expression is transformed into a syntax binary tree,and then the matrix combinational logic operation is used to recurse layer by layer to obtain a complete set of MC/DC minimum test cases.It is proved that the method of matrix combinational logic operation is reasonable and correct.The method can quickly obtain complete MC/DC minimum test case set for nontrivial Boolean expressions,and can also deal with complex Boolean expressions with coupling conditions.
Key words : MC/DC;test cases;coupling conditions;recursion;algorithms

0 引言

    更改條件/判定覆蓋(MC/DC)準則是一種軟件結構覆蓋性測試準則,非常適合大型的軟件測試領域,如國防、航空航天領域[1-2]。MC/DC與語句覆蓋、條件覆蓋、判定覆蓋等比較,能大幅減少測試用例數,如測試系統中有10個判定條件時,條件組合覆蓋需要1 024個測試用例,而MC/DC只需要11~20個測試用例[3-4]。在國內MC/DC最小測試用例集生成算法的相關研究中,比較典型的是最小真值表法[5]和快速生成法[6],但這兩種算法只適合處理非耦合條件的布爾表達式。也有學者將MC/DC準則應用于帶弱耦合條件和強耦合條件的布爾表達式中[7]。本文結合矩陣方式,從布爾表達式的語法二叉樹的葉子節點依次遞歸至根節點,直接生成完備的最小化測試用例集。

1 算法相關描述

    布爾表達式相關概念:條件表示不含有布爾操作符號的布爾表達式,記為Pi(1≤i≤n)。判定表示由條件Pi和若干布爾操作符號所組成的一個布爾表達式。

    MC/DC覆蓋準則[8]:(1)程序中,每個入口點和出口點至少被調用1次;(2)程序中判定的每個條件的所有取值至少出現1次,且能獨立影響該判定的輸出;(3)每一個判定的所有可能的輸出結果至少產生1次。

    Chilenski原則[9]:對于一個具有n個條件的判定,滿足MC/DC準則的測試用例至少有n+1組。

    MC/DC對[10]:一個MC/DC對是一對真值向量,該向量中一個條件值變化時可使得判定有不同的結果。

jsj2-gs1-s1.gif

    矩陣組合邏輯運算規則:將矩陣的條件部分進行兩兩組合,同時將結果部分按邏輯運算符進行邏輯運算,如式(1)所示:

jsj2-gs1.gif

    語法二叉樹:將一個判定從左到右依次轉化為對應的語法二叉樹,其中條件Pi采用葉子節點表示,and、or等邏輯運算符采用非葉子節點表示。以(P1 and P2)and(P3 or P4)為例,其對應的語法二叉樹如圖1所示。

jsj2-t1.gif

jsj2-t1-x1.gif

    語法二叉樹遞歸規則:從葉子節點開始往根節點逐層遞歸。左、右子樹為葉子節點時,按“語法二叉樹與矩陣對應關系”獲得對應矩陣。若某一子樹的左子樹或右子樹為非葉子節點時,利用該子樹的左、右矩陣,按“矩陣組合邏輯運算規則”進行運算:若為and運算,先將左矩陣中每一行與右矩陣中結果為1的行進行運算,然后將右矩陣中每一行與左矩陣中結果為1的行進行運算,最后合并運算結果;如為or運算時,選取相應矩陣中結果為0的行進行運算。運算結果即為該子樹對應的判定的最小測試用例集。遞歸到根節點時,即獲得整個判定的最小測試用例集。

    命題  按語法二叉樹遞歸規則可得到MC/DC最小測試用例集。

    證明  以n表示語法二叉樹的高度,當n=2時,左、右子樹為葉子節點,可直接獲得判定的矩陣,即最小測試用例集,結論成立。當n>2時,由于該子樹的左、右矩陣符合Chilenski原則,因此左、右矩陣的行集合其實就是MC/DC對集合。左、右矩陣按“矩陣組合邏輯運算規則”運算時,以and運算為例(or運算同理),左矩陣中MC/DC對分別與右矩陣中結果為1的行進行運算(此處只證明合理性,因此右矩陣中有多個結果為1的行時,只選取其中一行運算即可。實際操作時,結果為1的行均進行運算,這樣可獲得完備的最小測試用例集),實際上只是在該MC/DC對中增加了右矩陣中的同一組條件,MC/DC對數量不變。同樣原理,將右矩陣中MC/DC對與左矩陣中結果為1的行進行運算后,該MC/DC對中增加了左矩陣中的同一組條件,MC/DC對數量不變。然后合并運算結果,此時針對左、右子樹中條件的MC/DC對構造完畢,即該子樹的最小測試用例集構造完畢。遞歸至根節點時,就可獲得針對全部條件的MC/DC對,即該語法二叉樹的MC/DC最小測試用例集,證畢。

2 算法設計與驗證

2.1 算法步驟

    按照上述規則及定義,MC/CD最小測試用例集的生成算法步驟如下:

    (1)將判定轉換為語法二叉樹;

    (2)從葉子節點開始,按“語法二叉樹遞歸規則”向根節點逐層遞歸,遞歸過程按“語法二叉樹與矩陣對應關系”采用矩陣表示子樹,并按“矩陣組合邏輯運算規則”進行運算獲得子樹對應的矩陣;

    (3)遞歸至語法二叉樹的根節點時,算法結束。

2.2 算法驗證

2.2.1 零耦合條件的判定的驗證

jsj2-2.2.1-x1.gif

jsj2-2.2.1-x2.gif

2.2.2 帶耦合條件的判定的驗證

    帶耦合條件的判定是指判定中存在部分重復條件。以(P1 and P2 and P3) or (P1 and (P2 and P4))為例,條件P1、P2重復出現(判定中重復出現的條件采用P1′、P2′表示)。按照算法步驟先轉化為語法二叉樹,如圖2所示。

jsj2-t2.gif

jsj2-t2-x1.gif

jsj2-t2-x2.gif

    在處理帶耦合條件的判定時,在2.1算法步驟中增加兩個規則:(1)一致性規則。在遞歸過程中遇到重復條件時,為保證重復條件取值的一致性,在矩陣中選擇重復條件取值一致的MC/DC對進行運算。(2)構造規則。為了保證一致性,矩陣中MC/DC對數量受到了限制,不能滿足Chilenski原則,因此需要通過構造方式來滿足該原則。以左矩陣中與重復條件相關的MC/DC對為基礎,補充構造右矩陣中條件,構造時需遍歷相應子樹進行正確性驗證。構造完右矩陣中條件對應的MC/DC對后,在其基礎上反轉非重復條件,構造左矩陣中的MC/DC對。

3 實驗分析

    最小真值表法、快速生成算法等算法都是依據判定中的多種條件不斷進行判斷、歸約,從而依次生成每個用例。本算法從語法二叉樹的葉子端向根節點遞歸,每次遞歸得到的都是當前子樹的MC/DC最小測試用例集,其測試用例集始終限制在最小維度,而且遞歸過程只需進行簡單的矩陣組合邏輯運算,因此,在手動生成測試用例方面更快速、簡潔、直觀。最小真值表法、快速生成算法等算法只能獲得唯一一個最小測試用例集,無法得到其余的最小測試用例集。保證冗余的測試用例是有必要的[12]。在2.2.1的驗證中,本算法同時生成了兩個最小測試用例集,可以證明該判定有且僅有這兩個最小測試用例集,這表明本算法生成了完備的最小測試用例集,其可在不影響測試組大小范圍的情況下有效提高錯誤檢測效率。同時,在進行矩陣組合邏輯運算時,任意選取左或右矩陣中結果為1(and運算符)或0(or運算符)的一行進行運算,即可獲得唯一的最小真值矩陣。

    在判定(零耦合條件)的唯一最小測試用例的自動生成所需時間方面,本算法首先生成語法二叉樹,然后由葉子節點向根節點進行遞歸,由于左、右子樹可以實現并發遞歸,因此對于左、右子樹較對稱的、葉子節點較多的語法二叉樹而言,其所需的時間優于快速生成算法,具有快速生成測試用例的優勢。算法生成時間比較結果見表1,其中非布爾表達式分別為:(1)(P1 or P2) and (P3 and P4);(2)(P1 and P2 and P3) or (P4 and P5);(3)(P1 and P2 and P3) or (P4 and (P5 and P6));(4)(P1 and P2 and (P3 or P4)) or (P5 and (P6 and P7 or P8))。但是,本算法需要存儲空間存儲矩陣,其對存儲空間的要求高于快速生成算法。

jsj2-b1.gif

    最小真值表法、快速生成算法等算法只適合處理由標準運算符and、or構成的零耦合條件的判定,規避了對帶耦合條件的判定的分析。本算法適用于存在耦合條件的判定的分析,其在生成測試用例過程中雖需要遍歷語法二叉樹進行驗證,但生成的測試用例集滿足MC/DC要求,且遍歷時只需對部分子樹進行遍歷,因此數量遠小于全遍歷情況,對帶耦合條件的判定的分析具有一定借鑒意義。與謝祥南等[7]的耦合條件的MC/DC測試用例集生成算法相比,本算法比較簡潔直觀,但對于復雜的強耦合條件的判定的分析,本算法還有不足,需要進一步深入研究。

4 結論

    不同測試工具對于代碼的覆蓋能力是有區別的,通常能夠支持MC/DC的測試工具的價格極其昂貴[13]。本文提出的算法基于語法二叉樹,從葉子節點開始采用符合MC/DC覆蓋準則的矩陣進行遞歸,可快速、直觀、有效地處理零耦合條件的判定,并生成完備的的最小測試用例集,適合自動或手動生成。對于帶耦合條件的復雜判定,本算法也有一定適用性,其生成的測試用例集合遠遠低于全遍歷情況,這在減輕測試工程師工作量、提高工作效率方面有一定借鑒意義。下一步將對帶耦合條件的判定做進一步研究,提高其算法的生成效率。

參考文獻

[1] 朱少民.全程軟件測試(3版)[M].北京:人民郵電出版社,2019:130-132.

[2] 王吉茂,尹平.軟件測試用例執行優化研究[J].計算機工程與設計,2013,12(1):4242-4246.

[3] 王瑞,田宇立,周東紅,等.面向故障定位的基于MC/DC的測試用例約簡方法[J].計算機科學,2015,42(10):170-174.

[4] DONG L,LINGHUAN H,RUIZHI G.Improving MC/DC and fault detection strength using combinatorial testing[C].2017 IEEE International Conference on Software Quality,Reliability and Security Companion(QRS-C).Prague,Czech Republic:IEEE,2017:84-88.

[5] 朱曉波,楊偉民,葉芯.更改條件/判定覆蓋最小真值表生成算法及其應用[J].上海理工大學學報,2007,29(1):84-88.

[6] 段飛雷,吳曉,張凡,等.MC/DC最小測試用例集快速生成算法[J].計算機工程,2009,35(17):40-45.

[7] 謝祥南,魏延棟.耦合條件的MC/DC測試用例集生成算法[J].計算機系統應用,2017,26(6):164-169.

[8] 黃孝倫.基于圖的MC/DC最小測試用例集快速生成算法[J].計算機系統應用,2012,21(11):145-147.

[9] SEKOU K,ALEXIS T,MIHAELA B.Practical methods for automatic MC/DC test case generation of Boolean expressions[C].2015 IEEE Autotestcon.National Harbor,MD,USA:IEEE,2015.

[10] 周睿.基于Java編譯器的MC/DC測試覆蓋方法設計[J].軟件導刊,2016,15(8):39-41.

[11] 袁軍.基于MC/DC最小測試用例集設計方法研究[J].航空電子技術,2010,41(3):51-54.

[12] VILKOMIR S,BAPTISTA J,DAS G.Using MC/DC as a black-box testing technique[C].2017 IEEE 28th Annual Software Technology Conference(STC).Gaithersburg,MD,USA:IEEE,2017:25-28.

[13] 楊憶文.一種自動化測試系統中為I/O建模及約束提取的方法[M].北京:北京郵電大學,2014.



作者信息:

黃孝倫,王  東

(重慶市衛生信息中心,重慶401120)

此內容為AET網站原創,未經授權禁止轉載。
二分彩一期精准计划