Markov chains and component fault trees for modelling technical systems

Abstract

A method for modelling technical systems having a plurality of technical components, including the step of assigning a component Markov chain to each component having a Markov chain for representing various states of the respective component, at least one input one failure mode for externally triggering a transition from one state of the Markov chain into another state of the Markov chain, and at least one output failure mode to each Markov chain for propagating failures to other components, is provided.

Claims

1. A storage module for storing a data structure representing a component Markov chain, comprising: a Markov chain for representing various states of a technical component; at least one input failure mode representing incoming failures for outside a scope of the technical component for externally triggering a transition from one state of the Markov chain into another state of the Markov chain; and at least one output failure mode for propagating failures to other technical components; wherein the component Markov chain is transformed into a component fault tree element for qualitative analysis, wherein probabilities to reach each error state, which triggers the output failure mode, by a sequence of states from the initial state of the Markov chain are multiplied, wherein if a transition between two states has a fixed probability representing a failure rate, then a basic event is created, wherein if a transition between two states does not have a fixed probability then a OR-gate is created and all input failure modes, on which the transition depends, are connected to the OR-gate, wherein for each output failure mode of the component Markov chain and for all different paths leading from the initial state of the component Markov chain to error states connected to an output failure mode, the basic events or OR-gates with connected input failure modes within the component fault tree element, which represent the transition, are connected by an AND-gate, and wherein if more than one failure mode path exists in the component Markov Chain, all AND-gates within the component fault tree of the different failure mode paths are connected by a second OR-gate.

2. The storage module according to claim 1, wherein the Markov chain comprises an initial state and a set of error states of the component.

3. The storage module according to claim 2, wherein each transition from one state to another state is defined by a probability, which either represents a failure rate or a repair rate of the component.

4. The storage module according to claim 1, wherein the component comprises an inport in logical connection with one or several input failure modes of the component Markov chain.

5. The storage module according to claim 1, wherein the component comprises an outport in logical connection with one or several output failure modes of the component Markov chain.

6. The storage module according to claim 1, wherein an outport of one component is logically connected with an inport of another component.

7. A computer program product, comprising a non-transitory computer readable memory storing software code portions for executing a method for modelling technical systems having a plurality of technical components when the computer program is run on a processor, the method comprising: assigning a component Markov chain to each technical component of the plurality of technical components having: a Markov chain for representing various states of the respective component; at least one input failure mode representing incoming failures for outside a scope of the respective technical component for externally triggering a transition from one state of the Markov chain into another state of the Markov chain; and at least one output failure mode to each Markov chain for propagating failures to other components transforming the component Markov chain into a component fault tree element for qualitative analysis, multiplying probabilities to reach each error state, which triggers the output failure mode, by a sequence of states from the initial state of the Markov chain, creating a basic event if a transition between two states has a fixed probability representing a failure rate, creating an OR-gate if a transition between two states does not have a fixed probability and connecting all input failure modes, on which the transition depends, to the OR-gate, connecting, using an AND-gate, for each output failure mode of the component Markov chain and for all different paths leading from the initial state of the component Markov chain to error states connected to an output failure mode, the basic events or OR-gates with connected input failure modes within the component fault tree element, which represent the transition, and connecting, using a second OR-gate, if more than one failure mode path exists in the component Markov chain, all AND-gates within the component fault tree of the different failure mode paths.

8. The computer program product according to claim 7, wherein the Markov chain comprises an initial state and a set of error states of the component.

9. The computer program product according to claim 8, wherein each transition from one state to another state is defined by a probability, which either represents a failure rate or a repair rate of the component.

10. The computer program product according to claim 7, wherein the component comprises an inport in logical connection with one or several input failure modes of the component Markov chain.

11. The computer program product according to claim 7, wherein the component comprises an outport in logical connection with one or several output failure modes of the component Markov chain.

12. The computer program product according to claim 7, wherein an outport of one component is logically connected with an inport of another component.

