Tephra: Principled Discovery of Fuzzer Limitations

Fuzz testing has proven effective in discovering nontrivial bugs in complex, real-world systems, with coverage-guided greybox fuzzing being a key contributor to this success. Existing research has largely focused on developing new heuristics to increase code coverage, and current benchmarks measure coverage increase or the number of bugs found. However, there is a notable lack of investigation into programming constructs that systematically hinder or prevent fuzzing heuristics from achieving coverage, commonly referred to as "obstacles" or "roadblocks".This work makes two key contributions. First, we introduce Tephra, a principled methodology that uses semantics-guided synthesis to generate bug-free programs with diverse obstacles and statistically evaluate a fuzzer’s ability to overcome them. Second, we implement Tephra-C/C++, a concrete instantiation, and generate 26 different C and C++ obstacles. We use these to empirically evaluate the bypassing abilities of 31 contemporary fuzzers, consuming 37.4 CPU years.Our analysis reveals limitations in current fuzzing heuristics and uncovers bugs in the fuzzers themselves, including AFL++. All evaluated fuzzers struggle with certain obstacles, such as floating-point conditionals and character strings. We also find that signed integers are more challenging than unsigned, and some heuristics are overtuned for 32- and 64-bit types, neglecting 8- and 16-bit integers. Overall, we observe a single difficult semantic construct can significantly degrade a fuzzer’s overall performance. Our findings demonstrate Tephra’s effectiveness and highlight avenues for future research in fuzzing techniques.