2017年3月6日
第15卷，第1期

MongoDB 的 JavaScript 模糊测试器

模糊测试器适用于您的测试未捕获的那些边缘情况。

Robert Guo，MongoDB

随着 MongoDB 随着时间的推移变得功能更丰富和更复杂，开发更复杂的方法来查找错误的需求也在增长。三年前，MongDB 在其工具包中添加了一个自制的 JavaScript 模糊测试器，它现在是我们最高产的错误查找工具，在两个发布周期中负责检测到近 200 个错误。这些错误涵盖了从分片到存储引擎的各种 MongoDB 组件，症状范围从死锁到数据不一致。模糊测试器作为 CI（持续集成）系统的一部分运行，它经常捕获新提交代码中的错误。

模糊测试，或模糊测试技术，是一种为程序生成随机、意外和无效输入以触发未经测试的代码路径的技术。模糊测试最初在 20 世纪 80 年代开发，此后被证明可以有效地确保从文件系统¹⁵到分布式集群¹⁰到浏览器¹⁶等各种系统的稳定性。随着人们试图使模糊测试更有效，出现了两种哲学：智能模糊测试和愚蠢模糊测试。随着最先进技术的发展，用于实现模糊测试器的技术正在被划分为类别，其中最主要的是生成式和变异式。⁷在许多流行的模糊测试工具中，智能模糊测试对应于生成式技术，而愚蠢模糊测试对应于变异式技术，但这并非内在关系。实际上，在我们 MongoDB 的案例中，情况恰恰相反。

智能模糊测试

智能模糊测试器是对被测程序的有效输入面有很好理解的模糊测试器。有了这种理解，智能模糊测试器可以避免陷入输入验证，而专注于测试程序的行为。测试程序是否正确验证其输入很重要，但不是模糊测试的目标。

许多模糊测试器依赖于显式语法来生成测试，正是这种语法使这些测试变得智能。但是 MongoDB 的命令语言还很年轻，我们不想因为花时间提炼正式语法而延迟模糊测试器的交付。相反，我们从现有的 JavaScript 集成测试语料库¹⁸中借用我们对 MongoDB 命令语法的知识，随机变异它们以创建新颖的测试用例。因此，我们的变异式策略产生了智能模糊测试器。

这些 JavaScript 集成测试多年来一直是我们测试的中流砥柱。我们的 CI 系统 Evergreen⁸ 调用一个测试运行器，该运行器将每个测试文件馈送到 mongo shell，后者针对 MongoDB 服务器、分片路由器和其他要测试的组件执行测试文件中的命令。当模糊测试器运行时，它会接收这些 JS 测试的随机子集，并将它们转换为 JavaScript 解释器可以理解的 AST（抽象语法树）形式。然后，它通过选择性地替换节点、随机排列它们以及替换它们的值，对树进行（受控的）破坏。这样，我们生成了在正常测试期间不会遇到的参数的命令，但保留了有效 JavaScript 对象的整体结构。

例如，代码

db.coll.find({x:1})

在集合 coll 中查找字段 x 值为 1 的文档，如图 1 所示。

为了开始对该 AST 进行模糊测试，模糊测试器首先遍历树以标记应替换的节点。在这种情况下，假设它已决定替换 ObjectExpression¹⁴ 的值，即 1。然后，此节点被替换为占位符节点，如图 2 所示。

当模糊测试器遍历树时，它还会拾取它认为有趣的值，这些值通常是原始值，例如字符串和数字。这些值被收集并用于构造占位符节点的最终值。

在此示例中，占位符被替换为另一个 ObjectExpression，其中包含它从语料库中其他地方收集的键和值，如图 3 所示。

当这棵树转换为代码时，它变成了一个新的测试用例

db.coll.find(x:{$regex:'ab'}}

这会将查找字段 x 值为 1 的文档的原始测试用例替换为查找与正则表达式 a\0b 匹配的文档的新测试用例。

一个非常类似于此的测试实际上是由我们的模糊测试器运行的，结果证明 MongoDB 没有正确处理包含空字节的正则表达式字符串，因此这个测试用例导致服务器崩溃。¹¹

