Is it OK that gcc optimizes away overflow check?

Is it OK that gcc optimizes away overflow check?

[Agner Fog]

I have a program where I check for integer overflow. The program failed, 
and I found that gcc has optimized away the overflow check. I filed a 
bug report and got the answer:
> Integer overflow is undefined. You have to check before the fact, or compile
> >  with -fwrapv.  
( http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49820 )

I disagree for several reasons:

1). It is often easier and more logical to check for overflow after it 
happens than before. It can be quite complicated to write a code that 
predicts an overflow before it happens, in a portable way that works 
with all integer sizes. Checking for overflow after it happens is the 
only way that is sure to work in a hypothetical system that uses 
something else than 2's complement representation.

2). This is a security problem. It takes a very twisted mind to predict 
that your code is not safe when you are actually checking for overflow.

3). I think that you are interpreting the C/C++ standard in an 
over-pedantic way. There are good reasons why the standard says that the 
behavior in case of integer overflow is undefined. 2's complement 
wrap-around is not the only possible behavior in case of overflow. Other 
possibilities are: saturate, signed-magnitude wrap-around, reserve a bit 
pattern for overflow, throw an exception. If a future implementation 
uses internal floating point representation for integers then an 
overflow might variously cause loss of precision, INF, NAN, or throw an 
exception. I guess this is what is meant when the standard says the 
behavior is undefined. What the gcc compiler is doing is practically 
denying the existence of overflow ( 
http://www.mail-archive.com/pgsql-hackers@postgresql.org/msg105239.html 
) to the point where it can optimize away an explicit check for 
overflow. I refuse to believe that this is what the standard-writers 
intended. There must be a sensible compromize that allows the optimizer 
to make certain assumptions that rely on overflow not occurring without 
going to the extreme of optimizing away an overflow check.

4). The bug in my case disappears if I compile with -fwrapv or 
-fno-strict-overflow or without -O2, but this is not my point. My point 
is that gcc should be useful to a programmer with average skills.

5). I have tested many different C++ compilers, and gcc turned out to be 
the one that optimizes best. You guys are doing a fantastic job! Gcc has 
the potential to beat the expensive commercial compilers. But one 
obstackle to its use is that it has a well-deserved reputation for being 
over-pedantic.

Re: Is it OK that gcc optimizes away overflow check?

[Jeffrey Walton]

On Sat, Jul 23, 2011 at 4:13 PM, Agner Fog <agner@agner.org> wrote:
> I have a program where I check for integer overflow. The program failed, and
> I found that gcc has optimized away the overflow check. I filed a bug report
> and got the answer:
>>
>> Integer overflow is undefined. You have to check before the fact, or
>> compile
>> >  with -fwrapv.
>
> ( http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49820 )
>
> I disagree for several reasons:
>
> 1). It is often easier and more logical to check for overflow after it
> happens than before. It can be quite complicated to write a code that
> predicts an overflow before it happens, in a portable way that works with
> all integer sizes. Checking for overflow after it happens is the only way
> that is sure to work in a hypothetical system that uses something else than
> 2's complement representation.
>
> 2). This is a security problem. It takes a very twisted mind to predict that
> your code is not safe when you are actually checking for overflow.
>
> 3). I think that you are interpreting the C/C++ standard in an over-pedantic
> way. There are good reasons why the standard says that the behavior in case
> of integer overflow is undefined. 2's complement wrap-around is not the only
> possible behavior in case of overflow. Other possibilities are: saturate,
> signed-magnitude wrap-around, reserve a bit pattern for overflow, throw an
> exception. If a future implementation uses internal floating point
> representation for integers then an overflow might variously cause loss of
> precision, INF, NAN, or throw an exception. I guess this is what is meant
> when the standard says the behavior is undefined. What the gcc compiler is
> doing is practically denying the existence of overflow (
> http://www.mail-archive.com/pgsql-hackers@postgresql.org/msg105239.html ) to
> the point where it can optimize away an explicit check for overflow. I
> refuse to believe that this is what the standard-writers intended. There
> must be a sensible compromize that allows the optimizer to make certain
> assumptions that rely on overflow not occurring without going to the extreme
> of optimizing away an overflow check.
>
> 4). The bug in my case disappears if I compile with -fwrapv or
> -fno-strict-overflow or without -O2, but this is not my point. My point is
> that gcc should be useful to a programmer with average skills.
>
> 5). I have tested many different C++ compilers, and gcc turned out to be the
> one that optimizes best. You guys are doing a fantastic job! Gcc has the
> potential to beat the expensive commercial compilers. But one obstackle to
> its use is that it has a well-deserved reputation for being over-pedantic.

