5 ms·

Undefined Behavior deserves a better reputation (2021)

44 points by rramadass 4y ago

blueflow 4y ago
I thought Rust doesn't have a specification, just a reference? So all of it is undefined behavior?
- bruce343434 4y ago
  I'd say all Rust is implementation defined
- yccs27 4y ago
  "Undefined behavior" is a term of art[0], with the specific meaning as mentioned in the article: The compiler is allowed to assume that UB never happens, and change the compiled code based on that assumption. Not "no one has written down a definition" or anything else. As the sibling comment points out, a contrasting term is "implementation-defined". Confusing the two is a common misconception when learning C++: You might expect "overflow is undefined behavior" to mean that there is no prescribed result and every compiler might do it differently, but each will produce results in its own consistent way. But that would be implementation-defined behavior; instead by doing unchecked addition, you tell the compiler that you know the addition will never overflow, and don't care at all about the overflowing case. [0] aka. "improper noun", see https://news.ycombinator.com/item?id=32673100 https://news.ycombinator.com/item?id=32673100
  - yccs27 4y ago
    Followup to be precise: Undefined behavior in C++, of course, can have a definition set by the implementation. With the right switches, GCC will guarantee certain overflow behaviors. But a priori, the compiler is not bound by any guarantees.
- planede 4y ago
  IMO differentiating a specification and reference this way is just nitpicking. However it looks like that at least unsafe rust is underspecified regarding aliasing rules, therefore a bunch of unsafe rust is undefined behavior by definition. That is no authoritative text (whether reference or specification) defines the behavior of those programs. Key paragraph from the article: > Stacked Borrows is not part of the Rust spec, and is not the final word for aliasing-related UB in Rust. So there is still the chance that future revisions of this model can be made to better align with programmer intuition. The above code might get accepted because x2 is not actually being used to access memory. Or maybe &mut expr should only make such promises when used outside an unsafe block — but then, should adding unsafe really change the semantics of the program? As usual, language design is a game of trade-offs.
teddyh 4y ago
> This post is about defending and promoting UB as a concept, not UB in C/C++.
- zaphar 4y ago
  This is important. He is arguing specifically that when made explicit and opted into by the coder that UB can be useful. The issues that C and C++ have are that it's too easy for the developer to get opted in to UB by the compiler without knowing it.
  - megous 4y ago
    So you just remember the relevant UBs defined in the C standard: https://gist.github.com/Earnestly/7c903f481ff9d29a3dd1 https://gist.github.com/Earnestly/7c903f481ff9d29a3dd1 There are not that many UBs in the base language. And even fewer are relevant for day to day coding. Most of it is in the std library.
    - tialaramex 4y ago
      Well, it's countably many, but there are about 200 of them, so we're not even talking US states or US presidents, but more like UN member states. I remember Togo exists, but I can't point to it on a map, and if you left it off a map I wouldn't notice. So we're asking quite a lot to say people should just remember all of them and actually use this knowledge not just recite the list. And these aren't small things, they include very broad ideas, like 'object is referred to outside of its lifetime' and even just categories of deviations from the standard like 'A "shall" or "shall not" requirement that appears outside of a constraint is violated' It's impressive that they enumerated them, A+ gold stars. As I understand it WG21 (C++) is still attempting to produce a list of the Undefined Behaviours in their language - but I don't think "memorize all these vague ideas and use that knowledge when programming" is practical.
      - megous 4y ago
        Huge number of them are obscure or in the standard library. A C programmer with some experience can go through a list and ignore the C library ones, cross out the weird ones that he'd never hit anyway because he'd not even think of writing code that way, and end up with some useful compressed list of maybe 30 for day to day use that really need to be observed because they normally appear in regular code. As for the standard library, that is often irrelevant, depending on what kind of code you're writing. Bootloader or Linux kernel, some other microcontroller code? Probably not relevant. GNOME C app? Not very relevant either, because it's all wrapped by glib, etc. And even when it's relevant, docs are very quickly searchable (by function name) and pitfalls are documented there.
