Sûreté de fonctionnement

des systèmes informatiques

industriels
Jean-Charles Fabre
Méthodes et techniques permettant de considérer les fautes
comme des événements naturels et prévisibles!
Tel: 05 61 33 62 36 - Fax: 05 61 33 64 11 - E-mail: fabre@[Link]
Plan
• Concepts de base Delta4
— Définitions et notions de base (attributs, ! Systèmes répartis
entraves), Μk T-R
— Moyens (prévention, tolérance, élimination, ! Systèmes embarqués
prévision) et mesures Airbus A3*, B777
! Avionique
• Techniques de tolérance aux fautes Elektra
— Hypothèses de fautes, ! Ferroviaire
— Techniques de base, stratégies de réplication Nucléaire
— Solutions architecturales et exemples ! contrôle de procédé
• Techniques de caractérisation Ballista
— Injection de fautes (principes, techniques) ! Unix
— Analyse de robustesse, modes de défaillance Mafalda
— Exemples d'outils et de résultats
! Μk T-R
expérimentaux CoFFEE
! Corba
• Synthèse et conclusion.
Introduction aux concepts de base
et aux moyens
Généralités,
Définitions et notions de base (attributs, entraves),
Moyens (prévention, tolérance, élimination, prévision)
et mesures
B-1
Généralités
• Les systèmes industriels sont complexes et donc soumis à des
entraves de fonctionnement d’origine
— Physique, par exemple court circuit
— Logicielle, faute de programmation
• Deux approches:
— Zéro-défaut : qualité des processus de production des matériels et
des logiciels permettant de réaliser des composants parfaits
— Sûreté de fonctionnement:
» Les erreurs sont considérées comme des événements naturels et
inévitables dans les systèmes complexes
» L’objectif est de mettre en place des méthodes et des techniques
permettant de:
- Minimiser leur présence
- Tolérer leur occurrence
- Mesurer l’efficacité des techniques utilisées
B-2
 Concepts
• Définition: Propriété d’un système informatique permettant à ses
utilisateurs de placer une confiance justifiée dans le
service qu’il leur délivre
• Attributs:
— Disponibilité:
» Capacité d’un système à être prêt à l’utilisation
— Fiabilité:
» Capacité d’un système à assurer la continuité de service
— Sécurité
» Innocuité: non-occurrence de défaillances catastrophiques
» Confidentialité: non-occurrence de divulgation non autorisée de
l’information
— Intégrité:
» Non-occurrence d’altération inappropriée de l’information
— Maintenabilité
» Capacité d’effectuer des réparations et des évolutions
• Quantités mesurables
— Disponibilité : moyenne du bon fonctionnement (Tok/Ttotal)
— Fiabilité: Sachant que le système est ok à T0, ProbOK(T0+δt)
B-3
Concepts
SURETE DE FONCTIONNEMENT
PROPRIETE D'UN SYSTEME TELLE QUE SES UTILISATEURS PUISSENT PLACER
UNE CONFIANCE JUSTIFIEE DANS LE SERVICE QU'IL LEUR DELIVRE
Prêt à Continuité Absence Absence Absence Aptitude aux
l'utilisation de service de conséquences de divulgations d'altérations réparations
catastrophiques non-autorisées inappropriées de et aux
pour de l'information l'information évolutions
l'environnement
DISPONIBILITE FIABILITE SECURITE- CONFIDENTIALITE INTEGRITE MAINTENABILITE
INNOCUITE
SECURITE-CONFIDENTIALITE B-4
 Entraves et causalité
• Entraves
— défaillance:
» déviation du service délivré par rapport aux spécifications
— erreur:
» Partie du système susceptible de conduire à une défaillance
— faute:
» Cause adjugée ou supposée d’un erreur
• Chaîne causale faute-erreur-défaillance
Faute ➱ Erreur ➱ Défaillance
Origine Etat Service
• Modèle récursif:
... Défaillance ➠ Faute ➠ Erreur ➠ Défaillance ➠ Faute...
— Lorsque le système est composé de plusieurs composants, la
défaillance d’un composant due à une faute interne, est une faute
externe pour un autre composant avec lequel il interagit.
B-5
Entraves à la SdF
DEVIATION DU SERVICE DELIVRE DE
L'ACCOMPLISSEMENT DE LA FONCTION DU SYSTEME DEFAILLANCE
DEVIATION DE LA SERVICE CONFORME A PROPAGATION
CONFORMITE LA
A LA SPECIFICATION, MAIS
SPECIFICATION INACCEPTABLE
PARTIE DE L'ETAT DU SYSTEME SUSCEPTIBLE
D'ENTRAINER UNE DEFAILLANCE ERREUR
ACTIVATION (INTERNE) OU
OCCURRENCE (EXTERNE)
CAUSE SUPPOSEE OU ADJUGEE D'UNE ERREUR FAUTE
ERREUR : MANIFESTATION FAUTE DANS SYSTEME
DEFAILLANCE : MANIFESTATION ERREUR SUR SERVICE
B-6
 Des entraves… aux méthodes
… Défaillances ➙ Fautes ➙ Erreurs ➙ Défaillances ➙ Fautes …
Disponibilité Fiabilité Sécurité- Integrité Confidentialité Maintenabilité
innocuité
Prévention Tolérance Elimination Prévision
de fautes aux fautes des fautes des fautes
B-7
Méthodes
• Le développement d’un système sûr de fonctionnement passe par
l’utilisation combinée d’un ensemble de méthodes qui peuvent
être classées en :
— prévention de fautes : Techniques de genie logiciel
» comment empêcher l’occurrence ou l’introduction de fautes ;
— tolérance aux fautes : Techniques de redondance
» comment fournir un service à même de remplir la fonction du système
en dépit des fautes ;
— élimination des fautes : Techniques de test, injection de fautes
» comment réduire la présence (nombre, sévérité) des fautes ;
— prévision des fautes : Techniques de modélisation, évaluation
» comment estimer la présence, la création et les conséquences des
fautes.
B-8
 Sûreté de fonctionnement
• Entraves à la sûreté de fonctionnement :
» fautes, erreurs, défaillances ; elles sont les circonstances indésirables;
• Moyens pour la sûreté de fonctionnement :
» prévention de fautes,
» tolérance aux fautes,
» élimination des fautes,
» prévision des fautes ;
Il s’agit des méthodes et techniques permettant de fournir au
système l’aptitude à délivrer un service conforme à
l’accomplissement de sa fonction, et de donner confiance dans
cette aptitude ;
• Attributs de la sûreté de fonctionnement :
— disponibilité, fiabilité, sécurité_innocuité, confidentialité, intégrité,
maintenabilité ;
— ils permettent a) d’exprimer les propriétés qui sont attendues du
système, et b) d’apprécier la qualité du service délivré, telle que
résultant des entraves et des moyens de s’y opposer.
B-9
Arbre de la SdF
DISPONIBILITÉ
FIABILITÉ
SÉCURITÉ - INNOCUITÉ
ATTRIBUTS
CONFIDENTIALITÉ
INTÉGRITÉ
MAINTENABILITÉ
PRÉVENTION DE FAUTES
TOLÉRANCE AUX FAUTES
SÛRETÉ DE MOYENS
FONCTIONNEMENT ÉLIMINATION DES FAUTES
PRÉVISION DES FAUTES
FAUTES
ENTRAVES ERREURS
DÉFAILLANCES
B-10
 A
T DISPONIBILITE / FIABILITE
T
SECURITE - INNOCUITE
R
I CONFIDENTIALITE
B
U INTEGRITE
T MAINTENABILITE
S
S PREVENTION
U DE FAUTES
R Détection
E Traitement
T d'erreurs Diagnostic Reprise
E Recouvrement Poursuite
TOLERANCE
Compensation
D AUX FAUTES
Diagnostic
E Traitement
Passivation
M de fautes
F O Reconfiguration
O Y
N E Analyse statique
C N Statique
S Preuve
T
Vérification Exécution Symbolique
I
O Conformité / Recherche de fautes
ELIMINATION Dynamique
N Fonctionnel / Structurel
N DES FAUTES Diagnostic Test
E Basé fautes / Basé critères
Modification Déterministe / Aléatoire
M
E Evaluation
N Ordinale
PREVISION
T DES FAUTES Evaluation Modélisation / Test
Probabiliste Fiabilité stabilisée / Fiabilité évolutive
Physiques / Dues à l'homme
Accidentelles / Intentionelles non-malveillantes / Malveillantes
E FAUTES De développement / Opérationelles
N Internes / Externes
T Permanentes / Temporaires
R ERREURS
A $ J.C. Laprie et al.,
V En valeur / Temporelles Guide de la Sûreté de Fonctionnement,
E Conhérentes / Inconhérentes
S
DEFAILLANCES Cépaduès Editions, 1995
Bénignes / Catastrophiques B-11
Classes de fautes
• Quatre grandes classes de fautes et d’erreurs :
— les fautes physiques
— les fautes de conception ;
— les erreurs de l’opérateur ;
— les intrusions.
• Notion de détection: barrières tentant d’empêcher que l’activation
d’une faute sous la forme d’une erreur ne conduise à la
défaillance du système par propagation.
— codes détecteurs d’erreur ;
— duplication et comparaison ;
— contrôles temporels et d’exécution ;
— contrôles de vraisemblance ;
— contrôles de données structurées.
• Notion de recouvrement d’erreur: tentative de restauration d’un
état exempt de faute
B-12
 Pathologie des fautes
— Une faute est active lorsque l’erreur correspondante apparaît
— Une faute est dormante lorsque aucune erreur n’est observée
— Une erreur est latente tant qu’elle n’est pas détectée
Défaillance
Erreur
Erreur latente
Faute Correction
Faute dormante
Dormance de faute Latence d’erreur
temps
B-13
Phénomène de propagation
INTERFACE
DE
DEFAILLANCE SERVICE
MATERIEL
FAUTE ACTIVATION PROPAGATION PROPAG
DORMANTE ERREUR ERREUR . ERREUR
ERREUR
PROGRAMMEUR
PERTURBATION
ELECTROMAGNETIQUE
PROPAGATION PROPAG
ERREUR ERREUR . ERREUR
ERREUR
OPERATEUR
SERVICE
CORRECT DEFAILLANCE SERVICE
INCORRECT
B-14
 Exemples de types de faute
— Court-circuit dans un circuit (e.g. stuck-at) ➠ défaillance du circuit
(faute physique) ➠ erreur dans des cellules mémoire ➠ défaillance
du système
— Défaillance d’un programmer (faute de conception dans un
programme) ➠ activation par un profil activation donné ➠ erreurs
en sortie (en valeur ou temporelles) ➠ défaillance
— Programmeur malicieux qui insère une bombe logique -cheval de
Troie (faute malicieuse) ➠ activation à une date, selon ceratines
conditions opérationnelles ➠ deny de service
— perturbations électromagnétiques (faute physique externe ) ➠
erreur mémoire/registres ➠ défaillance
— fautes d’opérateurs du système (faute d’interaction accidentelle)
— fautes de documentation (d’un composant) ➠ faute d’interaction ou
de conception dans les couches hautes du système ➠ défaillance
B-15
Fautes Erreurs

Innocuité
Exemples de cas

Fiabilité

Confidentialité
Disponibilité/
Conception

Distribuées
Interaction

Localisées
Physiques

Sécurité-
réels observés
Juin 1980 : Fausses alertes à des attaques
✔ ✔ ✔
massives de fus ées soviétiques au NORAD
Juin 1985 - Janvier 1987 : Doses excessives de
radiothérapie (Therac -25)
✔ ✔ ✔
Août 1986 - 1987 : Le "Wily hacker" p énètre des
dizaines de centres informatiques sensibles
✔ ✔ ✔ ✔
15 Janvier 1990 : Indisponibilité totale du téléphone
✔ ✔ ✔
interurbain aux Etats -Unis , pendant 9 heures
Fé vrier 1991 : Scud raté par un Patriot à Dhahran ✔ ✔ ✔ ✔ ✔
Novembre 1992 : Ecroulement des communications
✔ ✔ ✔ ✔ ✔
du service d'ambulances de Londres
26 et 27 Juin 1993 : Refus des cartes de cr édit
dans les distributeurs de monnaie en France
✔ ✔ ✔ ✔
4 Juin 1996 : Défaillance du vol 501 d'Ariane 5 ✔ ✔ ✔
17 Juillet 1997: Mélange des adresses du ✔ ✔ ✔
domaine internet .com
13 Avril 1998 : Ecroulement du réseau de
données d'AT &T ✔ ✔ ✔ ✔
Fé vrier 2000 : Engorgement portails Web ✔ ✔ ✔ ✔
B-16
 Coût de la non SdF
