9 ms·

Now that C2x plans to make two's complement the only sign representation, is there any reason why signed overflow has to continue being undefined behavior? On

Now that C2x plans to make two's complement the only sign representation, is there any reason why signed overflow has to continue being undefined behavior? On a slightly more personal note: What are some undefined behaviors that you would like to turn into defined behavior, but can't change for whatever reasons that be?

rseacord 6y ago
Maybe someone else can respond to this as well, but I feel like the primary reason signed overflow is still undefined behavior is because so many optimizations depend upon the undefined nature of signed integer overflow. My advice has always been to use unsigned integer types when possible. Personally, I would like to get rid of many of the trap representations (e.g., for integers) because there is no existing hardware in many cases that supports them and it gives implementers the idea that uninitialized reads are undefined behavior. On the other hand, I just wrote a proposal to WG14 to make zero-byte reallocations undefined behavior that was unanimously accepted for C2x.
- saagarjha 6y ago
  > My advice has always been to use unsigned integer types when possible. Unsigned types have their own issues, though: they overflow at "small" values like -1, which means that doing things like correctly looping "backwards" over an array with an unsigned index is non-trivial. > On the other hand, I just wrote a proposal to WG14 to make zero-byte reallocations undefined behavior that was unanimously accepted for C2x. You're saying that realloc(foo, 0) will no longer free the pointer?
  - slavik81 6y ago
    realloc(foo, 0) was changed to no longer free in C99. A rant on the subject: https://github.com/Tarsnap/libcperciva/commit/cabe5fca76f6c38f872ea4a5967458e6f3bfe054 https://github.com/Tarsnap/libcperciva/commit/cabe5fca76f6c3...