Its really too bad that GCC does not offer something for overflow and
carry. There's been a couple of feature requests for overflow and
carry testing when the CPU supports it, but I don't believe its gained
any momentum (what does that say about secure programming practices?):
 * http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48580
 * http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49467

Jeff

Re: Is it OK that gcc optimizes away overflow check?

[Ian Lance Taylor]

Agner Fog <agner@agner.org> writes:

> I have a program where I check for integer overflow. The program
> failed, and I found that gcc has optimized away the overflow check. I
> filed a bug report and got the answer:
>> Integer overflow is undefined. You have to check before the fact, or compile
>> >  with -fwrapv.  
> ( http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49820 )
>
> I disagree for several reasons:

I see that I've already been quoted in the bug report.  Here I'll just
stress that I think it's important that gcc implement the relevant
standards.  There are arguments on both sides of an issue like whether a
compiler should optimize based on strict overflow.  When facing
arguments on both sides, which should we pick?  When possible and
feasible, we pick the alternative which is written in the standard.
That seems to me to be the most reasonable solution to such a problem.


> 1). It is often easier and more logical to check for overflow after it
> happens than before. It can be quite complicated to write a code that
> predicts an overflow before it happens, in a portable way that works
> with all integer sizes. Checking for overflow after it happens is the
> only way that is sure to work in a hypothetical system that uses
> something else than 2's complement representation.

It's reasonably straightforward to check for overflow of any operation
by doing the arithmetic in unsigned types.  By definition of the
language standard, unsigned types wrap rather than overflow.


> 2). This is a security problem. It takes a very twisted mind to
> predict that your code is not safe when you are actually checking for
> overflow.

I certainly recommend that the security conscious use
-fno-strict-overflow or -Wno-strict-overflow, along with a number of
other options such as -fstack-protector.  gcc serves a number of
different communities, though.  Many programmers have no reason to be
security conscious.  Repeating myself rhetorically, what should be the
default behaviour?  The one documented in the standard.


> 3). I think that you are interpreting the C/C++ standard in an
> over-pedantic way. There are good reasons why the standard says that
> the behavior in case of integer overflow is undefined. 2's complement
> wrap-around is not the only possible behavior in case of
> overflow. Other possibilities are: saturate, signed-magnitude
> wrap-around, reserve a bit pattern for overflow, throw an
> exception. If a future implementation uses internal floating point
> representation for integers then an overflow might variously cause
> loss of precision, INF, NAN, or throw an exception. I guess this is
> what is meant when the standard says the behavior is undefined. What
> the gcc compiler is doing is practically denying the existence of
> overflow (
> http://www.mail-archive.com/pgsql-hackers@postgresql.org/msg105239.html
> ) to the point where it can optimize away an explicit check for
> overflow. I refuse to believe that this is what the standard-writers
> intended. There must be a sensible compromize that allows the
> optimizer to make certain assumptions that rely on overflow not
> occurring without going to the extreme of optimizing away an overflow
> check.

It would be interesting to try to write such a compromise.


> 4). The bug in my case disappears if I compile with -fwrapv or
> -fno-strict-overflow or without -O2, but this is not my point. My
> point is that gcc should be useful to a programmer with average
> skills.

There are many many ways to cut yourself when using C++.  Personally I
suspect that a programmer with average skills should stick to Go or an
interpreted language.

Ian

Re: Is it OK that gcc optimizes away overflow check?

[Ian Lance Taylor]

Jeffrey Walton <noloader@gmail.com> writes:

> Its really too bad that GCC does not offer something for overflow and
> carry. There's been a couple of feature requests for overflow and
> carry testing when the CPU supports it, but I don't believe its gained
> any momentum (what does that say about secure programming practices?):
>  * http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48580
>  * http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49467

I apologize for the cliched response, but gcc is free software.  This
kind of feature is typically implemented by the person who cares the
most.  Perhaps you could be that person.

Ian

Re: Is it OK that gcc optimizes away overflow check?

[Agner Fog]

