PaperlayerView exact revision on arXiv

Source-linked AI summary

Smart Greybox Fuzzing

Van-Thuan Pham, Marcel Böhme, Andrew E. Santosa, Alexandru Răzvan Căciulescu, Abhik Roychoudhury

arXiv:1811.09447v1cs.CR

TL;DR

Conventional greybox fuzzing wastes mutations on invalid inputs when processing complex file formats. The paper introduces smart greybox fuzzing, which combines structural mutations and validity-based scheduling with coverage feedback. AFLSMART substantially improves path coverage and bug discovery over baseline fuzzers, while the approach depends on file-format specifications whose validity is not guaranteed.

  • Problem

    Generic bit-level mutations are unlikely to produce valid structured inputs, limiting coverage-guided exploration of complex file-processing logic.

  • Method

    SGF uses a parsed virtual file structure, format-aware mutation operators, and a validity-based power schedule integrated with AFL’s coverage feedback.

  • Results

    AFLSMART achieved up to 200% higher path coverage and found 33 bugs versus 16 for AFL and AFLFAST within 24 hours.

  • Takeaways & Limitations

    Format awareness brings blackbox-style structural guidance into greybox fuzzing while retaining AFL’s coverage-feedback-driven search.

  • Takeaways & Limitations

    Structural mutations do not guarantee validity, and relaxed format specifications may permit files that violate the formal format.

Abstract

from arXiv · show

Coverage-based greybox fuzzing (CGF) is one of the most successful methods for automated vulnerability detection. Given a seed file (as a sequence of bits), CGF randomly flips, deletes or bits to generate new files. CGF iteratively constructs (and fuzzes) a seed corpus by retaining those generated files which enhance coverage. However, random bitflips are unlikely to produce valid files (or valid chunks in files), for applications processing complex file formats. In this work, we introduce smart greybox fuzzing (SGF) which leverages a high-level structural representation of the seed file to generate new files. We define innovative mutation operators that work on the virtual file structure rather than on the bit level which allows SGF to explore completely new input domains while maintaining file validity. We introduce a novel validity-based power schedule that enables SGF to spend more time generating files that are more likely to pass the parsing stage of the program, which can expose vulnerabilities much deeper in the processing logic. Our evaluation demonstrates the effectiveness of SGF. On several libraries that parse structurally complex files, our tool AFLSmart explores substantially more paths (up to 200%) and exposes more vulnerabilities than baseline AFL. Our tool AFLSmart has discovered 42 zero-day vulnerabilities in widely-used, well-tested tools and libraries; so far 17 CVEs were assigned.

1. Introduction

Smart greybox fuzzing addresses the input-structure blind spot of conventional coverage-based greybox fuzzing by combining structural mutations with coverage feedback. AFLSMART reports substantially higher path coverage and more bugs than baseline fuzzers on complex file formats.

  • CGF limitations: Coverage-based greybox fuzzing uses lightweight instrumentation and coverage-guided seed retention, but its generic mutations operate without input-format awareness.Mutated inputs are retained when they exercise sufficiently novel control flows, supporting continued exploration within a limited time budget.
  • CGF limitations: Random bit-level mutations are unlikely to create the structural changes needed to explore the sparse valid-input domain of complex file formats.This limitation affects applications processing image, audio, video, database, document, and spreadsheet files.
  • Prior approaches: Dictionary and dynamic-taint approaches add limited input awareness, while smart blackbox fuzzers construct valid files but lack greybox coverage feedback.The paper reports that Peach performed worse than AFL in its experiments because it did not reuse generated files through an evolving seed corpus.
  • Smart greybox fuzzing: A validity-based power schedule gives more energy to more-valid seeds, increasing time spent generating inputs likely to pass parsing and reach deeper processing logic.AFLSMART integrates Peach’s input-structure component with AFL’s coverage-feedback component.
  • Evaluation: Up to 200% higher path coverage and 33 bugs versus 16 for AFL and AFLFAST were reported within 24 hours on widely used, well-fuzzed projects.AFLSMART also found seven bugs that VUZZER missed and nine additional zero-day bugs in a one-week FFmpeg campaign; the supplied passage reports 8 and 9 CVEs assigned, respectively.
  • Smart greybox fuzzing: SGF derives a virtual structure from a seed file and applies structural mutation operators alongside bit-level mutations to generate format-aware inputs.The operators are designed to preserve satisfaction of the file-format specification while exploring new input domains.

