Integer overflow

From Wikipedia, the free encyclopedia
Jump to: navigation, search
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 GPUs and DSPs, the result saturates; that is, once the maximum value is reached, attempts to make it larger simply return the maximum result.

Origin[edit]

The register width of a processor determines the range of values that can be represented. Typical binary register widths include:

8 bits: maximum representable value 28 − 1 = 255
16 bits: maximum representable value 216 − 1 = 65,535
32 bits: maximum representable value 232 − 1 = 4,294,967,295 (the most common width for personal computers as of 2005),
64 bits: maximum representable value 264 − 1 = 18,446,744,073,709,551,615 (the most common width for personal computers, but not necessarily their operating systems, as of 2012),
128 bits: maximum representable value 2128 − 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, signed integer overflow causes undefined behavior, while unsigned integer overflow causes the number to be reduced modulo a power of two, meaning that unsigned integers "wrap around" on overflow. This "wrap around" is the cause of the famous "Split Screen" in Pac-Man.[1] A "wrap around" corresponds to the fact, 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.

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. "brighter than white") just become white and all values "darker than black" just become black.

Security ramifications[edit]

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 (and certain variants of functional languages), provide mechanisms to make accidental overflows trigger an exception condition. In contrast, Python seamlessly converts a number that becomes too large for an integer to a long.[2] (This occurred in Python 2.4.)[3]

Techniques for mitigating integer overflow problems[edit]

List of techniques and methods that might be used to mitigate the consequences of integer overflow:

In languages with native support for Arbitrary-precision arithmetic and type safety (such as 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. In some such languages, situations are however still possible where an integer overflow could 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) [1] and lower the type safety level to zero [2] for a particular code block.[4][5][6][7]

See also[edit]

References[edit]

  1. ^ Pittman, Jamey. "The Pac-Man Dossier". 
  2. ^ Python documentation, section 5.1 Arithmetic conversions.
  3. ^ Python Enhancement Proposal 237
  4. ^ Reddy, Abhishek (2008-08-22). "Features of Common Lisp". 
  5. ^ Pierce, Benjamin C. (2002). Types and Programming Languages. MIT Press. ISBN 0-262-16209-1. 
  6. ^ Wright, Andrew K.; Matthias Felleisen (1994). "A Syntactic Approach to Type Soundness". Information and Computation 115 (1): 38–94. doi:10.1006/inco.1994.1093. 
  7. ^ Macrakis, Stavros (April 1982). "Safety and power" (requires subscription). ACM SIGSOFT Software Engineering Notes 7 (2): 25–26. doi:10.1145/1005937.1005941. 

External links[edit]