On 25-07-2011 08:04, Ian Lance Taylor wrote:
> There are arguments on both sides of an issue like whether a compiler 
> should optimize based on strict overflow. When facing arguments on 
> both sides, which should we pick? When possible and feasible, we pick 
> the alternative which is written in the standard. That seems to me to 
> be the most reasonable solution to such a problem. 
My point is that you are over-interpreting the standard when you 
conclude that the compiler is allowed to do anything in case of overflow.
> It's reasonably straightforward to check for overflow of any operation
> by doing the arithmetic in unsigned types.  By definition of the
> language standard, unsigned types wrap rather than overflow.
This is still optimized away without warning:
> #include <stdlib.h>
>
> int func(int x) {
>    int y = abs(x);
>    if ((unsigned int)y > ~(0u) >> 1)  y = 123;
>    return y;
> }
Unsigned and signed don't overflow at the same point. There is no 
straightforward way you can convert the overflow of the abs() function 
to an unsigned wraparound.

Is this what you call reasonably straightforward:
>    int x, y;
>    if ((unsigned int)x == ~(~0u >> 1))  { /* deal with overflow */}
>    else y = abs(x);
The code will become ugly and unreadable if you fill it with checks like 
this. And it still relies on the 2's complement, which is not guaranteed 
by the standard.
> I certainly recommend that the security conscious use
> -fno-strict-overflow or -Wno-strict-overflow, along with a number of
> other options such as -fstack-protector.  gcc serves a number of
> different communities, though.  Many programmers have no reason to be
> security conscious.  Repeating myself rhetorically, what should be the
> default behaviour?  The one documented in the standard.
You don't know that you need to be security conscious until it is too 
late :-)
>> 3). I think that you are interpreting the C/C++ standard in an
>> over-pedantic way. There are good reasons why the standard says that
>> the behavior in case of integer overflow is undefined. 2's complement
>> wrap-around is not the only possible behavior in case of
>> overflow. Other possibilities are: saturate, signed-magnitude
>> wrap-around, reserve a bit pattern for overflow, throw an
>> exception. If a future implementation uses internal floating point
>> representation for integers then an overflow might variously cause
>> loss of precision, INF, NAN, or throw an exception. I guess this is
>> what is meant when the standard says the behavior is undefined. What
>> the gcc compiler is doing is practically denying the existence of
>> overflow (
>> http://www.mail-archive.com/pgsql-hackers@postgresql.org/msg105239.html
>> ) to the point where it can optimize away an explicit check for
>> overflow. I refuse to believe that this is what the standard-writers
>> intended. There must be a sensible compromize that allows the
>> optimizer to make certain assumptions that rely on overflow not
>> occurring without going to the extreme of optimizing away an overflow
>> check.
> It would be interesting to try to write such a compromise.
I think it would be more sound to use pragmas than command line options. 
A pragma could be placed precisely at the place in the code where there 
is a problem, telling whether overflow should be ignored or not. If you 
apply a command line option to a specific module somewhere in the 
makefile of a big project, other people working on the same project 
would not know why it is there and it could easily be messed up when the 
project is restructured.

The compiler could either use the safe options by default and produce 
warning messages at missed optimization opportunities, or use unsafe 
options by default and produce warning messages when it makes unsafe 
optimizations.

> There are many many ways to cut yourself when using C++.  Personally I
> suspect that a programmer with average skills should stick to Go or an
> interpreted language.
I don't think Go is mature enough to be the first choice of beginners. 
The same applies to D.
Java, C#, VB and the like are terribly slow in my opinion.

Re: Is it OK that gcc optimizes away overflow check?

[Andrew Haley]

On 23/07/11 21:13, Agner Fog wrote:
> I have a program where I check for integer overflow. The program failed, 
> and I found that gcc has optimized away the overflow check. I filed a 
> bug report and got the answer:
>> Integer overflow is undefined. You have to check before the fact, or compile
>>>  with -fwrapv.  
> ( http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49820 )
>
> 5). I have tested many different C++ compilers, and gcc turned out to be 
> the one that optimizes best.

Well yes, and one of the reasons for this is that we take advantage of
integer overflow being undefined.  There is an entire class of
optimizations (loop induction variable optimization) that is difficult
of impossible without taking advantage of this.  We don't do this kind
of thing without good reason.

We can't promise you that in every case gcc will do what you would
like it to do,  However, we have thought long and hard about it.

Andrew.

Re: Is it OK that gcc optimizes away overflow check?

[Agner Fog]

