LeanSym: Efficient hybrid fuzzing through conservative constraint debloating

Xianya Mi, Sanjay Rawat, Cristiano Giuffrida, Herbert Bos

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

161 Downloads (Pure)


To improve code coverage and flip complex program branches, hybrid fuzzers couple fuzzing with concolic execution. Despite its benefits, this strategy inherits the inherent slowness and memory bloat of concolic execution, due to path explosion and constraint solving. While path explosion has received much attention, constraint bloat (having to solve complex and unnecessary constraints) is much less studied. In this paper, we present LeanSym (LSym), an efficient hybrid fuzzer. LSym focuses on optimizing the core concolic component of hybrid fuzzing by conservatively eliminating constraint bloat without sacrificing concolic execution soundness. The key idea is to partially symbolize the input and the program in order to remove unnecessary constraints accumulated during execution and significantly speed up the fuzzing process. In particular, we use taint analysis to identify the bytes that may influence the branches that we want to flip and symbolize only those bytes to minimize the constraints to collect. Furthermore, we eliminate non-trivial constraints introduced by environment modelling for system I/O. This is done by targeting the concolic analysis solely to library function-level tracing. We show this simple approach is effective and can be implemented in a modular fashion on top of off-the-shelf binary analysis tools. In particular, with only 1k LOC to implement simple branch/seed selection policies for hybrid fuzzing on top of unmodified Triton, libdft, and AFL, LSym outperforms state-of-the-art hybrid fuzzers with much less memory bloat, including those with advanced branch/seed selection policies or heavily optimized concolic execution engines such as QSYM and derivatives. On average, LSym outperforms QSYM by 7.61% in coverage, while finding bugs 4.79x faster in 18 applications of Google Fuzzer Test Suite. In real-world application testing, LSym reported 17 new bugs in 5 applications.

Original languageEnglish
Title of host publicationRAID 2021
Subtitle of host publication24th International Symposium on Research in Attacks, Intrusions and Defenses [Proceedings]
PublisherAssociation for Computing Machinery
Number of pages16
ISBN (Electronic)9781450390583
Publication statusPublished - Oct 2021
Event24th International Symposium on Research in Attacks, Intrusions and Defenses, RAID 2021 - Virtual, Online, Spain
Duration: 6 Oct 20218 Oct 2021

Publication series

NameACM International Conference Proceeding Series


Conference24th International Symposium on Research in Attacks, Intrusions and Defenses, RAID 2021
CityVirtual, Online

Bibliographical note

Funding Information:
We thank our shepherd, Nathan Burow, and the anonymous reviewers for their feedback. This work was supported by the Netherlands Organisation for Scientific Research through grants NWO “TROPICS” (628.001.030), “INTERSECT”, and “Theseus” and by the EKZ through grant “Memo” . Any opinions, findings, and conclusions or recommendations expressed in this paper are those of the authors and do not necessarily reflect the views of any of the sponsors.

Publisher Copyright:
© 2021 ACM.


  • concolic execution
  • hybrid fuzzing
  • taint analysis


Dive into the research topics of 'LeanSym: Efficient hybrid fuzzing through conservative constraint debloating'. Together they form a unique fingerprint.

Cite this