betaFeedback

WorksComputer Science

Sundance: A Simple SMT Solver for Program Verification

Abstract

We present Sundance, an SMT solver for program verification written in about 13,600 lines of Rust. Sundance combines the Cadical SAT solver with congruence closure, linear arithmetic, algebraic datatypes, and pattern-based quantifier instantiation. Sundance produces eDRAT proofs for every unsat answer. On 21,531 queries from Verus, Dafny, and F*, Sundance is comparable to existing solvers, with 26–38 times fewer lines of code than Z3 and cvc5. We further show that its components can be swapped for Z3's arithmetic solver, MiniSat, and the Semper e-graph. We have open sourced Sundance.

Introduction

Auto-active program verification tools such as Dafny [53], Verus [51], and F⋆F^\star [76] are used to verify large-scale systems in industry and academia [3, 4, 21, 44, 50, 69, 77, 91]. Program verification has become widespread in part because of automation provided by off-the-shelf Satisfiability Modulo Theories (SMT) solvers. Verification tools translate program properties into first-order logic and call a solver, such as Z3 [61], cvc5 [7], or Alt-Ergo [26] in the back-end. This allows verification engineers to focus on high-level program properties and ignore low-level proof details.

Z3 and cvc5, the primary SMT solvers used in program verification, support many logical fragments and theories. They are employed for a wide variety of tasks: mathematics [17], fuzzing [62], model-checking [27], and many others. This requires a broad set of capabilities, complicated heuristics, and performance tuned for many different use cases. This leads to complex, large code bases: Z3 and cvc5 are each several hundred thousand lines of C++ code (519,367 lines for Z3 and 358,294 for cvc5) [7, 61].1 This complexity costs verification users:

  1. Opacity. It is difficult to understand why a solver succeeds or fails, so users resort to intricate encodings, obscure flag combinations, and bespoke debugging tools [10].

  1. Trust issues. Existing solvers are trusted by the verification tools, but they have been shown to contain bugs [84].

  1. Monolithic architectures. Tightly coupled components make it difficult to add features or adopt new advances. For instance, there has been an explosion of research in e-graphs [83, 87], but none of these new ideas have made their way into mainstream SMT solvers.

We believe it is time to revisit how we design SMT solvers. Verifiers use only a narrow fragment of SMT, and often disable general-purpose features such as model-based quantifier instantiation. Meanwhile, the building blocks of a solver have matured into reusable components: modern SAT solvers such as CaDiCaL [68] expose interfaces for theory integration [38], e-graph libraries are widely available [32, 83, 87], and proof formats such as eDRAT [46] make certification much cheaper than before.

To demonstrate this, we present Sundance, a simpler SMT solver specialized for program verification. Sundance is written in 13,612 lines of Rust and consists of the CaDiCaL SAT solver [68], a pattern-based quantifier instantiation engine, a congruence closure module, and a linear arithmetic module. These features are sufficient to support 91.3% of the queries in our held-out Verus benchmarks, 93.0% of Dafny benchmarks, and 97.1% of F⋆F^\star benchmarks. Verus and Dafny developers have asked for a solver with exactly these features [54].

Sundance has three key properties:

  1. Transparency. Sundance is designed to be simple, with a clear architecture and few heuristics (§ 4–Sec. 5).

  2. Trustworthiness. Sundance produces proofs in the eDRAT format, a clausal proof format inspired by SAT solvers, and every unsat result comes with a proof.

  3. Modularity. Each module implements a Rust trait, so components can be swapped out: Sundance can use either CaDiCaL or MiniSat as its SAT solver (Sec. B), and either its own arithmetic solver or Z3’s.

We describe Sundance’s architecture and main modules. We then evaluate Sundance on 6,662 queries from Verus, including a held-out set of 4,086 queries not used during development, and on 11,674 Dafny and 3,195 F⋆F^\star queries from the Mariposa benchmark suite [90], comparing it with Z3, cvc5, and Alt-Ergo. Z3 without proofs solves nearly every query, which is expected: each query comes from a project that was already verified with Z3, so Z3 solves it by construction. Our evaluation shows that:

  • Sundance is competitive on Verus (§ 8.1). On the held-out Verus set, it solves 86.7% of queries within 10 s, more than Z3 with proofs (82.7%) and Alt-Ergo (77.4%) and close to cvc5 (90.5%), within 60 s, compared with 95.3% for cvc5, 97.7% for Z3 with proofs, and 82.8% for Alt-Ergo.

  • Sundance generalizes to Dafny and F⋆F^\star (§ 8.2), even though it was not developed for them. On Dafny, it solves 73.7% of queries, more than any other proof-producing solver and Alt-Ergo; on F⋆F^\star, it solves 56.7%, between cvc5 (54.9%) and Alt-Ergo (59.3%).

  • Sundance’s modules can be swapped (§ 8.3). Sundance also runs with Z3’s arithmetic solver, the Semper e-graph [32], and the MiniSat SAT

solver [36]. Each alternative regresses on every benchmark set, indicating that Sundance’s default configuration is the best of those we tried.

We have open sourced Sundance.

Sundance’s Design

We motivate the need for Sundance’s components through a running example from Verus and the SMT query it generates. Proving this query requires Boolean case analysis, equality reasoning, arithmetic, and quantifier instantiation. We present Sundance’s architecture, and we describe each module and the part of the example it is responsible for.

Running Example

Figure 1(a) shows a function written in Verus that iterates through a vector of integers, and maintains a running upper bound ub. Its ensures clause (line 3) states that the returned value is greater than or equal to every element of the vector. Verus cannot prove this on its own, so the developer provides a loop invariant (line 9): at the start of each iteration, ub is greater than or equal to every element seen so far. Verus must then show that (1) the invariant holds on entry to the loop, (2) it is preserved by each iteration, and (3) it implies the ensures clause on exit. Each of these obligations becomes a separate SMT query.

Verus source and SMT-LIB query for the invariant

Figure 1. Running example. (a) A Verus function that computes an upper bound of a vector, with its loop invariant highlighted. (b) The simplified SMT-LIB query that Verus generates to check that the loop invariant is preserved by each iteration.

Figure 1(b) shows a simplified version of the SMT query for checking that the loop invariant is preserved. The original is about 6,000 lines long, since Verus includes a large prelude of axioms for vectors and other standard constructs [51].

The query models vectors with an uninterpreted sort Vec\mathrm{Vec} and uninterpreted functions len\mathrm{len} and index\mathrm{index}. The constants ii and ub\mathrm{ub} are the loop index and bound at the start of an arbitrary iteration. Line 10 assumes the loop index is in bounds, and lines 13–16 assume the invariant holds at the start of the iteration. Lines 20–21 define ub_new\mathrm{ub\_new}, the bound after the loop body. Finally, lines 24–27 assert the negation of the invariant for the next iteration. The obligation holds if and only if the query is unsatisfiable.

The query is unsatisfiable: the negated goal (lines 24–27) states that the invariant fails for i+1i+1. There is then some index j0j_0 such that 0≤j0<i+10 \le j_0 < i+1 and index(a,j0)>ub_new\mathrm{index}(a,j_0) > \mathrm{ub\_new}. By its definition (lines 20–21), ub_new\mathrm{ub\_new} is the larger of ub\mathrm{ub} and index(a,i)\mathrm{index}(a,i). If j0<ij_0 < i, the invariant (lines 13–16) applies to j0j_0, so index(a,j0)≤ub≤ub_new\mathrm{index}(a,j_0) \le\mathrm{ub} \le\mathrm{ub\_new}. Otherwise, since j0j_0 is an integer with i≤j0<i+1i \le j_0 < i+1, we have j0=ij_0=i, and so index(a,j0)=index(a,i)≤ub_new\mathrm{index}(a,j_0)=\mathrm{index}(a,i) \le\mathrm{ub\_new}. Both cases contradict index(a,j0)>ub_new\mathrm{index}(a,j_0) > \mathrm{ub\_new}.

Each step of this argument is carried out by a different part of Sundance: naming j0j_0 is skolemization, applying the invariant to j0j_0 is quantifier instantiation, the case split is made by the SAT solver, j0=ij_0=i requires integer arithmetic, and index(a,j0)=index(a,i)\mathrm{index}(a,j_0)=\mathrm{index}(a,i) follows by congruence.

Architecture

Sundance is based on the CDCL(T) approach [9]. Its architecture is shown in Figure 2. The input script is parsed and type-checked by the Yaspar-IR library [1, 2] and then converted to conjunctive normal form (CNF). A SAT solver searches for an assignment to the Boolean skeleton, and theory modules check that assignment against their theories. A module that finds the assignment inconsistent returns a conflict clause; a module may also return lemmas, clauses that are valid in its theory and guide the search. The SAT solver adds these clauses and continues, until either all modules accept a full assignment or the SAT solver derives the empty clause and returns unsat.

Architecture of Sundance

Figure 2. The architecture of Sundance.

