3-白盒测试-图论与结构化覆盖

控制流图

图的形式化定义

一个图 $G$ 定义如下：

$G = (V, E)$

• $V$：有限且非空的顶点集合。
• $E$：边的集合，边是顶点对。
• $V = \{v_1, v_2, v_3, v_4\}$
• $E = \{(v_1, v_2), (v_1, v_3), (v_2, v_4), (v_3, v_4)\}$
• $V_0$：初始顶点集合，$V_0 = \{v_1\}$
• $V_f$：终止顶点集合，$V_f = \{v_4\}$
• $V_0$ 和 $V_f$ 都是 $V$ 的子集。

路径

一个顶点序列。

序列中每一个相邻顶点都必须有一条边。

长度

边的数量

子路径

路径p中的一个顶点子序列

测试路径 Test Path

测试路径：从初始顶点开始，并且在终止顶点结束的一条路径。

Test Path: A path that starts at an initial vertex and ends at a final vertex.

图覆盖准则 Graph Coverage Criteria

既然程序、需求、设计图都可以抽象成图，那么测试时就可以要求测试路径覆盖图中的某些元素，例如：

• 顶点
• 边
• 路径

可达 Reach

如果存在一条从v1开始到v2结束的路径，则称 v1 can reach v2

$v_1$ 可以到达 $v_2$。

如果存在一条从 $v_1$ 开始、到图 $G'$ 中某个顶点结束的路径，那么称：

$v_1 \text{ can reach } G'$

即：

$v_1$ 可以到达子图 $G'$。

例子：

• $v_1$ 可以到达 $v_5$；
• $v_2$ 可以到达 $v_6$；
• $v_2$ 可以到达 $G'$。

其中：

$V' = \{v_4, v_5, v_6\}$

$E' = \{(v_4, v_5), (v_4, v_6)\}$

语法可达

只要图中存在一条路径，就叫语法可达。

语义可达

如果存在一个测试用例可以真正执行这条路径，就叫语义可达。

注意：语法上可达，但是语义上可能不可达。

覆盖 Cover

如果测试路径 p 包含顶点 v，则称 p covers v

如果测试路径 p 中包含边 e，则称 p covers e

图覆盖 Graph Coverage

1. 将软件建模为一个图；
2. 要求特定测试覆盖特定的顶点、边或者子路径集合。

先把程序、需求或设计抽象成图，然后规定测试路径必须覆盖图中的某些结构。

结构覆盖 Structural Coverage

结构覆盖只根据图中的顶点和边来定义。

图可以来自：

• 源代码
• 需求规格说明
• 设计图

这里的“结构”指的是图结构本身，例如节点、边、路径，而不考虑变量值、数据依赖等信息。

数据流覆盖 Data Flow Coverage

数据流覆盖要求图中额外标注变量相关信息。

测试准则 Test Criteria 和 测试需求 Test Requirements

测试需求描述测试路径应该满足的性质。

eg:

• 必须覆盖每个顶点；
• 必须覆盖每条边；
• 必须覆盖每条长度为 2 的子路径；

测试准则是定义测试需求的规则。

eg:

• 顶点覆盖准则会生成“覆盖每个可达顶点”的测试需求；
• 边覆盖准则会生成“覆盖每条可达边”的测试需求；
• 边对覆盖准则会生成“覆盖每条长度不超过 2 的可达路径”的测试需求；

满足 Satisfaction

给定某个准则 C 的测试需求集合 TR，如果对于 TR 中的每一个测试需求 tr，测试集合 T 执行出的路径集合 path(T) 中都存在一条测试路径满足它，那么称测试集合 T 在图上满足准则 C。

每一个测试需求，都要被至少一条测试路径满足。

结构化覆盖

顶点覆盖 Vertex Coverage

如果对于图 $G$ 中每一个语法可达的顶点 $v \in V$，测试集合 $T$ 执行出的路径集合 $path(T)$ 中都存在一条路径 $p$，使得 $p$ 覆盖 $v$，则称测试集合 $T$ 满足顶点覆盖。

边覆盖 Edge Coverage

如果对于图 $G$ 中每一条语法可达的边 $e \in E$，测试集合 $T$ 执行出的路径集合 $path(T)$ 中都存在一条路径 $p$，使得 $p$ 覆盖 $e$，则称测试集合 $T$ 满足边覆盖。

覆盖多条边 Covering Multiple Edges

边对覆盖要求覆盖边的组合，也就是连续两条边组成的路径。

完全路径覆盖 CPC Complete Path Coverage

TR（测试需求集合）包含图 G 中的所有路径。

n-路径覆盖 nPC n-Path Coverage

TR 包含图 G 中所有长度不超过 n 的可达路径（含长度 n）。

包含 / 蕴含 Subsume

如果准则 $C_1$ 包含准则 $C_2$，记作：

$C_1 \succeq C_2$

含义是：

对于任意测试集合 $T$，如果 $T$ 满足 $C_1$，则 $T$ 一定满足 $C_2$。

结构覆盖示例

代码覆盖 Code Coverage

代码覆盖包含：

• 代码覆盖；
• 控制流覆盖；
• 语句覆盖；
• 分支覆盖；
• 路径覆盖；
• 覆盖率收集工具，例如 EclEmma。

Soot