• Coût moyen d’indisponibilité (CA perdu dans les banques,
assurances, assurance maladie, commerce de gros, bourse,
réservations, etc.): 78000 $/h
• Coût des défaillances informatiques
— Fautes accidentelles $ France: 0,9 G € USA: 4 G $
— Malveillances $ France: 1 G € UK: 1,25 G £
• Cout de la maintenance:
— Logiciel embarqué de la navette spatiale: 100 M $ / an
• Coût des logiciels abandonnés
— Aux USA, de l’ordre de 80 G $
— Exemple: FAA AAS (contrôle aérien)
» 1983: 1 G$ - 1988: 4G$ - 1994: 7G$
» Dérapage temporel estimé en 1994 de l’ordre de 6-8 ans
B-17
Classification des fautes
FAUTES DE DEVELOPPEMENT Conception, réalisation
PHASE DE CREATION
OU D'OCCURENCE FAUTES OPERATIONNELLES En exploitation
FAUTES INTERNES Etat interne du système
FRONTIERES SYSTEME
FAUTES EXTERNES Provenant de l’environnement
FAUTES MATERIELLES Composants, liens physiques
DIMENSION
FAUTES LOGICIELLES Programmes ou données
FAUTES
CAUSE FAUTES NATURELLES Aggression, usure…
PHENOMENOLOGIQUE FAUTES DUES A L'HOMME Nobody’s perfect…
FAUTES ACCIDENTELLES OU DELIBEREES SANS MALVEILLANCE
INTENTION
FAUTES DELIBEREMENT MALVEILLANTES Bad Guys…
FAUTES PERMANENTES Non liées à des conditions
PERSISTENCE
FAUTES TEMPORAIRES Dépendantes de conditions
B-18
 FAUTES FAUTES FAUTES
DE CONCEPTION PHYSIQUES D'INTERACTION
FAUTES DE DEVELOPPEMENT ! ! ! ! !
FAUTES OPERATIONELLES ! ! ! ! ! ! ! ! ! !
FAUTES INTERNES ! ! ! ! ! ! !
FAUTES EXTERNES ! ! ! ! ! ! ! !
FAUTES MATERIELLES ! ! ! ! ! ! ! ! ! !
FAUTES LOGICIELLES ! ! ! ! !
FAUTES NATURELLES ! ! ! ! !
FAUTES DUES A L'HOMME ! ! ! ! ! ! ! ! ! !
FAUTES ACCIDENTELLES OU ! ! ! ! ! ! ! ! !
DELIBEREES SANS MALVEILLANCE
FAUTES DELIBEREMENT
MALVEILLANTES ! ! ! ! ! !
FAUTES PERMANENTES ! ! ! ! ! ! ! ! !
FAUTES TEMPORAIRES ! ! ! ! ! !
DEFAULT
DEFAUT DETERIORATION VIRUS ENTREE
DEFAUT INTRUSION
LOGICIEL
LOFICEL MATERIEL PHYSIQUE & VER ERRONEE
LOGIQUE DEFAUT DE INTERFERENCE
ATTAQUE
MALIGNE PRODUCTION PHYSIQUE B-19
Les modes de défaillance
• Le système ne défaille pas toujours de la même façon
➠ modes de défaillance
DEFAILLANCES EN VALEUR
Factorielle de 3 = 975
DOMAINE
DEFAILLANCES TEMPORELLES
Déclenchement airbag 1h après choc
DEFAILLANCES CONTROLEES
Error status, exception, alarme
CONTROLABILITE
DEFAILLANCES INCONTROLEES
J’AI RIEN VU! Non détection!
DEFAILLANCES
DEFAILLANCES COHERENTES
Mode de défaillance admissible
COHERENCE
DEFAILLANCES INCOHERENTES
Mode de défaillance INadmissible
DEFAILLANCES BENIGNES
•
Pas grave!
CONSEQUENCES •
SUR ENVIRONNEMENT •
DEFAILLANCES CATASTROPHIQUES
DE GROS DEGATS!!!!! B-20
 Les modes de défaillance
• Le système ne défaille pas toujours de la même façon
➠ modes de défaillance
DOMAINE DE DEFAILLANCE
Valeur Valeur et Temporisation
(temporisation temporisation (valeur
correcte) correcte)
Service Service Service en Service en
interrompu erratique avance retard
DEFAILLANCES DEFAILLANCES DEFAILLANCES DEFAILLANCES DEFAILLANCES
EN VALEUR PAR ARRET ERRATIQUES TEMPORELLES EN
AVANCE PERFORMANCE
B-21
Les modes de défaillance
• Le système ne défaille pas toujours de la même façon
➠ modes de défaillance
CONTROLABILITE DES DEFAILLANCES
Défaillances Défaillances
détectées non détectées
Service Service
correct incorrect
Service Service
selon modes selon modes
défaillance défaillance
admissibles inadmissibles
FAUSSE DEFAILLANCES DEFAILLANCES DEFAILLANCES
ALARME CONTROLEES SIGNALEES NON SIGNALEES
B-22
 Systèmes à défaillance contrôlée
SYSTEMES A DEFAILLANCES CONTROLEES
DEFAILLANCES STOPPING DEFAILLANCES DEFAILLANCES
PAR ARRET FAILURE COHERENTES BENIGNES
FIGEMENT
ETAT SORTIES
SYSTEME FAIL-PASSIVE
A FIGEMENT SYSTEME A SYSTEME SUR
SYSTEM FAIL-SAFE
SUR DEFAILLANCE DEFAILLANCES EN PRESENCE DE
SYSTEM
COHERENTES DEFAILLANCE
SILENCE
(ABSENCE EVENEMENT)
SYSTEME FAIL-SILENT
A SILENCE SUR
DEFAILLANCE
SYSTEM Comment rendre un service acceptable
en dépit de l’occurrence de fautes?
SYSTEME
A ARRET SUR DEFAILLANCE
FAIL-HALT
SYSTEM
-Arrêt sur défaillance
-Défaillance contrôlée (mode dégradés)
-Sûreté en présence de défaillance
B-23
Statistiques de défaillances
• Défaillances accidentelles
— Causes Fautes physiques internes ≈10%
Fautes physiques environnementales ≈10%
Fautes d’interaction homme/système ≈20%
Fautes de conception ≈60%
Composant Système tolérant
— Fréquences
informatique les fautes
Fautes physiques permanentes ≈1 an 20-100 ans
Fautes intermittentes qq.h /qq sem. > 10 ans
— Densité de fautes de conception
» Fautes crées durant le développement: 10-300 / kLoC
» Fautes résiduelles en opération: 0,01 - 10 / kLoC
• Malveillances [Ernst &Young 1998; 1200 sociétés dans 32 pays]
— Sociétés ayant souffert d’au moins un fraude en un an: 66%
— Sociétés ayant souffert de plus de 5 fraudes en un an: 17%
» 85% de fraudes perpétrées par des employés
B-24
 Les moyens
B-25
Les moyens
• Prévention des fautes
» Toutes les méthodes pour améliorer les processus de production du
logiciel et du matériel
• Tolérance aux fautes
» Mécanismes pour assurer un service correct en présence de fautes
• Elimination des fautes:
» Techniques permettant de réduire la présence des fautes
• Prévision des fautes:
» Techniques pour estimer le nombre et les conséquences de fautes
« résiduelles ».
B-26
 La tolérance aux fautes
