MendelFuzz: The Return of the Deterministic Stage

Can a fuzzer cover more code with minimal corruption of the initial seed? Before a seed is fuzzed, the early greybox fuzzers first systematically enumerated slightly corrupted inputs by applying every mutation operator to every part of the seed, once per generated input. The hope of this so-called "deterministic" stage was that simple changes to the seed would be less likely to break the complex file format; the resulting inputs would find bugs in the program logic well beyond the program's parser. However, when experiments showed that disabling the deterministic stage achieves more coverage, i.e., applying multiple mutation operators at the same time to a single input, most fuzzers disabled the deterministic stage by default.

Instead of ignoring the deterministic stage, we analyze its potential and substantially improve deterministic exploration. Our deterministic stage is now the default in AFL++, reverting the earlier decision of dropping deterministic exploration. We start by investigating the overhead and the contribution of the deterministic stage to the discovery of coverage-increasing inputs. While the sheer number of generated inputs explains the overhead, we find that only a few critical seeds (20%), and only a few critical bytes in a seed (0.5%) are responsible for the vast majority of the coverage-increasing inputs (83% and 84%, respectively). Hence, we develop an efficient technique, called MendelFuzz, to identify these critical seeds / bytes so as to prune a large number of unnecessary inputs. MendelFuzz retains the benefits of the classic deterministic stage by only enumerating a tiny part of the total deterministic state space.

We evaluate MendelFuzz implementation on two benchmarking frameworks, FuzzBench and Magma. Our evaluation shows that MendelFuzz outperforms state-of-the-art fuzzers with and without the (old) deterministic stage enabled, both in terms of coverage and bug finding. MendelFuzz also discovered 8 new CVEs on exhaustively fuzzed security-critical applications. Finally, MendelFuzz has been independently evaluated and integrated into AFL++ as default option.