Estimation of the coverage of fault tolerant systems

This dissertation is dedicated to the estimation of the coverage of fault tolerant systems. Coverage is estimated by statistical processing of fault injection results. We consider both simple sampling and stratified sampling.

Concerning statistical tools from the Frequentist School, we show that the approximation given by the central limit theorem is no longer valid for high coverage estimations. The confidence region theory, which is necessary for an estimation without approximation when stratified sampling is used, is presented and applied to fault injection. A multidimensional constrained optimization problem must then be solved.

Concerning statistical tools from the Bayesian School, the global non-coverage posterior distribution is obtained for partitioned samples with few strata. The first moments of the global non-coverage distribution are obtained by computing the moments of the non-coverage posterior distributions in each stratum.

The statistical tools are applied to three examples of fault tolerant systems. These examples were constructed in such a way as to test the limits of applicability of the various estimation techniques. The comparison between the results obtained provides guidance for the choice of an estimation method depending on the characteristics of the fault tolerant system and the fault injection experiments.

The evolution of coverage with time is also studied. A Markovian model of a fault tolerant mechanism is presented in which coverage is a time-dependent function. We then propose for estimating the parameters of this model using the timing information obtained during fault injection experiments. The method takes into account the inevitable data truncation phenomenon.

Publications

Journal Publications

M. Cukier, D. Powell and J. Arlat, Coverage Estimation Methods for Stratified Fault-Injection, IEEE Transactions on Computers, vol. 48, no. 7, July 1999, pp.707-723. (Also published in Year 1 Report, Esprit Project 20072: Design for Validation, pp.559-591, 1996.)

Conference Publications

D. Powell, M. Cukier and J. Arlat, On Stratified Sampling for High Coverage Estimations, in Proc. 2nd European Dependable Computing Conference (EDCC-2), (A. Hlawiczka, J. G. Silva and L. Simoncini, Ed.), (Taormina, Italy), LNCS 1150, pp.37-54, Springer Verlag, October 1996.

M. Cukier, J. Arlat and D. Powell, Frequentist and Bayesian Coverage Estimations for Stratified Fault-Injection, in Proc. 6th IFIP Working Conf. on Dependable Computing for Critical Applications (DCCA-6), (M. Dal Cin, C. Meadows and W. H. Sanders, Eds.), Dependable Computing and Fault-Tolerant Systems, 11, pp.43-61, IEEE Computer Society Press, 1998 (Proc. IFIP 10.4 Work. Conf. held in Grainau, Germany, March 1997).

D. Powell, M. Cukier, J. Arlat and Y. Crouzet, Estimation of Time-Dependent Coverage, in Proc. 8th European Workshop on Dependable Computing (EWDC-8), Goteborg, Sweden, April 1997, (20 pages). (Also published in Year 2 Report, Part 2 (Papers), Esprit Project 20072: Design for Validation, pp.541-560, 1997.)

Technical Reports

D. Powell, M. Cukier and J. Arlat, On the Confidence of Very High Coverage Estimations, Research Report N°94506, LAAS-CNRS, Toulouse, France, December 1994 (modified in March 1995), 22 pages.

M. Cukier, Estimation de la couverture de systèmes tolérants aux fautes, Mémoire de Doctorat (Ph.D. thesis), Institut National Polytechnique de Toulouse, N°1180, July 1996.