Table of contents:

Integer overflow needs attention of the developer and misimplementation can cause serious security implementations. We examine the conditions and remedies below.

Introduction

You either have, probably will stumble on a know-it-all recruiter who will ask you to write a very simple function to add two integers. Your answer will be something like this:

static int add(int a, int b) {
  return a + b;
}

And you will be asked to see what wrong is with the code. Actually, I always tend to think the real mistake is asking for such a generic function, with no boundaries and this is the result: The integer overflow happens when the result of an integer operation doesn’t fit into the boundaries of the integer type.

In the context of this function, if we provide 2147483647 for a and 1 for b, the result would be wrong. Instead of returning 2147483648, it would result in -2147483648, clearly one of the possible wrong answers. This is a peculiarity of Java in particular and computers in general. What is more peculiar is that all-helpful Java compiler doesn’t aid us in the right direction to solve this, let alone at least throwing an exception. This behaviour is really a feature of how computers work, and here is a quick explanation:

An int type in Java is stored behind the scenes as a 32 bit, or 8 byte integer. One of the bits (the leftmost one, in our representation) is used for storing whether the number is positive or negative, so an int can take values between -231 and 231-1. In our example above 2147483647 is represented as 01111111111111111111111111111111 and 1 is represented as 00000000000000000000000000000001.

Adding

  01111111111111111111111111111111
+ 00000000000000000000000000000001
----------------------------------
  10000000000000000000000000000000

gives us the smallest integer that can exist in signed integer representation, -2147483648. During addition note that the sign bit has changed just because the addition is done as if it’s not a sign bit but a digit the same as the others. Addition in this sense is perfectly fine as far as the CPU of the computer is concerned, but the key concern is about how we interpret it:

  1. Integer overflow can actually be the desired behaviour in some cases. Algorithms for generating random numbers and check sums deliberately use integer overflowing.
  2. Otherwise, you really want to add two arbitrary integers and come up with a correct result.
  3. Or, you’d like to stay within the boundaries of your integer data type and have the computer act on integer overflow, possibly cancelling the operation and/or warning the user.
  4. In some cases, it may be suitable to set some default values instead of the overflowed value.
  5. Lastly, you may want to detect whenever this happens and mark that result.

Let’s study these cases one by one now.

Integer Overflow in Real Life

Mitigations

Getting a Correct Result by Casting to Another Type

Casting to higher type is the method to use in case we require an arithmetically correct result. Consider the previous example function of addition. If we accept the function input as all ints and operate on long data types, there won’t be an overflow:

static long add(int a, int b) {
  return (long) a + b;
}

will return the arithmetically correct result, without an overflow, because it’s possible to fit any integer addition to long type. Note that it’s not sufficient to change only the return type, because Java will consider the result an int as long as all the items in the process are already int. Therefore, we cast one of the parameters to long inside the method to make sure the result is a long.

This solution holds for multiplication and subtraction too. Division thankfully doesn’t overflow, so we can keep the result of a division operation in its type.

Here are the primitive types and their ranges:

Type name Length in bytes Minimum Maximum
byte 1 -128 127
short 2 -32768 32767
int 4 -2147483648 2,147,483,647
long 8 -9223372036854775808 9223372036854775807

So for instance, if you are operating on short data type, casting it to int or long will make the result arithmetically correct.

So, what about operations on long? How can we mitigate overflows on longs? The answer is to use java.math.BigInteger type. This class holds any kind of integer, as long as the memory allocated to Java holds.

Wait, why did we not use BigInteger all the time? Isn’t it a remedy to our agonies? Although the answer is yes, operations on BigInteger are way slower than Java’s native types. So, we tend to use BigInteger only when we have a concrete reason to justify the performance penalty.

Detecting the Overflow and Raising an Exception

In cases where we need arithmetical precision but keep it in the confines of the original type, one way to go is to notify the caller of the method that the operation caused an integer overflow, so we can’t provide an answer within the constraints of the function signature. As we mentioned before, vanilla Java operators don’t provide us with such a safeguard. But still, there is a solution within Java:

private static int add(int a, int b) {
  return Math.addExact(a, b);
}

Math.addExact will do the usual addition and throw a run-time exception (ArithmeticException that has integer overflow in its message, to be precise) in case of overflow.

Here are the other Math.* methods for exception-throwing operations on integers:

Function name Purpose
addExact Add two ints/longs
decrementExact Subtract 1 from the int/long
incrementExact Add 1 to the int/long
multiplyExact Multiply tow ints/longs
negateExact Multiply the int/long by 1
subtractExact Subtract tow ints/longs
toIntExact Cast the long number to and int

Note that all of these convenience methods operate on ints or longs so for byte and short types, you are on your own. You may choose to stay away from the ignored types, or roll your own *Exact methods. Let’s have a look at how Java library handles overflow.

This is how addition is performed in the source of addExact:

public static int addExact(int x, int y) {
  int r = x + y;
  if (((x ^ r) & (y ^ r)) < 0) {
    throw new ArithmeticException("integer overflow");
  }
  return r;
}

The if statement checking for the overflow is a bit cryptic, so let’s interpret it: ^ is the bitwise XOR operator and & is the bitwise AND operator. Bitwise prefix means that the operation is to be performed on an integer bit-by-bit and the result will be the same integer. Let’s see how these operators work.

XOR operation is useful when we want to detect differences:

x y x ^ y
0 0 0
0 1 1
1 0 1
1 1 0

