环绕正则表达式：从模糊测试正则表达式库中学到的经验（第一部分）

好的，如果你正在阅读本文，你可能已经知道模糊测试是什么。作为一个极其简化的总结：模糊测试是一种自动化的随机测试过程，试图探索被测程序（PUT；有时也称为SUT、DUT等）的状态空间（例如，对输入或行为的不同解释）。由于其固有的随机性，模糊测试通常被认为是在程序中发现错误的最有效方法之一，这种随机性违背了人类的期望或偏见¹。在其30多年的存在中，该策略已经发现了无数安全关键错误（想想数万或数十万），但仍然面临来自工业界和学术界的定期怀疑。

本文将讨论的错误不是安全关键的。下面描述的目标和错误反而作为模糊测试设计决策的研究，并理解模糊测试失败的地方。我认为这对于在安全和非安全环境中考虑模糊测试的人可能有用。如果有任何解释不清或不正确的地方，请联系我，我将很乐意进行更正、添加链接或必要的解释。

在这篇博客文章中，我将讨论对两个非常不同的正则表达式库进行模糊测试。对于每个库，我将详细介绍如何为这些目标设计模糊器，使用模糊器对这些目标进行测试，分析和报告错误，以及将模糊器作为自动化回归测试工具进行维护。

目标

好的，我们今天的PUT是：

rust-lang/regex
PCRE2

我们为每个目标开发了独立的差分模糊测试工具，这些工具依赖于每个程序的特定保证。

边栏：什么是正则表达式？

如果你编写过任何处理字符串操作的程序，你几乎肯定遇到过正则表达式（RegEx，或简称regex）库。正则表达式有多种形式，从正式定义到许多现代实现，比如这里讨论的两个。现代正则表达式的"风味"通常包括原始正式定义中未描述的生活质量特性或扩展功能，因此实际上代表了更大的形式构造（例如，我相当确信PCRE2能够编码比上下文无关文法更高的东西）。

这些库的目的在定义上是简单的：提供一种可以定义模式以搜索文本的语言。它们的实现很少如此简单，主要有两个原因：

用户要求使用表达性强的模式来搜索文本。这些库必须提供许多不同的策略，以便用户可以有效地搜索和提取文本中的细节。
文本搜索通常是文本处理程序中的热点路径。任何正则表达式的实现都必须极其高效地处理任何合理模式的文本。

我不会在这里概述正则表达式的编写和使用，因为这与本文的其余部分大多无关。对于感兴趣的人，你可以在这里找到常见功能的概述。

目标1：rust-lang/regex

regex crate（以下简称rust-regex）是整个Rust生态系统中使用最广泛的crate之一。由于其扩展的Unicode支持，其语法可能比其他一些引擎更复杂，但显著地将自己限制为常规语言。与大多数其他正则表达式库不同，rust-regex提供了中等复杂度的保证，因此在一定程度上抵抗某些恶意输入。

我在一段时间前（>2年）对rust-regex进行了模糊测试，但下面是我如何处理该软件的简要总结。

分析现有工具

模糊测试工具（在大多数情况下）只是一个接受输入并在目标中运行它的函数。最终，从用户的角度来看，模糊测试过程可以这样理解：

模糊器运行时启动
运行时产生一些输入
使用新输入运行工具；如果输入导致崩溃，停止
运行时了解你的程序的某些信息以生成更好的输入
转到步骤2

因此，为了非常明确，我们将模糊器描述为执行模糊测试的整个程序，将模糊器运行时描述为生成输入和分析程序行为的代码（通常不由用户实现），将工具描述为用户代码，通过调用PUT实际体现测试。拥有差的模糊器运行时意味着你的程序不会被很好地测试。拥有差的工具意味着运行时产生的输入可能实际上不会测试程序的太多部分，或者可能不会非常有效地测试它。

由于我们不想制作自定义模糊器运行时，只想测试程序，让我们专注于改进工具。

当我开始研究rust-regex时，它已经在OSS-Fuzz中。这意味着可能已经在目标上执行了数千个CPU年的模糊测试。在这里，我们将讨论两种发现新错误的方法：更好的输入和更多检测错误的方法。这两种方法都直接受到如何利用PUT的影响。

以下是我最初看到的rust-regex工具。该工具通过将第一个字节解释为长度字段，然后使用它来确定将输入的其余部分分割为搜索模式和"干草堆"（要搜索的文本）的位置。