DougBTX 4y ago
FWIW, the original link in the article shows that the panic_bounds_check check is present in optimised code in Rust 1.55, but if you update to a more recent Rust, say 1.60, then it is optimised away as expected: example::mid: test rsi, rsi je .LBB0_1 and rsi, -2 mov edx, dword ptr [rdi + 2*rsi] mov eax, 1 ret .LBB0_1: xor eax, eax ret https://rust.godbolt.org/z/Wz4Prjed4 https://rust.godbolt.org/z/Wz4Prjed4
- tialaramex 4y ago
  Interesting, do you know how this is achieved? Is there a Rust optimization that notices logically this type of construction is always in-bounds and so the bounds check is never emitted, or is the LLVM bounds check smarter now and realises hey, my parameter is never out of bounds, so no need to emit code here ?
raphlinus 4y ago
The main distinction I'd draw is whether you'd doing formal or informal reasoning. In the formal reasoning world, undefined behavior is mostly a good thing. On one side of the contract, it's a set of proof obligations for the code, and not especially onerous in the grand scheme of things - correct programs won't do UB. On the other side, it's a clear statement of what the compiler is and is not allowed to optimize. The more UB, the more opportunities to optimize. When you're doing informal reasoning, the calculus changes. There's all kinds of stuff that can go wrong that is not motivated by what the machine is actually doing. In fact, it's something of a nightmare. Doing a memcpy of a struct that has padding in it? What are the exact semantics of restrict? And threading. Benign data races used to be a thing, but in an undefined behavior world, it's game over. C makes things worse than they need to be with its wonky integer rules (left shift of a negative integer and wrapping multiplication of two unsigned shorts are both UB), but a lot of that is potentially fixable and those mistakes won't be repeated in new languages. In the context of Rust, more undefined behavior makes sense, and Ralf's work takes us much closer to a solid spec. But when you're doing mostly informal reasoning, I can see why people are so emotionally against it, and decisions such as turning off strict aliasing might be justified.
- jcranmer 4y ago
  While I do sympathize with some of the user complaints with UB, and the issues with things like signed integer overflow and strict aliasing seem entirely gratuitous, I think most users complaining about UB fail to comprehend that the issue with UB is that it's often really hard to constrain just what can possibly go wrong--and that's even without compiler optimizations kicking into play. It should be pretty clear that memory unsafety produces all sorts of crazy havoc--a write to errant memory could overwrite stack return locations and then basically do whatever it wants given the power of ROP gadgets. At first glance, it looks like uninitialized memory is "merely" an issue of reading more or less random data, but there are cases (e.g., MADV_FREE) where it turns out that the value of uninitialized memory can change underneath you. Traps cause lots of program state to become rather indeterminate, simply because of what may or may not live in a register or in memory, but on some architectures (e.g., Alpha), code may keep running for a while after an instruction traps, to the point that you're no longer even in the same function. Sanely describing what happens in data races are beyond the ken of formal semanticists (see the still-unsettled discussions over the semantics of relaxed atomics); what hope do programmers have of reasoning about these memory semantics? It also doesn't help that the distinction between undefined, unspecified, and implementation-defined behavior is poorly grasped by a large segment of the community.
somat 4y ago
"all it does is perform optimizations that are correct under the extra assumption that there is no Undefined Behavior." How did the compiler writers reach the point where they were able to read "undefined behavior" as "does not happen" rather than "specification left this undefined so that the compiler can define it" I don't think there is anything wrong with undefined behavior, I do however expect the compiler documentationto have an extensive section on stuff undefined by the specification. for example: when a signed integer would exceeds the maximum value this compiler just lets it go and it does whatever the underlying hardware would do. on amd64 this will overflow to a negative value.
- mort96 4y ago
  The specification has a separate concept for "specification left this undefined so that the compiler can define it": implementation-defined behaviour.
- jcranmer 4y ago
  There's a note in the C99 rationale explaining how compilers can use undefined behavior (specifically, with regards to signed overflow) to perform certain optimizations (specifically, reassociation of integer addition). I'd go back to C89, but the documents before the work effort to make C99 are not available on the WG14 website. > I do however expect the compiler documentation to have an extensive section on stuff undefined by the specification. There is an entire section of the C specification that lists every single undefined behavior. What more do you want?
  - kps 4y ago
    https://www.lysator.liu.se/c/rat/title.html https://www.lysator.liu.se/c/rat/title.html has the C89 Rationale. “The terms unspecified behavior, undefined behavior, and implementation-defined behavior are used to categorize the result of writing programs whose properties the Standard does not, or cannot, completely describe. […] Undefined behavior gives the implementor license not to catch certain program errors that are difficult to diagnose.”
    - 4y ago
