News for hackers. Stuff that matters.
Re:How undefined signed overflow enables optimizations in GCC by pak on Sunday February 21, 2016 @04:50PM (#11146753)
Wasn't there substantial controversy over gcc optimizing away certain code that tried to check for integer overflows?

Check out this infamous thread: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=30475 ...it gets pretty nasty!

The takeaway is that although overflow is technically undefined, a lot of security-related code was naively implemented by checking for overflows occurring in the most typical way (wraparound), and this check began to be removed by this sort of optimization. This made some pragmatically minded security folks quite angry, because although such behavior is technically undefined by the spec, it was the most widely used method of defending against overflows, and recognizing that such code was already everywhere in the wild they feared all the vulnerabilities that would be introduced by gcc dropping branches for i > i + proposed_increment.

Re:How undefined signed overflow enables optimizations in GCC by bluecalm on Sunday February 21, 2016 @07:00PM (#11147358)
>>The takeaway is that although overflow is technically undefined

As they say: technically correct is the best kind of correct.

>>This made some pragmatically minded security folks quite angry

They sound very entitled to me. The C standard is clear on the issue, it's not some arcane hidden thing, it's just a fundamental behavior of basic types in the language. It's very annoying to read the entitled comments from a person who is clearly in the wrong bashing the GCC crew.

>> it was the most widely used method of defending against overflows, and recognizing that such code was already everywhere in the wild they feared all the vulnerabilities that would be introduced by gcc dropping branches for i > i + proposed_increment.

As mentioned by maintainers in the thread there is already a flag to catch unsigned overflows. They even mentioned a way to catch those overflows in the code.

I want a compiler to be technically correct and do optimizations which are possible as the whole point of writing things in C is for them to be fast and efficient. It's nice that GCC has quite a big repertoire of flags, checks, sanity checks, warnings, sanitizers etc. They are very helpful. Demanding that the core compiler doesn't use the language specs to produce better code is pathetic though.

It also didn't "break" any real world things. You just need to use proper compiler flags to compile your non-conforming code if you want a newer version of the compiler. Then thank the hard working compiler maintainers for providing those to you as they could've spent their time on something more fun than fixing shitty code for you.

/rant

Re:How undefined signed overflow enables optimizations in GCC by userbinator on Sunday February 21, 2016 @08:03PM (#11147598)
The C standard is clear on the issue

The problem is succinctly summarised by the saying "In theory, there is no difference between theory and practice. In practice, there is." Unfortunately what most programmers think of as "C" is subtly different from how the standard defines it. In other words, perhaps we should fix compilers (and eventually the standard) to match reality instead of the other way around.

The standard even states in the section on undefined behaviour that "behaving during translation or program execution in a documented manner characteristic of the environment" --- exactly what C programmers are usually expecting from UB --- is a possible choice.

Re:How undefined signed overflow enables optimizations in GCC by to3m on Sunday February 21, 2016 @09:20PM (#11147977)
Yes. People are quick to point to the standard when it comes to compilers doing something surprising, and quick to use this as evidence that programmers are silly to expect the expected. But if compilers did exactly what these programmers expect, they could point to the standard just the same...

(At least this article provides a good explanation of advantages to be had from being aggressively pedantic about UB. Many by way of evidence just wave their hands and claim people are stupid.)

Re:How undefined signed overflow enables optimizations in GCC by username223 on Sunday February 21, 2016 @10:45PM (#11148293)
> (At least this article provides a good explanation of advantages to be had from being aggressively pedantic about UB. Many by way of evidence just wave their hands and claim people are stupid.)

This. While it doesn't show how much real programs benefit from these UB assumptions (or how many new security bugs are introduced...), at least it has some explanations. Still, you have to ask yourself whether the compiler is a tool to help you do your work, or a perverse, pedantic, and frustrating adversary. The ultimate "UB optimizer" would do its best to find tiny corners of undefined behavior in your program, then replace the whole thing with "exit(0)".

Re:How undefined signed overflow enables optimizations in GCC by eru on Monday February 22, 2016 @06:50PM (#11155322)
That would be an interesting exercises. Of course, the whole thing is only interesting if it comes with a proof of justification. Otherwise it's too easy for real world C programs: they are all undefined.
Re:How undefined signed overflow enables optimizations in GCC by stouset on Monday February 22, 2016 @01:09AM (#11148884)
If you don't go by the spec, what do you go by? Intuition? What if yours is different from someone else's?

In this case as well, acknowledging that signed integer overflow is undefined behavior allows for more consistent behavior in certain circumstances. For instance, the compiler knows that `x < x + c`, where `c > 0`, and optimize it to `true`. Even if you don't care about the optimization, is it not equally surprising that such a statement could ever be `false`?

No matter which way you go, some behavior is going to be surprising. And in these scenarios, the only plausible thing to do so is to follow the standard, so at least there's a consistent ideal that everyone's intuitions can converge to, which is crucially important. Each compiler implementing a different C-alike standard just leads to more confusion.

Re:How undefined signed overflow enables optimizations in GCC by userbinator on Monday February 22, 2016 @01:48AM (#11149010)
If you don't go by the spec, what do you go by?

To quote the standard, "a documented manner characteristic of the environment."

If the machine is two's complement (which is the vast majority of them), then you'd expect that behaviour. If it's sign-magnitude or one's complement or saturating, then the behaviour would be different but still consistent.

Even if you don't care about the optimization, is it not equally surprising that such a statement could ever be `false`?

Overflows wrapping around is not surprising, it's what decades of computing hardware (or centuries if you include mechanical calculators like https://en.wikipedia.org/wiki/Pascal%27s_Calculator ) have always done.

Re:How undefined signed overflow enables optimizations in GCC by stouset on Friday February 26, 2016 @01:39PM (#11183122)
> If the machine is two's complement (which is the vast majority of them), then you'd expect that behaviour. If it's sign-magnitude or one's complement or saturating, then the behaviour would be different but still consistent.

How is this different in practice from undefined behavior, other than the compiler can't take advantage of it for optimizations?

Re:How undefined signed overflow enables optimizations in GCC by Spivak on Monday February 22, 2016 @01:27AM (#11148951)
Maybe a better way to illustrate the surprising behavior is that

if (x < x + c) { // block }

if (0 < c) { // block }

are not equivalent statements if you add overflow wrapping into the spec. What if the processor your application is running on doesn't do two's compliment arithmetic? Does gcc need to emulate this behavior to comply with the spec?

Re:How undefined signed overflow enables optimizations in GCC by rdc12 on Sunday February 21, 2016 @08:32PM (#11147753)
Except that different programmers subtly different flavour of C is different from others. For a handful of features it may work but in general I doubt it.
Re:How undefined signed overflow enables optimizations in GCC by pcwalton on Monday February 22, 2016 @12:43PM (#11152657)
> In other words, perhaps we should fix compilers (and eventually the standard) to match reality instead of the other way around.

Without an analysis of the performance loss from removing this optimization, that would be irresponsible.

The authors of GCC were not stupid. They understood that these optimizations can be important for performance, and that's why they implemented them. When this came up on the mailing list several years ago, Ian Lance Taylor found several places this optimization was kicking in in GCC itself.

It is not OK to just randomly avoid doing optimizations allowed by the C standard because they might trigger bugs. C depends on undefined behavior for performance. You depend on these compiler optimizations to get good performance out of the programs you run every day.

Re:How undefined signed overflow enables optimizations in GCC by nkurz on Monday February 22, 2016 @01:54PM (#11153287)
It is not OK to just randomly avoid doing optimizations allowed by the C standard because they might trigger bugs. C depends on undefined behavior for performance. You depend on these compiler optimizations to get good performance out of the programs you run every day.

Geoff offers a simple succinct example of optimizing based on undefined behavior in another comment in this thread: https://news.ycombinator.com/item?id=11147068

I tested with GCC, Clang, MSVC, and ICC, and found that only GCC removed the checks and optimized the function down to a constant. Clang, MSVC, and ICC instead generated code that matched the programmer's clear intent.

Are you sure they would be better compilers if they matched GCC's behavior here? I agree the GCC authors are far from stupid, but I think there might be a difference in philosophy here rather than just a missed opportunity for optimization.

Re:How undefined signed overflow enables optimizations in GCC by pcwalton on Monday February 22, 2016 @03:39PM (#11154109)
> Are you sure they would be better compilers if they matched GCC's behavior here?

I don't know. Measure it on SPECINT or something.

Re:How undefined signed overflow enables optimizations in GCC by bluecalm on Sunday February 21, 2016 @09:35PM (#11148038)
My point is that we are talking about basic types in C. Something you should learn in your first few hours with the language. It's not some arcane thing like what happens in the pre-processor if you nest things or what happens in some rarely used library function in some never occurring edge case.
Re:How undefined signed overflow enables optimizations in GCC by greggman on Sunday February 21, 2016 @10:05PM (#11148145)
In my experience most people don't get exposed to underflows and overflows when learning programming. It's not until they hit a bug that they actually find out overflows and underflows exist. Then, in my experience they don't go read the spec. They ask a co-worker or google it. They may or may not end up with the correct answer vs an answer that works at the moment.

I've used C since the mid 80s and C++ since the late 90s. Overflow for me always worked as a normal 2's compliment overflow on every project from 1985 to 2011 so I had no reason to question that it might be undefined.... until it was. Even more interesting is when asking a mailing list of 200+ C++ experts, the answers for how to actually detect overflow where all over the place. Meaning no one really knew for sure the spec correct way to check even though they were all C++ guys with +15 years experience

There's all kinds of details to languages that are buried in a spec but are not something that comes up "in your first few hours with the language".

Re:How undefined signed overflow enables optimizations in GCC by phicoh on Monday February 22, 2016 @03:54AM (#11149481)
The problem with the C standard is that most programmers treat C as portable assembler whereas from the beginning the group that wrote the standard tried to make it a proper, abstract high-level language.

So we got an enormous disconnect between what programmers expect and what the language really offers.

For a long time, compilers would side with the programmers making sure that optimisations would not break common idiom.

A number of years gcc left that path. So now, for system code, certainly if the code has to be secure, it is better to avoid gcc.

The C standard is in some areas extremely complex, and it doesn't make sense to expect all programmers to completely understand what is essentially a broken standard.

Re:How undefined signed overflow enables optimizations in GCC by eru on Monday February 22, 2016 @06:53PM (#11155342)
Perhaps we should even leave C as a language for system code. (System code has to be correct and secure first. Optimization for speed comes second, and is only needed for a few small, very hot code paths.)
Re:How undefined signed overflow enables optimizations in GCC by userbinator on Monday February 22, 2016 @12:51AM (#11148807)
Relevant article expressing the same sentiment: http://blog.metaobject.com/2014/04/cc-osmartass.html
Re:How undefined signed overflow enables optimizations in GCC by pekk on Monday February 22, 2016 @12:41AM (#11148761)
I'm sorry if you feel gcc maintainers are unappreciated, that's not good. Clearly no compiler can rescue programmers from every security mistake they might make.

But raising security concerns is not "entitled," insecure-by-default is not okay, and "it's fast and the standard lets us get away with it" is not a sufficient defense.

Maybe non-conforming code should be penalized by making it slow, not by causing another large-scale public scourge like Heartbleed. Such risks are not just between gcc maintainers and inept programmers, there's a lot more at stake than that.

Re:How undefined signed overflow enables optimizations in GCC by PeCaN on Monday February 22, 2016 @01:57AM (#11149051)
Doing something that you _know_ is wrong, then complaining when the compiler happens to break it, is entitled if I've ever seen it.

I don't think I would trust code that relies on undefined behavior to be secure. That doesn't really sound that safe.

Re:How undefined signed overflow enables optimizations in GCC by asgfoi on Monday February 22, 2016 @06:30AM (#11150086)
As mentioned by maintainers in the thread there is already a flag to catch unsigned overflows. They even mentioned a way to catch those overflows in the code.

I can't seem to find that flag. Only ftrapv for signed, but none for unsigned. Do you know what flag is it exactly?

Re:How undefined signed overflow enables optimizations in GCC by asgfoi on Monday February 22, 2016 @11:41AM (#11152086)
As mentioned by maintainers in the thread there is already a flag to catch unsigned overflows

Too bad such a flag doesn't exist.

Re:How undefined signed overflow enables optimizations in GCC by nly on Sunday February 21, 2016 @07:41PM (#11147518)
GCC has builtins for overflow-detecting arithmetic operations, and has done for a while. These generally compile down to one of the jump instruction flavours on x86.

https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins...

Re:How undefined signed overflow enables optimizations in GCC by gpvos on Sunday February 21, 2016 @10:56PM (#11148341)
These look very unknown to me. How portable are these? If only GCC has these, I am not going to use them at all.
Re:How undefined signed overflow enables optimizations in GCC by frankzinger on Monday February 22, 2016 @12:49AM (#11148794)
Clang also has them: http://clang.llvm.org/docs/LanguageExtensions.html#builtin-f..., under the heading "Checked Arithmetic Builtins".
Re:How undefined signed overflow enables optimizations in GCC by cnvogel on Monday February 22, 2016 @06:08AM (#11150002)
You could implement them as static/inline functions for compilers that lack the builtins (using a bunch of comparisons with SHORT_/INT_MAX, ...) , which would be slower but for things explicitly meant as security check, probably worth the cost.

I've used them to replace explicit checks for overflow in some DSP related code which tried to implement saturation. The gcc builtins also were much faster than tedious "manual" checks.

Re:How undefined signed overflow enables optimizations in GCC by tobias3 on Monday February 22, 2016 @06:44AM (#11150147)
Here is how to do integer overflow checks from the same author as the OP in the bug report:

https://www.fefe.de/intof.html