Catching Integer Overflows in C

Update 20150422: clang and gcc 5 have builtins now for this, look for __builtin_add_overflow and __builtin_mul_overflow in the documentation. That makes these macros obsolete.

Note: This document and the macros make two important assumptions:

  1. There are 8 bits in a char. This is not guaranteed by the C standard, and is in fact not true on all platforms, most notably some ancient mainframes. You could work around this with CHAR_BIT from limits.h, if you really cared.
  2. The integers use two's complement. This is also not guaranteed by the C standard, but you will be hard pressed to find a platform where it is not true.

Integer Overflows are arithmetic errors. Integers have finite ranges in computers, for example a 32-bit unsigned integer goes from 0 to 0xffffffff. If you add one to 0xffffffff, you get 0 again.

Since the addition operation in the CPU is agnostic to whether the integer is signed or unsigned, the same goes for signed integers. For 32-bit signed integers, the minimum value is 0x80000000 (-2147483648) and the maximum value is 0x7fffffff (2147483647). Note that there is no value than can hold 2147483648, so if you negate (int)0x80000000, you get (int)0x80000000 again. That is something to look out for, because it means abs() returns a negative value when fed -2147483648.

So, if you want to add two integers a and b (b >= 0), the easiest way to find out if that overflows is to check whether a+b<a (or b; some people think you have to check against min(a,b), but that is unnecessary).

Issue 1: abs(-2147483648) < 0

The abs function returns the argument if it is positive, or the negated argument if it is negative. Unfortunately, -(-2147483648) is still -2147483648 (on a 32-bit platform). So don't rely on abs() on untrusted data to return a non-negative number!

The same is obviously also true for labs and llabs, but for different numbers.

This can become a security issue. I have seen one instance in the vasprintf implementation of libiberty, which is part of gcc, binutils and some other GNU software. vasprintf walks over the format string and tries to estimate how much space it will need to hold the formatted result string. In format strings, there is a construct %.*s or %*s, which means that the actual value should be taken from the stack. The libiberty code did it like this:

          if (*p == '*')
            {
              ++p;
              total_width += abs (va_arg (ap, int));
            }

This is actually two issues in one. The first issue is that total_width can overflow. The second issue is the one that is interesting in this context: abs can return a negative number, causing the code to allocate not enough space and thus cause a buffer overflow.

Issue 2: adding a positive number to an integer might make it smaller

If you add a positive integer to another positive integer, the result is truncated. Technically, if you add two 32-bit numbers, the result has 33 bits.

On the CPU level, if you add two 32-bit integers, the lower 32 bits of the result are written to the destination, and the 33rd bit is signalled out in some other way, usually in the form of a "carry flag".

Unfortunately, there is no way to access this carry bit from C directly.

There are two ways to get around this:

  1. Cast the numbers to a bigger integer type, then do the addition there, and check if the result is in the right range.
  2. Do the addition normally, then check the result (e.g. if (a+23<23) overflow).
  3. Check before adding whether the number you add can fit (requires knowledge of the maximum value for that data type)

Solution 1 does not work in general, because there might not be a bigger integer type, and solution 2 does not work, because in the C language, when adding a number to a pointer or to a signed integer, overflow is undefined. Unfortunately, gcc as of version 4.1 abuses this and optimizes away checks that would only be true if there was an overflow, in particular checks that check for an overflow. Here is an example program that demonstrates the problem.

That leaves us with approach 3. The general idea is given in the answer to question 20.6b of the C faq. Unfortunately, the example code has several issues:

  1. It only works for ints.
  2. We cannot easily generalize it, because we would need a function that returns INT_MAX for a given type.
  3. It does not catch adding -5 to INT_MIN.

Finding the minimum and maximum values for a given integer type

For unsigned data types, this is easy. The minimum value is 0, and the maximum value is (type)-1 (-1 cast to the type we want).

For signed data types, this is not so easy. For a 32-bit int, the minimum value is 0x80000000, and the maximum value is 0x7fffffff. It might be tempting to calculate one from the other, but we cannot just add or subtract one, because that would be the very integer overflow that caused the undefined behavior in the first place. Fortunately, for both signed and unsigned arithmetic, the minimum value is the bitwise NOT of the maximum value (the ~ operator in C).

We can construct 0x80000000 as 1 << (sizeof(type)*8-1). From that we can construct 0x7fffffff as ~0x80000000. That gives us min and max values for signed and unsigned integers.

Here are the macros to get the minimum and maximum values for a given integer type:

#define __HALF_MAX_SIGNED(type) ((type)1 << (sizeof(type)*8-2))
#define __MAX_SIGNED(type) (__HALF_MAX_SIGNED(type) - 1 + __HALF_MAX_SIGNED(type))
#define __MIN_SIGNED(type) (-1 - __MAX_SIGNED(type))

#define __MIN(type) ((type)-1 < 1?__MIN_SIGNED(type):(type)0)
#define __MAX(type) ((type)~__MIN(type))

Earlier versions of this document used a left shift of -1 to construct the return value of __MIN_SIGNED, but Christian Cornelssen pointed out to me that shifting a negative value is undefined, too. Therefore the new solution jumps through a few more hoops. Since these calculations are performed solely on constants, most compilers (including gcc) will calculate them completely at compile time, so do not worry that the new statements will be slower.

