4 ms·

> license for the kinds of dramatic and unintuitive transformations we’ve seen from the compilers, and any indication that undefined behavior should be a vehic

by jart 5y ago

> license for the kinds of dramatic and unintuitive transformations we’ve seen from the compilers, and any indication that undefined behavior should be a vehicle for permitting optimizations. Does anyone have an example of a time where Clang or GCC actually did something bad upon witnessing undefined behavior, rather than simply doing nothing, as the standard proposes? I ask because every time I've seen people get mad about UB it's always because they envisioned that the compiler would do something, but instead the compiler did nothing.

SloopJon 5y ago
The types of surprises that I've seen have to do with inferences that the compiler draws: this program would be undefined if foo was negative, therefore foo is not negative, therefore I can optimize away this condition.
anarazel 5y ago
What do you define as "bad"? Arguably several. I've seen cases of overflow checks that were implemented assuming signed overflow (which all relevant platforms implement!) getting optimized away. Correct, given "signed overflow is UB" and thus can be assumed to not happen. Problematic given for widespread such checks are, and given that there's no easy portable alternative. Entire checks getting optimized away because of a presumed strict aliasing violation. IIRC between structure with a compatible layout. Pretty code, no. UB yes. Reasonable, IDK.
bhk 5y ago
I've seen a real-world example something like this: int a[32] = {...}; int flag = 1 << index; if (index < ARRAYSIZE) { a[index] = x; return flag; } else { return 0; } The "1 << index" operation is undefined behavior (!) when index is greater than 32 (on a platform with 32-bit integers), even if the result is never used! The compiler inferred that index must always be less than 32, which allowed it to optimize out the array bounds check, which turns the code into a write-anywhere gadget. Note that if the standard had not declared "n << 32" to be all-bets-are-off UB, but instead had said something like, "it results in some implementation-specific value, or maybe traps" -- as a rational person would presume -- then this would not turn into a security problem.
- msbarnett 5y ago
  > Note that if the standard had not declared "n << 32" to be all-bets-are-off UB, but instead had said something like, "it results in some implementation-specific value, or maybe traps" -- as a rational person would presume -- then this would not turn into a security problem. But also note that a lot of existing code doing bitshift-and-index inside a hot loop that never went out of bounds would now get slower if it started having to run bounds checks it had previously elided in an optimization pass. Let's not pretend that "it results in some implementation-specific value, or maybe traps" is a clear win with no downsides that Standards Authors and Compiler Engineers are ignoring out of some kind of malice – there are very real performance tradeoffs here, and a new version of the standard that makes a lot of existing real-world code slower isn't going to be a popular one with many people.
  - bhk 5y ago
    It isn't clear to me precisely what example you have in mind. If you are saying that deleting array bounds checks might have performance benefits that outweigh the security concerns, then I disagree. If you are saying that the compiler would have to insert bounds checks, I don't see how you arrive at that. I have seen claims that gratuitous UB is important for enabling meaningful optimizations, but in every such case the examples did not hold up to scrutiny. In the end, the same optimization remains possible without the gratuitous UB, although it might involve a little more work on the part of the compiler engineer. Regarding "malice": "Never attribute to malice..."
    - msbarnett 5y ago
      > If you are saying that deleting array bounds checks might have performance benefits that outweigh the security concerns, then I disagree. I'm saying that there is existing code in this world in which some variation on /* insanely hot loop where ARRAYSIZE > 32 */ while(true) { ... int x = 1 << index; if (index < ARRAYSIZE) { a[index] = x; } else { a[index] = 0; } ... } exists that's currently compiling down to just "a[index] = 1 << index", with everything working fine. I'm saying that the authors and their customers are unlikely to be excited when your new compiler release stops assuming that index is < 32 (which it always was in practice) and their program gets slower because there's now extra tests in this part of the hot loop, which is also consuming more icache, evicting other important bits of the loop. "There's some work-around to win that performance back, given enough effort by the compiler author to give you some means to tell it what it had previously assumed" isn't likely to sell people on your patch, particularly if they'd have to make many such annotations. "They could just remove the tests if they know that index < 32" in this synthetic example, yes, but there are cases when this is less obvious but nonetheless true. And compiler updates that force you to go delete working code, work out un-obvious deductions the compiler had previously made, and re-validate just to regain the status quo still aren't going to make anybody happy. The point, broadly: People care a lot about performance. These UB discussions in which people blithely assert that compilers "should" do XYZ conservative assumption while eliding any mention of the real-world performance impact the changes they want would have on existing code are, frankly, masturbatory. Compiler engineers have to care when PostgreSQL and a dozen other critical programs get 4x slower because they stopped assuming that "1 << index" wouldn't happen with index > 32, or that loop bounds won't overflow. Like all software engineering, decision making here has to be driven by balancing tradeoffs, not by insisting that one treatment of the spec is obviously "the best approach" while ignoring any inconvenient consequences that change would have vs the status quo.
