V.T.

L
Validation et Test de Logiciel
Master Ingénierie du Logiciel

Chapitre 3- Les tests structurels

3- Méthodes de test structurel

Test structurel (test boîte blanche) (test boîte transparente)

– Utilise la structure interne du programme

I1 O1

I2
O2
I3

2
2- Méthodes de test structurel

Le test structurel s ’appuie sur l ’analyse du code source de

l’application pour établir les tests en fonction de critères de couverture

• Basés sur le graphe de flot de contrôle (toutes les instructions,

toutes les branches, tous les chemins, …)

• Basés sur la couverture du flot de données (toutes les définitions

de variable, toutes les utilisations, …)

• Basés sur les fautes (test par mutants)

3
le graphe de contrôle est un graphe qui résume les structures de contrôle d’un

programme (cf. Figure 2).

4
 2- Méthodes de test structurel

Dans l’approche par boîte blanche on tient compte de la structure interne du

module. On peut s’appuyer sur différents critères pour conduire le test comme :

C1) Le critère de couverture des instructions : le jeu d’essai doit

assurer que toute instruction élémentaire est exécutée au moins une fois.

C2) Le critère de couverture des arcs du graphe de contrôle; le

graphe de contrôle est un graphe qui résume les structures de contrôle d’un

programme (cf. Figure 2).

5
 2- Méthodes de test structurel
Exemple 1 : soit l’algorithme d’Euclide qui calcule le pgcd de 2 nombres (plus grand
commun diviseur) et son graphe de contrôle (cf. Fig. 3).

Le jeu d’essai (x=3,y=3), (x=4,y=3), (x=3,y=4) satisfait les 2 critères de couverture.

6
 2- Méthodes de test structurel
Exemple 1 : soit l’algorithme d’Euclide qui calcule le pgcd de 2 nombres (plus grand
commun diviseur) et son graphe de contrôle (cf. Fig. 3).

Le jeu d’essai (x=3,y=3), (x=4,y=3), (x=3,y=4) satisfait les 2 critères de couverture.

7
 2- Méthodes de test structurel

Exemple 2 : soit le programme suivant

(x = -2) satisfait le critère de couverture des instructions mais pas celui des arcs.

Il faudrait aussi tester ce qui se passe quand x est positif.

8
 2- Méthodes de test structurel

Exemple 2 : soit le programme suivant

(x = -2) satisfait le critère de couverture des instructions mais pas celui des arcs.

Il faudrait aussi tester ce qui se passe quand x est positif.

9
 2- Méthodes de test structurel

Remarque :

la complexité cyclomatique C vaut A – N + 2, où A est le nombre d’arcs

et N est le nombre de noeuds ;

c’est une mesure de la complexité d’un programme ;

C est aussi la borne supérieure du nombre de tests à effectuer

pour que tous les arcs soient couverts au moins une fois.

Dans l’exemple 1, C = 11 – 10 + 2 = 3 ; c’est aussi la taille de notre jeu de tests.

Dans l’exemple 2, C = 5 – 5 + 2 = 2 ; c’est aussi la taille nécessaire pour couvrir tous

les arcs.

10
c3) Le critère de couverture des chemins du graphe de contrôle.

Exemple 3 : soit le programme

Le jeu d’essai (x=0,z=1), (x=1,z=3) vérifie la couverture des arcs mais pas celle
des chemins et ne peut donc détecter une division par zéro.
(x=0,z=3), (x=1,z=1), (x=0,z=1), (x=1,z=3) vérifie la couverture des chemins et
détecte donc la division par zéro. 11
c3) Le critère de couverture des chemins du graphe de contrôle.

Exemple 3 : soit le programme

Le jeu d’essai (x=0,z=1), (x=1,z=3) vérifie la couverture des arcs mais pas celle
des chemins et ne peut donc détecter une division par zéro.
(x=0,z=3), (x=1,z=1), (x=0,z=1), (x=1,z=3) vérifie la couverture des chemins et
détecte donc la division par zéro. 12
Test Structurel

l'analyse du graphe permet d'identifier les données de tests en fonction

d'un chemin dans le graphe.

13
Tests Structurels Ou De Boite Blanche
(White/ Glass Box Testing)
( Suite )

14
Critère « tous les chemins »

On voit sur cet exemple que sur un

