NAUTILUS: Fishing for Deep Bugs with Grammars

By Cornelius Aschermann, Tommaso Frassetto, Thorsten Holz, Patrick Jauernig, Ahmad-Reza Sadeghi, D. Teuchert. Network and Distributed System Security Symposium, 2019

311 citations recorded by the source corpus.

Fuzz testing is a well-known method for efficiently identifying bugs in programs. Unfortunately, when programs that require highly-structured inputs such as interpreters are fuzzed, many fuzzing methods struggle to pass the syntax checks: interpreters often process inputs in multiple stages, first syntactic and then semantic correctness is checked. Only if both checks are passed, the interpreted code gets executed. This prevents fuzzers from executing “deeper” — and hence potentially more interesting — code. Typically, two valid inputs that lead to the execution of different features in the target program require too many mutations for simple mutation-based fuzzers to discover: making small changes like bit flips usually only leads to the execution of error paths in the parsing engine. So-called grammar fuzzers are able to pass the syntax checks by using ContextFree Grammars. Feedback can significantly increase the efficiency of fuzzing engines and is commonly used in state-of-the-art mutational fuzzers which do not use grammars. Yet, current grammar fuzzers do not make use of code coverage, i.e., they do not know whether any input triggers new functionality. In this paper, we propose NAUTILUS, a method to efficiently fuzz programs that require highly-structured inputs by combining the use of grammars with the use of code coverage feedback. This allows us to recombine aspects of interesting inputs, and to increase the probability that any generated input will be syntactically and semantically correct. We implemented a proofof-concept fuzzer that we tested on multiple targets, including ChakraCore (the JavaScript engine of Microsoft Edge), PHP, mruby, and Lua. NAUTILUS identified multiple bugs in all of the targets: Seven in mruby, three in PHP, two in ChakraCore, and one in Lua. Reporting these bugs was awarded with a sum of 2600 USD and 6 CVEs were assigned. Our experiments show that combining context-free grammars and feedback-driven fuzzing significantly outperforms state-of-the-art approaches like AFL by an order of magnitude and grammar fuzzers by more than a factor of two when measuring code coverage.

Subfields: Information Systems, Software

View Paper: https://www.semanticscholar.org/paper/d610be355072e52b72cddd9f8e2f9f188007d550

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Information Systems

In Software

Citations in the corpus

Fuzzing: A Survey for Roadmap (2022, methodology): “Then, both NAUTILUS and Superion use code coverage to optimize the mutation process.”
Fuzz4ALL: Universal Fuzzing with Large Language Models (2023, background): “In addition to basic mutations, researchers have developed complex transformations targeted at ensuring type consistency [11, 59], adding historical bug-triggering code snippets [31, 86], and coverage feed-back [3, 21, 46].”
The Art, Science, and Engineering of Fuzzing: A Survey (2018, methodology): “FairFuzz [141] H# ✓ ✓ ✓† H#† ✓ ✓ ✓ go-fuzz [225] H# ✓ ✓ ✓ ✓ ✓ ✓ H# ✓ Hawkeye [56] H# ✓ ✓ ✓ ✓ H# ✓ ✓ honggfuzz [213] H# ✓ ✓ ✓ kAFL [191] H# ✓ ✓ LibFuzzer [9] H# ✓ ✓ ✓ ✓ ✓ ✓ MagicFuzzer [50] H# ✓ ✓ ✓ Nautilus [25] H# ✓ ✓ ✓ H# ✓ ✓ RaceFuzzer [197] H# ✓ ✓ ✓ RedQueen [26] H# ✓ ✓ H# ✓”
AFLNET: A Greybox Fuzzer for Network Protocols (2020, background): “Most recently, the community explored the opportunities of making greybox fuzzing aware of the input structure [7], [16]–[18].”