Coverage-based Greybox Fuzzing as Markov chain

Marcel Böhme, Van-Thuan Pham, Abhik Roychoudhury

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

334 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationCCS' 2016
Subtitle of host publicationProceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security
EditorsShai Halevi, Christopher Kruegel, Andrew Myers
Place of PublicationNew York NY USA
PublisherAssociation for Computing Machinery (ACM)
Pages1032-1043
Number of pages12
ISBN (Print)9781450341394
DOIs
Publication statusPublished - 24 Oct 2016
Externally publishedYes
EventACM Conference on Computer and Communications Security 2016 - Vienna, Austria
Duration: 24 Oct 201628 Oct 2016
Conference number: 23rd
https://www.sigsac.org/ccs/CCS2016/

Conference

ConferenceACM Conference on Computer and Communications Security 2016
Abbreviated titleCCS 2016
Country/TerritoryAustria
CityVienna
Period24/10/1628/10/16
Internet address

Cite this