Hacker News Reader

Comment by jart | Hacker News Reader

> 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.

View on HN

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 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.

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.

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).

A fun historical example: 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."

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.

> 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.

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..."

There are a half-dozen examples on this very thread and in linked bug reports, with detailed explanations by professional compiler writers.

If you think they don’t hold up to scrutiny, then you should get to work implementing these things, because you are likely a better compiler writer than most others in the world, including Christian Lattner of llvm fame, who provides many examples here.

https://blog.llvm.org/2011/05/what-every-c-programmer-should...

> 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.

(I'll assume int is 32 bits, the hardware generates zero on shl overflow, and we don't care if a[31] is negative, since "everything working fine" wouldn't be true otherwise.)

The compiler is perfectly capable of seeing 1<<index and reasoning: if index >= 32, then x is 0 (on this hardware), so the two branches of the conditional are the same, and we can just use the first one. On the other hand, if index < 32, then index < ARRAYSIZE (transitive property), the conditional always picks the first branch, and we can just use that one. By exhaustivity, we can just use the first branch: `int x = 1<<index; a[index] = x;`. Further optimization produces `a[index] = 1 << index`.

Note that that did not make any reference to undefined behaviour.

There is zero customer demand for less reliable code as a tradeoff for "performance"

Certainly not when C was designed, and arguably not in some cases today as well.

For some reason I couldn't 'Reply' to compiler-guy's reply directly, so I'll try here.

I'm familiar with the Chris Lattner article. Most of it (especially the second installment) shows bad outcomes from UB optimization. When it comes to signed integer overflow UB, I see two examples where performance is cited as a motivation.

One mentions unrolling, and gives an example similar to one elsewhere in this thread: https://news.ycombinator.com/item?id=27223870 In my reply to that I explain how unrolling is not actually enabled by UB.

The other instance of integer overflow UB in the Lattner article is optimizing X*2/2 to X. That's perhaps a stronger case, but I haven't seen any numbers on the real-world implications of this particular optimization.

> For some reason I couldn't 'Reply' to compiler-guy's reply directly, so I'll try here.

Hacker News has a timeout where if you try to reply to someone too quickly, it will hide the reply button. This timeout increases the deeper the comment tree gets.

I think the compiler that you were using is broken. One can't infer "index < 32" unless on a code path to a use of "flag", and that inference can't override the predicates that dominate that use.

No, the initializer already counts as a use of the undefined expression.

You're right. Thanks!

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.

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.

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

Reply on news.ycombinator.com