9 ms·

The problem with integer overflow, in the general context of UB, isn't that it's expensive to trap. The problem is that the C (and C++) specs insist on overflo

by olliej 6y ago

The problem with integer overflow, in the general context of UB, isn't that it's expensive to trap. The problem is that the C (and C++) specs insist on overflow being undefined behavior. Then compilers insist on abusing the UB as meaning that they get to do whatever they want. This particular case is only partially the compiler's fault, as the various specs should not be defining well specified behavior as being undefined. Fully in the compiler's fault is the treatment of UB meaning "now I can do whatever I want", which turns the compiler into a security adversary. I have yet to see a non-microbenchmark, non-spec benchmark, that demonstrates a real world win by subverting the developer's intent.

formerly_proven 6y ago
Integer overflow should have been implementation-defined behavior from day one, because that's what it actually is.
- saagarjha 6y ago
  Implementation defined means that the behavior is defined. This is patently not what the existing behavior of compilers in the face of integer overflow is.
  - formerly_proven 6y ago
    I'm trying to say that integer overflow is architecture-specific, so it _should_ have been standardized as implementation defined.
    - rocqua 6y ago
      You probably know this, but by making it UB, compilers don't need to have the same behavior on every case of integer overflow. This allows compilers to apply much more optimizations.
  - ChrisLomont 6y ago
    Every implementation (compiler and arch combo) defines behavior as far as I know, and I’ve tested dozens of combos. What combo does not have implementation defined behavior for C/C++ signed overflow? Are there any?
    - saagarjha 6y ago
      GCC? Clang? Neither compiler defines it unless you give it flags to specify a certain behavior.
      - ChrisLomont 6y ago
        No, both define it by default on every platform, with no flags needed. Flags allow you to force behavior one way or another. Here [1], for example, is the output from godbolt demonstrating exactly this. Note there are no flags specified, it produces valid platform specific code, and it does so for every platform listed. You can then set flags if you desire, but there is a default, as I stated. https://godbolt.org/z/jbY6PM https://godbolt.org/z/jbY6PM
        saagarjha 6y ago
        As you can see, the compiler has chosen an implementation that overflows in this case. It is not required to.
        ChrisLomont 6y ago
        Yes, which is exactly what I stated. My response was to “ Implementation defined means that the behavior is defined. This is patently not what the existing behavior of compilers in the face of integer overflow is.”, implying compilers didn’t have implementation defined behavior. For integer overflow, they do. You just noted this compiler chose an implementation defined behavior. And you don’t need flags for it to choose. You just stated “ Neither compiler defines it unless you give it flags to specify a certain behavior”. It does define it, exactly as I said, per compiler per platform. No flags made any of them produce implementation defined output. Flags make them produce specific, cross platform behavior. What exactly are you disputing?
  - deleted 6y ago
    [deleted]
  - secondcoming 6y ago
    It means that the behaviour is defined for a particular compiler and architecture target.
- olliej 6y ago
  what you're after is specified behavior. C/C++ essentially has specified, unspecified, and undefined behavior. I can't recall correct terminology. Basically (in order), universally defined behavior, architecturally defined (under/overflow semantics, argument evaluation order, etc), things that cannot be defined (UaF, buffer under/overflows, etc). The problem is that there is a depressing amount of undefined behavior is unnecessarily undefined. UB should be specifically limited to things that cannot have a predictable/defined behavior on any arbitrary platform - e.g. memory errors, etc.
