Integration von Markov Modellen in FehlerbäumeAlexanderProhaskaprohaska@cs.uni-kl.deLehrstuhl Software Engineering: DependabilityTechnische Universität Kaiserslautern3049, 67653Postfach, KaiserslauternIntegration von Markov Modellen in Fehlerbäume27CEF2D4EB1CE49CAD2FC47FE8B7F679GROBID - A machine learning software for extracting information from scholarly documents
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.
Einleitung
Bei sicherheitskritischen Systemen spielt die verteilte Entwicklung eine immer größere Rolle, weil die verschiedenen Systemkomponenten von unterschiedlichen Herstellern produziert werden. Dabei handelt es sich oft um standardisierte Komponenten, die in den unterschiedlichsten Systemen eingesetzt werden können. Zum einen ist es notwendig, eine Komponente in verschiedenen Systemen verwenden zu können, ohne jedes Mal erneut eine Sicherheitsanalyse anfertigen zu müssen. Zum anderen sollen gleichwertige Komponenten untereinander austauschbar sein, ohne die Sicherheit des Systems erneut analysieren zu müssen. Das trägt dazu bei, die Kosten bei der Entwicklung von neuen Produkten durch die Wiederverwendung bereits durchgeführter Analysen zu senken. Auch bei Produktlinien ist es entscheidend, den Analyseaufwand für die einzelnen Ausführungen zu minimieren.
Voraussetzung für die Wiederverwendung von Komponenten ist eine einfache Integration der Komponenten und den dazugehörigen Analysemodellen und Ergebnissen. Dabei ist es essentiell, dass die Anforderungen der Komponenten mit denen des restlichen Systems übereinstimmen. Damit eine Integration gelingen kann ist es notwendig, entsprechende Schnittstellen für die Komponenten zu definieren. Das ist
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
Unabhängigkeit von Ereignissen
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
Basic Events
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 Markov-Modell 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.
ODER-Gatter
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.
Phase 1: Initiierung der Optionstabelle
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 " ( , … ,
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. Abbildung 2: Zwei ODER-Gatter mit je drei Eingängen
UND-Gatter
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).
Phase 1: Initiierung der Optionstabelle
Die Optionstabelle eines UND-Gatters enthält, wie auch bei einem ODER-Gatter, einen
Beschränkung der Anzahl der Ausgangssignale von Markov-Modellen 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. 2 Hintergrund 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.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.Phase 2 :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. 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 ,Abbildung 3: Zwei UND-Gatter mit je drei Eingängen 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 Zustandbefinden (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.
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 Isograph 1 , der KB3 Workbench 2 , Item Toolkit 3 und ESSaRel 4 . 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.
Phase 3: Füllen der Optionstabelle AusDie 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 1 7 eine Null. 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.
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 deshalb gilt 12 56 2 0 und 1 ,12 56 2 0. Für Schlüssel 1 giltkonventionelle Fehlerbaumberechnung ermittelte Eintrittswahrscheinlichkeit, wennkeine zwei Eingänge des Gatters vom gleichen Markov-Modell abhängig sind. DieBerechnung des Wertes für den Schlüsselerfolgt nach den folgenden Schritten:1. Deshalb wird für die Berechnung von verwendet. Weil dieser Wert von 1 abhängt müssen die anderen Eingänge des Gatters , (56 der Wert , ( 1 7 = 0,02= 0,01 und 1 (-= , (-= 0,01 gewährleistet wird. Nach der Berechnungsformel für von 1 unabhängig bleiben, was durch die Verwendung der Werte 1 ( UND-Gatter, (56 = ∏ ( , gilt , (56 = 2,0 * 10 "9 .Phase 2: Ermittlung der relevanten Markov-ModelleDiese Phase ist analog zum ODER-Gatter.BeispieleDas Gatter 56 2 auf der rechten Seite von Abb. 3 ist abhängig von 1 und 2. Darausergeben sich die Schlüssel, 1, 2 und { 1, 2} für die Tabelle von 56 2. Da dieEintrag für den Schlüssel Eingänge keine gemeinsamen Abhängigkeiten haben gilt . Allerdings führen mehrere Signale aus dem gleichen * , (56 2 = , ( , ( 2 * , (-= 7,94 * 10 "9 . Eingang 2 hat für den Schlüssel 2 eine Null,
A probabilistic approach to estimating computer system reliabilityRApthorpeProceedings of the Fifteenth Systems Administration Conference (LISA XV)(USENIX Associationthe Fifteenth Systems Administration Conference (LISA XV)(USENIX AssociationBerkeley, CA200131A new formalism that combines advantages of fault-trees and Markov models: Boolean logic driven Markov processesMBouissouJ.-LBon10.1016/S0951-8320(03)00143-1Reliability Engineering & System Safety0951-8320822November 2003Mathematical theory of reliabilityREBarlowFProschanSIAM. Classics in applied mathematics1996Dynamic Fault Tree Models for Fault Tolerant Computer SystemsJBDuganSJBavusoMABoydIEEE Transactions on Reliability4131992. SeptemberIEC 61165Application of Markov techniquesIEC20042State/event Fault Trees: A safety and Reliability analysis Technique for Sotware-Controlled SystemsBKaiser2005Technische Universitaet Kaiserslautern, Fachbereich InformatikPHD ThesisProbability InequalitiesZLinZBai2011SpringerBerlin HeidelbergFault Tree HandbookWEVeseleyDivision of the System Safety Office of Nuclear Reactor RegulationWashington DCUS Nuclear Regulatory Commission1981Pandora -A Logic for the Qualitative Analysis of Temporal Fault TreesMWalker2009University of Hull, UKPhD ThesisGastric esophageal surgery risk analysis with a fault tree and Markov integrated modelLZixianNXinLYiliuSQingluWYukunReliability Engineering & System Safety96122011