GCC undefined behaviors are getting wild

http://blog.pkh.me/p/37-gcc-undefined-behaviors-are-getting-wild.html

by signa11 • 4 years ago

156 347 4 years ago

blog.pkh.me

If this kind of optimization is unacceptably risky for your use case, you need a different programming language, not a different C compiler.

turminal3• 4 years ago

Do you have any specific languages in mind?

matkoniecz2• 4 years ago

Author of linked article mentions Rust

baq3• 4 years ago

Basically anything else.

raverbashing5• 4 years ago

"unacceptably risky" except I can't think of anything more basic than asking the computer if a > b and it fails at that?

masklinn10• 4 years ago

Why would “basic” and “correct” overlap in any way?

eru28• 4 years ago

UB invades your whole program, not specific lines.

However in this case, the culprit wasn't comparison `a > b`, but assignment `a = b`.

In general, addition like 'a + b' also isn't safe in C.

lamp987• 4 years ago

how does it fail at that? it does exactly what the standard advertises. you need to write standard-compliant code.

sanxiyn15• 4 years ago

No. Just compile with -fno-strict-overflow, like I do.

josephcsible8• 4 years ago

For signed overflow in particular, sure. I was talking more about these kind of optimizations for UB in general.

tgv• 4 years ago

It would seem GCC is doing its very best to make C an irrelevant language. They're taking "-pedantic" a bit too seriously.

mort96• 4 years ago

All optimizing compilers do stuff like this. You yourself ask the compiler to do it when you pass it '-O2'. Its default behavior is, in fact, to not optimize based on the assumption that UB won't happen.

32gbsd• 4 years ago

I knew rust had to be mentioned. But this is a optimization bug. I break my code several times while optimizing thinking a minor change wont matter then end up undoing it all.

proto_lambda4• 4 years ago

It's not a bug. This is perfectly acceptable behaviour according to the language standard. If anything, it's a standard bug.

ototot• 4 years ago

This is not a bug. This is the model of C. You should blame C not GCC.

iforgotpassword6• 4 years ago

I blame GCC. The C standards committee is some out of touch with reality conglomerate working in a vacuum, taking 50 years of language history into account.

I expect my compiler vendor to be on my side, ie produce a compiler that helps me write good software and not get in my way. GCC is doing the opposite, it's deliberately looking to use the standard to fuck me over in the most subtle and unexpected ways. Signed integer overflow is undefined; that gives compiler authors the liberty to make it do anything they want, including well defined things that anyone would expect and find useful. But GCC decides to fuck you over so their devs can give you an arrogant reply and impose their superiority if you show up on their bug tracker.

TazeTSchnitzel• 4 years ago

This is why undefined behaviour is insidious: if a tiny part of your code is undefined behaviour, the behaviour of your entire programme is.

josephcsible8• 4 years ago

Nitpick: it's not the behavior of the program that becomes undefined, but of the execution that it occurs in. For example, consider a program that reads argv[3] without making sure there's at least 4 arguments. If you call it with too few arguments, that entire execution is undefined (even stuff that happens before the out-of-bounds access), but if you call it with enough arguments, it is well-defined and the compiler has to emit code that will work.

masklinn10• 4 years ago

Ah but the trap is that if the compiler can reason that UB always occurs (in reality it will reason that code is dead because the constraints it computes don’t allow for its execution) then it can remove the entire thing.

See Raymond Chen’s well known “undefined behaviour can result in time travel”.

eru28• 4 years ago

Yes. To spell it out: undefined behaviour doesn't just affect specific values nor just the behaviour of your program after triggering UB. It's the entire behaviour of your programme. So UB can 'travel backwards in time'.

Fun fact: not closing a string literal is UB. Ending a non-empty source file in anything other than a newline is also UB.

mlindner3• 4 years ago

I'm expecting this article to make the rust crew go in a crusade again, and I think I might be with them this time.

I think he makes a good point. By having overflow be undefined you leave yourself open to all sorts of issues.

josefx2• 4 years ago

Of course with well defined overflow you can still end up with a nonsense result that just happens to be in your valid range of values. If you don't plan to harden your code against integer overflow manually you need a language that actively checks it for you or uses a variable sized integer to be safe.

ekidd• 4 years ago

I've spent a fair bit of time running a fuzzer on Rust code that parses untrustworthy data. And the thing that saved my code time and time again was that Rust has runtime bounds checks. Even if I messed up index calculations, I'd get a controlled panic, not a vulnerability.

eru28• 4 years ago

Ending up with a nonsense result ain't great, but it's still a step up from losing all guarantees about the behaviour of your program.

By the way, throwing an error on overflow is also a perfectly valid way to get defined behaviour and not end up with a nonsense value.

silon42• 4 years ago

He did harden the code by having an explicit range check.

p0nce3• 4 years ago

Ah someone else spotted it. The author's code is wrong whether signed overflow is well defined or not.

vgatherps2• 4 years ago

Somewhat unfortunately this is valid behavior according to the standard. Having to go through walls of text in a standard to prevent the compiler from deleting your security checks because of how you multiplied two integers seems a bit silly.

Having said that I’m of split feelings here. I work in a very performance sensitive industry and on one hand welcomes the ability of compilers to use the knowledge that certain things “can’t happen” to optimize, without me having to always do these optimizations be hand.

On the other hand, there seem to be so many cases like this one where the “undefined behavior code deleter goes brrrrrr” really overextends its usefulness. The “lalalalala standard say I can do this can’t hear you” finger in your ears attitude from compiler maintainers doesn’t help at all either.