• Deux notions essentielles
— Le traitement d’erreur: éliminer l’erreur avant défaillance
détection
Traitement d’erreur
Latence
{ recouvrement
d’erreur
Faute Erreur Défaillance
Latence de faute
— Le traitement de faute: éviter la ré-activation des fautes
Traitement d’erreur + traitement de faute = tolérance aux fautes
B-27
Traitement d’erreur
• Détection,
— Identification d’un état erroné dans le système
• Diagnostic,
— Analyse permettant de déterminer les causes et les dommages
causés par l’erreur
• Recouvrement
» Recouvrement arrière:
- Ramener le système dans un état antérieur exempt de faute,obtenu
avant l’occurrence de l’erreur (notion de points de reprise)
» Recouvrement avant:
- Déterminer un nouvel état à partir duquel on sait que le système peut
fonctionner (notion de mode dégradé)
• Compensation:
— Disposer de suffisamment de redondance en dépit de l’état erroné
pour le transformer en un état exempt d’erreur (techniques de
masquage de faute, par vote majoritaire, par exemple)
B-28
 Traitement d’erreur
Recouvrement arrière Recouvrement avant Compensation
Point de
reprise
Etat de
reprise
?
Nouvel Décision
État de
reprise
Service OK Service OK Service OK
B-29
Notion de modèle de faute
• Quelles sont les fautes que l’on souhaite traiter?
— Physiques, Conception, Malicieuses
— Quels sont leurs effets, c’est-à-dire les erreurs qu’elles provoquent
• Exemples vis-à-vis de fautes physiques
— Arrêt sur défaillance L’erreur a conduit a l’arrêt du composant ➠
basculement sur un composant identique correct
— Omissions L’erreur a conduit à la perte d’un message ➠
protocole de répétition ou de diffusion fiable
L’erreur a conduit à la corruption d’une valeur en
— Erreurs en valeur sortie ➠ mécanisme de compensation d’erreur
• Exemples vis-à-vis de fautes du logiciel
— Erreur de conception Faute de conception par rapport aux spécifications
“correctes” ➠ diversification
— Erreur de codage Faute de programmation ➠ diversification
— Erreur de ressources Défaut de ressource ➠ ré-exécution sur autre
support d’exécution
B-30
 Techniques classiques
• Architecture duplex
crash
P S basculement P S
Fonctionnement normal Fonctionnement après basculement
• Remarques importantes sur les hypothèses:
— Les sorties du primaire P sont considérées comme correctes tant
qu’un crash n’a pas été détecté
— Si un crash est détecté, on considère que le composant P est à
silence sur défaillance, c’est-à-dire sans propagation d’erreur
— Ceci impose :
» que toute erreur interne est confinée dans P (idem S)
» un protocole de surveillance signalant à S le crash de P
B-31
Techniques classiques
• Architecture TMR (Triple Modular Redundancy)
crash
X
C1 Y
C2 Y
C3
V
Y
Fonctionnement normal
• Remarques importantes sur les hypothèses :
— Les entées sont identiques: valeurs et séquence d’entrée
— Le crash est considéré comme une absence de réponse
— Parmi les réponses fournies, la valeur majoritaire est considérée
comme le résultat correct
— Si les composants sont identiques, vote=comparaison
— Si les composants sont diversifiés, vote=algorithme de décision
B-32
 Elimination des fautes
• Méthodes de test
— Identification des fautes dans le composants matériels et logiciels
— Approches
» Déterministes: choix sélectif pour couvrir un critère
» Aléatoires: tirage aléatoire des valeurs d’entrées, selon un critère
• Notion de critère :
— modèle structurel ou fonctionnel +
— éléments du modèle à activer
• Génération des vecteurs de test
— Exemple de critère: « toutes les branches »
» Cas déterministe: choix « a priori » des valeurs d’entrées qui
permettent de passer dans chaque branche
» Cas aléatoire: génération de valeurs d’entrée (e.g. branches
équiprobables) et analyse de la couverture (toutes les branches)
— Observation des sorties
» Comparaison avec une référence ➠ Notion d’Oracle de test
B-33
Techniques de vérification
Analyse statique (du code)
statique Preuve mathématique
Analyse du comportement
vérification
Exécution symbolique
dynamique
Test
• Application à la vérification du logiciel: pratiques actuelles
— Revue de code, inspections à l’aide d’outils (compilateurs,
analyseurs de code,etc.) ➠ identification d’erreur (var. non init.,
interfaces incompatibles, code mort, etc.)
— Spécification formelle + spécification formelle langage + règles
d’inférences
— Automates à états finis, réseaux de Petri, StateCharts
— Le test (en particulier du logiciel)
B-34
 Test du logiciel
Structurel Fonctionnel
Boîte blanche Boîte noire
Complémentaire

Choix déterministe déterministe

sélectif
Choix statistique statistique
aléatoire
Selon complexité du programme
• Critères test structurel:
— Technique s’appuyant sur le graphe de contrôle du programme
— Au moins une fois, toutes les instructions, toutes les branches
• Critère test fonctionnel:
— Notion de classes d’équivalence des entrées (valides/invalides)
— Valeurs aux limites
— Machines à états finis: couvrir les états, les transitions, les deux
Le test est plus facilement automatisable si l’on dispose d’un modèle
comportemental du système ou de la fonction B-35
Test du logiciel
• Types de tests
— Test unitaire: application de séquences de test à un composant
isolé
Entrées de test Emulation de l’
Composant environnement
Driver de test
sous test (bouchons)
Sortie
Oracle
— Test d’intégration: agrégation progressive des composants
— Le problème de l’Oracle: décision OK / non OK
» Test dos-à-dos basé sur les développements diversifiés (pb. fautes
corrélées)
» Spécifications formelles exécutables, modèles comportementaux,
simulation B-36
 Au moins une fois Toutes les branches
[Link]
Test structurel
Function LandingControl (integer: speed; integer: alt) Déterministe
Boîte blanche
speed=500; alt=* speed=300; alt=900
B1
speed=300; alt=1200
yes no
Speed > 400
yes no
Alt > 1000
Stub
Engines B2
Engines Stub
Alt.
B2 B3
AltControl
Control
[Link]
Oracle: Abort Landing
B-37
Test de la tolérance aux fautes
• Les mécanismes de tolérance aux fautes sont à la fois
— Faillibles (fautes de conception et/ou de réalisation)
— Conçus pour traiter des entrées spécifiques: les fautes!
$ leur vérification est essentielle!
• L’approche expérimentale par injection de fautes
— Simulation des fautes, ou plutôt de leurs effets, les erreurs
» physiques (bit-flip) ou du logiciel (mutation d’instruction)
— Cibles: un composant logiciel équipé de son mécanisme de TAF
» Boite blanche: visibilité structurelle (comment il est fait) et
comportementale (comment il agit/ré-agit)
» Boite noire: aucune connaissance, seules les interfaces sont visibles
— Les types d’injection:
» niveau physique(stuck-at), modèle (VHDL) ou par logiciel (SWIFI)
— Les problèmes:
» Représentativité des fautes
» Observation et analyse des résultats.
B-38
 Les techniques d’injection de fautes
système ➠ DEPEND, REACT, ...
niveau RTL ➠ ASPHALT, ... Nœuds ➠ ORCHESTRA
porte logique ➠ Zycad, Technost, ... tâche ➠ FIAT
circuit ➠ FOCUS, ... instr. ➠ FERRARI
... mém. ➠ DEF.I, DITA,
large spectre ➠ MEFISTO, SYSTÈME CIBLE MAFALDA
VERIFY(VHDL) Reg. ➠ Xception
Modèle Prototype
M Logique & injection injection
O Information en simulation en logiciel
Y
E ≈
injection
Physique
N physique
ions lourds ➠ Université Chalmers
perturbations EM ➠ TU Vienne
broches ➠ MESSALINE, Scorpion,
DEFOR, RIFLE, AFIT,...
B-39
Prévision des fautes
• Techniques classiques: AMDE(C) – Analyse des Modes de
Défaillance et leur Effet (et de leur Criticité)
— Analyse pour chaque composant de l’effet des erreurs
— Identification des modes de défaillance
— Conséquence des défaillance au niveau système
• Principe
— Étudier la structure du fonctionnelle du système
— Au plus tôt dans le processus de développement (représentation
abstraite)
— Pour chaque composant:
» Causes possibles de défaillance
» Effet sur le composant lui-même et les canaux de propagation
» Identification des moyens de détection
» Actions correctrice (en particulier si les conséquences sont catastrophiques)
— Avantages: Identifier et modifier des lacunes conceptuelles
— Inconvénients: multiplicité? Exhaustivité? Complexité?
B-40
 Prévision des fautes
• AMDEC appliqué au logiciel (AEEL: Analyse des Effets de Erreurs
du Logiciel)
— Bâtie sur la spécification et la conception préliminaire
— Intérêts:
» Guide pour la stratégies de détection et de tolérance aux fautes
» Orientation des tests sur certains modules ou modes de défaillance
» Compréhension en exploitation de l’origine d’une défaillance
• Notion d’arbre de fautes
— Recherche des combinaison possible d’événements conduisant à
un événement indésirable, tel qu’un défaillance catastrophique
— Combinaison des événements par des opérateurs logiques
— Intérêt: Identification des composants critiques sur lesquels de
techniques de tolérance aux fautes du logiciel sont nécessaires
B-41
Exemple
• Soit le système S, formé des composants X, Y et Z selon un
schéma d’interconnexion (interdépendance)
Y
X
Z OU
• S défaille si: X
— X défaille
ET
OU
— Y ET Z défaillent
Y Z
• Deux représentations équivalentes
B-42
 Evaluation de la SdF
Distributions en fonction du temps, temps moyens,...
• Reliability (fiabilité) ➡ continuité du service (sonde spatiale,...)
— MTFF ➡ temps moyen avant la 1ère défaillance,...
• Availability (disponibilité) ➡ paré à assurer le service
• Safety (sécurité-innocuité) ➡ non occurrence de défaillances
catastrophiques (transport,...)
Défaillance bénigne Service
incorrect
Défaillance (benign)
Service Service Service
correct incorrect correct
Restauration
Service
Restauration incorrect
Défaillance catastrophique (catastr.)
B-43
Sur les types de modèles
• Diagrammes de fiabilité Arbres de fautes
OU
Y X
X
Z ET
YZ
• Chaînes Markov cont. Rés. Petri Stochastiques généralisé
M[P1]*λ
2λ λ
2 1 0 P1 P2
µ µ µ
λ = taux de défaillance = 1/ temps moyen entre défaillance
µ = taux de restauration = 1/ temps moyen de réparation
B-44
 Introduction aux mesures de base
• Fiabilité (Reliability):
— Mesure de la délivrance continue d’un service correct, donc du
temps jusqu’à défaillance
• Disponibilité (Availability):
— Mesure de la délivrance d’un service correct par rapport à
l’alternance « service correct – service incorrect », donc de la
succession des défaillances et des restaurations
• Des exemples de symboles
— MTFF : Mean Time to First Failure, MTTF: Mean Time To Failure
— MTBF : Mean Time Between Failures
— MTTR : Mean Time to Repair
• Des estimateurs statistiques (moyennes arithmétiques)
— N(0): nb de systèmes de l’échantillon
— N(t): nb de systèmes non défaillants à l’instant t
— N1(t): nb de systèmes n’ayant pas défaillis depuis l’instant initial
B-45
Mesures / estimateurs statistiques
Nb de systèmes n’ayant
• Fiabilité (Reliability): pas défaillis depuis t0
R(t) = probabilité{S non défaillant sur [0,t]}
Fonction non croissante sur [0, ∞[ Nb total
de systèmes
Estimateur statistique de R(t) = N1(t)/ N(0)
• Disponibilité (Availability):
Nb de systèmes non
A(t) = probabilité{S non défaillant à l’instant t}
défaillants à l’instant t
La disponibilité concerne les systèmes réparables
Estimateur statistique de R(t) = N(t)/ N(0)
• Maintenabilité (Maintainability) Nb total
de systèmes
M(t) = 1- probabilité {S non réparé sur [0,t]}
Sachant qu’il est défaillant à l’instant t=0
• Calcul des MTTF et MTTR
MTTF= ∫0 R(t) dt
∞
MTTR=∫0 M(t) dt
∞
B-46
 Fiabilité
• Le taux de défaillance d’un système à l’instant t est défini par:
Le système tombe en panne entre t et t+∆t
Λ(t)= lim∆t➝0Probabilité { }
Sachant qu’il n’y a pas eu de défailance sur [0,t]
La connaissance de la fonction Λ(t) est équivalente à celle de R(t)
R(t)= exp ∫0 Λ(u) du
t
par :
En considérant que Λ(t) se réduit à une constante notée λ
alors : R(t)= e-λt
• Allure typique de la fiabilité (stabilisée)
R (u)
Prob {k+1ièmedef.<u}= Prob {kièmedef.<u}
1
TMR
duplex
simplex
0 t1 t2 t3 u
B-47
Fiabilité
• Le taux de défaillance d’un système à l’instant t est défini par:
Le système tombe en panne entre t et t+∆t
Λ(t)= lim∆t➝0Probabilité { }
Sachant qu’il n’y a pas eu de défailance sur [0,t]
La connaissance de la fonction Λ(t) est équivalente à celle de R(t)
R(t)= exp ∫0 Λ(u) du
t
par :
En considérant que Λ(t) se réduit à une constante notée λ
alors : R(t)= e-λt
• Allure typique de la fiabilité (stabilisée)
R (u)
MTFF
1
TMR 3 3λ 2 2λ
5/6λ TMR
duplex
duplex 2 2λ 1 λ
3/2λ simplex
λ
simplex 1 λ
0 t1 t2 t3 u
B-48
 Notion de couverture
• Efficacité de la tolérance et fautes
Notion de couverture C= Prob {traitement correct | erreur}
Sachant qu’il y a eu une erreur, quelle est la probabilité d’obtenir un
traitement correct?
Supposons qu’il y ait 10 erreurs dans un système parfaitement
observable, ou bien que l’on ait injecté 10 fautes qui ont été activées
et ont conduit à 10 erreurs:
Détection parfaite • si on détecte 10/10 alors
C=1 (100% de résultats corrects)
µ
1 2 3 • si on détecte 9/10 alors
λ
2λ C=0.9 (90% de résultas corrects)
Chaîne de Markov
Quelle est l’influence de C (la capacité de détecter des erreurs) sur la
fiabilité d’un système duplex?
B-49
Cas d’un système duplex
• Efficacité de la tolérance et fautes
Notion de couverture C= Prob {traitement correct | erreur}
104
S1
x MTTF Syst. 103
c = .999 c=1
S2 MTTFComp.
c = .995
2
10
Système « duplex » c = .99
1 c = .95
2 (1-c) λ 10
λ MTTR Comp.
=
c = .9 µ MTTF Comp.
µ 1
1 2 3
λ 10
-4
10
-3
10-2
2cλ
1/λ est grand (e.g. des mois) devant
Chaîne de Markov 1/µ (1 heure), donc λ/µ est petit
$ Si C est proche de 1 alors la fiabilité du système duplex/simplex est
bonne ➠ MTTF(Système) ≈ 1000*MTTF(Composant) si µ >> λ.
$ Si C est proche de 0.9 alors la fiabilité du système duplex…..!!!!!!!
B-50
 Cas d’un système TMR
Architecture Modèle —
"en réserve" 4 C T,1 λ N
4λ H + 4 CT λ N 3 λ H + 3 CT λ N
Hôte Hôte Hôte Hôte
1 2 3
µ — µ
NAC NAC NAC NAC 3 C T λ NN
— —
4 ( C T,2 + C T,3 ) λ N 2 λ
Anneau à jeton
4
MTFF réseau
MTFF station Modélisation
Expérience
NAC Duplex - V4 La détection-extraction est
10+3 effectuée par les NAC avec
une couverture imparfaite
NAC V3
10+2 Facteurs de couverture
NAC V2 mesurés expérimentalement
sur le système par des
10+1 NAC V1 techniques d’injection de
fautes
10-4 10 -3 λ/µ 10 -2
B-51
La suite
• Architecture des systèmes tolérant aux fautes
— Techniques de base
— Solutions architecturales
— Exemples de systèmes
• Caractérisation de la sûreté de fonctionnement des systèmes
— Techniques de base
— Outillages
— Exemple de résultats expérimentaux
B-52
 Techniques de tolérance aux
fautes
Hypothèses de fautes,
techniques de base et stratégies de réplication et
solutions architecturales
C-1
Rappel La tolérance aux fautes
• Deux notions essentielles
— Le traitement d’erreur: éliminer l’erreur avant défaillance
détection
Traitement d’erreur
Latence
{ recouvrement
d’erreur
Faute Erreur Défaillance
Latence de faute
— Le traitement de faute: éviter la ré-activation des fautes
Traitement d’erreur + traitement de faute = tolérance aux fautes
C-2
Rappel Traitement d’erreur
• Détection,
— Identification d’un état erroné dans le système
• Diagnostic,
— Analyse permettant de déterminer les causes et les dommages
causés par l’erreur
• Recouvrement
» Recouvrement arrière:
- Ramener le système dans un état antérieur exempt de faute, obtenu
avant l’occurrence de l’erreur (notion de points de reprise)
» Recouvrement avant:
- Déterminer un nouvel état à partir duquel on sait que le système peut
fonctionner (notion de mode dégradé)
• Compensation:
— Disposer de suffisamment de redondance en dépit de l’état erroné
pour le transformer en un état exempt d’erreur (techniques de
masquage de faute, par vote majoritaire, par exemple)
C-3
Hypothèses de fautes
• Fautes accidentelles
— Fautes physiques et leur effets
» Silence sur défaillance: toute faute d’un composant conduit à un arrêt
sur défaillance (silence), c’est-à-dire sans propagation d’information
erronée à l’extérieur du composant (valeurs en retour, messages émis,
actions sur l’environnement)
» Erreur en valeur: une valeur de sortie peut être corrompue
— Fautes du logiciel
» Fautes de développement (conception ou codage) d’un composant
» Fautes liés au support d’exécution d’un composant au niveau de la
gestion de ressource
• Fautes intentionnelles (malveillantes)
— Tentatives d’attaque: écoute passive, corruption d’information, sur
les données échangés par deux composants (en particulier
répartis)
— Mécanismes de cryptographie et de tolérance aux intrusions
C-4
 Stratégie de tolérance aux fautes
• Mécanismes pour la tolérance aux fautes physiques
» M1: disques miroir
» M2: réplication passive
» M3: réplication semi-active
» M4: réplication active
client
requête requête requête requête
réponse réponse réponse réponses
serveur
point de copie
reprise requête
M1 M2 M3 M4 C-5
Disques miroir
• Principes
— les processus d’application effectuent le traitement des requêtes de leur
clients et sauvegardent l’état courant de leur calcul (points de reprise)
sur des disques miroir :
» les points de reprise sont écrits sur les deux disques simultanément
» lors de la remise en service, le processus relit son contexte sur disque
client client client
requête
réponse
Crash
serveur serveur serveur
lecture
point de reprise
C-6
 Disques miroir
• Commentaires
— Une seule unité de traitement est utilisée
» la réparation doit intervenir avant la remise en service, c’est-à-dire le
redémarrage d’un service opérationnel. Il y a donc interruption de service
pendant la durée de réparation
— Différentes unités ont accès au support de mémoire stable
» redémarrage d’un service opérationnel avant terminaison de la réparation
client client client
requête
réponse
Crash
serveur serveur serveur
lecture
point de reprise
C-7
Réplication passive
• Principes
— Chaque processus
d’application (primaire)
possède un processus Primary…………………Backup
de secours (secondaire) sur un
site distinct de celui du
client
primaire.
— Le processus primaire effectue requête requête
le traitement des requêtes de réponse réponse
ses clients et transmet
périodiquement une image de serveur Crash
son état au secondaire.
— Le secondaire met à jour son point de
reprise
état (contenu de ses variables)
sur réception des points de
reprise.
— Seul le primaire retourne une
réponse au client.
C-8
 Réplication passive
• Commentaires
— L’hypothèse de base est que
toute réponse à une requête
est correcte. Primary…………………Backup
— Notion de silence sur
défaillance ➠ composant client
autotestable + couverture de
détection de 100% requête requête
réponse réponse
— Un point de reprise implique la
capture d’un état complet pour
la reprise après basculement serveur Crash
(processus + exécutif)
point de
— La détection correspond à une reprise
surveillance mutuelle
— La durée d’interruption de
service est due à la
restauration d’un service actif
C-9
Réplication semi-active
• Principe
— Chaque processus
d’application (primaire)
possède un processus de Leader…………………Follower
secours (secondaire) sur un
site distinct de celui du
primaire.
client
— Le processus primaire effectue
le traitement des requêtes de requête requête
ses clients et transmet au réponse réponse
secondaire la requête qu’il
vient de traiter. serveur
— Le secondaire traite à son tour
Crash
la requête pour mettre à jour copie
son état. requête
— Seul le primaire retourne une
réponse au client.
C-10
 Réplication semi-active
• Commentaires
— L’hypothèse de base est que
toute réponse à une requête
est correcte. Leader…………………Follower
— Notion de silence sur
défaillance ➠ composant client
autotestable + couverture de
détection de 100% requête
réponse
requête
réponse
— Il n’y a pas de point de reprise:
serveur
l’état est reconstruit par le Crash
traitement de la requête
copie
requête
— La détection correspond à une
surveillance mutuelle
— La durée d’interruption de
service est due à au seul
changement de mode
C-11
Réplication et vote majoritaire
• Principe
— Chaque processus d’application est répliqué en trois exemplaires
sur des sites distincts.
— Les trois répliques reçoivent des requêtes au travers d’un système
de communication de groupe et effectuent le traitement
correspondant.
— Chaque réplique transmets une réponse au client qui effectue
un vote majoritaire : client
» la défaillance d’un processus est détectée
par l’absence de réponse requête
» une erreur de valeur sur l’une des réponses
réponses est détectée par vote majoritaire
serveur
C-12
 Réplication et vote majoritaire
• Commentaires
— La diffusion des requêtes d’entrée:
» Toutes les requêtes, quelle que soit leur source, doivent être reçues
dans le même ordre
» Une copie de chaque requête est reçue par toutes les répliques ou
aucune n’en reçoit de copie
» Notion de diffusion de groupe atomique
client
— Les copies doivent être déterministes
» Les mêmes entrées produisent les mêmes sorties requête
réponses
— La décision:
» Répliques identiques: vote bit-à-bit serveur
» Répliques similaires: algorithme de décision
C-13
Synthèse (1)
Stratégies Hypothèse en Faute Déterminisme Coût en Coût en Coût lors du
présence de tolérée des répliques Ressources Communication Recouvrement
faute
Passive Silence sur Crash Non 1 serveur haut (checkpoints) Moyen (re-
défaillance actif exécution)
Semi-active Silence sur Crash Non 2 serveurs bas (notifications) bas (switch)
défaillance actifs
Active Défaillance Valeur Oui 3 serveurs moyen Nul
arbitraire actifs (duplication
messages)
Réplication Entités Action Motivation Moyens
passive
Communication Requêtes/réponses Emission/réception Synchronisation entre répliques. Interception
Exécution Points activation / Capture / restauration du Interception
d’interruption continuation / contrôle lors du traitement des Instrumentation
asynchrone du flot terminaison requêtes dans des composants de la plate-
de contrôle concurrents. forme
Etat Données internes, Mise-à-jour de Restauration cohérente de l’état Image mémoire
état plate-forme données internes, pour un recouvrement Sérialisation
interactions avec la transparent aux composants Interactions
plate-forme exécutive applicatifs clients. Journaux
locale
C-14
 Synthèse (2)
Réplication Entités Action Motivation Moyens
semi-active
Communication idem passive idem passive Contrôle des notifications idem
passive
Exécution idem passive + points de idem passive + points de Décisions non-déterministes idem
décision non- décision non- passive
déterministes déterministes
Etat idem passive idem passive Contrôle des interactions idem
avec la plate-forme passive
produisant des résultats non-
déterministes
Réplication Active Entités Action Motivation Moyens
(TMR)
Communication idem passive validation & propagation des réponses idem passive
Exécution Pas nécessaire (déterminisme imposé de l’exécution des répliques)
Etat Pas nécessaire (si clonage à chaud non considéré)
C-15
Notion de composant autotestable
• Définition
— L’ajout de capacités de détection d’erreur à un composant conduit
à la notion de composant autotestable (self-cheking component)
— Cette notion peut s’appliquer à des composants logiciels et
matériels
inputs outputs
function
errors
controller
• Commentaires
— Avantage: limitation de la propagation d’erreur ➠ zone de
confinement (error confinement area)
— Composant autotestable + couverture 100% ➠ composant à silence
sur défaillance (fail silent component).
— Approche récursive: contrôleur = composant autotestable
C-16
 Recouvrement « arrière »
• Principe
— Ramener le système dans un état précédemment occupé par le
calcul avant l’occurrence de l’erreur
— Cet état est suffisamment complet pour redémarrer l’exécution et a
été préalablement sauvé (disques miroir ou backup)
• Problèmes conceptuel:
— Etablissement des points de reprise recovery points
» Etat: interne, messages non traités, contexte de l’exécutif, etc.
» Quand? Périodique ou apériodiques?
— La définition des instants ou ces points de reprise sont établis
dépend de l’interaction des processus entr’eux.
C-17
Le problème de l’effet domino
• Processus concurrents communicants
— domino effect
P1 m1 m4
P2 crash de P2
m2
P3
m3
Mais, où est donc ce
message…
qui ne vient jamais?
m1 ? ? m4
P1
P2 m2
?
P3
? m3
Remarque: les interactions sont représentées ici par des messages,
Mais pourraient être de toute autre nature (e.g. partage de mémoire)
C-18
 Le problème de l’effet domino
• Processus concurrents communicants
— Si un IPC coupe une ligne de recouvrement, alors « effet domino »
P1 m1 m4
P2 crash de P2
m2
P3
m3
Ligne de recouvrement
• Notion de conversation
— Définir a priori un découpage des processus pour éviter le
problème
— Synchroniser la prise d’état sur ce principe
P1 m1 m4
P2
m2
P3
m3
C-19
Le problème de l’effet domino
• Processus concurrents communicants
— Si un IPC coupe une ligne de recouvrement, alors « effet domino »
P1 m1 m4
P2 crash de P2
m2
P3
m3
Ligne de recouvrement
• Synchronisation « point de reprise » / « réception message »
Hips!…
J’ai le message!
m1 m4
P1
P2 m2
?
P3
m3
C-20
 Combinaison de techniques
• Recouvrement « arrière » puis « avant »
— Le recouvrement « arrière » est la première tentative de traitement
de l’erreur
— Si l’erreur persiste, alors, une action de recouvrement « avant »
peut être entreprise en définissant un état des processus cohérent.
Cet état est souvent dépendant de l’application.
• Aspect temporel
— Lors d’un recouvrement, la surcharge temporelle (et donc le temps
de réponse) est plus important quand il y a erreur que quand il n’y
en a pas.
— Dans le cas du recouvrement « arrière » la surcharge temporelle en
l’absence de faute correspond à l’établissement des points de
reprise.
— Dans le cas de la compensation, la surcharge temporelle
correspond aux algorithmes de décision, le temps de réponse
restant à peu près constant.
C-21
Notion de protocoles de groupe
• Basic protocols
— Groupes (groups):
» une adresse correspond à un ensemble de destinataires
— Appartenance (membership): α
» liste des membres du groupe
β G
» notion de vues (views, view-change)
γ
— Diffusion (broadcast): send (M, G)
— Consensus (Consensus): vision uniforme d’une information
• Propriétés
• Unanimité: tout M reçu par un R correct est reçu par tous les R corrects
• Non-trivialité: tout M délivré a été émis par un processus correct
• Accessibilité: tout M délivré à un processus correct est accessible
• Délivrance: tout M est délivré tant que S non-défaillant ou R non-accessible
• Ordre: tous les M sont délivrés à tous les membres correct de G dans le
même ordre
C-22
 Notion d’ordre
• Causal • Total
S R1 R2 R3 S1 S2 R1 R2 R3
36 M1 M1
M3
S,36
37 M2 M2
S,37
Numéro de séquence géré à l’émission
C-23
Implémentation
• Ordre total
Niveau R1 R2 R3
S1 S2 Application
M1 M1 M1
M1 M2 M2 M2
M3 M3 M3 M3
Niveau délivrance
M2 Niveau
ordre
OS (1,2,3) (1,2,3) (1,2,3) causal
Niveau réception
M1 M1 M1
Niveau M2 M3 M2
Réseau
M3 M2 M3 C-24
 Implémentation
• Ordre total: Commentaires
R1 R2 R3
— Il faut assurer une
communication fiable sur des
liaisons bi-point entre le leader M1 M1 M1
et les membres du groupe
M2 M2 M2
— Le leader ne doit pas être M3 M3 M3
byzantin, c’est-à-dire envoyer
des informations non-uniformes Niveau délivrance
aux membres du groupe
➠ silence sur défaillance ordre
(1,2,3) (1,2,3) (1,2,3) causal
— Même en cas de défaillance du
leader, tous les membres du Niveau réception
groupe doivent décider la
même valeur (vecteur)
➠ notion de consensus
M1 M1 M1
M2 M3 M2
— La perte du leader impose
l’élection d’un nouveau leader M3 M2 M3 C-25
Implémentation
• Ordre total: Commentaires
R1 R2 R3
— Il faut assurer une
Utilisation de protocoles avec contrôle
communication fiable sur des
d’erreur et garantie de bi-point
liaisons séquencement
entre le (type TCP)
leader M1 M1 M1
et les membres du groupe
M2 M2 M2
— Le leader ne doit pas être M3 M3 M3
byzantin, c’est-à-dire
Composant logiciel/matériel deenvoyer
gestion
des informations
Des messages non-uniformes
doit être autotestable Niveau délivrance
aux membres du groupe
➠ silence sur défaillance ordre
(1,2,3) (1,2,3) (1,2,3) causal
1) Détection—de la défaillance
Même en cas dedudéfaillance
leader du
2) Protocole à deux phases:
leader, tous les membres du Niveau réception
2.1) transmission
groupeMdoivent
+ ack des membres
décider la
2.2) confirmation/abort
même valeur (vecteur)
➠ notion de consensus
M1 M1 M1
1) Statique: séquence pré-déterminée M2 M3 M2
2) Dynamique:
— La chaque membre
perte du leadervivant
imposegénère une
Valeur aléatoire αi que l’on
l’élection d’unrange par leader
nouveau M3
ordre croissant. M2 M3 C-26
La valeur la plus grande détermine le leader.
Hypothèses: Synchrone v.s. Asynchrone
• Hypothèse synchrone:
— Tout message émis par un processus correct vers une destination
correcte est 1) reçu et 2) traité dans un intervalle de temps connu.
— Pour du temps-réel dur il faut déterminer
» WCET (Worst Case Execution Time) des tâches
» Les bornes supérieures de transmission de message,
» La fréquence maximale des défaillances
— Masquage des fautes transitoires: redondance temporelle -
répétition systématique.
Hypothèse asynchrone:
— Pas de borne sup ➱ impossibility result (Fisher, Lynch & Paterson):
“In distributed asynchronous systems, it is impossible to detect a
failed process from a very slow process”.
— En pratique
» On se ramène à borner les temps de transmission de message
» Définition de ∆T avec une certaine couverture
C-27
Quelques exemples
C-28
 Solutions à micronoyau temps-réel
