PaperlayerView exact revision on arXiv

Source-linked AI summary

Superion: Grammar-Aware Greybox Fuzzing

Junjie Wang, Bihuan Chen, Lei Wei, Yang Liu

arXiv:1812.01197v3cs.CRcs.SE

TL;DR

Grammar-blind trimming and mutation make coverage-based greybox fuzzing less effective on structured inputs such as XML and JavaScript. Superion extends AFL with grammar-aware AST-based trimming and mutation strategies, and its evaluation reports higher coverage and bug-finding capability, including 31 new bugs and 21 new vulnerabilities. Its applicability is limited to formats with available grammars.

  • Problem

    Grammar-blind trimming and mutation in coverage-based greybox fuzzers often damage structured inputs or fail syntax parsing, limiting fuzzing of XML and JavaScript programs.

  • Method

    Superion uses input grammars and ASTs for grammar-aware trimming, enhanced dictionary mutation, and tree-based subtree replacement.

  • Results

    Superion improved coverage over AFL by 16.7% in line coverage and 8.8% in function coverage, while finding 31 new bugs, including 21 new vulnerabilities with 16 CVEs assigned.

  • Takeaways & Limitations

    Grammar-aware trimming and mutation can preserve syntax validity while extending fuzzing exploration for structured inputs.

  • Takeaways & Limitations

    Superion requires a grammar, limiting applicability to publicly documented formats with specified grammars.

Abstract

from arXiv · show

In recent years, coverage-based greybox fuzzing has proven itself to be one of the most effective techniques for finding security bugs in practice. Particularly, American Fuzzy Lop (AFL for short) is deemed to be a great success in fuzzing relatively simple test inputs. Unfortunately, when it meets structured test inputs such as XML and JavaScript, those grammar-blind trimming and mutation strategies in AFL hinder the effectiveness and efficiency. To this end, we propose a grammar-aware coverage-based greybox fuzzing approach to fuzz programs that process structured inputs. Given the grammar (which is often publicly available) of test inputs, we introduce a grammar-aware trimming strategy to trim test inputs at the tree level using the abstract syntax trees (ASTs) of parsed test inputs. Further, we introduce two grammar-aware mutation strategies (i.e., enhanced dictionary-based mutation and tree-based mutation). Specifically, tree-based mutation works via replacing subtrees using the ASTs of parsed test inputs. Equipped with grammar-awareness, our approach can carry the fuzzing exploration into width and depth. We implemented our approach as an extension to AFL, named Superion; and evaluated the effectiveness of Superion on real-life large-scale programs (a XML engine libplist and three JavaScript engines WebKit, Jerryscript and ChakraCore). Our results have demonstrated that Superion can improve the code coverage (i.e., 16.7% and 8.8% in line and function coverage) and bug-finding capability (i.e., 31 new bugs, among which we discovered 21 new vulnerabilities with 16 CVEs assigned and 3.2K USD bug bounty rewards received) over AFL and jsfunfuzz. We also demonstrated the effectiveness of our grammar-aware trimming and mutation.

I. INTRODUCTION

Structured inputs such as XML and JavaScript challenge grammar-blind greybox fuzzers because trimming and mutation often destroy syntax validity or stall exploration at parsing. Superion addresses these challenges with grammar-aware AST-based trimming and mutation, and outperforms AFL in coverage and bug finding.

  • Challenges: Structured-input programs process inputs through syntax parsing, semantic checking, and application execution, creating challenges for coverage-based greybox fuzzing.
  • Challenges: AFL’s grammar-blind trimming can destroy input structure, causing syntax errors and limiting exploration of deeper bugs.
  • Challenges: AFL’s grammar-blind mutations often fail syntax parsing, making large-step mutations difficult.
  • Proposed Approach: Superion parses inputs into ASTs and trims subtrees while observing coverage differences, preserving valid structure during trimming.
  • Proposed Approach: Superion improves AFL’s dictionary mutation with grammar-aware token operations and adds tree-based subtree replacement using queued test inputs.
  • Evaluation: 16.7% line coverage and 8.8% function coverage improvements over AFL accompanied Superion’s discovery of 31 new bugs.
  • Evaluation: 21 new vulnerabilities received 16 CVEs, and the authors received 3.2K USD in bug bounty rewards.

