Taming the Hydra: Targeted Control-Flow Transformations for Dynamic Symbolic Execution
Open Access
- 10 April 2026
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 10 (OOPSLA1) , 59-85
Abstract
Dynamic Symbolic Execution (DSE) suffers from the path explosion problem when the target program has many conditional branches. The classical approach for managing the path explosion problem is dynamic state merging. Dynamic state merging combines similar symbolic program states to avoid the exponential growth in the number of states during DSE. However, state merging still requires solver invocations at each program branch, even when both paths of the branch are feasible. Moreover, the best path search strategy for DSE may not create the best state merging opportunities. Some drawbacks of state merging can be mitigated by compile-time state merging (i.e., branch elimination by converting control-flow into dataflow). In this paper, we propose a non-semantics-preserving but failure-preserving compiler transformation for removing expensive symbolic branches in a program to improve the scalability of DSE. We have developed a framework for detecting spurious bugs that our transformation can insert. Finally, we show that our transformation can significantly improve the performance of DSE on various benchmark programs and help improve the performance of coverage and bug discovery of large real-world programs.Keywords
All Related Versions
Funding Information
- National Science Foundation (CCF-2216987)
- National Science Foundation (CCF-1919197)
- National Science Foundation (CCF-1908504)
This publication has 30 references indexed in Scilit:
- DARM: Control-Flow Melding for SIMT Thread Divergence Reduction2022
- T-Fuzz: Fuzzing by Program Transformation2018
- Non-Semantics-Preserving Transformations for Higher-Coverage Test Generation Using Symbolic Execution2017
- Postconditioned Symbolic Execution2015
- Improving Performance of OpenCL on CPUs2012
- Divergence Analysis and Optimizations2011
- Z3: An Efficient SMT Solver2008
- LLVM: A compilation framework for lifelong program analysis & transformation2004
- Phi-predication for light-weight if-conversion2003
- An O(logn) parallel connectivity algorithmJournal of Algorithms, 1982