Integer overflow: Difference between revisions

Revision as of 18:39, 10 June 2012

Revision as of 18:39, 10 June 2012

Line 1:

[[Image:Odometer_rollover.jpg|thumb|250px|[[Odometer]] rollover, a mechanical form of integer overflow. All digits are set to the maximum 9, and adding 1 causes a cascade of carry-over additions setting all digits to 0 but there is no higher digit to change to a 1, so the counter resets to zero.]]

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, adding 1 to the largest value that can be represented constitutes an integer overflow. The most common result in these cases is for the least significant representable bits of the result to be stored (the result is said to ''wrap''). On some processors like [[Graphics processing unit|GPU]]s and [[Digital signal processor|DSP]]s, the result [[saturation arithmetic|saturates]]; that is, once the maximum value is reached, attempts to make it larger simply return the maximum result.

== Origin ==

The [[register width]] of a processor determines the range of values that can be represented. Typical [[Binary numeral system|binary]] register widths include:

: 8 bits: maximum representable value 2⁸ − 1 = 255

: 16 bits: maximum representable value 2¹⁶ − 1 = 65,535

: 32 bits: maximum representable value 2³² − 1 = 4,294,967,295 (the most common width for personal computers {{As of|2005|lc=on}}),

: 64 bits: maximum representable value 2⁶⁴ − 1 = 18,446,744,073,709,551,615

: 128 bits: maximum representable value 2¹²⁸ − 1 = 340,282,366,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)|C programming language]], signed integer overflow causes [[undefined behavior]], while unsigned integer overflow causes the number to be reduced [[modular arithmetic|modulo a power of two]], meaning that unsigned integers "wrap around" on overflow. This "wrap around" is the cause of the famous "[[kill screen|Split Screen]]" in Pac-Man.<ref>{{cite web|url=http://home.comcast.net/~jpittman2/pacman/pacmandossier.html|title=The Pac-Man Dossier|author=Pittman, Jamey}}</ref>

A "wrap around" corresponds to the fact, that e.g. if the addition of two positive integers produces an overflow, it may result in a negative number. In counting, one just starts over again from the bottom.

Example: 16 bit signed integer: 30000 + 30000 = −5536.

<!-- Diagram that illustrates wrapping behavior of integer representation. -->

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 (i.e. [[high dynamic range imaging|"brighter than white"]]) 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.

Some languages, such as [[Ada (programming language)|Ada]] (and certain variants of functional languages), provide mechanisms to make accidental overflows trigger an exception condition. In contrast, [[Python (programming language)|Python]] seamlessly converts a number that becomes too large for an integer to a long.<ref>[http://www.python.org/doc/1.4/ref/ref5.html Python documentation], section 5.1 Arithmetic conversions.</ref> (This occurred in Python 2.4.)<ref>[http://www.python.org/dev/peps/pep-0237/ Python Enhancement Proposal 237]</ref>

==Techniques for mitigating integer overflow problems==

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 [http://www.cs.cmu.edu/~dbrumley/pubs/integer-ndss-07.pdf Efficient and Accurate Detection of Integer-based Attacks].

* [[CERT]] As-if Infinitely Ranged (AIR) integer model - a largely automated mechanism for eliminating integer overflow and integer truncation [http://www.cert.org/archive/pdf/09tn023.pdf As-if Infinitely Ranged Integer Model]

==See also==

*[[Arithmetic overflow]]

*[[SIGFPE]]

*[[Buffer overflow]]

*[[Heap overflow]]

*[[Stack buffer overflow]]

*[[Pointer swizzling]]

*[[Software testing]]

*[[Static code analysis]]

==References==

{{reflist}}

==External links==

*[http://www.phrack.org/issues.html?issue=60&id=10#article Phrack #60, Basic Integer Overflows]

*[http://www.phrack.org/issues.html?issue=60&id=9#article Phrack #60, Big Loop Integer Protection]

*[http://thetaeng.com/TimerWrap.htm How to implement efficiently in C]

*[http://projects.webappsec.org/Integer-Overflows WASC Threat Classification - Integer Overflows]

[[Category:Software bugs]]

[[Category:Computer security exploits]]

[[de:Ganzzahlüberlauf]]

[[fr:Dépassement d'entier]]

[[he:גלישה נומרית]]

[[pl:Przekroczenie zakresu liczb całkowitych]]