I understand that the way much of this works, propagating “poison/impossible values”, can hide the root cause, so you can’t just say “please do the good undefined behavior optimizations but not the bad, so there’s no easy answer. The outcome in the blog post doesn’t feel like a local optimum though, and it’s not the only place I’ve felt that your options are “potentially slow code” or “pray you were perfect enough to not have your program deleted”

proto_lambda4• 4 years ago

The problem here is that the thing that "can't happen" isn't actually something that can't happen, it's something that isn't allowed to happen according to a many-hundred-page document that approximately nobody reads. It's not something that can be optimised because the compiler can prove it cannot happen, it is allowed to be optimised because the standard says "dear programmer, if you ever make this happen, god help you".

iforgotpassword6• 4 years ago

It's still braindead and idiotic. Every relevant platform nowadays has well defined overflow for signed ints. A sane C compiler should go with that and base its optimizations on it. GCC has been a pile of garbage in this regard for many years now. Its devs get further removed from reality with every year. Treating signed int overflow as undefined should be hidden behind a flag.

josephcsible8• 4 years ago

I think this view is slightly unfair. I think of UB as the compiler saying "when you promised this thing wouldn't happen, I took you at your word. If bad things happen because you lied, they're your fault, not mine."

raverbashing5• 4 years ago

Except this can't happen happens many and many times in practice so maybe it's time the language bureaucrats got off their high horse (but they won't)

pjmlp8• 4 years ago

Even if someone would read all those pages, constraining ourselves to ISO C only, no way that after an year they would still remeber the about 200 UB cases that are documented there.

Which is why everyone should adopt static analysis tooling and enable all the warnings that are related to UB, pointer and casts misuses.

Many think they know better, it is like those that think builders don't need protection gear at a construction site, it is stuff only for the weak.

Asooka5• 4 years ago

Basically, the compiler implements integer addition using an operation that doesn't match the semantics of integer addition in the standard, then hallucinates that it did. That is:

1) The compiler sees an expression like "a += b;" where a and b are signed integers.

2) It emits "add rA rB" in x86 assembly (rA/B being the register a/b is currently in).

3) Technically the machine code emitted does not match the semantics of the source code, since it uses wraparound addition, whereas the C standard says that for the operation to be valid, the values of a and b must be such that no overflow would occur. This is fine however, because the implementation has the freedom to do anything on integer overflow, including just punting the problem to hardware as it did in this case.

4) The compiler proceeds with the rest of the code as if the line above would never overflow. My brother in the machine spirit, you chose to translate my program to a form where integer overflow is defined.

The compiler should either a) trap on integer overflow; or b) accept integer overflow. It will be fine if it chooses either a) or b) situationally, i.e. if we have a loop where assuming no overflow is faster, then by all means - add a precondition check and crash the program if it's false, but don't just assume overflow doesn't happen when you explicitly emit code with well-defined overflow semantics.

The bigger problem is there is pretty much no way to guard against this. The moment your program is longer than one page you're screwed. You may think all your functions are fine, but then you call something from some library, the compiler does some inlining and suddenly there's an integer overflow where you didn't expect, leading to your bounds check being deleted.

atoav• 4 years ago

The hard things about C are knowing all these footguns you are getting yourself into. If our electrical grid was built like this we had no isolation, no fuses, no RCDs and a constant torrent of electrocutions and fires. It is bad engineering.

fps_doug4• 4 years ago

... and people defending the status quo because "you just have to know how electricity works" :-)

oxff3• 4 years ago

On the other hand, there seem to be so many cases like this one where the “undefined behavior code deleter goes brrrrrr” really overextends its usefulness.

I would simply not depend on invoking UB as part of my program's behavior (?).

masklinn10• 4 years ago

Alternatively I would not trust myself with not doing that, which is why I don’t use C.

eru28• 4 years ago

That's the only way to use C correctly.

Alas, it's nearly impossible for a mere mortal to write any non-trivial C code that doesn't have UB.

vgatherps2• 4 years ago

I don't think I ever claimed that one would or should intentionally invoke UB as part of their program's behavior?

lilllly2• 4 years ago

We need a -fsane-c

Then they can add a #pragma optimize(assumes=no-int-overflow, whatever, etc) to precisely add optimizations when needed and you 'know' its safe.

throwaway815232• 4 years ago

Everyone wants that, but when asked for a concrete specification they seem to realize that it is harder than it sounds. Look for John Regehr's blog entries about "Friendly C" for an example. The basic problem here is that C is a terrible language. We should just give up on it by now.

Asooka5• 4 years ago

You can get 99% of the way there with -fno-delete-null-pointer-checks -fno-strict-aliasing -fwrapv . Pretty much every program I've worked on uses those flags, as that's the only way to keep your sanity.

gpderetta15• 4 years ago

-fdwim

Next generation of AI powered compilers will try to interpret code at a more abstract level and infer what the programmer was thinking even if they wrote the wrong thing.

Everything will work perfectly 100% of the time.

sanxiyn15• 4 years ago

This already exists. Don't write standard C, avoid it like the plague. Compile with -fno-strict-overflow -fno-strict-aliasing -fno-delete-null-pointer-checks, like I do, like Linux kernel does, and like everyone sane does.

FpUser2• 4 years ago

I am sort of uneasy with what the optimizing doing in here.

But I would not ever write something like this:

  int32_t i = x * 0x1ff / 0xffff;