Sundance has three modules. The e-graph stores every term in the query up to equality and implements congruence closure for uninterpreted functions. The e-graph is also the substrate for quantifier instantiation: e-matching searches it for terms that match quantifier patterns, and the resulting instances are queued and handed to the SAT solver. The arithmetic module decides linear integer and real arithmetic using simplex and branch-and-bound.

Inspired by our goals of transparency, trustworthiness, and modularity, we followed several high-level design principles:

Minimalism. Sundance supports only the SMT fragment that program verifiers use. It omits model-based and enumerative quantifier instantiation (which verifiers typically disable) and performs little preprocessing. We add standard SMT heuristics and optimizations only when they give a significant benefit on verification queries.

Explicit interfaces. Each module implements a Rust trait and can be replaced by any component implementing the same trait. For example, Sundance supports using the MiniSat solver [36], Z3’s arithmetic solver [13], and the Semper e-graph [32] as alternatives.

Proof generation. Every theory lemma and quantifier instance reaches the SAT solver as a clause, and CaDiCaL logs these together with its own learned clauses. Proof logging thus does not change the search and adds minimal overhead.

Modules

We now describe each module’s role in proving the running example, the challenge it faces on verification queries, and the approach Sundance takes, which later sections expand on.

Parsing. Sundance reads its input with Yaspar [2], a parser for SMT-LIB 2.7 and represents formulas with Yaspar-IR [1]. Yaspar-IR type-checks the parsed script and produces a typed, hash-consed representation of terms. Yaspar and Yaspar-IR are standalone libraries that other tools can reuse.

SAT Solver. Using Yaspar-IR, Sundance converts the query to CNF using the Tseitin transformation [81], and the SAT solver treats each atom as a separate SAT variable. In our example, the SAT solver makes the case split of the proof, on whether j0<ij_0 < i and on whether index⁡(a,i)>ub\operatorname{index}(a, i) > ub, which selects the branch of the ite that defines ub_newub\_new.

As the SAT solver picks a truth assignment for the atoms, it notifies the theory modules of each assignment. Theory modules can check each partial assignment eagerly, as literals are assigned, or lazily, i.e., once the SAT solver has a complete assignment. In Sundance, the e-graph and arithmetic modules are eager and quantifier instantiation is lazy.

In existing SMT solvers, the SAT solver is typically tightly coupled to the theory solvers, and its many heuristics are tuned together with theirs. This makes it hard to adopt advances in SAT solving, or to tell which heuristics actually matter for verification queries. Sundance instead uses an off-the-shelf SAT solver through the IPASIR-UP interface [38], and currently supports both CaDiCaL [68] and MiniSat [36]. Modules never directly influence SAT search; they only add clauses. This keeps the interface small, so we can experiment with SAT-level techniques such as chronological backtracking and phase selection independently of the theory modules (Sec. 3).

E-graph. In our example, the e-graph carries out the last step of the second case: once j0=ij_0 = i is known, congruence concludes index⁡(a,j0)=index⁡(a,i)\operatorname{index}(a,j_0) = \operatorname{index}(a,i). The e-graph implements congruence closure [63, 64], and it is also the shared data structure through which Booleans, ite terms, datatypes, and quantifier matching are handled. There are many e-graph designs, from the backtrackable congruence closure of SMT solvers to e-graph libraries built for equality saturation [32, 83, 87], and they make different trade-offs between efficiency, simplicity, and expressivity. In existing SMT solvers, the e-graph is deeply integrated with the rest of the solver, so these trade-offs are hard to explore.

Sundance places the e-graph behind a trait, so alternative implementations can be substituted, and we used this to experiment with several design choices. We keep every term in the e-graph, including Boolean terms; index congruences with a signature table; and keep constants as representatives of their equivalence classes so that conflicting merges are detected cheaply (Sec. 4).

Quantifier Instantiation. In our example, quantifier reasoning carries out the first two steps of the proof: naming j0j_0 skolemizes the negated goal, introducing a fresh constant, and applying the invariant to j0j_0 instantiates it with j:=j0j := j_0. Since the quantifier has infinitely many instances, a solver must decide both how to discover candidate instances and when to add them to the search. Existing solvers answer both questions with many interacting heuristics, and on large verification queries these heuristics largely determine performance. To discover instances, Sundance uses top-down e-matching [33] on the patterns supplied by the verifier: the pattern (index a j) matches index⁡(a,j0)\operatorname{index}(a,j_0) in the e-graph, yielding the needed instance. We found that the simple approach is sufficient for our Verus benchmarks, as the time spent searching for quantifier instantiations is not a significant bottleneck there. To decide when to instantiate, Sundance matches in rounds against a fixed e-graph and adds the resulting instances to the SAT solver lazily, in batches.

Arithmetic. Both cases of the proof end in arithmetic conflicts, and the second relies on integer reasoning: i≤j0<i+1i \le j_0 < i + 1 forces j0=ij_0 = i. The challenge is theory combination: the arithmetic module and the e-graph must agree on which terms are equal, but sharing every decade equality floods the SAT solver with lemmas. Sundance shares equalities lazily: it tentatively merges terms that are equal in the arithmetic model, and only adds a lemma when the merge causes a conflict in the e-graph. The arithmetic backend is itself a module: Sundance can use its own built-in arithmetic module or use Z3 for arithmetic (§ 6).

Proof Production. When Sundance reports that the example is unsat, it also produces a proof that can be checked independently. In existing SMT solvers, proof production places heavy demands on every component: each theory solver and preprocessing step must justify its reasoning in a fine-grained proof calculus [8, 72]. This is costly to implement, slows solving, and can leave gaps where a component does not support proofs. Sundance instead uses eDRAT [46], a clausal proof format in the style of SAT solvers. Because every module communicates with the SAT solver only through clauses, the proof is just a record of these clauses: CaDiCaL logs its learned clauses, and each theory lemma or quantifier instance is logged as it is added. Such proofs are easy to produce and easy to check: the propositional steps are checked by a SAT proof checker and each theory lemma is checked separately. They also make it easy to swap in new components, since a module only needs to produce valid clauses (§ 7).

Measuring design decisions. In § 4 and § 5, we report how individual design decisions affected Sundance’s performance during development. We measured each change by rerunning the published version of our Verus development benchmark (§ 8) with a 60 s timeout before and after the change. These numbers reflect Sundance at the time of each change, not its final version.

SAT Solver

Sundance delegates Boolean search to an off-the-shelf SAT solver. Sundance communicates with the SAT solver through the IPASIR-UP interface [38], using callbacks that allow its e-graph and arithmetic modules to eagerly process assignments to Boolean variables, decision levels, and backtracks. When the SAT solver finds a complete satisfying assignment to the Boolean skeleton, Sundance performs datatype reasoning, further arithmetic checks, and runs a quantifier round. If the Boolean model is theory-inconsistent or a quantifier round produces new instances, Sundance adds clauses to the SAT solver: conflict clauses, theory lemmas, and clauses for Skolem constants and quantifier instances.

The default SAT solver is CaDiCaL, but as an alternative, Sundance also supports MiniSatUP [43], a version of MiniSat that exposes an IPASIR-UP interface. By design, the SAT solver can be replaced by any IPASIR-UP solver without requiring changes to theory modules. However, performance depends on specific SAT-solver features. Sundance adds many clauses, especially from quantifier instantiation, so the elevate option added in CaDiCaL 3.0.1 [11] is critical to avoid discarding large parts of the current assignment upon each addition (§ 5.3); similar functionality is built into the version of MiniSat that we use. Additionally, setting the initial phase for new variables to false results in degraded performance on many benchmarks, so we configure our version of MiniSat to use true as the initial phase, matching the default phase setting in CaDiCaL. With this setting, MiniSat solves only slightly fewer Verus queries than CaDiCaL (Appendix § 14).

E-graphs

The e-graph is Sundance’s central data structure. It decides equality with uninterpreted functions through congruence closure. It is also the term index that e-matching searches and the channel through which arithmetic and datatype reasoning learn about equalities. We first describe how the e-graph computes and explains congruences, then the design decisions that shaped it, and finally how it interacts with the rest of Sundance.

Congruence Closure and Explanations

Sundance’s congruence closure follows the design of Nieuwenhuis and Oliveras [66]. It extends a union-find data structure with a proof forest: each node has at most one outgoing edge, labeled with the reason its endpoints are equal, and the root of each tree represents an e-class. An equality edge records an equality asserted by the SAT solver; a congruence edge records the argument pairs that made two applications congruent. To merge the classes of xx and yy, the e-graph re-roots yy’s tree at yy and adds an edge from yy to xx, so that edges always connect terms that were actually equated. It then checks the disequalities stored at the surviving root and looks for new congruences among the parents of yy’s old root.