saagarjha 6y ago
Measuring this is tricky for a macrobenchmark because most codebases tend to split into “give me -fwrapv or give me death” or “I care about avoiding undefined behavior so I insert checks myself”. You can’t change any compiler flags to change during benchmarking this for either because for the first one you may break the program and for the second those checks will prevent wrapping for occurring regardless. For what it’s worth, the usually argument given for overflow being undefined is that it makes loop analysis much easier and as a result it allows for better hoisting and strength reduction and autovectorization.
nly 6y ago
I've never bought this argument. If wrapping signed arithmetic (-fwrapv) were the default, and an overflow occurred, then most programs would still not function as intended. Basically your argument is that programmers should be implementing: https://wiki.sei.cmu.edu/confluence/display/c/INT30-C.+Ensure+that+unsigned+integer+operations+do+not+wrap https://wiki.sei.cmu.edu/confluence/display/c/INT30-C.+Ensur... instead of: https://wiki.sei.cmu.edu/confluence/display/c/INT32-C.+Ensure+that+operations+on+signed+integers+do+not+result+in+overflow https://wiki.sei.cmu.edu/confluence/display/c/INT32-C.+Ensur... Both of these solutions are garbage, and blaming the compiler because your language (C) is too weak to help you out is shrugging off responsibility. In places where overflow is likely to matter from a security perspective (parameters derived from user input for example), what mode is used is irrelevant. It's actually easier for a programmer to check for overflow using a safe compiler intrinsic[0] (or in C++ use a checked[1] or multiprecision[2] integer library) than it to correctly implement their own checks. [0] https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins... [1] https://www.boost.org/doc/libs/1_74_0/libs/safe_numerics/doc/html/index.html https://www.boost.org/doc/libs/1_74_0/libs/safe_numerics/doc... [2] https://www.boost.org/doc/libs/1_74_0/libs/multiprecision/doc/html/index.html https://www.boost.org/doc/libs/1_74_0/libs/multiprecision/do...
kazinator 6y ago
C compilers should assume that every bit of code is necessary. The only dead code is that which is predicated on a compile-time constant, as in: if (0) { /* safe to ptimize this away */ } Code which tests a run-time condition must always be assumed to be doing that for a reason. Just provide excellent code generation: great peephole optimizations, jump threading, instruction selection: all the "classics". Try to put local variables into registers nicely. Treat every pointer dereference as a load or store. No fucking bullshit like, "oh, this pointer was dereferenced four lines up from here so this null pointer check can be removed". Because, like, maybe that dereference is a simple mistake, and not an iron-clad logical proposition asserted by an infallible programmer. C was originally designed as a language in which optimizations were up to the programmer. If you wrote clever code like while (* d++ = * s++); to copy a string, that was not just for brevity; it produced better code. That was the idea. The compiler was dumb, and so the fact that in that entire expression, s and d appear only one time meant that they were only accessed one time in the generated code. The programmer was the optimizer. Terse code stuffing multiple effects into a single expression ran faster. And by that same token, no pun intended, code that was less terse was safer. It made all the memory accesses and evaluations that it looked like it was doing, in the order it was doing them.
- MaxBarraclough 6y ago
  You're essentially describing a C compiler with advanced optimisations disabled, no? If you want improved safety and fewer footguns, the solution is to use a safer language than C, rather than to try to declaw a fundamentally unsafe language. Even MISRA C fails to guarantee the absence of undefined behaviour. (Other far more involved projects have made this a goal. [0][1]) The obvious candidates are Ada, Rust, and Zig. It doesn't make sense to mandate the absence of serious compiler optimisations, especially for a language like C. [0] https://github.com/zetzit/zz https://github.com/zetzit/zz [1] https://github.com/microsoft/Armada https://github.com/microsoft/Armada
  - kazinator 6y ago
    It absolutely makes sense to mandate the absence of serious compiler optimizations in an unsafe language, in which programs frequently stray outside of the specification, and in which the programmer has excellent tools for optimizing by hand. You can write C that is nearly impossible not to generate into a nearly optimal instruction sequence with just basic optimizations that do not try to get clever by with deductions arising from multiple disconnected facts coming from separate statements in the program. There is a lot of optimization latitude without doing crazy things. You can turn a switch statement into a jump table without causing a problem, for instance. Unrolling loops is fairly safe. You can allocate registers well; you can improve the instruction sequences. You can thread jumps. You can fill branch delay slots. I don't need the compiler to delete a line of code for me. If I actually delete it myself in the source code, that will shave off just as many cycles! Now if the compiler would simply warn "that null pointer comparison is being done on a pointer that was dereferenced eralier", that would be useful. Instead of optimizing behind my back, give me diagnostics using which I can change the program to make it faster. I could look at that code and see: by golly, that is right; the pointer is guaranteed not to be null in that code, so we can drop the check. Or, oops, no; that dereference should not be happening before the check! You can't have compilers guessing about the purpose and intent of disconnected statements in relation to each other, under the assumption that there is no mistake anywhere. Even philosphically, that is stupid. Advanced optimizations arising from piecing together a deduction from multiple assumptions and facts should all take the form of diagnostic suggestions about how to change the source code.

