Abstract

Dynamic dependability analysis has become an essential step in the design process of safety-critical systems to ensure the delivery of a trusted service without failures. Dependability usually encompasses several attributes, such as reliability and availability. A dynamic dependability model is created using one of the dependability modeling techniques, such as Dynamic Fault Trees (DFTs) and Dynamic Reliability Block Diagrams (DRBDs). Several analysis methods, including paper-and-pencil or simulation, exist for analyzing these models to ascertain various dependability related parameters. However, their results cannot be always trusted since they may involve some approximations, truncations or even errors. Formal methods, such as model checking and theorem proving, can be used to overcome these inaccuracy limitations due to their inherent soundness and completeness. However, model checking suffers from state-space explosion if the state space is large. While, theorem proving was used only for the static dependability analysis without considering the system dynamics.

In order to conduct the formal dependability analysis of systems that exhibit dynamic failure behaviors within a theorem prover, these models need to be captured formally, where their structures, operators and properties are properly formalized. In this thesis, we provide a complete framework for the formal dependability analysis of systems modeled as DFTs and DRBDs in the HOL4 higher-order logic theorem prover. We provide the formalization of DFT gates and verify important simplification theorems based on well-known DFT algebra. In addition, our framework allows both qualitative and quantitative DFT analyses to be conducted using theorem proving. We use this formalization to formally verify the DFT rewrite rules, that are used by automated DFT analysis tools, to ascertain their correctness. Due to the lack of a DRBD algebra that allows the analysis using a theorem prover, in this thesis, we develop and formalize a novel algebra that includes operators and simplification theorems to formalize traditional RBD structures, such as the series and parallel, besides the DRBD spare construct. We formally verify their reliability expressions, which allows conducting both the qualitative and quantitative analyses of a given system. Leveraging upon the complementary nature of DFTs and DRBDs, our proposed framework provides the possibility of formally converting one model to the other, which allows reasoning about both the success and failure of a given system. Our framework provides generic expressions of probability of failure and reliability that are independent of the failure distribution of an arbitrary number of system components, which cannot be obtained using other formal tools, such as model checking. In order to demonstrate the usefulness of the proposed framework, we formally model and analyze the dependability of the terminal, broadcast and network reliability of shuffle-exchange networks, which are multistage interconnections networks that are used to connect the elements of multiprocessor systems. Conducting a sound analysis with generic expressions is essential in these systems, where it is required to accurately capture and analyze the failure behavior.