4 ms·
I've seen a real-world example something like this: int a[32] = {...}; int flag = 1 << index; if (index < ARRAYSIZE) { a[index] = x; retur
by 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 agoIt 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.
- vyodaiken 5y agoThere is zero customer demand for less reliable code as a tradeoff for "performance"
- pklausler 5y agoI 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.