msebor 6y ago
Some instances of undefined behavior at translation time can effectively be avoided in practice by tightening up requirements on implementations to diagnose them. But strictly speaking, because the standard allows compilers to continue to chug along even after an error and emit object code with arbitrary semantics, turning even such straightforward instances into constraint violations (i.e., diagnosable errors) doesn't prevent UB. It might seem like defining the semantics for signed overflow would be helpful but it turns out it's not, either from a security view or for efficiency. In general, defining the behavior in cases that commonly harbor bugs is not necessarily a good way to fix them.
klodolph 6y ago
Just going to inject that this impacts a bunch of random optimizations and benchmarks. Just to fabricate an example: for (int i = 0; i < N; i += 2) { // } Reasonably common idea but the compiler is allowed to assume the loop terminates precisely because signed overflow is undefined. I’m not trying to argue that signed overflow is the right tool for the job here for expressing ideas like “this loop will terminate”, but making signed overflow defined behavior will impact the performance of numerics libraries that are currently written in C. From my personal experience, having numbers wrap around is not necessarily “better” than having the behavior undefined, and I’ve had to chase down all sorts of bugs with wraparound in the past. What I’d personally like is four different ways to use integers: wrap on overflow, undefined overflow, error on overflow, and saturating arithmetic. They all have their places and it’s unfortunate that it’s not really explicit which one you are using at a given site.
- alerighi 6y ago
  The compiler assumes that the loop will alwasy terminate and that assumption is wrong, because in reality there is the possibility that the loop will not terminate, since the hardware WILL overflow. So it's not the best solution. If we want to make this behaviour for optimizations (that are to me not worthed, giving the risk of potentially critical bugs) we must make that behavior explicit, not implicit: thus is the programmer that has to say to the compiler, I guarantee you that this operation will never overflow, if it does it's my fault. We can agree that having a number that wraps around is not a particularly good choice. But unless we convince Intel in some way that this is bad and make the CPU trap on an overflow, so we can catch that bug, this is the behaviour that we have because is the behaviour of the hardware.
  - klodolph 6y ago
    > The compiler assumes that the loop will alwasy terminate and that assumption is wrong, because in reality there is the possibility that the loop will not terminate, since the hardware WILL overflow. The language is not a model of hardware, nor should it be. If you want to write to the hardware, the only option continues to be assembly.
  - 6y ago
cataphract 6y ago
Signed overflow being undefined behavior allows optimizations that wouldn't otherwise be possible Quoting http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html http://blog.llvm.org/2011/05/what-every-c-programmer-should-... > This behavior enables certain classes of optimizations that are important for some code. For example, knowing that INT_MAX+1 is undefined allows optimizing "X+1 > X" to "true". Knowing the multiplication "cannot" overflow (because doing so would be undefined) allows optimizing "X*2/2" to "X". While these may seem trivial, these sorts of things are commonly exposed by inlining and macro expansion. A more important optimization that this allows is for "<=" loops like this: > for (i = 0; i <= N; ++i) { ... } > In this loop, the compiler can assume that the loop will iterate exactly N+1 times if "i" is undefined on overflow, which allows a broad range of loop optimizations to kick in. On the other hand, if the variable is defined to wrap around on overflow, then the compiler must assume that the loop is possibly infinite (which happens if N is INT_MAX) - which then disables these important loop optimizations. This particularly affects 64-bit platforms since so much code uses "int" as induction variables.
- gwd 6y ago
  So in a corner case where you have a loop that iterates over all integer values (when does this ever happen?) you can optimize your loop. As a consequence, signed integer arithmetic is very difficult to write while avoiding UB, even for skilled practitioners. Do you think that's a useful trade-off, and do you think anything can be done for those of us who think it's not?
  - buckminster 6y ago
    N is a variable. It might be INT_MAX so the compiler cannot optimise the loop for any value of N. Unless you make this UB.
  - andrepd 6y ago
    No, it's exactly the opposite. Without UB the compiler must assume that the corner case may arise at any time. Knowing it is UB we can assert `n+1 > n`, which without UB would be true for all `n` except INT_MAX. Standardising wrap-on-overflow would mean you can now handle that corner case safely, at the cost of missed optimisations on everything else.
colanderman 6y ago
Beside optimization (as others have pointed out), disallowing wrapping of signed values has the important safety benefit that it permits run-time (and compile-time) detection of arithmetic overflow (e.g. via -fsanitize=signed-integer-overflow). If signed arithmetic were defined to wrap, you could not enable such checks without potentially breaking existing correct code.
wyldfire 6y ago
Could we instead just have standard-defined integer types which saturate or trap on overflow? Sometimes you're writing code where it really, really matters and you're more than willing to spend the extra cycles for every add/mul/etc. Having these new types as a portable idiom would help.
- rseacord 6y ago
  There was a proposal for a checked integer type that you might want to look at: N2466 2020/02/09 Svoboda, Towards Integer Safety http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2466.pdf http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2466.pdf The committee asked the proposers for further work on this effort. Integer types that saturate are an interesting idea. Because signed integer overflow is undefined behavior, implementations are not prohibited from implementing saturation or trapping on overflow.
  - hyc_symas 6y ago
    Eh? I thought that would only be "legal" if it was specified to be implementation-defined behavior. Which would, frankly, be perfectly good. But since it is specified as undefined behavior, programmers are forbidden to use it, and compilers assume it doesn't happen/doesn't exist. The entire notion that "since this is undefined behavior it does not exist" is the biggest fallacy in modern compilers.
    - DougGwyn 6y ago
      The rule is: If you want your program to conform to the C Standard, then (among other things) your program must not cause any case of undefined behavior. Thus, if you can arrange so that instances of UB will not occur, it doesn't matter that identical code under different circumstances could fail to conform. The safest thing is to make sure that UB cannot be triggered under any circumstances; that is, defensive programming.
      - flatfinger 6y ago
tlb 6y ago
Another approach would be a standard library of arithmetic routines that signal overflow. If people used them while parsing binary inputs that would prevent a lot of security bugs. The fact that this question exists and is full of wrong answers suggests a language solution is needed: https://stackoverflow.com/questions/1815367/catch-and-compute-overflow-during-multiplication-of-two-large-integers#1815371 https://stackoverflow.com/questions/1815367/catch-and-comput...
- rseacord 6y ago
  Take a look at N2466 2020/02/09 Svoboda, Towards Integer Safety which has some support in the committee: http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2466.pdf http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2466.pdf (signal is a strong word... maybe indicate?)
- asveikau 6y ago
  Microsoft in particular has a simple approach to this with things like DWordMult(). if (FAILED(DWordMult(a, b, &product))) { // handle error }
  - stephencanon 6y ago
    Clang and GCC's approach for these operations is even nicer FWIW (__builtin_[add/sub/mul]_overflow(a, b, &c)), which allow arbitrary heterogenous integer types for a, b, and c and do the right thing. I know there's recently been some movement towards standardizing something in this direction, but I don't know what the status of that work is. Probably one of the folks doing the AUA can update.
    - AaronBallman 6y ago
      We've been discussing a paper on this (http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2466.pdf http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2466.pdf) at recent meetings and it's been fairly well-received each time, but not adopted for C2x as of yet.
_kst_ 6y ago
> Now that C2x plans to make two's complement the only sign representation, is there any reason why signed overflow has to continue being undefined behavior? I presume you'd want signed overflow to have the usual 2's-complement wraparound behavior. One problem with that is that a compiler (probably) couldn't warn about overflows that are actually errors. For example: int n = INT_MAX; /* ... */ n++; With integer overflow having undefined behavior, if the compiler can determine that the value of n is INT_MAX it can warn about the overflow. If it were defined to yield INT_MIN, then the compiler would have to assume that the wraparound was what the programmer intended. A compiler could have an option to warn about detected overflow/wraparound even if it's well defined. But really, how often do you want wraparound for signed types? In the code above, is there any sense in which INT_MIN is the "right" answer for any typical problem domain?
- enriquto 6y ago
  > In the code above, is there any sense in which INT_MIN is the "right" answer for any typical problem domain? There is no answer different that INT_MIN that would be right and make sense, i.e. the natural properties of the + operator (associativity, commutativity) are respected. Thus, by want of another possibility, INT_MIN is precisely the right answer to your code. I read your code and it seems to me very clear that INT_MIN is exactly what the programmer intended.
  - _kst_ 6y ago
    > I read your code and it seems to me very clear that INT_MIN is exactly what the programmer intended. Well, I'm the author and that's not what I intended. I used INT_MAX as the initial value because it was a simple example. Imagine a case where the value happens to be equal to INT_MAX, and then you add 1 to it. The fact that no result other than INT_MIN makes sense doesn't imply that INT_MIN does make sense. Saturation (having INT_MAX + 1 yield INT_MAX) or reporting an error seem equally sensible. We don't know which behavior is "correct" without knowing anything about the problem domain and what the program is supposed to do. A likely scenario is that the programmer didn't intend the computation to overflow at all, but the program encountered input that the programmer hadn't anticipated. INT_MAX + 1 commonly yields INT_MIN because typical hardware happens to work that way. It's not particularly meaningful in mathematical terms. As for "natural properties", it violates "n + 1 > n". C integers are not, and cannot be, mathematical integers (unless you can restrict values to the range they support).
millstone 6y ago
Being brutal heterodox: STOP WRITING SIGNED ARITHMETIC. Your code assumes that negating a negative value is positive. Your division check forgot about INT_MIN / -1. Your signed integer average is wrong. You confused bitshift with division. etc. etc. etc. Unsigned arithmetic is tractable and should be treated with caution. Signed arithmetic is terrifying and should be treated with the same PPE as raw pointers or `volatile`. This applies if arithmetic maps to CPU instructions, but not to Python or Haskell or etc. If you have automatic bignums, signed arithmetic is of course better.

rseacord 6y ago

Maybe someone else can respond to this as well, but I feel like the primary reason signed overflow is still undefined behavior is because so many optimizations depend upon the undefined nature of signed integer overflow. My advice has always been to use unsigned integer types when possible. Personally, I would like to get rid of many of the trap representations (e.g., for integers) because there is no existing hardware in many cases that supports them and it gives implementers the idea that uninitialized reads are undefined behavior. On the other hand, I just wrote a proposal to WG14 to make zero-byte reallocations undefined behavior that was unanimously accepted for C2x.

saagarjha 6y ago
> My advice has always been to use unsigned integer types when possible. Unsigned types have their own issues, though: they overflow at "small" values like -1, which means that doing things like correctly looping "backwards" over an array with an unsigned index is non-trivial. > On the other hand, I just wrote a proposal to WG14 to make zero-byte reallocations undefined behavior that was unanimously accepted for C2x. You're saying that realloc(foo, 0) will no longer free the pointer?
- slavik81 6y ago
  realloc(foo, 0) was changed to no longer free in C99. A rant on the subject: https://github.com/Tarsnap/libcperciva/commit/cabe5fca76f6c38f872ea4a5967458e6f3bfe054 https://github.com/Tarsnap/libcperciva/commit/cabe5fca76f6c3...

msebor 6y ago

Some instances of undefined behavior at translation time can effectively be avoided in practice by tightening up requirements on implementations to diagnose them. But strictly speaking, because the standard allows compilers to continue to chug along even after an error and emit object code with arbitrary semantics, turning even such straightforward instances into constraint violations (i.e., diagnosable errors) doesn't prevent UB. It might seem like defining the semantics for signed overflow would be helpful but it turns out it's not, either from a security view or for efficiency. In general, defining the behavior in cases that commonly harbor bugs is not necessarily a good way to fix them.

klodolph 6y ago

Just going to inject that this impacts a bunch of random optimizations and benchmarks. Just to fabricate an example: for (int i = 0; i < N; i += 2) { // } Reasonably common idea but the compiler is allowed to assume the loop terminates precisely because signed overflow is undefined. I’m not trying to argue that signed overflow is the right tool for the job here for expressing ideas like “this loop will terminate”, but making signed overflow defined behavior will impact the performance of numerics libraries that are currently written in C. From my personal experience, having numbers wrap around is not necessarily “better” than having the behavior undefined, and I’ve had to chase down all sorts of bugs with wraparound in the past. What I’d personally like is four different ways to use integers: wrap on overflow, undefined overflow, error on overflow, and saturating arithmetic. They all have their places and it’s unfortunate that it’s not really explicit which one you are using at a given site.

alerighi 6y ago
The compiler assumes that the loop will alwasy terminate and that assumption is wrong, because in reality there is the possibility that the loop will not terminate, since the hardware WILL overflow. So it's not the best solution. If we want to make this behaviour for optimizations (that are to me not worthed, giving the risk of potentially critical bugs) we must make that behavior explicit, not implicit: thus is the programmer that has to say to the compiler, I guarantee you that this operation will never overflow, if it does it's my fault. We can agree that having a number that wraps around is not a particularly good choice. But unless we convince Intel in some way that this is bad and make the CPU trap on an overflow, so we can catch that bug, this is the behaviour that we have because is the behaviour of the hardware.
- klodolph 6y ago
  > The compiler assumes that the loop will alwasy terminate and that assumption is wrong, because in reality there is the possibility that the loop will not terminate, since the hardware WILL overflow. The language is not a model of hardware, nor should it be. If you want to write to the hardware, the only option continues to be assembly.
- 6y ago

cataphract 6y ago

Signed overflow being undefined behavior allows optimizations that wouldn't otherwise be possible Quoting http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html http://blog.llvm.org/2011/05/what-every-c-programmer-should-... > This behavior enables certain classes of optimizations that are important for some code. For example, knowing that INT_MAX+1 is undefined allows optimizing "X+1 > X" to "true". Knowing the multiplication "cannot" overflow (because doing so would be undefined) allows optimizing "X*2/2" to "X". While these may seem trivial, these sorts of things are commonly exposed by inlining and macro expansion. A more important optimization that this allows is for "<=" loops like this: > for (i = 0; i <= N; ++i) { ... } > In this loop, the compiler can assume that the loop will iterate exactly N+1 times if "i" is undefined on overflow, which allows a broad range of loop optimizations to kick in. On the other hand, if the variable is defined to wrap around on overflow, then the compiler must assume that the loop is possibly infinite (which happens if N is INT_MAX) - which then disables these important loop optimizations. This particularly affects 64-bit platforms since so much code uses "int" as induction variables.

gwd 6y ago
So in a corner case where you have a loop that iterates over all integer values (when does this ever happen?) you can optimize your loop. As a consequence, signed integer arithmetic is very difficult to write while avoiding UB, even for skilled practitioners. Do you think that's a useful trade-off, and do you think anything can be done for those of us who think it's not?
- buckminster 6y ago
  N is a variable. It might be INT_MAX so the compiler cannot optimise the loop for any value of N. Unless you make this UB.
- andrepd 6y ago
  No, it's exactly the opposite. Without UB the compiler must assume that the corner case may arise at any time. Knowing it is UB we can assert `n+1 > n`, which without UB would be true for all `n` except INT_MAX. Standardising wrap-on-overflow would mean you can now handle that corner case safely, at the cost of missed optimisations on everything else.

colanderman 6y ago

Beside optimization (as others have pointed out), disallowing wrapping of signed values has the important safety benefit that it permits run-time (and compile-time) detection of arithmetic overflow (e.g. via -fsanitize=signed-integer-overflow). If signed arithmetic were defined to wrap, you could not enable such checks without potentially breaking existing correct code.

wyldfire 6y ago

Could we instead just have standard-defined integer types which saturate or trap on overflow? Sometimes you're writing code where it really, really matters and you're more than willing to spend the extra cycles for every add/mul/etc. Having these new types as a portable idiom would help.

rseacord 6y ago
There was a proposal for a checked integer type that you might want to look at: N2466 2020/02/09 Svoboda, Towards Integer Safety http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2466.pdf http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2466.pdf The committee asked the proposers for further work on this effort. Integer types that saturate are an interesting idea. Because signed integer overflow is undefined behavior, implementations are not prohibited from implementing saturation or trapping on overflow.
- hyc_symas 6y ago
  Eh? I thought that would only be "legal" if it was specified to be implementation-defined behavior. Which would, frankly, be perfectly good. But since it is specified as undefined behavior, programmers are forbidden to use it, and compilers assume it doesn't happen/doesn't exist. The entire notion that "since this is undefined behavior it does not exist" is the biggest fallacy in modern compilers.
  - DougGwyn 6y ago
    The rule is: If you want your program to conform to the C Standard, then (among other things) your program must not cause any case of undefined behavior. Thus, if you can arrange so that instances of UB will not occur, it doesn't matter that identical code under different circumstances could fail to conform. The safest thing is to make sure that UB cannot be triggered under any circumstances; that is, defensive programming.
    - flatfinger 6y ago

tlb 6y ago

Another approach would be a standard library of arithmetic routines that signal overflow. If people used them while parsing binary inputs that would prevent a lot of security bugs. The fact that this question exists and is full of wrong answers suggests a language solution is needed: https://stackoverflow.com/questions/1815367/catch-and-compute-overflow-during-multiplication-of-two-large-integers#1815371 https://stackoverflow.com/questions/1815367/catch-and-comput...

rseacord 6y ago
Take a look at N2466 2020/02/09 Svoboda, Towards Integer Safety which has some support in the committee: http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2466.pdf http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2466.pdf (signal is a strong word... maybe indicate?)
asveikau 6y ago
Microsoft in particular has a simple approach to this with things like DWordMult(). if (FAILED(DWordMult(a, b, &product))) { // handle error }
- stephencanon 6y ago
  Clang and GCC's approach for these operations is even nicer FWIW (__builtin_[add/sub/mul]_overflow(a, b, &c)), which allow arbitrary heterogenous integer types for a, b, and c and do the right thing. I know there's recently been some movement towards standardizing something in this direction, but I don't know what the status of that work is. Probably one of the folks doing the AUA can update.
  - AaronBallman 6y ago
    We've been discussing a paper on this (http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2466.pdf http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2466.pdf) at recent meetings and it's been fairly well-received each time, but not adopted for C2x as of yet.

_kst_ 6y ago

> Now that C2x plans to make two's complement the only sign representation, is there any reason why signed overflow has to continue being undefined behavior? I presume you'd want signed overflow to have the usual 2's-complement wraparound behavior. One problem with that is that a compiler (probably) couldn't warn about overflows that are actually errors. For example: int n = INT_MAX; /* ... */ n++; With integer overflow having undefined behavior, if the compiler can determine that the value of n is INT_MAX it can warn about the overflow. If it were defined to yield INT_MIN, then the compiler would have to assume that the wraparound was what the programmer intended. A compiler could have an option to warn about detected overflow/wraparound even if it's well defined. But really, how often do you want wraparound for signed types? In the code above, is there any sense in which INT_MIN is the "right" answer for any typical problem domain?

enriquto 6y ago
> In the code above, is there any sense in which INT_MIN is the "right" answer for any typical problem domain? There is no answer different that INT_MIN that would be right and make sense, i.e. the natural properties of the + operator (associativity, commutativity) are respected. Thus, by want of another possibility, INT_MIN is precisely the right answer to your code. I read your code and it seems to me very clear that INT_MIN is exactly what the programmer intended.
- _kst_ 6y ago
  > I read your code and it seems to me very clear that INT_MIN is exactly what the programmer intended. Well, I'm the author and that's not what I intended. I used INT_MAX as the initial value because it was a simple example. Imagine a case where the value happens to be equal to INT_MAX, and then you add 1 to it. The fact that no result other than INT_MIN makes sense doesn't imply that INT_MIN does make sense. Saturation (having INT_MAX + 1 yield INT_MAX) or reporting an error seem equally sensible. We don't know which behavior is "correct" without knowing anything about the problem domain and what the program is supposed to do. A likely scenario is that the programmer didn't intend the computation to overflow at all, but the program encountered input that the programmer hadn't anticipated. INT_MAX + 1 commonly yields INT_MIN because typical hardware happens to work that way. It's not particularly meaningful in mathematical terms. As for "natural properties", it violates "n + 1 > n". C integers are not, and cannot be, mathematical integers (unless you can restrict values to the range they support).

millstone 6y ago

Being brutal heterodox: STOP WRITING SIGNED ARITHMETIC. Your code assumes that negating a negative value is positive. Your division check forgot about INT_MIN / -1. Your signed integer average is wrong. You confused bitshift with division. etc. etc. etc. Unsigned arithmetic is tractable and should be treated with caution. Signed arithmetic is terrifying and should be treated with the same PPE as raw pointers or `volatile`. This applies if arithmetic maps to CPU instructions, but not to Python or Haskell or etc. If you have automatic bignums, signed arithmetic is of course better.