Satisfiability Modulo Theories (SMT)

Concept

Satisfiability Modulo Theories (SMT) is used in UCLID5-based formal verification by solving verification-condition formulas over multiple theories such as uninterpreted data, integers, bit vectors, arrays, and other typed model elements. In the cited UCLID5 processor-verification workflow, SMT solvers report unsatisfiable, satisfiable, or indeterminate results, which respectively support proof, counterexample generation, or a need for less complex or more precise modeling.

First seen 5/26/2026

Last seen 5/26/2026

Evidence 3 chunks

Wiki v1

WIKI

Overview

In the UCLID5 verification workflow described in the evidence, Satisfiability Modulo Theories (SMT) is the solving technology invoked after UCLID5 generates verification conditions. Those verification conditions are formulas in a logic that supports multiple data types, described as theories, used in the model. The generated formulas are typically negations of the properties the user wants to verify.

Role in verification

READ FULL ARTICLE →

NEIGHBORHOOD

No graph connections found for this entity yet. It may appear in future ingestion runs.

explore full graph →

RELATIONSHIPS

1 connections

UCLID5 ← uses 100% 1e

UCLID5 generates verification conditions expressed as SMT formulas and invokes an SMT solver.

LINKED ENTITIES

4 links

UCLID5 invokes_smt_solver The evidence states that UCLID5 generates verification conditions and then invokes a satisfiability modulo theories solver.

Z3 is_smt_solver_used_with The evidence states that the reported work used the Z3 solver as the SMT solver with UCLID5.

Microsoft Research developed_z3_solver The evidence describes Z3 as a solver developed at Microsoft Research.

Uninterpreted Functions used_in_smt_modeling The evidence discusses uninterpreted functions as part of UCLID5 models and notes that SMT solver satisfying assignments include values for uninterpreted functions.

CITATIONS

12 sources

12 citations — click to expand

[1] UCLID5 generates verification conditions as formulas in a logic supporting multiple data types, called theories, and invokes an SMT solver. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5

[2] Verification-condition formulas are typically negations of the properties being verified. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5

[3] In the reported work, UCLID5 used Z3 version 4.5.0 as the SMT solver, and Z3 is described as developed at Microsoft Research. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5

[4] An SMT solver invoked by UCLID5 can return unsatisfiable, satisfiable, or indeterminate. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5

[5] For negated verification formulas, unsatisfiability indicates that the desired verification condition holds. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5

[6] When a formula is satisfiable, the SMT solver provides concrete values for data elements, including uninterpreted functions, and UCLID5 uses them to generate a counterexample. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5

[7] A counterexample may indicate a true design error, an inaccurate or overly abstract model, or an incorrectly expressed verification condition. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5

[8] An indeterminate result means the solver found no satisfying solution but could not prove unsatisfiability, typically because the model is too complex or needs more sophisticated reasoning. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5

[9] The report recommends using the most abstract model possible that still captures the properties needed for correctness. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5

[10] Data in the cited models can be represented as uninterpreted terms, integers, or bit vectors, while ALU and data operations can range from uninterpreted functions to precise arithmetic. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5

[11] The ALU increment/decrement property was expressed as an axiom imposed on an otherwise uninterpreted ALU function and provided as a constraint to the SMT solver. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5

[12] The SMT solver could not effectively use that axiom, making verification at that abstraction level unsuccessful and requiring the SW variant to model data as integers or bit vectors with precise addition. Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5