5 ms·

Undefined behaviour is a tool to generate faster code, by shifting some burden of correctness to the programmer. For example, accessing past the array size is u

Undefined behaviour is a tool to generate faster code, by shifting some burden of correctness to the programmer. For example, accessing past the array size is undefined behaviour. This lets the compiler skip the bounds check, an expensive check+branch on each array access. The trade-off is that now the programmer has to ensure correctness manually (or use an alternative interface that wraps a bounds check) else bad (TM) things will happen.

AaronFriel 7y ago
Despite this, tools will often not warn of undefined behavior or these premature optimizations. Quite the opposite, the compilers are almost user hostile for trying to ensure safety and correctness. I cannot see into the minds of the GCC and LLVM teams responsible for the C frontends, but to the extent that you'd think the compiler should do anything here, they seem to think it's largely not their job to improve safety or correctness. That's the job of static analysis tools (which can cost a lot of money), runtime analysis tools (which can cost a lot of time in writing tests that exercise all code paths), and fuzzers (yet more time). Punting all of this extremely important reasoning to "the programmer" is ridiculous when it's been proven over and over again that even incredibly smart C programmers get this wrong.
- saagarjha 7y ago
  Compilers could certainly do a better job when performing optimizations that “abuse” undefined behavior, but in general this isn’t a trivial problem. The way optimization passes are set up can often make it difficult to generate warnings that have a low false-positive rate.
  - AaronFriel 7y ago
    Do you think it might be a problem that undefined behavior optimizations and/or pattern matches are so prolific in C that reducing the "false-positive rate" of ... actually bad undefined behavior (?) would be the hard thing? Why not disallow undefined behavior and instead have the compiler emit: "Hey, this branch is never taken, if you want us not to compile it remove the dead code". Seems like that's exactly the same sort of putting the onus on the programmer that andrepd mentioned, but without the side effect of millions of device drivers are zero day remote code execution vulnerabilities waiting to happen?
    - cyphar 7y ago
      The array access example shows why this isn't generally possible -- the programmer hasn't written any bounds-checking code or assertions (they just wrote x[y]). Should the compiler emit bounds-checks? If yes, your code is now slower but there isn't an easy way to disable this "feature" (if x is heap-allocated or passed as a pointers, how will the compiler know what kind of bounds check is sufficient?). If no, you have undefined behaviour and crashes. Even Rust made a mistake with restricting undefined behaviour -- they accidentally allowed creating references to fields in packed structures (resulting in possibly unaligned references which is undefined behaviour in Rust) in safe code. These days you get a warning telling you to use unsafe or copy the value, but they have yet to make it an error. For comparison, C also gives you a warning for the same problem (or an error with -Werror). I also want to point out that modern compilers have different sanitisers (-fsanitize=...) which cause your program to abort() on memory unsafety or other violations. It's effectively a better valgrind which is compiled into your program.
      - AaronFriel 7y ago
        I would argue that most of the time, yes, the compiler should emit bounds checks and only in performance sensitive code should they be removed (or where the compiler can prove the bounds check holds for a range). I don't know how anyone who has studied the history of vulnerabilities and security issues and code would think this is a hard tradeoff: > If yes, your code is now slower but there isn't an easy way to disable this "feature" (if x is heap-allocated or passed as a pointers, how will the compiler know what kind of bounds check is sufficient?). > If no, you have undefined behaviour and crashes. The latter choice has resulted in how many millions or billions in losses, perhaps even lives lost?
        cyphar 7y ago
        The problem is that if you want to permit users to do things like dereference pointers and do pointer arithmetic (a requirement for a C-like language) there is no way for the compiler to ensure (even at runtime, because the pointer might not be to memory managed by the language) that the pointer dereference is valid. Okay, maybe you can add a small overhead to array accesses (which is what Rust did), but you can't stop undefined behaviour entirely. Rust has plenty of undefined behaviour (most can only be triggered through unsafe -- which is the whole argument behind the language -- but as I mentioned there are some cases where even they made a mistake and made an operation safe when it should've have been).
imtringued 7y ago
>an expensive check+branch on each array access It's not very expensive because the branch will never be taken except when it results in an out of bounds access. When that out of bound access happens you care more about the security benefits than performance.
- saagarjha 7y ago
  It has a code size penalty as well.
