Undefined Behaviour Canaries | Hacker News Reader

Undefined Behaviour Canaries

blog.regehr.org

41 pointscremno50 comments

Is there a C-like language that's sane by default?

One where, for example, uninitialized values are defined as though they are set to some arbitrary value?

* Go and D initialise all variables

* Ada can do so using the Normalize_Scalars (though by default it'll just read whatever garbage is at that location) however the initialisation value is implementation defined (it's recommended that the value be invalid, so that an access to an uninitialised value faults)

* Rust requires that all control paths initialise variables

Both Clang and GCC can warn about potentially uninitialised variables (using -Wuninitialized in Clang and -Wmaybe-uninitialized in GCC, both being in -Wall)

Initialization is not the same thing, though, for everything but Ada.

I'm not looking for a c-like language where variables must be defined / are implicitly initialized to a constant. Those have problems, among other things the cost of double-initialization.

I'm looking for a c-like language where the compiler is free to assume that an uninitialized variable is anything it wants - but it must be consistent about it. So, for example, "return x - x", where x is an integer, will always return zero.

I'm happy to say your question led me on a very interesting adventure :)

Suppose x is an uninitialized int★ (pretend ★ is an asterisk---HN doesn't seem to allow asterisks in comments). Suppose we do

int ★y = x; (★x)++; (★x)--;

Should y-x necessarily be 0, in the language you're looking for? Think carefully. If x had been initialized (and pointed to a valid memory location, say), would y-x necessarily be 0? Surprisingly the answer is no! It's possible that x could point to itself. In that case, (★x)++; actually changes the value of x itself, so that it is no longer cancelled out by the following (★x)--;

I guess the moral is that what you're asking for is subtler than meets the eye

GCC 4.9.2 seems to compile this:

    int test(int *x) {
      int *y = x; 
      (*x)++; 
      (*x)--;
      return (y - x);
    }

into this at O3:

    test(int*):
        xor	eax, eax
        ret

Effectively, into:

    int test(int *x) {
        return 0;
    }

Which seems to contradict your adventure. I think it's because x cannot legally point to itself - x is an int ★, not a void ★. And you can't do arithmetic on a void ★, so it's not a problem there either.

Here, GCC optimize it away. It's not required to do so. In fact, GCC can do whatever it wants in this case and still follow C standard. It may as well

Yeah, you can't do x = &x. But since you didn't initialize x, it's initial value can be whatever is in memory at that particular time (or something else, nasal demons etc)

If the particular value of x at runtime (there is no typechecks in C at runtime) happen to be &x, you can effectively get weird result.

In fact, at -O0 :

    000000000000000b <test>:
       b: 55                    push   %rbp
       c: 48 89 e5              mov    %rsp,%rbp
       f: 48 89 7d e8           mov    %rdi,-0x18(%rbp)
      13: 48 8b 45 e8           mov    -0x18(%rbp),%rax
      17: 48 89 45 f8           mov    %rax,-0x8(%rbp)
      1b: 48 8b 45 e8           mov    -0x18(%rbp),%rax
      1f: 8b 00                 mov    (%rax),%eax
      21: 8d 50 01              lea    0x1(%rax),%edx
      24: 48 8b 45 e8           mov    -0x18(%rbp),%rax
      28: 89 10                 mov    %edx,(%rax)
      2a: 48 8b 45 e8           mov    -0x18(%rbp),%rax
      2e: 8b 00                 mov    (%rax),%eax
      30: 8d 50 ff              lea    -0x1(%rax),%edx
      33: 48 8b 45 e8           mov    -0x18(%rbp),%rax
      37: 89 10                 mov    %edx,(%rax)
      39: 48 8b 55 f8           mov    -0x8(%rbp),%rdx
      3d: 48 8b 45 e8           mov    -0x18(%rbp),%rax
      41: 48 29 c2              sub    %rax,%rdx
      44: 48 89 d0              mov    %rdx,%rax
      47: 48 c1 f8 02           sar    $0x2,%rax
      4b: 5d                    pop    %rbp
      4c: c3                    retq

I don't see what you're saying here. In C, it's undefined, so it's irrelevant.

In my mythical language, the compiler is free to choose whatever initial value of x it wants. So your counterexample still doesn't work.

I think the real answer is that the DCE optimizer understands that y is assigned the same address in x, x never changes (after arithmetic cancels out), y never changes, and then the difference between y & x becomes 0.

Yep.

And you can apply the same logic to the grandparent comment.

There are a lot of other ways for that to fail. You could scribble all over the executing code, or your runtime, or part of the operating system....

I don't think anyone would expect a "sane C" to let you scribble all over completely random pointers without harm. But if the pointer doesn't hit any bytes that are already in use, then "sane C" should return 0.

It would be sane to ask that the literal expression "x - x" be optimised to 0, but I would never dream of asking that "y - x" be optimised to 0. Not unless the compiler can prove the values will be exactly the same in all circumstances and no, it's not allowed to just delete code that invokes undefined behaviour.

> it's not allowed to just delete code that invokes undefined behaviour.

In your mind, what does 'undefined behavior' mean? Because to the rest of us, it means "The standard says the compiler can do anything at all".

I think he's also talking about my mythical C-like language that has somewhat sane rules for these things.

> I think he's also talking about my mythical C-like language that has somewhat sane rules for these things.

Oh, OK.

It's important to realize, though, that if things get defined down too strictly, compilers will be hard-put to generate efficient code for more than one or two closely-related families of processors, which is important in a language designed to be useful for programming rather heterogeneous embedded systems (that is, more 'embedded' than ARM, perhaps with odd word sizes or similar).

Yep.

Which is why I'm not taking about removing UB altogether, just talking about the more egregious examples of things that cause nasty bugs that aren't particularly problematic to code-gen.

Not to mention that embedded systems end up using no optimization half the time anyways, because compilers go so overboard with performance that good luck trying to write safe code in them.

> no, it's not allowed to just delete code that invokes undefined behaviour.

I think it is.

> It's possible that x could point to itself.

...in a way that doesn't violate C++'s type aliasing rules, and thus invoking undefined behavior?

Ummm... x certainly cannot point to itself within the rules of the language, so... poor example.

> Those have problems, among other things the cost of double-initialization.

In D:

    int x;  // initialization eliminated as a 'dead store' by optimizer
    x = 3;

You can also do:

    int x = void;

making the "don't initialize this" proactively marked, rather than being the default behavior.

Right, and in trivial cases that works.

But if you've got, for example

    int x;
    if (somethingThatYouKnowIsTrueButTheCompilerDoesnt())
        x = 3;

there's no way to express that with either of those methods. You'll end up with the redundant store.

If you know it is always true, why is it in an if() ? You'd right it as:

    int x;
    if (somethingThatYouKnowIsTrueButTheCompilerDoesnt())
        x = 3;
    else
        assert(0);

and the compiler will remove the redundant store to x.

> Those have problems, among other things the cost of double-initialization.

Compilers optimise away significantly more complex things than initialising a variable twice.

> I'm looking for a c-like language where the compiler is free to assume that an uninitialized variable is anything it wants - but it must be consistent about it. So, for example, "return x - x", where x is an integer, will always return zero.

So you're looking for C? Because whatever garbage's in there will be the same garbage in both references to x. I have issues with your qualification of that as "sane" though.

Did you read the article?

In C, the compiler is perfectly allowed to compile "return x - x" with x uninitialized into "return 1". Accessing an uninitialized variable in C is undefined behavior. The compiler can do anything. Nasal daemons.

> Compilers optimise away significantly more complex things than initialising a variable twice.

Right, but there are cases where being required to initialize a variable to, say, 0, is not equivalent than being required to initialize a variable to <some arbitrary value>.

For instance, "if (x == 0) y = someExpensiveFunction();" with x being uninitialized. With the "must be initialized to a specific constant" this sort of thing cannot be optimized, whereas with "must be consistent" this can be compiled down to nothing.

> Did you read the article?

Of course.

> In C, the compiler is perfectly allowed to compile "return x - x" with x uninitialized into "return 1". Accessing an uninitialized variable in C is undefined behavior. The compiler can do anything.

Sure. The peephole optimiser will pretty certainly run first and remove the whole expression though.

> For instance, "if (x == 0) y = someExpensiveFunction();" with x being uninitialized. With the "must be initialized to a specific constant" this sort of thing cannot be optimized, whereas with "must be consistent" this can be compiled down to nothing.

You've noted yourself in an other comment that the arbitrary value may be 0, the compiler can make no assumption about what's inside x, so there's absolutely no way to optimise this away, whereas with a specified constant the compiler knows statically whether the test will or will not succeed.

> The peephole optimiser will pretty certainly run first

That's what I'm trying to avoid though. The whole "pretty certainly" thing. The compiler will "pretty certainly" do not optimize this. The compiler will "pretty certainly" optimize that.

And then compiler versions change and people get bitten. Time and time again.

You're misinterpreting what I'm trying to say w.r.t. uninitialized variables here, or perhaps I'm just being idiotic at explaining myself.

In what I'm describing, the compiler can assume the value of x to be anything it wishes. It's just that, once the value is fixed, it must be fixed.

Think of it this way: the compiler may choose any initial value of any variable it chooses.

I'm proposing a language where a read from an uninitialized variable must be consistent with the uninitialized variable having been set to an arbitrary value (in range) before the first read from it. So compiling the static code {int x; return x;} into {return 0;} is perfectly allowed, as is compiling it into {return 42;}.

>The peephole optimiser will pretty certainly run first and remove the whole expression though.

Which is pretty dangerous.

    RunCriticalCodeA();
    if (x) {
      y = 3;
      RunCriticalCodeB();
    } else {
      y = 4;
      RunCriticalCodeB();
    }
    OtherCriticalCodeC();

Fail to initialize x and suddenly all that code is replaced with a return. Even the part outside the if, even the part before the if. Compilers already exist that are this aggressive.

Yep. Optimization by C compilers has gotten to the point of "your worst enemy is the compiler". (My favorite: I had UB in my debug function, but inside an ifdef debug block for speed purposes. So I was getting the most absurd magic errors, that only happened when I was trying to debug)

As I've said, I want reads from uninitialized variables to be at least consistent.

    if (x) {
        foo();
    } else {
        foo();
    }

should always run foo(). Ditto:

    foo();
    if (x)
        bar();
    baz();

should always run baz() (assuming everything before it is "normal" - not going to get into jumps or system exit here), should always run foo() if it runs baz(), and should always run foo().

Why on earth would you want a language where

{ int i; if (x) return; i=2; ... }

generates more opcodes and takes more CPU time to run than

{ if (x) return; int i; i=2; ... }?

That doesn't seem very sane to me.

The variable i only needs to be initialized if it is accessed before being assigned, or if one wants the local stack to be cleared at every function call to avoid data leaks from previous/to later function calls.

The second case explains why someone might want

    int i;
    do_something();
    i = 2;

to behave differently from

    do_something();
    int i = 2;

'Telling whether i will be accessed before being assigned' is equivalent to the halting problem.

In your example, the only way the two options could differ would be if do_something() was dereferencing an invalid pointer that pointed at i. So what you really want is some kind of pointer guard, not automatic variable initialization.

> 'Telling whether i will be accessed before being assigned' is equivalent to the halting problem.

This is true. However, figuring out the most efficient program that's equivalent to a given program also suffers from the halting problem, and that's literally the definition of the goal of an optimizer.

So no: in general you cannot prove if an arbitrary variable will be accessed. However, you can, and will, take a conservative approach and narrow it down as much as possible.

In other words, if you can prove that it will be accessed before being assigned, great. If you can prove that it won't be accessed before being assigned, great. If you can't prove either... Meh, you have to include a redundant store.

It's exactly the same way that optimizers work to, for example, remove redundant stores to a variable. Because it is.

Except that, if you read carefully, what I proposed wasn't quite the same thing.

'Telling whether i will be accessed before being assigned' is equivalent to the halting problem.

Not in C it isn't, thanks to variable scope.

I don't. That's not what I'm saying.

I'm saying that I want a language where

    {int i; return i - i;}

always returns zero, for instance.

A non-braindead compiler would trivially see that the first store has no effect and would optimise it away.

In that silly case, sure, but in the general case that's equivalent to the halting problem.

The compiler can just assume that any given call will halt for this purpose. Nobody is likely to care if there is an unnecessary instruction before an infinite loop.

Edit: To clarify, the general strategy here is to apply the optimization if and only if the compiler can prove it valid (which will be most of the time).

Personally, I prefer the strategy of having the compiler produce an error when it can't prove something is initialized, but auto-initialization only when necessary is totally possible in a huge majority of practical cases.

Do you mean that syntactically uninitialized values are set to some well-defined value (0, for example), or one in which uninitialized values have an undefined value but don't cause undefined behavior on use?

Not where they are set to a constant.

Just that they behave consistently. So, for example, x - x == 0 for int x, even if x is uninitialized. (Basically, it behaves as though x was set to some value, although that value may vary from object to object and from run to run.)

> Just that they behave consistently.

Erroring out because the variable is not initialised is consistent yes?

Yes, but erroring out on something like that is not good for other reasons.

Among other things, that moves it from a local problem to a global problem.

It's the same problem with undefined behavior in general. It's an example of a local problem causing global problems.

You don't want your rocket to crash just because something threw an unchecked exception.

> You don't want your rocket to crash just because something threw an unchecked exception.

Good news: the error is a compile-time error, not a runtime error.

You hope.

And then you run into something like this [1] - which has been open for >10 years, and all of a sudden you're invoking UB without realizing it.

[1] https://gcc.gnu.org/bugzilla/show_bug.cgi?id=18501

I'm not aware of a language designed for programmers that works like this, but LLVM IR's undef works like that. http://llvm.org/docs/LangRef.html#undefined-values

No it doesn't.

For example, in LLVM "x - x" for int x isn't always zero if x is undef. (Skipping over syntax here)

Quoting from the linked document:

> This can be surprising to people (and also matches C semantics) where they assume that “X^X” is always zero, even if X is undefined.

> the short answer is that an ‘undef‘ “variable” can arbitrarily change its value over its “live range”.

So you want a language with a computer algebra system (CAS) that reduces expressions such as "x - x" at compile time. This has been doable in Lisp for a long time using macros. It'd be a bit trickier to do in a C-like language due to the syntax but still reasonable.

Nah, nothing quite that bad. Most of it could be done with standard optimization techniques that the compiler's already doing.

Though you could use a CAS for this, I suppose. Mind you, if you've got a CAS you may as well start using it for more than just this part of the compiler - and that way lies madness.

It's relatively easy. For example:

    int foo(int a) {
        int x;
        if (bar())
            x = 0;
        return a*(x - x) + x;
    }

You start with a first pass by just treating variables that may not being defined as though they are parameters to the function. (I'm doing this all in c-ish syntax, just imagine it's actually in the compiler's IR.) So, the above gets mangled into:

    int foo(int a, int x) {
        if (bar())
            x = 0;
        return a*(x - x) + x;
    }

And optimized at this stage as normal into

    int foo(int a, int x) {
        if (bar())
            x = 0;
        return x;
    }

And... Here's where a CAS comes in handy. Though for most cases you should be able to do pretty well by just choosing any potentially undefined variables to be the first conditional assignment to it. (Or, more likely, searching among "all" (with a limit) possible first assignments to the variable. This gets complex if you've got many variables that are potentially undefined, but that shouldn't happen often. And again, standard optimization techniques.) Which in this case turns into:

    int foo(int a) {
        x = 0;
        if (bar())
            x = 0;
        return x;
    }

And then into

    int foo(int a) {
        return 0;
    }

as expected.

Oh, you actually want a live range to be allocated for the value. No, I'm not aware of any programming language that works like this (nor do I think the benefits would be worth it since you'd be increasing register pressure).

I'm not so sure.

The number of debugging hours that have been spent because of UB causing globally logically inconstant behavior...

And it's better in terms of register pressure than the standard alternative - namely implicitly initializing everything.

Rust?

Rust, like most memory-safe languages, requires initialization, implicit or explicit. This is not quite the same thing.

Reply on news.ycombinator.com