12.2 Software Reliability

12.2.2 Software Reliability Modeling

It is increasingly evident that the reliability of a software system is largely determined during program design. One distinct aspect of the software design process that lends itself to measurement is the decomposition of the functionality of a system into modules and the subsequent interaction of the modules under a given set of inputs to the software. The actual distribution of execution time to each software module for a given input scenario is recorded in the execution profile for the system. For a given input scenario to a program, the execution profile is a function of how the design of the software has assigned functionality to program modules.

The reliability of a software system can be characterized in terms of the individual software modules that make up the system. From the standpoint of the logical description of the system, these functional components of the larger system are, in fact, operating in series. If any one of these components fails, the entire system will fail. The likelihood that a component will fail is directly related to the complexity of that module. If it is very complex, the fault probability is also large. The system will be as reliable as its weakest component.

For each possible design outcome in a software design effort, there will be a set of expected execution profiles, one for each of the anticipated program functionalities. We should evaluate design alternatives in terms of the variance of functional complexity. If there is high variability in functional complexity, the reliability of the product of the design is likely to be low. A reasonable design objective would be to reduce functional complexity.

At the design stage, quantitative measures correlated to module fault-proneness and product failure provide a means to begin to exert statistical process control techniques on the design of a software system as an ongoing quality control activity. Rather than merely documenting the increasing operational complexity of a software product and therefore its decreasing reliability, one can monitor the operational complexity of successive design adaptations during the maintenance phase. It becomes possible to ensure that subsequent design revisions do not increase operational complexity and especially do not increase the variance among individual module's functional complexity.

It is now quite clear that the architecture of a program will be a large determinant of its reliability. Some activities that a program will be asked to perform are quite simple. Designers and programmers alike will easily understand them. The resulting code will not likely contain faults. If, on the other hand, the specified functionality of a program is very complex and as a result ambiguous, then there is a good likelihood that this functionality will be quite fragile due to the faults introduced through the very human processes of its creation. A more realistic approach to software reliability modeling will reflect the software reliability in terms of the functionality of the software.

12.2.3 Software Module Reliability

To capture the essence of the concept of software failure, let us suppose that each software system has a virtual failure module (VFM), m _{n +1} , to which control is automatically passed at the instant the program departs from its specified behavior. We can easily accomplish this action with assertions built into the code. In essence, we cannot perceive a failure event if we are not watching. Some program activities such as a divide by zero will be trapped by the system automatically. The hardware and operating system, however, cannot know our intentions for the successful execution of a module on a more global scale. We must instrument the code to know whether it is operating correctly. Programming assertions into the code is a very good way to measure for failure events.

There are really three levels of granularity of program reliability. At the lowest level of granularity, there is module reliability. The module design process has specified each program module very carefully . We know what it should be doing. We can easily define the parameters for its successful operation. We can know, that is, whether the program module is operating within its design specifications. The moment that it begins to operate outside its design framework, we will imagine that the module will transfer control to the VFM representing the failure state. Thus, if we have a system of n program modules, we will imagine that this system is augmented by a module that will trap all contingencies that arise when any program module has failed.

Each program module, then, will or will not fail when it is executed. We can know this and we can remember these failure events. A program module will be considered reliable if we have used it frequently and it has failed infrequently. A program module will be considered unreliable if we have used it frequently and it has failed frequently. A program module that has been used infrequently is neither reliable nor unreliable.

Any program module can transfer control to the VFM. This transfer, of course, can only happen if the current module has departed from program specifications. With our dynamic instrumentation and measurement technique, we can clearly count the number of times that control has been transferred to each module. Those data can be accumulated in a module execution frequency vector (MEFV). We can also count the number of times that control has been transferred from any module to the VFM. These data can be accumulated in a failure frequency vector (FFV) for each module. A module will be considered reliable if there is a small chance that it will transfer control to the VFM.