kjhrklewiou 7y ago
> an expensive check+branch on each array access I'm curious if this still stands in general today, given today's advanced branch predictors and the fact that the CPU tends to be memory-bandwidth-bound, thus you have more "free computation" while waiting for memory (what GPU programmers call compute to memory ratio).

AaronFriel 7y ago

Despite this, tools will often not warn of undefined behavior or these premature optimizations. Quite the opposite, the compilers are almost user hostile for trying to ensure safety and correctness. I cannot see into the minds of the GCC and LLVM teams responsible for the C frontends, but to the extent that you'd think the compiler should do anything here, they seem to think it's largely not their job to improve safety or correctness. That's the job of static analysis tools (which can cost a lot of money), runtime analysis tools (which can cost a lot of time in writing tests that exercise all code paths), and fuzzers (yet more time). Punting all of this extremely important reasoning to "the programmer" is ridiculous when it's been proven over and over again that even incredibly smart C programmers get this wrong.

saagarjha 7y ago
Compilers could certainly do a better job when performing optimizations that “abuse” undefined behavior, but in general this isn’t a trivial problem. The way optimization passes are set up can often make it difficult to generate warnings that have a low false-positive rate.
- AaronFriel 7y ago
  Do you think it might be a problem that undefined behavior optimizations and/or pattern matches are so prolific in C that reducing the "false-positive rate" of ... actually bad undefined behavior (?) would be the hard thing? Why not disallow undefined behavior and instead have the compiler emit: "Hey, this branch is never taken, if you want us not to compile it remove the dead code". Seems like that's exactly the same sort of putting the onus on the programmer that andrepd mentioned, but without the side effect of millions of device drivers are zero day remote code execution vulnerabilities waiting to happen?
  - cyphar 7y ago
    The array access example shows why this isn't generally possible -- the programmer hasn't written any bounds-checking code or assertions (they just wrote x[y]). Should the compiler emit bounds-checks? If yes, your code is now slower but there isn't an easy way to disable this "feature" (if x is heap-allocated or passed as a pointers, how will the compiler know what kind of bounds check is sufficient?). If no, you have undefined behaviour and crashes. Even Rust made a mistake with restricting undefined behaviour -- they accidentally allowed creating references to fields in packed structures (resulting in possibly unaligned references which is undefined behaviour in Rust) in safe code. These days you get a warning telling you to use unsafe or copy the value, but they have yet to make it an error. For comparison, C also gives you a warning for the same problem (or an error with -Werror). I also want to point out that modern compilers have different sanitisers (-fsanitize=...) which cause your program to abort() on memory unsafety or other violations. It's effectively a better valgrind which is compiled into your program.
    - AaronFriel 7y ago
      I would argue that most of the time, yes, the compiler should emit bounds checks and only in performance sensitive code should they be removed (or where the compiler can prove the bounds check holds for a range). I don't know how anyone who has studied the history of vulnerabilities and security issues and code would think this is a hard tradeoff: > If yes, your code is now slower but there isn't an easy way to disable this "feature" (if x is heap-allocated or passed as a pointers, how will the compiler know what kind of bounds check is sufficient?). > If no, you have undefined behaviour and crashes. The latter choice has resulted in how many millions or billions in losses, perhaps even lives lost?
      - cyphar 7y ago
        The problem is that if you want to permit users to do things like dereference pointers and do pointer arithmetic (a requirement for a C-like language) there is no way for the compiler to ensure (even at runtime, because the pointer might not be to memory managed by the language) that the pointer dereference is valid. Okay, maybe you can add a small overhead to array accesses (which is what Rust did), but you can't stop undefined behaviour entirely. Rust has plenty of undefined behaviour (most can only be triggered through unsafe -- which is the whole argument behind the language -- but as I mentioned there are some cases where even they made a mistake and made an operation safe when it should've have been).

imtringued 7y ago

>an expensive check+branch on each array access It's not very expensive because the branch will never be taken except when it results in an out of bounds access. When that out of bound access happens you care more about the security benefits than performance.

saagarjha 7y ago
It has a code size penalty as well.

kjhrklewiou 7y ago

> an expensive check+branch on each array access I'm curious if this still stands in general today, given today's advanced branch predictors and the fact that the CPU tends to be memory-bandwidth-bound, thus you have more "free computation" while waiting for memory (what GPU programmers call compute to memory ratio).