Verification Modulo Theories (Language, Benchmarks and Tools)

 Verification Modulo Theories was originally proposed in the Rich-Model Toolkit meeting held in Turin in 2011 (see slides below).

Since then, a format has been defined (see below), and is now supported by the the nuXmv model checker. 

The VMT format is an extension of the SMT-LIBv2 (SMT2 for short) format to represent symbolic transition systems. VMT exploits the capability offered by the SMT2 language of attaching annotations to terms and formulas in order to specify the components of the transition system and the properties to verify. 

Core language

In the core VMT-LIB language, the following annotations are used:

In a VMT file, only annotated terms and their sub-terms are meaningful. Any other term is ignored. Moreover, only the following commands are allowed to occur in VMT files: set-logic, set-option, declare-sort, define-sort, declare-fun, define-fun (For convenience, an additional (assert true) command is allowed to appear at the end of the file).

The following example shows a simple NUXMV model and its corresponding VMT translation.


-- this is a comment


VAR x : integer;

IVAR b : boolean;

INIT x = 1;


next(x) = b ? x + 1 : x;


LTLSPEC FG x > 10;


; this is a comment

(declare-const x Int)

(declare-const x.next Int)

(define-fun sv.x () Int (! x :next x.next))

(declare-const b Bool)

(define-fun init () Bool (! (= x 1) :init true))

(define-fun trans () Bool

   (! (= x.next (ite b (+ x 1) x)) :trans true)

(define-fun p1 () Bool (! (> x 0) :invar-property 1))

(define-fun p2 () Bool (! (> x 10) :live-property 2))

Since the SMT2 format (and thus also the VMT one that inherits from SMT2) does not allow to annnotate the declaration of variables, it is a good practice to insert immediately after the declaration of the variables a set of defines to specify the relations among variables. See for instance the define sv0 in the example above that introduces the relation between x and xn.

Language extensions

The following annotations are not part of the core language, but are defined as syntactic sugar to model higher level constructs. They can be removed by the vmtext2core.py script that is part of the vmt-tools package (see below):

Format Specification

The VMT-LIB Language and Tools 

Tool Support

vmt-tools is a collection of tools for working with the VMT format. Currently, the following tools are provided:

Further converters to VMT

Verification Tools Supporting the VMT Format



Title: From Satisfiability to Verification Modulo Theories (slides available here)

Speaker: Alessandro Cimatti (FBK, Trento)

COST Meeting 2011

Abstract: The field of Satisfiability Modulo Theories (SMT) has greatly benefited from the SMT-LIB and SMT-COMP initiatives: the definition of a standard language supported the creation of a large collection of benchmarks, and the competition fostered tremendous progress in the performance of SMT solvers. Many practical problems in verification arise from the analysis of the transition systems that can be naturally represented in symbolic form within the SMT framework (e.g. software, timed and hybrid systems, word-level circuits, microcode). However, the SMT initiative does not deal directly with the sequential nature of the transition system, where reachability is defined by unrolling of the transition relation. To draw an analogy with the pure boolean case, SMT is the counterpart of SAT, but there is no "modulo theory" counterpart for Model Checking. In fact, many problems in the SMT-LIB are (bounded horizon) verification problems for such transition systems. In this talk I will argue in favour of a Verification Modulo Theory (VMT) initiative. The aim is to define a language, a library of benchmarks, and to set up a competition, for verification problems resulting from transition systems described in SMT. The VMT initiative, while leveraging the advances of SMT, will allow to deal natively with issues resulting from the verification of transition systems, hopefully resulting in a new generation of model checkers modulo theory.

Title: VMT techniques (slides available here)

Speaker: Stefano Tonetta (FBK, Trento)

COST Meeting 2011

Abstract: Satisfiability-modulo-theory is the problem of checking the satisfiability of a logical formula with a background theory. Many solvers have been optimized for different theories and enhanced with advanced features such as incrementality, unsat cores, interpolation. Meanwhile, many techniques have been conceived to verify properties of transition systems exploiting the efficiency and features of SMT solvers. In fact, by reducing a verification problem to a possibly infinite series of SMT problems, infinite-state systems with reals, integers, or other data types can be verified. This "Verification-Modulo-Theory" (VMT) has been applied to different applications such as software, timed and hybrid systems, and microcode. In this talk, we overview some of these techniques including bounded model checking, interpolation-based model checking, k-induction, predicate abstraction, and combination thereof. 

Title: SMT-Based Satisfiability of Temporal Logic (slides available here)

Speaker: Stefano Tonetta (FBK, Trento)

SCARE Workshop 2017

Abstract: The talk gives an overview of temporal satisfiability modulo theories for linear-time temporal logic over dicrete, continuous, and hybrid models of time. We start with giving some motivations derived from requirements analysis and contract-based design. We show how the problem can be reduced to discrete-time SMT-based model checking. Finally, we give an overview of some SMT-based algorithms and the related tool chain supported by FBK.