On 25-07-2011 11:43, Andrew Haley wrote:
> On 23/07/11 21:13, Agner Fog wrote:
>> 5). I have tested many different C++ compilers, and gcc turned out to be
>> the one that optimizes best.
> Well yes, and one of the reasons for this is that we take advantage of
> integer overflow being undefined.  There is an entire class of
> optimizations (loop induction variable optimization) that is difficult
> of impossible without taking advantage of this.  We don't do this kind
> of thing without good reason.
Actually, I think we can have the cake and eat it here. If gcc behaves 
reasonably safe by default and then makes warnings in case of missed 
optimization opportunities. The programmer should then have the 
opportunity to enable the desired optimizations, for example with 
pragmas at the critical places in the code. If the programmer doesn't 
need the best optimization then he would not enable those warnings and 
would be safe without having to care.

We already have the opportunity to allow the optimizer to ignore pointer 
aliasing at specific places with the 'restrict' keyword. It would be 
nice to have a similar opportunity to tell the compiler where it can 
ignore overflow.

Re: Is it OK that gcc optimizes away overflow check?

[Andrew Haley]

On 07/25/2011 04:37 PM, Agner Fog wrote:
> 
> On 25-07-2011 11:43, Andrew Haley wrote:
>> On 23/07/11 21:13, Agner Fog wrote:
>>> 5). I have tested many different C++ compilers, and gcc turned out to be
>>> the one that optimizes best.
>> Well yes, and one of the reasons for this is that we take advantage of
>> integer overflow being undefined.  There is an entire class of
>> optimizations (loop induction variable optimization) that is difficult
>> of impossible without taking advantage of this.  We don't do this kind
>> of thing without good reason.

> Actually, I think we can have the cake and eat it here. If gcc
> behaves reasonably safe by default and then makes warnings in case
> of missed optimization opportunities. The programmer should then
> have the opportunity to enable the desired optimizations, for
> example with pragmas at the critical places in the code.

We already give people wrapping integer arithmetic if their program
really needs it.  It's only really a band-aid until they fix their
programs.

> If the programmer doesn't need the best optimization then he would
> not enable those warnings and would be safe without having to care.

gcc is already safe, though: we don't do any optimizations that
generate incorrect code.  Why should people who write correct C be
penalized for the benefit of those who don't?  This is, I accept,
more of a philosophical question.

> We already have the opportunity to allow the optimizer to ignore
> pointer aliasing at specific places with the 'restrict' keyword. It
> would be nice to have a similar opportunity to tell the compiler
> where it can ignore overflow.

It'd really be a new type: wrapping integer arithmetic.  This is
rather a big ask for a compiler like gcc, and IMO this is really one
for the standard, not for us.

IMO the problem is that you don't really accept that your program is
wrong, despite the fact that the standard says that it has undefined
behaviour.

Andrew.

Re: Is it OK that gcc optimizes away overflow check?

[me22]

On Mon, Jul 25, 2011 at 01:31, Agner Fog <agner@agner.org> wrote:
>
> My point is that you are over-interpreting the standard when you conclude
> that the compiler is allowed to do anything in case of overflow.
>

How is signed overflow any different from dereferencing a null
pointer? UB is UB.

Re: Is it OK that gcc optimizes away overflow check?

[Ian Lance Taylor]

Agner Fog <agner@agner.org> writes:

> On 25-07-2011 08:04, Ian Lance Taylor wrote:
>> There are arguments on both sides of an issue like whether a
>> compiler should optimize based on strict overflow. When facing
>> arguments on both sides, which should we pick? When possible and
>> feasible, we pick the alternative which is written in the
>> standard. That seems to me to be the most reasonable solution to
>> such a problem. 
> My point is that you are over-interpreting the standard when you
> conclude that the compiler is allowed to do anything in case of
> overflow.

I don't think so.  gcc's treatment of signed overflow is the same as its
treatment of a number of other aspects of the standard.  The standard
says that signed overflow is undefined behaviour.  The standard says
that a valid program may not rely on undefined behaviour.  Therefore,
gcc can reasonably conclude that signed overflow can not occur.


>> It's reasonably straightforward to check for overflow of any operation
>> by doing the arithmetic in unsigned types.  By definition of the
>> language standard, unsigned types wrap rather than overflow.
> This is still optimized away without warning:
>> #include <stdlib.h>
>>
>> int func(int x) {
>>    int y = abs(x);
>>    if ((unsigned int)y > ~(0u) >> 1)  y = 123;
>>    return y;
>> }

If you are trying to test whether abs(x) overflows, then that is not the
right test.  You have to test before the operation, not after.


> Unsigned and signed don't overflow at the same point. There is no
> straightforward way you can convert the overflow of the abs() function
> to an unsigned wraparound.
>
> Is this what you call reasonably straightforward:
>>    int x, y;
>>    if ((unsigned int)x == ~(~0u >> 1))  { /* deal with overflow */}
>>    else y = abs(x);
> The code will become ugly and unreadable if you fill it with checks
> like this. And it still relies on the 2's complement, which is not
> guaranteed by the standard.

