Cornelius Aschermann (Ruhr-Universität Bochum), Tommaso Frassetto (Technische Universität Darmstadt), Thorsten Holz (Ruhr-Universität Bochum), Patrick Jauernig (Technische Universität Darmstadt), Ahmad-Reza Sadeghi (Technische Universität Darmstadt), Daniel Teuchert (Ruhr-Universität Bochum)

Fuzzing is a well-known method for efficiently identifying bugs in programs.
Unfortunately, when fuzzing targets that require highly-structured inputs such as interpreters, many fuzzing methods struggle to pass the syntax checks.
More specifically, interpreters often process inputs in multiple stages: first syntactic, then semantic correctness is checked. Only if these 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 application 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 Context-Free Grammars.
Using feedback can significantly increase the efficiency of fuzzing engines.
Hence, it is commonly used in state-of-the-art mutational fuzzers that do not use grammars.
Yet, grammar fuzzers do not make use of code coverage, i.e., they do not know whether any input triggers new functionality or not.

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 that were learned individually, and to dramatically increase the probability that any generated input will be accepted by the parser.
We implemented a proof-of-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 American Fuzzy Lop (AFL) by an order of magnitude and grammar fuzzers by more than a factor of two when measuring code coverage.

View More Papers

Life after Speech Recognition: Fuzzing Semantic Misinterpretation for Voice...

Yangyong Zhang (Texas A&M University), Lei Xu (Texas A&M University), Abner Mendoza (Texas A&M University), Guangliang Yang (Texas A&M University), Phakpoom Chinprutthiwong (Texas A&M University), Guofei Gu (Texas A&M University)

Read More

CRCount: Pointer Invalidation with Reference Counting to Mitigate Use-after-free...

Jangseop Shin (Seoul National University and Inter-University Semiconductor Research Center), Donghyun Kwon (Seoul National University and Inter-University Semiconductor Research Center), Jiwon Seo (Seoul National University and Inter-University Semiconductor Research Center), Yeongpil Cho (Soongsil University), Yunheung Paek (Seoul National University and Inter-University Semiconductor Research Center)

Read More

PeriScope: An Effective Probing and Fuzzing Framework for the...

Dokyung Song (University of California, Irvine), Felicitas Hetzelt (Technical University of Berlin), Dipanjan Das (University of California, Santa Barbara), Chad Spensky (University of California, Santa Barbara), Yeoul Na (University of California, Irvine), Stijn Volckaert (University of California, Irvine and KU Leuven), Giovanni Vigna (University of California, Santa Barbara), Christopher Kruegel (University of California, Santa Barbara),…

Read More

Giving State to the Stateless: Augmenting Trustworthy Computation with...

Gabriel Kaptchuk (Johns Hopkins University), Matthew Green (Johns Hopkins University), Ian Miers (Cornell Tech)

Read More