涉及数组的验证

Question

首先，我要感谢 Rustan 和整个社区为 Dafny 所做的工作。这是一门神奇的语言！

我正在写硕士论文，内容是关于使用 Dafny 对虚拟机进行形式验证。

这就是我定义虚拟机（精简版）的方式：

class VM
{
    var v: array<bv8>;
    var I: bv16;
    var memory: array<bv8>;
    predicate Valid()
      reads this
    {
        v.Length == 16
        && memory.Length == 0x0FFF
    }

    constructor Init()
      ensures Valid()
    {
        v := new bv8[16];
        I := 0;
        memory := new bv8[0x0FFF];
    }
}

到目前为止一切顺利。我有几种方法可以改变这台机器的状态。特别是，这里有一个：

method parse_opcode_registers(vm: VM, opcode: bv16)
  requires vm.Valid()
  modifies vm`I, vm.v
{
    var i: int := 0;
    var bound := ((opcode & 0x0F00) >> 8) as int;

    if opcode & 0xF0FF == 0xF065
    {
        while i < bound && vm.I as int < vm.memory.Length
          decreases bound - i
        {
            vm.v[i] := vm.memory[vm.I];
            i := i + 1;
            vm.I := vm.I + 1;
        }
    }
}

这通过了 Dafny 的验证。但是，当存在此方法的调用者时会出现问题。即，以下代码将产生错误 call may violate context's modifies clause:

method Main() {
    var vm := new VM.Init();
    parse_opcode_registers(vm, 0xF018);
}

如有任何提示，我们将不胜感激。

Answer 1

您需要将 ensures fresh(v) 添加到 VM 的 Init 构造函数中。

基本上，问题是 Dafny 很担心，因为 parse_opcode_register 声称要修改 vm.v，但 Dafny 不确定 vm.v 来自哪里。请记住，Dafny 一次分析程序一个方法，因此它在分析 Main 时不会查看构造函数 Init 内部。相反，Dafny 只查看 pre/postcondition。这就是为什么在后置条件中添加 fresh(v) 修复它的原因。

fresh(blah)的意思是blah是在方法执行的过程中新分配的

有关更多信息，请参阅 FAQ question about modifies clauses。

涉及数组的验证

Verification involving arrays

dafny