13. A computer-implemented method for modelling and analyzing a complex safety-critical technical system having a plurality of technical components, wherein the plurality of technical components include a hardware module and a software module, comprising: providing a processor; assigning, by the processor, a component Markov chain to each technical component of the plurality of technical components having: a Markov chain for representing various states of the respective component; at least one input failure mode representing incoming failures for outside a scope of the respective technical component for externally triggering a transition from one state of the Markov chain into another state of the Markov chain; and at least one output failure mode to each Markov chain for propagating failures to other components; transforming, by the processor, the component Markov chain into a component fault tree element for qualitative analysis, multiplying, by the processor, probabilities to reach each error state, which triggers the output failure mode, by a sequence of states from the initial state of the Markov chain, creating, by the processor, a basic event, if a transition between two states has a fixed probability representing a failure rate, creating, by the processor, a first OR-gate, if a transition between two states does not have a fixed probability and connecting, by the processor, all input failure modes, on which the transition depends, to the first OR-gate, connecting, by the processor, using an AND-gate, for each output failure mode of the component Markov chain and for all different paths leading from the initial state of the component Markov chain to error states connected to an output failure mode, the basic events or OR-gates with connected input failure modes within the component fault tree element, which represent the transition, and connecting, by the processor, using a second OR-gate, if more than one failure mode path exists in the component Markov chain, all AND-gates within the component fault tree of the different failure mode paths; and performing, by the processor, an analysis of the complex safety-critical technical system using the component fault tree element transformed from the component Markov chain.

14. The method according to claim 13, wherein the Markov chain comprises an initial state and a set of error states of the component.

15. The method according to claim 14, wherein each transition from one state to another state is defined by a probability, which either represents a failure rate or a repair rate of the component.

16. The method according to claim 13, wherein the component comprises an inport in logical connection with one or several input failure modes of the component Markov chain.

17. The method according to claim 13, wherein the component comprises an outport in logical connection with one or several output failure modes of the component Markov chain.

18. The method according to claim 13, wherein an outport of one component is logically connected with an inport of another component.

Description

BRIEF DESCRIPTION

(1) Some of the embodiments will be described in detail, with reference to the following figures, wherein like designations denote like members, wherein:

(2) FIG. 1 shows a classic fault tree and component fault tree;

(3) FIG. 2 shows an exemplary Markov chain;

(4) FIG. 3 shows an exemplary component Markov chain;

(5) FIG. 4 shows an exemplary hybrid fault tree; and

(6) FIG. 5 shows an exemplary component Markov chain transformed into a CFT element for qualitative analysis.

DETAILED DESCRIPTION

(7) FIG. 1 shows on the left side a classic fault tree 100 and on the right side a component fault tree 200. In both trees 100 and 200 the top events or output events TE1 and TE2 are modeled. The classic fault tree 100 and the component fault tree 200 comprise Boolean formulas represented by OR-Gates and AND-gates. Basic events A and In are processed into top events TE1 and TE2 by the Boolean formulas.

(8) The model of the component fault tree 200 allows, additionally to the Boolean formulas that are also modeled within the classic fault tree 100, to associate the specific top events TE1 and TE2 to the corresponding output ports O1 of a component 101 where these failures can appear. Input to the component 101 is supplied via input port I1.

(9) Top event TE1 for example appears at port O1. Using this methodology of components also within fault tree models, benefits during the development can be observed, for example an increased maintainability of the safety analysis model.

(10) Markov chains (MC) are a top-down analysis technique. A Markov chain represents various system states and the relationships among them. Markov chains are often described by a sequence of directed graphs, in which the edges of the graph, i.e. the so-called transitions, are labeled with probabilities of going from one state at time n to another state at time n+1. In this way a so-called transition rate can be defined. The transition rate from one state to another is either a function of the failure or repair rate. Each state of a Markov chain is mutually exclusive because at any given time, the system can be in only one of the states. Especially, in fault tolerant systems the safety assessment process and evaluation of such system may be more appropriately achieved by the application of the Markov technique then using fault trees.

