Automatic, Expressive, and Scalable Fuzzing with Stitching

1. Problem Statement

Automated fuzzing is a dominant technique for finding security vulnerabilities, but it faces two critical scalability challenges when applied to complex software libraries:

• Combinatorial Explosion of API Sequences: Traditional fuzzing approaches either synthesize fixed API sequences (harnesses) at compile time or explore sequences dynamically. Fixed-sequence harnesses (e.g., PromeFuzz, PromptFuzz) cannot cover the vast combinatorial space of possible function call orders. Dynamic approaches often lack the expressiveness to model complex usage constraints, leading to a flood of false positives caused by invalid API misuse (e.g., passing an object to a function before it is initialized).
• Complex Usage Constraints: Real-world libraries have strict, often undocumented, semantic constraints. These range from structural requirements (correct data types) to semantic state dependencies (e.g., a file handle must be open, or an object must share the same parent document as another). Existing tools struggle to encode these constraints, causing fuzzers to waste time exploring invalid states rather than finding genuine bugs.

2. Methodology: Stitching

The authors propose Stitching, a technique that encodes API usage constraints into composable "blocks" which a fuzzer dynamically assembles at runtime.

Core Concepts

• Code Blocks: Small units of code representing valid invocations of a single library function. Each block defines its inputs, outputs, and internal logic.
• Dynamic Assembly: Instead of a pre-defined sequence, the fuzzing engine "stitches" these blocks together at runtime to form testcases. This allows the fuzzer to explore millions of potential sequences guided by coverage feedback.
• Hybrid Constraint System: To handle complex constraints without sacrificing scalability, Stitching employs:
  1. Static Type System: Ensures structural correctness (e.g., matching C++ types) between blocks.
  2. Extrinsic Typestate: A dynamic mechanism that tracks arbitrary metadata (key-value pairs) across block executions. Blocks can read/write metadata (e.g., "is this file open?", "what is the parent document ID?") and enforce semantic constraints. If a constraint is violated (e.g., trying to read a closed file), the block executes a Bail signal, cleanly exiting that testcase without crashing the fuzzer. This focuses the search on valid API interactions.

The STITCH System

The authors implemented Stitching in STITCH, an end-to-end system for C/C++ that leverages Large Language Models (LLMs) to automate the entire fuzzing pipeline:

1. Configuration: An LLM agent analyzes a repository URL, compiles the project with instrumentation, and identifies public headers.
2. Specification Synthesis:
   • API Scanning: The LLM distills API functions and objects from headers into canonical descriptions.
   • Code Block Synthesis: The LLM generates C++ code blocks for each function, incorporating FUZZ_PARAM macros for random data and FUZZ_BAIL for constraint checking.
   • Data Generator Synthesis: The LLM creates generators to seed the fuzzer with meaningful initial values (e.g., valid JSON strings).
3. Iterative Fuzzing & Repair:
   • The fuzzer executes stitched testcases.
   • Triage Agent: Analyzes crashes, minimizes testcases, and distinguishes between true bugs and specification errors (false positives).
   • Patch Agent: If a crash is caused by an incorrect specification (e.g., missing a constraint), the LLM automatically updates the code blocks to fix the specification, and the fuzzer restarts with the refined constraints.

3. Key Contributions

• Stitching Technique: A novel formalism for encoding arbitrary API constraints in a fuzzable specification using extrinsic typestate, enabling the exploration of valid, complex interaction spaces.
• STITCH Implementation: A fully autonomous system for C/C++ that requires only a repository URL. It handles configuration, specification synthesis, fuzzing, crash triage, and specification repair without human intervention.
• Comprehensive Evaluation:
  • Benchmarking: Outperformed state-of-the-art (SOTA) tools (PromeFuzz, PromptFuzz, OGHarn) on 33 benchmarks.
  • Real-World Deployment: Successfully deployed on 1,365 open-source projects.

4. Results

The evaluation demonstrates significant improvements in coverage, bug discovery, and precision:

• Code Coverage: STITCH achieved the highest code coverage on 21 out of 33 benchmarks compared to SOTA tools.
• Bug Discovery:
  • On benchmarks, STITCH found 30 true-positive bugs, whereas all other tools combined found only 10.
  • In the large-scale real-world evaluation, STITCH discovered 131 new bugs across 102 projects.
  • 73 of these bugs have already been patched by maintainers.
• Precision: STITCH achieved a 70% precision rate (true positives vs. total crashes), significantly higher than the next-best LLM-based tool (12%). This is attributed to the effective use of extrinsic typestate to filter out invalid API misuses.
• Efficiency: STITCH was faster at inferring specifications (avg. 19 mins/benchmark) and more cost-effective ($1.77/bug) compared to competitors like PromptFuzz ($300/bug).

Notable Discoveries:

• pupnp: Found a crash involving namespace attributes that had eluded previous OSS-Fuzz efforts.
• libjpeg-turbo: Discovered a documentation gap leading to heap overflows.
• libcups: Found a remotely exploitable heap overflow in a release candidate.
• opencv: Identified out-of-bounds read vulnerabilities.

5. Significance

This paper represents a major advancement in automated software testing by bridging the gap between automation and semantic understanding.

• Scalability: By using LLMs to synthesize specifications and a dynamic "stitching" engine to explore them, STITCH overcomes the combinatorial explosion that limits traditional harness generation.
• Expressiveness: The introduction of extrinsic typestate allows fuzzers to model complex, state-dependent constraints that were previously too difficult to encode, drastically reducing false positives.
• Autonomy: STITCH demonstrates that fully autonomous bug finding is feasible at scale. It can configure, test, triage, and refine its own specifications, reducing the manual burden on security researchers and maintainers.
• Impact: The discovery and patching of 73 real-world vulnerabilities in widely used libraries (including OpenCV, CUPS, and JPEG libraries) highlights the immediate practical value of the approach for improving software security.