Testing the hardware

I once read an article by Edsger Dijkstra that posed the following thought-provoking question: Suppose you have a piece of hardware (or software!) that is intended to add two binary integers. How can you determine that it is doing its job correctly?

Even if we make the simplifying assumption that what we're testing is deterministic--that is, that whenever we give it two particular inputs, we will always get the same result--the problem is still daunting. Suppose, for example, that it purports to add two 32-bit integers, and that we can test a billion cases per second. It would still take more than 500 years to test all of the possibilities. So exhaustive testing of even a very simple adder is too difficult to be feasible.

What we need to do, then, is estimate where problems are likely to occur if they are there at all. For example, if a program works at the extremes of its range, it is likely to work in the middle as well. A plausible strategy might therefore be to try inputs that are near the points where overflow or underflow can occur, and then test other randomly selected "ordinary" values. Even though this strategy must necessarily leave a lot of inputs untested, it can still increase our confidence.

We can do better if we can take the test subject apart and see how it works. For example, if an adder has special-case checking for two specific input values (perhaps as part of an intentional security flaw), the only way that testing will reveal the special case is if we happen to test those particular values. But looking at the code or the hardware has at least a chance of revealing such tests, because they would take the form of code (or microcode, or hardware) that has no obvious purpose.

So although even a simple piece of hardware or software is likely to be too hard to test exhaustively, it may still be worthwhile to use a combination of three techniques:

1) Examine the code or hardware to look for components that don't belong.

2) See how the test subject behaves near its limits.

3) Test a random selection of inputs in addition.

My next note will give some examples of experience in this area.

Posted by Andrew Koenig at 09:58 AM  Permalink