steveklabnik 5y ago
A fun historical example: https://feross.org/gcc-ownage/ https://feross.org/gcc-ownage/ But yes, generally, UB manifests as "the compiler is allowed to assume this doesn't happen" and the bad stuff is a consequence of doing things following those assumptions, not the compiler going "oops well lol UB time to screw with this person."
Jiro 5y ago
This may not necessarily count as an example in the wild, but the 2013 Underhanded C contest at http://www.underhanded-c.org/_page_id_25.html http://www.underhanded-c.org/_page_id_25.html includes this example: h = abs(h) % HASHSIZE; // Extra sanity check if (h < 0 || h >= HASHSIZE) h = 0; return h; where h=INT_MIN causes the h to become negative and the sanity check is optimized out because abs(INT_MIN) is UB.
- jart 5y ago
  That's such a good example for teaching purposes, because it manages to combine the lack of understanding surrounding the remainder operator (i.e. unlike python % in c is not modulus) with the lack of understanding surrounding 0x80000000 (two's complement bane) into a single example. However it still makes my point that in this circumstance, the compiler's strategy still is to do nothing, because it can prove that the check could only be true under undefined behavior circumstances, so doing nothing means not compiling the check. I'm fine with that. Would anyone prefer that the compiler's internal definition of logic assume that absolute values can be negative? Must we throw out centuries of math because we've optimized integers to be 32-bits? The only thing that's problematic is we need better tools to bring logic assumptions to our attention. Currently, UBSAN can only warn us about that when two's bane actually gets passed to the function at runtime. So the only way to spot faulty logic we failed to consider is to both enable UBSAN and be super methodical about unit testing. Well, another thing I like to do is just read the assembly output. Constantly. Whenever I write something like a parser I've got a keyboard mapping that shows me the assembly output in Emacs with UBSAN enabled. If I turn off the noisy ones like pointer overflow then I can avoid these issues altogether by writing my code so that no UBSAN assembly gets generated. Since the compiler won't show that as a warning. You literally have to read the -S assembly output to get the compiler warnings that are actually meaningful.
- nyanpasu64 5y ago
  I wish there was an abs() function that returned the unsigned version of the signed input type and wasn't UB if you passed in the most negative value of the signed type. Sadly neither C or C++ nor Rust's standard libraries have a built-in implementation of this, and sending the most negative integer into Rust's .abs() will panic in debug mode (is not intended to be used in properly implemented code).
ben0x539 5y ago
Sounds like you're interested specifically in https://blog.tchatzigiannakis.com/undefined-behavior-can-literally-erase-your-hard-disk/ https://blog.tchatzigiannakis.com/undefined-behavior-can-lit...

by jart 5y ago

SloopJon 5y ago

The types of surprises that I've seen have to do with inferences that the compiler draws: this program would be undefined if foo was negative, therefore foo is not negative, therefore I can optimize away this condition.

anarazel 5y ago

What do you define as "bad"? Arguably several. I've seen cases of overflow checks that were implemented assuming signed overflow (which all relevant platforms implement!) getting optimized away. Correct, given "signed overflow is UB" and thus can be assumed to not happen. Problematic given for widespread such checks are, and given that there's no easy portable alternative. Entire checks getting optimized away because of a presumed strict aliasing violation. IIRC between structure with a compatible layout. Pretty code, no. UB yes. Reasonable, IDK.

bhk 5y ago

I've seen a real-world example something like this: int a[32] = {...}; int flag = 1 << index; if (index < ARRAYSIZE) { a[index] = x; return flag; } else { return 0; } The "1 << index" operation is undefined behavior (!) when index is greater than 32 (on a platform with 32-bit integers), even if the result is never used! The compiler inferred that index must always be less than 32, which allowed it to optimize out the array bounds check, which turns the code into a write-anywhere gadget. Note that if the standard had not declared "n << 32" to be all-bets-are-off UB, but instead had said something like, "it results in some implementation-specific value, or maybe traps" -- as a rational person would presume -- then this would not turn into a security problem.

