HackTricks
Search…
Z3 - Satisfiability Modulo Theories (SMT)
Very basically, this tool will help us to find values for variables that need to satisfy some conditions and calculating them by hand will be so annoying. Therefore, you can indicate to Z3 the conditions the variables need to satisfy and it will find some values (if possible).

# Basic Operations

## Booleans/And/Or/Not

1
#pip3 install z3-solver
2
from z3 import *
3
s = Solver() #The solver will be given the conditions
4
5
x = Bool("x") #Declare the symbos x, y and z
6
y = Bool("y")
7
z = Bool("z")
8
9
# (x or y or !z) and y
10
11
s.check() #If response is "sat" then the model is satifable, if "unsat" something is wrong
12
print(s.model()) #Print valid values to satisfy the model
Copied!

## Ints/Simplify/Reals

1
from z3 import *
2
3
x = Int('x')
4
y = Int('y')
5
#Simplify a "complex" ecuation
6
print(simplify(And(x + 1 >= 3, x**2 + x**2 + y**2 + 2 >= 5)))
7
#And(x >= 2, 2*x**2 + y**2 >= 3)
8
9
#Note that Z3 is capable to treat irrational numbers (An irrational algebraic number is a root of a polynomial with integer coefficients. Internally, Z3 represents all these numbers precisely.)
10
#so you can get the decimals you need from the solution
11
r1 = Real('r1')
12
r2 = Real('r2')
13
#Solve the ecuation
14
print(solve(r1**2 + r2**2 == 3, r1**3 == 2))
15
#Solve the ecuation with 30 decimals
16
set_option(precision=30)
17
print(solve(r1**2 + r2**2 == 3, r1**3 == 2))
Copied!

## Printing Model

1
from z3 import *
2
3
x, y, z = Reals('x y z')
4
s = Solver()
5
s.add(x > 1, y > 1, x + y > 3, z - x < 10)
6
s.check()
7
8
m = s.model()
9
print ("x = %s" % m[x])
10
for d in m.decls():
11
print("%s = %s" % (d.name(), m[d]))
Copied!

# Machine Arithmetic

Modern CPUs and main-stream programming languages use arithmetic over fixed-size bit-vectors. Machine arithmetic is available in Z3Py as Bit-Vectors.
1
from z3 import *
2
3
x = BitVec('x', 16) #Bit vector variable "x" of length 16 bit
4
y = BitVec('y', 16)
5
6
e = BitVecVal(10, 16) #Bit vector with value 10 of length 16bits
7
a = BitVecVal(-1, 16)
8
b = BitVecVal(65535, 16)
9
print(simplify(a == b)) #This is True!
10
a = BitVecVal(-1, 32)
11
b = BitVecVal(65535, 32)
12
print(simplify(a == b)) #This is False
Copied!

## Signed/Unsigned Numbers

Z3 provides special signed versions of arithmetical operations where it makes a difference whether the bit-vector is treated as signed or unsigned. In Z3Py, the operators <, <=, >, >=, /, % and >> correspond to the signed versions. The corresponding unsigned operators are ULT, ULE, UGT, UGE, UDiv, URem and LShR.
1
from z3 import *
2
3
# Create to bit-vectors of size 32
4
x, y = BitVecs('x y', 32)
5
solve(x + y == 2, x > 0, y > 0)
6
7
# Bit-wise operators
8
# & bit-wise and
9
# | bit-wise or
10
# ~ bit-wise not
11
solve(x & y == ~y)
12
solve(x < 0)
13
14
# using unsigned version of <
15
solve(ULT(x, 0))
Copied!

## Functions

Interpreted functions such as arithmetic where the function + has a fixed standard interpretation (it adds two numbers). Uninterpreted functions and constants are maximally flexible; they allow any interpretation that is consistent with the constraints over the function or constant.
Example: f applied twice to x results in x again, but f applied once to x is different from x.
1
from z3 import *
2
3
x = Int('x')
4
y = Int('y')
5
f = Function('f', IntSort(), IntSort())
6
s = Solver()
7
s.add(f(f(x)) == x, f(x) == y, x != y)
8
s.check()
9
m = s.model()
10
print("f(f(x)) =", m.evaluate(f(f(x))))
11
print("f(x) =", m.evaluate(f(x)))
12
13
print(m.evaluate(f(2)))
14
s.add(f(x) == 4) #Find the value that generates 4 as response
15
s.check()
16
print(m.model())
Copied!

# Examples

## Sudoku solver

1
# 9x9 matrix of integer variables
2
X = [ [ Int("x_%s_%s" % (i+1, j+1)) for j in range(9) ]
3
for i in range(9) ]
4
5
# each cell contains a value in {1, ..., 9}
6
cells_c = [ And(1 <= X[i][j], X[i][j] <= 9)
7
for i in range(9) for j in range(9) ]
8
9
# each row contains a digit at most once
10
rows_c = [ Distinct(X[i]) for i in range(9) ]
11
12
# each column contains a digit at most once
13
cols_c = [ Distinct([ X[i][j] for i in range(9) ])
14
for j in range(9) ]
15
16
# each 3x3 square contains a digit at most once
17
sq_c = [ Distinct([ X[3*i0 + i][3*j0 + j]
18
for i in range(3) for j in range(3) ])
19
for i0 in range(3) for j0 in range(3) ]
20
21
sudoku_c = cells_c + rows_c + cols_c + sq_c
22
23
# sudoku instance, we use '0' for empty cells
24
instance = ((0,0,0,0,9,4,0,3,0),
25
(0,0,0,5,1,0,0,0,7),
26
(0,8,9,0,0,0,0,4,0),
27
(0,0,0,0,0,0,2,0,8),
28
(0,6,0,2,0,1,0,5,0),
29
(1,0,2,0,0,0,0,0,0),
30
(0,7,0,0,0,0,5,2,0),
31
(9,0,0,0,6,5,0,0,0),
32
(0,4,0,9,7,0,0,0,0))
33
34
instance_c = [ If(instance[i][j] == 0,
35
True,
36
X[i][j] == instance[i][j])
37
for i in range(9) for j in range(9) ]
38
39
s = Solver()
40
41
if s.check() == sat:
42
m = s.model()
43
r = [ [ m.evaluate(X[i][j]) for j in range(9) ]
44
for i in range(9) ]
45
print_matrix(r)
46
else:
47
print "failed to solve"
Copied!