Frama-c : Trouble understanding WP memory models

Question

I'm looking for WP options/model that could allow me to prove basic C memory manipulations like :

• memcpy : I've tried to prove this simple code :

  struct header_src{
    char t1;
    char t2;
    char t3;
    char t4;
  };
  
  struct header_dest{
    short t1;
    short t2;
  };
  
  /*@ requires 0<=n<=UINT_MAX;
    @ requires \valid(dest);
    @ requires \valid_read(src);
    @ assigns (dest)[0..n-1] \from (src)[0..n-1];
    @ assigns \result \from dest; 
    @ ensures dest[0..n] == src[0..n];
    @ ensures \result == dest;
  */
  void* Frama_C_memcpy(char *dest, const char *src, uint32_t n);
  
  int main(void)
  {
    struct header_src p_header_src;
    struct header_dest p_header_dest;
    p_header_src.t1 = 'e';
    p_header_src.t2 = 'b';
    p_header_src.t3 = 'c';
    p_header_src.t4 = 'd';
  
    p_header_dest.t1 = 0x0000;
    p_header_dest.t2 = 0x0000;
  
    //@ assert \valid(&p_header_dest);
  
    Frama_C_memcpy((char*)&p_header_dest, (char*)&p_header_src, sizeof(struct header_src));
    //@ assert p_header_dest.t1 == 0x6265;
    //@ assert p_header_dest.t2 == 0x6463;
  }
  

  but the two last assert weren't verified by WP (with default prover Alt-Ergo). It can be proved thanks to Value analysis, but I mostly want to be able to prove the code not using abstract interpretation.

• Cast pointer to int : Since I'm programming embedded code, I want to be able to specify something like:

  #define MEMORY_ADDR 0x08000000
  #define SOME_SIZE 10
  struct some_struct {
      uint8_t field1[SOME_SIZE];
      uint32_t field2[SOME_SIZE];
  }
  // [...]
  // some function body {
      struct some_struct *p = (some_struct*)MEMORY_ADDR;
      if(p == NULL) {
          // Handle error
      } else {
          // Do something
      }
  // } body end
  

I've looked a little bit at WP's documentation and it seems that the version of frama-c that I use (Magnesium-20151002) has several memory model (Hoare, Typed , +cast, +ref, ...) but none of the given example were proved with any of the model above. It is explicitly said in the documentation that Typed model does not handle pointer-to-int casts. I've a lot of trouble to understand what's really going on under the hood with each wp-model. It would really help me if I was able to verify at least post-conditions of the memcpy function.

Plus, I have seen this issue about void pointer that apparently are not very well handled by WP at least in the Magnesium version. I didn't tried another version of frama-c yet, but I think that newer version handle void pointer in a better way.

Thank you very much in advance for your suggestions !

Answer 1

• memcpy

  Reasoning about the result of memcpy (or Frama_C_memcpy) is out of range of the current WP plugin. The only memory model that would work in your case is Bytes (page 13 of the manual for Chlorine), but it is not implemented.

  Independently, please note that your postcondition from Frama_C_memcpy is not what you want here. You are asserting the equality of the sets dest[0..n] and src[0..n]. First, you should stop at n-1. Second, and more importantly, this is far too weak, and is in fact not sufficient to prove the two assertions in the caller. What you want is a quantification on all bytes. See e.g. the predicate memcmp in Frama-C's stdlib, or the variant \forall int i; 0 <= i < n -> dest[i] == src[i];

  By the way, this postcondition holds only if dest and src are properly separated, which your function does not require. Otherwise, you should write dest[i] == \at (src[i], Pre). And your requires are also too weak for another reason, as you only require the first character to be valid, not the n first ones.

• Cast pointer to int

  Basically, all current models implemented in WP are unable to reason on codes in which the memory is accessed with multiple incompatible types (through the use of unions or pointer casts). In some cases, such as Typed, the cast is detected syntactically, and a warning is issued to warn that the code cannot be analyzed. The Typed+Cast model is a variant of Typed in which some casts are accepted. The analysis is correct only if the pointer is re-cast into its original type before being used. The idea is to allow using some libc functions that require a cast to void*, but not much more.

  Your example is again a bit different, because it is likely that MEMORY_ADDR is always addressed with type some_stuct. Would it be acceptable to change the code slightly, and change your function as taking a pointer to this type? This way, you would "hide" the cast to MEMORY_ADDR inside a function that would remain unproven.

Answer 2

I tried this example in the latest version of Frama-C (of course the format is modified a little bit).

for the memcpy case

Assertion 2 fails but assertion 3 is successfully proved (basically because the failure of assertion 2 leads to a False assumption, which proves everything).

So in fact both assertion cannot be proved, same as your problem.

This conclusion is sound because the memory models used in the wp plugin (as far as I know) has no assumption on the relation between fields in a struct, i.e. in header_src the first two fields are 8 bit chars, but they may not be nestedly organized in the physical memory like char[2]. Instead, there may be paddings between them (refer to wiki for detailed description). So when you try to copy bits in such a struct to another struct, Frama-C becomes completely confused and has no idea what you are doing.

As far as I am concerned, Frama-C does not support any approach to precisely control the memory layout, e.g. gcc's PACKED which forces the compiler to remove paddings.

I am facing the same problem, and the (not elegant at all) solution is, use arrays instead. Arrays are always nested, so if you try to copy a char[4] to a short[2], I think the assertion can be proved.

for the Cast pointer to int case

With memory model Typed+cast, the current version I am using (Chlorine-20180501) supports casting between pointers and uint64_t. You may want to try this version.

Moreover, it is strongly suggested to call Z3 and CVC4 through why3, whose performance is certainly better than Alt-Ergo.