Erreur, défaut, anomalie 1) On constate une anomalie 2) due à un défaut (on dit aussi une faute...

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