2. Motivating Example

WAVE files use hierarchical chunks whose structural constraints shape parsing and can create difficult vulnerability-triggering conditions. The WavPack case shows why coverage-guided fuzzing struggles with complex valid mutations.

  • The WAVE File Format: WAVE files organize audio data and metadata in hierarchical chunks governed by a file format.Each chunk contains an identifier, length, and data; the root requires RIFF, a size field, and WAVE.
  • The Vulnerability: CVE-2018-10536 is a WavPack buffer overwrite requiring multiple format chunks and several complex structural conditions.The exploit file includes mandatory riff, fmt, and data chunks plus an additional fmt chunk after the first.
  • The Vulnerability: The first fmt chunk establishes IEEE float configuration, while the second supplies PCM values that override fields without resetting the float state.This preserves an invalid configuration that passes earlier checks and leads to an attacker-controlled buffer overwrite.
  • Traditional Greybox Fuzzing: Traditional greybox fuzzing mutates seed files with bit-level operators and retains inputs that increase coverage.Its power schedule determines how many mutations each seed receives; AFL favors small, quickly executing seeds.
  • Traditional Greybox Fuzzing: AFL is extremely unlikely to insert an additional valid fmt chunk at the boundary between existing fmt and data chunks.Dictionaries containing tokens such as RIFF, fmt, and data do not address the complex construction of a valid inserted chunk.

3. Smart Greybox Fuzzing

Smart greybox fuzzing combines coverage guidance with a virtual structural representation of inputs, enabling chunk-level mutations and validity-aware scheduling for deeper exploration.

  • Virtual Structure: SGF represents each input as a parse tree whose chunk nodes carry byte boundaries and types, while attribute leaves encode important nonstructural data.A parser derives this virtual structure from a file-format specification and the seed file.
  • Smart Mutation Operators: SGF provides smart deletion, addition, and splicing operators that manipulate chunks and revise affected indices in generated files.Deletion removes a chunk, addition inserts a compatible chunk from another seed, and splicing substitutes same-type chunks.
  • Maintaining Validity: Structural operators preserve a higher degree of validity than bit-level mutation, while mutable attributes remain available for constrained bit-level changes.The approach increases the likelihood of producing files that pass parsing, although relaxed structural constraints can permit formally invalid files.
  • Deferred Parsing: Deferred parsing constructs a seed’s virtual structure probabilistically, increasing that probability as the time since the last new path discovery grows.When t reaches the threshold ϵ, construction occurs with probability 100%, limiting the overhead of parsing every newly discovered seed.
  • Validity-based Power Schedule: The validity-based power schedule treats validity as a ratio and assigns more energy to seeds with higher validity.This scheduling strategy is designed to spend more effort on inputs more likely to pass the parser and reach deeper processing logic.

4. File Format Specification

The paper develops reusable, progressively specified file-format models using chunk inheritance, coarse-grained completeness, and deliberately relaxed constraints.

  • File Format Specification: File-format specifications are costly to construct manually, so the authors use recurring structural patterns across document, video, audio, image, executable, and network formats.Tools such as 010Editor can decompose sample files into chunks and attributes; it supports 114 common file formats.
  • 4.1. Insight-1. Chunk inheritance: Chunk inheritance models shared attributes in a generic chunk and places format-specific attributes in concrete child chunks.The WAVE example represents common identifiers, sizes, data, and padding once, then specializes the format chunk’s fields.
  • 4.2. Insight-2. Specification completeness: A specification can begin coarse-grained and become more complete because unspecified chunk data can be treated as a size-consistent blob.This approach omits child attributes initially while retaining the chunk identifier and size relationship.
  • 4.2. Insight-2. Specification completeness: 82 lines specify WAVE and 24 lines specify PCAP, and these specifications helped SGF discover vulnerabilities missed by baseline techniques.The reported compact specifications support practical use of the specification-completeness insight.
  • 4.3. Insight-3. Relaxed constraints: Relaxed constraints preserve parser decomposition while allowing corner-case structures such as alternative chunk choices and repeated chunks.The WAVE model permits up to 30000 occurrences in its chunk choice, rather than enforcing every formal-format constraint.
  • 4.4. Insight-4. Reusability: File-format specifications are reusable across programs that process the same format, unlike specifications of program behavior.The authors report using specifications for 10 popular formats to discover more than 40 vulnerabilities.