Not because I am supersmart and will / can predict how optimizer will fuck it up. It is just that I am paranoid when coding and this type of code just simply hurts my perception for some reason.

saagarjha11• 4 years ago

It seems like a perfectly cromulent line of code to me, assuming you have overflow checks somewhere.

Karliss• 4 years ago

The trap in C is that you can't have overflow checks after the calculations testing if overflow happened by making assumptions about what the UB does. Once the UB has happened it's already too late. What you actually need is input range checks to ensure that following code can perform it's calculations correctly without hitting UB or you need to use helper intrinsics which perform checked math operations.

FpUser2• 4 years ago

As already said it just ruffles my feathers the wrong way. I would not analyze why as I usually have better things to do with my programming time. The best answer I can come up with without thinking is something like this:

overflow is an error. I would prefer the code not to create errors unless absolutely needed.

eru28• 4 years ago

This is the minimal example. For all we know, the original code might have made more sense in context?

hxhxhrra2• 4 years ago

As others are pointing out, the C standard does allow this. There is no safe way to check for undefined behavior (UB) after it has happened, because the whole program is immediately invalidated.

This has caused a Linux kernel exploit in the past [1], with GCC removing a null pointer check after a pointer had been dereferenced. Null pointer dereferences are UB, thus GCC was allowed to remove the following check against null. In the kernel, accessing a null ptr is technically fine, so the Linux kernel is now compiled with -fno-delete-null-pointer-checks, extending the list of differences between standard C and Linux kernel C.

[1] https://lwn.net/Articles/342330/

charcircuit• 4 years ago

the C standard does allow this

The C standard also allows doing it even when there is no UB. C gives implementations a ton of freedom.

xeeeeeeeeeeenu• 4 years ago

Linux kernel is now compiled with -fno-delete-null-pointer-checks

Like many other large C codebases, it also uses -fno-strict-aliasing and -fno-strict-overflow (which is a synonym for "-fwrapv -fwrapv-pointer").

fps_doug4• 4 years ago

We've got a few components written in C that I'm (partially) responsible for. It's mostly maintenance, but for reasons like this I run that code with -O0 in production, and add all those kinds of flags.

I'd be curious to know how much production code today that's written in C is that performance critical, i.e. depends on all those bonkers exploits of UB for optimizations. The Linux kernel seems to do fine without this.

throwaway815232• 4 years ago

-fwrapv introduces runtime bugs on purpose! The last thing you want is an unexpected situation where n is an integer and n+1 is somehow less than n. And of course that bug has good chances of leading to UB elsewhere, such as a bad subscript. If you want to protect from UB on int overflow, -ftrapv (not -fwrapv) is the only sane approach. Then at least you'll throw an exception, similar to range checking subscripts.

It is sad that we don't get hardware assistance for that trap on any widespread cpu, at least that I know of.

pjc504• 4 years ago

because the whole program is immediately invalidated.

The problem is the program isn't invalidated, it's compiled and run.

The malicious compiler introducing security bugs from Ken Thompson's "Reflections on Trusting Trust" is real, and it's the C standard.

I will grant that trying to detect UB at runtime may impose serious performance penalties, since it's very hard to do arithmetic without risking it. But at compile time? If a situation has been statically determined to invoke UB that should be a compile time error.

Also, if an optimizer determines that an entire statement has no effect, that should be at least a warning. (C lack C#'s concept of a "code analysis hint" which have individually configurable severity levels).

tpush6• 4 years ago

If a situation has been statically determined to invoke UB that should be a compile time error.

That's simply not how the compiler works.

There is (presumably, I haven't actually looked) no boolean function in GCC called is_undefined_behavior(). It's just that each optimization part of the compiler can (and does) assume that UB doesn't happen, and results like the article's are then essentially emergent behavior.

eru28• 4 years ago

The problem is the program isn't invalidated, it's compiled and run.

Anything can happen with undefined behaviour, including exactly what you would expect to happen for five years, and then everything breaks.

Compiling and running as if nothing is amiss is exactly how UB is allowed to look like.

Someone2• 4 years ago

If a situation has been statically determined to invoke UB that should be a compile time error.

But you typically can’t prove that. There’s lots of code where you could prove it might happen at runtime for some inputs, but proving that such inputs occur would, at least, require whole-program analysis. The moment a program reads outside data at runtime, chances are it becomes impossible.

If you want to ban all code that might invoke it it boils down to requiring programmers to think about adding checks around every addition, multiplication, subtraction, etc. in their code, and add them to most of them. Programmers then would want the compiler to include such checks for them, and C would no longer be C.

If, as you seem to say, you want to ban a subset that’s easily provable, I think enabling all warnings already does that. See for example https://clang.llvm.org/docs/DiagnosticsReference.html#wargum..., https://clang.llvm.org/docs/DiagnosticsReference.html#warray..., https://clang.llvm.org/docs/DiagnosticsReference.html#winteg... , https://clang.llvm.org/docs/DiagnosticsReference.html#wcompa...

dzaima2• 4 years ago

The example here doesn't have compile-time known undefined behavior though; as-is, the program is well-formed assuming you give it safe arguments (which is a valid assumption in plenty of scenarios), and the check in question is even kept to an extent. Actual compile-time UB is usually reported. (also, even if the compiler didn't utilize UB and kept wrapping integer semantics, the code would still be partly broken were it instead, say, "x * 0x1f0 / 0xffff", as the multiplication could overflow to 0)

The problem with making the compiler give warnings on dead code elimination (which is what deleting things after UB really boils down to) is that it just happens so much, due to macros, inlining, or anything where you may check the same condition once it has already been asserted (by a previous check, or by construction). So you'd need some way to trace back whether the dead-ness comes directly from user-written UB (as opposed to compiler-introduced UB, which a compiler can do if it doesn't change the resulting behavior; or user-intended dead code, which is gonna be extremely subjective) which is a lot more complicated. And dead code elimination isn't even the only way UB is used by a compiler.

