分支覆盖和MC/DC覆盖

分支覆盖

分支覆盖,即 Branch Coverage,是白盒测试中最常用的覆盖标准之一。对于一个被测程序 PP,分支覆盖准则要求 PP 中条件判断语句(如 ifcase 语句)的不同情况都被执行到,即都被执行出真和假。

MC/DC覆盖

MC/DC覆盖,即 Modified Condition/Deci
sion Coverage,是最严格的逻辑覆盖标准之一,通常应用于安全攸关领域的软件测试中。对于一个被测程序PP,它的条件判断语句称为 Decision(D)Decision(D),它可以包含一个或多个 Condition(C)Condition( C),即 D=C1...Ci...CnD=C_1\oplus...\oplus C_i\oplus...\oplus C_n 这里 \oplus 表示 \land
\lor,即逻辑与和逻辑或)。MC/DC测试标准要求被测程序 PP 同时满足以下四个条件

  • 程序 PP 的每个入口和出口都至少被执行过一次。
  • 程序P中的每个D都被执行出所有可能的结果,即真和假
  • 对于每个 CiDC_i\in D,它至少被执行出一次真和假。
  • 对于每个CiDC_i\in D,它能独立影响 DD 的结果,即通过固定所有除了 CiC_i 以外的变量的逻辑值,改变 CiC_i 本身的值,来判断 CiC_i 是否能独立影响 DD 的结果。具体来说,固定 Cj(ij)C_j(i\neq j) 的值,要求 D(C=ture)D(Ci=false)D(C=ture)\neq D(C_i= false)

示例程序 bubble.

图3.给出了一个函数bube,它来自于开源项目flex。图3.给出了它的程序控制流图。这个函数实现冒泡排序,即对给定的数组v的前n个元素进行升序排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define MAXLEN 6
void bubble(int v[MAXLEN], int n)
{
int i, j, k;
if(n >= MAXLEN)
return;
for(i = n; i > 1; --i)
for(j = 1; j < i; ++j)
/* compare */
if(v[j] > v[j+1])
{ /* exchange */
k = v[j];
v[j] = v[j+1];
v[j+1] = k;
}
}

覆盖结构

为了实现基于控制流覆盖准则的自动化测试,本节提出了基于覆盖结构(Coverage Structure, CS)的测试框架。其核心思想是,通过覆盖结构对各类控制流覆盖准则进行抽象,为以符号执行为基础的测试技术提供统一的接口。这样的设计能够有效地把符号执行技术与覆盖驱动測试两者结合在一起。与现有的测试方法相比,此测试框架能够

  • 将路径搜索策略与目标覆盖准则分离,为设计高效的路径搜索策略(即程序路径遍历算法)提供更高的自由度
  • 避免通过代码变换的方法实现覆盖测试,即把针对原始程序的目标覆盖测试转化为在变换后的程序上的覆盖测试(比如将原始程序的 MC/DC 覆盖测试转化为化简后程序的块覆盖测试),避免由此可能引入意想不到的副作用(如引入死代码);
  • 以覆盖驱动测试为目标,减少冗余测试用例的生成,降低符号执行的运行时间,提高单元测试的效率。

本节介绍的自动化测试框架基于覆盖结构,它由程序控制流图(control flowgraph)演化得到,并且可以支持大部分的控制流覆盖标准,如语句覆盖、分支覆
盖、条件覆盖、条件/判断覆盖、以及MC/DC覆盖。下面给出覆盖结构的定义。

定义

一个程序 PP 的控制流图 GG,是一个有向图;而覆盖结构 SS,是由被测程序 PP 的控制流图 GG,以及目标覆盖标准 CC 组成,即
S=(G,C,Eval,Cov)S=(G,C,Eval,Cov),这里:

  • 控制流图 GG 的定义与 CFGCFG 的定义一致。
  • EvalEval 是一个将 CFGCFG 节点映射为它所有可能的取值的数据结构。它记录了在程序执行过程中所有 CFGCFG 节点的取值。特别地,对于一个条件语句,它的取值是它的逻辑值,即 truetruefalsefalse;对于一个指令语句,当它被执行到,其取值为 truetrue:当它未被执行到,其取值为 falsefalse
  • CovCov 是一个函数。它根据目标覆盖准则 CC 和当前的 EvalEval,返回一系列新的被覆盖到的覆盖对象(coverage item)

事实上,针对目标覆盖准则 CC,这里只关心 GG 中特定的 CFGCFG 节点(比如,对于语句覆盖,关心指令语句;对于分支或者 MC/DC 覆盖,关心条件语句)。在覆盖结构 CSCS 中,把这些关心的节点,称为 CSCS 节点 或者 覆盖对象

以函数 bubble 为例,在分支测试下,其对应的覆盖结构有 4 个 CSCS 节点(位于第 5,7,8,10 行的条件语句)。当一个条件节点分别有 truetruefalsefalse
的取值时,CovCov 将把它对应的分支(即原始程序 PP 中的分支)标记为已覆盖。

又如下面这段程序为例:

$if((A \land B) \lor C) {s_1}\ else\ {s_2}; $

在 MC/DC 测试下,三个条件语句节点 A, B, C 是被关心对象。实际上,按照 MC/DC 的定义,至少需要如下的四个测试用例才能满足 MC/DC 覆盖准则:

  • (1) A = false, B = false, C = true,
  • (2) A = false, B = true, C = true,
  • (3) A = false, B = true, C = false,
  • (4) A = true, B = false, C = true,

在实际测试中,CovCov 通过计算 EvalEval 中各个条件语句的取值情况来判断对应的判断条件是否满足 MC/DC 充分性准则。因此,待测程序的覆盖情况是通过整个覆盖结构 CS 的覆盖情况进行判断的。