Integer overflow
Encyclopedia
Computer programming
Computer programming is the process of designing, writing, testing, debugging, and maintaining the source code of computer programs. This source code is written in one or more programming languages. The purpose of programming is to create a program that performs specific operations or exhibits a...
, an integer overflow occurs when an arithmetic
Arithmetic
Arithmetic or arithmetics is the oldest and most elementary branch of mathematics, used by almost everyone, for tasks ranging from simple day-to-day counting to advanced science and business calculations. It involves the study of quantity, especially as the result of combining numbers...
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 GPU
Graphics processing unit
A graphics processing unit or GPU is a specialized circuit designed to rapidly manipulate and alter memory in such a way so as to accelerate the building of images in a frame buffer intended for output to a display...
s and DSP
Digital signal processor
A digital signal processor is a specialized microprocessor with an architecture optimized for the fast operational needs of digital signal processing.-Typical characteristics:...
s, the result saturates
Saturation arithmetic
Saturation arithmetic is a version of arithmetic in which all operations such as addition and multiplication are limited to a fixed range between a minimum and maximum value. If the result of an operation is greater than the maximum it is set to the maximum, while if it is below the minimum it is...
; 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 binaryBinary numeral system
The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...
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 ),
- 64 bits: maximum representable value 264 − 1 = 18,446,744,073,709,551,615
- 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
C (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
, signed integer overflow causes undefined behavior, while unsigned integer overflow causes the number to be reduced modulo a power of two
Modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....
, meaning that unsigned integers "wrap around" on overflow. This "wrap around" is the cause of the famous "Split Screen
Kill screen
A kill screen is a stage or level in a video game that stops the player's progress due to a programming error or design oversight. Rather than "ending" in a traditional sense, the game will crash, freeze, or behave so erratically that further play is impossible.Video games, like any other computer...
" in Pac-Man.
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.
In computer graphics
Computer graphics
Computer graphics are graphics created using computers and, more generally, the representation and manipulation of image data by a computer with help from specialized software and hardware....
or signal processing
Signal processing
Signal processing is an area of systems engineering, electrical engineering and applied mathematics that deals with operations on or analysis of signals, in either discrete or continuous time...
, 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
Grayscale
In photography and computing, a grayscale or greyscale digital image is an image in which the value of each pixel is a single sample, that is, it carries only intensity information...
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
Pixel
In digital imaging, a pixel, or pel, is a single point in a raster image, or the smallest addressable screen element in a display device; it is the smallest unit of picture that can be represented or controlled....
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"
High dynamic range imaging
In image processing, computer graphics, and photography, high dynamic range imaging is a set of techniques that allows a greater dynamic range between the lightest and darkest areas of an image than current standard digital imaging techniques or photographic methods...
) 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
Ada (programming language)
Ada is a structured, statically typed, imperative, wide-spectrum, and object-oriented high-level computer programming language, extended from Pascal and other languages...
(and certain variants of functional languages), provide mechanisms to make accidental overflows trigger an exception condition. In contrast, Python
Python (programming language)
Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
seamlessly converts a number that becomes too large for an integer to a long. (This occurred in Python 2.4.)
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 Efficient and Accurate Detection of Integer-based Attacks.
- CERTCertCert or CERT may refer to:* Certificate, an official document* Certiorari, a Latin legal term for a court order requiring judicial review of a case...
As-if Infinitely Ranged (AIR) integer model - a largely automated mechanism for eliminating integer overflow and integer truncation As-if Infinitely Ranged Integer Model
See also
- Arithmetic overflowArithmetic overflowThe term arithmetic overflow or simply overflow has the following meanings.# In a computer, the condition that occurs when a calculation produces a result that is greater in magnitude than that which a given register or storage location can store or represent.# In a computer, the amount by which a...
- SIGFPESIGFPEOn POSIX compliant platforms, SIGFPE is the signal sent to a process when it performs an erroneous arithmetic operation. The symbolic constant for SIGFPE is defined in the header file signal.h.- Etymology :...
- Buffer overflowBuffer overflowIn computer security and programming, a buffer overflow, or buffer overrun, is an anomaly where a program, while writing data to a buffer, overruns the buffer's boundary and overwrites adjacent memory. This is a special case of violation of memory safety....
- Heap overflowHeap overflowA heap overflow is a type of buffer overflow that occurs in the heap data area. Heap overflows are exploitable in a different manner to that of stack-based overflows. Memory on the heap is dynamically allocated by the application at run-time and typically contains program data...
- Stack buffer overflowStack buffer overflowIn software, a stack buffer overflow occurs when a program writes to a memory address on the program's call stack outside of the intended data structure; usually a fixed length buffer....
- Pointer swizzlingPointer swizzlingIn computer science, pointer swizzling is the conversion of references based on name or position to direct pointer references. It is typically performed during the deserialization of a relocatable object from disk, such as an executable file or pointer-based data structure...
- Software testingSoftware testingSoftware testing is an investigation conducted to provide stakeholders with information about the quality of the product or service under test. Software testing can also provide an objective, independent view of the software to allow the business to appreciate and understand the risks of software...
- Static code analysisStatic code analysisStatic program analysis is the analysis of computer software that is performed without actually executing programs built from that software In most cases the analysis is performed on some version of the source code and in the other cases some form of the object code...