• Micronoyau temps-réel
— Services OS de base (synchronisation, gestion mémoire,
ordonnancement, communication,etc.)
— Nouvelle tendance: “Open” microkernels ➠ spécialisation
• Objet model
— objets interagissant par messages
— objets composés de threads de control concurrents
— objets encapsulant un état
• Exemple: Chorus
— Concepts de base:
» actors : objets actifs multi-theraded
» ports : boites à message
— Le noyau peut être spécialisé
— Notion de personnalité, UNIX par exemple
C-29
Microkernel technology
Subsystem
Multi-threaded
active objects message
port
IPC
Real-Time (messages / ports) Memory
executive management
IT, traps, MMU...
micro-core executive (machine dependent)
C-30
 Un exemple simple de réplication
• Threads et des ports
— Synchronization: gestion de la synchronisation (semi-actif)
— Handle_State: gestion des messages de points de reprise(passif)
— Recovery: mise-à-jour état, changement mode, re-nommage ports,
clonage
• Fonctions:
— Save_State, Send_Checkpoint, Send_Notification, Clone_Replica
Site 2 Object crash
Site 1
p2
p1
p2 checkpointing
Site 3
C-31
PBR
Site 1 Site 2
request ipcReceive state
p
pp bp
T H T
SaveState
Send_Checkpoint
reply ipcReply rp
R
p = service port p
pp = primary port
bp = backup port detection
rp = recovery port
T = service thread « Periodic I’am
alive messages »
H = Handling_State thread
R = Recovery thread
C-32
 Synthèse