Finding out whether we can assign a value to a variable without truncation

The next question is whether we can assign a certain value to a variable without losing precision. It is not sufficient if we just check for overflow during the addition or subtraction, because someone might add 1 to -5 and assign the result to an unsigned int. Then the actual addition does not overflow, but the result still does not fit.

The first approach would be to do the assignment, and then check whether the contents of the destination variable is equal to the value we tried to assign to it. Unfortunately, that is not sufficient.

Let's say, for example, that you try to assign an int of -23 to an unsigned int variable. You do the assignment, the variable is now 0xffffffe9, and then you compare 0xffffffe9 == -23, and the C integer promotion rules will convert -23 to unsigned int, and say both numbers are the same. So we also have to compare the signs. In the end, my macro looks like this:

#define assign(dest,src) ({ \
  typeof(src) __x=(src); \
  typeof(dest) __y=__x; \
  (__x==__y && ((__x<1) == (__y<1))?(void)((dest)=__y),0:1); \
})

typeof is a gcc extension. It is here so that you can give the macro arguments with side effects, like *ptr++. The code then does the assignment, checks whether the value didn't change, and then checks whether the sign is the same, too. In the sign comparison, I use < 1 instead of < 0 because the 0 case doesn't matter, and comparing an unsigned int with < 0 generates a gcc warning about a comparison always being true.

Now we have all we need to do the simple macro, at least a version that can add positive numbers:

#define __add_of(c,a,b) ({ \
  typeof(a) __a=a; \
  typeof(b) __b=b; \
  ((__MAX(typeof(c))-(__b) >= (__a))?assign(c,((typeof(c))__a+__b):1); \
})

Adding and subtracting arbitrary integers

Now that we have a macro that will work for adding positive integers, it's easy to generalize this into a macro that will work for negative integers, too:

#define add_of(c,a,b) ({ \
  typeof(a) __a=a; \
  typeof(b) __b=b; \
  (__b)<1 ? \
    ((__MIN(typeof(c))-(__b)<=(__a))?assign(c,(typeof(c))__a+__b):1) : \
    ((__MAX(typeof(c))-(__b)>=(__a))?assign(c,(typeof(c))__a+__b):1); \
})

And the subtraction macro works just the same:

#define sub_of(c,a,b) ({ \
  typeof(a) __a=a; \
  typeof(b) __b=b; \
  (__b)<1 ? \
    ((__MAX(typeof(c))+(__b)>=(__a))?assign(c,(typeof(c))__a-__b):1) : \
    ((__MIN(typeof(c))+(__b)<=(__a))?assign(c,(typeof(c))__a-__b):1); \
})

Issue 3: Multiplication can overflow, too

The next question is how to multiply integers. On most platforms, the CPU has a multiply instruction that returns a double width integer. On AMD64, for example, there is a mul instruction that will multiply two 32-bit integers into a 64-bit integer, or it can multiply to 64-bit integers into a 128-bit number (split over two registers).

In C, on the other hand, if you multiply two 32-bit integers, you get a 32-bit integer again, losing the upper 32 bits of the result. Fortunately, if you cast the first integer to a 64-bit number, and then multiply it by the other 32-bit integer, gcc is smart enough generate exactly the 32x32->64 instruction we want in the first place.

Multiplying two 32-bit integers

So, here is a routine that can multiply two 32-bit numbers, returning a 32-bit number, and checking for overflow:

int umult32(uint32 a,uint32 b,uint32* c) {
  unsigned long long x=(unsigned long long)a*b;
  if (x>0xffffffff) return 0;
  *c=x&0xffffffff;
  return 1;
}

Multiplying 16-bit values with overflow check works the same way. Note that it is

  (unsigned long long)a*b

and not

  (unsigned long long)(a*b)

which is a typical mistake of inexperienced C hackers. In the second case, the result is first truncated, and then cast to 64-bit, zeroing the upper bits, and the code will never detect an overflow.

Multiplying two 64-bit integers

But what if we want to multiply two 64-bit numbers and there is no 128-bit type? Then we need to do the multiplication by hand. To do that, we split both number in two 32-bit parts. Let's write "<< 32" as "* shift" to make this easier to read. Basically if we write the first number as a1 shift + a0 and the second number as b1 shift + b0, then the product is

  (a1 shift + a0) * (b1 shift + b0) ==
  a1 b1 shift shift + a1 b0 shift + a0 b1 shift + a0 b0

The first term is shifted by 64 bits, so if both a1 and b1 are nonzero, we have an overflow right there and can abort.

For the second and third part we do the 32x32->64 multiplication we just used to check for overflow for 32-bit numbers. This is shifted by 32 bits, so we have an overflow if the upper half of it is nonzero. Since we already know that either a1 or b1 is zero, we can simply calculate

  a=(uint64_t)(a1)*b0+(uint64_t)(a0)*b1;

At least one half of this term will be zero, so we can't have an overflow in the addition. Then, if a > 0xffffffff, we have an overflow in the multiplication and can abort.

If we got this far, the result is

  (a << 32) + (uint64_t)(a0)*b0;

We still need to check for overflow in this addition (thanks to Tomi Jylhä-Ollila for pointing this out). Then we can return the result.