Efficient state merging in symbolic execution
Authors:
Open Access
- 11 June 2012
- conference paper
- Published by Association for Computing Machinery (ACM)
- Vol. 47 (6) , 193-204
Abstract
Symbolic execution has proven to be a practical technique for building automated test case generation and bug finding tools. Nevertheless, due to state explosion, these tools still struggle to achieve scalability. Given a program, one way to reduce the number of states that the tools need to explore is to merge states obtained on different paths. Alas, doing so increases the size of symbolic path conditions (thereby stressing the underlying constraint solver) and interferes with optimizations of the exploration process (also referred to as search strategies). The net effect is that state merging may actually lower performance rather than increase it. We present a way to automatically choose when and how to merge states such that the performance of symbolic execution is significantly increased. First, we present query count estimation, a method for statically estimating the impact that each symbolic variable has on solver queries that follow a potential merge point; states are then merged only when doing so promises to be advantageous. Second, we present dynamic state merging, a technique for merging states that interacts favorably with search strategies in automated test case generation and bug finding tools. Experiments on the 96 GNU Coreutils show that our approach consistently achieves several orders of magnitude speedup over previously published results. Our code and experimental data are publicly available at http://cloud9.epfl.ch.Keywords
This publication has 21 references indexed in Scilit:
- Automatic partial loop summarization in dynamic test generation2011
- Lazy Annotation for Program Testing and Verification2010
- A Polymorphic Intermediate Verification Language: Design and Logical Encoding2010
- State Joining and Splitting for the Symbolic Execution of Binaries2009
- Back to the future2008
- F-Soft: Software Verification Platform2005
- Trace Partitioning in Abstract Interpretation Based Static Analyzers2005
- A Tool for Checking ANSI-C Programs2004
- Guarded commands, nondeterminacy and formal derivation of programsCommunications of the ACM, 1975
- SELECT---a formal system for testing and debugging programs by symbolic execution1975