To give a background why is that: UB is not an event that happens in the program. Instead, “UB is impossible” is an assumption that is baked into the compilers.
The compilers don’t have if is_UB() { screw_you() } anywhere. The no-UB assumptions can be implicit and pervasive. Like an assumption that opposite of true is false, so if (x) {do} and if (!x) {} else {do} are equivalent. If you magically made a 3-valued bool with filenotfound, then it’s not merely triggering some else { lol() } code path in the optimizer. Instead, it makes all the assumptions about boolean algebra invalid and full of impossible-to-reason about paradoxes. And it’s hard to warn about this, because UB is not an event or a code path. The compiler would have to warn about every non-issue like “here I’ve assumed that the opposite of false is true”.
The second reason is dealing with complexity of optimizations. It’s too difficult to optimize code in the high-level form you write it. There are too many tree structures to work with, too many scopes, too many constraints to preserve. Instead, the code is “lowered” to a simpler assembler-like representation that no longer resembles the source code. In this form programmer’s intention is hard to see, so it’s no longer obvious what should and shouldn’t be optimized out.
To manage the complexity, optimizations are applied to low-level code in multiple independent passes. This way instead of having to consider all of the C spec for any change, each pass can focus on one thing at a time, e.g. “can I change !!x to x”. There’s a pass that simplifies arithmetic, there’s a pass that checks which expressions are always true, and there’s a pass that removes unreachable code. They can end up removing your null or overflow checks, but they don’t mean to — each pass does its own thing that in isolation seems sensible, spec-compliant, and is useful for most of the code.
And finally, majority of the optimizers in C compilers are shared across all architectures. They evaluate code as if it ran on the hypothetical portable machine that the C spec describes, not your particular CPU. So it doesn’t matter that your CPU knows how to overflow a signed int or has caches coherent across threads. The low-level virtual machine the optimizer optimizes for doesn’t have that, and code under optimizer will “run” in the C way instead.
Instead, it makes all the assumptions about boolean algebra invalid and full of impossible-to-reason about paradoxes
This is a great explanation, but substitute ‘integer’ for ‘boolean’ and you get why C compilers really like that signed integer overflow is undefined. If you write something that loops performing some addition on an integer, then you have an induction variable that can be modelled as an arithmetic sequence. If you have a nested loop, then the induction variable can be modelled as a geometric sequence. This model is completely wrong in every regard if adding two positive values together can result in a negative number. Having to understand this case precludes any transform from making use of this information. This precludes a large number of loop optimisations.
Signed overflow is UB so compilers get to pretend it can’t happen. The lack of UB on unsigned integer overflow means that many compilers don’t optimize unsigned arithmetic nearly as aggressively, for precisely the reason you point out. The difference is that compilers aren’t allowed to ignore the possibility of unsigned overflow since it’s well-defined and allowed to happen.
My favorite example of undefined behavior: creating a pointer into the stack and messing around with its contents. In C or unsafe Rust or something like that, compiler has literally no way of preventing you from doing this, and no way of detecting that it has occurred. It’s not even “this is on you to make it safe” territory, because the compiler is allowed to assume the contents of the stack doesn’t change out from underneath it… it may juggle local variables in and out of registers or something and, within the bounds of the calling convention, you get make zero assumptions about how it works. Just ‘cause one compiler puts a particular local var at [rsp+24] or whatever doesn’t mean it will be there the next time you compile the program.
Yes, you can do it. You can even make it work, if you know exactly how the compiler works and the compiler doesn’t change. But you’re breaking the invariants that the compiler fundamentally uses to function, and it is incapable of noticing that you are doing it.
(Update: Notably, if you pass -O3 to most versions of gcc in godbolt it will generate the code you expect, but clang will almost invariably nope out and just return 1 or 0 or nothing at all. Fun!)
That’s not what I imagined a pointer into the stack would be from your description.
That’s a pointer into a local variable. The compiler wouldn’t even allocate stack space if you compile with optimizations.
Pointers to local variables are not UB.
Edit: What is UB in this case is that you incremented “b” outside the array bounds (a pointer to a single object is considered to be a pointer into an array of 1 element).
Edit 2: You can freely use such pointers while the compiler passes variables into and out of registers and your program will still work just fine. But your pointer is not allowed to go outside the bounds of the array (except to point one-past the array, but then you can’t dereference it).
You are correct, the UB in this case is incrementing the pointer out of its bounds. The thing is that a local variable (edit: usually) has to exist on the stack if you have a pointer to it that does arithmetic. So the easy way to get a pointer to a random place on the stack is to start from a local variable. You can also have a function that returns a pointer to a local var, you can start in the data segment or heap, or you can just make a good guess of where your stack is and hope ASLR doesn’t ruin your fun.
Or if you really want to go hard, you can ask a user to type in a number and use that as an address. Who knows what they’ll type in? The compiler sure doesn’t.
So the easy way to get a pointer to a random place on the stack is to start from a local variable.
No, you don’t necessarily get a pointer to a random place on the stack if you do that. The local variable or array may not even exist on the stack.
If you go outside the object/array bounds with pointer arithmetic, you get UB which does not have to (and many times won’t) translate into a random pointer, it will just mean that your code will break (and it can break in many different ways).
You should really, really, carefully read @kornel’s top post to understand how UB works.
You can also have a function that returns a pointer to a local var
That’s UB but again, you won’t necessarily get a random pointer to the stack, as the variable may not even exist on the stack. And even if it does exist, your code can break in completely different ways than getting a random pointer to the stack.
you can start in the data segment or heap
You’d get UB if your pointer goes outside of a malloc()-allocated area, but again, you wouldn’t necessarily get a pointer value. You’re making the exact same false assumptions that @kornel talks about.
Your code could simply be completely optimized out, or it may cause other very strange effects that have nothing to do with pointers.
or you can just make a good guess of where your stack is and hope ASLR doesn’t ruin your fun.
Even if you knew exactly where your stack is, I don’t think there is a way to deterministically create such a pointer without implementation-specific behavior (e.g. assembly code).
Edit: updated Godbolt link due to a typo in the code.
Or if you really want to go hard, you can ask a user to type in a number and use that as an address. Who knows what they’ll type in? The compiler sure doesn’t.
I believe converting an arbitrary integer into a pointer is also UB and you don’t necessarily get a pointer like you think you will, your code can just completely break in lots of different ways (including simply being optimized out).
You’d have to enable some kind of special implementation-specific compiler option to do something like that without UB.
What is not UB, I believe, is to e.g. pass a pointer value into an intptr_t variable and then back into a pointer without changing the value.
And yet this is also how just about every device driver under the sun works.
Because of this:
You’d have to enable some kind of special implementation-specific compiler option to do something like that without UB.
Edit:
Correction: technically speaking, it seems that the integer-to-pointer conversion itself is not UB if you use an explicit cast, but the C standard says the result is implementation-defined, so the code can behave differently depending on which compiler (or compiler version, or compiler flags) you’re using.
In fact, the C standard says that the resulting value can be a trap representation, which means that it could trigger UB as soon as you tried to do anything with that pointer.
Even if your implementation allows doing that and even if the integer is a valid memory location, I would imagine it would still be possible to trigger UB by violating other constraints, like creating a duplicate copy of another pointer of a different type (which could violate strict aliasing constraints), or creating a pointer with the wrong alignment, or calling free(ptr) if the memory location hadn’t been allocated with malloc() before, etc.
I believe converting an arbitrary integer into a pointer is also UB
The int-to-ptr operation is actually fundamentally implementation-defined. So you won’t find the UB rules for ptr-to-int and int-to-ptr in the standard, you need to look at the LLVM LangRef instead.
But that’s on GCC (probably clang does the same). There might be C compilers that are C-standard-compliant that might not generate an error.
If you are asking why doesn’t the C standard specify that such conversions are invalid rather than UB? No idea!
Edit: oh wait, I made a mistake! The above error is when compiling in C++ mode (the Compiler Explorer’s default, annoyingly). In C mode, it’s not an error, it’s a warning by default:
I don’t think this is the kind of error you’re expecting to see - if you change the code to int *a = (int *)4 it should compile without warning. I don’t know if this is even supposed to be undefined behaviour - when talking to devices you need to know the exact memory address “as a number” and write to it or read to it (think VGA video memory addressing and such), which is or was traditionally often done in C under DOS in real mode, for example.
Although it might be that this has sort-of been retconned into “always having been wrong” like relying on hardware behaviour on integer overflow has been.
Local variables are generally allocated on the stack. In some cases, it may be able to not allocate memory at all and keep the local variable purely in a register, but any time you mess around with pointers to local variables – especially when those pointers are passed across non-inlined function boundaries – that pointer is to the stack-allocated local variable.
With optimizations disabled, you can look at the assembly code and stack frame and verify that ‘a’ is allocated on the stack and ‘b’ is a pointer to that stack-allocated variable in icefox’s example. Here’s a slightly modified example where the pointer is passed across a function boundary to be dereferenced: https://godbolt.org/z/x8zEKEr1E
Yes, I know that, but @icefox was talking about “creating a pointer to the stack”, but as far as I can see there is no way to create a pointer to the stack in the C language, or at least no portable way to do it (i.e. without relying on implementation-defined behavior).
The C18 standard, as far as I can see, doesn’t even have the word “stack” in the 535-page document!
Someone else mentioned alloca() but even that is not part of any standard.
Then he said:
In C (…) [the] compiler has literally no way of preventing you from doing this,
Which seems to make little sense because if you’re relying on implementation-defined behavior (which has to be documented) to create a pointer to the stack, then that means that the compiler has already promised to give you a pointer to the stack. So of course it can’t prevent you from messing around with it.
It’s not like you “tricked” the compiler into giving you such a pointer, usually it’s actually the opposite: the compiler is the one who tricks you into thinking that you have a pointer to the stack when in fact the local variables (and even arrays) that the pointer points to, may only exist in registers or, since all the values of the variable might be possible to determine at compile time, may not exist at all!
Edit: That said, yes, I understand that if you rely on implementation-defined behavior then it is possible to deterministically create such a pointer (e.g. with alloca()) and mess around with it, such as corrupting the stack and causing UB. Which is what I meant when I said that you’d have to call some (platform-specific) library function to do that, it’s not like there’s a construct in the C language that says: “this is how you create a pointer to the stack”.
You can’t find the word “stack” in the C standard because the C standard indeed has no concept of a “stack”. As far as the standard is concerned, local variables have automatic storage and are alive until the function returns, variables allocated with malloc and the like have allocated storage and are alive until they are freed with free.
However, the common implementations have a chunk of memory they call “the stack”, where each function gets a sub-chunk called a “stack frame” which is where the compiler puts, among other things, the variables with automatic storage (except for those variables which it optimizes out or keeps in registers only). Therefore, when you take the address of a variable with automatic storage, the implementation will give you an address to the place in the function’s stack frame where that variable is kept; you have a pointer to somewhere in the stack.
There is some mixing of abstraction levels here. You never have a “pointer to a variable allocated on the stack” in terms of the C abstract machine, you have a “pointer to a variable with automatic storage”. But when we lower that into the level of concrete machine code for some operating system, we can see that in the right circumstances, our “pointer to a variable with automatic storage” gets lowered into a “pointer to a chunk of memory in the function’s stack frame”. So we can create an example program which proves @icefox’s point (namely that the “compiler has literally no way of preventing you from doing this, and no way of detecting that it has occurred”):
a.c:
// This function assumes it gets a pointer to a chunk of memory with at least 5 ints, and sets the 5th to 0.
// There is nothing at all wrong with this function, assuming the pointer does indeed point to 5+ mutable ints.
// There is no way for the compiler to detect that anything wrong is going on here.
void clear_fifth_int(int *ints) {
ints[4] = 0;
}
b.c:
void clear_fifth_int(int *ints);
// This function creates a local variable 'x', which the implementation will put on the stack,
// then calls 'clear_fifth_int' with a pointer to 'x'.
// There is nothing at all wrong with this function, *if* the 'get_fifth_int' function only dereferences the
// pointed-to int, so there's no way for the compiler to detect that anything wrong is going on here.
// However, we know that clear_fifth_int will touch whatever happens to be 4*sizeof(int) bytes after 'x'
// on the stack.
void stupid() {
int x = 10; // x ends up allocated on the stack
clear_fifth_int(&x); // &x gets a pointer to somewhere in the stack
}
No individual function in this example does anything wrong, but in combination, they mess around with the stack in ways which the implementation can’t anticipate.
No individual function in this example does anything wrong, but in combination, they mess around with the stack in ways which the implementation can’t anticipate.
You don’t actually know if they mess around with the stack, they may very well not. With link-time optimization all of that code could be inlined together and no pointers to the stack would even be created.
What you are saying is actually a result of the following:
The pointer points to a single object, rather than a sufficiently-large array of objects. Which results in UB when you do pointer arithmetic past the bounds of the array.
Or, in other situations, it could result in UB due to dereferencing a pointer past the lifetime of the object (which could happen both for automatic storage and for heap-allocated storage).
It has nothing to do with “the stack” or a “pointer to the stack”. It is simply the result of having “a pointer” (to some non-permanent storage).
You are assuming that a specific implementation detail will happen. How do you know that’s what will happen? Does your C compiler or some other standard guarantee that? I assume the compiler documentation or a calling convention such as the System V ABI may be able to guarantee that. But if it does guarantee it, how is that “the implementation not anticipating”?
I don’t understand what you are disagreeing with me about. Clearly, we have some C code, where all translation units are correct in isolation, but in common implementations, their combination might (and likely will, but is not guaranteed by any standard to) result in machine code which messes with values on the stack in a way the compiler can’t account for. That much is inarguable, and I don’t see you claiming otherwise; so where is the contention?
Clearly, we have some C code, where all translation units are correct in isolation but where their combination might (and likely will) result in machine code which messes up values on the stack in a way the compiler doesn’t expect. That much is inarguable, and I don’t see you disagreeing with it
Indeed, that is correct.
so where is the contention?
The contention is in the following two points:
In suggesting that “In C (…) the compiler has literally no way of preventing you from doing this, and no way of detecting that it has occurred”, where “this” is creating a pointer to the stack and messing around with the stack.
I think that phrase is a bit misleading, because:
The C language has no construct to create a pointer to the stack, which means you’re either:
Relying on implementation-defined behavior, which means that the compiler is actually giving you such a pointer on purpose
Or it means there’s no way to deterministically create such a pointer, because the pointer may not even exist, i.e. the compiler may optimize it out.
Which means that the compiler can prevent you from doing that. And if it can’t, it’s probably because you’re relying on the calling convention which is implementation-defined behavior, therefore documented and the compiler would be doing it on purpose.
Or it means you’re relying on some library function or assembly code to create such a pointer, which is what I thought he meant and why I asked him to clarify as it’s not very common to do this!
The other contention point, which I admit is (even more?) pedantic, is:
In saying that all of this is specific to “pointers to the stack” when it is actually just a result of having pointers and going outside their bounds or the lifetime of the storage they point to, which applies to all types of pointers.
That said, yes, I understand that when going outside the bounds of a pointer (for example) to heap storage is unlikely to corrupt the stack (even though it’s possible) and that stack corruption is a very particular type of corruption which usually has very… interesting side-effects!
So in conclusion, I think we are in agreement with regards to the underlying issues, I just disagree with the phrasing and particularly, how it appears to be suggesting that the compiler is powerless to prevent it, when in fact you’re either breaking the invariants of the language itself, or the compiler is actually going out of its way to help you do that, on purpose (just in case you like to shoot yourself in the foot)!
Edit: “external library” -> “library”
Edit 2: in other words, you haven’t really forced the compiler to give you a pointer to the stack, it was the compiler who decided to give that to you, and it could just as easily have decided to do something else if it wanted (proof: the existence of conforming C compilers for architectures that don’t even have a stack).
If the compiler has a concept of what we would conventionally call a “stack”, and it has put a variable on the stack, the compiler has no way to prevent you from taking a pointer to that variable and messing around with other stuff that’s also on the stack and no way of detecting that it has occurred, assuming the compiler implements pointer arithmetic in the way all the common implementations do.
Personally, I think the original comment was clear enough, adding all those caveats just muddies the meaning IMO. But I won’t disagree that it’s assuming a few things which aren’t strictly guaranteed by the C standard.
[…] I just disagree with the phrasing and particularly, how it appears to be suggesting that the compiler is powerless to prevent it, when in fact you’re either breaking the invariants of the language itself, or the compiler is actually going out of its way to help you do that, on purpose […]
Well, you are breaking the invariants of the language, but I don’t understand how that means the compiler can prevent it. The compiler gives you a pointer to a variable which the complier has decided to put on what it calls “the stack”. The language has features which make compile-time tracking of where pointers come from impossible. The language has features which lets you do arithmetic on pointers. Given those facts, if a compiler is implemented in such a way that there exists a stack which contains stuff like the return address and local variables, the compiler is powerless to prevent you from messing with stuff the compiler has to assume is left unchanged.
I agree that a compiler might be implemented differently, it might store the return address stack separately from the variable stack, it might allocate every local variable in a separate heap allocation and automatically free them when the function returns, it might do runtime checking of all pointer dereferences, or any number of other things. But under the assumption that the implementation works roughly like all the major C implementations currently do, everything icefox said is correct.
If the compiler has a concept of what we would conventionally call a “stack”, and it has put a variable on the stack, the compiler has no way to prevent you from taking a pointer to that variable and messing around with other stuff that’s also on the stack and no way of detecting that it has occurred, assuming the compiler implements pointer arithmetic in the way all the common implementations do.
This phrasing is also wrong. The compiler can do all of those things and yet the pointer is not a pointer to the stack, it’s a pointer to the variable (which may currently be stored in a register or even may only exist as a constant in this exact moment, even though there’s an allocation for the variable in the stack).
For example if you have this code:
void some_function(int *y, bool condition) {
*y = *y + 5;
if (condition) {
y += 100000;
*y = 20;
}
}
void foo() {
int x[100] = {0};
int *y = &x[50];
some_function(y, false);
printf("%d", *y);
(...)
}
… it may not do what you think it does. Why? Because the compiler is allowed to transform that code into this equivalent code:
int some_specialized_function() {
return 5;
}
void foo() {
int x[100] = {0};
int z = some_specialized_function();
printf("%d", z);
x[50] = z; // this line may or may not exist, e.g. if x[50] is never used again
(...)
}
So even if there’s an allocation for x[] in the stack frame for some reason (let’s say some further code manipulates the array), you think that y is a pointer to the stack, but it may very well not even exist as such, even if the code for some_function hasn’t been inlined!
And even if you call some_function(y, true) instead of false, you think you tricked the compiler into corrupting the stack, but the compiler can clearly see that y points to &x[50] so increasing y by 100000 is absurd and the entire if block of the specialized some_function() implementation can be removed.
So yes, the compiler can prevent you from messing around with the stack even in that case.
The compiler gives you a pointer to a variable which the complier has decided to put on what it calls “the stack”.
Yes, you said it very well here, even though that doesn’t always happen. The compiler has decided. You haven’t forced it to do that. The compiler could have decided something else. It was an implementation choice, which means the compiler could have prevented it.
I agree that a compiler might be implemented differently, it might store the return address stack separately from the variable stack, it might allocate every local variable in a separate heap allocation and automatically free them when the function returns, it might do runtime checking of all pointer dereferences, or any number of other things.
Exactly! Which means that the compiler can actually prevent you from doing the things icefox said.
But under the assumption that the implementation works roughly like all the major C implementations currently do, everything icefox said is correct.
Well, it’s not possible for me to prove this, but to be honest, I think icefox had a misconception, as evidenced by the fact that (before he edited it) his reply to my comment said that just doing pointer arithmetic on a pointer to a local variable means that the compiler is forced to give you a pointer to the stack, when this is not true: compilers often optimize such pointers out of the code completely.
And you know, this entire debate could have been avoided if he just said “it’s often possible to corrupt the stack [perhaps by doing such and such], which has all these interesting effects” rather than suggesting that C compilers have some underlying limitation and are powerless to prevent you from messing with what they do.
But you know, apart from that, I think we are in agreement!
So it doesn’t matter that your CPU knows how to overflow a signed int.
I would say, it doesn’t matter that virtually all CPU in active use since… say the start of the 21st century, know how to overflow a signed int. Some platforms somewhere that existed at some point in time don’t know how to overflow signed integers, and so the standard committee thought it was a good idea to mark it “UB”, probably for portability reasons, and the compiler writers later thought it was a good idea to interpret it literally, for optimisation reasons.
This is where the standard committee should really have said something along the lines of:
Signed integer overflow is implementation defined…
except on platforms that produce non-deterministic results, in which case it’s unspecified…
except on platforms that fault, in which case it aborts the program, whatever that should mean…
except on platforms that fall into an inconsistent state, in which case it’s Undefined Behaviour™.
Sure, the specs are wordier this way, but that would have gotten rid of a huge swath of security vulnerabilities. And while some code would be slower, compiler writers would have told everyone they should use unsigned size_t indices for their loops.
But no, they didn’t define behaviour depending on the platform. If something is undefined in one supported platform, no matter how niche, then it’s undefined in all supported platforms. Just so it could be a little bit faster without requiring users to touch their source code.
My understanding of undefined behaviour is now as follows: compilers will, in the face of undefined behaviour, generate code that under the “right” conditions causes your hard drive to be encrypted and print a ransom message. The most useful threat model of a compiler is that of a sentient adversary: if there’s any UB in your code, it will eventually find it, and cause as much harm as it can up to and including causing people to die.
The compiler isn’t out to get you, and generally won’t include disk-encrypting code into your program if it wasn’t there before. The line about playing DOOM on UB is meant as humor and to demonstrate that it’s still not a compiler bug if this happens. But in reality, it isn’t actually going to happen in GCC, or Clang, or rustc, or any other compiler that wasn’t purpose-built to do that. It’s not guaranteed to not happen, but compilers are in practice not written to maliciously manufacture instructions out of whole cloth just to mess with you on purpose.
But at the same time, providing guarantees about undefined behavior … makes it not-undefined anymore. There can certainly be less undefined behavior (e.g. mandating the equivalent of NullPointerException, or Rust’s “safe Rust is UB-free Rust, or it’s a bug in the compiler” guarantee), but any real compiler will still have some UB. UB just means “this is an invariant that I expect and internally continue to uphold, and I don’t know what happens if something breaks it.” Even my toy compiler for the Advent of Code day 23 problem from last year contains a notion of UB, which I plan to discuss in an upcoming episode of my Compiler Adventures blog series – and that’s for a programming language that doesn’t even have if statements or loops!
I guess the playing DOOM on UB being humorous is written with MMU-using operating system mindset. I witnessed IRL a situation where a simple read from stdin, do some calculations, write to stdout C program was quite reliably opening CD-ROM tray… That was on Windows 3.11 I think.
My dad once traced a client-reported bug in his company’s software down to a bad CPU in the client’s machine. When adding two very specific 3-digit integers together, the sum was incorrect. It wasn’t UB that time, just bad hardware, but it doesn’t sound like it was fun to track down. And the accountants using the software certainly didn’t appreciate the fact that the computer was adding up their numbers wrong…
Since it’s the accountants’ computer that is broken, they have a catch 22. They need to ask for their money back, but the computer they do all their sums on is broken, so how much refund should they be asking for!? They can’t possibly calculate it. ;)
The compiler isn’t out to get you, and generally won’t include disk-encrypting code into your program if it wasn’t there before.
Correct, but ransomware authors are out to get me, and they’ll exploit any vulnerability they can. And UB driven compilers are a source of vulnerabilities that wouldn’t be there if more behaviour was defined. That’s where my threat model comes from. Blaming the compiler as if it was the enemy isn’t accurate, but it is simpler and more vivid.
Oh, and that talk from Chandler Carruth? I’ve watched it several time, its misleading and harmful. All the more because he’s such a good speaker. He’s trying to reassure people about the consequences of their bugs. Sure the compiler itself won’t actively summon the nasal demons, but outside attackers finding vulnerabilities will. And the result is the same: UB does enable the summoning of nasal demons.
But he’s not saying that out loud, because that would drive people away from C and C++.
But at the same time, providing guarantees about undefined behavior … makes it not-undefined anymore.
Correct, which is why I advocate for defining more behaviours in C.
Correct, which is why I advocate for defining more behaviours in C.
I think that’s a lost cause. Instead, it would be nice to have more options like -fwrapv that at least impose sane behaviour for things that are UB, strictly speaking.
I think the larger point is that, effectively, people who write C have to treat the compiler as a deadly hyperintelligent enemy deliberately attempting to cause as much harm as possible via any means available. Otherwise they just end up being hurt by the compiler, and then when they write it up they get mocked and belittled by people who tell them it’s their fault that this happened.
And since it’s effectively impossible to write useful/non-trivial C programs without UB, the takeaway for me is “don’t ever write C”.
FWIW I feel similarly. I’ve switched to Rust because I don’t trust myself to not write UB and to not commit memory safety errors. I still haven’t needed unsafe in Rust anywhere thus far, and “if it compiles then it’s memory-safe and UB-free” is worth a lot to me.
C users as a whole are hostile to any overheads and speed regressions in compilers. Compilers get benchmarked against each other, and any “unnecessary” instructions are filed as issues to fix.
Look how long it is taking to zero-init all variables in C and C++, even though overhead is rare and minimal, and the change is good for security and reliability.
I can’t imagine users accepting speed regressions when indexing by int, especially when it’s such a common type.
The most useful threat model of a compiler is that of a sentient adversary:
I just wrote a whole post trying to explain this couldn’t be further from the truth, so I don’t get what you’re trying to say here.
The most useful threat model of a compiler is that of a sentient adversary:
I just wrote a whole post trying to explain this couldn’t be further from the truth, so I don’t get what you’re trying to say here.
It’s an oversimplification. There are sentient adversaries out there out to exploit whatever vulnerabilities that may arise from your code. And mr compiler here, despite being neither sentient nor actively hostile, does tend to magnify the consequence of many bugs, or to turn into bugs idioms that many long time practitioners thought were perfectly reasonable.
Thus, I like to pretend the compiler itself is hostile. It makes my threat model simpler and more vivid. Which I pretty much need when I’m writing a cryptographic library in C, which I ship in source form with no control over which compilation flags may be used.
For example, you can compile an entire Linux distro with the -fwrapv gcc and clang flags and you’ll get the behavior you want (i.e. well-defined signed overflow with wrapping behavior).
All code that was previously C-standard-conformant will still remain C-standard-conformant. Additionally, code which previously triggered UB on signed overflow now also becomes well-defined.
Although I do sympathize with your point that this should probably be the default even if it has a performance cost, also note that in many cases such well-defined signed overflow can lead straight into UB or a crash anyway, because these integers in many cases are used as array indexes or on array index calculations.
Edit: might I suggest deterministically aborting on signed overflow/underflow? You can use -ftrapv for that.
I do wonder if one could extend LLVM with a visualization that tells us what optimizations used which assumptions, somehow summarizing on a top-level view while allowing us to drill down to each block. That would be a great teaching and debugging tool indeed.
That would be cool! But it sounds quite difficult to be honest. I’ve been thinking about ways to describe and represent information flow in my Compiler Adventures blog series on how compiler optimizations are implemented, and even for the massively-simplified language used there (no loops, no branches, no functions!) it’s still quite difficult to track “who did what where because of whose info.”
Of course this doesn’t say it can’t be done, and I really hope someone takes up that challenge. I’ll be excited to see the results.
If your compiler has 10 individual optimizations which get performed iteratively in a total of 30 optimization passes, you could imagine recording the output of every one of the 30 optimization passes and then showing that to the user, allowing him to go to the previous/next pass and see a diff of what changed.
You wouldn’t know exactly why an optimization happened if you’re not familiar with the optimization, but I think it would still be immensely instructive.
Although you’d need different visualizations and diff algorithms for different intermediate compiler languages (C AST, LLVM IR, assembly, etc).
This is a very good way to understand the behaviour of the compiler you’re using.
Fwiw you don’t need to store all the intermediate results if the compiler is deterministic, you can generate the one you want to look at by running all the passes up to that point.
I think you can do this right now with clang? By changing the list of passes and dumping IL.
You can do something like this with ghc-core for Haskell. :)
That is a load-bearing phrase right there :) Making compilers behave deterministically is possible but quite difficult. Folks working on reproducible builds have gone down this road, so we can learn from their experiences.
It might be a topic for a future “falsehoods programmers believe about compilers” post :)
I’d be a quite an ambitious project. Consider how incomplete debug information is in optimized programs. Optimizers already struggle with even the most basic tracking of where the code came from. So tracking all the changes, their causes, and their assumptions would be even harder.
There’s a lot of passes (that’s where majority of compilation time is spent). They are a mix of analysis and transformations passes that aren’t explicitly connected. Some passes even generate new unoptimized code that is meant to be cleaned up by other passes, so it’s hard to track meaningful causality throughout all of that.
Optimizers work on a low-level code representation where your variables don’t exist any more (SSA form), there are no for, while or if constructs, only goto between chunks of assembly-like code (CFG). So even if you collect all the data without running out of memory, filter it down to only relevant bits, it would still be difficult to present it in a way that is relevant to C programmers.
Compilers have these in what they call back-ends, which are usually separate from their main optimiser, and are language-independent, so the concept of C’s UB doesn’t exist there any more.
But if the line with UB isn’t executed, then the program will work normally as if the UB wasn’t there
I think you must mean something different by this than how I’m reading it.
Just about any line of C code could contain undefined behaviour. A dereferenced pointer could be null or invalid. Most (admittedly not all) undefined behaviours are a result of runtime operations, not existence of a line of code, even if that line of code could only ever have undefined behaviour were it to be executed. As long as such a line is not executed, the “program will work normally” assumption is actually correct (assuming “work normally” means it will work without the effects of UB coming into play).
(Exception to this would be lines of code which have undefined behaviour that does not depend on a runtime action, of course. One somewhat perverse example that was in the C standard at one point - I’m not sure if it still is - is when the source file does not end with a newline).
Similarly with:
Okay, but if the line with UB is unreachable (dead) code, then it’s as if the UB wasn’t there
You have an example for this one (good!). It’s in Rust so I’m not sure I fully understand it, but I think what it’s showing is that UB (in this case invoked by having an invalid value, even though it’s not “used”) can seemingly cause dead code to be executed, not that UB in dead code has an effect otherwise.
There’s been a good amount of discussion (across various sites) about those few points, and I plan to update the article (with clearly marked edits) with what I’ve learned. Given what I know now, I think points 13-16 are too vague and inaccurate without further (not necessarily obvious) assumptions. It’s not unreasonable to declare them incorrect as currently stated.
Most (admittedly not all) undefined behaviours are a result of runtime operations, not existence of a line of code, even if that line of code could only ever have undefined behaviour were it to be executed.
As long as such a line is not executed, the “program will work normally” assumption is actually correct (assuming “work normally” means it will work without the effects of UB coming into play).
It’s a bit hard for me to understand exactly what you mean in the above sentences.
But if I understood you correctly, I think you are correct about C but not C++, as this sentence from the C++ standard [1] seems to contradict what you are saying:
However, if any such execution contains an undefined operation, this document places
no requirement on the implementation executing that program with that input (not even with regard to operations preceding the first undefined operation).
With this definition, in an extreme case, it would be possible for your program to crash on the very first line of code, if the compiler could somehow determine that 20 minutes later your program would invoke UB.
I am not aware of a similar definition existing for C, though.
I think you may have misunderstood me, actually. I’m not saying that undefined behaviour that does (or which definitely will) happen cannot change the behaviour of the program before the UB happens (not even for C, though maybe that’s less explicit than it is for C++).
I’m saying that, if there is some code that would exhibit UB if it executed, but it won’t execute, then the presence of such code alone does not cause the program overall to have undefined behaviour (and cannot cause such issues such as code that should be dead to actually execute).
As a trivial example, consider:
if (0) {
*((int *)NULL) = 0; // would be UB if it executed, but it will never execute
}
Having such code in your program doesn’t automatically result in your program having undefined behaviour. The UB-exhibiting code (eg the assignment through the NULL pointer) needs to execute (in an execution according to the rules of execution for the abstract machine defined by the C standard) for that to be the case, and in this particular example, it can’t, assuming that the program doesn’t otherwise have undefined behaviour due to some other part of the code.
This is in contrast to the original post, which says that:
But if the line with UB isn’t executed, then the program will work normally as if the UB wasn’t there
Higher level languages often do have some guarantees for UB, but not much. For example, the UB in your Java program may not crash the JVM. It may hang it, but not crash it.
Rust and C# have similar “UB only with unsafe” designs.
And if you think that UB in Java can’t crash the JVM, try using Unsafe to scribble random bytes at random offsets in memory for a bit :) At a previous job, I was in charge of a component that used Java Unsafe and bugs in that component frequently caused programs to die with a segfault and without a Java stack trace.
Hmmm…. I no longer program in Java. For years after working at JavaSoft, I claimed I did not know Java.
If you were able to get undefined behavior with poor synchronization. From 17.4.8: We use f|d to denote the function given by restricting the domain of f to d. For all x in d, f|d(x) = f(x), and for all x not in d, f|d(x) is undefined.
The existence of a test suite (new to include in a language) did cut down the undefined stuff. We had a policy of ‘excusing’ any test failure and letting people still brand as Java on a release. To release the next update, they had to pass every compatibility test they failed previously.
Still, we ran out of Russian software professors desperately working from the spec when it was too dangerous to ship them workstations. The lack of undefined behavior is merely a pleasant fantasy.
To give a background why is that: UB is not an event that happens in the program. Instead, “UB is impossible” is an assumption that is baked into the compilers.
The compilers don’t have
if is_UB() { screw_you() }anywhere. The no-UB assumptions can be implicit and pervasive. Like an assumption that opposite oftrueisfalse, soif (x) {do}andif (!x) {} else {do}are equivalent. If you magically made a 3-valued bool withfilenotfound, then it’s not merely triggering someelse { lol() }code path in the optimizer. Instead, it makes all the assumptions about boolean algebra invalid and full of impossible-to-reason about paradoxes. And it’s hard to warn about this, because UB is not an event or a code path. The compiler would have to warn about every non-issue like “here I’ve assumed that the opposite offalseistrue”.The second reason is dealing with complexity of optimizations. It’s too difficult to optimize code in the high-level form you write it. There are too many tree structures to work with, too many scopes, too many constraints to preserve. Instead, the code is “lowered” to a simpler assembler-like representation that no longer resembles the source code. In this form programmer’s intention is hard to see, so it’s no longer obvious what should and shouldn’t be optimized out.
To manage the complexity, optimizations are applied to low-level code in multiple independent passes. This way instead of having to consider all of the C spec for any change, each pass can focus on one thing at a time, e.g. “can I change
!!xtox”. There’s a pass that simplifies arithmetic, there’s a pass that checks which expressions are always true, and there’s a pass that removes unreachable code. They can end up removing your null or overflow checks, but they don’t mean to — each pass does its own thing that in isolation seems sensible, spec-compliant, and is useful for most of the code.And finally, majority of the optimizers in C compilers are shared across all architectures. They evaluate code as if it ran on the hypothetical portable machine that the C spec describes, not your particular CPU. So it doesn’t matter that your CPU knows how to overflow a signed int or has caches coherent across threads. The low-level virtual machine the optimizer optimizes for doesn’t have that, and code under optimizer will “run” in the C way instead.
This is a great explanation, but substitute ‘integer’ for ‘boolean’ and you get why C compilers really like that signed integer overflow is undefined. If you write something that loops performing some addition on an integer, then you have an induction variable that can be modelled as an arithmetic sequence. If you have a nested loop, then the induction variable can be modelled as a geometric sequence. This model is completely wrong in every regard if adding two positive values together can result in a negative number. Having to understand this case precludes any transform from making use of this information. This precludes a large number of loop optimisations.
But isn’t that just as true of unsigned integer overflow? You don’t unexpectedly get a negative sum, but you do get one that’s completely wrong.
Signed overflow is UB so compilers get to pretend it can’t happen. The lack of UB on unsigned integer overflow means that many compilers don’t optimize unsigned arithmetic nearly as aggressively, for precisely the reason you point out. The difference is that compilers aren’t allowed to ignore the possibility of unsigned overflow since it’s well-defined and allowed to happen.
My favorite example of undefined behavior: creating a pointer into the stack and messing around with its contents. In C or unsafe Rust or something like that, compiler has literally no way of preventing you from doing this, and no way of detecting that it has occurred. It’s not even “this is on you to make it safe” territory, because the compiler is allowed to assume the contents of the stack doesn’t change out from underneath it… it may juggle local variables in and out of registers or something and, within the bounds of the calling convention, you get make zero assumptions about how it works. Just ‘cause one compiler puts a particular local var at
[rsp+24]or whatever doesn’t mean it will be there the next time you compile the program.Yes, you can do it. You can even make it work, if you know exactly how the compiler works and the compiler doesn’t change. But you’re breaking the invariants that the compiler fundamentally uses to function, and it is incapable of noticing that you are doing it.
Wait, what? How do you create such a pointer, exactly?
You’d have to use assembly code I assume? Or some library that uses assembly code?
The alloca function returns a pointer to memory allocated on the stack! I’m surprised it hasn’t been mentioned in the thread yet.
https://www.man7.org/linux/man-pages/man3/alloca.3.html
D’oh! Of course, how didn’t I remember that? Thanks!
Edit: goes to show how often that function is used, hah!
…You mean playing around with the stack isn’t the first thing everyone does when learning how C works?
https://godbolt.org/z/GYzq87G4s
(Update: Notably, if you pass
-O3to most versions of gcc in godbolt it will generate the code you expect, but clang will almost invariably nope out and just return 1 or 0 or nothing at all. Fun!)That’s not what I imagined a pointer into the stack would be from your description.
That’s a pointer into a local variable. The compiler wouldn’t even allocate stack space if you compile with optimizations.
Pointers to local variables are not UB.
Edit: What is UB in this case is that you incremented “
b” outside the array bounds (a pointer to a single object is considered to be a pointer into an array of 1 element).Edit 2: You can freely use such pointers while the compiler passes variables into and out of registers and your program will still work just fine. But your pointer is not allowed to go outside the bounds of the array (except to point one-past the array, but then you can’t dereference it).
You are correct, the UB in this case is incrementing the pointer out of its bounds. The thing is that a local variable (edit: usually) has to exist on the stack if you have a pointer to it that does arithmetic. So the easy way to get a pointer to a random place on the stack is to start from a local variable. You can also have a function that returns a pointer to a local var, you can start in the data segment or heap, or you can just make a good guess of where your stack is and hope ASLR doesn’t ruin your fun.
Or if you really want to go hard, you can ask a user to type in a number and use that as an address. Who knows what they’ll type in? The compiler sure doesn’t.
What? No, that’s not true. See for yourself: https://godbolt.org/z/PvfEoGTnc
No, you don’t necessarily get a pointer to a random place on the stack if you do that. The local variable or array may not even exist on the stack.
If you go outside the object/array bounds with pointer arithmetic, you get UB which does not have to (and many times won’t) translate into a random pointer, it will just mean that your code will break (and it can break in many different ways).
You should really, really, carefully read @kornel’s top post to understand how UB works.
That’s UB but again, you won’t necessarily get a random pointer to the stack, as the variable may not even exist on the stack. And even if it does exist, your code can break in completely different ways than getting a random pointer to the stack.
You’d get UB if your pointer goes outside of a malloc()-allocated area, but again, you wouldn’t necessarily get a pointer value. You’re making the exact same false assumptions that @kornel talks about.
Your code could simply be completely optimized out, or it may cause other very strange effects that have nothing to do with pointers.
Even if you knew exactly where your stack is, I don’t think there is a way to deterministically create such a pointer without implementation-specific behavior (e.g. assembly code).
Edit: updated Godbolt link due to a typo in the code.
I believe converting an arbitrary integer into a pointer is also UB and you don’t necessarily get a pointer like you think you will, your code can just completely break in lots of different ways (including simply being optimized out).
You’d have to enable some kind of special implementation-specific compiler option to do something like that without UB.
What is not UB, I believe, is to e.g. pass a pointer value into an
intptr_tvariable and then back into a pointer without changing the value.And yet this is also how just about every device driver under the sun works.
Because of this:
Edit:
Correction: technically speaking, it seems that the integer-to-pointer conversion itself is not UB if you use an explicit cast, but the C standard says the result is implementation-defined, so the code can behave differently depending on which compiler (or compiler version, or compiler flags) you’re using.
In fact, the C standard says that the resulting value can be a trap representation, which means that it could trigger UB as soon as you tried to do anything with that pointer.
Even if your implementation allows doing that and even if the integer is a valid memory location, I would imagine it would still be possible to trigger UB by violating other constraints, like creating a duplicate copy of another pointer of a different type (which could violate strict aliasing constraints), or creating a pointer with the wrong alignment, or calling
free(ptr)if the memory location hadn’t been allocated withmalloc()before, etc.The int-to-ptr operation is actually fundamentally implementation-defined. So you won’t find the UB rules for ptr-to-int and int-to-ptr in the standard, you need to look at the LLVM LangRef instead.
Yes, I mentioned that in my other reply.
But note: it is undefined behavior if you don’t use an explicit cast, e.g. if you do this:
int *a = 4, then it is UB.Why is it not a compile error?
It is a compile error:
https://godbolt.org/z/Gq8qbW559
But that’s on GCC (probably clang does the same). There might be C compilers that are C-standard-compliant that might not generate an error.
If you are asking why doesn’t the C standard specify that such conversions are invalid rather than UB? No idea!
Edit: oh wait, I made a mistake! The above error is when compiling in C++ mode (the Compiler Explorer’s default, annoyingly). In C mode, it’s not an error, it’s a warning by default:
https://godbolt.org/z/rP3KoGbx3
That said, you can transform that into an error by adding
-Werrorto the compiler flags, of course.I don’t think this is the kind of error you’re expecting to see - if you change the code to
int *a = (int *)4it should compile without warning. I don’t know if this is even supposed to be undefined behaviour - when talking to devices you need to know the exact memory address “as a number” and write to it or read to it (think VGA video memory addressing and such), which is or was traditionally often done in C under DOS in real mode, for example.Although it might be that this has sort-of been retconned into “always having been wrong” like relying on hardware behaviour on integer overflow has been.
Local variables are generally allocated on the stack. In some cases, it may be able to not allocate memory at all and keep the local variable purely in a register, but any time you mess around with pointers to local variables – especially when those pointers are passed across non-inlined function boundaries – that pointer is to the stack-allocated local variable.
With optimizations disabled, you can look at the assembly code and stack frame and verify that ‘a’ is allocated on the stack and ‘b’ is a pointer to that stack-allocated variable in icefox’s example. Here’s a slightly modified example where the pointer is passed across a function boundary to be dereferenced: https://godbolt.org/z/x8zEKEr1E
Yes, I know that, but @icefox was talking about “creating a pointer to the stack”, but as far as I can see there is no way to create a pointer to the stack in the C language, or at least no portable way to do it (i.e. without relying on implementation-defined behavior).
The C18 standard, as far as I can see, doesn’t even have the word “stack” in the 535-page document!
Someone else mentioned
alloca()but even that is not part of any standard.Then he said:
Which seems to make little sense because if you’re relying on implementation-defined behavior (which has to be documented) to create a pointer to the stack, then that means that the compiler has already promised to give you a pointer to the stack. So of course it can’t prevent you from messing around with it.
It’s not like you “tricked” the compiler into giving you such a pointer, usually it’s actually the opposite: the compiler is the one who tricks you into thinking that you have a pointer to the stack when in fact the local variables (and even arrays) that the pointer points to, may only exist in registers or, since all the values of the variable might be possible to determine at compile time, may not exist at all!
Edit: That said, yes, I understand that if you rely on implementation-defined behavior then it is possible to deterministically create such a pointer (e.g. with
alloca()) and mess around with it, such as corrupting the stack and causing UB. Which is what I meant when I said that you’d have to call some (platform-specific) library function to do that, it’s not like there’s a construct in the C language that says: “this is how you create a pointer to the stack”.Edit 2: clarified the comment a bit.
You can’t find the word “stack” in the C standard because the C standard indeed has no concept of a “stack”. As far as the standard is concerned, local variables have automatic storage and are alive until the function returns, variables allocated with
mallocand the like have allocated storage and are alive until they are freed withfree.However, the common implementations have a chunk of memory they call “the stack”, where each function gets a sub-chunk called a “stack frame” which is where the compiler puts, among other things, the variables with automatic storage (except for those variables which it optimizes out or keeps in registers only). Therefore, when you take the address of a variable with automatic storage, the implementation will give you an address to the place in the function’s stack frame where that variable is kept; you have a pointer to somewhere in the stack.
There is some mixing of abstraction levels here. You never have a “pointer to a variable allocated on the stack” in terms of the C abstract machine, you have a “pointer to a variable with automatic storage”. But when we lower that into the level of concrete machine code for some operating system, we can see that in the right circumstances, our “pointer to a variable with automatic storage” gets lowered into a “pointer to a chunk of memory in the function’s stack frame”. So we can create an example program which proves @icefox’s point (namely that the “compiler has literally no way of preventing you from doing this, and no way of detecting that it has occurred”):
a.c:
b.c:
No individual function in this example does anything wrong, but in combination, they mess around with the stack in ways which the implementation can’t anticipate.
You don’t actually know if they mess around with the stack, they may very well not. With link-time optimization all of that code could be inlined together and no pointers to the stack would even be created.
What you are saying is actually a result of the following:
The pointer points to a single object, rather than a sufficiently-large array of objects. Which results in UB when you do pointer arithmetic past the bounds of the array.
Or, in other situations, it could result in UB due to dereferencing a pointer past the lifetime of the object (which could happen both for automatic storage and for heap-allocated storage).
It has nothing to do with “the stack” or a “pointer to the stack”. It is simply the result of having “a pointer” (to some non-permanent storage).
You are assuming that a specific implementation detail will happen. How do you know that’s what will happen? Does your C compiler or some other standard guarantee that? I assume the compiler documentation or a calling convention such as the System V ABI may be able to guarantee that. But if it does guarantee it, how is that “the implementation not anticipating”?
Edit: API -> ABI
I don’t understand what you are disagreeing with me about. Clearly, we have some C code, where all translation units are correct in isolation, but in common implementations, their combination might (and likely will, but is not guaranteed by any standard to) result in machine code which messes with values on the stack in a way the compiler can’t account for. That much is inarguable, and I don’t see you claiming otherwise; so where is the contention?
Indeed, that is correct.
The contention is in the following two points:
I think that phrase is a bit misleading, because:
Which means that the compiler can prevent you from doing that. And if it can’t, it’s probably because you’re relying on the calling convention which is implementation-defined behavior, therefore documented and the compiler would be doing it on purpose.
The other contention point, which I admit is (even more?) pedantic, is:
That said, yes, I understand that when going outside the bounds of a pointer (for example) to heap storage is unlikely to corrupt the stack (even though it’s possible) and that stack corruption is a very particular type of corruption which usually has very… interesting side-effects!
So in conclusion, I think we are in agreement with regards to the underlying issues, I just disagree with the phrasing and particularly, how it appears to be suggesting that the compiler is powerless to prevent it, when in fact you’re either breaking the invariants of the language itself, or the compiler is actually going out of its way to help you do that, on purpose (just in case you like to shoot yourself in the foot)!
Edit: “external library” -> “library”
Edit 2: in other words, you haven’t really forced the compiler to give you a pointer to the stack, it was the compiler who decided to give that to you, and it could just as easily have decided to do something else if it wanted (proof: the existence of conforming C compilers for architectures that don’t even have a stack).
So you would be completely happy with:
Personally, I think the original comment was clear enough, adding all those caveats just muddies the meaning IMO. But I won’t disagree that it’s assuming a few things which aren’t strictly guaranteed by the C standard.
Well, you are breaking the invariants of the language, but I don’t understand how that means the compiler can prevent it. The compiler gives you a pointer to a variable which the complier has decided to put on what it calls “the stack”. The language has features which make compile-time tracking of where pointers come from impossible. The language has features which lets you do arithmetic on pointers. Given those facts, if a compiler is implemented in such a way that there exists a stack which contains stuff like the return address and local variables, the compiler is powerless to prevent you from messing with stuff the compiler has to assume is left unchanged.
I agree that a compiler might be implemented differently, it might store the return address stack separately from the variable stack, it might allocate every local variable in a separate heap allocation and automatically free them when the function returns, it might do runtime checking of all pointer dereferences, or any number of other things. But under the assumption that the implementation works roughly like all the major C implementations currently do, everything icefox said is correct.
This phrasing is also wrong. The compiler can do all of those things and yet the pointer is not a pointer to the stack, it’s a pointer to the variable (which may currently be stored in a register or even may only exist as a constant in this exact moment, even though there’s an allocation for the variable in the stack).
For example if you have this code:
… it may not do what you think it does. Why? Because the compiler is allowed to transform that code into this equivalent code:
So even if there’s an allocation for
x[]in the stack frame for some reason (let’s say some further code manipulates the array), you think thatyis a pointer to the stack, but it may very well not even exist as such, even if the code forsome_functionhasn’t been inlined!And even if you call
some_function(y, true)instead offalse, you think you tricked the compiler into corrupting the stack, but the compiler can clearly see thatypoints to&x[50]so increasingyby100000is absurd and the entireifblock of the specializedsome_function()implementation can be removed.So yes, the compiler can prevent you from messing around with the stack even in that case.
Yes, you said it very well here, even though that doesn’t always happen. The compiler has decided. You haven’t forced it to do that. The compiler could have decided something else. It was an implementation choice, which means the compiler could have prevented it.
Exactly! Which means that the compiler can actually prevent you from doing the things icefox said.
Well, it’s not possible for me to prove this, but to be honest, I think icefox had a misconception, as evidenced by the fact that (before he edited it) his reply to my comment said that just doing pointer arithmetic on a pointer to a local variable means that the compiler is forced to give you a pointer to the stack, when this is not true: compilers often optimize such pointers out of the code completely.
And you know, this entire debate could have been avoided if he just said “it’s often possible to corrupt the stack [perhaps by doing such and such], which has all these interesting effects” rather than suggesting that C compilers have some underlying limitation and are powerless to prevent you from messing with what they do.
But you know, apart from that, I think we are in agreement!
Edit: renamed function name to clarify the code.
I would say, it doesn’t matter that virtually all CPU in active use since… say the start of the 21st century, know how to overflow a signed int. Some platforms somewhere that existed at some point in time don’t know how to overflow signed integers, and so the standard committee thought it was a good idea to mark it “UB”, probably for portability reasons, and the compiler writers later thought it was a good idea to interpret it literally, for optimisation reasons.
This is where the standard committee should really have said something along the lines of:
Sure, the specs are wordier this way, but that would have gotten rid of a huge swath of security vulnerabilities. And while some code would be slower, compiler writers would have told everyone they should use unsigned
size_tindices for their loops.But no, they didn’t define behaviour depending on the platform. If something is undefined in one supported platform, no matter how niche, then it’s undefined in all supported platforms. Just so it could be a little bit faster without requiring users to touch their source code.
My understanding of undefined behaviour is now as follows: compilers will, in the face of undefined behaviour, generate code that under the “right” conditions causes your hard drive to be encrypted and print a ransom message. The most useful threat model of a compiler is that of a sentient adversary: if there’s any UB in your code, it will eventually find it, and cause as much harm as it can up to and including causing people to die.
A plea to compiler writers: please rein that in?
(post author here)
Unfortunately, it’s not that easy.
The compiler isn’t out to get you, and generally won’t include disk-encrypting code into your program if it wasn’t there before. The line about playing DOOM on UB is meant as humor and to demonstrate that it’s still not a compiler bug if this happens. But in reality, it isn’t actually going to happen in GCC, or Clang, or rustc, or any other compiler that wasn’t purpose-built to do that. It’s not guaranteed to not happen, but compilers are in practice not written to maliciously manufacture instructions out of whole cloth just to mess with you on purpose.
But at the same time, providing guarantees about undefined behavior … makes it not-undefined anymore. There can certainly be less undefined behavior (e.g. mandating the equivalent of
NullPointerException, or Rust’s “safe Rust is UB-free Rust, or it’s a bug in the compiler” guarantee), but any real compiler will still have some UB. UB just means “this is an invariant that I expect and internally continue to uphold, and I don’t know what happens if something breaks it.” Even my toy compiler for the Advent of Code day 23 problem from last year contains a notion of UB, which I plan to discuss in an upcoming episode of my Compiler Adventures blog series – and that’s for a programming language that doesn’t even haveifstatements or loops!I highly recommend this talk on UB if you have 40min: https://www.youtube.com/watch?v=yG1OZ69H_-o
I guess the playing DOOM on UB being humorous is written with MMU-using operating system mindset. I witnessed IRL a situation where a simple read from stdin, do some calculations, write to stdout C program was quite reliably opening CD-ROM tray… That was on Windows 3.11 I think.
That’s amazing :)
My dad once traced a client-reported bug in his company’s software down to a bad CPU in the client’s machine. When adding two very specific 3-digit integers together, the sum was incorrect. It wasn’t UB that time, just bad hardware, but it doesn’t sound like it was fun to track down. And the accountants using the software certainly didn’t appreciate the fact that the computer was adding up their numbers wrong…
Since it’s the accountants’ computer that is broken, they have a catch 22. They need to ask for their money back, but the computer they do all their sums on is broken, so how much refund should they be asking for!? They can’t possibly calculate it. ;)
Correct, but ransomware authors are out to get me, and they’ll exploit any vulnerability they can. And UB driven compilers are a source of vulnerabilities that wouldn’t be there if more behaviour was defined. That’s where my threat model comes from. Blaming the compiler as if it was the enemy isn’t accurate, but it is simpler and more vivid.
Oh, and that talk from Chandler Carruth? I’ve watched it several time, its misleading and harmful. All the more because he’s such a good speaker. He’s trying to reassure people about the consequences of their bugs. Sure the compiler itself won’t actively summon the nasal demons, but outside attackers finding vulnerabilities will. And the result is the same: UB does enable the summoning of nasal demons.
But he’s not saying that out loud, because that would drive people away from C and C++.
Correct, which is why I advocate for defining more behaviours in C.
I think that’s a lost cause. Instead, it would be nice to have more options like
-fwrapvthat at least impose sane behaviour for things that are UB, strictly speaking.Of course, your position is valid: it sounds like you are making an even more conservative set of assumptions than the minimum necessary set.
I wish more people took more precautions than strictly necessary, rather than fewer than necessary as is frequently the case :)
I think the larger point is that, effectively, people who write C have to treat the compiler as a deadly hyperintelligent enemy deliberately attempting to cause as much harm as possible via any means available. Otherwise they just end up being hurt by the compiler, and then when they write it up they get mocked and belittled by people who tell them it’s their fault that this happened.
And since it’s effectively impossible to write useful/non-trivial C programs without UB, the takeaway for me is “don’t ever write C”.
FWIW I feel similarly. I’ve switched to Rust because I don’t trust myself to not write UB and to not commit memory safety errors. I still haven’t needed
unsafein Rust anywhere thus far, and “if it compiles then it’s memory-safe and UB-free” is worth a lot to me.C users as a whole are hostile to any overheads and speed regressions in compilers. Compilers get benchmarked against each other, and any “unnecessary” instructions are filed as issues to fix.
Look how long it is taking to zero-init all variables in C and C++, even though overhead is rare and minimal, and the change is good for security and reliability.
I can’t imagine users accepting speed regressions when indexing by
int, especially when it’s such a common type.I just wrote a whole post trying to explain this couldn’t be further from the truth, so I don’t get what you’re trying to say here.
It’s an oversimplification. There are sentient adversaries out there out to exploit whatever vulnerabilities that may arise from your code. And mr compiler here, despite being neither sentient nor actively hostile, does tend to magnify the consequence of many bugs, or to turn into bugs idioms that many long time practitioners thought were perfectly reasonable.
Thus, I like to pretend the compiler itself is hostile. It makes my threat model simpler and more vivid. Which I pretty much need when I’m writing a cryptographic library in C, which I ship in source form with no control over which compilation flags may be used.
Strictly speaking, undefined behavior allows implementation-specific behavior ;)
For example, you can compile an entire Linux distro with the
-fwrapvgcc and clang flags and you’ll get the behavior you want (i.e. well-defined signed overflow with wrapping behavior).All code that was previously C-standard-conformant will still remain C-standard-conformant. Additionally, code which previously triggered UB on signed overflow now also becomes well-defined.
Although I do sympathize with your point that this should probably be the default even if it has a performance cost, also note that in many cases such well-defined signed overflow can lead straight into UB or a crash anyway, because these integers in many cases are used as array indexes or on array index calculations.
Edit: might I suggest deterministically aborting on signed overflow/underflow? You can use
-ftrapvfor that.I do wonder if one could extend LLVM with a visualization that tells us what optimizations used which assumptions, somehow summarizing on a top-level view while allowing us to drill down to each block. That would be a great teaching and debugging tool indeed.
Apparently you can now see optimization passes in LLVM on the Compiler Explorer, but I don’t think it has assumptions or things like that.
That would be cool! But it sounds quite difficult to be honest. I’ve been thinking about ways to describe and represent information flow in my Compiler Adventures blog series on how compiler optimizations are implemented, and even for the massively-simplified language used there (no loops, no branches, no functions!) it’s still quite difficult to track “who did what where because of whose info.”
Of course this doesn’t say it can’t be done, and I really hope someone takes up that challenge. I’ll be excited to see the results.
I think that e-class (program equivalence classes) graph edges could be annotated with which optimization produced the candidate equivalent program
If your compiler has 10 individual optimizations which get performed iteratively in a total of 30 optimization passes, you could imagine recording the output of every one of the 30 optimization passes and then showing that to the user, allowing him to go to the previous/next pass and see a diff of what changed.
You wouldn’t know exactly why an optimization happened if you’re not familiar with the optimization, but I think it would still be immensely instructive.
Although you’d need different visualizations and diff algorithms for different intermediate compiler languages (C AST, LLVM IR, assembly, etc).
This is a very good way to understand the behaviour of the compiler you’re using.
Fwiw you don’t need to store all the intermediate results if the compiler is deterministic, you can generate the one you want to look at by running all the passes up to that point.
I think you can do this right now with clang? By changing the list of passes and dumping IL.
You can do something like this with ghc-core for Haskell. :)
That is a load-bearing phrase right there :) Making compilers behave deterministically is possible but quite difficult. Folks working on reproducible builds have gone down this road, so we can learn from their experiences.
It might be a topic for a future “falsehoods programmers believe about compilers” post :)
I think in practice they mostly are.
I’d be a quite an ambitious project. Consider how incomplete debug information is in optimized programs. Optimizers already struggle with even the most basic tracking of where the code came from. So tracking all the changes, their causes, and their assumptions would be even harder.
There’s a lot of passes (that’s where majority of compilation time is spent). They are a mix of analysis and transformations passes that aren’t explicitly connected. Some passes even generate new unoptimized code that is meant to be cleaned up by other passes, so it’s hard to track meaningful causality throughout all of that.
Optimizers work on a low-level code representation where your variables don’t exist any more (SSA form), there are no
for,whileorifconstructs, onlygotobetween chunks of assembly-like code (CFG). So even if you collect all the data without running out of memory, filter it down to only relevant bits, it would still be difficult to present it in a way that is relevant to C programmers.There may also be asm optimization passes
Compilers have these in what they call back-ends, which are usually separate from their main optimiser, and are language-independent, so the concept of C’s UB doesn’t exist there any more.
I think you must mean something different by this than how I’m reading it.
Just about any line of C code could contain undefined behaviour. A dereferenced pointer could be null or invalid. Most (admittedly not all) undefined behaviours are a result of runtime operations, not existence of a line of code, even if that line of code could only ever have undefined behaviour were it to be executed. As long as such a line is not executed, the “program will work normally” assumption is actually correct (assuming “work normally” means it will work without the effects of UB coming into play).
(Exception to this would be lines of code which have undefined behaviour that does not depend on a runtime action, of course. One somewhat perverse example that was in the C standard at one point - I’m not sure if it still is - is when the source file does not end with a newline).
Similarly with:
You have an example for this one (good!). It’s in Rust so I’m not sure I fully understand it, but I think what it’s showing is that UB (in this case invoked by having an invalid value, even though it’s not “used”) can seemingly cause dead code to be executed, not that UB in dead code has an effect otherwise.
There’s been a good amount of discussion (across various sites) about those few points, and I plan to update the article (with clearly marked edits) with what I’ve learned. Given what I know now, I think points 13-16 are too vague and inaccurate without further (not necessarily obvious) assumptions. It’s not unreasonable to declare them incorrect as currently stated.
Here’s a good summary with better wording of the weirdness that I was attempting (and failing) to convey: https://www.reddit.com/r/rust/comments/z7115a/comment/iy4w557/
It’s a bit hard for me to understand exactly what you mean in the above sentences.
But if I understood you correctly, I think you are correct about C but not C++, as this sentence from the C++ standard [1] seems to contradict what you are saying:
With this definition, in an extreme case, it would be possible for your program to crash on the very first line of code, if the compiler could somehow determine that 20 minutes later your program would invoke UB.
I am not aware of a similar definition existing for C, though.
[1] https://isocpp.org/files/papers/N4860.pdf
Edit: added a sentence
I think you may have misunderstood me, actually. I’m not saying that undefined behaviour that does (or which definitely will) happen cannot change the behaviour of the program before the UB happens (not even for C, though maybe that’s less explicit than it is for C++).
I’m saying that, if there is some code that would exhibit UB if it executed, but it won’t execute, then the presence of such code alone does not cause the program overall to have undefined behaviour (and cannot cause such issues such as code that should be dead to actually execute).
As a trivial example, consider:
Having such code in your program doesn’t automatically result in your program having undefined behaviour. The UB-exhibiting code (eg the assignment through the NULL pointer) needs to execute (in an execution according to the rules of execution for the abstract machine defined by the C standard) for that to be the case, and in this particular example, it can’t, assuming that the program doesn’t otherwise have undefined behaviour due to some other part of the code.
This is in contrast to the original post, which says that:
… is false.
I hope that makes sense.
Yes, that makes sense now. Thanks!
Higher level languages often do have some guarantees for UB, but not much. For example, the UB in your Java program may not crash the JVM. It may hang it, but not crash it.
AFAIK Java has no undefined behaviour.
There’s definitely less UB in Java, but not zero. The outcomes of misusing the functionality in the
Unsafeclass are most certainly undefined: https://blogs.oracle.com/javamagazine/post/the-unsafe-class-unsafe-at-any-speedRust and C# have similar “UB only with unsafe” designs.
And if you think that UB in Java can’t crash the JVM, try using
Unsafeto scribble random bytes at random offsets in memory for a bit :) At a previous job, I was in charge of a component that used JavaUnsafeand bugs in that component frequently caused programs to die with a segfault and without a Java stack trace.Hmmm…. I no longer program in Java. For years after working at JavaSoft, I claimed I did not know Java.
If you were able to get undefined behavior with poor synchronization. From 17.4.8: We use f|d to denote the function given by restricting the domain of f to d. For all x in d, f|d(x) = f(x), and for all x not in d, f|d(x) is undefined.
There are others I didn’t get burned by: https://itecnotes.com/software/java-undefined-behaviour-in-java/
The existence of a test suite (new to include in a language) did cut down the undefined stuff. We had a policy of ‘excusing’ any test failure and letting people still brand as Java on a release. To release the next update, they had to pass every compatibility test they failed previously.
Still, we ran out of Russian software professors desperately working from the spec when it was too dangerous to ship them workstations. The lack of undefined behavior is merely a pleasant fantasy.