II. OUR APPROACH

Superion extends AFL with grammar-aware techniques for fuzzing structured inputs. Its approach uses a grammar-aware trimming strategy and two grammar-aware mutation strategies to preserve input validity while expanding exploration.

  • Grammar-Aware Fuzzing: Superion requires a context-free grammar to parse structured test inputs into ASTs and guide fuzzing.
  • Grammar-Aware Fuzzing: Its grammar-aware trimming strategy operates on AST subtrees, while its mutation strategies modify tokens or replace AST subtrees.

A. Grammar-Aware Trimming Strategy

Superion trims structured test inputs at the AST level, preserving syntax validity while retaining coverage. This enables removal of complete syntactic units that AFL’s byte-chunk trimming cannot reliably prune.

  • AFL’s chunk-based trimming is grammar-blind and can destroy structured inputs, leaving syntax-invalid tests that hinder deeper fuzzing.It removes byte chunks when coverage remains unchanged, without modeling the input grammar.
  • Superion parses each input with the grammar into an AST and attempts to remove subtrees while checking coverage changes.If parsing fails, it falls back to AFL’s trimming; otherwise, it rejects subtree removals that change coverage.
  • A complete JavaScript try-catch statement can be removed without changing coverage, whereas AFL’s built-in strategy can hardly prune such a statement.

B. Grammar-Aware Mutation Strategies

Superion combines enhanced dictionary mutation with AST-based subtree replacement to generate more structurally appropriate mutations. Heuristics bound input, subtree, and mutation-set sizes to control cost.

  • AFL’s fine-grained, grammar-blind mutations often fail syntax parsing, motivating grammar-aware mutation strategies.
  • 1) Enhanced Dictionary-Based Mutation: Enhanced dictionary mutation inserts tokens only at boundaries between non-alphanumeric sequences, avoiding insertions inside alphabetic or numeric tokens.This reduces structure-destroying mutations compared with inserting or overwriting at arbitrary byte positions.
  • 2) Tree-Based Mutation: Tree-based mutation parses target and provider inputs into ASTs, then replaces target subtrees with subtrees collected from both trees.The procedure can generate 100×(100+500) = 60,000 inputs when the target and provider contain 100 and 500 subtrees.
  • 2) Tree-Based Mutation: Inputs are capped at 10,000 bytes, the mutation provider is capped at 10,000 subtrees, and subtrees larger than 200 bytes are excluded.These empirically established heuristics limit memory use and mutation burden.
  • 2) Tree-Based Mutation: In the tree-based example, the subtree for x+2 is replaced by the subtree for Number(x), producing a new test input.

III. EVALUATION

The evaluation measures Superion against AFL across XML and JavaScript programs using bug-finding, coverage, trimming, mutation, and overhead research questions. The setup uses publicly available grammars, diverse engines, and extended fuzzing runs.

  • Superion was implemented by extending AFL and evaluated against AFL on bug-finding capability and code coverage.
  • Target Languages: The study targets XML and JavaScript, whose publicly available grammars represent weakly structured and strongly structured inputs, respectively.XML has eight grammar symbols, while JavaScript has 98.
  • Target Programs: The evaluation uses libplist plus the JavaScript engines WebKit, Jerryscript, and ChakraCore.These programs were selected as security-critical and widely fuzzed.
  • Target Programs: Coverage measurement uses edge coverage for libplist and Jerryscript, but block coverage for WebKit and ChakraCore because of nondeterminism.Nondeterministic code in WebKit and ChakraCore was excluded from instrumentation.
  • Experimental Duration: Fuzzing ran for about three months, exceeding 100 cycles for libplist and Jerryscript but not completing one cycle for WebKit and ChakraCore.
  • Research Questions: The experiments address five questions covering bug finding, code coverage, grammar-aware trimming, grammar-aware mutation, and Superion’s performance overhead.

