10 pages paper

Variability-Aware Safety Analysis using Delta Component Fault Diagrams

Christoph Seidl Technische Universität

Dresden Software Technology Group 01062 Dresden, Germany christoph.seidl@tu-

dresden.de

Ina Schaefer Technische Universität

Braunschweig Software Engineering Institute

38106 Braunschweig, Germany

[email protected]

Uwe Aßmann Technische Universität

Dresden Software Technology Group 01062 Dresden, Germany

uwe.assmann@tu- dresden.de

ABSTRACT Component Fault Diagrams (CFD) allow the specification of fault propagation paths, which is employed for the design of safety-critical systems as well as their certification. Even though families of safety-critical systems exist with many similar, yet not equal, variants there is no dedicated variabil- ity mechanism for CFDs to reuse commonalities of all family members and to alter only variable parts. In this paper, we present a variability representation approach for CFDs based on delta modeling that allows to transform an initial CFD within a closed or open variant space. Furthermore, we provide delta-aware analysis techniques for CFDs in order to analyse multiple variants efficiently. We show the feasibil- ity of our approach by means of an example scenario based on the personal home robot TurtleBot using a prototypical implementation of our concepts.

Categories and Subject Descriptors D.2.2 [Software Engineering]: Design Tools and Tech- niques—Modules and interfaces; D.2.4 [Software Engineer- ing]: Software/Program Verification—Formal methods

General Terms Algorithms, Measurement

Keywords Delta Modeling, Component Fault Diagrams, Software Fault Trees, Safety, Variability, Minimum Cut Set

1. INTRODUCTION Safety-critical systems contain software controlling hard-

ware that is capable of causing harm to humans or to the environment through accidents, e.g., in domains such as the defense sector, automated processing or personal robotics.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. SPLC 2013 workshops August 26 - 30 2013, Tokyo, Japan Copyright 2013 ACM 978-1-4503-2325-3/13/08 ...$15.00.

In order to assure safety, safety-critical systems are certified by independent certification authorities, which require ex- tensive documentation of the system’s safety aspects in the form of safety artifacts such as Component Fault Diagrams (CFDs) [9] (see Section 2).

Many similar, yet not equal, software systems are built that address similar tasks but adhere to specific requirements of individual customers, e.g., to support different hardware platforms or to provide slightly different functionality. This effectively creates a family of closely related software ap- plications. Instead of creating and maintaining individual applications, these families may be managed in a structured way, e.g., by using software product line (SPL) engineering [13]. In an SPL, a family of applications is perceived as consisting of a common core functionality and various well- defined variable assets that may be combined with this core. SPLs are proven to be beneficial due to shorter times to market and increased reuse of well-established pieces of soft- ware [13]. Other approaches, such as software ecosystems [4, 17] (SECOs) support an open variant space where not all possible members of the family are known in advance.

Safety-critical systems can benefit greatly from SPL and SECO engineering. However, certification authorities do not perform modular certification of application families. Preparing certification documents for each product individu- ally is infeasible or even impossible due to the large number of possible variants. Yet, the process of certification may be aided by using variability modeling techniques for the artifacts documenting safety in order to capitalize on the similarities inherent to these documents due to the close relationship of the underlying systems. In this paper, we present an approach for variability-aware CFDs, which are one essential type of documentation artifact for safety. Fur- thermore, we present variability-aware analysis techniques to assess and compare multiple CFDs of one family efficiently. The presented analysis techniques can be classified as incre- mental product-based approaches following the classification approach of von Rhein et al. [20]. Our contribution is twofold: it allows the reuse of the modeling of fault propagation paths in CFDs as well as the reuse of partial results from analyses on these CFDs.

This paper is structured as follows: Section 2 elaborates on the notation for CFDs. Section 3 introduces our approach of extending CFDs with a variability representation based on delta modeling. Section 4 explains our extension of common analyses on CFDs to make them delta-aware for efficient pro-

2

cessing of entire families of related CFD variants. Section 5 demonstrates the feasibility of our approach by means of an example scenario for the personal home robot TurtleBot. Section 6 elaborates on work from areas related to that of this paper and Section 7 closes with a conclusion.

2. COMPONENT FAULT DIAGRAMS Component Fault Diagrams (CFDs) allow describing fault

propagation behavior of an application based on reusable components in order to devise, build and certify safety-critical systems. Kaiser et al. [9] proposed the original notation underlying CFDs which they call Component Fault Trees (CFTs). However, as the fault propagation paths may span a directed acyclic graph, we use the name Component Fault Diagrams (CFDs) in order to avoid confusion.

Collision

Braking System (BS)

BrakingFails

Moving LowFrictionSurface

Main Component (MC)

Collision Detector (CD)

Collision AvoidableCollision

Obstacle Moving

AND (G1)

ObstacleInWay (OIW) RobotIsMoving (RIM) LowFrictionSurface (LFS)