Let t _i represent the i ^th element of the MEFV. It will contain the number of times that module i has received control during the last epochs. Similarly, let s _i represent the number of times that module i has transferred control to the VFM during the same time period. It is clear that s _i ≤ t _i . That is, a module could have failed every time it was executed or it could have executed successfully at least once. Our current estimate for the failure probability of module i on the m ^th epoch is . This means that of the total epochs that module i has received control, it has worked successfully on epochs. The reliability of this module is simply one (1) minus its failure probability: . From these observations we can construct a vector of failure probabilities for each module on the m ^th epoch.

It is clear that if module i has executed successfully for a large number of epochs, say 100,000, and failed but once over these epochs, then the module will be fairly reliable. In contrast, consider another module j that has executed only ten times and has not failed at all. At face value, the reliability of module j is 1, whereas the reliability of module i is 0.99999. However, we really lack enough information on module j to make a real accurate assessment of its behavior.

What we are really interested in is the current point estimate for reliability and a lower confidence for that estimate. It is clear that we can derive our estimate for the failure probability from . It is also clear that executing module i will have exactly two outcomes : it will execute successfully or it will fail. The distribution of the outcome of each trial will be binomial. Let us observe that for relatively large n, we can use the binomial approximation to a normal distribution with a mean of np and a standard deviation of .

An estimate a for the (l - α ) w upper bound for this failure probability can be derived from the binomial approximation to the normal distribution where:

If, for example, we wished to find the 9 percent confidence interval for , we could compute this from:

where 1.65 is the x ordinate value from the standard normal (N(0,1)) distribution for α = 0.95. This estimate, , is an unbiased estimate for the upper bound of . The problem is that if we have executed a particular module only a very few times and it has not failed, then the number of failures for this module will be zero and the estimate for the upper bound will also be zero. This would seem to imply that an untested module is also highly reliable and we are very confident about that estimate. Nothing could be further from the truth.

A more realistic assumption for the reliability of each module is to assume that it is unreliable until it is proven reliable. To this end, we will assume that each module has, at the beginning, been executed exactly once and it has failed. Thus, the number of measured epochs for each module will be increased by one and the number of failures experienced by that module will also be increased by one. Let and . Thus, a more suitable estimate for the initial failure probability for a module is with an upper bound on this estimate of:

We can construct a vector u ^{( m )} whose elements are the (1 - α ) upper bounds on the estimates for the failure probabilities. Thus, with the vector of failure probabilities z ^{( m )} and the vector of upper bounds on these estimates u ^{( m )} , we can characterize the failure potential and our confidence in this estimate of set of modules that comprise the complete software system.

As each functionality f _i is exercised, it will induce a module execution profile on the set of n program models. That is, each functionality will exercise the set of program modules differently. Therefore, each functionality will have a different failure potential, depending on the failure probability of the modules that it executes. We can compute an expected value for the functionality failure probability of each functionality on the m ^th execution epoch as follows :

In matrix form we can represent the vector of functional failure probabilities as q = pz ^(m) , where p is an m × n matrix of module execution profiles for each functionality. We can also compute an upper bound on the expected value of the functional failure probabilities as q' = pu ^(m) .

As each operation ω _i in the set of l operations is exercised by the user, it will induce a functional profile on the set of k functionalities. That is, for every operation, there will be a vector of conditional probabilities for the execution of each functionality given that operation. Let p' represent the l × k matrix of the conditional probabilities of the k functionalities for the l operations.

It is clear that each operation will exercise the set of program functionalities differently. Therefore, each operation will have a different failure potential, depending on the failure probability of the functionalities that it executes. We can compute an expected value for the operational failure probability of each operation on the m ^th execution epoch as follows:

In matrix form we can represent the vector of operational failure probabilities as x = p'q , where p' is an l × k matrix of functional profiles. Substituting for q we can define x directly in terms of the measurable module failure probabilities to wit: x = p'pz ^(m) . We can also establish an upper bound on the operational failure probabilities as x' = p'pu ^(m) .

