Fault Injection for the Formal Testing of Fault Tolerance

Dimitri Avresky, Jean Arlat, Jean-Claude Laprie, Yves Crouzet

Abstract

This study addresses the use of fault injection for explicitly removing designhnplementation faults in complex fault-tolerance algorithms & mechanisms (FTAM), viz, fault-tolerance deficiency faults. A formalism is introduced to represent the FTAM by a set of assertions. This formalism enables an execution tree to be generated, where each path from the root to a leaf of the tree is a well-defined formula. The set of well-defined formulas constitutes a useful framework that fully characterizes the test sequence. The input patterns of the test sequence (fault & activation domains) then are determined to cover specific structural criteria over the execution tree (activation of proper sets of paths). This provides a framework for generating a functional deterministic test for programs that implement complex FTAM.

This methodology has been used to extend a debugging tool aimed at testing fault tolerance protocols developed by BULL France. It has been applied successfully to the injection of faults in the inter-replica protocol that supports the application-level faulttolerance features of the architecture of the ESPRIT-funded Delta4 project. The results of these experiments are analyzed in detail. In particular, even though the target protocol had been independently verified formally, the application of the proposed testing strategy revealed two fault-tolerance deficiency faults.

Keywords: Fault-tolerance testing, fault/error injection, desig/implementation fault removal, execution tree, well-defined formula.