经验教训

AST > 正则表达式

使用抽象语法树是模糊测试的绝佳策略。以前，我们尝试使用基于正则表达式的方法进行模糊测试。这涉及字符串化测试并查找要替换或随机排列的特定标记。一段时间后，维护这些正则表达式变成了一场噩梦，并且很容易引入细微的错误，导致变异变得不那么有效。另一方面，语法树旨在表示您需要了解的有关代码的所有信息，这是可以使用正则表达式推断出的信息的超集。此外，AST 非常难出错：模糊测试器所做的只是操作对象中的属性。

开源库可用于将大多数语言的代码转换为 AST；我们使用了 acorn.js。¹

启发式 > 随机

在实现模糊测试器的变异方面时，注意哪些类型的变异正在引发最多的错误可能会产生好处。最初的实现随机选择要替换的节点，但修改后的 ObjectExpression 有助于发现更多新错误，因此我们调整了概率以使更多变异发生在 ObjectExpression 上。

愚蠢模糊测试

智能的基于 AST 的变异使 MongoDB 模糊测试器熟悉输入格式，但它也保证了盲点，因为语料库是从人工编写的测试中收集的有限列表。愚蠢模糊测试学派提出了针对此缺陷的答案，倡导生成随机输入而不考虑有效性的模糊测试器，从而覆盖开发人员可能忽略的区域。

这有点像走钢丝。在完全不了解目标程序的情况下，模糊测试器可以做的最好的事情就是输入随机的 0 和 1 流。这通常除了触发某些中间层中的输入验证代码之外什么也不做，然后才到达被测程序。仅触发输入验证代码是不良模糊测试器的标志。

为了在我们的模糊测试器中加入一些愚蠢性，而又不求助于随机二进制，值是从种子列表中生成的。由于我们的测试输入是 JavaScript 对象，由 MongoDB 命令和原始值组成，因此种子列表由我们从经验中知道是边缘情况的 MongoDB 命令和原始类型组成。这些种子值保存在文件中，JavaScript 对象使用它们作为键和值生成。这是一个摘录

