Combining Dynamic Fault Trees and Event Trees for Probabilistic Risk Assessment

Hong Xu, University of Virginia, Charlottesville Joanne Bechta Dugan, Ph.D., University of Virginia, Charlottesville
Key Words: dynamic fault tree, event tree, Markov Chain, module SUMMARY & CONCLUSIONS As system analysis methodologies, both event tree analysis (ETA) and fault tree analysis (FTA) are used in probabilistic risk assessment (PRA), especially in identifying system interrelationships due to shared events. Although there are differences between them, ETA and FTA, are so closely linked that fault trees (FT) are often used to quantify system events that are part of event tree (ET) sequences (Ref. 1). The logical processes employed to evaluate ET sequences and quantify the consequences are the same as those used in FTA. Although much work has been done to combine FT and ET, traditional methods only concentrate on combining static fault trees (SFT) and ET. Our main concern is considering how to combine dynamic fault trees (DFT) and ET. We proposed a reasonable approach in this paper, which is illustrated through a hypothetical example. Because of the complexity of dynamic systems, including the huge size and complicated dependencies, there may exist contradictions among different dynamic subsystems. The key benefit of our approach is that we avoid the generation of such contradictions in our model. Another benefit is that efficiency may be improved through modularization. 1. INTRODUCTION An ET is a graphical representation of mitigating or aggravating events that may occur in response to some initiating event or perturbation in the system. As the number of events increases, the picture fans out like the branches of a tree (Refs. 2, 3). ETA was first introduced for the nuclear industry and since then has been applied in diverse industries. ETA techniques are helpful to identify the consequences that can result in the following occurrence of a potentially hazardous event. Figure 1 is a simple example of a propellant supply system (Ref. 2). The initiating event is the induced hazard inadvertent release of hydrogen, which forms the beginning of the ET. From here, the tree branches into the two possible responses that the hydrogen detector can have, namely to detect or not to detect the released hydrogen. Each of these possible events in turn branches into the two possible states that the cutoff valve can either close or remain open when commanded shut. As the figure indicates, hydrogen is contained only along the path in which both the detector and cutoff valve operate.

Figure 1. Event tree for a propellant supply system A FT is another kind of graphical representation, which is constructed by defining the TOP undesired event and then using backward logic to define causes. Basic events at the bottom of the fault tree are linked via logic symbols (known as gates) to one or more higher-level events (Ref. 2). FTA techniques have been widely adopted by a wide range of engineering disciplines as one of the primary methods of performing reliability and safety analysis. Figure 2 is a simple example of SFT for a hypothetical washing machine system. The FT structure function for the example is that the system would fail (i.e. overflow) if either the valve fails OR both the timeout control and the full sensor fail.

Figure 2. Fault tree for a washing machine system Although ETA and FTA are quite different in the structure forms, the logic orders and so on, they are often used together. The standard approach to combine FT and ET is that the branch point of an ET can be treated as a FT. The probability

of the top event of the FT serves as the branch probability for the ET. In dealing with FTs, much work has been done involving minimal cut set (MCS) or prime implicant (PI)based methods (Ref. 7). J.D. Andrews and S.J. Dunnett proposed a BDD-based approach to combine SFT and ET so as to overcome the inefficiency and inaccuracy of previous methods for non-coherent systems (Refs. 1, 4, 5). Our goal is to consider the possibility and a feasible way to combine DFT and ET, which has not been studied in previous work. We organize the paper as follows: a brief comparison of ET and FT is given to indicate their relationship in section 2. Section 3 then identifies three different cases to consider when combining FT and ET, including static systems, dynamic systems with no shared events and dynamic systems with shared events. In order to illustrate the 3rd case that includes dynamic subsystems and shared events, a hypothetical example is used and analyzed in section 4. Section 5 includes the future work. 2. A BRIEF COMPARISON OF ET AND FT ET and FT are quite different in many aspects. An ET is an inductive or forward logic representation, which starts from an initiating event and includes all possible paths, whose branch points represent successes and failures (sometimes can also represent partial failures). The quantification of an ET is used to predict frequency of each outcome (Ref. 1). While a FT is a deductive or backward logic representation, which involves specifying a top event to analyze (always a system failure), followed by identifying all of the associated elements in the system that could cause that top event to occur. Although there exist differences between ET and FT, they are closely related to each other. The first thing is that the same system can be represented either by an ET or a FT. Figure 3 shows the ET structure for the same washing machine system in figure 2, whose outcomes tell us that the system would fail if either the end point F1 or F2 occurs, namely both the timeout control and the full sensor fail OR the valve fails.

