Fuzzilli源码分析

Fuzzilli源码分析

环境

分析与调试环境为

1
2
3
dog@dog:~/swift/usr/bin$ lldb --version
lldb version 17.0.0 (https://github.com/swiftlang/llvm-project.git revision 3a02857b159678d97e33f8c5032541c3ddd5f1f6)
Swift version 6.2-dev (LLVM 3a02857b159678d, Swift c91e29523420c00)

使用swift编译Fuzzilli时，使用debug模式：swift build -c debug，这种情形下，才能对其进行调试。

Vscode调试swift项目时会存在BUG，调试时无法获取变量的值，也无法获得任何有用信息。即鼠标悬停在变量时，出现Unable to determine byte size，解决方案：Codelldb Debugging problems

以下是使用vscode调试时的launch.json文件：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
{
    // Use IntelliSense to learn about possible attributes.
    // Hover to view descriptions of existing attributes.
    // For more information, visit: https://go.microsoft.com/fwlink/?linkid=830387
    "version": "0.2.0",
    "configurations": [

        {
            "type": "lldb",
            "request": "launch",
            "sourceLanguages": ["swift"],
            "name": "Debug swift-executable",
            "program": "${workspaceFolder}/.build/debug/FuzzilliCli",
            "args": ["--profile=qjs","Targets/QJS/quickjs/qjs"],
            "cwd": "${workspaceFolder}",
            // "preLaunchTask": "Build for debug"
        }
    ]
}

Fuzzilli 工作原理

Fuzzilli具有两个主要的模糊测试引擎：Mutation Engine和Hybrid Engine。后者本质上是纯生成组件与现有变异的结合。

在解释这些引擎的工作原理之前，首先解释FuzzIL，这是Fuzzilli构建的基础的自定义中间语言。

可以通过使用--inspectCLI标志来观察文档中描述的所有机制的实际运行情况。如果启用，所有写入磁盘的程序（本质上是语料库中的程序以及Crash）都将有一个额外的.history文件，描述程序的“历史记录”，即为生成程序而执行的确切变异、拼接、代码生成等步骤。

Fuzzilli的目标

除了生成”interesting”的JavaScript代码这个核心目标外，Fuzzilli还必须处理以下两个问题。

语法正确性

如果一个程序在语法上无效，它将在引擎中被解析器在处理的早期阶段拒绝。 由于 Fuzzilli 不尝试查找语言解析器中的错误，因此这样的执行将有效地被浪费。 因此，Fuzzilli 致力于实现 100% 的句法正确率。 这是通过使用 FuzzIL（接下来讨论）来构建实现的，FuzzIL 只能表达在语法上有效的 JavaScript 代码。

语义正确性

在 Fuzzilli 中，引发未捕获异常的程序被认为是语义上不正确的，或简称为无效。 虽然可以将每个（或大多数）语句包装到 try-catch 块中，但这将从根本上改变生成的程序的控制流，从而改变 JIT 编译器的优化方式。 许多 JIT 错误无法通过这样的程序触发。 因此，至关重要的是，Fuzzilli 生成具有相当高程度的语义有效的样本（作为基准，Fuzzilli 应以高于 50% 的正确率为目标）。

这个挑战取决于每个模糊测试引擎，因此将分别针对每个引擎进行讨论。

FuzzIL 中间语言

源码位于：Sources/Fuzzilli/FuzzIL

Fuzzilli基于一种名为FuzzIL的自定义中间语言。FuzzIL的设计具有四个核心目标：

  • 促进有意义的代码变异
  • 易于静态推理（参见关于类型系统的章节）
  • 易于提升（lift）到JavaScript
  • 确保生成的JavaScript代码的某些正确性属性，例如语法正确性以及在使用变量之前定义变量

Fuzzilli 内部专门对 FuzzIL 程序进行操作，并且仅为了执行才将其提升到 JavaScript。 因此，使用 FuzzIL 的高级模糊测试管道如下所示：

提升由 JavaScriptLifter 执行，而 JavaScript 代码的执行通过 REPRL（读取-求值-打印-重置-循环）机制进行，这本质上是 JS 引擎的持久模糊测试的实现，它还提供有关执行是否成功的反馈（如果执行因未捕获的异常而终止，则执行失败）。

FuzzIL 程序可以序列化为 protobuf，这用于将它们存储到磁盘或在分布式模糊测试的情况下通过网络发送它们。 可以使用 FuzzILTool 将 protobuf 格式的 FuzzIL 程序转换为 JavaScript 或 FuzzIL 的文本表示形式：

1
swift run FuzzILTool --liftToFuzzIL path/to/program.protobuf

FuzzIL 致力于实现大部分自解释性。 例如，一个假想的 FuzzIL 样本可能如下所示

1
2
3
4
5
6
7
8
v0 <- BeginPlainFunctionDefinition -> v1, v2, v3
    v4 <- BinaryOperation v1 '+' v2
    SetProperty v3, 'foo', v4
EndPlainFunctionDefinition
v5 <- LoadString "Hello World"
v6 <- CreateObject ['bar': v5]
v7 <- LoadFloat 13.37
v8 <- CallFunction v0, [v7, v7, v6]

当内联中间表达式时，提升到 JavaScript 代码的同一个程序可能如下所示

1
2
3
4
5
function f0(a1, a2, a3) {
  a3.foo = a1 + a2;
}
const v6 = { bar: "Hello World" };
f0(13.37, 13.37, v6);

或者，当使用简单的提升算法时，可能如下所示：

1
2
3
4
5
6
7
8
function f0(a1, a2, a3) {
  const v4 = a1 + a2;
  a3.foo = v4;
}
const v5 = "Hello World";
const v6 = { bar: v5 };
const v7 = 13.37;
const v8 = f0(v7, v7, v6);

最终，使用的提升算法可能并不重要，因为无论代码的语法表示形式如何，JavaScript 引擎的字节码和 JIT 编译器都会产生几乎相同的结果。

FuzzIL 有一个“受保护”操作的概念，这些操作通过 try-catch 保护免受运行时异常的影响。 例如，如果 CallFunction 操作可能合理地引发异常（例如，因为参数类型不正确），则可以将其标记为受保护：CallFunction v3, [v5, v6] (guarded)。 在这种情况下，它将提升到如下所示的 JavaScript 代码

1
2
3
try {
  v3(v5, v6);
} catch {}

由于为受保护操作生成的 try-catch 块会对程序的行为产生负面影响（如上所述），因此应谨慎使用它们。 此外，Fuzzilli 尝试在 Minimization 期间以及通过 FixupMutator 将受保护操作转换为不受保护的操作，这两者将在本文档后面进一步讨论。

FuzzIL 具有许多属性：

  • 一个 FuzzIL 程序只是一个指令列表。
  • 每个 FuzzIL 程序都可以提升为语法上有效的 JavaScript 代码。
  • 一个 FuzzIL 指令是一个操作，以及输入和输出变量，并且可能有一个或多个参数（在上面的表示法中用单引号括起来）。
  • 每个变量在使用之前都已定义，并且变量编号是递增且连续的。
  • 控制流通过“块”来表达，这些块至少具有一个 Begin 和一个 End 操作，但也可能具有中间操作，例如 BeginIf、BeginElse、EndIf。
  • 块指令可以具有内部输出（在上面的表示法中，-> 后面的那些），这些输出仅在新打开的作用域中可见（例如函数参数）。
  • 指令的输入始终是变量，没有立即值。
  • 指令的每个输出都是一个新变量，并且只能通过专用操作（例如 Reassign 指令）来重新分配现有变量。

变异FuzzIL代码

FuzzIL 旨在促进各种有意义的代码变异。 在本节中，将解释核心变异。

应该注意的是，Fuzzilli 中的程序是不可变的，这使得推理它们更容易。 因此，当一个程序被变异时，它实际上是在将变异应用到它的同时被复制。 这是通过 ProgramBuilder 类完成的，它是 Fuzzilli 中的一个核心组件，允许生成新指令或从另一个程序复制指令，并公开关于正在构建的程序的各种信息，例如哪些变量当前可见。

Input Mutator

实现：InputMutator.swift

这是核心数据流变异。 本质上，它只是将指令的输入替换为另一个随机选择的输入：

1
SetProperty v3, 'foo', v4		# v3.foo = v4

可能变成

1
SetProperty v3, 'foo', v2		# v3.foo = v2

由于 FuzzIL 的设计，特别是所有指令的输入都是变量这一事实，这种变异只需要少量 LOC（Lines of Code, 代码行数）即可实现。

Operation Mutator

实现：OperationMutator.swift

另一种基本变异，它会变异操作的参数（在 FuzzIL 的文本表示形式中用单引号括起来的值）。 例如：

1
v4 <- BinaryOperation v1 '+' v2

可能变成

1
v4 <- BinaryOperation v1 '/' v2

Splicing

实现：SpliceMutator

拼接背后的想法是将一个程序中自我包含的一部分复制到另一个程序中，以便组合来自不同程序的特性。 考虑以下程序：

1
2
3
4
5
v0 <- LoadInt '42'
v1 <- LoadFloat '13.37'
v2 <- LoadBuiltin 'Math'
v3 <- CallMethod v2, 'sin', [v1]
v4 <- CreateArray [v3, v3]

以其最简单的形式，从 CallMethod 指令进行拼接将导致三个中间指令被复制到当前程序中。 这还需要重命名变量，以便它们不与现有变量冲突：

1
2
3
4
5
... 现有代码
v13 <- LoadFloat '13.37'
v14 <- LoadBuiltin 'Math'
v15 <- CallMethod v14, 'sin', [v13]
... 现有代码

也可以进行更复杂的拼接。 例如，Fuzzilli 将概率性地将正在拼接的程序中的一些变量重新映射到宿主程序中的“兼容”变量，以组合两个程序的数据流，因此也可能最终产生以下结果：

1
2
3
4
... 现有代码
v14 <- LoadBuiltin 'Math'
v15 <- CallMethod v14, 'sin', [v3]
... 现有代码

在这里，拼接算法已决定用现有变量 (v3) 替换 LoadFloat 操作，例如因为该变量也包含一个浮点数。

拼接变异的一个简单的变体是 CombineMutator，它只是将另一个程序完整地插入到当前变异的程序中。 在这种情况下，拼接本质上是整个程序。

Code Generation

实现：CodeGenMutator.swift

最终的基本变异是代码生成。 这种变异器在变异程序的单个或多个随机位置生成新的随机代码。

代码生成是通过“CodeGenerators”执行的：小函数，用于生成特定的代码片段，通常只是单个 FuzzIL 指令，同时（通常）根据需要将现有变量用作输入。 一个非常简单的代码生成器如下所示：

1
2
3
CodeGenerator("IntegerGenerator") { b in
    b.loadInt(b.genInt())
}

此生成器发出一个 LoadInteger 指令，该指令创建一个包含随机整数值的新变量（从技术上讲，并不完全随机，因为 genInt() 将倾向于一些“有趣的”整数）。 另一个示例代码生成器可能是：

1
2
3
CodeGenerator("ComparisonGenerator", inputs: (.anything, .anything)) { b, lhs, rhs in
    b.compare(lhs, with: rhs, using: chooseUniform(from: allComparators))
},

此生成器发出一个比较指令（例如 ==），比较两个现有变量（任意类型）。

默认代码生成器可以在 CodeGenerators.swift 中找到，而自定义代码生成器可以为特定引擎添加，例如触发不同级别的 JITing。

代码生成器存储在加权列表中，因此使用不同的（当前手动选择的）权重来选择它们。 这允许对生成的代码的分布进行某种程度的控制，例如，大致上执行算术运算或方法调用的频率，或者生成多少控制流（if-else、循环等），相对于数据流。 此外，CodeGenerators 提供了一种简单的方法，通过添加生成过去经常导致错误的特定代码片段（例如原型更改、自定义类型转换回调（例如 valueOf）或索引访问器）的 CodeGenerators，来引导 Fuzzilli 寻找某些错误类型。

通过代码生成器，最终将生成所有相关的语言功能（例如，对象操作、一元和二元操作等），然后将其保存在语料库中（因为它们触发了新的覆盖范围）并在此后进行进一步变异。

Exploration

实现：ExplorationMutator.swift

这种高级变异器使用 JavaScript 中可用的运行时类型信息来执行更智能的变异，特别是确定可以对现有值执行的可能操作。 它执行以下操作：

  1. 它为要变异的程序中的随机现有变量插入 Explore 操作
  2. 它执行生成的（临时）程序。 Explore 操作将被提升为一段代码，该代码在运行时检查变量（使用 JavaScript 中的“typeof”和“Object.getOwnPropertyNames”等功能），并选择要对其执行的“有用”操作（例如，加载属性、调用方法等），然后报告它做了什么
  3. 变异器处理步骤 2 的输出，并将一些 Explore 变异替换为运行时选择的具体操作。 所有其他 Explore 操作都将被丢弃

结果是一个程序，即使在静态未知其类型的情况下，也可以对一些现有变量执行有用的操作。 结果程序也是确定性的和“JIT 友好”的，因为它不再依赖于任何类型的运行时对象检查。

Probing

实现：ProbingMutator.swift

这是另一种运行时辅助变异器，它试图确定现有值的使用方式。 特别是，它试图确定某个对象上是否应该存在某些属性。 这种变异器执行以下操作：

  1. 它为要变异的程序中的随机现有变量插入 Probe 操作
  2. 它执行生成的（临时）程序。 Probe 操作将被提升为一段代码，该代码将对象（实际上是对象的原型）替换为 Proxy，然后记录对不存在的属性的所有访问。 然后将这些列表发送回 Fuzzilli。
  3. 变异器处理步骤 2 的输出并安装一些缺失的属性和回调。

这种变异器因此实现了几件事：

  • 它可以自动检测操作是否触发回调，然后可以安装回调函数。 例如，这可以帮助查找与意外回调相关的错误。
  • 它可以确定内置 API 的工作方式以及它期望的参数类型。 例如，许多 API 需要“配置”对象，这些对象应该具有某些键。 这种变异器可以确定这些键是什么，从而可以以一种有用的方式调用这些 API。
  • 它可以使现有代码更有用。 例如，我们可能已经有一个在对象参数上运行但访问不存在的属性的 jit 优化函数，这可能不是很有用。 这种变异器可以确保这些属性存在，从而使整个程序更有意义。

FixupMutator

实现：FixupMutator.swift

这是最后的运行时辅助变异器。 它的目标是修复/改进现有代码。 特别是，它想要

  • 删除不必要的 try-catch 块和保护
  • 修复对不存在的属性和元素的访问（待办）
  • 修复无效的函数、方法或构造函数调用（待办）
  • 修复导致 NaN 的算术运算，这通常表明没有执行有意义的操作（待办）

除了第一个之外，所有这些都尚未实现，因此此变异器仍在开发中。

FixupMutator 是将受保护操作转换为不受保护操作的两种方式之一（通常首选后者）。

类型系统和类型推断

实现：TypeSystem.swift 和 JSTyper.swift

到目前为止，代码生成器只是一个简单的函数，它获取零个或多个随机输入变量并生成一些新的 FuzzIL 指令来对它们执行一些操作。 现在考虑以下假想的代码生成器：

1
2
3
4
5
CodeGenerator("FunctionCallGenerator") { b in
    let function = b.randomVariable()
    let arguments = [b.randomVariable(), b.randomVariable(), b.randomVariable()]
    b.callFunction(f, with: arguments)
}

此生成器选择一个随机的、当前可见的变量，然后将其作为带有三个随机参数的函数调用。

这里的问题是，由于在任何给定时间只有少量变量实际上是函数，因此此生成器最终会生成大量无效的函数调用，例如以下内容：

1
2
3
v3 <- LoadString "foobar"
v4 <- CallFunction v3, []
// TypeError: v3 is not a function

这将导致抛出运行时异常，然后导致程序的其余部分不被执行，并且该程序被认为是无效的。

为了解决这个问题，Fuzzilli 实现了相对简单的类型推断，它尝试在 ProgramBuilder 构建程序时推断每个变量的可能类型。 这（可能）比听起来容易，因为解释器只需要在大多数时候是正确的（它基本上是一种优化），而不是总是正确的。 这大大简化了实现，因为许多具有复杂效果的操作（例如原型更改）在很大程度上可以忽略。 例如，考虑推断 typeof、instanceof 和比较操作结果的规则：

1
2
3
4
5
6
7
8
case is TypeOf:
    set(instr.output, environment.stringType)

case is InstanceOf:
    set(instr.output, environment.booleanType)

case is Compare:
    set(instr.output, environment.booleanType)

为了正确推断内置对象、方法和函数的类型，类型推断依赖于 JavaScript 运行时环境的静态模型，该模型可以例如告诉解释器 eval 内置函数是一个期望单个参数的函数，Object 内置函数是一个具有各种方法的对象，或者 Uint8Array 内置函数是一个返回 Uint8Array 实例的构造函数，然后该实例具有一组特定的属性和方法。

FuzzIL 的设计旨在使类型推断尽可能简单。 例如，考虑 ES6 类的实现。 在 FuzzIL 中，它们看起来大致像这样：

1
2
3
4
5
6
7
8
9
v0 <- BeginClassDefinition
ClassAddInstanceProperty "foo", v5
BeginClassInstanceMethod "bar" -> v8 (this), v9
    ... implementation of method "bar"
EndClassInstanceMethod
BeginClassInstanceMethod "baz" -> v6 (this)
    ... implementation of method "baz"
EndClassInstanceMethod
EndClassDefinition

根据这些，从 FuzzIL 代码推断类实例的类型相当简单：.object(withProperties: ["foo"], withMethods: ["bar", "baz"])。

有了可用的类型信息，上面的 CodeGenerator 现在可以请求一个包含函数的变量，并且还可以尝试查找与函数的参数类型兼容的变量：

1
2
3
4
5
CodeGenerator("FunctionCallGenerator") { b in
    let function = b.randomVariable(ofType: .function())
    let arguments = b.randomArguments(forCalling: function)
    b.callFunction(f, with: arguments)
}

但是，即使进行了此更改，如果参数值具有错误的类型，函数调用仍然会引发异常。 Fuzzilli 尝试通过两种方式来处理这个问题：

  1. 如果函数的类型已知（即其签名已知），randomArguments(forCalling:) 将尝试查找合适的参数。
  2. 如果没有找到匹配的参数（或者如果签名未知），生成器可以选择将调用操作标记为“受保护”。 这将导致在提升期间将其包装在 try-catch 中。

重要的是要注意，对于基于变异的模糊测试，JSTyper 和类型系统应被视为优化，而不是基本功能，因此模糊器仍然应该能够在没有类型信息的情况下运行。 此外，虽然使用类型信息进行变异可以提高模糊器的性能（产生较少明显不正确的样本），但过度依赖它可能会限制模糊器，从而对性能产生负面影响（产生较少多样化的样本）。 一个例子是 InputMutator，它可以选择是类型感知的，在这种情况下，它将尝试找到“兼容的”替换变量。 为了不过多地限制模糊器，Fuzzilli 的 MutationEngine 目前配置为同时使用非类型感知的 InputMutator 和类型感知的 InputMutator。

类型系统

实现：TypeSystem.swift

为了完成它的工作，JSTyper 需要一个类型系统。 FuzzIL 的类型系统旨在支持两个主要用例：

  1. 确定可以对给定变量执行的操作。 例如，类型系统需要说明对象上哪些属性和方法可用，以及它们的类型和签名是什么。
  2. 为给定操作找到一个兼容的变量。 例如，一个函数可能需要某种参数类型，例如 Number 或 Uint8Array。 类型系统必须能够表达这些类型，并且能够识别存储这种类型或子类型的值的变量。 例如，当需要 Uint8Array 时，可以使用具有附加属性的 Uint8Array，当需要父类时，可以使用子类的对象。

这两种操作都需要高效，因为它们将经常执行。

类型系统围绕位集构建，基本类型分别由 32 位整数中的单个位表示：

1
2
3
4
5
6
7
8
9
10
11
12
13
static let nothing     = BaseType([])
static let undefined   = BaseType(rawValue: 1 << 0)
static let integer     = BaseType(rawValue: 1 << 1)
static let bigint      = BaseType(rawValue: 1 << 2)
static let float       = BaseType(rawValue: 1 << 3)
static let boolean     = BaseType(rawValue: 1 << 4)
static let string      = BaseType(rawValue: 1 << 5)
static let regexp      = BaseType(rawValue: 1 << 6)
static let object      = BaseType(rawValue: 1 << 7)
static let function    = BaseType(rawValue: 1 << 8)
static let constructor = BaseType(rawValue: 1 << 9)
static let iterable    = BaseType(rawValue: 1 << 10)
static let anything    = BaseType([.undefined, .integer, .float, .string, .boolean, .object, .function, .constructor, .bigint, .regexp, .iterable])

每个基本类型都表示可以在其类型的某个值上执行某些操作（用例 1）。 例如，数值类型表示可以在其值上执行算术运算，.iterable 类型表示可以迭代该值（例如，通过 for-of 循环或使用扩展运算符），.object 类型表示该值具有可以访问的属性和方法，.function 类型表示可以使用函数调用来调用该值。

附加类型信息，例如属性和方法、函数的签名或数组的元素类型，存储在“类型扩展”对象中，这些对象可以在多个 Type 结构之间共享（以减少内存消耗）。

可以使用三个运算符组合基本类型以形成更复杂的类型：并集、交集和合并。 接下来将讨论这些。

Union Operator

Operator: | (按位或)

并集表示变量具有一种类型或另一种类型：类型 t1 | t2 表示值是 t1 或 t2。

在 Fuzzilli 中，并集类型经常作为函数的输入或输出类型出现。 例如，String.prototype.replace 方法可以将正则表达式对象或字符串作为第一个参数："replace" : [.string | .jsRegExp, .string] => .jsString。 此外，由于条件执行，也会出现并集类型：

1
2
3
4
5
let v4 = 42; 		// .integer
if (v2) {
    v4 = "foobar"; 	// .string
}
// v4 = .integer | .string
Intersection Operator

运算符：&（按位与）

交集运算符计算两个（并集）类型之间的交集。 例如，t1 | t2 与 t1 | t3 的交集是 t1。

在 Fuzzilli 中，此运算符用于确定变量是否可能具有某种类型，例如它是否可能是 BigInt，在这种情况下，许多算术运算符的结果类型也应包括 BigInt。

Merge Operator

运算符：+ (加号)

这个运算符可能是最不直观的，并且可能对这个类型系统来说是独一无二的。

本质上，如果一个变量具有合并类型 t1 + t2，那么它同时是两种输入类型。 因此，只要需要原始类型之一，就可以使用它。 为了理解为什么这可能有用，请考虑一些常见的 JavaScript 值：

  • 字符串："foobar" 虽然 JavaScript 字符串显然是“字符串”类型，这意味着例如它可以用于进行字符串连接，但它也是一个具有属性（例如 .length）和方法（例如 .charCodeAt）的对象。 此外，它也表现为数组，因为它可以迭代和扩展。 因此，JavaScript 字符串的类型将是 .string + .object(...) + .array
  • 函数：function foo(...) { ... } JavaScript 函数既是函数（可以调用），又是对象（具有属性和方法）。 因此，类型将是 .function(...) + .object(...)
  • 数组：[ ... ] JavaScript 数组是可迭代的，但也包含属性和方法，因此表示为 .array + .object(...)。

本质上，合并类型允许 FuzzIL 对 JavaScript 语言的动态特性进行建模，特别是经常执行的隐式类型转换以及许多事物（也）是对象这一事实。

Type Subsumption

运算符：<= 和 >=

为了支持类型查询（用例 2），类型系统实现了类型之间的蕴含关系。 这可以被认为是“是”关系，并且通常应该在搜索给定类型约束的“兼容”变量时使用。

一般的蕴含规则是：

  • 基本类型只蕴含自身（整数是整数但不是字符串）
  • 并集 t1 | t2 蕴含 t1 和 t2（字符串是“字符串或数字”）
  • 合并类型 t1 + t2 被 t1 和 t2 蕴含（JavaScript 函数既是函数又是具有属性和方法的对象）
  • 继承关系（包括添加的属性/方法）按预期工作：具有附加属性的 Uint8Array 仍然是 Uint8Array。 子类的实例也是父类的实例。
Implementation Details

类型实现为两个 32 位整数，一个存储明确类型，一个存储可能类型。 根据经验，明确类型通过合并增长，而可能类型通过并集增长。

由于这种表示形式，类型通常只能是并集类型或合并类型。 例如，不可能（如果尝试，将会导致运行时错误）合并并集类型，因为这无法正确表示。 然而，在实践中，这是不需要的，因此没有问题。 支持Union Merged types，但是，结果通常太宽泛。 例如，类型 (t1 + t2) | (t3 + t4) 将与类型 t1 | t2 | t3 | t4 无法区分。 因此，结果类型比必要的更宽泛，但仍然是正确的，因为结果类型蕴含两个输入类型。 同样，在实践中，这并不重要，因为这种情况仅在条件执行期间发生，在这种情况下，结果类型可能无论如何都无法以有意义的方式使用（它不能保证是任何类型，因此在需要其中一种类型时不能使用）。

Type Examples

为了更好地理解 FuzzIL 的类型系统，本节展示了一些常见的 JavaScript 值以及它们在 FuzzIL 中对应的类型。 也可以通过使用 --inspect=types 标志来检查这一点。 如果启用，写入磁盘的程序将包含变量类型的注释。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
let v0 = "foobar";
// .string + .object(...) + .array
// the object part contains all the standard string methods and properties

let v0 = { valueOf() { ...; return 13.37; }};
// .object(...) + .float
// The object can be used for numerical operations since it has a meaningful
// conversion operator defined (a custom valueOf method with known signature).
// Note: this is not yet implemented, currently the type would just be .object

let v0 = [...];
// .array + .object(...)
// the JavaScript array is clearly an array (can be iterated over) but also
// exposes properties and methods and as such is also an object

class v0 { ... foo() { ... }; bar() { ... } };
// .constructor([...] => .object(...))
// The variable v0 is a constructor with the parameters indicated by its
// constructor and which returns an object of the v0 "group" with certain
// properties and methods (e.g. foo and bar)

The Mutation Engine

实现: MutationEngine.swift（–engine=mutation）

本节将解释 Fuzzilli 的变异引擎是如何工作的。 为此，它首先介绍变异引擎的三个缺失组件，即最小化器、语料库和覆盖率收集，然后解释变异引擎使用的高级模糊测试算法。

Minimization

实现：Minimization/

Fuzzilli 执行的变异都有一个共同点：它们只能增加 FuzzIL 程序的大小（指令数量），而永远不会减小它。 因此，经过多轮变异后，程序最终会变得太大而无法在时限内执行。 此外，如果不从有趣的程序中删除不必要的功能，未来变异的效率会降低，因为许多变异将被“浪费”在变异不相关的代码上。 因此，Fuzzilli 需要一个最小化器，在程序插入语料库之前删除程序中不必要的代码。

最小化在概念上很简单：Fuzzilli 尝试识别和删除触发新发现的覆盖边缘不需要的指令 。 在最简单的情况下，这意味着删除单个指令，然后重新运行程序以查看它是否仍然触发新的边缘。 还有一些专门的最小化过程。 例如，有一个内联简化器，它尝试将函数内联到它们的调用点。 这是必要的，否则代码模式，例如

1
2
3
4
5
6
7
8
9
function v1(...) {
    function v2(...) {
        function v3(...) {
        }
        v3(...);
    }
    v2(...);
}
v1(...);

会随着时间的推移而构建，例如当从另一个程序中拼接函数调用和定义到当前程序中时。

可以想象，最小化非常昂贵，经常需要超过一百次执行。 然而，虽然最小化开销在模糊测试的早期阶段（当经常发现有趣的样本时）占主导地位，但在模糊测试的后期阶段（当很少发现新的、有趣的程序时），它接近于零。

可以通过 --minimizationLimit=N CLI 标志来调整最小化器以减少代码的积极程度。 这样，可以强制最小化器使最小化的程序保持在给定的指令数量之上。 这有助于保留一些可能有助于未来变异的额外代码片段。 这也可以稍微加快最小化速度，因为需要删除的指令更少。 但是，将此值设置得太高可能会导致与最小化器尝试首先解决的相同类型的问题。

除了删除指令，最小化器还尝试以其他方式简化程序。 例如，它尝试将受保护的操作转换为不受保护的操作，删除函数调用中不必要的参数，合并包含相同值的变量，并将一些复杂的指令转换为更简单的指令（例如，将扩展调用转换为常规调用）。

Corpus

实现：Corpus.swift

Fuzzilli 将“有趣的”样本保存在其语料库中以供未来变异。 在默认语料库实现中，样本被添加、然后随机变异，并在它们被变异至少一定次数后（通过 --minMutationsPerSample 标志控制）最终“退役”。 也可以实现其他语料库管理算法。 例如，已经实现了一种基于马尔可夫链的语料库管理算法。

如果使用 --storagePath CLI 标志，Fuzzilli 会将其添加到语料库中的所有样本以 protobuf 格式写入磁盘。 例如，这些可以通过 --resume 恢复之前的模糊测试会话，或者可以使用 FuzzILTool 进行检查。

Compiler

实现：Compiler/

默认情况下，Fuzzilli 始终从语料库中单个任意选择的程序开始。 可能希望从现有的程序语料库开始，例如查找过去错误的变体。 在 Fuzzilli 中，这需要从 JavaScript 到 FuzzIL 的编译器，因为 Fuzzilli 只能对 FuzzIL 程序进行操作。 Fuzzilli 附带了这样一个编译器，它使用 babel.js 来解析 JavaScript 代码，然后使用一个相对简单的编译器来处理生成的 AST 并从中生成 FuzzIL 程序。 该编译器尚未完成所有功能，需要支持更多的语言结构。

Coverage

实现：Evaluation/ 子目录

为了确定是否应将生成的程序添加到语料库中，Fuzzilli 依赖于代码覆盖率作为指导指标。 为了获得覆盖率信息，目标 JavaScript 引擎使用 -fsanitize-coverage=trace-pc-guard 进行编译，并且向其中添加了一个小代码存根，该代码存根通过 REPRL 接口在每次执行 JavaScript 程序期间收集边缘覆盖率信息。 在每次执行新生成的程序之后，都会处理覆盖率位图，以确定是否发现了 JavaScript 引擎控制流图中的任何新分支（因此覆盖率增加）。 如果是这样，则该样本被确定为有趣的，并在最小化后添加到语料库中。

应该注意的是，在 JIT 编译器的情况下，Fuzzilli 仅收集编译器代码上的覆盖率信息，而不收集生成代码上的覆盖率信息。 这比尝试检测生成的代码（如果原始 JavaScript 代码被变异，生成的代码将迅速改变）要简单得多。 此外，通常应该是这种情况，JIT 编译器仅编译已经执行多次的代码。 因此，生成的 JIT 代码之后也被执行的可能性应该相当高。 无论如何，研究是否可以将关于发出的 JIT 代码的覆盖率指导用作指导指标仍然是未来研究的主题。

关于确定性的一点说明

现代 JavaScript 引擎在后台线程上执行各种任务，例如 JIT 编译或垃圾回收。 除其他原因外，这可能导致非确定性行为：一个样本可能触发一次 JIT 编译器或 GC 边缘，但在随后的执行期间不会触发。 如果 Fuzzilli 保留了这样的样本，它将对变异引擎的有效性产生负面影响，例如因为 Fuzzilli 将无法最小化该样本，并且随后会“浪费”许多执行来尝试变异它。 为了处理这个问题，Fuzzilli 默认情况下确保新发现的样本能够确定性地触发新的边缘。 这是通过重复执行样本并形成触发边缘的交集来实现的，直到该交集变得稳定为止。 此外，在使用分布式模糊测试时，worker 实例在导入样本时会重新执行样本，从而也确保了确定性行为。

由于与非确定性行为相关的崩溃可能难以重现但仍然可能很有趣，因此 Fuzzilli 在重现器样本中包含了原始失败消息（例如，断言失败消息和堆栈跟踪）以及退出代码作为注释，以帮助进行分析。

变异算法

Fuzzilli 的变异引擎遵循基于变异的模糊器的典型过程：从语料库中获取一个样本（在 Fuzzilli 的例子中是一个 FuzzIL 程序），并变异给定的次数。 在变异期间，变量的类型通过 JSTyper 进行近似，以允许更智能的变异。 如果在任何时候，变异后的样本触发了新的覆盖率，则在最小化后将其添加到语料库中。 然而，为了实现高度的语义正确性，如果变异导致无效的程序，变异引擎将恢复变异。 这确保了高度的语义正确性，因为只有有效的程序被变异，并且因为每个变异只有相对较低的概率将有效的程序变为无效的程序。

变异引擎实现的高级算法总结在下图。

mutation_engine

当前变异引擎的局限性

免责声明：本节主要基于思维实验、现有的模糊测试研究、直觉、已发现（尤其是未发现）的漏洞以及偶尔的语料库检查，而不是专门的实验或测量。

本节试图从理论的角度讨论变异引擎的局限性。

可以将模糊器视为从可能的输入宇宙中进行采样的工具。 从这个角度来看，Fuzzilli 将从所有语法上有效的 JavaScript 程序的宇宙中进行采样。 Fuzzilli 的一个通用原则是，它不应该尝试（均匀地）从所有语法上有效的 JavaScript 程序的整个宇宙中进行采样，因为那个宇宙太大了。 因此，需要某种形式的指导来（希望）将模糊器引导到更有可能触发错误的样本。 在 MutationEngine 中，这种指导（主要）来自覆盖率反馈，它自动将模糊器引导到具有高复杂度的代码区域。 可以使用额外的、手动的指导来偏向模糊器，例如通过旨在触发 JIT 编译的特定 CodeGenerators。 这样，变异引擎基本上从可以通过将 N 个连续的变异应用于语料库中的程序而到达的程序集合中进行采样，而语料库中的程序是那些触发新覆盖率的程序。 此外，应该存在这样的情况：一个样本离语料库“越远”，就越不可能被发现，因为导致它的长度为 N 的可能变异“路径”的数量减少（即，一个非常接近语料库中样本的样本可能可以通过许多不同的变异来找到，而一个遥远的样本需要特定的变异序列才能到达）。

然后，MutationEngine 将能够找到与语料库中的错误有些“接近”的错误，但不能找到远离语料库的错误。

那么，关键问题是语料库中样本的分布可能是什么样子，因为它极大地影响了生成的样本的总体分布。 这里的论点是，语料库中的样本通常只会触发引擎的一个或几个特性，因为一个新程序不太可能一次触发多个新的、复杂的优化。 这可以通过查看典型语料库中样本的新发现的边缘数量（--inspect 将包含它）来在一定程度上进行测量。 下表显示了针对 JavaScriptCore 进行的具有大约 20000 个样本的模糊测试运行的结果：

新边的数量 样本数量 占总数的百分比 平均大小（以JS LoC为单位）
1 9631 48% 40
2-5 5999 30% 61
6-10 1580 8% 69
10+ 2849 14% 74

因此，MutationEngine 可能最大的缺点之一是它很难找到需要对相关对象执行多个不同操作的漏洞。 虽然覆盖率指导会奖励模糊器第一次触发每个操作的实现，但将它们组合成单个数据流不会有额外的奖励。 类似地，一旦模糊器触发了一次回调机制（例如 valueOf 回调或 Proxy 陷阱），它可能不会因为在不同的上下文（例如不同的内置函数）中触发相同的回调机制而获得奖励，尽管这可能会导致有趣的错误。

对此问题有许多可能的解决方案：

  • 设计一种替代指导指标，作为纯代码覆盖率的替代或补充，该指标引导模糊器发现现有指标难以发现的错误。 例如，该指标可以尝试将覆盖率反馈与某种形式的数据流分析相结合，以奖励模糊器在同一数据流上触发多个不同的特性。 这是未来研究的主题。
  • 从旧漏洞的概念验证代码或回归测试中为模糊器播种，以找到可以通过有些类似的代码触发的剩余错误。 这可以通过使用上面讨论的 FuzzIL 编译器将现有的 JavaScript 代码编译成 FuzzIL 语料库来实现。 这种方法本质上仅限于寻找与过去漏洞至少有些相似的错误。
  • 改进代码生成基础设施并使用它从头开始创建新程序，可能针对目标 JavaScript 引擎的特定错误类型或组件。 本文档的其余部分讨论了这种方法和实现它的 HybridEngine。

The HybridEngine

实现：HybridEngine.swift（--engine=hybrid）

HybridEngine 背后的核心思想是将代码生成与现有的变异和拼接机制相结合。 这实现了许多目标：

  • 通过配置生成的程序的形状和方面（例如，强调 JavaScript 引擎的某些区域或特定 API），可以实现手动模糊器指导。
  • 允许纯代码生成器保持相当简单，而是依赖于变异器使生成的代码更有趣或更正确。 特别是，FixupMutator 专门设计用于帮助 HybridEngine 生成正确且有意义的程序。
  • 它可以防止过度专业化，并提高发出的代码的多样性，因为变异（主要是输入和操作变异）是完全随机且无偏的（例如，它们忽略任何类型信息）。 因此，它们也经常导致语义上无效的样本。
  • 它使代码生成引擎能够“学习”有趣的代码片段，因为这些片段将被添加到语料库中（由于覆盖率反馈），然后用于拼接。 因此，即使在生成式模糊测试模式下，仍然使用代码覆盖率反馈。

与 MutationEngine 相比，HybridEngine 主要缺乏覆盖率指导。 因此，它需要以不同的方式解决许多问题：

1. 正确性问题

由于变异引擎会恢复无效的变异（那些导致引发运行时异常的变异），因此变异期间的代码生成可能有些激进，因此导致更多无效的样本。 然而，当从头开始生成整个程序时，生成的样本的正确率更为重要。 因此，代码生成器需要小心不要生成无效的代码。 这通过多种方式实现：

  • 代码生成器应选择正确类型的输入变量。 例如，发出函数调用的生成器应确保所选变量包含可调用的值。
  • 当代码生成器无法证明在运行时不会抛出异常时（这可能由于多种原因发生，包括当前没有所需类型的变量可用），可以使用受保护的指令（或显式的 try-catch 块）。 如上所述，FixupMutator 和 Minimizer 都会负责删除不必要的保护。
  • 还有一些其他的临时机制，试图防止无效程序的常见来源。 例如，ProgramBuilder 支持“递归保护”，它可以防止琐碎的递归。

2. 意义性问题

考虑以下代码：

1
2
let v0 = ...;
let v1 = v0 / {};

虽然语义上有效（运行时不会抛出异常），但该代码在很大程度上是语义上无意义的，因为它只会产生 NaN（非数字）值。 因此，无论 v0 的实际值如何，此代码的输出状态空间都是 1。 （大多数）无意义操作的其他示例包括加载或删除不存在的属性（这将始终导致未定义）、对没有自定义 toPrimitive 转换运算符的对象或非数字字符串执行任何类型的数学运算（算术运算符或 Math 函数）、将不正确类型的值作为参数传递给内置函数，或在非对象上存储属性。

理想情况下，“无意义”很可能被定义为始终导致引擎的相同内部状态转换，而不管输入类型和周围代码如何。 由于这很难衡量，Fuzzilli 对该术语的解释在很大程度上是模糊的近似值，因此 Fuzzilli 认为无意义的某些操作实际上会在某些引擎中引起一些有趣的行为。 然而，由于执行的变异，“无意义”的代码仍然会被生成（只是不是以不合理的高概率），希望允许发现相关的错误。

在变异引擎中，代码覆盖率与最小化器相结合有效地解决了这个问题：无意义的代码片段不会触发任何新的覆盖率，因此会在包含在语料库中之前被最小化器删除。 因此，语料库包含的主要是有意义的代码片段，因此生成的代码也主要是有意义的。

然而，生成式引擎没有依赖于覆盖率反馈的奢侈（除了拼接）。 因此，代码生成引擎的主要设计目标是努力以高频率生成有意义的代码，其中有意义的宽松定义是，对于给定的输入类型，输出可以根据输入值具有不同的值。 在实践中，这个例子意味着执行按位运算的 CodeGenerator 应该需要数值输入值而不是完全任意的输入值：

1
2
3
CodeGenerator("BitOp", inputs: .preferred(.number, .number)) { b, lhs, rhs in
    b.binary(lhs, rhs, with: chooseUniform(from: allBitwiseOperators))
}

此外，FixupMutator（最终）也旨在通过检测运行时无意义的操作并将它们更改为更有意义的操作来解决此问题。

3. 前瞻性问题

考虑 Fuzzilli 生成函数定义的情况（例如通过 PlainFunctionGenerator）：

1
2
3
function foo(v4, v5) {
    ...
}

在这里，当生成函数体时，v4 和 v5 的类型是未知的，因为它们只能在稍后调用该函数时由 JSTyper 观察到。 然而，如果参数只是设置为未知类型（FuzzIL 类型系统中的 .anything），那么主体中的代码将无法有意义地使用它们。

因此，解决方案是每次生成函数时都生成一个随机但非平凡的函数签名。 例如，在伪代码中：

1
2
3
4
function foo(v4: Number, v5: JSArray) -> JSArray {
    // 可以在这里有意义地使用 v4 和 v5
    ...;
}

这样，主体中的代码可以有意义地使用参数，并且它的返回值也可以被使用。 该函数将具有存储在其类型中的签名（就像内置函数和方法一样），因此将来对其进行的任何调用都将尝试获取正确类型的参数值。 生成签名时，会考虑当前可用的变量，以使生成无法满足的签名的概率非常低。

一个相关的问题是如何处理自定义对象类型，例如生成如下代码：

1
2
3
function foo(v3) {
    return v3.a.b.c;
}

为了使这成为可能，Fuzzilli 不仅必须知道 v3 的类型，还必须知道其属性的类型。

这可以通过预先生成许多自定义对象类型并在生成器中使用它们来类似地解决。 例如，以下类型可能用于上面的 v3：

1
2
3
4
5
6
7
v3 = .object("ObjType1", [
    .a: .object("ObjType2", [
        .b: .object("ObjType3", [
            .c: .integer
        ])
    ])
])

为了使此方法有效，生成对象或属性存储的代码生成器必须遵守这些属性类型。

程序模板

如前所述，需要某种指导机制将模糊器引导到代码的特定区域。 在 HybridEngine 中，这通过 ProgramTemplates 实现：程序结构的高级描述，然后从中生成具体的程序。 这有效地限制了搜索空间，因此可以更有效地发现漏洞。

接下来显示 ProgramTemplate 的示例。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ProgramTemplate("JITFunction") { b in
    // 从一个随机前缀和一些随机代码开始。
    b.buildPrefix()
    b.build(n: 5)

    // 生成一个较大的函数并为其生成一个签名
    let f = b.buildPlainFunction(with: b.randomParameters()) { args in
        assert(args.count > 0)
        b.build(n: 30)
        b.doReturn(b.randomVariable())
    }

    // 触发 JIT 优化
    b.buildRepeatLoop(n: 100) { _ in
        b.callFunction(f, withArgs: b.randomArguments(forCalling: f))
    }
}

这个相当简单的模板旨在通过生成一个随机函数，强制编译它，然后使用不同的参数再次调用它来搜索 JIT 编译器错误。

Example

以下是 HybridEngine 如何基于上述模板生成程序的示例。 请注意，并非所有 CodeGenerators 都已迁移以与 HybridEngine 很好地配合使用（例如，通过在必要时发出受保护的指令），因为这仍在进行中。

1. 前缀代码生成

该模板首先通过 b.buildPrefix() 方法生成一个小的“前缀”。 前缀只是代码片段，其目的是创建一些变量以供后续代码使用。 通常建议从这样的前缀开始，因为它确保 CodeGenerators 具有可见变量以用作输入。 在底层，前缀生成执行代码生成，但只使用标记为“值生成器”的一小部分代码生成器。 这些必须始终生成新变量并且不得失败。 结果可能是一段代码，例如

1
2
3
v0 <- LoadInt '42'
v1 <- LoadInt '1337'
v2 <- LoadString 'foo'
2. 随机代码生成

模板的下一部分只是使用主代码生成 API：ProgramBuilder.build(n:) 生成几个随机指令。 对于代码生成，ProgramBuilder 将重复选择随机 CodeGenerators 并运行它们，直到至少生成 n 个指令。 例如，CodeGenerator 可以如下所示：

1
2
3
4
CodeGenerator("BinOp", inputs: .preferred(.number, .number)) { b, lhs, rhs in
    let needGuard = b.type(of: lhs).MayBe(.bigint) || b.type(of: rhs).MayBe(.bigint)
    b.binary(lhs, rhs, with: chooseUniform(from: allBinaryOperators), guard: needGuard)
}

请注意，生成器如何小心地生成正确且有意义的代码，同时又不对其输入要求过于严格。 它的做法是声明它“希望”接收数字作为输入（这意味着如果有可用的变量，则应使用数字调用它，但也可以使用不同类型的变量调用），然后检查其中一个输入是否可能是 BigInts（在这种情况下，很可能会出现运行时异常：“TypeError: Cannot mix BigInt and other types, use explicit conversions”），如果是，则将操作标记为受保护的（导致在运行时使用 try-catch）。

在此上下文中，可以使用 v0 和 v1 调用生成器：

1
v3 <- Binary v0, '*', v1

由于静态已知两个输入的类型都不是 BigInts，因此不需要任何保护。

此时，只生成了一个新指令，因此代码生成将继续。 然而，为了简洁起见，在本例中我们将在此处停止代码生成并继续到模板的下一部分。

3. 函数生成

模板的下一部分负责生成一个随机函数。 为此，第一步是使用 ProgramBuilder.randomParameters API 生成一个随机签名。 这将查看现有变量及其类型，并基于它们选择签名。 这样，以后很有可能找到合适的参数值。 在此特定情况下，它可以提出诸如 [.string, .int] 之类的签名，因为存在两种类型的现有变量。 请注意，签名尚不包括返回值类型。 这将仅在函数定义结束时根据函数体内部生成的 Return 语句来计算。

生成签名后，模板将创建函数并使用代码生成机制填充其主体。 这次，我们将使用以下三个代码生成器：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
CodeGenerator("BuiltinGenerator") { b in
    b.loadBuiltin(b.randomBuiltin())
},

CodeGenerator("FunctionCallGenerator", inputs: .preferred(.function())) { b, f in
    let arguments = b.randomArguments(forCalling: f)
    let needGuard = b.type(of: f).MayNotBe(.function())  // 技术上，如果参数类型与签名不匹配，也需要保护
    b.callFunction(f, withArgs: arguments, guard: needGuard)
},

CodeGenerator("ComputedPropertyAssignmentGenerator", inputs: .preferred(.object())) { b, obj in
    let propertyName = b.randomVariable()
    let value = b.randomVariable()
    let needGuard = b.type(of: obj).MayBe(.nullish)
    b.setComputedProperty(propertyName, of: obj, to: value, guard: needGuard)
},

运行第一个生成器时，ProgramBuilder.randomBuiltin API 将查询静态环境模型以查找可用的内置函数。 在这种情况下，环境模型可能包含以下内置函数：bar: .function([] => .anything)，然后选择它。 接下来，代码生成可能会选择 FunctionCallGenerator。 因为它声明它需要 .function() 作为参数，所以 ProgramBuilder 会（可能）选择先前加载的内置函数。 因为它的签名是已知的，所以没有为调用选择任何参数值，并且返回值类型为 .anything。 最后，代码生成可能会选择 ComputedPropertyAssignmentGenerator。 因为当前没有类型为 .object() 的可用值，所以函数调用的返回值（可能）会被选择，因为它具有类型 .anything。 这样，至少有机会使该值在运行时成为对象。 由于不能排除该值不是“nullish”（null 或 undefined）的情况，在这种情况下会引发运行时异常，因此代码生成器将操作标记为受保护的。 将所有内容放在一起，为函数生成以下代码：

1
2
3
4
5
6
v4 <- BeginPlainFunction -> v5, v6
    v7 <- LoadBuiltin 'bar'
    v8 <- CallFunction v7, []
    SetComputedProperty v8, v5, v6 (guarded)
    Return v8
EndPlainFunction
4. 组合各个部分

模板的其余部分只是生成一个循环来调用在步骤 3 中生成的函数。 通常，应该使用不同的参数再次调用该函数几次，并且可能在执行更多随机生成的代码之后。 为了使本示例保持简短，此处省略了这些步骤。

提升到 JavaScript（使用表达式内联），生成的代码现在将是：

1
2
3
4
5
6
7
8
function f4(a5, a6) {
    let v8 = bar();
    try { v8[a5] = a6; } catch {}
    return v8;
}
for (let v9 = 0; v9 < 100; v9++) {
    f6("foo", 42 * 1337);
}

生成后，样本将被进一步变异。 由于 FixupMutator 对于 HybridEngine 特别有用，因此它始终用作第一个变异器，以“完善”生成的程序。 在这种情况下，变异器可能会发现不需要 try-catch 保护（如果它在运行时从未触发），因此可以将其删除，从而产生最终的（“完善的”）程序：

1
2
3
4
5
6
7
8
function f4(a5, a6) {
    let v8 = bar();
    v8[a5] = a6;
    return v8;
}
for (let v9 = 0; v9 < 100; v9++) {
    f6("foo", 42 * 1337);
}

随后的变异可能会以各种有趣（和不太有趣）的方式更改生成的程序。

Code Generation + Mutations: The HybridEngine

HybridEngine 将代码生成引擎与现有的变异器结合在一起。 为此，它首先选择一个随机 ProgramTemplate，然后使用如前所述的代码生成引擎从中生成一个程序。 如果生成的程序有效，它将使用 Mutationengine 也使用的算法进一步变异几次。

混合引擎使用的高级算法总结在下图。

hybrid_engine

HybridEngine 可以通过不同的方式使用。接下来将讨论这些内容。

Application: Component Fuzzing

通过 ProgramTemplates，可以将模糊器引导到引擎的主要组件，例如 JIT 编译器。 除了对目标代码（以及可能其中的过去错误）有高级别的理解之外，这种模板可能几乎不需要任何努力。

应用：补丁正确性验证和变体模糊测试

HybridEngine 的另一个应用是搜索先前错误的变体。

这种技术的一个很好的例子是 V8MapTransition 模板。 该模板搜索 CVE-2020-16009 的变体（并尝试验证补丁的正确性）。 这个想法只是将代码生成引擎限制为一小组 JavaScript 特性，即对象字面量、属性加载和存储以及函数定义和调用，以减少搜索空间。 该模板成功地在数亿次执行中再次触发了原始漏洞，从而证明了该技术是可行的。

Application: Targeted Fuzzing

此应用与前一个应用类似，不同之处在于它不是从现有错误开始的。 相反，安全研究人员或开发人员必须首先确定目标引擎中可能容易出现复杂错误的特定功能，然后开发一个模板来尽可能好地强调该组件。

与第一个应用相比，这种模板需要对目标源代码区域有相当深入的了解，例如，为了确定需要生成哪些类型的代码片段以及不需要生成哪些类型的代码片段。 另一方面，它应该效率更高。

MutationEngine vs. HybridEngine

本节简要比较Fuzzilli中使用的两种引擎。

MutationEngine HybridEngine
遵循通用指导算法，几乎不需要手动调整即可生成有趣的 JavaScript 代码 需要手动指导，以程序模板和代码生成器形式
生成的样本对控制的余地很小，因为它们主要是由覆盖率反馈决定的。影响代码的可能方法包括代码生成器及其相对权重、突变体以及最小化器的侵略性。 允许对生成的代码有大量控制，包括对高级结构（例如，一个正在 JIT 编译的函数，然后被调用几次）以及通过代码生成器对低级代码片段的控制
能够发现与样本“相似”的漏洞，从而触发新的覆盖率（因此被添加到语料库中），但可能难以发现不是这种情况的漏洞。后者可能包括需要通过多个不同的代码路径进行复杂状态操作的漏洞 能够找到与所使用的 ProgramTemplates 之一“相似”的漏洞，这些模板可能来自过去的漏洞、希望测试特定区域的开发者或希望测试代码库复杂区域的审计员

由于这两个引擎相互补充，因此可能需要在同一个模糊测试会话中同时运行这两个引擎。 至少在理论上，这两个引擎也应该能够相互受益：变异引擎可以进一步变异来自 HybridEngine 的样本，而 HybridEngine 可以（通过拼接）从由 MutationEngine 构建的更好的语料库中受益。 因此，MultiEngine（--engine=multi）允许在一个模糊测试会话中使用这两个引擎，并允许大致控制每个引擎的调度频率。

源码分析

一次周期内，Fuzzilli的执行流分析。

基本架构：由main.swift开始

FUZZILLI/Sources/FuzzilliCli/main.swift主要是对参数的读取、初始化、以及启动Fuzz loop。

创建好CodeGenerator加权列表用于后续的随机选择：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 是否启用WasmCodeGenerator
let codeGeneratorsToUse = if enableWasm {
    CodeGenerators + WasmCodeGenerators
} else {
    CodeGenerators
} 
// 设置CodeGenerator权重
let standardCodeGenerators: [(CodeGenerator, Int)] = codeGeneratorsToUse.map {
    guard let weight = codeGeneratorWeights[$0.name] else {
        logger.fatal("Missing weight for code generator \($0.name) in CodeGeneratorWeights.swift")
    }
    return ($0, weight)
}
// 创建一个空的加权列表来存储CodeGenerator
var codeGenerators: WeightedList<CodeGenerator> = WeightedList<CodeGenerator>([])
// 遍历所有Generator，跳过被禁用的Generator
for (generator, var weight) in (additionalCodeGenerators + standardCodeGenerators) {
    if disabledGenerators.contains(generator.name) {
        continue
    }

    if swarmTesting {
        weight = Int.random(in: 1...30)
        logger.info(String(format: "%6d | \(generator.name)", weight))
    }

    codeGenerators.append(generator, withWeight: weight)
}

接下来是loadCorpus函数的定义，用于从指定目录加载文件。生成的programs是该目录下的文件列表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func loadCorpus(from dirPath: String) -> [Program] {
    var isDir: ObjCBool = false
    guard FileManager.default.fileExists(atPath: dirPath, isDirectory: &isDir) && isDir.boolValue else {
        logger.fatal("Cannot import programs from \(dirPath), it is not a directory!")
    }

    var programs = [Program]()
    let fileEnumerator = FileManager.default.enumerator(atPath: dirPath)
    // 遍历目录的每个文件
    while let filename = fileEnumerator?.nextObject() as? String {
        guard filename.hasSuffix(".fzil") else { continue }
        let path = dirPath + "/" + filename
        do {
            let data = try Data(contentsOf: URL(fileURLWithPath: path))
            let pb = try Fuzzilli_Protobuf_Program(serializedBytes: data)
            let program = try Program.init(from: pb)
            if !program.isEmpty {
                programs.append(program)
            }
        } catch {
            logger.error("Failed to load program \(path): \(error). Skipping")
        }
    }

    return programs
}

然后是makeFuzzer函数，这个函数的定义很长，用来初始化并配置一个Fuzzer示例，代码就不放了。简单分析一下：

1
func makeFuzzer(with configuration: Configuration) -> Fuzzer
  • 作用：根据传入的Configuration配置，构建并返回一个完整的Fuzzer实例。
1
let runner = REPRL(executable: jsShellPath, processArguments: jsShellArguments, processEnvironment: profile.processEnv, maxExecsBeforeRespawn: profile.maxExecsBeforeRespawn) // 在插桩的JavaScript引擎中运行测试代码。

REPRL为在被插装的JS引擎中执行js代码的script runner

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 为各个变异器分配权重，如（ExplorationMutator权重为3，更频繁使用）。
// mutator负责根据语料库变异程序并且评估结果
var mutators = WeightedList([
        (ExplorationMutator(),                 3),
        (CodeGenMutator(),                     2),
        (SpliceMutator(),                      2),
        (ProbingMutator(),                     2),
        (InputMutator(typeAwareness: .loose),  2),
        (InputMutator(typeAwareness: .aware),  1),
        // Can be enabled for experimental use, ConcatMutator is a limited version of CombineMutator
        // (ConcatMutator(),                   1),
        (OperationMutator(),                   1),
        (CombineMutator(),                     1),
        // Include this once it does more than just remove unneeded try-catch
        // (FixupMutator()),                   1),
    ])

前面的文档中提及过的FuzzEngine：

1
2
3
4
5
6
7
8
9
10
switch engineName {
    case "hybrid":
    engine = HybridEngine(numConsecutiveMutations: consecutiveMutations)
    case "multi":
    let mutationEngine = MutationEngine(numConsecutiveMutations: consecutiveMutations)
    let hybridEngine = HybridEngine(numConsecutiveMutations: consecutiveMutations)
    let engines = WeightedList<FuzzEngine>([
        (mutationEngine, 1),
        (hybridEngine, 1),
    ])

其余的还有程序模板（ProgramTemplates），JavaScriptEnvironment是管理可用的内置函数、属性名和方法名，可以通过配置文件来添加自定义内置函数。ProgramCoverageEvaluator接收覆盖率数据。还有lifter，Corpus以及Minimizer。就不赘述了。

然后是调用Configuration函数进行配置信息的初始化：

1
2
3
4
5
6
7
8
9
let mainConfig = Configuration(arguments: CommandLine.arguments,
                               timeout: UInt32(timeout),
                               logLevel: logLevel,
                               startupTests: profile.startupTests,
                               minimizationLimit: minimizationLimit,
                               enableDiagnostics: diagnostics,
                               enableInspection: inspect,
                               staticCorpus: staticCorpus,
                               tag: tag)

再调用makeFuzzer函数以config来创建一个Fuzzer实例。再初始化信号处理器，在接收到终止信号时能够优雅地关闭fuzzer（这是一种标准的Swift信号处理模式，适用于需要优雅地退出的命令行工具或服务）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Install signal handlers to terminate the fuzzer gracefully.
var signalSources: [DispatchSourceSignal] = []
for sig in [SIGINT, SIGTERM] {
    // Seems like we need this so the dispatch sources work correctly?
    signal(sig, SIG_IGN)

    let source = DispatchSource.makeSignalSource(signal: sig, queue: DispatchQueue.main)
    source.setEventHandler {
        fuzzer.async {
            fuzzer.shutdown(reason: .userInitiated)
        }
    }
    source.activate()
    signalSources.append(source)
}

然后fuzzer.sync，它初始化关键模块（统计数据，存储，网络同步等）。网络同步是分布式模糊测试，支持多机协同（主节点发 任务，子节点执行），随后又一个ThreadParent(for: fuzzer)多线程并行，最后三步是fuzzer.initialize()初始化所有模块，fuzzer.runStartupTests()运行基础测试，确保各个模块，引擎等正常工作。最后fuzzer.start(runUntil: exitCondition)，启动fuzz loop。

首先看一下Fuzzer对象的ShutDownComplete事件对象上挂载了一个回调函数（称为listener），用于在Fuzzer退出时做一些收尾工作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
fuzzer.sync {   // 向fuzzer的dispath queue发送一个回调函数, 并等待任务完成 
    ...

    // 当主fuzzer完全停止时, 退出这个进程
    fuzzer.registerEventListener(for: fuzzer.events.ShutdownComplete) { reason in
        if resume, let path = storagePath {
            // Check if we have an old_corpus directory on disk, this can happen if the user Ctrl-C's during an import.
            if FileManager.default.fileExists(atPath: path + "/old_corpus") {
                logger.info("Corpus import aborted. The old corpus is now in \(path + "/old_corpus").")
                logger.info("You can recover the old corpus by moving it to \(path + "/corpus").")
            }
        }
        exit(reason.toExitCode())    // 整个进程退出, 所有线程被kill
    }
    ...
}

进一步了解Fuzzer的事件机制

Event<T>类的定义如下，发现Event其实是一个listener容器，表示该事件发生时所有要回调的listener，T则代表回调函数的参数类型

1
2
3
4
5
6
7
8
9
10
11
public class Event<T> {
    public typealias EventListener = (T) -> Void			// 事件监听器也就是listener的类型

    /// The list of observers for this event.				// 所有监听该事件的listener组成的数组
    private(set) public var listeners = [EventListener]()

    /// Registers an event listener for this event.			// 向该事件中注册listener
    public func addListener(_ listener: @escaping EventListener) {
        listeners.append(listener)
    }
}

Events则是各种类型的集合，包含所有可以被分派给fuzzer的事件，部分事件如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/// List of all events that can be dispatched in a fuzzer.
public class Events {
    /// Signals that the fuzzer is fully initialized. fuzzer被完全初始化
    public let Initialized = Event<Void>()

    /// Signals that a this instance is shutting down.	fuzzer即将被关闭
    public let Shutdown = Event<ShutdownReason>()

    /// Signals that this instance has successfully shut down.	fuzzer被成功关闭
    /// Clients are expected to terminate the hosting process when handling this event.
    public let ShutdownComplete = Event<ShutdownReason>()

    /// Signals that a log message was dispatched.	一个日志信息被发送
    /// The origin field contains the UUID of the fuzzer instance that originally logged the message.
    public let Log = Event<(origin: UUID, level: LogLevel, label: String, message: String)>()

    /// Signals that a new (mutated) program has been generated.	一个新的（变异后的）程序被生成
    public let ProgramGenerated = Event<Program>()

    /// Signals that a valid program has been found.			一个合法程序被发现
    public let ValidProgramFound = Event<Program>()

}

因此fuzzer.registerEventListener()其实就是把listener回调添加到event.listeners数组中

1
2
3
4
public func registerEventListener<T>(for event: Event<T>, listener: @escaping Event<T>.EventListener) {
    dispatchPrecondition(condition: .onQueue(queue))
    event.addListener(listener)
}

listener被触发的流程：

  • 以ShutdownComplete时间为例，在fuzz循环次数到达限制或者时间到达限制后会调用Fuzzer::shutdown()方法退出fuzz
  • 该方法会执行dispatchEvent(events.ShudownComplete, data: reason)表示以参数data触发ShutdownComplete事件对象上的所有listener
  • 而dispatchEvent()会直接回调event.listeners数组中所有的事件监听器
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// Store samples to disk if requested.
if let path = storagePath {			// 把生成的样本保存在磁盘中， 参数--storagePath被设置时
    if resume {	// 恢复模式：将旧语料库移动到old_corpus，并后续导入
        // Move the old corpus to a new directory from which the files will be imported afterwards
        // before the directory is deleted.
        if FileManager.default.fileExists(atPath: path + "/old_corpus") {
            logger.fatal("Unexpected /old_corpus directory found! Was a previous import aborted? Please check if you need to recover the old corpus manually by moving to to /corpus or deleting it.")
        }
        do {
            try FileManager.default.moveItem(atPath: path + "/corpus", toPath: path + "/old_corpus")
        } catch {
            logger.info("Nothing to resume from: \(path)/corpus does not exist")
            resume = false
        }
    } else if overwrite {	// 覆盖模式：清空存储目录
        logger.info("Deleting all files in \(path) due to --overwrite")
        try? FileManager.default.removeItem(atPath: path)
    } else {
        // The corpus directory must be empty. We already checked this above, so just assert here
        let directory = (try? FileManager.default.contentsOfDirectory(atPath: path + "/corpus")) ?? []
        assert(directory.isEmpty)
    }
	// 添加存储模块
    fuzzer.addModule(Storage(for: fuzzer,
                             storageDir: path,
                             statisticsExportInterval: exportStatistics ? Double(statisticsExportInterval) * Minutes : nil
                            ))
}

Storage模块：负责将测试用例和Crash数据存储到磁盘中。

下面研究一下什么是模块，Module接口的定义如下，该接口只要求实现一个initialize()方法，该方法会在Fuzzer的对象初始化完毕之后回调，用于进行模块初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
extension Module {
    // initialize()方法会在fuzzer完全完全初始化并且能够执行程序时调用
    // 此时，其他模块将要被初始化但是还没有完全初始化
    public func initialize(with fuzzer: Fuzzer) {}

    public var name: String {
        return String(describing: type(of: self))
    }

    public static var name: String {
        return String(describing: self)
    }

    /// Returns the instance of this module on the provided fuzzer instance if it exists, nil otherwise.
    public static func instance(for fuzzer: Fuzzer) -> Self? {
        if let instance = fuzzer.modules[self.name] {
            return instance as? Self
        } else {
            return nil
        }
    }
}

以Storage模块为例子，该模块初始化时会向Fuzzer对象的CrashFound和InterestingProgramFound事件注册回调，用于在发现crash和interesting prog时将其保存在磁盘中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Storage: Module {

    // fuzzer对象初始化完毕后回调该模块的该方法, 负责对fuzzer对象进行初始化
    public func initialize(with fuzzer: Fuzzer) {
        ...

        // 在fuzzer中注册事件回调, 在发现crash时写入到磁盘中
        fuzzer.registerEventListener(for: fuzzer.events.CrashFound) { ev in
            let filename = "program_\(self.formatDate())_\(ev.program.id)_\(ev.behaviour.rawValue)"
            if ev.isUnique {
                self.storeProgram(ev.program, as: filename, in: self.crashesDir)
            } else {
                self.storeProgram(ev.program, as: filename, in: self.duplicateCrashesDir)
            }
        }

        // 注册事件回调: 发现interesting prog时写入到磁盘中
        fuzzer.registerEventListener(for: fuzzer.events.InterestingProgramFound) { ev in
            let filename = "program_\(self.formatDate())_\(ev.program.id)"
            self.storeProgram(ev.program, as: filename, in: self.corpusDir)
        }
        ...
    }
}

可以发现，Fuzzer对象初始化完毕后回调模块中的initialize()方法，各个模块可以根据需求对Fuzzer进行一些修改以实现功能。

1
2
3
4
5
fuzzer.initialize()			// fuzzer对象的初始化
fuzzer.runStartupTests()	// 进行fuzz loop启动前的测试

// Start the main fuzzing job.
fuzzer.start(runUntil: exitCondition)

Fuzzer::initial()会调用所有依赖组件的initialize()方法，完成依赖组件的初始化，至此Fuzzer对象才算是初始化完毕；然后回调所有模块的初始化方法，完成模块的安装；最后发送Initialized事件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
public func initialize() {
    dispatchPrecondition(condition: .onQueue(queue))
    assert(!isInitialized)

    // Initialize the script runner first so we are able to execute programs.
    // 初始化脚本执行器，这样就可以执行js脚本了
    runner.initialize(with: self)

    // Then initialize all components. 初始化所有组件
    engine.initialize(with: self)
    evaluator.initialize(with: self)
    environment.initialize(with: self)
    corpus.initialize(with: self)
    minimizer.initialize(with: self)
    corpusGenerationEngine.initialize(with: self)

    // Finally initialize all modules. 初始化所有模块
    for module in modules.values {
        module.initialize(with: self)
    }

    // Install a watchdog to monitor the utilization of this instance. 安装一个watchdog监控这个实例的使用情况
    var lastCheck = Date()
    timers.scheduleTask(every: 1 * Minutes) {
        // Monitor responsiveness
        let now = Date()
        let interval = now.timeIntervalSince(lastCheck)
        lastCheck = now
        if interval > 180 {
            self.logger.warning("Fuzzer appears unresponsive (watchdog only triggered after \(Int(interval))s instead of 60s).")
        }
    }

    // Install a timer to monitor for faulty code generators and program templates. 安装一个计时器来监视错误的代码生成器和程序模板
    timers.scheduleTask(every: 5 * Minutes) {
        for generator in self.codeGenerators {
            if generator.totalSamples >= 100 && generator.correctnessRate < 0.05 {
                self.logger.warning("Code generator \(generator.name) might be broken. Correctness rate is only \(generator.correctnessRate * 100)% after \(generator.totalSamples) generated samples")
            }
        }
        for template in self.programTemplates {
            if template.totalSamples >= 100 && template.correctnessRate < 0.05 {
                self.logger.warning("Program template \(template.name) might be broken. Correctness rate is only \(template.correctnessRate * 100)% after \(template.totalSamples) generated samples")
            }
        }
    }

    // Determine our initial state if necessary.
    assert(state == .uninitialized || state == .corpusImport)
    if state == .uninitialized {
        let isChildNode = modules.values.contains(where: { $0 is DistributedFuzzingChildNode })
        if isChildNode {
            // We're a child node, so wait until we've received some kind of corpus from our parent node.
            // We'll change our state when we're synchronized with our parent, see updateStateAfterSynchronizingWithParentNode() below.
            changeState(to: .waiting)
        } else {
            // Start with corpus generation.
            assert(corpus.isEmpty)
            changeState(to: .corpusGeneration)
        }
    }

    dispatchEvent(events.Initialized)		// 触发事件：Fuzzer已初始化
    logger.info("Initialized")
    isInitialized = true
}

最后通过fuzzer.start()启动fuzz loop

1
2
3
4
5
6
7
8
9
10
11
12
public func start(runUntil exitCondition: ExitCondition = .none) {
    // 线程安全检查
    dispatchPrecondition(condition: .onQueue(queue))
    // 状态检查
    assert(isInitialized)
	// 设置退出条件
    self.exitCondition = exitCondition
	
    logger.info("Let's go!")
	// 调用FuzzOne，Fuzz一轮。和AFL++的Fuzz_one一样
    fuzzOne()
}

执行fuzzOne()开始第一次fuzz，注意fuzzer.sync{...}是同步任务，所以此时是主线程在执行fuzzOne()，Fuzzer:fuzzOne()函数如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
public class Fuzzer {
    // fuzzOne()在主线程执行一次后会通过DispatchQueue在另一个线程不断循环调用自身, 实现fuzz事件循环
    private func fuzzOne() {
        ...
        // 检查是否fuzz结束
        switch exitCondition {
        case .none:
            break
        case .iterationsPerformed(let maxIterations):   // 迭代次数到达上限
            if iterations > maxIterations {
                return shutdown(reason: .finished)
            }
        case .timeFuzzed(let maxRuntime):   // 执行时间到达上线
            if uptime() > maxRuntime {
                return shutdown(reason: .finished)
            }
        }

        // 根据当前fuzzer实例的状态进行处理, 真正干活的部分
        switch state {
        case .uninitialized:
            ...
        case .waiting:
            ...

        case .corpusImport: // 导入语料库, Fuzzer初始化完毕后就是该状态
            let program = currentCorpusImportJob.nextProgram()

            if currentCorpusImportJob.numberOfProgramsImportedSoFar % 500 == 0 {
                logger.info("Corpus import progress: imported \(currentCorpusImportJob.numberOfProgramsImportedSoFar) of \(currentCorpusImportJob.totalNumberOfProgramsToImport) programs")
            }

            let outcome = importProgram(program, origin: .corpusImport(mode: currentCorpusImportJob.importMode))    // 导出语料
            currentCorpusImportJob.notifyImportOutcome(outcome)

            if currentCorpusImportJob.isFinished {    // 导入完毕
                ...
                dispatchEvent(events.CorpusImportComplete)    // 触发事件
                changeState(to: .fuzzing)    // 状态改变成.fuzzing
            }

        case .corpusGeneration: // 在没有起始语料的情况下, 用于生成语料并进行fuzz
            ...

        case .fuzzing:  // 使用生成的语料对引擎进行fuzz
            iterations += 1
            engine.fuzzOne(fuzzGroup)   // 使用fuzz引擎进行一轮的fuzz
        }

        // 一旦本次迭代的相关任务都处理完毕, 就立刻发送任务进行下一次迭代
        // 一旦queue中的任务执行完毕, 就回调{self.fuzzOne()}从而再次执行
        // 这样就相当于通过DispatchGroup在另一个线程中开启了一个不断调用self.fuzzOne()的循环
        fuzzGroup.notify(queue: queue) {
            self.fuzzOne()  // Fuzzer::fuzzOne
        }
    }

    ...
}

需要关注两点：

  1. Fuzzer对象的状态变化：在提供初始语料库的情况下，Fuzzer对象的状态变化为unintialized=>corpusImport=>fuzzing。Fuzzer:fuzzOne()会根据当前不同的状态做不同的处理
  2. 线程调度：Fuzzer::fuzzOne()每处理一次当前状态，都会调用fuzzGroup.notify()开启下一轮迭代。

整体线程执行模型可以概况如下：

  • 第一次调用fuzzOne()时由主线程执行，会执行fuzz相关的任务，在处理过程中外部有可能向queue中添加异步任务
    • 本轮处理完毕后，主线程会执行fuzzGroup.notify(queue){...}添加一个异步任务：在queue中所有的任务处理完毕后触发回调，执行fuzzOne()开启新一轮的fuzz。主线程不会阻塞在fuzzGroup上，而是直接返回，然后永久等待。
    • 后续swift会自动从线程池中调用线程处理queue和fuzzGroup中的异步任务，因此第二次再执行fuzzOne()时就是其他进程了
    • 第二次fuzzOne()的执行过程与上述类似，最后又会通过fuzzGroup开启新一轮的循环

接下来是一个多线程的操作以及工作实例的配置。

1
2
3
4
5
6
7
8
9
10
11
let workerConfig = Configuration(
    arguments: CommandLine.arguments,
    timeout: UInt32(timeout),
    logLevel: .warning,  // 比主实例更低的日志级别
    startupTests: profile.startupTests,
    minimizationLimit: minimizationLimit,
    enableDiagnostics: false,  // 禁用诊断（减少开销）
    enableInspection: inspect,
    staticCorpus: staticCorpus,
    tag: tag
)

工作实例与之前的Fuzzer实例基本相同，logLevel: .warning减少日志输出，避免干扰。同时enableDiagnostics: false禁用调试功能，提升性能。接下来就是多线程工作实例的创建了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 创建多个从（子）Fuzzer对象
for _ in 1..<numJobs {
    let worker = makeFuzzer(with: workerConfig)		// 为其子worker创建Fuzzer对象
    worker.async {	// 子worker异步初始化
        // Wait some time between starting workers to reduce the load on the main instance.
        // If we start the workers right away, they will all very quickly find new coverage
        // and send lots of (probably redundant) programs to the main instance.
        // 启动从Fuzzer对象(主进程的是主Fuzzer对象)前随机等待
        let minDelay = 1 * Minutes			
        let maxDelay = 10 * Minutes
        let delay = Double.random(in: minDelay...maxDelay) // 随机延迟（1 ~ 10min）
        Thread.sleep(forTimeInterval: delay)

        worker.addModule(Statistics())	// 统计模块
        worker.addModule(ThreadChild(for: worker, parent: fuzzer))	// 子线程模块，负责与主实例通信，将发现的新覆盖率程序或崩溃发送回主实例
        worker.initialize()	//Fuzzer对象初始化
        worker.start()	// 开始fuzz
    }
}

其中，numJobs是参数中配置的（默认为1）。随后使用makeFuzzer创建Fuzzer实例，然后加入线程worker中。避免所有工作实例同时发现新覆盖率，导致主实例被大量程序同步淹没，随机延迟1~10分钟使得工作实例负载均匀分布。

最后是main.swift的结束：

1
RunLoop.main.run()	// 主线程持续运行，开始在主任务队列中调度任务

这是Swift中用于启动主线程事件的循环核心方法，它会启动主线程的RunLoop，RunLoop.main.run()会阻塞主线程，并持续处理事件。

接下来进一步看一轮fuzz中所做的事。

之前看到Fuzzer::fuzzOne()会调用engine.fuzzOne(fuzzGroup)进行一轮fuzz，由于前面文档所说的三种Engine，这里我们选取最基本的MutationEngine为例子。也就是engine.fuzzOne(fuzzGroup)，engine是MutationEngine

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public override func fuzzOne(_ group: DispatchGroup) {
    var parent = fuzzer.corpus.randomElementForMutating()	//从种子池中随机选择一个种子用于变异
    parent = prepareForMutating(parent)		// 进行变异前准备
    for _ in 0..<numConsecutiveMutations {	// 生成种子的数量，也就是变异轮次
        // TODO: factor out code shared with the HybridEngine?
        var mutator = fuzzer.mutators.randomElement()	//随机选择一个变异器
        let maxAttempts = 10		// 一个种子最多尝试变异次数为10次
        var mutatedProgram: Program? = nil
        for _ in 0..<maxAttempts {
            if let result = mutator.mutate(parent, for: fuzzer) {	// 变异成功则停止
                // Success!
                result.contributors.formUnion(parent.contributors)
                mutator.addedInstructions(result.size - parent.size)
                mutatedProgram = result
                break
            } else {
                // Try a different mutator.
                // 变异失败，则重新随机选择一个变异器进行变异
                mutator.failedToGenerate()
                mutator = fuzzer.mutators.randomElement()
            }
        }
        guard let program = mutatedProgram else {		// 变异失败
            logger.warning("Could not mutate sample, giving up. Sample:\n\(FuzzILLifter().lift(parent))")
            continue
        }
        assert(program !== parent)
        let outcome = execute(program)		// 执行变异后的js程序
        // Mutate the program further if it succeeded.
        if .succeeded == outcome {	// 变异后的程序执行成功，那么就在该样本的基础上继续进行变异
            parent = program
        }
    }
}

可以发现两点：

  • 随机从corpus中选取一个种子，如果该种子变异后执行成功，那么就会继续变异该种子numConsecutiveMutations次。即每次成功变异成功执行后，在现在的基础上再继续变异。
  • 对一个种子变异时，会尝试maxAttempts次，直到成功一次为止，如果每次都失败则会抛弃该样本

execute()方法定义在FuzzEngine中，是所有fuzz引擎的公共方法。

参考链接：fuzzilli原理：基本架构

覆盖率：由编译开始

下载并构建V8引擎

v8使用名为depot_tools的脚本包来管理。

depot_tools包括gclient，gcl，git-cl，repo等。可以通过以下方式安装：

1
2
3
git clone https://chromium.googlesource.com/chromium/tools/depot_tools.git
echo "export PATH=`pwd`/depot_tools:$PATH" >> ~/.bashrc
source  ~/.bashrc

随后，通过fetch获取v8源码。

1
2
3
4
5
cd fuzzilli/Targets/V8
fetch v8
cd v8
git checkout origin
gclient sync

接下来构建和测试v8引擎，首先是安装构建依赖项。

1
./build/install-build-deps.sh

再使用gn生成构建文件

1
gn gen out/Release "--args=is_debug=false"

使用以下命令进行编译，编译成功后会在out/Release目录下生成可执行文件d8

1
ninja -C out/Release

测试一下d8是正常的：

1
./out/Release/d8 ./test/fuzzer/parser/hello-world

完事儿后再用脚本编译v8即可：

1
2
cd fuzzilli/Targets/V8/v8
../fuzzbuild.sh

编译成功后，会生成./out/fuzzbuild/d8文件，这就是目标文件，也就是v8的js shell。

编译脚本参数分析

再简要分析编译过程，以下是fuzzilli编译V8的脚本：

1
2
3
4
5
6
7
8
if [ "$(uname)" == "Linux" ]; then
    # See https://v8.dev/docs/compile-arm64 for instructions on how to build on Arm64
    gn gen out/fuzzbuild --args='is_debug=false dcheck_always_on=true v8_static_library=true v8_enable_verify_heap=true v8_fuzzilli=true sanitizer_coverage_flags="trace-pc-guard" target_cpu="x64"'
else
    echo "Unsupported operating system"
fi

ninja -C ./out/fuzzbuild d8
  • gn gen：使用GN(Generate Ninja)生成构建文件
  • out/fuzzbuild：构建输出目录
  • --args：构建参数配置：
    • is_debug=false：构建发布版本（非调试版本）
    • dcheck_always_on=true：始终启用调试检查
    • v8_static_library=true：构建静态库版本的V8
    • v8_enable_verify_heap：启用堆验证
    • v8_fuzzilli=true：启用Fuzzilli特定支持
    • sanitizer_coverage_flags="trace-pc-guard"：设置代码覆盖率检测
    • target_cpu="x64"：指定目标CPU架构为x86-64

最后的ninjia -C ./out/fuzzbuild d8指的是在指定目录进行构建，而d8表示构建目标为V8的开发者shell

重点关注：v8_fuzzilli=true和sanitizer_coverage_flags="trace-pc-guard"参数

v8_fuzzilli=true

当设置这个参数时，BUILD.gn会添加一个V8_FUZZILLI宏

1
2
3
if (v8_fuzzilli) {
    defines += [ "V8_FUZZILLI" ]
}

并且在编译时额外添加如下4个文件，这四个文件用于llvm覆盖率插桩函数

1
2
3
4
5
6
7
8
if (v8_fuzzilli) {
  sources += [
    "src/fuzzilli/cov.cc",
    "src/fuzzilli/cov.h",
    "src/fuzzilli/fuzzilli.cc",
    "src/fuzzilli/fuzzilli.h",
  ]
}
sanitizer_coverage_flags

.gni后缀的文件是GN Build 系统的构建配置文件，通常用于**GN(Generage Ninja)**工具链。

  • GN是一个由Google开发的元构建系统，用于生成Ninja构建文件（build.ninja）。
  • .gni文件类似于Makefile或CMakeLists.txt，但语法更简洁，专为高性能构建涉及。

.gni文件的作用

  • 定义变量、模板和构建规则
  • 被主BUILD.gn文件引用，用于模块化配置
  • 在以下使用过程中，用来控制编译过程

根据文件V8/v8/build/config/sanitizers/sanitizers.gni中的描述：

  • 设置sanitizer_coverage_flags会用作-fsanitize-coverage的值
  • 并且设置该标志会自动启用use_sanitizer_coverage
1
2
3
4
5
6
7
8
9
10
# Value for -fsanitize-coverage flag. Setting this causes 
# use_sanitizer_coverage to be enabled.	设置它会使use_sanitizer_coverage被启用。
# This flag is not used for libFuzzer (use_libfuzzer=true). Instead, we use:
#     -fsanitize=fuzzer-no-link			这个标志不用于libFuzzer。相反，我们使用：-fsanitize=fuzz-no-link
# Default value when unset and use_fuzzing_engine=true:
#     trace-pc-guard						未设置且use_fuzzing_engine时的默认值：trace-pc-guard
# Default value when unset and use_sanitizer_coverage=true:
#     trace-pc-guard,indirect-calls
# 未设置且use_sanitizer_coverage=true时的默认值：trace-pc-guard，indirect-calls
sanitizer_coverage_flags = ""

由于它会自动启用use_sanitizer_coverage，所以看看启用该参数的时候编译时会发生什么：

来到V8/v8/build/config/sanitizers/BUILD.gn，这个文件会引用sanitizers.gni文件来模块化配置。查看use_sanitizer_coverage部分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
config("coverage_flags") {
  cflags = []
  if (use_sanitizer_coverage) {
    # Used by sandboxing code to allow coverage dump to be written on the disk.
    defines = [ "SANITIZER_COVERAGE" ]

    if (use_libfuzzer) {
    	...
    } else {
      cflags += [
        "-fsanitize-coverage=$sanitizer_coverage_flags",
        "-mllvm",
        "-sanitizer-coverage-prune-blocks=1",
      ]
      if (current_cpu == "arm") {
      	...
      }
    }
    ...
  }
  if (use_centipede) {
  	...
  }
}

参数有三个：-fsanitize-coverage、-mllvm和-sanitizer-coverage-prune-blocks，分别表示：

  • -fsanitize-coverage与llvm覆盖率检测相关，后续会详细研究
  • -mllvm表示把后面一个参数传递给LLVM
  • -sanitizer-coverage-prune-blocks表示在编译时对basic block进行精简，删除不会被执行到的基本块，可以提高运行速度，缺点是可能会影响代码覆盖率的准确性

llvm的sanitizer coverage

桩回调函数

-fsanitize-coverage=$sanitizer_coverage_flags表示启用llvm内置的覆盖率检测，并且可以提供覆盖率报告和可视化。llvm-SanitizerCoverage-官方文档

支持如下模式的覆盖率追踪，不同模式会调用不同的回调(call back)函数。

trace-pc-guard

该模式下编译器会在每一个edge插入如下代码

1
__sanitizer_cov_trace_pc_guard(&guard_variable)

guard_variable是一个32位无符号整数，它唯一标识一条边或者一个基本块，即每个guard_variable对应一个特定的代码路径。在执行过程中，SanitizerCoverage运行时可以通过修改guard_variable的值来标记该路径是否被执行过。

每条边都有自己的guard_variable (uint32_t)。编译器也会在每一个模块的构造函数中插入如下调用

1
2
3
4
5
// The guards are [start, stop). 它的执行区间是[start, stop)，也就是stop地址处是不会被初始化的
// This function will be called at least once per DSO and may be called
// more than once with the same values of start/stop.
// 该函数将在每个DSO(动态库)中至少调用一次，并且可以使用相同的start/stop值多次调用。
__sanitizer_cov_trace_pc_guard_init(uint32_t *start, uint32_t *stop);

编译器会在每个模块（如共享库或可执行文件）的构造函数中插入__sanitizer_cov_trace_pc_guard_init；这个函数的目的是初始化所有的guard_variable ，其参数的含义是：

  • start：指向该模块所有guard_variable数组的起始地址
  • stop：指向该模块所有guard_variable数组的结束地址（即最后一个元素的下一个位置）

整个插装过程涉及到三部分

  • guard section：每一个二进制文件都会有一个guard section， guard section实际就是一个uint32_t组成的数组
  • 在该二进制文件初始化时回调模块初始化函数触发，__sanitizer_cov_trace_pc_guard_init(start, stop)，[start, stop)就对应guard section的开始与结束
  • 执行时，每一个边对应guard section中一个slot（一条边对应guard section数组的一个索引），会触发__sanitizer_cov_trace_pc_guard(&guard_variable)，从而得知某条边被执行到了，并通过guard进行统计

至此，可以修改这两个函数的实现可以让用户达到：

  • 控制每一个edge的guard的生成方式（__sanitizer_cov_trace_pc_guard_init）
  • 控制每一个边被触发后的处理方式（__sanitizer_cov_trace_pc_guard）

函数__sanitizer_cov_trace_pc_*可以被用户自定义，例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// trace-pc-guard-cb.cc
#include <stdint.h>
#include <stdio.h>
#include <sanitizer/coverage_interface.h>

// This callback is inserted by the compiler as a module constructor
// into every DSO. 'start' and 'stop' correspond to the
// beginning and end of the section with the guards for the entire
// binary (executable or DSO). The callback will be called at least
// once per DSO and may be called multiple times with the same parameters.
/*
	这个回调会被编译器作为一个模块构造函数插入到每一个DSO中
	start和stop对应整个二进制文件(可执行文件 or 动态库)中guard段的开始和结束
	每一个动态库这个callback至少被调用一次, 并且有可能以相同的参数调用多次
*/
extern "C" void __sanitizer_cov_trace_pc_guard_init(uint32_t *start,
                                                    uint32_t *stop) {
  static uint64_t N;  // Counter for the guards.
  if (start == stop || *start) return;  // Initialize only once. 只初始化一次
  printf("INIT: %p %p\n", start, stop);
  for (uint32_t *x = start; x < stop; x++)
    *x = ++N;  // Guards should start from 1. 给[start, stop)中的guard_variable赋值，从1开始。
}

// This callback is inserted by the compiler on every edge in the
// control flow (some optimizations apply).
// Typically, the compiler will emit the code like this:
//    if(*guard)
//      __sanitizer_cov_trace_pc_guard(guard);
// But for large functions it will emit a simple call:
//    __sanitizer_cov_trace_pc_guard(guard);
/*
	这个回调函数会被编译器插入到控制流的每一个边中
	通常来说编译器会生成如下代码
	if(*guard)
            __sanitizer_cov_trace_pc_guard(guard);
    但是对于某些大函数会生成一个简单的调用, 所以callbak内部需要进行二次检查
     	__sanitizer_cov_trace_pc_guard(guard);
*/
extern "C" void __sanitizer_cov_trace_pc_guard(uint32_t *guard) {
  if (!*guard) return;  // Duplicate the guard check.
  // If you set *guard to 0 this code will not be called again for this edge.
  // Now you can get the PC and do whatever you want:
  //   store it somewhere or symbolize it and print right away.
  // The values of `*guard` are as you set them in
  // __sanitizer_cov_trace_pc_guard_init and so you can make them consecutive
  // and use them to dereference an array or a bit vector.
  /*
  	如果设置*guard为0, 那么对于这个边该代码就不会被调用了。
  	现在你可以得到PC并做任何你想做的事情：将它存储在某个地方或将其标记并立即打印。
  	*guard就是之前__sanitizer_cov_trace_pc_guard_init()中设置的值
  */
  void *PC = __builtin_return_address(0);
  char PcDescr[1024];
  // This function is a part of the sanitizer run-time.
  // To use it, link with AddressSanitizer or other sanitizer.
  /*
  	这是sanitizer run-time函数的一部分, 可以获取pc相关信息
  	为了使用它需要与AddressSanitizer或者其他sanitizer链接到一起
  */
  __sanitizer_symbolize_pc(PC, "%p %F %L", PcDescr, sizeof(PcDescr));
  printf("guard: %p %x PC %s\n", guard, *guard, PcDescr);
}

下面是被插桩的程序：

1
2
3
4
5
// trace-pc-guard-example.cc
void foo() { }
int main(int argc, char **argv) {
  if (argc > 1) foo();
}

执行编译命令：

1
2
3
4
5
6
7
8
# 编译example.cc, 会为每个边生成guard并插入对于__sanitizer_cov_trace_pc*()的调用
clang++ -g  -fsanitize-coverage=trace-pc-guard trace-pc-guard-example.cc -c

# 链接, 获取__sanitizer_cov_trace_pc*()的实现
clang++ trace-pc-guard-cb.cc trace-pc-guard-example.o -fsanitize=address

# 执行
ASAN_OPTIONS=strip_path_prefix=`pwd`/ ./a.out

执行结果：

1
2
3
INIT: 0x71bcd0 0x71bce0
guard: 0x71bcd4 2 PC 0x4ecd5b in main trace-pc-guard-example.cc:2
guard: 0x71bcd8 3 PC 0x4ecd9e in main trace-pc-guard-example.cc:3:7

执行（带参数）：

1
ASAN_OPTIONS=strip_path_prefix=`pwd`/ ./a.out with-foo

执行结果：

1
2
3
4
INIT: 0x71bcd0 0x71bce0
guard: 0x71bcd4 2 PC 0x4ecd5b in main trace-pc-guard-example.cc:3
guard: 0x71bcdc 4 PC 0x4ecdc7 in main trace-pc-guard-example.cc:4:17
guard: 0x71bcd0 1 PC 0x4ecd20 in foo() trace-pc-guard-example.cc:2:14
Inline 8bit-counters

-fsanitize-coverage=inline-8bit-counters将在每个edge插入内联计数器增量。这同上面的插装类似，但是只检测不回调处理。用户需要实现一个函数来在启动时捕获计数器。

1
2
3
4
5
6
extern "C"
void __sanitizer_cov_8bit_counters_init(char *start, char *end) {
  // [start,end) is the array of 8-bit counters created for the current DSO.
  // Capture this array in order to read/modify the counters.
  // [start，end]是为当前DSO创建的8位计数器数组。捕获该数组以便读取/修改计数器。
}

其余的就不看了，对当前而言意义不大。

插桩方式

sanitizer coverage提供不同程度的插桩

  • edge：对控制流的边插桩
  • bb：对基本块插桩
  • func：对函数入口处插桩

用它的方法也很简单：将其和trace-pc或trace-pc-guard一起用，例如：-fsanitize-coverage=func,trace-pc-guard，那么就会使用函数级插桩，回调函数用的是trace-pc-guard

当使用edge或者bb时, 如果有些插桩被认为是冗余的, 那么就会进行精简, 所以有些edge或者block可能没有被插桩, 可以使用no-prune标志来禁止精简, 比如-fsanitize-coverage=bb,no-prune,trace-pc-guard

Edge coverage

对于代码：

1
2
3
4
void foo(int *a) {
  if (a)
    *a = 0;
}

包含三个基本块（很容易判断，if前的语句，满足条件的语句，不满足条件的语句构成三个基本块）

1
2
3
4
5
6
7
A
|\
| \
|  B
| /
|/
C

如果三个块都被覆盖了, 那么就可以确定A=>B和B=>C这两个边被执行了, 但是我们无法得知A=>C是否执行. CFG中这样的edge被称为关键边 critical edge. edge-level的覆盖率会通过引入新的dummy block分割所有的critical edge, 然后插桩这些block:

1
2
3
4
5
6
7
A
|\
| \
D  B
| /
|/
C
Tracing data flow

目前支持如下数据流相关插桩方式, 以支持数据流引导的fuzzing。

  • 使用-fsanitize-coverage=trace-cmp标志, 编译器会在比较和switch语句周围进行额外的插桩,
  • -fsanitize-coverage=trace-div标志会对整数除法进行插桩
  • -fsanitize-coverage=trace-gep会对LLVM GEP(Get Element Ptr)指令进行插桩
  • -fsanitize-coverage=trace-loads会对load指令进行插桩
  • -fsanitize-coverage=trace-stores会对store指令进行插桩

目前，这些标志本身不能工作-它们需要-fsanize-coverage={trace-pc,inline-8bit-counters，inline-bool}标志之一才能工作。

Tracing control flow

使用-fsanizize-coverage=control-flow，编译器将创建一个表来收集每个函数的控制流。更具体地说，对于函数中的每个基本块，将填充两个列表。一个列表用于基本块的后继程序，另一个列表用于非内部调用的函数。

每一个表行包含基本块的地址, 后面跟着后继和callee的null-ended列表。

默认实现

sanitizer runtime（AddressSanitizer、MemorySanitizer 等）提供了一些覆盖回调的默认实现。可以使用此实现将覆盖率转储到进程出口的磁盘上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
% cat -n cov.cc
     1  #include <stdio.h>
     2  __attribute__((noinline))
     3  void foo() { printf("foo\n"); }
     4
     5  int main(int argc, char **argv) {
     6    if (argc == 2)
     7      foo();
     8    printf("main\n");
     9  }

% clang++ -g cov.cc -fsanitize=address -fsanitize-coverage=trace-pc-guard

% ASAN_OPTIONS=coverage=1 ./a.out; wc -c *.sancov
main
SanitizerCoverage: ./a.out.7312.sancov 2 PCs written
24 a.out.7312.sancov

% ASAN_OPTIONS=coverage=1 ./a.out foo ; wc -c *.sancov
foo
main
SanitizerCoverage: ./a.out.7316.sancov 3 PCs written
24 a.out.7312.sancov
32 a.out.7316.sancov
桩回调函数cov.cc

根据fuzzilli的编译条件：sanitizer_coverage_flags="trace-pc-guard"，没有修改插桩方式，也就是默认的Edge插桩。llvm通过插入用户自定义回调的方式来收集覆盖率, 而编译中额外插入的src/fuzzilli/cov.cc就是桩回调函数的实现, 下面研究下fuzzilli是如何实现这些callback的。还记得参数分析的时候有v8_fuzzilli=true吗？那时候有四个文件分别为：

1
2
3
4
5
6
7
8
if (v8_fuzzilli) {
  sources += [
    "src/fuzzilli/cov.cc",	// 这四个文件是V8自带的，而不是fuzzilli中的
    "src/fuzzilli/cov.h",
    "src/fuzzilli/fuzzilli.cc",
    "src/fuzzilli/fuzzilli.h",
  ]
}

这个cov.cc桩回调函数的实现，接下来分析cov.cc：

1
2
3
4
5
6
7
8
#define SHM_SIZE 0x100000				// 共享内存的大小
#define MAX_EDGES ((SHM_SIZE - 4) * 8)	// 一个边对应u char edges[]中的一个bit，因此最大边得*8
struct shmem_data {						// 该结构体大小为SHM_SIZE
  uint32_t num_edges;					// 表示边的数量
  unsigned char edges[];				// 存储每条边，每个bit
};

struct shmem_data* shmem;				// 执行共享内存的全局指针

在模块初始化时会调用__sanitizer_cov_trace_pc_guard_init()。该方法获取共享内存后会调用sanitizer_cov_reset_edgeguards()对guard section进行初始化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
void sanitizer_cov_reset_edgeguards() {
    uint32_t N = 0;
    for (uint32_t* x = edges_start; x < edges_stop && N < MAX_EDGES; x++)
        *x = ++N;
}

extern "C" void __sanitizer_cov_trace_pc_guard_init(uint32_t* start,
                                                    uint32_t* stop) {
    // We should initialize the shared memory region only once. We can initialize
    // it multiple times if it's the same region, which is something that appears
    // to happen on e.g. macOS. If we ever see a different region, we will likely
    // overwrite the previous one, which is probably not intended and as such we
    // fail with an error.
    /*
  	我们应该只初始化共享内存区域一次。如果它在同一个区域，我们可以对它进行多次初始化，这在macOS上似乎是会发生的。
  	如果我们看到一个不同的区域，我们可能会覆盖之前的区域，这可能不是我们想要的，因此我们会失败并出现错误。
  	*/
    if (shmem) {
        ...
            // Already initialized. 已经初始化过了就返回。
            return;
    }
    // Map the shared memory region
    // 通过环境变量获取共享内存key
    const char* shm_key = getenv("SHM_ID");
    if (!shm_key) {	//如果没有，则自己映射一片内存自己用
        fprintf(stderr, "[COV] no shared memory bitmap available, skipping\n");
        shmem = (struct shmem_data*)v8::base::Malloc(SHM_SIZE);
    } else {	// 存在SHM_ID
        int fd = shm_open(shm_key, O_RDWR, S_IREAD | S_IWRITE);	// 获取共享内存的fd
        if (fd <= -1) { // 错误处理
            fprintf(stderr, "[COV] Failed to open shared memory region\n");
            _exit(-1);
        }
        // 映射到本进程的地址空间中
        shmem = (struct shmem_data*)mmap(0, SHM_SIZE, PROT_READ | PROT_WRITE,
                                         MAP_SHARED, fd, 0);
        if (shmem == MAP_FAILED) {
            fprintf(stderr, "[COV] Failed to mmap shared memory region\n");
            _exit(-1);
        }
    }

    edges_start = start;		// guard section的起始位置
    edges_stop = stop;		// guard section的结束位置
    sanitizer_cov_reset_edgeguards();	// 调用sanitizer_cov_reset_edgeguards，初始化每条edge的guard_variable

    shmem->num_edges = static_cast<uint32_t>(stop - start);	// 初始化num_edges，也就是共享内存中的edge数量
    builtins_start = 1 + shmem->num_edges;
    fprintf(stderr,
            "[COV] edge counters initialized. Shared memory: %s with %u edges\n",
            shm_key, shmem->num_edges);
}

sanitizer_cov_reset_edgeguards()会为[start,stop)从1开始连续赋值，如果超过了MAX_EDGES，那么超出部分的边就不会被初始化。紧接着看一下__sanitizer_cov_trace_pc_guard()回调函数，前文提及过，它会在边被执行时触发。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
extern "C" void __sanitizer_cov_trace_pc_guard(uint32_t* guard) {
    // There's a small race condition here: if this function executes in two
    // threads for the same edge at the same time, the first thread might disable
    // the edge (by setting the guard to zero) before the second thread fetches
    // the guard value (and thus the index). However, our instrumentation ignores
    // the first edge (see libcoverage.c) and so the race is unproblematic.
    /*
  	这里有一个小的竞争条件：如果这个函数在两个线程中同时对同一条边执行，那么在第二个线程获取保护值（从而获取索引）之前，
  	第一个线程可能会禁用该边（通过将保护设置为零）。然而，我们的检测忽略了第一条边（参见libcoverage.c），
  	因此竞争是没有问题的。
  	*/
    uint32_t index = *guard;		// 获取边对应的唯一标识
    shmem->edges[index / 8] |= 1 << (index % 8);	// 设置shmem->edges中第index个bit为1，表示该边已被执行
    *guard = 0;			// 再将这条边置为0，因此再次执行时，就不会触发callback了。
}

由上可以看出, shmem->edges是一个bit map（位图）, 就好像一个二维码一样, 记录着对于某个样本所有执行到的边。

这里会有一个问题, shmem->edges能记录的边的数量是有限的, 最大为MAX_EDGES, 等于(0x100000-4)*8 = 8388576, 够用么?

答案是够用, 实际执行时最多要记录1367283条边, 小于MAX_EDGES, 因此不会有边被忽略掉。 这个1367283从何而来呢？shmem->num_edges会记录下来，因此可以拿到所有的边。

这个边的数量比想象中要少，为什么呢？因为编译器会对插桩进行优化：

  • SanitizerCoverage 的优化：编译器会避免对某些低风险代码（如简单算术运算）插桩，减少边数量。
  • 即使 V8 是一个复杂项目，其 控制流图（CFG）的边数量 仍受以下因素限制：
    • 函数数量：V8 的核心功能（如解析、编译、执行）的代码路径是有限的。
    • 循环和分支的复杂度：大多数函数的控制流不会无限膨胀。

如果目标更庞大，一个超大型代码库呢？

起始，我们所做的就是一个超大型代码库的一部分。Chromium 浏览器是十分庞大的，但是可以经过功能拆解，分成许多子模块进行测试，比如我们测试的v8 Js引擎。倘若真是一个很大的目标程序，也可以选择扩大共享内存（例如，libFuzzer的-shm_base_size参数）。

接下来看看cov.cc中其他的函数：

1
2
3
4
5
6
7
8
9
10
11
12
uint32_t sanitizer_cov_count_discovered_edges() {
    uint32_t on_edges_counter = 0;
    for (uint32_t i = 1; i < builtins_start; ++i) {
        const uint32_t byteIndex = i >> 3;  // 找到当前边i对应的字节在数组中的位置。
        const uint32_t bitIndex = i & 7;  // 找到当前边在字节中的具体位置。

        if (shmem->edges[byteIndex] & (1 << bitIndex)) {	// 边存在的话
            ++on_edges_counter;		// 计数
        }
    }
    return on_edges_counter; // 返回统计结果。
}

sanitizer_cov_count_discovered_edges()会遍历所有边，统计已经被执行过的代码路径（edges）的数量。接下来是内置函数的边初始化。

1
2
3
4
5
6
7
8
9
10
11
12
13
void cov_init_builtins_edges(uint32_t num_edges) {
    if (num_edges + shmem->num_edges > MAX_EDGES) {	// 检查共享内存剩余空间是否能容纳新增的边
        fprintf(stderr,
                "[COV] Error: Insufficient amount of edges left for builtins "
                "coverage.\n");
        exit(-1);
    }
    builtins_edge_count = num_edges;				// 保存新增的内置函数边数量
    builtins_start = 1 + shmem->num_edges;		// 内置函数的边从当前总边数+1开始。
    shmem->num_edges += builtins_edge_count;		// 更新总边数
    fprintf(stderr, "[COV] Additional %d edges for builtins initialized.\n",
            num_edges);
}

参数num_edges为内置函数新增的边的数量。这样做是为了分隔内置函数与用户代码，以便单独启用/禁用内置函数的覆盖率检测。内置函数是指由语言或引擎本身预先实现并提供给用户直接调用的核心功能函数。 它们通常是语言标准的一部分，无需用户手动定义即可实现。

接下来是最后一个函数，更新内置函数的基本块覆盖率信息到共享内存中：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// This function is ran once per REPRL loop. In case of crash the coverage of
// crash will not be stored in shared memory. Therefore, it would be useful, if
// we could store these coverage information into shared memory in real time.
/*
	这个函数在每个REPRL循环中运行一次。在崩溃的情况下，崩溃的覆盖将不会存储在共享内存中。因此，如果我们能够实时地将这些覆盖
	率信息存储到共享内存中，这将是非常有用的。
*/
void cov_update_builtins_basic_block_coverage(
    const std::vector<bool>& cov_map) {
    if (cov_map.size() != builtins_edge_count) {
        fprintf(stderr, "[COV] Error: Size of builtins cov map changed.\n");
        exit(-1);
    }
    for (uint32_t i = 0; i < cov_map.size(); ++i) {
        if (cov_map[i]) {
            const uint32_t byteIndex = (i + builtins_start) >> 3;
            const uint32_t bitIndex = (i + builtins_start) & 7;

            shmem->edges[byteIndex] |= (1 << bitIndex);
        }
    }
}

这个函数是为了将内置函数的覆盖率信息及时写入共享内存，即使发送Crash也能保存已经探索的路径。

JavaScriptCore引擎的编译分析

以下是JSC引擎编译的脚本：

1
2
3
4
5
6
7
export WEBKIT_OUTPUTDIR=FuzzBuild	# 设置WebKit构建输出目录为"FuzzBuild"，这样所有构建生成是文件都会放在这个目录下

if [ "$(uname)" == "Linux" ]; then	# 检测操作系统是否为Linux
    ./Tools/Scripts/build-jsc --jsc-only --debug --cmakeargs="-DENABLE_STATIC_JSC=ON -DCMAKE_C_COMPILER='/usr/bin/clang' -DCMAKE_CXX_COMPILER='/usr/bin/clang++' -DCMAKE_CXX_FLAGS='-fsanitize-coverage=trace-pc-guard -O3 -lrt'"
else
    echo "Unsupported operating system"
fi

调用./Tools/Scripts/build-jsc构建脚本，参数：--jsc-only，只构建JavaScriptCore（不构建整个webKit）。--debug：构建调试版本。--cmakeargs：传递给CMake的额外参数。如下：

1
"-DENABLE_STATIC_JSC=ON -DCMAKE_C_COMPILER='/usr/bin/clang' -DCMAKE_CXX_COMPILER='/usr/bin/clang++' -DCMAKE_CXX_FLAGS='-fsanitize-coverage=trace-pc-guard -O3 -lrt'"
  • -DENABLE_STATIC_JSC=ON：启用静态链接的JSC构建
  • -DCMAKE_C_COMPILER='/usr/bin/clang'：指定使用Clang作为C编译器
  • -DCMAKE_CXX_COMPILER='/usr/bin/clang++'：指定使用Clang++作为C++编译器
  • -DCMAKE_CXX_FLAGS=...：设置C++编译标志
    • -fsanitize-coverage=trace-pc-guard：启用代码覆盖率检测（用于模糊测试）
    • -03：最高级别优化
    • -lrt：链接实时库（Linux特定）

其实逻辑是一致的，回调函数的定义在./webkit/Source/JavaScriptCore/fuzzilli/Fuzzilli.cpp，当边被执行时，guard被触发，其逻辑是一致的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
extern "C" void __sanitizer_cov_trace_pc_guard(uint32_t* guard)
{
    // There's a small race condition here: if this function executes in two threads for the same
    // edge at the same time, the first thread might disable the edge (by setting the guard to zero)
    // before the second thread fetches the guard value (and thus the index). However, our
    // instrumentation ignores the first edge (see libcoverage.c) and so the race is unproblematic.

    uint32_t index = *guard;
WTF_ALLOW_UNSAFE_BUFFER_USAGE_BEGIN
    Fuzzilli::sharedData->edges[index / 8] |= 1 << (index % 8);
WTF_ALLOW_UNSAFE_BUFFER_USAGE_END

    *guard = 0;
}

以及初始化guard section也是一致的，不过它选择让initializeCoverage()执行初始化guard_variable的操作

1
2
3
4
5
6
7
8
9
extern "C" void __sanitizer_cov_trace_pc_guard_init(uint32_t* start, uint32_t* stop);
extern "C" void __sanitizer_cov_trace_pc_guard_init(uint32_t* start, uint32_t* stop)
{
    // Avoid duplicate initialization.
    if (start == stop || *start)
        return;

    Fuzzilli::initializeCoverage(start, stop);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
SUPPRESS_COVERAGE
void Fuzzilli::initializeCoverage(uint32_t* start, uint32_t* stop)
{
    RELEASE_ASSERT_WITH_MESSAGE(!edgesStart && !edgesStop, "Coverage instrumentation is only supported for a single module");

    edgesStart = start;
    edgesStop = stop;

    if (const char* shmKey = getenv("SHM_ID")) {
        int32_t fd = shm_open(shmKey, O_RDWR, S_IREAD | S_IWRITE);
        RELEASE_ASSERT_WITH_MESSAGE(fd >= 0, "Failed to open shared memory region: %s", strerror(errno));

        sharedData = static_cast<SharedData*>(mmap(0, SHM_SIZE, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0));
        RELEASE_ASSERT_WITH_MESSAGE(sharedData != MAP_FAILED, "Failed to mmap shared memory region");

        dataLogLn("[COV] edge counters initialized. Shared memory: %s with %zu edges.", shmKey, edgesStop - edgesStart);
    } else
        sharedData = static_cast<SharedData*>(malloc(SHM_SIZE));

    resetCoverageEdges();

    sharedData->numEdges = static_cast<uint32_t>(edgesStop - edgesStart);
}

同v8的逻辑一致。但是JSC会多一些REPRL相关的接口。

执行器：由REPRL.swift开始

在目标引擎执行生成的脚本时，执行速度对于fuzzer的性能至关重要。因此实现了两个机制以减少启动新进程时的开销

  1. forkserver：与AFL中使用的类似
  2. REPRL：本质上与libFuzzer中实现的进程内fuzz类似

libFuzzer是在单个进程中执行的fuzzer。libFuzzer不会为每个测试用例启动新进程，而是在同一个进程内存中直接处理数据，这减少了启动进程的开销。

forkserver的核心思想是：节省execve或类似系统调用的大量开销。在目标程序初始化完毕后添加一段代码，等待新的输入样例，每有一个新样例到来都会执行fork()系统调用，由子进程执行输入样例，以避免重复的初始化。

另一种模式称为”Read-Eval-Print-Repeat-Loop”，检测REPRL，该模式会对多个输入重用现有进程，无需fork一个子进程。本质上他修改了引擎，以便从预定义的fd中读入测试样例然后执行，执行完毕后会重置引擎的内部状态并等待下一个程序，这样就可以避免引擎初始化的大量开销。

接下来从REPRL类的定义来分析REPRL与Fuzzer的数据交互部分。

REPRL类

先去之前makFuzzer函数初始化runnner的地方，前文提及过：

1
2
3
4
5
6
7
8
9
10
11
12
13
func makeFuzzer(with configuration: Configuration) -> Fuzzer {
    // A script runner to execute JavaScript code in an instrumented JS engine.
    // 一个脚本运行器，用于在被插桩的JS引擎中执行JavaScript代码
    let runner = REPRL(executable: jsShellPath, processArguments: jsShellArguments, processEnvironment: profile.processEnv, maxExecsBeforeRespawn: profile.maxExecsBeforeRespawn)
    ...
    ...
    // The evaluator to score produced samples.
    // evaluator为生成的测试用例（样本）进行评分。
    let evaluator = ProgramCoverageEvaluator(runner: runner)
    ...
}
// 根据配置生成一个Fuzzer实例
let fuzzer = makeFuzzer(with: mainConfig)

对REPRL函数进行分析，它在Sources/Fuzzilli/Execution/REPRL.swift中，这个文件是REPRL类，REPRL的构造函数很简单，只会记录一下执行参数与环境变量，那么看一下它的构造函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class REPRL: ComponentBase, ScriptRunner {
    ...
    public init(executable: String, processArguments: [String], processEnvironment: [String: String], maxExecsBeforeRespawn: Int) {
        // 把js shell路径与js shell的参数进行拼接
        // e.g. path_to_v8 + v8_shell的参数
        self.processArguments = [executable] + processArguments
        self.maxExecsBeforeRespawn = maxExecsBeforeRespawn
        super.init(name: "REPRL")
		// 记录环境变量
        for (key, value) in processEnvironment {
            env.append(key + "=" + value)
        }
    }
	...
}

ProgramCoverageEvaluator的构造函数会设置runner的环境变量，以通过环境变量传入共享内存的id，JS引擎运行时的覆盖率等信息都会被写入到这片共享内存中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class ProgramCoverageEvaluator: ComponentBase, ProgramEvaluator {
    ...
    public init(runner: ScriptRunner) {
        // In order to keep clean abstractions, any corpus scheduler requiring edge counting
        // needs to call EnableEdgeTracking(), via downcasting of ProgramEvaluator
        self.shouldTrackEdgeCounts = false

        super.init(name: "Coverage")
		// 设置实例id
        let id = ProgramCoverageEvaluator.instances
        ProgramCoverageEvaluator.instances += 1

        context.id = Int32(id)
        guard libcoverage.cov_initialize(&context) == 0 else {
            fatalError("Could not initialize libcoverage")
        }
#if os(Windows)
        runner.setEnvironmentVariable("SHM_ID", to: "shm_id_\(GetCurrentProcessId())_\(id)")
#else
        runner.setEnvironmentVariable("SHM_ID", to: "shm_id_\(getpid())_\(id)")
#endif

    }
}

共享内存

共享内存的机制，第一次接触是在AFL/AFL++中，现在探讨一下它的机制：

共享内存就是允许两个不相关的进程访问同一个逻辑内存。共享内存是在两个正在运行的进程之间共享和传递数据的一种非常有效的方式。不同进程之间共享的内存通常安排为同一段物理内存。进程可以将同一段共享内存连接到它们自己的地址空间中，所有的进程都可以访问共享内存中的地址，就好像它们是由用C语言函数malloc()分配的内存一样。而如果某个进程向共享内存写入数据，所做的改动将立即影响到可以访问同一段共享内存的任何其他进程。使用信号量机制可同步对共享内存的访问。

1
int shmget(key_t key, size_t size, int shmflg);

第一个参数key（非0整数），它有效地为共享内存段命名，shmget()函数成功时返回一个与key相关的共享内存标识符（非负整数，也就是上述说的SHM_ID）。第二个参数size，以字节为单位指定需要共享的内存容量。第三个参数shmflag是权限标志，与文件的读写权限一样。

不相关的进程可以通过该函数的返回值(shm_id)访问同一共享内存。

1
void *shmat(int shm_id, const void *shm_addr, int shmflg);

第一次创建完共享内存时，它还不能被任何进程访问，shmat()函数的作用就是用来启动对该共享内存的访问，并把共享内存连接到当前进程的地址空间。

第一个参数shm_id，即由shmget()函数返回的共享内存标识符。

第二个参数shm_addr指定共享内存连接到当前进程中的地址位置，通常为空，让系统来选择共享内存的地址。

第三个参数shmflg标志位，通常为0

调用成功时返回一个指向共享内存第一个字节的指针，如果调用失败返回-1。

1
int shmdt(const void *shmaddr);

该函数用于将共享内存从当前进程中分离。注意，将内存共享分离并不是删除它，只是该共享内存对当前进程不再可用。

参数shmaddr是shmat()函数返回的地址指针，调用成功时返回0，失败时返回-1。

1
int shmctl(int shm_id, int command, struct shmid_ds *buf);

第一个参数shm_id，共享内存id。第二个参数command，采取的操作，它的取值如下：

  • IPC_STAT：获取共享内存段的信息，存储到buf中。
  • IPC_SET：修改共享内存段的权限或属性（通过buf设置）
  • IPC_RMID：标记删除共享内存段（实际销毁会在所有进程分离后执行）

第三个参数buf指向struct shmid_ds结构的指针，用于读取或设置共享内存段的信息。

REPRL的初始化

在let fuzzer = makeFuzzer(with: mainConfig)后，获得了一个初始化了fuzzer对象。随后在Fuzzloop中有fuzzer.initialize()，这时就会对fuzzer中的所有配置进行初始化（initialize而不是构造函数init）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public func initialize() {
        dispatchPrecondition(condition: .onQueue(queue))
        assert(!isInitialized)

        // Initialize the script runner first so we are able to execute programs.
    	// 首先初始化脚本运行器，以便我们能够执行程序
        runner.initialize(with: self)

        // Then initialize all components.
        engine.initialize(with: self)
        evaluator.initialize(with: self)
        environment.initialize(with: self)
        corpus.initialize(with: self)
        minimizer.initialize(with: self)
        corpusGenerationEngine.initialize(with: self)
		
        // Finally initialize all modules.
   		...
        // Install a watchdog to monitor the utilization of this instance.
       	...
        // Determine our initial state if necessary.
       	...

        dispatchEvent(events.Initialized)
        logger.info("Initialized")
        isInitialized = true
    }

REPRL在初始化时会通过libreprl创建并初始化一个REPRL上下文，这部分涉及到C与swift混合编程。由于REPRL与性能息息相关，因此作者通过C实现libreprl。关于runner的initialize方法只是对libreprl中API的调用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class REPRL: ComponentBase, ScriptRunner { 
    ...
    override func initialize() {
        // 分配一个新的reprl_context结构
        reprlContext = libreprl.reprl_create_context()
        if reprlContext == nil {
            logger.fatal("Failed to create REPRL context")
        }

        let argv = convertToCArray(processArguments)		// 转换为C中的数组
        let envp = convertToCArray(env)
		// 初始化REPRL上下文
        if reprl_initialize_context(reprlContext, argv, envp, /* capture stdout */ 1, /* capture stderr: */ 1) != 0 {
            logger.fatal("Failed to initialize REPRL context: \(String(cString: reprl_get_last_error(reprlContext)))")
        }
		// 初始化完毕，释放这些数组
        freeCArray(argv, numElems: processArguments.count)
        freeCArray(envp, numElems: env.count)
		// 对Shutdown事件添加Listener
        fuzzer.registerEventListener(for: fuzzer.events.Shutdown) { _ in                     			       		reprl_destroy_context(self.reprlContext)
        }
    }
    ...
}

关于reprl_context结构，以及REPRL具体的实现（libreprl-posix.c），下文会进一步讨论。完成runner的初始化后，会进行:

1
2
// Start the main fuzzing job.
fuzzer.start(runUntil: exitCondition)

也就是FuzzOne()，那么FuzzOne()中会有进行Fuzzing的部分，也就是execute()：

1
2
3
case .fuzzing:
	iterations += 1
	engine.fuzzOne(fuzzGroup)

这个engine就是MultiEngine/HybridEngine/MutationEngine/GenerativeEngine中的一个。这个GenerativeEngine是针对空Corpus执行的，当Corpus中存在种子那么基本就不会用它了。这里以通用的MutationEngine为例：

1
2
3
4
5
6
public override func fuzzOne(_ group: DispatchGroup) {
    	...
        let outcome = execute(program)
    	...
    }
}

其余部分在main.swift中说明过了，这里直接看关键的execute方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class FuzzEngine: ComponentBase {
	final func execute(_ program: Program, withTimeout timeout: UInt32? = nil) -> ExecutionOutcome {
        // 如果有Processor，那么先调用它进行处理
        let program = postProcessor?.process(program, for: fuzzer) ?? program
		// 触发ProgramGenerated事件
        fuzzer.dispatchEvent(fuzzer.events.ProgramGenerated, data: program)
		// 执行program程序
        let execution = fuzzer.execute(program, withTimeout: timeout, purpose: .fuzzing)

        switch execution.outcome {		// 处理执行结果
            case .crashed(let termsig):	// 触发Crash
                fuzzer.processCrash(program, withSignal: termsig, withStderr: execution.stderr, withStdout: execution.stdout, origin: .local, withExectime: execution.execTime)
                program.contributors.generatedCrashingSample()

            case .succeeded:	// 执行成功
                fuzzer.dispatchEvent(fuzzer.events.ValidProgramFound, data: program)
                var isInteresting = false	// 是否触发新边
                if let aspects = fuzzer.evaluator.evaluate(execution) {	// 对该程序进行评估
                    if fuzzer.config.enableInspection {
                        program.comments.add("Program may be interesting due to \(aspects)", at: .footer)
                        program.comments.add("RUNNER ARGS: \(fuzzer.runner.processArguments.joined(separator: " "))", at: .header)
                    }
                    isInteresting = fuzzer.processMaybeInteresting(program, havingAspects: aspects, origin: .local)	// 判断是否发现新边
                }
				// 触发该程序上的回调
                if isInteresting {
                    program.contributors.generatedInterestingSample()
                } else {
                    program.contributors.generatedValidSample()
                }

            case .failed(_):	// 执行失败，js shell抛出异常
                if fuzzer.config.enableDiagnostics {
                    program.comments.add("Stdout:\n" + execution.stdout, at: .footer)
                }
                fuzzer.dispatchEvent(fuzzer.events.InvalidProgramFound, data: program)
                program.contributors.generatedInvalidSample()

            case .timedOut:		// 执行超时
                fuzzer.dispatchEvent(fuzzer.events.TimeOutFound, data: program)
                program.contributors.generatedTimeOutSample()
        }
        return execution.outcome		// 返回执行结果
    }
}

Execute()方法会执行该测试样例，然后根据执行结果做对应的处理。可以看到，其实还封装了一层，这里依然会调用Fuzzer::execute()方法来执行这个program。这里的program是FuzzIL指令组成的程序，因此需要通过lifter将其翻译成字符串格式的js脚本，然后调用runner.run()执行该脚本。

1
2
3
4
5
6
7
8
9
10
11
12
public class Fuzzer {
    public func execute(_ program: Program, withTimeout timeout: UInt32? = nil, purpose: ExecutionPurpose) -> Execution {
        ...
        let script = lifter.lift(program)   // 把FuzzIL提升为js程序

        dispatchEvent(events.PreExecute, data: (program, purpose))  // 触发preExecute事件
        let execution = runner.run(script, withTimeout: timeout ?? config.timeout)  // 调用执行器执行脚本
        dispatchEvent(events.PostExecute, data: execution)  // 触发PostExecute事件

        return execution
    }
}

进一步看runner.run()方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class REPRL: ComponentBase, ScrswiftiptRunner {
    public func run(_ script: String, withTimeout timeout: UInt32) -> Execution {
        ...
        // 初始化一个执行结果对象，用于记录执行结果并返回
        let execution = REPRLExecution(from: self)
        ...
        
        var status: Int32 = 0
        script.withCString { ptr in
            // 调用libreprl中的reprl_execute()执行js脚本
            status = reprl_execute(reprlContext, ptr, UInt64(script.utf8.count), UInt64(timeout), &execTime, freshInstance)
            // 如果执行失败了，那么就尝试等待一会儿再执行
            if status < 0 {
                ...log...
                Thread.sleep(forTimeInterval: 1)
                status = reprl_execute(reprlContext, ptr, UInt64(script.utf8.count), UInt64(timeout), &execTime, 1)
            }
        }

        if status < 0 {
            ...
        }
        recentlyFailedExecutions = 0
		// 从返回的状态码中提取信息
        if RIFEXITED(status) != 0 {
            let code = REXITSTATUS(status)
            if code == 0 {	// 成功执行
                execution.outcome = .succeeded
            } else {	// 执行失败
                execution.outcome = .failed(Int(code))
            }
        } else if RIFSIGNALED(status) != 0 {		// 由于signal而终止执行
            execution.outcome = .crashed(Int(RTERMSIG(status)))
        } else if RIFTIMEDOUT(status) != 0 {
            execution.outcome = .timedOut			// 超时
        } else {
            fatalError("Unknown REPRL exit status \(status)")
        }
        execution.execTime = Double(execTime) / 1_000_000		// 写入运行时间

        return execution 	// 返回执行结果，覆盖率信息已经被写入到共享内存中了，由ProgramCoverageEvaluator负责处理
    }
}

那么，REPRL类的部分就结束了，可以发现最终执行脚本是由Sources/libreprl负责的，下面进一步研究libreprl-posix.c

libreprl-posix.c

该文件最开始的部分都是些功能方法，跳过直接来到关键的reprl_context结构体。前面提到在runner初始化时，会初始化一个新的reprl_context对象，下面看看reprl_context：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
struct reprl_context {
    // reprl_initialize是否在此context中成功执行
    int initialized;

    // control pipe用于和js解释器进行交互
    int ctrl_in;	// control pipe的read fd,只在子进程存活时有效
    int ctrl_out;	// control pipe的write fd,只在子进程存活时有效

    struct data_channel* data_in;	// REPRL 到 Child的数据信道
    struct data_channel* data_out;	// Child 到 REPRL的数据信道

    struct data_channel* child_stdout;	// 用于收集子进程stdout的信道, 可选
    struct data_channel* child_stderr;	// 用于收集子进程stderr的信道, 可选

    // 子进程的PID。如果当前没有子进程正在运行，则为零。
    pid_t pid;

    // 子进程的参数和环境变量
    char** argv;
    char** envp;

    // A malloc'd string containing a description of the last error that occurred.
    // 一个malloc分配的字符串缓冲区, 包含上一次出现的错误的描述
    char* last_error;
};

上述结构体的定义中，主要包含子进程的执行环境，子进程的pid，两个传递大量数据的信道，两个与子进程传递控制信息的fd。上面有个关键的结构体data_channel，用其定义了四个信道。下面详细看看这个结构体定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// A unidirectional communication channel for larger amounts of data, up to a maximum size (REPRL_MAX_DATA_SIZE).
// 用于更大数据量的单向通信通道，直至最大大小（REPRL_MAX_DATA_SIZE）。
// Implemented as a (RAM-backed) file for which the file descriptor is shared with the child process and which is mapped into our address space.
// 实现为一个（RAM支持的）文件，其文件描述符与子进程共享，并映射到我们的地址空间。
struct data_channel {
    // File descriptor of the underlying file. Directly shared with the child process.
    // 底层文件的文件描述符。直接与子进程共享。
    // 父进程中的文件描述符，会连接到子进程的fd上
    int fd;
    // Memory mapping of the file, always of size REPRL_MAX_DATA_SIZE.
    // 文件的内存映射，大小始终为REPRL_MAX_DATA_SIZE
    // 上述文件映射到父进程地址空间的地址
    char* mapping;
};
// data_channel是一个用于大量数据通讯的单向信道
// 通过内存映射文件实现, fd与子进程共享并映射到REPRL进程的地址空间中

只看定义可能有点懵哈，那么我们看一下runner.initialize()关于REPRL上下文做的操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
override func initialize() {
    reprlContext = libreprl.reprl_create_context()
    if reprlContext == nil {
        logger.fatal("Failed to create REPRL context")
    }

    let argv = convertToCArray(processArguments)
    let envp = convertToCArray(env)

    if reprl_initialize_context(reprlContext, argv, envp, /* capture stdout */ 1, /* capture stderr: */ 1) != 0 {
        logger.fatal("Failed to initialize REPRL context: \(String(cString: reprl_get_last_error(reprlContext)))")
    }

    freeCArray(argv, numElems: processArguments.count)
    freeCArray(envp, numElems: env.count)

    fuzzer.registerEventListener(for: fuzzer.events.Shutdown) { _ in
        reprl_destroy_context(self.reprlContext)
    }
}

显然，首先有一个reprl_create_context()来创建reprl_context对象，随后由reprl_initialize_context()来初始化REPRL上下文对象。先看一下reprl_create_context()函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#define REPRL_CHILD_CTRL_IN 100			// 控制输入fd
#define REPRL_CHILD_CTRL_OUT 101		// 控制输出fd
#define REPRL_CHILD_DATA_IN 102			// 数据输入fd
#define REPRL_CHILD_DATA_OUT 103		// 数据输出fd

struct reprl_context* reprl_create_context()
{
    // 预先占用下面四个fd, 因为在子进程中下面四个fd用于与父进程交互
    int devnull = open("/dev/null", O_RDWR);
    dup2(devnull, REPRL_CHILD_CTRL_IN);
    dup2(devnull, REPRL_CHILD_CTRL_OUT);
    dup2(devnull, REPRL_CHILD_DATA_IN);
    dup2(devnull, REPRL_CHILD_DATA_OUT);
    close(devnull);
	// 分配reprl_context对象
    return calloc(1, sizeof(struct reprl_context));
}

通过reprl_create_context()占用文件描述符，确保子进程和父进程可以通过固定的文件描述符进行通信。REPRL使用4个预定义的FD进行父子进程通信。为避免其他代码（程序）以外占用这些FD，该函数提前用dup2将它们绑定到/dev/null（一个黑洞设备，写入的数据会被丢弃，读取时返回EOF）。这样后续在设置进程间通信（如管道或者socketpair）时，可以安全地覆盖这些FD，而不会与其他FD冲突。dup2(old_fd, new_fd)会让new_fd指向old_fd相同的文件/设备。这里使用dup2时会将REPRL_CHILD_CTRL_IN等FD指向/dev/null。

随后，再看看初始化操作reprl_initialize_context()：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 初始化reprl_context，在这里就是传入的ctx结构体对象
int reprl_initialize_context(struct reprl_context* ctx, const char** argv, const char** envp, int capture_stdout, int capture_stderr)
{
    if (ctx->initialized) {
        return reprl_error(ctx, "Context is already initialized");
    }

    // 我们需要忽略SIGPIPE，因为我们可能会在子进程退出后写入管道。
    signal(SIGPIPE, SIG_IGN);
	// 复制调用js shell的参数和环境变量
    ctx->argv = copy_string_array(argv);
    ctx->envp = copy_string_array(envp);
	// 创建两个data_channel
    ctx->data_in = reprl_create_data_channel(ctx);
    ctx->data_out = reprl_create_data_channel(ctx);、
    // 根据是否需要捕获子进程的stdout与stderr创建data_channel， 可选项
    if (capture_stdout) {
        ctx->child_stdout = reprl_create_data_channel(ctx);
    }
    if (capture_stderr) {
        ctx->child_stderr = reprl_create_data_channel(ctx);
    }
    if (!ctx->data_in || !ctx->data_out || (capture_stdout && !ctx->child_stdout) || (capture_stderr && !ctx->child_stderr)) {
        // Proper error message will have been set by reprl_create_data_channel
        return -1;
    }
	// 表示该上下文已经初始化（初始化成功）
    ctx->initialized = 1;
    return 0;
}

然后看到reprl_create_data_channel()函数，用来创建channel。那么进一步看看以理解data_channel结构体：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
static struct data_channel* reprl_create_data_channel(struct reprl_context* ctx)
{
#ifdef __linux__
    // 创建一个匿名内存文件（不关联磁盘文件），适用于进程间共享数据
    // MFD_CLOEXEC：表示FD在`exec`时自动关闭（防止子进程意外继承）
    int fd = memfd_create("REPRL_DATA_CHANNEL", MFD_CLOEXEC);
#else
    char path[] = "/tmp/reprl_data_channel_XXXXXXXX";
    int fd = mkostemp(path, O_CLOEXEC);
    unlink(path);
#endif
    // 设置文件大小为REPRL_MAX_DATA_SIZE
    if (fd == -1 || ftruncate(fd, REPRL_MAX_DATA_SIZE) != 0) {
        reprl_error(ctx, "Failed to create data channel file: %s", strerror(errno));
        return NULL;
    }
    // 把匿名内存文件映射到进程的地址空间中
    char* mapping = mmap(0, REPRL_MAX_DATA_SIZE, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
    if (mapping == MAP_FAILED) {
        reprl_error(ctx, "Failed to mmap data channel file: %s", strerror(errno));
        return NULL;
    }
	// 创建一个data_channel对象
    struct data_channel* channel = malloc(sizeof(struct data_channel));
    channel->fd = fd;	// 在父进程中的fd
    channel->mapping = mapping;	//在父进程地址空间中的地址
    return channel;
}

那么此时便已经完成runner的初始化（也就是reprl_context的初始化）。笔者到这还是不太理解这个mapping有何作用。 这个mapping就是共享内存地址，后面的父子进程通信的四个管道fd会通过dup2()指向这块内存地址以进行传输数据，并且后续会通过memcpy()将javaScript直接copy到共享内存中。那么继续往后走吧，执行脚本最后调用的是reprl_execute()，这个太长了，并且是关键的执行函数，那么一步步拆解一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int reprl_execute(struct reprl_context* ctx, const char* script, uint64_t script_size, uint64_t timeout, uint64_t* execution_time, int fresh_instance)
{
    // 执行前先检查此ctx是否已经完成初始化
    if (!ctx->initialized) {
        return reprl_error(ctx, "REPRL context is not initialized");
    }
	// 生成的脚本大小应小于共享内存的大小
    if (script_size > REPRL_MAX_DATA_SIZE) {
        return reprl_error(ctx, "Script too large");
    }
	// 超时时间的设置检查
    if (timeout > REPRL_MAX_TIMEOUT_IN_MICROSECONDS) {
        return reprl_error(ctx, "Timeout too large");
    }
    int timeout_ms = (int)(timeout / 1000);

    // Terminate any existing instance if requested.
    // 判断是否需要终止子进程，在先前有一个判断，防止一个子进程执行次数过多
    if (fresh_instance && ctx->pid) {
        reprl_terminate_child(ctx);
    }
    ...
}

执行前的一些检查，随后：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int reprl_execute(struct reprl_context* ctx, const char* script, uint64_t script_size, uint64_t timeout, uint64_t* execution_time, int fresh_instance)
{
    ...
	// Reset file position so the child can simply read(2) and write(2) to these fds.
    // 重置数据信道的fd，以方便子进程使用
    lseek(ctx->data_out->fd, 0, SEEK_SET);
    lseek(ctx->data_in->fd, 0, SEEK_SET);
    if (ctx->child_stdout) {
        lseek(ctx->child_stdout->fd, 0, SEEK_SET);
    }
    if (ctx->child_stderr) {
        lseek(ctx->child_stderr->fd, 0, SEEK_SET);
    }

    // Spawn a new instance if necessary.
    // 如有必要，生成一个新实例。
    // 实际就是，如果此时没有子进程的话，那么会创建一个。因为初始化时pid没有做任何修改，此时应该为空。
    if (!ctx->pid) {
        int r = reprl_spawn_child(ctx);
        if (r != 0) return r;
    }
    ...
}

lseek(fd, offset, SEEK_SET)：设置文件描述符fd的当前读写位置，SEEK_SET表示从文件开头计算偏移量，而这里offset为0，则回到起始位置。在Fuzzing中会反复执行目标程序并重置状态，每次执行前需要确保数据信道的读写位置归0，避免旧数据的干扰。

随后会执行reprl_spawn_child(ctx)来创建子进程以执行，这个函数依然比较长，一步步拆解查看：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
static int reprl_spawn_child(struct reprl_context* ctx)
{
    // This is also a good time to ensure the data channel backing files don't grow too large.
    // 这也是确保数据通道备份文件不会变得太大的好时机。
    ftruncate(ctx->data_in->fd, REPRL_MAX_DATA_SIZE);	// 调整data_in通道文件大小
    ftruncate(ctx->data_out->fd, REPRL_MAX_DATA_SIZE);	// 调整data_out通道文件大小
    if (ctx->child_stdout) ftruncate(ctx->child_stdout->fd, REPRL_MAX_DATA_SIZE);
    if (ctx->child_stderr) ftruncate(ctx->child_stderr->fd, REPRL_MAX_DATA_SIZE);
	// 初始化pipefd数组为0
    int crpipe[2] = { 0, 0 };          // 子进程 -> REPRL（读端在父进程，写端在子进程）
    int cwpipe[2] = { 0, 0 };          // REPRL -> 子进程（写端在父进程，读端在子进程）

    if (pipe(crpipe) != 0) {	// 创建父进程读，子进程写的管道
        return reprl_error(ctx, "Could not create pipe for REPRL communication: %s", strerror(errno));
    }
    if (pipe(cwpipe) != 0) {	// 创建父进程写，子进程读的管道
        close(crpipe[0]);
        close(crpipe[1]);
        return reprl_error(ctx, "Could not create pipe for REPRL communication: %s", strerror(errno));
    }

    ctx->ctrl_in = crpipe[0];	// 当前是父进程，那么设置父进程读取子进程消息的fd
    ctx->ctrl_out = cwpipe[1];	// 设置父进程向子进程写入消息的fd
    // 设置文件描述符的 close-on-exec 标志，确保在 exec() 时自动关闭，避免子进程意外继承。
    fcntl(ctx->ctrl_in, F_SETFD, FD_CLOEXEC);
    fcntl(ctx->ctrl_out, F_SETFD, FD_CLOEXEC);
    ...
}

  • ftruncate(fd, size)

    • 将文件描述符 fd 关联的文件大小设置为 size（字节）。
    • 如果文件原来比 size 大，多余部分会被截断丢弃。
    • 如果文件原来比 size 小，则扩展并用 \0 填充新增部分。

  • pipe(int pipefd[2])

    • 创建一个 单向管道，pipefd[0] 是读端，pipefd[1] 是写端。即，pipe会创建一对新的fd，并写入pipefd[0]和pipefd[1]。
    • crpipe（child → reprl）：
      • 子进程写入控制消息，父进程读取。
    • cwpipe（reprl → child）：
      • 父进程写入控制消息，子进程读取。

此时创建好了父子进程通信的管道，接下来就是创建子进程了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
static int reprl_spawn_child(struct reprl_context* ctx)
{
    ...
    
#ifdef __linux__
	// 创建一个子进程
    pid_t pid = vfork(); // vfork()表示创建专用于执行execute的进程, 以提高效率, 但是execute()之前地址空间都是共享的
#else
    pid_t pid = fork();
#endif
    if (pid == 0) {	// 子进程
        // 把控制信道和数据信道的fd重定向到子进程特定的读写fd上
        if (dup2(cwpipe[0], REPRL_CHILD_CTRL_IN) < 0 ||
            dup2(crpipe[1], REPRL_CHILD_CTRL_OUT) < 0 ||
            dup2(ctx->data_out->fd, REPRL_CHILD_DATA_IN) < 0 ||
            dup2(ctx->data_in->fd, REPRL_CHILD_DATA_OUT) < 0) {
            fprintf(stderr, "dup2 failed in the child: %s\n", strerror(errno));
            _exit(-1);
        }
		...
        // 关闭管道无用的另一端
        close(cwpipe[0]);
        close(crpipe[1]);
		// 设置子进程的stdin stdout stderr
        int devnull = open("/dev/null", O_RDWR);
        dup2(devnull, 0);	// 关闭stdin
        if (ctx->child_stdout) dup2(ctx->child_stdout->fd, 1);	// 根据条件是否关闭stdout 和 stderr
        else dup2(devnull, 1);
        if (ctx->child_stderr) dup2(ctx->child_stderr->fd, 2);
        else dup2(devnull, 2);
        close(devnull);

        // 处理stdin stdout stderr，控制管道fd，数据管道fd，然后关闭剩余所有的fd
        int tablesize = getdtablesize();
        for (int i = 3; i < tablesize; i++) {
            if (i == REPRL_CHILD_CTRL_IN || i == REPRL_CHILD_CTRL_OUT || i == REPRL_CHILD_DATA_IN || i == REPRL_CHILD_DATA_OUT) {
                continue;
            }
            close(i);
        }
        // 开始执行js shell
        execve(ctx->argv[0], ctx->argv, ctx->envp);
        fprintf(stderr, "Failed to execute child process %s: %s\n", ctx->argv[0], strerror(errno));
        fflush(stderr);
        _exit(-1);	// 子进程执行至此则退出
    }
    // 以上都是子进程执行的内容*
    ...
}

最后是通过系统调用execve()进行执行js shell。后续部分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
static int reprl_spawn_child(struct reprl_context* ctx)
{
    // 父进程关闭管道无用的另一端
    close(crpipe[1]);
    close(cwpipe[0]);

    if (pid < 0) {	// 错误处理，fork失败
        close(ctx->ctrl_in);
        close(ctx->ctrl_out);
        return reprl_error(ctx, "Failed to fork: %s", strerror(errno));
    }
    ctx->pid = pid;	// 父进程记录子进程的pid
	// 阻塞等待子进程的HELO，出现
    char helo[5] = { 0 };
    if (read(ctx->ctrl_in, helo, 4) != 4) {
        reprl_terminate_child(ctx);
        return reprl_error(ctx, "Did not receive HELO message from child: %s", strerror(errno));
    }
	// 如果收到的消息不是"HELO"则杀死子进程
    if (strncmp(helo, "HELO", 4) != 0) {
        reprl_terminate_child(ctx);
        return reprl_error(ctx, "Received invalid HELO message from child: %s", helo);
    }
	// 向子进程发送HELO作为回复
    if (write(ctx->ctrl_out, helo, 4) != 4) {
        reprl_terminate_child(ctx);
        return reprl_error(ctx, "Failed to send HELO reply message to child: %s", strerror(errno));
    }
	...
    return 0;
}

此时，reprl_spawn_child()便已经结束，那么我们回到reprl_execute()中：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int reprl_execute(struct reprl_context* ctx, const char* script, uint64_t script_length, uint64_t timeout, uint64_t* execution_time, int fresh_instance)
{
    ...
    // Copy the script to the data channel.
    // 将Script文件写入到共享内存中
    memcpy(ctx->data_out->mapping, script, script_size);

    // Tell child to execute the script.
    // 发送控制信息让子进程执行测试程序
    if (write(ctx->ctrl_out, "exec", 4) != 4 ||			// 执行脚本
        write(ctx->ctrl_out, &script_size, 8) != 8) {	// Script脚本长度的地址写入共享内存
        // These can fail if the child unexpectedly terminated between executions.
        // Check for that here to be able to provide a better error message.
        int status;
        if (waitpid(ctx->pid, &status, WNOHANG) == ctx->pid) {	// 使用`WNOHANG`进行非阻塞地检查子进程是否已经终止。若终止则返回值为子进程的pid，此处为错误处理，若子进程意外终止，那么进行下面代码执行进行error告知
            reprl_child_terminated(ctx);
            ...
        }
        return reprl_error(ctx, "Failed to send command to child process: %s", strerror(errno));
    }
    ...
}

最后阻塞等待子进程执行完毕，然后通过获取子进程的执行结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int reprl_execute(struct reprl_context* ctx, const char* script, uint64_t script_length, uint64_t timeout, uint64_t* execution_time, int fresh_instance)
{
    ...
    // Wait for child to finish execution (or crash).
    // // 等待子进程执行完毕或者crash
    uint64_t start_time = current_usecs();
    struct pollfd fds = {.fd = ctx->ctrl_in, .events = POLLIN, .revents = 0};
    int res = poll(&fds, 1, timeout_ms);	// 阻塞等待控制信道的信息，最多等待timeout_ms
    *execution_time = current_usecs() - start_time;	// 计算执行耗时
    if (res == 0) {	// poll返回0说明执行超时了
        // kill子进程, 然后返回超时的状态
        reprl_terminate_child(ctx);
        return 1 << 16;
    } else if (res != 1) {	// 不是1说明poll出错了
        return reprl_error(ctx, "Failed to poll: %s", strerror(errno));
    }
    
    // Poll succeeded, so there must be something to read now (either the status or EOF).
    // poll成功后, 通过控制管道获取子进程的输出的执行状态
    int status;
    ssize_t rv = read(ctx->ctrl_in, &status, 4);
    if (rv < 0) {
        ...
    }
    else if (rv != 4) {
       	// 错误处理
        ...
    }
    // The status must be a positive number, see the status encoding format below.
    // We also don't allow the child process to indicate a timeout. If we wanted,
    // we could treat it as an error if the upper bits are set.
    // 返回子进程输出的执行状态, 之后子进程会重置状态做好下一次执行的准备
    status &= 0xffff;
    return status;
}

在一次执行结束后, 子进程会重置js引擎的状态为下一次执行做准备, 我们可以看到相较于fork server不仅免去了js引擎初始化的开销, 还面去了fork系统调用的开销, fork的开销。此外由于父进程会阻塞等待子进程执行, 父子进程不可能同时执行, 因此一个Fuzzer对象在某一时刻只会占用一个线程。

v8_fuzzilli=true

关于v8的编译脚本参数分析中，存在一个参数：v8_fuzzilli=true，它除了会添加一些回调函数（前文已经分析过），还会增加对Reprl的支持。主要影响了v8/v8/src/d8/d8.cc，该文件是d8的入口，从头开始分析：

1
2
3
4
#ifdef V8_FUZZILLI
#include "src/fuzzilli/cov.h"
#include "src/fuzzilli/fuzzilli.h"
#endif  // V8_FUZZILLI

首先会include先前提及的回调函数的文件。然后再设置一个全局变量：

1
2
3
4
5
#ifdef V8_FUZZILLI
bool fuzzilli_reprl = true;
#else
bool fuzzilli_reprl = false;
#endif  // V8_FUZZILLI

接着来到d8的入口函数int Shell::Main(int argc, char* argv[])处：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int Shell::Main(int argc, char* argv[]) {
  // 引擎初始化相关工作
  v8::V8::InitializeICUDefaultLocation(argv[0], options.icu_data_file);
  v8::V8::Initialize();
  Isolate* isolate = Isolate::New(create_params);

    ...

#ifdef V8_FUZZILLI
  // Let the parent process (Fuzzilli) know we are ready.
  if (options.fuzzilli_enable_builtins_coverage) {
    ...
  }
  // 向Fuzzer发送HELO并等待回复
  char helo[] = "HELO";
  if (write(REPRL_CWFD, helo, 4) != 4 || read(REPRL_CRFD, helo, 4) != 4) {
    fuzzilli_reprl = false;
  }

  if (memcmp(helo, "HELO", 4) != 0) {
    FATAL("REPRL: Invalid response from parent");
  }
#endif  // V8_FUZZILLI
  ...
}

接下来进入fuzzilli_reprl的执行循环，那么对于fuzzilli的reprl来说：

  1. 会等待父进程的exec信号；
  2. 然后调用RunMain()获取和执行测试程序并重置执行环境
  3. 最后获取结果，通过控制管道将结果传输到Fuzzer中，并重置收集覆盖率信息的共享内存
  4. 然后重复上述步骤
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
int Shell::Main(int argc, char* argv[])
{
    ... 
    do  // fuzzilli_reprl执行循环
    {
        // 等待父进程的exec信号
#ifdef V8_FUZZILLI
        if (fuzzilli_reprl) {
            unsigned action = 0;
            ssize_t nread = read(REPRL_CRFD, &action, 4);
            if (nread != 4 || action != 'cexe') {
                FATAL("REPRL: Unknown action: %u", action);
            }
        }
#endif // V8_FUZZILLI

        result = 0;
        if (i::v8_flags.stress_runs > 0) {
            ...
        } else if (options.code_cache_options != ShellOptions::kNoProduceCache) {
            ...
        } else {
            bool last_run = true;
            result = RunMain(isolate, last_run);    // 获取脚本并执行
        }

#ifdef V8_FUZZILLI
        if (fuzzilli_reprl) {
            // 获取执行结果
            int status = result << 8;
            std::vector<bool> bitmap;
            if (options.fuzzilli_enable_builtins_coverage) {
                ...
            }
            if (options.fuzzilli_coverage_statistics) {
                ...
            }
            // 把执行结果通过管道返回给Fuzzilli
            fflush(stdout);
            fflush(stderr);
            CHECK_EQ(write(REPRL_CWFD, &status, 4), 4);
            // 重置edge guard段
            sanitizer_cov_reset_edgeguards();
            if (options.fuzzilli_enable_builtins_coverage) {
                ...
            }
        }
#endif // V8_FUZZILLI
    }
    while (fuzzilli_reprl);
    ...
}

Shell::RunMain()会调用RunMainIsolate()方法在主Isolate上执行脚本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int Shell::RunMain(v8::Isolate* isolate, bool last_run) {
  i::Isolate* i_isolate = reinterpret_cast<i::Isolate*>(isolate);
  ...

  // 判断是否要保留js执行上下文: 如果上一次执行成功了, 并且是交互执行模式, 则保留
  const bool keep_context_alive = last_run && (use_interactive_shell() || i::v8_flags.stress_snapshot);
  // 获取一个js脚本并执行
  bool success = RunMainIsolate(isolate, keep_context_alive);
  // 垃圾收集
  CollectGarbage(isolate);
  ...
  // 如果执行时有异常抛出,则认为执行失败
  return (success == Shell::options.expected_to_throw ? 1 : 0);
}

Shell::RunMainIsolate()会调用SourceGroup::Execute()方法开始在主Isolate上执行js脚本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool Shell::RunMainIsolate(v8::Isolate* isolate, bool keep_context_alive) {
  HandleScope scope(isolate);
  // 创建执行上下文
  Local<Context> context;
  if (!CreateEvaluationContext(isolate).ToLocal(&context)) {
    return false;
  }
  if (keep_context_alive) {
    evaluation_context_.Reset(isolate, context);
  }

  bool success = true;
  {
    Context::Scope context_scope(context);
    InspectorClient inspector_client(context, options.enable_inspector);
    PerIsolateData::RealmScope realm_scope(PerIsolateData::Get(isolate));
    if (!options.isolate_sources[0].Execute(isolate)) success = false;    // 开始执行
    if (!CompleteMessageLoop(isolate)) success = false;
  }

  WriteLcovData(isolate, options.lcov_file);
  return success;
}

然后来到d8的Execute()：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#ifdef V8_FUZZILLI
  if (fuzzilli_reprl) {
    HandleScope handle_scope(isolate);
    Local<String> file_name =
        String::NewFromUtf8(isolate, "fuzzcode.js", NewStringType::kNormal)
            .ToLocalChecked();

    size_t script_size;	// 读取Reprl发送过来的script_size的地址
    CHECK_EQ(read(REPRL_CRFD, &script_size, 8), 8);	// 然后检查script_size地址是否正确读取
    // 在栈上开辟Script脚本大小+1的空间
    char* buffer = new char[script_size + 1];
    char* ptr = buffer;
    // 通过数据信道把测试程序读入到buffer中
    size_t remaining = script_size;
    while (remaining > 0) {	// 保证读完
      ssize_t rv = read(REPRL_DRFD, ptr, remaining);
      CHECK_GE(rv, 0);
      remaining -= rv;
      ptr += rv;
    }
    buffer[script_size] = 0;	// 末尾置0

    Local<String> source =	
        String::NewFromUtf8(isolate, buffer, NewStringType::kNormal)
            .ToLocalChecked();
    delete[] buffer;
    Shell::set_script_executed();
    // 执行
    if (!Shell::ExecuteString(isolate, source, file_name,
                              Shell::kReportExceptions)) {
      return false;
    }
  }
#endif  // V8_FUZZILLI

这里会发现子进程通过read 管道句柄来访问jsc脚本数据，而不是直接通过地址来直接访问那块共享内存的，因此父进程写入脚本的效率会大大优于子进程读取脚本的效率。有没有办法能够让子进程拿到父进程mapping的地址？或者父进程mapping到子进程地址空间呢？

可能的解决方案：可以让子进程通过fd来mmap映射一个内存地址，虽然虚拟内存不一样，但是由于fd是一致的，因此实际物理内存是一致的，所以映射出来的东西是一样的。

REPRL其实是一种更加精细化的持久化fuzz: 每次执行测试样例时进程, 线程, Isolate都是同一个, 只会刷新js执行上下文, 以减少执行消耗。

关于REPRL模式的详细逻辑执行流：

makeFuzzer()初始化Fuzzer对象 $$\rightarrow$$ 初始化runner/engine/codeGenerators/evaluator/lifter/... $$\rightarrow$$ 变异/生成FuzzIL代码 $$\rightarrow$$ 使用lifter将FuzzIL代码翻译成javascript代码 $$\rightarrow$$ 若子进程不存在，则父进程创建子进程execve() $$\rightarrow$$ 将javaScript代码写入shm，并向子进程发送“exec”信号 $$\rightarrow$$ 子进程接收到”exec“信号，通过read()拿到测试用例并执行 $$\rightarrow$$ 子进程继续等待信号，父进程进入Fuzzloop。

结构清晰后，就需要细看Fuzzilli的mutator，lifter，generator，evaluator等等，才能知道种子是如何生成/变异的，以及种子选择策略。到这儿之后，笔者就去重新过一遍Fuzzilli的项目文档了。

变异引擎：由FuzzEngine初始化开始

依然来到makeFuzzer()方法，查看engine的初始化做了哪些操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
func makeFuzzer(with configuration: Configuration) -> Fuzzer {
    ...
    // Engines to execute programs.
    let engine: FuzzEngine
    switch engineName {
        case "hybrid":
        engine = HybridEngine(numConsecutiveMutations: consecutiveMutations)
        case "multi":
        let mutationEngine = MutationEngine(numConsecutiveMutations: consecutiveMutations)
        let hybridEngine = HybridEngine(numConsecutiveMutations: consecutiveMutations)
        let engines = WeightedList<FuzzEngine>([
            (mutationEngine, 1),
            (hybridEngine, 1),
        ])
        // We explicitly want to start with the MutationEngine since we'll probably be finding
        // lots of new samples during early fuzzing. The samples generated by the HybridEngine tend
        // to be much larger than those from the MutationEngine and will therefore take much longer
        // to minimize, making the fuzzer less efficient.
        // For the same reason, we also use a relatively larger iterationsPerEngine value, so that
        // the MutationEngine can already find most "low-hanging fruits" in its first run.
        engine = MultiEngine(engines: engines, initialActive: mutationEngine, iterationsPerEngine: 10000)
        default:
        engine = MutationEngine(numConsecutiveMutations: consecutiveMutations)
    }

    // Add a post-processor if the profile defines one.
    if let postProcessor = profile.optionalPostProcessor {
        engine.registerPostProcessor(postProcessor)
    }
    ...
}

根据参数确定选择的Engine进行对应的初始化操作，三种模式：hybrid、multi和默认的MutationEngine。为了便于理解，先看默认的MutationEngine

MutationEngine

1
2
3
4
5
6
7
8
9
10
11
12
// 前文通过参数初始化的变量，连续变异的次数，缺省值为5
let consecutiveMutations = args.int(for: "--consecutiveMutations") ?? 5
....

switch engineName {
    case "hybrid":
    	...
    case "multi":
    	...
    default:
    	engine = MutationEngine(numConsecutiveMutations: consecutiveMutations)
}

紧接着来看MutationEngine()构造函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
/// The core fuzzer responsible for generating and executing programs.
// 负责生成和执行程序的核心fuzzer。
public class MutationEngine: FuzzEngine {
    // The number of consecutive mutations to apply to a sample.
    // 其实质控制变异时生成测试样例的数量，默认为5，则说明一次FuzzOne会变异生成5个样本去执行，每个样本是某个种子应用10次变异算子。
    private let numConsecutiveMutations: Int

    public init(numConsecutiveMutations: Int) {
        self.numConsecutiveMutations = numConsecutiveMutations
        super.init(name: "MutationEngine")
    }
    ...
}

这个初始化也就是覆盖一个连续变异次数变量，直接来到关键的FuzzOne()吧，这才是Engine的关键：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class MutationEngine: FuzzEngine {
    ...
    public override func fuzzOne(_ group: DispatchGroup) {
        // 随机选取一个种子作为本次Mutation的parent
        var parent = fuzzer.corpus.randomElementForMutating()
        // 将这个种子进行一个预处理以便能够变异
        parent = prepareForMutating(parent)
        // numConsecutiveMutations之前说过，控制本轮FuzzOne()产生的样本数量
        for _ in 0..<numConsecutiveMutations {
            // 根据权重在所有Mutator中选取一个
            var mutator = fuzzer.mutators.randomElement()
            // 在该样本上执行变异的次数：10次
            let maxAttempts = 10
            var mutatedProgram: Program? = nil
            for _ in 0..<maxAttempts {
                // 调用mutate方法对种子进行变异
                if let result = mutator.mutate(parent, for: fuzzer) {
                    // Success!
                    result.contributors.formUnion(parent.contributors)
                    mutator.addedInstructions(result.size - parent.size)
                    mutatedProgram = result
                    break
                } else {
                    // Try a different mutator.
                    mutator.failedToGenerate()
                    mutator = fuzzer.mutators.randomElement()
                }
            }

            guard let program = mutatedProgram else {
                logger.warning("Could not mutate sample, giving up. Sample:\n\(FuzzILLifter().lift(parent))")
                continue
            }

            assert(program !== parent)
            let outcome = execute(program)

            // Mutate the program further if it succeeded.
            if .succeeded == outcome {
                parent = program
            }
        }
    }
    ...
}

大多是调用Mutator的api来完成变异操作，没有种子选择策略，是随机在corpus中随机选择一个种子。MutationEngine类的重点其实是prepareForMutating()方法，进一步看看这个方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class MutationEngine: FuzzEngine {
    ...
    /// Pre-processing of programs to facilitate mutations on them.
    // 对程序进行预处理，使其易于进行变异。
    private func prepareForMutating(_ program: Program) -> Program {
        // 初始化一个ProgramBuilder对象
        let b = fuzzer.makeBuilder()
        // 生成一些前缀代码
        b.buildPrefix()
        // 前缀代码+program组成新的program
        b.append(program)
        // finalize()会将新的program返回，并重置对象b的状态
        return b.finalize()
    }
    ...
}

这些API就不进一步分析了，因为ProgramBuilder是Base类，等到二次开发再细究这些接口功能就行了。不用关心具体实现。简单看看这个和Program相关的Prefix：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class MutationEngine: FuzzEngine {
    ...
    public func buildPrefix() {
        // 每个值生成器应该至少生成3个变量，并且我们可能希望至少运行其中的几个变量（可能大约为>= 3），
        // 因此要构建的变量数量不应该设置得太低。
        assert(CodeGenerator.numberOfValuesToGenerateByValueGenerators == 3)
        // 产生一个10 ~ 15的随机数
        let numValuesToBuild = Int.random(in: 10...15)

        trace("Start of prefix code")
        // 运行ValueGenerators,直到创建numValuesToBuild个新变量
        buildValues(numValuesToBuild)
        // 可见变量的数量要确定大于等于刚创建的可见变量
        assert(numberOfVisibleVariables >= numValuesToBuild)
        trace("End of prefix code. \(numberOfVisibleVariables) variables are now visible")
    }
    ...
}

变异器：由Mutator初始化开始

依然还是makeFuzzer()方法，看看变异器对象的初始化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func makeFuzzer(with configuration: Configuration) -> Fuzzer {
    let disabledMutators = Set(profile.disabledMutators)	// 通过命令行参数profile来确定是否有被禁用的变异器
    // 初始化各个变异器的对象，并为它们分配一个权重
    var mutators = WeightedList([
        (ExplorationMutator(),                 3),
        (CodeGenMutator(),                     2),
        (SpliceMutator(),                      2),
        (ProbingMutator(),                     2),
        (InputMutator(typeAwareness: .loose),  2),
        (InputMutator(typeAwareness: .aware),  1),
        // 还在实验性阶段的Mutator: ConcatMutator是一个限制版的CombineMutator()
        // (ConcatMutator(),                   1),
        (OperationMutator(),                   1),
        (CombineMutator(),                     1),
        // 如果删除了必要的try-catch，那么就启用FixupMutator
        // (FixupMutator()),                   1),
    ])
    // 获取一个所有变异器名称的集合，方便后续过滤禁用的变异器
    let mutatorsSet = Set(mutators.map { $0.name })
    if !disabledMutators.isSubset(of: mutatorsSet) {	// 如果不是所有变异器集合的子集，那么报错
        ...
    }
    if !disabledMutators.isEmpty {	// 如果禁用变异器列表不为空，那么mutators禁用这些变异器
        mutators = mutators.filter({ !disabledMutators.contains($0.name) })
    }
    if mutators.isEmpty {	// 如果所有的变异器都被禁用，报错
        ...
    }
    ...
}

先看看这里这么多变异器的构造函数做了什么，ExplorationMutator()：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class ExplorationMutator: RuntimeAssistedMutator {
    // 如果为true,则此mutator将记录详细的统计信息，例如执行每种类型操作的频率。
    private static let verbose = true

    // 在探索期间执行每个操作的频率，仅在verbose模式下使用。
    private var actionUsageCounts = [ActionOperation: Int]()

    // 出于统计目的，跟踪插入的explore操作的平均数量。
    private var averageNumberOfInsertedExploreOps = MovingAverage(n: 1000)
    public init() {
        super.init("ExplorationMutator", verbose: ExplorationMutator.verbose)
        if verbose {
            for op in ActionOperation.allCases {
                actionUsageCounts[op] = 0
            }
        }
    }
    ...
}

接下来是CodeGenMutator()：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/// A mutator that generates new code at random positions in a program.
// 在程序中的随机位置生成新代码的mutator
public class CodeGenMutator: BaseInstructionMutator {
    // DeadCodeAnalyzer是确定当前指令之后的代码是否为死代码（永远不会执行的部分，如return后面的代码）。
    private var deadCodeAnalyzer = DeadCodeAnalyzer()
    // VariableAnalyzer是在程序构造期间跟踪当前可见的变量（确保生成的代码能正确引用已有变量）。
    private var variableAnalyzer = VariableAnalyzer()
    private let minVisibleVariables = 3	// 最小可见变量数量为3，即最少3个可见变量才开始生成新代码

    public init() {
        super.init(maxSimultaneousMutations: defaultMaxSimultaneousCodeGenerations)
        // ProgramBuilder.minBudgetForRecursiveCodeGeneration指能够调用递归代码生成器所需的最小预算
        // defaultCodeGenerationAmount是每次生成代码时的默认预算
        assert(defaultCodeGenerationAmount >= ProgramBuilder.minBudgetForRecursiveCodeGeneration)
    }
    ...
}
1
2
3
4
5
6
7
// 在MutatorSettings.swift中一些全局变量定义如下
// 单次测试用例变异时，最多同时应用7种不同的基础变异（变异算子）操作
let defaultMaxSimultaneousMutations = 7		
// 单次测试用例变异时，最多插入3次全新生成的代码块，也就是最多执行3次CodeGenMutator
let defaultMaxSimultaneousCodeGenerations = 3	
// 每次调用CodeGenMutator时，生成指令的数量
let defaultCodeGenerationAmount = 5      // This must be at least ProgramBuilder.minBudgetForRecursiveCodeGeneration

需要确定的是，因为CodeGenMutator会有生成递归结构的可能性，一个递归结构需要生成至少五条FuzzIL指令，因此生成器每次生成的指令数需要大于递归结构最小的指令数。

紧接着是SpliceMutator()：

1
2
3
4
5
6
7
8
public class SpliceMutator: BaseInstructionMutator {
    private var deadCodeAnalyzer = DeadCodeAnalyzer()

    public init() {
        super.init(maxSimultaneousMutations: defaultMaxSimultaneousMutations)
    }
    ...
}

随后是ProbingMutator()：

1
2
3
4
5
6
7
8
9
10
/// A large bit of the logic of this mutator is located in the lifter code that implements Probe operations
/// in the target language. For JavaScript, that logic can be found in JavaScriptProbeLifting.swift.
// 这个mutator的大部分逻辑位于用目标语言实现Probe的lifter代码中。对于JavaScript，该逻辑可以在JavaScriptProbeLifting.swift中找到。
public class ProbingMutator: RuntimeAssistedMutator {
    ...
    public init() {
        super.init("ProbingMutator", verbose: ProbingMutator.verbose)
    }
    ...
}

然后是InputMutator，但是根据参数有不同的表现。InputMutator(typeAwareness: x)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class InputMutator: BaseInstructionMutator {  
    ...
    public init(typeAwareness: TypeAwareness) {
        // 初始化参数
        self.typeAwareness = typeAwareness
        self.logger = Logger(withLabel: "InputMutator \(String(describing: typeAwareness))")
        var maxSimultaneousMutations = defaultMaxSimultaneousMutations
        // A type aware instance can be more aggressive. Based on simple experiments and
        // the mutator correctness rates, it can very roughly be twice as aggressive.
        switch self.typeAwareness {
            case .aware:	// 当typeAwareness为.aware时，将单个测试用例变异次数扩大到原先两倍：7*2
            maxSimultaneousMutations *= 2
            default:
            break
        }
        super.init(name: "InputMutator (\(String(describing: self.typeAwareness)))", maxSimultaneousMutations: maxSimultaneousMutations)
    }
    ...
}

剩下的OperationMutator()和CombineMutator()在构造函数中没有做什么。

Fuzz
#Fuzz
Fuzzilli源码分析
https://loboq1ng.github.io/2025/03/13/Fuzzilli源码分析/
作者
Lobo Q1ng
发布于
2025年3月13日
许可协议