Over the last year or so, I’ve seen a lot of information coming out of Microsoft dealing with integer overflow. Some Microsofties have even gone on to say that “Integer overflow is the next round of exploitable security bugs” (which is something that I agree with).
So anyway, I noticed today on the Google Research blog an interesting article about just this topic, “Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken”. It seems that an integer overflow has existed in Java’s binarySearch method for nine years! It basically comes about because of code like midpoint = (min + max) / 2 which suffers from an integer overflow when min + max is larger than what can be represented by the integer type.
It can be fixed in various ways (as described in the google research blog post), but after I saw this blog, I had a look at the source for .NET (using none other than Reflector, of course!) and it seems that while the bug existed in .NET 1.x, which had code the following:
int median = (low + hi) >> 1;
.NET 2.0 has replaced that with a call to a new method, “GetMedian”:
static int GetMedian(int low, int hi)
{
return (low + ((hi - low) >> 1));
}
Which is the a non-integer-overflow-susceptible version.
I also noticed that mono has the same bug (see this file, you’ll have to do a search for “DoBinarySearch”). I suppose I could submit a patch, but I’m too lazy :)
Now, on a 32-bit architecture, I don’t think you’d ever run into this particular integer overflow bug, simply because it’s not possible to allocate an array big enough to hit it. But in the move to 64-bit, integer overflows will become increasingly common as the limits of a 32-bit integer are pushed.