VMT-LIB
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:
:next name is used to represent state variables. For each variable x in the model, the VMT file contains a pair of variables, xc and xn, representing respectively the current and next version of x. The two variables are linked by annotating xc with the attribute :next xn. All the variables that are not in relation with another by means of a :next attribute are considered inputs.
:init is used to specify the formula for the initial states of the model. This formula should contain neither next-state variables nor input variables.
:trans is used to specify the formula for the transition relation.
:invar-property idx is used to specify invariant properties, i.e. formulas of the form Gp, where p is the formula annotated with :invar-property. The non-negative integer idx is a unique identifier for the property.
:live-property idx is used to specify an LTL property of the form F Gp, where p is the formula annotated with :live-property. The non-negative integer idx is a unique identifier for the property.
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.
nuXmv
-- this is a comment
MODULE main
VAR x : integer;
IVAR b : boolean;
INIT x = 1;
TRANS
next(x) = b ? x + 1 : x;
INVARSPEC x > 0;
LTLSPEC FG x > 10;
VMT
; 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):
:invar is used to specify additional invariant constraints (that must always hold).
:ltl-property idx is used to specify an arbitrary LTL property, using the built-in functions ltl.X, ltl.F, ltl.G and ltl.U to represent temporal operators.
multiple formulas annotated with the same :live-property idx annotation (with the same index value) are considered multi-fairness constraints, and interpreted as FGp1 | ... | FGpn
Format Specification
Tool Support
vmt-tools is a collection of tools for working with the VMT format. Currently, the following tools are provided:
vmt.py: parsing and printing of transition systems in the VMT format.
vmt2btor.py: converter from VMT to the BTOR2 format.
btor2vmt.py: converter from BTOR to VMT.
vmt2horn.py: converter from VMT to Constrained Horn Clauses.
vmt2nuxmv.py: converter from VMT to the SMV dialect of nuXmv.
vmtext2core.py: a tool to convert an extended VMT file to a core VMT file.
Further converters to VMT
From Constrained Horn Clauses to VMT: there's an horn2vmt tool that comes with the IC3ia model checker. Alternatively, there is another translator (also called horn2vmt) available on GitHub.
From nuXmv to VMT: the nuXmv model checker provides a write_vmt_model command.
From Aiger to VMT: via nuXmv.
From VMT to Aiger: via nuXmv.
Verification Tools Supporting the VMT Format
Benchmarks
Some transition systems with invariant properties can be found here.
Presentations
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.