Fuzzing: On the Exponential Cost of Vulnerability Discovery
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.
Wed 16 NovDisplayed time zone: Beijing, Chongqing, Hong Kong, Urumqi change
11:00 - 12:30
|Model-Based Exploration of the Frontier of Behaviours for Deep Learning System Testing|
|Baital: An Adaptive Weighted Sampling Approach for Improved t-wise Coverage|
|Fuzzing: On the Exponential Cost of Vulnerability Discovery|
ESEC/FSE 2020DOI Pre-print
|Boosting Fuzzer Efficiency: An Information Theoretic Perspective|
Marcel Böhme MPI-SP, Germany and Monash University, Australia, Valentin Manès KAIST, South Korea, Sang Kil Cha KAIST, South KoreaDOI Pre-print