s Z3 无效模型的反例

Question

这是问题的扩展：

在下面的代码中，我尝试使用 Z3 为我满足某些 CHC 子句的猜测候选人获取反例：

from z3 import *


x, xp = Ints('x xp') 

P = lambda x: x == 0
B = lambda x: x < 5
T = lambda x, xp: xp == x + 1
Q = lambda x: x == 5 

s = 10

def Check(mkConstraints, I, P , B, T , Q):
    s = Solver()
    # Add the negation of the conjunction of constraints
    s.add(Not(mkConstraints(I, P , B, T , Q)))
    r = s.check()
    if r == sat:
        return s.model()
    elif r == unsat:
        return {}
    else:
        print("Solver can't verify or disprove, it says: %s for invariant %s" %(r, I))

def System(I, P , B, T , Q):


    # P(x) -> I(x)
    c1 = Implies(P(x), I(x))

    # P(x) /\ B(x) /\ T(x,xp) -> I(xp) 
    c2 = Implies(And(B(x), I(x), T(x, xp)) , I(xp))

    # I(x) /\ ~B(x) -> Q(x)
    c3 = Implies(And(I(x), Not(B(x))), Q(x))

    return And(c1, c2, c3)


cex_List = []
I_guess = lambda x: x < 3


for i in range(s):
    cex = Check(System, I_guess, P , B , T , Q)
    I_guess = lambda t: Or(I_guess(t) , t == cex['x'])
    cex_List.append( cex[x] )

print(cex_List )

思路是用Z3为猜测不变量I学习一个反例x0，然后运行Z3为I学习一个反例|| (x == x0) 等等，直到我们得到 s 个反例。但是下面的代码给出了'RecursionError: maximum recursion depth exceeded '.我很困惑，因为我什至没有在任何地方以深度 > 1 递归。谁能描述一下出了什么问题？

Answer 1

你的问题确实与z3无关；而是 Python 的特点。考虑一下：

f = lambda x: x
f = lambda x: f(x)

print(f(5))

如果你运行这个程序，你也会看到它落入同一个 infinite-recursion 循环，因为当你“得到”到内部 f ，外部 f 再次绑定到自身。在您的情况下，这显示在行中：

    I_guess = lambda t: Or(I_guess(t) , t == cex['x'])

它通过使 I_guess 递归而落入相同的陷阱，这不是你想要的。

避免这种情况的方法是使用中间变量。这很丑 counter-intuitive 但这就是 python 的方式！对于上面的示例，您可以将其写为：

f = lambda x: x
g = f
f = lambda x: g(x)

print(f(5))

因此，您需要对 I_guess 变量执行相同的操作。请注意，由于您正在迭代更新函数，因此需要确保记住每个步骤中的函数，而不是一遍又一遍地使用相同的名称。也就是说，每次创建新函数时都捕获旧版本。当应用于上述情况时，它将类似于：

f = lambda x: x
f = lambda x, old_f=f: old_f(x)

print(f(5))

这将确保迭代不会破坏捕获的函数。将这个想法应用到您的问题中，您可以编写如下代码：

for i in range(s):
    cex = Check(System, I_guess, P, B, T, Q)
    I_guess = lambda t, old_I_guess=I_guess: Or(old_I_guess(t), t == cex[x])
    cex_List.append(cex[x])

当运行时，打印：

[2, 2, 2, 2, 2, 2, 2, 2, 2, 2]

没有任何infinite-recursion问题。（我不确定这是正确的输出还是你真正想做的。在我看来你需要告诉 z3 给你一个“不同的”解决方案，也许你忘记了这样做。但是那是一个不同的问题。我们在这里真正讨论的是 Python 问题，而不是 z3 建模。）

s Z3 无效模型的反例

s Counterexamples for invalid model for Z3

python

z3py