AND operation is about making sure every bit is set:

x y x & y
0 0 0
0 1 0
1 0 0
1 1 1

For the purpose of simplicity, let’s assume our integer type is only two bits long: One bit holds the number, and the second bit holds the sign:

Bits Integer
00 0
01 1
10 -2
11 -1

In such an imaginary type, the operation 1+1 (01 + 01) will result in -2 (10) instead, causing an overflow. Let’s see how the check above determines it’s an overflow:

And in case of a non-overflowing operation, where we add 1+0 (01 + 00) and result in 01:

The idea behind is that, in order to have an integer overflow, both input values must have the same sign: either both positive or both negative. If the signs are different, there will be no overflow in addition.

So the result changes sign if there is an overflow. ^ operation makes sure that the bit that denotes if there is a - in front of the result is true if the input sign and the output sign is the same. By checking both inputs and combining the result with &, we make sure we keep the - sign only if both of them did change signs, so the result of the check operation will be less than 0.

Let’s see how the standard Java math library handles overflow in multiplication:

public static int multiplyExact(int x, int y) {
  long r = (long)x * (long)y;
  if ((int)r != r) {
    throw new ArithmeticException("integer overflow");
  }
  return (int)r;
}

This one takes the shortcut: Method does the calculation by casting to long, coming up with arithmetically correct result. Then it casts the result to int. In case it doesn’t fit, the result will be wrong, detecting the overflow.

But, how about detecting overflow in multiplication of two longs? It might be preferrable to use BigInteger for this purpose, but still we might have performance considerations:

public static long multiplyExact(long x, long y) {
  long r = x * y;
  long ax = Math.abs(x);
  long ay = Math.abs(y);
  if (((ax | ay) >>> 31 != 0)) {
    // Some bits greater than 2^31 that might cause overflow
    // Check the result using the divide operator
    // and check for the special case of Long.MIN_VALUE * -1
    if (((y != 0) && (r / y != x)) || (x == Long.MIN_VALUE && y == -1)) {
      throw new ArithmeticException("long overflow");
    }
  }
  return r;
}

This method pulls the trick of checking whether the division of the result by one of the parameters yield the other parameter, taking into account the edge cases considered in the remarks.

Let’s summarize how we detect overflow:

  1. In addition (therefore, also in subtraction):
  2. Checking the outcome of (((x ^ r) & (y ^ r)) < 0)
  3. Casting the result to a larger integer type and detecting the overflow by undercasting back to the original type
  4. In multiplication:
  5. Casting the result to a larger integer type and detecting the overflow by undercasting back to the original type
  6. Dividing the result by one of the input parameters and checking if we come up with the other input parameter

Marking the Result as Overflown and Propagating

The previous section was all about detecting the integer overflow and protesting the operation by raising exceptions. Sometimes it’s necessary to detect and inform, rather than quitting. While dealing with floating numbers, Java has the notion of Float.NaN, where NaN stands for not a number, but this concept does not exist in integer.

Consider the scenario where a counter on the screen increases whenever user clicks on a button. We don’t want the counter to reset, but we just want to handle the edge case where the idlest user manages to hit the limit and we don’t do much after that. We can change our exception throwing method this way:

private static Optional<Integer> add(int i, int j) {
  try {
    return Optional.of(Math.addExact(i, j));
  } catch (ArithmeticException e) {
    return Optional.empty();
  }
}

Another piece of code that calls this method will have to check whether the Optional return value holds a result, and act accordingly. This will handle honest addition operations and will also signal overflows without exceptions.

Replacing the Overflow with Default Values

Now let’s consider another scenario. Our data is supposed to hold value of a screen pixel in a grayscale spectrum where 0 black and 255 is white. So, in order to make the pixel look lighter we increase the value, or decreasing the value will make the pixel darker. Making the darkest possible value one bit darker will result in a white pixel unless we handle integer overflow. In this use case, we know that overflowing and resetting is not an option. Plus, we expect that there might be an overflow and know what to do when it happens: nothing.

A solution for handling a non-domain-specific integer would be some code like this:

public class Pixel {
  private int value = 0;
  public int getValue() {
    return value;
  }
  public void incr(int c) {
    try {
      this.value = Math.addExact(this.value, c);
    } catch (ArithmeticException e) {
      if (c < 0) {
        this.value = Integer.MIN_VALUE;
      } else {
        this.value = Integer.MAX_VALUE;
      }
    }
  }
}

Adopting this approach to handle a grayscale of 0-255 is left as an exercise to the reader.

Getting Along with the Overflow

Lastly, there are times we just embrace the overflow and get along with it. There are some cases in your daily life which that happens: When your old but dependable car hits the maximum of the mileage counter and resets it to zero, you don’t assume a fault here. Briefly checking the looks of the car, you can guess how many times (if any) the odometer has reset.

In practical computing applications, integer overflow is exploited as a feature rather than a bug especially in pseudo-random number generation4 and creating checksums5. You might also happen to cases where the default behaviour of integer operations just makes sense. That’s why integer overflow is considered to be condition of computing, not a bug or a vulnerability that need to be patched.

TL;DR

We have seen how integer flow occurs and what to do when it occurs. Our proposed mitigations are:

  1. Keep arithmetical correctness by casting to a larger type.
  2. Be pedantic and raise an exception when it occurs.
  3. Accept it as a fact of life and signal the others accordingly.
  4. Live with it if we need it (and sometimes, yes we do).

References