This should work reliably:

#include <stdlib.h>
int func(int x) {
  unsigned int y = (unsigned int) x;
  if (y == -y)
    return 123;
  return abs(x);
}


> You don't know that you need to be security conscious until it is too
> late :-)

That could well be true.  Nevertheless, it does not follow that gcc
should assume that you know what you want.  I have come around to
believing that the first step in being security conscious is to not use
C/C++.  They can be used in a fully secure manner by experts.  However,
you are concerned about non-experts, and I think that history has
demonstrated clearly that C/C++ can not be used securely by non-experts.
Signed overflow is just one tiny aspect of security problems caused by
C/C++.


>>> 3). I think that you are interpreting the C/C++ standard in an
>>> over-pedantic way. There are good reasons why the standard says that
>>> the behavior in case of integer overflow is undefined. 2's complement
>>> wrap-around is not the only possible behavior in case of
>>> overflow. Other possibilities are: saturate, signed-magnitude
>>> wrap-around, reserve a bit pattern for overflow, throw an
>>> exception. If a future implementation uses internal floating point
>>> representation for integers then an overflow might variously cause
>>> loss of precision, INF, NAN, or throw an exception. I guess this is
>>> what is meant when the standard says the behavior is undefined. What
>>> the gcc compiler is doing is practically denying the existence of
>>> overflow (
>>> http://www.mail-archive.com/pgsql-hackers@postgresql.org/msg105239.html
>>> ) to the point where it can optimize away an explicit check for
>>> overflow. I refuse to believe that this is what the standard-writers
>>> intended. There must be a sensible compromize that allows the
>>> optimizer to make certain assumptions that rely on overflow not
>>> occurring without going to the extreme of optimizing away an overflow
>>> check.
>> It would be interesting to try to write such a compromise.
> I think it would be more sound to use pragmas than command line
> options. A pragma could be placed precisely at the place in the code
> where there is a problem, telling whether overflow should be ignored
> or not. If you apply a command line option to a specific module
> somewhere in the makefile of a big project, other people working on
> the same project would not know why it is there and it could easily be
> messed up when the project is restructured.

__attribute__ ((optimize ("-fno-strict-overflow"))) should work already
at the function level.  Some work has been done toward making _Pragma
work at the statement or expression level, but it's hard to implement in
gcc's framework.  That will be the way to go going forward, I think.


> The compiler could either use the safe options by default and produce
> warning messages at missed optimization opportunities, or use unsafe
> options by default and produce warning messages when it makes unsafe
> optimizations.

Or the compiler could use the language standard by default, and produce
warning messages upon request when it makes potentially unsafe
optimizations.  That is what we are already doing today.

Ian

Re: Is it OK that gcc optimizes away overflow check?

[Agner Fog]

On 25-07-2011 08:04, Ian Lance Taylor wrote:
> It's reasonably straightforward to check for overflow of any operation 
> by doing the arithmetic in unsigned types. By definition of the 
> language standard, unsigned types wrap rather than overflow. 
I tried some more google search on this problem. It is quite common to 
check for overflow after the fact, so obviously many programmers are 
unaware of the problem.

The safe solution is described in a recent CERT paper: 
https://www.securecoding.cert.org/confluence/display/seccode/INT32-C.+Ensure+that+operations+on+signed+integers+do+not+result+in+overflow

The CERT paper recommends this check for overflow before adding two 
signed integers on a 2's complement machine:

|if| |( ((si1^si2) | (((si1^(~(si1^si2) & INT_MIN)) + si2)^si2)) >= 0) {|
|||/* handle error condition */|
|} ||else| |{|
|||sum = si1 + si2;|
|}|

Now, imagine doing something like this before every +, -, *, /, etc. in 
your code! If this is necessary then the C/C++ language is useless. We 
are in deep trouble now and we desperately need a better solution.

A security conscious programmer will typically replace an array with a 
SafeArray class with bounds checking. But even this will not work if the 
array index is the result of a calculation that can overflow, which 
almost all calculations can.

Your suggestion to use __attribute__ ((optimize 
("-fno-strict-overflow"))); was an excellent idea. Unfortunately it 
doesn't work. The compiler says: warning: âoptimizeâ attribute directive 
ignored.