programme dont le graphe de contrôle
comporte une quinzaine d'arcs; il
existe un nombre importants de
chemin différents menant du point
A au point B
51+52+....520= 1014 chemins différents
Si un test dure 5ms il faudrait 635
années pour les passer tous!!!

15
Critère « tous les chemins »

− “Tous les chemins” ⇒ “tous les arcs” ⇒ “tous les nœuds”

− Problèmes des boucles :
− Chemin limite : traversée de la boucle sans itération
− Chemin intérieur : itération de la boucle une seule fois
− i-Chemin : itération de la boucle i fois
− Impossible à obtenir en général

− test exhaustif = “tous les chemins avec toutes les valeurs possibles”

16
b) Graphe de contrôle par bloc

1 Read(X) ;
Read(Y) ;
2 While (not (x=y)) do
3 If x > y then
4 X := x – y
Else
5 Y := y – x ;
6 Pgcd := x ;

17
Graphe de flot de contrôle
Entrée : a
a if (x<=0) Sortie : g
b x = -x;
else
Exécutions possible du code :
c x= 1 - x;
d if (x == -1) ch1 = abdeg
e x = 1; ch2 = acdeg
else ch3 = abdfg
f x++;
ch4 = acdfg

18
Chemins exécutables
Sensibiliser un chemin :
On dit qu’une DT sensibilise un chemin, si pour ses valeurs, le code suit le
chemin de contrôle en visitant consécutivement ces nœuds

Chemin exécutable :
Un chemin de contrôle est exécutable si il existe une DT qui le sensibilise

ch1 = abdeg
ch2 = acdeg
ch3 = abdfg
ch4 = acdfg

DT = {x = −2} sensibilise ch3

DT = {x = 3} sensibilise ch4
DT = {x = 2} sensibilise ch2
Aucune valeur de x ne sensibilise ch1 ⇒
chemin non-exécutable

19
Chemins non exécutables

∞ Chemins d’un graphe de contrôle :

− Ne sont pas tous exécutables
− L’ensemble des chemins : exécutables + non exécutables
∞ Détecter les chemins non-exécutables est un problème
indécidable
∞ Etant donné un chemin, trouver une DT qui exécute ce chemin ?
− problème très difficile
∞ Chemins non-exécutables : casse-tête pour le testeur
− une erreur de codage
− du code mort
− un code pas optimisé du tout

20
Couverture des conditions logiques

21
 Couverture des conditions logiques

Dans les couvertures du flôt de contrôle :

on s’appuie sur le flôt de contrôle,
sans regarder le contenu de chacun des noeuds.

Dans la couverture des conditions logiques, au lieu de passer une

fois dans le cas true et une fois dans le cas false, on cherche les
différentes façons de rendre la condition logique vraie ou fausse ;
on augmente ainsi la confiance obtenue dans le logiciel
(couverture). 22
 Couverture des conditions logiques : table de vérité

Couverture des conditions logiques

Plusieurs façons de couvrir les conditions logiques.

Les deux extrêmes :

• évaluer les conditions une a une (n tests)

• la table de vérité de chaque condition (2n tests)

23
 Stratégie pour limiter la combinatoire

stratégie pour l’opérateur OU, effectuer

• un test avec toutes les sous conditions a FAUX
• un test pour chaque sous condition a VRAI unitairement(circulation d’un 1)
• un test avec toutes les sous conditions a VRAI

Par conséquent, n + 2 tests par condition (sur l’exemple,

on fait 5 tests au lieu de 8 : on évite les tests t2, t3, t5)

24
 Stratégie pour limiter la combinatoire

stratégie pour l’opérateur ET, effectuer

• un test avec toutes les sous conditions a VRAI
• un test pour chaque sous condition a FAUX unitairement (circulation d’un 0).
Par conséquent, n + 1 tests par condition
Cette stratégie pour limiter la combinatoire est appelée
couverture des conditions logiques.

25
 Couverture des itérations

Couverture des itérations

Pour chaque boucle :
• 0 itération
• 1 itération
• max - 1 itérations
• max itérations
• max+1 itérations
26
Tests Structurels Ou De Boite Blanche
(White/ Glass Box Testing)
( Suite : Partie 03 )

27
b) Graphe de contrôle par bloc

1 Read(X) ;
Read(Y) ;
2 While (not (x=y)) do
3 If x > y then
4 X := x – y
Else
5 Y := y – x ;
6 Pgcd := x ;

