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

引言

如果你正在阅读本文，你可能已经了解模糊测试的基本概念。作为一个极度简化的总结：模糊测试是一种自动化的随机测试过程，旨在探索被测程序（PUT；有时也称为SUT、DUT等）的状态空间（例如，对输入的不同解释或行为）。由于其固有的随机性，模糊测试经常被誉为发现程序错误的最有效方法之一，这种随机性超越了人类的预期或偏见¹。在过去30多年的存在中，该策略已经发现了无数安全关键错误（数量达到数万甚至数十万），但仍然经常受到工业界和学术界的质疑。

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

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

测试目标

我们今天的被测程序（PUTs）是：

• rust-lang/regex
• PCRE2

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

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

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

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

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

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

目标1：rust-lang/regex

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

我在大约两年前对rust-regex进行了模糊测试，但下面简要总结了我如何处理该软件。

分析现有测试框架

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

1. 模糊测试运行时启动
2. 运行时产生一些输入
3. 使用新输入运行测试框架；如果输入导致崩溃，停止
4. 运行时了解程序的某些信息以生成更好的输入
5. 返回第2步

因此，为了非常明确，我们将模糊测试器描述为执行模糊测试的整个程序，将模糊测试运行时描述为生成输入和分析程序行为的代码（通常不由用户实现），将测试框架描述为用户代码，通过调用PUT实际体现测试。

拥有差的模糊测试运行时意味着你的程序不会被很好地测试。拥有差的测试框架意味着运行时产生的输入可能实际上不会测试程序的太多部分，或者可能不会非常有效地测试它。

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

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

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

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

深入内部

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

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

1. 模糊测试运行时启动
2. 运行时从语料库（保留的输入集）中选择一些现有输入；如果没有可用输入，生成一个并转到第4步
3. 运行时突变输入
4. 使用新输入运行测试框架；如果输入导致崩溃，停止
5. 运行时检查最后一次运行的覆盖范围；如果输入导致探索了新的代码区域，将其添加到语料库
6. 返回第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/2^32——大约十亿分之四。这不是最好的几率。

覆盖引导模糊测试的承诺是，通过突变，我们慢慢探索程序，从而将问题分解为单独的、更容易生成的子问题。假设我们的运行时只应用随机产生编辑距离为1的输入的突变。现在，当我们突变我们的输入时，从小开始，我们可以一次猜测每个1/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。现在，只要我们的突变器足够聪明，能够弄清楚如何将字符串"a"放入该字段，我们实际上保证能够产生命中"bug!“的输入。

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

数据重解释：重装上阵

遗憾的是，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编译器，它有效地将人类可读的模式转换为中间表示，然后"执行"以执行实际搜索操作。这种表示扩展了所有重复，意味着问题在保证应用之前影响编译。原始实现假定中间表示的内存增长代表了模式编译的计算成本，而发现的测试用例具有许多重复的零大小项。这导致在模式甚至可以使用之前有很长的编译时间。 ↩