Detection of Intrusions and Malware, and Vulnerability Assessment

Leyla Bilge, Lorenzo Cavallaro, Giancarlo Pellegrino, Nuno NevesLecture Notes in Computer Science 2021 · DOI · arXiv · OpenAlex

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.

Table 1: Sivo's parameterized procedures and their variations.

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.

Algorithm 1: The SIVO main loop, including the coverage flushing logic.

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

BibTeX
@inproceedings{bilge2021detection,
  author = {Leyla Bilge and Lorenzo Cavallaro and Giancarlo Pellegrino and Nuno Neves},
  title = {{Detection of Intrusions and Malware, and Vulnerability Assessment}},
  booktitle = {Lecture Notes in Computer Science},
  year = {2021},
  doi = {10.1007/978-3-030-80825-9},
}

Loading related content...

Figure