Soot 是一个可以为 Java 程序构造控制流图的工具。

基于 CFG 的覆盖：语句覆盖

CFG: Control Flow Graph

语句覆盖率表示：测试用例覆盖了多少比例的语句。

例如图中共有 5 条语句，测试执行了 4 条语句，那么：

$\text{SCov} = \frac{4}{5} = 80\%$

其中：

• SCov表示Statement Coverage语句覆盖率
• 分子是被执行的语句数
• 分母是总的语句数

基于 CFG 的覆盖：分支覆盖

分支覆盖率表示：测试用例覆盖了多少比例的分支。

对于每个分支条件，需要同时考虑

• true 分支
• false 分支

基于 CFG 的覆盖：路径覆盖

路径覆盖率表示：测试用例覆盖了多少比例的程序执行路径。

路径覆盖需要考虑所有可能的程序执行路径。

例如图中共有 4 条路径，测试覆盖了 1 条路径，那么：

$\text{PCov} = \frac{1}{4} = 25\%$

其中：

• PCov 表示Path Coverage路径覆盖率
• 分子是被执行的路径数
• 分母是所有可能路径数量

基于 CFG 的覆盖：比较

前面例子中的覆盖率为：

我们可以提出两个问题：

1. 如果达到 100% 分支覆盖，是否自动得到 100% 语句覆盖？
2. 如果达到 100% 路径覆盖，是否自动得到 100% 分支覆盖？

路径覆盖 ⇒ 分支覆盖 ⇒ 语句覆盖

答案是：

1. 100% 分支覆盖，得到 100% 语句覆盖。
2. 100% 路径覆盖，得到 100% 分支覆盖。

1. 100% 分支覆盖 ⇒ 100% 语句覆盖吗？

是

Branch Coverage 严格包含（strictly subsumes）Statement Coverage

如果一个测试套件达到 100% 分支覆盖，那么它一定达到 100% 语句覆盖。

原因：

1. 不在分支中的语句会被任意测试覆盖；
2. 其他语句都位于某个分支中；
3. 如果所有分支都被覆盖，那么这些分支中的语句也都会被执行。

但是反过来不一定成立。

2. 100% 路径覆盖 ⇒ 100% 分支覆盖吗？

是的，一般成立。

Path Coverage 严格包含（strictly subsumes）Branch Coverage

路径覆盖要求程序中所有可能的执行路径都至少走一遍。

而每个分支，比如：

if (x > 0) {
    a = 1;
} else {
    a = 2;
}

它的 True 分支和 False 分支都会出现在某些路径中。

所以如果你已经覆盖了所有路径，那么这些分支自然也都被覆盖了。

因此：

100% 路径覆盖 ⇒ 100% 分支覆盖

覆盖强度关系

可以记成：

路径覆盖 > 分支覆盖 > 语句覆盖

基于 CFG 的覆盖：有效性

大约 65% 的 bug 可以在单元测试中被发现。

单元测试主要由控制流测试方法主导。

在控制流测试中，语句测试和分支测试占主导地位。

也就是说，在实际工程中，语句覆盖和分支覆盖是最常见、最实用的代码覆盖指标。

基于 CFG 的覆盖：局限性

某方面达到 100% 覆盖率，永远不能保证软件没有 bug。

eg:

public int sum(int x, int y) {
    return x - y; // should be x + y
}

测试用例为：assertEquals(1, sum(1, 0));

这时，语句覆盖，分支覆盖和路径覆盖都为100%。但是仍然没有发现bug。

覆盖率只能说明代码被执行过，不代表测试断言足够强，也不代表程序逻辑一定正确。

覆盖率收集：机制

覆盖率收集通常通过插桩实现。

也就是说，可以在源代码层面或二进制层面对程序进行插桩。

插桩的做法是：在每个分支、语句等位置插入记录代码，用来把执行轨迹写入跟踪文件。

当插桩后的代码被执行时，覆盖率信息会被写入跟踪文件。

可以这么简单理解：

1. 先改造程序，在关键位置加入“记录执行情况”的代码；
2. 运行测试；
3. 根据记录文件统计哪些语句、分支、路径被执行过；
4. 计算覆盖率。

覆盖率收集：工具支持

常见覆盖率工具包括：

其中 JaCoCo 是 Java 中非常常见的覆盖率工具，EclEmma 是 Eclipse 中基于 JaCoCo 的覆盖率插件。

小结

主要讲了白盒测试中的图论基础和结构化覆盖：

1. 图可以表示程序、需求、设计等软件结构。
2. 路径、测试路径、可达性、覆盖 是图覆盖测试的基础概念。
3. 语法可达 只看图中是否存在路径；语义可达 要看是否真的有测试输入能执行该路径。
4. 顶点覆盖 VC 对应代码中的语句覆盖。
5. 边覆盖 EC 对应代码中的分支覆盖。
6. 边对覆盖 EPC 要求覆盖连续两条边组成的路径。
7. 完整路径覆盖 CPC 要求覆盖所有路径，但遇到循环时通常不可行。
8. 覆盖强弱关系： 路径覆盖 > 分支覆盖 > 语句覆盖
9. 但是，100% 覆盖率不等于没有 bug。覆盖率只能说明执行过，不能保证断言充分或逻辑正确。