Technical Perspective: Stacking Up Undefined Behaviors

Any computer system must make trade-offs between freedoms retained by the system and guarantees made to the system’s users. Designers attempt to balance conflicting goals, such as throughput and ease of use. Programming languages must make these trade-offs too. For example, a language with built-in garbage collection often retains the freedom to move objects around in memory, making it difficult to share objects with other processes or with hardware devices.

C and C++ are based on an extreme set of trade-offs: In these languages, a wide variety of hard-to-avoid program behaviors, such as signed integer overflow and out-of-bounds array references, are "undefined behaviors." No guarantees at all are made to a program that executes an undefined behavior. The languages’ heavy reliance on undefined behaviors stems from C’s obsolete philosophy of "trust the programmer" and also from pragmatic efforts by standards committees to encompass a wide variety of implementations. Bugs arising from undefined behaviors are difficult to prevent and during the last few decades they have led to a huge number of exploitable vulnerabilities in security-critical computer programs.

In 2009, a researcher found the Linux kernel contained code that dereferenced a pointer before checking if it was null. The C compiler was then able to effectively perform the following analysis:

Case 1: The pointer is not null, rendering the null check unnecessary.

Case 2: The pointer is null. Since this is undefined behavior, the compiler does not have any obligation to consider this case.

It is easy to see that neither case requires the null check, which the compiler failed to emit, resulting in an exploitable vulnerability in the kernel. This bug was considered to be pernicious since the source code contained the necessary null pointer check but the compiled binary code did not.

In the following paper, Wang et al. recognized this Linux bug was a member of a broader class of bugs. They hypothesized that any time the compiler is able to delete code by using reasoning based on undefined behavior, the program being compiled probably contains a bug. Their tool, STACK, detects this kind of "unstable code," and it has been used to find many bugs in important applications.

Although much effort had previously been put into detecting undefined behaviors, STACK’s design point is interesting and new. First, a tool that warns about every instance of dead code is useless, because dead code is common and is often benign. STACK’s differential approach to detecting unstable code permits it to focus on the special kind of code that is dead only because of undefined behavior. Empirically, C and C++ developers have a very difficult time finding unstable code by hand. Second, STACK makes no attempt to warn about undefined behaviors that do not lead to unstable code. While this may at first glance appear to be a limitation, in practice it means a large fraction of STACK’s defect reports are useful to developers. Finally, STACK’s model for undefined behavior is not tied to any particular compiler. Rather, STACK generates queries about undefined behavior that are passed to an automated theorem prover, enabling it to detect code that is unstable even if no C or C++ compiler can yet remove it.

The computing community is working hard to purge bugs arising from undefined behaviors from our huge installed base of C and C++. These languages were used to implement nearly all of our most safety-critical and security critical programs. More novel approaches, such as STACK, are needed.

Back to Top

Back to Top