It’s Not You, It’s Me: Reevaluating the Relationship between Concolic Execution and Fuzzing

Concolic execution is a well-established program analysis technique for discovering vulnerabilities in software systems. However, recent concolic executors have been primarily designed and optimized for hybrid fuzzing scenarios, where they complement fuzzers by solving constraints to reach program paths with complex conditions. This scenario has led to architectural decisions that prioritize integration with fuzzers over the inherent strengths of concolic execution itself, namely systematic path exploration in the presence of complex constraints. We argue that the design choices borrowed from fuzzing, such as shared coverage metrics and corpus management strategies, may actually limit the effectiveness of concolic execution when used independently.In this paper, we develop SYMCTS, a concolic executor that breaks from the hybrid fuzzing paradigm to revisit the potential of modern standalone concolic execution design. SYMCTS introduces a novel coverage metric, edge-dependence coverage, and scheduling algorithm that prioritizes under-explored regions of code. These design choices enable SYMCTS to efficiently explore complex program behaviors independently without relying on an accompanying fuzzer.We evaluate SYMCTS against state-of-the-art concolic executors on well-known benchmark targets from the FuzzBench and Unibench benchmarks. Our results show that SYMCTS can significantly improve coverage when using our coverage metric compared to existing concolic execution approaches and our scheduler improves coverage reached when using an empty input corpus. Notably, standalone concolic execution using SYMCTS performs on-par with or even outperforms established greybox and hybrid fuzzers on a few targets, motivating further research into the capabilities of concolic execution itself.