Hacker News Reader

Comment by cowboylowrez | Hacker News Reader

from the ubc.pdf paper linked in this thread.

    int d[16];
    int SATD (void)
    {
    int satd = 0, dd, k;
    for (dd=d[k=0]; k<16; dd=d[++k]) {
    satd += (dd < 0 ? -dd : dd);
    }
    return satd;
    }

This was “optimized” by a pre-release of gcc-4.8 into the following infinite loop: SATD: .L2: jmp .L2

(simply because k<16 is always true because k is used as an index to an array with a known size)

I mean thats just sort of nuts, how do you loop over an array then in an UB free manner? The paper referred to this situation being remediated:

"The GCC maintainers subsequently disabled this optimization for the case occuring in SPEC"

I try to keep up with the UB thing, while for current code I just use o0 because its fast enough and apparently allows me to keep an array index in bounds. Reading about this leaves me thinking that some of this UB criticism might not be so mindless.

View on HN

Leaving aside the fact that that code reads an array out-of-bounds (which is not a trivial security issue) that's a ridiculously obtuse way to write that code. For loop conditions should be almost always be expressed in terms of their induction variable. A much cleaner and safe version is

    int d[16];
    int SATD (void)
    {
    int satd = 0, k = 0;
    for (k = 0; k < 16; ++k)
      satd += d[k] < 0 ? -d[k] : d[k];
    return satd;
    }

I don't understand your logic though, according to my obviously inadequate understanding of UB, "k < 16" can never be false because its used as an array index for d[16]??? is the critical difference here that the array access happens outside of the "for" expression?

> Is the critical difference here that the array access happens outside of the "for" expression?

Precisely: this means that `d[k]` is guaranteed to execute before the check that `k < 16`. In general, if you have some access like `d[k]` where `k` is some integer and `d` is some array of size `N`, you can assume that `k < N` on all paths which are dominated by the statement containing `d[k]`. In simpler terms, the optimizer will assume that `k < N` is true on every path after the access to `d[k]` occurs.

To make this clearer, consider an equivalent, slightly-transformed version of the original code:

    int d[16];
    int SATD (void)
    {
      int satd = 0, dd, k;
      dd = d[k=0];
      do {
        satd += (dd < 0 ? -dd : dd);
        k = k + 1;
        dd=d[k]; // At this point, k must be < 16.
      } while (k < 16); // The value of `k` has not changed, thus our previous
                        // assumption that `k < 16` must still hold. Thus `k < 16`
                        // can be simplified to `true`.
      return satd;
    }

Now consider a slightly-transformed version of the correct code:

    int d[16];
    int SATD (void)
    {
    int satd = 0, k = 0;
    k = 0;
    do
    {
      satd += d[k] < 0 ? -d[k] : d[k]; // At this point, k must be < 16
      k = k + 1;
    } while (k < 16); // The value of `k` has changed -- at best, we can assert
                      // that `k < 17` since its value increased by 1 since we
                      // last assumed it was less than 16. But the assumption
                      // that `k < 16` doesn't hold, and this check cannot be
                      // simplified.
    return satd;
    }

It's important that this is understood in terms of dominance (in the graph-theoretical sense), because statements like "k < 16 can never be false because it's used in d[k] where k == 16" or "the compiler will delete checks for k < 16 if it knows that d[16] occurs" which seem equivalent to the previously-stated dominance criterion simply are not. It's not that the compiler is detecting UB, thus deleting your checks -- it's that it assumes UB never occurs in the first place.

After thinking about it and reading the other comments, the for loop needs to be changed (k<15), because ++k sets k to 16 in the last step of the version in the parent comment.

This one is nasty.

And it will still cause trouble close to arrays if size INT_MAX.

Fun times.

The problem isn't ++k per se. The problem is the expression d[++k], which immediately reads d[16] before realizing that `k < 16` is false. Look at your sibling comments for explanations and corrections: https://news.ycombinator.com/item?id=43553392 , https://news.ycombinator.com/item?id=43553519

> And it will still cause trouble close to arrays if size INT_MAX.

Fun fact, `for (int i = 0; i <= INT_MAX; i++) {}` is undefined behavior in C/C++ but a well-defined infinite loop in Java.

The problem is checking for k<16 and incrementing k and then using k to access array d[16] afterwards. That's how it goes out if bounds. The condition is inadequate for ensuring that k stays in the bounds of array d[16].

It seems like k is "obviously" an array index for array d[16] here, but whatever. Not in a position to have that discussion right now.

As for Java, (too lazy to look that up right now): That at least sounds like they enforce twos-complement representation for signed int values. C89 has UB here because ancient hardware also used ones-complement. And C89 wanted to be portable as a portable assembler. Well, if UB really makes anything portable. They didn't even go with platform-dependent a.k.a. implementation defined. Instead they specifically chose undefined behavior. The argument brought forward, at least today, is that C isn't supposed to be a portable assembler. Now which one is it supposed to be? Cannot have both at the same time.

Reference: https://c9x.me/compile/bib/ubc.pdf#page=4

Both the parent comment and the referenced paper fail to mention the out-of-bounds access of d[16]. At best, the paper says:

