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