Figure 1: Example CFD describing possible causes for colli- sions of a mobile personal robot.

A CFD consists of four basic types of elements: basic events, intermediate events, gates and components. Basic events are the atomic building blocks describing events that occur with a specific probability during operation of the system and cannot be refined further. Intermediate events represent complex events aggregated of multiple more fine- grained events. CFDs generally use the term event rather than fault as not every occurrence of an event necessarily means an abnormal condition or defect of a system [10] even though it might lead to one. Gates represent logical expres- sions of other events by means of a gate type that is one of the Boolean operators AND/OR/NOT. Finally, components represent modules that have complex error propagation logic specified by a combination of any of the previously mentioned elements together with fault propagation paths.

The elements of a CFD have an ID that is unique within their diagram and, except for gates, a more descriptive name. Furthermore, elements posses ports, which serve as anchors to connect other elements. In-ports allow connection of elements that represent necessary preconditions and out-ports may connect elements that are activated as a result of the element in question. All ports are characterized by a name that is unique within the context of their defining element but not within the scope of the entire CFD. Thus, the ID of a port consists of the ID of the defining element and the port’s name. The number of possible in-ports and out-ports of an element differs with the element’s concrete type where a basic event has no in-ports (as it is perceived as happening without

preconditions) and only components are allowed to have more than one in-port or out-port. Table 1 gives details on the allowed ports and illustrates the graphical symbols used for each element. A causal relation of individual elements in a CFD may be expressed by use of connections between the ports of diagram elements where activation of the source port causes the target port to be activated as a consequence.

Figure 1 shows the main component (MC) of a CFD for fault propagation regarding collisions of the personal robot TurtleBot, which we use in our example scenario. It con- tains two components (CD, BS) as well as three basic events (OIW, RIM, LFS). The braking system (BS) uses simplistic fault propagation logic where the conjunction of activating both in-ports (Moving, LowFrictionSurface) leads to activation of the out-port (BrakingFails). The basic event Moving is activated when the robot is in motion and LowFriction- Surface appears in situations where the robot is located on slippery ground such as ceramic tiles or wet floor. The detailed fault propagation paths of the collision detector (CD) are omitted at this point, but will be discussed in more detail in Section 5 as part of the example scenario.

Table 1: Overview of the object types in a CFD.

Object Type Symbol In-Ports Out-Ports

E le

m e n ts Basic Event <name> 0 1

Intermediate Event

<name> 1 1

Gate <type> 1 1

Component <name>

1..* 0..*

P o rt

s In-Port

<name>

- -

Out-Port <name>

- -

Connection - -

In contrast to other notations, such as Software Fault Trees [10] (SFTs) or Event Trees [10] (ETs), CFDs mix top- down and bottom-up approaches to specify fault propagation paths in safety-critical systems. The top-down part allows successively refining a coarse-grain fault into its constituents and the bottom-up part allows using fault propagation logic of existing components, which is essential for structured reuse.

However, CFDs do not possess a variability modeling mech- anism allowing the creation of different variants of a CFD. Even though components can be substituted for others with equivalent ports, this notion of variability is very limited as a) the extension points have to be predefined for all possi- ble variants through respective structuring of components and b) modifications on a more fine-grained level than re- placing components (e.g., adding new connections) are not supported.

3. DELTA CFDS In order to manage families of related software artifacts,

e.g., CFDs, a structured approach for variability represen- tation is beneficial. Individual applications of a family are determined by a valid configuration of variable assets that comply to a set of combination rules defined in a variability model (e.g., a feature model). Using a variability modeling

3

mechanism, the relevant realization assets for the selected configuration are assembled to build the application. One integrated mechanism consisting of a variability model and a variability modeling mechanism is delta modeling [15]. It uses transformation rules (called delta operations specified in deltas) to turn a source artifact into a variant of that artifact, e.g., by adding, modifying or replacing elements. This is in contrast to additive variability mechanisms [16] or subtractive variability mechanisms [16], which both use possibly invalid artifacts as source of product derivation: For the prior, a so-called 150% model is used, which contains information for all possible variants and, thus, possibly con- tradicting information for incompatible variable assets. The latter starts with a possibly incomplete fraction of a model and adds parts for variable assets during product derivation. Delta modeling is very beneficial to our goals as it does not depend on a closed variant space where all possible variants of an application are (theoretically) known in advance but supports the creation of unforeseen variants by specifying and applying new deltas. This may be used to evolve the software family [8] and to support an open variant space as found in SECOs.

In the following sections, we extend the general notation of CFDs with a variability representation based on delta modeling allowing fine-grained adaptation of CFDs without predefined variation points.

3.1 CFD Delta Operations In order to create a variability representation based on

