Abstract
Satisfiability Modulo Theories (SMT) solvers are fundamental to modern software verification and symbolic execution. However, their performance heavily depends on manually crafted strategies—sequences of tactics—that often fail to generalize across diverse logic theories. We present SIRISMT, a novel framework that automates strategy synthesis through a three-stage process: Simulation, Refinement, and Integration. By leveraging Graph Neural Networks (GNNs) to capture formula structure and Reinforcement Learning (RL) to explore tactic sequences, SIRISMT produces optimized, branching strategies. Our evaluation shows that SIRISMT solves up to 26.8% more formulas than default Z3 configurations and significantly enhances downstream symbolic execution performance.
1. Introduction
Modern SMT solvers like Z3 utilize sequences of "tactics" (e.g., simplification, bit-blasting, or quantifier elimination) to solve complex logic formulas. The search space for these strategies is astronomical, with Z3 alone offering over 100 tactics, many with unique parameters. Hand-crafted default strategies are often "one-size-fits-all" and perform poorly on specialized or highly complex constraints. Previous machine learning attempts have often treated formulas as simple text strings, failing to capture deep structural interdependencies, or produced "noisy" strategies filled with redundant, time-wasting steps.
2. The SIRISMT Framework
SIRISMT addresses these challenges through a modular pipeline designed to automate the "black art" of strategy engineering.
2.1 Simulation (The Explorer)
Instead of treating a formula as a sequence of tokens, SIRISMT constructs an AST-based graph. A critical innovation is the inclusion of "use-definition" edges, which explicitly link variables to their definitions. This structural representation is essential for tactics like constant propagation. Graph Attention Networks (GATs) encode these graphs into embeddings. A Double DQN (Reinforcement Learning) agent then "plays" the solver, choosing tactics based on the current state of the formula and receiving rewards for successful, fast solves.
2.2 Refinement (The Optimizer)
RL-generated sequences are often bloated with redundant steps. SIRISMT uses Probabilistic Delta Debugging (ProbDD) to systematically prune tactics that do not contribute to the solve. It also identifies "frequent subsequences"—tactic combinations that work well across many formulas—and uses them to augment training data, creating a virtuous feedback loop with the RL agent that significantly accelerates learning.
2.3 Integration (The Architect)
To handle diverse datasets, a single linear sequence is insufficient. SIRISMT uses the C4.5 decision tree algorithm to synthesize a branching strategy. It employs "probes" (cheaply computed features of a formula) to decide which specific tactic sequence to apply to a given input at runtime.
3. Experimental Evaluation
The framework was evaluated on five major SMT-LIB benchmark suites (QFBV, QFNIA, QFNRA) and tested for downstream impact on symbolic execution using the KLEE engine on standard Linux utilities like coreutils, Make, and Gawk.
3.1 Key Results
- Solve Rate: SIRISMT solved 26.8% more formulas than the default Z3 strategy and outperformed state-of-the-art ML competitors like fastSMT and Z3Alpha by roughly 15-16%.
- Efficiency: It achieved up to an 86.3% improvement in PAR-2 scores, indicating much faster solving times and fewer timeouts.
- Real-World Impact: When integrated into KLEE, the synthesized strategies improved code coverage by up to 11.8% on
coreutils. - Generalization: Strategies trained on one dataset (e.g.,
Sage2) generalized well to real-world programs, significantly outperforming KLEE's default solver settings.
4. Conclusion
SIRISMT demonstrates that combining structural graph encoding with iterative RL and systematic refinement significantly advances automated SMT strategy synthesis. By recognizing that formulas are dynamic and their structure matters, the framework moves beyond static prediction to adaptive, high-performance solver configuration. Future work includes extending the framework to other solvers like cvc5 and exploring the integration of Large Language Models (LLMs) to incorporate human-written heuristics.
Summary updated