We need to be constructive here. We want the optimizations, but we also 
want to check if the optimizations go wrong. I think the compiler should 
be able to generate warnings for every unsafe optimization, especially 
when removing a branch. The compiler generates a warning when optimizing 
away  if (a+5 < a)  but not when optimizing away  if (abs(a)<0).

Some compilers make a warning whenever optimizing away a branch, saying 
something like "warning: condition is always false". A branch that 
cannot be taken is quite likely to be the symptom of a logical error, so 
such a warning will be useful I think, and it would catch an overflow 
check that is optimized away. Would that generate too many warnings? 
That depends on the programming style, but in most cases I think it 
would be useful, and of course you can turn off the warnings.

Re: Is it OK that gcc optimizes away overflow check?

[Andrew Haley]

On 26/07/11 10:38, Agner Fog wrote:

> We need to be constructive here. We want the optimizations, but we
> also want to check if the optimizations go wrong. I think the
> compiler should be able to generate warnings for every unsafe
> optimization,

Continuing to describe these as "unsafe optimizations" is tendentious
at best, and doesn't help the discussion to continue in a polite way.

> especially when removing a branch. The compiler generates a warning
> when optimizing away if (a+5 < a) but not when optimizing away if
> (abs(a)<0).

I think you'd be surprised at just how many warnings would be
generated.

Consider

  for (i = 0; i < limit; i++)
    f(i * 2);

which can be rewritten to

  tmp = limit * 2;
  for (i = 0; i < tmp; i++)
    f(i);

but only if you know integer overflow in i*2 can't occur.

This kind of thing happens all the time, in many programs.  It isn't
usually a problem because the programmer "just knows" that i*2 is less
than INT_MAX.

Andrew.

Re: Is it OK that gcc optimizes away overflow check?

[Ian Lance Taylor]

Agner Fog <agner@agner.org> writes:

> Now, imagine doing something like this before every +, -, *, /,
> etc. in your code! If this is necessary then the C/C++ language is
> useless. We are in deep trouble now and we desperately need a better
> solution.

Nobody would suggest using that construction before every arithmetic
operation.  One would only suggest using it before an operation which
may overflow.

You are writing as though wrapping overflow is always the right thing to
do, but that is false.  In code written by a naive programmer, wrapping
on overflow will cause problems just as undefined overflow will.


> Your suggestion to use __attribute__ ((optimize
> ("-fno-strict-overflow"))); was an excellent idea. Unfortunately it
> doesn't work. The compiler says: warning: âoptimizeâ attribute
> directive ignored.

When I compile this test case with current gcc mainline

#include <stdlib.h>
int f (int) __attribute__ ((optimize ("-fno-strict-overflow")));
int f (int i) { return abs (i) < 0; }

the comparison is not optimized away.  So I think that the attribute
does work in current gcc.


> We need to be constructive here. We want the optimizations, but we
> also want to check if the optimizations go wrong. I think the compiler
> should be able to generate warnings for every unsafe optimization,
> especially when removing a branch. The compiler generates a warning
> when optimizing away  if (a+5 < a)  but not when optimizing away  if
> (abs(a)<0).

When I compile this test case

#include <stdlib.h>
int f (int i) { return abs (i) < 0; }

with -O2 -Wstrict-overflow I see this warning:

foo.c:2: warning: assuming signed overflow does not occur when simplifying comparison of absolute value and zero

So I think the compiler does warn about optimizing that comparison away.

Ian

Re: Is it OK that gcc optimizes away overflow check?

[Jeffrey Walton]

On Tue, Jul 26, 2011 at 5:38 AM, Agner Fog <agner@agner.org> wrote:
> On 25-07-2011 08:04, Ian Lance Taylor wrote:
>>
>> It's reasonably straightforward to check for overflow of any operation by
>> doing the arithmetic in unsigned types. By definition of the language
>> standard, unsigned types wrap rather than overflow.
>
> I tried some more google search on this problem. It is quite common to check
> for overflow after the fact, so obviously many programmers are unaware of
> the problem.
>
> The safe solution is described in a recent CERT paper:
> https://www.securecoding.cert.org/confluence/display/seccode/INT32-C.+Ensure+that+operations+on+signed+integers+do+not+result+in+overflow
>
> The CERT paper recommends this check for overflow before adding two signed
> integers on a 2's complement machine:
>
> |if| |( ((si1^si2) | (((si1^(~(si1^si2) & INT_MIN)) + si2)^si2)) >= 0) {|
> |||/* handle error condition */|
> |} ||else| |{|
> |||sum = si1 + si2;|
> |}|
>
> Now, imagine doing something like this before every +, -, *, /, etc. in your
> code! If this is necessary then the C/C++ language is useless. We are in
> deep trouble now and we desperately need a better solution.
Notice CERT does a expr + expr - the intermediate result might be
'undefined' which puts you back in the same boat as before! As I've
said before, its ridiculous to test 'a priori' (I wasn't being
argumentative).

