Xtykutl

I am trying to prove the correctness of my sorting function 'order' with Frama-C with the ACSL language. I have an additional 'swap' function to permute two values of my array 't'.

EDIT :
I updated my code.

/*@ 

    requires valid (t+ (0..(l-1)));

    requires l > 0;

    requires i<l && j<l && i>=0 && j>=0;

    assigns t[i], t[j];

    ensures t[j] == old(t[i]);

    ensures t[i] == old(t[j]);

*/

void swap(int *t, int l, int i,int j){

  int tmp;

  tmp = t[i];

  t[i] = t[j];

  t[j] = tmp;

  return;

}



/*@ 

    requires valid (t+ (0..(l-1)));

    requires l > 0;

    ensures forall integer k; (0 <= k < l-1) ==> t[k] <= t[k+1]; 

*/

void order(int *t, int l) {

  int i;

  int j;

/*@

    loop assigns i, t[0 .. l-1];

    loop invariant 0<=i<l && i>=0;

    loop invariant forall integer k; (0 <= k<=i) ==> t[k] <= t[k+1]; 

    loop variant l-i;





*/

  for (i=0;i<l;i++) {



/*@

    loop assigns j, t[0 .. l-1];

    loop invariant i<=j<l && i>=0 && j>=0;

    loop invariant  forall  integer k; (0 <= k <= j)  ==> (t[k] <=  t[k+1]);

    loop variant l-j;



*/

    for (j=i; j<l; j++) {



      if (t[i] > t[j]){

    /*@ assert t[i] > t[j] && i<l && j<l && i>=0 && j>=0 ; */

    swap(t, l, i, j);

    /*@ assert t[i] < t[j] && i<l && j<l && i>=0 && j>=0 ; */

      }

    }

  }

}

Thanks for your help!

As always when using WP, it is crucial that all functions called by the function under proof are equipped with a contract with assigns clauses. Furthemore, all loops of said function under proof must have a loop assigns clause. If this is not the case, WP will conclude that any part of the memory state might be modified by the call (resp. the loop), so that it won't be able to say anything meaningful after the corresponding instruction.

Thus, at the very minimum, you should add/replace the existing clause by:

• in the contract of swap, a clause assigns t[i], t[j];
  


• in the loop annotation of the outer loop, a clause loop assigns i, t[0 .. l-1];
  


• in the loop annotation of the inner loop, a clause loop assigns j, t[i .. l-1];
  

As as side note regarding loop assigns:

• they must describe all the potential modifications from the first entry into the loop up to the current step (hence t[i], t[j] is not sufficient, as there might have been other swaps occuring before the current j).


• the index of the loop (here i and j) must be part of the loop assigns, although it is very easy to overlook it and wonder why WP is not happy.

Note that there might be others issues with your annotations, but these are the most obvious ones, and having appropriate assigns clauses is probably the single most important thing to have before attempting to prove deeper functional properties.