{'fraction_non_alphanumeric': 0.030410282680575607, 'fraction_numerical': 0.004983001909374563, 'mean_word_length': 4.503331624807791, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Combination of component fault trees and Markov chains to analyze complex, software-controlled systems

Fault Tree analysis is a widely used failure analysis methodology to assess a system in terms of safety or reliability in many industrial application domains. However, with Fault Tree methodology there is no possibility to express a temporal sequence of events or state-dependent behavior of software-controlled systems. In contrast to this, Markov Chains are a state-based analysis technique based on a stochastic model. But the use of Markov Chains for failure analysis of complex safety-critical systems is limited due to exponential explosion of the size of the model. In this paper, we present a concept to integrate Markov Chains in Component Fault Tree models. Based on a component concept for Markov Chains, which enables the association of Markov Chains to system development elements such as components, complex or software-controlled systems can be analyzed w.r.t. safety or reliability in a modular and compositional way. We illustrate this approach using a case study from the automotive domain.


I. INTRODUCTION
The importance of safety-critical systems in many application domains of embedded systems, such as aerospace, railway, health care, automotive and industrial automation is continuously growing. Thus, along with the growing system complexity, also the need for safety assessment as well as its effort is increasing drastically in order to guarantee the high quality demands in these application domains. The goal of the safety assessment process is to identify all failures that cause hazardous situations and to demonstrate that their probabilities are sufficiently low. In the application domains of safety-critical systems the safety assurance process is defined by the means of safety standards (e.g. the IEC 61508 standard [1]). Fault Tree Analysis (FTA) [2] is a common top-down deductive approach to identify failure modes, their causes, and effects with impact on the system safety. With Component Fault Trees (CFTs) [3] there is a model-and componentbased methodology for FTA, which supports a modular and compositional safety analysis strategy.
However, when using Fault Tree methodology there is no possibility to express a temporal sequence of events or statedependent behavior. But this is especially needed for modern, complex systems that are increasingly controlled by software components. In contrast to this, Markov Chains (MCs) [4], [5] are a state-based analysis technique and enable safety and reliability analysis of systems with temporal or state-based behavior (e.g. fault tolerance capabilities). However, the use of MCs to analyze systems in industrial practice is limited due to exponential explosion of the size of the model when modeling large-scale systems. In order to overcome these limitations and to combine the advantages of CFTs and MCs, an integrated approach using a component concept for MCs is required.
In this work, we present a concept to integrate Markov Chains into the Component Fault Tree methodology. This concept is based on a generalized component concept for MCs.
These so-called Component Markov Chain (CMC) elements can be associated to system development elements such as components and reused along with the respective development artifact. Thus, providing a modular and compositional safety analysis strategy for MCs which is similar to CFTs. Thereby, so-called Generalized Hybrid Component Fault Trees (GHCFTs) consisting of a combination of CFT and CMC elements can be created to analyze complex, software-controlled systems w.r.t. safety and reliability.
The remainder of this paper is organized as follows: In Sec. II we summarize related work. Afterwards, the concept of MCs and CFTs is outlined in Sec. III. Sec. IV describes the generalized component concept for Markov Chains. Based on this concept, we introduce Generalized Hybrid Component Fault Trees in Sec. V and show how to analyze the combination of CFT and CMC elements qualitatively and quantitatively. We illustrate our approach in Sec. VI using an exemplary case study from the automotive domains. The paper is concluded in Sec. VII.

II. RELATED WORK
Existing concepts for modular Markov Chains [6]- [8] solely focus on the modular design and composition of Markov models. The combination of Markov Chains and Fault Trees is not considered in these approaches.
Other approaches to represent temporal sequences of events or in Fault Trees, such as [9]- [12] focus on the integration of Markov Chains in Fault Trees as a substitute of the Fault Tree's Basic Events. Thereby, a Basic Event is represented by a MC. However, such an approach is limited to MCs with exactly one error state. Moreover, according to these existing solutions a MC can only be associated to specific components (e.g. sensor components), which do not depend on other components.
Dynamic Fault Trees [13] or AltaRica [14] use their own and specific syntax to describe a safety-critical system, which is more powerful in terms of expressiveness than classic Fault Trees. However, such approaches are rarely used in industry, since safety experts must first be trained on the new methodology and migration strategies for existing models are missing yet.
State/Event Fault Trees (SEFTs) [15] combine the concept of fault trees with a graphical representation of state/event semantics that is similar to state charts. SEFTs are partitioned into components using the component concept of CFTs. Each component is in exactly one state at an instant of time. State transitions are triggered by internal or external events. Although, SEFTs extend fault tree analysis with capabilities to model temporal or state-based behavior, for quantitative analysis the SEFTs need to be transformed into Deterministic and Stochastic Petri Nets. This results in a state explosion problem. Besides from the missing support of tools for modeling SEFTs there is no evidence that this approach can be applied to analyze complex systems in industrial practice.
In this work, we present a general component concept for Markov Chains which can be combined with Component Fault Tree methodology and which is not restricted by the above indicated limitations. It can be integrated into the CFT methodology seamlessly and analyzed qualitatively or quantitatively using well-established algorithms.

A. Markov Chains
Markov Chains (MC) [4], [5] are a top-down analysis technique. A MC represents various system states and the relationships among them. MCs are often described by a sequence of directed graphs, where the edges of the graph (the so-called transitions) are labeled by the rates for going from one state to another state (the so-called transition rate). The transition rate from one state to another is either a failure rate λ or a repair rate µ. Each state of a MC is mutually exclusive because at any given time, the system can be in only one of the states. In this paper, we restrict our approach to the use of Continuous Time Markov Chain (CTMC) with constant transition rates (failure rate or repair rate). Please note, that in the following we refer to CTMC as Markov Chain (MC).
Especially, in state-based or fault tolerant (software) systems the safety assessment process and evaluation of such system may be more appropriately achieved by the application of the Markov technique than using Fault Trees.

B. Component Fault Trees
A Component Fault Tree (CFT) is a Boolean model associated to system development elements such as components [3]. It has the same expressive power as classic fault trees that can for example be found in [2]. As classic fault trees, also CFTs are used to model failure behavior of safety-critical systems. This failure behavior is used to document that a system is safe and it can also be used to identify drawbacks of the design of a system.
In CFTs, a separate CFT element is related to a component. Failures that are visible at the outport of a component are models using Output Failure Modes (OFMs) which are related to the specific outport. To model how specific failures propagate from an inport of a component to the outport, Input Failure Modes (IFMs) are used. The internal failure behavior that also influences the output failure modes is modeled using the Boolean gates such as OR and AND as well as Basic Events.
In addition, it is possible to have more than one top event within a CFT element, such as an accident when a primary failure coincides with the failure of a countermeasure, but only a system unavailability when the same primary failure occurs while the countermeasure is working. Thus, the tree structure is extended towards a Directed Acyclic Graph (DAG) structure in the CFT methodology. This avoids the artificial splitting of common cause errors into multiple repeated events. Instead, it is possible for more than one path to start from the same basic event or sub-graph.  [16] A small example of a CFT was presented in [16] (see Fig. 1). The example shows an exemplary controller system Ctrl, including two redundant CPUs (i.e. two instances of the same component type) and one common power supply Sply (which would be a repeated event in traditional fault tree). The controller is unavailable if both CPUs are in the state "'failed"'. The inner fault tree of the component type CPU is shown on a separate screen; as the CPUs are of identical type, they only have to be modeled once and are then instantiated twice. The failure of a CPU can be caused by some inner basic event "'E1"' (the repetition of the ID "'E1"' in several components is not a problem, as each component constitutes its own name space). The failure of the CPU can also be caused by an external failure cause which is connected via an input port. As both causes result in a CPU failure, they are joined via a 2-input OR gate. The power supply is modeled as a separate component. Let us assume that the power supply is in its failed state if two separate basic failures are present (for example having two redundant batteries). Hence, instead of a single large fault tree, the CFT model consists of small, reusable and easy-to-review components.
Using this methodology of components also within fault tree models, benefits during the development can be observed in industrial practice, for example an increased maintainability of the safety analysis model [17].

