Abstract
Fuzzing is a critical technique for identifying software vulnerabilities, yet traditional grey-box fuzzers often encounter performance plateaus due to rigid mutation strategies and inefficient taint analysis. This paper introduces Sivo, a redesigned grey-box fuzzer that approaches software testing as a dynamic optimization problem. By utilizing logarithmic-time taint inference, lightweight inequality solving, and a Multi-Armed Bandit (MAB) framework for strategy selection, Sivo achieves significant improvements in code coverage and vulnerability discovery.
Introduction
Modern software security relies heavily on fuzzing—the automated process of providing mutated inputs to a program to trigger unexpected behaviors. Despite its success, standard grey-box fuzzers like AFL face two primary challenges: the "one-size-fits-all" trap of hard-coded mutation strategies and the efficiency bottlenecks of traditional taint analysis. Sivo addresses these by adapting its strategies in real-time and employing high-speed, approximate analysis techniques.
Methodology
Sivo's architecture is built upon four key innovations designed to maximize execution speed and coverage depth.
Dynamic Strategy Optimization
Unlike traditional fuzzers, Sivo parameterizes every aspect of the fuzzing process, from seed selection to mutation types. It employs a Multi-Armed Bandit (MAB) engine to dynamically prioritize strategies that yield the best results for a specific target program.
TaintFAST: Efficient Taint Inference
To overcome the $O(n)$ complexity of standard taint analysis, Sivo introduces TaintFAST. By using probabilistic group testing, it reduces the complexity of inferring input-to-branch dependencies to $O(\log n)$. This enables Sivo to handle large input files without the prohibitive overhead of byte-by-byte testing.
Lightweight Symbolic Reasoning
Sivo bypasses heavy SMT solvers by using a custom "system of intervals" to solve simple integer inequalities. This allows the fuzzer to quickly identify inputs that satisfy branch conditions, facilitating the exploration of deeper code paths.
Precise Coverage Tracking and Flushing
To mitigate hash collisions and "logarithmic bucket" blindness—where subtle but important state changes are ignored—Sivo uses multiple labels per code block and a periodic coverage "flushing" mechanism to find edge cases that other tools ignore.
Experimental Evaluation
Sivo was benchmarked against 11 state-of-the-art fuzzers across 27 real-world programs, including binutils, tcpdump, and libjpeg.
Key Results
- Code Coverage: Sivo outperformed all competitors in 25 of 27 benchmarks, showing a 20% average increase over MOpt and 180% over AFL.
- Vulnerability Discovery: Sivo identified 31 unique vulnerabilities that were missed by all other tested fuzzers.
- Optimization Impact: Analysis revealed that the MAB-based optimization engine was the single most impactful component, demonstrating the value of adaptive strategy selection.
Conclusion
Sivo demonstrates that a refined, optimization-first approach to grey-box fuzzing can significantly enhance both code coverage and bug discovery. While its approximate methods trade some precision for speed, the empirical results suggest this is a highly effective trade-off for practical vulnerability assessment. Future work could involve expanding the interval solver to handle more complex data types or integrating Sivo's MAB engine into other security tools.
Summary updated