Am I being too fussy about trivialities?

Reading my last posting about how to add three integers may leave you thinking that I'm wasting my time on silly stuff. Here's why I'm not.

I have two examples.

Not too long ago, I entered an informal programming contest, which asked entrants to write a binary-search program. Like many such programs, my entry had a line somewhat like this:

    int mid = (low + high) / 2;

This line of code lost points because the computation of low+high might overflow. The solution in this case was

    int mid = low + (high - low) / 2;

This rewrite has the nice property of working for random-access iterators as well as for integers.

If you think this example is also trivial, here is one that is much less so. Once upon a time, I used a time-sharing system that integrated an interpretive programming language into its operating system. Because the language was based on an interpreter, the designers felt there was no need to protect the rest of the operating system from the interpreter. Instead, it relied on the interpreter to prevent user programs from doing nasty things to the operating system. This decision may seem foolhardy, but it looks less so when one realizes that this system was running on a computer that lacked the hardware that would have been necessary for such protection.

Anyway, I discovered that when I allocated a multidimensional array, the code that computed the array's size didn't check for overflow. So if I allocated an array with a size just slightly larger than all of memory, it looked to the interpreter like a small object, even though its dimensions were huge.

This anomaly allowed me to stay within the array's nominal dimensions while still accessing all of the machine's memory, which in turn allowed me to take over control of the operating system. I informed the system's proprietors that I could do this, and they refused to believe me until I demonstrated it for them.

In other words, what looks to an ordinary programmer like a silly error in an edge case may actually be a serious security vulnerability.

Bad guys like it when abstractions deviate from the reality they are intended to represent.

Posted by Andrew Koenig at 01:54 PM  Permalink