Formal Dependability Analysis using Higher-order-logic Theorem Proving

Abstract

Dependability is an umbrella concept that subsumes many key properties about a system, including reliability, maintainability, safety, availability, con- dentiality, and integrity. Various dependability modeling techniques have been developed to e ectively capture the failure characteristics of systems over time. Traditionally, dependability models are analyzed using paperand- pencil proof methods and computer based simulation tools but their results cannot be trusted due to their inherent inaccuracy limitations. To overcome these limitations, we propose to leverage upon the recent developments in probabilistic analysis support in higher-order-logic theorem proving to conduct accurate and rigorous dependability analysis. This thesis provides a semantic language embedding of the dependability concept that relies on a theory for probabilistic reasoning to develop a framework for formal dependability analysis within the sound environment of higher-order-logic theorem proving. In this thesis, we mainly focus on the formalization of two widely used dependability modeling techniques: (i) Reliability Block Diagrams - a graphical technique used to determine the reliability of overall system by utilizing the failure characteristics of individual system components; and (ii) Fault Trees - used for graphically analyzing the conditions and the factors causing an undesired top event, i.e., a critical event, which can cause the whole system iv v failure upon its occurrence. In particular, we present a RBD and FT-based formal dependability analysis framework that has the ability to accurately and rigorously determine the formal reliability, failure, availability and un- availability of safety-critical systems with arbitrary number of components. To illustrate the practical e ectiveness of our proposed infrastructure, we present the formal dependability analysis of several real-world safety-critical systems, including smart grids, WSN data transport protocols, satellite solar arrays, virtual data centers, oil and gas pipeline systems and an air tra c management system using the HOL4 theorem prover.