• SaveState
— Sauvegarde de l’état interne de l’objet
• Send_Checkpoint
— Propagation de l’état interne au backup
• Thread H
— Mise-à-jour de l’état interne de l’objet à l’aide de l’information
contenue dans le point de reprise
• Thread R
— Activation par le signal de détection : “primary crash”.
— Restauration port de service et clonage nouvelle réplique
— Traitement des requêtes:
» Lorsque un protocole de groupe n’est pas utilisé, il peut y avoir perte de
messages donc un protocole de bout-en-bout est nécessaire
C-33
Solutions à intergiciel (Middleware)
• Les approches
— Par interception d’appels système (system calls)
» fork/exec : création de copie multiples
» send/receive(socket): multicast de messages à un groupe
» open/read/write(file) : gestion de copies multiple copies
— Intergiciel à objet
» creation/init : création de copie multiples d’objets
» method call : multicast des requêtes d’invocation
» state access : l’état doit comprendre idéalement
- Les variables internes
- Les données de niveau intergiciel
- Les données de niveau noyau de système
• Properties
— Transparence et séparation entre application et mécanismes
— Quelques difficultés de ré-utilisation et de spécialisation
C-34
 Le projet DELTA-4 (Esprit #2252)
Definition and Design of an open Dependable Distributed
architecture
« L'objectif commercial de ce projet est de créer une capacité européenne de
produire des systèmes informatiques tolérant les fautes qui soient compétitifs
au niveau mondial pour leur coût, leur sûreté de fonctionnement et leurs
performances. Les applications visées sont celles des systèmes d'information à
large échelle, y compris ceux qui ont des exigences temps-réel : productique,
banques, centrales électriques, contrôle de trafic aérien, systèmes d'aide au
commandement militaires, etc. »
Partenaires
Ferranti CSL, UK LAAS-CNRS, F
Bull SA, F LGI-IMAG,F
CA, F MARI Ad. Electonics, UK
IFhG-IITB, G NCSR-AEA, UK
IEI-CNR, I Renault, F
INESC, P SEMA Group, F
Univ. Newcastle, UK
C-35
DELTA-4
• Objectifs: Tolérance aux fautes distribuée for “$-critical” systems
• Architecture à base de
— Stations de travail COTS (Commercial Off-The-Shelf) sous UNIX
— Contrôleur d’accès au réseau spécifique (Network Attachement
Controller)
• Stratégies réplication : passive, semi-active, active (s)
• Approche Middleware
— modèle objet, an IDL (Interface Definition Language) + services
— CORBA-like
• Efforts de validation significatifs par injection de faute
C-36
 Architecture ➠ T-à-F
off-the-shelf processeurs + Unix Unités de réplication ➙ objets
Host Host Host Host Host
NAC NAC NAC NAC NAC
Local Area Network
LAN standard
« Network Attachment Controller » à silence sur
défaillance • 802.4 token bus
• Autotests logiciels • 802.5 token ring
• Protection mémoire
• Duplication-comparaison
C-37
Protocoles
• Atomic Multicast Protocol (AMP)
— implémenté niveau 2 (au dessus du MAC)
— data frames envoyées à des portes logiques identifiant les groupes
— Assurance de l’unanimité, ordre et appartenance
— Protocole d’acceptation à deux phases
— Détection par timeout
— Répétition pour tolérer un nombre fini de fautes d’omission
• Inter-replica Protocol (IRP)
— Serveurs répliqués transparents aux clients (transparent multicast)
— Réplication à la source (clients) caché aux destinations
» arbitration entre événements émis ➱ message unique
» comparaison de signature ➱ détection et compensation
C-38
 Traitement d’erreur
Réplication Active
• Traitement déterministe des messages
• Silence sur défaillance — l’un quelconque des messages
• Défaillance incontrôlée — détection d’erreur et compensation (IRp)
Réplication Passive
• Un primaire et plusieurs backups
• Checkpointing systématique lors de l’émission d’un message du primaire
• Nécessite le silence sur défaillance mais pas le déterminisme
• Multicast atomique des messages et des points de reprise
Réplication Semi-active
• Un leader et plusieurs followers - le leader produit les messages
• Non-déterminisme résolu par des notifications leader-to-follower
• Extension à l’hypothèse de défaillance incontrôlée (comparaison-arrêt)
C-39
PBR
request message
group
reply message
message copies delivery
active to all correct members

t
me kpoin
mode

ges
PRIMARY

ssa
c
passive

che
I/P msg
mode updating the
object state
O/P msg CKP BACKUP(S)
O/P msg CKP À toutes les répliques: AMP
O/P msg CKP Au client et à toutes les répliques: AMP
C-40
 LFR
request message
group
reply message
message copies delivery
to all correct members
ges on

active
i
me nisat

mode
LEADER
ssa
o
chr

I/P msg passive

mode updating the
syn

object state
FOLLOWER(S)
Notification à toutes les répliques: AMP
O/P msg Au client et à toutes les répliques: AMP
C-41
TMR
request message
group
reply messages
• Propagate-before-validate
— Toutes les copies traitent les M1 M2 M3
messages d’entrée et produisent
un message de résultat
— Le vote à lieu à la destination
• Validate-before -propagate S2
— Toutes les copies traitent les M1
S3
messages d’entrée et produisent
un message de résultat Si Sig(M1)= S2 ou S3 alors
— Validation entre les serveurs send (M1)
» Échange de signatures Sinon
électroniques get(M2) ou leader(2)
» Notion de leader qui vote sur les send (M2)
signatures sur le NAC finsi Fail-silent NAC
» Emission d’un seul message au
client
C-42
 Validation expérimentale
D Pred. T Pred.
100% T Predicate:
Protocole de réplication OK
80% (tolérance et confinement d’erreur)
60% NAC D Predicate:
"duplex"
Auto-extraction !
40% de la station injectée
NAC Std
20% !?
0%
10ms 100ms 1s 10s 100s Std Duplex
Errors tolerated,
12% but not detected
Injection Physique
(Pin-Level fault injection) 94% 85% 99%
–MESSALINE– F E D T
87 ms 1,8 s
6% 3% 1%
1) “Standard” Errors detected,
[autotest logiciel] Non significant Failure but not tolerated
experiments
2) Duplex Arch. Mean Latency and dormancy
[duplication/comparaison] C-43
Leçons
• Leçon 1
— Réplication active et connexion au monde réel
— Vote sur senseurs ou pilotage par vote d’actuateurs
— I/O sur nœud unique ➱ fail silence
— Couverture faible ➱ non disponibilité, etc.
• Leçon 2
— autotest duplex et comparaison ➱ couverture de détection 96%
— Difficulté majeure: low-level LAN controller chips
• Leçon 3
— implémentation AMP niveau 2 ➱ rapide
— implémentation AMP niveau 2 ➱ non distribution de Delta-4.
• Leçon 4
— Démonstration en vrai grandeur Software-implemented distributed FT
— Problème de performance / solutions matérielles
— Intérêt économique et flexibilité de la solution
C-44
 Tolérance aux fautes du logiciel