delta modeling for CFDs, deltas have to be specified, which can alter a CFD. A CFD delta is comprised of a sequence of delta operations. In total, we provide 20 delta opera- tions in four categories, i.e., adding, removing, replacing and modifying elements as displayed in an overview in Table 2.

Add operations create a new element in a CFD. Depend- ing on the concrete type of element that is being created, the respective attributes have to be specified for the new element. For basic events, intermediate events, gates and components, it is further possible to specify the component which they should be part of as parent component. If no value is given, the root component of the CFD is used as parent component. Equivalently, for ports, the respective owning diagram element has to be specified. For connections, the owning parent component is determined automatically from the parent components of source and target port.

Remove operations delete a specified element from the CFD regardless of whether it is connected to other elements or not. As a consequence, it is possible to create syntactically invalid CFDs due to dangling connections by using improper remove operations. Avoiding these problems is considered to be the responsibility of the creator of a CFD delta.

Replace operations are provided for basic events, interme- diate events, gates and components to replace them with another element. The replacement is not required to be of the same type as the element to be replaced. However, both elements have to be compatible in terms of the ports that actually are connected at the time of substituting the replacement. This means that all in-ports and out-ports of the element to be replaced that have at least one connection attached to them have to have a counterpart with equiva- lent name in the replacement element. When applying the replace operation, ports of the replacement are automati- cally connected in the same way as their counterparts in

the element to be replaced. In addition, the replacement element may possess further ports that do not get connected automatically.

Modify operations are provided for basic events and gates. For basic events, the probability of occurrence may be altered. For gates, the gate type representing one of the Boolean operators AND, OR, NOT of the gate may be changed. We explicitly refrained from altering IDs or names of entities as we feel that this would change the identity of the element in question. If this is desired, the respective elements should either be replaced or removed and added with different ID or name instead.

Table 2: Overview of the available CFD delta operations.

Object Type Add Remove Replace Modify

E le

m e n ts Basic Event x x x probability

Intermediate Event

x x x -

Gate x x x gate type Component x x x -

P o rt

s In-Port x x - - Out-Port x x - - Connection x x - -

CFD deltas are a container for a set of modifications to a CFD. They are characterized by a name for the delta and a sequence of delta operations that are performed when apply- ing the delta. In order to use the available delta operations on concrete elements of a CFD, parameters of the operation referencing diagram elements have to be set, e.g., the optional parent component in add operations or the element to be removed in remove operations. For this purpose, all elements can be referenced by their unique identifier for the CFD. For basic events, intermediate events, gates and components, this is the ID attribute. Ports are referenced by concatenating the ID of their defining element and the port’s name using a colon as separator, e.g., CD:Moving references the right in- port of the collision detector component in Figure 1. Single unlabeled in-ports or out-ports of elements in the graphical examples in this paper have IDs of In and Out, respectively. Finally, connections are uniquely identified by their source and target ports so that they can be referenced by specifying references to both these ports. Using these mechanisms, it is possible to specify a sequence of delta operations with parameters for concrete CFD elements to comprise a CFD delta.

3.2 CFD Variants A CFD delta consists of multiple CFD delta operations

applied to concrete elements of a CFD. In order to foster reuse even within CFD deltas, it is possible to split up deltas into multiple parts and to add dependencies between them. In a system with many variants, it is possible to use the operations specified in a shared delta in multiple depending deltas. For example, a shared delta might create an element in a CFD that has different connections for variants specified in multiple other depending deltas. Through the mechanism of requiring other deltas, it is not necessary to have an explicit core CFD that is the necessary starting point of any transformation. Instead, the first delta in the dependency chain may create the initial contents of the diagram. As even required deltas may require other deltas, the set of all transitively required deltas has to be applied in order to

4

create a valid variant. The specified deltas may be used stand- alone to create variants or in conjunction with a variability model, such as a feature model [15], e.g., by assigning certain sets of deltas to features. A selection of features would then result in a set of deltas that has to be applied in order to create a variant.

In order to create a variant of a CFD, at least one delta has to be selected. In the first step of variant creation, all deltas required to create a particular variant are collected. This set contains an initial set of deltas resulting either from manual selection or the specification of a configuration in a variability model. This initial set is extended by all transitively required deltas by recursively adding directly required deltas and then processing their individual requirements in the same way. In the second step, a topological sorting using the requires relations of the deltas is performed in order to create a valid sequence in which deltas may be applied. During this procedure, the order of the originally selected deltas is maintained. The first delta in the selection is considered to create the core product which is modified by following deltas. In the third step, deltas are applied in the determined order by sequentially executing the delta operations they specify. The resulting CFD is a variant of the family of possible CFDs. An example of delta modeling and variant generation for CFDs is shown in Section 5.

4. DELTA-AWARE CFD ANALYSES CFDs are used to devise, construct and certify safety-

