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?

Thanks, Yannick, that's very interesting and I will loop up the papers.

I have been playing around with this example to see how well Frama-C/Jessie/Why... is able to deal with pointers and aliasing.  Below is a variation in which I believe the contract for f holds but I can't verify it.

If you comment out the call to choosePtr, the verification goes through fine.  Frama-C/... correctly figures out that the pointer p must point to k1 or k2 and therefore cannot affect i, j, n, or m.  Pretty smart.   

However if you keep the call to choosePtr in the code, I can't verify the VCs with anything (at least, so far, giving big time limits to all the provers).    I don't think that call should affect anything since the contract to choosePtr says "assign \nothing" and the result of this call is not even used.  

Note that the call doNothing2 does not cause any problems.

-Steve



/* This function just returns one of the two given pointers
 * and doesn't modify anything. */
/*@ requires \valid(p) && \valid(q);
  @ ensures \valid(\result) && (\result==p || \result==q);
  @ assigns \nothing;
  @*/
int* choosePtr(int *p, int *q);

/* This function does absolutely nothing */
/*@ assigns \nothing; @*/
void doNothing2(int *p, int *q);

/*@ 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, k1=0, k2=0;
    int *p;

    doNothing2(&i, &k2);
    choosePtr(&k1, &i); // COMMENT ME OUT AND PROGRAM VERIFIES
    p=choosePtr(&k1, &k2);

    /*@ loop invariant j<=m;
      @ loop variant m-j;
      @*/
    while (j<m) { j++; *p = 10;}
    //@ assert j==m;
    i++;    
  }
  //@ assert i==n;
}


On Oct 25, 2013, at 1:41 AM, Yannick Moy <moy at adacore.com> wrote:

> -- 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
> 
> 
> 
> 
> 
> _______________________________________________
> Frama-c-discuss mailing list
> Frama-c-discuss at lists.gforge.inria.fr
> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/frama-c-discuss