Integer Overflow/Underflow and Floating Point Imprecision.
How memory restrictions in computers can lead to serious side effects.
Results generated from arithmetic operations in a computer are stored in local memory. Registers of a processor store the numeric values of these operations. Registers, however, consist of a small amount of very fast storage. In computer programming, when an arithmetic operation attempts to create a numeric value which is greater than the highest value that can be stored in the memory, an integer overflow occurs. The interpreted value is wrapped around and started again from the minimum value.
The incorrect results generated in a process because of some underlying operation causing an integer overflow are undetectable after the overflow has occurred.
The ISO C99 standard says that an integer overflow causes “undefined behaviour”. Possible undefined behavior ranges from ignoring the situation completely with unpredictable results, to behaving during translation or program execution in a documented manner characteristic of the environment (with or without the issuance of a diagnostic message), to terminating a translation or execution (with the issuance of a diagnostic message).
Source: C99 Specification
Consider a computer that has a memory of just 8 bits. Thus, any permutation of 0s’ and 1s’, as long as the total number of these ‘bits’ is 8, and the corresponding decimal equivalent can be stored in the memory of the particular computer. The largest possible value that can be stored will simply be a series of 1s’. Converting to decimal, we obtain a value of 255.
Therefore, the maximum value(decimal) that can be stored on such a computer is 255. When some operation tries to raise this value, the interpreted value may roll back to 0 and start counting from the minimum because of integer overflow.
Using the same logic, the maximum values storable in registers of different sizes are:
- 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 computer CPUs, as of 2017),
- 128 bits: maximum representable value 2128 − 1 = 340,282,366,920,938,463,463,374,607,431,768,211,455
If the variable has a signed integer type, a program may make the assumption that a variable always contains a positive value. An integer overflow can cause the value to wrap and become negative.
The term integer underflow is a condition in a computer program where the result of a calculation is a number of smaller absolute value than the computer can actually store in memory. For example, an 8-bit computer is capable of storing unsigned integers ranging from 0–255. Any operation that generates an output which is less than 0 will result in an underflow. The effects may be the reverse of the overflow case as the interpreted results might roll over and start counting down from the highest storable value. As specified in IEEE 754 the underflow condition is only signaled if there is also a loss of precision. Typically this is determined as the final result being inexact.
Underflow can in part be regarded as negative overflow of the exponent of the floating point value
Floating Point Arithmetic Imprecision:
In computing, floating-point arithmetic is arithmetic using formulaic representation of real numbers as an approximation so as to support a trade-off between range and precision.
Source: Wikipedia
Memory limitations in computers can also affect the precision of calculations involving numbers of much smaller magnitudes. Accurately describing all real numbers is not possible in computers. The fact that floating-point numbers cannot precisely represent all real numbers, and that floating-point operations cannot precisely represent true arithmetic operations, leads to many surprising situations. This is related to the finite precision with which computers generally represent numbers. As such, calculations involving floating points may lead to loss of precision.
This behavior is the result of one of the following:
- The binary representation of the decimal number may not be exact.
- There is a type mismatch between the numbers used (for example, mixing float and double).
Source: Why Floating-Point Numbers May Lose Precision
Examples:
Unhandled arithmetic overflows are not uncommon. In many cases, the overflow is not anticipated. Some famous cases involving integer overflows are:
- Ariane 5: On 4 June 1996, the first Ariane 5 rocket, manufactured by the European Space Agency(ESA), malfunctioned and consequently self-destructed 37 seconds after launch. The resulting $370m loss was primarily due to control software failure. Much of the software for Ariane 5 was originally written for its predecessor, the Ariane 4. The older software was unable to handle the unexpectedly high readings for the sideways velocity of the newer, faster vehicle. The resulting integer overflow lead to software malfunction which was the reason for initiating the self-destruct sequence on the rocket.
A data conversion from 64-bit floating point value to 16-bit signed integer value to be stored in a variable representing horizontal bias caused a processor trap (operand error) because the floating point value was too large to be represented by a 16-bit signed integer.
Source: Wikipedia, Ariane 5 Failure Report
- Patriot Missile Imprecision: The US Army used the Patriot Missile systems during the Gulf War in Saudi Arabia to track and intercept incoming Iraqi Scud missiles. On February 25, 1991, an American Patriot Missile battery in Dhahran, Saudi Arabia, dropped the track on an incoming scud. Failure to intercept led to the missile directly striking an US Army barracks resulting in 28 deaths. The reason for failure to launch missiles as counter-measure was related to a bug in the software of the Patriot system.
The time in tenths of second as measured by the system’s internal clock was multiplied by 1/10 to produce the time in seconds. This calculation was performed using a 24 bit fixed point register. In particular, the value 1/10, which has a non-terminating binary expansion, was chopped at 24 bits after the radix point. The small chopping error, when multiplied by the large number giving the time in tenths of a second, led to a significant error. Indeed, the Patriot battery had been up around 100 hours, and an easy calculation shows that the resulting time error due to the magnified chopping error was about 0.34 seconds.
Source: The Patriot Missile Failure
- Gangnam Style breaks YouTube: Before December, 2014, YouTube had programmed their view counter using a 32-bit memory system which stored signed integers. The maximum value recordable on the counter was, therefore, 2,147,483,647. However, the music video for South Korean singer Psy’s Gangnam Style exceeded YouTube’s view limit, prompting the site to upgrade its counter.
The new counter uses a 64-bit memory and thus allows a value of up to 9,223,372,036,854,775,808.
- Civilization Gandhi Bug: In the first installment of the popular turn base video game series Civilization, each leader in the game was assigned a numeric value, greater that zero, to attribute their various characteristics. Gandhi was assigned an “aggressiveness” score of 1 by default. If the player/AI adopted democracy as the ideology for any civilization, the aggressiveness score would drop by 2 for the leader of that civilization. This score, which was already at 1 for Gandhi, would become negative on adopting democracy.
As the game used unsigned 8-bit integers to represent these scores, in Gandhi’s case, instead of having a negative aggressiveness score, the score would roll over (a case of integer underflow) and become 255. Thus Gandhi, in the game, would behave very aggressilvely, frequently attacking other civilizations and players.
- Millennium Bug/Y2K Bug: Until the 1990s, many computer programs stored the four-digit year in an abbreviated format consisting of the last two-digits of the year, primarily for saving memory. So the year 1999 was represented on these computers as ‘99’. The next year would be represented as 00 and could possibly be interpreted by the computers as 1900 instead of 2000.
According to reports, $300 billion were spent on upgrading computer systems to make them Y2K compliant, however, the consequences of the bug were not nearly as severe as anticipated.
About 15 years ago programmer William Porquet had the idea of thinking ahead to yet another crucial date — GMT 3.14.07am on Tuesday 19 January 2038. This is the moment when the number of seconds since 1 January 1970 will exceed one of the maximum values of many computers’ date and time registers nowadays. Like the Millennium Bug, failure to prepare for this could result in computer crashes.
Source: BBC
Handling Overflows:
Overflows can easily be avoided by careful programming. Assigning appropriate data types and analysing operands can prevent overflows. Other methods are also available.
References:
- webappsec.org-Integer Overflows
- utexas.edu-Integer Overflows
- open-std-C99 Specification
- microsoft.com-Floating-Point Imprecision.
- math.unm-Some disasters attributable to bad numerical computing.
- math.unm-The Patriot Missile failure.
- Wikipedia-Year 2000 problem.
- Furman.edu-Risks in Numeric Computing.
- Britannica-The Y2K Bug/The Millennium Bug.
- BBC Future-The number glitch that can lead to catastrophe.
- archive.org-Patriot Missile Failure Report