critical systems by dividing an inspected undesired event (root fault ) into its causal constituents. Within this notation, the fault propagation paths specified in the CFD may be analyzed to yield metrics for the safety of the system, e.g., to determine the smallest possible combination of basic events that cause a root fault (minimum cut set analysis) or to calculate the probability of the root fault occurring (probability analysis). In order to use these analyses efficiently with delta CFDs, we adapt the analysis procedures known from SFTs [14] to fit the notation of CFDs and extend the analysis procedures to make them delta-aware so that they can be applied to entire families of CFDs efficiently by tracing the effects of individual deltas. We reuse intermediate results of analyses of a variant for similar parts of different variants, which can be applied when analyzing a number of family members simultanuously or sequentially, so that even previously unknown variants may benefit from calculations already performed. Concrete examples of both variant derivation and delta-aware analyses can be found in Section 5.

4.1 Delta Traces In order to facilitate delta-aware analyses of CFDs, we

analyze and store the impact of a delta on individual CFD elements during variant creation. During the process of applying delta operations, delta traces are created to track deltas that logically affect a particular CFD element as well as those that do not affect the element. Hence, a delta trace for a particular CFD element consists of a sequence of deltas that modified the element and a set of deltas that did not affect the element.

Determining the effect of a delta consists of two steps performed for each delta operation: In the first step, directly modified objects are marked if they are a CFD element (basic event, intermediate event, gate, component); for example, for a remove gate operation, the deleted gate is marked and

for an add basic event operation the created basic event. In the second step, the modification of all objects in the first step is propagated to the CFD objects logically depending on the modified objects.

This procedure traces connections from source to target port and marks all CFD elements on the way as being affected by the delta, which constitutes a particular form of change impact analysis. The concrete marking for objects along the way depends on the type of object encountered:

• Connection: Mark the target port of the connection as being affected.

• In-port: Mark the element owning the port. If the element is a component, then mark the outgoing con- nection of the affected in-port belonging to the internal fault propagation logic of the component. For all other types of elements, mark the outgoing connections of the out-port of the respective element.

• Out-port: Mark the outgoing connections of the port.

Furthermore, for each object that is traversed during mark- ing, the containing element is marked as being affected (i.e., elements for ports and components for elements). The algo- rithm may start at either a port, a connection or an element depending on the inspected delta operation. The marking is finished if no more elements can be marked according to the rules above.

For example, if in Figure 1, a remove connection delta operation was applied to BS:BrakingFails -> G1:In, the following objects would be traversed and marked in the presented order: MC (as it contains the connection), G1:In, G1, G1:Out, G1:Out -> MC:Collision, MC:Collision. All other elements of the diagram are not affected by the delta operation.

Applying this procedure for all delta operations of a CFD delta yields the change impact of the inspected delta in the form of all transitively affected elements. All unmarked elements are unaffected by this particular delta and have their delta traces extended by marking the current delta as irrelevant. This information of delta traces may be used throughout multiple cycles of creating variants, which is an essential part of delta-aware analyses on CFDs.

4.2 Delta-Aware Minimum Cut Set Analysis The goal of a minimum cut set analysis is to determine

all smallest conjunctions of events that activate the root fault when they appear–the minimum cut set. Any one conjunction of basic events causing the root fault is called a cut and it is further called a minimum cut if there is no other cut that logically subsumes it. For CFDs, the root fault is represented by an out-port of a component that is to be analyzed and the cut set consists of out-ports for basic events or Boolean literals (true/false).

In order to determine the minimum cut set, the CFD is transformed into a Boolean expression. This expression is then transformed into disjunctive normal form and mini- mized, e.g., by using the Quine-McCluskey algorithm [12]. The clauses of the resulting disjunctions are the minimum cuts of the CFD, which together are considered the minimum cut set of the CFD where individual cuts consist of out-ports owned by basic events in negated or non-negated form or Boolean literals.

5

A CFD is translated to logic iteratively, starting at the inspected out-port, by replacing each out-port that belongs to an element other than a basic fault with the logical formula describing the causes leading to the port’s acti- vation. Elements causal to the activation of a port are those connected through incoming connections, e.g., in Fig- ure 1, CD:AvoidableConnection and BS:BrakingFails are the causal constituents used to transform the AND gate G1 to Boolean logic.

The four types of CFD elements are transformed as follows: A basic event is replaced with its respective out-port. An intermediate event is replaced with the logical expression created by its sub diagram. A gate is replaced with the logical expression of its sub diagram using the logical operand specified as gate type. Finally, for a component, each out- port is replaced with the logical expression created by the sub diagram within the component, which will eventually lead to a basic event or an in-port of the inspected component in which case the procedure is continued by traversing the connections having this port as target.