• Redondance temporelle
— Répétition de l’exécution pour tolérer les fautes temporaires du
support d’exécution
— Exemple: exception “no more memory buffers is available at the time
of the call”.
— Deux types de répétition
» Répétition locale (fautes temporaires de ressources)
» Répétition sur autre support d’exécution pour des fautes persistantes
processing
step
checkpoints ! !
recovery re-start
point exception or execution
error status
Executive support Executive support
node 1 node 2
Time C-45
Redondance temporelle
• Détection
— mécanismes de détection d’erreur internes au composant,
conduisant à des exceptions
— assertions exécutables externes analysant la validité des résultats
produits et de leur cohérence vis-à-vis des entrées et du contexte
opérationnel.
• Ré-execution et tolérance aux fautes
— En fait, la ré-exécution s’effectue sous des conditions
opérationnelles différentes
— Ne tolère pas les fautes dures de conception
• Exemple
— Cette approche à été développée par AT&T Labs sous la forme
d’une bibliothèque de fonctions libft et d’un processus système
Unix watchd, et appliquée en particulier dans des systèmes de
télécom.
C-46
 Tolérance aux fautes de conception
• Recovery blocks [Randell 1975]
— variantes sont appelées des « alternats »
— algorithme de décision ou « test d’acceptation » (acceptance test)
est appliqué séquentiellement aux résultats produits par les
alternats.
— Si le test d’acceptation déclare que les résultats sont erronés, le
second alternat est exécuté, ainsi de suite, jusqu’à épuisement des
alternats disponibles. Dans ce cas extrême, le bloc de
recouvrement est déclaré défaillant.
A1 A2 A3
Non
OK
Test d’acceptation
OK
C-47
Tolérance aux fautes de conception
• Recovery blocks [Randell 1975]
— variantes sont appelées des « alternats »
— algorithme de décision ou « test d’acceptation » (acceptance test)
est appliqué séquentiellement aux résultats produits par les
alternats.
— Si le test d’acceptation déclare que les résultats sont erronés, le
second alternat est exécuté, ainsi de suite, jusqu’à épuisement des
alternats disponibles. Dans ce cas extrême, le bloc de
recouvrement est déclaré défaillant.
A1 A2 A3
Non
OK
Test d’acceptation
OK
C-48
 Tolérance aux fautes de conception
• Recovery blocks [Randell 1975]
— variantes sont appelées des « alternats »
— algorithme de décision ou « test d’acceptation » (acceptance test)
est appliqué séquentiellement aux résultats produits par les
alternats.
— Si le test d’acceptation déclare que les résultats sont erronés, le
second alternat est exécuté, ainsi de suite, jusqu’à épuisement des
alternats disponibles. Dans ce cas extrême, le bloc de
recouvrement est déclaré défaillant.
Défaillance
A1 A2 A3 ?
Non
OK
Test d’acceptation
OK
C-49
Tolérance aux fautes de conception
• N-version programming [Chen & Avizienis 1978]
— variantes sont dites des « versions »
— algorithme de décision = un vote sur les résultats produits par les
versions.
— Les algorithmes de décision effectuent, par exemple, des calculs
de médiane en rejetant les valeurs aberrantes.
A1 A2 A3
Algorithme de décision
Valeur
C-50
 Tolérance aux fautes de conception
• N-self-checking programming [Laprie et al. 1990],
» au moins deux composants logiciels auto testables sont exécutés en
parallèle, chaque composant étant construit,
» soit sous la forme d’une variante et de son test d’acceptation,
» soit de deux versions avec un test de comparaison.
• Remarque
— Dans ce second cas, une seule variante peut être écrite dans le but de fournir des
résultats, l’autre effectuant la fonctions avec une précision plus faible, ou bien le calcul
inverse quand cela est possible, ou encore la vérification de résultats intermédiaires de
la variante principale (Certification Path Approach [Sullivan & Masson 1990]).
A1 A2 A1 A2
comparaison comparaison
Valeur OK sélection Valeur OK
C-51
Airbus 320
Commande 2 x ELAC ELevator and
Aileron Computer
28 V DC Thomson-CSF
68000
Mémoire Processeur E/S
3 x SEC Spoiler and
Elevator Computer
SFENA/Aérospatiale
Alimentation
80186
2 x SFCC Slats and Flaps
Computer
GEC Marconi
Alimentation 80C88 / 68000
2 x FAC Flight
Augmentation
Mémoire Processeur E/S Computer
SFENA
8086
Surveillance
C-52
 Airbus 320
SFCC1
Becs et
volets SFCC2
ELAC1
Ailerons
ELAC2
SEC1
Spoilers
SEC2
SEC3
Plan horizontal
Gouvernes de
profondeur
FAC1
Gouverne
de direction FAC2
C-53
Boeing 777
Spécification
fonctionnelle
• Primary Flight Computer (PFC)
du système de commande de vol
électrique du Boeing 777 Outils et Équipe de
règles programmeurs
— Ce système comporte trois PFC
identiques dans une
configuration à vote majoritaire. Programme source
— Un PFC est basée sur
l’utilisation de trois voies
utilisant des processeurs COTS Compilateur A Compilateur B Compilateur C
diversifiés (en l’occurrence, un
AMD 29050, un Motorola 68040 Exécutable A Exécutable B Exécutable C
et un Intel 486).
— Ces trois processeurs Exécutif A Exécutif B Exécutif C
exécutent un même programme Processeur A Processeur B Processeur C
applicatif
» écrit en Ada, Exécution A Exécution B Exécution C
» compilé par trois compilateurs
Ada différents,
Comparaison
➠ programmes exécutables et Comparaison
des exécutifs (run-times Ada)
différents pour les 3 proc.
Sorties Erreur Erreur C-54
 Boeing 777
Spécification
fonctionnelle
• Primary Flight Computer (PFC)
du système de commande de vol
électrique du Boeing 777 Outils et Équipe de
règles programmeurs
• En fonctionnement normal,
— l’une des voies du PFC joue le Programme source
rôle de voie de commande (une
voie différente est choisie dans
chaque PFC), Compilateur A Compilateur B Compilateur C
— les deux autres étant des voies
de surveillance. Exécutable A Exécutable B Exécutable C
Exécutif A Exécutif B Exécutif C
• En cas de désaccord,
Processeur A Processeur B Processeur C
— la voie fautive peut être
localisée et
Exécution A Exécution B Exécution C
— inhibée du fait de la présence
de deux voies de surveillance. Comparaison
Comparaison
Sorties Erreur Erreur C-55
ELEKTRA
• The Elektra Railway Signalling Spécification
fonctionnelle
Règles de sécurité
System
— Ce système est basé sur
Outils et Équipe de Équipe de Outils et
l’utilisation de deux chaînes de règles A programmeurs A programmeurs B règles B
traitement en tout point
identiques aux niveaux matériel
et exécutif Programme source Programme source
fonctionnel de contrôle
— Une des chaînes de traitement,
appelée « interlocking
processor » supporte le Compilateur A Compilateur B
traitement fonctionnel de Exécutable Exécutable de
signalisation fonctionnel contrôle
— L’autre chaîne, appelée Exécutif Exécutif
« safety bag processor », x3 x3
Processeur Processeur
exécute le traitement de
contrôle: assertions Exécution Exécution de
fonctionnelle contrôle
exécutables déduites des
règles de sécurité ferroviaires.
Comparaison
Sorties Erreur C-56
 ELEKTRA
• The Elektra Railway Signalling Spécification
fonctionnelle
Règles de sécurité
System
— Toute commande élaborée par
Outils et Équipe de Équipe de Outils et
la chaîne fonctionnelle est règles A programmeurs A programmeurs B règles B
transmise vers la périphérie et
vers la chaîne de contrôle.
Programme source Programme source
— Cette dernière transmet aussi la fonctionnel de contrôle
commande vers la périphérie
après avoir vérifié la conformité
de la commande par rapport Compilateur A Compilateur B
aux règles de sécurité. Exécutable Exécutable de
fonctionnel contrôle
— L’action correspondante n’est
exécutée qu’en cas d’accord Exécutif Exécutif
entre les deux commandes x3 x3
Processeur Processeur
transmises vers la périphérie.
• En pratique, Exécution Exécution de
contrôle
fonctionnelle
— TMR Interlocking processor
— TMR Safety Bag
Comparaison
Sorties Erreur C-57
Système de contrôle – Nucléaire
• Niveau 0 ➠ application Spécification Spécification ••• Spécification
nominale niveau défense 1 niveau défense N
nominale
• Niveaux 1..N ➠hiérarchie
de défenses. Équipe de Outils et Équipe de Outils et Équipe de
Outils et
règles 0 programmeurs 0 règles 1 programmeurs 1 règles N programmeurs N
• Défense niveau k ➠
contrôle du
Source 0 Source 1 Source N
fonctionnement des
niveaux 0,…, k-1, et mise
en œuvre par une
commande simplifiée Compilateur 0 Compilateur 1 Compilateur N
mais plus fiable, voire
seulement la mise à l’état Exécutable 0 Exécutable 1 Exécutable N
sûr, en cas de défaillance
d’un niveau inférieur. Exécutif 0 Exécutif 1 Exécutif N
Processeur 0 Processeur 1 Processeur N
• Contrôle des niveaux
0,…, k-1 est en fait Exécution 1 ••• Exécution N
indirect ➠ mis en œuvre Exécution 0
Comparaison Comparaison
au moyen de la
N-1
surveillance de variables Erreur Sorties N
Sorties 0 Erreur Sorties 1
pertinentes du procédé
commandé. PROCÉDÉ Erreur
$ Cette approche constitue, en quelque sorte, une généralisation de la technique du « safety bag ». La principale
différence consiste en l’observation indirecte des sorties du niveau inférieur, au travers du procédé commandé.
C-58
 Tolérance aux intrusions
• Problématique
— Garantir l’intégrité et la confidentialité de l’information
— La redondance est une entrave à la garantie de ces propriétés
L’idée
— Fragmenter l’information de façon à produire des fragments non
significatifs (non-confidentiel)
— Disperser l’information de façon redondante sur un réseau de
calculateurs
• Application
— À la messagerie: fragmenter et router les fragments par des liens
différents (fragmentation des communications de Koga)
— Aux clés: fragmenter les clés de façon à ce qu’un sous-ensemble
seulement soit nécessaire pour reconstruire une clé secrète
(notion de schémas à seuil de Shamir)
— Aux fichiers, à la gestion des autorisations, aux traitements (notion
de Fragmentation-Redondance-Dissémination)
C-59
Schéma à seuil de Shamir
• Le problème :
— stockage de clés secrètes ➠ confidentialité, disponibilité
• Une solution qui n’est est pas une!
— plusieurs zone protégées dans lesquelles on réplique la clé
$ violation d’une zone ➠ perte du secret
• L’idée des schémas à seuil:
— Stocker K sous la forme d’un ensemble de valeur Ki (appelées
images), telles que:
» S images permettent de reconstruire le secret
» S-1 images n’apportent aucune information
— Si l’on sait générer N images, avec N>S alors, N-S images peuvent
être perdues
C-60
 Schéma à seuil de Shamir
• Exemple simple (S=2)
$ y = a x + b = P(x)
y4
» y0 = a x 0 + b
y3
» y1 = a x 1 + b
y
2 •••
y
1 » yn = a x n + b
y0 $ Posons a, b secrets et x1, x2,…
xn fixés
• Généralisation ➠ polynôme de
x0 x1 x2 x3 x4 degré S:
( x − xj ) mod q
∑ y ∏ ( )
1≤i≤k i1≤ j≠ i≤k ( xi − xj)
On sait générer autant de valeurs que l’on veut! P(x) =
Interpolation polynomiale de Lagrange C-61
Fragmentation-Redondance-Dissémination
Sites
Réseaux de utilisateurs
communication
.
..
...
Sites de ? ?
sécurité ?
? ?
? Sites
Sites de ? ? ... d'archivage
traitements ?
? ?
?
C-62
 FRD (Fichiers)
