Understanding Integer Overflow in CC++.pdf

(238 KB) Pobierz
Appeared in
Proceedings of the 34th International Conference on Software Engineering (ICSE),
Zurich, Switzerland, June 2012.
Understanding Integer Overflow in C/C++
Will Dietz,
∗
Peng Li,
†
John Regehr,
†
and Vikram Adve
∗
∗
Department of Computer Science
University of Illinois at Urbana-Champaign
{wdietz2,vadve}@illinois.edu
†
School of Computing
University of Utah
{peterlee,regehr}@cs.utah.edu
Abstract—Integer
overflow bugs in C and C++ programs
are difficult to track down and may lead to fatal errors or
exploitable vulnerabilities. Although a number of tools for
finding these bugs exist, the situation is complicated because
not all overflows are bugs. Better tools need to be constructed—
but a thorough understanding of the issues behind these errors
does not yet exist. We developed IOC, a dynamic checking tool
for integer overflows, and used it to conduct the first detailed
empirical study of the prevalence and patterns of occurrence
of integer overflows in C and C++ code. Our results show that
intentional uses of wraparound behaviors are more common
than is widely believed; for example, there are over 200
distinct locations in the SPEC CINT2000 benchmarks where
overflow occurs. Although many overflows are intentional, a
large number of accidental overflows also occur. Orthogonal
to programmers’ intent, overflows are found in both well-
defined and undefined flavors. Applications executing undefined
operations can be, and have been, broken by improvements in
compiler optimizations. Looking beyond SPEC, we found and
reported undefined integer overflows in SQLite, PostgreSQL,
SafeInt, GNU MPC and GMP, Firefox, GCC, LLVM, Python,
BIND, and OpenSSL; many of these have since been fixed.
Our results show that integer overflow issues in C and C++
are subtle and complex, that they are common even in mature,
widely used programs, and that they are widely misunderstood
by developers.
Keywords-integer
overflow; integer wraparound; undefined
behavior
I. I
NTRODUCTION
Integer numerical errors in software applications can
be insidious, costly, and exploitable. These errors include
overflows, underflows, lossy truncations (e.g., a cast of an
int
to a
short
in C++ that results in the value being
changed), and illegal uses of operations such as shifts (e.g.,
shifting a value in C by at least as many positions as its
bitwidth). These errors can lead to serious software failures,
e.g., a truncation error on a cast of a floating point value to
a 16-bit integer played a crucial role in the destruction of
Ariane 5 flight 501 in 1996. These errors are also a source
of serious vulnerabilities, such as integer overflow errors in
OpenSSH [1] and Firefox [2], both of which allow attackers
to execute arbitrary code. In their 2011 report MITRE places
integer overflows in the “Top 25 Most Dangerous Software
Errors” [3].
Detecting integer overflows is relatively straightforward
by using a modified compiler to insert runtime checks.
However, reliable detection of overflow
errors
is surprisingly
difficult because overflow behaviors are not always bugs.
The low-level nature of C and C++ means that bit- and
byte-level manipulation of objects is commonplace; the line
between mathematical and bit-level operations can often be
quite blurry. Wraparound behavior using unsigned integers
is legal and well-defined, and there are code idioms that
deliberately use it. On the other hand, C and C++ have
undefined semantics for signed overflow and shift past
bitwidth: operations that are perfectly well-defined in other
languages such as Java. C/C++ programmers are not always
aware of the distinct rules for signed vs. unsigned types in C,
and may na¨vely use signed types in intentional wraparound
ı
1
operations. If such uses were rare, compiler-based overflow
detection would be a reasonable way to perform integer error
detection. If it is not rare, however, such an approach would
be impractical and more sophisticated techniques would be
needed to distinguish
intentional
uses from
unintentional
ones.
Although it is commonly known that C and C++ programs
contain numerical errors and also benign, deliberate use
of wraparound, it is unclear how common these behaviors
are and in what patterns they occur. In particular, there is
little data available in the literature to answer the following
questions:
1) How common are numerical
errors
in widely-used
C/C++ programs?
2) How common is use of intentional wraparound op-
erations with signed types—which has undefined
behavior—relying on the fact that today’s compilers
may compile these overflows into
correct
code? We
refer to these overflows as “time bombs” because they
remain latent until a compiler upgrade turns them into
observable errors.
3) How common is
intentional
use of well-defined
fact, in the course of our work, we have found that even experts
writing
safe integer libraries
or
tools to detect integer errors
are not always
fully aware of the subtleties of C/C++ semantics for numerical operations.
1
In
c 2012 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes
or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must
be obtained from the IEEE.
wraparound operations on unsigned integer types?
Although there have been a number of papers on tools
to detect numerical errors in C/C++ programs,
no previous
work we know of has explicitly addressed these questions, or
contains sufficient data to answer any of them.
The closest is
Brumley et al.’s work [4], which presents data to motivate the
goals of the tool and also to evaluate false positives (invalid
error reports) due to intentional wraparound operations.
As discussed in Section V, that paper only tangentially
addresses the third point above. We study all of these
questions systematically.
This paper makes the following primary contributions.
First, we developed Integer Overflow Checker (IOC), an
open-source tool that detects both undefined integer behav-
iors as well as well-defined wraparound behaviors in C/C++
programs.
2
IOC is an extension of the Clang compiler for
C/C++ [5]. Second, we present the first detailed, empirical
study—based on SPEC 2000, SPEC 2006, and a number
of popular open-source applications—of the prevalence and
patterns of occurrence of numerical overflows in C/C++
programs. Part of this study includes a manual analysis of a
large number of
intentional
uses of wraparound in a subset
of the programs. Third, we used IOC to discover previously
unknown overflow errors in widely-used applications and
libraries, including SQLite, PostgreSQL, BIND, Firefox,
OpenSSL, GCC, LLVM, the SafeInt library, the GNU MPC
and GMP libraries, Python, and PHP. A number of these
have been acknowledged and fixed by the maintainers (see
Section IV).
The key findings from our study of overflows are as
follows: First, all four combinations of intentional and
unintentional, well-defined and undefined integer overflows
occur frequently in real codes. For example, the SPEC
CINT2000 benchmarks had over 200 distinct occurrences
of intentional wraparound behavior, for a wide range of
different purposes. Some uses for intentional overflows are
well-known, such as hashing, cryptography, random number
generation, and finding the largest representable value for
a type. Others are less obvious, e.g., inexpensive floating
point emulation, signed negation of
INT_MIN,
and even
ordinary multiplication and addition. We present a detailed
analysis of examples of each of the four major categories
of overflow. Second, overflow-related issues in C/C++ are
very subtle and we find that even experts get them wrong.
For example, the latest revision of Firefox (as of Sep 1,
2011) contained integer overflows
in the library that was
designed to handle untrusted integers safely
in addition to
overflows in its own code. More generally, we found very
few mature applications that were completely free of integer
numerical errors. This implies that there is probably little
hope of eliminating overflow errors in large code bases
without sophisticated tool support. However, these tools
2
IOC
Table I
E
XAMPLES OF
C/C++
INTEGER OPERATIONS AND THEIR RESULTS
Result
Expression
UINT_MAX+1
0
LONG_MAX+1
undefined
INT_MAX+1
undefined
SHRT_MAX+1
if
INT_MAX>SHRT_MAX,
SHRT_MAX+1
otherwise undefined
char c = CHAR_MAX; c++
varies
1
undefined
2
-INT_MIN
(char)INT_MAX
commonly
-1
1<<-1
undefined
1<<0
1
commonly
INT_MIN
in ANSI C and
1<<31
C++98; undefined in C99 and C++11
2,3
1<<32
undefined
3
1/0
undefined
INT_MIN%-1
undefined in C11,
otherwise undefined in practice
1
The question is: Does
c
get “promoted” to
int
before being incre-
mented? If so, the behavior is well-defined. We found disagreement
between compiler vendors’ implementations of this construct.
2
Assuming that the
int
type uses a two’s complement representation
3
Assuming that the
int
type is 32 bits long
cannot simply distinguish errors from benign operations by
checking rules from the ISO language standards. Rather,
tools will have to use highly sophisticated techniques and/or
rely on manual intervention (e.g., annotations) to distinguish
intentional and unintentional overflows.
II. O
VERFLOW IN
C
AND
C++
Mathematically,
n-bit
two’s complement arithmetic is
congruent, modulo
2
n
, to
n-bit
unsigned arithmetic for
addition, subtraction, and the
n
least significant bits in
multiplication; both kinds of arithmetic “wrap around” at
multiples of
2
n
. On modern processors, integer overflow is
equally straightforward:
n-bit
signed and unsigned opera-
tions both have well-defined behavior when an operation
overflows: the result wraps around and condition code bits
are set appropriately. In contrast, integer overflows in C/C++
programs are subtle due to a combination of complex
and counter-intuitive rules in the language standards, non-
standards-conforming compilers, and the tendency of low-
level programs to rely on non-portable behavior. Table I
contains some C/C++ expressions illustrating cases that arise
in practice. There are several issues; to clarify them we make
a top-level distinction between
well-defined
(albeit perhaps
non-portable) and
undefined
operations.
A. Well-Defined Behaviors
Some kinds of unsigned integer arithmetic uses well-
defined and portable wraparound behavior, with two’s
complement semantics [6]. Thus, as Table I indicates,
UINT_MAX+1
must evaluate to zero in every conforming
C and C++ implementation. nOf course, even well-defined
semantics can lead to logic errors, for example if a developer
na¨vely assumes that
x
+ 1
is larger than
x.
ı
2
is available at http://embed.cs.utah.edu/ioc/
Listing 1.
1
2
3
4
5
6
7
8
9
Source for
overflow.c
referred to in the text
int foo ( int x ) {
return ( x+1 ) > x ;
}
int main
printf
printf
return
}
( void ) {
( " % d \ n " , ( INT_MAX+1 ) > INT_MAX ) ;
( " % d \ n " , foo ( INT_MAX ) ) ;
0;
Many unsigned integer overflows in C and C++ are well-
defined, but
non-portable.
For example
0U-1
is well-defined
and evaluates to
UINT_MAX,
but the actual value of that
constant is
implementation defined:
it can be relied upon, but
only within the context of a particular compiler and platform.
Similarly, the
int
type in C99 is not required to hold values
in excess of 32,767, nor does it have to be based on a two’s
complement representation.
B. Undefined Behaviors
Some kinds of integer overflow are undefined, and these
kinds of behavior are especially problematic. According to
the C99 standard, undefined behavior is
“behavior, upon use of a non-portable or erroneous
program construct or of erroneous data, for which
this International Standard imposes no require-
ments.”
In Internet parlance:
3
“When the compiler encounters [a given undefined
construct] it is legal for it to make demons fly out
of your nose.”
Our experience is that many developers fail to appreciate the
full consequences of this. The rest of this section examines
these consequences.
1) Silent Breakage:
A C or C++ compiler may exploit
undefined behavior in optimizations that silently break a
program. For example, a routine refactoring of Google’s
Native Client software accidentally caused
1<<32
to be
evaluated in a security check.
4
The compiler—at this point
under no particular obligation—simply turned the safety
check into a nop. Four reviewers failed to notice the resulting
vulnerability.
Another illuminating example is the code in Listing 1.
In this program, the same computation ((INT_MAX+1)
>INT_MAX)
is performed twice with two different idioms.
Recent versions of GCC, LLVM, and Intel’s C compiler,
invoked at the
-O2
optimization level, all print a 0 for the
first value (line 6) and a 1 for the second (line 7). In other
words, each of these compilers considers
INT_MAX+1
to
be both larger than
INT_MAX
and also not larger, at the
same optimization level, depending on incidental structural
features of the code. The point is that when programs exe-
cute undefined operations, optimizing compilers may silently
3
http://catb.org/jargon/html/N/nasal-demons.html
4
http://code.google.com/p/nativeclient/issues/detail?id=245
break them in non-obvious and not necessarily consistent
ways.
2) Time Bombs:
Undefined behavior also leads to
time
bombs:
code that works under today’s compilers, but breaks
unpredictably in the future as optimization technology im-
proves. The Internet is rife with stories about problems
caused by GCC’s ever-increasing power to exploit signed
overflows. For example, in 2005 a principal PostgreSQL
developer was annoyed that his code was broken by a recent
version of GCC:
5
It seems that gcc is up to some creative reinterpre-
tation of basic C semantics again; specifically, you
can no longer trust that traditional C semantics of
integer overflow hold ...
This highlights a fundamental and pervasive misunderstand-
ing: the compiler was not “reinterpreting” the semantics but
rather was beginning to take advantage of leeway explicitly
provided by the C standard.
In Section IV-E we describe a time bomb in SafeInt [7]: a
library that is itself intended to help developers avoid unde-
fined integer overflows. This operation,
until recently,
was
reliably compiled by GCC (and other compilers) into code
that did not have observable errors. However, the upcoming
version of GCC (4.7) exposes the error, presumably because
it optimizes the code more aggressively. We discovered this
error using IOC and reported it to the developers, who fixed
it within days [8].
3) Illusion of Predictability:
Some compilers, at some
optimization levels, have predictable behavior for some
undefined operations. For example, C and C++ compil-
ers typically give two’s complement semantics to signed
overflow when aggressive optimizations are disabled. It is,
however, unwise to rely on this behavior, because it is not
portable across compilers or indeed across different versions
of the same compiler.
4) Informal Dialects:
Some compilers support stronger
semantics than are mandated by the standard. For example,
both GCC and Clang (an LLVM-based C/C++/Objective-C
compiler) support a
-fwrapv
command line flag that forces
signed overflow to have two’s complement behavior. In fact,
the PostgreSQL developers responded to the incident above
by adding
-fwrapv
to their build flags. They are now, in
effect, targeting a non-standard dialect of C.
5) Non-Standard Standards:
Some kinds of overflow
have changed meaning across different versions of the
standards. For example,
1<<31
is implementation-defined
in ANSI C and C++98, while being explicitly undefined
by C99 and C11 (assuming 32-bit ints). Our experience is
that awareness of this particular rule among C and C++
programmers is low.
A second kind of non-standardization occurs with con-
structs such as
INT_MIN%-1
which is—by our reading—well
5
http://archives.postgresql.org/pgsql-hackers/2005-12/msg00635.php
3
IOC
Instrumentation
Runtime
B. Overflow Checks
Finding overflows in shift operations is straightforward:
operand values are bounds-checked and then, if the checks
pass, the shift is performed. Checking for overflow in arith-
metic operations is trickier; the problem is that a checked
n-
bit addition or subtraction requires
n+1
bits of precision and
a checked
n-bit
multiplication requires
2n
bits of precision.
Finding these extra bits can be awkward. There are basically
three ways to detect overflow for an operation on two signed
integers
s
1
and
s
2
.
1)
Precondition test.
It is always possible to test whether
an operation will wrap without actually performing the
operation. For example, signed addition will wrap if
and only if this expression is true:
((s
1
>
0)
∧
(s
2
>
0)∧(s
1
>
(INT_MAX
−
s
2
)))∨
((s
1
<
0)
∧
(s
2
<
0)∧(s
1
<
(INT_MIN
−
s
2
)))
In pseudocode:
if (!precondition) then
call failure handler
endif
result = s1 op s2
2)
CPU flag postcondition test.
Most processors contain
hardware support for detecting overflow: following
execution of an arithmetic operation, condition code
flags are set appropriately. In the general case, it is
problematic to inspect processor flags in portable code,
but LLVM supports a number of intrinsic functions
where, for example, an addition operation returns a
structure containing both the result and an overflow
flag. The LLVM backends, then, emit processor-specific
code that accesses the proper CPU flag. In pseudocode:
(result, flag) = s1 checked_op s2
if (flag) then
call failure handler
endif
3)
Width extension postcondition test.
If an integer
datatype with wider bitwidth than the values being
operated on is available, overflow can be detected in
a straightforward way by converting
s
1
and
s
2
into
the wider type, performing the operation, and checking
whether the result is in bounds with respect to the
original (narrower) type. In pseudocode:
result = extend(s1) op extend(s2)
if (result < MIN || result > MAX) then
call failure handler
endif
IOC supports both the precondition test and the CPU flag
postcondition test; width extension seemed unlikely to be
better than these options due to the expense of emulating 64-
bit and 128-bit operations. Initially we believed that the CPU
flag postcondition checks would be far more efficient but this
4
Source
Front End
Checked IR
Back End
Executable
Execution
Figure 1.
Architecture of IOC
defined in ANSI C, C99, C++98, and C++11. However, we
are not aware of a C or C++ compiler that reliably returns
the correct result, zero, for this expression. The problem
is that on architectures including x86 and x86-64, correctly
handling this case requires an explicit check in front of every
%
operation. The C standards committee has recognized the
problem and C11 explicitly makes this case undefined.
III. T
OOL
D
ESIGN AND
I
MPLEMENTATION
IOC, depicted in Fig. 1, has two main parts: a compile-
time instrumentation transformation and a runtime handler.
The transformation is a compiler pass that adds inline
numerical error checks; it is implemented as a
∼1600
LOC
extension to Clang [5], the C/C++ frontend to LLVM [9].
IOC’s instrumentation is designed to be semantically trans-
parent for programs that conform to the C or C++ language
standards, except in the case where a user requests additional
checking for conforming but error-prone operations, e.g.,
wraparound with unsigned integer types. The runtime library
is linked into the compiler’s output and handles overflows
as they occur; it is
∼900
lines of C code.
A. Where to Put the Instrumentation Pass?
The transformation operates on the Abstract Syntax Tree
(AST) late in the Clang front end—after parsing, type-
checking, and implicit type conversions have been per-
formed. This is an appropriate stage for inserting checks
because full language-level type information is available,
but the compiler has not yet started throwing away useful
information as it does during the subsequent conversion into
the flat LLVM intermediate representation (IR).
In a previous iteration of IOC we encoded the required
high-level information into the IR (using IR metadata),
allowing the transformation to be more naturally expressed
as a compiler pass. Unfortunately, this proved to be un-
reliable and unnecessarily complicated, due to requiring a
substantial amount of C-level type information in the IR
in order to support a correct transformation. The original
transformation was further complicated by the lack of a
one-to-one mapping between IR and AST nodes. Also, some
important operations (such as signed to unsigned casts) don’t
exist at the IR level. In short, it is much less error-prone to
do the instrumentation in the frontend where all the required
information is naturally available.
proved not to be the case. Rather, as shown in Section III-D,
using the flag checks has an uneven effect on performance.
The explanation can be found in the interaction between the
overflow checks and the compiler’s optimization passes. The
precondition test generates far too many operations, but they
are operations that can be aggressively optimized by LLVM.
On the other hand, the LLVM intrinsics supporting the flag-
based postcondition checks are recognized and exploited
by relatively few optimization passes, causing much of
the potential performance gain due to this approach to be
unrealized.
C. Runtime Library
To produce informative error messages, IOC logs the
source-code location corresponding to each inserted check,
including the column number where the operator appeared.
(Operating on the AST instead of the LLVM IR makes
such logging possible.) Thus, users can disambiguate, for
example, which shift operator overflowed in a line of code
containing multiple shift operators. Also in service of
readable error messages, IOC logs the types and values of
the arguments passed to the operator; this is important for
operators with multiple modes of failure, such as shift. For
example, an error we found in OpenSSL was reported as:
<lhash.c, (464:20)> : Op: >>, Reason :
Unsigned Right Shift Error: Right operand is negative or is
greater than or equal to the width of the promoted left operand,
BINARY OPERATION: left (uint32): 4103048108 right (uint32): 32
.
Table II
T
AXONOMY OF INTEGER OVERFLOWS IN
C
AND
C++
WITH
REFERENCES TO DETAILED DISCUSSION OF EXAMPLES
intentional
unintentional
undefined behavior
e.g. signed overflow,
shift error,
divide by zero
Type 1:
design error,
may be a “time bomb”
§
IV-C3, IV-C9
Type 3:
implementation error,
may be a “time bomb”
§
IV-C4
defined behavior
e.g. unsigned wrapround,
signed wraparound
with
-fwrapv
Type 2:
no error,
but may not be portable
§
IV-C2, IV-C5, IV-C8
Type 4:
implementation error
§
IV-C1, IV-C6
Based on the value of an environment variable, the IOC
failure handler can variously send its output to
STDOUT,
to
STDERR,
to the syslog daemon, or simply discard the output.
The syslog option is useful for codes that are sensitive to
changes in their
STDOUT
and
STDERR
streams, and for codes
such as daemons that are invoked in execution environments
where capturing their output would be difficult.
Finally, to avoid overwhelming users with error messages,
the fault handler uses another environment variable to spec-
ify the maximum number of times an overflow message from
any particular program point will be printed.
D. Runtime Overhead of Integer Overflow Checking
To evaluate the effect of IOC on programs’ runtime, we
compiled SPEC CPU 2006 in four ways. First, a baseline
compilation using Clang with optimization options set for
maximum performance. Second, checking for undefined
integer overflows (shifts and arithmetic) using precondition
checks. Third, checking for undefined integer overflows
(shifts and arithmetic) using the CPU flag postcondition
test. Finally, checking for all integer overflows including
unsigned overflow and value loss via sign conversion and
truncation.
We then ran the benchmarks on a 3.4 GHz AMD Phe-
nom II 965 processor, using their “ref” inputs—the largest
input data, used for reportable SPEC runs—five times and
5
used the median runtime. We configured the fault handler to
return immediately instead of logging overflow behaviors.
Thus, these measurements do not include I/O effects due
to logging, but they do include the substantial overhead of
marshaling the detailed failure information that is passed to
the fault handler.
For undefined behavior checking using precondition
checks, slowdown relative to the baseline ranged from
−0.5%–191%.
In other words, from a tiny accidental
speedup to a 3X increase in runtime. The mean slowdown
was
44%.
Using flag-based postcondition checks, slowdown
ranged from
0.4%–95%,
with a mean of
30%.
However,
the improvement was not uniform: out of the 21 benchmark
programs, only 13 became faster due to the IOC implementa-
tion using CPU flags. Full integer overflow checking using
precondition checks incurred a slowdown of
0.2%–195%,
with a mean of
51%.
IV. I
NTEGER
O
VERFLOW
S
TUDY
This section presents the qualitative and quantitative re-
sults of our study of overflow behaviors in C and C++
applications.
A. Limitations of the Study
There are necessarily several limitations in this kind of
empirical study. Most important, because IOC is based on
dynamic checking, bugs not exercised by our inputs will
not be found. In this sense, our results likely understate the
prevalence of integer numerical errors as well as the preva-
lence of intentional uses of wraparound in these programs.
A stress testing strategy might uncover more bugs.
Second, our methodology for distinguishing intentional
from unintentional uses of wraparound is manual and sub-
jective. The manual effort required meant that we could only
study a subset of the errors: we focused on the errors in the
SPEC CINT2000 benchmarks for these experiments. For the
other experiments, we study a wider range of programs.
B. A Taxonomy for Overflows
Table II summarizes our view of the relationship between
different integer overflows in C/C++ and the correctness of

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin