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 \emph{same bugs} linearly faster requires linearly more machines. For instance, with twice the machines, we can find \emph{all known bugs} in half the time. Yet, finding linearly \emph{more bugs} in the same time requires exponentially more machines. For instance, for every \emph{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 \emph{same code} exponentially faster, but \emph{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 \emph{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.
Tue 10 NovDisplayed time zone: (UTC) Coordinated Universal Time change
08:00 - 08:30 | |||
08:00 2mTalk | Boosting Fuzzer Efficiency: An Information Theoretic PerspectiveACM SIGSOFT Distinguished Paper Award Research Papers Marcel Böhme Monash University, Australia, Valentin Manès KAIST, South Korea, Sang Kil Cha KAIST, South Korea DOI | ||
08:03 1mTalk | CrFuzz: Fuzzing Multi-purpose Programs through Input Validation Research Papers Suhwan Song Seoul National University, South Korea, Chengyu Song University of California at Riverside, USA, Yeongjin Jang Oregon State University, USA, Byoungyoung Lee Seoul National University, South Korea DOI | ||
08:05 1mTalk | Detecting Critical Bugs in SMT Solvers Using Blackbox Mutational Fuzzing Research Papers Muhammad Numair Mansur MPI-SWS, Germany, Maria Christakis MPI-SWS, Valentin Wüstholz ConsenSys, Fuyuan Zhang MPI-SWS, Germany DOI Pre-print | ||
08:07 1mTalk | Fuzzing: On the Exponential Cost of Vulnerability Discovery Research Papers DOI | ||
08:09 1mTalk | Harvey: A Greybox Fuzzer for Smart Contracts Industry Papers DOI Pre-print | ||
08:11 1mTalk | Intelligent REST API Data Fuzzing Research Papers Patrice Godefroid Microsoft Research, USA, Bo-Yuan Huang Princeton University, USA, Marina Polishchuk Microsoft Research, USA DOI | ||
08:13 1mTalk | MTFuzz: Fuzzing with a Multi-task Neural Network Research Papers Dongdong She Columbia University, USA, Rahul Krishna Columbia University, USA, Lu Yan Shanghai Jiao Tong University, China, Suman Jana Columbia University, USA, Baishakhi Ray Columbia University, USA DOI Pre-print | ||
08:15 15mTalk | Conversations on Fuzzing Research Papers Dongdong She Columbia University, USA, Muhammad Numair Mansur MPI-SWS, Germany, Marcel Böhme Monash University, Australia, Suhwan Song Seoul National University, South Korea, Valentin Wüstholz ConsenSys, M: Mike Papadakis University of Luxembourg, Luxembourg | ||