12:37 AM

From time to time I get sleepless nights. It's not really unpleasant, but my mind just races from one thing to the next until the middle of the night. Today it was racing over some wild claims about software reliability based on random testing made by some folks I know a couple of years back. At the time, I couldn't come up with why the idea seemed really far fetched, but now I think I have it.

First of all, what is software reliability? My fuzzy 1 AM definition is that it is the probability that the software will behave correctly (i.e., meet its requirements) in its intended environment. It is the last part that is the sticky wicket.

Embedded software is always dependent on the environment. You can't perform very meaningful statistics (e.g., reliability) on something without understanding the distribution of the data that you're working on. For embedded software, this is manifest on the choice of input values that describe the "environment" that the software is supposed to control. Often, people use a normal or random distribution to describe inputs, but this is specious for several reasons:

1. In a "real" system, the inputs tend to constrain each other's value. So, if P is true, then Q is likely true also. Due to errors or failures in sensors / hardware problems / general nastiness, you usually can't *always* assume this will be the case, but if you're trying to describe software reliability using random testing, then you should usually (but not always) obey a complex set of restrictions on inputs
2. The constraints on inputs change over time. This change is due to some "world model" that is not visible to the software. You may be able to approximate it (in fact, you may use the state of the software to approximate it), but this is one of the hardest things to get right when writing control software. It's one of the main reasons that control software is necessary in the first place. Matt Jaffe wrote a paper back in the late 80s where he characterized control software errors; one of the top ones on the list was a disconnect between the actual state of the process and the perceived state of the process by the software. Very little has changed in this regard since Jaffe's paper; we still don't know how to monitor the actual state of the process.
   

Unless you can be sure you've got your world model right, you know very little about the reliability of the software in that environment.

Suppose you're trying to dock the space shuttle at the ISS (this is a problem that Mats Heimdahl's group at UMN looked at a couple years back). There is a quite complex mode machine that describes the behavior of the shuttle as it approaches the ISS bounded by certain conditions on the environment. The mode controller has, if I remember correctly, something like 10^20 states (that is, 100,000,000,000,000,000,000 states), so you're not going to be able to just get lucky with random test. Furthermore, the inputs are mode-dependent, so as you approach the ISS different Boolean input variables will "trip" if you've entered the next smaller region of the state space. Additionally, the input values for distance, attitude, speed, etc. are directly related to the mode of the machine; for example, if you are very close, then you should be going very slow.

In the intended environment, the variables tend to line up like pearls on a string, and those pearls have to move in a coordinated fashion for a significant period of time. In order to test the most critical code, which executes when the shuttle is very close to the ISS, this complex input history must match just so, or the controller will abort.

If you throw this at a random search tool, it completely falls flat; it isn't able to get out of the initial mode, even after thousands upon thousands of tests. Claiming that after you've run a million random tests you some level of confidence in your software is *obviously* wrong when you consider the intended environment. In the case of the docking procedure, you won't even execute 90% of the code. Furthermore, a numeric level of reliability *outside* the intended environment is meaningless, unless you really want to try to use your ISS docking procedure to control a toaster.