正确的 Dafny 方法的 Z3 模型

Question

对于一个正确的方法，Z3能否找到方法验证条件的模型？

我原以为不是，但这是一个方法正确的例子

但验证找到了一个模型。

这是 Dafny 1.9.7。

Answer 1

由于两种可能的不完整性来源的组合，Dafny 未能证明该引理：递归定义（此处 Pow）和归纳。由于信息太少，证明实际上失败了，即因为问题约束不足，这反过来解释了为什么可以找到反例。

感应

自动化归纳很困难，因为它需要计算归纳假设，这并不总是可行的。但是，Dafny 有一些 heuristics 用于应用归纳法（可能有效也可能无效），并且可以切换，如以下代码所示：

lemma {:induction false} EvenPowerLemma_manual(a: int, b: nat)
  requires Even(b);
  ensures Pow(a, b) == Pow(a*a, b/2);
{
  if (b != 0) {
    EvenPowerLemma_manual(a, b - 2);
  }
}

启发式关闭后，需要手动"call"引理，即使用归纳假设（这里只针对b >= 2的情况），才能通过.

在您的案例中，启发式算法已被激活，但它们并未 "good enough" 来完成证明。接下来我会解释为什么。

递归定义

通过展开递归定义进行静态推理很容易出现无限下降，因为通常无法确定何时停止。因此，Dafny 默认只展开一次函数定义。在您的示例中，仅展开 Pow 的定义一次不足以使归纳启发法起作用，因为归纳假设必须应用于 Pow(a, b-2)，而 "appear" 在证明中不适用（因为展开一次只会让你到达 Pow(a, b - 1)）。在证明中明确提及 Pow(a, b-2)，即使在其他方面毫无意义的公式中，也会触发归纳启发式，但是：

function Dummy(a: int): bool
{ true }

lemma EvenPowerLemma(a: int, b: nat)
  requires Even(b);
  ensures Pow(a, b) == Pow(a*a, b/2);
{
  if (b != 0) {
    assert Dummy(Pow(a, b - 2));
  }
}

Dummy 函数用于确保断言不提供任何超出句法包括 Pow(a, b-2) 的信息。一个看起来不那么奇怪的断言是 assert Pow(a, b) == a * a * Pow(a, b - 2).

计算证明

仅供参考：您还可以明确证明步骤并让 Dafny 检查它们：

lemma {:induction false} EvenPowerLemma_manual(a: int, b: nat)
  requires Even(b);
  ensures Pow(a, b) == Pow(a*a, b/2);
{
  if (b != 0) {
    calc {
         Pow(a, b);
      == a * Pow(a, b - 1);
      == a * a * Pow(a, b - 2);
      == {EvenPowerLemma_manual(a, b - 2);}
         a * a * Pow(a*a, (b-2)/2);
      == Pow(a*a, (b-2)/2 + 1);
      == Pow(a*a, b/2);
    }
  }
}

Answer 2

Malte 所说的是正确的（我发现它的解释也很好）。

Dafny 是可靠的，因为它只会验证正确的程序。换句话说，如果一个程序不正确，Dafny 验证器永远不会说它是正确的。然而，潜在的决策问题通常是不可判定的。因此，难免会出现程序符合规范，而验证者仍然给出错误信息的情况。事实上，在这种情况下，验证者甚至可能会显示一个 声称的 反例。它可能是一个错误的反例（如上例所示）——它只是意味着，就验证者而言，这是一个反例。如果验证者只是多花一点时间，或者如果它足够聪明来展开更多的函数定义、应用归纳假设或做许多其他好事，则有可能确定反例是伪造的.因此，您收到的任何错误消息（包括可能伴随此类错误消息的任何反例）都应解释为 possible 错误（和 possible 反例).

如果您尝试验证循环的正确性但没有提供足够强大的循环不变量，则经常会出现类似的情况。然后 Dafny 验证器可能会在进入循环时显示一些实际上永远不会出现的变量值。然后，反例试图让您了解如何适当地加强循环不变量。

最后，让我对 Malte 所说的话补充两点。

首先，这个例子中至少还有另一个不完整的来源，即非线性算术。有时很难导航。

其次，可以简化使用函数Dummy的技巧。提到 Pow 调用就足够了（至少在这个例子中），例如：

lemma EvenPowerLemma(a: int, b: nat)
  requires Even(b)
  ensures Pow(a, b) == Pow(a*a, b/2)
{
  if b != 0 {
    var dummy := Pow(a, b - 2);
  }
}

不过，我更喜欢其他两个手动证明，因为它们在向用户解释证明是什么方面做得更好。

鲁斯坦

正确的 Dafny 方法的 Z3 模型

Z3 model for correct Dafny method

z3

dafny