Compositionality and correctness of fault tolerant patterns in HOL4

In the development of critical systems, it is common practice to make use of redundancy in order to achieve higher levels of reliability. There are well established design patterns that introduce redundancy and that are widely documented and adopted by the industry. However there have been few attempts to formally verify them. In this work, we modelled in the HOL4 system such design patterns, which we call here fault tolerant patterns. We illustrate our approach by modelling three classical fault tolerant patterns: Homogeneous Redundancy, Heterogeneous Redundancy and Triple Modular Redundancy. Our model takes into account that the original system (without redundancy) computes a certain function with some delay and is amenable to random failures.We proved that our fault tolerant patterns preserve the behaviour of its replicated subsystems. The notion of correctness adopted makes use of interval arithmetic and is restricted to functional behaviour. Timing is not regarded as part of the functional behaviour in this work. Therefore, real-time systems are not the focus of our approach. We also proved that our fault tolerant patterns are compositional in the sense that we can apply fault tolerant patterns consecutively and for an arbitrary number of times. The consecutive application of our patterns still results in a system that computes a certain function with some delay and amenable to random failures. We developed a case study that verifies that a fault tolerant pattern applied to a simplified avionic Elevator Control System preserves its original behaviour. This work was done in collaboration with the Brazilian aircraft manufacturer Embraer.