利用代码覆盖率提升模糊测试结果

大家好， 我是 Lars Opstad，MSEC 科学组的工程经理，负责支持微软内部的 SDL（安全开发生命周期）。我想与大家分享我们在改进内部安全实践方面的一些方法，特别是在文件模糊测试领域。

许多模糊测试工具以良好文件（模板）为起点来创建畸形内容。自 2002 年《编写安全代码》出版以来，SDL 多年来一直鼓励人们使用“具有代表性的良好模板集”来模糊测试文件解析器。问题是“如何判断我是否拥有一个好的集合？”在微软，我们的答案是代码覆盖率，这与外部其他研究一致（仅举几例：Guruswami、Miller 和 Sutton，Greene 和 Amini）。

代码覆盖率定义

在深入讨论如何将代码覆盖率用于模糊测试之前，我应该简要定义这些术语。如果您对这些概念很熟悉，可以跳过直接阅读“使用覆盖率进行更好的模糊测试”。

代码覆盖率是根据一组测试或输入来衡量代码集被锻炼程度的指标。最简单的代码覆盖率方案是在函数级别。函数覆盖率测量哪些函数被调用，哪些函数未被调用。虽然这在非常广泛的层面上有用，但它并没有真正提供测量文件解析器有意义覆盖率所需的粒度。更好的指标是“块”覆盖率。在覆盖率术语中，基本块是一段始终按顺序执行、没有跳入或跳出的代码。以下面的代码示例为例：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

x+=1; // 块 1
y+=2;
if(
sin(x)
< // 块 2（虽然在块 3 之后执行）
sin(y) ) // 块 3
{ // 块 4
y+=1;
result=true;
}
else // 块 5
{
result=false;
}
x+=1; // 块 6
return result;

对于上面的示例，有两个主要的覆盖率情况，取决于 sin(x)<sin(y) 是否成立。如果成立，覆盖的块将是（按执行顺序）1、3、2、4、6（不包括 5）。如果不成立，覆盖的块将是 1、3、2、5、6（不包括 4）。要实现完全覆盖，这两种情况都是必需的。

在更详细的分析中，还有其他覆盖率概念可能有用，但就本文而言，这奠定了良好的基础。

有许多免费和商业可用的覆盖率工具（包括 Visual Studio 内置的一个，在此描述），可以提供这类信息。本文的重点不是任何特定工具，而是使用这些测量来提高文件模糊测试的有效性。

使用覆盖率进行更好的模糊测试

我们使用覆盖率进行模糊测试的第一个目标仅仅是评估模板集的整体完整性。这是通过测量每个模板在应用程序中运行并计算解析器代码的整体块覆盖率来实现的。这个练习最重要的部分是在覆盖率太低（例如低于 60%）时执行差距分析。通过差距分析，团队可以找到或构建额外的模板来锻炼剩余的代码。例如，对于标准的 RIFF 格式，可能所有模板都缺少某种类型的标签。有了这些知识，该组件的所有者可以轻松找到或生成包含缺失记录类型的文件，并适当增加覆盖率。

在这方面做了一些工作后，我们意识到许多模板文件覆盖的代码块几乎完全相同。模糊测试其中一个模板与模糊测试任何其他类似模板大致等效。我们希望能够增加命中较少使用代码部分的机会，基于一个基本假设：错误在测试较少的代码部分中更为常见。因此，我们希望减少重复，并选择最少数量的模板，同时仍能提供与我们完整原始集等效的覆盖率。

基于覆盖率的模板优化技术细节

我们用于选择优化模板集的算法称为贪心算法，其前提是选择最佳匹配，然后是次佳匹配，依此类推。在这个特定情况下，以下是我们算法的伪代码（在收集了每个模板的覆盖率之后）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

while (FullTemplateList.count>0)
{
    Template candidate=null;
    foreach (Template t in FullTemplateList)
    {
        if (candidate==null || t.BlocksCovered>candidate.BlocksCovered)
        {
            candidate=t;
        }
    }
    FullTemplateList.Remove(candidate);
    OptimalTemplateList.Add(candidate);
    // 从其他模板的覆盖率中排除候选模板覆盖的块
    foreach (Template t in FullTemplateList)
    {
        t.CoverageMask = t.CoverageMask & ~candidate.CoverageMask;
        t.BlocksCovered=t.CoverageMask.BlocksSet();
        if (t.BlocksCovered == 0)
        {
            FullTemplateList.Remove(t);
        }
    }
}

为了说明这个算法，假设您测量了七个输入文件的覆盖率，得到了以下掩码：

完整模板列表：

模板 A: ■■■■■■■■■■ (10 块) 模板 B: ■■■■■■■■■■ (6 块) 模板 C: ■■■■■■■■■■ (5 块) 模板 D: ■■■■■■■■■■ (4 块) 模板 E: ■■■■■■■■■■ (3 块) 模板 F: ■■■■■■■■■■ (2 块) 模板 G: ■■■■■■■■■■ (1 块)

从这个列表中的最佳选择是模板 B，覆盖了六个块。经过一次循环迭代后，列表将如下所示（灰色块表示原始模板中已被优化模板列表覆盖的块）：

优化模板列表： 模板 B: ■■■■■■

完整模板列表（剩余）： 模板 A: □□□□□□□□□□ (4 块) 模板 C: □□□□□□□□□□ (3 块) 模板 D: □□□□□□□□□□ (2 块) 模板 F: □□□□□□□□□□ (1 块)

已移除： 模板 E: □□□□□□□□□□ (0 块) 模板 G: □□□□□□□□□□ (0 块)

最终，这将导致优化模板列表中有四个模板： 模板 B: ■■■■■■ 模板 C: ■■■■■ 模板 A: ■■■■ 模板 D: ■■■

模板优化的结果

基于覆盖率的模板优化首次在微软用于 Windows Vista 的开发过程中。应用上述算法显著减少了覆盖文件解析器所需的模板数量。在检查由 MSHTML.DLL（用于 Internet Explorer）解析的 90,000 个 JPG 文件时，我们确定了不到 100 个文件，它们提供了与所有 90,000 个文件相同的覆盖率。因此，发现仅由一个模板覆盖的代码块附近问题的几率增加了 900 倍。

在调查一个 MSRC 案例时，MSRC 工程部的 Gavin Thomas 使用模板优化来查看一小部分优化模板集与正常大型模板集相比的效果。在这个测试中，他使用了两个不同的变异模糊测试器，每个运行了 500,000 次迭代。优化集的问题数量对于任一模糊测试器都几乎翻倍：

模糊测试器 A：

• 完整集：12 个问题
• 优化集：23 个问题

模糊测试器 B：

• 完整集：15 个问题
• 优化集：28 个问题

结论

代码覆盖率只是改进模糊测试过程的一种方法。虽然它不能保证您会找到产品中的所有错误，但它增加了您的模糊测试器到达较少锻炼代码部分的概率，因为您减少了锻炼更常见代码块的时间。MSEC 鼓励软件开发团队使用这种技术来最大化其模糊测试的效果。

感谢 Adel Abouchaev 和 Michael Levin 对算法的改进，Gavin Thomas 和 Andy Renk 进行实验验证有效性，Michael Howard 提供历史视角，以及 Damian Hasse 和 Matt Miller 进行技术审查。

谢谢， Lars Opstad, MSEC 科学组