static analyser should warn about signed arithmetic overflow

[llvmbot]

Bugzilla Link	9131
Version	trunk
OS	Linux
Reporter	LLVM Bugzilla Contributor
CC	@FlashSheridan,@regehr

Extended Description

GAP (http://www.gap-system.org/) uses the following idiom to try to detect
overflowing multiplication. It is wrong because it uses undefined behaviour
(the result of an overflowing signed multiplication). It would be great if
either the compiler or the static analyser would warn about this.

int mul_overflows(int a, int b) {
int mul = a * b;
// Wrong attempt to detect overflow:
return (mul / b) != a;
}

This is particularly important because the optimizers convert this to
"return false;"!

Here are the real code snippets from GAP (variables have type Int, which
is long int):

...
ex = ex * pow;

    /* check that n*pow fits into the exponent                         */
    if ( ex/pow!=exs || (0<ex && expm<ex) || (ex<0 && expm<-ex) ) {

...

static inline Obj prod_intobjs(Int l, Int r)
{
Int prod;
if (l == (Int)INTOBJ_INT(0) || r == (Int)INTOBJ_INT(0))
return INTOBJ_INT(0);
if (l == (Int)INTOBJ_INT(1))
return (Obj)r;
if (r == (Int)INTOBJ_INT(1))
return (Obj)l;
prod = ((Int)l >> 2) * ((Int)r-1)+1;
if ((prod << 1)>> 1 != prod)
return (Obj) 0;
if ((((Int)l)<<HALF_A_WORD)>>HALF_A_WORD == (Int) l &&
(((Int)r)<<HALF_A_WORD)>>HALF_A_WORD == (Int) r)
return (Obj) prod;
if ((prod -1) / (l >> 2) == r-1)
return (Obj) prod;
else
return (Obj) 0;
}

[llvmbot]

assigned to @tkremenek

[regehr]

A lot of "safe math in C" libraries that I've looked at contain similar undefined behaviors. It's quite hard to avoid. These warnings would be awesome.

[lattner]

This is too expensive (requires dataflow) to catch in the simple warning flags, the static analyzer should handle this someday.

[llvmbot]

+1

I would also like to see the analyzer catch integer over/underflows. These are a very common issue, and often they have security impacts. Detecting them manually in the general case is extremely tedious.

Note that signed overflows are only part of the story. Allowing unsigned over/underflows to happen is usually less bad, but if the resulting values are used in length calculations in an inconsistent way, one can often end up with buffer overflows as a result. I imagine it would be quite tricky to catch these dangerous situations without spewing lots of false positives, but commercial static analyzers do a pretty good job with it, so it is apparently possible. I believe it requires tracking high/low values for each integer throughout the dataflow.