Integer Overflow | Sahithyan's Notes

Integer overflow is not itself a memory safety violation. It leads to one when the overflowed value is used:

For pointer arithmetic
As a malloc argument
As an array index

An overflowed value used this way often leads to a buffer overflow, or directly to an out-of-bounds read or write.

Unsigned Overflow

An $n$ -bit unsigned integer represents $x$ with $0 \leq x < 2^n$ . On overflow, C++11 requires the value be reduced modulo $2^n$ , so unsigned arithmetic never triggers undefined behaviour.

An $n$ -bit unsigned integer can overflow in multiple cases, for $0 \leq a,b < 2^n$ :

Addition
$a+b \geq 2^n$
Subtraction
$a-b < 0$ if $b > a$
Multiplication
$a \cdot b \geq 2^n$

Examples:

Stagefright
uint8_t *buffer = malloc(size + chunk_size) overflows if size + chunk_size exceeds the unsigned range, allocating a buffer smaller than intended. Fixed by checking size > UINT_MAX - chunk_size before adding, rejecting the allocation instead of letting the sum wrap.

Signed Overflow

By the C++11 standard, if evaluating an expression produces a result not mathematically defined or not representable by its type, the behaviour is undefined. This applies only to signed integers.

An $n$ -bit signed integer can overflow in multiple cases, for $-2^{n-1} \leq a,b < 2^{n-1}$ :

Addition or subtraction
$a+b \geq 2^{n-1}$ or $a+b < -2^{n-1}$ .
Negation
$a = -2^{n-1} \implies -a = 2^{n-1}$ , an asymmetry of two’s complement since $2^{n-1}$ is not representable.
Multiplication
$a \cdot b \geq 2^{n-1}$ or $a \cdot b < -2^{n-1}$ . Multiplication by $-1$ reduces to negation.
Division
$\frac{-2^{n-1}}{-1} = 2^{n-1}$ , reducing to negation.

Examples:

Java’s binarySearch computed mid = (low + high) / 2. For large arrays, low + high overflows a signed 32-bit int before the division, producing a negative or invalid index. Fixed by computing mid = low + (high - low) / 2 instead, since high - low stays within the array’s valid index range and cannot overflow.

Type Conversion

C automatically converts between types, known as coercion, performed by the compiler and capable of unintended consequences.

float to int
Truncates the fractional part.
double to float
Rounds to the nearest representable value.

Converting a smaller type to a larger one uses:

Sign extension
High bits set to the sign bit, used when the source is signed.
Zero extension
High bits set to 0, used when the source is unsigned.

For an arithmetic operation between 2 operands, the compiler chooses a common type:

Same type, same rank
No conversion.
Same type, different rank
Convert the smaller type to the larger.
Unsigned operand with rank at least the signed operand’s rank
Convert both to unsigned.
Signed type can represent every value of the unsigned type
Convert both to signed.
None of the above
Convert both to unsigned, using the signed operand’s type as the unsigned width.

Fixing Integer Overflow

Checking width * height > UINT_MAX after computing width * height is unsound, since the multiplication has already overflowed by the time the check runs.

A correct check divides instead of multiplying, guarding against division by $0$ :

void* new_8bit_image(unsigned int width, unsigned int height)
{
  if (!width || (UINT_MAX / width < height)) return NULL;
  unsigned int memory = width * height;
  void* data = malloc(memory);
  return data;
}

GCC and clang also provide built-in overflow-checking arithmetic, e.g. __builtin_umul_overflow, __builtin_add_overflow, __builtin_sub_overflow, for various integer types.

unsigned int memory;
if (__builtin_umul_overflow(width, height, &memory)) {
  return NULL;
}
void* data = malloc(memory);