Date: 21 November 2007
Contributed by: Tom Plum
Original file name: nov20-plum.html
Notes: Also published as ISO/IEC JTC 1/SC 22/WG 14 N1278
20 November 2007 Thomas Plum, tplum@plumhall.com
The standards for C and C++ have a category for "undefined behavior", and other languages have similar categories. The language standards could provide better assistance to the software-security community if a finer distinction could be made, to distinguish the "critical" undefined behavior from the "non-critical" behavior.
Naturally, there is an understandable reluctance to tinker with the categories of behavior; this paper attempts to create the necessary distinction with minimal invention.
Obvious examples of the "critical" undefined behavior category are buffer overflow (modifying out-of-bounds memory via pointer or subscript), or calling indirect via an invalid pointer-to-function. Once this kind of behavior occurs in any component, it can create a security problem in any other components in the same application, or sometimes even in unrelated applications running on the same platform. The security literature is unfortunately replete with examples of clever exploits that take advantage of these critical undefined behaviors.
On the other hand, C and C++ have many behaviors classified as "undefined behavior" which would (in commercial reality) never create these security problems.
This paper is an attempt to clarify this distinction. It is addressed to language-standards experts, so it's a pretty high-level treatment. It attempts a "big picture" overview; once we're approaching a consensus we can flesh out details.
This is a personal contribution, not the official contribution of any particular group. These personal opinions do not mean that a consensus view has been adopted yet by OWGV or WG14 on any issues discussed herein.
One aspect of C/C++ "undefined behavior" is that a compiler can issue a fatal diagnostic (i.e., as if by #error) if it can determine that control flow must unconditionally reach an undefined behavior. Let's refer to this as the "severe-diagnostic" aspect of undefined behavior.
Define an out-of-bounds store as an assignment (or increment/decrement, etc.) which (at run-time, for a given computational state) affects one or more bytes that lie outside the bounds permitted by the standard.
Define an improper control-flow as an alteration of the flow of control which violates the semantics specified by the standard (e.g., function return via a return address which has been tampered with) or invokes a function which is not compatible with the type of the invoking expression.
Define a critical undefined behavior as one which causes either an out-of-bounds store or an improper control-flow.
As best one could tell from today's C/C++ standards, any undefined behavior might be critical; in particular, the behavior could corrupt the heap, or the stack, or global system data.
However, a reasonable person might infer that behavior which is not undefined (e.g., implementation-defined or unspecified behavior) is not permitted to produce critical behavior, and it might be worth saying this explicitly somewhere.
WG21 has already wrestled with some aspects of this distinction. Several of the situations previously categorized as "undefined behavior" actually involve compile-time context-senstive semantics that just didn't originally happen to fall within a "Constraint" clause in C. In the C++0x Working Paper, these situations have been re-categorized as "ill-formed", meaning that a diagnostic is required; in C, we might change "behavior is undefined" to "is a constraint violation". As always, an implementation might still support the construct as an extension. (It might at some point be worth clarifying that any such extension is still not permitted to perform a critical behavior.)
One other alternative to "undefined behavior" has been introduced in the C++0x WP, known as conditionally-supported behavior. The original impetus came from POSIX, which requires that data pointers and function pointers can be converted to and from each other round-trip without loss of value. But that requirement was clearly labeled as "undefined behavior" in C++ (and it still is, in C), and POSIX didn't like having a requirement of one ISO standard being labeled as undefined behavior in another ISO standard. Conditionally-supported behavior permits the implementation to diagnose the behavior ("we don't support this kind of thing"), but otherwise the implementation must conform to whatever other requirements are provided.
Given this much background, one way to treat non-critical undefined behavior would be to call it "conditionally-supported, with unspecified behavior"; i.e., an implementation can reject it at compile-time (maintaining the severely-diagnosable aspect), but if it chooses to generate code, that code (like all other unspecified behavior) cannot perform a critical behavior. One could go even further and change the undefined behavior to "conditionally-supported, with implementation-defined behavior"; that would require the implementer to document just what the implementation will do if it chooses to support the behavior.
There is an alternative that could be used in addition to this "conditionally-supported" approach, or used instead of it: we could in various places add the words "but not critical", as in "the behavior is undefined but not critical". Still another alternative would be the word "localized", as in "the behavior is undefined but localized". (Localized undefined behavior could, in general, immediately trap, or set all the modified lvalues to indeterminate values, creating further consequences downstream.)
Either of those alternatives would have a direct impact upon test suites as well as upon applications and implementations. A behavior which is "undefined but localized" should mean that a test case for that behavior might provoke a diagnostic message, but if an executable is produced, then that executable program will run to completion (or trap), without any alteration to the memory space outside the set of permissible lvalues in the expression containing the "undefined but localized" behavior.
There will be many dozens of fine-grained details to address in making this new distinction, but this will suffice for an overview.