Embed Size (px)
Citation preview
1
Test orienté propriété basé sur leRecuit Simulé
Résultats Expérimentaux
Olfa ABDELLATIF-KADDOUR, Pascale THÉVENOD-FOSSE
et Hélène WAESELYNCK
Féria-SVF, 5 Février 2002
2
Plan
� Objectif
� Techniques d’optimisation pour les
problèmes combinatoires
� Adaptation du Recuit Simulé
� Étude de cas : la chaudière
� Conclusion et prospective
3
Objectif
� Définition d’une méthodologie de conception deprofils de test statistique susceptibles demettre en défaut une propriété de sécurité-innocuité
Logiciel
EnvironnementEntrées
={ Activité + Fautes }
4
� Longueur des séquences ?
� Construction par étape
� Méthode pour guider l’exploration à chaque étape ?
� Heuristiques d’optimisation
Problématique
… …
Situation dangereuse
5
Techniques d’optimisation
� Techniques utilisées dans le cas du test� Recuit Simulé� Algorithmes Génétiques
� Applications [Tracey et al.]
� Traitement d’exception
� Couverture structurelle
� Couverture de prédicats Avant-Après
Limitation à des problèmes combinatoires etdes propriétés locales
6
Algorithme du Recuit Simulé
� Fonction de coût
➥ Mesure la “distance” d’une
solution par rapport à l’objectif
� Génération dans le voisinage
� Processus de refroidissement
➥ Taux d’acceptation des
mauvaises solutions
Initialisation(Solution_Courante,Température)Calcul du Coût_CourantLOOP Génération (Nouvelle_Solution) Calcul du Nouveau_Coût IF Nouveau_Coût < Coût_Courant THEN Solution_Courante=Nouvelle_Solution ELSE IF Exp(Coût_Courant - Nouveau_Coût) /
Température ) > Random (0,1) THEN -- Accepter Solution_Courante=Nouvelle_Solution
ELSE -- Ne pas accepter
Diminution de la TempératureEXIT When STOP_CRITERIONEND LOOP
7
Test d’une propriété [Tracey et al.]
Procedure Wrap_Inc (N : in out Integer); --# pre N~ ≥≥≥≥ 0 and N~ ≤≤≤≤ 10; . . . --# post (N~ < 10 →→→→ N = N~ + 1) and --# (N~ = 10 →→→→ N = 0); end Wrap_Inc
Procedure Wrap_Inc (N : in out Integer); --# pre N~ ≥≥≥≥ 0 and N~ ≤≤≤≤ 10; . . . --# post (N~ < 10 →→→→ N = N~ + 1) and --# (N~ = 10 →→→→ N = 0); end Wrap_Inc
N~=2 & N=3 N~=10 & N=11N~≥≥≥≥ 0 0 0
N~≤≤≤≤10 0 . . . 0
N~=10 8+K 0
N ≠≠≠≠ 0 0 0
Élément Coût Booléen if TRUE then 0 else K
a = b if abs(a-b) = 0 then 0 else abs(a-b) + K
a ≠≠≠≠ b if abs(a-b) ≠≠≠≠ 0 then 0
else K a < b if a-b < 0 then 0
else (a-b) + K a ≤≤≤≤ b if a-b ≤≤≤≤ 0 then 0
else (a-b) + K a > b if b-a < 0 then 0
else (b-a) + K a ≥≥≥≥ b if b-a ≤≤≤≤ 0 then 0
else (b-a) + K a ∨∨∨∨ b Min(coût (a), coût (b))
a ∧∧∧∧ b coût (a) + coût (b)
¬¬¬¬ a Négation propagée sur a
Objectif : pre ∧∧∧∧ ¬¬¬¬post
N~≥≥≥≥0 ∧∧∧∧ N~≤≤≤≤10 ∧∧∧∧ (N~<10 ∧∧∧∧ N ≠≠≠≠ N~+1) (1)
N~≥≥≥≥0 ∧∧∧∧ N~≤≤≤≤10 ∧∧∧∧ (N~=10 ∧∧∧∧ N ≠≠≠≠ 0) (2)
8
� Combinatoire ⇒⇒⇒⇒ Séquentiel
Entrée individuelle ⇒⇒⇒⇒ Séquence d’entréesCoût ?
� Propriété de haut niveau
➥ Violée / Pas Violée
���� Notion de « situations potentiellement dangereuses »
➥ Coût modulé
➥ Poursuivre les tests à partir des séquences stressantes
Adaptation du " Recuit Simulé "
9
� Étape 1
Chercher des séquences de test menant :
soit à une violation de la propriété
soit à une situation dangereuse
� Étape i+1
A partir de chaque situation dangereuse
trouvée à l’étape i, poursuivre les tests
Stratégie de test proposée
… …
Situation dangereuse
10
Étude de cas : Chaudière
« le niveau d’eau ne doit pas être < M1 ou > M2
pendant plus de 5 s. (sinon la chaudière explose) »
Situation dangereuse : Différence entre état perçu et état effectif
11
Choix des paramètres (1/2)
� Définition d’une séquence de test
faute affectant les unités physiques viale simulateur (10 fautes)
Séquence de test
numéro de cycle / à une classe deséquences donnée
6 classes de séquences selon :
- régime transitoire ou permanent- nombre cycles d’injection (petit, moyen, grand)
� Génération au voisinage� Changer le cycle d’injection d’une faute
� Ajouter une faute
� Enlever une faute
Logiciel
Simulateur
Séquences de test
+
12
Exemples
0 1 2 3 4 N
0 1 2 3 4 N
Faute
1
Faute
3
Faute
2
Faute
4
0 1 2 3 4 N
Cyclesd’injection
Évolutiondu système
Faute
3Fau
te 4
Séquence de test :
Voisinage d’une séquence :
Faute
2
Faute
3Fau
te 4
Faute
1Fau
te 2
Faute
1
X
13
� Fonction coût
� Processus de refroidissement
Température = αααα . Température 0,9 < αααα < 0,99
if TRUE then 0
else
Mauvaise estimationdu niveau d’eau
if TRUE then 0
else
Détection dedéfaillances en plus
if TRUE then 0
else
Non-détection detoutes les défaillances
If TRUE then 0
else
Explosion
Fonction coûtObjectif
KNbre Def Inject
21_ _ +
KNbre Def Inject
311 1− +_ _
Kqc qc
42 1−
K1Coût Tout / Rien
Coût modulé
Choix des paramètres (2/2)
14
Génération des séquences de testavec et sans optimisation
Choisir un nombre N entre 1 et 10 (nombre fautes)POUR i = 1 à N Choisir une faute Choisir son cycle d’injection (selon la classe considérée)FINPOURLancer le simulateur+contrôleur avec cette séquenceCalculer le Coût_CourantInitialiser la températureLOOP Génération dans le voisinage (Nouvelle_Solution) Exécution du programme Calcul du Nouveau_Coût IF Nouveau_Coût < Coût_Courant THEN Solution_Courante=Nouvelle_Solution ELSE IF Exp(Coût_Courant - Nouveau_Coût) /
Température ) > Random (0,1) THEN -- Accepter Solution_Courante=Nouvelle_Solution
ELSE -- Ne pas accepter
Diminution de la TempératureEXIT When STOP_CRITERIONEND LOOP
¬¬¬¬ R
ecu
it S
imu
lé
Rec
uit
Sim
ulé
15
Résultats Expérimentaux
� 3 catégories de scénarios menant à une explosion
� Fautes affectant plusieurs pompes ou contrôleurs de pompe
suivie de faute affectant le capteur d’eau
� Faute affectant le capteur de vapeur durant les cycles 0 ou 1
� Fautes affectant le capteur d’eau et le capteur de vapeur
durant les cycles 0 ou 1
� 2 catégories de scénarios stressants
� Faute affectant une pompe, contrôleur associé OK
� Faute affectant le capteur de vapeur juste avant le régime
permanent
16
Exemple sur une classe de scénarios
Explosion 35Explosion 21410
Moyenne(35 graines)
Écart type
Explosion 26Explosion 3129
Moins-Détect1Moins-Détect18
Explosion 22Explosion 297
Moins-Détect4Explosion 396
Explosion 25Explosion 335
Moins-Détect1Moins-Détect14
Moins-Détect4Moins-Détect173
Explosion 22Explosion 332
Moins-Détect3Moins-Détect21
État finalNbre Seq.État finalNbre Seq.
Graine
12,7
18,3
3,8
2,9
Recuit Simulé ¬¬¬¬ Recuit Simulé
17
0 1 2 3 4 N
0 1 2 3 4 N0 1 2 3 4 N
0 1 2 3 4 N 0 1 2 3 4 N
Recuit Simulé ¬¬¬¬ Recuit Simulé
Problème du voisinage : Exemple
1
2
30
28 3
2
5
18
Recuit Simulé ¬¬¬¬ Recuit Simulé
Recuit Simulé Modifié
Recuit Simulé Modifié
x
x
x
x
x
x
xx
xxxxxxx
xx
xx
xxxxxxx
xx
xx
xxxxxxx
xx
xx
xxxxxxx
xx
xx
xxxxxxx
xx
xx
19
Compteur_Itérations = 0;REPEAT
Initialisation de Séquence_Test_Courante et Coût_Courant;Reset-Flag = FAUX;WHILE (Coût_Courant ≠≠≠≠ 0) AND (Reset_Flag = FAUX) AND (Compteur_Itérations < 100)
Génération dans le voisinage “Nouvelle_Séquence_ Test”;Exécution du programme;Calcul du “Nouveau_Coût”;Incrémenter Compteur_Itérations ;δδδδ = Nouveau_Coût – Coût_Courant;IF (δδδδ < 0) THEN
Séquence_Test_Courante = Nouvelle_Séquence_ Test;Coût_Courant = Nouveau_Coût ;
ELSE30 %: -- Accepter la nouvelle séquence de test -- OR30 %: -- Ne pas accepter -- OR40 %: Reset_Flag = VRAI;
FIN WHILE;UNTIL (Coût_Courant = 0) OR (Compteur_Itérations = 100)
Algorithme du Recuit Simulé Modifié
20
Résultats Expérimentaux
Nbre total seq(35 graines)
Nbre de succès
------100Explosion31Explosion3910
Explosion93------100------1009
Explosion70Explosion87------1008
Explosion55------100Explosion767
------100------100------1006
Explosion82Explosion83------1005
Explosion65------100------1004
------100Explosion87------1003
------100Explosion28Explosion622
Explosion68Explosion11------1001
Etat finalNbre Seq.Etat finalNbre Seq.Etat finalNbre Seq.
Graine Recuit Simulé Standard Recuit Simulé Modifié ¬¬¬¬ Recuit Simulé
3146 2296 2668
���� Une nouvelle catégorie de scénarios
6 20 17
21
Conclusion & Prospective
� Intérêt d’une construction incrémentale
� Performance décevante du Recuit Simulé
� Adaptation nécessaire
� Application de cette démarche avec d’autres
techniques d’optimisation et sur d’autres études
de cas
