Not All Bugs Are Random
Last week, I started discussing white-box testing, which I suggested was important because sometimes software misbehaves in ways that are not evident from the outside.
White-box testing is important for another reason: By looking at a program's structure, we can sometimes predict circumstances in which it is particularly likely to fail. Looking only at a program's externally visible behavior might not reveal those circumstances, which means that we might neglect to check whether the program behaves appropriately under those particular circumstances.
Of course, some such circumstances are easy to predict. For example, if a program deals with a collection of n items, two obvious cases to test are n = 0 and n = 1. However, other such cases may require looking inside the program. For example, any time a program decides to use one or two (or more) algorithms depending on an aspect of its input such as size, we should verify that it works properly as close as possible to the decision boundary on both sides. I've seen quite a few programs that impose arbitrary length limits on, say, the size of an input line or the length of a name. I've also seen far too many such programs that fail when they are presented with input that fits the limit exactly, or is one greater (or less) than the limit. If you know by inspecting the code what those limits are, it is much easier to test for cases near the limits.
Another kind of predictable error is when a program detects that something has gone wrong and retries the operation. What happens, for example, if the failure is permanent? Does the program keep retrying indefinitely? I remember one program, before the days of ubiquitous networking, that transmitted data from one computer to another by phone line. If the computer on the receiving end indicated a failure, the sending computer would terminate the connection, wait a while, then try to send the data again.
This scheme seemed like a useful and robust way to cope with transmission errors. However, its authors did not know that in the interest of conserving resources, a later release of the operating system would impose an arbitrary upper bound on the size of a file. This limit was settable, but its default value was small enough that people would sometimes want to transmit files larger than the default limit. If the file on the sending end was larger than the file size limit on the receiving end, the receiving program would fail when the file it was creating grew beyond the limit. This transgression would show up as an I/O error, which the receiving machine would duly report to the sending machine. The sender, in turn, would drop the connection, wait a while, and then try again. The receiver would create a new temporary file to hold the data, and the whole dance would repeat.
In other words, adding an operating-system feature to limit file lengths wound up consuming more resources. Trying to send a single file to a machine with a small file-size limit would result in an infinite loop of failed send attempts, blocking further communication between the two machines while it slowly consumed all of the disk space on the receiving end.
Serious as these problems may be, there is an even more important reason for white-box testing: security. Security bugs are even harder to detect during testing than performance bugs because one has to assume that security bugs will be exploited maliciously. Many security bugs are really failures to implement correctly a requirement of the form "No matter what the input to this program is, it must not do X." Black-box testing is generally able to verify only what a program does, not what it does not do. However, with a suitable combination of white-box testing and instrumentation, we can often be much more confident in the absence of at least certain kinds of security bugs. We’ll discuss such techniques further next week.