Fuzzing: on the exponential cost of vulnerability discovery

Marcel Böhme, Brandon Falk

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

3 Citations (Scopus)

Abstract

We present counterintuitive results for the scalability of fuzzing. Given the same non-deterministic fuzzer, finding the same bugs linearly faster requires linearly more machines. For instance, with twice the machines, we can find all known bugs in half the time. Yet, finding linearly more bugs in the same time requires exponentially more machines. For instance, for every new bug we want to find in 24 hours, we might need twice more machines. Similarly for coverage. With exponentially more machines, we can cover the same code exponentially faster, but uncovered code only linearly faster. In other words, re-discovering the same vulnerabilities is cheap but finding new vulnerabilities is expensive. This holds even under the simplifying assumption of no parallelization overhead. We derive these observations from over four CPU years worth of fuzzing campaigns involving almost three hundred open source programs, two state-of-the-art greybox fuzzers, four measures of code coverage, and two measures of vulnerability discovery. We provide a probabilistic analysis and conduct simulation experiments to explain this phenomenon.

Original languageEnglish
Title of host publicationESEC/FSE'20 - Proceedings of the 28th ACM Joint Meeting European Software Engineering Conference and Symposium on the Foundations of Software Engineering
EditorsPrem Devanbu, Myra Cohen, Thomas Zimmermann
Place of PublicationNew York NY USA
PublisherAssociation for Computing Machinery (ACM)
Pages713-724
Number of pages12
ISBN (Electronic)9781450370431
DOIs
Publication statusPublished - 2020
EventJoint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering 2020 - Virtual, United States of America
Duration: 8 Nov 202013 Nov 2020
Conference number: 28th
https://dl.acm.org/doi/proceedings/10.1145/3368089 (Proceedings)
https://2020.esec-fse.org (Website)

Conference

ConferenceJoint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering 2020
Abbreviated titleESEC/FSE 2020
CountryUnited States of America
CityVirtual
Period8/11/2013/11/20
Internet address

Keywords

  • Efficiency
  • Fuzzing
  • Scalability
  • Software testing

Cite this