5. Experimental Setup

The evaluation compares AFLSMART with traditional greybox and smart blackbox fuzzers across structured-file programs, using shared resources, specifications, and seed corpora. AFLSMART extends AFL with structure-aware components and validity-guided energy allocation.

  • Evaluation goals: AFLSMART is evaluated against AFL, AFLFAST, and Peach to measure input-structure awareness and vulnerability-finding capability.The experiments also compare AFLSMART with VUZZER on VUZZER’s benchmark.
  • AFLSMART architecture: AFLSMART adds a File Cracker, Structure Collector, Energy Calculator, and modified Fuzzer to AFL.The Fuzzer implements hierarchical virtual structures and chunk-level mutations, while the Energy Calculator assigns more energy to syntactically valid inputs.
  • Implementation scope: AFLSMART’s changes preserve AFL’s instrumentation and support fuzzing instrumented binaries through compatible binary-fuzzing tools.The paper notes compatibility with binaries instrumented using tools such as DynamoRio.
  • Subject programs: The benchmark covers 11 well-known open-source subjects processing highly structured ELF, PNG, JPEG, JP2, WAV, and AVI files.The selected programs had been well tested for many years.
  • Inputs and specifications: AFLSMART and Peach use the same ten Peach Pit file-format specifications, while AFL and AFLSMART also use dictionaries where available.The ten specifications cover PDF, AVI, MP3, WAV, JPEG, JPEG2000, PNG, GIF, PCAP, and ELF.
  • Experimental controls: All fuzzers receive the same initial seed corpus, dictionaries, computational resources, and 24-hour time budget in the primary comparison.For each subject, five isolated instances of each fuzzer run in parallel to mitigate randomness.

6. Experimental Results

AFLSMART generally improves path exploration and bug finding over AFL, AFLFAST, Peach, and VUZZER on structured-file benchmarks. Its advantages are attributed to coverage feedback combined with structural mutations and valid-file generation.

  • RQ.1 SGF Versus Traditional Greybox Fuzzing: AFLSMART discovered more paths than AFL and AFLFAST in 10 of 12 subjects, including 200% more paths on ffmpeg and avconv.It underperformed on nm-new and decompress after the first six hours, although early path coverage was similar.
  • RQ.1 SGF Versus Traditional Greybox Fuzzing: 33 zero-day bugs were found by AFLSMART, compared with 16 found by AFL and AFLFAST; all baseline bugs were also found by AFLSMART.Seventeen reported bugs were heap or stack buffer overflows, and 12 were fixed by maintainers.
  • RQ.1 SGF Versus Traditional Greybox Fuzzing: AFLSMART’s advantage on structured media programs is linked to keeping data chunks ordered and correctly located during mutation.Traditional greybox mutations struggle with highly structured image, audio, and video files.
  • RQ.2 SGF Versus Smart Blackbox Fuzzing: Given the same specifications, AFLSMART outperformed Peach in all 12 subjects and found 33 zero-day bugs while Peach found no vulnerabilities.AFLSMART also generated up to an order of magnitude more meaningful test cases.
  • RQ.2 SGF Versus Smart Blackbox Fuzzing: Peach’s enumeration-based smart blackbox strategy lacks coverage feedback and seed-corpus evolution, limiting its exploration of the benchmark.The paper also attributes Peach’s performance to the precision and completeness of its file-format specifications.
  • RQ.3 Versus Taint analysis-based Greybox Fuzzing: AFLSMART found 15 bugs on VUZZER’s benchmark, including seven that VUZZER did not find in tcpdump, tcptrace, and gif2png.These bugs were not zero-day vulnerabilities because the benchmark uses old software versions.
  • RQ.3 Versus Taint analysis-based Greybox Fuzzing: AFLSMART and VUZZER found 16 bugs together, with AFLSMART finding almost all bugs discovered by VUZZER.The paper characterizes the approaches as potentially supplementary because they exploit structural information and taint-inferred attribute features differently.