IV. A GENERAL COMPONENT CONCEPT FOR MARKOV CHAINS
In this section, we present our general component concept for Continuous Time Markov Chains. In the following, this method is described formally and illustrated using an example.
First, we assume that the System S consists of a set of components C = {c 1 , ..., c n }. Each component c ∈ C includes a set of inports IN (c) = {in 1 , ..., in p } and a set of outports OU T (c) = {out 1 , ..., out q }. The information flow between the outport of a component c i ∈ C and the inport of another component .., s n }, with an initial state s init ∈ S to start from and a set of error states S error ⊂ S. The relation between the states of the MC is defined by a set of transitions: Each transition t(j, k) ∈ T from state j ∈ S to state k ∈ S is defined by a rate τ j,k , which either represents a constant failure rate λ j,k or a constant repair rate µ j,k : Hence, a Markov Chain is defined by the tuple An example for a MC is illustrated in Fig. 2.
The dependency of one transition t ∈ T is defined as When a transition t(a, b) ∈ T from state a ∈ S to b ∈ S is interconnected with one or more input failure modes, the rate of the transition t(a, b) changes to Moreover, a CMC may have a set of output failure modes OF M = {of m 1 , ..., of m r } which represent failures propagated to other components with the failure rate τ (of m) of of m ∈ OF M .
The rate τ (of m) is calculated as the rate that a corresponding specific error state s ∈ S error is reached, since the error states of the CMC represent the failures modes. This relation is represented by a set of so-called Output Failure Mode Dependencies: If the error state s is reached, the output failure mode of m is triggered. Thus, τ (of m) is the calculated rate τ (s) for arriving in error state s. An example for a CMC is illustrated in Fig. 3. This When the CMC is analyzed, the values for τ (c) and τ (d) are calculated.
A CMC cmc can be associated to a system component c ∈ C in the same way a CFT element is associated with a component [18]:CM C(c) = cmc.
Based on the construction of the CMC it is possible to combine CMC and CFT elements and analyze it qualitatively and quantitatively.

