Speculative Symbolic Execution
This addresses a key bottleneck in program analysis for software verification and testing, though it is an incremental improvement over existing symbolic execution methods.
The paper tackles the scalability problem in symbolic execution for large-scale or complex programs by proposing Speculative Symbolic Execution (SSE), which reduces constraint solver invocations by speculatively exploring branches without immediate feasibility checks, resulting in an average 30% reduction in solver invocations and search time savings.
Symbolic execution is an effective path oriented and constraint based program analysis technique. Recently, there is a significant development in the research and application of symbolic execution. However, symbolic execution still suffers from the scalability problem in practice, especially when applied to large-scale or very complex programs. In this paper, we propose a new fashion of symbolic execution, named Speculative Symbolic Execution (SSE), to speed up symbolic execution by reducing the invocation times of constraint solver. In SSE, when encountering a branch statement, the search procedure may speculatively explore the branch without regard to the feasibility. Constraint solver is invoked only when the speculated branches are accumulated to a specified number. In addition, we present a key optimization technique that enhances SSE greatly. We have implemented SSE and the optimization technique on Symbolic Pathfinder (SPF). Experimental results on six programs show that, our method can reduce the invocation times of constraint solver by 21% to 49% (with an average of 30%), and save the search time from 23.6% to 43.6% (with an average of 30%).