A formal approach to fault tree synthesis for the analysis of distributed fault tolerant systems

ABSTRACT

Designing cost-sensitive real-time control systems for safety-critical applications requires a careful analysis of both performance versus cost aspects and fault coverage of fault tolerant solutions. This further complicates the difficult task of deploying the embedded software that implements the control algorithms on a possibly distributed execution platform (for instance in automotive applications). In this paper, we present a novel technique for constructing a fault tree that models how component faults may lead to system failure. The fault tree enables us to use existing commercial analysis tools to assess a number of dependability metrics of the system. Our approach is centered on a model of computation, Fault Tolerant Data Flow (FTDF), that enables the integration of formal verification techniques. This new analysis capability is added to an existing design framework, also based on FTDF, that enables a synthesis-based, correct-by-construction, design methodology for the deployment of real-time feedback control systems in safety critical applications.

REFERENCES

• 1: M. Baleani , A. Ferrari , L. Mangeruca , A. Sangiovanni-Vincentelli , Maurizio Peri , Saverio Pezzini, Fault-tolerant platforms for automotive safety-critical applications, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA [doi>10.1145/951710.951734]
• 2: Michael Barborak , Anton Dahbura , Minoslaw Malek, The consensus problem in fault-tolerant computing, ACM Computing Surveys (CSUR), v.25 n.2, p.171-220, June 1993 [doi>10.1145/152610.152612]
• 3: A. Benveniste, P. Caspi, S. Edwards, N. Halbwachs, P.L. Guernic, and R.de Simone. The synchronous language twelve years later. Procs. of the IEEE 91(1):64--83, Jan. 2003.
• 4: Francisco V. Brasileiro , Paul Devadoss Ezhilchelvan , Santosh K. Shrivastava , Neil A. Speirs , S. Tao, Implementing Fail-Silent Nodes for Distributed Systems, IEEE Transactions on Computers, v.45 n.11, p.1226-1238, November 1996 [doi>10.1109/12.544479 ]
• 5: C. Dima, A. Girault, C. Lavarenne, and Y. Sorel. Off-line real-time fault-tolerant scheduling. In Euromicro 2001 Mantova, Italy, February 2001.
• 6: I. Item Software. FaultTree+ for Windows volume 8.0. Isograph Limited, 1998.
• 7: H. Lambert. Use of fault tree analysis for automotive reliability and safety analysis. Computer 33(9):18--26, 2000.
• 8: E.A. Lee and D.G. Messerschmitt. Synchronous data flow. Procs. of the IEEE 79(9), September 1987.
• 9: E.A. Lee and S. Neuendorffer. Classes and subclasses in actor oriented designs. In Procs. of the Conference on Formal Methods and Models for Codesign (MEMOCODE) San Diego, California, USA, June 2004.
• 10: E.A. Lee and T.M. Parks. Data flow process networks. Procs. of the IEEE 83(5):773--801, May 1995.
• 11: B. Natvig. Reliability analysis: Encyclopedia of acturial science. Technical Report, University of Oslo, Department of Mathematics, September 2002.
• 12: Y. Papadopoulos and D. Parker. A method and tool support for model-based semi-automated failure modes and effects analysis of engineering designs. Procs. of the IEEE 79(9):1305--1320, September 1991.
• 13: Claudio Pinello , Luca P. Carloni , Alberto L. Sangiovanni-Vincentelli, Fault-Tolerant Deployment of Embedded Software for Cost-Sensitive Real-Time Feedback-Control Applications, Proceedings of the conference on Design, automation and test in Europe, p.21164, February 16-20, 2004
• 14: K.K. Venmuri, J.B. Dugan, and K.J. Sullivan. Automatic synthesis of fault trees for computer-based systems. IEEE Transactions on Reliability 48(4):394--402, December 1999.
• 15: W.E. Vesely, F.F. Goldberg, N.H. Roberts, and D.F. Haasl. Fault tree handbook. Technical Report NUREG-0492, U.S. Nuclear Regulatory Commission, Division of Technical Information and Document Control, January 1981.
• 16: N. Viswanadham, V.V.S. Sarma, and M.G. Singh. Reliability of Computer and Control Systems volume 8. North Holland, Amsterdam, 1987.
• 17: W. Wang, J. Loman, and P. Vassiliou. Reliability importance of components in complex system. In Reliability and Maintainability Symposium Los Angeles, California, USA, January 2004.
• 18: J.A. Wysockiand R. Debouk. Redundancy and reliability tradeoffs for safety/mission critical systems. In International Systems Safety Conference Providence, Rhode Island, USA, August 2004.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

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

General Terms:
Algorithms, Design, Reliability

Keywords:
design exploration, fault tree construction, feedback control applications, system analysis