Undefined behavior in C is a reading error.

Considering how important “undefined behavior” has become to C semantics and the ISO/IEC JTC1/SC22/WG14 Committee, the lack of any reference to it in the K&R ANSI book is notable and the description in the 1999 C Rationale was quite modest.

Undefined behavior gives the implementor license not to catch certain program errors that are difficult to diagnose. It also identifies areas of possible conforming language extension: the implementor may augment the language by providing a definition of the officially undefined behavior. – C Rationale

And yet, a misreading of C89 has turned this simple property into a serious threat to C semantics.

The destructive prevailing interpretation

The governing provision in C89 starts:

Undefined behavior — behavior, upon use of a nonportable or erroneous program construct, or of erroneous data, or of indeterminately-valued objects, for which the Standard imposes no requirements.

The obvious reading of this passage is that it simply naming the class of behaviors where the Standard doesn’t specify what happens as “undefined behavior”.  But almost immediately, this passage was interpreted by self-appointed experts on the comp.lang.c mailing list  to mean that  “the Standard imposes no requirements” on how compilers can implement undefined behavior. This became the prevailing interpretation and C compilers rely on it to justify all sorts of “optimizations” even though it is an unlikely reading of the text and damages the semantic coherence of the language.    John Regehr explains some consequences, using the example of the surprising  undefined behavior caused by shifting  by more than the number of bits in an “int”:

If any step in a program’s execution has undefined behavior, then the entire execution is without meaning. This is important: it’s not that evaluating (1<<32) has an unpredictable result, but rather that the entire execution of a program that evaluates this expression is meaningless. Also, it’s not that the execution is meaningful up to the point where undefined behavior happens: the bad effects can actually precede the undefined operation.

So, “i << 32” buried in a million lines of database code makes the entire program junk – supposedly as an “optimization”!  That is not the end of the destructive super powers of undefined behavior under the prevailing interpretation, because the compiler developers claim that no requirements are imposed on when they can change how they implement undefined behavior.  Chris Lattner of LLVM warned  that thanks to unrestricted undefined behavior, “huge bodies of C code are land mines just waiting to explode.” The argument is that maybe something  worked in one  way for 20 years, but it was always undefined behavior so the compiler is free to delete it, detonate it, replace it with something else or change behavior in any way, at any time (see this peculiar argument on the gcc bug list ).  Apparently, even then, the compiler could change its mind tomorrow or 5 minutes later!   Parsing it out, the prevailing interpretation reads the passage as follows (and note that we have to delete the comma after “behavior” to make it work):

behavior upon use of a nonportable or erroneous program construct, or of erroneous data, or of indeterminately-valued objects:  The Standard imposes no requirements on this behavior  (even as to stability!).

This reading would imply that use of any nonportable program construct or data error or indeterminately-valued object produces undefined behavior  but  WG14  is  not  ready to suppose that the ANSI C standard invalidated nearly every C  program (system calls are nonportable, for example, and malloc returns a pointer to indeterminately valued objects).  Under the  prevailing interpretation “imposes no requirements” is the only operative phrase: the WG14 Committee ignores “use of a nonportable or …”  from the text, and   has built out a long, ad-hoc list of uses that produce “undefined behavior” ( compiler developers have expanded  the list  on their own initiative without documenting much).  The WG14 Committee   also ignored the next sentence in C89, which is an apparent contradiction because it —  imposes requirements on how compilers may implement undefined behavior.

Permissible undefined behavior ranges from ignoring the situation completely with unpredictable results, to behaving during translation or program execution in a documented manner characteristic of the environment (with or without the issuance of a diagnostic message), to terminating a translation or execution (with the issuance of a diagnostic message).

In terms of ISO/ANSI conventions, this second sentence is “normative” (imposes requirements) and “Permissible” is a “shall” word (meaning “must” ). The permissible range of undefined behavior went from ignoring the situation (for those difficult to diagnose errors per the Rationale)  to behaving in a documented manner characteristic of the environment, to flagging an error. What is conspicuously missing from this list of permissible undefined behaviors is any hint that undefined behavior renders the entire program meaningless,  any  license for the kinds of  dramatic and unintuitive transformations we’ve seen from the compilers, and any indication that undefined behavior should be a vehicle for permitting optimizations.

A constructive interpretation.

The more constructive interpretation is that the intention of the first sentence was specify that “undefined behavior”  was what happened when the programmer used certain constructs and data buy Aurogra next day delivery , not otherwise defined by the Standard.

Undefined behavior — behavior Sétif ,  upon use of those particular nonportable or erroneous program constructs, or of erroneous data, or of indeterminately-valued objects, for which the Standard imposes no requirements.