(11) A component fault tree (CFT) 200 is a Boolean model associated to system development elements such as components 101. It has the same expressive power as classic fault trees 100. Like classic fault trees 100, also component fault trees 200 are used to model failure behavior of safety-critical systems. This failure behavior is used to document that a system is safe and can also be used to identify drawbacks of the design of a system. In component fault trees 200, a separate component fault tree element is related to a component 101. Failures that are visible at the outport of the component 101 are modeled using output failure modes which are related to the specific outport O1. To model how specific failures propagate from an inport I1 of a component 101 to the outport O1, input failure modes In are used. The internal failure behavior that also influences the output failure modes TE1 and TE2 is modeled using the Boolean gates such as “OR” and “AND” as well as basic events. Every component fault tree 200 can be transformed to a classic fault tree 100 by removing the input and output failure modes elements.

(12) This can be combined into a general component concept for Markov chains. In the following, this method is described formally and illustrated using an example.

(13) First, we assume that the System S consists of a set of components C={c.sub.l, . . . , c.sub.n}. Each component c∈C includes a set of inports IN(c)={in.sub.l, . . . , in.sub.p} and a set of outports OUT(c)={out.sub.l, . . . , out.sub.q}.

(14) The information flow between the outport O1 of a component c.sub.i∈C and the inport of another component c.sub.j∈C (with c.sub.i≠c.sub.j) is represented by a set of connections
CON={(out.sub.x,in.sub.y)|out.sub.x∈OUT(c.sub.i),in.sub.y∈IN(c.sub.j)}.

(15) A Markov chain is a directed graph which consists of a set of states S={S.sub.i, . . . , S.sub.n} with an initial state s.sub.init∈S to start from and a set of error states S.sub.error⊂S. The relation between the states of the Markov chain is defined by a set of transitions:
T={(S.sub.x,S.sub.y)|S.sub.x,S.sub.y∈S}.

(16) Each transition t.sub.i∈T from state s.sub.j∈S to state s.sub.k∈S is defined by a probability P(j,k), which either represents a failure rate λ.sub.j,k or a repair rate μ.sub.j,k:

(17) $P (j, k) = p_{j, k} = {\begin{matrix} λ_{j, k} = [0, 1] \\ μ_{j, k} = [0, 1] \end{matrix}$

(18) Hence, a Markov chain is defined by the tuple
MC=(S,S.sub.error,s.sub.init,T)

(19) FIG. 2 shows an example of a Markov chain 300 having an init state 1, intermediate state 2 and an error state 3. This exemplary Markov chain 300 is defined by:
S={1,2,3}
S.sub.init=1
S.sub.error={3}
T={(1,2),(2,3),(3,1)}
P(1,2)=p.sub.1,2=λ.sub.1,2=0.3
P(2,3)=p.sub.2,3=λ.sub.2,3=0.6
P(3,1)=p.sub.3,1=μ.sub.3,1=0.12

(20) In order to specify a component Markov chain (CMC) cmc.sub.i which can be associated to any development artifact, like technical components 101 of the system c.sub.i∈C, the definition of the Markov chain 300 is extended.

(21) In addition the component Markov chain element cmc.sub.i may have a set of input failure modes IFM={ifm.sub.l, . . . , ifm.sub.q} which represent incoming failures for outside of the scope of the component 101 with the failure rate P(ifm.sub.i). Each input failure mode ifm.sub.j∈IFM can trigger one or several transitions T.sub.ifmj.Math.T of the component Markov chain. This relation is represented by a set of input failure mode dependencies:
DI={(ifm.sub.x,t.sub.y|ifm.sub.x∈IFM,t.sub.y∈T}

(22) Each input failure mode dependency di.sub.j,k∈DI may define a factor f(di.sub.j,k).fwdarw. custom character which scales the failure rate P(ifm.sub.j) of the input failure mode ifm.sub.j∈IFM. The interconnection of a transition t.sub.k∈T with one or more input failure modes changes the probability of the transition P(t.sub.k) from state s.sub.a∈S to state s.sub.b∈S:

(23) $P (a, b) = p_{a, b} + {.Math.}_{l = 1}^{q} f (d i_{l, k}) * P (i f m_{l})$

(24) Moreover, a component Markov chain may have a set of output failure modes OFM={ofm.sub.1, . . . , ofm.sub.r} which represent failure propagated to other components with the failure rate P(ofm.sub.i). Each output failure mode ofm.sub.j∈OFM is triggered when a specific error state s.sub.k∈S.sub.error is reached, since the error states of the component Markov chain represent the failures modes. This relation is represented by a set of output failure mode dependencies:
DO={(s.sub.x,ofm.sub.y)|s.sub.x∈S,ofm.sub.y∈OFM}

(25) If the error state s.sub.k is reached, the output failure mode ofm.sub.j is triggered. Thus, P(s.sub.k)=P(ofm.sub.j).

(26) Hence, a component Markov chain is defined by the tuple
CMC=(S,S.sub.error,s.sub.sinit,T,IFM,DI,OFM,DO)

(27) FIG. 3 shows an example for a component Markov chain 400. This exemplary component Markov Chain 400 is defined by:
S={1,2,3,4}
s.sub.init=1
S.sub.error={3,4}
T={(1,2),(2,3),(3,1),(3,4)}
IFM={a,b}
DI={(a,t.sub.1),(b,t.sub.4)}
OFM={c,d}
DO={(3,c),(4,d)}
with
f(a,t.sub.1)=0.0
f(b,t.sub.4)=0.45

(28) Hence, the probabilities for the transition rates of the exemplary component Markov chains 400 are as follows:
P(1,2)=λ.sub.1,2+f(a,t.sub.1)*P(a)=0.3
P(2,3)=λ.sub.2,3=0.6
P(3,1)=μ.sub.3,1=0.12
P(3,4)=λ.sub.3,1+f(b,t.sub.4)*P(b)=0.0+0.45*P(b)

(29) A component Markov chain cmc.sub.i can be associated to a technical system component c.sub.i∈C in the same way a CFT element is associated with a component 101:
C{tilde over (M)}C(c.sub.i)=cmc.sub.i with cmc.sub.i≠∅

(30) Thereby, it is possible that the input and output failure modes of a component Markov chain cmc.sub.i can be mapped onto the input and output ports of the component c.sub.i. Based on the above definition a component Markov chain 400 can be analyzed qualitatively or quantitatively.

(31) FIG. 4 shows an exemplary hybrid Fault Tree (hFT) 500 to illustrate the analysis of the component Markov chain 400 having the components 101-1, 101-2 and 101-3. The following exemplary hybrid fault tree 500 is defined by:
C={c.sub.1,c.sub.2,c.sub.3}
IN(c.sub.1)={ }
IN(c.sub.2)={i1}
IN(c.sub.3)={i2}
OUT(c.sub.1)={o1}
OUT(c.sub.2)={o2}
OUT(c.sub.3)={o3}
CON={(o1,i1),(o2,i2)}
C{tilde over (F)}T(c.sub.1)=cft.sub.1
C{tilde over (M)}C(c.sub.2)=cmc.sub.2
C{tilde over (F)}T(c.sub.3)=cft.sub.3

(32) For qualitative analysis the component Markov chain 400 is transformed into a component fault tree element. This transformation is performed in two steps:

(33) 1. If a transition between two states has a fixed probability, i.e. there is no input failure mode dependency between an input failure mode and the transition, and this probability represents a failure rate λ and a repair rate μ, then a basic event is created. Otherwise, an OR-gate is created and all input failure modes, on which the transition depends, are connected to this gate.
2. For each output failure mode of the component Markov chain 400 and for all different paths leading from the initial state of the component Markov chain 400 to error states connected to an output failure mode, the basic events or OR-gates with connected input failure modes within the CFT element, which represent the transition, are connected by an AND-gate. If more than one path is existing, all AND-gates are connected by an OR-gate, which is then connected to the output failure mode.

(34) FIG. 5 shows an exemplary component Markov chain 400 transformed into a CFT element 600 for qualitative analysis. For the exemplary hybrid Fault Tree 500 as depicted in FIG. 4, the component Markov chain cmc.sub.2 for the qualitative analysis is transformed into a CFT as follows.

(35) In a quantitative analysis the failure probability P(ofm.sub.j) of each output failure mode ofm.sub.j∈OFM of a component Markov chain cmc.sub.i is defined as

(36) $\underset{d o_{k, j} \in D O}{.Math.} P (s_{k}) = \underset{d o_{k, j} \in D O}{.Math.} {.Math.}_{l = 1}^{n} P (s_{k + l - 1,} s_{k + l})$

(37) Thereby, the probabilities to reach the error state, which triggers the output failure mode ofm.sub.j, is calculated by summing up the probabilities of each sequence of states from the initial state of the Markov Chain to this error state. The probability of a sequence of transitions is defined the product of all transition rates P(s.sub.k+l−l,s.sub.k+l).

(38) Since the failure rate of each output failure mode of a component Markov chain 400 can be calculated as described above, the component Markov chain 400 can be combined with CFT elements in any way and integrated into the hybrid fault tree. For the exemplary hybrid fault tree as depicted in FIG. 4 the following failure rates for the basic events are assumed:
P(x)=2.0*10.sup.−7
P(y)=4.0*10.sup.−7
P(z)=1.0*10.sup.−7

(39) Thus, the failure rate of the input failure mode a is P(a)=6.0*10.sup.−7.

(40) Hence, the quantitative analysis of the component Markov chain cmc.sub.2 results in:

(41) $\begin{matrix} P (b) = P (3) = P (1, 2) * P (2, 3) \\ = 0.3 * (0.6 + (0.4 * P (a)) \\ = 0.3 * (0.6 + (0.4 * 6.0 * 1 0^{- 7}) \\ = 0.18 \end{matrix}$

(42) The component concept for Markov chains allows the modular specification of a Markov chain and the association to a system development element such as a technical component.

(43) The technical component can be a software module, like an object in object oriented programming (OOP). The technical component can also be hardware module, like an electronic circuit or an application-specific integrated circuit (ASIC). The technical component can also comprise combinations of hardware and software.

(44) Since the approach enables the composition of component Markov chain, large-scale systems including a plurality of components can be modeled using a divide-and-conquer strategy and Markov chains can be reused along with the associated technical system component.

(45) Thus, the complexity of building Markov models for complex technical systems is reduced. Moreover, component Markov chain models can be combined with Component Fault Tree (CFT) models in any way in order to build a hybrid fault trees which can then be analyzed qualitatively, e.g. by a minimal cut set analysis or quantitatively.

(46) All features discussed or shown with respect to particular embodiments can be provided in various combinations in order to simultaneously realize their advantageous effects.

(47) All method steps can be implemented by corresponding means which are adapted for performing the respective method step. All functions provided by particular means can be a method step of the method.

(48) The scope of protection is given by the claims and not restricted by features discussed in the description or shown in the figures.

(49) Although the present invention has been disclosed in the form of preferred embodiments and variations thereon, it will be understood that numerous additional modifications and variations could be made thereto without departing from the scope of the invention.

(50) For the sake of clarity, it is to be understood that the use of “a” or “an” throughout this application does not exclude a plurality, and “comprising” does not exclude other steps or elements.

Markov chains and component fault trees for modelling technical systems

Assignee

Inventors

Cpc classification

Classification Explorer

G06F30/33

PHYSICS

Classification Explorer

G06N7/01

PHYSICS

Classification Explorer

G06F2111/08

PHYSICS

Classification Explorer

G05B23/0248

PHYSICS

Classification Explorer

G05B23/0254

PHYSICS

Classification Explorer

G06F2111/20

PHYSICS

Classification Explorer

G05B2219/24076

PHYSICS

International classification

Classification Explorer

G05B23/02

PHYSICS

Classification Explorer

G06N7/00

PHYSICS

Abstract

Claims

Description