B. Discovered Bugs and Vulnerabilities (RQ1)

Superion found 31 previously unknown bugs across four target programs, including 21 vulnerabilities with CVE assignments and reported bug-bounty rewards. AFL found only six of these bugs, with especially limited results on JavaScript engines.

  • 31 unique bugs were discovered across libplist, WebKit, Jerryscript, and ChakraCore, including 21 vulnerabilities with 16 assigned CVEs.The discoveries included 11 bugs in libplist, 13 in WebKit, 4 in Jerryscript, and 3 in ChakraCore.
  • 3.2K USD in bug-bounty rewards were received for the discovered bugs.
  • Comparison to AFL: AFL discovered only six of Superion’s 31 bugs and found no other new bugs in the comparison.For XML, AFL found five bugs while Superion found those five plus six more; for JavaScript, AFL found only one bug in Jerryscript.
  • Bug Types: The confirmed bugs included buffer overflows, integer overflows, memory corruption, arbitrary address access, use-after-free, null-pointer dereferences, and assertion failures.Twenty-five of the 31 confirmed bugs had been fixed.

C. Code Coverage (RQ2)

Superion achieved higher line and function coverage than AFL across libplist and three JavaScript engines. The reported gains were 16.7% in line coverage and 8.8% in function coverage.

  • 16.7% higher line coverage was achieved by Superion than AFL overall.Superion reached 68.9%, 78.0%, 88.2% and 76.9% line coverage for libplist, WebKit, Jerryscript and ChakraCore, respectively.
  • Superion further covered 24.6% of the code on average, compared with 7.9% for AFL.The comparison used line coverage across one XML engine and three JavaScript engines.
  • 8.8% higher function coverage was achieved by Superion than AFL overall.Average function coverage increased from 49.1% with AFL to 57.9% with Superion.

D. Effectiveness of Grammar-Aware Trimming (RQ3)

Superion’s tree-based trimming removed fewer bytes than AFL’s built-in trimming but produced substantially more grammar-valid test inputs. This preserved syntax validity while supporting subsequent grammar-aware mutation.

  • 11.7% of libplist XML bytes were trimmed by Superion, compared with 21.7% for AFL.For JavaScript, Superion trimmed 7.6%, 4.7% and 11.3% for WebKit, Jerryscript and ChakraCore, respectively.
  • 100% grammar validity was reached after tree-based trimming for WebKit, Jerryscript and ChakraCore.The corresponding AFL validity ratios were 86.4%, 89.3% and 83.7%.
  • Grammar-aware trimming significantly improved post-trimming grammar validity despite its relatively low trimming ratio.The higher validity ratio facilitated grammar-aware mutation.

E. Effectiveness of Grammar-Aware Mutation (RQ4)

Superion’s grammar-aware mutation strategies increasingly outperformed AFL’s built-in strategies in generating test inputs that triggered new coverage. However, all mutation strategies remained inefficient overall.

  • Superion denotes enhanced dictionary mutations as ui, uo, ai and ao, and tree-based mutation as tree.The labels represent insertion or overwrite using user-supplied or automatically extracted tokens, plus subtree-based mutation.
  • Figure 7 plots processed queue inputs against the number of interesting test inputs produced during WebKit fuzzing.Interesting test inputs are those triggering new coverage; results after mutation strategies become ineffective are omitted.
  • Tree-based mutation and overwrite with user-supplied tokens significantly outperformed other mutation strategies over time.Bit and byte flips led initially, partly because they were applied first and often triggered error-handling paths by damaging structure.
  • Only two of 1000 mutated test inputs triggered new coverage, indicating low efficiency across all mutation strategies.Figure 8 reports the ratio of interesting test inputs to all generated test inputs.
  • The enhanced dictionary-based mutation reduced mutation applications by half while still producing interesting test inputs.Figure 9 compares AFL’s dictionary insertion and overwrite with Superion’s enhanced versions.
  • Superion’s grammar-aware mutation strategies were effective for generating test inputs that triggered new coverage, but their efficiency still needed improvement.This conclusion compares the strategies with AFL’s built-in mutation strategies.

