r'u /-" -- ORC 78-14 LLAUGUST 1978 COMPUTER-AIDED FAULT TREE ANALYSIS by RANDALL R. WILLIE 10. I: ... I OPERATIONS RESEARCH CE N T Tis docuinothabeenppmved for puboice roloase(cid:127) =d ad ib CENTER OFCifriA " u ingtL& UNIVERSITY OF CALIFORNIA WE R(ELEY It COMPUTER-AIDED FAULT TREE ANALYSISt by Randall R. Willie Operations Research Center University of California, Berkeley AUGUST 1978 ORC 78-14 This research has been partially supported by the Otfice of Naval Research under Contract N00014-75-C-0781, the Air Force Office of Scientific Research (AFSC), USAF, under Grant AFOSR-77-3179 and the Lawrence Livermore Laboratory under Purchase Order No. 7800103 with the University of California. Reproduction in whole or in part is permitted for any purpose of the United States Government. tThe computer program FTAP is available from NISEE/Computer Applica- tions, Davis Hall, University of California, Berkeley, California 94720, (415) 642-5113. J MEý1 ISCLAI THIS DOCUMENT IS BEST QUALITY AVAILABLE. THE COPY N-RNISHED TO DTIC CONTALNED A SIGNIFICANT NUMBER OF ',AC"Ih(cid:127)(cid:127)1".- DO NOT 4-EGI~BTY REPRODUCED FROM BEST AVAILABLE COPY Unclassified qCU..ýITY CLASSIFICATION OF THIS PAGE (fton Dal* Emotedet) READ INSTRUCTIONS REPORT DOCUMENTATION PAGE BEFORE COMPLETING FORM .GOT ACCESSION NO. 3. RECIPIENT'S CATALOG NUMBER ORC VE7 COMPUTrER-AIDED FAULT TREE AN.YS~ Research 6. PERFORMING 0 MIENa 7. A TW R~e _ZNTIRACT OR GRANT NUM!S~a 9. PERFORMING ORGANIZATION NAME ANG ACCRESSARA&WICUT UEN Operations Research Center University of California NR 042 238 Berkeley, California 94720 It. CONTROILLING OISWICK NAME AND ADDRESS ,- LRP5~AT-- Office of Naval Research Aumot 448 Departmens-. of the Navy / Arlington, Virginia 22217 103 T4.- MONITORINrG AGENCY NAME a AUDRIESS(if different fro'.i Controlling Office) 15. SECURITY CLASS. Wa this ,0eort) Unc lass if ied SC. E(C.ASSIPFICAT1ONI OOWNGNAAOING SCNIEDULIE IS. DISTRIBUTION SfATEMCNT (of this Report) Approved for public release; distribution unlimited. 17. DISTRIBUTION STATEMENT (of IA. Pnb*Ict entered in Block 20, it dgff.,u.,t from Repeart) Ifl. SUPPLEMENTARY NOTES Also supported by the Air Force Office of Scientific Research (AFSC), USAF, under Grant AFOSR-77-3179 and the Lawrence Livermore Laboratory under Purchase Order No. 7800103. IS. KEY WORDS (Contlnuma n Poers*a idej it fl*comyC Und identity by block nuatibe') Fault Tree Logic Tree Minimal Cut Set Prime implicant ZO. ABSTRACT (Codtioula* on reverse aid* it necessary and i*d~fiit by block numsb.,) (SEE ABSTRACT) DD I OA"W'7, 1473 EDITION OF IHOV 65 IS OBSOLETE Unclassified S/N1 02-F-04-6601 ,'~~-*Z~ ~~2 SECURITY CLASSIFICATION OF THIS PAGE (USI erl tw~ ACKNOWLEDGMENT I am deeply indebted to Professor Richard E. Barlow of University of California, Berkeley for his guidance and encouragement in the pre- Sparation of this report and the associated computer program. I am also grateful for his cheerful patience as I consistently under- estimated the remaining time to complete this project. Dr. Howard Lambert of Tera Corporation (formerly of Lawrence Livermore Laboratories) deserves special thanks for providing a number of large fault trees to test the algorithms and program logic. Finally, I am grateful to Dr. Richard Worrell of Sandia Laboratories for a stimulating discussion of fault tree methods during his visit to Berkeley in November, 1977. S...................................... ......... ABSTRACT Part I of this report discusses a computer-oriented methodology for deriving minimal cut and path set families associated with arbitrary fault trees. Part II describes the use of the Fault Tree Analysis Program (FTAP), an extensive FORTRAN computer package that implements the Part I methodology. An input fault tree to FTAP may specify the system state as any logical function of subsystem or component state variables or complements of these variables. When fault tree logical relations involve complements of state variables, the analyst may instruct FTAP to produce a family of prime imp(cid:127)ioants, a generalization of the minimal cut set concept. FTAP can also identify certain sub- systems associated with the tree as system modules and provide a collection of minimal cut set families that essentially expresses the state of the system as a function of these module state variables. Another FTAP feature allows a subfamily to be obtained when the family of minimal cut sets or prime implicants is too large to be found in its entirety; this subfamily consists only of sets that are K interesting to the analyst in a special sense. 'I.(cid:127)(cid:127) . . . . : : ,::,,r (cid:127) (cid:127),',:,(cid:127) ,= :- • (cid:127) . (cid:127) (cid:127) d __ _ (cid:127) -: TABLE OF CONTENTS Page INTRODUCTION .......................... ........................... 1 PART I: METHODS FOR COMPUTER-AIDED FAULT TREE ANALYSIS .... ...... 4 1.1 Boolean Expressions ............... ................... 4 1.2 Fault Tree Fundamentals .............. ................. 8 1.2.1 Fault Tree Definitions ............ .............. 9 1.2.2 The MOCUS and MICSUP Methods .... ........... ... 16 1.2.3 General Framework for Implicant Elimination . . . 23 1.3 Simple Modules ............... ...................... .. 24 1.3.2 Application of Simple Modules to Implicant Families ............ ..................... 28 1.3.3 A Method for Identifying Modular Subtrees. ..... ... 33 1.4 Obtaining Implicant Families Associated with Modular Subtrees .............. ................... ... 40 1.4.1 The MSDOWN Method ......... ................. ... 41 1.4.2 The MSUP Method ......... ................. .... 49 1.4.3 The Nelson Method ......... ................ ... 55 1.4.4 Comments on the Choice of Method ... ......... ... 61 PART 11: USE OF THE FAULT TREE ANALYSIS PROGRAM . .. .. .. . .. 66 11.1 General Input Structure ......... ................. ... 67 11.2 Fault Tree Specification ......... ................ .. 69 11.3 Execution Instructions ............ ................ .. 72 11.4 Option Instructions ....... ................. .... 75 11.4.1 Fault Tree Modification (TRUE, FALSE) .. ...... .. 76 11.4.2 Gate Event Selection (PROCESS, ALL) .. ....... .. 78 11.4.3 Methodology Specification (PRIME, ALLNEL, NELSON, MSUP, MSDOWN, WRKFILES, MSONLY, DUAL, UPWARD, MINCHECK) . . ............ 79 11.4.4 Control of Printed and Punched Output (MSPRINT, STATUS, DSTATUS, PUNCH, MSPUNCH, NOPRINT) ...... ............... ... 83 11.4.5 Implicant Elimination Based on Size and Importance (MAXSIZE, MODSIZE, IMPORT) .. ...... .. 89 11.5 Program Implementation ......... ................. ... 92 11.6 Specifications for Assembler Routines .... .......... ... 95 REFERENCES .................. ............................. .... 97 I I I I I I I I I II INTRODUCTION The analyst who seeks to determine reliability characteristics of a complex system, such as a nuclear reactor, in terms of the reliability characteristics of its subsystems and components confronts a number of difficult tasks. One task involves identification either implicitly or explicitly, of logical modes of system si'. .wis or failure, that is, various distinct combinations of subsystems whose mutual success or failure implies success or failure of the entire system. Minimal cut set and path set families, tools familiar to reliability analysts for some time, provide an explicit representation of these modes. These families are useful not only re~valuating reliability characteristics of a system but also as tool to guide system modifications for enhancing reliability. A widely used concept in reliability analysis of complex systems is that of a fault tree. Fault tree methods are based on the observa- tion that the system state, either working or failed, can usually be expressed as a Boolean relation between states of several large, readily identifiable subsystems. The state of each subsystem in turn depends on states of simpler subsystems and components which compose it, so the state of the system itself is determined by a hierarchy of logical relationships between states of subsystems. A fault tree is a graphical representation of these relationships. At the lowest level of the hierarchy are sulsystems whose success or failure dependence is not further described. If reliability informa- tion is available for these lowest level subsystems, then it may be possible to use this information to deduce reliability characteristics of the system itself. S-I 2 An analyst who prepares a system fault tree often does so with the intention of utilizing it to obtain certain minimal cut (or path) set families in terms of these lowest level subsystems and components. Part I of this discussion outlines a computer-oriented methodology for deriving such families for an arbitrary fault tree. Part II describes the use of the Fault Tree Analysis Program (FTAP), an extensive computer package, written mostly in FORTRAN, which implements the Part I methodology. FTAP has a number of useful features that make it well-suited to nearly all fault tree applications. An input fault tree to this program may specify the system state as any logical function of sub- system or component state variables or complements of these variables; thus, for instance, exclusive -. or type relations may be formed. When fault tree logical relations involve complements of state variables, the concept of a minimal cut set family is no longer particularly useful, so in this case the analyst may instruct FTAP to produce a family of prime implicants, a generalization of the minimal cut set concept. The program offers the flexibility of several distinct methods of generating cut set families, and these methods may differ considerably in efficiency, depending on the particular tree analyzed. FTAP can also identify certain subsystems as system modules and provide a collection of minimal cut set families that essentially expresses the state of the system as a function of these module state variables. This collection is a compact way of representing the same information as contained in the system minimal cut set family in terms of lowest level subsystems and components. Another feature allows a useful subfamily to be obtained when a family 3 of minimal cut sets or prime implicancs is too large to be found in its entirety; this subfamily may consist of only sets not con- taining more than some fixed number of elements or only sets that are "interesting" to the analyst in a special sense. Finally, the analyst can modify the input fault tree in various ways by declaring state variables identically true or false. A number of computer programs are currently available for obtaining minimal cut set families from fault trees, and some of these programs are mentioned in the discussion of Part I. One very capable package that deserves special mention is the SETS program developed by Dr. Richard Worrell of Sandia Laboratories [18], In addition to fault trde analysis, SETS manipulates arbitrary Boolean expressions. For fault tree work, several features of FTAP and SETS are similar. and both programs have been used with good results during the past year in nuclear reactor safety studies conducted by Dr. Howard Lambert of the Lawrence Livermore Laboratories. !z(