测试预言问题

简单说，测试预言就是测试的预期答案，它体现出来被测单元的的预期功能。它将程序的输入输出映射到由成功和失败组成的集合当中。

例如，我们可以在一个栈的单元测试中检查它的 pop() 功能：

public static void testPop(){
    Stack<Integer> s = new Stack<Integer>();
    int a = 2;
    s.push(a);
    s.pop();

    boolean empty = s.isEmpty();
    assert (empty); //[!code error]
}

我们可以形式化定义测试预言，即给定一次测试 $T=\{P,I\}$，其中 $P$ 和 $I$ 分别表示待测程序和测试输入，而对应的输出 $O$ 满足 $O=P(I)$。给定预期的输出 $O^{\ast }$，则测试预言为 $\tau :O\cong O\ast$，其中 $\cong$ 表示符合某种关系。如果 $\tau$ 能满足，那么称本次测试通过。

测试预言分为显式测试预言和隐式测试预言。显式测试预言指有具体的代码执行对测试预言的检测，而隐式测试预言通过某些能够引发程序崩溃的缺陷来检测。

预言问题

预言问题指给定系统的输入（约束和期望），如何找到能够正确辨别出符合期望的正确行为与发现潜在的不正确行为测试预言的挑战性难题。

由于系统的文档通常使用自然预言来编写，所以存在二义性的问题，难以直接生成测试预言；此外软件是动态变化的，因为网络或多并发等问题可能会导致测试预言的情况繁多。总之，当下的测试预言问题现状即为：复杂的预言难以构建，但容易构建的测试预言效果又较差。

蜕变测试

蜕变测试是一种基于规则的生成测试用例的新思路。它可以通过测试输入和预期输出之间的关系来进一步利用成功的测试用例，即对成功测试用例表现出的必要属性进行复用。

最短路的例子

例如，给定了一个实现了无向图 $G$ 中最短路径算法 $f$ 的程序 $P$，以及两个节点 $a$ 和 $b$。这就是测试的输入。我们发现，图中必然满足

$$|f(G,b,a)|=|f(G,a,b)|$$

那么，测试输入和预期输出之间也应当满足

$$|P(G,b,a)|=|P(G,a,b)|$$

这一关系。假设我们已经有若干个测试集，我们就可以利用这一关系生成更多的测试用例。即使没有相应的测试用例，我们也可以根据这一性质进行检验。即蜕变测试在测试预言存在和不存在的情况下都可以应用。

在蜕变测试中，测试输入序列 $\{x_1,x_2,\cdots ,x_n\}$ 和预期输出 $(f(x_1),f(x_2),\cdots ,f(x_n))$ 之间的一些必要属性叫做蜕变关系 $\mathcal{R}$，它是一个 $X^n\times Y^n$ 的笛卡尔积。经常，测试输入序列中的 $x_1,x_2,\cdots ,x_j$ 是原始给定的测试输入，叫做原输入；$x_j+1,\cdots ,x_n$ 是原输入根据蜕变关系 $\mathcal{R}$ 的闭包额外生成补全的测试输入，叫做后续输入。整个蜕变集合即测试输入集合构成的集合。

差分测试

差分测试通过向一系列类似的应用程序（或同一应用程序的不同实现）提供相同的输入，根据这些相似程序执行结果是否存在差异来判定是否检测到缺陷。显然，如果存在差异，说明其中至少有一个程序存在缺陷。

编译器的测试

在同一 C 标准下，编译产物应当是等价的机器码（假设无 UB）。因此，在开发一款新的 C 编译器时，可以和多个已验证的编译器同时运行某个程序，随后便进行编译和运行，给各个程序相同的输入，检查其输出是否相同。如果新的编译器与原有编译器存在不相同之处，则说明某处存在着缺陷。

形式化来说，差分测试首先要确定一组相似的待测程序 $\mathbb{P}=\{P_1,P_2,\cdots ,P_n\}$，其中，对于任意的 $P_i,P_j\in \mathbb{P}$ 都满足 $P_i$ 与 $P_j$ 相近似。在此基础上，生成一组测试输入 $\mathbb{I}=\{I_1,I_2,\cdots ,I_m\}$。之后检测对于存在 $1\le i,j\le n,1\le k\le m$，$P_i(I_k)=P_j(I_k)$ 不成立，那么说明 $P_i$ 和 $P_j$ 至少有一个程序存在缺陷。

此外， 差分测试还可以同模糊测试结合，提供测试输入的生成方法。