When a merge violates a disequality s≠ts \ne t, the e-graph must explain why s=ts = t in terms of literals the SAT solver assigned in order to learn a conflict clause. In Figure 3, literals (1) and (2) put uu and g(f(a))g(f(a)) in the class of ee; (3) makes f(a)f(a) and f(b)f(b) congruent, and hence g(f(a))g(f(a)) and g(f(b))g(f(b)), which violates (4). Since g(f(b))g(f(b)) and uu are in the same tree, they are connected by a single path. Each edge on this path contributes to the explanation: an equality edge contributes its literal, (2) and (1) here, and a congruence edge contributes the explanations of its argument pairs, computed recursively in the same way. Explaining f(b)=f(a)f(b) = f(a) yields (3), so the conflict clause is

Explaining a conflict

Figure 3. Explaining a conflict. Arrows point from a node to its parent. Solid edges record an asserted equality; dashed edges are congruence edges, labeled with the argument pair they depend on. To explain g(f(b))=ug(f(b)) = u, the e-graph follows the blue path from g(f(b))g(f(b)) and the orange path from uu to their least common ancestor ee, and recursively explains the congruence edges (also blue).

¬(e=u)∨¬(e=g(f(a)))∨¬(a=b)∨g(f(b))=u.\neg(e = u) \mathbin{\lor} \neg(e = g(f(a))) \mathbin{\lor} \neg(a = b) \mathbin{\lor} g(f(b)) = u.

Although the conflict involves two congruence steps, the clause mentions only literals the SAT solver assigned. When an argument pair has no equality atom in the input, Sundance introduces one. These clauses enter the eDRAT proof as theory lemmas (§ 7).

Design Decisions

Several of these choices are standard in congruence closure; we include them because they had a large effect on performance or simplicity.

All terms in the e-graph. Every term is an e-graph node, including Boolean terms. When the SAT solver assigns an atom, the e-graph merges it with true or false. This lets congruence reason about predicates and ite terms directly: for example, if a=ba=b, P(a)P(a) is true, and P(b)P(b) is false, congruence merges true with false, which is a conflict. It also allows pattern matching against Boolean terms. Keeping Boolean terms out of the e-graph could be more efficient, but in our experiments excluding them gave only a negligible speedup.

Signature table. To find new congruences, the e-graph keeps a signature table mapping each signature (f,find⁡(t1),…,find⁡(tn))(f,\operatorname{find}(t_1),\ldots,\operatorname{find}(t_n)), where find⁡(t)\operatorname{find}(t) is the representative of tt’s class, to an application with that signature. After a merge, each application with an argument in the merged class is looked up in the table: a hit in a different class is a new congruence, merged immediately. Adding the signature table increased the number of Verus queries Sundance solved by 3.7% on our development benchmark (§ 2.3).

Constants as representatives. A constant, such as 3 or true, is always kept as the representative of its class. A merge of two classes with different constant representatives, such as true and false, is therefore detected as a conflict with a single comparison. This change increased the number of Verus queries Sundance solved by 9.9%, the largest single improvement during development.

No theory propagation. Sundance reports conflicts but never propagates implied literals to the SAT solver. We experimented with theory propagation and found that it made no significant difference on program verification benchmarks, so we left it out for simplicity.

A modular e-graph. The rest of the solver accesses the e-graph only through a Rust trait covering term registration, asserting and querying (dis)equalities, explanations, pattern matching, and backtracking, so a different implementation, such as the Semper e-graph [32], can be easily substituted.

Integration with Semper. Semper [32] is an e-graph providing the same core operations as Sundance’s e-graph, but designed for equality saturation workloads [79]. Specifically, Semper is optimized for marking and restoring very large e-graphs. To save space, it compresses the changes made since the last mark incrementally, and decompresses them when a restore undoes them.

Semper also recycles the identifiers of nodes that a restore has released. A restore deletes every node created since the mark, and later nodes may reuse their identifiers. After each restore, the adapter therefore re-inserts every term registered above the restore point and updates the term table to the new nodes. This re-insertion takes 56% of a quantifier instantiation round, and it accounts for much of the slowdown of Sundance with Semper (§ 8.3).

Interaction with Other Modules

Backtracking. The e-graph processes each literal as soon as the SAT solver assigns it. It must undo its state whenever the SAT solver backtracks. Every merge is recorded on a trail and reversed on backtracking. Stale parent lists and disequality entries are invalidated lazily rather than deleted. Terms introduced during search, by quantifier instances or datatype axioms, are permanent; after backtracking, Sundance re-inserts them so their congruences are rediscovered.

Arithmetic. Every merge between classes containing arithmetic terms is sent to the arithmetic solver as an equality. In the other direction, Sundance uses a model-based variant of Nelson–Oppen combination [9, 34]: when the arithmetic solver accepts a full assignment, Sundance tentatively merges pairs of e-classes with the same value in the arithmetic model. Only if a merge causes a conflict does it add the lemma x<y∨x=y∨x>yx < y \lor x = y \lor x > y; all tentative merges are then undone. This generates lemmas only for equalities that actually matter to the e-graph.

Datatypes. Like Z3 [12], Sundance adds some datatype axioms eagerly when a datatype term is registered: for a constructor application C(t1,…,tn)C(t_1,\ldots,t_n), it asserts is-C(C(t1,…,tn))is\text{-}C(C(t_1,\ldots,t_n)) and seli(C(t1,…,tn))=tisel_i(C(t_1,\ldots,t_n)) = t_i, and for terms of non-recursive datatypes it asserts that some tester holds. When a tester is-C(t)is\text{-}C(t) is assigned true, Sundance lazily adds the axiom t=C(sel1(t),…,seln(t))t = C(sel_1(t),\ldots,sel_n(t)). Acyclicity is checked at final check by a depth-first search over e-class representatives; a cycle yields a conflict explained by the e-graph equalities along it.

Quantifier Instantiation

Program verification queries are dominated by quantifiers. Verifiers encode function definitions, datatype and collection axioms, and loop invariants as universally quantified formulas with syntactic patterns, and the solver’s job is mostly to find the instances that close the proof. Sundance supports only the style of quantifier reasoning that verifiers rely on: pattern-based instantiation by e-matching [33, 58], and skolemization of existential quantifiers. After describing how quantifiers are represented, we discuss the two questions raised in § 2.3: how Sundance discovers instances, and when it adds them to the search.

Quantifiers as Literals

Sundance does not preprocess quantifiers. Each quantified formula is a Boolean atom like any other: the SAT solver assigns it, and the e-graph stores it as an opaque term. A universal P=∀x⃗.φ(x⃗)P = \forall\vec{x}.\varphi(\vec{x}) assigned true, or an existential Q=∃x⃗.φ(x⃗)Q = \exists\vec{x}.\varphi(\vec{x}) assigned false, is instantiated. A universal assigned false, or an existential assigned true, is skolemized.

Discovering Instances

Patterns. Each universal quantifier carries one or more multi-patterns: lists of terms over the bound variables that must all match under a single substitution.

Program verifiers annotate almost all quantifiers with patterns. For inputs without them, Sundance can optionally infer patterns in the style of Simplify [33], preferring a single term that covers all bound variables and otherwise choosing a small multi-pattern by greedy set cover.

E-matching. Sundance implements the top-down backtracking e-matching algorithm of Simplify [33]. For a pattern f(p1,…,pn)f(p_1,\ldots,p_n), it scans the registered applications of ff and matches each argument recursively, modulo the current e-classes: a pattern variable binds to the argument’s e-class, a ground subterm must be in the argument’s class, and a nested application is matched against the applications of its symbol in that class.

Matching is not the bottleneck for Verus. More efficient algorithms exist. Z3 compiles patterns into code trees [58] that share work across patterns, and relational e-matching [88] offers asymptotic speedups on complex patterns; we also experimented with the latter. On our Verus development benchmark, however, matching takes a small fraction of solving time, so the simple algorithm sufficed during development. This is not true of every benchmark: on the very large F{sup}⋆ queries from DICE{sup}⋆, matching does become a bottleneck (§ 8.2). Because matching is a separate module, a faster algorithm can be substituted in the future (§ 10).

Scheduling Instances

Rounds against a fixed e-graph. Sundance runs quantifier reasoning lazily, only when the SAT solver finds a full assignment that the e-graph and arithmetic module accept. It then runs a round: it skolemizes every newly assigned quantifier that requires it and matches the patterns of every universal quantifier assigned true. All matches are computed before any instance is added to the e-graph, so a round’s matches depend only on the e-graph at its start, not on the order in which instances are added. We found this to be faster and more robust: it increased the number of Verus queries Sundance solved by 0.6% on our development benchmark (§ 2.3).

Lazy batches. Matches are placed in a pending queue, skipping any instance already produced. Sundance adds up to a fixed batch of pending instances (85 by default) to the SAT solver, and the rest one per subsequent full assignment, starting a new round only once the queue is empty. Bounding the batch lets the SAT solver react to the first instances, which often produce a conflict, before many more clauses are added. Adding a clause rejects the current assignment, so Sundance uses CaDiCaL’s elevate option, introduced in CaDiCaL 3.0.1 [11], to backjump only as far as needed and keep most of the assignment between batches. Together, these changes increased the number of Verus queries Sundance solved by 2.1% on the same benchmark.