msbarnett 5y ago
> Note that if the standard had not declared "n << 32" to be all-bets-are-off UB, but instead had said something like, "it results in some implementation-specific value, or maybe traps" -- as a rational person would presume -- then this would not turn into a security problem. But also note that a lot of existing code doing bitshift-and-index inside a hot loop that never went out of bounds would now get slower if it started having to run bounds checks it had previously elided in an optimization pass. Let's not pretend that "it results in some implementation-specific value, or maybe traps" is a clear win with no downsides that Standards Authors and Compiler Engineers are ignoring out of some kind of malice – there are very real performance tradeoffs here, and a new version of the standard that makes a lot of existing real-world code slower isn't going to be a popular one with many people.
- bhk 5y ago
  It isn't clear to me precisely what example you have in mind. If you are saying that deleting array bounds checks might have performance benefits that outweigh the security concerns, then I disagree. If you are saying that the compiler would have to insert bounds checks, I don't see how you arrive at that. I have seen claims that gratuitous UB is important for enabling meaningful optimizations, but in every such case the examples did not hold up to scrutiny. In the end, the same optimization remains possible without the gratuitous UB, although it might involve a little more work on the part of the compiler engineer. Regarding "malice": "Never attribute to malice..."
  - msbarnett 5y ago
    > If you are saying that deleting array bounds checks might have performance benefits that outweigh the security concerns, then I disagree. I'm saying that there is existing code in this world in which some variation on /* insanely hot loop where ARRAYSIZE > 32 */ while(true) { ... int x = 1 << index; if (index < ARRAYSIZE) { a[index] = x; } else { a[index] = 0; } ... } exists that's currently compiling down to just "a[index] = 1 << index", with everything working fine. I'm saying that the authors and their customers are unlikely to be excited when your new compiler release stops assuming that index is < 32 (which it always was in practice) and their program gets slower because there's now extra tests in this part of the hot loop, which is also consuming more icache, evicting other important bits of the loop. "There's some work-around to win that performance back, given enough effort by the compiler author to give you some means to tell it what it had previously assumed" isn't likely to sell people on your patch, particularly if they'd have to make many such annotations. "They could just remove the tests if they know that index < 32" in this synthetic example, yes, but there are cases when this is less obvious but nonetheless true. And compiler updates that force you to go delete working code, work out un-obvious deductions the compiler had previously made, and re-validate just to regain the status quo still aren't going to make anybody happy. The point, broadly: People care a lot about performance. These UB discussions in which people blithely assert that compilers "should" do XYZ conservative assumption while eliding any mention of the real-world performance impact the changes they want would have on existing code are, frankly, masturbatory. Compiler engineers have to care when PostgreSQL and a dozen other critical programs get 4x slower because they stopped assuming that "1 << index" wouldn't happen with index > 32, or that loop bounds won't overflow. Like all software engineering, decision making here has to be driven by balancing tradeoffs, not by insisting that one treatment of the spec is obviously "the best approach" while ignoring any inconvenient consequences that change would have vs the status quo.

steveklabnik 5y ago

A fun historical example: https://feross.org/gcc-ownage/ https://feross.org/gcc-ownage/ But yes, generally, UB manifests as "the compiler is allowed to assume this doesn't happen" and the bad stuff is a consequence of doing things following those assumptions, not the compiler going "oops well lol UB time to screw with this person."

Jiro 5y ago

This may not necessarily count as an example in the wild, but the 2013 Underhanded C contest at http://www.underhanded-c.org/_page_id_25.html http://www.underhanded-c.org/_page_id_25.html includes this example: h = abs(h) % HASHSIZE; // Extra sanity check if (h < 0 || h >= HASHSIZE) h = 0; return h; where h=INT_MIN causes the h to become negative and the sanity check is optimized out because abs(INT_MIN) is UB.

jart 5y ago
That's such a good example for teaching purposes, because it manages to combine the lack of understanding surrounding the remainder operator (i.e. unlike python % in c is not modulus) with the lack of understanding surrounding 0x80000000 (two's complement bane) into a single example. However it still makes my point that in this circumstance, the compiler's strategy still is to do nothing, because it can prove that the check could only be true under undefined behavior circumstances, so doing nothing means not compiling the check. I'm fine with that. Would anyone prefer that the compiler's internal definition of logic assume that absolute values can be negative? Must we throw out centuries of math because we've optimized integers to be 32-bits? The only thing that's problematic is we need better tools to bring logic assumptions to our attention. Currently, UBSAN can only warn us about that when two's bane actually gets passed to the function at runtime. So the only way to spot faulty logic we failed to consider is to both enable UBSAN and be super methodical about unit testing. Well, another thing I like to do is just read the assembly output. Constantly. Whenever I write something like a parser I've got a keyboard mapping that shows me the assembly output in Emacs with UBSAN enabled. If I turn off the noisy ones like pointer overflow then I can avoid these issues altogether by writing my code so that no UBSAN assembly gets generated. Since the compiler won't show that as a warning. You literally have to read the -S assembly output to get the compiler warnings that are actually meaningful.
nyanpasu64 5y ago
I wish there was an abs() function that returned the unsigned version of the signed input type and wasn't UB if you passed in the most negative value of the signed type. Sadly neither C or C++ nor Rust's standard libraries have a built-in implementation of this, and sending the most negative integer into Rust's .abs() will panic in debug mode (is not intended to be used in properly implemented code).

ben0x539 5y ago

Sounds like you're interested specifically in https://blog.tchatzigiannakis.com/undefined-behavior-can-literally-erase-your-hard-disk/ https://blog.tchatzigiannakis.com/undefined-behavior-can-lit...