by olliej 6y ago

formerly_proven 6y ago

Integer overflow should have been implementation-defined behavior from day one, because that's what it actually is.

saagarjha 6y ago
Implementation defined means that the behavior is defined. This is patently not what the existing behavior of compilers in the face of integer overflow is.
- formerly_proven 6y ago
  I'm trying to say that integer overflow is architecture-specific, so it _should_ have been standardized as implementation defined.
  - rocqua 6y ago
    You probably know this, but by making it UB, compilers don't need to have the same behavior on every case of integer overflow. This allows compilers to apply much more optimizations.
- ChrisLomont 6y ago
  Every implementation (compiler and arch combo) defines behavior as far as I know, and I’ve tested dozens of combos. What combo does not have implementation defined behavior for C/C++ signed overflow? Are there any?
  - saagarjha 6y ago
    GCC? Clang? Neither compiler defines it unless you give it flags to specify a certain behavior.
    - ChrisLomont 6y ago
      No, both define it by default on every platform, with no flags needed. Flags allow you to force behavior one way or another. Here [1], for example, is the output from godbolt demonstrating exactly this. Note there are no flags specified, it produces valid platform specific code, and it does so for every platform listed. You can then set flags if you desire, but there is a default, as I stated. https://godbolt.org/z/jbY6PM https://godbolt.org/z/jbY6PM
      - saagarjha 6y ago
        As you can see, the compiler has chosen an implementation that overflows in this case. It is not required to.
        ChrisLomont 6y ago
        Yes, which is exactly what I stated. My response was to “ Implementation defined means that the behavior is defined. This is patently not what the existing behavior of compilers in the face of integer overflow is.”, implying compilers didn’t have implementation defined behavior. For integer overflow, they do. You just noted this compiler chose an implementation defined behavior. And you don’t need flags for it to choose. You just stated “ Neither compiler defines it unless you give it flags to specify a certain behavior”. It does define it, exactly as I said, per compiler per platform. No flags made any of them produce implementation defined output. Flags make them produce specific, cross platform behavior. What exactly are you disputing?
- deleted 6y ago
  [deleted]
- secondcoming 6y ago
  It means that the behaviour is defined for a particular compiler and architecture target.
olliej 6y ago
what you're after is specified behavior. C/C++ essentially has specified, unspecified, and undefined behavior. I can't recall correct terminology. Basically (in order), universally defined behavior, architecturally defined (under/overflow semantics, argument evaluation order, etc), things that cannot be defined (UaF, buffer under/overflows, etc). The problem is that there is a depressing amount of undefined behavior is unnecessarily undefined. UB should be specifically limited to things that cannot have a predictable/defined behavior on any arbitrary platform - e.g. memory errors, etc.

saagarjha 6y ago

Measuring this is tricky for a macrobenchmark because most codebases tend to split into “give me -fwrapv or give me death” or “I care about avoiding undefined behavior so I insert checks myself”. You can’t change any compiler flags to change during benchmarking this for either because for the first one you may break the program and for the second those checks will prevent wrapping for occurring regardless. For what it’s worth, the usually argument given for overflow being undefined is that it makes loop analysis much easier and as a result it allows for better hoisting and strength reduction and autovectorization.

nly 6y ago