kazinator3• 4 years ago

and it's the C standard.

No, it's puerile interpretations of the C standard learned from the comp.lang.c newsgroup and such places rather than from engineering work.

rocqua7• 4 years ago

Thanks for that lwn article.

I had read it a long time ago, and had since forgotten the source. I've spent a few hours trying to find it in bug-trackers. really glad to have the link now, thanks!

kazinator3• 4 years ago

I don't believe that it does. If the invalid arithmetic proceeds without crashing, and produces a value in the int32_t i variable, then that issue is settled. The subsequent statement should behave according to accessing that value.

"Possible undefined behavior ranges from ignoring the situation completely with unpredictable results, to behaving during translation or program execution in a documented manner characteristic of the environment (with or without the issuance of a diagnostic message), to terminating a translation or execution (with the issuance of a diagnostic message)."

Ignoring the situation completely means exactly that: completely. The situation is not being ignored completely if the compilation of something which follows is predicated upon the earlier situation being free of undefined behavior.

OK, so since the situation is not being ignored completely, and translation or execution is not terminated with a diagnostic message, it must be that this is an example of "behaving in a documented manner characteristic of the implementation". Well, what is the characteristic; where is it documented? That part of the UB definition refers to documented extensions; this doesn't look like one.

What is "characteristic of the implementation" is in fact that when you multiply two signed integers together with overflow, that you get a particular result. A predictable result characteristic of how that machine performs the multiplication. If the intent is to provide a documented, characteristics behavior, that would be the thing to document: you get the machine multiplication, like in assembly language.

hxhxhrra2• 4 years ago

I don't believe that it does. If the invalid arithmetic proceeds without crashing, and produces a value in the int32_t i variable, then that issue is settled. The subsequent statement should behave according to accessing that value.

You may dislike it, but that is not how UB in C and C++ works. See [1] for a guide to UB in C/C++ that may already have been posted elsewhere here.

It is a common misconception that UB on a particular operation means "undefined result", but that is not the case. UB means there are no constraints whatsoever on the behavior of the program after UB, often referred to as "may delete all your files". See [2] for a real-world demo doing that.

[1] https://blog.regehr.org/archives/213

[2] https://kristerw.blogspot.com/2017/09/why-undefined-behavior...

MaxBarraclough• 4 years ago

If the invalid arithmetic proceeds without crashing, and produces a value in the int32_t i variable, then that issue is settled. The subsequent statement should behave according to accessing that value.

The C standard imposes no such constraint on undefined behaviour, neither is it the case that real compilers always behave as if it did.

hxhxhrra has already shown this, but here's another good blog post on this kind of thing: https://markshroyer.com/2012/06/c-both-true-and-false/

matheusmoreira• 4 years ago

The C standard doesn't really matter. Standards don't compile or run code. Only thing that matters is what the compilers do. "Linux kernel C" is a vastly superior language simply because it attempts to force the compiler to define what used to be undefined.

This -fno-delete-null-pointer-checks flag is just yet another fix for insane compiler behavior and it's not the first time I've seen them do it. I've read about the Linux kernel's troube with strict aliasing and honestly I don't blame them for turning it off so they could do their type punning in peace. Wouldn't be surprised if they also had lots more flags like -fwrapv and whatnot.

adrian_b• 4 years ago

Even if this solution cannot be used for the Linux kernel, for user programs written in C the undefined behavior should always be converted into defined behavior by using compilation options like "-fsanitize=undefined -fsanitize-undefined-trap-on-error".

Phelinofist• 4 years ago

Why did GCC change x < 0 to -1 < x? I guess it is faster - but why? x >=0 would have also been a valid transformation to archive the same flow

proto_lambda4• 4 years ago

It's just an artifact of decompilation. It's the same operation in machine code (checking the MSB), there's no way to tell which one was used in the original source code.

stop50• 4 years ago

An signed integer uses the leftmost bit for the sign: 00000000 = 0 10000000 = 128 = -128 https://onlinetoolz.net/unsigned-signed#base=2&value=1000000...

WirelessGigabit• 4 years ago

What the purpose of the / 0xffff?

f1shy• 4 years ago

Had the same question. This is the minimal implementation of the error, so there is no clue what was the original purpose.

I think as it is, it indexes a table where the first positions return tab[0], the next ffff/1ff will return tab[1] and so on.

If I see such a code at work I would reject it in less than 1ms

hddqsb• 4 years ago

It should be noted that in this particular case it only happens when optimisations are enabled (-O2).

With -O2: https://godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename...

Without -O2: https://godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename...

[Edited. I originally wrote "It should be noted that this only happens when..." but inserted "in this particular case" after @eru pointed it out.]

eru28• 4 years ago

In this particular case, yes. You can't rely -O0 to save your bacon in general.

pjmlp8• 4 years ago

Usually most UB only shows up when optimizations are turned on.

t0suj4• 4 years ago

I think the lesson here is to stop using signed integer as an index into an array.

eru28• 4 years ago

