Integer overflow

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 or a signed integer. Most commonly, signed integers are represented in two's complement format, where the high-order bit is interpreted as the sign.
For example, in a 32-bit word, an unsigned integer has a value from 0 to 2³²-1 = 4294967295, while a signed integer has a value from -2³¹=-2147483648 to 2³¹-1=2147483647.
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 2^W, 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 and digital signal processors 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 the following operation will have an invalid result:. Likewise, a binary system limited to 4 positions 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.

Bits	Alias	Range	Signed Range	Unsigned Range
8-bit	byte, sbyte, octet	2⁸ − 1	-128	0
8-bit	byte, sbyte, octet	2⁸ − 1	127	255
16-bit	word, short, int16, uint16	2¹⁶ − 1	−32,768	0
16-bit	word, short, int16, uint16	2¹⁶ − 1	32,767	65,535
32-bit	int32, uint32	2³² − 1	-2,147,483,648	0
32-bit	int32, uint32	2³² − 1	2,147,483,647	4,294,967,295
64-bit	int64, uint64	2⁶⁴ − 1	−9,223,372,036,854,775,808	0
64-bit	int64, uint64	2⁶⁴ − 1	9,223,372,036,854,775,807	18,446,744,073,709,551,615
128-bit	int128, uint128	2¹²⁸ − 1	−170,141,183,460,469,231,731,687,303,715,884,105,728	0
128-bit	int128, uint128	2¹²⁸ − 1	170,141,183,460,469,231,731,687,303,715,884,105,727	340,282,366,920,938,463,463,374,607,431,768,211,455

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.
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.

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, e.g., 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 2^W, 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, in the language Rust, while functionality is provided to give users choice and control, the behavior for basic use of mathematic operators is naturally fixed; however, this fixed behavior differs between a program built in 'debug' mode and one built in 'release' mode. In C, unsigned integer overflow is defined to wrap around, while signed integer overflow causes undefined behavior.

Methods to address integer overflow problems

Detection

Run-time overflow detection implementation UBSan 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 developed the As-if Infinitely Ranged integer model, a largely automated mechanism to eliminate integer overflow and truncation in C/C++ using run-time error handling.

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, or after it. 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.