Saturday, May 23, 2009
Some bugs can lurk for years
I was shocked to learn that the binary search program that Bentley proved correct and subsequently tested in Chapter 5 of Programming Pearls contains a bug. Once I tell you what it is, you will understand why it escaped detection for two decades. Lest you think I'm picking on Bentley, let me tell you how I discovered the bug: The version of binary search that I wrote for the JDK contained the same bug. It was reported to Sun recently when it broke someone's program, after lying in wait for nine years or so.
Back in November I was working on a program where I needed a binary search that not only returned if I found something, but where it was, or would be if found. I had written such code for my greylist daemon so I lifted the code from there. As I was reusing the code, I realized that there indeed, could be a potential problem with it, in that a calculation of a certain value could overflow and cause unpredictable behavior.
But while I recognized the problem, I neglected to fix the problem in the greylist daemon. And I completely forgot about it until I came across the blog post “Official Google Research Blog: Extra, Extra— Read All About It: Nearly All Binary Searches and Mergesorts are Broken.
Oops.
Anyway, the patch was a one line change, from
mod = (low + high) / 2;
to
mid = low + ((high - low) / 2);
The old code certainly worked, but there could be a chance, if the
indicies low and high were significantly large
enough, to overflow and cause undefined behavior. Truth be told, both
high and low would have to be above 2,000,000,000
(on a typical system) before you might even get bit by this bug.
But still, the potential exists, and why not if it's an easy fix.
And all this is to announce the latest version of the greylist daemon (the “Beefier Bsearch” version if you will).
