Webinar: Parsing C++ - 10.10
Undefined behavior (UB) is a tricky concept in programming languages and compilers. I've heard many misconceptions about what the compiler guarantees in the presence of UB. This is unfortunate but not surprising!
We published and translated this article with the copyright holder's permission. The author is Predrag Gruevski. The article was originally published on Predrag's Blog.
For a primer on undefined behavior and why we can't just "define all the behaviors," I highly recommend Chandler Carruth's talk "Garbage In, Garbage Out: Arguing about Undefined Behavior with Nasal Demons."
You might also be familiar with my Compiler Adventures blog series on how compiler optimizations work. An upcoming episode is about implementing optimizations that take advantage of undefined behavior like dividing by zero, where we'll see UB "from the other side."
Undefined behavior is also not the same as unspecified behavior, which is similar to implementation-defined behavior minus the requirement that the implementation document its choices and stick to them. Here we're focusing on undefined behavior, not unspecified behavior, so we'll lump unspecified behavior and implementation-defined behavior together.
Program behaviors fall into three buckets, not two:
Here's the list of guarantees compilers make about the outcomes of undefined behavior:
That's the whole list. No, I didn't forget any items. Yes, seriously.
It is possible to analyze how UB affects a specific program when compiled by a specific compiler or executed on a specific target platform. For example, there exist exotic compilers, operating systems, and hardware that offer additional guarantees (like CHERI, with awesome powers around pointer safety) relative to most common platforms, which only guarantee OS-level process isolation. We aren't talking about those in this post.
The mindset for this post is this: "If my program contains UB, and the compiler produced a binary that does X, is that a compiler bug?"
It's not a compiler bug.
1. Undefined behavior only "happens" at high optimization levels like -O2 or -O3.
2. If I turn off optimizations with a flag like -O0, then there's no UB.
3. If I include debug symbols in the build, there's no UB.
4. If I run the program under a debugger, there's no UB.
5. Okay there's still UB with all of these, but my code will "do the right thing" regardless.
6. It will either "do the right thing" or crash with a Segmentation Fault (SIGSEGV signal).
7. It will either "do the right thing" or crash somehow.
8. It will either "do the right thing" or crash or infinite-loop or deadlock.
9. At least it won't run some unrelated code from elsewhere in the program.
10. At least it won't run any unreachable code the program might contain.
11. If a line with UB previously "did the right thing," then it will continue to "do the right thing" the next time we run the program.
12. The UB line will at least continue to "do the right thing" while the program is still running.
13. It's possible to determine if a previous line was UB and prevent it from causing problems.
14. At least the impact of the UB is limited to code which uses values produced from the UB.
15. At least the impact of the UB is limited to code which is in the same compilation unit as the line with UB.
16. Okay, but at least the impact of the UB is limited to code which runs after the line with UB. UB is explicitly allowed to alter the behavior of other code, even including operations preceding it! "Alter" here encompasses corrupting, undoing, or altogether preventing (as if it never happened) the outcomes of that other code. To learn more and see examples of UB causing "time travel," check out this blog post. Thanks to these two Reddit posts for suggesting better wording for these items. For the original text, see the Errata section at the end of this post.
17. At least it won't corrupt the memory of the program.
18. At least it won't corrupt the memory of the program other than where the UB-affected data was located.
19. At least it won't corrupt the heap.
20. At least it won't corrupt the stack.
21. At least it won't corrupt the current stack frame. (My name for this is the "local variables are safely in registers" fallacy.)
22. At least it won't corrupt the stack pointer.
23. At least it won't corrupt the CPU flags register / any other CPU state.
24. At least it won't corrupt the executable memory of the program.
OS and hardware security features like W^X can make this unlikely, but self-modifying programs can be built so it's in principle possible through UB as well. Certainly, there's no guarantee that UB won't do this!
25. At least it won't corrupt streams like stdout or stderr.
26. At least it won't overwrite any files the program already had open.
27. At least it won't open new files and overwrite them.
28. At least it won't completely wipe the drive.
29. At least it won't damage or destroy any hardware components. Not all devices have the same level of self-protection against bad inputs written to their control registers. This is the kind of lesson one tends to learn the hard way.
30. At least it won't start playing Doom if the program didn't already have the Doom source code in it. I'd be quite impressed if you made a compiler that makes programs run Doom when they encounter UB. Consider it a challenge!
31. If a UB-containing program "worked fine" previously, recompiling the program without any code changes will still produce a binary that "works fine."
32. Recompiling without code changes and with the same compiler and flags will produce a binary that still "works fine."
33. Recompiling as above + on the same machine will produce a binary that still "works fine."
34. Recompiling as above + if you haven't rebooted the machine since the last compilation will produce a binary that still "works fine."
35. Recompiling as above + with the same environment variables will produce a binary that still "works fine."
36. Recompiling as above + at the same time of day and day of week as before, during a Lunar eclipse, having first sacrificed a fresh stick of RAM to the binary gods, will produce a binary that still "works fine."
37. Multiple runs of the program compiled as above and with the same inputs will produce the same behavior in each run.
38. Those multiple runs will produce the same behavior if the program, ignoring the UB, is deterministic.
39. But they will if the program is also single-threaded.
40. But they will if the program also doesn't read any external data (files, network, environment variables, etc.).
41. Using a debugger on a UB-containing program will show program state that corresponds to the source code. This is a corollary of falsehood #16, further explained in this post. UB can corrupt the behavior of the program both before and after the UB, so the source code you see in your editor no longer matches the actual executing program. Of course, you can still use the debugger to step through assembly instructions and view register state. But highly optimized assembly isn't easy to understand to begin with, and UB-induced weirdness will only make it harder. Overall, a situation that is best avoided. Contributed here.
42. Undefined behavior is purely a runtime phenomenon. In Rust, a counter-example is misusing #[no_mangle] to overwrite a symbol with an incorrect type. A C++ counter-example is violations of the One Definition Rule (ODR), some of which the compiler is not required to report before causing havoc.
43. Any kind of reasonable or unreasonable behavior happening with any consistency or any guarantee of any sort.
The moment your program contains UB, all bets are off. Even if it's just one little UB. Even if it's never executed. Even if you don't know it's there at all. Probably even if you wrote the language spec and compiler yourself (Speaking from experience. Hopefully not one you have to relive to believe.).
This is not to say that all outcomes in the list above are equally likely, or even plausible (especially the one about running Doom). But they are all allowed, valid, spec-compliant behavior.
It's perfectly possible that your program has UB, and it's been running fine for years without issues. That's great! I'm happy to hear it! I'm not even saying you need to go back and rewrite it to remove the UB. But as you make your decisions, it's good to know the full picture of what the compiler will or won't guarantee for your program.
Honorable mention for one special assumption
"If the program compiles without errors then it doesn't have UB."
This is 100% false in C and C++.
It's also false as stated in Rust, but with one tweak it's almost true. If your Rust program never uses unsafe, then it should be free of UB. In other words: causing UB without unsafe is considered a bug in the Rust compiler. These are rare and you are quite unlikely to run into them.
When Rust unsafe is used, then all bets are off just as in C or C++. But the assumption that "Safe Rust programs that compile are free of UB" is mostly true.
This is not an easy feat. We owe a debt of gratitude to the folks who cumulatively put engineer-centuries into making it so. It's Thanksgiving, and I thank you!
Thanks to arriven, Conrad Ludgate, sharnoff, Brian Graham, and a few folks who preferred to remain unnamed, for feedback on drafts of this post. Any mistakes are mine alone.
0