愚蠢的建模整数溢出

Question

Dafny 模型整数可以溢出吗？当 Dafny 证明以下内容时，我感到很惊讶：

method overflow(c : int)
{
    if (c > 0)
    {
        assert((c+1) > 0);
    }
}

我错过了什么？

Answer 1

Dafny 中的类型 int 表示“数学整数”。所以没有溢出。

如果您想对机器算法建模，有几种方法可以做到。

一种方法是定义如下内容：

type uint64 = x:int | 0 <= x < 0x10000000000000000

然后当您尝试将结果存储在 uint64 中时，您将得到一个错误：

method overflow(c: uint64) {
  if c > 0 {
    var d: uint64 := c + 1;
    assert d > 0;
  }
}

这项技术主要用于证明您的程序没有溢出。相反，如果您想推理一个有意使用二进制补码算法的程序，您可以使用位向量来实现，如下所示：

method overflow(c: bv64) {
  if c > 0 {
    assert c + 1 > 0;
  }
}

Bitvectors 是 Dafny 相对较新的新增功能（好吧，不是最近，但在过去几年），根据我的经验，除非您专门推理一段按位执行的代码，否则它们并没有被广泛使用操作（例如，加密）。如果可能的话，我会建议远离位向量。

dafny modeling integer overflow