索引	含义
0	长度字段
[1, 1 + data[0] % (len(data) - 1))	搜索模式
[1 + data[0] % (len(data) - 1), len(data))	干草堆

而且，这有效；几年来，这个模糊器在实践中使用并发现了几个错误。但这个工具有一些问题，其中最大的问题是：数据重解释优于变异。

深入探究

遗憾的是，模糊器不是神奇的bug打印机。这里使用的模糊器运行时是libFuzzer，它执行随机字节变异，并且对被测程序没有基本理解。事实上，模糊器真正考虑区分不同输入效果的唯一事情是程序的覆盖率²。当生成输入时，只有当程序表现出新的覆盖率时，它才被认为是有趣的（因此被保留）。

此外，输入不是简单地由libFuzzer生成的。它们而是变异的结果——修改现有输入以获得新输入的过程。让我们将之前描述的循环分解为更细的步骤（粗体为编辑部分）：

模糊器运行时启动
运行时从语料库（保留的输入集）中选择一些现有输入；如果没有可用，生成一个并转到4
运行时变异输入
使用新输入运行工具；如果输入导致崩溃，停止
运行时检查最后一次运行的覆盖率；如果输入导致探索了新的代码区域，将其添加到语料库
转到步骤2

理解变异

关于使用变异进行模糊测试的一个基本假设是，变异的输入与其基于的输入相似，但在有趣的方式上不同。但是，相似是什么意思？有趣地不同是什么意思？

通常，我们希望探索PUT解释输入的各种方式。我们不能³神奇地生成到达我们之前未探索过的地方的输入。相反，我们需要通过缓慢地逐步探索程序。

考虑模糊测试中的一个经典演示程序（伪代码）：

1
2
3
4
5
6
7
8
9


if (len(data) >= 1 && data[0] == 'a') {
 if (len(data) >= 2 && data[1] == 'b') {
  if (len(data) >= 3 && data[2] == 'c') {
   if (len(data) >= 4 && data[3] == 'd') {
    // bug!
   }
  }
 }
}

假设我们想命中说"bug!“的那一行。我们需要向程序提供一个以abcd开头的输入。如果我们简单地生成随机字符串，产生这样一个字符串的几率最多是1 in 2^32——大约1 in 40亿。不是最好的几率。

覆盖率引导模糊测试的承诺是，通过变异，我们缓慢地探索程序，从而将问题分解为单独的、更容易生成的子问题。假设我们的运行时只应用随机产生编辑距离为1的输入的变异。现在，当我们变异我们的输入时，从小开始，我们可以一次猜中每个1 in 256字节，我们的运行时将逐步探索程序，并在解决这一系列较小的子问题后到达说"bug!“的那一行。

数据重解释问题

让我们稍微重写我们的工具，以更代表rust-regex工具。

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


if (len(input) <= 1) {
 return;
}
data = input[1..];
offset = input[0] % len(data);
if (len(data) + offset >= 1 && data[offset] == 'a') {
 if (len(data) + offset >= 2 && data[offset + 1] == 'b') {
  if (len(data) + offset >= 3 && data[offset + 2] == 'c') {
   if (len(data) + offset >= 4 && data[offset + 3] == 'd') {
    // bug!
   }
  }
 }
}

这个程序与原始问题完全相同的"难度”；我们设置input[0] = 0和input[1..]为原始工具的解决方案。除了，对于覆盖率引导的模糊器，这个问题难度大了几个数量级（鼓励读者尝试！）。让我们看看这个程序在变异过程中的行为；为清晰起见，原始字节（如偏移字段）将写为[x]，其中x是该字节中的值。

从一些随机生成的输入开始：

1
2
3
4
5
6


[123]c
  ^  ^
  |  |
  |  + 第一个字节
  |
  + 偏移字段；offset = 123 % len(input[1..]) = 123 % 1 = 0

这个输入被保留，因为我们在前几行有新的覆盖率，但我们还没有进入嵌套的if。然后，我们变异它直到找到新的覆盖率：

1
2
3
4
5
6


[123]a
  ^  ^
  |  |
  |  + 第一个字节（通过我们的检查！）
  |
  + 偏移字段；offset = 123 % len(input[1..]) = 123 % 1 = 0

