{"id":8289,"date":"2022-02-21T12:00:00","date_gmt":"2022-02-21T10:00:00","guid":{"rendered":"https:\/\/blog.eset.ee\/et\/2022\/02\/21\/integer-overflow-how-does-it-occur-and-how-can-it-be-prevented\/"},"modified":"2022-02-21T12:00:00","modified_gmt":"2022-02-21T10:00:00","slug":"integer-overflow-how-does-it-occur-and-how-can-it-be-prevented","status":"publish","type":"post","link":"https:\/\/blog.eset.ee\/et\/en\/2022\/02\/21\/integer-overflow-how-does-it-occur-and-how-can-it-be-prevented\/","title":{"rendered":"Integer overflow: How does it occur and how can it be prevented?"},"content":{"rendered":"

For many people in the IT community, 2022 got off to a bad start after a bug in on-premises versions of Microsoft Exchange Server caused emails to become stuck en route due to a failed date check. Put simply, a bug subsequently dubbed Y2K22 (named in the style of the Y2K bug that spooked the world starting about a quarter century ago) caused the software to be unable to handle the date format for the year 2022. Microsoft\u2019s fix<\/a>? Set the date on malware detection updates back to the fictional December 33rd<\/sup>, 2021, giving the date value enough \u201cbreathing space<\/abbr>\u201d before reaching the highest value the underlying integer type can hold.<\/p>\n

Yet the real lesson for developers is that implementing your own date-handling code is too fraught with the risk of making such mistakes and coming up with strange fixes that would use fictional dates. So unless you are writing those routines for an operating system, a compiler, etc., you should always use standard date APIs.<\/p>\n

Back in 2015, a bug of similar ilk was found to affect the software of Boeing\u2019s 787 Dreamliner jet. Had it not been spotted and squashed in time, the bug could have led to a total loss of all AC electrical power<\/a>, even in midflight, on the aircraft after 248 days of continuous power<\/abbr>. The solution to avoid pilots losing control of their airliner midair? Reboot your 787 before 248 days are up, or better, apply the patch.<\/p>\n

So why did Microsoft need to pretend updates for its Exchange antimalware component were still from 2021? Why does a plane need to be turned off and back on just so it doesn\u2019t crash? In both cases, the blame fell squarely on an integer overflow, a vulnerability that is a concern in all types of software, ranging from video games to GPS systems to aeronautics. In the 2021 CWE Top 25 Most Dangerous Software Weaknesses<\/a> list, which looked at around 32,500 CVEs published in 2019 and 2020, integer overflow or wraparound ranked in twelfth place.<\/p>\n

Are software developers so mathematically challenged that they can\u2019t anticipate when they might be running out of numbers? The reality is more complex, in fact. Let\u2019s look a little more deeply at how computers store and handle numbers to see how elusive an integer overflow can be.<\/p>\n

What is an integer?<\/h2>\n

In mathematics, integers include positive numbers like 1, 2, and 3, the number 0, and negative numbers like \u22121, \u22122, and \u22123. Integers do not include fractions or decimals. That means the set of all integers can be represented with the following number line:<\/p>\n<\/p>\n

\"\"<\/a><\/p>\n

Commonly, a programming language has several integer variable types \u2013 each one stores a range of integer values depending on the number of bits that type uses on a particular machine. The more bits that an integer type consumes, the greater the values that can be stored therein.<\/p>\n

Let\u2019s consider the integer types in the C programming language, assuming bit sizes that we might expect on a typical x64 machine.<\/p>\n

A char<\/span> consumes 8 bits of memory, meaning that it can store the following values:<\/p>\n<\/p>\n

\"\"<\/a><\/p>\n

Notice that a char<\/span> can only store values down to a minimum of -128 and up to a maximum of 127.<\/p>\n

But there is another \u201cmode\u201d of the char<\/span> integer type that only stores non-negative integers:<\/p>\n<\/p>\n

\"\"<\/a><\/p>\n

Integer types have both signed and unsigned modes. Signed types can store negative values, whereas unsigned types cannot.<\/p>\n

The following table shows some of the principal integer types in the programming language C, their sizes on a typical x64 machine, and the range of values they can store:<\/p>\n

Table 1. Integer types, their typical sizes and ranges for the Microsoft C++ (MSVC) compiler toolset<\/a><\/em><\/p>\n<\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n
Type<\/th>\nSize (bit width)<\/th>\nRange<\/th>\n<\/tr>\n<\/thead>\n
char<\/span><\/td>\n8<\/td>\nsigned: \u2212128 to 127<\/td>\n<\/tr>\n
#rowspan#<\/td>\nunsigned: 0 to 255<\/td>\n<\/tr>\n
short int<\/span><\/td>\n16<\/td>\nsigned: \u221232,768 to 32,767<\/td>\n<\/tr>\n
#rowspan#<\/td>\nunsigned: 0 to 65,535<\/td>\n<\/tr>\n
int<\/span><\/td>\n32<\/td>\nsigned: \u22122,147,483,648 to 2,147,483,647<\/td>\n<\/tr>\n
#rowspan#<\/td>\nunsigned: 0 to 4,294,967,295<\/td>\n<\/tr>\n
long long int<\/span><\/td>\n64<\/td>\nsigned: \u22129,223,372,036,854,775,808 to 9,223,372,036,854,775,807<\/td>\n<\/tr>\n
#rowspan#<\/td>\nunsigned: 0 to 18,446,744,073,709,551,615<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

What is an integer overflow?<\/h2>\n

An integer overflow or wraparound happens when an attempt is made to store a value that is too large for an integer type. The range of values that can be stored in an integer type is better represented as a circular number line that wraps around. The circular number line for a signed char can be represented as the following:<\/p>\n<\/p>\n

\"\"<\/a><\/p>\n

If an attempt is made to store a number greater than 127 in a signed char<\/span>, the count wraps around to \u2212128 and continues upwards, toward zero, from there. Thus, instead of what should be 128 the value \u2212128 is stored, instead of 129 the value \u2212127, and so on.<\/p>\n

Looking at the problem in reverse, if an attempt is made to store a number less than -128 in a signed char<\/span>, the count wraps around to 127 and continues downwards, toward zero, from there. Thus, instead of what should be \u2212129 the value 127 is stored, instead of \u2212129 the value 126, and so on. This is sometimes called an integer underflow<\/em>.<\/p>\n

Hunting down the elusive integer overflow<\/h2>\n

Thinking of an integer overflow as a circle of values that wrap around makes it fairly easy to understand. However, it\u2019s when we get down to the nitty gritty of \u201ccasting\u201d integer types and porting and compiling programs that we can better understand some of the challenges involved in avoiding integer overflows.<\/p>\n

Watch your casts<\/h3>\n

Sometimes it is useful, or even required, to store a value in a different type than the one originally used \u2013 casting<\/em>, or \u201ctype conversion\u201d, allows programmers to do that. Although some casts are safe, others are not because they can lead to integer overflows. A cast is considered safe when the original value is guaranteed to be preserved.<\/p>\n

It is safe to cast a value stored in a smaller (in terms of bit width) integer type to a larger integer type within the same mode \u2013 from a smaller unsigned type to a larger unsigned type and from a smaller signed type to a larger signed type. Thus, it is safe to cast from a signed char<\/span> to a signed short int<\/span> because a signed short int<\/span> is large enough to store all the possible values that can be stored in a signed char<\/span>:<\/p>\n<\/p>\n

\"\"<\/a><\/p>\n

Casting between signed and unsigned integers is a red flag for integer overflows as the values cannot be guaranteed to remain the same. When casting from a signed type to an unsigned type (even if it\u2019s larger) an integer overflow can happen because unsigned types cannot store negative values:<\/p>\n<\/p>\n

\"\"<\/a><\/p>\n

All the negative signed char<\/span> values to the left of the red line in the image above from \u2212128 to \u22121 will cause an integer overflow and become high positive values when cast to an unsigned type. \u2212128 becomes 128, \u2212127 becomes 129, and so on.<\/p>\n

In reverse, when casting from an unsigned type to a signed type of the same size<\/em>, an integer overflow can happen because the upper half of the positive values that can be stored in an unsigned type exceed the maximum value that can be stored in a signed type of that size.<\/p>\n

All the high positive unsigned char<\/span> values to the left of the red line in the above image from 128 to 255 will cause an integer overflow and become negative values when cast to a signed type of the same size. 128 becomes \u2212128, 129 becomes \u2212127, and so on.<\/p>\n

Casting from an unsigned typed to a signed type of a larger size<\/em> is more forgiving because it carries no risk of an integer overflow: all the values that can be stored in a smaller unsigned type can also be stored in a larger signed type.<\/p>\n

Implicit upcasts: Beware of the \u201cprejudice\u201d for 32 bits<\/h3>\n

Although having the ability to explicitly cast integer types is useful, it is important to be aware of how compilers implicitly upcast the operands of operators (arithmetic, binary, Boolean, and unary). In many cases, these implicit upcasts help prevent integer overflows because they promote operands to larger-sized integer types before operating on them \u2014 indeed, the underlying hardware commonly requires operations to be done on operands of the same type and compilers will promote smaller-sized operands to larger ones to achieve this goal.<\/p>\n

However, the rules for implicit upcasts favor 32-bit types, meaning that the consequences can at times be unexpected for the programmer. The rules follow a priority. First, if one or both of the operands is a 64-bit integer type (long long int<\/span>), the other operand is upcast to 64 bits, if it is not already one, and the result is a 64-bit type. Second, if one or both of the operands is a 32-bit integer type (int<\/span>), the other operand is upcast to a 32-bit type, if it is not already one, and the result is a 32-bit type.<\/p>\n

Now here is the exception to this pattern that can easily trip up programmers. If one or both of the operands are 16-bit types (short int<\/span>) or 8-bit types (char<\/span>), the operands are upcast<\/em> to 32 bits before the operation is performed and the result is a 32-bit type (int<\/span>). The only operators that are an exception to this behavior are the pre- and postfix increment and decrement operators (++, –), which means that a 16-bit (short int<\/span>) operand, for instance, is not upcast and the result is also 16 bits.<\/p>\n

The \u201cprejudiced\u201d upcast of 8-bit and 16-bit operands to 32-bits is critical to understand when making checks to prevent integer overflows. If you think you are adding two char<\/span> or two short int<\/span> types, you are mistaken because they are implicitly upcast to int<\/span> types and return an int<\/span> result. With a 32-bit result being returned by the operation, it is necessary to downcast the result to 16 or 8 bits before checking for an integer overflow. Otherwise, there is a risk of not detecting an integer overflow because an int<\/span> won\u2019t overflow with the comparatively small values that a short int<\/span> or a char<\/span> might provide as operands.<\/p>\n

Code portability issues I \u2013 different compilers<\/h3>\n

Creating different builds of a program that can run on different architectures is an important consideration at software design time. Not only can it be a headache to rewrite code that was poorly planned out for different builds, but it can also lead to integer overflows if care is not taken.<\/p>\n

Compilers, which are used to build code for different target machines, are expected to support the standard of a programming language, but there are certain implementation details that are undefined and left to the decision of compiler developers. The sizes of integer types in C is one of those details with only a bare skeleton of guidance in the C language standard, meaning that not understanding the implementation details for your compiler and target machine is a recipe for possible disaster.<\/p>\n

The number of bits consumed by each integer type described in Table 1 is the scheme used by the Microsoft C++ (MSVC) compiler toolset, which includes a C compiler<\/a>, when targeting 32-bit, 64-bit, and ARM processors. However, different compilers that implement the C standard can use different schemes. Let\u2019s consider an integer type called a long<\/span>.<\/p>\n

For the MSVC compiler, a long<\/span>
\nconsumes<\/a> 32 bits regardless of whether the build is for a 32-bit or 64-bit program. For the IBM XL C compiler, however, a long consumes<\/a> 32 bits in a 32-bit build and 64 bits in a 64-bit build. It is critical to know the sizes and maximum and minimum values an integer type can hold in order to check for integer overflows correctly for all your builds.<\/p>\n

Code portability issues II \u2013 different builds<\/h3>\n

Another portability issue to watch out for is in the use of size_t<\/span>, which is an unsigned integer type, and ptrdiff_t<\/span>, which is a signed integer type. These types consume<\/a> 32 bits in a 32-bit build and 64 bits in a 64-bit build for the MSVC compiler. A piece of code that decides whether to branch based on a comparison in which one of the operands is of one of these types could lead the program down different execution paths depending on whether it is part of a 32-bit build or a 64-bit build.<\/p>\n

For example, in a 32-bit build, a comparison between a ptrdiff_t<\/span> and an unsigned int means that the compiler casts the ptrdiff_t<\/span> to an unsigned int<\/span> and so a negative value becomes a high positive value \u2014 an integer overflow that then leads to an unexpected path in the program being executed, or an access violation. But in a 64-bit build, the compiler upcasts the unsigned int<\/span> to a signed 64-bit type, meaning there is no integer overflow and the expected path in the program is executed.<\/p>\n

How an integer overflow leads to a buffer overflow<\/h2>\n

The principal manner in which an integer overflow vulnerability can be exploited is by circumventing any checks that limit the length of data to be stored in a buffer so as to induce a buffer overflow<\/a>. This opens the door to the vast array of buffer overflow exploitation techniques that lead to further problems like escalation of privilege and execution of arbitrary code.<\/p>\n

Let\u2019s consider the following contrived example:<\/p>\n

#include <string.h> #include <stdio.h> #include <stdlib.h> int MAX_BUFFER_LENGTH = 11; \/\/ [1] char* initializeBuffer () { char* buffer = (char*) malloc(MAX_BUFFER_LENGTH * sizeof(char)); if (buffer == NULL) { printf(\"Could not allocate memory on the heapn\"); } return buffer; } int main(void) { signed int buffer_length; char* source_buffer = \"0123456789\"; \/\/ Arbitrary test data char* destination_buffer = NULL; buffer_length = -1; \/\/ Hypothetical attacker-controlled variable printf(\"buffer_length as a signed int is %d and implicitly cast to an unsigned int is %un\", buffer_length, buffer_length); \/\/ [2] Faulty size check if (buffer_length > MAX_BUFFER_LENGTH) { printf(\"Integer overflow detectedn\"); } else { destination_buffer = initializeBuffer(); \/\/ [3] Potential buffer overflow due to integer overflow strncpy(destination_buffer, source_buffer, buffer_length); destination_buffer[buffer_length] = '\u0000'; printf(\"Destination buffer contents: %sn\", destination_buffer); } free(destination_buffer); return 0; }<\/code><\/pre>\n
Not accustomed to C? Run this code right in your browser with a notebook<\/a> in Google Colab.<\/em><\/p>\n
At [2], there is no check for negative values of buffer_length<\/span> meaning that it passes the check. Furthermore, the MAX_BUFFER_LENGTH<\/span> is a signed int<\/span>, but it should have been declared at [1] as an unsigned integer type because negative values should never be used when assigning buffer lengths. As an unsigned integer type, the compiler would have implicitly cast the buffer_length to an unsigned int at the check at [2] leading to detection of the integer overflow.<\/p>\n
But with the \u22121 stored in buffer_length<\/span> slipping past the check and the compiler implicitly casting it as an unsigned int<\/span> in the initializeBuffer<\/span> function at [3] instead, it overflows to a high positive value of around 4 billion, quite beyond the maximum expected buffer length of 11.<\/p>\n
This integer overflow then leads directly to a buffer overflow because strncpy<\/span> attempts to make a copy of around 4GB of data from the source buffer into the destination buffer. Thus, even though an attempt is made to prevent a buffer overflow with the size check at [2], the check is made incorrectly and an integer overflow occurs that leads directly to a buffer overflow.<\/p>\n
When handling casts between signed and unsigned integer types, it\u2019s not enough to make a size check for a value that is greater than the expected maximum value. It\u2019s also critical to check for a value that is less than the expected minimum value:<\/p>\n
\/\/ [2] Corrected size check if (buffer_length < 0 || buffer_length > MAX_BUFFER_LENGTH) {<\/code><\/pre>\n
Rules of thumb<\/h2>\n
Various strategies can be employed to check for and handle possible integer overflows in your code, some of which have a trade-off in portability vs. speed. Without considering those here, keep in mind at least the following guidelines:<\/p>\n