Overview

Satisfiability Modulo Theories (SMT) is described in the provided sources as a core tool in formal verification. The SMT-LIB specification language can be used to interact with theorem-proving or SMT-solving software, while higher-level interfaces may make complex SMT formulae easier to specify. [C1]

In the SMT-LIB2 representation described by Antmicro, an SMT problem is expressed in a Lisp-like language in terms of functions and constraints, called assertions in SMT terminology. Variables are represented as 0-argument functions. [C2]

SMT-LIB2 problem structure

A typical SMT-LIB2 bit-vector problem can declare bit-vector symbols, assert constraints over them, and then call check-sat. In Antmicro’s example, the solver is asked to solve an integer-factorization-style problem over 32-bit bit vectors using declarations such as declare-fun, assertions such as equality and multiplication constraints, and a final (check-sat). A compliant solver can report that the constraints are satisfiable and can then be queried for a concrete model, such as values for x and y. [C3]

SMT-LIB2 also distinguishes operations by theory and operator semantics. For bit vectors, signedness is determined by the operation rather than by a signed or unsigned bit-vector type. For example, Antmicro cites bvslt as signed less-than and bvult as unsigned less-than. [C4]

Solvers

The evidence identifies z3 and cvc5 as SMT solvers used in the context of Verilator constrained randomization. [C5]

SMT solvers are also characterized as typically deterministic. In Verilator’s constrained-randomization implementation, Antmicro notes that determinism is usually desirable, but it can be a challenge when randomized outputs are wanted. Their implementation adds an artificial random-hash constraint over selected output bits to encourage exploration of different parts of the solution space. [C6]

Use in Verilator constrained randomization

Verilator’s constrained-randomization flow uses SMT solving to turn SystemVerilog randomization constraints into solver queries. Antmicro describes an upstream Verilator solution that converts SystemVerilog expressions to SMT-LIB2, using $sformatf to build solver-digestible strings for subexpressions. For example, a SystemVerilog expression of the form LHS && RHS is converted to an SMT-LIB-style (and ...) expression. Verilator constant folding normalizes nested expressions into a single $sformatf call with runtime-filled fields. [C7]

In this flow, each SystemVerilog constraint is converted to a separate function that is called when constraints are gathered. Antmicro also notes current and future implementation concerns: state-dependent and conditional constraints, arrays, and the distinction between 1-bit vectors and booleans. In SMT-LIB2, booleans and 1-bit vectors are separate kinds and cannot be mixed, whereas Verilator currently does not distinguish them in the same way. [C8]

Use in processor verification

The EPEX processor-verification approach uses a formal ISA model together with SMT reasoning to generate an equivalent test program. EPEX then checks equivalence by executing the original and equivalent programs iteratively on two instances of the same processor design; the architectural states are expected to remain equal. The cited paper reports bug-finding results on the VexRiscv processor. [C9]

Other applications

The public context also describes SMT as useful outside hardware verification. One cited work formulates grammatical inference as an SMT problem, presenting encodings for deterministic finite automata and extensions for Moore and Mealy machines. [C10]