If multiple connections are attached to a single in-port, they are considered as an implicit form of a logical OR, which is used during the transformation process. The exception are gates with gate type AND, which create a logical conjunction of all sub expressions created from connections to the in-port of the gate. Furthermore, gates using NOT as gate type create a disjunction of the negation of all sub expressions created from connections to the in-port of the gate. In addition, in-ports that are not connected at all can never be activated and are replaced with a Boolean value false. For example, the top level out-port Collision of Figure 1 would be transformed to Boolean logic as follows:

Collision ≡ CD:Collision∨G1:Out ≡ CD:Collision ∨ (CD:AvoidableCollision∧BS:BrakingFails)

The out-ports of the components for collision detector and braking system would then have to be replaced with the respective logical representations of the internal fault propagation logic within the respective components until only out-ports of basic events or Boolean literals remain as literals of the expression.

In order to make the minimum cut set analysis for CFDs delta-aware, we introduce a mechanism to reuse intermediate results of the analysis that are shared by multiple variants so that they do not have to be recalculated. In consequence, the transformation to a logical expression may reuse partial logical expressions determined for CFD elements in another variant that have not changed for the variant in question.

The logical expression describing an element in a specific CFD variant is stored in a cache after a number of deltas in a given sequence have been applied. This cache contains triples consisting of a CFD element, a delta trace and a logical formula. The logical formula corresponds to the logical representation of the CFD element after all deltas in the delta trace have been applied. A cache lookup for a specific CFD element is performed by first retrieving all entries for the CFD element and then selecting the CFD element in a triple with a delta trace that is equivalent to the delta trace of the CFD element in the currently processed variant. Two delta traces are considered equivalent iff they contain the same deltas affecting an element in the same order. (Deltas that do not affect an element are disregarded.) If such a CFD

element does not exist, there is a cache miss. If this entry exists in the cache, it contains the logical representation of the CFD element that has been calculated before. In this case, the cached logical formula can be used and does not have to be recalculated. This way, entire sub diagrams of the CFD can have their logical representation cached so that variants similar in this regard can benefit from previous calculations. The delta-aware minimum cut set analysis benefits from this mechanism when multiple variants are processed simultaneously, e.g., for analysing the impact of enabling or disabling a particular set of deltas.

4.3 Delta-Aware Probability Analysis Probability analysis of a CFD determines the likelihood

of a root fault by calculating the probability of activation for the respective out-port of a CFDs component. As basis for this procedure, the minimum cut set of the out-port in question has to be determined. On this basis, the likelihood of activating this out-port can be determined by means of probabilistic evaluation using the probability of occurrence for all relevant basic events.

The general idea underlying this procedure is that the sole situation in which the inspected out-port is not activated occurs when none of the cuts within the minimum cut set appear. The result can easily be used to calculate the proba- bility of activating the out-port. For a minimum cut set of an out-port OP consisting of n cuts C1, C2, . . . , Cn where p(x) describes the probability of x occurring, the following equation holds:

p(OP ) = 1 −p(¬OP ) = 1 − (p(¬C1) ∗p(¬C2) ∗ . . .∗p(¬Cn)) = 1 − ((1 −p(C1)) ∗ (1 −p(C2)) ∗ . . .∗ (1 −p(Cn)))

The probability for each cut Ci consisting of m references ci1, ci2, . . . , cim to the out-port of stochastically independent basic events is calculated as:

p(Ci) = p(ci1) ∗p(ci2) ∗ . . .∗p(cim)

The Boolean values true and false are considered to have a probability of 1.0 and 0.0, respectively. Using these formulas, the probability of activating the out-port OP can be calculated from the specified probability of basic events.

For demonstration purposes, we perform this procedure only for port BS:BrakingFails in Figure 1 considering a simple internal fault propagation logic of the braking system component. We assume the conjunction of both in-ports and p(RIM) = 0.8 and p(LFS) = 0.02 as probabilities for the basic events. In this case, the logical representation of the braking system would be

BS:BrakingFails ≡ RIM∧LFS

The resulting minimum cut set consists of only one cut: {[RIM, LFS]}. Calculating the probability of BS:BrakingFails appearing is performed in the following steps:

p(BS:BrakingFails) = 1 −p(¬BS:BrakingFails) = 1 −p(¬[RIM, LFS]) = 1 − (1 −p([RIM, LFS])) = 1 − (1 − (p(RIM) ∗p(LFS))) = 1 − (1 − (0.8 ∗ 0.02)) = 0, 016

With the probability analysis, the necessary creation of

6

the minimum cut set for an inspected out-port is the opera- tion computationally most expensive. Thus, when using the probability analysis of our approach on multiple variants of a CFD, the procedure benefits from the delta-awareness of the minimum cut set analysis described in Section 4.2. Fur- thermore, we can introduce another level of delta-awareness into the probability analysis if the results of the probability analysis are cached with delta traces similar to the minimum cut sets. The probability of activating a particular port only has to be calculated if the current delta trace does not result in a cache hit or when the deltas of the current delta trace contain at least one operation modifying the probability of a basic event included in the cut set.

