Search code examples
z3smtsat

Z3 switching between unknown/unsat by just changing the range sort of array

I am facing a weird result when using Z3. Consider these two benchmarks written in smt-lib:

(declare-fun a () (Array (_ BitVec 32) (_ BitVec 32)))
(declare-fun b () (Array (_ BitVec 32) (_ BitVec 32)))
(assert (forall ((fqv (Array (_ BitVec 32) (_ BitVec 8))))
  (= (select a
                (concat (select fqv #x00000003)
                        (concat (select fqv #x00000002)
                                (concat (select fqv #x00000001)
                                        (select fqv #x00000000)))))
        (select b
                (concat (select fqv #x00000003)
                        (concat (select fqv #x00000002)
                                (concat (select fqv #x00000001)
                                        (select fqv #x00000000))))))))

(assert (= false (= (select a #x00000000) (select b #x00000000))))
(check-sat)
(get-model)

and

(declare-fun a () (Array (_ BitVec 32) (_ BitVec 8)))
(declare-fun b () (Array (_ BitVec 32) (_ BitVec 8)))
(assert (forall ((fqv (Array (_ BitVec 32) (_ BitVec 8))))
  (= (select a
                (concat (select fqv #x00000003)
                        (concat (select fqv #x00000002)
                                (concat (select fqv #x00000001)
                                        (select fqv #x00000000)))))
        (select b
                (concat (select fqv #x00000003)
                        (concat (select fqv #x00000002)
                                (concat (select fqv #x00000001)
                                        (select fqv #x00000000))))))))

(assert (= false (= (select a #x00000000) (select b #x00000000))))
(check-sat)
(get-model)

Their only difference is in the range of a and b. In the first case, it is a bit-vector of size 32. While in the second case, it is a bit-vector of size 8.

The interesting part is that (check-sat) is returning unsat for the first case, and unknown for the second one.

Is there an explanation for this? Here is a link where you can quickly run this experiment: https://people.csail.mit.edu/cpitcla/z3.wasm/z3.html

Solution

  • This looks odd indeed. I'd have expected you to get unknown regardless of which, since you have a quantified assert that ranges over an array.

    The most likely reason is that there's some "internal" heuristic that kicks in for the first case, but fails to do so for the second. (So, in a sense, you're getting "lucky" for the first one, and the second one is the expected behavior given the quantified assert.)

    Please report this at https://github.com/Z3Prover/z3/issues. Even though this isn't strictly a bug, I'm sure the developers would appreciate taking a look to see what internal heuristic might be improved to handle both of these cases.