Dynamic array with Frama-C and Eva

Question

In https://stackoverflow.com/a/57116260/946226 I learned how to verify that a function foo that operates on a buffer (given by a begin and end pointer) really only reads form it, but creating a representative main function that calls it:

#include <stddef.h>

#define N 100
char test[N];

extern char *foo(char *, char *);

int main() {
  char* beg, *end;
  beg = &test[0];
  end = &test[0] + N;
  foo(beg, end);
}

but this does not catch bugs that only appear when the buffer is very short.

I tried the following:

#include <stddef.h>
#include <stdlib.h>
#include "__fc_builtin.h"

extern char *foo(char *, char *);

int main() {
  int n = Frama_C_interval(0, 255);
  uint8_t *test = malloc(n);
  if (test != NULL) {
    for (int i=0; i<n; i++) test[i]=Frama_C_interval(0, 255);

    char* beg, *end;
    beg = &test[0];
    end = &test[0] + n;
    foo(beg, end);
  }
}

But that does not work:

[eva:alarm] frama-main.c:14: Warning: 
  out of bounds write. assert \valid(test + i);

Can I make it work?

Answer 1

As mentioned in anol's comment, none of the abstract domains available within Eva is capable of keeping track of the relation between n and the length of the memory block returned by malloc. Hence, for all practical purposes, it will not be possible to get rid of the warning in such circumstances for a real-life analysis. Generally speaking, it is important to prepare an initial state which leads to precise bounds for the buffer that are manipulated throughout the program (while the content can stay much more abstract).

That said, for smaller experiments, and if you don't mind wasting (quite a lot of) CPU cycles, it is possible to cheat a little bit, by basically instructing Eva to consider each possible length separately. This is done by a few annotations and command-line options (Frama-C 19.0 Potassium only)

#include <stdint.h>
#include <stddef.h>
#include <stdlib.h>
#include "__fc_builtin.h"

extern char *foo(char *, char *);

int main() {
  int n = Frama_C_interval(0, 255);
  //@ split n;
  uint8_t *test = malloc(n);
  if (test != NULL) {
    //@ loop unroll n;
    for (int i=0; i<n; i++) {
      Frama_C_show_each_test(n, i, test);
      test[i]=Frama_C_interval(0, 255);
    }
    char* beg, *end;
    beg = &test[0];
    end = &test[0] + n;
    foo(beg, end);
  }
}

Launch Frama-C with

  frama-c -eva file.c \
          -eva-precision 7 \
          -eva-split-limit 256 \
          -eva-builtin malloc:Frama_C_malloc_fresh

In the code, //@ split n indicates that Eva should consider separately each possible value of n at this point. It goes along with the -eva-split-limit 256 (by default, Eva won't split if the expression can have more than 100 values). //@ loop unroll n ask to unroll the loop n times instead of merging results for all steps.

For the other command-line options, -eva-precision 7 sets the various parameters controlling Eva precision to sensible values. It goes from 0 (less precise than default) up to 11 (maximal precision - don't try it on anything more than a dozen of lines). -eva-builtin malloc:Frama_C_malloc_fresh instructs Eva to create a fresh base address for any call to malloc it encounters. Otherwise, you'd get a single base for all lengths, defeating the purpose of splitting on n in the first place.