Blog

Integer Overflow Prevention in C

Integer overflows are known bugs in C which can lead to exploitable vulnerabilities. A short paragraph in Understanding Integer Overflow in C/C++ (Will Dietz, Peng Li, John Regehr, and Vikram Adve) highlights the scope of such errors:

These errors can lead to serious software failures, e.g., a truncation error on a cast of a floating point value to a 16-bit integer played a crucial role in the destruction of Ariane 5 flight 501 in 1996. These errors are also a source of serious vulnerabilities, such as integer overflow errors in OpenSSH and Firefox, both of which allow attackers to execute arbitrary code. In their 2011 report MITRE places integer overflows in the “Top 25 Most Dangerous Software Errors”.

Integer overflows occur when the result of an arithmetic operation is a value, that is too large to fit in the available storage space. To clarify the problem, I'll introduce the term process register. Process registers represent an amount of storage available in digital processors and its width defines the range of values that can be represented. Typical process register widths are shown in the following table.

Binary register width Maximum representable value
8 bits 2^8 - 1 = 255
16 bits 2^16 - 1 = 65,535
32 bits 2^32 - 1 = 4,294,967,295
64 bits 2^64 - 1 = 18,446,744,073,709,551,615

The following example helps to clarify what exactly leads to an arithmetic overflow. Let's assume we have three 16 bit unsigned integer values a, b and c. For a, the maximum 16 bit representable value 0xffff (hexadecimal value of 65535) is assigned, and for b the value of 0x1 (hexadecimal value of 1). If we add a and b and store the result in c, the addition would lead to an arithmetic overflow:

c = a + b
c = 0xffff + 0x1
c = 0x10000

The value 0x10000 is too large for a 16 bit binary register, so the addition results in an arithmetic overflow.

In C programming language, a computation of unsigned integer values can never overflow, this means that UINT_MAX + 1 yields zero. More precise, according to the C standard unsigned integer operations do wrap around, the C Standard, 6.2.5, paragraph 9 [ISO/IEC 9899:2011], states:

A computation involving unsigned operands can never overflow, because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting type.

Since the computation overflows, the arithmetic operation is handled in the following way:

c = ((size_t)0xffff + 0x1) % 0x10000
c = 0x10000 % 0x10000
c = 0

So the size of the result is truncated to a size that fits into the available process register width. In other words, when an integer overflow occurs, the value may wrap to result in a small or negative number.

Impact

The following vulnerable program int-example is used to print the character A as many times as the user specifies.

% ./int-example 5
AAAAA

In the preceding program execution the character A is printed 5 times. For that, a buffer mem is allocated with the size of 5 * sizeof(char *).

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main(int argc, char **argv)
{
  int val, i;
  char *mem;

  if (argc < 2)
    exit(1);

  val = atoi(argv[1]);

  if (val > 0) {
    mem = malloc(val * sizeof(char *));

    if (mem == NULL) {
      printf("Failure\n");
      exit(2);
    }
  }

  for (i = 0; i < val; i++) {
    mem[i] = 'A';
    printf("%c", mem[i]);
  }

  printf("\n");

  return 0;
}

This example program checks whether the input value before the memory allocation is greater than 0. malloc(0) will allocate memory with size 0, and that will allow for overwriting memory segments on the heap.

In the preceding example the developer forgot that the result of the multiplication val * sizeof(char *) can overflow.

sizeof(char *) = 4
INT_MAX = 4294967295
INT_MAX + 1 = 4294967296 // <-- Overflow

4294967296 / 4 = 1073741824

So an input of 1073741824 leads to a call of malloc(0) despite the val > 0 check.

% ./int-example 1073741824
Segmentation fault

Mitigation

The OpenBSD 5.6 release introduces a very helpful new libc function reallocarray(3). This new function has integrated integer overflow detection, and is described in the manpage as follows:

The reallocarray() function is similar to realloc() except it operates on nmemb members of size size and checks for integer overflow in the calculation nmemb x size.

This means, that in reallocarray() the result of the multiplication is checked for an integer overflow before calling realloc().

If an integer overflow is detected, reallocarray() returns NULL and set errno to ENOMEM.

With the help of the reallocarray() function we can replace the potential unsafe malloc() and realloc() functions. For this we introduce the C preprocessor macros MALLOC(type), MALLOC_ARRAY(number, type) and REALLOC_ARRAY(pointer, number, type).

#define MALLOC(type) ((type *)reallocarray(NULL, 1, sizeof(type)))
#define MALLOC_ARRAY (number, type) \
  ((type *)reallocarray(NULL, number, sizeof(type)))
#define REALLOC_ARRAY (pointer, number, type) \
  ((type *)reallocarray(pointer, number, sizeof(type)))

Now we are able to adapt the above example code to use the introduced MALLOC_ARRAY function and verify that the possibility to overwrite or to read memory content beyond the buffer boundaries is eliminated.

...
if (val > 0) {
  mem = MALLOC_ARRAY(val, char *);

  if (mem == NULL) {
    printf("Failure\n");
    exit(2);
  }
}
...

With this adaption the execution of the int-example program terminates correctly, if an overflow is detected.

% ./int-example 1073741824
Failure

The OpenBSD reallocarray() function is released under a ISC license. So anyone is free to use or modify it as long as you adhere to the terms of the license. The implementation plus the license can be found in the OpenBSD CVS source code repository.

Further Reading