：更改条件/判定覆盖(MC/DC)准则

Modified Condition/Decision Coverage (MC/DC)准则是一种软件结构覆盖测试准则，非常适用于国防、航空航天等大规模软件测试领域[1-2]。与语句覆盖、条件覆盖、决策覆盖相比，MC/DC可以大大减少测试用例的数量。例如，当测试系统中有10个判断条件时，条件组合覆盖需要1024个测试用例，而MC/DC只需要11个测试用例。约 20 个测试用例 [3-4]。在国内MC/DC最小测试用例集生成算法的相关研究中，最典型的是最小真值表法[5]和快速生成法[6]冗余测试是什么意思，但这两种算法只适用用于处理非耦合条件的布尔表达式。模式。一些学者还将MC/DC准则应用于弱耦合条件和强耦合条件的布尔表达式[7]。本文结合矩阵法，从布尔表达式的语法二叉树的叶子节点递归到根节点，直接生成完整的最小化测试用例集。

1 算法相关说明

布尔表达式相关概念： Condition 表示一个没有布尔运算符符号的布尔表达式，记为 Pi(1≤i≤n)。谓词表示由条件 Pi 和几个布尔运算符组成的布尔表达式。

MC/DC覆盖准则[8]：(1)程序中，每个入口点和出口点至少调用一次；(2)程序中确定的每个条件的所有值都出现在至少一次1次，并且可以独立影响判断的输出；(3)每个判断所有可能的输出结果至少产生一次。

Chilenski 原则[9]：对于具有 n 个条件的决策，至少有 n+1 组测试用例满足 MC/DC 准则。

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对的集合。当左右矩阵按照“矩阵组合逻辑运算规则”进行运算时，以和运算为例（或运算相同）。证明合理性，所以当右矩阵有多行结果为1时，只能选择一行进行运算。实际操作中，对结果为1的所有行进行操作，这样就可以得到一个完整的最小测试用例集），实际上，只有右矩阵中相同的一组条件被添加到 MC/DC 对中，而 MC/DC 对的数量保持不变。同理，右矩阵中的MC/DC对与左矩阵中结果为1的行进行运算后，将左矩阵中相同的一组条件加入到MC/DC对中, 并且 MC/DC 对的数量保持不变。然后将运算结果合并，此时构造左右子树中条件的MC/DC对，即构造子树的最小测试用例集。递归到根节点时，可以得到所有条件的MC/DC对，即语法二叉树的MC/DC最小测试用例集，验证完成。只有右矩阵中相同的一组条件被添加到 MC/DC 对中，MC/DC 对的数量保持不变。同理，右矩阵中的MC/DC对与左矩阵中结果为1的行进行运算后，将左矩阵中相同的一组条件加入到MC/DC对中, 并且 MC/DC 对的数量保持不变。然后将运算结果合并，此时构造左右子树中条件的MC/DC对，即构造子树的最小测试用例集。递归到根节点时，可以得到所有条件的MC/DC对，即语法二叉树的MC/DC最小测试用例集，验证完成。只有右矩阵中相同的一组条件被添加到 MC/DC 对中，MC/DC 对的数量保持不变。同理，右矩阵中的MC/DC对与左矩阵中结果为1的行进行运算后，将左矩阵中相同的一组条件加入到MC/DC对中, 并且 MC/DC 对的数量保持不变。然后将运算结果合并，此时构造左右子树中条件的MC/DC对，即构造子树的最小测试用例集。递归到根节点时，可以得到所有条件的MC/DC对，即语法二叉树的MC/DC最小测试用例集，验证完成。同理，右矩阵中的MC/DC对与左矩阵中结果为1的行进行运算后，将左矩阵中相同的一组条件加入到MC/DC对中, 并且 MC/DC 对的数量保持不变。然后将运算结果合并，此时构造左右子树中条件的MC/DC对，即构造子树的最小测试用例集。递归到根节点时，可以得到所有条件的MC/DC对，即语法二叉树的MC/DC最小测试用例集，验证完成。同理，右矩阵中的MC/DC对与左矩阵中结果为1的行进行运算后，将左矩阵中相同的一组条件加入到MC/DC对中, 并且 MC/DC 对的数量保持不变。然后将运算结果合并，此时构造左右子树中条件的MC/DC对，即构造子树的最小测试用例集。递归到根节点时，可以得到所有条件的MC/DC对，即语法二叉树的MC/DC最小测试用例集，验证完成。MC/DC 对的数量保持不变。然后将运算结果合并，此时构造左右子树中条件的MC/DC对，即构造子树的最小测试用例集。递归到根节点时，可以得到所有条件的MC/DC对，即语法二叉树的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（和算子）或0（或算子）的一行进行运算，就可以得到一个唯一的最小真值矩阵获得。可以证明判断只有这两个最小测试用例集，说明算法生成了一套完整的最小测试用例集，在不影响测试组大小范围的情况下，可以有效提高错误检测效率。同时，在进行矩阵组合逻辑运算时，任意选择左或右矩阵中结果为1（和算子）或0（或算子）的一行进行运算，就可以得到一个唯一的最小真值矩阵获得。可以证明判断只有这两个最小测试用例集，说明算法生成了一套完整的最小测试用例集，在不影响测试组大小范围的情况下，可以有效提高错误检测效率。同时，在进行矩阵组合逻辑运算时，任意选择左或右矩阵中结果为1（和算子）或0（或算子）的一行进行运算，就可以得到一个唯一的最小真值矩阵获得。

在自动生成唯一最小测试用例用于判断（零耦合条件）所需时间方面，算法首先生成一棵语法二叉树，然后从叶子节点递归到根节点。由于左右子树可以实现并发递归，对于左右子树对称且叶子节点较多的语法二叉树，所需时间优于快速生成算法，具有快速生成测试用例的优势。算法生成时间对比结果如表1所示，其中非布尔表达式为：(1)(P1or P2) and (P3and P4);(2)@ >(P1and P2and P3) or (P4and P5);(3)(P1and P2and P3) or (P4and (P5and P6)));(< @4)

最小真值表法和快速生成算法等算法只适用于处理由标准算子和，或组成的零耦合条件的判断，避免了对耦合条件判断的分析。该算法适用于具有耦合条件的判断分析。虽然在生成测试用例的过程中需要遍历语法二叉树进行验证，但是生成的测试用例集满足MC/DC的要求冗余测试是什么意思，遍历时只需要遍历部分子树。，所以数量远小于全遍历案例，对于分析耦合条件判断具有一定的参考意义。与谢向南等人的耦合条件MC/DC测试用例集生成算法比较。[7]，该算法相对简单直观，但对于复杂强耦合条件的分析，该算法仍有不足之处，需要进一步深入研究。

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 detectionstrength using combination testing[C].2017 IEEE International Conference on Software Quality, Reliability and Security Companion(QRS-C).布拉格，捷克： 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. 布尔表达式自动 MC/DC 测试用例生成的实用方法[C]。2015 年 IEEE 自动测试大会。美国马里兰州国家港口：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. 使用 MC/DC 作为黑盒测试技术 [C]。2017 IEEE 第 28 届年度软件技术会议 (STC)。美国医学博士盖瑟斯堡：IEEE，2017：25-28.

[13] 杨一文．一种自动化测试系统中I/O建模与约束提取的方法[M]. 北京：北京邮电大学，2014.

作者信息：

黄小伦、王冬

（重庆市卫生信息中心，重庆 401120)