overgard 4y ago
Here's my issue with UB in C/C++ (and I think it agrees with the article): I would much rather have direct compiler directives over the compiler being clever in a quiet way. The first example in this article is very good -- get_unchecked avoids undefined behavior (well, outside of accessing out of bounds), but still provides the wanted optimization. If something goes bad in your program, one of the first things you're going to suspect is functions with _unchecked at the end of them, so the developer ergonomics are great. My main problem with undefined behavior is that it's rare to know when it's happening. I would much rather give hints to the compiler than having it "prove" something very subtle underneath the hood using UB, because then I understand where those things are happening. And it's not even like it's a rare thing! My C++ is littered with "const" and "[[nodiscard]]" and #pragma pack and all sorts of other things that don't change the behavior of the program but do indicate something important to the compiler. I want more of that, and less subtlety.
kazinator 4y ago
> I have presented Undefined Behavior as a tool that enables the programmer to write code that the compiler cannot check for correctness, and argued that — used responsibly — it is a useful component in a language designer's toolbox. That is simply wrong. Code that the compiler cannot or does not check for correctness isn't "undefined behavior". Traditionally that is called "unsafe code": the programmer ensures safety through analyzing all the cases that may occur and making sure they have reliable consequences. (The article talks about Rust a lot; maybe undefined and unsafe are the same thing in Rust?) Undefined behavior with ill consequence may co-occur with safety. A case of undefined behavior may be flagged by the compiler by a diagnostic "undefined behavior in line 42". Thus, safety was ensured; the situation was diagnosed. Yet, an executable program could be produced anyway, and if that is run, it may mishbehave due to that undefined behavior in line 42. This is the case in C, when you assign incompatible types, and use a compiler like GCC which only warns about that, by default, and translates anyway. Some undefined behavior leads to a documented extension, which makes it defined for the given implementation, and safe (if used as documented). If you try to perform arithmetic on a void * pointer, that is not an ISO C feature; it requires a diagnostic. GCC allows void * pointer arithmetic; it behaves like byte addressing. Programs which use this feature are invoking undefined behavior: they are violating an ISO C constraint rule, yet being executed anyway. Furthermore, if the diagnostic isn't issued, then GCC is being a non-conforming implementation; it's a non-conforming extension.
imtringued 4y ago
The only way to avoid C undefined behaviour is to not use C. Stop using C.

44 points by rramadass 4y ago

blueflow 4y ago

I thought Rust doesn't have a specification, just a reference? So all of it is undefined behavior?

bruce343434 4y ago
I'd say all Rust is implementation defined
yccs27 4y ago
"Undefined behavior" is a term of art[0], with the specific meaning as mentioned in the article: The compiler is allowed to assume that UB never happens, and change the compiled code based on that assumption. Not "no one has written down a definition" or anything else. As the sibling comment points out, a contrasting term is "implementation-defined". Confusing the two is a common misconception when learning C++: You might expect "overflow is undefined behavior" to mean that there is no prescribed result and every compiler might do it differently, but each will produce results in its own consistent way. But that would be implementation-defined behavior; instead by doing unchecked addition, you tell the compiler that you know the addition will never overflow, and don't care at all about the overflowing case. [0] aka. "improper noun", see https://news.ycombinator.com/item?id=32673100 https://news.ycombinator.com/item?id=32673100
- yccs27 4y ago
  Followup to be precise: Undefined behavior in C++, of course, can have a definition set by the implementation. With the right switches, GCC will guarantee certain overflow behaviors. But a priori, the compiler is not bound by any guarantees.
planede 4y ago
IMO differentiating a specification and reference this way is just nitpicking. However it looks like that at least unsafe rust is underspecified regarding aliasing rules, therefore a bunch of unsafe rust is undefined behavior by definition. That is no authoritative text (whether reference or specification) defines the behavior of those programs. Key paragraph from the article: > Stacked Borrows is not part of the Rust spec, and is not the final word for aliasing-related UB in Rust. So there is still the chance that future revisions of this model can be made to better align with programmer intuition. The above code might get accepted because x2 is not actually being used to access memory. Or maybe &mut expr should only make such promises when used outside an unsafe block — but then, should adding unsafe really change the semantics of the program? As usual, language design is a game of trade-offs.

teddyh 4y ago

> This post is about defending and promoting UB as a concept, not UB in C/C++.

