MCDC最小测试用例集递归分块矩阵生成算法①.PDF

2011 年 第 20 卷 第 7 期 计 算 机 系 统 应 用 MC/DC 最小测试用例集递归分块矩阵生成算法① 葛汉强 (重庆信息技术职业学院 软件学院 重庆 404000) 摘 要：测试用例个数可以影响软件测试的成本与效率，因此最小测试用例集的生成算法具有重要的实用价值。 对布尔表达式语法树采用递归分块矩阵处理，得到了 MC/DC 最小测试用例集生成算法。并证明了该算法的正确 性，给出其成立的前提条件。 关键词：MC/DC ；最小测试用例集；递归分块矩阵；生成算法 Generating Algorithm of Recursive Blocks Matrix for Minimum Test Case Set on MC/DC GE Han-Qiang (College of Software, Chongqing Information Technology College, Chongqing 404000, China) Abstract: The quantity of the test suite affects the cost and efficiency of software testing, so it is important to generate an algorithm of minimum test case set. According to studying syntactic tree of Boolean expressions on recursive blocks matrix, an algorithm for minimum test case set on MC/DC is proposed. Its correctness is proved in theory and its premise is considered. Key words: MC/DC; minimum test case set; recursive blocks matrix; generating algorithm 1 引言 原则，对真值表矩阵中的“确定项”反转得到 MC/DC 软件测试的一个核心主题就是构造精简高效的测 最小测试用例集。 试用例集。MC/DC 即修正条件判定覆盖是白盒测试逻 辑覆盖法中的一种，是由欧美的航空/航天制造厂商和 2 生成算法 使用单位联合制定的“航空运输和装备系统软件认证 2.1 算法相关概念 标准”，与白盒测试其他逻辑覆盖相比，MC/DC 覆盖 定义 1. 设 B 是一布尔表达式，p ，p ，…，p 为 1 2 n 强度高于语句、判定和条件覆盖，覆盖范围大于条件 B 中 n 个分量记为 p (1≤i ≤n)称为 B 的条件，当 p 每 i i [4] 判定组合覆盖，测试性能接近多条件覆盖，但测试用 个只出现一次则称 B 为非平凡布尔表达式 。 例数却是线性增加远小于多条件覆盖的指数级增加， 定义 2. 在 B 中各条件分量仅由OR，AND ，NOT 符合精简高效的原则，在国防、航空航天