Fragmentation Réplication Dissémination
s2drtz9t
Chiffrement nuazt8zt
adodh23e
Nommage •
•
h4sfg6g1 •
Fichier Fragments
Site utilisateur
Réseau à diffusion
Sites d'archivage
Chiffrement (F) ➠ distribution ➠ chiffrement des noms ➠ dissémination aléatoire (R copies)
C-63
Serveur de sécurité tolérant aux intrusions
AUDIT RECOUVREMENT
AUTHENTIFICATION GESTION des INFOS
SENSIBLES
AUTORISATION
SERVEUR
SITE
UTILISATEUR SERVEUR
C-64
 Authentification
Vote
Site de Site de Site de
sécurité sécurité sécurité
C-65
Autorisation
Serveur de Sécurité
Site de Site de Site de
sécurité sécurité sécurité
(1) REQUETE (2) VOTE
(3) TICKET (5) TICKET
UTILISATEUR
SERVEUR
(4) AUTHENTIFIEUR
DE SESSION
Serveur Sécurisé
(6) SESSION
C-66
 La tolérance aux intrusions
Un sujet d’actualité…
• Des programmes gigantesques:
Organically Assured and Survivable Information Systems (OASIS)
Defense Advanced Research Projects Agency (DARPA)
Tolérance aux fautes, tolérance aux intrusions, détection d’intrusions,etc.
• Des exemples de projets dans ce cadre
DARPA ISO Sponsored Research
2000 Project Summary
SRI,
Draper Labs,
« Dependable Intrusion Tolerance » Etc.
« Intrusion Tolerant Software Architectures »
« Intrusion Tolerant Distributed Object Systems »
« Intrusion Tolerance Using Masking, Redundancy and Dispersion »
C-67
Résumé
• Différentes techniques permettent de tolérer des fautes, en fait
l’effet de ces fautes sur le comportement du système (les erreurs)
• Fautes physiques ➠ techniques de réplication
— Hypothèses de fautes
— Couverture des hypothèses
— Notion de composant autotestable
— Techniques de réplication passive, semi-active, active
• Fautes du logiciel ➠ techniques de diversification
— Redondance temporelle (fautes transitoires de support) ➠ AT&T
— Recovery blocks
— N-Version programming ➠ Airbus 320, 330, 340, Boeing 777
— N-Self Checking programming ➠ Elektra
• Intrusions ➠ fragmentation-redondance-dissémination
C-68
 Techniques de caractérisation
Techniques de base,
en particulier par injection de fautes,
Analyse de robustesse,
exemples d'outils et de résultats expérimentaux
D-1
Rappel Test de la tolérance aux fautes
• Les mécanismes de tolérance aux fautes sont à la fois
— Faillibles (fautes de conception et/ou de réalisation)
— Conçus pour traiter des entrées spécifiques: les fautes!
! leur vérification est essentielle!
• L’approche expérimentale par injection de fautes
— Simulation des fautes, ou plutôt de leurs effets, les erreurs
» physiques (bit-flip) ou du logiciel (mutation d’instruction)
— Cibles: un composant logiciel équipé de son mécanisme de TAF
» Boite blanche: visibilité structurelle (comment il est fait) et
comportementale (comment il agit/ré-agit)
» Boite noire: aucune connaissance, seules les interfaces sont visibles
— Les types d’injection:
» niveau physique(stuck-at), modèle (VHDL) ou par logiciel (SWIFI)
— Les problèmes:
» Représentativité des fautes
» Observation et analyse des résultats.
D-2
 Les techniques d’injection de fautes
Rappel
système ➠ DEPEND, REACT, ...
niveau RTL ➠ ASPHALT, ... Nœuds ➠ ORCHESTRA
porte logique ➠ Zycad, Technost, ... tâche ➠ FIAT
circuit ➠ FOCUS, ... instr. ➠ FERRARI
... mém. ➠ DEF.I, DITA,
large spectre ➠ MEFISTO, SYSTÈME CIBLE MAFALDA
VERIFY(VHDL) Reg. ➠ Xception
Modèle Prototype
M Logique & injection injection
O Information en simulation en logiciel
Y
E ≈
injection
Physique
N physique
ions lourds ➠ Université Chalmers
perturbations EM ➠ TU Vienne
broches ➠ MESSALINE, Scorpion,
DEFOR, RIFLE, AFIT,...
D-3
Evaluation expérimentale
Sûreté de fonctionnement Tolérance aux fautes
(SdF) (TF)
# Impact sur mesures SdF # TF construction faillible
# Calibration des modèles # Estimation couverture TF
# Limites appr. formelles # Approche expérimentale
# Entrave événement rare # Expériences contrôlées
Injection de fautes
D-4
 Les attributs de l'injection de
fautes
# Test des mécanismes de TF vis-à-vis d'entrées spécifiques : les
fautes
# Séquence de test = série d'expériences élémentaires
# Caractérisation d'une expérience
Faute Erreur Défaillance
tF Dormance tE Latence tD
Traitement Erreur/Faute approprié (Prédicat P)
Domaine d'entrée Domaine de sortie
• f ∈ F Fautes à injecter • r ∈ R Relevés et observations des
•a∈A Données d'entrée destinées prédicats caractérisant :
- les mécanismes de TF
à activer le système
- le système cible
Élaboration de mesures expérimentales : l'ensemble M D-5
Caractérisation des prédicats de
la TF
• Définition de prédicats et d'un ensemble d'états
F E D T OK
Défaillance
• Test des prédicats
Assertion de P
Faute
∅ P = faux P = vrai ∅ v0 v1
tF tP t Max P = faux P = vrai
Domaine d'observation : T
∅ P = vrai ∅ v1 v0
t Max P = vrai P = faux D-6
tF
 Rôle de l’injection de fautes
VÉRIFICATION ÉVALUATION
Test de l'adéquation ... Estimation de l'efficacité
...
... de la conception et/ou mise en œuvre
des algorithmes/mécanismes de tolérance aux fautes ...
... par rapport aux hypothèses de facteur de couverture,
fautes dormance faute, latence erreur, ...
Élimination des fautes Prévision des fautes
(déficiences) de la TF (mesures de la SdF)
D-7
Elimination des fautes dans les MTF
Finj
Hpre
Hpost
Déficience Couverture Déficience
Couv. hyp. Nominale Fausse
alarme ?
[attendu?]
“Bonus” de Comport.
Déficience nominal
couverture couverture
Tests Tests
avec injection sans injection
de fautes de fautes
D-8
 Distribution temporelle de la
couverture
Faute Succès
Traitement
Erreur/Faute
Échec 2ème Faute
Défaillance Défaillance
100%
Couverture C ≈ C(T) < C(∞)
C(t) facteur de
couverture
asymptotique
[ ] temps de
D-9
Domaine d'observation latence
E[TMTF ]
tf T
Estimation de la couverture
tf tp t max
t Expériences ≈
0 P T Épreuves de Bernouilli
F
n 0 d
X G MTFs y (tP, G)=  événements
Exp. 1 significatifs
A
Var. aléatoire TP :
instant d’assertion
(tP ≤ T)
n d du prédicat P
n1 G1 d1 ➢ Distribution de la couverture :
n2
G2
d2 n
1 N(t)
Cˆ 1(t,G) = n ∑ y(t, Gi) = n
•
•
•
ni
Gi di
i=1
• ➢ Valeur asymptotique (facteur de couverture) :
•
• d
N(T)
GM C(∞,G) = C(G) ≈ Ĉ1(T,G) = =
nD-10
nM dM n
Influence du facteur de couverture
1ère défaillance (couverte)
2 unités 1 unité
C1 actives active
E S
réparation
2ème défaillance
C2
1ère défaillance
(non couverte) Défaillance
système
104
MTTFSyst.
3
MTTFComp. 10 c=1
c = .999
c = .995
10 2
c = .99
10
1 c = .95 MTTRComp.
c = .9 MTTFComp.
1 D-11
10-4 10-3 10-2
Evaluation de la robustesse
D-12
Architecture des systèmes
Objets d’application
Interagissant par
messages
Intergiciel (e.g. CORBA)
Intergiciel supportant la distribution
transparente des objets
Système opératoire Système opératoire
(e.g. POSIX)
Micro-noyau temps-réel Micro-noyau
Temps-réel
D-13
Intergiciels
Evaluation de la robustesse des Intergiciels
par injection de fautes
D-14
 Intergiciel
• Injection avant encapsulation par TCP.
➣ Simulation de la proportion de paquets erronés délivrés par TCP
D-15
Comparaison d’intergiciels CORBA
Percentage per SUB
Non Reported Reported Failure
Failure (CORBA Exceptiion raised)
(No
diagnosis)
Bit flip dans les requêtes IIOP
D-16
 Système opératoire
Evaluation de la robustesse des exécutifs POSIX
Avec Ballista
D-17
Carnegie Mellon
University, USA BALLISTA
• Objectif
— Test automatique des fonctions d’un système opératoire (API)
— La cible est l’ensemble des appels système invoqués par les
applications
Comportement Espace Espace réponse
attendu d’entrée
Correct Entrées Opération robuste
valides

posix
UNIX Défaillance
Indéfini répétable
Entrées
invalides Défaillance
Incorrect Non répétable
➠ erreur code
Ballista effectue l’injection de faute au niveau API en
utilisant un combinaison de paramètres valides et invalides
D-18
 L’échelle CRASH
• Réponses incorrectes regroupées selon 5 niveaux
— C - Catastrophic: la défaillance n’est pas confinée à une seule
tâche (i.e., l’appel à une fonction de l’ OS a causé le crash ou le
hang d’une autre tâche ou du système)
— R - Restart: la tâche est bloquée et doit être re-démarrée
— A - Abort: terminaison anormale de tâche (e.g., segmentation
violation)
— S - Silent: la tâche termine sans signaler d’erreur (e.g., un appel à
openfile avec un nom de fichier NULL devrait retourner une erreur)
— H - Hindering: la tâche renvoie un code d’erreur incorrect
D-19
Expériences
Tests appliqué à 175-233 des appels POSIX sur chaque OS
• Exemples de paramètres invalides
— Type integer et descripteurs de fichier :
» not in range,0,1,-1,+maxint, -maxint
— Type pointer :
» null, -1, hors zone d’adressage de buffer mémoire
— Type string :
» large (64K), format incorrect (filenames, modes, printf)
• Résultats
— Comparaison sur l’échelle C-R-A-S-H
— Exemples de situations surprenantes :
» mmap sur HP-UX (dirty parameters) --> system panic
» setpgid sur LynxOS (parameters combination) --> system crash
— Seulement entre 37% et 58% des cas de test n’entraînent pas de
défaillance
D-20
Système opératoires POSIX
15 « (C)OTS » OSs
[Koopman & DeVale 99 (FTCS-29)]
AIX
AIX
FreeBSD
FreeBSD
HPUX
HP-UX 9.05
B.9.05
Abort
Abort %
HP-UXPUX 10.20
B.10.20
Silent
Silent %
Irix5.3
Irix 5.3 Restart
Restart %
Irix6.2
Irix 6.2 Catastrophic
Catastrophic
Linux
Linux
LynxOS
Lynx
NetBSD
NetBSD
OSF-13.2
OSF-1 3.2
OSF-1
OSF-14.0
4.0 9
QNX
QNX4.22
4.22
QNX
QNX4.24
4.24
SunOS
unOS4.13
4.13
SunOS5.5
SunOS 5.5
00% 10
10% 20
20% 30
30% 40
40% 50
50%
Normalized failure rate (%)
Paramètre invalide dans les appels systèmes POSIX D-21
Micro-noyaux temps-réel
Evaluation de la robustesse de micro-noyaux temps-réel
Avec Mafalda
D-22
 Principe
Microkernel
Assessment
Detection by Fault injection Functional models
Executables assertions
Propagation
Failures
AnaLysis Wrappers
Reflexive
Execution traces implementation
Design Aid
MAFALDA
D-23
Description-1
Machines cibles
Machine contrôleur
Wp1 Wp2 Wp3
Campaign_FD controler
Workload_FD metakernel
Wrapping Injection Interception
Graph Exp. results Log. files Internal
Reflection COTS Function
mgr. Microkernel Call
Pilote de toutes les étapes:
1) Génération Oracle
Tableur 2*) Série d’expériences
3) Analyse
Information de
trace pour analyse
Modes de
a posteriori
défaillance D-24
 Description-2
