通过在线学习进行模版引导的混合执行测试( 二 ) _模版引导

文章插图

其中 ∗ 表示一个任意字符。混合执行测试的目标是产生这样的输入以驱动程序执行能够运行到错误位置。
但是，由于搜索空间巨大，常规的混合执行测试不太可能触发错误。为了到达错误位置，程序执行必须成功执行第 5 行和第 9 行。为此，混合执行测试最初用随机输入运行程序，同时用符号输入执行程序。

文章插图

文章插图

在执行过程中，符号变量(α1, ... , α8)的约束条件被收集起来，并用于生成下一个输入。例如，当初始执行按照第 4 行的条件语句为真的分支和第 7、11 行的条件语句为假的分支去执行时，以下的约束条件会被收集。

文章插图

例如，否定最后一个连接条件，将产生使程序执行到第 7 行的第一个条件语句为真的分支的输入。然后，假设新的输入不满足第 7 行的第二个条件，将新生成以下路径条件。

文章插图

再次否定最后一个连接的条件，混合执行测试成功到达第 8 行条件语句之前的程序位置。但在这个点，它仍然需要探索一个巨大的搜索空间来生成满足条件(!strncmp(...))的输入：因为 strncmp 的主体不可用，符号变量 α7 和 α8 是不受限制的。因此，最后两个字符'du'一定是被偶然的生成且生成概率太低，鉴于从程序入口到第 8 行已经存在多条(更确切的来说，9 条) 。
我们的模板引导的混合执行测试旨在有效和自动地减少搜索空间。在混合执行测试过程中，我们的技术会自适应地生成模板，这些模版通过有选择地引入符号变量从而被用来限制输入空间。例如，当它被应用到图 1 中的程序中时，我们的技术会自动生成以下模板来限制搜索空间。

文章插图

也就是说，除了最后两个输入值之外，所有的输入值都由具体的值固定下来，这样，混合执行测试就不再无谓地试图探索无法到达第 8 行的那些执行路径。换句话说，我们的技术能够强制执行到达错误位置的必要条件，使得混合执行测试能够专注于分别生成 α7 和 α8 的输入'd'和'u' 。通过该模板，混合执行测试能够更有效地生成能够触发错误的输入，比传统方法在示例程序中的速度快 9 倍。
2.2 模板引导下的在线学习混合执行测试图 2 说明了我们的技术在用于执行混合执行测试同时在线自动生成模板。我们的技术能够在不需要任何事先的领域知识的情况下生成有效的模板。该算法重复以下五个过程，直到给定的测试预算用完。

文章插图
【通过在线学习进行模版引导的混合执行测试】
2.2.1 常规的混合执行测试。我们首先执行常规的混合执行测试(无模板)，以生成一组有效的测试用例。如果一个测试用例能够在混合执行测试过程中行使之前未覆盖到的分支，我们就说它是有效的。我们在一定时间内运行混合执行测试，收集有效的测试用例。例如，当我们对图 1 中的示例程序运行几分钟的混合执行测试时，我们可以收集到超过 40000 个有效的测试用例，例如以下的测试用例：

文章插图

2.2.2 序列模式挖掘。一旦收集到有效测试用例的数据集，我们就会尝试捕捉这些输入向量中的共同模式。具体来说，我们的目标是提取有效测试用例中经常出现的部分字符序列。为此我们使用了一种最新的序列模式挖掘算法，它从上一阶段收集到的 40000 个测试用例中找出以下四种模式：

文章插图

例如，模式 P1 表示有效测试用例很可能依次包含字符'-'、'X'、'-' 。
2.2.3 模式排序。在通过序列模式挖掘生成候选模式后，我们选择最有可能最大化独特分支覆盖范围的前 k 种模式；该覆盖范围的计算方法是常规的混合执行测试没有发现的分支数量。在我们的例子中为了快速覆盖独特分支（例如图 1 中第 8 行的判断为真的分支），需要使用图 2 中的模式 P3 。然而，在候选者中精确定位有效模式是不容易的，因为在现实程序上运行算法通常会发现成千上万的模式。更糟糕的是，只有一小部分候选模式对增加分支覆盖范围是有效的。我们通过根据之前运行中评估的类似模式的有效性对候选模式进行排名来解决这一挑战。我们在算法过程中积累了一些好的和坏的模式集合，利用它们来估计新生成的模式的有效性。对于示例程序，当 k=2 时，我们选择 P3 和 P2 这两种候选模式。