28
b) Graphe de Flots de données
Annoter le graphe par des informations pertinentes quant à la manipulation des
variables (définition d'une variable, utilisation d'une variable).

1 Open fichier1;
Read(X, fichier1);
Read (Y, fichier1);
Z:=0;

2 While X >= Y do
3 Begin
X:= X-Y;
Z:=Y+ 1;
End

4 Print (Y, Fichier2);

Close Fichier1;
Close Fichier2;
29
b) Flots de données

Les principales anomalies sont les suivantes :

- Utiliser une variable sans la définir au préalable.

- Définir une variable sans l'utiliser ultérieurement.

Exemple

Le long chemin est 1.2.3., la variable Z est définie en 1 mais

jamais utilisée. Même chose pour le chemin 1.2.3.2.4

30
Exemple de graphe de Flots de données

1 Read(X) ; Def (X), c_use( X)

B1 B1
2 V := 2 * X Def (V)
3 If X > 0 then C1
P_use( X )
4 Y := X + 1 B2
Else C1
5 Z := 2 * X ; B3
C2 C_use( X) , def (Y) B2 B3 c_use( X),
6 If V < 0 then Def( Z)
7 T := Y B4
Else P_use(V) C2
8 T := Z ; B5

c_use(Y) def(T) B4 B5 c_use( Z),

def (T)

31
Chemin infaisable:
L'anomalie détectée: le chemin B1C1B2C2B4
Read(X) ;
V := 2 * X est un chemin infaisable;
If X > 0 then
Y := X + 1 le chemin B1C1B2C2B5 passant par le 1er
Else
Z := 2 * X ;
then (Y:=X + 1) et le 2ème else c-a-d T:=Z ;
If V < 0 then
T := Y
Else La variable Z est utilisée mais non définie: c'est
T := Z ;
un chemin infaisable ; Pour les systèmes

complexes, il est extrêmement difficile de savoir

si un chemin est faisable ou non c'est un problème

indécidable c.a.d pas de solution générale.

32
Graphe de Flot de Données (Weyuker)

− But : représenter les dependences entre les données du

programme dans le flot d’exécution.

− Graphe de contrôle décoré d’informations sur les données

(variables) du programme.

− Sommets :idem GC

• une définition (= affectation) d’une variable v

est notée def(v)

• une utilisation d’une variable est v notée

P_use(v) dans un prédicat et C_use(v) dans un

 Graphe de Flot de Données (Weyuker)
Exemple

pgcd: integer is
local p,q : integer;
do
read(p, q) B1- Def(p), Def(q)
while p<> q do P1 - Puse(p), Puse(q)
if p > q
P2- Puse(p), Puse(q)
then p := p-q
else q:= q-p B2- Def(p), Cuse(q), Cuse(p)
end -- if B3 - Def(q), Cuse(p),Cuse(q)
end -- while
result:=p
end-- pgcd B4- Cuse(p),
 Graphe de Flot de Données (Weyuker)
Exemple

E
pgcd: integer is
local p,q : integer;
do B1- Def(p), Def(q)
B1
read(p, q)
while p<> q do
P1 - Puse(p), Puse(q)
if p > q P1
p<>q
then p := p-q
else q:= q-p
end -- if P2- Puse(p), Puse(q) P2
end -- while p>q
B3 - Def(q), Cuse(p),Cuse(q)
result:=p B4 B2 B3
B4- Cuse(p),
end-- pgcd
B2- Def(p), Cuse(q), Cuse(p)

S
Graphe de Flot de Données (Weyuker)

36
Graphe de Flot de Données (Weyuker)
Exemple
all-defs:
B1 Def(p) : EB1P1 E
B1 Def(q):EB1P1
B2 def(p):EB1P1P2B2P1B4S
B3 def (q): EB1P1P2B3P1B4S B1- Def(p), Def(q)
B1
all-uses:
P1 Puse(p) : EB1P1
P1 Puse(q) : EB1P1 P1 - Puse(p), Puse(q)
P1
p<>q
P2 Puse(p) : EB1P1P2
P2 Puse(q) : EB1P1P2
P2- Puse(p), Puse(q) P2
B2 Cuse(p) :B2 p>q
B3 - Def(q), Cuse(p),Cuse(q)
Ou EB1P1P2B2
B2 Cuse(q) : EB1P1P2B2 B4- Cuse(p), B4 B2 B3

B3 Cuse(p) : EB1P1P2B3 B2- Def(p), Cuse(q), Cuse(p)

