Verification Modulo Theories

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 definition of the VMT format in the nuXmv manual, page 130), 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. More specifically, 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 true is used to specify the formula for the initial states of the model. This formula should contain neither next-state variables nor input variables. (The “dummy” value true in the annotation is needed because the current SMT2 standard requires annotations to always have an associated value.)
  • :trans true 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 VMT
-- this is a comment  ; this is a comment
MODULE main  (declare-fun x () Int)
VAR x : integer;  (declare-fun xn () Int)
INIT x = 1;  (define-fun .sv0 () Int (! x :next xn))
TRANS next(x) = x + 1;  ¨C11C
¨C12C  ¨C13C
   ¨C14C

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

In the future, the VMT-LIB initiative will result in a collection of model checking benchmarks for infinite-state transition systems, and in pyVMT, a toolset based on extensions of the pySMT library.

Format Specification

VMT-LIB Syntax and Semantics Specification, Version 0.1

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.
  • ltl2vmt.py: a tool to convert a :ltl-property into a :live-property specification (by compiling them into symbolic tableaux which are then put in product with the transition system).

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.

Tools Supporting the VMT Format

  • The nuXmv model checker
  • IC3ia, an open-source implementation of infinite-state IC3 with implicit predicate abstraction
  • Horn2vmt, a tool for translating Horn reachability into transition systems
  • The AVR model checker

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.

 

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.

Recent Posts