Automatic, Expressive, and Scalable Fuzzing with Stitching

这篇论文提出了一种名为 Stitching（缝合） 的新型模糊测试（Fuzzing）技术，并实现了名为 STITCH 的系统。该系统利用大语言模型（LLM）自动为 C/C++ 库生成模糊测试规范，旨在解决现有自动化模糊测试在扩展性、表达力和误报率方面的局限性。

以下是对该论文的详细技术总结：

1. 问题背景与挑战 (Problem & Challenges)

现有的自动化模糊测试方法主要面临两个核心挑战，导致难以覆盖真实世界中复杂的 API 交互：

• 组合爆炸的搜索空间 (Combinatorial Search Space)：

  • 现代软件库包含大量函数，可能的调用序列呈组合爆炸式增长。
  • 传统的自动化测试生成工具（如自动生成的 Harness）通常在合成阶段就固定了 API 调用序列。这意味着每个 Harness 只能测试有限的几种顺序，无法覆盖所有可能的交互路径。
  • 即使尝试动态生成序列，如果缺乏约束，搜索空间也会大到无法遍历。

• 复杂的 API 使用约束 (Complex API Usage Constraints)：

  • 许多 API 调用有严格的结构和语义约束（例如：对象必须先初始化、文件句柄必须处于打开状态、特定参数必须匹配特定的对象状态）。
  • 现有的动态模糊测试工具（如 Hopper）往往忽略这些约束，导致大量时间浪费在生成无效的 API 误用（False Positives）上，而不是发现真正的漏洞。
  • 现有的基于图或状态机的方法（如 GraphFuzz）通常只能表达基本的生命周期约束，难以处理复杂的语义依赖（如“两个对象必须属于同一个父文档”）。

2. 方法论：Stitching 技术 (Methodology: Stitching)

Stitching 的核心思想是将 API 的使用约束编码为可组合的“代码块（Blocks）”，模糊测试引擎在运行时动态地将这些块“缝合”在一起，而不是预先定义固定的序列。

核心机制：

1. 代码块 (Code Blocks)：

   • 每个块描述单个库函数的调用方式，包含输入、输出和可模糊的参数（Fuzzable Parameters）。
   • 块之间通过引用索引连接，形成有向无环图（DAG），表示数据流。

2. 混合类型系统 (Hybrid Type System)：

   • 静态类型系统： 确保基本的结构正确性（如参数类型匹配）。
   • 外在类型状态 (Extrinsic Typestate)： 这是 STITCH 的关键创新。它允许在运行时动态跟踪和更新对象的元数据（Metadata）。
     • 代码块可以读取和写入任意键值对（Key-Value pairs）到对象或全局状态中。
     • 动态检查： 在调用函数前，块可以检查元数据。如果约束不满足（例如：尝试从已关闭的文件读取），块会优雅地退出（Bail），而不是导致崩溃。
     • 这使得规范能够表达丰富的语义约束（如：属性是否带命名空间、对象是否共享父文档），从而大幅减少无效测试用例。

3. 运行时执行：

   • 模糊测试引擎根据覆盖率反馈，随机采样并缝合代码块，构建测试用例。
   • 只有满足所有约束（不触发 Bail）的序列才会继续执行，从而引导搜索空间聚焦于有效的 API 交互。

3. 系统实现：STITCH (System Implementation)

STITCH 是一个端到端的自动化系统，利用 LLM 来配置项目、生成规范、分类崩溃并修复规范。

• 工作流：
  1. 项目配置 (Configure Agent)： 自动分析仓库，构建 Docker 容器，配置模糊测试仪器（Instrumentation），并定位头文件。
  2. 规范合成 (Inference Workflow)：
     • API 扫描： LLM 扫描头文件，提取函数签名、对象类型和使用约束。
     • 代码块合成： 为每个函数生成对应的代码块，包含调用逻辑和约束检查。
     • 数据生成器合成： 为复杂的输入格式（如 JSON、特定字符串）生成初始种子数据。
  3. 迭代模糊测试 (Iterative Fuzzing Loop)：
     • 执行缝合后的测试用例。
     • 崩溃分类 (Triage Agent)： 自动分析崩溃，区分是真正的 Bug、规范错误导致的误报，还是浅层 Bug。
     • 规范修复 (Patch Agent)： 如果崩溃是由错误的规范（如错误的约束逻辑）引起的，LLM 会自动修改代码块以排除该误报，然后重新运行模糊测试。

4. 主要贡献 (Key Contributions)

1. Stitching 技术： 提出了一种在模糊测试规范中编码任意 API 约束的新方法，通过动态缝合代码块和外在类型状态，实现了高表达力且可扩展的测试。
2. STITCH 系统： 实现了首个完全独立运行、无需人工干预即可为 C/C++ 库生成测试并发现漏洞的端到端系统。
3. 评估结果：
   • 在 33 个基准测试中，STITCH 在 21 个项目中实现了最高的代码覆盖率。
   • 发现了 30 个真阳性（True Positive）漏洞，而其他所有对比工具（包括 PromeFuzz, PromptFuzz, OGHarn 和 OSS-Fuzz 手动 Harness）加起来仅发现了 10 个。
   • 精度极高： STITCH 的误报率仅为 30%（即 70% 的精度），而基于 LLM 的次优工具（PromeFuzz）精度仅为 12%。
4. 大规模真实世界评估：
   • 在 1365 个 广泛使用的开源项目中自动部署。
   • 成功配置了约 67% 的项目。
   • 发现了 131 个新漏洞，分布在 102 个项目中。
   • 其中 73 个漏洞已被修复，包括 OpenCV、libjpeg-turbo 和 libcups 等关键库中的严重漏洞（如越界读写、堆溢出）。

5. 意义与影响 (Significance)

• 突破扩展性瓶颈： STITCH 证明了通过动态缝合和语义约束，可以在不牺牲覆盖率的情况下，有效处理复杂的 API 交互空间，解决了传统方法“要么覆盖不全，要么误报太多”的困境。
• 自动化程度高： 从项目配置到漏洞报告的全流程自动化，极大地降低了模糊测试的门槛，使得大规模、持续性的开源软件安全审计成为可能。
• LLM 在安全领域的有效应用： 展示了 LLM 不仅可用于生成代码，还能通过迭代反馈机制（合成 - 测试 - 修复）来理解复杂的文档和代码约束，生成高质量的测试规范。
• 实际安全价值： 在真实世界中发现了大量尚未被修复的高危漏洞，证明了该方法在提升软件供应链安全性方面的巨大潜力。

总结：
这篇论文通过引入“缝合”概念和“外在类型状态”机制，结合 LLM 的自动化能力，成功构建了一个能够自动理解复杂 API 约束、高效探索有效测试路径并发现真实漏洞的系统。STITCH 在覆盖率、漏洞发现数量和精度上均显著优于现有的最先进（SOTA）工具，为自动化软件安全测试树立了新的标杆。