7. Case Study.Bug Hunting using AFLSMART

A one-week FFmpeg campaign tested AFLSMART with an AVI specification and found nine zero-day crashes, all of which were fixed and assigned CVE identifiers. The case study supports practical impact on heavily fuzzed software.

  • Campaign design: AFLSMART was tested against FFmpeg because it is a popular, heavily fuzzed software package used by many applications.The campaign targeted AVI-to-MPEG4 conversion functionality.
  • Findings: Nine zero-day crashing bugs were found during one week of parallel AFLSMART fuzzing with the AVI input specification.Five AFLSMART instances ran in parallel.
  • Findings: All nine FFmpeg bugs were fixed and assigned CVE IDs, with severity ratings ranging from medium to high.The findings included buffer overflows, null pointer dereferences, and assertion failures.
  • Implication: The case study concludes that smart greybox fuzzing has practical impact for programs processing highly structured input files.It also states that the vulnerability-finding benefit outweighs the one-time effort of writing input specifications.

8. Related Work

The paper positions AFLSMART at the intersection of coverage-based greybox fuzzing and input-structure awareness. It contrasts its approach with smart blackbox, smart whitebox, boosted, restricted-mutation, symbolic-execution, and format-inference techniques.

  • Smart blackbox fuzzing: Smart blackbox fuzzers use grammars or file-format specifications to generate inputs while treating the target program as a black box.Examples include Peach, Spike, Domato, and LangFuzz.
  • Smart whitebox fuzzing: Smart whitebox fuzzers combine program structure and input structure, often using symbolic execution or semantic constraints.Grammar-based and model-based whitebox fuzzing are cited as examples.
  • Coverage-based greybox fuzzing: Coverage-based greybox fuzzing uses lightweight instrumentation to guide exploration without the high constraint-solving overhead of whitebox approaches.The paper presents AFLSMART as the first input format-aware greybox fuzzer to its knowledge.
  • Boosted greybox fuzzing: Boosted greybox fuzzers prioritize seeds using models such as Markov chains, target distance, or gradient descent to improve coverage or reachability.AFLFAST, AFLGO, and Angora exemplify these strategies.
  • Restricted mutations: Restricted-mutation approaches specialize mutation locations or operations using program analysis, magic bytes, or learned bit dependencies.VUZZER, Steelix, and SymFuzz are representative systems.
  • Greybox fuzzing and symbolic execution: Other hybrids remove blocking checks or combine fuzzing with symbolic execution, whereas AFLSMART avoids symbolic execution while retaining greybox efficiency.T-Fuzz and Driller illustrate the contrasted designs.
  • Format specification inference: Format-inference research derives input structure from traces, machine learning, or dynamic taint analysis rather than relying solely on manually written specifications.Examples include Learn&Fuzz and AUTOGRAM.

9. Discussion

AFLSMART combines input-format awareness with greybox feedback while retaining AFL’s efficiency, achieving higher path coverage and finding more bugs than AFL. Its current scope can be extended toward protocol fuzzing and automated format learning.

  • AFLSMART achieves up to 200% higher path coverage and finds more bugs than AFL on applications processing popular file formats.The evaluation covered formats including AVI, MP3, and WAV.
  • File-format-aware mutations, validity-based power schedules, and deferred parsing preserve the efficiency of AFL while adding input-format awareness.
  • Specifying an input format requires a one-time manual effort limited to 4 hours for each examined format.
  • Future work could extend AFLSMART from file-format fuzzing to reactive-system protocol fuzzing using input protocol specifications and state models.
  • Automatically learning input formats and interfacing with other format-aware fuzzers could reduce manual effort and broaden AFLSMART’s supported formats.
Loading 1811.09447v1…