In computer programming, an integer overflow occurs when an arithmetic operation on integers attempts to create a numeric value that is outside of the range that can be represented in the space allocated for the result – either higher than the maximum or lower than the minimum representable value.
Most integer arithmetic in modern computation uses binary representation of integers, though decimal representation also exists. This article will focus on binary representation, though similar considerations hold in the other case.
An integer represented as a bit-pattern in a computer can be interpreted as either an unsigned integer (whose value can be from 0 up to some maximum) or a signed integer (whose value can be positive or negative). Most commonly, signed integers are represented in two's complement format, where the high-order bit is interpreted as the sign (0 for +, 1 for −). For example, in a 32-bit word, an unsigned integer has a value from 0 to , while a signed integer has a value from to .
Integer overflow results in a stored value which is different from the mathematical value indicated by the operation which was performed. Most commonly, the resulting bit-pattern is the same as if the operation was performed modulo 2W, where W is the word size in bits. The operation also sets or unsets one or more flags that indicate whether overflow has occurred. On some processors like graphics processing units (GPUs) and digital signal processors (DSPs) which support saturation arithmetic, overflowed results may be clamped, i.e. set to the minimum value in the representable range if the result is below the minimum and set to the maximum value in the representable range if the result is above the maximum.
If it is not anticipated by the programmer, integer overflow can negatively impact a program's reliability and security.
Origin Integer overflow occurs when an arithmetic operation on integers attempts to create a numeric value that is outside of the range that can be represented with a given number of digits. In the context of computer programming, the integers are binary, but any positional numeral system can have an invalid result of an arithmetic operation if positions are confined. As shown in the odometer example, using the decimal system, with the constraint of 6 positions (digits) the following operation will have an invalid result: . Likewise, a binary system limited to 4 positions (bits) will have an invalid result for the following operation: . For both examples the results will have a value exceeding the range that can be represented by the constraints. Another way to look at this problem is that the most significant position's operation has a carry requiring another position/digit/bit to be allocated, breaking the constraints.
All integers in computer programming have constraints of a max value and min value. The primary factors for determining the range is the allocation of bits and if it is signed or unsigned. The standard integer depends on the platform and programming language. Additional integer representation can be less than or greater than standard. Examples are the short integer and long integer respectively. Even arbitrary-precision exists, but would be limited by pre-set precision or available system memory.
+ Typical integer boundaries Bits Alias Range Signed range Unsigned range 8-bit byte, sbyte, octet 28 − 1 16-bit word, short, int16, uint16 216 − 1 32-bit int32, uint32 232 − 1 64-bit int64, uint64 264 − 1 128-bit int128, uint128 2128 − 1
When an unsigned arithmetic operation produces a result larger than the maximum above for an N-bit integer, an overflow reduces the result to modulo N-th power of 2, retaining only the least significant bits of the result and effectively causing a wrap around.
In particular, multiplying or adding two integers may result in a value that is unexpectedly small, and subtracting from a small integer may cause a wrap to a large positive value (for example, 8-bit integer addition results in 1, which is , and similarly subtraction results in 255, a two's complement representation of −1).
Such wrap around may cause security detriments—if an overflowed value is used as the number of bytes to allocate for a buffer, the buffer will be allocated unexpectedly small, potentially leading to a buffer overflow which, depending on the use of the buffer, might in turn cause arbitrary code execution.
If the variable has a signed integer type, a program may make the assumption that a variable always contains a positive value. An integer overflow can cause the value to wrap and become negative, which violates the program's assumption and may lead to unexpected behavior (for example, 8-bit integer addition of results in −128, a two's complement of 128). (A solution for this particular problem is to use unsigned integer types for values that a program expects and assumes will never be negative.)
Flags Most modern computers have dedicated processor flags that are set on overflow by addition and subtraction operations.
The carry flag is set when the result of an addition or subtraction, considering the operands and result as unsigned numbers, does not fit in the given number of bits. This indicates an overflow with a carry or borrow from the most significant bit.
The overflow flag is set when the result of an addition or subtraction on signed numbers does not have the sign that one would predict from the signs of the operands, for example, a negative result when adding two positive numbers. This indicates that an overflow has occurred and the signed result represented in two's complement form would not fit in the given number of bits. For an ADD instruction, this means that the carry into the sign bit was different from the carry out of the sign bit.
Definition variations and ambiguity For an unsigned type, when the ideal result of an operation is outside the type's representable range and the returned result is obtained by wrapping, then this event is commonly defined as an overflow. In contrast, the C standard defines that this event is not an overflow and states "a computation involving unsigned operands can never overflow." The explanation is that the standard defines arithmetic with unsigned integers to be arithmetic modulo 2W, where W is the word size, which is mathematically well-defined and only has representable values.
When the ideal result of an integer operation is outside the type's representable range and the returned result is obtained by clamping, then this event is commonly defined as a saturation. Use varies as to whether a saturation is or is not an overflow. To eliminate ambiguity, the terms wrapping overflow and saturating overflow can be used.
The case of an integer operation producing a value less than the smallest representable value is sometimes called integer underflow, though most commonly it is known as a type of overflow. This usage is quite different from floating-point underflow, which refers to a floating-point value that is too close to 0.
Inconsistent behavior The behavior on occurrence of overflow may not be consistent in all circumstances. For example, the Rust programming language allows the programmer to specify particular overflow behavior, but the default arithmetic operators differ depending on the build mode: overflow is trapped in 'debug' mode, but silently wraps modulo 2W in 'release' mode. In C, unsigned integer overflow is defined to wrap around, while signed integer overflow is undefined behavior.
Methods to address integer overflow problems + Integer overflow handling in various programming languages Language Unsigned integer Signed integer Ada modulo the type's modulus raise Constraint_Error C, C++ modulo power of two undefined behavior C# modulo power of 2 in unchecked context; System.OverflowException is raised in checked context Java modulo power of two (char is the only unsigned primitive type in Java) modulo power of two JavaScript all numbers are double-precision floating-point except BigInt MATLAB Built-in integers saturate. Fixed-point integers configurable to wrap or saturate Python 2 convert to long type (bigint) Scheme convert to bigNum Simulink configurable to wrap or saturate Smalltalk convert to LargeInteger Swift Causes error unless using special overflow operators.The Swift Programming Language. Swift 2.1 Edition. October 21, 2015.
Detection Run-time overflow detection implementation UBSan (undefined behavior sanitizer) is available for C compilers.
In Java 8, there are overloaded methods, for example , which will throw an in case of overflow.
Computer Emergency Response Team (CERT) of the Software Engineering Institute at Carnegie Mellon University developed the As-if Infinitely Ranged (AIR) integer model, a largely automated mechanism to eliminate integer overflow and truncation in C/C++ using run-time error handling.As-if Infinitely Ranged Integer Model
Avoidance By allocating variables with data types that are large enough to contain all values that may possibly be computed and stored in them, it is always possible to avoid overflow. Even when the available space or the fixed data types provided by a programming language or environment are too limited to allow for variables to be defensively allocated with generous sizes, by carefully ordering operations and checking operands in advance, it is often possible to ensure a priori that the result will never be larger than can be stored. Static analysis tools, formal verification and design by contract techniques can be used to more confidently and robustly ensure that an overflow cannot accidentally result.
Handling If it is anticipated that overflow may occur, then tests can be inserted into the program to detect when it happens, or is about to happen, and do other processing to mitigate it. For example, if an important result computed from user input overflows, the program can stop, reject the input, and perhaps prompt the user for different input, rather than the program proceeding with the invalid overflowed input and probably malfunctioning as a consequence.
CPUs generally have a way to detect this to support addition of numbers larger than their register size, typically using a status bit. The technique is called multiple-precision arithmetic. Thus, it is possible to perform byte-wide addition on operands wider than a byte: first add the low bytes, store the result and check for overflow; then add the high bytes, and if necessary add the carry from the low bytes, then store the result.
Handling possible overflow of a calculation may sometimes present a choice between performing a check before a calculation (to determine whether or not overflow is going to occur), or after it (to consider whether or not it likely occurred based on the resulting value). Since some implementations might generate a trap condition on integer overflow, the most portable programs test in advance of performing the operation that might overflow.
Programming language support Programming languages implement various mitigation methods against an accidental overflow: Ada and certain variants of functional languages trigger an exception condition on overflow, while Python (since 2.4) seamlessly converts internal representation of the number to match its growth, eventually representing it as long – whose ability is only limited by the available memory.Python documentation, section 5.1 Arithmetic conversions.