5. EXAMPLE SCENARIO We provide an example scenario from the domain of home

robotics creating CFDs for the personal robot TurtleBot. The robot is meant to serve as a basic platform that is extended by both hardware and software through possibly multiple vendors. Vendors customize the platform to the needs of end users, which yields multiple variants of both the hardware and its controlling software in an open variant space.

Due to the mobility of the robot, software controlling its behavior is safety-critical as the robot may damage itself or its environment through collisions. In its basic variant, the robot merely features a bump sensor triggered on impact in order to detect obstacles. An extension for collision detection can be created by using infrared distance sensors to avoid impact. An obstacle is recognized within the range of 0cm– 70cm and is considered critically close when it is closer than 40 cm where timely braking may no longer be possible.

Obstacle Moving

Collision AvoidableCollision

AND (G2)

Bumped (BUM)

Figure 2: Detailed CFD of the “Collision Detector” compo- nent in a variant using only a bump sensor (Variant A).

In order to demonstrate feasibility of our approach, we first provide a CFD for the basic variant of the TurtleBot describing the fault propagation logic regarding collisions (Variant A). We then use delta CFDs to transform the basic variant into another variant featuring the distance sensor extension. The minimum cut set analysis and the probability analysis of the variants allow us to identify the set of basic faults causing the root fault, i.e. a collision of the robot, and the probability of the root fault.

As main CFD for the example scenario, we employ Fig- ure 1, which describes the general fault propagation with regard to the collision detector (CD) and braking system (BS) components. Furthermore, we provide detailed CFDs for the fault propagation logic encapsulated within CD. In its basic variant, it only features the bump sensor of the TurtleBot with its inherent fault propagation logic depicted in Figure 2,

which provides a basic event BUM stating that the TurtleBot bumped into an obstacle in order to detect it.

The variant of the CFD that uses the distance sensor extension in addition to the built-in bump sensor (Variant B) alters fault propagation within the collision detector as depicted in Figure 3. Another basic event WCD is introduced stating that the infrared distance sensor detected an obstacle that is critically close so that avoiding collision with the obstacle may no longer be possible. Finally, we create another variant (Variant C) of the CFD describing the hypothetical situation when the distance sensor was used as replacement for the bump sensor depicted in Figure 4.

Obstacle Moving

Collision AvoidableCollision

AND (G3)

AND (G2) AND (G4)

AND (G5)

NOT (G6)

Bumped (BUM) WithinCritical Distance (WCD)

δAδB

δAδA

δA

δAδB

δBδB

δAδAδA

δAδAδA

Figure 3: Detailed CFD of the “Collision Detector” compo- nent in a variant using a distance sensor and a bump sensor (Variant B) annotated with the deltas that create individual elements.

In order to transform the original CFD into these respective variants, we use three CFD deltas. This allows fine-grained modification of CFDs without the need for redundancy. Fur- thermore, it allows reuse of partial results of safety analyses for this family of products. In detail, the three deltas used in the example scenario are the following:

• Delta A: It creates the inherent logic of the distance sensor, consisting of elements G4, G5, G6 and WCD along with the respective connections as marked in Figure 3 and Figure 4. Furthermore, it removes connection G2:Out -> CD:Collision.

• Delta B: It adds the elements for the distance sensor in conjunction with the bump sensor consisting of G3 and the connections marked in Figure 3. This delta requires Delta A as a prerequisite.

• Delta C: It removes the fault propagation logic asso- ciated with the bump sensor consisting of G2 and BUM along with their respective direct connections. Further- more, it adds the connection marked in Figure 4. This delta requires Delta A as a prerequisite.

Variant A is the original variant of the CFD. Variant B and Variant C are created by applying Delta B and Delta C, respectively. Delta A is a shared prerequisite of both deltas and creates the distance sensor logic along with all of

7

its relevant causal connections making the respective parts suitable for caching. Furthermore, the braking system of the main CFD depicted in Figure 1 remains unaffected by all deltas. We apply these deltas to transform the basic Variant A into Variant B and Variant C, respectively, and perform the subsequent analyses using an Eclipse-based prototypical implementation of the approaches described in this paper.

Obstacle Moving

Collision AvoidableCollision

AND (G4)

AND (G5)

NOT (G6)

WithinCritical Distance (WCD)

δA

δA

δAδA

δA

δAδAδA

δAδA

δA

δC

Figure 4: Detailed CFD of the “Collision Detector” compo- nent in a variant using a distance sensor instead of a bump sensor (Variant C) annotated with the deltas that create individual elements.

Deriving Variant B and Variant C from the basic Vari- ant A and performing the minimum cut set analysis defined in Section 4.2 for all three variants yields the following mini- mum cut sets (MCS):