Arithmetic

Sundance includes its own solver for mixed linear integer and real arithmetic, based on techniques by Dutertre and de Moura [35] and Bromberger [18]. It can be used as a theory solver or as a standalone QF_LIRA solver. Like the rest of Sundance, it favors simplicity and stability over peak performance, targeting the small to medium linear systems that arise in program verification. It consists of a preprocessor, a dual simplex solver, and integer reasoning on top of simplex.

Preprocessing

The solver receives arithmetic literals from the SAT solver and e-graph and applies only lightweight preprocessing. It orders the variables deterministically, moves variables to one side and constants to the other, and scales each relation so that its leading coefficient is 1; relations with the same linear term can then share a slack variable [35]. Trivially true relations, such as 0<10 < 1, are dropped, and a trivially false relation, such as 0<−10 < -1, is immediately reported as a conflict. Equalities become a pair of bounds, and disequalities are handled by the e-graph, which avoids splitting x≠yx \ne y into x<y∨x>yx < y \lor x > y. The result is a set of bounded linear sums

li≤∑jaijxj≤ui(1)l_i \le\sum_j a_{ij}x_j \le u_i \tag*{(1)}

with rational coefficients and bounds that are rational or ±∞\pm\infty.

Simplex

The rational relaxation is decided by a dual simplex solver that closely follows existing implementations [18, 35]. Strict inequalities are handled by working over Qδ\mathbb{Q}_{\delta}, replacing l<xl < x with l+δ≤xl+\delta\le x for an infinitesimal δ\delta, which is instantiated with a suitable rational value when a model is produced. Each relation in Equation (1) receives a slack variable sis_i, giving the tableau Ax=sAx=s with bounds li≤si≤uil_i \le s_i \le u_i. The solver then runs the standard dual simplex algorithm [18 Sec. 2.7.1], using Bland’s rule [14] to choose pivots and guarantee termination. We chose Bland’s rule over more sophisticated pivoting heuristics [18 Ch. 7] for simplicity and determinism. The dual simplex solver is incremental: bounds can be asserted in any state, and the solver can set and return to backtrack points.

Integer Reasoning

When the rational relaxation is feasible but some integer variable has a non-integral value, the solver first tries cheap tests that can decide the integer problem directly: the GCD test [13 Sec. 4.3] and the fast cube test [18 Ch. 4]. If these fail, it falls back on branch-and-bound [18 Sec. 2.7.3], using the incremental interface to explore strengthened bounds. Branch-and-bound is not complete for unbounded problems, so the solver may time out; Bromberger’s bounding transformation [18], which turns any mixed integer system into an equisatisfiable bounded one, would remove this limitation and is left for future work. The solver also omits techniques common in other SMT solvers [13], such as Gomory cuts, Hermite normal forms, and nonlinear arithmetic.

The end-to-end arithmetic module exposes an incremental interface. This is driven by the SAT solver and used to detect conflicts early as the SAT solver builds partial models. The implementation relies on a growing tableau with slack row caching to avoid tableau size blow-up. When assertions are backtracked over, the corresponding slack variable’s bounds are loosened to ±∞\pm\infty, preserving satisfiability while not requiring the row to be removed or any pivots to occur.

Modularity

The arithmetic module implements a Rust trait, so it can be replaced without changing the rest of Sundance. We have also implemented this trait using Z3’s arithmetic solver through its Rust API; the two backends are selected with a command-line flag.

Proof Production

Sundance produces proofs in the eDRAT format [46], an extension to SMT of the DRAT format used by SAT solvers. eDRAT uses SMT-LIB syntax for declaring sorts, functions, and constants, and for defining terms and formulas. In addition, an eDRAT proof records theory and Boolean reasoning steps performed by SMT solvers in the form of clauses. A clause is written in the DIMACS style as a list of integers. eDRAT distinguishes three types of clauses: assumptions correspond to the assertions in the original SMT file after conversion to CNF, theory lemmas are clauses derived by theory reasoning, and regular clauses are derived by Boolean resolution. As in DRAT, the format also allows clauses to be deleted. eDRAT proofs can be produced by Sundance with negligible overhead.

We have modified the original eDRAT format described in [46] to allow theory lemmas to be labeled by a theory identifier. For example, theory lemmas produced by congruence closure and lemmas produced by the arithmetic solvers have different labels, which facilitates proof checking. We have also added new constructs to describe skolemization and quantifier instantiation.

Proof checking is done by using the Valido toolchain described in [46]. We have extended Valido to check quantifier reasoning steps and to parse the modified eDRAT format. We have also generalized Valido to use external SMT solvers to validate theory lemmas.2

Evaluation

In this section, we aim to answer three research questions:

RQ1 How does Sundance compare with existing SMT solvers on Verus, which it was initially developed for?

RQ2 How well does Sundance generalize to other verification frameworks like Dafny and F⋆F^\star?

RQ3 How does Sundance’s performance change when swapping out its modules?

Benchmarks. We evaluate on several datasets. First, we evaluate on a set of 2,576 Verus queries, originally compiled by Zhou et al. [92], from a number of Verus systems verification projects: Anvil [75], Atmosphere [22], Verified SplinterDB [82], VeriSMo [93], and a collection of other Verus systems verification projects [50]. A subset of this benchmark set was first submitted to the SMT competition in 2025 [73]. We used this benchmark set to guide the development of Sundance, and the effects of design decisions reported in § 4 and § 5 were measured on it. Its published version contains 3,763 queries, of which 1,187 are duplicate copies of SplinterDB queries; we remove these duplicates here, leaving 2,576. We directly shared the benchmarks with the developers of cvc5 and Z3 when we started developing Sundance so that both solvers could improve on Verus benchmarks.

To answer RQ1 without the bias of evaluating on the benchmarks we developed against, we also created a new, held-out set of 4,086 Verus queries that was not used during development. These come from four more recent Verus projects: CortenMM [85], OwlC [74], Verdict [56], and vostd [80]. To answer RQ2, we use the Dafny and F∗F^\ast queries from the Mariposa benchmark suite [90]: 11,674 Dafny queries from Komodo [39] and from two versions of VeriBetrKV, one using dynamic frames [42] and one using linear types [55], and 3,195 F∗F^\ast queries from DICE∗^\ast [78] and vWasm [16]. Sundance was not developed on these.

For the development Verus benchmarks, we pick the UFDTLIA queries. For the other benchmark sets, we compiled the queries from the original verification tool and filtered out any queries that used theories that we did not support such as bit-vectors, nonlinear arithmetic, and strings. Overall, we found that we could support 91.3% of the Verus held-out benchmarks, 97.1% of the F∗F^\ast benchmarks, and 93.0% of the Dafny benchmarks.

Setup. All experiments run on an AWS EC2 m7i.48xlarge instance (2× Intel Xeon Platinum 8488C, 192 hardware threads, 743 GB RAM), with 150 queries solved in parallel. Each query has a 60 s wall-clock timeout, and counts as solved only if the solver returns unsat. Sundance always produces eDRAT proofs, and on Dafny and F∗F^\ast queries, which contain quantifiers without patterns, it infers patterns automatically. We checked the proof of every unsat answer Sundance produced in our evaluation with Valido (§ 7); every check succeeded except one, which timed out. We compare against Z3 5.3.0 [61], cvc5 1.4.2 (git 282d5e0) [7], and Alt-Ergo 2.4.3 [26]. Z3 runs with the options each verifier passes to it. cvc5 runs with --no-cbqi --user-pat=strict, the configuration recommended by its developers. Both cvc5 and Z3 regress with their default configurations.

Because Sundance always produces proofs, we run Z3 and cvc5 with proof production enabled. We also report Z3 without proofs, as proof production is a significant overhead. Alt-Ergo does not produce proofs; it runs with its default options, but we have to translate the inputs to its SMT-LIB dialect.

We also ran SMTInterpol 2.5 [24], which supports the logics and features used by Verus, on the two Verus benchmark sets. It solves only 17.7% of the development set and 14.2% of the held-out set within 60 s, so we omit it from the rest of the evaluation.

RQ1: Verus

Figure 4 shows the results on the two Verus benchmark sets. Apart from Z3, the solvers perform comparably. Within 60 s, Sundance solves 83.0% of the development set, compared with 88.4% for cvc5, 91.8% for Z3 with proofs, and 79.8% for Alt-Ergo; on the held-out set, the corresponding numbers are 90.2%, 95.3%, 97.7%, and 82.8%. Z3 without proofs solves 99.8% of both sets.

Percentage of Verus queries solved within a given time budget

Figure 4. Percentage of Verus queries solved within a given time budget. Sundance, Z3 (proofs), and cvc5 (proofs) produce proofs; Z3 and Alt-Ergo do not.