F. Performance Overhead (RQ5)

Superion introduced additional overhead from parsing and tree-based mutation, but the authors judged that overhead acceptable relative to the reported coverage and bug-finding improvements. The case study also shows tree-based mutation producing a vulnerability-triggering input through repeated evolution.

  • Performance Overhead: 0.63 ms for mutation and 0.39 ms for execution were measured on average for the small project libplist.Table VI reports overhead from tree-based mutation and corresponding execution overhead.
  • Performance Overhead: Superion introduced additional overhead through its grammar-aware tree-based mutation strategy.The authors considered this overhead acceptable given the improved bug-finding capability and code coverage.
  • Case Study: CVE-2017-7xxx resulted from WebKit using indices from an old input string to create a substring of a new input string.The vulnerability involved setInput failing to reify leftContext and rightContext before later use.

H. Discussion

Superion is evaluated against related fuzzing approaches, but the evaluation omits some standardized datasets and grammar-aware mutation baselines. Its main scope boundary is the need for publicly documented grammars.

  • Discussion: Superion was not evaluated on standardized datasets such as LAVA and CGC because many programs there process unstructured inputs or lack suitable grammars.The authors instead evaluated four real-life programs and characterize those results as representative.
  • Discussion: The evaluation did not empirically compare Superion with LangFuzz and IFuzzer, because LangFuzz was unavailable and IFuzzer lacked sufficient setup documentation.The authors compared Superion with jsfunfuzz instead.
  • Discussion: Superion requires a grammar, limiting applicability to publicly documented formats and potentially excluding proprietary grammars or undocumented extensions.The authors identify automatic grammar inference as a planned way to widen applicability.
  • Grammar-Based Mutation: Superion differs from LangFuzz and IFuzzer by bringing grammar-awareness into coverage-based greybox fuzzing rather than using blackbox fragment recombination.LangFuzz and IFuzzer extract and replace same-type code fragments from pools or through evolutionary recomposition.
  • Grammar-Based Generation: Unlike generation-based fuzzers such as Skyfire and TreeFuzz, Superion performs grammar-aware mutation and incrementally reuses interesting behaviors from prior test inputs.This distinction is tied to Superion's use of coverage feedback.
  • Fuzzing Boosting: Superion's efficiency-oriented fuzzing enhancements are orthogonal to techniques for seed selection, scheduling, parameter tuning, directed fuzzing, and operating primitives.These techniques address fuzzing efficiency rather than grammar-aware input handling.

V. CONCLUSIONS

Superion applies grammar-aware trimming and mutation to structured-input programs while preserving input validity. Experiments on XML and JavaScript engines showed improved coverage and bug-finding over AFL, including 31 new bugs and 21 new vulnerabilities.

  • V. CONCLUSIONS: Superion combines grammar-aware trimming with two grammar-aware mutation strategies for programs processing structured inputs.The approach is designed to keep input structure valid while carrying exploration into width and depth.
  • V. CONCLUSIONS: Superion improved code coverage and bug-finding capability over AFL in experiments on several XML and JavaScript engines.The conclusion reports results across multiple structured-input engines.
  • V. CONCLUSIONS: 31 new bugs were found, including 21 new vulnerabilities, with 16 CVEs assigned.These are the principal bug-finding outcomes reported in the conclusion.
Loading 1812.01197v3…