Is it possible to get a legit range info when using a SMT constraint with Z3

Question

So basically I am trying to solve the following SMT constraint with a generic constraint solver like Z3:

>>> from z3 import *
>>> a = BitVec("a", 32)
>>> b = BitVec("b", 32)
>>> c1 = (a + 32) & (b & 0xff)
>>> c2 = (b & 0xff)
>>> s = Solver()
>>> s.add(c1 == c2)
>>> s.check()
sat
>>> s.model()
[b = 0, a = 4294967199]

Note that obviously, the constraint should be sat whenever b falls within the range of [0x00000000, 0xffffff00].

So here is my question, is it in general feasible for a SMT solver like Z3 to provide the "range" information, of a satisfiable constraint? Thanks.

Answer 1

If you are asking for a valid "widest" range of values such that your property will be satisfied for all numbers in that range, that would be a quantified optimization problem. (Also, what "widest" means in this context can be hard to express.) Currently, neither z3 nor any other SMT solver I'm aware of can handle such problems, unfortunately.

However, if you are looking for the minimum and maximum values of b such that your property will hold, then you can use the Optimize class for that:

from z3 import *

a = BitVec("a", 32)
b = BitVec("b", 32)
c1 = (a + 32) & (b & 0xff)
c2 = (b & 0xff)

s = Optimize()
s.add(c1 == c2)

min_b = s.minimize(b)
max_b = s.maximize(b)
s.set('priority', 'box')
s.check()

print "min b = %s" % format(min_b.value().as_long(), '#x')
print "max b = %s" % format(max_b.value().as_long(), '#x')

This prints:

min b = 0x0
max b = 0xffffffff

[Aside: The max value of b differs from what you predicted it would be. But what z3 is saying looks good to me: If you pick a to be 0x7fffffdf, then a+32 will be 0x7fffffff, which is all 1s; and thus c1 and c2 will be equivalent for any value of b. So nothing here really constrains b in any way. Perhaps you had a different constraint in mind?]

But more importantly, note that this does not mean your property will be true for all values of b in this range: All it's saying is that of all the values of b that satisfy your property, these are the minimum and maximum values b can assume. (In this particular case, it turns out that all values within that range satisfy it, but that's something we deduced ourselves.) For instance, if you add a constraint that b is not 5, you will still get these bounds. I hope that's clear!

Answer 2

The answer provided by Levent Erkok is valid in general and, in most practical cases, it is the only one which is worth being considered.

However, technically speaking, this is not a problem that is completely beyond the reach of OMT solvers, at least when the domain of values being considered is finite and, possibly, small. In this case, it is possible to simply enumerate all possible values in the formulation of the problem. Naturally, this approach should not be expected to scale very well.

---

Example.

The goal of this model is to find the largest interval delta, contained in [low, upp], such that for all the values inside the interval a certain Boolean property Prop holds.

File: test.smt2

(set-option :produce-models true)

(declare-fun low () (_ BitVec 4))
(declare-fun upp () (_ BitVec 4))
(declare-fun delta () (_ BitVec 4))

(declare-fun Prop () Bool)

(assert (bvule low upp))
(assert (= delta (bvadd upp (bvneg low) (_ bv1 4))))

; Put in relation a domain value with the desired Property
(assert (=> (and (bvule low (_ bv0 4)) (bvule (_ bv0 4) upp)) Prop))
(assert (=> (and (bvule low (_ bv1 4)) (bvule (_ bv1 4) upp)) Prop))
(assert (=> (and (bvule low (_ bv2 4)) (bvule (_ bv2 4) upp)) Prop))
(assert (=> (and (bvule low (_ bv3 4)) (bvule (_ bv3 4) upp)) Prop))
(assert (=> (and (bvule low (_ bv4 4)) (bvule (_ bv4 4) upp)) Prop))
(assert (=> (and (bvule low (_ bv5 4)) (bvule (_ bv5 4) upp)) Prop))
(assert (=> (and (bvule low (_ bv6 4)) (bvule (_ bv6 4) upp)) Prop))
(assert (=> (and (bvule low (_ bv7 4)) (bvule (_ bv7 4) upp)) Prop))
(assert (=> (and (bvule low (_ bv8 4)) (bvule (_ bv8 4) upp)) Prop))
(assert (=> (and (bvule low (_ bv9 4)) (bvule (_ bv9 4) upp)) Prop))
(assert (=> (and (bvule low (_ bv10 4)) (bvule (_ bv10 4) upp)) Prop))
(assert (=> (and (bvule low (_ bv11 4)) (bvule (_ bv11 4) upp)) Prop))
(assert (=> (and (bvule low (_ bv12 4)) (bvule (_ bv12 4) upp)) Prop))
(assert (=> (and (bvule low (_ bv13 4)) (bvule (_ bv13 4) upp)) Prop))
(assert (=> (and (bvule low (_ bv14 4)) (bvule (_ bv14 4) upp)) Prop))
(assert (=> (and (bvule low (_ bv15 4)) (bvule (_ bv15 4) upp)) Prop))

; These are just to make the solution "interesting"
; Your problem should already entail some values bvX for
; which Prop is false
(assert (=> (and (bvule low (_ bv5 4)) (bvule (_ bv5 4) upp)) (not Prop)))
(assert (=> (and (bvule low (_ bv6 4)) (bvule (_ bv6 4) upp)) (not Prop)))
(assert (=> (and (bvule low (_ bv13 4)) (bvule (_ bv13 4) upp)) (not Prop)))

(maximize delta)

(check-sat)
(get-objectives)
(get-model)

A short explanation. The goal of the objective function is to maximize the size of the interval [low, upp], which is measured by delta. The largest value of delta is 2^N, which corresponds to the interval [0, 2^N - 1].

The constraint:

(assert (=> (and (bvule low (_ bv0 4)) (bvule (_ bv0 4) upp)) Prop))

says that, if the value bv0 is contained in the current interval [low, upp], then the property Prop must hold.

The constraint:

(assert (=> (and (bvule low (_ bv5 4)) (bvule (_ bv5 4) upp)) (not Prop)))

says that, for the value bv5, the property Prop does not hold. Same for bv6 and bv13. These constraints are just to make the solution interesting. Your problem should already contain some values bvX for which property Prop cannot be true.

The optimal solution matches the desired value:

~$ time ./optimathsat test.smt2 
sat

(objectives
 (delta (_ bv6 4))
)
( (low (_ bv7 4))
  (upp (_ bv12 4))
  (delta (_ bv6 4))
  (Prop true) )

real    0m0,042s
user    0m0,029s
sys     0m0,013s

Naturally, the same formula can also be solved with z3.