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

[Arnold Reinhold]

On Tue, 22 Apr 2014 00:51 D. Hugh Redelmeier responded:
> | From: Arnold Reinhold <agr at me.com>
> 
> | The events described in the above linked Bugzilla thread regarding Bug 
> | 30475, as I read it, is that the GCC team was informed that the GCC 
> | complier in its common mode of operation is, without any warning, 
> | removing safety checks that have inserted in wide variety of existing 
> | programs; that the safety checks were inserted by competent programmers 
> | who were unaware of any potential problem with their use; that the 
> | safety checks, if left in place, would be functional and could avert 
> | serious security lapses; and that it is not feasible to find all the 
> | instances of these checks and apply proposed workarounds in a reasonable 
> | amount of time and effort.
> 
> I don't like the way the C language handles overflow with signed ints.
> I think signed overflow should, by default, cause a trap.
> 
> But the problem actually lies with the success of the PDP-11.  That
> machine uses a pun: signed and unsigned add of two's complement
> numbers produce the exact same bits of result from the same bits of
> operands.  The only difference is how to interpret the signedness and
> overflow of the result.  So the PDP-11 had a single add instruction.
> It set a lot of condition bits:  the program could test the bits that
> were relevant to the representation intended.  But the computer could
> not trap on overflow because it didn't know if there were an overflow.
> 
> Contrast this with the IBM/360.  It too used two's complement.  But it
> had distinct signed and unsigned add operations (it called the
> unsigned operations "Logical").  It could generate a trap on overflow.
> 
> Almost all important machines after the PDP-11 copied it in this 
> respect (and much else).

The IBM 360 is 50 years old, the PDP-11 is 44. As you suggest, due to their influence twos-complement has become the de facto standard for binary signed integer arithmetic. The C standards have been revised several times since.

> 
> C is a close-to-the-metal language.  The designers didn't wish to
> impose inefficiency on the program.  Furthermore, the C Committee
> tried to be as hardware-agnostic as they could afford.  So the
> committee decided early-on that the result of signed int overflow was
> undefined.  This allowed but didn't require trap-on-overflow.

The leap from "overflows may or may not be trapped" to "the compiler can generate any evil code it want whenever it thinks it sees a possible signed integer overflow" is simply astounding. Criminal in my opinion.

> 
> The assertion
> 	assert(a + 100 > a);
> is nonsense: it assumes a definition of arithmetic overflow that does
> not apply.  I can see that as a human.  But compilers often see tests
> that are redundant, and this just looks redundant.

As you say, C is a close-to-the-metal language. That is a major reason for its popularity, particularly with embedded systems. If translated into machine language in the naive way, the assert statement's test will do just what its author intended on the vast majority of computers out there.  If, on some architecture I am not familiar with, it generates a false abort, the assert will still have done its job in alerting the programmer to a potential problem. The only bad case I can see is if, on our outlier architecture, it allows a bad operation to pass. But that is exactly what removing the assert allows on ALL architectures. 

> 
> I like my compilers to warn me when I write nonsense.  But like
> everyone else, I get on my high horse when there are false positives.
> Redundant code that is intended is hard to separate from redundant
> code that is a mistake.

That of course is a common problem with no universal solution, but one should err on the side of safety, not blissful ignorance. 

> 
> I write a lot of assertions that I hope are redundant.  I love it when the 
> compiler can make them free!

Maybe your management, if your are writing mission critical, or life safety code, might see it differently. Most of us write code expecting to catch all bad conditions.  Assertions are backups in case we missed something. They are helpful when the concern is accidental oversights. They are vital when the concern is active attacks, where a clever attacker might find a way to generate a condition that the compiler considers impossible. 

> 
> I know enough to not write overflow tests that create overflows.  I
> write them to prevent overflows.
 
That can be pretty subtile. See e.g. http://www.gnu.org/software/autoconf/manual/autoconf-2.64/html_node/Signed-Overflow-Examples.html#Signed-Overflow-Examples. 

The revelation that NSA has been working to weaken publically-available computer security has generated a hunt for possible instances where this has happened. I prefer stupidity and arrogance to conspiracy as an explanation for failures, but it is hard to imaging a a more productive win for the state security snoops than compilers that remove safety tests. Most programming is done by mere mortals.  And program maintenance is rarely assigned to top tier coders. Source code, publicly available or purloined, for targeted programs can be fed through an instrumented compiler to find instances where safety tests are removed and these can then be analyzed further for exploitable weaknesses. This bug/feature of C compilers not just an exploit, its an exploit generator, a gift that keeps on giving. Know your tools, indeed.

Arnold Reinhold


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20140423/2876c44c/attachment.html>