FuzzCheck

(注意：我曾在 Functional Swift Conference 上讨论过 FuzzCheck，点击此处观看视频。视频比此自述文件更好地解释了其背后的动机。）

FuzzCheck 是一个实验性的覆盖率引导的模糊测试引擎，适用于 Swift 包，它使用类型化的值而不是原始二进制缓冲区。

名称“FuzzCheck”是“Fuzzer”（模糊器）和“QuickCheck”的组合。目标是创建一个足够方便的模糊测试引擎，可以用作基于属性的测试的输入生成器。

给定一个测试函数 (Input) -> Bool，它会尝试查找触发代码中边缘情况的 Input 值。它还可以自动最小化导致测试失败的输入。

因为 FuzzCheck 本身就是一个 Swift 包，所以它比 libFuzzer 更容易修改。如果您想为它做出贡献，我很高兴指导您了解代码。

FuzzCheck 尚未准备好用于生产环境。使用它需要 Swift 编译器的开发快照和 Swift Package Manager 的自定义构建。这是因为必须为被测目标启用编译标志 -sanitize=fuzzer。

好消息是，一旦安装了这些工具，FuzzCheck 就只是您的 Package.swift 文件中的另一个依赖项！

• 访问 swift.org/downloads，点击“Xcode”链接并按照说明下载 Swift 4.2 开发快照。
• 找到您刚刚安装的 swiftc 可执行文件的路径，并将其分配给 SWIFT_EXEC 环境变量。例如，如果您安装的是 7 月 3 日的快照，则应运行

  export SWIFT_EXEC=/Library/Developer/Toolchains/swift-4.2-DEVELOPMENT-SNAPSHOT-2018-07-03-a.xctoolchain/usr/bin/swiftc

• 克隆我 fork 的 Swift Package Manager。

  git clone https://github.com/loiclec/swift-package-manager

• 然后构建它。应该不会超过几分钟。

  cd swift-package-manager
  Utilities/bootstrap

就这样！您现在拥有使用 FuzzCheck 所需的一切！用于编译 Swift 包的可执行文件位于 swift-package-manager/.build/x86_64-apple-macosx10.10/debug/ 中

# swiftc: verify that its version contains `Apple Swift version 4.2-dev`
.build/x86_64-apple-macosx10.10/debug/swiftc --version
Apple Swift version 4.2-dev (LLVM 647959670b, Clang 8756d7b836, Swift 107e307eae)
Target: x86_64-apple-darwin18.0.0

# swift-build replaces `swift build`
.build/x86_64-apple-macosx10.10/debug/swift-build --version
Swift Package Manager - Swift 4.2.0

# swift-package replaces `swift package`
.build/x86_64-apple-macosx10.10/debug/swift-package --version

Swift Package Manager - Swift 4.2.0

我创建了一个名为 FuzzCheckExample 的示例项目，您可以使用它来熟悉 FuzzCheck。但在解释其工作原理之前，让我们尝试启动它并最终看到一些结果！

git clone https://github.com/loiclec/FuzzCheckExample.git
cd FuzzCheckExample
# Use the swift-build executable from the modified SwiftPM and use the fuzz-release configuration
../swift-package-manager/.build/x86_64-apple-macosx10.10/debug/swift-build -c fuzz-release
# launch FuzzCheckTool with the test target as argument
.build/fuzz-release/FuzzCheckTool --target FuzzCheckExample

几秒钟后，该过程将停止

...
...
DELETE 1
NEW     528502  score: 122.0    corp: 81        exec/s: 103402  rss: 8
DELETE 1
NEW     528742  score: 122.0    corp: 81        exec/s: 103374  rss: 8

================ TEST FAILED ================
529434  score: 122.0    corp: 81        exec/s: 103374  rss: 8
Saving testFailure at /Users/loic/Projects/fuzzcheck-example/artifacts/testFailure-78a1af7b1be086ca0.json

它在 529434 次迭代后检测到测试失败，并将 JSON 编码的崩溃输入保存在文件 testFailure-78a1af7b1be086ca0.json 中。五十万次迭代可能看起来很多，但如果测试使用简单的穷举或随机搜索，即使经过数万亿次迭代，也永远找不到该测试失败。

FuzzCheckExample 的 Package.swift 清单是

// swift-tools-version:4.2
import PackageDescription

let package = Package(
    name: "FuzzCheckExample",
    products: [
        .library(name: "Graph", targets: ["Graph"]),
        .executable(name: "FuzzCheckExample", targets: ["FuzzCheckExample"])
    ],
    dependencies: [
        .package(url: "https://github.com/loiclec/FuzzCheck.git", .revision("b4abbf661f4d187ec88bc2811893283d4c091260"))
    ],
    targets: [
        .target(name: "FuzzCheckExample", dependencies: [
            "FuzzCheck",
            "FuzzCheckTool", 
            "GraphFuzzerInputGenerator", 
            "Graph"
        ]),
        .target(name: "GraphFuzzerInputGenerator", dependencies: ["FuzzCheck", "Graph"]),
        .target(name: "Graph", dependencies: [])
    ],
    fuzzedTargets: [
        "FuzzCheckExample",
        "Graph"
    ]
)

此清单

• 具有 FuzzCheck 依赖项，固定到特定提交（尚未发布稳定版本）
• 包含一个名为 FuzzCheckExample 的模糊测试可执行文件。它的目标依赖于 FuzzCheck 和 FuzzCheckTool。
• 具有一个 fuzzedTargets 参数，其中包含需要使用 fuzzer sanitizer 编译的目标
• 具有一个 GraphFuzzerInputGenerator 目标，它定义了如何改变 Graph 类型的值。这是 FuzzCheck 所必需的。

测试本身位于 Sources/FuzzCheckExample/main.swift 中

import FuzzCheck
import GraphFuzzerInputGenerator
import Graph

func test(_ g: Graph<UInt8>) -> Bool {
    if
        g.count == 8,
        g.vertices[0].data == 100,
        g.vertices[1].data == 89,
        g.vertices[2].data == 10,
        g.vertices[3].data == 210,
        g.vertices[4].data == 1,
        g.vertices[5].data == 210,
        g.vertices[6].data == 9,
        g.vertices[7].data == 17,
        g.vertices[0].edges.count == 2,
        g.vertices[0].edges[0] == 1,
        g.vertices[0].edges[1] == 2,
        g.vertices[1].edges.count == 2,
        g.vertices[1].edges[0] == 3,
        g.vertices[1].edges[1] == 4,
        g.vertices[2].edges.count == 2,
        g.vertices[2].edges[0] == 5,
        g.vertices[2].edges[1] == 6,
        g.vertices[3].edges.count == 1,
        g.vertices[3].edges[0] == 7,
        g.vertices[4].edges.count == 0,
        g.vertices[5].edges.count == 0,
        g.vertices[6].edges.count == 0,
        g.vertices[7].edges.count == 0
    {
        return false
    }
    return true
}

let generator = 
    GraphFuzzerInputGenerator<IntegerFuzzerGenerator<UInt8>>(
        vertexGenerator: .init()
    )

try CommandLineFuzzer.launch(
    test: test, 
    generator: generator
)

这是一个愚蠢的测试，只有当作为输入的图数据结构等于以下内容时才会失败

             ┌─────┐            
             │ 100 │            
             └─┬─┬─┘            
        ┌──────┘ └──────┐       
     ┌──▼──┐         ┌──▼──┐    
     │ 89  │         │ 10  │    
     └──┬──┘         └──┬──┘    
   ┌────┴───┐       ┌───┴───┐   
┌──▼──┐  ┌──▼──┐ ┌──▼──┐ ┌──▼──┐
│ 210 │  │  1  │ │ 210 │ │  9  │
└──┬──┘  └─────┘ └─────┘ └─────┘
   │                            
┌──▼──┐                         
│ 17  │                         
└─────┘                         

在没有向模糊器传递任何关于测试的特殊知识的情况下，它能够在不到 1_000_000 次迭代中找到此图！考虑到仅仅找到其顶点的 8 个值平均需要 256^7 ~= 70_000_000_000_000_000 次迭代（通过简单的穷举或随机搜索），这令人印象深刻。

要测试函数 (Input) -> Bool，您需要一个 FuzzerInputGenerator 来生成 Input 的值。FuzzerInputGenerator 有三个要求

1. 一个属性 baseInput，其中包含 Input 的最简单可能的值（例如，空数组）
2. 一个略微改变 Input 值的函数（例如，将元素附加到数组）
3. 一个生成 Input 随机值的函数（有一个基于 mutate 函数的默认实现）

public protocol FuzzerInputGenerator: FuzzerInputProperties {
    associatedtype Input

    var baseInput: Input { get }
    func initialInputs(maxComplexity: Double, _ rand: inout FuzzerPRNG) -> [Input]
    func mutate(_ input: inout Input, _ spareComplexity: Double, _ rand: inout FuzzerPRNG) -> Bool
}

FuzzerInputGenerator 还符合 FuzzerInputProperties，它给出了输入的复杂性和哈希值

public protocol FuzzerInputProperties {
    associatedtype Input

    static func complexity(of input: Input) -> Double
    static func hash(_ input: Input, into hasher: inout Hasher)
}

我希望提供许多开箱即用的这两个协议的默认实现，并拥有自动创建它们的工具（例如，使用 Sourcery）。但目前，您必须自己实现它们。

FuzzCheck 的工作原理是维护一个测试输入池，并使用输入的复杂性和 test(input) 引起的代码覆盖率的唯一性对它们进行排名。从该池中，它选择一个高排名的输入，对其进行变异，然后再次运行测试函数。如果新的变异输入在二进制文件中发现了新的代码路径，则将其添加到池中，否则，FuzzCheck 会使用不同的输入和变异再次尝试。

在伪代码中（实际实现稍微复杂一些）

while true {
    var input = pool.select()
    mutate(&input)

    let analysis = analyze { test(input) }

    switch analysis {
    case .crashed, .failed:
        return reportFailure(input)
    case .interesting(let score):
        pool.add(input, score)
    case .notInteresting:
        continue
    }
}

• 不支持使用多个线程的测试（但将来应该支持）
• 几乎没有提供 FuzzerInputGenerator 实现
• 大型代码库的模糊测试速度会很慢。需要完成一些工作才能使其更快
• 一些基本的设计和实现细节可能仍会发生变化

FuzzCheck 最初是 LLVM 的 libFuzzer 的副本，但从那时起发生了重大变化。主要区别在于 FuzzCheck

• 使用类型化的值而不是原始二进制缓冲区
• 使用不同的算法对池中的输入进行排名
• 旨在使代码覆盖率以外的其他度量标准可用于对池中的输入进行排名
• 不支持交叉变异
• 不使用字典，无论是手动的还是自动的
• 仅适用于 Swift 程序
• 未与地址清理器集成
• 未经实战检验，尚未证明自己