Integer arithmetic sometimes has bugs too

Wouldn't you think that something as simple as integer arithmetic would work reliably? I found out otherwise when I tried to write a portable program for simple digital signatures.

The program was intended to defend against data becoming corrupted during transmission. It wasn't intended to withstand an attack by clever bad guys, but instead to offer the same level of security as an office file cabinet.

It worked by doing a straightforward hash of the data, then computing a checksum of the hashed data. The hashing was intended to pick up the possibility of data bytes being interchanged, perhaps by a wayward disk controller. If I remember right, it involved repeatedly multiplying a variable by a prime number and adding the next character to the product.

Both C and C++ specify that the effect of integer overflow is undefined if the computation is signed; but if it is unsigned, the result is computed modulo the word size. When my program failed to work on one particular machine, I was surprised to discover that an unsigned integer multiply was overflowing to zero instead of yielding the proper result.

The multiplication in question was of type unsigned long. The machine had no native hardware for doing long integer multiplication; instead, it simulated it in software. Apparently the software implementor decided to cut corners and cause both signed and unsigned multiplication to yield zero on overflow.

It is hard to express how annoying such bugs are to someone who has never encountered one. The trouble is not just that one must work around the bug; it is that one must simultaneously work around all such bugs on all machines that one wishes to support. Which means that an obscure bug in an obscure implementation affects the code that runs on all implementations. Not only that, but once one has discovered the bug, one has to figure out exactly what circumstances evoke the bug in order to be able to work around it.

In this particular case, it wasn't too difficult: A little experimentation showed that the bug occurred only when an unsigned long multiplication would overflow. Fortunately, it wasn't too hard to restructure the computation in a way that would avoid such overflows. More generally, though, if you write code that intends to cater to a variety of platforms, you have to avoid all the bugs in all the platforms at the same time.

Posted by Andrew Koenig at 09:42 AM  Permalink