V. GENERALIZED HYBRID COMPONENT FAULT TREES
A first concept to combine CFTs and MCs was already introduced in [9]. However, the use of MCs in this approach was limited to the substitution of basic events with one failure state. Hence, MCs can only be used to model the failure behavior of a sensor. With the generalized component concept for MCs as presented in Sec. IV, GHCFTs can be built from any combination of CFT and CMC elements. The only limitation in building a GHCFT is that common cause failures (repeated events within Fault Trees) can only be input to one CMC, if this captures the whole influence of this repeated event on the top event of the GHCFT.
The GHCF T (S) of a system S is defined a follows: Each component c ∈ C has a failure logic model f lm, which is either a CFT element cf t c ∈ CF T or a CMC element cmc c ∈ CM C representing the component's failure behavior: This example is defined by: With GHCFTs there is a modular and hierarchical approach to describe the failure behavior of a system. The concept of GHCFT is more powerful in terms of expressiveness than classical Fault Tree or CFT methodology, because it is possible to express dynamic system behavior. Since a GHCFT can be composed of CFT and CMC elements, the failure behavior of complex, large-scale systems can be modeled using a divideand-conquer strategy. Hence, state explosion is avoided, since not the complete system has to be modeled using a MC, but only the part with relevant dynamic or state-dependent behavior (e.g. fault-tolerant components). Moreover, CMC elements can be composed automatically in the same way as CFT elements can be composed (cf. [19]).
Thus, a GHCFT has a similar power w.r.t. expressiveness as AltaRica 3.0 [14] or State/Event Fault Trees (SEFTs) [15] regarding the attributes identified in [20] (see table I). The GHCFT methodology enables the modeling of the failure behavior of a system in dynamic, event-based way by using states & transition in CMC elements and it allows the user to specify and compose hierarchical systems by using the principles of the CFT methodology. Moreover, a GHCFT can be analyzed with the well-known algorithms for qualitative and quantitative FTA [21]. Thereby, our approach avoids a potential explosion of state-spaces and thus performance problems during analysis, which is according to [22] the main drawback of the AltaRica as well as the SEFT methodology.

A. Qualitative Analysis
For qualitative analysis the CMC is transformed into a CFT element. This transformation is performed in two steps: 1) For each transition between two states a basic event is created. If the transition has an input failure mode dependency then an OR gate is created and all IFMs the transition is depending on as well as the basic event of the transition are connected to this OR gate. 2) For each OFM of the CMC and for each path leading from the initial state of the CMC to an error state connected to an OFM, the Basic Events or OR gates with connected IFMs 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 OFM. For the exemplary GHCFT as depicted in Fig. 4, the CMC cmc 2 for the qualitative analysis is transformed into a CFT as presented in Fig. 5.

