frama-calt-ergo

Proofs for code that relies on unsigned integer overflow?


How should I approach proving the correctness of code like the following, which, to avoid some inefficiency, relies on modular arithmetic?

#include <stdint.h>

uint32_t my_add(uint32_t a, uint32_t b) {
    uint32_t r = a + b;
    if (r < a)
        return UINT32_MAX;
    return r;
}

I've experimented with WP's "int" model, but, if I understand correctly, that model configures the semantics of logical integers in POs, not the formal models of C code. For example, the WP and RTE plugins still require and inject overflow assertion POs for the unsigned addition above when using the "int" model.

In cases like this, can I add annotations stipulating a logical model for a statement or basic block, so I could tell Frama-C how a particular compiler actually interprets a statement? If so, I could use other verification techniques for things like defined-but-often-defect-inducing behaviors like unsigned wrap-around, compiler-defined behaviors, nonstandard behaviors (inline assy?), etc., and then prove correctness for the surrounding code. I'm picturing something similar to (but more powerful than) the "assert fix" used to inform some static analyzers that certain properties hold when they can't derive the properties for themselves.

I'm working with Frama-C Fluorine-20130601, for reference, with alt-ergo 95.1.


Solution

  • I'm working with Frama-C Fluorine-20130601

    Glad to see that you found a way to use the latest version.

    Here are some random bits of information that, although they do not completely answer your question, do not fit in a StackOverflow comment:

    Jessie has:

    #pragma JessieIntegerModel(modulo)
    

    The above pragma makes it consider that all overflows (both the undefined signed ones and the defined unsigned ones) wrap around (in the same of signed overflows, in 2's complement arithmetic). The generated proof obligations are much harder, because they contain additional modulo operations everywhere. Of automated theorem provers, typically only Simplify is able to do something with them.

    In Fluorine, RTE does not warn about a + b by default:

    $ frama-c -rte t.c -then -print
    [kernel] preprocessing with "gcc -C -E -I.  t.c"
    [rte] annotating function my_add
    /* Generated by Frama-C */
    typedef unsigned int uint32_t;
    uint32_t my_add(uint32_t a, uint32_t b)
    {
      uint32_t __retres;
      uint32_t r;
      r = a + b;
      if (r < a) {
        __retres = 4294967295U;
        goto return_label;
      }
      __retres = r;
      return_label: return __retres;
    }
    

    RTE can be made to warn about the unsigned addition with option -warn-unsigned-overflow:

    $ frama-c -warn-unsigned-overflow -rte t.c -then -print
    [kernel] preprocessing with "gcc -C -E -I.  t.c"
    [rte] annotating function my_add
    /* Generated by Frama-C */
    typedef unsigned int uint32_t;
    uint32_t my_add(uint32_t a, uint32_t b)
    {
      uint32_t __retres;
      uint32_t r;
      /*@ assert rte: unsigned_overflow: 0 ≤ a+b; */
      /*@ assert rte: unsigned_overflow: a+b ≤ 4294967295; */
      r = a + b;
      …
    

    But that's precisely the opposite of what you want so I don't see why you would do that.