The Boston Diaries

The ongoing saga of a programmer who doesn't live in Boston, nor does he even like Boston, but yet named his weblog/journal “The Boston Diaries.”

Go figure.

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.

Official Google Research Blog: Extra, Extra—Read All About It: Nearly All Binary Searches and Mergesorts are Broken

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).

Obligatory Picture

[It's the most wonderful time of the year!]

Obligatory Links

Obligatory Miscellaneous

You have my permission to link freely to any entry here. Go ahead, I won't bite. I promise.

The dates are the permanent links to that day's entries (or entry, if there is only one entry). The titles are the permanent links to that entry only. The format for the links are simple: Start with the base link for this site: http://boston.conman.org/, then add the date you are interested in, say 2000/08/01, so that would make the final URL:

http://boston.conman.org/2000/08/01

You can also specify the entire month by leaving off the day portion. You can even select an arbitrary portion of time.

You may also note subtle shading of the links and that's intentional: the “closer” the link is (relative to the page) the “brighter” it appears. It's an experiment in using color shading to denote the distance a link is from here. If you don't notice it, don't worry; it's not all that important.

It is assumed that every brand name, slogan, corporate name, symbol, design element, et cetera mentioned in these pages is a protected and/or trademarked entity, the sole property of its owner(s), and acknowledgement of this status is implied.

Copyright © 1999-2019 by Sean Conner. All Rights Reserved.