Frama-C Prove While Loop with "/*@ ensures"

user_19400032 0
Viewed 99

I am a newbie at Frama-C and I am trying to validate a C code. The code is very basic but somehow I can not validate it.

In summary, I am trying to prove If that function or loop has ever run. For that, I give a variable a value (4) in the beginning. In the function, I change the value to "5", and I try to ensure that the variable 5 at the end.

The Code:

#include <stdio.h>
int x=4;
/*@
ensures x ==5;
*/
int abs(int val){

    int accept=0;
    int count=3;
    /*@
    loop invariant 0 <= count <= \at(count, Pre);
    loop assigns accept,x,count; 
    loop variant count;
    */
    while (count !=0){
        x=5;
        accept =1;
        count--;
    }
    return x;
 }

I give the command to CLI as "frama-c-gui -wp -rte testp4.c" to start frama-c.

As result: Frama-1

But the "*@ ensures x ≡ 5; */" is still unknown.

Is there anyone can help me about this ? If I take "x=5;" to outside of the while loop ( before return) It validates the /*@ ensures x ==5; */

Thanks in advance to everyone who contributed!

verification acsl frama-c c loops
1 Answers

Most of the problems here are related to the use of builtin labels. Here are the labels that we need here:

  • Pre: the state in precondition
  • Post: the state in postcondition
  • LoopEntry: the state when starting the loop
  • Here: the state at the program point where it is used

First things first. I do not known which version of Frama-C you are using but I'd suggest updating ;) . You would have the following error message to prevent a mistake:

[kernel:annot-error] file.c:11: Warning: 
  unbound logic variable count. Ignoring loop annotation

Why? Because you are talking about count in precondition when it does not exist. Note that in old versions of Frama-C, WP might be OK with this because the pre-state and the initialization of local variables was merged in some cases.

What we want is probably something like "the current value of count is somewhere between 0 and the value it had when we started the loop", thus:

loop invariant 0 <= count <= \at(count, LoopEntry);
which is:
loop invariant 0 <= \at(count, Here) <= \at(count, LoopEntry);

Now that we have this (proven) invariant, we want to link the behavior of the loop with the postcondition (currenty, our loop invariant does not say anything about x and WP does not use the body of the loop out of it. That means that we need another invariant that is "when count does not equal to its value when starting the loop, x is 5`".

Thus:

loop invariant count != \at(count, LoopEntry) ==> x == 5 ;

Which allows to have the program entirely proved :) . Final annotated program:

#include <stdio.h>
int x=4;
/*@
  ensures x ==5;
*/
int abs(int val){

  int accept=0;
  int count=3;
  /*@
    loop invariant 0 <= count <= \at(count, LoopEntry);
    loop invariant count != \at(count, LoopEntry) ==> x == 5 ;
    loop assigns accept,x,count; 
    loop variant count;
  */
  while (count !=0){
    x=5;
    accept =1;
    count--;
  }
  return x;
}

Some words about why \at(count, Pre) != 0 ==> \at(x, Post) == 5 (in the comments) does not work:

  • \at(count, Pre) is the value of count in precondition of the function and \at(count, Post) is the value of count in postcondition of the function. Thus, not what we need here.
user_46281250
Related