'KeY' in Java 的形式验证无法证明数组重置循环

Question

目前我正在尝试掌握一些用于 Java 程序的 formal verification with the KeY 工具。

这是我的键注释 Java 代码：

public class Test {
    public int[] a;

    /*@ public normal_behavior
    @ ensures (\forall int x; 0<=x && x<a.length; a[x]==1);
    @*/
    public void fillArray() {
        int i = 0;
        while(i < a.length) {
            a[i] = 1;
            i++;
        }
    }
}

令我惊讶的是 KeyY，它无法证明当前程序根据其规范是有效的。 Key 在目标 54 失败。当前目标 window 显示：

 self.a.<created> = TRUE,
 wellFormed(heap),
 self.<created> = TRUE,
 Test::exactInstance(self) = TRUE,
 measuredByEmpty
==>
 self.a = null,
 self = null,
 {exc:=null || i:=0}
   \<{
         try {
             method-frame(source=fillArray()@Test, this=self)
             : {
                 while (i<this.a.length) {
                   this.a[i] = 1;
                   i++;
                 }
               }
         }
         catch (java.lang.Throwable e) {
             exc = e;
         }
     }\> (\forall int x; (x <= -1 | x >= self.a.length | self.a[x] = 1) & self.<inv> & exc = null)

不太理解：规范证明失败的主要原因是什么？

Answer 1

失败的最基本原因是，如果证明者在方法中发现无限循环 - 那么它就无法遵循没有 loop invariant 规范的方法规范。

因此，对于每个无限循环，我们必须指定一个循环不变量。循环不变量是一些规则，它对每个循环迭代都成立 。每个循环都可以有自己特定的不变规则。所以Java有规范的代码必须固定为：

public class Test{ public int[] a; /*@ public normal_behavior @ ensures (\forall int x; 0<=x && x<a.length; a[x]==1); // method post-condition @ diverges true; // not necessary terminates @*/ public void fillArray() { int i = 0; /*@ loop_invariant @ 0 <= i && i <= a.length && // i ∈ [0, a.length] @ (\forall int x; 0<=x && x<i; a[x]==1); // x ∈ [0, i) | a[x] = 1 @ assignable a[*]; // Valid array location @*/ while(i < a.length) { a[i] = 1; i++; } } }

考虑如何指定方法最难的部分是找出循环不变量。但与此同时 - 这是最有趣的。出于原因，我将重复此循环的不变量：

i ∈ [0, a.length]
x ∈ [0, i) | a[x] = 1

并且此条件在 ANY 迭代的循环中永远不会改变。这就是为什么它是 不变的.

顺便说一句，如果正式规范正确 - 我们可以扔掉 TDD 并进行单元测试 window。如果程序可以根据其规范在数学上被证明是正确的，谁会关心运行时间的结果？

如果规范很好并且代码语义经过验证 - 那么没有任何 可以在程序执行中出错 - 这是肯定的。正因为如此 - 形式验证是一个非常有前途的领域。

'KeY' in Java 的形式验证无法证明数组重置循环

Formal verification with 'KeY' in Java fails to prove array reset loop

java

formal-verification

jml

key-formal-verification