static-analysisframa-cacsl

ACSL "assigns" annotation for inner structs and fields of C code


Suppose we have such a data structure:

#typedef struct
{
int  C_Field;
}C;

#typedef struct
{
C B_Array[MAX_SIZE];
}B;

#typedef struct
{
 B A_Array[MAX_SIZE];
}A;

It seems that Frama-C doesn’t assign a location for a field of a struct of type C in the following example:

/*@
  assigns Arg->A_Array[0..(MAX_SIZE - 1)].B_Array[0..(MAX_SIZE - 1)].C_Field;
*/
void Initialize (A * Arg);

Is the above annotation acceptable by Frama-C at all?

The code is elaborated as follows. The main goal is to reset the field C_Field to 0:

/*@ predicate 
      ResetB (B * Arg) =
        \forall integer Index; 0<= Index < MAX_SIZE ==>
                 Arg -> B_Array[Index].C_Field == 0;
*/

//@ assigns * Arg;
// Even I tried this:
//@ assigns Arg -> A_Array[0..(MAX_SIZE - 1)];
void Initialize (A * Arg)
{
 /*@ loop invariant 0 <= Index <= MAX_SIZE;
     loop invariant ResetB(&(Arg->A_Array[Index]));
     loop assigns Index, Arg -> A_Array[0..(MAX_SIZE - 1)];
 */
 for (int Index = 0; Index < MAX_SIZE; Index++)
  {
    Reset(&(Arg -> A_Array[Index]));
  }
}

/*@ assigns Arg -> B_Array[0..(MAX_SIZE - 1)];
    ensures ResetB(Arg);      
*/
void Reset(B * Arg)
{
 /*@ loop invariant 0 <= Index <= MAX_SIZE;
     loop invariant \forall integer i; 0<= i < Index ==>
                     Arg -> B_Array[i].C_Field == 0;
     loop assigns Index, Arg -> B_Array[0..(MAX_SIZE - 1)];
 */
 for (int Index = 0; Index < MAX_SIZE; Index++)
 {
  Arg -> B_Array[Index].C_Field = 0;
 }
}

The contract of the function Reset is satisfied but the contract of the function Initialize is not. How to write a correct "assigns" for the contract of Initialize?


Solution

  • Assuming that you're using plugin WP (see comment above), your main issue is that you haven't written a loop assigns for your loop in the Initialize function. loop assigns are mandatory for each loop appearing in the function(s) over which you want to use WP. In addition, if your contract has ensures clauses, you'll very likely need loop invariant, again for every single loop in the code under analysis.

    Update With the code you have provided, and frama-c Silicon, the only thing that is not proved with frama-c -wp file.c is the loop invariant in Initialize about ResetB. The reason why it is not proved is that it is wrong. The real invariant should read \forall integer i; 0<=i<Index ==> ResetB(&(Arg->A_Array[i])). With the following complete example, everything gets discharged, at least with Silicon:

    #define MAX_SIZE 100
    
    typedef struct
    {
    int  C_Field;
    int D_Field;
    }C;
    
    typedef struct
    {
    C B_Array[MAX_SIZE];
    }B;
    
    typedef struct
    {
     B A_Array[MAX_SIZE];
    }A;
    
    /*@ predicate 
          ResetB (B * Arg) =
            \forall integer Index; 0<= Index < MAX_SIZE ==>
                     Arg -> B_Array[Index].C_Field == 0;
    */
    
    void Reset(B * Arg);
    
    // @ assigns * Arg;
    // Even I tried this:
    //@ assigns Arg -> A_Array[0..(MAX_SIZE - 1)];
    void Initialize (A * Arg)
    {
     /*@ loop invariant 0 <= Index <= MAX_SIZE;
         loop invariant \forall integer i; 0<=i<Index ==> ResetB(&(Arg->A_Array[i]));
         loop assigns Index, Arg -> A_Array[0..(MAX_SIZE - 1)];
     */
     for (int Index = 0; Index < MAX_SIZE; Index++)
      {
        Reset(&(Arg -> A_Array[Index]));
      }
    }
    
    /*@ assigns Arg -> B_Array[0..(MAX_SIZE - 1)];
        ensures ResetB(Arg);
    */
    void Reset(B * Arg)
    {
     /*@ loop invariant 0 <= Index <= MAX_SIZE;
         loop invariant \forall integer i; 0<= i < Index ==>
                         Arg -> B_Array[i].C_Field == 0;
         loop assigns Index, Arg -> B_Array[0..(MAX_SIZE - 1)];
     */
     for (int Index = 0; Index < MAX_SIZE; Index++)
     {
      Arg -> B_Array[Index].C_Field = 0;
     }
    }