Undefined behavior, and the sledgehammer principle
thephd.dev
thephd.dev
C++’s main contribution to the C evolutionary line is rich, zero-cost abstraction.
The main determinants of the residual cost of your abstractions in a language like C++ are the effectiveness of heuristic or profile-driven inlining and the aggressive application of fairly basic optimizations (constant propagation, common subexpression elimination, dead-code elimination, …) to the resulting inlined code, which for good reason “looks” like no code any self-respecting developer would actually write.
This is where reasoning from UB becomes essential. The developer didn’t write this code, didn’t express a direct intention: The compiler synthesized a new program from inlined and rewritten pieces of the AST. “Warning” about possible UB in this code doesn’t make any sense, nor does being conservative about “should-be-impossible” states.
"if ((INT32_MAX / 0x1ff) <= x) { ... }" is not the same as "int32_t i = x * 0x1ff / 0xffff; if (i >= 0 && i < sizeof(tab)) { ... }".
The reason for the difference is that the result might get into the permitted range accidentally. The function should have returned zero (as it does for out-of-range inputs) but returned some element of a table.
The same bug exists in their Rust code.
ifoops( c = a*b )
{
// over flow?
exit(1);
}
// whew that was closeif (!ckd_int(&result, a, b)) exit(1);
Use size_t for indices. That's defined as an unsigned value big enough to index the largest possible array. Rust uses "usize" for the same purpose. Only use signed integers where negative values are meaningful.
And a wrapped unsigned integer is probably still a bug. Yes, your compiler can't blow up a branch that you thought would be there, but "hey I added two numbers and got back a smaller number" is almost always not actually the function that you were trying to implement. The wrap can even happily lead to a security vulnerability if you are computing some sort of buffer offset and think that the guarantees of arithmetic will keep you within the buffer bounds and didn't stop to think about modular arithmetic. So your program is slower and still buggy.
The Sledgehammer Principle is not enough; UB is a nuclear holocaust for a program.
So I'll take the buggy behavior that slows my code and only uses a sledgehammer over the buggy behavior that treats my program as a suggestion.
https://web.archive.org/web/20210508125532/https://twitter.c...
https://news.ycombinator.com/item?id=26498233
Nasal demons was an analogy, not something to take literally.
C and C++ are both nightmare languages and the connection between UB and the as-if rule are a mess. But incorrect programs can still blast off into incredible harm without the optimizer's help. And the emphasis on UB because it is so fun to construct weird scenarios has led to a world where people make strange and ill defined demands for how the compiler should react in these situations.
Yes, you can get messed up control flow from modular arithmetic code, but the compiler is not going to delete that code if it happens to overflow.
And just because it's purposefully constructed doesn't mean it won't happen in real code, which is much more complicated and liable to triggering such problems.
Why not? Why is that somehow worse than code that breaks everywhere, all the time?
Correctness should always come first. Sometimes performance is part of correctness (real-time), but it is not most of the time.
When performance is not a part of correctness, why would optimizing for performance even be a possibility?
And having done real-time work, I can tell you that the output of the compiler is scrutinized heavily in that domain. If the compiler is optimizing according to UB, changes would be made.
But to answer your question, this is what I would do: If a programmer did not opt-in to the UB, don't optimize according to the assumption of lack of that particular UB.
Programmers do not opt-in to signed overflow as UB, so it should never be used as an optimizing assumption.
Programmers do opt-in to UB for data races by sharing memory across threads or signal handlers, so compilers can optimize against that.
Programmers do not opt-in to non-terminating loops as UB, so compilers should not optimize to that.
Programmers do opt-in to strict aliasing by using pointers to different types, or by using the `restrict` keyword, so the compiler can optimize on that.
You may complain that if I use signed types, I'm opting-in to that UB. I disagree, but even if you are right, I'm explicitly opting-out by using unsigned types.
And yet, you'll still complain about that; you started this discussion by complaining about developers using unsigned types because it would be slower, even though you acknowledged that the bugs wouldn't be as bad.
In other words, you want performance at any cost, so much so that you'll complain when people use mitigations against compiler optimizations that can raze code like Rome razed Carthage.
So you and I will never see eye-to-eye because you firmly believe that performance is everything, and I firmly believe that correctness is everything.
I usually try to be diplomatic on HN (and often fail), but this is one time I can confidently say: you are dead wrong.
By the way, I have public code that uses unsigned types as much as possible, and it still holds its own against an implementation that uses a heavily optimized library. So you are also wrong that unsigned types make it noticeably slower.
Imagine this code
int x = 0;
f();
return x;
You don't need to share memory across threads to opt in to data races. You can access whatever you want with pointer arithmetic if you want to be correct in the presence of UB.
Or this code
void do(foo* f) {
if (f == nullptr) return;
f->do();
}
> So you and I will never see eye-to-eye because you firmly believe that performance is everything
I do not believe this. I am one of the people at my company fighting to spend performance to buy safety. I just don't believe that the principle of least surprise can be implemented in the standard in the way some people say and I don't believe that UB is totally unique from other forms of incorrectness in a way that should cause us to behave very differently about it.
> I firmly believe that correctness is everything.
Do you run your production binaries with all of the sanitizers enabled?
Yeah, so you allocate space on the stack (which is free, by the way, because space has to be allocated anyway for the new function's frame), store to it, and load from it.
An extra store and an extra load. Of stack space that was probably already in cache anyway.
So what? What a miniscule price to pay. [0]
> You don't need to share memory across threads to opt in to data races. You can access whatever you want with pointer arithmetic if you want to be correct in the presence of UB.
So C should have bounds checks and define a failing bounds check as an abort. And then such optimizations could be correct. That's what so many other languages do, and it works.
> Or this code...f could be deleted. This could be UB.
Do you mean freed?
Yes, that could be UB. But the compiler should never say, "Oh, well, f could be freed here, so I'm just going to delete the `f->do()` call."
Bad example because compilers don't currently take advantage of it. They day they take advantage of that is the day that I quit programming.
> I do not believe this. I am one of the people at my company fighting to spend performance to buy safety.
Ha! I do not believe you at all! You are okay with compilers taking advantage of UB to elide a store and a load.
The only way you are telling the truth is if your company is full of malicious compiler authors.
> I just don't believe that the principle of least surprise can be implemented in the standard in the way some people say
It totally could. C could even have bounds checks without changing the ABI. They just don't.
> I don't believe that UB is totally unique from other forms of incorrectness in a way that should cause us to behave very differently about it.
It's the only form of incorrectness that:
* Will destroy everything.
* That compiler authors claim they have a right to take advantage of.
Yeah, we definitely should treat it differently. You are dead wrong.
> Do you run your production binaries with all of the sanitizers enabled?
No, because I don't work in the industry.
But in my personal code, I wrote my own bounds checks and enabled them. In C. In release mode. All your talk of "but you could make a pointer to anywhere" doesn't happen in my code.
I use structured concurrency to allocate and free items in only one place, in the same stack frame. When threads are created, they prevent the creating thread from returning from the stack frames that the children may have gotten pointers to.
I fuzz like you wouldn't believe and make sure all paths come back clean in ASan, UBSan, TSan, and Valgrind, including memory leaks.
I add all unique paths from fuzzing to my test suite.
I'm going to write my own malloc() that will have double-free and use-after-free checks.
I use unsigned types to avoid signed overflow, and such unsigned types more easily trip the bounds checks when they overflow because the bounds checks only need one condition.
Tell you what: I would like you to take version 6.7.2 of my bc [1] and get it to execute UB. Any UB is fine.
If you do, I'll enable sanitizers on my release builds of all of my software.
But you won't, and that's why I can forego sanitizers on release builds: I do enough work to ensure that UB won't happen.
And that's why I use unsigned types. Your bellyaching about their poor optimization will not change that.
[0]: https://gavinhoward.com/2023/10/he-who-gives-up-correctness-...
But to answer your question, because the malicious compiler doubled the work I had to go to get to this point. Or worse. Maybe it increased the work by an order of magnitude.
In addition, the checks are what prevent UB, especially the kind where you claim that any pointer anywhere can mess up everything. It's not UB if the behavior is defined as a crash before anything bad happens.
And to answer your complaint that I'm leaving performance on the table, so what? Sure, I'm "messing" with speculation (though not by much because I tell the compiler that the error branch is unlikely to be taken), but Spectre and Meltdown showed that maybe speculation was a bad thing.
By the way, in my bc, I actually turn a lot of checks off, the checks for which I am 10 9's sure there aren't problems.
Not an exaggeration, by the way; I've run my bc under a fuzzer for probably 50 billion executions or more. And every single one of the paths were fixed until they came out clean in the sanitizers and Valgrind.
Even across the entire world, I doubt my bc has run 50 billion unique executions; most of the time, people run it on the same scripts with similar data, over and over.
In my other project, I don't turn off checks because it hasn't seen that level of testing.
That's why I said you could attack bc; checks will actually be off. Make sure you do it in release mode, though if you get an assert to trigger in debug mode first, that same input should also cause UB in release mode.
Have fun. I'm done. Contact my through my bio if you succeed.
And once again, you are making false statements about me. In fact, I am one of the people the performance folks are mad at because I'm fighting to buy safety. It is just impossible to do this when the conversation is so poisoned by arguments like yours.
This is exactly the sort of communication that makes it so difficult to make meaningful progress on this problem. People just calling other people stupid idiots who don't care about correctness.
People need to be precise in what they are asking for from the compilers and the committees and honest about what it costs. That is all I am asking.
As a bit of an aside, when is this actually useful? The only example I know of is bytebeats[1], and it's unlikely this is what Ritchie had in mind when he created C. Wikipedia says "for some applications, such as timers and clocks, wrapping on overflow can be desirable", but even there wrapping an int usually seems wrong (e.g. you want to wrap minutes on 60, hours on 24, etc – not 255 or 65k or whatever the size is).
[1]: e.g. stuff like: main(t){for(;;t++) putchar(t*((t>>12|t>>8)&63&t>>4));} – pipe to aplay or /dev/dsp or whatever.
For the counters, since you questioned it-- say you want your program to perform a calibration cycle every once in a while, the exact interval isn't critical. Just free run an unsigned iteration counter and then test that some masked version of it equals a constant.
All that said, when you want wrapping behavior you know it. It's critical that it's available, first class supported, and fast-- but it wouldn't hurt if you had to ask for it.
But the alternatives to wrapping aren't themselves magic bullets: Say you use saturating arithmetic, now lots of code that might have worked more or less fine with wrapping (or only been a little glitchy) goes into a hard lockup, esp since saturation breaks the property that var+1 != var, or fails in some more serious way, when e.g. because var+pos-pos != var.
And the wrapping behavior at least has the property that its fast on extant hardware, while implementing saturating or trapping operations is inherently slower.
Wrapping also manages to produce correct results by accident pretty often, like in my above point about var+pos-pos=var. Sometimes machine generated code does some nonsense that takes a variable out of range then pulls it back. Switching to saturating would just switch the cases that are magically correct, switching to trapping would turn any otherwise magically correct cases into failures. In some cases you might prefer a clean crash to potentially glitchy behavior, but in other cases there is no such thing as a "clean crash" and crashing on overflow is the worst failure possible (so whatever else might happen if it kept running could be no worse).
There is, unfortunately, no replacement for thoroughly understanding the behavior of a piece of code nor any replacement for formal analysis.
We shouldn't cry too much. Software is absurdly cheap to make compared to e.g. engineering and machining a part out of metal. But part of that ease is an illusion because it's only that easy if you don't care if the software is correct, and only need it to be somewhat correct or only correct some of the time.
Few of the drivers for improved software quality are actually backed by research either. Would doing X or Y instead be better? We don't know. Alternatives start with at least a minor headwind that there is a lot of experience out there dealing with the way things have historically been done. Unfortunately researching the interaction between programming languages and programmers is itself really hard.
I can think of some cases where wrapping comes in handy.
Suppose you want to compute `a + b - c`. Mathematically speaking, the addition and subtraction should be associative. You shouldn’t have to care about the difference between `(a + b) - c` and `a + (b - c)`, since they should be equivalent. Using commutativity of addition, you can also rewrite it as `(a - c) + b`, or `b + (a - c)`, and those too should be equivalent. With wrapping, they are equivalent! All of those expressions will always compute the same value, and it will be the mathematically correct value as long as said value fits into the integer type you’re using – even if the intermediate values don’t. This property is true for any series of additions, subtractions, and multiplications (though not divisions). In contrast, with overflow-checked arithmetic you have to think about which order is ‘correct’, i.e. which one is guaranteed not to overflow given whatever invariants you have in place.
…But that’s only useful if the final result is guaranteed not to overflow. Or if you don’t care if it overflows. If it can overflow and you do care, then you probably need to overflow-check the intermediate computations anyway, so wrapping just gets in the way.
VAXen had a trap on overflow capability. I once rebuilt the C compiler to set that bit in the function header mask, and recompiled many of the UNIX utilities. About half of them broke. It was too late for a retrofit by 1980.
Burroughs machines had 48-bit numbers, which were signed-magnitude floats using a 32-bit mantissa with the binary point at the low end. So integers were floats with a zero mantissa. Integer overflow caused promotion to a float.
So, the hardware people did try.
The instruction can then set one condition code that means "if you intended this as an unsigned addition, the answer was out of range" and a different one that means "if you intended this as a two's complement addition, the answer was out of range".
Doesn't undefined behaviour more appropriately mean that once you used the sledgehammer on whatever item in your house there is a chance that not only the vase is gone but the structural integrity of the whole building is compromised?
Maybe "minefield principle" would be more accurate. Because one wrong step and you are finished.
What this means in practice is not concrete at all, or rather it is only meaningful in relation to a rather large set of things: the compiler, its version, the optimizations enabled and applicable, the platform, etc. The optimizations applicable are dependent in your program too, so even though the ramifications are usually (but not always) deterministic, even that may not help.
You might add one more call, now something is inlined that wasn't before, and because you compute `i+5` 300 lines later, the compiler can assume `i <= MAX_INT - 5` in the body of the now-inlined function and so it can now just drop a comparison you were making to prevent overflow since it knows the later overflow Can Never Happen so there's no point emitting code that will never execute.
Yeah! isn't that enough? Your program is Wrong and therefore it should be fixed.
Reasoning about the wrongness is not time well spent. Just consider it a defect and mitigate it.
Yes, in theory you could internalize all of the rules and write UB-free code. While you're at it, be sure you only write code with no bugs at all. I'm not sure why everyone isn't doing that already...
I love the addition of `<stdckdint.h>` in modern C. What I definitely love less is that it's quite easy to hit undefined behavior with arithmetic and I'm personally too dumb to fully avoid it. On the Rust side Miri is shaping up to be a reasonable tool to help you figure out when you do dumb stuff, maybe something like this for C would make this a more enjoyable experience. I learned that `-fsanitize=undefined` is a reasonable tool on some compilers that adds runtime checks into the binary that at least tells you what's going on in some of those cases but that requires the right kind of input making it down such a code path. Miri on the other hand is running fully at compile time.
Generally though I'm really happy to see that there are folks on the C standard that have this sort of stuff in mind.
> We deserve multiplies and subtracts and adds that don’t punch us in the face. We deserve code that actually respects what we write and what we say when we say it, so we can build the necessary safety guarantees into what I know C programmers are shipping to millions of people all over the globe daily.
Impossible to disagree
> Update: Here's the bug, and as you can see, the gcc guy who's to blame for the problem (he admits as much in the other piece of code) thinks that's fine if people get outed because he can justify an optimization in formal legal terms. Sick. Makes you wonder what you're actually doing audits for if you're then torpedoed like this. Oh, by the way: with icc (the Intel compiler) you get an assertion correctly.
(translation by DeepL)
The argument: 'you shouldn't have written the code that way, because it breaks a rule stated in this large UB book' is a bit petty to say the least.
What about making it (almost) impossible to write UB code, wouldn't that be better for all? In the example shown, the compiler could simply throw an error stating that signed integers are not fit to be used as array indexes. Yes, such change of rules in the language would break backward compatibility, but adapting such code to the new rules would be a benefit anyway.
This is not possible without pessimizing a significant portion of the architecture targets and also causing major slowdowns across all architectures. Dereferencing a pointer to a deleted object is UB. How are you going to test for this at runtime. ASan is already a huge amount of overhead and it isn't even guaranteed to detect UaF.
> In the example shown, the compiler could simply throw an error stating that signed integers are not fit to be used as array indexes.
Are unsigned indexes fit to be used? Reading an array out of bounds is UB and arrays don't carry their lengths with them.
Hence the (almost)
> Are unsigned indexes fit to be used?
More fit than signed ones, clearly shown in the example in the article where a check was removed by the compiler's optimizer.
UaF is a huge source of UB in C and C++. There are two ways to make UaF almost impossible: either a total adoption of Rust-style lifetime checking, which is not a possible transition for the large majority of existing code, or runtime checks that have large and unacceptable performance overhead. The overhead doesn't come from some a few weird corner cases that you can avoid in ordinary development. The overhead would come from core components.
Congratulations, you have invented Rust.
1. The tone of the article implies the author is taking sides. Specifically, they root for the poor developers, against the evil standard committee and compiler writers. But for context, the author is currently co-editor for the C standard committee ("WG14"). This is important because the post contains lots of humorous language and irony, which can be disorienting without this context.
2. The author correctly points out that some criticisms of UB come with exaggerate levels of passion. However, again, this verbose and "fun" article full of analogies is not helping the cause.
3. Namely, whichever side you are on, UB is subtle and would benefit from simpler exposition. The whole "Sledgehammer" explanation towards the end of the article could be summarized as: "UB does not invalidate just the statement or value that contains it. Invoking UB invalidates the whole program." The author being on the standard committee should add, I think, a sense of responsibility regarding how they communicate.
In general I think that the whole discussion around UB would benefit from serious and dispassionate studies of the costs/benefits for the various types of UB, and avenues for improvement.
There's a C++ talk by Alistair Meredith which ends up saying that UB can't delete client files unless you the programmer wrote code to delete those files...
But note that C++ doubled down on the idea UB invalidates the whole program.
But I also disagree that UB is the problem. It simply means the ISO C standard did not define something. A compiler can still do something perfectly safe in most cases. And in fact, many can do this with the right options. Users must learn to use these features.
"Must learn to use these features" was a reasonable strategy for, say, the Apollo missions. The astronauts are very smart, very motivated, they're heavily supervised and working as a team, we can "just" train them to do it properly and if they don't they all die, if such training saves us $100M and five years R&D compared with idiot-proofing the rocket it's an excellent trade.
It's not OK for everyday tools and activities. The reality, whether we like it or not, is that C and C++ are widely used across many industries by people with greater or less skill and experience. As a result "Must learn" is a guarantee of failure. The language needs to define this properly, or the language must not be used.
Also, once we're out of the ISO C standard and requiring vendor options, much of the justification for C falls away pretty rapidly. "It's an ISO standard" is gone, "Works on all platforms" is gone, "Common tooling works" is gone. If we're giving up all these things, why not get the benefits we could have obtained in exchange from a language like Rust?
An ISO standard will always be just minimum requirements, simply because there are too many different requirements out there and it is created by consensus. It is not the ruling committee of C that could decide top-down what the language is. If users do not drive the change bottom-up by demanding improvements from their compiler vendors, it will not happen. Luckily, this is happening and compilers get more and better features for safety now. I agree though that defaults are still poor and for some problems there is still no good solution.
If somebody wants to use Rust, why not? I do not like it for a variety of reasons, but that it is safer by default (with respect to memory safety - which is not everything) is good. I personally also want to have this in C.
I don't buy the claim that WG14 can't do top-down decisions. Like at WG21 this is a convenient fiction, offered when they're reluctant to do what is asked, and immediately forgotten when it gets in the way of something they want to do.
In theory, WG14 could make top-down decisions. But if we would decide something implementors really do not want to do, they would simply ignore the standard. And this happens. For example, we had to make some realloc corner case UB in C23 because different implementations did behave differently and no one wanted to change their implementation. But the implementors themselves are represented inside WG14, so we usually can't get consensus for such decisions in the first place. So WG14 rules the C world by finding a minimum consensus everybody can agree to and this is really the only way it can work if you have so many different players with so many different requirements. The C world is far bigger than most of us imagine.
...like, uh, libc or something...
Or, not by default, even with optimizations on.
This is an unsafe behavior that should be opt-in, at a fine granularity, so that its benefit can be obtained when it matters.
That's all there is to it.
fn foo() {
let x = 0;
bar();
return x;
}
fn foo() {
bar();
return 0;
}
Optimising compilers require the ability to make assumptions about your code - that's the basis by which program transformations are valid. Even something as simple as constant loop unrolling would be forbidden by your rules, since your code can (invalidly) choose to try to mess with loop variables in a way the compiler can't spot.
We are not relying on specifics about bar(), just the general assumption that up until the return 0, the program hasn't done anything incorrect which interferes with what we want to do.
It's a different reasoning from "this loop cannot terminate because i++ never goes negative, so we can cheerfully remove the code after it, including the return instruction."
If it's easy to overflow integer addition, then that must be regarded as an accident. Assuming absence of accidents is a poor default in ways that assuming the absence of fraud isn't.
First make it so that perpetrating integer overflow is inconvenient, so that the programmer has to go out of his way to request it. If that has been done, then sure, blindly assume that i + 1 is greater than i.
That's not qualitatively any different. You're still describing a class of behaviour (messing with local variables not in the same scope) that the program isn't allowed to do, because it breaks the compiler's view of the code. That behaviour is UB.
What do you think separates "good" assumptions from "bad" ones?
Rarely to never wrong vs often wrong.
This is not actually different reasoning than what you describe. I encourage you to try to formalize what you are saying. You'll find that it is remarkably hard to distinguish the two cases, especially if you understand the steps the compiler takes to get to these changes.
If, in the given language, it is dead easy for bar() to manipulate x by accident, and frequently occurs due to that being a pitfall in that language, then it would be stupid for the language to have advanced optimizations over local variables.
Unless the implementors are confident that they can diagnose almost every instance of the pitfall.
I do not believe that this is true. If you can do it precisely, that'd be a significant contribution to the community. If you can it precisely in a way that doesn't create a massive overhead because of tracking object lifetimes explicitly then that'd be an incredible contribution to the community.
There’s a lot of very reasonable assumptions that compilers make and some less reasonable ones, but there is no clean line between the two. Ideally the standard would have clearly specified what assumptions compilers could make, but this whole thing is the result of GCC following their interpretation of what the standard says they can do and people not liking the result.