The lesson is to only use C when absolutely necessary, and regularly use all the sanitizers and other safety tools you can find. Not just when you suspect something fishy.

sanxiyn15• 4 years ago

The lesson is you shouldn't use standard C, until the standard is fixed. Until then, compile with -fno-strict-overflow, like I do.

nly• 4 years ago

C standards fault. GCC has intrinsics that let you do arithmetic safely with overflow checks

Just use them

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

nindalf• 4 years ago

If these intrinsics are used can clang or msvc still compile it?

latency-guy2• 4 years ago

Clang should, MSVC has plans for it but no news since 2018: https://developercommunity.visualstudio.com/t/please-impleme..., so looks like it's a blackhole for now

saagarjha11• 4 years ago

The C standard (finally) fixed this in C23, see <stdckdint.h>.

codedokode7• 4 years ago

Sadly the macros they proposed are ugly, long to type and hard to read. People will not use them.

josephcsible8• 4 years ago

C standards fault.

I take issue with this sentence, since it makes it sound like there's something wrong with the C standard for it, which isn't the case.

eru28• 4 years ago

Huh? There's all kinds of things wrong with the C standard. For example, they really went overboard with the UB even for cases that should have arguably been implementation defined or just throw an error.

Eg ending a non-empty source file with anything but a newline is undefined behaviour. So is not closing a string literal.

kristopolous2• 4 years ago

Those look rather inconvenient. Is there a sane way to keep things infix at least without having to crack open a spew of operator overloading?

Something like #pragma come_on_be_reasonable ?

(This is rhetorical. They point is it shouldn't be every coders personal responsibility to make the tool not be openly hostile. You may take pride in personal mastery of an unreasonable thing but that doesn't make it more acceptable)

sanxiyn15• 4 years ago

Yes there is. Compile with -fno-strict-overflow.

leni536• 4 years ago

In gcc you can use the -ftrapv or -fwrapv compiler options to get defined signed integer overflow arithmetic.

sanxiyn15• 4 years ago

These also work on Clang.

pbsd2• 4 years ago

This has nothing to do with undefined behavior. Switch the code to unsigned integers, where overflow is perfectly defined as wrapping, and the result is exactly the same.

The compiler, to avoid the division, compares x * 0x1ff with 512 * 0xffff instead of x * 0x1ff / 0xffff with 512. This comparison is obviously bunk, since it doesn't take the uppermost bits of the multiplication into account. But so is the original comparison!

You see the same thing happen in Rust -- https://rust.godbolt.org/z/xf67rM77T -- the difference being that there's a second language-level bounds-check inserted at the lookup site.

comex• 4 years ago

It doesn’t matter what x is. Without prior undefined behavior, there is no way to justify “if (i >= 0 && i < sizeof(tab))” passing when (as demonstrated by the printf) i is not actually in that range.

Edit: Though, incidentally, the comparison does not work the way it was probably intended to work. In `i < sizeof(tab)`, `i` is converted to `size_t`, so an unsigned comparison is performed, making the `i >= 0` part redundant. But the result is the same as what was intended.

dathinab2• 4 years ago

That is not how undefined behavior works in C (or C++).

Effects of UB are not temporal or spacial limited to the place where undefined behavior happens.

The moment you enter a compilation unit (assuming no link optimizations) with a state which at some point will run into undefined behavior all bets are of.

EDIT: Yes, UB can "time travel". Compared to that ignoring an if condition iff the UB code was triggered is harmless. Similar it can also "split realities". E.g. a value produced by UB might at one place have the value 1 and at another place a completely different value. E.g. unsigned int overflow values might for an if condition have one value and for the print statment in the condition another and for the index operation again a different value.

EDIT2: Which is why a lot of people which have proper understanding of C++ and don't have a sunken (learn C++) cost fallacy came to the conclusion that using C++ is a bad choice for most use-case.

pbsd2• 4 years ago

Yeah, I was wrong. Mixed up the signed and unsigned cases.

bonzini3• 4 years ago

The author took issue with the compiler removing the i >= 0 part. The compiler did so because it could infer it's true given x >= 0, the only way i < 0 could be true is via integer overflow.

I think the output of the Rust compiler is fine because it uses an unsigned comparison ("ja" as opposed to "jl") to implement the "if".

mytailorisrich2• 4 years ago

In the example, the crash occurred because the compiler removed the i<512 part because without overflow that condition is always true.

eru28• 4 years ago

Hmm, I had expected more from the article given the title.

This is about the least surprising UB. It didn't even travel backwards in time.

pjmlp8• 4 years ago

GCC's UBSan catches it,

runtime error: signed integer overflow: 50000000 * 511 cannot be represented in type 'int'

https://godbolt.org/z/oz9vvj5YM

Another heads up of the dangers of UB optimizations, and why using static analysis is a requirement for C derived languages.

If you aren't using all warnings turned on as errors, disabled implicit conversions and at very least have static analysis on the CI/CD pipeline, you're up for a couple of surprises.

From CppCon 2022, "Purging Undefined Behavior & Intel Assumptions in a Legacy C++ Codebase"

https://www.youtube.com/watch?v=vEtGtphI3lc

saagarjha11• 4 years ago

Note that UBSan is a dynamic analysis tool.

pjmlp8• 4 years ago

Thanks for the correction, one should use those as well on debug builds for integration tests.

eru28• 4 years ago

Indeed. But still a good idea to run at least your test-suite with it. And also with address sanitizer and clang's memory sanitizer, etc. Whatever you can find.