I've never bought this argument. If wrapping signed arithmetic (-fwrapv) were the default, and an overflow occurred, then most programs would still not function as intended. Basically your argument is that programmers should be implementing: https://wiki.sei.cmu.edu/confluence/display/c/INT30-C.+Ensure+that+unsigned+integer+operations+do+not+wrap https://wiki.sei.cmu.edu/confluence/display/c/INT30-C.+Ensur... instead of: https://wiki.sei.cmu.edu/confluence/display/c/INT32-C.+Ensure+that+operations+on+signed+integers+do+not+result+in+overflow https://wiki.sei.cmu.edu/confluence/display/c/INT32-C.+Ensur... Both of these solutions are garbage, and blaming the compiler because your language (C) is too weak to help you out is shrugging off responsibility. In places where overflow is likely to matter from a security perspective (parameters derived from user input for example), what mode is used is irrelevant. It's actually easier for a programmer to check for overflow using a safe compiler intrinsic[0] (or in C++ use a checked[1] or multiprecision[2] integer library) than it to correctly implement their own checks. [0] https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins... [1] https://www.boost.org/doc/libs/1_74_0/libs/safe_numerics/doc/html/index.html https://www.boost.org/doc/libs/1_74_0/libs/safe_numerics/doc... [2] https://www.boost.org/doc/libs/1_74_0/libs/multiprecision/doc/html/index.html https://www.boost.org/doc/libs/1_74_0/libs/multiprecision/do...

kazinator 6y ago

C compilers should assume that every bit of code is necessary. The only dead code is that which is predicated on a compile-time constant, as in: if (0) { /* safe to ptimize this away */ } Code which tests a run-time condition must always be assumed to be doing that for a reason. Just provide excellent code generation: great peephole optimizations, jump threading, instruction selection: all the "classics". Try to put local variables into registers nicely. Treat every pointer dereference as a load or store. No fucking bullshit like, "oh, this pointer was dereferenced four lines up from here so this null pointer check can be removed". Because, like, maybe that dereference is a simple mistake, and not an iron-clad logical proposition asserted by an infallible programmer. C was originally designed as a language in which optimizations were up to the programmer. If you wrote clever code like while (* d++ = * s++); to copy a string, that was not just for brevity; it produced better code. That was the idea. The compiler was dumb, and so the fact that in that entire expression, s and d appear only one time meant that they were only accessed one time in the generated code. The programmer was the optimizer. Terse code stuffing multiple effects into a single expression ran faster. And by that same token, no pun intended, code that was less terse was safer. It made all the memory accesses and evaluations that it looked like it was doing, in the order it was doing them.

MaxBarraclough 6y ago
You're essentially describing a C compiler with advanced optimisations disabled, no? If you want improved safety and fewer footguns, the solution is to use a safer language than C, rather than to try to declaw a fundamentally unsafe language. Even MISRA C fails to guarantee the absence of undefined behaviour. (Other far more involved projects have made this a goal. [0][1]) The obvious candidates are Ada, Rust, and Zig. It doesn't make sense to mandate the absence of serious compiler optimisations, especially for a language like C. [0] https://github.com/zetzit/zz https://github.com/zetzit/zz [1] https://github.com/microsoft/Armada https://github.com/microsoft/Armada
- kazinator 6y ago
  It absolutely makes sense to mandate the absence of serious compiler optimizations in an unsafe language, in which programs frequently stray outside of the specification, and in which the programmer has excellent tools for optimizing by hand. You can write C that is nearly impossible not to generate into a nearly optimal instruction sequence with just basic optimizations that do not try to get clever by with deductions arising from multiple disconnected facts coming from separate statements in the program. There is a lot of optimization latitude without doing crazy things. You can turn a switch statement into a jump table without causing a problem, for instance. Unrolling loops is fairly safe. You can allocate registers well; you can improve the instruction sequences. You can thread jumps. You can fill branch delay slots. I don't need the compiler to delete a line of code for me. If I actually delete it myself in the source code, that will shave off just as many cycles! Now if the compiler would simply warn "that null pointer comparison is being done on a pointer that was dereferenced eralier", that would be useful. Instead of optimizing behind my back, give me diagnostics using which I can change the program to make it faster. I could look at that code and see: by golly, that is right; the pointer is guaranteed not to be null in that code, so we can drop the check. Or, oops, no; that dereference should not be happening before the check! You can't have compilers guessing about the purpose and intent of disconnected statements in relation to each other, under the assumption that there is no mistake anywhere. Even philosphically, that is stupid. Advanced optimizations arising from piecing together a deduction from multiple assumptions and facts should all take the form of diagnostic suggestions about how to change the source code.