ISO/IEC JTC 1/SC 22/OWGV N0104
ISO/IEC JTC 1/SC 22/WG14 N1278
20 November 2007
Distinguishing Criticality of Undefined Behavior
OWGV N0104 Distinguishing Criticality of Undefined Behavior
Introduction
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.
Discussion
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 the full-target of (the current value of)
//a pointer as the set of
//objects (equivalently, the set of bytes)
//which could permissibly be fetched or stored using that pointer,
//according to the semantic restrictions of the standard.
//Thus, the "one-too-far" value lies one object (i.e., one byte)
//past the end of the full-target.
//
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 unbounded side-effect
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.