Fault Injection and Dependability Evaluation of Fault-Tolerant Systems.
The authors describe a dependability evaluation method based on fault injection that establishes the link between the experimental evaluation of the fault tolerance process and the fault occurrence process. The main characteristics of a fault injection test sequence aimed at evaluating the coverage of the fault tolerance process are presented. Emphasis is given to the derivation of experimental measures. The various steps by which the fault occurrence and fault tolerance processes are combined to evaluate dependability measures are identified and their interactions are analyzed. The method is illustrated by an application to the dependability evaluation of the distributed fault-tolerant architecture of the Esprit Delta-4 Project.
Introduction
The evaluation of a fault tolerant system is a complex task that requires the use of different
levels of modeling (axiomatic, empirical and physical models) and related tools [1]. A large
number of studies (e.g., see [2-4]), have shown the prominence of the efficiency of the fault
tolerance algorithms and mechanisms (FTAMs) on the dependability of a wide range of
systems and architectures. Determination of the appropriate model for the fault tolerance
process and proper estimation of the associated coverage parameters are therefore essential in
any dependability evaluation study.
Compared to other possible approaches such as proving or analytical modeling, fault-injection
is particularly attractive [5-13]. By speeding up the occurrence of errors and failures,
fault injection is a method for testing the FTAMs with respect to their own specific inputs: the
faults that they are intended to tolerate.
This work was performed within the framework of PDCS, ESPRIT Basic Research Action n- 3092, (Predictably
Dependable Computing Systems). Some aspects of this research were put into practice on the testbed architecture
developed as part of the implementation validation activity of the ESPRIT Precompetitive Project n- 2252 Delta-4
(Definition and Design of an open Dependable Distributed system architecture) with the support of a Grant awarded by
the Midi-Pyr-n-es Regional Authority.
The authors are with the Laboratoire d'Automatique et d'Analyse des Syst-mes du Centre National de la Recherche
Scientifique (LAAS-CNRS) Toulouse, France. Jean Arlat was holding the Toshiba Endowed Chair at the Tokyo
Institute of Technology, Japan, during the preparation of the final manuscript of this paper.
As pointed out in [14], fault injection addresses both dimensions of FTAM validation: fault
removal and fault forecasting [15-16]. With respect to the fault removal objective, fault
injection is explicitly aimed at reducing, by verification, the presence of FTAM design and
implementation faults. Since such faults can cause incorrect behavior of the FTAMs when they
are faced with the faults they are intended to handle, we call them fault-tolerance deficiency
faults (in short, ftd-faults). From the verification viewpoint, fault injection therefore aims to
reveal such ftd-faults and to determine appropriate actions to correct the design or
implementation of the FTAMs. In the case of fault forecasting, the main issue is to rate, by
evaluation, the efficiency of the operational behavior of the FTAMs. This type of test thus
constitutes primarily a test of the FTAMs with respect to their overall behavioral specification.
In practice, this means estimating the parameters that characterize the operational behavior of
the FTAMs: coverage factors, dormancy, latency, etc.
Both dimensions are of interest for validating the FTAMs. The relationships and
complementarity between these two objectives, as well as the main characteristics of the ftd-
removal objective, are addressed in [14, 17, 18]. This paper focuses on the fault
forecasting objective.
The fault tolerance coverage estimations obtained through fault injection experiments are
estimates of conditional probabilistic measures characterizing dependability. They need to be
related to the fault occurrence and activation rates to derive overall measures of system
dependability. Such a necessary relationship is - at least conceptually - well established.
However, few studies consider its actual incorporation into the dependability evaluation of real
fault-tolerant systems. Among the most significant related studies, see the work reported in
[19], the ESS, SIFT and FTMP validation processes depicted in chapters 12, 16 and 17 of [20]
and, more recently, the evaluation of the MAFT architecture presented in [21].
This paper describes a dependability evaluation method based on fault injection that
establishes the link between the experimental evaluation of the coverage of the fault tolerance
process and the fault occurrence process. The paper also illustrates the application of the
method to the evaluation of a real system. Such an experiment-based evaluation method
combining fault injection experiments and analytical evaluation has been - along with formal
protocol verification activities - the central point in the validation of the distributed fault-tolerant
architecture of the ESPRIT Delta-4 Project (see [22] for a global description of the
validation tasks). Markov-based modeling and evaluation, and especially sensitivity analysis of
the impact of the coverage parameters (both coverage factors and latencies), helped to identify
the most significant parameters to be estimated from the fault injection experiments.
Conversely, the experiments not only made it possible to obtain the range of values for the
coverage parameters used in the analytical models, but also helped in the validation and refinement
of these models. In particular, the models were refined to capture specific behaviors
revealed by the experiments.
More recently, the study presented in [23] described an example of cross-fertilization
between experimental evaluation and analytical modeling. However, that study relied more on
the analysis of recorded field data than on fault injection experiments. The physical fault
injection experiments carried out on the Delta-4 prototype testbed made it possible to iterate the
evaluation process for validating the design assumptions (e.g., the fail-silence assumption) and
thus had an impact - albeit during the final phases - on the development of the Delta-4
architecture.
The paper defines and analyzes the relationships between experimental and analytical
dependability evaluation. The results obtained in the case of the evaluation of a real system
provide practical examples of such relationships. The remainder of this paper consists of four
sections. Section II depicts the main characteristics of a fault injection test sequence aimed at
evaluating the fault tolerance process. This section - adapted and extended from [24] -
summarizes some definitions and results that are necessary for the understanding of the
developments presented in the next section. Section III describes the main steps of the
integration of the fault occurrence and fault tolerance processes that were defined and fully
detailed in [25]. Section IV applies the method to the dependability evaluation of the Delta-4
distributed fault-tolerant architecture. Section V concludes the paper.
II. Experimental Evaluation of Fault Tolerance
The proposed experimental evaluation method embodies the concept of a fault injection test
sequence, characterized by an input domain and an output domain.
The input domain corresponds to a set of injected faults F and a set A that specifies the data
used for the activation of the target system and thus, of the injected faults.
The output domain corresponds to a set of readouts R that are collected to characterize the
target system behavior in the presence of faults and a set of measures M that are derived from
the analysis and processing of the FAR sets.
Together, the FARM sets constitute the major attributes that can be used to fully characterize a
fault injection test sequence. In practice, the fault injection test sequence consists of a series of
experiments; each experiment specifying a particular point in the {FxAxR} space.
A . Characterization of a Fault Injection Test Sequence
During each experiment in a fault injection test sequence, a fault from the F set is injected
that, in conjunction with the activity of the target system determines an error pattern
that constitutes a test input for the FTAMs to be validated. For increased confidence in the
estimates obtained, it is necessary to carry out a large number of experiments. For minimum
bias in the estimation, it is further recommended to select both F and A sets by statistical
sampling among the expected operational fault and activation domains of the target fault tolerant
system. Further issues concerning the combination of the F and A sets to produce error
patterns are discussed in detail in [14]; we focus here on the R and M sets characterizing the
experimental evaluation process.
The readouts collected in R during an experiment contribute to a characterization of the state
of the target system. This is achieved by way of the assertion or not of a set of predicates that
are meant to abstract the specification of the behavior of the target system and thus of the
FTAMs under test. Typical examples of predicates are: {fault_activated}, {fault_activated &
{error_signalled & proper service delivered}. Such predicates or their
combinations define the set of vertices of a graph that models the behavior of the target system
(or of the FTAMs) in the presence of faults. This graph can be either established a priori to
describe anticipated behaviors or obtained a posteriori from the analysis of the R set, which is a
form of model extraction from the experimental results (e.g., see [12]).

Figure

1 gives an example of such a graph. Transition 1 corresponds to the activation of an
injected fault as an error; the associated time defines the fault dormancy. Transition 2
represents the situation where an injected fault is not activated; such an experiment is not
significant when FTAM coverage is evaluated with respect to error patterns (resulting from
activated faults) rather than with respect to the faults injected. Transition 3 depicts the case of a
detected error; the associated time characterizes the latency of error detection. Transition 4
represents the case where an error is apparently tolerated although it was not detected whereas
transition 6 depicts the (normal) situation where the error is tolerated after having been
detected. Transitions 5 and 7 distinguish the cases of failure of the detection and tolerance
mechanisms. This graph depicts the faulty behavior observed during the experiments carried
out on the Delta-4 architecture. In particular, transition 4 characterizes a singular behavior, that
is not always easy to diagnose in practice since it may result from either (i) an activated fault
that remains hidden (latent) or (ii) a propagated error that is tolerated or that is eliminated by
some other - unobserved - mechanism.

Figure

further illustrates the types of predicates and system state transitions that can be
deduced from the readout set R, in the case of a single binary predicate p; three principal cases
are accounted for, depending on whether the predicate is expected (i) to maintain its value for
the whole interval that defines the observation domain for an experiment
(figure 2-a), or (ii) to change value once (figure 2-b) or several times (figure 2-c) during the
experiment.
A typical example of figure 2-a is the case of a reliability or availability predicate
characterizing the continuity of service delivery in the presence of faults (e.g., fault masking):
{ acceptable_results_delivered } and { erroneous_result_delivered }
The testability property, for which an error must be signalled whenever a fault is present, is
a possible example for figure 2-b:
{ error_signalled } and { error_not_signalled } (1)

Figure

2-c provides an example for the test of a fail-safe property defined as:
{ fault_not_activated - error_signalled } and
{ fault_activated - error_not_signalled }
where - and - denote respectively OR and AND connectives.
This corresponds to an alternating behavior between graph vertices v 0 and v 1 that may be
described by the decomposition of the predicate p into two elementary predicates of the types
shown in figure 2-b:
{ fault_activated } and { error_signalled }
where - is the NOT operator.
The observation of the instant of assertion of a predicate characterizes the temporal
performance of the FTAM under test; in particular for the predicate of figure 2-b, relation (1)
can be modified to:
Since relevant timing measurements are related to the instant of fault occurrence, it is simpler to
consider hereafter that the observation domain T is defined by the interval [0, T].
. Definition of Experimental Measures
We only summarize here the major experimental measures that can be derived from a fault
injection test sequence.
Let T p denote the random variable characterizing the instant of assertion of a predicate p
then the cumulative distribution function of the coverage (with respect to predicate p) can be
defined as:
Other related studies (e.g., see [26]) focus on the probability density function of the coverage.
Both approaches are equivalent in principle, however, we advocate the use of the cumulative
function as this facilitates the relationship with analytical models: the asymptotic value simply
tends towards the constant coverage parameters usually used in these models.
Two principal constraints have to be considered in the derivation of experimental measures.
First, it is worth noting that C(t) is usually defective (e.g., see [3]) since all the faults cannot
be properly covered, thus its asymptotic value is less than or equal to one, i.e.:
Also, the observation domain T is bounded and the readouts obtained from the experiments
form a set of so-called Type I (or time) censored data (e.g., see [27], p. 248); the unobserved
times are known only to be above the upper bound T (censoring time) of the observation
domain. The characteristics of the considered target system and especially the temporal
parameters of the FTAMS to be evaluated have a direct impact on the determination of T. The
choice of T relies on a careful analysis of thea prori (partial) information available concerning
the temporal parameters of the FTAMs and may necessitate a set of preliminary experiments for
its proper adjustment.
The combination of these two constraints results in a total uncertainty for the experiments
for which no outcome (predicate assertion) is observed. Indeed, either the assertion would
occur in a finite time beyond T or the assertion is not true for that experiment (which denotes a
coverage deficiency). These implications are further analyzed in the following sub-sections.
Estimation of the Coverage Function
Consider a test sequence of n independent fault injection experiments; in each experiment, a
point in the {FxA} space is randomly selected according to the distribution of occurrences in
{FxA} and the corresponding readouts collected. If t pi denotes the instant of assertion of p
for experiment i, denote the random variable defined by:
{ 1, if assertion p is observed in [0, t]
0, otherwise
The number of assertions of p cumulated within the time interval [0, t] can thus be expressed
as:
and the coverage function C(t) can be simply estimated by:
The asymptotic coverage is estimated by:
Due to the monotonically increasing behavior of C(t) and to the finite restriction of the
observation domain, this estimation is always pessimistic. Furthermore, as C(t) is defective,
another interesting measure corresponds to the conditional coverage expressed as:
{
Prob . { T p -
This experimental conditional coverage refers also to the conditional distributions defined for
the coverage model presented in reference [3].
If T '
designates the random variable characterizing the non-infinite coverage times (non-
infinite instants of assertion of p), then T' p can be described by the following distribution:
that is estimated by:
Estimation of the Mean Coverage Time
The mean coverage time is defined
dC(t). The two constraints
identified previously also complicate the estimation of t; three types of estimators can be
{ e i
{ e i
The first estimator given by expression (10) corresponds to the estimation of the mean of the
coverage times actually observed. It is thus an estimator of E[T' p ], i.e., of the mean of the
conditional coverage time.
The second estimator defined by expression (11) estimates the random variable min(T p, T).
It has been modified to assign a time T (i.e., the upper bound of the observation domain) to
each of the [n - N(T)] experiments for which the assertion of p was not observed.
The third estimator (expression (12)) corresponds to the estimator typically used when dealing
with time-censored exponentially distributed test data (e.g., see [28], pp. 105-106) or with the
estimation of the Mean Time to First Failure (MTFF) [29].
It is worth noting constitutes an "optimistic"
estimation of the mean coverage time. However, the fact that C(t) is defective prevents
conclusions being drawn about the bias induced by the other estimators. We therefore selected
the first estimator.
III. Integration of Experimental Measures of Fault Tolerance with
the Fault Occurrence Process
In this section we first identify the main interactions between analytical dependability
modeling and experimental evaluation. We then present a framework for characterizing the
relationship between the experimental estimates obtained in a fault injection test sequence and
the coverage parameters usually considered to account for FTAM behavior in Markov chain
models. An example is given to illustrate the respective impact on dependability evaluation of
asymptotic coverage and coverage distribution.
A . Bridging the Gap between Analytical Modeling and Fault Injection

Figure

3 depicts the principal phases of analytical dependability evaluation and experimental
dependability evaluation based on fault injection that rely respectively on the construction and
the processing of either axiomatic models (sequence 1-2-4-6), or empirical and physical
models (sequence 1-3-5-7).
Of course, both sequences may be used separately to impact the target system (e.g.,
parameter sensitivity analysis for early architectural design decisions in the case of model-based
evaluation or as a design aid for fault removal in the case of fault injection-based experimental
testing). However, we would like to stress here the benefits that can be obtained from the
interactions between these two sequences. For sake of conciseness, we will emphasize only the
most significant interactions (identified by bold arrows in figure 3).
The transition from 2 to 5 depicts the necessary impact of modeling on the definition of the
readouts in the R set and the determination of the measures in the M set. In particular, one
impact represented by this transition may be that of considering the relative ratios of the
occurrence rates of different fault classes in order to refine the general estimators of the
coverage function given in section II (e.g., see [30] and [31]).
The transition from 7 to 8 identifies two types of interactions:
. impact of models on experiments: the reference to the fault occurrence process, usually
described in axiomatic models, is necessary to derive dependability measures,
. impact of experiments on models, including: estimation of the coverage parameters of
the original models, validation of the assumptions made in the elaboration of these
models and refinement of the structure of the models.
Relevant measures of system dependability can be obtained by processing models thus
supported by experiments. This provides an objective foundation for proposing modifications
to the design and implementation of the target fault-tolerant system.
The interactions induced by transition 7-8 are analyzed further in the next sub-section.
B . Dependability Evaluation
If we assume that the major risk of system failure is that induced by the failure of the
FTAMs in properly processing the first fault occurrence, the reliability expression for a non-
maintained fault-tolerant system can be written as:
where F F (t) and f F (t) are respectively the cumulative distribution and density functions
characterizing the fault occurrence process of the whole target fault-tolerant system and C(t)
designates the cumulative distribution of the FTAM coverage function (see section II). In
particular, the first part of expression (13), 1 - F F (t) expresses the probability that no fault
occurred before t and the last term expresses the probability of survival to the first component
failure.
The derivation of expression (13) is based on the fact that, in a fault-tolerant system, the
risks of failure resulting from exhaustion of redundancy correspond generally to much lower
orders of magnitude than those induced by a coverage deficiency in the FTAMs. This is
especially true when the mission time is small compared to the mean time to fault occurrence. It
should also be pointed out that the reference to the fault occurrence process is by no means a
limiting factor; the extension to the error occurrence process (fault activation) can be simply
achieved by substituting E for F in the indices.
Three major techniques (namely, Monte Carlo simulation, closed-form expressions and
Markov chains) can be considered for implementing the relationship between the fault
occurrence process and the experimental coverage parameters formally expressed by relation
(see [14]). Of these three, Markov chains are especially attractive since they provide a
tractable means to account for the main temporal characteristics of the coverage distribution, as
exemplified in the following sub-sections.
1 . Estimation of the Coverage Parameters of a Markov Chain
Let us consider the model of figure 4-a that describes the behavior of a fault-tolerant
system. This model accounts for the coverage of the FTAMs with respect to the occurrence of a
fault and the possible occurrence of a second (near-coincident [32]) fault while processing the
first one.
As shown in [3], an equivalent Markov representation (figure 4-b) can be derived for such
a behavior where the equivalent coverage C* is defined as:
where the constant parameter C can be identified as the asymptotic value of the coverage
cumulative distribution C(t) (see section II), l* is the rate of occurrence of a near coincident
fault and the E[T d
designates the successive moments of the random variable characterizing
the processing time of the FTAMs.
By limiting expression (14) to the first order and letting the decision rate of
the FTAMs, we obtain the model of figure 4-c. This model provides an essential "building
block" to describe the coverage process, in particular for studying the impact of the temporal
distribution.
Although the truncation of the observation domain leads to a conservative estimation of the
asymptotic coverage (see expression (6)), the estimation of the distribution of T d is in practice
more complex. Basically, the distribution of T d can be related to the distribution of the random
variable T '
characterizing the non-infinite coverage times (see expression (10)) which is in
turn related to the random variable T p characterizing the coverage process (i.e., the assertion of
predicate p) by:
assertion of p in [0,t] }
Prob.{ assertion of p in [0,t] | assertion of p in [0,-[ }
Prob.{ assertion of p in [0,-[ }
Accordingly, E[T d thus expression (14) can be simply expressed as:
and E[T p ] can then be (under-)estimated by the estimator given in expression (10).
. Impact of the Time Distribution of the Fault Tolerance Process
In order to study this impact, we consider as an example the case of a duplex architecture
featuring (i) self-checking units whose coverage is characterized by an asymptotic coverage C
and a mean decision time denoted by 1/n and (ii) a procedure for cross-checking both units
- with perfect coverage - and whose timing is characterized by the activation process that is
common to both units; let a denote the associated rate. Figure 5 describes the considered
model and defines the model parameters as well as the meaning of the states. This model
corresponds to the basic model used in the safety and availability evaluation of the potential
architectures for the computerized interlocking of the French National Railways [33].
The analysis of the failure states explicitly distinguishes whether or not an error was
detected. Accordingly, state 3, although unreliable since the service delivery has been
interrupted during the repair action that follows the detection of an error, can be considered as a
safe state (benign failure); therefore, only states 4 and 6 are catastrophic failure states. State 5
represents the system after a second failure but before (re-)activation of the system. Its positive
effect on system dependability is usually very slight (since a >> l) and can be neglected (by
merging it into state 6).
For the evaluation, we use the equivalent catastrophic failure rate (denoted G) associated
with the absorbing states 4 and 6. The strong connectivity property of the graph consisting of
the non-absorbing states as well as the very small values that are usual for the model parameter
ratios l/a and l/n ensure that the absorption process is asymptotically a homogeneous Poisson
process and that the associated equivalent failure rate G is given by (e.g., see [34],
pp.
paths from
initial state (I) to
failed state(s)


transition rates of the considered path
s t a t es i n pa t h
output rates of the considered state
Application of (17) to the model of figure 5, and some algebraic manipulations lead to the
following normalized failure rate:
G
l
l
a
l
a (C -
l
l
l
a
l 2
Expression (18) reveals the prominent role of the asymptotic non-coverage of the self-checking
mechanisms (C - ), or by the activation rate (a), according to the value of the ratio l/n
(with respect to C
- ). It is worth noting that this ratio corresponds to the normalized mean
decision time (1/n) - with respect to the MTFF of one unit (i.e., 1/l). These results extend
and refine the results usually found in the existing literature, which are mainly restricted to the
influence of the asymptotic coverage. It is also worth noting that the ratio obtained when
inverting expression corresponds to the ratio of the MTFF procured by the redundant
duplex architecture (i.e., MTFFduplex - 1/G) over the MTFF of one unit
1/l). This is illustrated by the curves shown in figure 6 that plot the gain in MTFF procured
by the redundant duplex architecture as a function of the ratio l/n. Figure 6-a illustrates the
impact of the lack of coverage (C - ), while figure 6-b illustrates the influence of the activation
rate through the normalized mean activation time (l/a).
The curves provide useful insight about the domains where the impact of the FTAM
coverage time distribution is significant. The variations observed explicitly show that, for the
usual orders of magnitudes of the ratio l/n, i.e., l/n << 1, the impact of the asymptotic
coverage is the most prominent. This clearly indicates that, in the experimental evaluation,
specific attention should be paid to the estimation of asymptotic coverages.
IV . Example of Fault Injection-Based Dependability Evaluation
This section illustrates the concepts set forth in the previous sections by applying them to
the Delta-4 distributed fault-tolerant architecture. The reader interested by the Delta-4
architecture can refer to [35] and [36]. Two issues are considered here:
. model construction, exemplified by the description of a typical experimental graph,
. calibration of coverage parameters for the evaluation of dependability measures.
A . Experimental Graph
The target system considered for the experimental validation of the Delta-4 architecture is
made up of a local area network of 4 nodes. Each node is composed of a host computer and of
a Network Attachment Controller (NAC). The NAC features hardware self-checking
mechanisms specifically designed to ensure a fail-silent behavior (by provoking the extraction
of a faulty node from the network). Tolerance of faults at the host computer level is achieved
through data and code replication and a variety of alternate mechanisms of which the basic
building block is an Atomic Multicast protocol (AMp) also implemented in the NAC.
The fault injection test sequence was aimed at testing the hardware self-checking
mechanisms implemented in the NACs as well as the behavior of the AMp software in the
presence of hardware faults. Faults were injected in the NAC of a single node (the faulty node)
that was monitored to assess the efficiency of its hardware self-checking mechanisms.
Successful hardware error-detection (resulting in node extraction) is characterized by a
predicate D. The resulting behavior of the non-injected nodes (the non-faulty nodes) was also
observed to assess the efficiency of the AMp mechanisms in tolerating the faults at the
communication level. Correct operation of AMp is specified in terms of atomicity, order and
group membership properties that are globally characterized by a predicate T.
To carry out the test sequence, a general distributed testbed, featuring automatic control and
sequencing of the experiments, as well as reset and recovery of the crashed nodes, was built
around the fault injection tool MESSALINE [24]. This enabled us to carry out extensive fault
injection experiments (almost 20000 experiments of about 5-minute duration each) on a
prototype of the Delta-4 architecture.
Faults in the F set were injected by forcing "zero" or "one" levels on the pins (up to 3 pins
simultaneously) - and thus on the connected equipotential lines - of 86 ICs on the NAC
board. To account for the most likely faults, the injected faults were mainly intermittent faults,
but transient as well as permanent faults were also injected. Activation of the target system (the
A set) consisted of two types of traffic exchanged among the nodes with various traffic profiles
that ensured different activation modes for the injected node. Further details on the testing
environment can be found in [37].
The experimental results obtained proved very useful in building a relevant model of fault
tolerance behavior. Figure 7 gives an example of values obtained for a typical experimental
graph, which in fact corresponds to the predicate graph discussed earlier (figure 1).
The percentages indicate the values of asymptotic coverage for the predicates E (error), D
(hardware error detection) and T (tolerance by the communication protocol). The time
measures indicate the mean values of the fault dormancy and error detection latency
distributions; only asymptotic coverage is considered with respect to the T predicate since such
a predicate is of the type described in figure 2-a.
The main feature of this graph concerns the inclusion of transitions that might have been
omitted from an a priori model of system behavior and thus also from the evaluation of the
associated probabilities; two such transitions exist, which are related to (i) the identification of
the injected faults that were not activated as errors, and (ii) the inclusion of a transition
between states E and T accounting for injected faults that were actually activated as errors but
were apparently tolerated without being detected.
The first transition represents the experiments that are non-significant (i.e., experiments that
cannot activate the tested FTAMs); relevant error-based coverage estimates can be obtained by
processing only the readouts of the significant experiments. The results show that, thanks to
the large proportion of intermittent faults injected and to the variety of activation modes applied,
a very large proportion of experiments (i.e., 93 %) were significant ones since the injected
faults were actually activated as errors; this information was obtained by means of current
sensors attached to each fault-injection device.
The T predicate coverage can be estimated more conservatively when the percentage associated
with the second transition (E to T) is taken (pessimistically) to represent experiments that
terminate with errors that have remained latent but could eventually lead to failure.
An experimental graph such as this, together with the experimental values obtained, serve as
the basis for the system-level dependability evaluation sketched out in the next sub-section.
. Evaluation of Dependability Measures
To relate the dependability evaluation to the experiments that were carried out, we consider a
system made up of 4 nodes, as in the case of the target system used for the fault injection test
sequence. Such an architecture may for example correspond to the case of a system
requirement for triplex task execution with a 4th node as a back-up in order to tolerate 2
consecutive faults.

Figure

8 shows the Markov model that describes the behavior of this architecture. A
proportion h of the total node failure rate is considered to be that of the host computer, the
remaining (1-h) that of the NAC.
In the model, parameter CT accounts only for the asymptotic coverage associated with the
tolerance predicate T of the NACs (see figure 7); as a high coverage majority voting decision
is applied to the results of task replicas running on the host computers, the coverage of the
faults in the host computers is considered here as perfect. The rate at which task replicas
exchange results for voting is considered to be much greater than the mean time to node failure
(1/l). Consequently, the host and the NAC fault-tolerance processes (activated respectively by
the exchange of results for majority voting and execution of the underlying AMp protocol) are
considered as instantaneous in comparison with the other model parameters. Therefore, this
model contains no parameters analogous to the a and n parameters of figure 5.
The experiments that were carried out clearly revealed cases of non-confinement of errors
(i.e., some injected faults not only resulted in the fact that the faulty node did extract from the
rest of the network, but also provoked the extraction of several non-faulty nodes). The
multiplicity of such multiple node extractions impacts the dependability behavior of the system;
therefore, the model includes parameters C
T,i to account for the undesired extraction of i non-faulty
nodes.
The model assumes that it is possible to tolerate up to two simultaneous extractions.
Although this assumption is valid for the redundant configuration considered here and it has
been possible to obtain these figures in the case of our 4-node testbed, this might not be true in
practice for more complex configurations. This model can thus be considered as leading to an
(optimistic) upper bound for dependability evaluation. It is also interesting to account for the
(pessimistic) case when any multiple extraction results in total network failure. In practice, this
can be achieved by simply transferring the rate associated with transition 1-3 to transition 1-4
on the model of figure 8.
The equivalent failure rate of the system described by the model of figure 8, normalized
with respect to the failure rate of a single node, is:
G
MTFFnode
l
l
l
l
l
l
l
When considering the more restrictive assumption, then the equivalent failure rate becomes:
G
MTFFnode
l
l
l
l
l
For the analysis, we consider the results obtained during the experiments concerning two
distinct versions of the NAC hardware architecture: a NAC with only limited self-checking
capabilities (LSC NAC) and a NAC featuring enhanced self-checking capabilities provided by
a duplex architecture (ESC NAC). The fault injection experiments that were carried out - in
particular on the LSC NAC (featuring a lower coverage) - had a significant impact in the
debugging of the AMp software and several releases of the AMp software (denoted AMp Vx.y)
were therefore tested. The table of figure 9 summarizes the experimental measures considered
for the analysis. More details on the experimental results can be found in [38] and [39].
The results obtained for the ESC NAC - AMp V2.5 configuration show a very appreciable
improvement in the coverage. Out of the 4019 significant experiments that were carried out,
only faults were not tolerated; no non-confinement of multiplicity 2 was observed. To
provide a more objective estimation for this configuration, we have therefore considered
confidence intervals for the coverage estimations. The percentages in bold characters give the
nominal estimates; the figures in italics correspond to the upper and lower confidence limits for
a 95 % confidence level. Confidence intervals are not considered for the other configurations
as their impact would be negligible due to the relatively low coverage values.

Figure

compares the ranges of variations observed on the dependability gain measure
for the configurations considered and for both optimistic and pessimistic assumptions.
The upper and lower bounds that define the areas shown for each configuration are obtained
respectively from expressions (19) and (20) when considering the nominal coverage
percentages of figure 9; they can thus be considered as nominal bounds. Note that the areas
associated with configurations LSC NAC - AMp V2 and LSC NAC - AMp V2.3 overlap.
The confidence limits for the coverage of configuration ESC NAC - AMp V 2.5 enable
confidence limits to be obtained for these bounds; these limits appear as dotted lines. Note that
the lower limit of the upper bound and the upper limit of the lower bound almost coincide.
The best nominal upper and lower bounds obtained for configuration ESC NAC -
2.5 indicate an MTFF improvement factor of 2000 and 500, respectively. However,
the limits shown for each bound indicate how the uncertainty in the estimation of the coverages
may affect these dependability predictions. As could be expected, the influence is stronger for
the upper bound; the lower/upper limits are respectively 800/4000 for the upper bound and
400/800 for the lower bound. This shows that, even in the most conservative case, the Delta-4
architecture still provides a substantial dependability improvement.

Figure

shows that the ESC NAC - AMp V2.5 combination provides almost one order of
magnitude gain over the best results obtained for the LSC NAC architecture. This improvement
can be attributed mainly to the improved self-checking mechanisms of the ESC NAC
architecture rather than the change in AMp version since some partial tests using version 2.5 of
AMp software on the LSC NAC were carried out and it was observed that there was no
significant modification with respect to those obtained for version 2.3.
It should be pointed out that the curves shown here have been plotted for
is, the proportion of node failure rate associated to the host computer. Although it is clear from
expressions (19) and (20) that parameter h impacts the absolute value of the gain, the
sensitivity analysis with respect to h carried out in [37] has shown that for h - 95 % (which
covers the most realistic values of the ratio of host and NAC failure rates), the relative impact
of the software and hardware modifications of the architecture shown in figure 10 is not
significantly changed.
. Conclusion
The dependability evaluation of complex fault-tolerant systems requires a combination of
both experimental and analytical methods. This issue has been addressed by proposing a
framework that establishes the link between the experimental evaluation of the coverage of the
fault tolerance process and the fault occurrence process.
By investigating the relationships between the time distributions of the fault occurrence and
coverage processes, we were able to show how it is possible to identify the relative domains
where the time distribution has an impact on dependability measures.
The examples given clearly illustrate how the main interactions between model-based
evaluation and experimental evaluation - namely, model characterization and coverage
parameter calibration - fit within this framework and can be applied in practice.
The insights gained from the combined fault injection and dependability analysis carried out
were regarded by the industrial partners of the Delta-4 project as providing very valuable aids
in improving the designs and in making architectural decisions concerning the fault tolerance
algorithms and mechanisms.
However, much work remains to be carried out towards the incorporation of fault injection
at the various stages of the development and validation process of fault-tolerant systems. The
results reported in this paper constitute only one facet of the work we are carrying out towards
this goal. Other investigations include:
. the use of fault simulation as a complement to physical fault injection on a fault tolerant
system prototype,
. the identification of specific input patterns aimed at distinguishing the various error/fault
processing actions of the fault tolerance algorithms and mechanisms so that they can be
adequately and efficiently verified,
. the clustering of the experimental results in order to refine the computation of the
coverage estimators by accounting for significant differences in the operational fault
occurrence rates associated with these clusters.

Acknowledgement

We would like to thank Eliane Martins, Jean-Charles Fabre and Martine Agu-ra at LAAS
for their significant contribution in designing and setting up the fault injection testbed. The
technical support from Bull and Ferranti and the feedback for refining the analysis of the
experimental results received from Marc Ch-r-que and Ren- Ribot (Bull SA, France) and
Nigel Howard (Ferranti International plc, UK), are also gratefully acknowledged. The authors
are also grateful to the anonymous referees for providing helpful comments that greatly helped
in improving the presentation of the paper.



--R

"Design and Evaluation Tools for Fault-Tolerant Systems"
"Reliability Modeling Techniques for Self-Repairing Computer Systems"
"Coverage Modeling for Dependability Analysis of Fault-Tolerant Systems"
"Failure Mode Assumptions and Assumption Coverage"
"Measurements of Fault Detection Mechanisms Efficiency: Results"
"Fault Detection, Isolation and Reconfiguration in FTMP: Methods and Experimental Results"
Injection based Automated Testing Environment"
Experimental Evaluation of Error-Detection and Self-Checking Coverage of Components of a Distributed Real-time System
"Understanding Large System Failures - A Fault Injection Experiment"
"Evaluation of Error Detection Schemes using Fault Injection by Heavy-ion Radiation"
"Effect of Transient Gate-Level Faults on Program Behavior"
"A Fault Behavior Model for an Avionic Microprocessor : A Case Study"
"FERRARI: A Tool for the Validation of System Dependability Properties"
"Fault Injection for the Experimental Validation of Fault Tolerance"
"Dependable Computing and Fault Tolerance: Concepts and Terminology"
Dependability: Basic Concepts and Terminology
"Evaluation of Deterministic Fault Injection for Fault-Tolerant Protocol Testing"
"Fault Injection for the Formal Testing of Fault Tolerance"
"Methodology for Measurement of Fault Latency in a Digital Avionic Miniprocessor"
The Theory and Practice of Reliable System Design
"Evaluation and Design of an Ultra-Reliable Distributed Architecture for Fault Tolerance"
Dependability Evaluation Report LA3 - Architecture Validation
"Impact of Correlated Failures on Dependability in a VAXcluster System"
"Fault Injection for Dependability Validation - A Methodology and Some Applications"
Dependability Validation by Fault Injection: Method
"Modeling Recovery Time Distributions in Ultrareliable Fault-Tolerant Systems"
Applied Life Data Analysis
Statistical Models and Methods for Lifetime Data
"Fast Simulation of Dependability Models with General Failure, Repair and Maintenance Processes"
"Some Past Experiments and Future Plans in Experimental Evaluations of fault Tolerance"
Validation of Distributed Systems by Fault Injection
"Effects of Near-Coincident Faults in Multiprocessor Systems"
"On the Dependability Evaluation of High Safety Systems"
System Reliability
"The Delta-4 Approach to Dependability in Open Distributed Computing Systems"

"Experimental Evaluation of the Fault Tolerance of an Atomic Multicast Protocol"
Dependability Testing Report LA2 - Fault-Injection on the Fail-Silent NAC: Preliminary Results
Dependability Testing Report LA3 - Fault-Injection on the Extended Self-Checking NAC
--TR
Coverage Modeling for Dependability Analysis of Fault-Tolerant Systems
Fault Injection for Dependability Validation
Four
Reliability modeling techniques for self-repairing computer systems

--CTR
Chen Fu , Ana Milanova , Barbara Gershon Ryder , David G. Wonnacott, Robustness Testing of Java Server Applications, IEEE Transactions on Software Engineering, v.31 n.4, p.292-311, April 2005
Chen Fu , Barbara G. Ryder , Ana Milanova , David Wonnacott, Testing of java web services for robustness, ACM SIGSOFT Software Engineering Notes, v.29 n.4, July 2004
A. Steininger , C. Scherrer, Identifying Efficient Combinations of Error Detection Mechanisms Based on Results of Fault Injection Experiments, IEEE Transactions on Computers, v.51 n.2, p.235-239, February 2002
Michel Cukier , David Powell , Jean Arlat, Coverage Estimation Methods for Stratified Fault-Injection, IEEE Transactions on Computers, v.48 n.7, p.707-723, July 1999
D. Powell , J. Arlat , L. Beus-Dukic , A. Bondavalli , P. Coppola , A. Fantechi , E. Jenn , C. Rabjac , A. Wellings, GUARDS: A Generic Upgradable Architecture for Real-Time Dependable Systems, IEEE Transactions on Parallel and Distributed Systems, v.10 n.6, p.580-599, June 1999
Timothy K. Tsai , Mei-Chen Hsueh , Hong Zhao , Zbigniew Kalbarczyk , Ravishankar K. Iyer, Stress-Based and Path-Based Fault Injection, IEEE Transactions on Computers, v.48 n.11, p.1183-1201, November 1999
Guillermo A. Alvarez , Flaviu Cristian, Simulation-based Testing of Communication Protocols for Dependable Embedded Systems, The Journal of Supercomputing, v.16 n.1-2, p.93-116, May 2000
David Powell , Eliane Martins , Jean Arlat , Yves Crouzet, Estimators for Fault Tolerance Coverage Evaluation, IEEE Transactions on Computers, v.44 n.2, p.261-274, February 1995
Andrea Bondavalli , Alessandro Fantechi , Diego Latella , Luca Simoncini, Design Validation of Embedded Dependable Systems, IEEE Micro, v.21 n.5, p.52-62, September 2001
Xubin He , Ming Zhang , Qing (Ken) Yang, SPEK: A Storage Performance Evaluation Kernel Module for Block-Level Storage Systems under Faulty Conditions, IEEE Transactions on Dependable and Secure Computing, v.2 n.2, p.138-149, April 2005
J. C. Baraza , J. Gracia , D. Gil , P. J. Gil, A prototype of a VHDL-based fault injection tool: description and application, Journal of Systems Architecture: the EUROMICRO Journal, v.47 n.10, p.847-867, April 2002
Jean Arlat , Yves Crouzet , Johan Karlsson , Peter Folkesson , Emmerich Fuchs , Gnther H. Leber, Comparison of Physical and Software-Implemented Fault Injection Techniques, IEEE Transactions on Computers, v.52 n.9, p.1115-1133, September
dependability measures;distributed fault-tolerant architecture;fault injection;dependability evaluation;distributed processing;fault occurrence process;test sequence;Esprit Delta-4 Project;fault-tolerant systems;fault tolerance process;fault tolerant computing