Ironically, often the invalid code involves checking for these integer limits. For example the following may overflow and so is invalid:
size_t alloc = SIZE_MAX; if (alloc + BUFSIZ < SIZE_MAX) proceed...Compilers traditionally used to roll over to a smaller value and hence would proceed in this case erroneously. Modern compilers may assume the overflow does not occur (for signed types at least) and auto rearrange the expression as shown below. I.e. assume that signed overflow is undefined behavior, and optimize the expression so there is no addition at runtime, only a comparison to a constant. For details on signed overflow handling see: To fix this common construct so that it works portably and for both signed and unsigned, one can trivially reorganize the equation by reducing the values of both sides, like:
size_t alloc = SIZE_MAX; if (alloc < SIZE_MAX - BUFSIZ) proceed...
Undefined Behavior
It's worth mentioning briefly the more general area of "undefined behavior", under which integer overflow is a part. The rearrangement example above is faster and fixes a bug, though in the general case the side effects compilers introduce from undefined behavior aren't always expected or beneficial, and there have been calls for a "more defined C". Chris Lattner's what every programmer should know about undefined behavior is a great summary of the issues involved.[note from Sep 2013: The MIT CSAIL lab have a great paper summarising cases of the more general problem of undefined behavior in C programs, and they have subsequently released STACK, a new tool for finding undefined behavior bugs by finding dead code, which can be used to find cases like described above. Note these "ignored code" issues can even occur with unsigned integers, which gives more importance to using automated tools like this to flag such cases.]
clang >= 3.3 and GCC >= 4.9 have the -fsanitize=undefined option to enable the UndefinedBehaviorSanitizer (ubsan) to detect various undefined behaviors at runtime. Specifics relating to integer overflow detection are mentioned below. Also tis-interpreter developed through a Linux foundation grant, is available as of Apr 2016, and will interpret C source to identify undefined behavior.Finding integer overflow issues
At compile time
GCC actually has a plethora of options related to this. They're not enabled by default as they would show up too many issues with existing code, but for new code, one really should enable the warnings below (and any other GCC warnings really).gcc -Wtype-limits -Wstrict-overflow=5 -fstrict-overflow -Wsign-compare
Note none of these options warn or change the operation of the above example for unsigned integers – only signed integer overflow is catered for. Note also the -Wconversion warning which is quite awkward to avoid, but again useful when writing new code. Note also that one can give the compiler hints about signed integers to avoid certain warnings. For example one can use the gnulib assume macro to indicate an int is always positive like assume(optind > 0);.
At run time
One can also add explicit checking at runtime to your integer operations – known as precondition testing. Paul Eggert has written convenience macros for this, which can be used like: assert (!INT_ADD_OVERFLOW (a, b));. See also this good article on techniques for efficient integer overflow detection. There is also GCC and clang support for run time detection of signed integer overflow, with the -ftrapv option, or any overflow with the newer -fsanitize=signed-integer-overflow,unsigned-integer-overflow options, but note they're probably best only enabled for tests due to the overflow checking overhead introduced, though that is being improved in LLVM at least. Also clang and gcc >=5, support __builtin_{add,mul,sub}_overflow() to allow adding explicit runtime behavior on overflow. For other runtime handling options see this excellent paper on As-if Infinitely Ranged (AIR) Integers.[Update May 2023: C23 has defined equivalent routines to the convenience macros above. One can #include <stdckdint.h> and then use assert (!ckd_add (&result, a, b); etc.]
Avoiding integer overflow issues
In general to address these roll over issues, we can either use reorganization like in the code example above, or promotion to a wider type (either implicitly or through casting). One should really try to avoid casting though, and use more appropriate integer types or expression reorganization if possible.[Update Jul 2014: CERT has good examples on avoiding overflow with signed integers for various operations.]
[Update Feb 2022: Raymond Chen has good examples on finding the average of two unsigned integers without overflow .]
Following is a more involved example where we want to round a value, with an initial naïve approach susceptible to overflow.
off_t chunk_size (off_t file_size, int n)
{
assert (n && n <= file_size);
return (file_size + n/2) / n; /* round() */
}
The above overflows as the file size approaches OFF_T_MAX.
I.E. the result will go negative as file_size + n/2 rolls
over OFF_T_MAX. One might be tempted to use implicit
promotion to unsigned as follows:
off_t chunk_size (off_t file_size, unsigned int n)
{
assert (n && n <= file_size);
return (file_size + n/2) / n; /* round() */
}
However the above will fail when _FILE_OFFSET_BITS=64.
I.E. when off_t is wider than int.
If we had used long instead of int
then we have the same issue on 32 bit systems.
Generally issues porting between platforms with different width ints
are a common source of these overflow bugs.
The examples below, show how to handle this overflow
using the 3 techniques mentioned above, with the
"implicit promotion" probably being most appropriate
for this situation.
/* Reorganization. */
off_t chunk_size (off_t file_size, int n)
{
assert (n && n <= file_size);
/* Given the above assertions, the largest file_size%n
can be is file_size-n as know n will divide file_size
at least once. */
return file_size/n + (file_size%n + n/2)/n;
}
/* Implicit promotion to wider types. */
off_t chunk_size (off_t file_size, uintmax_t n)
{
assert (n && n <= file_size);
return (file_size + n/2) / n; /* round() */
}
/* Explicit casting to wider types. */
off_t chunk_size (off_t file_size, int n)
{
assert (n && n <= file_size);
return ((uintmax_t) file_size + n/2) / n; /* round() */
}
Integer overflow in other languages
Rust being a programming language designed to protect against bugs, has explicit protection in this area. In debug mode, integer overflows panic by default, while reverting to the C wrapping behavior in release mode. In addition there is no undefined operation wrt overflows, and so is much easier to reason about. For details see this post on integer overflow in rust.
Python being higher level has integer objects abstracted from the base machine integer hardware, and so integers do not overflow, and are constrained only by available memory. Note however floats do map to base hardware and so overflow like in C.