The elements of the vector x represent the failure probabilities for each of the l operations. The reliability of operation ω _i can be derived from its failure probability as follows: r _i = 1 - x _i . Thus, we can construct a vector of operational reliability estimates r = I - x , where I is a vector of ones. We can also construct a vector of lower bounds on these reliability estimates: r' = I - x'.

The reliability of a software system is therefore not a static attribute of the system. It is an artifact of how the system will be used. There is a different reliability estimate for each operation, depending on how that operation exercises different modules. Furthermore, there is a lower bound on that reliability estimate, depending on how much we know about the modules that comprise that operation. A user's perception of the reliability of our system will depend on how he or she uses that system. The operational profile o represents the distribution of user activity across the system. Therefore, the user's reliability perception of the system ρ is simply ρ = or and the lower bound for this estimate is ρ ' = or '.

12.2.4 Data Collection for Reliability Estimation

It seems pointless to engage in the academic exercise of software reliability modeling without making at least the slightest attempt to discuss the process of measuring failure events. A failure occurs immediately at the point that the program departs from its specification, not when we first perceive this departure . The latencies between when a system fails and when the user perceives this may be substantial. We could, for example, have a small memory leak in our Web browser. We will have to run this program for some time before it self-destructs, but die it will with this memory leak. The actual failure occurs at the point when the browser software failed to release some memory it had used. The instant when this first happened is when the failure occurred. If we are not watching, we will fail to see this happen. We will see it only when some functionality is first impaired. The user may not see the problem until the Web browser crashes or slows his machine to a crawl.

The basic premise of our approach to reliability modeling is that we really cannot measure temporal aspects of program failure. There are, however, certain aspects of program behavior that we can measure and also measure with accuracy. We can measure transitions to program modules, for example. We can measure the frequency of executions of functions, if the program is suitably instrumented. We can also measure the frequency of executions of program operations, again supposing that the program has been instrumented to do this.

Let us now turn to the measurement scenario for the modeling process described above. Consider a system whose requirements specify a set O of user operations. These operations, again specified by a set of functional requirements, will be mapped into a set F of elementary program functions. The functions, in turn, will be mapped by the design process into the set of M program modules.

The software will be designed to function optimally under known and predetermined operational profiles. We will need a mechanism for tracking the actual behavior of the user of the system. To this end we will require a vector O in which the program will count the frequency of each of the operations. That is, an element o _i of this vector will be incremented every time the program initiates the i ^th user operation as per our discussion in Chapter 10. This is, of course, assuming that the system will perform only operations within the set O . A system that has failed will depart from the specified set of operations. It will do something else. We really do not care what it does specifically. The point is that the system has performed an operation outside of the set O . We know it to have failed as a result. This implies the existence of an additional operational state of the system, a failure state. That is, the system is performing an operation o _{n +1} completely outside the repertoire of the normal set of n specified user operations. This fact has strong implications in the area of computer security. It is clear that if a program is executing within a predefined set of operational specifications, it is operating normally. Once it has departed from this scenario, it is operating abnormally. This likely means that the program is now operating in a potentially unsafe manner.

When we first start using a program we will have little or no information about how its components will interact. The initial test activity is, in essence, the start of a learning process wherein we will come to understand how program components actually work together. To help understand this learning process, let us imagine that we have built a small software system that will perform four simple operations. These operations, in turn, will be implemented by a total of six functionalities. These functionalities will be mapped during the design process to a total of eight program modules. As per the discussion in Chapter 10, we will instrument this program so that we can monitor the transition from one operation to another, from one functionality to another, and from one module to another. Exhibit 1 shows the O × F mapping for this hypothetical system. Exhibit 2 shows the F × M mapping.

Exhibit 1: Mapping of Operations to Functionalities

Exhibit 2: Mapping of Functionalities to Modules

