Can Undefined Behavior Erase the Hard Drive

Can undefined behavior erase the hard drive?

Can it? Sure. Happened to me, in fact.

I wrote code to delete a temporary directory. That involved creating a recursive delete <temp directory>\*.* command. Due to a bug, the <temp directory> field wasn't always filled in. Our file system code happily executed the recursive delete \*.* command.

My colleagues noticed when the icons on their desktop suddenly disappeared. Took out two machines.

How to explain undefined behavior to know-it-all newbies?

"Congratulations, you've defined the behavior that compiler has for that operation. I'll expect the report on the behavior that the other 200 compilers that exist in the world exhibit to be on my desk by 10 AM tomorrow. Don't disappoint me now, your future looks promising!"

Undefined behavior, in principle

Frama-C's value analysis, a static analyzer the purported goal of which is to find all undefined behaviors in a C program, considers the assignment const int b = a; as okay. This is a deliberate design decision in order to allow memcpy() (typically implemented as a loop over unsigned char elements of a virtual array, and that the C standard arguably allows to re-implement as such) to copy a struct (which can have padding and uninitialized members) to another.

The “exception” is only for lvalue = lvalue; assignments without an intervening conversion, that is, for an assignment that amounts to a copy of a slice of memory for a memory location to another.

I (as one of the authors of Frama-C's value analysis) discussed this with Xavier Leroy at a time when he was himself wondering about the definition to pick in the verified C compiler CompCert, so he may have ended up using the same definition. It is in my opinion cleaner than what the C standard tries to do with indeterminate values that can be trap representations, and the type unsigned char that is guaranteed not to have any trap representations, but both CompCert and Frama-C assume relatively non-exotic targets, and perhaps the standardization committee was trying to accommodate platforms where reading an uninitialized int can indeed abort the program.

Returning b, or passing n1, n2 or n3 to printf in the end at least can be considered undefined behavior, because copying an uninitialized slice of memory does not making it initialized. With an oldish Frama-C version:

$ frama-c -val t.c
…
t.c:19:… accessing uninitialized left-value: assert \initialized(&n1);

And in an oldish version of CompCert, after minor modifications to make the program acceptable to it:

$ ccomp -interp t.c
Time 33: in function foo, expression <loc> = <undef>
ERROR: Undefined behavior

Does an expression with undefined behaviour that is never actually executed make a program erroneous?

If a side effect on a scalar object is unsequenced relative to etc

Side effects are changes in the state of the execution environment (1.9/12). A change is a change, not an expression that, if evaluated, would potentially produce a change. If there is no change, there is no side effect. If there is no side effect, then no side effect is unsequenced relative to anything else.

This does not mean that any code which is never executed is UB-free (though I'm pretty sure most of it is). Each occurrence of UB in the standard needs to be examined separately. (The stricken-out text is probably overly cautious; see below).

The standard also says that

A conforming implementation executing a well-formed program shall produce the same observable behavior
as one of the possible executions of the corresponding instance of the abstract machine with the same program
and the same input. However, if any such execution contains an undefined operation, this International
Standard places no requirement on the implementation executing that program with that input (not even
with regard to operations preceding the first undefined operation).

(emphasis mine)

This, as far as I can tell, is the only normative reference that says what the phrase "undefined behavior" means: an undefined operation in a program execution. No execution, no UB.

Is undefined behavior only an issue if you are deploying on several platforms?

OS changes, innocuous system changes (different hardware version!), or compiler changes can all cause previously "working" UB to not work.

But it is worse than that.

Sometimes a change to an unrelated compilation unit, or far away code in the same compilation unit, can cause previously "working" UB to not work; as an example, two inline functions or methods with different definitions but the same signature. One is silently discarded during linking; and completely innocuous code changes can change which one is discarded.

The code that is working in one context can suddenly stop working in the same compiler, OS and hardware when you use it in a different context. An example of this is violating strong aliasing; the compiled code might work when called at spot A, but when inlined (possibly at link-time!) the code can change meaning.

Your code, if part of a larger project, could conditionally call some 3rd party code (say, a shell extension that previews an image type in a file open dialog) that changes the state of some flags (floating point precision, locale, integer overflow flags, division by zero behavior, etc). Your code, which worked fine before, now exhibits completely different behavior.

Next, many kinds of undefined behavior are inherently non-deterministic. Accessing the contents of a pointer after it is freed (even writing to it) might be safe 99/100, but 1/100 the page was swapped out, or something else was written there before you got to it. Now you have memory corruption. It passes all your tests, but you lacked complete knowledge of what can go wrong.

By using undefined behavior, you commit yourself to a complete understanding of the C++ standard, everything your compiler can do in that situation, and every way the runtime environment can react. You have to audit the produced assembly, not the C++ source, possibly for the entire program, every time you build it! You also commit everyone who reads that code, or who modifies that code, to that level of knowledge.

It is sometimes still worth it.

Fastest Possible Delegates uses UB and knowledge about calling conventions to be a really fast non-owning std::function-like type.

Impossibly Fast Delegates competes. It is faster in some situations, slower in others, and is compliant with the C++ standard.

Using the UB might be worth it, for the performance boost. It is rare that you gain something other than performance (speed or memory usage) from such UB hackery.

Another example I've seen is when we had to register a callback with a poor C API that just took a function pointer. We'd create a function (compiled without optimization), copy it to another page, modify a pointer constant within that function, then mark that page as executable, allowing us to secretly pass a pointer along with the function pointer to the callback.

An alternative implementation would be to have some fixed size set of functions (10? 100? 1000? 1 million?) all of which look up a std::function in a global array and invoke it. This would put a limit on how many such callbacks we install at any one time, but practically was sufficient.

Is while(1); undefined behavior in C?

It is well defined behavior. In C11 a new clause 6.8.5 ad 6 has been added

An iteration statement whose controlling expression is not a constant expression,¹⁵⁶⁾ that performs no input/output operations, does not access volatile objects, and performs no synchronization or atomic operations in its body, controlling expression, or (in the case of a for statement) its expression-3, may be assumed by the implementation to terminate.¹⁵⁷⁾

---

¹⁵⁷⁾_{This is intended to allow compiler transformations such as removal of empty loops even when termination cannot be proven.}

Since the controlling expression of your loop is a constant, the compiler may not assume the loop terminates. This is intended for reactive programs that should run forever, like an operating system.

However for the following loop the behavior is unclear

a = 1; while(a);

In effect a compiler may or may not remove this loop, resulting in a program that may terminate or may not terminate. That is not really undefined, as it is not allowed to erase your hard disk, but it is a construction to avoid.

There is however another snag, consider the following code:

a = 1; while(a) while(1);

Now since the compiler may assume the outer loop terminates, the inner loop should also terminate, how else could the outer loop terminate. So if you have a really smart compiler then a while(1); loop that should not terminate has to have such non-terminating loops around it all the way up to main. If you really want the infinite loop, you'd better read or write some volatile variable in it.

Why this clause is not practical

It is very unlikely our compiler company is ever going to make use of this clause, mainly because it is a very syntactical property. In the intermediate representation (IR), the difference between the constant and the variable in the above examples is easily lost through constant propagation.

The intention of the clause is to allow compiler writers to apply desirable transformations like the following. Consider a not so uncommon loop:

int f(unsigned int n, int *a)
{       unsigned int i;
        int s;
        
        s = 0;
        for (i = 10U; i <= n; i++)
        {
                s += a[i];
        }
        return s;
}

For architectural reasons (for example hardware loops) we would like to transform this code to:

int f(unsigned int n, int *a)
{       unsigned int i;
        int s;
        
        s = 0;
        for (i = 0; i < n-9; i++)
        {
                s += a[i+10];
        }
        return s;
}

Without clause 6.8.5 ad 6 this is not possible, because if n equals UINT_MAX, the loop may not terminate. Nevertheless it is pretty clear to a human that this is not the intention of the writer of this code. Clause 6.8.5 ad 6 now allows this transformation. However the way this is achieved is not very practical for a compiler writer as the syntactical requirement of an infinite loop is hard to maintain on the IR.

Note that it is essential that n and i are unsigned as overflow on signed int gives undefined behavior and thus the transformation can be justified for this reason. Efficient code however benefits from using unsigned, apart from the bigger positive range.

An alternative approach

Our approach would be that the code writer has to express his intention by for example inserting an assert(n < UINT_MAX) before the loop or some Frama-C like guarantee. This way the compiler can "prove" termination and doesn't have to rely on clause 6.8.5 ad 6.

P.S: I'm looking at a draft of April 12, 2011 as paxdiablo is clearly looking at a different version, maybe his version is newer. In his quote the element of constant expression is not mentioned.

Why is f(i = -1, i = -1) undefined behavior?

Since the operations are unsequenced, there is nothing to say that the instructions performing the assignment cannot be interleaved. It might be optimal to do so, depending on CPU architecture. The referenced page states this:

If A is not sequenced before B and B is not sequenced before A, then
two possibilities exist:

• evaluations of A and B are unsequenced: they may be performed in any order and may overlap (within a single thread of execution, the
  compiler may interleave the CPU instructions that comprise A and B)

• evaluations of A and B are indeterminately-sequenced: they may be performed in any order but may not overlap: either A will be complete
  before B, or B will be complete before A. The order may be the
  opposite the next time the same expression is evaluated.

That by itself doesn't seem like it would cause a problem - assuming that the operation being performed is storing the value -1 into a memory location. But there is also nothing to say that the compiler cannot optimize that into a separate set of instructions that has the same effect, but which could fail if the operation was interleaved with another operation on the same memory location.

For example, imagine that it was more efficient to zero the memory, then decrement it, compared with loading the value -1 in. Then this:

f(i=-1, i=-1)

might become:

clear i
clear i
decr i
decr i

Now i is -2.

It is probably a bogus example, but it is possible.

Does IFNDR take precedence over diagnosable rule violations?

Section 2.3 is clear – "this document places no requirement on implementations". Not "this document except for 2.2", but "this document". If an IFNDR situation exists, then the implementation is free to do anything.

Necessary

Overriding 2.2 is necessary. Hypothetically, an IFNDR situation could throw compilation off-track, resulting in it missing an ill-formed situation that does require a diagnostic. (Bugs hidden by other bugs is not a novel concept.) This does not make the implementation non-conforming. The existence of the IFNDR situation gives implementations the leeway they need to potentially miss a diagnostic in related code despite good-faith processing.

This does mean that implementations also have leeway to miss a diagnostic in unrelated code. Oh well. The standard could try to distinguish between "related code" and "unrelated code", but it would be wasted effort. At some point, it is better to trust that implementations work in good faith, rather than excessively regulate.

A "diagnostic not required" scenario is a valid reason for missing a diagnostic. If an implementation uses it as an excuse to actively omit a diagnostic, then it is compliant, but you should stay away.
Just like you should stay far away from a compliant implementation that detects undefined behavior and uses that as an excuse to format your hard drive.

Practical

From a practical perspective, though, 2.3 does not override 2.2. While the official terminology is "no diagnostic required", a more practical view is "the situation does not need to be detected". Situations that require a diagnostic must be detected so that the diagnostic can be produced. Situations that do not require any particular action by the implementation do not need to be detected.

If an implementation does not try to detect an IFNDR situation, then it cannot make decisions based upon the IFNDR existing. That is, it must provide diagnostics for the ill-formedness that it does detect. This is not just "quality-of-implementation", nor is it just "good faith", but rather it is necessary to ensure compliance in the face of an unknown.

If an implementation does detect an IFNDR situation, then we fall back on good faith.

---

Related Topics