Sicherheitskritische Systeme bestehen heutzutage aus einer Vielzahl von Komponenten, die meist von unterschiedlichen Herstellern mit verschiedenen Sicherheitsanalysetechniken untersucht werden. Diese Sicherheitsanalysen müssen später vom Systemintegrator zu einer heterogenen Systemanalyse zusammengefügt werden. Im Allgemeinen wird dabei vorausgesetzt, dass ein Markov-Modell nicht mehr als ein Ausgangssignal liefert, um eine modulare Integration und damit auch die Wiederverwendung der Sicherheitsanalysen der Komponenten zu ermöglichen. Diese Einschränkung reduziert jedoch die Auswahl der modularen Kompositionsszenarien. Die hier vorgestellte Arbeit ermöglicht es, mehrere Ausgangssignale eines Markov-Modells in einem Fehlerbaum zu verwenden und stellt einen Mechanismus zur Verfügung, der logische Modellierungsfehler erkennt und diese bei der qualitativen und quantitativen Analyse berücksichtigt.
nicht nur beim Austausch von Komponenten in einem fertig analysierten System zweckdienlich. Denn bei der modularen Komposition über Schnittstellen kann der Fehlerbaum des Gesamtsystems bereits konstruiert werden, bevor die verwendeten Komponenten ausgewählt bzw. die Ergebnisse der Analysen vorliegen. Durch die Schnittstellenabstraktion kann zudem die zu verwendende Sicherheitsanalysetechnik unbestimmt bleiben und ermöglicht somit eine maximale Wiederverwendbarkeit in anderen Systemen.
Damit manche Techniken zu Eingang-Ausgang-Schnittstellen passen, müssen jedoch Restriktionen bestimmt werden, die oft auch die Modularität einschränken. Zum Beispiel wird bei der Markov-Analyse die Anzahl der ausgehenden Signale auf genau eines beschränkt, um die Unabhängigkeit der Ereignisse in der Fehlerbaumanalyse des Gesamtsystems zu gewährleisten. Diese Einschränkung führt dazu, dass der Systemdesigner für die Module auf der untersten Ebene der Fehlerbaumhierarchie entscheiden muss, ob Markov als Analysetechnik zugelassen werden sollen oder nicht. Sollen mehrere Ausgangssignale einer Komponente im Fehlerbaum verwendet werden, dann ist bei diesem Ansatz die Verwendung einer Markov-Analyse für diese Komponente nicht möglich. Steht jedoch fest, dass genau ein Ausgangssignal ausreichend für die Integration der Sicherheitsanalysen ist, dann kann die Beschränkung im Modell umgesetzt und somit die Verwendung von Markov als Analysetechnik erlaubt werden.
Könnte man auf die Beschränkung der Anzahl der Ausgangssignale von MarkovModellen verzichten, dann käme das dem modularen Modellierungsansatz und der Wiederverwendbarkeit von Komponenten zu Gute. Die hier vorgestellte Arbeit setzt sich deshalb mit diesem Problem auseinander und zeigt, wie mehrere voneinander abhängige Signale aus einem Markov-Modell in einem Fehlerbaum verwendet werden können. Dabei werden logische Modellierungsfehler erkannt und in den Berechnungen der Wahrscheinlichkeiten berücksichtigt.
Die Fehlerbaumanalyse ist wohl eine der bekanntesten und weitverbreitetsten Analysetechniken in Bezug auf die Sicherheit von Systemen [Ve81]. Standards wie z.B. ISO 26262 verlangen für sicherheitskritische Systeme eine deduktive Sicherheitsanalyse und erwähnen dabei explizit die Fehlerbaumanalyse. Im Laufe der Jahrzehnte wurde eine Vielzahl an Varianten und Weiterentwicklungen vorgestellt. Component Fault Trees (CFT) [Ka05] bieten beispielsweise eine Modularisierung über Schnittstellen und ermöglichen dadurch eine komponenten-orientierte Entwicklung und Komposition von Fehlerbäumen. Andere Ansätze erhöhen die Ausdruckskraft von Fehlerbäumen durch das Hinzufügen spezieller Gates, um z.B. zeitliche Abhängigkeiten modellieren zu können. Beispiele für solche Ansätze sind Dynamic Fault Trees (DFT) [DBB92] und Pandora [Wa09].
Im Vergleich zu Fehlerbäumen sind Markov-Modelle [IEC04] zustandsbasiert und verfügen über eine höhere Ausdruckskraft bei der Modellierung von Systemen. Sie besitzen eine Vielzahl nützlicher mathematischer Eigenschaften [BP96]. Im Gegenzug leiden Markov-Modelle aber unter der Komplexität der quantitativen Analyse und mangelhafter Kompositionsfähigkeit, weil keine Eingangssignale im Markov-Modell verwendet werden können. Deshalb werden meist nur Komponenten, wie z.B. Sensoren, oder kleine Systeme mit Markov modelliert.
Die Integration von Markov-Modellen und Fehlerbäumen ist ein für die Industrie relevantes Thema und wurde daher schon mehrfach in der Literatur behandelt. So werden z.B. die Basic Events in Boolean logic Driven Markov Processes (BDMP) grundsätzlich als unabhängige Markov-Ketten mit zwei Zuständen modelliert [BB03]. Die Verbindung mit Fehlerbäumen erfolgt üblicherweise in Form einzelner Basic Events, die mit Markov modelliert und in den Fehlerbaum aufgenommen werden (siehe z.B. [Zi11]). Diese Form der Integration ist in vielen Softwaretools verfügbar, z.B. der Reliability Workbench von Isograph1, der KB3 Workbench2, Item Toolkit3 und ESSaRel4. Alle Tools haben gemein, dass aus einem Markov-Modell nur die Zustandswahrscheinlichkeit von einem Zustand bzw. einer Gruppe von Zuständen im Fehlerbaum verwendet werden kann. Diese Einschränkung verhindert, dass voneinander abhängige Ereignisse im Fehlerbaum verwendet werden.
Eine Möglichkeit zur Berechnung der Wahrscheinlichkeit des Top-Level Events ist es, die Wahrscheinlichkeit für jedes Gatter im Fehlerbaum anhand der Eingänge zu bestimmen. Dazu wird bei den Gattern direkt oberhalb der Basic Events begonnen und stufenweise vorgegangen, bis schließlich das Top-Level Event erreicht wird. Ein Nachteil dieser Methode ist, dass für die einzelnen Gatter nur die Wahrscheinlichkeiten bekannt sind. Information über deren Eingänge und eventuelle Abhängigkeiten zwischen diesen, oder innerhalb von Teilbäumen, gehen verloren. Das ist ein Problem, denn in der Fehlerbaumanalyse wird grundsätzlich davon ausgegangen, dass alle Basic Events voneinander unabhängig sind. Ist dies nicht der Fall, dann kann es zu Fehlern in der qualitativen und quantitativen Analyse kommen. Markov-Modelle sind zustandsbasiert und befinden sich daher zu jedem Zeitpunkt in genau einem Zustand. Ein einzelner Zustand oder eine Gruppe von Zuständen kann mit einem Ausgangssignal verbunden werden. Dieses Ausgangssignal kann nun z.B. als Basic Event oder Eingang für andere Systemkomponenten verwendet werden. Dazu wird berechnet wie wahrscheinlich es ist, dass das Markov-Modell nach einer bestimmten Zeit (z.B. nach Ablauf der Missionszeit) in einem der entsprechenden Zustände ist.
Das Problem bei der Verwendung mehrerer Signale aus dem gleichen Markov-Modell ist, dass die verknüpften Wahrscheinlichkeiten nicht unabhängig sind. Abbildung 1 veranschaulicht dieses Problem anhand eines Widerspruchs. Werden die beiden Ausgangssignale des Markov-Modells im Fehlerbaum an einem UND-Gatter 1 http://www.isograph.com/ 2 http://researchers.edf.com/software/kb3-44337.html 3 http://www.itemsoft.com/item_toolkit.html 4 http://www.essarel.de/ zusammengeführt, dann kann dieses Gatter niemals erfüllt sein. Obwohl rechnerisch aufgrund der zugewiesenen Wahrscheinlichkeiten ein Wert ermittelt werden kann, ist es unmöglich, dass sich das Markov-Modell zur gleichen Zeit in zwei unterschiedlichen Zuständen befindet.
Abbildung 1: Logischer Modellierungsfehler am UND-Gatter Im Gegensatz dazu stellt die Verwendung mehrerer Signale aus einem Markov-Modell bei einem ODER-Gattern keinen Modellierungsfehler dar, abgesehen von der Nichtbeachtung der Unabhängigkeit von Basic Events in der Fehlerbaumanalyse. Die Abhängigkeit führt zu einer falschen Berechnung der Eintrittswahrscheinlichkeit des ODER-Gatters. Bei zwei Eingängen 1 und 1 gilt die Formel 1 1 1 ∗ 1 . Für zwei sich gegenseitig ausschließende Ereignisse ist die korrekte Formel jedoch 1 1 . Auch wenn die Differenz der beiden Formeln für kleine Werte von 1 und 1 gering ist [An01], entspricht dies doch einer optimistischen Approximation. Um eine Unterschätzung der Fehlerwahrscheinlichkeit zu verhindern, dürfen Schnittmengenprodukte abhängiger Ereignisse deshalb nicht von deren Summe abgezogen werden.
Damit die hier aufgezeigten Probleme erkannt werden können ist es deshalb notwendig, die Quellen von Wahrscheinlichkeiten im Fehlerbaum zu propagieren. Es ist nicht ausreichend, die Überprüfung der Abhängigkeit von Basic Events auf die untersten Gatter des Fehlerbaums zu beschränken. Im Folgenden wird eine Methode vorgestellt, die Informationen über die Herkunft von Basic Events im Fehlerbaum propagiert und dadurch Modellierungsfehler an UND-Gattern erkennen bzw. Berechnungsfehler an ODER-Gattern vermeiden kann. Jedem im System verwendeten Markov-Modell muss ein eindeutiger Name zugewiesen werden, z.B. 1 dem ersten, 2 dem zweiten usw. Diese Namen werden verwendet, um den Einfluss voneinander abhängiger Ausgangssignale (kurz Signale) von MarkovModellen im Fehlerbaum verfolgen zu können. Diese Signale werden als Basic Events behandelt und erhalten ebenfalls eindeutige Namen, z.B. 1 , 1 usw. Zur Vereinfachung werden nur ODER- und UND-Gatter betrachtet. Alle anderen nichtdynamischen Gatter können durch diese beiden Gatter dargestellt werden. Um die Veranschaulichung des Algorithmus zu vereinfachen wird ferner angenommen, dass Signale aus Markov-Modellen nicht mehrfach als Basic Event verwendet werden. Mit einer zusätzlichen Unterscheidung der Signale in den Optionstabellen ist es jedoch möglich, diese Voraussetzung zu verwerfen.
Basic Events und Gattern werden Optionstabellen zugeordnet, die aus Schlüssel-Wert Paaren bestehen. In ihnen werden konditionelle Ausfallwahrscheinlichkeiten gespeichert. Jede Optionstabelle (kurz Tabelle) verfügt über einen Wert für den Standardschlüssel , der die Signale von Markov-Modellen nicht einschränkt. Abhängig von der Verwendung von Signalen im entsprechenden Teil des Fehlerbaums kann eine Tabelle noch weitere Schlüssel enthalten. Bei der Berechnung der zugehörigen Werte wird den Signalen aus den im Schlüssel enthaltenen Markov-Modellen eine Null zugewiesen. Anhand der berechneten Tabelleneinträge kann z.B. bei einem UND-Gatter festgestellt werden, ob ein Eingang ohne den Einfluss eines bestimmten MarkovModells überhaupt auftreten kann. Das Erstellen der Tabellen wird bei den Basic Events begonnen und bis zum Top Event weitergeführt. Für die Bearbeitung eines Gatters müssen die Tabellen aller Eingänge des Gatters vorliegen. In Bezug auf Basic Events und Gatter bedeutet die Aussage „von Markov-Modell abhängig“, dass es in der jeweiligen Tabelle einen Eintrag für gibt.
Ein Basic Event , das kein Signal aus einem Markov-Modell ist, bekommt als einzigen Eintrag in die Optionstabelle das Paar ( , ( . Basic Events, die aus einem MarkovModell stammen, bekommen zusätzlich einen Tabelleneintrag mit dem Namen des Markov-Modells und einer Null, denn das Basic Event kann nicht eintreten, wenn der Einfluss des Markov-Modells ignoriert wird.
Zur Berechnung eines ODER-Gatters werden die Tabellen aller Eingänge benötigt. Zunächst wird die Tabelle des ODER-Gatters mit dem Standardwert initialisiert (Phase 1). Danach werden alle Markov-Modelle ermittelt, von denen das Gatter abhängig ist (Phase 2). Aus der Liste der Markov-Modelle werden schließlich die restlichen Schlüssel generiert und die zugehörigen Wahrscheinlichkeiten berechnet (Phase 3). Die drei Phasen werden nun im Einzelnen erläutert. Die Tabelle eines ODER-Gatters enthält immer den Eintrag , , der die normal berechnete Wahrscheinlichkeit darstellt. Das heißt, dass alle Signale der Markov-Modelle uneingeschränkt auftreten können und somit in die Berechnung der Wahrscheinlichkeit einfließen. Zur Berechnung werden die Einträge mit dem Schlüssel der jeweiligen Tabellen genommen. Falls zwei Eingänge und vom selben Markov-Modell abhängig sind, dann gilt , 0, denn beide Ereignisse schließen sich gegenseitig aus. Für ein ODER-Gatter mit Eingängen lautet die Formel [LB11]: ∑ 1 !" ∑ ∑ ⋯ ! ( , ⋯ , … , ! + ⋯ + (−1 " ( , … , (1) Abbildung 2 zeigt links als Beispiel ein ODER-Gatter mit drei Eingängen. Setzt man die Wahrscheinlichkeiten (Variable $) der Eingänge in (1) ein, dann erhält man ( = (% + ( 1 + ( 1 − (%, 1 − (%, 1 − ( 1 , 1 + (%, 1 , 1 = 0,039502 . Berücksichtigt man jedoch die Abhängigkeit der beiden Basic Events 1 und 1 , dann hat der Schlüssel den Wert ( = (% + ( 1 + ( 1 − (%, 1 − (%, 1 = 0,0397.
Für die weiteren Einträge in der Tabelle ist es notwendig zu wissen, welche MarkovModelle bei der Berechnung des Gatters beachtet werden müssen. Dazu wird aus den Tabellen aller Eingänge eine Liste von eindeutigen Schlüsseln generiert, die genau einen Namen eines Markov-Modells enthalten. Falls es keine Signale aus Markov-Modellen unterhalb des Gatters gibt, dann bleibt die Namensliste leer und es werden keine weiteren Einträge zur Tabelle hinzugefügt.
Aus der Liste der relevanten Markov-Modelle werden nun die weiteren Schlüssel für die Einträge der Tabelle generiert. Es ist auch notwendig Kombinationen von MarkovModellen zu betrachten, da es vorkommen kann, dass bei der Berechnung des nächst höheren Gatters gleich mehrere Markov-Modelle ignoriert werden müssen. Dazu wird jedem Namen aus der Liste eine binäre Variable zugeordnet. Anschließend kann unter Verwendung einer Binärtabelle jede mögliche Kombination von Namen abgeleitet und als Schlüssel in die Tabelle eingetragen werden. Bei der Berechnung des Wertes für einen Schlüssel * wird von jedem Eingang der Wert +( genommen. Weil die Schlüssel des ODER-Gatters Kombinationen aus allen enthaltenen Markov-Modellen darstellen kann es vorkommen, dass sich für Eingänge des Gatters kein Wert für * zuordnen lässt. In diesem Fall wird der längste Teilschlüssel von * aus der Tabelle gewählt. Sollte es überhaupt keine Übereinstimmung für einen Eingang geben, dann wird der Standardwert , ( verwendet. Abbildung 2 zeigt auf der rechten Seite das Gatter 2 mit drei Eingängen. Das Gatter (links) ist, wie aus der Tabelle ersichtlich, abhängig von 1. 2 ist ein Signal aus einem anderen Markov-Modell 2 und hat deshalb die Schlüssel und 2. B ist ein gewöhnliches Basic Event mit Standardschlüssel nil.
12 und 12 In Phase 1 wird die Optionstabelle initialisiert. Da es keine zwei Eingänge gibt, die vom selben Markov-Modell abhängig sind, kann der Wert für mit der Standardformel (1) und den Werten , 0,0397, , 2 0,02 und , - 0,01 berechnet werden. In Phase 2 werden nun die relevanten Markov-Modelle ermittelt. Laut den Tabellen der Eingänge lautet die Liste . 1, 2/. In Phase 3 werden schließlich die Schlüssel generiert und die Tabelle mit Werten gefüllt. Aus den binären Variablen 01 und 012 werden die Kombinationen . 1/, . 2/ und . 1, 2/ hergeleitet. Der Wert 1 2 wird mit den Werten 1 0,01, 1 2 , 2 0,02 und 1 - , - 0,01 berechnet. Analog dazu , 0,0397, 12 2 0 und 12 2 mit 12 - , - 0,01, 1 0,01, 1 ,12 2 0,01. Die Werte in Abb. 2 sind Rundungen. mit
,
Abbildung 2: Zwei ODER-Gatter mit je drei Eingängen
Analog zum ODER-Gatter wird die Optionstabelle zunächst initiiert (Phase 1) und dann mit den ermittelten Markov-Modellen (Phase 2) der Rest der Tabelle berechnet (Phase3).
Die Optionstabelle eines UND-Gatters enthält, wie auch bei einem ODER-Gatter, einen Eintrag für den Schlüssel . Allerdings führen mehrere Signale aus dem gleichen Markov-Modell beim UND-Gatter, wie bereits gezeigt, zu einem logischen Widerspruch. Der Wert für den Schlüssel repräsentiert deshalb nur die durch konventionelle Fehlerbaumberechnung ermittelte Eintrittswahrscheinlichkeit, wenn keine zwei Eingänge des Gatters vom gleichen Markov-Modell abhängig sind. Die Berechnung des Wertes für den Schlüssel erfolgt nach den folgenden Schritten: 1. Die Tabellen aller Eingänge werden auf Nullen durchsucht und die entsprechenden Schlüssel in einer Liste 4 gespeichert. Enthält diese Liste Dubletten oder den Schlüssel , dann ist der Wert des UND-Gatters null. Dies lässt auf einen logischen Fehler in der Modellierung schließen, denn das Gatter kann nicht beim Eintritt des Top-Level Events mitwirken. Die Situation sollte vom Systemintegrator eingehend untersucht werden. 2. Für jeden Eingang des UND-Gatters wird eine Kopie der Liste 4 aus Schritt 1 erstellt und alle Schlüssel * entfernt, für die + 0 gilt. Aus der Liste wird der längst mögliche Schlüssel * gebildet, für den es in der Tabelle von einen Eintrag gibt. Gibt es keinen solchen Schlüssel, dann gilt * . 3. Berechne den Wert des UND-Gatters unter Verwendung der entsprechenden
Werte für * für alle Eingänge .
Abbildung 3 zeigt als Beispiel links das Gatter 56 mit drei Eingängen: Das Gatter (siehe Abb. 2), ein Basic Event aus 1, und ein reguläres Basic Event. Die Tabellen der Eingänge enthalten nur für Schlüssel 1 von Eingang 17 eine Null. Deshalb wird für die Berechnung von , (56 der Wert , ( 17 = 0,02 verwendet. Weil dieser Wert von 1 abhängt müssen die anderen Eingänge des Gatters von 1 unabhängig bleiben, was durch die Verwendung der Werte 1 ( = 0,01 und 1 (- = , (- = 0,01 gewährleistet wird. Nach der Berechnungsformel für UND-Gatter, (56 = ∏ ( , gilt , (56 = 2,0 ∗ 10"9.
Diese Phase ist analog zum ODER-Gatter.
Aus der Liste der relevanten Markov-Modelle werden, wie beim ODER-Gatter beschrieben, die weiteren Schlüssel für die Einträge der Optionstabelle generiert. Enthält die Tabelle eines Eingangs für den Schlüssel * oder einen Teil des Schlüssels * eine Null, dann ist +(56 = 0. Die restlichen Schlüssel werden berechnet, indem für jeden Eingang aus der entsprechenden Tabelle ebenfalls der Wert für den Schlüssel * bzw. den längsten vorhandenen Teilschlüssel von * genommen wird. Gibt es für einen Eingang keinen solchen Teilschlüssel, dann wird der Standardwert , ( verwendet.
Das Gatter 56 2 auf der rechten Seite von Abb. 3 ist abhängig von 1 und 2. Daraus ergeben sich die Schlüssel , 1, 2 und { 1, 2} für die Tabelle von 56 2 . Da die Eingänge keine gemeinsamen Abhängigkeiten haben gilt , (56 2 = , ( ∗ , ( 2 ∗ , (- = 7,94 ∗ 10"9. Eingang 2 hat für den Schlüssel 2 eine Null, deshalb gilt 1 56 2 12 56 2 1
0 und ∗ , , Abbildung 4 zeigt rechts das Gatter 56 mit zwei Eingängen aus Markov-Modellen und dem Gatter (links) als weiteren Eingang. Wegen der beiden Eingangssignale 1 und 2 darf nicht von 1 und 2 abhängig sein, da sonst das Gatter 56 nicht erfüllt werden kann. Aus 1 ,12 0 folgt aber , 56 0. In diesem vereinfachten Beispiel ist das Ergebnis direkt nachvollziehbar, denn keines der Markov-Modelle kann sich in Zustand - befinden (Eingänge 1 und 2 ), wenn es sich gleichzeitig in Zustand % befinden muss (Eingang ). Das Gatter 56 kann niemals erfüllt werden und der Systemintegrator muss in diesem Fall die Logik und die Struktur des Fehlerbaums eingehend überprüfen und entsprechend berichtigen.
Abbildung 4: Erkennung eines Modellierungsfehlers Die vorgestellte Arbeit befasst sich mit der Integration modularer Sicherheitsanalysen und untersucht im Speziellen die Möglichkeit, mehrere Ausgangssignale aus einem Markov-Modell in einem Fehlerbaum verwenden zu können. Mit Hilfe von Optionstabellen, in denen bedingte Wahrscheinlichkeiten und Abhängigkeiten für Basic Events und Gatter des Fehlerbaums gespeichert werden, kann der Einfluss der Signale aus Markov-Modellen von den Basic Events bis hin zum Top-Level Event verfolgt werden. Mit den gewonnenen Informationen werden zum einen Berechnungsfehler an ODER-Gattern vermieden und zum anderen logische Modellierungsfehler durch zwei sich gegenseitig ausschließende Basic Events unterhalb eines UND-Gatters erkannt. Die erkannten Fehler können dann durch den Systemintegrator gezielt berichtigt werden. Als weiterführende Arbeit wurde die mehrfache Verwendung von Ausgangssignalen im Fehlerbaum bereits methodisch erarbeitet. Als nächster Schritt ist eine Toolintegration in Enterprise Architect geplant. Des Weiteren soll der Ansatz auf dynamische Fehlerbäume ausgeweitet werden. Außerdem ist eine Verfeinerung der Abhängigkeiten zwischen den Basic Events angedacht. So könnten mit einem modifizierten Ansatz die unterschiedlichsten kausalen und temporalen Abhängigkeiten zwischen Basic Events im Fehlerbaum verfolgt und berücksichtigt werden.