太好了！我们已经命中了嵌套块中的第一个if。不幸的是，编辑距离为1，我们现在永远无法触发错误。假设我们幸运地产生了一个b，这在历史上现在会通过第二个条件：

1
2
3
4
5
6
7
8


[123]ab
  ^  ^^
  |  ||
  |  |+ 第一个字节（未能通过第一个检查）
  |  |
  |  + 被偏移跳过
  |
  + 偏移字段；offset = 123 % len(input[1..]) = 123 % 2 = 1

由于偏移现在由于长度的变化被程序重新解释，从程序的角度来看，输入实际上与原始输入不相似。即使假设我们幸运地得到了一个a，结果程序的覆盖率不会比第一个变异的输入有所改善，因此不会被保留。如果我们将偏移更改为零，那么我们不会获得新的覆盖率，因为我们仍然只有一个a。编辑距离为1，我们根本无法从该输入产生任何新的覆盖率。

这个数据重解释问题在OSS-Fuzz工具中普遍存在，减轻由此引起的问题是改进现有工具的一个很好的起点。虽然在实践中，变异的编辑距离非常大，但重解释产生的随机性有效地将我们完全带回到随机生成（因为我们几乎保证通过几乎所有模糊器使用的havoc变异引起重解释）。在rust-regex中，这种重解释问题的后果是，当输入很小（如模糊器通常优化的）或当第一个字节被变异时，正则表达式被疯狂地重新解释。此外，模式实际上永远不能超过255字节（！）。

重新设计工具

好的，我们知道现有工具有一些问题。让我们重新设计工具，通过结构上定义输入来清晰分割"模式"和"干草堆”。我们可以使用方便的arbitrary crate来定义对任意字节的解析器，将输入转换为格式良好的模式和干草堆。这反过来通过使arbitrary充当输入中位的解释器，并使变异对arbitrary⁴定义的解析器所做的决策产生直接影响，从而有效地使变异直接影响决策。作为用户，这简单、直接，并使输入更加"有意义"；我们现在知道输入中的字节代表一个有意义的模式。

你可以在作者合并的更改中找到这些更改；更改1，更改2。

我们解决了重解释问题吗？

插曲：语法模糊测试与字节模糊测试

