Arithmetic overflow

The Arithmetic overflow ( English arithmetic overflow ) or counter overflow (engl. Counter overflow ) is a term used in computer science . Such an overflow occurs when the result of a calculation for the valid range of numbers is too large to be interpreted correctly.

Usually you will encounter the overflow when calculating with two's complement numbers. So it may happen that in the addition of two numbers with the same sign creates a number with a different label. In this case the processor sets the overflow bit . With some processors and programming an overflow, by a runtime error or exception handling ( Exception are collected).

The overflow always depends on the number representation used. He is by no means the transfer (Engl. Carry ) to be confused.

Integer overflow

An integer overflow (Engl. Integer overflow ) occurs when a computer calculations with a limited number of places performs, requiring the calculation result to display more digits.

The number of digits and thus the range of values is limited by the arithmetic unit . The arithmetic unit of today's computers is usually designed for 32 or 64 binary digits . If an integer overflow occurs here, this is registered in the status register of the processor; this case can be determined by the programmer.

Another case is when a calculation result is stored in a variable that has fewer digits than the arithmetic unit. This case is not automatically recognized by the processor, the variable receives an incorrect value.

Only by using function libraries is it possible to perform calculations with millions of digits without reaching an integer overflow.

An example from the C programming language : The unsigned char data type usually comprises 8 bits and has a range of values from 0 to 255.

unsigned char a = 255;
unsigned char b = 2;
unsigned char Ergebnis = a + b;

The associated dual calculation illustrates the integer overflow:

  11111111 (a)
+ 00000010 (b)
----------
 100000001 (Ergebnis)

The first one, the ninth bit, is not contained in the 8 bits of the selected data type. If you only look at these last 8 bits, you get 00000001 , ie 1 and not 257. Even if the numerical values are already fixed when the program code is compiled , some C compilers ignore these overflows, which leads to incorrect results. The data type should therefore always be selected to be sufficiently large.

In the case of platform-independent programming, the integer overflow should not be used deliberately, since the value range of the data types and thus the point of overflow can be different on the target systems.

Example: 32 bit integer

The commonly used on 32-bit processors, integer data type Integer can be in two's the values -2 ³¹ = -2147483648 to + (2 ³¹ represent) -1 = +2,147,483,647. If one is now added to +2,147,483,647 ( binary 01111111 11111111 11111111 11111111), the result is not +2,147,483,648, as expected, but –2,147,483,648, since the binary value 10000000 00000000 00000000 00000000 is interpreted as a negative number. Such an overflow is also the cause of the year 2038 problem .

Example: 4 bits in two's complement

In two's positive and negative numbers are displayed, so that the subtraction can be attributed to the addition. There are 3 cases to consider:

Adding two positive numbers	Addition of negative numbers with overflow	Adding negative numbers without overflow
${\ displaystyle {{\ begin {matrix} \ & {\} _ {\} & 0 _ {\} & 1 _ {\} & 0 _ {\} & 1 &&& 5_ {10} \\ + & {\} _ {\} & 0 _ {\ color {Red} 1} & 1 _ {\} & 0 _ {\ color {Red} 1} & 1 &&& 5_ {10} \ end {matrix}} \ over {\ begin {matrix} \ quad & {(0)} _ {\} & 1_ { \} & 0 _ {\} & 1 _ {\} & 0 _ {\} &&& - 6_ {10} \ end {matrix}}}}$	${\ displaystyle {{\ begin {matrix} \ & {\} _ {\} & 1 _ {\} & 0 _ {\} & 1 _ {\} & 1 &&& - 5_ {10} \\ + & {\} _ {\ color {Red } 1} & 1 _ {\} & 0 _ {\ color {Red} 1} & 1 _ {\ color {Red} 1} & 1 &&& - 5_ {10} \ end {matrix}} \ over {\ begin {matrix} \ quad & {( 1)} _ {\} & 0 _ {\} & 1 _ {\} & 1 _ {\} & 0 _ {\} &&& 6_ {10} \ end {matrix}}}}$	${\ displaystyle {{\ begin {matrix} \ & {\} _ {\} & 1 _ {\} & 1 _ {\} & 1 _ {\} & 1 &&& - 1_ {10} \\ + & {\} _ {\ color {Red } 1} & 1 _ {\ color {Red} 1} & 1 _ {\ color {Red} 1} & 0 _ {\ color {Red} 1} & 1 &&& - 3_ {10} \ end {matrix}} \ over {\ begin {matrix} \ quad & {(1)} _ {\} & 1 _ {\} & 1 _ {\} & 0 _ {\} & 0 _ {\} &&& - 4_ {10} \ end {matrix}}}}$

All numbers that can be represented in 4 bits as a circle; one adds z. B. 5 and 5, you look for the displayed 5 and continue clockwise 5 units, the circle "overflows" and you end up at −6.

generalization

surgery	correct result	Overflow
A + B	${\ displaystyle c_ {n} = 0, c_ {n-1} = 0}$	${\ displaystyle c_ {n} = 0, c_ {n-1} = 1}$
A - B	${\ displaystyle c_ {n} = c_ {n-1}}$	not possible
-A - B	${\ displaystyle c_ {n} = 1, c_ {n-1} = 1}$	${\ displaystyle c_ {n} = 1, c_ {n-1} = 0}$

You always have to look at the last two transfers, named here and . If these are not equal, then the result is wrong, as the result of an overflow. This can never be the case when adding a positive and a negative number. ${\ displaystyle c_ {n}}$ ${\ displaystyle c_ {n-1}}$

Inference

In a 4-bit architecture using two's complement, e.g. B. the decimal number 10 cannot be mapped as dual.

Some processors can register an overflow with an overflow bit.

hazards

Integer overflows can indirectly pose a security problem if they are part of a program bug. In particular if the incorrect calculation is used to determine the size of a buffer or concerns the addressing of a field . This can then result in buffer overflows or allow an attacker to overwrite the stack .

The so-called signedness bug is a special case . It occurs when a signed integer ( signed ) is interpreted as a nonnegative number ( unsigned ).

Often, integer overflows also cause serious consequences because they cannot be detected after they occur. Such faulty places are therefore difficult to find in the program code.

literature

Blexim: Basic Integer Overflows . In: Phrack magazine . 11, No. 60, February 2002

Individual evidence

↑ However, this is not required by the C standard. That is why there are also systems and associated C compilers in which a char or unsigned char has a different number of bits and therefore a different value range. See http://stackoverflow.com/questions/5516044/system-where-1-byte-8-bit
↑ Fricke, Klaus. Digital technology: text and exercise book for electrical engineers and computer scientists. 5th edition Vieweg + Teubner, 2007. Print, page 9.

[1] However, this is not required by the C standard. That is why there are also systems and associated C compilers in which a char or unsigned char has a different number of bits and therefore a different value range. See http://stackoverflow.com/questions/5516044/system-where-1-byte-8-bit

[2] Fricke, Klaus. Digital technology: text and exercise book for electrical engineers and computer scientists. 5th edition Vieweg + Teubner, 2007. Print, page 9.