B3 Cuse(p) : B3 ou
EB1P1P2B3 S

B4 Cuse(p) : EB1P1B4
Test par Mutation

Principe :
modifier le programme P en P’ en injectant une modification syntaxique correcte
idéalement, le comportement de P’ doit être différent de celui de P

sélectionner une DT qui met en évidence cette différence de comportement (= tuer

le mutant P’)

Difficile et côuteux, mais grande qualité des tests générés; Plutôt à utiliser comme
critère de qualité .

Idée : si le jeu de test JT peut distinguer le programme initial de ses mutants, c’est

que JT est trés “fin”, donc il devrait trouver aussi les bugs.
38
Test par Mutation
L’idée est de considérer des variantes du programme (les mutants) ne
différant que par une instruction du programme original.

Par exemple, pour l’instruction suivante :

if a > 8 then x := y /* programme P*/

on peut considérer les mutants suivants :

if a *<* 8 then x := y /* Mutant P’1 */

if a *>=* 8 then x := y /* Mutant P’2 */

if a > *10* then x := y /* Mutant P’3 */

if a > 8 then x := *y+1* /* Mutant P’3 */

if a > 8 then x := *z* /* Mutant P’4 */ 39

Test par Mutation

Opérateur de mutation : transforme un programme P syntaxiquement

correct en un programme P’ syntaxiquement correct en opérant une

modification syntaxique.

40
 Test par Mutation
Quelques exemples d’opérateurs de mutation :
 modifier une expression arithmétique e en |e| (ABS)
 modifier une expression arithmétique e en −e
 modifier une expression booléenne b en ¬b
 modifier un opérateur booléen par un autre
 modifier un nom de variable par un autre
 modifier un nom de variable par une constante du bon type
 modifier une constante par une autre constante du bon type
...

Attention : les mutations doivent préserver la correction syntaxique et le typage, sinon le

mutant est trivialement distingué (ne compile même pas).

41
Test par Mutation
Soit un programme P, un ensemble d’opérateurs de mutation (fonctions

de Programme → Programme), un ensemble M de mutants P’ de P, et

un jeu de test TS :

TS tue P’ si il existe DT ∈ TS tel que P(DT) != P’(DT)

différence observationnelle

Le score de mutation de TS est : (# mutants tués) / (# mutants)

Attention, certains P’ sont indistingables de P. on en tient pas compte de ces

mutants indistingables pour le calcul du score de mutation.

probléme : savoir si P et P’ sont distingables est indécidable ; le faire à la main 42

Test par Mutation
critére trés fort mais trés coûteux :
grand nb mutants générés
décider ceux qui sont distingables
trouver les DT pour tuer les mutants distingables

Utilité de la technique des mutant : elle permet de choisir le meilleur jeu de test ( celui

qui tue le plus de mutants. )

43
A test report
id_mut EQ METHODE SOURCE MUTANT COMMENTAIRE

2 1 empty count = lower_bound – 1 count <= lower_bound – 1 jamais <

6 2 full count = upper_bound count >= upper_bound jamais >
16 3 index_of – loop variant count + 2 count * 2 même
24 4 index_of – loop until count or else structure count or structure court test
30 5 make count := 0 (nul) valeur défaut
45 6 make lower_bound, upper_bound (lower_bound – 1), upper_bound redondance
46 7 make lower_bound, upper_bound lower_bound, (upper_bound + 1) redondance
60 I full count = count + 1 = test insuf.
63 II full upper_bound; (upper_bound – 1); test insuf.
72 III put if not has (x) then if true then Spec inc.
75 IV put if not has (x) then if not false then Spec inc.
98 8 index_of – loop variant - Result) - Result + 1) même
99 9 index_of – loop variant - Result) - Result - 1) même
100 10 index_of – loop variant count + 2 - (count + 2 + 1) - même
101 11 index_of – loop variant count + 2 - (count + 2 – 1) - même
102 12 index_of – loop variant count + 2 - (count + 1) + 2 - même
103 13 index_of – loop variant count + 2 - (count – 1) + 2 - même
104 14 index_of – loop variant count + 2 - (count + 3 - même
105 15 index_of – loop variant count + 2 - (count + 1 - même
110 V index_of – loop until > count or > (count + 1) or test insuf.

NON EQUIVALENT

EQUIVALENT 119 mutants, 99 dead, 15 equivalents MS= 99/104=95%