Proofs for code that relies on unsigned integer overflow?

Question

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.

One problem with your code: Let `a` be `UINT32_MIN` and let `b` be `-1`. How is this handled? (I have no background with your tools/specific compiler) — BLaZuRE, Aug 02 '13 at 11:43

score 1 · Accepted Answer · answered Aug 02 '13 at 22:29

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.

I think that the issue is that the model for r = a + b doesn't seem to allow for overflow in a way that can then be used to reason about the overflow detection done by the next statement. I did try Jessie's (modulo) back on Windows, perhaps I'll try it again here. I'll also look at getting Simplify; alt-ergo may be having trouble proving (in a different routine) that r = a * b doesn't overflow when a and b are limited to prevent overflow. Thanks again for the quick responses. — Barrie Slaymaker, Aug 02 '13 at 23:08

score 1 · Answer 2 · answered Aug 08 '13 at 12:38

You didn't provide the exact command line that you have been using. I guess this is frama-c -wp -wp-rte file.c -pp-annot. In that case, indeed, all assertions that RTE can possibly emit are generated. You can however have a finer control over that, by instructing frama-c to first generate only the categories of RTE that you're interested in (be careful that they are controlled by two kinds of options: the ones of frama-c -rte-help and the -warn-{signed,unsigned}-{overflow,downcast} defined in the kernel), and then launch wp on the result. This is done by frama-c -rte -pp-annot file.c -then -wp By default, rte does not consider unsigned overflow to be an error, so that with the above command line, I'm able to prove that your function respects the following specification:

/*@
  behavior no_overflow:
    assumes a + b <= UINT32_MAX;
    ensures \result == a+b;
  behavior saturate:
    assumes a+b > UINT32_MAX;
    ensures \result == UINT32_MAX;
 */
 uint32_t my_add(uint32_t a,uint32_t b);

Proofs for code that relies on unsigned integer overflow?

2 Answers2