Let us now assume that we have tested our software and exercised at least some of its capabilities. Exhibit 3 shows the frequency of exposure of each functionality for each operation. We can see, for example, that functionality 1 was uniquely associated with operation 1 and was invoked 201 times during the operation of the software.

Exhibit 3: Distribution of Functionalities by Operation

We can now derive the conditional probabilities of each functionality by operation from the data in Exhibit 3. These conditional probabilities are shown in Exhibit 4. They represent the contents of the matrix p' from the previous section.

Exhibit 4: Conditional Probabilities of Functionality Execution by Operation

Let us now assume that we have tallied the execution of each module within each functionality. That is, we will build a matrix of module execution frequencies for each of the functionalities. These data are shown in Exhibit 5.

Exhibit 5: Distribution of Module Activity by Functionality

From the frequency data in Exhibit 5 we can derive the conditional probabilities for the execution of each module given a functionality. Again, these conditional probabilities are derived by dividing the row marginal sums into the individual row entries. The resulting conditional probabilities are shown in Exhibit 6. They represent the contents of the matrix p from the previous section.

Exhibit 6: Conditional Probabilities of Module Execution by Functionality

If we multiply the two matrices p and p' , we will get the product matrix pp' shown in Exhibit 7. These are the conditional probabilities of executing a particular module while the user is expressing each operation.

Exhibit 7: Conditional Probabilities of Module Execution by Operation

We have instrumented our hypothetical system so that we can keep track of the number of times that each module has failed during the total time we have tested the system. These data are shown in Exhibit 8. In every case, we are going to assert that every module has failed once in epoch 0.

Exhibit 8: Hypothetical Module Executions

Using the formulas for failure probability derived in the previous section we can compute the failure probability for each module from the data in Exhibit 8. These failure probabilities are shown in Exhibit 9. We can also compute the 95 percent upper confidence intervals for these failure probabilities. These upper bounds are also shown in Exhibit 9. The data are sorted by failure probability. We can see that the most reliable module is module 7, and the least reliable module is module 2. Not only is module 2 the most likely to fail, the upper bound on this estimate is also very large.

Exhibit 9: Module Failure Probabilities

We now know something about the failure probability (reliability) of each module. We know very little, however, about the reliability of the system. This will depend entirely on how this system is used. If a user were to choose operations that expressed modules 7, 5, and 3, the system would be seen as very reliable. If, on the other hand, the user were to favor operations that heavily used modules 6, 4, and 2, then this same system would very likely fail in the near term .

Now let us assume that there are four different users of our hypothetical system. Each user will exercise the system in his own particular way, represented by an operational profile. Exhibit 10 shows the operational profiles for each of the four users. We can see that user 1, represented by Operational Profile 1, shows a heavy bias to Operation 3, while user 3 exploits Operation 2 and, to a small extent, Operation 4.

Exhibit 10: Four Sample Operational Profiles

If we multiply the contents of Exhibit 10 with the contents of Exhibit 7, PP' , we can see how each of the four users' activity will distribute across the modules that comprise the system. This module activity is shown in Exhibit 11. Clearly, there is a distinct pattern of module execution for each of these users (operational profiles).

Exhibit 11: Distribution of Module Activity under Four Operational Profiles

Exhibit 11 represents a matrix that shows the distribution of module activity for each operational profile. Exhibit 9 is a matrix containing the failure probability of each module and an upper bound for that estimate. The product of these two matrices is shown in the second and third columns of Exhibit 12. We can now associate a failure probability with each operational profile and establish an upper bound for that estimate. The reliability of each operational profile is simply one minus the failure probability. Thus, the fourth column represents the reliability of the system under each operational profile. The fifth column (Lower Bound) shows the lower bound for each of the reliability estimates. This is, of course, simply one (1) minus the estimate for the upper bound of the failure probability.

Exhibit 12: Distribution of Module Activity under Four Operational Profiles