3. PREVIOUS WORK TO COMBINE SFT AND ET Some researchers have realized the benefit and possibility of combining FT and ET for PRA. For a static coherent system where the branch point events of an ET are independent of each other, quantification is easy to achieve by multiplying the frequency of the initiator and the probabilities of passing along each branch leading to an outcome scenario. The exact probability of each branch point can be obtained by Inclusion-Exclusion Expansion (IEE) approach given in Equation (1). Ci is the MCS, while P(T ) is the top event probability. Figure 4 shows the process to combine SFT and ET for a simple static coherent system. In the ET shown in figure 4 (c), each branch point is replaced with a SFT.
P(T ) = P(Ci )
i =1 n

all i < j

P(C C ) + P(C C
i j i all i < j <k

Ck ) + L

+ (1) n+1 P(C1 C2 L Cn )

(1)

(a) FT of the system

(b) FT of two subsystems

(c) ET of a static system with no shared events Figure 4. Combine SFT and ET for a static coherent system If a static coherent system is very large, approximation calculating is adopted to yield a result of acceptable accuracy, either using IEE by truncating terms after the first or second one or using MCS upper-bound shown in equation (2).
P (T ) 1 (1 P ( C i )
i =1 n

(2)

Figure 3. Event tree for the washing machine system The second connection between FT and ET is that the branch point events of an ET can be defined using FT structures. We are more interested in this point and will discuss three cases below.

However, the approaches used in a static coherent system are not useful for a static non-coherent system, such as a system shown in figure 5, whose subsystems X1 and X2 have some shared events. Because the convergence of IEE can be very slow and truncating a large number of terms will lead to inaccuracy, therefore J.D. Andrews and S.J. Dunnett provide a

BDD-based approach, which overcomes these shortcomings (Ref. 1).

(c) Conversion for subsystem X1 using MC

A&E

Figure 5. FT of two dependent subsystems 4. COMBINE DFT AND ET So far, all cases above only concentrate on static systems; no research has considered the relationship between DFT and ET. Although various solution techniques have been utilized in DFT analysis (Ref. 8), the question is can we use these techniques to combine DFT and ET? If yes, how? In this section we will look at some dynamic systems, and use MC, the normal tool to show our idea. 4.1 Combine DFT and ET Without Shared Events
dy na m ic s ys tem 1

C fails

D fails

failed
--

CD

X2

D fails C

C fails

(d) Conversion for subsystem X2 using MC

X1 HSP

X2

(e) ET of the system

Figure 6. Combine DFT and ET with no static subsystems and no shared events For dynamic systems where no dependencies exist in different subsystems, each subsystem can be resolved separately, either using a MC for any subsystem, or a MC for a dynamic one and a combinatorial tool such as BDD for a static one. For simplicity, only MC is used in our example. Since each state in a MC represents either UP or DOWN of the corresponding subsystem, it is easy to represent any branch point of an ET via MC, with UP states representing the positive branch point and DOWN states representing the negative branch point. Two examples are given in figure 6 and figure 7, one with only dynamic subsystems, the other with both static and dynamic subsystems. Since no common or shared events across two or more branch point events, the methods applied in the two examples are the same.
dynamic system 2

(a) FT of dynamic system 1

x2

OK

x2
D

F1

x1

F2

(b) ET of the system

failed
B A fails
AB

X1

X2 HSP

B fails

--

X1
A B C D

B fails A A fails

ok
- -*

(a) FT of dynamic system 2

x1
X1

x2

OK

X2 HSP

x2
E

F1

x1

F2

(b) ET of the system replacing branch point with FT

problems with the two servers. For X3, since the system manager can work on the servers directly, the occurrence of the top event is simple to analyze. Based on figure 8, both X1 and X2 include two parts, one is a static part in the dotted circle on the left, the other is a dynamic part in the dotted circle on the right shown in figure 8 (a) and (b); X3 is only composed of one dynamic part. After considering all shared events among these parts, we combine all related dynamic parts to obtain one module, and combine all non-related static parts to obtain another module. For the new-formed dynamic module, we use MC shown in figure 9 and the corresponding ET shown in figure 10 to explain the details of our idea. Table 1. Basic Event Names Symbol P T A/B D E F Definition personal computer of the customer terminal in the bank primary/backup server in the bank local power supply service backup power supply service in the bank UPS for the customers computer
X1

(c) ET of the system replacing branch point with MC Figure 7. Combine ET and DFT with no shared events 4.2 Combine DFT and ET With Shared Events For dynamic systems with shared events, on one hand, like static non-coherent systems, we cannot treat subsystems independently due to the dependencies. On the other hand, unlike the BDD-based approach used in a static system, De Morgans Laws are not suitable for dynamic systems. Therefore we are now facing two problems: one is to avoid constructing a single MC for each subsystem both because of the dependencies and the unnecessary redundant work due to shared events; the other is to look for a way to represent all branch points of an ET, especially the negative points. Further more, it is unreasonable to construct one MC for the whole system due to the obvious disadvantage of MC that the size would face a state-space explosion problem with the increase of the number of events. A feasible and efficient way is to make use of the concept of modularization by analyzing all related units within one module, and deal with all non-related modules independently (Refs. 6, 9). This methodology is illustrated by a hypothetical bankaccount-access example shown in figure 8-10. Three subsystems X1, X2 and X3 are depicted in figure 8(a)-(c). X1 describes the failure of the first way to access a bank account, which is achieved by a customer operating his/her own personal computer through Internet. X2 means the failure of the second way, through a teller operating one of all three terminals in the bank. The third way occurs under an emergency situation, done by the bank computer system manager operating on a server directly, whose failure structure is represented by X3. Basic event names are defined in table 1. For X1, the top event may be caused by either the failure of the personal computer or the failures of both the two bank servers, whose normal working conditions both depend on the power supply service. Once the local power cannot be supplied, UPS will continue to provide the power a period of time long enough. For X2, the top event will happen if all three terminals cannot be used (may due to the hardware reason or being unavailable of all tellers in the bank) or there are some

F D E P -D F -A B
FDE P

H S P -A -B HSP

H S P -D -F A HSP A B B

(a) FT of subsystem X1 --- accessing by the customer

AND-3*T

FDEP-DE-AB
FDEP

HSP-A-B HSP

3*T

HSP-D-E A HSP A B B

(b) FT of subsystem X2 --- accessing by tellers

F D E P -D E -A B
FD EP

H S P -A -B H SP

H SP-D-E A HSP A B B

(c) FT of subsystem X3 --- accessing by the system manager Figure 8. DFTs for three subsystems of a dynamic system with shared events

x1x2x3:

000

100

111

Figure 9. MC for the dynamic module Figure 9 shows the MC of the dynamic module, which involves all related parts, including shared events A, B, D, E and F. Since this MC is affected by all three subsystems, we use three bits to indicate the UP or DOWN status for these subsystems respectively, with 0 meaning UP and 1 meaning DOWN. For instance, 100 means X1 is down while both X2 and X3 are up. From figure 9, there are totally three different groups of states (000, 100 and 111). Any other results (e.g. 011, 001) are impossible otherwise there should exist some contradictions. With such a 3-bit vector, all branches of the ET can be efficiently obtained, whose results are shown in figure 10 (0 branches are those impossible to appear).

Figure 11. ET for the static module units, there is no chance to let X3 down in this static module, so any branch going along X 3 should be impossible. We use 0 to represent such case in figure 11. The final results for the whole system ET are formed after combining the two ETs of figure 10 and 11, listed in table 2. Three end points are impossible to appear, which implies that once the third way fails to access the bank account (X3 occurs), there is no possibility to reach the goal by other two ways.

Figure 10. ET for the dynamic module Following the same way, we can obtain the equivalent ET for the static module shown in figure 11. Based on figure 8, X3 has no static units then is unrelated to the static module; but it has also been included in this ET, so that the two ET structures of dynamic and static modules are the same then we can easily compare their each corresponding branch to get a final ET for the whole system. Also because X3 has no static
Mark Up/Down Impossible 000

Table 2. The Results of ET

4.3 Modified MC We need note that the MC in figure 9 is a little different from those used in previous systems, because the letter (e.g. A, B) of each state in a traditional MC represents that the corresponding event/component is available. While in our example, the letter in each state represents the actual operational physical situation of the corresponding event/component. For example, in subsystem X1, the failures of D and F will lead to the unavailability of both A and B. We use AB - E - to represent the state in our current MC rather than use - - - E - to represent such state in a traditional MC. The reason is that one unavailable event in one subsystem, may be still available for another subsystem due to different causes. Since we only construct one MC for all related dynamic units in this example (they are grouped into one module), it is not reasonable to represent such an event by simply using a symbol -. 5. FUTURE WORK Based on our hypothetical example in this paper, the process in combining DFT&ET and the corresponding results appear to hold promise. However, considering the diversity of dynamic systems and the disadvantages of MC, our work so far has just started at the beginning, there is still much work need to do. In order to develop a general methodology, two issues would be our concerns in the next step. The first is that we need consider enough different examples besides the hypothetical one, which would be helpful for us to find their common features. The second one is that we will concentrate more on quantitative analysis as well as qualitative analysis. We aim to develop such a general methodology that it can be used to analyze any dynamic system. ACKNOWLEDGMENTS We would like to thank NASA Langley Research Center under NASA Contract NAS1-02076, by which the work reported in this paper was funded. REFERENCES 1. Andrews JD, Dunnett SJ, "Event Tree Analysis using Binary Decision Diagrams", IEEE Trans. Reliability, Vol 49, 2000 Jun, pp 230 - 238. 2. William R. Dunn, Practical Design of Safety-Critical Computer Systems, Reliability Press 2002, pp 166 176. 3. Relex Software Corporation, Visual Reliability Software, URL: http://www.event-tree.com. 4. Rauzy, A., "A Brief Introduction to Binary Decision Diagrams". European Journal of Automation, Vol 30, No.8, 1996. 5. Sinnamon, R.M. and Andrews, J.D., "Quantitative Fault Tree Analysis Using Binary Decision Diagrams", European Journal of Automation, Vol 30, No.8, 1996. 6. Gulati, R. and JB Dugan, "A Modular Approach for Analyzing Static and Dynamic Fault Trees," 1997 Proceedings of the Annual Reliability and Maintainability

Symposium, Philadelphia, Pennsylvania, Jan. 1997, pp 5763. 7. Y.Dutuit, A.Rauzy, Exact and truncated computations of prime implicants of coherent and noncoherent fault trees with Aralia, Reliability Engineering and System Safety, 58(1997)127-144. 8. Ragavan Manian, Joanne Bechta Dugan, David Coppit, and Kevin Sullivan, Combining various solution techniques for dynamic fault tree analysis of computer systems. In Proceedings Third IEEE International HighAssurance Systems Engineering Symposium, pages 21-28, Washington, D.C., 13-14 November 1998. IEEE. 9. Y. Dutuit and A. Rauzy, Alinear time Algorithm to find Modules of Fault Trees, IEEE Transactions on Reliability, Vol. 45, No. 3, September 1996, pp.422-425. BIOGRAPHIES Hong Xu Department of Electrical and Computer Engineering University of Virginia 351 McCormick Road PO Box 400743 Charlottesville, Virginia 22904-4743 USA e-mail: hx5s@virginia.edu Hong Xu received her B.S. degree in Computer Science and Engineering from Beijing University of Aeronautics and Astronautics, Beijing, China, in 1995. She is now a graduate student in the Department of Electrical & Computer Engineering at the University of Virginia. Joanne Bechta Dugan, Ph.D. Department of Electrical and Computer Engineering University of Virginia 351 McCormick Road PO Box 400743 Charlottesville, Virginia 22904-4743 USA e-mail: jbd@virginia.edu Joanne Bechta Dugan was awarded the B.A. degree in Mathematics and Computer Science from La Salle University, Philadelphia, PA in 1980, and the M.S. and Ph.D. degrees in Electrical Engineering from Duke University, Durham, NC in 1982 and 1984, respectively. Dr. Dugan is currently Professor of Electrical and Computer Engineering at the University of Virginia. She has performed and directed research on the development and application of techniques for the analysis of computer systems that are designed to tolerate hardware and software faults. Her research interests include hardware and software reliability engineering, fault tolerant computing, and mathematical modeling using dynamic fault trees, Markov models, Petri nets, and simulation. Professor Dugan is a member of Phi Beta Kappa, Eta Kappa Nu, Tau Beta Pi and IEEE; is an IEEE Fellow; was Associate Editor of the IEEE Transactions on Reliability for 10 years; and is currently Associate Editor of the IEEE Transactions on Software Engineering. She is a past winner of both the P.K. McElroy and the Alan O. Plait Awards.