Comment by hxhxhrra
3 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.
> 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).
> 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.
See also: https://blog.regehr.org/archives/213
C++ bans undefined behavior in constexpr, so you can force GCC to prove that code has no undefined behavior by sprinkling it in declarations where applicable:
https://shafik.github.io/c++/undefined%20behavior/2019/05/11...
1 reply →
It is undefined behaviour if I write GCC --hlep
Does that mean it's acceptable for GCC to reformat my hard drive?
Just because something is UD doesn't give anyone a license to do crazy things.
If I misspell --help I expect the program to do something reasonable. If I invoke UD I still expect the program to do something reasonable.
Removing checks for an overflow because overflows 'can't happen' is just crazy.
UD is supposed to allow C to be implemented on different architectures if you don't know whether it will overflow to INT_MIN it makes sense to leave the implementation open. If I, the user knows what happens when an int overflows then I should be able to make use of that and guard against it myself. A compiler undermining that is a bug and user hostile.
34 replies →
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.
> 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
That's the most important point! You simply cannot detect overflow when multiplying integers in C after the fact. This is not GCC's fault.
I agree that some of the optimizations exploiting UB are too aggressive, but the article presents a really bad example.
> 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...
C will accept every valid program, at the cost of also accepting some invalid programs. Rust will reject every invalid program, at the cost of also rejecting some valid ones.
("unsafe" (aka "trust me" mode) means that's not quite true, and so do some of the warnings and errors that you can enable on a C compiler, but it's close enough)
> 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.
No, I specifically ruled out doing that in my comment.
I was referring to the situation where a null check was deleted because the compiler found UB through static analysis.
(Or specifically, placing a null check after a possibly-null usage. It is wrong to assume that after possibly-null usage the possibly-null variable is definitely-null.)
22 replies →
You typically can't prove it, but if and when you can prove it, you should definitively warn about it or even refuse to compile.
Things like that meaningless null check mentioned, can definitively be found statically (the meaningless arithmetic sanity check in OP's example, I'm not so sure, at least not with C's types).
2 replies →
> 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.
> Compiling and running as if nothing is amiss is exactly how UB is allowed to look like.
Yes, and this is a "billion-dollar mistake" that's responsible for an ongoing flow of CVEs.
(the proposal to replace "undefined" with "implementation-defined" may be the only way of fixing this, and that gets slightly easier to do as the number of actively maintained C implementations shrinks)
2 replies →
> 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.
>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").
-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.
I can easily test if n+1 is < n with fwrapv.
Without you have to do convoluted things like rearranging the expression to unnatural forms (move the addition to the right but invert to subtraction, etc), special case INT_MAX/INT_MIN, and so on - which you then have to hope the compiler is smart enough to optimize, which it often isn't (oh how ironic).
It's not to protect from UB, it's to protect from the optimiser deleting your bounds checks.
On x86 you can put an INTO instruction after each arithmetic operation to trap if the overflow flag is set.
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.
I'm fairly confident in declaring the answer to your question: None.
Most programs rarely issue all the instructions that a CPU can handle simultaneously, they are stuck waiting on memory or linear dependencies. An extra compile-out-able conditional typically doesn't touch memory and is off the linear dependency path, which makes it virtually free.
So the actual real-world overhead ends up at less than 1%, but in most cases something that is indistinguishable from 0.
If you care that much about 1% you are probably already writing the most performance critical parts in Assembly anyway.
1 reply →
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!
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.
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.
> 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...
I should clarify that I believed all that in 1990-something; I've arrived at a more mature professional opinion in the nearly three decades since.
> 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/
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".
>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.