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.
|Title of host publication||RAID 2021: 24th International Symposium on Research in Attacks, Intrusions and Defenses|
|Subtitle of host publication||Proceedings|
|Publisher||Association for Computing Machinery|
|Number of pages||16|
|Publication status||Published - Oct 2021|
|Event||24th International Symposium on Research in Attacks, Intrusions and Defenses, RAID 2021 - Virtual, Online, Spain|
Duration: 6 Oct 2021 → 8 Oct 2021
|Name||ACM International Conference Proceeding Series|
|Conference||24th International Symposium on Research in Attacks, Intrusions and Defenses, RAID 2021|
|Period||6/10/21 → 8/10/21|
Bibliographical noteFunding 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.
© 2021 ACM.
- concolic execution
- hybrid fuzzing
- taint analysis