B. Quantitative Analysis
The failure rate τ (of m) is calculated in the Markov Chain-Analysis: A general analysis approach is to use an implicit numerical integration scheme with step-size control for the Fig. 5. Exemplary CMC transformed into a CFT element for qualitative analysis stiff system of ordinary differential equations representing the CTMC as described e.g. in [23]. This also allows nonconstant transition rates at inports resulting from redundancy in upstream CFTs or CMCs. Thus, the failure rate of each OFM of a CMC can be calculated and the CMC can be combined with CFTs.
Since the failure rate of each OFM of a CMC can be calculated as described above, CMC can be combined with CFT elements and integrated into a GHCFT. Please note, that common cause failures represented as repeated basic events within the GHCFT can be input to one CMC, if this captures the whole influence of this repeated event on the top event of the GHCFT. Otherwise the GHCFT cannot be analyzed quantitatively.
For the exemplary GHCFT as depicted in Fig. 4, assuming an infinite mission time, we need no numerical integration and can, however, explicitly calculate τ (c) the stationary solution in the following way. Thereby, we assume the following failure rates for the basic events in Fig. 4: Please note, that with this approach repeated events can only be handled as input of one CMC, if this input captures the whole influence of this repeated event on the top event of the GHCFT.

VI. CASE STUDY
In this section, a case study from the automotive domain is presented to demonstrate our approach. The presented system is a radio controlled car. Please note, that this system is a simplification of a real system to be used for demonstration purposes. Fig. 6 shows the system architecture of an emergency braking functionality in the radio controlled car in form of a SysML Internal Block Diagram (IBD). The architecture consists of the components Ultrasonic Sensor 1 (US 1), Ultrasonic Sensor 2 (US 2), Emergency Braking Controller (EBC) (implemented in software) and Engine (E), which exchange data via the modeled ports and interconnections. Both sensors are a source Fig. 6. System architecture as a SysML Internal Block Diagram for random faults leading to the hazardous situations on system level (cf. Fig. 7 & Fig. 9). The random failures are represented by the basic events false-negative with a failure rate of 50000 FIT (Failures in Time, in 10 9 h) and false-positive with a failure rate of 500 FIT in the CFT element of the sensor component. The omission failure mode (omission obstacle detection / no emergency braking) refers to the situation where accidentally no braking command is generated by the EBC component. The commission failure mode (commission obstacle detection / sporadic braking) refers to the situation where accidentally a braking command is generated. The EBC component sends a brake command to the electric engine E, if one of the sensors detects an obstacle in front of the vehicle. The controller is fault-tolerant in the sense, that the system can still determine an obstacle if only US 1 is defect. US 2 is a cold spare of US 1. The failure rate of US 2 in stand-by mode prior to its activation after the failure of US 1, is neglected. Therefore, we look at the failure of US 2 after the failure of US 1 leading to the overall failure of the emergency braking function. Since such temporal sequences of events behavior cannot be expressed using a CFT element, it is represented using CMC element as described in Sec. IV (cf. Fig. 8). Fig. 9 shows the GHCFT representing the failure behavior of the emergency braking function in our case study. It consists of a CMC element for the EBC and CFT elements for the Ultrasonic Sensors as well as the Engine component. The GHCFT can be analyzed qualitatively and quantitatively as outlined in Sec. V.
The results of the qualitative and quantitative analysis of the GHCFT presented in Fig. 9 are as follows: In this paper, we present a concept to integrate Markov Chains in Component Fault Tree models. Based on a component concept for Markov Chains which allows the modular specification of a Markov Chain and its association to a system development element such as a component similar to Component Fault Tree (CFT) methodology. Thus, complex or software-controlled systems can be analyzed w.r.t. safety or reliability in a modular and compositional way. The combination of CFT and CMC models results in a so-called Generalized Hybrid Component Fault Tree (GHCFT), which can then be analyzed qualitatively (Minimal Cut Set analysis) or quantitatively using well-established algorithms. This combination of CMC and CFT models allows less complex quantitative analysis that takes the temporal sequence of failure events or state-dependent behavior into account compared to an analysis using a Markov Chain for the whole system. The only limitation of our approach is that in case a common cause failure enters a CMC, its effect at the CMC inport must already represent the complete effect on the top event of the GHCFT.
Future work will be a more detailed evaluation using a largescale industrial case study which shows the benefits of our approach in analyzing safety or reliability. Moreover, we will investigate approaches how to handle repeated events within GHCFTs.
ACKNOWLEDGMENT Parts of the work leading to this paper was funded by the Framework Programs for Research and Innovation Horizon 2020 under grant agreement No. 732242 (DEIS).