Data Redundancy for the Detection and Tolerance of Software Faults

In crucial computer applications, such as avionics systems and automated life support systems, great confidence must be placed in the correct, safe, and reliable operation of the software. For a typical system, current development, analysis, and fault tolerance techniques cannot guarantee either the absence of software faults or adequate levels of confidence in proper operation. Such systems are nonetheless being built, however, and it is desirable to enlarge the set of techniques available for improving the software for critical applications. One such set is based upon the use of design redundancy to provide fault tolerance during operation and to aid testing during development The most general of these techniques, N-version programming and recovery blocks, have been the subjects of widespread study. A newer technique, called data diversity, is based on redundancy in the the data space rather than the design space. Two observations underlie the technique. First, program faults often cause failure only under certain special case conditions. Second, for some applications a program may express its input and internal state in a large number of equivalent ways. These observations suggest obtaining a related set of points in the data space, executing the same software on these points, and then employing a decision algorithm to determine system output Like design redundancy, data redundancy can be exploited during both testing and operation. Although data redundancy avoids many of the objections to design redundant systems, it raises new issues of its own.