Aims
To understand the factors which affect the reliability of a system, we
introduce how software and hardware design faults can be tolerated
We look at:
- Safety and Dependability
- Reliability, failure and faults
- Failure modes
- Fault prevention and fault tolerance
- N-Version programming
- Dynamic Redundancy
Safety and Reliability
- Safety: freedom from those conditions that can cause death, injury,
occupational illness, damage to (or loss of) equipment (or property),
or environmental harm - By this definition, most systems which have an element of risk associated with
their use, as unsafe - Reliability: a measure of the success with which a system conforms to
some authoritative specification of its behavior
Safety is the probability that conditions that can lead to mishaps do not
occur whether or not the intended function is performed
Safety
E.g., measures which increase the likelihood of a
weapon firing when required may well increase
the possibility of its accidental detonation
* In many ways, the only safe airplane is one that
never takes off, however, it is not very reliable
* As with reliability, to ensure the safety
requirements of an embedded system, system
safety analysis must be performed throughout
all stages of its life cycle development
4
Reliability, Failure and Faults
- The reliability of a system is a measure of the success with which it conforms to an
authoritative specification of its behaviour - When the behaviour of a system deviates from that which is specified for it, this is called
a failure - Failures result from unexpected problems internal to the system that eventually manifest
themselves in the system’s external behaviour - These problems are called errors and their mechanical or algorithmic cause are termed
faults - Systems are composed of components which are themselves systems; hence
- > fault -> error -> failure -> fault
Fault Types
- A transient fault starts at a particular time, remains in the system
for some period and then disappears - E.g. hardware components which have an adverse reaction to
radioactivity - Many faults in communication systems are transient
- Permanent faults remain in the system until they are repaired; e.g.,
a broken wire or a software design error - Intermittent faults are transient faults that occur from time to time
- E.g. a hardware component that is heat sensitive, it works for a
time, stops working, cools down and then starts to work again
Software Faults
- Called Bugs
- Bohrbugs: reproducible identifiable.
- Heisenbugs: only active under rare
conditions: e.g. race conditions - Software doesn’t deteriorate with age: it is
either correct or incorrect, but faults can remain
dormant for long periods usually related to
resource usage e.g. memory leaks
Effect of failure in the US Patriot Missile system
Failure modes
fig 1 & fig 2
Approaches to Achieving Reliable Systems
- Fault prevention attempts to eliminate any possibility of faults
creeping into a system before it goes operational - Fault tolerance enables a system to continue functioning even in the
presence of faults
Both approaches attempt to produces systems which have
well-defined failure modes
Fault Prevention
Two stages: fault avoidance and fault removal
* Fault avoidance attempts to limit the introduction of faults during system
construction by:
1. use of the most reliable components within the given cost and performance
constraints
2. use of thoroughly-refined techniques for interconnection of components
and assembly of subsystems
3. use of proven design methodologies
4. use of languages with facilities for data abstraction and modularity
5. use of software engineering environments to help manipulate software
components and thereby manage complexity
Fault Removal
Design errors (hardware and software) will exist
* Fault removal: procedures for finding and removing the causes of errors;
- e.g. design reviews, program verification, code inspections and system testing
* System testing can never be exhaustive and remove all potential faults
- A test can only be used to show the presence of faults, not their absence
- It is sometimes impossible to test under realistic conditions
- Most tests are done with the system in simulation mode and it is difficult to guarantee that the simulation is
accurate
- Requirements errors during the system’s development may not manifest themselves until the system goes
operational
Failure of Fault Prevention Approach
- In spite of all the testing and verification techniques, hardware
components will fail; the fault prevention approach will therefore be
unsuccessful when
1. either the frequency or duration of repair times are unacceptable, or
2. the system is inaccessible for maintenance and repair activities. An extreme
example of the latter is the crewless spacecraft Voyager (currently 10 billions
miles from the sun!) - Alternative is Fault Tolerance
Levels of Fault Tolerance
- Full Fault Tolerance — the system continues to operate in the presence of
faults, albeit for a limited period, with no significant loss of functionality or
performance - Graceful Degradation (fail soft) — the system continues to operate in the
presence of errors, accepting a partial degradation of functionality or
performance during recovery or repair - Fail Safe — the system maintains its integrity while accepting a temporary
halt in its operation
The level required will depend on the application. Most safety critical systems
require full fault tolerance, however in practice many settle for graceful
degradation
Graceful Degradation in an Air Traffic Control System & Redundancy
- All fault-tolerant techniques rely on extra elements introduced into
the system to detect & recover from faults - Components are redundant as they are not required in a perfect system
- Often called protective redundancy
- Aim: minimise redundancy while maximising reliability, subject to the
cost and size constraints of the system - Warning: the added components inevitably increase the complexity of the overall system
- This itself can lead to less reliable systems
- E.g., first launch of the space shuttle
- It is advisable to separate out the fault-tolerant components from the
rest of the system
Hardware Fault Tolerance
*Two types: static (or masking) and dynamic redundancy
* Static: redundant components are used inside a system to hide the
effects of faults; e.g. Triple Modular Redundancy (TMR)
- TMR — 3 identical subcomponents and majority voting circuits; the outputs are compared and
if one differs from the other two, that output is masked out
- Assumes the fault is not common (such as a design error) but is either transient or due to
component deterioration
- To mask faults from more than one component requires NMR
* Dynamic: redundancy supplied inside a component which indicates
that the output is in error; provides an error detection facility;
recovery must be provided by another component
- E.g. communications checksums and memory parity bits
Software Fault Tolerance
- Used for detecting design errors
- Static — N-Version programming
- Dynamic
- Detection and Recovery
- Recovery blocks: backward error recovery
- Exceptions: forward error recovery
N-Version Programming
Design diversity
* The independent generation of N (N > 2) functionally equivalent
programs from the same initial specification
No interactions between groups
* The programs execute concurrently with the same inputs and their
results are compared by a driver process
* The results (VOTES) should be identical, if different the consensus
result, assuming there is one, is taken to be correct
+ N-version programming
Vote Comparison
- To what extent can votes be compared?
- Text or integer arithmetic will produce identical results
- Real numbers => different values
- Need inexact voting techniques
Consistent Comparison Problem
Fig 1
Each version will produce a
different but correct result
Even if inexact comparison
techniques are used, the problem
occurs
N-version programming depends on
- Initial specification — The majority of software faults stem from inadequate specification
- This will manifest itself in all N versions of the implementation
- Independence of effort — Experiments produce conflicting results
- Complex parts of a specification leads to a lack of understanding of the requirements
- If these also refer to rarely occurring input data, common design errors may not be caught
during system testing - Adequate budget — The predominant cost is software.
- A 3-version system will triple the budget requirement and cause problems of maintenance
- Would a more reliable system be produced if the resources potentially available for
constructing an N-versions were instead used to produce a single version?
Error Detection
- Environmental detection
- hardware — e.g. illegal instruction
- O.S/RTS — null pointer
- Application detection
- Replication checks
- Timing checks (e.g., watch dog)
- Reversal checks
- Coding checks (redundant data, e.g. checksums)
- Reasonableness checks (e.g. assertion)
- Structural checks (e.g. redundant pointers in linked list)
- Dynamic reasonableness check
Software Dynamic Redundancy
Software Dynamic Redundancy
24
Alternative to static redundancy: four phases
* error detection — no fault tolerance scheme can be utilised until the
associated error is detected
* damage confinement and assessment — to what extent has the
system been corrupted?
- The delay between a fault occurring and the detection of the error means
erroneous information could have spread throughout the system
* error recovery — techniques should aim to transform the corrupted
system into a state from which it can continue its normal operation
(perhaps with degraded functionality)
* fault treatment and continued service — an error is a symptom of a
fault; although the damage is repaired, the fault may still exist
Damage Confinement and Assessment
- Damage assessment is closely related to damage confinement
techniques used - Damage confinement is concerned with structuring the system so as
to minimise the damage caused by a faulty component (also known
as firewalling) - Modular decomposition provides static damage confinement; allows
data to flow through well-define pathways (assuming strongly type
language) - Atomic actions provides dynamic damage confinement; they are used
to move the system from one consistent state to another
Error Recovery
- Probably the most important phase of any fault-tolerance technique
- Two approaches: forward and backward
- Forward error recovery continues from an erroneous state by making
selective corrections to the system state - This includes making safe the controlled environment which may be
hazardous or damaged because of the failure - It is system specific and depends on accurate predictions of the location and
cause of errors (i.e, damage assessment) - Examples: redundant pointers in data structures and the use of self-correcting
codes such as Hamming Codes
Backward Error Recovery (BER)
- BER relies on restoring the system to a previous safe state and
executing an alternative section of the program - This has the same functionality but uses a different algorithm (c.f. N-
Version Programming) and therefore no fault - The point to which a process is restored is called a recovery point and
the act of establishing it is termed checkpointing (saving appropriate
system state) - Advantage: the erroneous state is cleared and it does not rely on
finding the location or cause of the fault - BER can, therefore, be used to recover from unanticipated faults
including design errors - Disadvantage: it cannot undo errors in the environment!