> The compiler assumed that no out-of-bounds access to d would happen, and from that derived that k is at most 15 after the access

Here is my analysis. By unrolling the loop and tracing the statements and values, we get:

    k = 0;  dd = d[k];
    k is 0;  k < 16 is true;  loop body;  ++k;  k is 1;  dd = d[k];
    k is 1;  k < 16 is true;  loop body;  ++k;  k is 2;  dd = d[k];
    k is 2;  k < 16 is true;  loop body;  ++k;  k is 3;  dd = d[k];
    k is 3;  k < 16 is true;  loop body;  ++k;  k is 4;  dd = d[k];
    k is 4;  k < 16 is true;  loop body;  ++k;  k is 5;  dd = d[k];
    k is 5;  k < 16 is true;  loop body;  ++k;  k is 6;  dd = d[k];
    k is 6;  k < 16 is true;  loop body;  ++k;  k is 7;  dd = d[k];
    k is 7;  k < 16 is true;  loop body;  ++k;  k is 8;  dd = d[k];
    k is 8;  k < 16 is true;  loop body;  ++k;  k is 9;  dd = d[k];
    k is 9;  k < 16 is true;  loop body;  ++k;  k is 10;  dd = d[k];
    k is 10;  k < 16 is true;  loop body;  ++k;  k is 11;  dd = d[k];
    k is 11;  k < 16 is true;  loop body;  ++k;  k is 12;  dd = d[k];
    k is 12;  k < 16 is true;  loop body;  ++k;  k is 13;  dd = d[k];
    k is 13;  k < 16 is true;  loop body;  ++k;  k is 14;  dd = d[k];
    k is 14;  k < 16 is true;  loop body;  ++k;  k is 15;  dd = d[k];
    k is 15;  k < 16 is true;  loop body;  ++k;  k is 16;  dd = d[k];  OUT OF BOUNDS!

As long as we enter the loop, the loop must eventually execute undefined behavior. Furthermore, every instance of testing `k < 16` is true before we hit UB. Therefore it can be simplified to true without loss of functionality, because after we hit UB, we are allowed to do absolutely anything. In my ancestor post where I said that any mistake, no matter how small, can have unbounded consequences, I fully mean it and believe it.

Please stop blaming the compiler. The problem is buggy code. Either fix the code, or fix the language specification so that wild reads either return an arbitrary value or crashes cleanly at that instruction.

Note that we cannot change the spec to give definite behavior to writing out of bounds, because it is always possible to overwrite something critical like a return address or an instruction, and then it is literally undefined behavior and anything can happen.

> I mean thats just sort of nuts, how do you loop over an array then in an UB free manner?

The code is significantly transformed, but the nasty behavior can be prevented by designing code that does not read out of bounds! The trick is that the test `k < 16` must be false before any attempt to read/write `d[k]`. Which 99.99% of programmers get right, especially by writing a loop in the standard way and not in the obtuse way demonstrated in the referenced code. The obvious and correct implementation is:

    for (int k = 0; k < 16; k++) {
        int dd = d[k];
        satd += dd < 0 ? -dd : dd;
    }

The fact that the SPEC code chose to load `d[k]` before checking that `k` is still in bounds is an overly clever, counterproductive "jumping the gun" tactic. Putting assignment statements into indexing expressions is also needless obfuscation (which I untangled in the unrolled analysis).

according to my understanding UB mechanics says "k < 16" is always true because its used as an index into d[16]. obviously my understanding is wrong because of your correct code allows it, so I'm just looking for the takeaway here. why is yours not UB when original is? Is there some magic going on that the compiler knows that the value 16 will be used as an index?

is the compiler doing a loop unroll and study that parallels your analysis?

aside from trying to understand this, it also seems a bit nuts that these c guys remediated that behavior by allowing an out of bounds index access with their change (?). so are they saying somehow that in this one case, the out of bounds should be allowed?

Regarding the wrong code, I already wrote (and you can confirm in my unrolled analysis):

> every instance of testing `k < 16` is true before we hit UB. Therefore it can be simplified to true without loss of functionality, because after we hit UB, we are allowed to do absolutely anything.

Regarding the correct code, the key insight is that when k is 16, the test `k < 16` is false, so we break out of the loop and avoid reading out of bounds. Always check bounds before indexing the array, not after!

This article is a helpful introduction: https://blog.regehr.org/archives/213

> is the compiler doing a loop unroll and study that parallels your analysis?

Yes, compilers do all sorts of crazy stuff from bounds analyses to loop induction transformations. Personally, I've seen GCC eliminate my second loop variable in an implementation of the TEA cipher because it figured out that the first variable can be derived from the second, and it adjusted the bounds.

> it also seems a bit nuts that these c guys remediated that behavior by allowing an out of bounds index access with their change

You are right, it's insane that they decided to make a special case for one piece of wrong code (SPEC), probably because it's too popular to fail. That's a social/political problem, not a technical one.

seems like gcc is being pragmatic, at least with the version 12 something I'm running, it doesn't remove the k<16 test/expression, loop terminates, and with enough -W's I see the warning. still, even to detect this I have to use something other than -O0 which is news to me lol

Reply on news.ycombinator.com