Matryoshka
Authors:
Open Access
- 6 November 2019
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 499-513
Abstract
Greybox fuzzing has made impressive progress in recent years, evolving from heuristics-based random mutation to approaches for solving individual branch constraints. However, they have difficulty solving path constraints that involve deeply nested conditional statements, which are common in image and video decoders, network packet analyzers, and checksum tools. We propose an approach for addressing this problem. First, we identify all the control flow-dependent conditional statements of the target conditional statement. Next, we select the taint flow-dependent conditional statements. Finally, we use three strategies to find an input that satisfies all conditional statements simultaneously. We implemented this approach in a tool called Matryoshka and compared its effectiveness on 13 open source programs against other state-of-the-art fuzzers. Matryoshka has significantly higher cumulative line and branch coverage than AFL, QSYM, and Angora. We manually classified the crashes found by Matryoshka into 41 unique new bugs and obtained 12 CVEs. Our evaluation also uncovered the key technique contributing to Matryoshka's impressive performance: it collects only the nesting constraints that may cause the target conditional statement unreachable, which greatly simplifies the path constraints that it has to solve.Keywords
Funding Information
- National Science Foundation (1801751)
- ARL Cyber Security CRA (W911NF-132-0045)
This publication has 16 references indexed in Scilit:
- Directed Greybox Fuzzing2017
- Steelix: program-state based binary fuzzing2017
- VUzzer: Application-aware Evolutionary Fuzzing2017
- LAVA: Large-Scale Automated Vulnerability Addition2016
- SOK: (State of) The Art of War: Offensive Techniques in Binary Analysis2016
- Driller: Augmenting Fuzzing Through Selective Symbolic Execution2016
- Program-Adaptive Mutational Fuzzing2015
- Symbolic execution for software testingCommunications of the ACM, 2013
- A Taint Based Approach for Smart Fuzzing2012
- LLVM: A compilation framework for lifelong program analysis & transformation2004