Frama-C-discuss mailing list archives

This page gathers the archives of the old Frama-C-discuss archives, that was hosted by Inria's gforge before its demise at the end of 2020. To search for mails newer than September 2020, please visit the page of the new mailing list on Renater.

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Frama-c-discuss] how does Frama-C infer missing invariants?

-- Stephen Siegel (2013-10-24)
> The simple program below is verified by Frama-C+Jessie+AltErgo.   What is a little surprising is that it still verifies if you leave out the "loop invariant i<=n;" for the inner loop.  I think I remember reading somewhere that Frama-C can infer some invariants and frame conditions automatically.  I assume something like that is going on here, but I don't remember where I read about it and would like to understand how it works.

No, that's a different issue here, see below.

> I spend a bit of time making my students do Hoare logic proofs like this by hand, and drill into them that anything you want to "know" after the loop terminates had better be in the loop invariant, but then they use Frama-C and see that isn't true!

Your statement that the loop "forgets" everything about variables is true for classical Hoare logic proofs, but not for proofs using Why3 (the underlying generator of formulas behind Jessie plug-in). In classical Hoare logic, you quantify over all variables for the loop-rule, so anything that is not given in the loop invariant is lost. In Why3, the weakest-precondition calculus is more clever than that: it only quantifies over variables that are modified in the loop! Since "i" and "n" in your code are not modified in the inner loop, their values are maintained, as well as the relation "i<n".

> /*@ requires n>=0 && m>=0; */
> void f(int n, int m) {
>  int i=0;
> 
>  /*@ loop invariant i<=n;
>    @ loop variant n-i;
>    @*/
>  while (i<n) {
>    int j=0;
> 
>    /*@ loop invariant j<=m;
>      @ loop invariant i<=n;
>      @ loop variant m-j;
>      @*/
>    while (j<m) { j++; }
>    //@ assert j==m;
>    i++;
>  }
>  //@ assert i==n;
> }


It is even slightly better than that: Why3 quantifies over every variable that is modified on a path that stays in the loop. So if you modify "z" only on paths that exit the loop, Why3 maintains its value through the loop. Here, it really depends on how the C loop is translated into a Why3 loop (the level at which Why3 operates), but I think it should work with the translation in Jessie.

When I present weakest-preconditions during a presentation, I always say it's "old" ideas from the 70's (Hoare, Dijkstra), except the ideas that make it usable in practice are much more recent: Jean-Christophe Filli?tre for the above effect computation (1996) and Rustan Leino for the efficient generation of formulas (2005).
--
Yannick Moy, Senior Software Engineer, AdaCore