Integer overflow: Difference between revisions

Revision as of 20:13, 13 July 2016

Revision as of 09:59, 26 August 2016

Line 1:

{{merge|Arithmetic overflow|discuss=Talk:integer_overflowinteger overflow#Merger proposal|date=September 2015}}

[[Image:Odometer rollover.jpg|thumb|250px|[[Odometer]] rollover, a mechanical form of integer overflow. All digits are set to the maximum 9 and the next increment of the white digit 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. This is ''wrapping'' asin opposedcontrast to ''saturating''.]]

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 instanceexample, taking the arithmetic mean of two numbers by adding them and dividing by two, as done in many [[search algorithm]]s, causes error if the sum (although not the resulting mean) is too large to be represented, and hence overflows.<ref>[http://googleresearch.blogspot.co.uk/2006/06/extra-extra-read-all-about-it-nearly.html Google Research blog: Nearly All Binary Searches and Mergesorts are Broken, Joshua Bloch, 2 June 2006]</ref> 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 [[Graphicsgraphics processing unit|GPU]]s (GPUs) and [[Digitaldigital signal processor|DSP]]s (DSPs), the result [[saturation arithmetic|saturates]]; that is, once the maximum value is reached, any attempt to increase it always returns the maximum integer value.

== Origin ==

Line 15:

* 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 programming language [[C (programming language)|C programming language]], [[Signed number representations|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 thea factcase where, 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.

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

Line 38:

| [[Java (programming language)|Java]] || NA || ignored

|-

| [[Python (programming language)|Python 2]] 2 || NA || convert to long

|-

| [[Seed7]] || NA || <tt>'''raise''' OVERFLOW_ERROR</tt><ref>[http://seed7.sourceforge.net/manual/errors.htm#OVERFLOW_ERROR Seed7 manual], section 15.2.3 OVERFLOW_ERROR.</ref>

Line 46:

| [[Smalltalk]] || NA || convert to LargeInteger

|-

| [[Swift (programming language)|Swift]] || colspan="2 | Causes error unless using special overflow operators.<ref>The Swift Programming Language. Swift 2.1 Edition. October 21, 2015.</ref>

|-

|}

Line 52:

In some situations, a program may make the assumption that a variable always contains a positive value. If the variable has a [[Signed number representations|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.

==TechniquesMethods forto mitigatingmitigate integer overflow problems==

Programming languages implement various mitigation techniquesmethods against an accidental overflow: [[Ada (programming language)|Ada]], [[Seed7]] (and certain variants of functional languages), trigger an exception condition on overflow, while [[Python (programming language)|Python]] (since 2.4) seamlessly converts internal representation of the number to match its growth, eventually representing it as <code>long</code> whosewhich capabilityability is only limited by the available memory.<ref>[https://docs.python.org/2/reference/expressions.html Python documentation], section 5.1 Arithmetic conversions.</ref>

Run-time overflow detection implementation <code>AddressSanitizer</code> is also available for [[C compiler]]s.

Line 59:

{{Main article|AddressSanitizer}}

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

* [[Computer emergency response team|CERT]] (CERT) As-if Infinitely Ranged (AIR) integer model - a largely automated mechanism forto eliminatingeliminate integer overflow and integer truncation <ref>[http://www.cert.org/archive/pdf/09tn023.pdf As-if Infinitely Ranged Integer Model]</ref>

In languages with native support for [[Arbitrary-precision arithmetic]] and [[type safety]] (such as [[Python (programming language)|Python]] or [[Common Lisp]]), numbers are promoted to a larger size automatically when overflows occur, or exceptions thrown (conditions signaled) when a range constraint exists. Using such languages may thus be helpful to mitigate this issue. InHowever, in some such languages, situations are however still possible where an integer overflow couldcan 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 (fixnum) [http://www.lispworks.com/documentation/HyperSpec/Body/d_type.htm] and lower the type safety level to zero [http://www.lispworks.com/documentation/HyperSpec/Body/d_optimi.htm] for a particular code block.<ref name="reddy">{{cite web

| url = http://random-state.net/features-of-common-lisp.html

| title = Features of Common Lisp

| first = Abhishek | last = Reddy

| date = 2008-08-22

}}</ref><ref>{{Cite book|authorlink=Benjamin C. Pierce |last=Pierce |first=Benjamin C. |title=Types and Programming Languages |publisher=MIT Press |year=2002 |isbn=0-262-16209-1 |url=http://www.cis.upenn.edu/~bcpierce/tapl/}}</ref><ref>{{Cite journal|last=Wright |first=Andrew K. |author2=[[Matthias Felleisen]] |title=A Syntactic Approach to Type Soundness |journal=Information and Computation |volume=115 |issue=1 |pages=38–94 |year=1994 |url=http://citeseer.ist.psu.edu/wright92syntactic.html |doi=10.1006/inco.1994.1093}}</ref><ref>{{Cite journal|first=Stavros |last=Macrakis |title=Safety and power |journal=ACM SIGSOFT Software Engineering Notes |volume=7 |issue=2 |pages=25–26 |date=April 1982 |url=http://portal.acm.org/citation.cfm?id=1005937.1005941 |format=requires subscription |doi=10.1145/1005937.1005941}}</ref>

In Java 8, there are overloaded methods, for example like Math#addExact(),<ref>[https://docs.oracle.com/javase/8/docs/api/java/lang/Math.html#addExact-int-int- Math#addExact()],</ref> 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.<ref>{{cite news |title= F.A.A. Orders Fix for Possible Power Loss in Boeing 787 |work= [[New York Times]] |date= 30 April 2015 |url= http://www.nytimes.com/2015/05/01/business/faa-orders-fix-for-possible-power-loss-in-boeing-787.html?_r=0}}</ref> The [[European Aviation Safety Agency]] followed on 4 May 2015.<ref>{{cite web |url= http://ad.easa.europa.eu/ad/US-2015-09-07 |work= Airworthiness Directives |title= US-2015-09-07 : Electrical Power - Deactivation |date= {{date|2015-05-04}} |publisher= [[European Aviation Safety Agency]]}}</ref> The error happens after 2³¹ centiseconds ({{#expr:2^31/100/3600/24}} days), indicating a 32 -bit [[Signed number representations|signed]] [[Integer (computer science)|integer]].

It is impossible to progress past level 22 ofIn the arcade game ''[[Donkey Kong]]'', becauseit ofis impossible to advance past level 22 due to an integer overflow in its time/bonus. ''DonkeyThe Kong''game takes the level number you'rea user is on, multiplies it by 10 and adds 40. When youthey 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 longtoo enoughshort to completefinish the level.

In ''[[Donkey Kong Jr. Math]]'', when you trytrying to calculate a number over 10000, it shows only shows the first 4 digits.

==See also==

Line 92:

==References==

{{reflistReflist}}

==External links==