That is, we take the comma seriously so  that the sentence is read to be limiting the category of “undefined behavior” to uses of certain constructs and data that have not been otherwise defined in the Standard. The sentence doesn’t say anything about implementation, because that is covered in the next sentence with the permissible list. Returning a pointer to indeterminate value data, surely a “use”, is not undefined behavior because the standard mandates that malloc will do that.  Use of “asm” does not cause undefined behavior although it is  nonportable because the standard (glancingly) mentions using asm.  Instead of unleashing the compiler to make arbitrary changes, the provision limits what the standards process could dump into the  undefined behavior bucket.  With this interpretation, the passage as a whole makes sense – and is in agreement with the Rationale. We don’t have to ignore the list of uses that can trigger undefined behavior, we don’t have to ignore the range requirements of the second sentence, we can get some intuition about what should be undefined and what should not be, and undefined behavior stays  a manageable concept, instead of creating a giant breach in the hull of the semantics. In retrospect, it may have been an error to  believe everything claimed  in internet discussion forums like comp.lang.c.

Consider the shift example from Linux that Regehr mentioned. Under the constructive interpretation, compilers would have to choose some  “in range” option in place of an “optimization” that doesn’t optimize anything:

1. ignore the situation, generate a “shl” instruction for x86 or the appropriate instruction for other architectures and let the machine architecture determine the semantics. In this case, the programmers screwed up because x86 will truncate the shift value to 5 bits but the “permissible range” allows the compiler to escape all blame and let the programmers either find the problem or not.
2. behaving during translation or program execution in a documented manner characteristic of the environment (with or without the issuance of a diagnostic message) – warn the programmer on an X86 and just compile on ARM.
3. terminating a translation or execution (with the issuance of a diagnostic message) – “Error: Guard your shift left to a machine appropriate number”.

Explaining why the Standard text would decree that  no requirements are imposed in one sentence and then go on to  impose requirements in the next sentence was apparently awkward, so the WG14 committee solved the problem by making a submarine change to the passage in C99.

Undefined behavior —

behavior, upon use of a nonportable or erroneous program construct, of erroneous data, or of indeterminately-valued objects, for which the Standard imposes no requirements. [insert newline]

2 NOTE Permissible Possible undefined behavior ranges from ignoring the situation completely with unpredictable results, to behaving during translation or program execution in a documented manner characteristic of the environment (with or without the issuance of a diagnostic message), to terminating a translation or execution (with the issuance of a diagnostic message).

Thanks to Eskil Steenberg for pointing out the difference between C89 and C99 on this point.  Under ISO rules, inserting the word “NOTE” changed the second sentence from “normative” (mandatory) to non-normative (advisory or informational), and  replacing the requirement word “Permissible” with the informational word “Possible” emphasized the optional nature of the range of behaviors. Currently, this second sentence is completely ignored in WG14 deliberations and apparently is also ignored as even a suggestion by compiler developers. Someone felt the need to weaken this sentence, I can’t find any records of the discussion.

The Prevailing interpretation is fatal to C

So what does it matter that 40 years ago, a murky section of an often murky document could have been misinterpreted?  It matters because over time the Standard and the common compilers have  made C an unsuitable language for developing a range of applications, from memory allocators, to cryptography applications, to threading libraries and, especially operating systems. We have the absurd situation that C, specifically constructed to write the UNIX kernel, cannot be used to write operating systems. In fact, Linux and other operating systems are written in an unstable dialect of C that is produced by using a number of special flags that turn off compiler transformations based on undefined behavior (with no guarantees about future “optimizations”).  The Postgres database also needs some of these flags as does the libsodium encryption library and even the machine learning tensor-flow package.

Because the prevailing interpretation of undefined behavior is so powerful, WG14 and the compiler developers have made it their goto method to  enable  “optimization” and  add to type safety and other rules. Instead of adding rules for optimization in the optimization section of the standard, WG14  has preferred to expand the domain of undefined behavior (often based on completely unsupported assumptions about efficacy) so compilers have a free hand. Instead of coming up with coherent rules for how to access memory via pointers, WG14 has simply declared a large part of customary C usage to be undefined behavior and left it to the compilers to figure out what that means.  As a result, as Lattner pointed out this means the C code base is unstable and:

There is No Reliable Way to Determine if a Large Codebase Contains Undefined Behavior

Compilers have become more powerful (opening up new ways to exploit undefined behavior) and the primary C compilers are free software with corporate sponsors, not programmer customers (or else perhaps Andrew Pinski would not have been so blithe about ignoring his customer Felix-gcc  in the GCC bug report cited above). All these help C semantics continue to degrade. There is even  a widely supported (within the standards body) proposed addition to the C Standard which will radically expand the application of undefined behavior to pointers.

None of this is necessary. C can accommodate significant optimization while regaining semantic coherence – if only the standard and the compilers stop a lazy reliance on a mistaken reading of “impose no requirements”.  A standard is supposed to impose requirements and provide clear guidance to programmers and implementors.

---

See also:   the PLOS paper, or Undefined Behavior and the Purpose of C” , Torvalds on alias, Dennis Ritchie on noalias, and a really simple example

Thanks to Robert Seacord and Eskil Steenberg for reading early versions of this note and providing suggestions.