In computer programming, an integer overflow occurs when an arithmetic
operation attempts to create a numeric value that is too large to be
represented within the available storage space. For instance, taking the
arithmetic mean of two numbers by adding them and dividing by two, as done in
many search algorithms, causes error if the sum is too large to be represented,
and hence overflows. The most common result of an overflow is that the least
significant representable bits of the result are stored; the result is said to
wrap. On some processors like GPUs and DSPs, the result saturates; that is,
once the maximum value is reached, any attempt to increase it always returns
the maximum integer value. Origin
The register width of a processor determines the range of values that can
be represented. Typical binary register widths include:
8 bits: maximum representable value 28 − 1 = 255
16 bits: maximum representable value 216 − 1 = 65,535
32 bits: maximum representable value 232 − 1 = 4,294,967,295,
64 bits: maximum representable value 264 − 1 = 18,446,744,073,709,551,615,
128 bits: maximum representable value 2128 − 1 =
,920,938,463,463,374,607,431,768,211,455 Since an arithmetic operation may
produce a result larger than the maximum representable value, a potential error
condition may result. In the C programming language, signed integer
overflow causes undefined behavior, while unsigned integer overflow causes
the number to be reduced modulo a power of two, meaning that unsigned integers
"wrap around" on overflow. This "wrap around" is the cause of the famous
"Split Screen" in Pac-Man. A "wrap around" corresponds to the fact, that
e.g. if the addition of two positive integers produces an overflow, it may
result in an unexpected result. For example with unsigned 32 bit integers,
4000000000u + 1000000000u = 705032704u. In computer graphics or signal
processing, it is typical to work on data that ranges from 0 to 1 or from −1
to 1. An example of this is a grayscale image where 0 represents black, 1
represents white, and values in-between represent varying shades of gray. One
operation that one may want to support is brightening the image by multiplying
every pixel by a constant. Saturated arithmetic allows one to just blindly
multiply every pixel by that constant without worrying about overflow by just
sticking to a reasonable outcome that all these pixels larger than 1 just
become white and all values "darker than black" just become black.
Security ramifications In some situations, a program may make
the assumption that a variable always contains a positive value. If the
variable has a signed integer type, an overflow can cause its value to wrap and
become negative. This overflow violates the program's assumption and may lead to
unintended behavior. Similarly, subtracting from a small unsigned value
may cause it to wrap to a large positive value which may also be an unexpected
behavior. Multiplying or adding two integers may result in a value that is
non-negative, but unexpectedly small. If this number is used as the number of
bytes to allocate for a buffer, the buffer will be allocated unexpectedly
small, leading to a potential buffer overflow.
Techniques for mitigating integer overflow problems
Programming languages implement various mitigation techniques against an
accidental overflow: Ada, Seed7, trigger an exception condition on overflow,
while Python seamlessly converts internal representation of the number to
match its growth, eventually representing it as long whose capability
is only limited by the available memory. Run-time overflow detection
implementation AddressSanitizer is also available for C compilers.
List of techniques and methods that might be used to mitigate the
consequences of integer overflow: The effects of integer-based attacks for
C/C++ and how to defend against them by using subtyping in Efficient and
Accurate Detection of Integer-based Attacks.
CERT As-if Infinitely Ranged integer model - a largely automated mechanism
for eliminating integer overflow and integer truncation As-if Infinitely
Ranged Integer Model In languages with native support for
Arbitrary-precision arithmetic and type safety, numbers are promoted to a larger
size automatically when overflows occur, or exceptions thrown when a range
constraint exists. Using such languages may thus be helpful to mitigate this
issue. In some such languages, situations are however still possible
where an integer overflow could occur. An example is explicit optimization of a
code path which is considered a bottleneck by the profiler. In the case
of Common Lisp, this is possible by using an explicit declaration to
type-annotate a variable to a machine-size word [1] and lower the type
safety level to zero [2] for a particular code block.
In Java 8, there are overloaded methods, for example like Math#addExact(), which
will throw ArithmeticException in case of overflow.
Example On 30 April 2015, the Federal Aviation
Authority announced it will order Boeing 787 operators to reset its electrical
system periodically, to avoid an integer overflow which could lead to loss of
electrical power and ram air turbine deployment, and Boeing is going to
deploy a software update in the fourth quarter. The European Aviation Safety
Agency followed on 4 May 2015. The error happens after 2³¹ centiseconds,
indicating a 32 bit signed integer. When Donkey Kong breaks on level 22 it
is because of an integer overflow in its time/bonus. Donkey Kong takes the level
number you're on, multiplies it by 10 and adds 40. When you reach level 22 the
time/bonus number is 260 which is too large for its 8-bit 256 value register
so it resets itself to 0 and gives the remaining 4 as the time/bonus - not long
enough to complete the level. See also
Arithmetic underflow Arithmetic overflow
SIGFPE Buffer overflow
Heap overflow Stack buffer overflow
Pointer swizzling Software testing
Static code analysis References
External links Phrack #60, Basic Integer Overflows
Phrack #60, Big Loop Integer Protection How to implement efficiently in C
WASC Threat Classification - Integer Overflows
Understanding Integer Overflow in C/C++