Douglas Gwyn made a similar comment at
https://www.securecoding.cert.org/confluence/display/seccode/INT03-C.+Use+a+secure+integer+library.

Also, CERT is moving towards the AIR integer model. See
http://www.sei.cmu.edu/library/abstracts/reports/10tn008.cfm.

> A security conscious programmer will typically replace an array with a
> SafeArray class with bounds checking. But even this will not work if the
> array index is the result of a calculation that can overflow, which almost
> all calculations can.
>
> Your suggestion to use __attribute__ ((optimize ("-fno-strict-overflow")));
> was an excellent idea. Unfortunately it doesn't work. The compiler says:
> warning: āoptimizeā attribute directive ignored.
>
> We need to be constructive here. We want the optimizations, but we also want
> to check if the optimizations go wrong. I think the compiler should be able
> to generate warnings for every unsafe optimization, especially when removing
> a branch. The compiler generates a warning when optimizing away  if (a+5 <
> a)  but not when optimizing away  if (abs(a)<0).
>
> Some compilers make a warning whenever optimizing away a branch, saying
> something like "warning: condition is always false". A branch that cannot be
> taken is quite likely to be the symptom of a logical error, so such a
> warning will be useful I think, and it would catch an overflow check that is
> optimized away. Would that generate too many warnings? That depends on the
> programming style, but in most cases I think it would be useful, and of
> course you can turn off the warnings.

Jeff

Re: Is it OK that gcc optimizes away overflow check?

[Agner Fog]

On 26-07-2011 16:43, Ian Lance Taylor wrote:
> int f (int i) { return abs (i) < 0; } 

> with -O2 -Wstrict-overflow I see this warning: foo.c:2: warning: 
> assuming signed overflow does not occur when simplifying comparison of 
> absolute value and zero So I think the compiler does warn about 
> optimizing that comparison away. 
You are right. I used -Wall. Unfortunately, -Wall sets 
-Wstrict-overflow=1 and you need |-Wstrict-overflow=2 to catch the abs 
example. Too bad that you can't even rely on -Wall to catch such a 
serious problem. I don't see why a+1<a = false should have a different 
warning level from abs(a)<0 = false.

I think that there is a big difference between optimizing a loop with an 
induction variable, as you mention, and optimizing away a branch. In a 
simple for-loop with i++, it is unlikely that the programmer intended 
any wrap-around. But if there is a branch or loop that can be optimized 
away completely, then it is either violating the programmer's intentions 
or the programmer has made a logical error. A warning would be in place 
in either case. In other words, there is a difference between (1) 
"ignoring overflow allows us to optimize an arithmetic expression or an 
induction variable", and (2) "ignoring overflow allows us to optimize 
away a branch". The latter situation should be regarded as more serious 
and therefore give a warning at a lower warning-level. Then we would be 
more likely to catch the situation where an intended overflow check is 
optimized away. I wonder if it is possible to make such a distinction in 
the compiler?

|

Re: Is it OK that gcc optimizes away overflow check?

[Andrew Haley]

On 07/26/2011 11:35 AM, Andrew Haley wrote:

> Consider
> 
>   for (i = 0; i < limit; i++)
>     f(i * 2);
> 
> which can be rewritten to
> 
>   tmp = limit * 2;
>   for (i = 0; i < tmp; i++)
>     f(i);

duh.

  int tmp = limit * 2;
  for (i = 0; i < tmp; i += 2)
    f(i);

Andrew.

Re: Is it OK that gcc optimizes away overflow check?

[Ian Lance Taylor]

Agner Fog <agner@agner.org> writes:

> On 26-07-2011 16:43, Ian Lance Taylor wrote:
>> int f (int i) { return abs (i) < 0; } 
>
>> with -O2 -Wstrict-overflow I see this warning: foo.c:2: warning:
>> assuming signed overflow does not occur when simplifying comparison
>> of absolute value and zero So I think the compiler does warn about
>> optimizing that comparison away. 
> You are right. I used -Wall. Unfortunately, -Wall sets
> -Wstrict-overflow=1 and you need |-Wstrict-overflow=2 to catch the abs
> example. Too bad that you can't even rely on -Wall to catch such a
> serious problem. I don't see why a+1<a = false should have a different
> warning level from abs(a)<0 = false.