At short time budgets, Sundance is faster than every solver except Z3 without proofs. Within 1 s, it solves 70.3% of the development set and 75.4% of the held-out set, compared with 67.5% and 62.1% for Z3 with proofs, 64.4% and 60.7% for cvc5, and 60.2% and 54.1% for Alt-Ergo. We believe this is because Sundance does minimal preprocessing.

We attribute Z3’s lead to two factors. First, Z3 has mature quantifier instantiation heuristics, such as eager instantiation and relevancy propagation, that Sundance does not yet implement (§ 10). Second, the benchmarks are biased towards Z3 in two ways. The verifiers themselves are built around Z3: their encodings, pattern choices, and solver options have been tuned to its heuristics (§ 10). More fundamentally, every query comes from a project that was already verified with Z3, so each query is, by construction, one that Z3 solves; a query Z3 could not solve would have been rewritten by the developer before the project was committed.

RQ2: Dafny and F⋆F^\star

On Dafny (Figure 5(a)), Sundance solves 73.7% of the queries within 60 s, more than cvc5 (69.8%), Alt-Ergo (70.4%), and Z3 with proofs (66.5%), while Z3 without proofs solves 98.0%.

Percentage of Dafny and F⋆ queries from Mariposa solved within a given time budget

Figure 5. Percentage of Dafny and F⋆ queries from Mariposa solved within a given time budget. Sundance, Z3 (proofs), and cvc5 (proofs) produce proofs; Z3 and Alt-Ergo do not.

The F⋆F^\star results (Figure 5(b)) have a distinctive elbow. Most solvers solve 40–50% of the queries within about a second and a few more after that, while Z3 solves most of the rest after about 4 s. These more challenging queries come from DICE⋆\mathrm{DICE}^\star, whose queries are very large (a median of 14 MB) and take several seconds just to parse and preprocess. On DICE⋆\mathrm{DICE}^\star, Sundance solves 25.6% of the queries within 60 s, more than cvc5 (9.0%) and Alt-Ergo (22.7%), whereas Z3 solves 96.8%. On the other F⋆F^\star project, vWasm, the solvers are again comparable

(Sundance 84.8%, Alt-Ergo 92.5%, cvc5 96.4%, Z3 98.8%). Overall, Sundance solves 56.7% of the F⋆F^{\star} queries, between cvc5 (54.9%) and Alt-Ergo (59.3%).

Unlike on Verus and Dafny, enabling proofs barely affects Z3 on F⋆F^{\star} (97.8% without proofs, 97.7% with). We believe Z3’s advantage on these queries comes from its e-matching techniques [58], which keep matching efficient over the very large sets of terms in DICE⋆^{\star}; we discuss adopting them in § 10.

RQ3: Varying Modules

To evaluate Sundance’s modularity, we replace one module at a time: the e-graph with Semper [32], the SAT solver with MiniSat [36] (Sec. B), and the arithmetic solver with Z3’s. Each swap required no changes to the rest of the solver. Figure 6 shows the results. Every variant solves fewer queries than the default configuration on every benchmark set. Within 60 s, the default configuration solves 87.4% of the Verus queries and 70.0% of the Dafny and F⋆F^{\star} queries, compared with 85.8% and 66.2% with Z3’s arithmetic solver, 83.5% and 65.9% with MiniSat, and 79.4% and 56.4% with Semper.

Percentage of queries solved within a given time budget by Sundance’s default configuration and by variants that replace one module

Figure 6. Percentage of queries solved within a given time budget by Sundance’s default configuration and by variants that replace one module: the Semper e-graph, the MiniSat SAT solver, or Z3’s arithmetic solver.

Each variant is slower for a different reason. MiniSat is a much simpler SAT solver than CaDiCaL and lacks many of its modern techniques. Semper is designed for equality saturation workloads, rather than for the incremental, backtracking use of an e-graph in an SMT solver. Semper’s restore deletes the nodes created since the snapshot, whereas Sundance expects terms to persist across backtracking, so the adapter re-inserts every term registered above the restore point after each restore (§ 4). Profiling attributes 56% of a quantifier instantiation round to this re-insertion. Z3’s arithmetic solver is fast on its own, but its API does not match Sundance’s incremental use: keeping it synchronized with the SAT solver’s assignments and backtracking requires redundant work that Sundance’s own solver avoids.

Related Work

SMT Solving. Early program verifiers such as ESC/Java [41] used verification-specific provers like Simplify [33]. Simplify’s e-graph and pattern-based quantifier instantiation [63] became the model for later SMT solvers and inspired Sundance’s matching algorithm. Verifiers later moved to general-purpose SMT solvers, largely for their performance. Sundance revisits Simplify’s focus on verification while building on modern components such as CDCL SAT solving and efficient proof formats. Alt-Ergo [26] is a modern SMT solver designed for program verification and is used by Why3 [15] and Frama-C [49]; we compare against it in § 8. SMTInterpol [24] supports the logics and features used by Verus, but its main focus is on interpolant generation; it solves few of our Verus queries (§ 8). Other SMT solvers [25, 28, 34, 48, 65] lack features required by program verification.

Proof Production. Several SMT solvers can produce proof certificates that allow unsatisfiability results to be checked independently. Z3 produces proofs in a natural-deduction style format [60] that is specific to Z3, coarse-grained, and does not cover all of its theories and features. cvc5 produces proofs in several formats, including the cooperating proof calculus (CPC) [8] and Alethe [72]. CPC is formalized in the Eunoia logical framework and checked by Ethos [71] (written in C++) or by Logos [70] (written in Lean). Alethe proofs can be checked with Carcara [6], but Alethe does not support as many theories as CPC. In general, proof production adds overhead, and may require some optimizations to be disabled. As a result, proofs are rarely checked in practice: program verifiers do not check solver proofs. Sundance instead uses eDRAT [46], which extends the clausal DRAT format used by SAT solvers [45]. A clausal proof is cheap to produce, and its propositional part can be checked with existing SAT proof tools. We describe Sundance’s proof production in § 7. A limitation of eDRAT is its inability to capture preprocessing and simplification rules, but Sundance does not rely on heavy preprocessing, only on conversion to CNF.

Understanding and Debugging Solver Behavior. Because general-purpose solvers are opaque, a range of tools help users understand why a query fails or behaves unpredictably. The Axiom Profiler [10] and SMTScope [40] analyze Z3’s quantifier instantiation traces to expose matching loops and expensive axioms. Verifier-level guides and tools help users diagnose and repair failing proofs [23, 31, 37], and Cazamariposas [92] automatically locates the sources of instability [90] in a query. These tools work around the solver: they reconstruct its behavior from traces tied to Z3’s internals, which change across versions. Sundance instead aims to be transparent by design, with few heuristics and a small codebase that users can inspect directly.

Future Work

We outline several major avenues for future research and discuss how Sundance can facilitate them.

Instability. A major challenge in SMT solvers is instability, where semantically irrelevant changes in the input can lead to large variations in solver performance [90]. This is especially frustrating in verification, where a developer’s proof may fail because of a slight change in the input, such as renaming a variable. Prior work mitigates instability by normalizing queries [5, 86], pruning irrelevant assertions [30, 89], choosing patterns or restructuring proofs [29, 47, 52, 57], or debugging unstable queries after the fact [10, 19, 92]. These techniques help, but none fully solves the problem, and all of them treat the solver as a black box. Recent work has shown that stability can also be improved inside the solver, by modifying Z3’s quantifier instantiation heuristics [20]. In a large solver, however, such changes must contend with many interacting components. Because Sundance is small and relies on few heuristics, it offers a platform for controlling the sources of instability directly.

Quantifier Heuristics. Closely related to instability are the heuristics that govern quantifier instantiation [20]. Beyond e-matching, Z3 relies on several heuristics that decide which instances are created, when they are created, and how long they are kept. We plan to explore Z3 heuristics such as relevancy propagation [59] and eager instantiation in Sundance. In addition, Z3 uses garbage collection to discard terms when the solver backtracks. We have not yet implemented such garbage collection in Sundance, but we plan to do so in the future.

Tailoring Solvers to Verifiers. Verifiers and their solvers are tightly coupled, but only in one direction: verifiers tune their encodings, patterns, and options to Z3’s heuristics, while Z3 knows nothing about the verifier. This coupling is fragile; for instance, Verus’s upgrade from Z3 4.12.5 to 4.16.0 broke proofs in its standard library, its tests, and six downstream projects [67]. With a small, modular solver, a verifier could control its own version of Sundance, control when it changes, and adapt the solver to its encoding: for example, instantiation heuristics aware of Verus’s encoding. We see Sundance as a step towards codesigning verifiers and their solvers.

Conclusion