考虑一下JSON解析器。JSON是一种非常明确的结构化语言，积极拒绝格式错误的输入。然而，没有JSON格式意识的字节级变异模糊器可以通过探索程序空间产生格式良好的JSON输入。也就是说，大多数产生的变异会显著破坏JSON输入（例如，在{“hello”:“world”}中，变异为{“hel"o”:“world”}会立即使JSON解析器拒绝输入）。这限制了字节级变异模糊器产生有趣输入以测试JSON解释器背后代码的能力。

考虑我们之前示例的以下呈现：

1
2
3
4
5


obj = JSON.loads(input); // 在JSON中有很多覆盖率要探索！

if (obj.a == 'a') {
  // bug!
}

我们的字节级变异模糊器将尝试找到尽可能多的代码覆盖率——并且大部分会在JSON步骤中迷失方向。假设我们"聪明"并告诉模糊器神奇地忽略JSON中的覆盖率；现在，模糊器几乎肯定永远不会产生甚至有效的JSON输入。结果，我们永远不会命中"bug!"。

但是，假设我们编写了一个arbitrary实现，能够将我们的变异模糊器产生的随机字节解释为具有名为"a"的字段的有效对象，然后序列化它并将其交给PUT。现在，我们有效地保证能够产生命中"bug!“的输入，前提是我们的变异器足够聪明，能够弄清楚如何将字符串"a"放入该字段。

当然，变异器会轻松做到这一点，对吧？

数据重解释：重装上阵

遗憾的是，Arbitrary不是神奇的输入打印机。

在内部，解析器本身在整个解析过程中定义了各种长度字段，这些字段决定了如何处理输入的其余部分。这使得输入的格式随着输入的小变化而 dramatically 变化⁵，因此，数据重解释问题再次出现。

更糟的是，当我们现在部署我们的模糊器时，输入的含义发生了变化——因此我们过去数千个CPU年的模糊测试现在被丢弃了。

事实证明，数据重解释问题可能不可避免；如果没有简单了解数据类型的变异，产生相似的输入可能不可能。即使直接变异语法中的条目（例如，通过简单地将输入的一个子树替换为另一个），编辑距离通常也很大。这使我们覆盖率引导模糊器的基本前提无效，因此使我们的模糊器实际上无用。

对吧？

结果

我基于arbitrary的模糊器在30分钟内编写完成。我运行了不到一分钟，一个测试用例在模糊器的发布版本中触发了CVE-2022-27413⁶作为超时。

事实证明，当使用arbitrary时，输入的大规模重解释不是问题。由于变异引起的随机性导致输入的主要重解释，探索了输入语法的大量内容。这有效地将变异器转变为黑盒语法生成器，并且语法覆盖作为程序覆盖的自然结果。

由于随机性被限制为有效输入，只是时间问题，就会产生满足错误确切前提条件的有效输入。而且，它还发现了许多其他问题。我甚至制作了差分模糊器，成功识别了版本和子实现之间的一些一致性错误。

所以，我们现在找到了所有错误，对吧？

要点

我承认这部分有点难以解释。我们开始时说保持输入的相似性对于基于覆盖率的模糊器很重要，然后结束时说"哦，如果我们使用arbitrary，实际上并不重要”。那么，到底是什么？

可悲的答案很简单，我们的测试是不完整的——而且将永远不完整。虽然我们现在能够快速产生格式良好、高度复杂和有趣的输入，但我们在实际执行变异时缺乏指导。我们的输入在变异之间非常不相似，我们可能遭受我之前描述的JSON加载问题，即我们无法找到依赖于解析结果的更深层错误。

也不清楚我们是否有效地测试了不同的匹配策略。虽然我们的输入现在宏大而复杂，但它们可能没有有效地测试匹配代码，因为我们不知道我们的干草堆与模式的相关性如何。因此，模糊器错过了其他用户发现的几次崩溃和不正确性。

最后，由于差分模糊器没有积极使用，我们完全依赖断言和崩溃。换句话说，我们根本无法发现正确性问题。即使启用了差分模糊器，也不能保证它们会捕获所有问题，特别是因为我们没有很好地探索程序空间以进行匹配。

我可以继续谈论这里现在使用的模糊器的其他弱点一段时间，但这既不在这里也不在那里。亲爱的读者，你应该考虑的主要事情是你的模糊器内部如何尝试测试程序，以及你愿意花多少时间使模糊器工作良好。模糊器运行时不是魔法，工具也不是。你不能期望它可靠地产生输入，这些输入通过你的工具传递时，会触发程序中的错误。此外，你不能期望你会神奇地发现你没有检测手段的错误。你必须批判性地思考输入将如何生成、变异、解释和执行，并决定你将花多少时间使模糊器有效地在目标中发现错误。

但几乎可以肯定，字节级变异是不够的。

目标2：PCRE2

继续在第二部分，发布于2024.07.15 2024.07.20 2024.08.24（有点忙！）。

¹ 大多数情况下。模糊器可能有意或无意地过拟合某些应用程序。 ↩
² 这不严格准确。libFuzzer收集许多不同类型的信息，但其核心最终是覆盖率引导的模糊器。 ↩
³ 实际上我们有点可以，通过符号执行，但这有它自己的问题，我不在这里讨论。 ↩
⁴ 这最近在Caroline Lemieux在SBFT'24的主题演讲中向我描述，但我一生都记不起引文，在录音中找不到，在Google中也不容易找到。 ↩
⁵ 这实际上不被普遍讨论为arbitrary的问题。你可以在几个地方看到这种效果。 ↩
⁶ 我最初认为这违反了rust-regex的复杂度保证，尽管它们的复杂度保证指的是模式编译后或准备使用后的大小。相反，问题是rust-regex编译器，它有效地将人类可读的模式转换为中间表示，然后"执行"以执行实际的搜索操作。这种表示扩展了所有重复，意味着问题在应用保证之前影响编译。原始实现假定中间表示的内存增长代表了模式编译的计算成本，而发现的测试用例具有许多重复的零大小项。这导致在使用模式之前有很长的编译时间。 ↩

正则表达式模糊测试实战：从Rust库漏洞挖掘到变异策略优化

本文深入探讨了对rust-lang/regex库进行模糊测试的技术细节，包括变异策略分析、数据重解释问题解决方案，以及如何通过arbitrary crate改进测试效果，最终成功发现CVE-2022-27413等安全漏洞。