Speculative Symbolic Execution

Yufeng Zhang, Zhenbang Chen, Ji Wang

Abstract

Symbolic execution (SE) is a powerful technique for bug discovery and program verification, yet its scalability is frequently hampered by the high cost of constraint solving. Traditional SE engines invoke a solver at every conditional branch to check path feasibility, leading to significant performance bottlenecks. This paper introduces Speculative Symbolic Execution (SSE), a novel approach that optimistically explores program paths and batches solver queries. By reducing the frequency of solver interactions, SSE achieves substantial performance gains. Experimental results on various benchmarks demonstrate a reduction in solver calls by up to 49% and an average speedup of 30% in total execution time.

Introduction

Symbolic execution explores programs using symbolic values instead of concrete inputs, building path conditions that represent the constraints required to reach specific code locations. A major challenge in SE is the "path explosion" problem, compounded by the computational expense of constraint solvers (e.g., SMT solvers). In many real-world scenarios, solver time accounts for 40% to 90% of the total analysis time. While existing optimizations focus on simplifying constraints or caching results, they typically maintain a one-to-one mapping between branch points and solver calls.

Speculative Symbolic Execution (SSE)

The core innovation of SSE is the decoupling of path exploration from immediate feasibility checking. Instead of querying the solver at every branch, SSE "speculates" that branches are feasible and continues execution.

Batching and Backtracking

SSE accumulates branch constraints and invokes the solver only when a predefined "max speculation depth" is reached or a terminal state is encountered. This allows multiple constraints to be verified in a single batch, which is often more efficient than multiple sequential calls.

Comparison of solver call frequency in Pure SE versus Speculative Symbolic Execution (SSE).

If a batch is found to be infeasible ("unsat"), SSE employs a binary search backtracking strategy to identify the specific branch that caused the contradiction. This minimizes the overhead of recovering from incorrect speculations.

Logical Optimizations

SSE incorporates "Absurdity-Based Optimization" derived from the principle of Reductio AD Absurdum. If one side of a branch is proven infeasible, the engine can logically infer the feasibility of the alternative path without an additional solver query. Furthermore, the authors observed that the "false" branch of a conditional is often more likely to be feasible in practice, as "true" branches frequently handle error cases or rare conditions. Prioritizing the exploration of likely-feasible paths improves the success rate of speculation.

Experimental Evaluation

The SSE framework was implemented within the Symbolic PathFinder (SPF) for Java and evaluated against six benchmarks: the Wheel Brake System (WBS) and five complex data structures (TreeMap, BinTree, BinHeap, FibHeap, and List).

Experimental results comparing Pure SE, SSE, and optimized SSE+ across various benchmarks.

As shown in the results table, SSE consistently outperforms pure SE. In the WBS benchmark, which contains no infeasible branches, SSE reduced solver calls by 49%. Across all benchmarks, total search time was reduced by an average of 30%. The "sweet spot" for speculation depth was typically between 2 and 6 branches for data structure benchmarks.

Discussion and Future Work

While SSE significantly improves performance, it introduces new challenges. Speculating through code with external side effects (e.g., I/O) requires careful environment modeling to prevent irreversible actions on infeasible paths. Additionally, deep speculation on highly infeasible paths can lead to wasted exploration. Future research will focus on integrating SSE with non-DFS search strategies and further refining speculation heuristics to balance exploration speed with the risk of path divergence.

Conclusion

Speculative Symbolic Execution addresses a fundamental bottleneck in program analysis by batching constraint solver queries. By shifting from a reactive to an optimistic exploration model, SSE provides a scalable path forward for symbolic execution in complex software systems.

Summary updated

Abstract

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 20.7% to 48.7% (with an average of 29.9%), and save the search time from 23.6% to 43.6% (with an average of 30%).
BibTeX
@inproceedings{zhang2012speculative,
  author = {Yufeng Zhang and Zhenbang Chen and Ji Wang},
  title = {{Speculative Symbolic Execution}},
  booktitle = {ISSRE},
  year = {2012},
  url = {https://openreview.net/forum?id=YY03zxWU3L},
}
Figure