Coverage-based Greybox Fuzzing as Markov Chain
- 24 October 2016
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1032-1043
- https://doi.org/10.1145/2976749.2978428
Abstract
Coverage-based Greybox Fuzzing (CGF) is a random testing approach that requires no program analysis. A new test is generated by slightly mutating a seed input. If the test exercises a new and interesting path, it is added to the set of seeds; otherwise, it is discarded. We observe that most tests exercise the same few \"high-frequency\" paths and develop strategies to explore significantly more paths with the same number of tests by gravitating towards low-frequency paths. We explain the challenges and opportunities of CGF using a Markov chain model which specifies the probability that fuzzing the seed that exercises path i generates an input that exercises path j. Each state (i.e., seed) has an energy that specifies the number of inputs to be generated from that seed. We show that CGF is considerably more efficient if energy is inversely proportional to the density of the stationary distribution and increases monotonically every time that seed is chosen. Energy is controlled with a power schedule. We implemented the exponential schedule by extending AFL. In 24 hours, AFLFAST exposes 3 previously unreported CVEs that are not exposed by AFL and exposes 6 previously unreported CVEs 7x faster than AFL. AFLFAST produces at least an order of magnitude more unique crashes than AFL.Keywords
Funding Information
- National Research Foundation, Prime Minister's Office, Singapore (NRF2014NCR-NCR001-21)
This publication has 16 references indexed in Scilit:
- Model-based whitebox fuzzing for program binariesPublished by Association for Computing Machinery (ACM) ,2016
- Coverage-directed differential testing of JVM implementationsPublished by Association for Computing Machinery (ACM) ,2016
- A Probabilistic Analysis of the Efficiency of Automated Software TestingIEEE Transactions on Software Engineering, 2015
- Program-Adaptive Mutational FuzzingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2015
- Regression tests to expose change interaction errorsPublished by Association for Computing Machinery (ACM) ,2013
- Scheduling black-box mutational fuzzingPublished by Association for Computing Machinery (ACM) ,2013
- SAGE: Whitebox Fuzzing for Security TestingQueue, 2012
- The anatomy of a large-scale hypertextual Web search engineComputer Networks and ISDN Systems, 1998
- An empirical study of the reliability of UNIX utilitiesCommunications of the ACM, 1990
- Optimization by Simulated AnnealingScience, 1983