Machines cibles
Machine contrôleur
Wp1 Wp2 Wp3
Campaign_FD controler
Workload_FD metakernel
Wrapping Injection Interception
Graph Exp. results Log. files Internal
Reflection COTS Function
mgr. Microkernel Call
Vérification des
Interception
assertions exécutables Bit-flip: des system calls,
parameters, de leurs paramèters,
segments code et de quelques
Introspection
& data fonctions internes
Intercession D-25
Analyse des modes de défaillance
Evaluation Observation
• Robustesse de l’interface • Comportement d’un module
• Mécanismes de détection • Propagation inter-module
Cibles de l’injection Résultats
• Appels système • Statistiques
• Composants noyau • Analyse de trace a posteriori
Modèle de faute Workload
...
SYN COM MEM
• Corruption données d’entrée
Application
• Corruption du micronoyau Fault
(segments code & data) microkernel interface
propagation
Type de faute ... Error
SYN COM MEM
• Bit-flip Fault
• Aléatoire Microkernel components
D-26
 Comportement en présence de fautes
Corruption
externe ! Défaillance Application
(Application) (valeur et ordonnancement)
! Application Hang
Application / middleware Propagation
API
Microkernel
Erreur
! Blocage noyau
Corruption
interne ! Signal (détection)
Propagation " Error Status
Erreur " Exceptions
µkCi µkCj
D-27
Caractérisation de micronoyaux temps-réels
Micro-noyaux Chorus and LynxOS
Chorus
LynxOS
45
40
35
30
% 25
20
15
10
5
0 Appli. Appli. Kernel Exception Error No Obs
Failure Hang Hang Status MAFALDA
Bit flips dans les segments de code du noyau
D-28
 Exemple de mesures
D-29
Catégories d’observation comportementale
FAILURE
9%
Non Significant
Experiments APPFAIL
9,0% APPHANG
28.5% NO OBS.
6,0%
28,5%
SYSHANG
1,4%
HANG
3010 KDB
Exp. 13,9% 21.3%
ERROR
STATUS
3,0%
EXCEPTION
38,1%
DETECTION
41.1%
D-30
 Kernel
Distribution d’erreur code
FAILURE
9%
Non sign.
28.5% HANG
3010 21.3%
exp.
DETECTION
41.1%
FAILURE FAILURE
2.4% SYNCHRONISATION
HANG 3.6% HANG
Non sign. 7% 10.3%
Non sign.
33% 31.3%
2924 2970
exp. exp.
DETECTION
57.7% DETECTION
55%
MEMORY COMMUNICATION
D-31
Kernel
Propagation d’erreur code
84,2% AF Application Failure
COM 0% EXC Exception
63.3 % 15,8% ES Error Status
(30/3010) SYN
36.7 % 100%AF
MEM 0% EXC
0% ES
8,9% AF (26/2970)
COM 77,2%EXC 57.7 % COM
13,9%ES
32,5%AF 100%AF
SYN 61,3%EXC SYN 0% EXC 43.3 %
6,2% ES 55,8 % 0% ES
100%AF
MEM MEM 0% EXC
44,2 %
(181/2924) 0% ES
D-32
 Kernel
Latence des exceptions code
40 100
0 %
80
Cumulative Distr.

30
# EXceptions

%
0
60
20 %
0 40
%
10
0 20
%
0 0
0 1 2 3 4 5 6 7 8 9 1 %
0 >1
microseconds
0
D-33
MAFALDA in action
D-34
 The Oracle
D-35
Fault Injection
D-36
 Résultats
D-37
Synthèse (1)
• Définition de la charge applicative et Oracle
— Option 1: charge applicative indépendante d’une application
» Principes
- Activation de toutes les fonctions
- Séparation / partitionnement pour détecter la propagation d’erreur
- Conçu pour pouvoir obtenir un Oracle
» Intérêt
- Identifier des fautes de conception/programmation
- Identification de comportements/modules faibles
» Inconvénient
- Ne reflète pas le comportement / profil typique d’une application
— Option 2:
» Définition d’un profil d’application (application elle-même?)
» Définition de l’Oracle?
D-38
 Synthèse (2)
• Injection de fautes
— Principes
» Sélection aléatoire du bit inversé (bit-flip)
— Injecteurs
» Noyau
- Utilisation des moyens de debug des processeurs modernes
- Octet aléatoire et sélection bit
- Optimisation:
! Frontière des composants
! Flot de contrôle du noyau
» Paramètres
- Interception des appels noyau (librairies & trap)
- Octet aléatoire et sélection bit
— Sélection pré-définie d’adresses, de valeurs, de différentes
combinaisons possibles
D-39
Synthèse (3)
• Assertions et wrappers de confinement
— Formalisation des comportements corrects attendus
— Implémentation: vérification en-ligne
» Dérivation d’assertions exécutables
» Dérivation de AFSM (Abstract Finite State Machine)
— Efficacité
» Précision du modèle
» Type de formalisme
— Performance
» Compromis entre modélisation et surcharge temporelle
— Expressions en logique temporelle interprétées par un Runtime
checker
-> MAFALDA-RT
D-40
 Synthèse (4)
• Analyse de l’information brute observée
— Les résultats statistiques procurent des informations significatives
pour la sélection d’un candidat
— L’information détaillée permet:
» Identification des fautes de conception / programmation
» Compréhension du comportement réel en présence de fautes :
- Pourquoi une erreur conduit à la défaillance ?
- Pourquoi a-t-on observé un executive hang?
- Pourquoi l’erreur s’est-elle propagée d’un composant à un autre?
— Scripts permettant de filtrer les information brutes obtenir par les
mécanismes de traçage
— Les utilisateurs peuvent eux-même définir les modes de
défaillance.
D-41
Synthèse (5-6)
• Interprétation des résultats
— Une campagne cible :
» Une seule instance d’un micro-noyau temps-réel
» Un certain profil d’activation
— Variabilité des résultats
» Version Stand Alone vs. version Posix
» Application réactive vs. Application static
• Evolution des systèmes cibles
— Nouvelle instance -> Nouvelle campagne ?
— Est-ce que la nouvelle instance est compatible avec la solution
architecturale ?
D-42
 Mafalda-RT
Limitation of
temporal intrusiveness Microkernel Formal spécification
(temporal logic)
Detection
Aut. translation
Propagation Assessment
On-line Checking
Failures by Fault injection Wrapping
(value & time)
mechanisms
Execution traces
AnaLysis • detection
Temporal • recovery
characteristics Reflective
of kernel
Design Aid implementation
(e.g., switching time)
Explicit analysis
Analysis of scheduling of temporal
of captured events overhead
for Real-Time systems D-43
Empaquettage
Notion de wrappers
D-44
 Principe du wrapping
wrapper
Microkernel
Input Output
module
— Mécanismes d’encapsulation (wrappers), par classes fonctionnelles
— Modélisation du comportement de fonctions/services de base d’un
micro-noyau temps-réel en l’ absence de faute
➠ notion d’assertion exécutables, de prédicat vérifié en-ligne
» Observation de données et événements internes
» Contrôle de certaines actions du noyau
— Nécessité de mécanismes d’observation et de contrôle étendus ➠
notion d’implémentation réflexive (instrumentation)
— Mesure de l’efficacité des wrappers par injection de faute D-45
Exemple de wrapper fonctionnel: Synchronization
Sémaphores: Soit #P(s) et #V(s) le nombre total d’appels à
P(s) et V(S)
- integer [Link]
- process queue [Link] [Link]= init_value - #P(s) + #V(s)
Opérations: Soit #Suspended (s)
le nombre de threads dans [Link]
- Init: I (s)
- Get: P(s) #Suspended (s) = max(0, -[Link])
- Release:V (s)
Valeur init init_value
P(s) V(s)
Un prédicat peut être défini comme suit:
Wrapper
[[Link]= init_value - #P(s) + #V(s)] ξ
Micronoyau SYN [#Suspended(s) = max(0, -[Link]) ]
D-46
Exemple de wrapper comportemental: Scheduling
CREATE(Ready)
Stopped Ready to Run Running
CREATE(Stopped) START ()
STOP ()
DELAY(NoDelay)
SETPRIORITY()
SEMV() SEMP()
Internal preemption DELAY(TimeDelay)
Time-Out RECEIVE()
Event-Message
Waiting
Post-condition associée
à une transition correcte
Politique préemptif FIFO
After SEMV(S) :
t ∉ W(s) ∧ P_Sched (•) =
t∈ R∧ La tâche en cours est toujours la première
P_Sched (•) de celles de plus haute priorité dans la file
ready_to_run
D-47
Impact de l’encapsulation
~ 3000 expériences
Module de SYNCHRONISATION
100%
87%
Application failure
80%
External errors Internal errors
60%
Intérêt….
40%
• empêche la corruption de paramètres
• réduit le nb d’erreurs non-détectées et leur propagation
20%
9%
2.2%
0% 0.5%
0%
Standard SYN Wrapper SYN & SCH
Wrappers
D-48
 Impact de l’encapsulation
Efficacité des wrappers
~ 3000 expériences
• tâches non réveillées
• violation de règle de préemption
• violation de règle d’élection
Module de SCHEDULING • manipulation incorrecte de files
25%
23%
20% Standard module Wrapped module
Cause des défaillances résiduelles 15%
15%
• mauvaise priorité
• non-capture d’événement
• thread hang
10%
• flot d’exécution incorrect
7%
5%
5% 4%
2% 3%
1%
0%
Application Application System hang Total
failure hang
D-49
Etalonnage de la SdF
Dependability
Assessment
≈ Dependability
Benchmarking
Performance
Benchmarking
Desired Properties
Agreement/Acceptance
Usefulness
Fairness
Usability
Portability
etc. D-50
 Cadre conceptuel
Analyse
B
A
Modélisation Mesures de la
SdF
Fautes Système
Charge cible Mesures expérimentales
Expérimentation
DBench
Dependability Benchmarking
IST 2000 25425 D-51
[Link]
Résumé des techniques de base
Propag. Φ-device level ➠ RTL
-> Fautes physiques Simulation
Analyse
VHDL
Paramètre Bit-flip ds
-> Fautes du logiciel Bit-flip ds
d’appel Paramètre
paramètre invalide Fonct. Int.
(OS, micronoyau)
Fautes ds
Drivers
-> Fautes du logiciel Mutation Mutation
Bas-niveau haut-niveau
(Niveau application)
-> Fautes d’opérateur & Script Fautes
réelles
et d’administrateur d’émulation (field data)
DBench
Dependability Benchmarking D-52
 Sûreté de fonctionnement
Résumé et conclusion
Jean-Charles Fabre
Méthodes et techniques permettant de considérer les fautes
comme des événements naturels et prévisibles!
Tel: 05 61 33 62 36 - Fax: 05 61 33 64 11 - E-mail: fabre@[Link]
E-1
Informatique sûre de fonctionnement
• Tolérance aux fautes : «zéro défaut » « zéro défaillance »
• Émergence d’autres classes de fautes :
— de Conception
— Interactions Homme-Système
— Malveillances
• Compromis entre [coût + fonctionnalité]
et sûreté de fonctionnement
— Hiérarchie de la tolérance aux fautes + confinement des erreurs
— Équilibre matériel/logiciel
— Transparence
— Généricité et réutilisation (composants “OTS”)
• Évaluation analytique & expérimentale du comportement
en présence de fautes “Benchmarking” de la SdF
E-2
 Synthèse
Hypothèses et modèle de faute
Composant autotestable
Techniques de réplication
Diversification
Mécanisme de TAF
Modèle, Prototype Type de Fautes
Outillage de caractérisation Mesures (couverture,
modes de défaillance)E-3
Sûreté de fonctionnement
des systèmes informatiques
industriels
Jean-Charles Fabre
Méthodes et techniques permettant de considérer les fautes
comme des événements naturels et prévisibles!
Tel: 05 61 33 62 36 - Fax: 05 61 33 64 11 - E-mail: fabre@[Link]
E-4