An Integer Overflow is the condition that occurs when the result of an arithmetic operation, such as multiplication or addition, exceeds the maximum size of the integer type used to store it. When an integer overflow occurs, the interpreted value will appear to have “wrapped around” the maximum value and started again at the minimum value, similar to a clock that represents 13:00 by pointing at 1:00.
For example, an 8-bit signed integer on most common computer architectures has a maximum value of 127 and a minimum value of -128. If a programmer stores the value 127 in such a variable and adds 1 to it, the result should be 128. However, this value exceeds the maximum for this integer type, so the interpreted value will “wrap around” and become -128.
Related Conditions
Integer Overflows are closely related to other conditions that occur when manipulating integers:
Integer Underflows occur when the result of an arithmetic operation is smaller than the minimum value of the destination integer type. When an integer underflow occurs, the interpreted value will wrap around from the minimum value to the maximum value for its integer type.
Integer Casts occur when an integer of one type is interpreted as another. When this occurs, the bitstream of the source integer is interpreted as if it were the destination integer type. The interpreted value can be significantly different than the original value. Integer casts can be subdivided into context-specific scenarios:
- Signed/Unsigned Mismatch In the Two's Compliment System, the bitstreams that represent a negative signed integer correspond to a very large unsigned integer. For example, the same 32-bit stream is used to represent both -1 and 4,294,967,295 -- casting between signed and unsigned integers can result in a drastic change in interpreted value.
- Integer Truncations occur when an integer is assigned or cast to an integer type with a shorter bit length. When this occurs, the least-significant bits of the larger integer are used to fill as many bits of the shorter integer type as possible. Any bits that cannot be copied are lost, changing the value of the result.
- Sign Extension occurs when a signed integer of a smaller bit length is cast to an integer type of a larger bit length. When the result is interpreted as a signed integer, the interpreted value is correct. However, when interpreted as an unsigned value, a very large positive number results.
Security Impact of Integer Operations
Attackers can use these conditions to influence the value of variables in ways that the programmer did not intend. The security impact depends on the actions taken based on those variables. Examples include, but are certainly not limited, to the following:
- An integer overflow during a buffer length calculation can result in allocating a buffer that is too small to hold the data to be copied into it. A buffer overflow can result when the data is copied.
- When calculating a purchase order total, an integer overflow could allow the total to shift from a positive value to a negative one. This would, in effect, give money to the customer in addition to their purchases, when the transaction is completed.
- Withdrawing 1 dollar from an account with a balance of 0 could cause an integer underflow and yield a new balance of 4,294,967,295.
- A very large positive number in a bank transfer could be cast as a signed integer by a back-end system. In such case, the interpreted value could become a negative number and reverse the flow of money - from a victim's account into the attacker's.
Integer Overflow Example
In C and C++ programming, Integer Overflows often occur when calculating the size of a buffer to be allocated. When this occurs, the calculated size of the buffer will be smaller than the amount of data to be copied to it. This can lead to a buffer overflow, as the following code demonstrates:
// This function reads the student grade from stdin and returns it as an int
// The full implementation has been omitted for clarity
int get_student_grade();
int main(int argc, char *argv[])
{
if (argc != 2)
{
printf("No grades to input.\n");
return (-1);
}
int *student_grades;
unsigned int num_items = atoi(argv[1]);
student_grades = (int *) malloc(num_items * sizeof(int));
if (NULL == student_grades)
{
printf("Could not allocate memory.\n");
return -1;
}
for (unsigned int ctr = 0; ctr < num_items; ctr++)
{
printf("\nPlease input student %u's grade: ", ctr);
student_grades[ctr] = get_student_grade();
}
for (unsigned int ctr = 0; ctr < num_items; ctr++)
{
printf("Student %u grade: %d.\n", ctr, student_grades[ctr]);
}
free(student_grades);
return 0;
}
Example 1 – A C program with an integer overflow
This program allows a person to enter grades for an arbitrary number of students in a class and have them printed out. The number of students in the class is passed as a command line argument, and each student’s grade is retrieved by the get_student_grade
function.
If one assumes a 32-bit computer architecture, an integer overflow occurs when the number of students in the class is greater than 230 - 1, or 1,073,741,823. If a value of 230 + 1 is used, the calculated size of the student_grades
array passed to malloc is 230 multiplied by four (in this example, sizeof(int)
equals 4 bytes). The result, 232 + 4, exceeds the maximum 32-bit unsigned integer size, 232 – 1, and wraps around to simply four, or enough to hold a single integer. The for loop, on the other hand, will still treat this four byte buffer as if it was an array of 230 integers and write input data beyond its allocated bounds.
Integer Casting Example
Integer operations can lead to buffer overflows when mixed integer types are used for variable assignment and comparison. This often results in integers that are truncated, sign-extended, or have mixed signs during value comparisons.
void bad_function(char *input)
{
char dest_buffer[32];
char input_len = strlen(input);
if (input_len < 32)
{
strcpy(dest_buffer, input);
printf("The first command line argument is %s.\n", dest_buffer);
}
else
printf("Error – input is too long for buffer.\n");
}
int main(int argc, char *argv[])
{
if (argc > 1)
{
bad_function(argv[1]);
}
else
{
printf("No command line argument was given.\n");
}
return 0;
}
Example 2 – Function with a buffer overflow due to mismatched integer types
In C, char
is an 8-bit signed integer, so the variable input_len
can store values between -128 and 127. If input
is less than 32 characters in length the program will print the command line argument. If the length is between 32 and 127, the program’s length validation will work properly and the error message will be printed. However, if an input length of 128 is given, input_len
will overflow and become -128. The check will verify that -128 is indeed smaller than 32 and proceed with the strcpy. This will overflow dest_buffer
.
There are two contributing causes for this flaw. Though the 8-bit char type is sufficient to reference elements in the dest_buffer array, it is not large enough to represent all return values from strlen
. As a result, a value over 127 is sufficient to overflow this integer and render that check ineffective. In addition, the fact that char
is a signed integer type renders the check against the static value 32 ineffective; the overflowed value -128 is indeed less than 32. The lack of arithmetic in this example does not make it any less prone to security defects.
Preventing Defects in Integer Operations
Preventing defects in integer operations requires that the software developer anticipate and/or respond to these conditions. The best practices for doing so can be summarized in two main actions:
First, choose an integer type used for a variable that is consistent with the functions to be performed. In some cases, one can avoid an integer overflow by choosing an integer type that can hold all possible values of a calculation. In all cases, the proper integer type reduces the need for integer type casting, a major source of defects.
Second, the operands of an integer operation and/or the result of it should be checked for overflow conditions.
Checking the result attempts to determine whether an exceptional condition has occurred after the fact. For example, if A
and B
are both unsigned integers, then A + B < A
should never be true in normal operation. If it is, one could assume that an integer overflow has occurred. Unfortunately, compilers have been known to optimize away such checks. See "Catching Integer Overflows in C" ([6]) for more details.
It is considered safer to check the operands of the operation before the calculation. The previous example could be changed to check if B > SIZE_MAX - A
. When true, then an integer overflow will occur if the two are added together and stored in a variable of type size_t
. Similarly, one should check if B > SIZE_MAX / A
to determine if A
multiplied by B
would overflow.
Unfortunately, these checks can become very complicated when integers of different sign, size, and order of operations are considered. For this reason, it is highly recommended that safe integer libraries, such as "SafeInt" referred to in ([5]), be used.
Support for protecting against defects in integer operations can be provided by the CPU, the programming language, or libraries used by the programmer. Assembly programmers have immediate access to the CPU, and can check for integer overflows by examining the overflow flag available on most CPUs. Some languages, such as C#, treat most such conditions as an exception, while others like Python use arbitrary-precision integers that will not overflow or underflow.
References
General Reference
"Intel 64 and IA-32 Architectures Software Developer's Manual"
[1] http://download.intel.com/design/processor/manuals/253665.pdf
"Computer Organization and Design", By Patterson, D., Hennessy, J.
[2] Morgan Kaufmann Publishers, Inc.
"The Art of Software Security Assessment", By Dowd, M., McDonald, J., & Schuh, J.
[3] Addison Wesley Professional Press
Integer Overflow/Underflow
"Basic Integer Overflows", By blexim
[4] http://www.phrack.org/issues.html?issue=60&id=10#article
Protecting Against
"SafeInt" by LeBlanc, D.
[5] http://www.codeplex.com/SafeInt
"Catching Integer Overflows in C", by Felix von Leitner
[6]http://www.fefe.de/intof.html
Related Attacks
"Format String Attack"
[7] http://projects.webappsec.org/Format-String
"Buffer Overflow"
[8] http://projects.webappsec.org/Buffer-Overflow
Comments (0)
You don't have permission to comment on this page.