一句话：揭示非确定性 fuzzer 的可扩展性：复现已知漏洞可线性加速，发现新漏洞需指数级机器。
本文研究 fuzzing 的可扩展性，并给出反直觉结论。对于同一个非确定性 fuzzer，若要线性更快地找到同一批漏洞，只需线性增加机器：例如机器数翻倍，找到全部已知漏洞的时间减半。但若要在相同时间内找到线性更多的新漏洞，则需要指数级更多的机器：例如每多找一个新的漏洞并仍限定在 24 小时内，可能就需要机器数翻倍。覆盖率也类似：用指数级更多机器可以指数级更快地覆盖同一段代码，但覆盖未覆盖代码只能线性加速。换言之，重新发现相同漏洞很便宜，而发现新漏洞非常昂贵。该结论在忽略并行化开销的简化假设下依然成立。
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.
DOI 原文 ·
@inproceedings{paperbot5780,
title = {Fuzzing: on the exponential cost of vulnerability discovery},
author = {Marcel Böhme and Brandon Falk},
booktitle = {FSE},
year = {2020},
doi = {10.1145/3368089.3409729}
}