Rare event simulation for non-Markovian repairable fault trees
CC Attribution 3.0 Germany:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Budde, Carlos E.
Monti, Raúl E.
Dynamic fault trees (DFTs) are widely adopted in industry to assess the dependability of safety-critical equipment. Since many systems are too large to be studied numerically, DFTs dependability is often analysed using Monte Carlo simulation. A bottleneck here is that many simulation samples are required in the case of rare events, e.g. in highly reliable systems where components fail seldomly. Rare event simulation (RES) provides techniques to reduce the number of samples in the case of rare events. We present a RES technique based on importance splitting, to study failures in highly reliable DFTs. Whereas RES usually requires meta-information from an expert, our method is fully automatic: By cleverly exploiting the fault tree structure we extract the so-called importance function. We handle DFTs with Markovian and non-Markovian failure and repair distributions—for which no numerical methods exist—and show the efficiency of our approach on several case studies.
 Welcome everybody to this talk, where along with my colleague Carlos Bude we're going to present you our work relevant simulation for non-Marcovian repairable fault trees. This is a joint work between the Dependable System Group of the National University of Córdoba in Argentina and the Formal Methods and Tool Group at the University of Twente in the Netherlands. I will walk you through the first part of the talk where I will tell you what a fault tree is and how complex it can get. I will also dive a little bit into input-outpost-tocastic automata, which we used to give semantics to one of the most complicated variations of fault trees in order to be able to analyze their reliability. Then Carlos will present you relevant simulation and will also present you the main contribution of our work, which are heuristics for the automatic derivation of importance functions which are at the core of relevant simulation methodology. So fault trees are just a graphical way of representing the failure of a system as the combination of failures of smaller parts of the system. These failures of smaller parts of the system are referred to as basic events and they conform the lower layer of the tree. These failures are combined by gates, which are at the same time combined by other gates, all up to you get to the top gate, which we refer to as the top level event and represents the failure of the system under study. So fault trees enable fault tree analysis, which is used to calculate the reliability of a system. You do this by assigning first a formal semantics to the gates and to the basic events and then doing some numerical calculation or statistical calculations in order to calculate the reliability. So while fault trees can be very simple and just have gates as in the static fault trees, logical gates as in the static fault trees, they can get a little more complicated and even include repair boxes, which allow to repair these parts that get broken. In this case and in the case where the failures and repairs respond to general probability distributions and not only Markovian ones, approaching the fault tree analysis with numerical methods is just infeasible because of the complexity between the repairs and the failures of the basic elements. So for this case, we actually propose to use simulation, but in order to simulate on our trees, we need to first give them a formal semantic, which allows to simulate on them. So it should be a formal semantic that's deterministic. So you always know what's the next step to simulate. So we propose to use input-outpost-tocastic automatas. Input-outpost-tocastic automatas use clocks to control the occurrence of events. They are guarding the events. So clocks get assigned a value according to a sample from their probability distribution that is assigned to that clock. And when a clock expires, all clocks count down at the same time and when a clock expires, it may enable a transition. Clocks can also be reset in the transitions to new value samples from their probability distributions. So input-outpost-tocastic automata has some rules to build them up and they ensure that the final model is simulatable. So it's deterministic. They are compositional and they can be known Markovian. To model actually a full tree using the language of input-outpost-tocastic automata, we use this symbolic language very similar to that of prism. But actually to build the trees, we give a simpler language as just a declarative language where you can define a full tree similar to the way you do it with the Galileo language, which is the most famous one for defining full trees. So to illustrate how we use simulation to analyze the reliability of the full trees, let's take this simple example where the top level event is just the combination of all the failures of the basic event. So if they all fail at the same time, then the top level event will fail. So calculating the reliability up to a time horizon t is just calculating the probability of all these basic events being failed at the same times. Then in the most basic case of simulation, we just use Monte Carlo's where we run a lot of simulations and we just write down how many of those runs reach the actual top level event. So how many of the runs were we able to see that all the basic events were failed at the same time. Then we just divide those amounts of runs between the total amount of runs and we get our reliability value, the one we were looking for, the probability. So of course, when the system we are studying is a system that's designed to be full tolerant or resilent, the probability of actually reaching this event in a run is very low. And the amount of runs you have to make to have some confidence in the results you get by Monte Carlo simulation is immense. So it's actually not the best approach for analyzing these kind of trees which are highly resilent. So for this we propose another way of simulating which is Red Event Simulation and which Carlos is going to present you now. So there are many ways to do Red Event Simulation to overcome this problem. One of them is called important splitting. Essentially it starts like standard Monte Carlo and when we have a trace that evolves in time, when it approaches the red event that we want to observe, we clone this trial so we split it into trials that evolve independently from now on. Some of them may get truncated for different reasons, some of them may further approach our event of interest upon which we do the splitting again. So eventually we will observe some events that we want to count. When all the simulations are done, then we can estimate the probability of Red Event by counting the number of successes and dividing that by the maximum amount of splitting that we could have had. The details are not important now, this is well known theory. What matters is that the efficiency of my method depends crucially on how much do we split on each of these thresholds, where the thresholds are located and this notion of importance. So in this important splitting way of doing Red Event Simulation, we have a function called the importance function that assigns a value to a state called its importance which should be proportional to the probability of observing the red event from that state. So the higher the importance, the more likely to observe the red event from a given state. And this function can be easily performed for some systems, for instance in the AND gate here, we know that the more basic events that are failed, the closer we are to observing a propagation of a top level event here. So by counting the number of failed basic events, essentially we have an ocean of importance function. But already for priority AND gates, this is more difficult because we then need to also take into consideration the order in which things have failed. So essentially the take home is that this importance function is hard to come by for general systems and you usually record an expert, both in the system that you are modeling and in the modeling approach that you use, so the modeling form is in. Our contribution for this paper was to come up with a notion of importance function that can be deducted inductively from the faultless structure. This can be worked for repairable dynamic faultless. It doesn't matter the kind of distributions that the failures and repairs have, they can be normal Cobbian and this can be used to estimate tracing as steady state metrics. So let me walk you through the construction of this importance function. Let's start from the simplest case, for tree which is just a BE, a basic element. We have something that is fail operational, so we can use as importance function only two values. So we give it importance 1 when the system is failed, when the BE is failed, and importance 0 when this operation. That was very easy. Let's go a little bit more complex to an AND gate. We know that we could just add together the states of these things, so count the number of failed basic events and call that the importance of my AND gate. But then this is the same given the previous equation to the summation of the importance of these basic events. So now we have written the importance of my AND gate as a function of the importance of its children. But this can be extended to arbitrary subtree. So in this case we have a voting gate, the voting gate count up to k fail elements out of its held children and then it fails. So again we can write the importance of the AND gate as the summation between the importance of this child plus the importance of this other child. So we have the same structure as before. Notice however that from the AND gate perspective the failure of either of its children is equally important. So it's in a sense unbalanced that the failure of this child can add up to let's say one importance unit, whereas the failure of this child can add up to k importance units. Because they both are equally important in terms of contributing to the failure of the AND gate. So instead of just adding these things together we have to scale these functions so that they contribute equally in terms of importance to the failure of the AND gate. So to do that we use a scaling factor that we are going to introduce next. This is how we presented the importance function in the paper. I'm going to present an alternative definition for this explanation. I just do this to show you that for each of these gates we are writing the importance of the gate as a function of its children, of the importance of its children, a scale by certain factor that makes them all kind of level equally together so that each of the child contributes equally to the importance of the gate. So the functions for the basic, the static gates are only just a function of the children. For the dynamic gates we also have to take into consideration the state of the gate itself because there's some information there of how close is the gate to failing. Remember for instance the case of the priority AND gate that I mentioned before where we have to take into consideration the order of failure of events. When we do that here, this is an importance function for a binary priority AND and essentially if the right child failed first, this value becomes minus 1 so the importance is decreased. So essentially this is a way in which we can construct inductively the importance function on a tree by starting on its top level event and propagating, depending on the case of the gate, each of these importance until we reach the level of the basic events. So this is what Raoul called heuristic to build the importance function which we use on several experiments to see its efficiency to implement rate event simulation. Before that we constructed a tool chain which takes a repairable fault tree model, gives a Yoast as a semantics as Raoul explained and then we also use the structure of the fault tree to build the importance function and give it to FIG, a statistical model checker that can perform rate event simulations, importance splitting, to compute transient and steady state measures. We did use this tool chain on several case studies of different complexities and sizes and I wanted to mention just that the fail and repair times of the PDFs of the basic events really use various normal code and distributions to just experiment with the tool chain. So what does an experiment consist in? For instance let's take the fault tolerant pattern processor, a standard benchmark in fault tree analysis and let's say that we want to compute its unreliability. So the probability of failure of this system within a time horizon T. We estimate this value as a confidence interval doing statistical model checking, in particular the rate events and we know that a good algorithm is we give it a time limit, it's going to give us back a confidence interval which is very narrow, the width of this confidence interval is going to be very small. So how do we compare different algorithms and how do we put our importance function here into the picture? Well essentially we are going to estimate the unreliability of this system using standard multi-carrel on one side and on the other side we are going to use different algorithms of rate event simulation which use as a backend the importance function that we compute from this structure automatically using the method that I just mentioned. Now to see how this increases in efficiency as the system becomes more resilient we parameterize all our models for the fault tolerant pattern processor we increase the number of spares here, the more spares that we have here the more resilient the system is and the lower the probability of failure given a fixed time horizon. So for these three variants of the FTPP we tested all our algorithms and checked the width of the confidence interval built for a given time limit in runtime of execution. So the algorithm that could achieve the narrowest interval in the most resilient case is the most efficient algorithm. So we did this for different systems each with its own parameterization we studied transient and also steady state properties of the systems, all the details are in the paper. I just want to focus on the results a little bit to show you that well as expected the more resilient any of these systems became the more the bridge between the standard Monte Carlo and the rate event simulators that use our importance function as a backend right? So that's essentially what we wanted to observe that our importance function is an efficient automatic way to implement rate event simulation. These are the results for the transient analysis so for unreliability we have similar outcomes for the steady state analysis of unavailability. Then as the system become more resilient essentially the rate event simulation methods that use our importance function can build for the same time limit of simulation a narrower confidence interval than standard Monte Carlo. I also wanted to perform a live demo with the tool that we use for this tool chain but essentially we are already out of time already so I just mentioned you to this tool demo paper which includes an artifact which you can try on your own and with which you can reproduce many of the experiments that I showed here. So to conclude we showed how to implement Yoast as a Mantis for DFTs, I mean we showed that we have a tool that implements this and we did show how to build an importance function inductively from the structure of a dynamic for tree that can be repairable to perform rate event simulation on it in a way that is as automatic as standard Monte Carlo but is much more efficient to compute metrics when we are talking of rate events and we have a tool chain that can implement all of this. As future work we wanted to for instance try other importance functions based on the FD structure we actually did this already this was in an MMB paper with Marielle and me and other things we want to do in the near future specifically this one for instance is to put information on the time limit that we have for instance for transient analysis of unreliability into the importance function instead of just counting the number of failed things in general. So this is a snapshot of the people that contributed to this and that was our contribution to Tecas 2020.
 Welcome everybody to this talk, where along with my colleague Carlos Bude we're going  to present you our work relevant simulation for non-Marcovian repairable fault trees.  This is a joint work between the Dependable System Group of the National University of  Córdoba in Argentina and the Formal Methods and Tool Group at the University of Twente  in the Netherlands.  I will walk you through the first part of the talk where I will tell you what a fault  tree is and how complex it can get.  I will also dive a little bit into input-outpost-tocastic automata, which we used to give semantics  to one of the most complicated variations of fault trees in order to be able to analyze  their reliability.  Then Carlos will present you relevant simulation and will also present you the main contribution  of our work, which are heuristics for the automatic derivation of importance functions  which are at the core of relevant simulation methodology.  So fault trees are just a graphical way of representing the failure of a system as the  combination of failures of smaller parts of the system.  These failures of smaller parts of the system are referred to as basic events and they conform  the lower layer of the tree.  These failures are combined by gates, which are at the same time combined by other gates,  all up to you get to the top gate, which we refer to as the top level event and represents  the failure of the system under study.  So fault trees enable fault tree analysis, which is used to calculate the reliability  of a system.  You do this by assigning first a formal semantics to the gates and to the basic events and then  doing some numerical calculation or statistical calculations in order to calculate the reliability.  So while fault trees can be very simple and just have gates as in the static fault trees,  logical gates as in the static fault trees, they can get a little more complicated and  even include repair boxes, which allow to repair these parts that get broken.  In this case and in the case where the failures and repairs respond to general probability  distributions and not only Markovian ones, approaching the fault tree analysis with numerical  methods is just infeasible because of the complexity between the repairs and the failures  of the basic elements.  So for this case, we actually propose to use simulation, but in order to simulate on our  trees, we need to first give them a formal semantic, which allows to simulate on them.  So it should be a formal semantic that's deterministic.  So you always know what's the next step to simulate.  So we propose to use input-outpost-tocastic automatas.  Input-outpost-tocastic automatas use clocks to control the occurrence of events.  They are guarding the events.  So clocks get assigned a value according to a sample from their probability distribution  that is assigned to that clock.  And when a clock expires, all clocks count down at the same time and when a clock expires,  it may enable a transition.  Clocks can also be reset in the transitions to new value samples from their probability  distributions.  So input-outpost-tocastic automata has some rules to build them up and they ensure that  the final model is simulatable.  So it's deterministic.  They are compositional and they can be known Markovian.  To model actually a full tree using the language of input-outpost-tocastic automata, we use  this symbolic language very similar to that of prism.  But actually to build the trees, we give a simpler language as just a declarative language  where you can define a full tree similar to the way you do it with the Galileo language,  which is the most famous one for defining full trees.  So to illustrate how we use simulation to analyze the reliability of the full trees,  let's take this simple example where the top level event is just the combination of all  the failures of the basic event.  So if they all fail at the same time, then the top level event will fail.  So calculating the reliability up to a time horizon t is just calculating the probability  of all these basic events being failed at the same times.  Then in the most basic case of simulation, we just use Monte Carlo's where we run a lot  of simulations and we just write down how many of those runs reach the actual top level  event.  So how many of the runs were we able to see that all the basic events were failed at the  same time.  Then we just divide those amounts of runs between the total amount of runs and we get  our reliability value, the one we were looking for, the probability.  So of course, when the system we are studying is a system that's designed to be full tolerant  or resilent, the probability of actually reaching this event in a run is very low.  And the amount of runs you have to make to have some confidence in the results you get  by Monte Carlo simulation is immense.  So it's actually not the best approach for analyzing these kind of trees which are highly  resilent.  So for this we propose another way of simulating which is Red Event Simulation and which Carlos  is going to present you now.  So there are many ways to do Red Event Simulation to overcome this problem.  One of them is called important splitting.  Essentially it starts like standard Monte Carlo and when we have a trace that evolves in time,  when it approaches the red event that we want to observe, we clone this trial so we split  it into trials that evolve independently from now on.  Some of them may get truncated for different reasons, some of them may further approach  our event of interest upon which we do the splitting again.  So eventually we will observe some events that we want to count.  When all the simulations are done, then we can estimate the probability of Red Event  by counting the number of successes and dividing that by the maximum amount of splitting that  we could have had.  The details are not important now, this is well known theory.  What matters is that the efficiency of my method depends crucially on how much do we  split on each of these thresholds, where the thresholds are located and this notion of  importance.  So in this important splitting way of doing Red Event Simulation, we have a function called  the importance function that assigns a value to a state called its importance which should  be proportional to the probability of observing the red event from that state.  So the higher the importance, the more likely to observe the red event from a given state.  And this function can be easily performed for some systems, for instance in the AND gate  here, we know that the more basic events that are failed, the closer we are to observing  a propagation of a top level event here.  So by counting the number of failed basic events, essentially we have an ocean of importance  function.  But already for priority AND gates, this is more difficult because we then need to also  take into consideration the order in which things have failed.  So essentially the take home is that this importance function is hard to come by for  general systems and you usually record an expert, both in the system that you are modeling  and in the modeling approach that you use, so the modeling form is in.  Our contribution for this paper was to come up with a notion of importance function that  can be deducted inductively from the faultless structure.  This can be worked for repairable dynamic faultless.  It doesn't matter the kind of distributions that the failures and repairs have, they can  be normal Cobbian and this can be used to estimate tracing as steady state metrics.  So let me walk you through the construction of this importance function.  Let's start from the simplest case, for tree which is just a BE, a basic element.  We have something that is fail operational, so we can use as importance function only  two values.  So we give it importance 1 when the system is failed, when the BE is failed, and importance  0 when this operation.  That was very easy.  Let's go a little bit more complex to an AND gate.  We know that we could just add together the states of these things, so count the number  of failed basic events and call that the importance of my AND gate.  But then this is the same given the previous equation to the summation of the importance  of these basic events.  So now we have written the importance of my AND gate as a function of the importance  of its children.  But this can be extended to arbitrary subtree.  So in this case we have a voting gate, the voting gate count up to k fail elements out  of its held children and then it fails.  So again we can write the importance of the AND gate as the summation between the importance  of this child plus the importance of this other child.  So we have the same structure as before.  Notice however that from the AND gate perspective the failure of either of its children is equally  important.  So it's in a sense unbalanced that the failure of this child can add up to let's say one  importance unit, whereas the failure of this child can add up to k importance units.  Because they both are equally important in terms of contributing to the failure of the  AND gate.  So instead of just adding these things together we have to scale these functions so that they  contribute equally in terms of importance to the failure of the AND gate.  So to do that we use a scaling factor that we are going to introduce next.  This is how we presented the importance function in the paper.  I'm going to present an alternative definition for this explanation.  I just do this to show you that for each of these gates we are writing the importance  of the gate as a function of its children, of the importance of its children, a scale  by certain factor that makes them all kind of level equally together so that each of  the child contributes equally to the importance of the gate.  So the functions for the basic, the static gates are only just a function of the children.  For the dynamic gates we also have to take into consideration the state of the gate itself  because there's some information there of how close is the gate to failing.  Remember for instance the case of the priority AND gate that I mentioned before where we  have to take into consideration the order of failure of events.  When we do that here, this is an importance function for a binary priority AND and essentially  if the right child failed first, this value becomes minus 1 so the importance is decreased.  So essentially this is a way in which we can construct inductively the importance function  on a tree by starting on its top level event and propagating, depending on the case of  the gate, each of these importance until we reach the level of the basic events.  So this is what Raoul called heuristic to build the importance function which we use  on several experiments to see its efficiency to implement rate event simulation.  Before that we constructed a tool chain which takes a repairable fault tree model, gives  a Yoast as a semantics as Raoul explained and then we also use the structure of the  fault tree to build the importance function and give it to FIG, a statistical model checker  that can perform rate event simulations, importance splitting, to compute transient and steady  state measures.  We did use this tool chain on several case studies of different complexities and sizes  and I wanted to mention just that the fail and repair times of the PDFs of the basic events  really use various normal code and distributions to just experiment with the tool chain.  So what does an experiment consist in?  For instance let's take the fault tolerant pattern processor, a standard benchmark in  fault tree analysis and let's say that we want to compute its unreliability.  So the probability of failure of this system within a time horizon T. We estimate this  value as a confidence interval doing statistical model checking, in particular the rate events  and we know that a good algorithm is we give it a time limit, it's going to give us back  a confidence interval which is very narrow, the width of this confidence interval is going  to be very small.  So how do we compare different algorithms and how do we put our importance function here  into the picture?  Well essentially we are going to estimate the unreliability of this system using standard  multi-carrel on one side and on the other side we are going to use different algorithms  of rate event simulation which use as a backend the importance function that we compute from  this structure automatically using the method that I just mentioned.  Now to see how this increases in efficiency as the system becomes more resilient we parameterize  all our models for the fault tolerant pattern processor we increase the number of spares  here, the more spares that we have here the more resilient the system is and the lower  the probability of failure given a fixed time horizon.  So for these three variants of the FTPP we tested all our algorithms and checked the width  of the confidence interval built for a given time limit in runtime of execution.  So the algorithm that could achieve the narrowest interval in the most resilient case is the  most efficient algorithm.  So we did this for different systems each with its own parameterization we studied transient  and also steady state properties of the systems, all the details are in the paper.  I just want to focus on the results a little bit to show you that well as expected the  more resilient any of these systems became the more the bridge between the standard Monte  Carlo and the rate event simulators that use our importance function as a backend right?  So that's essentially what we wanted to observe that our importance function is an efficient  automatic way to implement rate event simulation.  These are the results for the transient analysis so for unreliability we have similar outcomes  for the steady state analysis of unavailability.  Then as the system become more resilient essentially the rate event simulation methods  that use our importance function can build for the same time limit of simulation a narrower  confidence interval than standard Monte Carlo.  I also wanted to perform a live demo with the tool that we use for this tool chain but  essentially we are already out of time already so I just mentioned you to this tool demo  paper which includes an artifact which you can try on your own and with which you can  reproduce many of the experiments that I showed here.  So to conclude we showed how to implement Yoast as a Mantis for DFTs, I mean we showed  that we have a tool that implements this and we did show how to build an importance function  inductively from the structure of a dynamic for tree that can be repairable to perform  rate event simulation on it in a way that is as automatic as standard Monte Carlo but  is much more efficient to compute metrics when we are talking of rate events and we have  a tool chain that can implement all of this.  As future work we wanted to for instance try other importance functions based on the FD  structure we actually did this already this was in an MMB paper with Marielle and me and  other things we want to do in the near future specifically this one for instance is to put  information on the time limit that we have for instance for transient analysis of unreliability  into the importance function instead of just counting the number of failed things in general.  So this is a snapshot of the people that contributed to this and that was our contribution to Tecas  2020.
604907f51a80aac83ca25d9b_0_563.png 604907f51a80aac83ca25d9b_564_1487.png 604907f51a80aac83ca25d9b_1488_4427.png 604907f51a80aac83ca25d9b_4428_5651.png 604907f51a80aac83ca25d9b_5652_6335.png 604907f51a80aac83ca25d9b_6336_6383.png 604907f51a80aac83ca25d9b_6384_12443.png 604907f51a80aac83ca25d9b_12444_12527.png 604907f51a80aac83ca25d9b_12528_17111.png 604907f51a80aac83ca25d9b_17112_17207.png 604907f51a80aac83ca25d9b_17208_17735.png 604907f51a80aac83ca25d9b_17736_18095.png 604907f51a80aac83ca25d9b_18096_21719.png 604907f51a80aac83ca25d9b_21720_22187.png 604907f51a80aac83ca25d9b_22188_22247.png 604907f51a80aac83ca25d9b_22248_22811.png 604907f51a80aac83ca25d9b_22812_23519.png 604907f51a80aac83ca25d9b_23520_23615.png 604907f51a80aac83ca25d9b_23616_23673.png