![[Home]](http://www.bayleshanks.com/cartoonbayle.png)
---
flatfinger on April 15, 2020 [–]
The difference between "Undefined behavior", as the term is used in the Standard, and "Implementation-Defined Behavior", is that implementations are required to document at least some kind of guarantee about the behavior of the latter, even in cases where guaranteeing anything about behavior would be expensive, but nothing that could be guaranteed about the behavior would be useful.
What is needed is a category of actions where implementations (which I would call "conditionally-defined", where implementations would be required to indicate via "machine-readable" means [e.g. predefined macros, compiler intrinsics, etc.] all possible consequences (one of which would be UB), from which the implementation might choose in Unspecified fashion. If an implementation reports that it may process signed arithmetic using temporary values that may, at the compiler's leisure, be of an unspecified size that's larger than specified, but signed overflow will have no effect other than to yield values that may be larger than their type would normally be capable of holding, then the implementation would be required to behave in that fashion if integer overflow occurs.
...
---
mbauman on April 14, 2020 [–]
Does it concern you how aggressively compiler teams are exploiting UB?
Spivak on April 14, 2020 [–]
You do have to understand that compiler teams aren't saying something like "this triggers UB, quick just replace it with noop." It's just something that naturally happens when you need to reason about code.
For example, consider a very simple statement.
let array[10];
let i = some_function();
print(array[i]);The function might not even be known to the compiler at compilation time if it was from a DLL or something.
But the compiler is like "hey! you used the result of this function as an index for this array! i must be in the range [0, 10)! I can use that information!"
gwd on April 14, 2020 [–]
> But the compiler is like "hey! you used the result of this function as an index for this array! i must be in the range [0, 10)! I can use that information!"
As a developer who has seen lots of developers (including himself) make really dumb mistakes, this seems like a very strange statement.
Imagine if you hired a security guard to stand outside your house. One day, he sees you leave the house and forget to lock the door. So he reasons, "Oh, nothing important inside the house today -- guess I can take the day off", and walks off. That's what a lot of these "I can infer X must be true" reasonings sounds like to me: they assume that developers don't make mistakes; and that all unwanted behavior is exactly the same.
So suppose we have code that does this:
int array[10]; int i = some_function();
/* Lots of stuff */
if ( i > 10 ) {
return -EINVAL;
}array[i] = newval;
And then someone decides to add some optional debug logging, and forgets that `i` hasn't been sanitized yet:
int array[10]; int i = some_function();
logf("old value: %d\n", array[i]);/* Lots of stuff */
if ( i > 10 ) {
return -EINVAL;
}array[i] = newval;
Now reading `array[i]` if `i` > 10 is certainly UB; but in a lot of cases, it will be harmless; and in the worst case it will crash with a segfault.
But suppose a clever compiler says, "We've accessed array[i], so I can infer that i < 10, and get rid of the check entirely!" Now we've changed an out-of-bounds read into an out-of-bounds write, which has changed worst-case a DoS? into a privilege escalation!
I don't know whether anything like this has ever happened, but 1) it's certainly the kind of thing allowed by the spec, 2) it makes C a much more dangerous language to deal with.
btilly on April 14, 2020 [–]
Per https://lwn.net/Articles/575563/, Debian at one point found that 40% of the C/C++ programs that they have are vulnerable to known categories of undefined behavior like this which can open up a variety of security holes.
This has been accepted as what to expect from C. All compiler authors think it is OK. People who are aware of the problem are overwhelmed at the size of it and there is no chance of fixing it any time soon.
The fact that this has become to be seen as normal and OK, is an example of Normalization of Deviance. See http://lmcontheline.blogspot.com/2013/01/the-normalization-o... for a description of what I mean. And deviance will continue to be normalized right until someone writes an automated program that walks through projects, finds the surprising undefined behavior, and tries to come up with exploits. After project after project gets security holes, perhaps the C language committee will realize that this really ISN'T okay.
And the people who already migrated to Rust will be laughing their asses off in the corner.
pjmlp on April 15, 2020 [–]
Just to put in context how much they care, see when Morris worm happened.
asveikau on April 14, 2020 [–]
> in a lot of cases, it will be harmless; and in the worst case it will crash with a segfault.
I am not sure if a segfault is always the worst case. It could be by some coincidence that array[i] contains some confidential information [maybe part of a private key? 32 bits of the user's password?] and you've now written it to a log file.
I know it's hard to imagine a mis-read of ~32 bits would have bad consequences of that sort, but it's not out of the question.
saagarjha on April 14, 2020 [–]
Misreads of much less than that have been exploitable in the past.
---
https://news.ycombinator.com/item?id=22865357
" Consider signed integer overflow.
The intent wasn't that the compiler could generate nonsense code if the programmer overflowed an integer. The intent was the the programmer could determine what would happen by reading the hardware manual. You'd wrap around if the hardware naturally would do so. On some other hardware you might get saturation or an exception.
In other words, all modern computers should wrap. That includes x86, ARM, Power, Alpha, Itanium, SPARC, and just about everything else. ...
favorited on April 14, 2020 [–]
If most C developers wanted to trade the performance they get from the compiler being able to assume `n+1 > n` for signed integer n, it would happen.
flatfinger on April 15, 2020 [–]
Most of the useful optimizations that could be facilitated by treating integer overflow as jump the rails optimization could be facilitated just as well by allowing implementations to behave as though integers may sometimes, non-deterministically, be capable of holding values outside their range. If integer computations are guaranteed never to have side effects beyond yielding "weird" values, programs that exploit that guarantee may be processed to more efficient machine code than those which must avoid integer overflow at all costs.
...
Under the kind of model I have in mind, a compiler would be allowed to treat temporary integer objects as being capable of holding values outside the range of their types, which would allow a compiler to optimize e.g. x*y/y to x, or x+y>y to x>0, but the effects of overflow would be limited to the computation of potentially weird values. If a program would meet requirements regardless of what values a temporary integer object holds, allowing such objects to acquire such weird values may be more efficient than requiring that programs write code to prevent computation of such values. "
According to the published Rationale, the authors of C89 would have expected that something like:
unsigned mul(unsigned short x, unsigned short y)
{ return (x*y); }would on most implementations yield an arithmetically-correct result even for values of (x*y) between INT_MAX+1U and UINT_MAX. Indeed, I rather doubt they could imagine any compiler for a modern system would do anything other than yield an arithmetically-correct result or--maybe--raise a signal or terminate the program. In some cases, however, that exact function will disrupt the behavior of its caller in nonsensical fashion. Do you think such behavior is consistent with the C89 Committee's intention as expressed in the Rationale?
clarry on April 15, 2020 [–]
> Do you think such behavior is consistent with the C89 Committee's intention as expressed in the Rationale?
No, but in general I'm ok with integer overflows causing disruptions (and I'm happy that compilers provide an alternative, in the form of fwrapv, for those who don't care).
I do think that the integer promotions are a mistake. I would also welcome a standard, concise, built-in way to perform saturating or overflow-checked arithmetic that both detects overflows as well as allows you to ignore them and assume an implementation-defined result.
As it is, preventing overflows the correct way is needlessly verbose and annoying, and leads to duplication of apis (like reallocarray).
flatfinger on April 15, 2020 [–]
I wouldn't mind traps on overflow, though I think overflow reporting with somewhat loose semantics that would allow an implementation to produce arithmetically correct results when convenient, and give a compiler flexibility as to when overflow is reported, could offer much better performance than tight overflow traps. On the other hand, the above function will cause gcc to silently behave in bogus fashion even if the result of the multiplication is never used in any observable fashion.
whelming_wave on April 15, 2020 [–]
It lets you check that a+b > a for unknown unsigned b or signed b known > 0, to make sure addition didn’t overflow. I’m rather certain all modern C compilers will optimize that check out.
---
cataphract on April 14, 2020 [–]
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-...
> 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.
userbinator on April 15, 2020 [–]
I've always thought that assuming such things should be wrong, because if you were writing the Asm manually, you would certainly think about it and NOT optimise unless you had a very good reason why it won't overflow. Likewise, I think that unless the compiler can prove that it, it should, like the sane human, refrain from making the assumption.
scaredginger on April 15, 2020 [–]
Well, by that reasoning, if you were coding in C, you would certainly think about it and ensure overflows won't happen.
The fact is that if the compiler encounters undefined behaviour, it can do basically whatever it wants and it will still be standard-compliant.
rbultje on April 14, 2020 [–]
> for (i = 0; i <= N; ++i) { ... }
The worst thing is that people take it as acceptable that this loop is going to operate differently upon overflow (e.g. assume N is TYPE_MAX) depending on whether i or N are signed vs. unsigned.
JoeAltmaier? on April 14, 2020 [–]
Is this a real concern, beyond 'experts panel' esoteric discussion? Do folks really put a number into an int, that is sometimes going to need to be exactly TYPE_MAX but no larger?
I've gone a lifetime programming, and this kind of stuff never, ever matters one iota.
btilly on April 14, 2020 [–]
Yes, people really do care about overflow. Because it gets used in security checks, and if they don't understand the behavior then their security checks don't do what they expected.
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=30475 shows someone going hyperbolic over the issue. The technical arguments favor the GCC maintainers. However I prefer the position of the person going hyperbolic.
JoeAltmaier? on April 14, 2020 [–]
That example was not 'overflow'. It was 'off by one'? That seems uninteresting, outside as you say the security issue where somebody might take advantage of it.
btilly on April 14, 2020 [–]
That example absolutely was overflow. The bug is, "assert(int+100 > int) optimized away".
GCC has the behavior that overflowing a signed integer gives you a negative one. But an if tests that TESTS for that is optimized away!
The reason is that overflow is undefined behavior, and therefore they are within their rights to do anything that they want. So they actually overflow in the fastest way possible, and optimize code on the assumption that overflow can't happen.
The fact that almost no programmers have a mental model of the language that reconciles these two facts is an excellent reason to say that very few programmers should write in C. Because the compiler really is out to get you.
---
cataphract on April 14, 2020 [–]
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-...
> 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 on April 14, 2020 [–]
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?
andrepd on April 14, 2020 [–]
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.
rbultje on April 14, 2020 [–]
I/we understand the optimization, and I'm sure you understand the problem it brings to common procedures such as DSP routines that multiply signed coefficients from e.g. video or audio bitstreams:
for (int i = 0; i < 64; i++) result[i] = inputA[i] * inputB[i];
If inputA[i] * inputB[i] overflowed, why are my credit card details at risk? The question is: can we come up with an alternate behaviour that incorporates both advantages of the i<=N optimization, as well as leave my credit card details safe if the multiplication in the inner loop overflowed? Is there a middle road?
qppo on April 14, 2020 [–]
Another problem is that there's no way to define it, because in that example the "proper" way to overflow is with saturating arithmetic, and in other cases the "proper" overflow is to wrap. Even on CPUs/DSPs that support saturating integer arithmetic in hardware, you either need to use vendor intrinsics or control the status registers yourself.
jononor on April 14, 2020 [–]
One could allow the overflow behavior to be specified, for example on the scope level. Idk, with a #pragma ? #pragma integer-overflow-saturate
gwd on April 14, 2020 [–]
I'd almost rather have a separate "ubsigned" type which has undefined behavior on overflow. By default, integers behave predictably. When people really need that extra 1% performance boost, they can use ubsigned just in the cases where it matters.
---
thayne on April 14, 2020 [–]
Have you considered adding intrinsic functions for arithmetic operations that _do_ have defined behavior on overflow. Such as the overflowing_* functions in rust?
flatfinger on April 15, 2020 [–]
The semantics most programs need for overflow are to ensure that (1) overflow does not have intolerable side effects beyond yielding a likely-meaningless value, and (2) some programs may need to know whether an overflow might have produced an observably-arithmetically-incorrect result. A smart compiler for a well-designed language should in many cases be able to meet these requirements much more efficiently than it could rigidly process the aforementioned intrinsics.
A couple of easy optimizations, for example, that would be available to a smart compiler processing straightforwardly-written code to use automatic overflow checking, but not to one fed code that uses intrinsics:
1. If code computes x=yz, but then never uses the value of x, a compiler that notices that x is unused could infer that the computation could never be observed to produce an arithmetically-incorrect result, and thus there would be no need to check for overflow.
2. If code computes xy/z, and a compiler knows that y=z*2, the compiler could simplify the calculation to x+x, and would thus merely have to check for overflow in that addition. If code used intrinsics, the compiler would have to overflow check the multiplication, which on most platforms would be more expensive. If an implementation uses wrapping semantics, the cost would be even worse, since an implementation would have to perform an actual division to ensure "correct" behavior in the overflow case.
Having a language offer options for the aforementioned style of loose overflow checking would open up many avenues of optimization which would be unavailable in language that only over precise overflow checking or no overflow checking whatsoever.
thayne on April 16, 2020 [–]
oops, i meant the wrapping_* functions
flatfinger on April 16, 2020 [–]
If one wants a function that will compute xy/z when xy doesn't overflow, and yield some arbitrary value (but without other side-effects) when it does, wrapping functions will often be much slower than would be code that doesn't have to guarantee any particular value in case of overflow. If e.g. y is known to be 30 and z equal to 15, code using a wrapping multiply would need to be processed by multiplying the value by 30, computing a truncated the result, and dividing that by 15. If the program could use loosely-defined multiplication and division operators, however, the expression could be simplified to x+x.
---
"What I’d personally like is four different ways to use integers: wrap on overflow, undefined overflow, error on overflow, and saturating arithmetic"
---
flatfinger on April 15, 2020 [–]
I can certainly understand the value in allowing compilers to perform integer arithmetic using larger types than specified, at their leisure, or behave as though they do. Such allowance permits `x+y > y` to be replaced with `x > 0`, or `x30/15` to be replaced with `x2`, etc. and also allows for many sorts of useful loop induction.
Some additional value would be gained by allowing stores to automatic objects whose address isn't taken to maintain such extra range at their convenience, without any requirement to avoid having such extra range randomly appear and disappear. Provided that a program coerces values into range in when necessary, such semantics would often be sufficient to meet application requirements without having to prevent overflow.
What additional benefits are achieved by granting compilers unlimited freedom beyond that? I don't see any such benefits that would be worth anything near the extra cost imposed on programmers.
---
colanderman on April 14, 2020 [–]
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.
---
klodolph on April 14, 2020 [–]
At -O2, GCC 9.2 (the compiler I happened to use for testing) will use pointer arithmetic, compiling it as something like the following:
int sum_diff(int *arr, length n) {
int sum = 0;
int *ptr = arr;
int *end = arr + n;
while (ptr < end) {
sum += ptr[1] - ptr[0];
ptr += 2;
}
return sum;
}At -O3, GCC 9.2 will emit SSE instructions. You can see this yourself with Godbolt.
Now, try replacing "int" with "unsigned". Neither of these optimizations happen any more. You get neither autovectorization nor pointer arithmetic. You get the original loop, compiled in the most dumb way possible.
---
---
_kst_ on April 14, 2020 [–]
Pointer equality (the == and != operators) is well defined for any pointers (of the same type) to any objects.
Relational operators (< <= > >=) on pointers have undefined behavior unless both pointers point to elements of the same array object or just past the end of it. A single non-array object is treated as a 1-element array for this purpose.
(That's for object pointers. Function pointers can be compared for equality, but relational operators on function pointers are invalid.)
---
MaxBarraclough? on April 14, 2020 [–]
Does the following code fragment cause undefined behaviour?
unsigned int x;
x -= x;
There's a lengthy StackOverflow? thread where various C language-lawyers disagree on what the spec has to say about trap values, and under what circumstances reading an uninitialised variable causes UB. I'd appreciate an authoritative answer. Thanks for dropping by on HN!
https://stackoverflow.com/q/11962457/
msebor on April 14, 2020 [–]
Yes, it's undefined. It involves a read of an uninitialized local variable. Except for the special case of unsigned char, any uninitialized read is undefined.
---
rini17 on April 14, 2020 [–]
And are there standard primitives to do this correctly (signed-unsigned-signed conversion) that never invoke undefined behavior?
stephencanon on April 14, 2020 [–]
Signed to unsigned conversion is fully defined (and does the two's complement thing):
> Otherwise, if the new type is unsigned, the value is converted by repeatedly adding or subtracting one more than the maximum value that can be represented in the new type until the value is in the range of the new type (6.3.1.3 Signed and unsigned integers)
Unsigned to signed is the hard direction. If the result would be positive (i.e. in range for the signed type), then it just works, but if it would be negative, the result is implementation-defined (but note: not undefined). You can further work around this with various constructs that are ugly and verbose, but fully defined and compilers are able to optimize away. For example, `x <= INT_MAX ? (int)x : (int)(x + INT_MIN) + INT_MIN` works if int has a twos-complement representation (finally guaranteed in C2x, and already guaranteed well before then for the intN_t types), and is optimized away entirely by most compilers.
---
BeeOnRope? on April 14, 2020 [–]
When deciding on the behavior of some operation that maps to hardware [1], how do you weight the existing hardware behaviors?
For example, if all past, current and contemplated hardware behaves in the same way, I assume that the standard will simply enshrine this behavior.
However, what if 99% of hardware behaves one way and 1% another? Do you set the behavior to "undefined" to accommodate the 1%? At what point to you decide that the minority is too small and you'll enshrine the majority behavior even though it disadvantages minority hardware?
---
[1] Famous examples include things like bit shift and integer overflow behavior.
rseacord on April 14, 2020 [–]
Some example of hardware variation (since you mentioned shifting and overflow):
BeeOnRope? on April 14, 2020 [–]
On x86 it's actually mixed: scalar shifts behave as you describe, but vectorised logical shifts flush to zero when the shift amount is greater than the element size!
So x86 actually has both behaviors in one box (three behaviors if you could the 32-bit and 64-bit scalar things you mentioned separately).
This is an example of where UB for simple operations actually helps even on a single hardware platform: it allows efficient vectorization.
---
eska on April 14, 2020 [–]
There's a compiler attribute in GCC to promise that a function is pure, i.e. free from side effects and only uses its inputs.
This is useful for parallel computations, optimizations and readability, e.g.
sum += f(2); sum += f(2);
can be optimized to
x = f(2); sum += x; sum += x;
Would the current motto of the consortium forbid adding a feature such as marking a function as pure, that would not just promise, but also enforce that no side effects are caused (only local reads/writes, only pure functions may be called), and no inputs except for the function arguments are used?
pascal_cuoq on April 14, 2020 [–]
If you wrote down your proposal, which the C committee member Robert Seacord is encouraging you to do here: https://news.ycombinator.com/item?id=22870210 , you would have to think carefully about functions that are pure according to your definition (free from side effects and only uses its inputs) but do not terminate for some inputs.
There is at least one incorrect optimization present in Clang because of this (function that has no side-effects detected as pure, and call to that function omitted from a caller on this basis, when in fact the function may not terminate).
temac on April 14, 2020 [–]
I thought the compiler was free to pretend loops without side effects always terminate, and in that sense it is already a "correct" optimization? Or is it only for C++, I'm not sure?
pascal_cuoq on April 14, 2020 [–]
That may be the case in C++, but in C infinite loops are allowed as long as the controlling condition is a constant expression (making it clear that the developper intends an infinite loop). These infinite loops without side-effects are even useful from time to time in embedded software, so it was natural for the committee to allow them: https://port70.net/~nsz/c/c11/n1570.html#6.8.5p6
And you now have all the details of the Clang bug, by the way: write an infinite loop without side-effects in a C function, then call the function from another C function, without using its result.
---
" Another aspect of Go being a useful programming environment is having well-defined semantics for the most common programming mistakes, which aids both understandability and debugging. This idea is hardly new. Quoting Tony Hoare again, this time from his 1972 “Quality of Software” checklist:
As well as being very simple to use, a software program must be very difficult to misuse; it must be kind to programming errors, giving clear indication of their occurrence, and never becoming unpredictable in its effects.
The common sense of having well-defined semantics for buggy programs is not as common as one might expect. In C/C++, undefined behavior has evolved into a kind of compiler writer's carte blanche to turn slightly buggy programs into very differently buggy programs, in ever more interesting ways. Go does not take this approach: there is no “undefined behavior.” In particular, bugs like null pointer dereferences, integer overflow, and unintentional infinite loops all have defined semantics in Go. "
---
