[Cryptography] GCC bug 30475 (was Re: bounded pointers in C)

[Benjamin Kreuter]

On Thu, 2014-05-01 at 17:36 -0400, Arnold Reinhold wrote:

> After the developers have been told that a specific optimization is
> potentially causing widespread security and safety problems, I think it
> is evil. 

Yeah, and once upon a time people made use of gets().  The response was
to demand that people replace gets() with fgets().  Why should the
response to this class of bug -- relying on undefined behavior in a
safety check -- be any different?

> > I might not have written that line; that line might have been a result
> > of other optimizations.  Here is a simple example:
> > 
> > #include <stdio.h>
> > 
> > void foo(int x, int y) {
> >  if (x > y) {
> >    printf("Greater\n");
> >  } else {
> >    printf("Lesser\n");
> >  }
> > }
> > 
> > int main() {
> >  int x;
> >  scanf("%d\n", &x);
> >  foo(x, x+1);
> >  return 0;
> > }
> > 
> > Copy propagation (a textbook optimization) would cause "if (x > x+1)" to
> > appear.  If the next step is algebraic simplification (also textbook),
> > then the behavior of this code when x is INT_MAX will change.  In fact,
> > on my system GCC goes even further -- it replaces the call to "foo" with
> > a call to "puts:" ...
> 
> Same issue applies. If you know what foo does, why would you write
> "foo(x, x+1);" ?

Maybe I call foo with different parameters in different places and for
maintainability I do not want to copy and paste things.  In context,
calling the function like that might make sense -- especially if it has
a more complicated body that *happens* to reduce to something simple
with (x, x+1) as arguments.

>  If you weren't checking for overflow, it makes no sense.

It makes no sense as a way to check for overflow, since it is dependent
on undefined behavior doing something highly specific.

>  Maybe you really meant to write "foo(x, y+1);" The compiler
> should flag this, not optimize it away.

Yeah and maybe you actually meant to write "foo(y, x+1)" or maybe the
call to foo was spurious.  Compilers cannot really make those kinds of
judgments.  It could be that "foo(x, x+1)" is intentional, and in some
situations that would make sense.

> Which course of action makes more sense, rewriting all the security
> sensitive software written in C or getting the compiler to stop
> removing signed integer overflow checks? 

"x > x+1" is not a check for signed integer overflow.  Even if the
optimizer does not remove it, there is no guarantee that an overflow
would be detected by that.  A compiler might not emit the signed
arithmetic code that you expect.  What you think is "32 bit signed
arithmetic" could actually be compiled as "64 bit signed arithmetic
using a sign-extended representation," and then "x > x+1" will be false
even if X=INT_MAX.

> > 
> >> Isn't it more reasonable to expect the developers of C to respond to
> >> the safety needs of their users and the public?
> > 
> > The way C programmers do that is by not writing programs with undefined
> > behavior.  Writing programs with undefined behavior is writing programs
> > with bugs.
> 
> If the undefined behavior is a bug, the compiler should treat it as a
> compile time error, not allow it during ordinary compiles and silently
> optimize it away later. 

Consider this function:

int fact(int x) {
  if (x <= 1) return 1;
  else return x * fact(x - 1);
}

Would you expect that to compile, or for it to be an error?  If
potentially undefined behavior is a compiler error, that code cannot
compile, since the multiplication might cause an overflow.  If you only
call the function with a small argument, the behavior is not undefined,
and it would have been a waste of time to write a version that
guarantees no overflow (better to just document the acceptable range of
"x" as a precondition).

> Does what you said above "Writing programs with undefined behavior is
> writing programs with bugs" apply equally to "accessing arrays,
> dereferencing pointers, passing arguments to functions, etc."?

Yes, if your code has undefined behavior it is a bug.

> In your example:
> 
> char c[] = "abcdefghij";
> int z = 55;
> printf("%s %d\n", c+20, z);
> return 0;
> 
> Would your optimizer be justified in silently deleting everything but
> the return, since whatever c+20 points to is clearly undefined?  Can it
> remove all pointer dereferences whenever it can't verify that proper
> bounds checks have taken place?

No, because pointers might be function arguments, functions might be
linked dynamically, etc.  There is no way for a C compiler to verify
that bounds checks occur, any more than that integers are in the proper
range.
 
> > You keep referring to optimizers as saving "nanoseconds" as if we
> > should all believe that optimizers are just toys.  Modern optimizers do
> > more than shave off a few nanoseconds.  In the general case optimizers
> > are better at producing fast code than human beings.  Optimizers can and
> > do analyze code across entire programs, finding simplifications and
> > eliminating unnecessary code.  The difference can be very big in both
> > speed and program size, and it can be measured in dollars saved on
> > equipment, electricity, cooling, etc.
> > 
> 
> If your bank account gets raided, will you be comforted in the
> knowledge that the bank got by with fewer servers?

If your bank runs inefficient code and passes the extra operational
costs on to you, will you be comforted by the knowledge that they did
not use an optimizing compiler?

> Again let's stick to signed integer overflow. How much of this
> performance gain would be lost if signed integer overflow operations
> and their sequela were not optimized away? 

The optimizer is not removing "signed integer overflow."  It is
simplifying expressions based on how they behave under well-defined
circumstances.  Those performance gains are typically large, especially
if you write code that can assume that its preconditions are met (i.e.
that its integer arguments are within some range that will not cause
overflows).

Again, even with optimization disabled the behavior of signed integer
overflows is undefined and cannot be relied on, even if your
architecture uses 2s complement representation.

-- Ben
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 836 bytes
Desc: This is a digitally signed message part
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20140502/812dd62e/attachment.pgp>