astrange5• 4 years ago

The static analysis is you compile with it and see if there's any trap instructions emitted by the compiler.

(The answer is: yes.)

yaantc• 4 years ago

Yes absolutely, and this is possible today with only open source software. So money is not a barrier.

The sanitizers (UB, address, memory, threads) are supported by both Clang and GCC [1]. Yes that's up to 4 different builds and tests runs but with an automated C/I this is not a big deal.

The Clang static analyzer, with Z3 enabled as a checker, used through CodeChecker [2] is now very good, so much so that I prefer it to a different commercial product showing too many false alarms. Using it on an embedded GCC cross-compiled code base may still require some workarounds, but nothing too bad and this is improving regularly too.

I wouldn't want to do without this. Switching to Rust may not always be possible, and there are big C and C++ code base that will live a long while. Tools like this help and they should be used.

[1] https://github.com/google/sanitizers/

[2] https://codechecker.readthedocs.io/en/latest/

pjmlp8• 4 years ago

Definitly, Java, V8, .NET, Android runtimes still have lots of C++ into them, LLVM and GCC depend on C++ and are comparable to Linux kernel in complexity, GPGPU toolchains, .....

So reboting into any safe alternative, is going to take decades, hence why the first step is still trying to advocate for best practices, even if it feels like a Quixotic endevour.

Asooka5• 4 years ago

Or you know, just turn off UB. I don't know why C still has this, it was useful when we had truly exotic architectures with sign bits &c, but these days it is doing way more harm than good.

gpderetta15• 4 years ago

Or you know, just turn off UB

I'm sure you will be willing to write the GCC PR that implements the required, surely trivial, analysis.

kergonath• 4 years ago

Or you know, just turn off UB.

You cannot “turn off UB”. The behaviour is undefined in the standard, and nothing the compiler can do will make it defined. There is a profound misunderstanding of what undefined behaviour is in a lot of the comments. It is not a compiler setting. The way to make it defined is to change the standard.

gpderetta15• 4 years ago

I keep asking this: in my experience sanitizers and other dynamic checkers have always overperformed, while I'm underwhelmed by static analysis. Do people have different experiences?

pjmlp8• 4 years ago

The biggest issue is that too few use them, most surveys place the number around 10% - 20% in such tooling adoption.

symmetricsaurus2• 4 years ago

There’s no reason to expect the result of integer overflow to be negative, or any particular value at all. It is undefined.

So after checking that x > o there is no way for i (a product and ratio of positive numbers) to become negative.

The only reason this is surprising is that there is an expectation of wrapping on overflow. But this is simply not the behavior of the C virtual machine.

(Maybe today it makes sense to have even C wrap in a two’s-complement way? C is used in many places though, maybe there are still platforms in use that aren’t two’s-complement?)

josephcsible8• 4 years ago

Be careful: it's not just that the result of the multiplication won't be what you expect. The entire execution of the program becomes undefined. For example, if you had an unconditional `puts("hello");` between the multiplication and comparison lines, if the overflow happens, it would be allowed to print "goodbye" instead.

symmetricsaurus2• 4 years ago

Yes, and in particular the compiler can assume that you stay within the defined behavior. That's what's enabling the optimization in removing the i < 0 check.

eqvinox• 4 years ago

While I have been a member of the "unsigned counting variable" minority for a long time, this kinda drives the nails into the coffin for a lot of signed array index / offset use. It's just too big a risk to accidentally have the compiler go YOLO on you for some minor detail you missed.

Also, this UB optimization train has gone way too far and needs to back up a few stations.

I'm gonna say there needs to be a switch to make signed overflow not be UB. Maybe that already exists? starts checking docs

colonwqbang• 4 years ago

-fwrapv

eru28• 4 years ago

`-fno-strict-overflow`

moring3• 4 years ago

Since the author and GCC disagree about whether this behaviour is useful, it is likely that insufficient requirements analysis has taken place. Is GCC supposed to behave this way? This depends on what goals it is supposed to reach. The GCC authors would say that the C standard allows such compiler behavior, and what is allowed by the C standard doesn't need to be justified by other means. The article author would argue that usability towards the programmer leads to less bugs and is needed, at least partially, as a justification.

Going a step further, this places the article author outside GCC's main intended user group. It raises the question: Who are GCC's main intended users? And is there a way to more clearly advertise that the article author isn't part of them? This would probably help other potential GCC users to decide whether GCC is the right tool for them at all.

I don't really get the discussion about the C standard and UB in the other threads here. The standard and UB are only a tiny pixel in the big picture.

fisf• 4 years ago

There really is no disagreement here.

GCC implements a language. The intended users are people programming in that language, which implies some sort of proficiency. The author isn't aware of the pitfalls of said language.

This is not about GCC.

unsafecast• 4 years ago

Oh it is. The fact that you have to remember a (very lengthy) document and every single mention of undefined behavior in it just to be sure that the code that goes out of the compiler will somewhat resemble your mental model of it is, in my opinion, not a reasonable requirement.

It really shouldn't be that difficult to wrap all these assumptions into a ‘if (can_exploit_ub)’. Then you can just pass something like -fno-exploit-ub and everybody's happy.

moring3• 4 years ago

That's just saying, "there is no disagreement because one side is clearly right, and the other is clearly wrong". Even if that were true, which is far from certain in this case, it doesn't preclude a disagreement.