Sundance is a new open-source SMT solver specialized for program verification. For reliability, Sundance is written in a safe programming language and it is designed to be proof-producing from the start. One of our goals for Sundance is to stay simple and modular, and achieve comparable performance to state-of-the-art solvers on our target applications. We hope Sundance will pave the way for more research in SMT solving, and help researchers and practitioners understand and control automation in verification tools.

Disclosure of AI Use. We discuss our use of AI in Appendix § 13.

Data Availability. Sundance is open source at https://github.com/yaspar-org/Sundance-SMT.

Acknowledgments. We would like to thank Clark Barrett, Zachary Battleman, Armin Biere, Nikolaj Bjørner, Martin Nyx Brain, Cayden Codel, Katalin Fazekas, Robert Jones, Rustan Leino, Florian Pollitt, Long Qian, Giles Reger, Andy Reynolds, and Max Willsey for insightful discussions and feedback during the development of Sundance. We would also like to thank Federico Mora for providing feedback on an earlier draft of this paper.

This work was supported in part by funding from AFRL and DARPA under Agreement FA8750-24-9-1000, the Future Enterprise Security initiative at Carnegie Mellon CyLab (FutureEnterprise@CyLab), and support from the Beneficial AI Foundation.

Bibliography

Use of AI

We began working on this project in May 2025. At that time, we found AI tools to not be significantly helpful except for asking questions and generating small, boilerplate code. The core of Sundance was mostly developed by the end of 2025 in this manner with a very small amount of AI-generated code. We open-sourced Sundance shortly thereafter at the start of 2026. After open-sourcing the code, all changes to Sundance were done via a pull request to the GitHub repository and required at least one human review before being merged. Starting around March 2026, we found AI tools to be significantly more helpful for generating code, refactoring, and providing suggestions for improvements. As more powerful models became available, the scope of AI assistance in our development process expanded. For instance, some optimizations to the incremental arithmetic solver were found with the assistance of AI tools. The role of AI tools has surprised us in its rapid evolution and increasing impact on our development workflow. We believe AI tools will continue to play a significant role in the future development of SMT solvers.

We have used AI tools to assist in brainstorming, creating figures, drafting, and editing the text of the paper. Any text generated by AI tools was reviewed and edited by the authors both for style and accuracy.

Swapping the SAT Solver

As described in § 3, Sundance supports MiniSat [36] (via MiniSatUP [43]) as an alternative to CaDiCaL [68], with MiniSat’s initial variable phase set to true to match CaDiCaL’s default rather than MiniSat’s default of false. Figure 7 compares the two SAT solvers on the Verus development set (§ 8.1), using Z3’s arithmetic solver as the arithmetic backend in both configurations. This differs from § 8, which uses Sundance’s own arithmetic solver except in the Z3-arithmetic variant of § 8.3, so the numbers below are not directly comparable with those in § 8. The results show that Sundance solves slightly fewer Verus queries with MiniSat than with CaDiCaL as the backend SAT solver: 2,138 (83.0%) with CaDiCaL and 2,070 (80.4%) with MiniSat, out of 2,576; 69 are solved only with CaDiCaL and one only with MiniSat. The right panel of Figure 7 isolates the effect of initial phase by running CaDiCaL with different phase settings, showing that the false phase alone accounts for a large slowdown and additional timeouts: with the false phase, Sundance solves only 1,436 queries (55.7%).

Per-query solving time on Verus queries

Figure 7. Per-query solving time on Verus queries, in seconds, with Z3’s arithmetic solver as the arithmetic backend; points above the diagonal are slower on the vertical axis. Left: Sundance with CaDiCaL (xx-axis) vs. Sundance with MiniSat (yy-axis). Right: an experiment using CaDiCaL in both configurations, with its initial variable phase set to its default of true (phase1, xx-axis) vs. set to false (phase0, yy-axis), showing that choice of initial phase affects performance.