var defaultTokens = { primitives: ['Infinity', '-Infinity', 'NaN', '-NaN', 'ab', 'AB', '000', '000000'], commands: ['all', 'bitsAllClear'] // 等等。 }

这些值来自我们测试 MongoDB 的经验，但就模糊测试器而言，它们只是 AST 的节点，它从它们组合测试输入，而不考虑什么是有效的。因此，我们的生成方法产生了愚蠢性。

它不是这样工作的

我们正在尝试平衡覆盖率和避免验证。为了生成有可能通过输入验证的测试输入，我们可以从有效 JavaScript 对象的模板开始。此模板中的字母代表占位符

{a:X, b:Y, c:Z}

然后，我们可以将大写字母替换为种子原始值

{a: 4294967296, b: 'ab', c: NumberDecimal(-NaN)}

并将小写字母替换为种子 MongoDB 命令参数

{create: 4294967296, $add: 'ab', $max: NumberDecimal(-NaN)}

然而，这不是有效的 MongoDB 命令。即使从有效 MongoDB 原始值列表中填充格式良好的模板，此生成的输入仍然只会触发验证代码。

混合模糊测试

变异模糊测试会留下盲点，而生成式模糊测试本身根本无法测试有趣的逻辑。然而，当结合使用时，这两种技术都变得更加强大。这就是我们的模糊测试器实际工作的方式。

当它变异现有测试时，有时，它不是从语料库中提取替换项，而是从其种子列表中生成 AST 节点。这种生成式替换通过生成语料库中不存在的值来减少盲点，而变异基础意味着生成的命令保留了有效输入的结构，使其很可能通过验证。只有当程序深入堆栈时，它才会意识到事情已经变得非常糟糕。任务完成。

这是一个混合模糊测试在实际应用中的示例，使用了实际暴露错误的简化版本测试。模糊测试器从以下语料库开始

db.test.insert({x:1}); db.test.update({some: "object"}, ...);

其中第一行变成了图 4 所示的 AST。

ObjectExpression 被转换为占位符节点，方式与变异模糊测试相同。

然后，模糊测试器决定不使用语料库中其他地方的值替换占位符节点，而是使用生成的对象替换它——在本例中，是一个以大的 NumberLong 作为参数的 newExpression，如图 5 所示。

这产生了以下测试

db.test.insert({a: new NumberLong("9223372036854775808")}); db.test.update({}, {$inc: {a: 13.0}});

结果是将一个大的 64 位整数插入到 MongoDB 中，然后更新其值。当实际测试运行时，结果证明新值仍然是一个很大的数字，但不是正确的数字。错误是 MongoDB 在内部将整数存储为双精度浮点数，而双精度浮点数只有 53 位的精度。¹³模糊测试器能够通过生成大的 NumberLong 来发现这一点，而 NumberLong 没有出现在任何测试中。

变异模糊测试与我们播种到生成式模糊测试器的边缘情况的结合，比显式地为这些边缘情况编写测试强大一个数量级。事实上，模糊测试器发现的很大一部分错误是由以这种方式生成的值触发的。

不受约束的模糊测试器会产生太多噪音

最终，模糊测试是一场随机数的游戏。随机数使模糊测试器功能强大，但也可能导致无法预见的问题。我们需要采取一些步骤来确保模糊测试器不会自行崩溃。以下代码块类似于 MongoDB 的 JavaScript 测试之一中可能存在的代码

while(coll.count() < 654321) assert(coll.update({a:1}, {$set: {...}}))

如果我们将其通过前面描述的变异和生成式模糊测试步骤，模糊测试器可能会产生以下可能的测试用例

while(true) assert(coll.update({}, {$set: {"a.654321" : 1}}))

新代码现在测试的是完全不同的东西。它尝试设置存储在某些 MongoDB 集合中所有文档中的数组中的第 654321 个元素。

这是一个有趣的测试用例。将 $set 运算符与如此大的数组一起使用可能不是我们想到要显式测试的东西，并且可能会触发错误（实际上，它确实会）。¹²但是，模糊处理后的 true 条件与剩余的 while 循环之间的交互将使测试挂起！—除非，while 循环中的 assert 调用失败，如果原始测试中定义 coll 的行（此处未显示）被模糊测试器变异或删除，从而使 coll 未定义，则可能会发生这种情况。如果 assert 调用失败，它将被 Mongo shell 捕获并导致其终止。

然而，挂起和断言失败都不是由 MongoDB 中的错误引起的。它们只是随机生成的测试用例的副产品，它们代表了必须从模糊测试中过滤掉的两类噪音：分支逻辑和断言失败。

分支逻辑

为了防止意外挂起，我们的模糊测试器只是通过 AST 操作消除了所有分支逻辑。除了 while 循环之外，我们还移除了 try/catch、break 和 continue 语句、do/while、for、for/in 和 for/of 循环。这些语言结构在静态列表中定义。

断言失败

对于断言失败，生成的测试代码的每一行都用 try/catch 语句包装。所有逻辑仍将执行，但不会传播客户端错误并导致失败。

在通过此清理阶段后，我们之前的示例现在看起来像这样

try { assert(coll.update({}, {$set: {"a.654321" : 1}})) } catch {}

那么模糊测试器如何捕获错误？

将所有内容包装在 try/catch 块中可以防止模糊测试器生成的噪音淹没我们，并产生误报，但它也阻止了任何错误通过我们典型测试所依赖的客户端断言浮出水面。实际上，模糊测试器必须依靠其他机制来检测它引发的错误。

通用错误工具

第一组工具是我们无论如何都在使用的工具，用于查找段错误、内存泄漏和未定义的行为。即使没有模糊测试器，我们仍然会使用这些语言运行时工具³，例如 LLVM 的地址清理器⁴和未定义行为清理器⁵，但是当模糊测试器用其所有随机输入轰炸测试目标时，它们变得更加有用。

这些工具对于通用编码错误很有用，但它们不能验证程序是否按最终用户的预期运行。为了捕获业务逻辑问题，我们的模糊测试器依赖于测试目标内的断言，这些断言检查它不应处于的条件。

被测系统内的断言

许多应用程序都大量使用断言来防止非法条件，但模糊测试依赖它们来捕获应用程序逻辑错误。它在您的代码库中造成严重破坏，并假设您已检测应用程序的组件，以便注意到严重破坏。

例如，当充当 MongoDB 副本集中的辅助节点时，如果 mongod 无法写入操作，则会断言停止。⁹如果主节点为其辅助节点记录写入，则它们最好也能够执行写入，否则当发生故障转移时，我们将最终导致严重的数据丢失。由于这些断言是致命错误，因此测试框架会立即注意到模糊测试何时触发它们。

随机测试的局限性

这实际上是断言可以用于捕获随机生成的测试引发的错误的唯一方法。目标程序中的断言可以忽略正在运行的测试；实际上，它们必须在所有情况下都成立（包括当程序由用户运行时）。相比之下，测试中的断言必须特定于测试场景。然而，我们已经表明，模糊测试器生成的测试本质上不得包含致命断言。因此，在真正的随机条件下，模糊测试器将触发无定制的断言。这是所有随机测试技术的局限性，这也是任何良好的测试框架都不能仅依赖随机测试的原因。

分类模糊测试器故障

执行随机代码并依赖目标系统断言的测试有一些缺点：它们发现的问题没有预定义的用途；它们中的许多操作可能是无害的噪音；并且它们产生的错误通常是复杂的。在测试的特定行观察到的故障可能依赖于先前操作设置的状态，因此必须检查和理解可能不相关的代码库部分。

因此，模糊测试器故障需要分类，以找到触发问题的最小操作集。这可能需要大量的人工干预，就像已知问题¹⁷那样，在并发客户端调用 cursor.explain()⁶ 会导致段错误。引发此问题的测试使用了十几个并发执行不同操作的客户端，因此除了了解测试集中的操作设置的状态之外，还必须手动检查来自所有客户端和服务器线程的日志消息并将其相互关联。

所有这些工作都是分类模糊测试器测试失败的典型工作，因此我们构建了一组功能，以帮助开发人员筛选混乱。这些功能特定于使用 JavaScript 通过网络测试 MongoDB 集群，但可以用作所有模糊测试项目的灵感。

我们只对将命令发送到 MongoDB 服务器的代码行感兴趣，因此第一步是隔离这些行。使用我们可靠的 AST 操作器，我们在每行模糊测试器代码后添加一个 print 语句，以记录运行所需的时间。运行时间很长的行通常运行命令并与 mongodb 服务器通信。有了这些计时器，我们的模糊测试看起来像这样

var $startTime = Date.now(); try { // 模糊测试器生成的代码行 } catch (e) { } var $endTime = Date.now(); print('顶层语句 0 在', $endTime - $startTime, '毫秒内完成'); var $startTime = Date.now(); try { // 模糊测试器生成的代码行 } catch (e) { } var $endTime = Date.now(); print('顶层语句 1 在', $endTime - $startTime, '毫秒内完成'); // 等等。

当我们遇到故障时，我们会从日志消息中找到最后成功完成的语句，而下一个实际运行的命令是分类开始的地方。

此技术足以识别可能导致服务器因一两行测试代码而崩溃的微不足道的错误。更复杂的错误需要编程辅助来准确查找哪些测试代码行导致了问题。我们通过对每个模糊测试器生成的文件进行广度优先二分搜索来达到目的。我们的脚本递归生成包含失败代码的每一半的新测试，直到进一步删除不再导致测试失败为止。

然而，二分搜索脚本并非万能药。某些错误无法一致地重现或导致挂起，并且需要不同的工具集。特定工具将完全取决于您的产品，但识别挂起的一种简单方法是使用计时器。我们记录测试套件的运行时，如果它比平均运行时长一个数量级，我们假设它已挂起，附加调试器并生成核心转储。

通过使用计时器、print 语句和二分搜索脚本，我们能够快速正确地分类我们的大部分故障。调试没有万能药——每个问题都是新的，大多数问题都需要一些试验和错误才能正确解决。我们正在持续投资于该领域，以加速和简化故障隔离。

在 CI 系统中运行模糊测试器

模糊测试传统上是在专用集群中完成的，这些集群定期在选定的提交上运行，但我们决定将其作为测试套件包含在我们的 CI 框架 Evergreen 中。这为我们节省了构建新的自动化测试环境的工作量，并使我们免于投入资源来确定在哪个提交中引入了该错误。

当定期调用模糊测试器时，查找有问题的提交需要使用诸如 git-bisect²之类的工具。通过我们在 CI 框架中运行的变异模糊测试器方法，我们始终将新提交的测试包含在语料库中。每次模糊测试器运行时，我们都会从语料库中随机选择 150 组由几十个文件组成的文件，并通过模糊测试器运行每个文件以生成 150 个模糊处理的文件。每组语料库文件始终包含添加到代码库的新逻辑，这意味着模糊处理的测试也很可能测试新代码。这是一种简单而优雅的方式，使模糊测试器可以“理解”代码库的更改，而无需大量工作来解析源文件或读取代码覆盖率数据。

当模糊测试导致失败时，下游效果与任何其他类型的测试失败相同，只是需要额外的分类。

模糊测试器：您最好的朋友

总的来说，模糊测试器已成为 MongoDB 测试基础设施中最有价值的工具之一。在我们现有的 JavaScript 测试套件的基础上，我们能够以相对较小的努力显着提高我们的覆盖率。把所有事情都做好需要时间，但是要启动一个基本的简陋系统，您只需要一组现有的测试作为语料库，一个用于您选择的语言的语法树解析，以及一种将框架添加到 CI 系统的方法。最重要的是，无论为测试功能付出多少努力，都不可避免地会有一个未处理的边缘情况。在那些令人沮丧的时刻，模糊测试器就在您身边。

参考文献

1. Acorn； https://github.com/ternjs/acorn。

2. Chacon, S., Straub, B.. Git-bisect； https://git-scm.cn/book/en/v2。

3. Clang 3.8 文档。将 Clang 用作编译器； http://releases.llvm.org/3.8.0/tools/clang/docs/index.html#using-clang-as-a-compiler。

4. Clang 3.8 文档。AddressSanitizer； http://releases.llvm.org/3.8.0/tools/clang/docs/AddressSanitizer.html。

5. Clang 3.8 文档。UndefinedBehaviorSanitizer； http://releases.llvm.org/3.8.0/tools/clang/docs/UndefinedBehaviorSanitizer.html。

6. Cursor.explain()。MongoDB 文档； https://docs.mongodb.com/manual/reference/method/cursor.explain/。

7. Déjà vu Security。2014 年。生成模糊测试。Peach Fuzzer； http://community.peachfuzzer.com/GenerationMutationFuzzing.html。

8. Erf, K. 2016 年。Evergreen 持续集成：我们为什么要重新发明轮子。MongoDB 工程期刊； https://engineering.mongodb.com/post/evergreen-continuous-integration-why-we-reinvented-the-wheel/。

9. GitHub。MongoDB； https://github.com/mongodb/。

10. Godefroid, P., Levin, M. Y., Molnar, D. 2012 年。SAGE：用于安全测试的白盒模糊测试。通讯 55(3): 40-44； http://courses.cs.washington.edu/courses/cse484/14au/reading/sage-cacm-2012.pdf。

11. Guo, R. 2016 年。在某些操作上调用 .explain() 时 Mongos 段错误。MongoDB； https://jira.mongodb.org/browse/SERVER-22767。

12. Guo, R. 2016 年。对大型数组的 $push 在辅助节点上 fasserts。MongoDB； https://jira.mongodb.org/browse/SERVER-22635。

13. Kamsky, A. 2016 年。更新认为数值类型的更改是空操作。MongoDB； https://jira.mongodb.org/browse/SERVER-16801。

14. McCloskey, B., et al. 2015 年。Parser API。Mozilla 开发者网络； https://mdn.org.cn/en-US/docs/Mozilla/Projects/SpiderMonkey/Parser_API#Expressions。

15. Nossum, V., Casasnovas, Q. 2016 年。使用 American Fuzzy Lop 进行文件系统模糊测试。Oracle Linux 和 VM 开发—Ksplice 团队； https://events.linuxfoundation.org/sites/events/files/slides/AFL filesystem fuzzing, Vault 2016_0.pdf。

16. Ruderman, J. 2007 年。Introducing jsfunfuzz。Indistinguishable from Jesse； https://www.squarefree.com/2007/08/02/introducing-jsfunfuzz/。

17. Siu, I. 2016 年。Explain("executionStats") 可能会在集合被删除后尝试访问它。MongoDB； https://jira.mongodb.org/browse/SERVER-24755。

18. Storch, D. 2016 年。MongoDB，jstests。GitHub； https://github.com/mongodb/mongo/tree/r3.3.12/jstests。

构建 Nutch：开源搜索
- Mike Cafarella 和 Doug Cutting，Nutch
编写开源搜索引擎的案例研究
https://queue.org.cn/detail.cfm?id=988408

大规模赋值武器
- Patrick McKenzie，Kalzumeus
Ruby on Rails 应用程序突出显示了一些严重但易于避免的安全漏洞。
https://queue.org.cn/detail.cfm?id=1964843

沉浸在约束中
- Bruce Johnson，Google
Google Web Toolkit 是绕过 Web 开发障碍的终极解决方案。
https://queue.org.cn/detail.cfm?id=1572457

Robert Guo 是 MongoDB 服务器团队的软件工程师，专注于数据一致性和正确性。在过去的两年中，他一直在从事 MongoDB 的 JavaScript 模糊测试器的工作。

最初发表于 Queue 第 15 卷，第 1 期—
在数字图书馆中评论本文

更多相关文章

Sanjay Sha - 企业应用程序的可靠性
企业可靠性是一门学科，它确保应用程序以一致、可预测且经济高效的方式交付所需的业务功能，而不会损害可用性、性能和可维护性等核心方面。本文介绍了一组核心原则和工程方法，企业可以应用这些原则和方法来帮助他们驾驭复杂的企业可靠性环境，并交付高度可靠且经济高效的应用程序。

Robert V. Binder, Bruno Legeard, Anne Kramer - 基于模型的测试：它的现状如何？
您可能听说过 MBT（基于模型的测试），但像许多未使用 MBT 的软件工程专业人士一样，您可能对其他人使用此测试设计方法的经验感到好奇。从 2014 年 6 月中旬到 2014 年 8 月初，我们进行了一项调查，以了解 MBT 用户如何看待其效率和有效性。2014 年 MBT 用户调查是 2012 年类似调查的后续调查，向所有评估或使用过任何 MBT 方法的人开放。它的 32 个问题包括 2013 年高级自动化测试用户会议上分发的一些问题。一些问题侧重于 MBT 的效率和有效性，提供了管理者最感兴趣的数字。

Terry Coatta, Michael Donat, Jafar Husain - EA 的自动化 QA 测试：由事件驱动
对于数百万游戏迷来说，在 Electronic Arts 担任 QA（质量保证）测试员的职位一定像是梦想成真。但从公司的角度来看，与 QA 相关的开销可能看起来非常可怕，尤其是在大型多人游戏时代。

James Roche - 在质量保证中采用 DevOps 实践
长期以来，软件生命周期管理一直是一项受控的练习。产品设计、开发和支持的持续时间是足够可预测的，以至于公司及其员工围绕产品发布安排他们的财务、假期、手术和合并。当开发人员忙碌时，QA（质量保证）很容易。随着发布周期的编码部分接近尾声，当支持人员增加时，QA 接管。然后在产品发布时，开发人员呼出一口气，休息一下，然后重新开始循环，而支持人员则忙于支持新产品。