Variant A: MCS = [RIM, OIW, BUM] Variant B: MCS = [RIM, OIW, WCD, BUM], [RIM, OIW,¬WCD, LFS] Variant C: MCS = [RIM, OIW, WCD], [RIM, OIW,¬WCD, LFS]

During the process of deriving Variant B, the logical repre- sentation of the braking system component and its causes was cached and reused for the derivation of Variant C as neither the component nor the elements connected to its in-ports were altered as part of applying the deltas creating Variant C when compared to the state of Variant B. Assuming that, in a realistic scenario, the failure propagation logic of the braking system would be similarly complex to that of the collision detector, this procedure would save approximately half the effort of transcribing the CFD to logic when creating Variant C after Variant B.

When applying the minimum cut set analysis to the entire family of CFDs instead of just a single CFD, it is further possible to compare the resulting minimum cut sets and find differences in the variants. Generally, the larger cut sets of Variant B and Variant C suggest that the root fault of a collision has more prerequisites that need to occur when compared to the basic Variant A hinting safer systems. Fur- thermore, the additional basic event in the first cut of the cut set for Variant B compared to that of Variant C may suggest a lower chance of activating this cut. However, the concrete probabilities depend on the likelihood of the rele- vant basic events and need to be determined by a probability

analysis. We use the following plausible values for the likelihood

of basic events occurring based on our experience with the TurtleBot robot and its components when used in a domestic environment: p(RIM) = 0.8, p(OIW) = 0.15, p(LFS) = 0.02, p(BUM) = 0.95, p(WCD) = 0.1. Using the procedure described in Section 4.3, the following values for the likelihood of a collision occurring in each variant are determined (rounded to the fifth place for legibility):

Variant A: p(Collision) = 0.1140 Variant B: p(Collision) = 0.0135 Variant C: p(Collision) = 0.0141

The analysis of the different variants of the system yields valuable results on the occurrence and probability of the root fault. The rate of collisions can be greatly reduced when installing the distance sensor extension as it allows detection of obstacles without contact. Furthermore, the assumed re- duction of collisions when using bump and distance sensor in conjunction does exist but the benefits compared to using solely the distance sensor are relatively small. Based on these results, the system may still be considered sufficiently safe without the bump sensor so that other hardware configura- tions might favor a variant of the system utilizing only the distance sensor in order to save costs for the bump sensor.

6. RELATED WORK Kaiser et al. [9] created the notation underlying CFDs

to specify fault propagation paths on the basis of reusable components. Even though components may be replaced by other components with similar ports, full variability is not supported in their approach as variation points need to be predefined and modifications more fine-grained than replacing components are not possible.

In the area of SFTs, tools such as Saphire, [18] Fault- Tree+, [3] OpenFTA [2] and BlockSim7 [1] allow creating SFTs and performing minimum cut set and probability anal- yses. However, they do not support variability such that there is no dedicated concept of handling safety artifacts for families of safety-critical software systems. Moreover, none of the tools supports the extended notation of CFDs.

Gomez [7] acknowledges the need to specify variability in component fault trees. The authors propose to apply a meta- model of a compositional variability modeling approach [16] to Component Fault Trees. In this approach, variation points are introduced inside the CFT, which can be replaced by different variable elements. However, the granularity of the variation points and variability-aware analyses are not considered.

The work most related to ours is that of Lutz and Dehlinger. They describe a variability mechanism for SFTs [11, 5] and provide tool support for creating and analyzing SFTs for SPLs [6]. They use feature modeling with an annotative variability mechanism employing a 150% model, which con- tains the elements and connections for all possible variants of the SFT. Individual elements are labeled with combinations of features for the variants in which they appear. During product derivation, the parts not included in the variant are removed. Even though their approach can create variants of SFTs, we argue that our approach has certain benefits: their initial SFT is not a semantically valid model and variants can only be created with a closed variant space because el-

8

ements for all possible variants have to be included in the 150% model of the SFT. In contrast, our approach uses as source model a valid variant and allows flexible addition of new deltas, which allows coping with an open variant space. Furthermore, our approach has an external variability mechanism which does not mix concerns of representing fault propagation and variability. Finally, our approach supports CFDs, which are an extension to SFTs.

Sun et al. [19] integrate SFTs for product families into architectural models. As part of their work, they use product line SFTs containing faults and gates for all possible variants. These 150% models are pruned during product derivation to create an SFT for a concrete software product on which they perform analyses. However, their variability mechanism depends on a closed variant space as in the previous approach and their analyses do not consider the fact that different variants are often very similar.

7. CONCLUSION In this paper, we presented a variability modeling approach

for CFDs based on delta modeling, which allows transform- ing an initial CFD to specific variants and is suitable for closed and open variant spaces. We introduced delta-aware analysis techniques for CFDs to analyse multiple variants efficiently. Finally, we showed the feasibility of our approach by means of an example scenario employing multiple variants of CFDs describing fault propagation regarding collision de- tection of the TurtleBot home robot using our Eclipse-based prototypical implementation.