The argument about proficiency has been bruoght up multiple times already -- but only by one of the parties involved in the discussion, which shows that there is disagreement -- and besides that, makes a visit in literally every single discussion about usability.

denton-scratch• 4 years ago

It raises the question: Who are GCC's main intended users?

Thank you, for not using the word "begs".

avereveard2• 4 years ago

question about the condition removal he's lamenting

his code would have gotten an overflow at

int32_t i = x * 0x1ff / 0xffff;

where it not optimized away

so it seems gcc is maintaining the code behaviour, only reporting a wrong debug line for it due code being shifted around.

shultays2• 4 years ago

the part that was optimized away is `i >= 0` check. Which can't happen because x >= 0 already holds true

avereveard2• 4 years ago

it also moves the division around

WalterBright• 4 years ago

D solved this particular problem by defining arithmetic as being 2-s complement, including wraparound behavior.

eru28• 4 years ago

`-fno-strict-overflow` give you that behaviour in GCC and clang, too.

shultays2• 4 years ago

I am on split here. Signed overflow is UB and it is pretty well known, yet author is writing code that depends on such overflow.

But is there are a reason for `i >= 0` not raising a warning if it can't happen? Or is there a warning that was not enabled? I think `i >= 0 cant be false` would save a lot of headache

edit: one post mentions macros. Which makes sense in that case I think. You can easily write such impossible conditions with macros, so making it a warning would add a lot of warnings I guess

Although there are warnings for `if (true)/if (false)` "this condition is always true/false"

nullc• 4 years ago

In addition to the points that other posts have made: it's also not especially new behavior. E.g. I see it at O2 gcc version 9.3.0 on i386. The optimization isn't performed by gcc 4.9.2 at O2 on i386. If I had to guess it probably shows up around GCC 5, but I don't seem to have any i386 vm's with gcc between 4.9.2 and 9.3 handy at the moment.

And 4.9 absolutely will do similar in other cases: fwrapv has existed since GCC 3.3 and fno-strict-overflow was introduced in GCC 4.2, which are flags to defeat these optimizations (and either of which avoids the crash on GCC 9.3)-- both introduced in response to increasingly effective optimization in prior GCC versions exposing errors like this. 4.9.2 just misses the optimization in this specific case.

sanxiyn15• 4 years ago

I compile all my C code with -fno-strict-overflow and -fno-strict-aliasing, and I recommend you to do so as well. C standard committee and GCC and Clang are being stupid, but that does not mean you should suffer their stupidity.

rowanG077• 4 years ago

I'm not so sure it's that wild. Signed overflow is UB so it makes perfect sense it's not possible to check overflow happened. You need to make sure overflow doesn't happen.

Similarly it's invalid to check if an access to an array is out of bounds after you have accessed it.

codedokode7• 4 years ago

I think it was a mistake when CPU and language designers decided to make overflow in arithmetic operations not an error. This is wrong. Overflow can produce invalid data, which can break something elsewhere. Overflow has been a reason for security vulnerabilities.

For example, you don't want to have an overflow when calculating a total cost of ordered goods or size of an allocated memory block.

One could argue that it is a developer's responsibility to make sure overflow doesn't happen, but the history shows that developers usually fail to protect the program from such kind of errors. We have memory protection, why cannot we have overflow protection?

In my opinion, an overflow should cause an exception unless the program explicitly asks to ignore it. Of course this means that every addition now becomes a (very unlikely) conditional branch, but I guess this can be optimized by static prediction. Every memory access is already a conditional branch, and it doesn't cause problems.

But CPUs and programming languages seems to make writing overflow-safe code more difficult than unsafe. In assembly, you have to insert additional branch instructions, and in business-oriented languages like Java you have to write long sentences like Math.addExact(). If you write a complicated formula this way, it becomes unreadable.

Sadly, modern languages like Rust haven't fixed the mistake and also penalize writing safe code.

The only language I know with overflow protection is Swift: an overflow causes an exception there. Well done, Apple, you are lightyears ahead of open source software.

MiguelX413• 4 years ago

What's wrong with checked_add() and its friends in Rust?

codedokode7• 4 years ago

They are longer to type than `+`.

It is easy to write unsafe code and difficult to write safe code. As a result, while most mathematical operations must be safe, developers use unsafe operations because they are easier to type and more readable.

Operators like `+` should be equivalent to checked_add().unwrap(), not to unchecked_add(). Why choose unsafe and rarely used operation as a default? It is a mistake. Swift uses sane defaults.

UPD: for example, let's say we need to allocate memory for N elements of size S and a header of size H. Here is the unsafe code:

    u32 s = N * S + H

And here is safe code:

    u32 s = checked_add(checked_mul(N, S).unwrap(), H).unwrap()

And here is safe code in Swift:

    let s: Uint32 = N * S + H

And unsafe code in Swift:

    let s = N &* S &+ H

scoutt2• 4 years ago

CPU and language designers

Which CPU? There are a lot of CPU architectures and their variants, some older than 40 years, and C is supported on most of them. Each CPU has its use case. Also, safety is not always a top requirement.

But I also think that true safety will come at silicon level, and not from a programming language.

codedokode7• 4 years ago

Also, safety is not always a top requirement.

Safety is the requirement for desktop, mobile and server processors but x86 and ARM penalize using safe math operations (you have to insert branch instructions).

There are a lot of CPU architectures and their variants, some older than 40 years, and C is supported on most of them.

Between safety on modern CPUs and supporting 40-years CPU I would choose the first.

UncleEntity2• 4 years ago