It is uncommon to simply write abs(a) < 0.  It is more common to use
abs(a) in an expression where the compiler can apply an optimization by
assuming that abs(a) is always positive.  It's not clear that all such
cases deserve a warning with -Wall.  The general idea of -Wall is that
it should issue warnings which apply to all code written by all
programmers.  While -Wall may issue false positives, it should only do
so when the code is easy to rewrite to avoid the warning.  I don't think
implicit assumptions that abs(a) is positive rise to that level.  I
concede that there are reasonable counterarguments here.  Arguing about
which warnings should be issued at which levels is a matter of opinion,
not a matter of fact.

In any case, I think the root of your different opinion is one we've
touched on before: you seem to be implicitly assuming that all C/C++
programmers should be security conscious.  I am implicitly assuming that
the choice to use C/C++ means that the compiler should default to
trusting the programmer.  The compiler offers options here, such as
-Wstrict-overflow, for those who want them, but the default is to trust
the programmer.  I think that that default behaviour is closer to the
so-called spirit of C.


> I think that there is a big difference between optimizing a loop with
> an induction variable, as you mention, and optimizing away a
> branch. In a simple for-loop with i++, it is unlikely that the
> programmer intended any wrap-around. But if there is a branch or loop
> that can be optimized away completely, then it is either violating the
> programmer's intentions or the programmer has made a logical error. A
> warning would be in place in either case. In other words, there is a
> difference between (1) "ignoring overflow allows us to optimize an
> arithmetic expression or an induction variable", and (2) "ignoring
> overflow allows us to optimize away a branch". The latter situation
> should be regarded as more serious and therefore give a warning at a
> lower warning-level. Then we would be more likely to catch the
> situation where an intended overflow check is optimized away. I wonder
> if it is possible to make such a distinction in the compiler?

It is very difficult to make this sort of distinction in the compiler,
because these warnings are issued after many optimizations have already
been applied.  You must also consider the effect of preprocessor macros
here: many C/C++ macros are written with the intention that the compiler
simplify them.

However, I would not go so far as to say that the distinction you draw
is impossible, and I would encourage you to experiment to see if it
possible to distinguish these cases in the compiler.

Ian

Re: Is it OK that gcc optimizes away overflow check?

[Agner Fog]

On 26-07-2011 18:37, Andrew Haley wrote:
> On 07/26/2011 11:35 AM, Andrew Haley wrote:
>
>> Consider
>>
>>    for (i = 0; i<  limit; i++)
>>      f(i * 2);
>>
>> which can be rewritten to
>>
>>    int tmp = limit * 2;
>>    for (i = 0; i<  tmp; i += 2)
>>      f(i);
>>
I tried your example. It doesn't make an induction variable because it 
can do i*2 with the LEA instruction at no extra cost. With i*11 it makes 
two counters:

for (i=0, k=0; i<limit; i++, k+=11) f(k);

I can't make it do what we both expect unless limit is a compile-time 
constant:

for (k=0; k<limit*11; k+=11) f(k);

The reason I'm asking is that it would be interesting to know whether it 
is better to use signed or unsigned integers in order to get the best 
optimizations. I would publish that in my optimization manuals ( 
http://www.agner.org/optimize/#manuals )

Can you give any examples where optimization is better for signed 
integers than for unsigned, or vice versa?

Re: Is it OK that gcc optimizes away overflow check?

[Vincent Lefevre]

On 2011-07-25 17:21:42 +0100, Andrew Haley wrote:
> gcc is already safe, though: we don't do any optimizations that
> generate incorrect code.

Not always (but bugs have been reported about incorrect optimizations).

-- 
Vincent Lefèvre <vincent@vinc17.net> - Web: <http://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / Arénaire project (LIP, ENS-Lyon)

Re: Is it OK that gcc optimizes away overflow check?

[Andrew Haley]

On 07/31/2011 12:30 AM, Vincent Lefevre wrote:
> On 2011-07-25 17:21:42 +0100, Andrew Haley wrote:
>> gcc is already safe, though: we don't do any optimizations that
>> generate incorrect code.
> 
> Not always (but bugs have been reported about incorrect optimizations).

Well, obviously we have bugs.  I hope it was clear that we don't
do unsafe optimizations, i.e. those that turn well-defined code
into something that isn't.  Except by mistake!  We're not perfect.

Andrew.