Modeling software design diversity: a review

ABSTRACT

Design diversity has been used for many years now as a means of achieving a degree of fault tolerance in software-based systems. While there is clear evidence that the approach can be expected to deliver some increase in reliability compared to a single version, there is no agreement about the extent of this. More importantly, it remains difficult to evaluate exactly how reliable a particular diverse fault-tolerant system is. This difficulty arises because assumptions of independence of failures between different versions have been shown to be untenable: assessment of the actual level of dependence present is therefore needed, and this is difficult. In this tutorial, we survey the modeling issues here, with an emphasis upon the impact these have upon the problem of assessing the reliability of fault-tolerant systems. The intended audience is one of designers, assessors, and project managers with only a basic knowledge of probabilities, as well as reliability experts without detailed knowledge of software, who seek an introduction to the probabilistic issues in decisions about design diversity.

REFERENCES

• 1: ADAMS, E. N. 1984. Optimizing preventive service of software products. IBM J. Res. Devel. 28,1, 2-14.
• 2: Paul E. Ammann , John C. Knight, Data Diversity: An Approach to Software Fault Tolerance, IEEE Transactions on Computers, v.37 n.4, p.418-425, April 1988 [doi>10.1109/12.2185]
• 3: ANDERSON, T., BARRETT, P. A., HALLIWELL,D.N.AND MOULDING, M. R. 1985. An evaluation of software fault tolerance in a practical system. In Proceedings of the 15th IEEE International Symposium on Fault-Tolerant Computing (FTCS- 15). (Ann Arbor, MI.)
• 4: BABBAGE, C. 1974. On the mathematical powers of the calculating engine (unpublished manuscript, December 1837). In The Origins of Digital Computers: Selected Papers, B. Randell, Ed. Springer- Verlag, New York, 17-52.
• 5: BISHOP, P. G. 1988. The PODS diversity experiment. In Software Diversity in Computerized Control Systems, U. Voges, Ed. Springer-Verlag, New York, pp. 51-84.
• 6: BISHOP,P.G.AND PULLEN, F. D. 1988. PODS revisited-A study of software failure behavior. In Proceedings of the 18th International Symposium on Fault-Tolerant Computing. (Tokyo), IEEE Computer Society Press, Los Alamitos, Calif.
• 7: BLOUGH,D.M.AND SULLIVAN, G. 1990. A comparison of voting strategies for fault-tolerant distributed systems. In Ninth Symposium on Reliable Distributed Systems (SRDS-9) (Huntsville, AL), IEEE Computer Society.
• 8: BONDAVALLI, A., CHIARADONNA, S., DI GIANDOMENICO, F. AND STRIGINI, L. 1999. A contribution to the evaluation of the reliability of iterativeexecution software. Soft. Test. Verif. Reliab. 9,3, 145-166.
• 9: BRIERE,D.AND TRAVERSE, P. 1993. Airbus A320/A330/A340 electrical flight controls-A family of fault-tolerant systems. In Proceedings of the 23rd International Symposium on Fault- Tolerant Computing (FTCS-23). (Toulouse, France), IEEE Computer Society, Los Alamitos, Calif.
• 10: DI GIANDOMENICO,F.AND STRIGINI, L. 1990. Adjudicators for diverse-redundant components. In Ninth Symposium on Reliable Distributed Systems (SRDS-9) (Huntsville, AL.), IEEE Computer Society Press, Los Alamitos, Calif.
• 11: Michael Dyer, The cleanroom approach to quality software development, John Wiley & Sons, Inc., New York, NY, 1992
• 12: ECKHARDT,D.E.AND LEE, L. D. 1985. A theoretical basis for the analysis of multiversion software subject to coincident errors. IEEE Trans. Softw. Eng. SE-11, 12, 1511-1517.
• 13: FAA 1985. Federal Aviation Administration, Advisors Circular AC 25 1309-1A.
• 14: HAGELIN, G. 1988. ERICSSON safety systems for railway control. In Software Diversity in Computerized Control Systems, U. Voges, Ed. Springer-Verlag, New York, pp. 11-21.
• 15: Nick Kolettis , N. Dudley Fulton, Software Rejuvenation: Analysis, Module and Applications, Proceedings of the Twenty-Fifth International Symposium on Fault-Tolerant Computing, p.381, June 27-30, 1995
• 16: HUGHES, R. P. 1987. A new approach to common cause failure. Reliab. Eng. 17, 211-236.
• 17: C. Koza, The ELEKTRA Railway Signalling-System: Field Experience with an Actively Replicated System with Diversity, Proceedings of the Twenty-Fifth International Symposium on Fault-Tolerant Computing, p.453, June 27-30, 1995
• 18: KERSKEN,M.AND SAGLIETTI, F. Eds. 1992. Software fault tolerance: Achievement and assessment strategies. Research Reports ESPRIT, Springer- Verlag, New York.
• 19: John C. Knight , Paul E. Ammann, An experimental evaluation of simple methods for seeding program errors, Proceedings of the 8th international conference on Software engineering, p.337-342, August 28-30, 1985, London, England
• 20: J. C. Knight , N. G. Leveson, An experimental evaluation of the assumption of independence in multiversion programming, IEEE Transactions on Software Engineering, v.12 n.1, p.96-109, Jan. 1986
• 21: John C. Knight , Nancy G. Leveson, A reply to the criticisms of the Knight & Leveson experiment, ACM SIGSOFT Software Engineering Notes, v.15 n.1, p.24-35, Jan 1990 [doi>10.1145/382294.382710]
• 22: Jean-Claude Laprie , Christian Béounes , Karama Kanoun, Definition and Analysis of Hardware- and Software-Fault-Tolerant Architectures, Computer, v.23 n.7, p.39-51, July 1990 [doi>10.1109/2.56851]
• 23: LARYD, A. 1994. Operating experience of software in programmable equipment used in ABB Atom nuclear I&C application. In Advanced Control and Instrumentation Systems in Nuclear Power Plants. Design, Verification and Validation. IAEA/IWG/ATWR & NPPCI Technical Committee Meeting (Espoo, Finland).
• 24: Inhwan Lee , Ravishankar K. Iyer, Software Dependability in the Tandem GUARDIAN System, IEEE Transactions on Software Engineering, v.21 n.5, p.455-467, May 1995 [doi>10.1109/32.387474]
• 25: LINDEBERG, J. F. 1993. The Swedish state railways' experience with n-version programmed systems. In Directions in Safety-Critical Systems, F. Redmill and T. Anderson, Eds. Springer- Verlag, New York, p. 36.
• 26: LITTLEWOOD, B. 1996. The impact of diversity upon common mode failures. Reliab. Eng. Syst. Safety. 51, 101-113.
• 27: Bev Littlewood , Peter T. Popov , Lorenzo Strigini , Nick Shryane, Modeling the Effects of Combining Diverse Software Fault Detection Techniques, IEEE Transactions on Software Engineering, v.26 n.12, p.1157-1167, December 2000 [doi>10.1109/32.888629]
• 28: B. Littlewood , D. R. Miller, Conceptual Modeling of Coincident Failures in Multiversion Software, IEEE Transactions on Software Engineering, v.15 n.12, p.1596-1614, December 1989 [doi>10.1109/32.58771]
• 29: Bev Littlewood , Lorenzo Strigini, Validation of ultrahigh dependability for software-based systems, Communications of the ACM, v.36 n.11, p.69-80, Nov. 1993 [doi>10.1145/163359.163373]
• 30: LITTLEWOOD,B.AND STRIGINI, L. 1998. Guidelines for the statistical testing of software. Centre for Software Reliability, City University, London.
• 31: LITTLEWOOD, B., POPOV,P.,AND STRIGINI, L. 1999. A note on reliability estimation of functionally diverse systems. Reliab. Eng. Syst. Safety. 66, 93- 95.
• 32: Michael R. Lyu, Software Fault Tolerance, John Wiley & Sons, Inc., New York, NY, 1995
• 33: Michael R. Lyu, Handbook of software reliability and system reliability, McGraw-Hill, Inc., Hightstown, NJ, 1996
• 34: MIGNEAULT, G. E. 1982. The Cost of Software Fault Tolerance Technical Report. NASA Langley Research Center, Hampton, Va.
• 35: MoD, 1996. Safety management requirements for defence systems. U.K. Ministry of Defence.
• 36: MoD, 1997. Requirements for safety related software in defence equipment. U.K. Ministry of Defence.
• 37: MONGARDI, G. 1993. Dependable computing for railway control systems. In Third IFIP International Working Conference on Dependable Computing for Critical Applications (DCCA-3) (Mondello, Italy).
• 38: John D. Musa, Operational Profiles in Software-Reliability Engineering, IEEE Software, v.10 n.2, p.14-32, March 1993 [doi>10.1109/52.199724]
• 39: Victor F. Nicola , Ambuj Goyal, Modeling of Correlated Failures and Community Error Recovery in Multiversion Software, IEEE Transactions on Software Engineering, v.16 n.3, p.350-359, March 1990 [doi>10.1109/32.48942]
• 40: P. T. Popov , L. Strigini, Conceptual Models for the Reliability of Diverse Systems - New Results, Proceedings of the The Twenty-Eighth Annual International Symposium on Fault-Tolerant Computing, p.80, June 23-25, 1998
• 41: POPOV, P., STRIGINI, L., AND PIZZA, M. 1998. The efficacy of diverse redundancy against design error: Some practical considerations. In Preprints of the INucE Third International Conference on Control and Instrumentation in Nuclear Installations (Edinburgh).
• 42: RTCA/EuroCAE, 1992. DO-178B, Software considerations in airborne systems and equipment certification.
• 43: M. L. Shooman, Avionics software problem occurrence rates, Proceedings of the The Seventh International Symposium on Software Reliability Engineering (ISSRE '96), p.55, October 30-November 02, 1996
• 44: SMITH,I.C.,WALL,D.N.,AND BALDWIN, J. A. 1991. DARTS-An experiment into cost of and diversity in safety critical computer systems. In IFAC/IFIP/EWICS/SRE Symposium on Safety of Computer Control Systems (SAFECOMP '91). (Trondheim, Norway), Pergamon Press.
• 45: STRIGINI, L. 1996. On testing process control software for reliability assessment: The effects of correlation between successive failures. Softw. Test. Verif. Reliab. 6, 1, 36-48.
• 46: TRAVERSE, P. J. 1988. AIRBUS and ATR system architecture and specification. In Software Diversity in Computerized Control Systems, U. Voges, Ed. Springer-Verlag, New York, pp. 95- 104.
• 47: David B. Turner , Roger Burns , Herbert Hecht, Designing micro-based systems for fail-safe travel, IEEE Spectrum, v.24 n.2, p.58-63, Feb. 1987
• 48: VOGES,U.AND GMEINER, L. 1979. Software diversity in reactor protection systems: An experiment. In IFAC Workshop, SAFECOMP'79 (Stuttgart, Germany May 16-18).
• 49: U. Voges, Software diversity in computerized control systems, Springer-Verlag New York, Inc., New York, NY, 1988
• 50: VOGES, U. 1994. Software diversity. Reliab. Eng. Syst. Safety 43, 2, 103-110.
• 51: Y. C. (Bob) Yeh, Design Considerations in Boeing 777 Fly-By-Wire Computers, The 3rd IEEE International Symposium on High-Assurance Systems Engineering, p.64, November 13-14, 1998

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability; Fault tolerance

  J. Computer Applications

General Terms:
Design, Reliability

Keywords:
N-version software, control systems, functional diversity, multiple version programming, protection systems, safety, software fault tolerance