Embed Size (px)
Citation preview
Erreur, défaut, anomalie
1) On constate une anomalie2) due à un défaut (on dit aussi une faute (!) )du logiciel3) défaut du à une erreur du programmeur (ex. : confusion d ’un I avec un 1)
Tout défaut ne provoque pas nécessairement une anomalie.
Les tests
« Program testing can be used to show the presence of bugs, but never
to show their absence! »
Edsger Wybe Dijkstra
in Notes On Structured Programming, 1970, at the end of section 3, On The Reliability of Mechanisms.
Six classes de défauts (fautes)
- Calcul x := x + 2; au lieu de x := y + 2;
- Logique if (a>b) then au lieu de if (a < b) then
- Entrée/sortie mauvaise description, conversion, formatage
- Traitement des données mauvais accès ou manip (variable non définie, mauvaise utilisation d ’un pointeur, débordement d ’un tableau
- Interface on appelle p1 au lieu de p2, mauvais passage de paramètres
- Définition de données : mauvais type, simple précision au lieu dedouble
Test vs débogage
- quand on teste on ne corrige pas- débogage : correction des défauts
Test réussi ?
Un test réussi n ’est pas un test qui n ’a pas trouvé de défauts, mais un test qui a effectivement trouvé un défaut (ou une anomalie)
G.J. Myers
50 % ou plus du coût
D ’un projet !
K.Gödel avec …
Gödel !
1931Un système formel : un ensemble d ’axiomes et règles de déductionOn produit des théorèmes (par preuve)
Si on prend l ’ensemble des entiers muni des opérations classiques, ilexiste toujours des énoncés qu ’il est impossible de démontrer.
Pire ! Si on rajoute ces énoncés à l ’ensemble des axiomes initiaux,on obtient un système comportant de nouveaux énoncés nondémontrables
Idée de Gödel
Idée de base : l ’autoréférence, voir Hoffstadter :Gödel, Escher, Bach
Cette phrase est fausse.
- si elle est vraie, alors ce qu ’elle dit est vraie, i.e. elle est fausse- si elle est fausse, alors elle est vraie
Gödel (suite)
Deux niveaux de langage :- celui de la phrase- celui qui parle de la phrase
Gödel a construit un énoncé analogue à la première phrase à l ’intérieurd ’un système mathématique.
- numérote tous les signes utilisés dans un théorème concernant les entiers (comme un code ASCII des maths !)- à tout théorème, il fait correspondre un entier (son code)- construit un théor. T qui dit qu ’il n ’existe pas de théor.ayant un codeC, code qui est la codification de T.
I.e. a pu construire un théorème niant sa propre existence.
Ce théorème avait été construit de manière formelle, mais il était impossible de décider sur sa valeur de vérité.
Puis Turing et Church...
Il existe des algorithmes qu ’on ne peut écrire
Exemple : un algo qui, sans utiliser des fichiers de recopie ou autresartifices, donne comme résultat d ’exécution l ’impression du textesource.
a := 1;b := 2;
Il faudrait ajouterwriteln (‘ a := 1; ’);writeln (‘ b := 2; ’);
Mais comme ces 2 instructionsappartiennent aussi au code source, ilfaut ajouter :writeln(‘ writeln (‘ ‘ a := 1; ’’););writeln (‘ writeln (‘ ‘ b := 2; ’’););
Limitations
Un programme T doit lire le code source de n ’importe quel programmeB et nous dire si ce dernier (pour un ens de données d ’E) va s ’arrêter.
(* prog B1 *)10 : goto 10; (*prog B2*)
a := 0;while (a <> 1) dobegina := a + 2;end;
(*prog B3*)read (a)while (a < 10) do
beginb := a + 2;end;
Limitations (suite)
T doit dire que : B1 et B2 ont une boucle infinieque B3 boucle infiniment si a prend une valeur < 10.Si T repère une boucle infinie, message d ’erreur et s ’arrêtesi non, T boucle
(* Prog T *)Lire le code source de B et ses entréesAnalyser B pour savoir si risque de boucler indéfiniment.Si (B boucle indéfiniment) alors
écrire (‘ Le prog B boucle indéfiniment. ’)sinon tant que vrai faire
début (* on se fait en bouclage infini *)fin;
Limitations (suite)
Si on fournit à T son propre code.Soit T boucle indéfinimentSoit s ’arrête.
Si T boucle indéfiniment, T doit s ’arrêter et le signaler.C ’est impossible, puisqu ’on a supposé que T boucle indéfiniment !
Cette hypothèse étant exclue, on en déduit que T s ’arrête.
Mais nous avons prévu que dans cette situation, B est mis en bouclageinfini… donc que T ne se termine pas.Contradiction
Jeu de test, scénario de test
DT = {x = 5, y = 5, b = 58}
Jeux de test : ensemble de données de test
Scénario de test : séquence d ’actions
Oracle de test
Exemple d ’oracle automatique :
Pour la calcul de la racine carrée, c ’est :résultat au carré = entrée ?
Critères de test
Fiable : si produit uniquement des jeux de tests réussis ou, uniquementdes jeux de tests non réussis.
Si on sait que le critère est fiable, il suffit de passer un seul jeu de testpour savoir que tous les autres seront réussis ou non.
Valide : si produit au moins un jeu de test non réussi dans le cas où leprogramme n ’est pas correct.
.
Analogie : le crible
Crible valide : on est sûr qu ’il existe un trou assez petit pour nepas laisser passer la plus petite bille.
Mais le crible ne va pas arrêter toutes les billes !Car une bille petite pourra passer par un trou plus grand : le jeu de test a réussi: on n ’a pas capturé le défaut
Crible fiable : les tailles de tous les trous sont égales.Soit toutes les billes vont passer (on ne détecte aucun défaut, jeuxde test réussis)Soit toutes les billes sont arrêtées (tous les tests échouent)
Fiable et valide
Fiable et valide
Crible dont les trous sont tous assez petits pour arrêter les toutes lesbilles
Et si aucun trou…ce serait le test exhaustif !
Mais on veut un test léger.
Définir automatiquement un algo de découverte de critère fiable etvalide est indécidable
Critère adéquat
On fait une hypothèse sur la taille ou la forme des différentes billes pour construire des trous en mesure de les arrêter.
Types de test
1) Fonctionnels ou boîte noire2) Structurels ou boîte blanche
1) statiques (on observe le code)2) dynamiques (on exécute le code)
Grises
Stratégie de test
- ressources mises en œuvre (équipes, testeurs, outils, etc)
- mécanismes du processus de test (gestion des configurations, réunions pendant lesquelles on évaluera le processus de test etses résultats, etc.)
Catégories d ’anomalies
Mineures (ex. impression)
Bloquantes
Majeures et graves : ex. production d ’information de navigation erronées
Intégration
1) Intégration massive (big bang)2) au fil de l ’eau3) par incréments (agrégats)
Lanceurs : composants sollicitant le composant à tester
Bouchons : composants sollicités par le composant à tester
Intégration : Variantes
- descendante- ascendante- guidée par le risque- mixte
Les outils
De préparation des tests
Générateurs de jeux d ’essais
Formateurs de données
Analyseurs statiques : produisent le graphe de contrôle
Instrumenteurs
Gestionnaires de test
Les outils
Outils d ’exécution des tests
Procédures d ’exécution
Jeux de tests
Procédures de commande
Lanceurs et bouchons
Analyseurs, émulateurs, etc.
Les outils
Outils de traitement de résultats
Comparateurs de résultats
Gestionnaires de résultats
Oracles de test
Les outils
Outils d ’observation et de mesure
Analyseurs de performance
De couverture de tests
Avantages/inconvénients
function sum (x, y: integer) : integer; begin if (x = 600) and (y = 500) then sum := x - y else sum := x + y; end
Approche fonctionnelle
Doit calculer la somme de 2 entiers
Impossible de trouver le défaut
Approche structurelle : couverture de toutes les instructionsDT = {x = 600, y = 500} , résultat = 100 et non 1100
Test fonctionnel/analyse partitionnelle
Choix d ’un représentant de chaque classe
Ex 1: Calcul de la fonction f(x) = racine carrée de 1/x avec x réel
3 classes d ’équivalence (2 invalides, 1 valide)
1ere classe : les réels négatifs2ème classe : x = 03ème classe ; les réels positifs (seule classe valide)
Test fonctionnel/analyse partitionnelle
Ex. 2 Le prog lit 3 réels (longueur des côtés d ’un triangle). Sices 3 nombres ne sont pas ceux d ’un triangle, imprime message.Si triangle, isocèle, équilatéral ou scalaire et si son plus grand angle est aigu, droit ou obtus.
10 cas : 1 + 3 * 3
AngleTriangle aigu obtus droitscalaire 6, 5, 3 5, 6, 10 3, 4, 5isocèle 6, 1, 6 7, 4, 4 Rac 2, 2, rac 2équilatéral 4, 4, 4 impossible impossible
L’ex. du triangle
Cas d ’un non triangle :1, 2, 8
Test aux limites
Ex. Si a : 1..100, on définit 6 DT où a prend les valeurs :
0, 1, 299, 100, 101
Test aux limites1, 1, 2 non triangle0, 0, 0 un seul point4, 0, 3 une longueur vide1, 2, 3.00001 presque triangle0.0001 0.0001 0.0001 très petit triangle88888, 88888, 88888 très grand triangle3.00001, 3, 3 presqu’équilatéral2.99999, 3, 4 presqu’isocèle3, 4 5.00001 presque droit3, 4, 5, 6 4 données3 1 seule donnée3, 4, , 5 2 virgules-3, -3, 5 valeurs négatives
Graphes cause-effet
« Le caractère dans la colonne 1 doit être un « A » ou un « B ».Dans la colonne 2, il doit y avoir un chiffre. Dans ce cas, nousconsidérons que le fichier est mis à jour. Si le premier caractèreest erroné, le message d ’erreur X12 doit être imprimé.Si dans la deuxième colonne nous n ’avons pas de chiffre, il faut alors que le message X13 soit imprimé. »
Graphes cause-effet
Causes :A1 caractère de la première colonne est « A »A2 caractère de la première colonne est « B » A3 caractère de la deuxième colonne est un chiffre
Effets :
M1 fichier mis à jourM2 message X12M3 message X13
Graphe cause- effet
A1
A2
E
M3
M1
M2
A3
\/
/\
Faire la tdd
Tests syntaxiques
Par exemple, grammaire de commandes
On construit l ’arbre de dérivation de la grammaire
Puis on construit - les commandes valides, - les commandes invalides
en suivant les nœuds et les niveaux dans le graphe
Tests aléatoires
- échantillonnage uniforme des domaines de définition
Analyse transactionnelle
Test structurel
a
d
b
c
u1
u2
u6
u4
u7
u3u5
Chemin c1 = [u3, u1, u4, u5, u6]ou = [b, c, a, c, d, d]
c2 = [a, b, c, d], c3 = [b, c] c2 couvre c3
Mais ne couvre ni [b, c, b] ni [a, c]
Circuits linéairt indépendants
a
d
b
c
u1
u2
u6
u4
u7
u3u5
c1 = [u3, u1, u4, u5, u6]
c6 = [u2, u3]
c4 = [u7, u3, u7, u3, u1]
c5 = [u3, u1, u4, u7]
u1 u2 u3 u4 u5 u6 u70 1 1 0 0 0 01 0 2 0 0 0 21 0 1 1 0 0 1
c6c4c5
Circuits linéairt- indépendants
Circuit 1 = [u1, u4] = (1, 0, 0, 1, 0, 0, 0)Circuit 2 = [u3, u7] = (0, 0, 1, 0, 0, 0, 1)
(1, 0, 1, 1, 0, 0, 1)
L ’addition donne le circuit circuit 5 qui se définit à l ’aidedes circuits circuit 1 et circuit 2circuit 5 = circuit 1 + circuit 2 oucircuit 2 = circuit 5 - circuit 1
Circuit 7 = [u2, u3, u1] (1, 1, 1, 0, 0, 0, 0)est indépendant de circuit 1 et 2 puisque n ’enconstitue pas une combinaison linéaire
Critique
N.B. : le fait qu ’un chemin M s ’exprime à l ’aide d ’un cheminB ne signifie pas que M couvre B
a b cu1 u2
u3
M= [u1, u2, u3] B =[u3, u1, u2]
(1, 1, 1)(1, 1, 1)
L ’expression vectoriellene tient pas comptede l ’ordre de visitedes nœuds !
Nb cyclomatique
Il existe un chemin connectant deux nœuds quelconquesdu graphe
Il existe un ensemble de circuits indépendants CI, de sorte que de n ’importe quel circuit du graphe puisse se traduire à l ’aidedes CI
Base : ensemble des circuits indépendants
Nbre max de circuits indépendants pour former la base, dans un graphe fortement connexe = nb d ’arcs - nb de nœuds + 1
Le nombre cyclomatique
c
a
b
d
u4
u5
u3u1
u2
B1 = [u1, u2, u3]
B2 = [u4, u5, u2]
B = [u5, u2, u3, u1, u2, u4]= B1 + b2
B1 1 1 1 0 0B2 0 1 0 1 1B 1 2 1 1 1
u1 u2 u3 u4 u5
5-4+1 = 2
Nbre cyclomatique
Pour vérifier l ’indépendance entre chemin :calculer leur vecteurvoir si chaque chemin comprend au moins un arc n ’existant pas chezles autres
Graphe de contrôle
i:= 1; while i <= Max do begin if a[i] = s then pos := i; i := i + 1; end;
i:=1
i<=Max
a[i] /= s
i := i + 1
pos := i;
Revues de code
Exemples :- commentaires utiles ?i := i + 1 (* incrémentation du compteur i *)- le code a-t-il des points et utilitaires de traçabilité- le nommage des identificateurs est-il compréhensible ?- code lisible (structuré) ?- grand nombre de littéraux dans le code ?if (choices = 2) then answer := ‘ a ’ ;
Le jour où on veut remplacer 2 par 3 il faut parcourir l ’ensemble ducode pour détecter les apparitions de 2, puis se demander si il est bien la valeur d ’une variable que l ’on veut modifier : nb de jours ?de mois ?
Les constantes
Solution : utiliser une « constante », regrouper les constantes dansun fichier.
- taille des routines acceptables ?
Détection de défauts ou configurations douteuses :
- boucles utilisant <> (différent) comme condition terminale oucomparaison de 2 réels (erreur de précisions conduisant à mauvais choix)Eviter d ’écrire :
while i <> Max do … au lieu de while ( i < Max) do
ou encore :
while (r1 <> r2) do … au lieu de while (trunc(r1) < trunc(r2)) do ...
Revues de code (suite)
- Emploi d ’instruction de la forme :if ( x = F(a) + a ) then …ouif (F or P) then …
où F est une fonction booléenne ayant des effets de bord sur le paramètre a (i.e. que le par. est modifié à l ’intérieur de F)Il se peut que la valeur de a que le prog a voulu ajouter à F(a)ne soit pas la même que celle passée à la fonction
P va-t-il être effectivement calculé dans le cas où F a retourné vrai(selon la stratégie d ’évaluation de la sémantique) ?
Revues de code (suite)
- mauvais emploi d ’indices d ’un tableau
- tentative de division par zéro ou défauts dus à des arrondis
- mauvais emploi des instructions d ’E/S
- mauvaises manipulations des fichiers (fermés après ouverture ?)
Complexité : nb de croisements
L2:
GOTO L1
GOTO L2
L1:
Profondeur max d ’imbrication
If a > 0 thenwhile a < i do
beginwhile j > i do
if j = 2 * x then y := jelse j := j + 1 ;
a := a + 1 ;end;
= 4
Exécution symbolique
a := a * ax := a + b ; if x = 0 then x := 0 else x := 1;
a = A, b = B, x = X
a = A * A, b = B, x = X
A = A*A, b = B, x = A*A+B
A*A+B =0 A*A+B /= 0
a = A*Ab = Bx = 0
a = A*Ab = Bx = 1
Exécution symbolique
Exécution symbolique (suite)
Nécessité d ’évaluations intermédiaires
a = A*A + A*A + 5 + 2 simplifiée en a = 2*A*A + 7
Difficulté : tableaux
a[i] := 5;:a[j] := 3;:x := a[i];
La valeur de x peut tout aussi bien être 5(si i <>j) que 3 (si i = j)
if x < 0 then a := - x else a := x; b := - aif -2*b < 0 then writeln (‘ Error1 ’) else writeln (‘ Error2 ’)
Interprétation abstraite
On attribue à chaque variable des Intervalles (réels ou entiers)
I(a) = 10.. 20I(b) = 10..15
if a = b then b := a + 3 else b := a - 3
Par union des 2 I de b, on peut prédire que la valeur finale de b : 7..18
Avant exécution : a : 10..15 & b : 10..15
Après exécution 1ere branche :a : 10..15 & b : 13..18 Après exécution 2e branche :
a :10..15 & b : 7..17
Interprétation abstraite
s := 0;i := 1;while (i<=n) do
begins := s + i ;i := i + 1;if s> c then n := iend;
But du programmeur :calculer la somme s de tous les entiersinférieurs à n
Il a imposé une autre condition :cette somme ne doit pas dépasser c
Il a cru « forcer » l ’arrêt de la boucle en affectantà n la valeur i
Interprétation abstraite
s := 0;i := 1;while (i<=n) do
begins := s + i ;i := i + 1;if s> c then n := iend;
En supposant I(n) = 0..20 et I(c) = 300..1000,l ’exécution semi-symbolique met enévidence que s n ’appartiendra jamais à 300..1000
Quelles que que soient les valeurs de n et c appartenant à I(n) et I(c) respectivement, l ’instruction d ’affectationn := i est non exécutable Code mort
Interprétation abstraiteAgrandissons I(c) pour satisfaire s > c I(c ) = 200..1000
n := i est symboliquement exécutée, mais peut provoquer bouclageinfini
Valeur initiale de i = 1n : 0..20
1e exécution du while, I(n) : 1..20
2e exécution du while, I(n) : 2..20, etc.
Au fur et à mesure où i augmente, l ’intervalle se réduit
s := 0;i := 1;while (i<=n) do
begins := s + i ;i := i + 1;if s> c then n := iend;
Interprétation abstraite
Rétrécissement des intervalles des variables intervenant dans la condition d ’itération caractérise la convergence de l ’algo
La méthode semi-symbolique permet de détecter le non rétrécissement
Lorsque n dépassera c, n prendra la valeur de iI(c) = I(n) et condition du while toujours vraie.
s := 0;i := 1;while (i<=n) do
begins := s + i ;i := i + 1;if s> c then n := iend;
Analyse du flot des données
x := a + b ; x est définie et a et b référencées
read(x) x est définiewrite (x) x est référencéeif (x=1) then x := 7 x est référencée, puis définiea [i] := x a est définie, i et x référencéesx := x + 1 x est référencée, puis définie
dr-chaîne
dr-chaînes
program p (input, output) ;var x, y, z, a, b, c : integer ;beginread (c);x := 7;y := x + a;b := x+y+a;c := y + 2*x + z;write (x, c)end.
Variable dr-chaîne
x drrrry drrz ra rrb dc ddr
z et a : référencées et non définiesc définies 2 fois de suitedéfinition de b inutile
dr-chaînes
r.. Variable a une valeur indéfinie lors de sa 1e utilisation
…dd… 2 définitions consécutives, la 1e est inutile
…d dernière définition inutile
Analyse des domaines finis
read (x, y) ;if (y >= x) then begin if (y > 5) then d := 1 else c := 2; endelse c := 3;if (x + y < 4) then c := c + 10else c := c + 20;writeln (c );
y >= xy > 5x + y < 4
D1 y=xD2 y=5D3 y=4 - x
y
x
D2
D1
D3
TTF
TTF: (x, y) qui satisfont la1e Condition, non la 2e, non la 3e
TFF
TFT
FT
FF
Analyse des domaines finis
y
x
D2
D1
D3
TTF
TFF
TFT
FT
FF
Certaines régions n ’existent pas :FFT la non satisfaction de la 1e conditionne permet pas d ’atteindre la 2eou TTTcar D2 et D3 ne se croisent pas et nepermettent aucune intersection de leurdomaine
Analyse des domaines finis
y
x
D2
D1
D3
TTF
TFF
TFT
FT
FF
Points les plus sensibles à toutetransformation (rotation outranslation) que les différentesdroites (conditions du programme)risquent d ’avoir subie à caused ’erreurs du programmeur
Analyse des domaines finis
x
D2
D1
D3
TTF
TFF
TFT
FT
FF
Si DT (intersection)
DT1 = {x=0, y=0}DT2 = {x=0, y= 10}DT3 = {x=10, y=0}DT4 = {x=10, y=10}
DT5 ={x=0, y=4}DT6 = {x=4, y=0}
DT7 = {x=5, y=5}DT8 = {x=2, y=2}
Analyse des domaines finis
- il est très difficile de représenter des conditions de plus de 2 variables (ex : x + y < z), des tableaux, variables liées par unefonction non linéaire (x * x <= y)
- dans les conditions on trouve non des entrées mais des variablesintermédiaires
Analyse dynamique (test structurel)
1 - Techniques de couverture du graphe de contrôle
2 - Techniques des tests mutationnels
Techniques de couverture
1 - Chemins dans un graphe de contrôle2 - Couvertures basées sur le flot de contrôle3 - Couvertures basées sur le flot des données
Structures élémentaires
repeat
while
case
if then else
séquence
Réduction de graphe de F de C
Graphe de contrôle
If x <= 0 then x := -xelse x := 1 - x;if x = -1 then x := 1else x := x + 1;writeln (x);
a
e
g
f
d
cb
x<=0 x >0
x = -1 x /= -1
x:= -x x:=1-x
x:=x+1
writeln(x)
Chemin de contrôle :[a, c, d, e, g]
Non chemin de contrôle :[b, d, f, g]
Expression de chemin
a
e
g
f
d
cb
x<=0 x >0
x = -1 x /= -1
x:= -x x:=1-x
x:=x+1
writeln(x)
Expression de chemin :a (b + c) d (e + f) g
Expression de chemin
a b c d
ab (cb)* d
Expression régulière
Sensibilisation de chemin
a
e
g
f
d
cb
x<=0 x >0
x = -1 x /= -1
x:=1-x
x:=x+1
writeln(x)
{x = 2} sensibilise le chemin[a, c, d, f, g]{x = 0} sensibilise le chemin[a, b, d, e, g]{x = 1} sensibilise le chemin[a, c, d, e, g]
Chemins exécutables/non exécutables
a
e
g
f
d
cb
x<=0 x >0
x = -1 x /= -1
x:=1-x
x:=x+1
writeln(x)
Aucune valeur de x n ’est capable de sensibiliser [a, b, d, f, g]si on passe b, on ne passerajamais f
Chemins exécutables : il existe desDT qui les sensibilisent
Chemins inexécutables : infaisable
Chemin non exécutable
1
2
3
5
4
6
read(choice);
choice=1
x:=x+1;
choice=2
x:=x-1;
read (choice);if choice = 1 then x := x + 1;if choice = 2 then x := x-1;
[1, 2, 3, 4, 5, 6] non exécutablecar choix ne peut avoir en mêmetemps la valeur 1 et la valeur 2
Restructuration en:read (choice);if (choice = 1) then x := x +1else if (choice = 2) then x := x - 1;
Chemin non exécutable
1
4
6
35
2
read(choice);
choice=1
X:= x+1; Choice=2
X:=x+1;
Restructuration en:read (choice);if (choice = 1) then x := x +1else if (choice = 2) then x := x - 1;
Sensible/révélateur d ’erreur
Read (x)if x > 7 then y := 0else y := x;writeln (1/y);
1
3 4
2
4
Read (x);
x <= 7
writeln(1/y);
y := 0;
x > 7
[1, 2, 4, 5 ] est sensible aux erreurs
[1, 2, 3, 5] est révélateur d ’erreur car erreur qqs la valeur init de x et y
Flot de ctrl vs flot de données
Read (x, y);if (x mod 2 = 0) then y := y + x/2;if (x <0) then
begin y := - x;writeln (y) ;end
else writeln (y);
1
2
3
54
read(x, y);
x impair
X >= 0
writeln (y);y :=- x;writeln(y);
X < 0
y:=y+x/2
x pair
Flot d ’exécution
1
2
3
54
read(x, y);
x impair
x >= 0
writeln (y);y :=- x;writeln(y);
X < 0
y:=y+x/2
x pair Couverture des arcs :DT1 = {x=-2, y= 0}DT2 = {x= 1, y = 0}
DT1 exécute [1, 2, 3, 4]DT2 [1, 3, 5]
Si 2 erroné, l ’erreur ne sera pasdétectée par les DT1, 2car la valeur de y est masquée parune nouvelle affectation y := - x
1
2
3
54
read(x, y);
x impair
x >= 0
writeln (y);
X < 0
y:=y+x/2
x pairPour tester l ’affectation du nœud 2,il faut exécuter [1, 2, 3, 5]avec la DT3 = [{x=2, y=0} pour avoir x paire et positive
Flot d ’exécution/flot de donnée
Pour trouver la nécessité de DT3, 2 raisonnements possibles :
1) on suit le flot d ’exécution
Voir que flot d ’exécution [1, 2, 3, 5] n ’est pas pris en compteet créer une DT supplémentaire
2) on suit le flot de données
Voir que l ’affectation de y au nœud 2 n ’a pas été ‘ utilisée ’par les deux premières DT car elle a été « couverte » par celle dunœud 4et créer une DT supplémentaire pour la « rendre utile »
Couverture basée sur le flot de contrôle
Fonction censée calculer la somme de 2 entiers :function sum (x,y: integer) : integer; begin if (x=0) then sum := x else sum := x + y; end;
Si test boîte noire, on ne découvrira pas l ’erreur
Elle n ’est découverte que par DT = {x=0, y /=0}
a
b c
c
x=0
sum:=x+y;
x/=0
Taux de couverture
function sum (x,y: integer) : integer;beginif (x=0) then sum := xelse sum := x + y;end;
a
b c
c
x=0
sum:=x+y;
x/=0
sum:=x;
La plupart des DT ne couvrent que [a, b, d].Ce n ’est qu ’en essayant de passer par c que nous exécutons lechemin sensible à l ’erreur [a, c, d]
Taux de couverture
1e critère : sensibiliser les chemins de contrôle qui nous permettrontde visiter tous les nœuds.Critère « tous-les-nœuds »
A chaque critère de couverture est associé le taux de couverture oumesure de complétude (d° de satisfaction du critère)
Si on soumet uniquement DT1 = {x=2, y=5}, on exécute [a, b, d]i.e. 3 nœuds sur 4Test Effectiveness Ratio (TER) : nb de nœuds couverts/ nb total de nœuds = 3/4 = 0, 75 = 75 %
a
b c
c
x=0
sum:=x+y;
x/=0
Critère TER
TER = 1 <=> C1 = 1 <=> tous-les-nœuds est satisfait <=> tous les nœuds du graphe de contrôle ont été
couverts <=> toutes les instructions ont été exécutées (au
moins une fois)
a
b c
c
x=0
sum:=x+y;
x/=0
couverture de tous les actes
2e critère : couverture de tous les actes
Tous-les-nœuds est insuffisant.
a
d
c
bX=0
y:=1/x;
read(x);
x:=1;
x/=0
read(x);:if x < > 0 then x := 1;:y:= 1/x;
DT = {x=2} sensibilise [a, b, c, d], couvre tous les nœuds sansfaire apparaître l ’anomalie qui se produira si b n ’est pas exécuté
Critère tous-les-arcs
Le pb vient que nous n ’avons pas couvert tous les arcs
Couvrir tous les chemins de contrôle composés uniquement d ’un arc.
B1 = [a, b]B2 = [b, c]B3 = [a, c]B4 = [c, d]
a
d
c
bX=0
y:=1/x;
read(x);
x:=1;
x/=0
TER2 ou C2
a
d
c
bX=0
y:=1/x;
read(x);
x:=1;
x/=0 Pour la DT {x=2} qui couvre les chemins B1, B2 et B4 (3 sur 4)
TER2 = nb des arcs couverts /nb total d ’arcs = 3/4= 0,75 = 75%
B1 = [a, b]B2 = [b, c]B3 = [a, c]B4 = [c, d]
Alors que la même DT donne
TER1 = 4/4 = 1 = 100%
TER2
La couverture de tous les arcs équivaut à la couverture de toutes lesvaleurs de vérité pour chaque nœud de décision.En satisfaisant ce critère, nous couvrons tous les chemins reliant un nœud de décision à un autre (appelé aussi dd-chemins ou branches)
TER2 = 1 <=> C2 = 1 <=> tous-les-arcs est satisfait <=> tous les arcs du graphe sont couverts <=> toutes les décisions ont été couvertes (V et F) <=> tous le dd-chemins ont été couverts <=> toutes les branches ont été couvertes <=> tous-les-nœuds est satisfait => C1 = 1
Décision composée
If (( a < 2) and (b = a)) then x := 2 - a else x := a - 2
1
32
4
(a<=2) or(b/=a)
(a<2) and (b=a)
x:=2-a;x=a-2
DT1 = {a=b=1}DT2 = {a=3}couvrent tous les arcsmais non les deux conditionscomposant la décision.
Mesure C3
1
32
4
(a<=2) or(b/=a)
(a<2) and (b=a)
x:=2-a;
1
4
3
2
5
6
a>=2a<2
b=a
x:=2-a
x:=a-2
b=ab/=a
b/=a
Pour couvrir tous les arcs il faut2 * 2 = 4 DT
DT1 = {a=b=1}DT2 = {a=1, b=0}
DT3 = {a=3, b=2}DT4 = {a=b=3}
1
4
3
2
5
6
a>=2a<2
b=a
x:=2-a
x:=a-2
b=ab/=a
b/=a
1
3
2
4
5
a>=2a<2
b=a
x:=2-a
x:=a-2
b/=a
1
3
2
4
5
a>=2a<2
b=a
x:=2-a
x:=a-2
b/=a
DT1 = {a=b=1}DT2 = {a=1, b=0}DT3 = {a=3, b=2}
Couvrent tous les arcs
Couverture de tous les chemins linéairement indépendants
read (inf, sup)i := inf;sum := 0;while (i <= sup) dobeginsum := sum + a[i];i := i + 1;end;
Évalue l ’inverse de la somme des éléments compris entre la placeinf et sup d ’un tableau a comprenant des entiers positifs.
b
c e
d
u1
u4
u2
u3 sum:= sum + a[i];i:=i+1;
writeln(1/sum);
read(inf,sup);i:=inf;sum:=0;
i<=sup
b
c e
d
u1
u4
u2
u3 sum:= sum + a[i];i:=i+1;
read(inf,sup);i:=inf;sum:=0;
i<=sup
DT1= {a[1]=50, a[2] =60, a[3]=80, inf =1, sup=3}
B1=[b,c,d,c,d,c,d,c,e]=[u1,u2,u3,u2,u3,u2,u3,u4]couvre tous les arcs (et nœuds) sans détecter l ’erreur
Erreur qui se manifeste lorsque inf > sup.En effet, si la boucle n ’est pas exécutée, sum reste à 0 et l ’évaluation de son inverse est impossible.
Il faut ajouter le chemin B2 =[u1, u4]sensibilisé par ex. par DT2={inf=2, sup=1}
b
c e
d
u1
u4
u2
u3 sum:= sum + a[i];i:=i+1;
i<=sup
Nombre de McCabe
u1 u2 u3 u4B1 1 3 3 1B2 1 0 0 1B3 1 1 1 1
B3 = 1/3 (B1 + 2B2) B3 combinaison linéaire de B1 et B2
v(G) = 4 - 4 + 2 = 2v(G) = nb de nœuds de décision + 1= 1 + 1
B1 et B2 étant deux ch. Linéairement indépendants, ils constituent unebase. N ’importe quel chemin peut s ’exprimer à l ’aide de B1 et B2
Limites
Si le critère tous-les-chemins-indépendants est satisfait, alors les critères tous-les-arcs et tous-les-nœuds le sont aussi.
Mais la propriété d ’indépendance n ’est ni nécessaire ni suffisantepour détecter le défauts
Si nous avions choisi B3 (qui est aussi indép. De B1) au lieu de B2, on aurait obtenu une base sans détecter l ’erreur.
Couverture « vectorielle » !
Program p (input, output); var a : array[1..2] of integer; E, i : integer; found : boolean; begin read(i, E, a[1], a[2]); found := false; while i <= 2 do begin if (a[i] = E) then found := true else found := false ; i := i + 1; end; writeln(found);end.
1
72
4
3
5
6
u1
u2
u3
u4 u5
u6 u7
u8
i>2
a[i]=Ea[i]/=E
i:= i+1
1
72
4
3
5
6
u1
u2
u3
u4 u5
u6 u7
u8
i>2
a[i]=Ea[i]/=E
i:= i+1
DT1 ={i=3} sensibilise B1=[u1, u2]
Modifions la condition du nœud 2 :DT2 ={i=1, E=10, a[1]=20, a[2]=10}
qui sensibiliseB2 =[u1, u3, u4, u6, u8, u3, u5, u7, u8, u2]
1
72
4
3
5
6
u1
u2
u3
u4 u5
u6 u7
u8
i>2
a[i]=Ea[i]/=E
i:= i+1
En modifiant la condition du nœud 3
DT3 = {i=1, E=10, a[1]=10, a[2] = 20]sensibilise :B3 =[u1,u3,u5,u7,u8,u3,u6,u8,u2]
Mais B3 n ’est pas indépendant de B2, caradmettent le même vecteur v = [1, 1, 2, 1, 1, 1, 1, 2]
B2 et B3 ont les mêmes arcs le même nb de fois.
On produit 2 autres chemins : B4 et B5DT4 ={i=1, E=10, a[1]=10, a[2]=10}sensibilisantB4 =[u1, u3, u5, u7, u8, u3, u5, u7, u8,u2]DT5 ={i=1, E=10, a[1]=20, a[2]=30}sensibilisantB5 =[u1, u3, u4, u6, u8, u3, u4, u6, u8, u2]
B1, B4 et B5 sont vectoriellement indépendants
Limites
Résultats exactsDT1 found = false car boucle non exécutéeDT4 found = trueDT5 found est affecté deux fois à false
Or ne détectent pas l ’erreur (la valeur de found ne dépend endéfinitive que de la dernière valeur de l ’élément du tableau.
Le seul chemin parmi ceux proposés, qui détectait l ’erreurétait B3 (celui que l ’on a rejeté à cause de sa dépendance avecB2 !)
Couverture des PLCSPortion Linéaire de Code Suivie de SautLCSAJ (Linear Code Subpath And Jump)
005 INPUT A, C010 B= 2*A020 A=A+1030 IF A<0 THEN GOTO 60040 B= -A050 PRINT A+B060 IF B=2*C THEN GOTO 80070 A=1:GOTO 90080 A=-2:GOTO 20090 PRINT A100 END
En gras et vertles « sauts »
PLCS : chemin partant d ’un nœud saut et aboutissantà un nœud saut. L ’avant dernier et dernier nœud sont le seul sautdu chemin
PLCS20
5
60
80
90
100
30
40
70
1) [5, 20, 30, 60]2) [5, 20, 30, 40, 60, 80]3) [5, 20, 30, 40, 60, 70, 90]4) [20, 30, 60]5) [20, 30, 40, 60, 80]6) [20, 30, 40, 60, 70, 90]7) [60, 80]8) [60, 70, 90]9) [80, 20]10) [90, 100]
4 incluse dans 1, 5 dans 2, 6 dans 37 dans 2, 8 dans 3
TER3
Si on exécute les 3 chemins :B1 = [5, 20, 30, 60, 70, 90, 100]B2 = [5, 20, 30, 40, 60, 80, 20, 30, 60, 70, 90, 100]B3 = [5, 20, 30, 40, 60, 70, 90, 100]
on couvre la totalité des PLCS
TER3 = nb de PLCS couvertes / nb total de PLCS
Tests des chemins de boucle
Limites et intérieurs à une boucle (boundary interior path test)
Limites : traversent la boucle mais ne l ’itèrent pasIntérieurs : itèrent la boucle une seule fois.
1
2
3
1
2
43
[1,2,3] chemin limite
[1,2,1,2,3] [1,2,4,2,3]
sont intérieurs
1
6
43
2
5
v f
Chemins limitesL1=[1,2,3,5,6]L2 =[1,2,4,5,6]
Chemins intérieursvv=[1,2,3,5,2,3,5,6]vf=[1,2,3,5,2,4,5,6]fv=[1,2,4,5,2,3,5,6]ff=[1,2,4,5,2,4,5,6]
On peut compléter par :1) chemins exécutant deux fois la boucle2) chemins exécutant le nombre max d ’itérations
Couvertures basées sur le flot de données
d variable définier variable référencée (utilisée)p-utilisation dans le prédicat d ’une instruction de décisionc-utilisation dans un calcul
while (i < N) do i et N sont p-utilisées et à la dernière exécution,i esst c-utilisée et ensuite définie
begin s := s + i; s et i sont c-utilisées, puis s est définie i := i + 1; end;writeln (s); s est utilisée
C-utilisation et p-utilisation
Chemin d ’utilisation (c-utilisation ou p-utilisation) :chemin reliant l ’instruction de définition d ’une variable à uneinstruction utilisatrice.
1
4
2
3
read(x,y);
x >=100
x<100
x:=x*y;y:=y+1;
[1,2,3,2,4] couvre tous les arcs
L ’arc (2, 4) est p-utilisateur de x parrapport au nœud 1Or le chemin de p-utilisation [1,2,4]qui relie la définition de x au nœud 1 avec son arc p-utilisateur (2,4) n ’estpas inclus dans le chemin de testinitial.
P-utilisation et c-utilisation
Le critère tous-les-p-utilisateurs nécessite que tous les arcs p-utilisateurscorrespondant à toutes les définitions du graphe (affectation, read, etc.)soient couvertes, par un chemin de p-utilisation.
Nous ne développerons pas plus
Complémentarité des méthodes
If a > b then x := a - belse x := b - a
Si le programmeur avait dû écrire y := b - a au lieu dex : b - a, alors une couverture basée sur le flot de données sera sans doute en mesure de détecter l ’erreur
Si le programmeur a commis une erreur de branchement (a < b au lieude a > b) une couverture basée sur les chemins sera plus pertinente.
Test mutationnels
Sélection du meilleur mécanicien parmi 10 candidats
On présente à chaque candidat (DT) différentes pannes (mutants)que l ’on a volontairement provoquées sur la voiture (programmeinitial)Le candidat détectant le plus de pannes sera le plus compétent
On va tester si la DT est appropriée en comparant les résultats qu ’elledonnera lorsqu ’elle est soumise aux différents mutants
Mutants
Principaux : Mutants qui, pour au moins une DT, donnent des résultats différents du programme initial
Prog. Principal :a := b + c ; writeln (a) ;
Mutants :i) a := b + 1; writeln (a);ii) a := b - c; writeln (a);iii) a := b + c; writeln (b) ;
Mutants (suite)
Mutants secondaires Donnent pour toutes les DT les mêmes résultats que ceux du programme initial
var a, b, c : interger;beginif a < b then c := a;end i) if a <= b - 1 then c := a;
ii) if a + 1 <= b then c := a;iii) if a < b then c := a + 0;
Mutants principaux
Plus une DT tue de mutants principaux, plus elle est appropriéeCas idéal : une DT qui tue tous les mutants principaux.
Si le programme initial est erroné et que sa bonne version constitueun mutant de celui-ci :1) soit ces programmes donnent toujours le même résultat (ils sontéquivalents)
2) soit donnent des résultats différents. La DT peut les distinguer. Elle est appropriée
Exemple
Prog. : ajouter 2 à un nombre lu en entrée
Erreur : confusion entre ^ et + et *
On choisit l ’entrée de 2.
Si le résultat est 5, prog. erroné
Si le résultat est 4, sûr d ’avoir bien testé ?
Non ! x:= x *2 , x := x ^2
Mutants
On produit DT {x=3} pour tuer les deux mutantsx := x*2 et x := x2
Tolérance aux erreurs
read (a, b);while b > 0 do begin a := a + 1; b := b - 1; manip (a, b) ; end;
Manip(a, b) permet d ’observer et modifierles valeurs de a et b en cours d ’exécution.
Soit étant initial S0 =<3,5>
1e observation état S1 = <4,4>2e état S2 = <5,3>3e état S3 = <6,2>4e état S4 = <7,1>5e état S5 = <8,0>
S5 = <a + b, 0>
Tolérance aux erreurs
read (a, b);while b > 0 do begin a := a + 1; b := b - 1; manip (a, b) ; end;
1e observation état S1 = <4,4>On modifie S2 en S2 ’=<17, -1>le bouclage s ’arrête et l ’état final est :<17, -1>
L ’algo n ’a pas toléré la « déformation »
On recherche des transformations, qui tout en modifiant un état intermédiaire, peuvent secompenser par le comportement ultérieur et donnerle résultat attendu
P-correct, s-correct
1e observation état S1 = <4,4>Modification de S2S2 ’ = <7,1>S3 = <8, 0>
S est faiblement correct (f-correct) à un certain endroit par rapportà un état initial S0, ssi, en reprenant à l ’algo à partir de cet état,on retrouve le résultat attendu.
<7,1> est f-correct par rapport à <3,5> mais aussi à <1,7> , <4,4> etc.
S2 = <5, 3> issu d ’un fonctionnement normal, est strictement correct
Sp-correct
2e observation modifions S2=<5,3> en <8,-2>On obtient l ’état final <8,-2>, qui n ’est pas le résultat attendu maison a bien la bonne valeur de a
<8,-2> est correct d ’après les spécifications (sp-correct) par rapportà S0 et à l ’endroit de la 2e observation.
Les états intermédiaires
1) modifications donnant le résultat final attendu.Etat intermédiaire f-correct
2) modifications qui ne donnent pas le résultat final attendu, maiscelui prévu par les spécifications.Etat intermédiaire sp-correct
3) modifications altérant irrémédiablement l ’état intermédiaire.Etat non-sp correct
F-récupérable
Si l ’état S courant n ’est plus f-correct.
Si on peut le transformer par une routine de récupération locale, enun état f-correct,
l ’état est f-récupérable.
Fin
![Erreur et Délivrance(Al Ghazali)[1]](https://img.pdfslide.fr/doc/110x75/557202574979599169a35c5f/erreur-et-delivranceal-ghazali1.jpg)
