Skip to main content
 首页 » 编程设计

python之Z3Py 证明函数返回错误的反例

2024年12月31日12lvdongjie

我正在尝试使用 Z3Py 证明函数,但它似乎返回了一个不正确的反例。 问题是什么?? (Z3-4.7.1-x86-win, Python-2.7.15)

>>> import z3 
>>> A = z3.BitVec('A', 8) 
>>> B = z3.BitVec('B', 8) 
>>> C = z3.BitVec('C', 8) 
>>> z3.prove((A*B)/C == A*(B/C)) 
counterexample 
[A = 67, B = 86, C = 2] 
>>> ((67*86)%256)/2 
65 
>>> (67*(86/2))%256 
65 

请您参考如下方法:

让我们看看 Z3 在做什么:

import z3 
A = z3.BitVec('A', 8) 
B = z3.BitVec('B', 8) 
C = z3.BitVec('C', 8) 
 
s = z3.Solver() 
s.add((A*B)/C == A*(B/C)) 
print s.sexpr() 

当你运行这个脚本时,你会得到:

$ python a.py 
(declare-fun C () (_ BitVec 8)) 
(declare-fun B () (_ BitVec 8)) 
(declare-fun A () (_ BitVec 8)) 
(assert (= (bvsdiv (bvmul A B) C) (bvmul A (bvsdiv B C)))) 

啊,它在 8 位向量上使用 bvmul 和 bvsdiv。事实证明,乘法对于有符号-无符号无关紧要,但除法却很重要。因此,实际上完成映射是为了将结果映射到 -128 到 127 的范围,而不是(正如我怀疑您可能已经预料到的那样)到 0 到 255。

因此,如果您进行数学计算,左侧会减少到 -63,因为乘法会产生 5762,它会映射到 -126 在带符号的 8 位表示中。然而,右侧被缩减为 65;从而给你合法的反例。

为了避免这种情况,您可以使用旧的 Int 类型;或者通过 UDiv 告诉 Python 不要使用带符号的除法,参见这里:https://z3prover.github.io/api/html/namespacez3py.html#a64c02a843a4ac8781dd666a991797906

如果使用UDiv,可以得到更好的反例:

>>> import z3 
>>> A = z3.BitVec('A', 8) 
>>> B = z3.BitVec('B', 8) 
>>> C = z3.BitVec('C', 8) 
>>> z3.prove(z3.UDiv(A*B, C) == A*z3.UDiv(B, C)) 
counterexample 
[A = 95, B = 140, C = 41] 
>>> ((95*140)%256/41)%256 
5 
>>> (95*((140/41)%256))%256 
29 

我想这更符合您的预期。