zaphar 4y ago
This is important. He is arguing specifically that when made explicit and opted into by the coder that UB can be useful. The issues that C and C++ have are that it's too easy for the developer to get opted in to UB by the compiler without knowing it.
- megous 4y ago
  So you just remember the relevant UBs defined in the C standard: https://gist.github.com/Earnestly/7c903f481ff9d29a3dd1 https://gist.github.com/Earnestly/7c903f481ff9d29a3dd1 There are not that many UBs in the base language. And even fewer are relevant for day to day coding. Most of it is in the std library.
  - tialaramex 4y ago
    Well, it's countably many, but there are about 200 of them, so we're not even talking US states or US presidents, but more like UN member states. I remember Togo exists, but I can't point to it on a map, and if you left it off a map I wouldn't notice. So we're asking quite a lot to say people should just remember all of them and actually use this knowledge not just recite the list. And these aren't small things, they include very broad ideas, like 'object is referred to outside of its lifetime' and even just categories of deviations from the standard like 'A "shall" or "shall not" requirement that appears outside of a constraint is violated' It's impressive that they enumerated them, A+ gold stars. As I understand it WG21 (C++) is still attempting to produce a list of the Undefined Behaviours in their language - but I don't think "memorize all these vague ideas and use that knowledge when programming" is practical.
    - megous 4y ago
      Huge number of them are obscure or in the standard library. A C programmer with some experience can go through a list and ignore the C library ones, cross out the weird ones that he'd never hit anyway because he'd not even think of writing code that way, and end up with some useful compressed list of maybe 30 for day to day use that really need to be observed because they normally appear in regular code. As for the standard library, that is often irrelevant, depending on what kind of code you're writing. Bootloader or Linux kernel, some other microcontroller code? Probably not relevant. GNOME C app? Not very relevant either, because it's all wrapped by glib, etc. And even when it's relevant, docs are very quickly searchable (by function name) and pitfalls are documented there.

DougBTX 4y ago

FWIW, the original link in the article shows that the panic_bounds_check check is present in optimised code in Rust 1.55, but if you update to a more recent Rust, say 1.60, then it is optimised away as expected: example::mid: test rsi, rsi je .LBB0_1 and rsi, -2 mov edx, dword ptr [rdi + 2*rsi] mov eax, 1 ret .LBB0_1: xor eax, eax ret https://rust.godbolt.org/z/Wz4Prjed4 https://rust.godbolt.org/z/Wz4Prjed4

tialaramex 4y ago
Interesting, do you know how this is achieved? Is there a Rust optimization that notices logically this type of construction is always in-bounds and so the bounds check is never emitted, or is the LLVM bounds check smarter now and realises hey, my parameter is never out of bounds, so no need to emit code here ?

raphlinus 4y ago

The main distinction I'd draw is whether you'd doing formal or informal reasoning. In the formal reasoning world, undefined behavior is mostly a good thing. On one side of the contract, it's a set of proof obligations for the code, and not especially onerous in the grand scheme of things - correct programs won't do UB. On the other side, it's a clear statement of what the compiler is and is not allowed to optimize. The more UB, the more opportunities to optimize. When you're doing informal reasoning, the calculus changes. There's all kinds of stuff that can go wrong that is not motivated by what the machine is actually doing. In fact, it's something of a nightmare. Doing a memcpy of a struct that has padding in it? What are the exact semantics of restrict? And threading. Benign data races used to be a thing, but in an undefined behavior world, it's game over. C makes things worse than they need to be with its wonky integer rules (left shift of a negative integer and wrapping multiplication of two unsigned shorts are both UB), but a lot of that is potentially fixable and those mistakes won't be repeated in new languages. In the context of Rust, more undefined behavior makes sense, and Ralf's work takes us much closer to a solid spec. But when you're doing mostly informal reasoning, I can see why people are so emotionally against it, and decisions such as turning off strict aliasing might be justified.

jcranmer 4y ago
While I do sympathize with some of the user complaints with UB, and the issues with things like signed integer overflow and strict aliasing seem entirely gratuitous, I think most users complaining about UB fail to comprehend that the issue with UB is that it's often really hard to constrain just what can possibly go wrong--and that's even without compiler optimizations kicking into play. It should be pretty clear that memory unsafety produces all sorts of crazy havoc--a write to errant memory could overwrite stack return locations and then basically do whatever it wants given the power of ROP gadgets. At first glance, it looks like uninitialized memory is "merely" an issue of reading more or less random data, but there are cases (e.g., MADV_FREE) where it turns out that the value of uninitialized memory can change underneath you. Traps cause lots of program state to become rather indeterminate, simply because of what may or may not live in a register or in memory, but on some architectures (e.g., Alpha), code may keep running for a while after an instruction traps, to the point that you're no longer even in the same function. Sanely describing what happens in data races are beyond the ken of formal semanticists (see the still-unsettled discussions over the semantics of relaxed atomics); what hope do programmers have of reasoning about these memory semantics? It also doesn't help that the distinction between undefined, unspecified, and implementation-defined behavior is poorly grasped by a large segment of the community.