Currently, well-formedness of the created CFD variants is not inspected so that, e.g., orphaned gates without any connections may be created. Future work will implement validity checks for derived variants to detect these incon- sistencies. Furthermore, deltas currently may only specify requirement of other deltas. In the future, other relations will be implemented, e.g., to express incompatibility with other deltas using an excludes relation. Finally, we are planning an industrial-size case study to evaluate our approach on a larger scale and to determine actual reduction of run time efforts in practical scenarios.

8. ACKNOWLEDGMENTS The authors thank the anonymous reviewers for their valu-

able comments and suggestions. This work was partially funded by the European Social Fund (ESF) and the Federal State of Saxony within project VICCI #100098171.

9. REFERENCES [1] BlockSim7 Online Help. ReliaSoft Corporation Web

Site: http://www.reliasoft.com/BlockSim (accessed on 15 April 2013).

[2] OpenFTA User Manual. Formal Software Construction Limited Web Site: http://www.openfta.com (accessed on 15 April 2013).

[3] Reliability Workbench Technical Specification, Version 10.3. Isograph Reliability Software Web Site: http://www.isograph-software.com/_techspecs/

rwb103techspec.pdf (accessed on 15 April 2013).

[4] J. Bosch. From Software Product Lines to Software Ecosystems. In Proceedings of the 13th International Software Product Line Conference, SPLC, 2009.

[5] J. Dehlinger and R. Lutz. Software Fault Tree Analysis for Product Lines. In High Assurance Systems Engineering, 2004. Proceedings. Eighth IEEE International Symposium on. IEEE, 2004.

[6] J. Dehlinger and R. Lutz. PLFaultCAT: A Product-line Software Fault Tree Analysis Tool. Automated Software Engineering, 2006.

[7] C. Gómez, P. Liggesmeyer, and A. Sutor. Variability Management of Safety and Reliability Models: An Intermediate Model Towards Systematic Reuse of Component Fault Trees. In SAFECOMP - Computer Safety, Reliability, and Security. Springer, 2010.

[8] A. Haber, H. Rendel, B. Rumpe, and I. Schaefer. Evolving Delta-Oriented Software Product Line Architectures. In Monterey Workshop, 2012.

[9] B. Kaiser, P. Liggesmeyer, and O. Mäckel. A New Component Concept for Fault Trees. In Proceedings of the 8th Australian Workshop on Safety Critical Systems and Software-Volume 33. Australian Computer Society, Inc., 2003.

[10] N. G. Leveson. Safeware: System Safety and Computers. Addison-Wesley Longman, 1995.

[11] D. Lu and R. R. Lutz. Fault Contribution Trees for Product Families. In Software Reliability Engineering, 2002. ISSRE 2003. Proceedings. 13th International Symposium on. IEEE, 2002.

[12] M. M. Mano. Digital Logic & Computer Design. Pearson Education, 1979.

[13] K. Pohl, G. Böckle, and F. J. van der Linden. Software Product Line Engineering - Foundations, Principles and Techniques. Springer Berlin/Heidelberg, 2005.

[14] D. G. Raheja and M. Allocco. Assurance Technologies Principles and Practices: A Product, Process, and System Safety Perspective. Wiley-Interscience, 2006.

[15] I. Schaefer, L. Bettini, V. Bono, F. Damiani, and N. Tanzarella. Delta-Oriented Programming of Software Product Lines. In Software Product Lines: Going Beyond. Springer, 2010.

[16] I. Schaefer, R. Rabiser, D. Clarke, L. Bettini, D. Benavides, G. Botterweck, A. Pathak, S. Trujillo, and K. Villela. Software Diversity: State of the Art and Perspectives. STTT, 14, 2012.

[17] C. Seidl and U. Aßmann. Towards Modeling and Analyzing Variability in Evolving Software Ecosystems. In Proceedings of the 7th International Workshop on Variability Modelling of Software-intensive Systems (VaMoS), VaMoS’13, 2013.

[18] C. Smith. SAPHIRE Risk and Reliability Assessment Software. Idaho National Engineering and Environmental Laboratory Web Site: http: //saphire.inl.gov/pdf/SAPHIRE_overview.pdf

(accessed on 15 April 2013).

[19] H. Sun, M. Hauptman, and R. Lutz. Integrating Product-line Fault Tree Analysis into AADL Models. In High Assurance Systems Engineering Symposium, 2007. HASE’07. 10th IEEE. IEEE, 2007.

[20] A. von Rhein, S. Apel, C. Kästner, T. Thüm, and I. Schaefer. The PLA Model: On the Combination of Product-Line Analyses. In Proceedings of the Seventh International Workshop on Variability Modelling of Software-intensive Systems, 2013.

9