0 引言

更改条件/判定覆盖(MC/DC)准则是一种软件结构覆盖性测试准则，非常适合大型的软件测试领域，如国防、航空航天领域^[1-2]。MC/DC与语句覆盖、条件覆盖、判定覆盖等比较，能大幅减少测试用例数，如测试系统中有10个判定条件时，条件组合覆盖需要1 024个测试用例，而MC/DC只需要11~20个测试用例^[3-4]。在国内MC/DC最小测试用例集生成算法的相关研究中，比较典型的是最小真值表法^[5]和快速生成法^[6]，但这两种算法只适合处理非耦合条件的布尔表达式。也有学者将MC/DC准则应用于带弱耦合条件和强耦合条件的布尔表达式中^[7]。本文结合矩阵方式，从布尔表达式的语法二叉树的叶子节点依次递归至根节点，直接生成完备的最小化测试用例集。

1 算法相关描述

布尔表达式相关概念：条件表示不含有布尔操作符号的布尔表达式，记为P_i(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)所示：

语法二叉树：将一个判定从左到右依次转化为对应的语法二叉树，其中条件P_i采用叶子节点表示，and、or等逻辑运算符采用非叶子节点表示。以(P₁and P₂)and(P₃or P₄)为例，其对应的语法二叉树如图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 带耦合条件的判定的验证

带耦合条件的判定是指判定中存在部分重复条件。以(P₁and P₂and P₃) or (P₁and (P₂and P₄))为例，条件P₁、P₂重复出现(判定中重复出现的条件采用P₁′、P₂′表示)。按照算法步骤先转化为语法二叉树，如图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₁or P₂) and (P₃and P₄)；(2)(P₁and P₂and P₃) or (P₄and P₅)；(3)(P₁and P₂and P₃) or (P₄and (P₅and P₆))；(4)(P₁and P₂and (P₃or P₄)) or (P₅and (P₆and P₇or P₈))。但是，本算法需要存储空间存储矩阵，其对存储空间的要求高于快速生成算法。

最小真值表法、快速生成算法等算法只适合处理由标准运算符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)