Fixed-points in Z3

Z3 contains an extension called muZ with fixed-point constraints. This tutorial includes some examples that demonstrate features of this engine. The following papers μZ - An Efficient Engine for Fixed-Points with Constraints. (CAV 2011) and Generalized Property Directed Reachability (SAT 2012) describe some of the main features of the engine. Be sure to follow along with the examples by clicking the "edit" link in the corner. See what the tool says, try your own formulas, and experiment! Please send feedback, comments and/or corrections to nbjorner@microsoft.com.

Introduction

This tutorial covers some of the fixedpoint utilities available with Z3. The main features are a basic Datalog engine, an engine with relational algebra and an engine based on a generalization of the Property Directed Reachability algorithm, as well as the Duality engine.

Basic Datalog

The default fixed-point engine is a bottom-up Datalog engine. It works with finite relations and uses finite table representations as hash tables as the default way to represent finite relations.

Relations, rules and queries

The first example illustrates how to declare relations, rules and how to pose queries. load in editor
(declare-rel a ())
(declare-rel b ())
(declare-rel c ())
(rule (=> b a))
(rule (=> c b))

;(set-option :fixedpoint.engine datalog)
(query a)

(rule c)
(query a
 :print-answer true)
The example illustrates some of the basic constructs. 
 (declare-rel a ())
declares a 0-ary relation a. 
 (rule (=> b a))
Create the rule that a follows from b. In general you can create a rule with multiple premises and a name using the format 
 (rule (=> (and b c) a) name)
The name is optional. It is used for tracking the rule in derivation proofs. Continuing with the example, a is false unless b is established. 
 (query r)
Asks if relation a can be derived. The rules so far say that a follows if b is established and that b follows if c is established. But nothing establishes c and b is also not established, so a cannot be derived. 
 (rule c)
Now it is the case that a can be derived.

Relations with arguments

Relations can take arguments. We illustrate relations with arguments using edges and paths in a graph.

load in editor
;(set-option :fixedpoint.engine datalog)
(define-sort s () (_ BitVec 3))
(declare-rel edge (s s))
(declare-rel path (s s))
(declare-var a s)
(declare-var b s)
(declare-var c s)

(rule (=> (edge a b) (path a b)))
(rule (=> (and (path a b) (path b c)) (path a c)))

(rule (edge #b001 #b010))
(rule (edge #b001 #b011))
(rule (edge #b010 #b100))

(declare-rel q1 ())
(declare-rel q2 ())
(declare-rel q3 (s))
(rule (=> (path #b001 #b100) q1))
(rule (=> (path #b011 #b100) q2))
(rule (=> (path #b001 b) (q3 b)))

(query q1)
(query q2)
(query q3 :print-answer true)
The example uses the declaration 
 (declare-var a s)
to instrument the fixed-point engine that a should be treated as a variable appearing in rules.

Engine for Property Directed Reachability

A different underlying engine for fixed-points is based on an algorithm for Property Directed Reachability (PDR). The PDR engine is used by default for relations over integers, reals and algebraic data-types. The version in Z3 applies to Horn clauses with arithmetic and Boolean domains. The engine also works with domains using algebraic data-types and bit-vectors, although it is currently not overly tuned for either. The PDR engine is targeted at applications from symbolic model checking of software. The systems may be infinite state. The following examples also serve a purpose of showing how software model checking problems (of safety properties) can be embedded into Horn clauses and solved using PDR.

Procedure Calls

McCarthy's 91 function illustrates a procedure that calls itself recursively twice. The Horn clauses below encode the recursive function: 

  mc(x) = if x > 100 then x - 10 else mc(mc(x+11))
The general scheme for encoding recursive procedures is by creating a predicate for each procedure and adding an additional output variable to the predicate. Nested calls to procedures within a body can be encoded as a conjunction of relations.

load in editor
(declare-rel mc (Int Int))
(declare-var n Int)
(declare-var m Int)
(declare-var p Int)

(rule (=> (> m 100) (mc m (- m 10))))
(rule (=> (and (<= m 100) (mc (+ m 11) p) (mc p n)) (mc m n)))

(declare-rel q1 (Int Int))
(rule (=> (and (mc m n) (< n 91)) (q1 m n))) 
(query q1 :print-certificate true)

(declare-rel q2 (Int Int))
(rule (=> (and (mc m n) (not (= n 91)) (<= m 101)) (q2 m n)))
(query q2 :print-certificate true)

(declare-rel q3 (Int Int))
(rule (=> (and (mc m n) (< n 92)) (q3 m n)))
(query q3 :print-certificate true)
The first two queries are unsatisfiable. The PDR engine produces the same proof of unsatisfiability. The proof is an inductive invariant for each recursive predicate.

Traffic Jam

A self-contained example that exercises the .NET API over C# is provided as a separate download.

Syntax

Three different text-based input formats are accepted.

Basic datalog

Files with suffix .datalog are parsed using the BDDBDDB format. The format can be used for comparing benchmarks with the BDDBDDB tool.

We use an artificial program to illustrate the basic Datalog format that complies to the format used by BDDBDDB.

Z 64

P0(x: Z) input
Gt0(x : Z, y : Z) input
R(x : Z) printtuples
S(x : Z) printtuples
Gt(x : Z, y : Z) printtuples
Gt(x,y) :- Gt0(x,y).
Gt(x,y) :- Gt(x,z), Gt(z,y).
R(x) :- Gt(x,_).
S(x) :- Gt(x,x0), Gt0(x,y), Gt0(y,z), P0(z).
Gt0("a","b").
Gt0("b","c").
Gt0("c","d").
Gt0("a1","b").
Gt0("b","a1").
Gt0("d","d1").
Gt0("d1","d").
P0("a1").

SMT-LIB2 extension

The following commands are added to the SMT-LIB2 syntax:

Pure SMT-LIB2

Many problems about program safety can be reduced to pure Horn clause satisfiability modulo theories (typically of arithmetic). These problems are expressible directly in SMT-LIB2. The repository Horn clause benchmarks in SMT-LIB2 contains more than 10,000 samples taken from different benchmarks and different encodings of the same benchmarks. An assertion is Horn if it is an implication; the head of the implication is either a formula using only interpreted functions, or it is an uninterpreted predicate; the body of the implication is a formula in negation normal form where the uninterpreted predicates occur positively. load in editor
(set-logic HORN)
(declare-fun mc (Int Int) Bool)

(assert (forall ((m Int)) (=> (> m 100) (mc m (- m 10)))))
(assert (forall ((m Int) (n Int) (p Int)) 
           (=> (and (<= m 100) (mc (+ m 11) p) (mc p n)) (mc m n))))

(assert (forall ((m Int) (n Int))
       (=> (and (mc m n) (<= m 101)) (= n 91))))
(check-sat)
(get-model)
Note the following:

Programmatic API

You can interact with muZ over the programmatic API from Python, C, OCaml, Java, and .NET. The APIs support adding rules and posing queries.