Every memory access is already a conditional branch, and it doesn't cause problems.

Is that how it actually works or is it the kernel/hardware not letting you dereference 0?

codedokode7• 4 years ago

I mean every memory access can cause an exception and handling an exception is a kind of branch.

dist1ll• 4 years ago

If your unsafe code is sound, you can't cause memory corruptions with wrapping integer overflows, no matter what you do with them. If your Rust code is engineered correctly, overflows are primarily logic bugs, not memory safety issues.

Every memory access is already a conditional branch, and it doesn't cause problems.

What are you referring to here? The MMU/TLB?

Sadly, modern languages like Rust haven't fixed the mistake and also penalize writing safe code

Writing safe code is smooth as butter. You just follow borrowing and lifetime rules and you get memory safety basically for free. Same with safe concurrent data structures.

Unsafe code is the one penalized. The amount of boilerplate and unstable features I need to use in Rust for ergonomic unsafe code is pretty staggering.

anfilt3• 4 years ago

This probably just an example, but why are they using a signed int for indexing???

astrange5• 4 years ago

They're correct to do this. Signed integers have more UB, therefore you /should/ use them in all situations when overflow isn't going to happen, because you're not going to need that extra defined behavior.

This lets you use UBSan most effectively and it's what the Google style guide says to do.

(Exception if you care about micro-performance: * / >> operations can be a little faster on unsigned types IIRC)

mxmlnkn• 4 years ago

I would also prefer unsigned indexes but exactly because the compiler may assume that there will be no overflow, signed index access may be a bit faster and therefore preferable.

account423• 4 years ago

Is there a reason why the language doesn't provide UB-on-overflow (and wrappring overflow) for both unsigned and signed types?

It always feels dirty deliberately using a signed type for something you know can never be neagtive just because that signed type has other properties you want.

anfilt3• 4 years ago

On most machines this days there is not really a performance difference between the math done on signed or unsigned integers. The only case would be if your wanting to the compiler to optimize on the fact that UB does exist. So like this in example "impossible things" get optimized out. The author here clearly does not want that.

Pabloski80• 4 years ago

Make C Safe Again.

UBs in C language are the asleep plague just asking to get triggered into a głos bal disaster. Oops, too late.

There is another class of those there, described in some papers for CSmith. Milder but still quite bad.

Both got quietly not acted upon, when C++ got made.

Lets go back to Pascal/Modula/Oberon.

p0nce3• 4 years ago

But that code code is wrong in the first place with defined overflow.

If x == 0x804021 then x * 0x1FF yields 0x1DF, and then proceeed to access tab[0]. This is very probably NOT what the author wanted.

- Defined overflow doesn't help at all, in fact the compiler would preserve what is wrong in the first place

- overflow trap is a little bit better, at least you would get the occasion to think about it

Even if the compiler doesn't act on the UB the code is still wrong.

dxuh• 4 years ago

This is why I use unsigned integers for indices (and firmly believe most everyone should).

0x000xca0xfe2• 4 years ago

The root of all these problems is that C doesn't guarantee two's complement behavior when compiled for two's complement machines, as far as I understand. But why is that? Why are integer operations not defined as implementation-defined?

I get that the C standard cannot guarantee two's complement when C code can be compiled for other architectures. But looking at the list of supported architectures ( https://gcc.gnu.org/backends.html ), even exotic architectures like vax and microblaze seem to be two's complement.

Does gcc even support one's complement machines or those with CHAR_BIT != 8 ? If not, all those optimizations are utterly ridiculous. Basically an adversarial competition between compiler writers and users.

sanxiyn15• 4 years ago

As I understand, the only ones' complement architecture in active use is UNIVAC (yes, believe or not UNIVAC is in active use and Unisys provides commercial support).

Non-8-bit char is a bit more common, probably the most common is TMS320 C5000, see https://lists.llvm.org/pipermail/llvm-dev/2009-September/026... for an example. As far as I know there is no GCC port, but it could very well have one, after all TMS320 C6000 port is upstream in GCC. (It is c6x in your table.)

0x000xca0xfe2• 4 years ago

Interesting, thanks. So the c5x (if it would be in the list) has 16-bit bytes and the c6x the usual 8-bit bytes.

Do you happen to know what compiler/language the UNIVAC folks use?

nsajko• 4 years ago

It's rude to spam bug reports like that. GCC has a mailing list, if a discussion is what you want.

skozharinov• 4 years ago

Well, that's undefined behaviour. It could have inserted system("rm -rf /*"); instead and be right about that.

xg15• 4 years ago

There is an old german proverb that fits here, "Es kann nicht sein, was nicht sein darf", mocking lords and judges who purposefully mixed up things that are physically impossible to happen and things that ought not to happen by policy and made their life awfully easy that way.

People already weren't fond of that kind of logic a hundred years ago.

I think HTML5 sets a good example of how to do it instead: A large part of the standard is about defining behaviour for functionality the standard explicitly deprecates and disallows in compliant documents - all just so "legacy" HTML documents don't end up with "undefined behaviour".

ohdannyboy• 4 years ago

I think this article makes a far better case than the college hyperbole of "once you invoke undefined behavior it is allowed to format your drive and kill your cat."

As chance would have it, I am actually arguing with another team today about introducing undefined behavior into our code-base. They're arguing "well it works so its fine." I used this article to argue that it doesn't matter and we're inviting really insidious errors to come in later down the road.

GCC undefined behaviors are getting wild

Related Stories