Lune

CAV2026Top-tier venue

Improving Stability of SMT Solvers via Context-Driven Normalization

Xiang Zhang, Mengyu Zhao, Shaohuang Chen, Jian Zhang, Shaowei Cai

Abstract

Abstract Satisfiability Modulo Theories (SMT) solvers are widely used in formal verification. In program analysis, users often encounter queries that differ only by simple syntactic mutations and are logically equivalent. These mutations typically include assertion reordering, symbol renaming, anti-symmetric relation inversion, and commutative operand reordering. However, such minor changes can cause runtimes to vary by orders of magnitude. This variability reduces the predictability required for industrial-scale verification and remains a critical challenge. This paper presents SMTStabilizer, a tool that improves the stability of SMT solvers via context-driven normalization. Since complete input normalization is as hard as the graph isomorphism problem, SMTStabilizer adopts an approximate normalization strategy to avoid the high cost of exact normalization. The framework converts formulas into a structured representation and propagates structural information across nodes, enabling each node to capture its surrounding context. Using this context information, SMTStabilizer derives a consistent ordering over subformulas. This process yields a nearly canonical form that remains consistent across isomorphic inputs. SMTStabilizer also leverages pruning techniques that exploit the syntactic structure of SMT formulas to reduce normalization time. Evaluation on millions of queries using Z3 and cvc5 shows that SMTStabilizer improves solver stability to over 98%98\% 98 % under 10 random mutations.

Ask Lune

Know where this paper stands in minutes, not an afternoon.

Lune can read the top-tier papers that cite it and the ones closest to it, and tells you what it claims, what came after and where it falls short, each point cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

its abstract · related work

Get the answer

Free to start. No credit card required.

Related papers

  1. Validating SMT Solvers via Skeleton Enumeration Empowered by Historical Bug-Triggering InputsMaolin Sun, Yibiao Yang, Ming Wen, Yongcong Wang et al.ICSE 2023 · 9 citations
  2. On the unusual effectiveness of type-aware operator mutations for testing SMT solversDominik Winterer, Chengyu Zhang, Zhendong SuOOPSLA 2020 · 55 citations
  3. Diver: Oracle-Guided SMT Solver Testing with Unrestricted Random MutationsJongwook Kim, Sunbeom So, Hakjoo OhICSE 2023 · 7 citations
  4. Validating SMT Rewriters via Rewrite Space Exploration Supported by Generative Equality SaturationMaolin Sun, Yibiao Yang, Jiangchang Wu, Yuming ZhouOOPSLA 2025 · 3 citations
  5. Fuzzing SMT solvers via two-dimensional input space explorationPeisen Yao, Heqing Huang, Wensheng Tang, Qingkai Shi et al.ISSTA 2021 · 18 citations
Dusk over the sea between two cliffs drawn in fine vertical lines