SMT-LIB is an international initiative that develops common languages, theory specifications, and benchmark collections for satisfiability modulo theories (SMT). Its best-known component is the SMT-LIB language, a standardized textual interface for expressing logical constraints and interacting with SMT solvers. The initiative supports interoperability between tools, reproducible experiments, and the systematic evaluation of automated reasoning systems. It is not itself a solver, nor does it prescribe a particular solving algorithm.
Purpose and scope
An SMT solver determines whether a logical formula has a satisfying interpretation under specified background theories, such as integer arithmetic, arrays, or fixed-width bit-vectors. This extends the Boolean satisfiability problem by giving mathematical meaning to operations such as addition, comparison, and array access.
For example, the constraints and are jointly satisfiable when is an integer, whereas adding makes them unsatisfiable. An SMT solver reasons about the arithmetic meaning of these expressions rather than treating each comparison as an unrelated Boolean variable.
SMT-LIB standardizes several distinct parts of this process:
- The expression language, used to represent terms, formulas, declarations, and commands.
- Background theories, which specify the meaning of built-in sorts and operations.
- Logics, which identify permitted combinations of theories and restrictions on formulas.
- Benchmarks, which supply problems for testing and comparing solvers.
These components serve different purposes. A theory defines mathematical meaning; a logic defines a class of admissible problems; a script directs a solver through a sequence of interactions.
Language and semantics
Terms, sorts, and formulas
SMT-LIB uses a parenthesized prefix notation based on S-expressions, familiar from Lisp. An addition is written (+ x 1), and a comparison is written (< x 5). Semicolons introduce comments extending to the end of a line.
The language is organized around a many-sorted logical framework. A sort identifies the domain of a term, such as Bool, Int, or Real. Sorts can also be parameterized: (_ BitVec 32) denotes 32-bit bit-vectors, while (Array Int Bool) denotes arrays indexed by integers with Boolean elements. This sort discipline plays a role analogous to a type system in a programming language.
In the established SMT-LIB 2 framework, formulas are Boolean terms within a many-sorted first-order logic with equality. The language includes Boolean connectives, function application, conditional expressions, local bindings, and quantifiers. A script may introduce additional sorts and function symbols.
For example:
(declare-const x Int)
(declare-fun f (Int) Int)
The first command introduces an integer constant whose value is to be determined. The second introduces a function from integers to integers without giving it a definition. Such an uninterpreted function must behave consistently as a mathematical function, but otherwise its interpretation is constrained only by the assertions in the problem.
Mathematical meaning
SMT-LIB distinguishes mathematical domains from machine-level representations. Int denotes mathematical integers, not a fixed-width machine integer type. Real denotes mathematical real numbers, not hardware floating-point values. Fixed-width arithmetic and floating-point operations use separate theories.
This distinction matters in formal verification. An integer encoding does not automatically reproduce integer overflow in a program. A bit-vector encoding can represent modular arithmetic, while the floating-point theory provides operations corresponding to IEEE 754 floating-point arithmetic.
Definitions also contain details that differ from familiar programming conventions. For example, ordinary theory functions are total, so exceptional-looking inputs do not necessarily cause runtime errors. Some operations are deliberately underspecified in certain cases rather than assigned a single prescribed result.
Scripts and solver interaction
An SMT-LIB script is a sequence of commands. Common commands include:
| Command | Purpose |
|---|---|
set-logic |
Select a named logic |
set-option |
Configure a standard or implementation-specific option |
declare-sort, declare-fun, declare-const |
Introduce symbols |
define-fun |
Give a function an explicit definition |
assert |
Add a Boolean constraint |
check-sat |
Test the current assertions for satisfiability |
get-model |
Request a satisfying interpretation |
push, pop |
Save and restore assertion contexts |
exit |
End the session |
A complete example is:
(set-option :produce-models true)
(set-logic QF_LIA)
(declare-const x Int)
(assert (> x 3))
(assert (< x 5))
(check-sat)
(get-model)
(push 1)
(assert (distinct x 4))
(check-sat)
(pop 1)
(exit)
QF_LIA designates quantifier-free linear integer arithmetic. The first satisfiability check returns sat, and a model assigns . Within the pushed context, the additional assertion excludes that value, so the second check returns unsat. The pop command removes the temporary assertion.
Results and diagnostic output
A satisfiability check can return:
sat: the assertions have a satisfying interpretation.unsat: no satisfying interpretation exists under the selected semantics.unknown: the solver has not established either conclusion.
unknown is not a third mathematical truth value. It reflects a limitation of the solving procedure or its execution. Errors and unsupported commands are separate from these satisfiability results.
Depending on enabled options and solver support, a script can request models, values of particular expressions, proofs, or an unsatisfiable core. An unsatisfiable core identifies a subset of the assertions sufficient for unsatisfiability; it need not be the smallest such subset.
The standard also supports checks under temporary assumptions through check-sat-assuming. Together with assertion stacks, this enables incremental solving, in which an application asks a series of related questions without restarting the solver for every query.
Theories and logics
SMT-LIB separates reusable theory definitions from named logics. Major theory families include:
- Core logic, including Boolean values, equality, and conditional expressions.
- Integer and real arithmetic, with arithmetic operations and order relations.
- Fixed-size bit-vectors, including modular arithmetic, bitwise operations, extraction, and concatenation.
- Arrays, characterized by operations such as reading and updating an indexed value.
- Floating-point arithmetic, with explicit formats and rounding modes.
- Strings and sequences, including operations such as concatenation and length.
- Algebraic datatypes, for structured values built from constructors.
Theories evolve, and support differs across solver releases and language versions.
A logic combines selected facilities and may restrict their use. Common examples include:
| Logic | Main scope |
|---|---|
QF_UF |
Quantifier-free formulas with uninterpreted functions |
QF_LIA |
Quantifier-free linear integer arithmetic |
QF_LRA |
Quantifier-free linear real arithmetic |
QF_BV |
Quantifier-free fixed-size bit-vectors |
QF_AUFBV |
Quantifier-free arrays, uninterpreted functions, and bit-vectors |
QF_NIA |
Quantifier-free nonlinear integer arithmetic |
Here, QF means quantifier-free. Linear arithmetic restricts multiplication so that it does not multiply two variable-dependent expressions.
Logic selection is more than documentation: it communicates the expected problem fragment and can influence solver configuration and admissibility checks. A solver may accept constructs outside a declared fragment, but such permissiveness is not a portable property of the language.
The fragments also differ in decidability and computational complexity. Standardizing a syntax does not make every expressible problem decidable. Quantifier-free nonlinear integer arithmetic, for example, is undecidable in general.
History and benchmark infrastructure
The SMT-LIB initiative began in 2003, when SMT tools lacked a sufficiently uniform language and shared benchmark infrastructure. Early work established common representations for formulas and organized benchmark families around theories and logics.
SMT-LIB 2, introduced in 2010, established a command-oriented language supporting interactive solver sessions. Later revisions extended and clarified the language and theory specifications. Version distinctions matter because a construct supported by one revision or solver release may not be available in another.
The benchmark library contains problems from application domains as well as generated or specially constructed instances. Benchmark files can carry information such as their origin, category, expected satisfiability status, and explanatory notes.
SMT-LIB is closely associated with SMT-COMP, an annual competition for SMT solvers. The competition uses standardized inputs and benchmark collections to evaluate implementations under defined conditions. SMT-LIB and SMT-COMP are nevertheless distinct: the former supplies specifications and shared resources, while the latter organizes evaluations and competition rules.
Applications
SMT-LIB is widely used as an interchange format between constraint-generating tools and solvers. Applications include software and hardware verification, model checking, symbolic execution, scheduling, and automated theorem proving.
A verification tool may translate a program property into a logical formula whose satisfying assignments describe counterexamples. If the solver reports sat, the model may help reconstruct an execution that violates the property. If it reports unsat, that establishes the absence of a counterexample within the encoding and its assumptions.
The textual format also supports debugging and reproducibility. A tool can save the exact constraints submitted to a solver, allowing them to be inspected, minimized, or tested with another implementation. Direct solver application programming interfaces may offer richer integration, but SMT-LIB provides a comparatively implementation-independent exchange layer.
Portability and limitations
Standardized syntax and semantics improve portability without making all implementations interchangeable. Solvers differ in supported logics, resource consumption, model presentation, proof formats, and extension commands. Optimization objectives and specialized reasoning features may rely on solver-specific interfaces rather than the common standard.
Equivalent encodings can also produce very different solving times. Variable representations, use of quantifiers, and the choice between integer and bit-vector arithmetic can strongly affect the search. Benchmark results therefore characterize performance on particular workloads and configurations, not universal superiority.
Finally, a solver result applies to the formula submitted. A sound unsat result does not by itself establish that a program, circuit, or physical system was modeled correctly. The translation from the original problem to SMT constraints remains a separate part of the verification argument.