Please note: This master’s thesis presentation will take place in TBD.
Zekun Wang, Master’s candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Meng Xu
Coverage-guided fuzzing is one of the most effective approaches to automated software testing, yet its performance depends critically on the coverage metric that guides input generation. It is widely assumed that finer metrics — especially path coverage, which captures complete control-flow information — should lead to more effective fuzzing. However, practical realizations of path coverage have been limited to restricted forms due to path explosion.
In this work, we introduce a path reduction algorithm that bounds loop iterations in execution paths, enabling a practical form of path coverage that preserves essential control-flow information. Despite this advancement, we find that path coverage performs no better than existing metrics such as edge coverage. To understand this phenomenon, we establish the concept of coverage complexity — a quantitative measure of the granularity of coverage metrics. Analogous to complexity and the Big-O notation in algorithm analysis, coverage complexity classifies metrics into asymptotic complexity classes such as linear, polynomial, and exponential. This framework provides a structured overview of the entire space of coverage metrics, and guides the design of new coverage metrics.
Our complexity analysis and empirical evaluation on the MAGMA and FuzzBench benchmarks reveals a consistent pattern: metrics within the same complexity class tend to exhibit similar fuzzing performance, where linear-complexity metrics consistently outperform more complex metrics. This suggests a simple but powerful principle: when designing a new coverage metric, the first step is to determine its complexity class, which serves as an early predictor of its potential performance. Since higher-complexity metrics consistently underperform, our results imply that the family of linear metrics may already represent the optimal frontier of coverage-guided fuzzing, offering — for the first time — a structured overview of the landscape of coverage metrics.