somat 4y ago

"all it does is perform optimizations that are correct under the extra assumption that there is no Undefined Behavior." How did the compiler writers reach the point where they were able to read "undefined behavior" as "does not happen" rather than "specification left this undefined so that the compiler can define it" I don't think there is anything wrong with undefined behavior, I do however expect the compiler documentationto have an extensive section on stuff undefined by the specification. for example: when a signed integer would exceeds the maximum value this compiler just lets it go and it does whatever the underlying hardware would do. on amd64 this will overflow to a negative value.

mort96 4y ago
The specification has a separate concept for "specification left this undefined so that the compiler can define it": implementation-defined behaviour.
jcranmer 4y ago
There's a note in the C99 rationale explaining how compilers can use undefined behavior (specifically, with regards to signed overflow) to perform certain optimizations (specifically, reassociation of integer addition). I'd go back to C89, but the documents before the work effort to make C99 are not available on the WG14 website. > I do however expect the compiler documentation to have an extensive section on stuff undefined by the specification. There is an entire section of the C specification that lists every single undefined behavior. What more do you want?
- kps 4y ago
  https://www.lysator.liu.se/c/rat/title.html https://www.lysator.liu.se/c/rat/title.html has the C89 Rationale. “The terms unspecified behavior, undefined behavior, and implementation-defined behavior are used to categorize the result of writing programs whose properties the Standard does not, or cannot, completely describe. […] Undefined behavior gives the implementor license not to catch certain program errors that are difficult to diagnose.”
  - 4y ago

overgard 4y ago

Here's my issue with UB in C/C++ (and I think it agrees with the article): I would much rather have direct compiler directives over the compiler being clever in a quiet way. The first example in this article is very good -- get_unchecked avoids undefined behavior (well, outside of accessing out of bounds), but still provides the wanted optimization. If something goes bad in your program, one of the first things you're going to suspect is functions with _unchecked at the end of them, so the developer ergonomics are great. My main problem with undefined behavior is that it's rare to know when it's happening. I would much rather give hints to the compiler than having it "prove" something very subtle underneath the hood using UB, because then I understand where those things are happening. And it's not even like it's a rare thing! My C++ is littered with "const" and "[[nodiscard]]" and #pragma pack and all sorts of other things that don't change the behavior of the program but do indicate something important to the compiler. I want more of that, and less subtlety.

kazinator 4y ago

> I have presented Undefined Behavior as a tool that enables the programmer to write code that the compiler cannot check for correctness, and argued that — used responsibly — it is a useful component in a language designer's toolbox. That is simply wrong. Code that the compiler cannot or does not check for correctness isn't "undefined behavior". Traditionally that is called "unsafe code": the programmer ensures safety through analyzing all the cases that may occur and making sure they have reliable consequences. (The article talks about Rust a lot; maybe undefined and unsafe are the same thing in Rust?) Undefined behavior with ill consequence may co-occur with safety. A case of undefined behavior may be flagged by the compiler by a diagnostic "undefined behavior in line 42". Thus, safety was ensured; the situation was diagnosed. Yet, an executable program could be produced anyway, and if that is run, it may mishbehave due to that undefined behavior in line 42. This is the case in C, when you assign incompatible types, and use a compiler like GCC which only warns about that, by default, and translates anyway. Some undefined behavior leads to a documented extension, which makes it defined for the given implementation, and safe (if used as documented). If you try to perform arithmetic on a void * pointer, that is not an ISO C feature; it requires a diagnostic. GCC allows void * pointer arithmetic; it behaves like byte addressing. Programs which use this feature are invoking undefined behavior: they are violating an ISO C constraint rule, yet being executed anyway. Furthermore, if the diagnostic isn't issued, then GCC is being a non-conforming implementation; it's a non-conforming extension.

imtringued 4y ago

The only way to avoid C undefined behaviour is to not use C. Stop using C.