References

  1. [1]Amazon Trusted Solver team: Yaspar-IR: Representations of SMT scripts. https://github.com/yaspar-org/yaspar-ir (2026), version 2.7.7. Accessed October 2026
  2. [2]Amazon Trusted Solver team: Yaspar: Yet another SMT parser. https://github.com/yaspar-org/yaspar (2026), version 2.7.2. Accessed October 2026
  3. [3]Amazon Web Services: AWS Encryption SDK. https://github.com/aws/aws-encryption-sdk-dafny (2019), formally verified cryptographic library in Dafny. Accessed November 2026
  4. [4]Amazon Web Services: Introducing Nitro Isolation Engine: Transparency through mathematics. AWS re:Invent 2025 (2025)
  5. [5]Amrollahi, D., Preiner, M., Niemetz, A., Reynolds, A., Charikar, M., Tinelli, C., Barrett, C.: Towards SMT solver stability via input normalization. In: Formal Methods in Computer-Aided Design (FMCAD) (2025). https://doi.org/10.34727/2025/isbn.978-3-85448-084-6_14
  6. [6]Andreotti, B., Lachnitt, H., Barbosa, H.: Carcara: An efficient proof checker and elaborator for SMT proofs in the Alethe format. In: Tools and Algorithms for the Construction and Analysis of Systems (TACAS) (2023). https://doi.org/10.1007/978-3-031-30823-9_19
  7. [7]Barbosa, H., Barrett, C., Brain, M., Kremer, G., Lachnitt, H., Mann, M., Mohamed, A., Mohamed, M., Niemetz, A., Nötzli, A., Ozdemir, A., Preiner, M., Reynolds, A., Sheng, Y., Tinelli, C., Zohar, Y.: cvc5: A versatile and industrial-strength SMT solver. In: Tools and Algorithms for the Construction and Analysis of Systems (TACAS) (2022)
  8. [8]Barbosa, H., Reynolds, A., Kremer, G., Lachnitt, H., Niemetz, A., Nötzli, A., Ozdemir, A., Preiner, M., Viswanathan, A., Viteri, S., Zohar, Y., Tinelli, C., Barrett, C.: Flexible proof production in an industrial-strength SMT solver. In: International Joint Conference on Automated Reasoning (IJCAR) (2022). https://doi.org/10.1007/978-3-031-10769-6_3
  9. [9]Barrett, C., Sebastiani, R., Seshia, S.A., Tinelli, C.: Satisfiability modulo theories. In: Handbook of Satisfiability, chap. 33, pp. 1267–1329. IOS Press, second edn. (2021)
  10. [10]Becker, N., Müller, P., Summers, A.J.: The Axiom Profiler: Understanding and debugging SMT quantifier instantiations. In: Tools and Algorithms for the Construction and Analysis of Systems (TACAS) (2019)
  11. [11]Biere, A., et al.: CaDiCaL 3.0.1 release notes. https://github.com/arminbiere/cadical/blob/master/NEWS.md (2026), “Less disruptive clause import with user propagators due to elevate.” Accessed October 2026
  12. [12]Bjørner, N., Eisenhofer, C., Gurfinkel, A., Lopes, N.P., de Moura, L., Nachmanson, L., Wintersteiger, C.: Z3 internals (draft). https://z3prover.github.io/papers/z3internals.html (2026), accessed October 2026
  13. [13]Bjørner, N., Nachmanson, L.: Arithmetic solving in Z3. In: Computer Aided Verification (CAV) (2024)DOI
  14. [14]Bland, R.G.: New finite pivoting rules for the simplex method. Mathematics of Operations Research 2(2), 103–107 (1977)
  15. [15]Bobot, F., Filliâtre, J.C., Marché, C., Paskevich, A.: Why3: Shepherd your herd of provers. In: International Workshop on Intermediate Verification Languages (Boogie) (2011)
  16. [16]Bosamiya, J., Lim, W.S., Parno, B.: Provably-safe multilingual software sandboxing using WebAssembly. In: USENIX Security Symposium (USENIX Security) (2022)
  17. [17]Bright, C., Kotsireas, I., Heinle, A., Ganesh, V.: Complex Golay pairs up to length 28: A search via computer algebra and programmatic SAT. Journal of Symbolic Computation 102, 153–172 (2021). https://doi.org/10.1016/j.jsc.2019.10.013
  18. [18]Bromberger, M.: Decision procedures for linear arithmetic. Ph.D. thesis, Saarland University (2019)DOI
  19. [19]Cebeci, C., Bjørner, N., Candea, G., Pit-Claudel, C.: A conjecture regarding SMT instability. In: International Workshop on Satisfiability Modulo Theories (SMT) (2025)
  20. [20]Cebeci, C., Bjørner, N., Candea, G., Pit-Claudel, C.: A deeper look at depth: Stable generation accounting for quantifier reasoning (2026), https://arxiv.org/abs/2609.26345
  21. [21]Chakarov, A., Geldenhuys, J., Heck, M., Hicks, M., Huang, S., Jaloyan, G.A., Joshi, A., Leino, R., Mayer, M., McLaughlin, S., Mritunjai, A., Pit-Claudel, C., Porncharoenvase, S., Rabe, F., Rapoport, M., Reger, G., Roux, C., Rungta, N., Salkeld, R., Schlaipfer, M., Schoepe, D., Schwarzen-truber, J., Tasiran, S., Tomb, A., Torlak, E., Tristan, J., Wagner, L., Whalen, M., Willems, R., Xiang, J., Byun, T.J., Cohen, J., Wang, R., Jang, J., Rath, J., Syeda, H.T., Wagner, D., Yuan, Y.: Formally verified cloud-scale authorization. In: International Conference on Software Engineering (ICSE) (2025), https://www.amazon.science/publications/formally-verified-cloud-scale-authorization
  22. [22]Chen, X., Li, Z., Mesieck, L., Narayanan, V., Burtsev, A.: Atmosphere: Towards practical verified kernels in Rust. In: Workshop on Kernel Isolation, Safety and Verification (KISV) (2023). https://doi.org/10.1145/3625275.3625401
  23. [23]Cho, C., Zhou, Y., Bosamiya, J., Parno, B.: A framework for debugging automated program verification proofs via proof actions. In: Computer Aided Verification (CAV) (2024)DOI
  24. [24]Christ, J., Hoenicke, J., Nutz, A.: SMTInterpol: An interpolating SMT solver. In: International SPIN Workshop on Model Checking of Software (SPIN) (2012)DOI
  25. [25]Cimatti, A., Griggio, A., Schaafsma, B.J., Sebastiani, R.: The MathSAT5 SMT solver. In: Tools and Algorithms for the Construction and Analysis of Systems (TACAS) (2013)
  26. [26]Conchon, S., Coquereau, A., Iguernelala, M., Mebsout, A.: Alt-Ergo 2.2. In: International Workshop on Satisfiability Modulo Theories (SMT) (2018)
  27. [27]Cordeiro, L., Fischer, B., Marques-Silva, J.: SMT-based bounded model checking for embedded ANSI-C software. In: Automated Software Engineering (ASE) (2009). https://doi.org/10.1109/ASE.2009.63
  28. [28]Corzilius, F., Kremer, G., Junges, S., Schupp, S., Ábrahám, E.: SMT-RAT: An open source C++ toolbox for strategic and parallel SMT solving. In: Theory and Applications of Satisfiability Testing (SAT) (2015)DOI
  29. [29]Cutler, J.W., Torlak, E., Hicks, M.: Improving the stability of type soundness proofs in Dafny. In: Dafny Workshop (Dafny) (2024)
  30. [30]Dafny Maintainers: Prevent changes unrelated to a proof from changing the verification behavior of the proof. https://github.com/dafny-lang/dafny/pull/1612 (2021), accessed November 2026
  31. [31]Dafny Maintainers: Verification debugging when verification fails. https://dafny.org/dafny/DafnyRef/DafnyRef#sec-brittle-verification (2023), accessed November 2026
  32. [32]Delmas, R.: A semi-persistent E-graph with native AC canonization and leapfrog AC matching. In: EGRAPHS Workshop (2026), implementation: https://docs.rs/semi-persistent-egraph
  33. [33]Detlefs, D., Nelson, G., Saxe, J.B.: Simplify: a theorem prover for program checking. J. ACM 52(3), 365–473 (2005). https://doi.org/10.1145/1066100.1066102
  34. [34]Dutertre, B.: Yices 2.2. In: Computer Aided Verification (CAV) (2014)
  35. [35]Dutertre, B., de Moura, L.: A fast linear-arithmetic solver for DPLL(T). In: Computer Aided Verification (CAV) (2006)
  36. [36]Één, N., Sörensson, N.: An extensible SAT-solver. In: Theory and Applications of Satisfiability Testing (SAT) (2004)
  37. [37]F* Developers: Profiling Z3 and solving proof performance issues. https://fstar-lang.org/tutorial/book/under_the_hood/uth_smt.html#profiling-z3-and-solving-proof-performance-issues (2026), accessed November 2026
  38. [38]Fazekas, K., Niemetz, A., Preiner, M., Kirchweger, M., Szeider, S., Biere, A.: IPASIR-UP: User propagators for CDCL. In: Theory and Applications of Satisfiability Testing (SAT) (2023). https://doi.org/10.4230/LIPIcs.SAT.2023.8
  39. [39]Ferraiuolo, A., Baumann, A., Hawblitzel, C., Parno, B.: Komodo: Using verification to disentangle secure-enclave hardware from software. In: Symposium on Operating Systems Principles (SOSP) (2017). https://doi.org/10.1145/3132747.3132782
  40. [40]Fiala, J., Müller, P.: SMTScope: Automated and efficient analysis of SMT traces. In: Tools and Algorithms for the Construction and Analysis of Systems (TACAS) (2026). https://doi.org/10.1007/978-3-032-22752-2_12
  41. [41]Flanagan, C., Leino, K.R.M., Lillibridge, M., Nelson, G., Saxe, J.B., Stata, R.: Extended static checking for Java. SIGPLAN Not. 37(5), 234–245 (2002). https://doi.org/10.1145/543552.512558
  42. [42]Hance, T., Lattuada, A., Hawblitzel, C., Howell, J., Johnson, R., Parno, B.: Storage systems are distributed systems (so verify them that way!). In: USENIX Symposium on Operating Systems Design and Implementation (OSDI) (2020)
  43. [43]Hao, C.: MiniSatUP. https://github.com/hchenqide/minisat/tree/minisatup (2025), accessed Oct. 2026
  44. [44]Hawblitzel, C., Howell, J., Kapritsos, M., Lorch, J.R., Parno, B., Roberts, M.L., Setty, S., Zill, B.: IronFleet: Proving practical distributed systems correct. In: Symposium on Operating Systems Principles (SOSP) (2015)DOI
  45. [45]Heule, M.J.H.: The DRAT format and DRAT-trim checker (2016), https://arxiv.org/abs/1610.06229
  46. [46]Hitarth, S., Codel, A., Lachnitt, H., Dutertre, B.: Extending DRAT to SMT. In: Formal Methods in Computer-Aided Design (FMCAD) (2024). https://doi.org/10.34727/2024/isbn.978-3-85448-065-8
  47. [47]Ho, S., Pit-Claudel, C.: Incremental proof development in Dafny with module-based induction. In: Dafny Workshop (Dafny) (2024)arxiv.org/abs/2401.16233
  48. [48]Hyvärinen, A.E.J., Marescotti, M., Alt, L., Sharygin, N.: OpenSMT2: An SMT solver for multi-core and cloud computing. In: Theory and Applications of Satisfiability Testing (SAT) (2016)DOI
  49. [49]Kirchner, F., Kosmatov, N., Prevosto, V., Signoles, J., Yakobowski, B.: Frama-C: A software analysis perspective. Formal Aspects of Computing 27(3), 573–609 (2015). https://doi.org/10.1007/s00165-014-0326-7
  50. [50]Lattuada, A., Hance, T., Bosamiya, J., Brun, M., Cho, C., LeBlanc, H., Srinivasan, P., Achermann, R., Chajed, T., Hawblitzel, C., Howell, J., Lorch, J.R., Padon, O., Parno, B.: Verus: A practical foundation for systems verification. In: Symposium on Operating Systems Principles (SOSP) (2024)DOI
  51. [51]Lattuada, A., Hance, T., Cho, C., Brun, M., Subasinghe, I., Zhou, Y., Howell, J., Parno, B., Hawblitzel, C.: Verus: Verifying Rust programs using linear ghost types. In: Object-Oriented Programming Systems, Languages, and Applications (OOPSLA) (2023)DOI
  52. [52]Leino, K.R.M., Pit-Claudel, C.: Trigger selection strategies to stabilize program verifiers. In: Computer Aided Verification (CAV) (2016)DOI
  53. [53]Leino, K.R.M.: Dafny: An automatic program verifier for functional correctness. In: Logic for Programming, Artificial Intelligence, and Reasoning (LPAR) (2010)
  54. [54]Leino, K.R.M.: Personal communication (2025)
  55. [55]Li, J., Lattuada, A., Zhou, Y., Cameron, J., Howell, J., Parno, B., Hawblitzel, C.: Linear types for large-scale systems verification. In: Object-Oriented Programming Systems, Languages, and Applications (OOPSLA) (2022)DOI
  56. [56]Lin, Z., McLoughlin, M., Singh, P., Brennan-Jones, R., Hitchcox, P., Gancher, J., Parno, B.: Towards practical, end-to-end formally verified X.509 certificate validators with Verdict. In: USENIX Security Symposium (USENIX Security) (2025)DOI
  57. [57]McLaughlin, S., Jaloyan, G.A., Xiang, T., Rabe, F.: Enhancing proof stability. In: Dafny Workshop (Dafny) (2024)
  58. [58]de Moura, L., Bjørner, N.: Efficient e-matching for SMT solvers. In: Conference on Automated Deduction (CADE) (2007)
  59. [59]de Moura, L., Bjørner, N.: Relevancy propagation. Tech. rep., Microsoft Research (2007), https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/tr-2007-140.pdf
  60. [60]de Moura, L., Bjørner, N.: Proofs and refutations, and Z3. In: LPAR Workshops (2008), https://ceur-ws.org/Vol-418/paper10.pdf
  61. [61]de Moura, L., Bjørner, N.: Z3: An efficient SMT solver. In: Tools and Algorithms for the Construction and Analysis of Systems (TACAS) (2008). https://doi.org/10.1007/978-3-540-78800-3_24
  62. [62]Muduli, S.K., Roy, S.: Satisfiability modulo fuzzing: A synergistic combination of SMT solving and fuzzing. In: Object-Oriented Programming Systems, Languages, and Applications (OOPSLA) (2022). https://doi.org/10.1145/3563332
  63. [63]Nelson, C.G.: Techniques for program verification. Ph.D. thesis, Stanford University, Stanford, CA, USA (1980)
  64. [64]Nelson, G., Oppen, D.C.: Fast decision procedures based on congruence closure. J. ACM 27(2), 356–364 (1980). https://doi.org/10.1145/322186.322198
  65. [65]Niemetz, A., Preiner, M.: Bitwuzla. In: Computer Aided Verification (CAV) (2023). https://doi.org/10.1007/978-3-031-37703-7_1
  66. [66]Nieuwenhuis, R., Oliveras, A.: Proof-producing congruence closure. In: Term Rewriting and Applications (RTA) (2005)DOI
  67. [67]Parno, B.: Upgrade to Z3 4.16.0. https://github.com/verus-lang/verus/pull/2578 (2026), Verus pull request #2578. Accessed November 2026
  68. [68]Pollitt, F., Fleury, M., Fazekas, K., Froleyks, N., Schidler, A., Schreiber, D., Biere, A.: CaDiCaL 3.0. In: Theory and Applications of Satisfiability Testing (SAT) (2026). https://doi.org/10.4230/LIPIcs.SAT.2026.40
  69. [69]Protzenko, J., Parno, B., Fromherz, A., Hawblitzel, C., Polubelova, M., Bhargavan, K., Beurdouche, B., Choi, J., Delignat-Lavaud, A., Fournet, C., Kulatova, N., Ramanamandandro, T., Rastogi, A., Swamy, N., Wintersteiger, C., Zanella-Béguelin, S.: EverCrypt: A fast, verified, cross-platform cryptographic provider. In: Symposium on Security and Privacy (S&P) (2020)
  70. [70]Reynolds, A.: Logos: A verified proof checker for SMT solvers. https://github.com/vc5/logos (2026), accessed November 2026
  71. [71]Reynolds, A., Schurr, H.J., Soldevila, M., Barbosa, H., Barrett, C., Tinelli, C.: Ethos: A fast proof checker for the Eunoia logical framework. In: International Joint Conference on Automated Reasoning (IJCAR) (2026). https://doi.org/10.1007/978-3-032-32589-1_19
  72. [72]Schurr, H.J., Fleury, M., Barbosa, H., Fontaine, P.: Alethe: Towards a generic SMT proof format (extended abstract). In: Workshop on Proof eXchange for Theorem Proving (PxTP) (2021). https://doi.org/10.4204/EPTCS.336.6
  73. [73]Shah, A.: Adding benchmarks from Verus (a Rust verification tool). GitHub Pull Request #12 (2025), https://github.com/SMT-LIB/benchmark-submission/pull/12, merged on April 17, 2025
  74. [74]Singh, P., Gancher, J., Parno, B.: OwlC: Compiling security protocols to verified, secure, high-performance libraries. In: USENIX Security Symposium (USENIX Security) (2025)DOI
  75. [75]Sun, X., Ma, W., Gu, J.T., Ma, Z., Chajed, T., Howell, J., Lattuada, A., Padon, O., Suresh, L., Szeker es, A., Xu, T.: Anvil: Verifying liveness of cluster management controllers. In: USENIX Symposium on Operating Systems Design and Implementation (OSDI) (2024)
  76. [76]Swamy, N., Hrițcu, C., Keller, C., Rastogi, A., Delignat-Lavaud, A., Forest, S., Bhargavan, K., Fournet, C., Strub, P.Y., Kohlweiss, M., Zinzindohoue, J.K., Zanella-Béguelin, S.: Dependent types and multi-monadic effects in F*. In: Principles of Programming Languages (POPL) (2016)
  77. [77]Swamy, N., Ramananan dro, T., Rastogi, A., Spridionova, I., Ni, H., Malloy, D., Vazquez, J., Tang, M., Cardona, O., Gupta, A.: Hardening attack surfaces with formally proven binary format parsers. In: Programming Language Design and Implementation (PLDI) (2022)DOI
  78. [78]Tao, Z., Rastogi, A., Gupta, N., Swamy, K., Thakur, A.V.: DICE*: A formally verified implementation of DICE measured boot. In: USENIX Security Symposium (USENIX Security) (2021)
  79. [79]Tate, R., Stepp, M., Tatlock, Z., Lerner, S.: Equality saturation: a new approach to optimization. In: Principles of Programming Languages (POPL) (2009). https://doi.org/10.1145/1480881.1480915
  80. [80]The Asterinas Developers: vostd: Formally verifying OSTD, the standard library of the Asterinas kernel, with Verus. https://github.com/asterinas/vostd (2026), accessed October 2026
  81. [81]Tseitlin, G.S.: On the complexity of derivation in propositional calculus. In: Siekmann, J.H., Wrightson, G. (eds.) Automation of Reasoning 2: Classical Papers on Computational Logic 1967–1970, pp. 466–483. Springer Berlin Heidelberg (1983). https://doi.org/10.1007/978-3-642-81955-1_28
  82. [82]VMware Research: Verified SplinterDB. https://github.com/vmware-labs/verified-betrfs/tree/main/Splinter (2025), accessed Feb. 2025
  83. [83]Willsey, M., Nandi, C., Wang, Y.R., Flatt, O., Tatlock, Z., Panchekha, P.: egg: Fast and extensible equality saturation. In: Principles of Programming Languages (POPL) (2021). https://doi.org/10.1145/3434304
  84. [84]Winterer, D., Zhang, C., Su, Z.: Validating SMT solvers via semantic fusion. In: Programming Language Design and Implementation (PLDI) (2020). https://doi.org/10.1145/3385412.3385985
  85. [85]Zhang, J., Xu, X., Zou, Y., Tang, Z., Wan, X., Hu, K., Wang, S., Xu, W., Wang, D., Chen, H., Huang, L., Yan, S., Tamir, Y., Luo, Y., Wang, X., Yu, H., Wang, Z., Tian, H., Zhou, D.: CortenMM: Efficient memory management with strong correctness guarantees. In: Symposium on Operating Systems Principles (SOSP) (2025). https://doi.org/10.1145/3731569.3764836
  86. [86]Zhang, X., Zhao, M., Chen, S., Zhang, J., Cai, S.: Improving stability of SMT solvers via context-driven normalization. In: Computer Aided Verification (CAV) (2026)DOI
  87. [87]Zhang, Y., Wang, Y.R., Flatt, O., Cao, D., Zucker, P., Rosenthal, E., Tatlock, Z., Willsey, M.: Better together: Unifying Datalog and equality saturation. In: Programming Language Design and Implementation (PLDI) (2023). https://doi.org/10.1145/3591239
  88. [88]Zhang, Y., Wang, Y.R., Willsey, M., Tatlock, Z.: Relational e-matching. In: Principles of Programming Languages (POPL) (2022). https://doi.org/10.1145/3498696
  89. [89]Zhou, Y., Bosamiya, J., Li, J., Heule, M., Parno, B.: Context pruning for more robust SMT-based program verification. In: Formal Methods in Computer-Aided Design (FMCAD) (2024)
  90. [90]Zhou, Y., Bosamiya, J., Takashima, Y., Li, J., Heule, M., Parno, B.: Mariposa: Measuring SMT instability in automated program verification. In: Formal Methods in Computer-Aided Design (FMCAD) (2023)DOI
  91. [91]Zhou, Y., Gibson, S., Cai, S., Winchell, M., Parno, B.: Galápagos: Developing verified low-level cryptography on heterogeneous hardware. In: Computer and Communications Security (CCS) (2023)DOI
  92. [92]Zhou, Y., Shah, A., Lin, Z., Heule, M., Parno, B.: Cazamariposas: Automated instability debugging in SMT-based program verification. In: Conference on Automated Deduction (CADE) (2025)DOI
  93. [93]Zhou, Z., Anjali, Chen, W., Gong, S., Hawblitzel, C., Cui, W.: VeriSMo: a verified security module for confidential VMs. In: USENIX Symposium on Operating Systems Design and Implementation (OSDI) (2024)

Paper details

vlnc:W_jqwjwsdn
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

AI tools

View statement
Looking for related papers…
Contents