QSYM: a practical concolic execution engine tailored for hybrid fuzzing

TLDR

Hybrid fuzzing combines fuzzing and concolic execution to overcome their individual limitations, proving effective on synthetic benchmarks but still scaling poorly for complex real‑world software. This work introduces QSYM, a fast concolic execution engine designed to enable scalable hybrid fuzzing. QSYM tightly couples symbolic emulation with native execution through dynamic binary translation, enabling fine‑grained instruction‑level symbolic analysis, relaxing strict soundness constraints, and leveraging a faster fuzzer for validation, optimistic constraint solving, and basic‑block pruning. Evaluation shows QSYM discovers 14× more bugs than VUzzer on LAVA‑M, outperforms Driller on 104 of 126 binaries, and uncovers 13 previously unknown security bugs in eight real‑world programs such as Dropbox Lepton, ffmpeg, and OpenJPEG.

Abstract

Recently, hybrid fuzzing has been proposed to address the limitations of fuzzing and concolic execution by combining both approaches. The hybrid approach has shown its effectiveness in various synthetic benchmarks such as DARPA Cyber Grand Challenge (CGC) binaries, but it still suffers from scaling to find bugs in complex, realworld software. We observed that the performance bottleneck of the existing concolic executor is the main limiting factor for its adoption beyond a small-scale study. To overcome this problem, we design a fast concolic execution engine, called QSYM, to support hybrid fuzzing. The key idea is to tightly integrate the symbolic emulation with the native execution using dynamic binary translation, making it possible to implement more fine-grained, so faster, instruction-level symbolic emulation. Additionally, QSYM loosens the strict soundness requirements of conventional concolic executors for better performance, yet takes advantage of a faster fuzzer for validation, providing unprecedented opportunities for performance optimizations, e.g., optimistically solving constraints and pruning uninteresting basic blocks. Our evaluation shows that QSYM does not just outperform state-of-the-art fuzzers (i.e., found 14× more bugs than VUzzer in the LAVA-M dataset, and outperformed Driller in 104 binaries out of 126), but also found 13 previously unknown security bugs in eight real-world programs like Dropbox Lepton, ffmpeg, and OpenJPEG, which have already been intensively tested by the state-of-the-art fuzzers, AFL and OSS-Fuzz.