更改條件/判定覆蓋(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對是一對真值向量，該向量中一個條件值變化時可使得判定有不同的結果。
矩陣組合邏輯運算規則：將矩陣的條件部分進行兩兩組合，同時將結果部分按邏輯運算符進行邏輯運算，如式(1)所示：
語法二叉樹：將一個判定從左到右依次轉化為對應的語法二叉樹，其中條件Pi採用葉子節點表示，and、or等邏輯運算符采用非葉子節點表示。以(P1and P2)and(P3or P4)為例，其對應的語法二叉樹如圖1所示。
語法二叉樹遞歸規則：從葉子節點開始往根節點逐層遞歸。左、右子樹為葉子節點時，按“語法二叉樹與矩陣對應關係”獲得對應矩陣。若某一子樹的左子樹或右子樹為非葉子節點時，利用該子樹的左、右矩陣，按“矩陣組合邏輯運算規則”進行運算：若為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 零耦合條件的判定的驗證
2.2.2 帶耦合條件的判定的驗證
帶耦合條件的判定是指判定中存在部分重複條件。以(P1and P2and P3) or (P1and (P2and P4))為例，條件P1、P2 重複出現(判定中重複出現的條件採用P1′、P2′表示)。按照算法步驟先轉化為語法二叉樹，如圖2所示。
在處理帶耦合條件的判定時，在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)(P
1or P2) and (P3and P4)；(2)(P1and P2and P3) or (P4and P5)；(3)(P1and P2and P3) or (P4and (P5and P6))；(4)(P1and P2and (P3or P4)) or (P5and (P6and P7or P8))。但是，本算法需要存儲空間存儲矩陣，其對存儲空間的要求高於快速生成算法。
最小真值表法、快速生成算法等算法只適合處理由標準運算符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)
閱讀更多 電子技術應用 的文章
