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

Question

Currently I'm trying to grasp a little bit of formal verification with the KeY tool for Java programs.

Here is my key-annotated Java code:

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++;
        }
    }
}

To my surprise KeY, it fails to prove that the current program is valid according to its specification. KeY fails at goal 54. Current goal window shows:

 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)

I don't really comprehend: What is the main cause of failing to prove the specification?

Answer 1

The most basic reason of failure was that if the prover found an unbounded loop in a method - then it couldn't follow a method specification without a loop invariant specification.

Thus for each unbounded loop we must specify a loop invariant. A loop invariant is some rule which holds true for each loop iteration. Every loop can have its own specific invariant rule. So Java code with specification must be fixed to:

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++;
    }
  }

}

The hardest part in thinking about how to specify method will be to find-out a loop invariant. But at the same time - it's most interesting. For the sake of reason I'll repeat this loop's invariant:

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

And this condition never changes in the loop in ANY iteration. That's why it is an invariant.

BTW, if formal specification is done right - we can throw away TDD and unit testing out out the window. Who cares about run-time results if program can be mathematically proven to be correct according to its specification?

If the specification is good and code semantics is proven - then nothing can go wrong in program execution - that's for sure. Because of that - formal validation is a very promising field.