L3 informatique et MIAGE
Année 2016-2017
Génie logiciel avancé
Test structurel à partir du
graphe de flot de contrôle
Delphine Longuet
[email protected]
http://www.lri.fr/~longuet/Enseignements/16-17/L3-GLA
Test structurel (ou test boîte blanche)
Sélection des tests à partir de l'analyse du code source du système
Résultats
Spécification
attendus
sélection
Verdict
oracle
Système Résultats
Tests
exécution des tests
Construction des tests uniquement pour du code déjà écrit
D. Longuet - GLA 2
Test structurel (ou test boîte blanche)
Principe : utiliser la structure du code pour dériver des cas de test
Complémentaire des méthodes de test fonctionnel (ou boîte noire) car
étude de la réalisation et pas seulement de la spécification
Deux méthodes :
●
À partir du graphe de flot de contrôle : couverture de toutes les
instructions, tous les branchements...
●
À partir du graphe de flot de données : couverture de toutes les
utilisations d'une variable, de tous les couples définition-
utilisation...
D. Longuet - GLA 3
Méthodes d'analyse du code
Fonction calculant XN
S:=1 S:=1 dS
E dX dN E
P:=N P:=N uN dP
uP
f f
P>=1 S P>=1 S uS
v v
S:=S*X S:=S*X uS uX dS
P:=P-1 P:=P-1 u d
P P
Graphe de flot de contrôle Graphe de flot de données
D. Longuet - GLA 4
Sélection de tests à partir du code
Idée : Couvrir les chemins d'exécution du programme
Problème : Nombre de chemins infini
Définir des critères de couverture
Critère de couverture : Éléments du code à couvrir par les tests
●
nœuds, arcs
●
décisions
●
couples de définition-utilisation d'une variable...
Objectifs de test définis sur la structure du code
D. Longuet - GLA 5
Graphe de flot de contrôle
Graphe orienté avec un nœud initial E et un nœud final S tel que :
●
un nœud interne est
●
soit un bloc d'instructions élémentaires
●
soit un nœud de décision étiqueté par une condition
●
un arc relie les nœuds correspondant à des instructions ou
conditions successives (flot de contrôle)
bloc d'instructions
S:=1
S:=1; E
P:=N
P:=N;
décision
condition
while P>=1 do
f
P>=1 S
S:=S*X;
P:=P-1; v
endwhile; S:=S*X
P:=P-1
D. Longuet - GLA 6
Encore les triangles
triangle(j,k,l : positive):void
eg := 0;
if j + k <= l or k + l <= j or l + j <= k
then write(“impossible”);
else if j = k then eg := eg + 1; endif;
if j = l then eg := eg + 1; endif;
if l = k then eg := eg + 1; endif;
if eg = 0 then write(“scalene”);
elsif eg = 1 then write(“isocele”);
else write(“equilateral”); endif;
endif;
D. Longuet - GLA 7
Graphe de flot de contrôle associé
j+k<=l
E eg:=0 or k+l<=j write(“impossible”)
or l+j<=k v
f
j=k eg:=eg+1
v
f
j=l eg:=eg+1
v
f
l=k eg:=eg+1
v
f
eg=0 write(“scalene”) S
v
f
f v
write(“equilateral”) eg=1 write(“isocele”)
D. Longuet - GLA 8
Graphe de flot de contrôle associé
j+k<=l
E eg:=0 or k+l<=j write(“impossible”)
or l+j<=k v
f
j=k eg:=eg+1
v
f
Chemin d'exécution j=l eg:=eg+1
v
pour j = 3 f
k = 5
l=k eg:=eg+1
l = 3 v
f
eg=0 write(“scalene”) S
v
f
f v
write(“equilateral”) eg=1 write(“isocele”)
D. Longuet - GLA 9
Graphe de flot de contrôle associé
j+k<=l
E eg:=0 or k+l<=j write(“impossible”)
or l+j<=k v
f
j=k eg:=eg+1
v
f
Chemin infaisable j=l eg:=eg+1
v
f
l=k eg:=eg+1
v
f
eg=0 write(“scalene”) S
v
f
f v
write(“equilateral”) eg=1 write(“isocele”)
D. Longuet - GLA 10
Chemins du graphe de flot de contrôle
Exécution : Chemin allant de E à S dans le graphe de flot de contrôle,
associé à l'ensemble des conditions sur les variables d'entrée qui
permet d'exécuter précisément ce chemin
Pour j = 3, k = 5 et l = 3, conditions du chemin :
¬(j + k ≤ l ∨ k + l ≤ j ∨ l + j ≤ k)
∧j≠k∧j=l∧l≠k
Conditions satisfiables par tout triplet (j, k, l) qui forme un triangle et
tel que j = l et j ≠ k
D. Longuet - GLA 11
Chemins du graphe de flot de contrôle
Exécution : Chemin allant de E à S dans le graphe de flot de contrôle,
associé à l'ensemble des conditions sur les variables d'entrée qui
permet d'exécuter précisément ce chemin
Conditions pour le deuxième chemin :
¬(j + k ≤ l ∨ k + l ≤ j ∨ l + j ≤ k)
∧ j ≠k ∧ j ≠l ∧ l ≠k
∧0≠0∧0≠1
Conditions insatisfiables : il n'existe aucun triplet (j, k, l) tel que ces
conditions soient remplies pendant l'exécution
D. Longuet - GLA 12
Chemins du graphe de flot de contrôle
Exécution : Chemin allant de E à S dans le graphe de flot de contrôle,
associé à l'ensemble des conditions sur les variables d'entrée qui
permet d'exécuter précisément ce chemin
Exécution réelle : Chemin dont les conditions peuvent être satisfaites
Si conditions impossibles à satisfaire, chemin infaisable
(donc pas de test possible pour couvrir ce chemin)
Problème : Comment détecter les chemins infaisables ?
D. Longuet - GLA 13
Chemins infaisables
Existence de chemins infaisables : Problème indécidable
Suite de Syracuse
On ne sait pas si ce programme termine toujours, donc s'il existe des
chemins infaisables de E à S
E
while x<>1 do
if x mod 2 == 0 f
x<>1 S
then x:=x/2;
else x:=3*x+1; v
endif;
endwhile; x mod 2 == 0
v f
x:=x/2 x:=3*x+1
D. Longuet - GLA 14
Conditions de chemin
Existence de chemins infaisables : Problème indécidable
Mais : On sait calculer les conditions pour qu'un chemin donné soit
faisable (conditions de chemin)
On a x = x0 en entrée E
Conditions pour passer une seule fois f
par la boucle dans le then : x<>1 S
x0 ≠ 1 v
et x0 mod 2 = 0 x mod 2 == 0
et x0/2 = 1 v f
Donc il faut que x0 = 2 x:=x/2 x:=3*x+1
D. Longuet - GLA 15
Exécution symbolique
Soit P un chemin de E à S dans le graphe de flot de contrôle
1. On donne des valeurs symboliques aux variables x0, y0, z0...
2. On initialise la condition de chemin à true
3. On suit le chemin P nœud par nœud depuis E :
●
si le nœud est un bloc d'instructions, on exécute les instructions sur
les valeurs symboliques
●
si le nœud est un bloc de décision étiqueté par une condition C :
●
si on suit la branche où C est vraie, on ajoute C à la condition
de chemin, en substituant les variables par leur valeur symbolique
●
si on suit la branche où C est fausse, on ajoute la négation de C
à la condition de chemin, en substituant les variables par leur
valeur symbolique
D. Longuet - GLA 16
Exécution symbolique
État : application associant à chaque variable x du programme une
valeur d'un ensemble Dx
etat : V → (Dx)x ∈ V
x ↦ d ∈ Dx
État symbolique : application associant à chaque variable x du
programme un ensemble de valeurs possibles
etatsym : V → �(Dx)x ∈ V
x ↦ E ⊆ Dx
Représentation d'un état symbolique :
substitution des variables : S ↦ x0, P ↦ n0 – 1, X ↦ x0, N ↦ n0
+ ensemble de conditions (condition de chemin) : n0 ≥ 1 ∧ n0 – 1 < 1
D. Longuet - GLA 17
Exécution symbolique (formellement)
B1 P1 B2
E
S:=1
P>=1 v S:=S*X
P:=N P:=P-1
f
E B1 P1 v B2 P1 f S
S ↦ s0
P ↦ p0
substitution initiale
X ↦ x0
des variables et
N ↦ n0
condition de chemin initiale
true
D. Longuet - GLA 18
Exécution symbolique (formellement)
B1 P1 B2
E
S:=1
P>=1 v S:=S*X
P:=N P:=P-1
f
exécution des instructions de B1
S
sur les valeurs symboliques de S et P
E B1 P1 v B2 P1 f S
S ↦ s0 S↦1 S↦1
P ↦ p0 P ↦ n0 P ↦ n0
X ↦ x0 X ↦ x0 X ↦ x0
N ↦ n0 N ↦ n0 N ↦ n0 ajout de la condition P>=1
true true n0 ≥ 1 en substituant P par sa
valeur symbolique n0
D. Longuet - GLA 19
Exécution symbolique (formellement)
B1 P1 B2
E
S:=1
P>=1 v S:=S*X
P:=N P:=P-1
f
exécution des instructions de B2
S
sur les valeurs symboliques de S et P
E B1 P1 v B2 P1 f S
S ↦ s0 S↦1 S↦1 S ↦ x0 S ↦ x0
P ↦ p0 P ↦ n0 P ↦ n0 P ↦ n0 – 1 P ↦ n0 – 1
X ↦ x0 X ↦ x0 X ↦ x0 X ↦ x0 X ↦ x0
N ↦ n0 N ↦ n0 N ↦ n0 N ↦ n0 N ↦ n0
true true n0 ≥ 1 n0 ≥ 1 n0 ≥ 1 ∧ n0 – 1 < 1
ajout de la négation de la condition P>=1
en substituant P par sa valeur symbolique n0 – 1
D. Longuet - GLA 20
Exécution symbolique (formellement)
B1 P1 B2
E
S:=1
P>=1 v S:=S*X
P:=N P:=P-1
f
E B1 P1 v B2 P1 f S
S ↦ s0 S↦1 S↦1 S ↦ x0 S ↦ x0
P ↦ p0 P ↦ n0 P ↦ n0 P ↦ n0 – 1 P ↦ n0 – 1
X ↦ x0 X ↦ x0 X ↦ x0 X ↦ x0 X ↦ x0
N ↦ n0 N ↦ n0 N ↦ n0 N ↦ n0 N ↦ n0
true true n0 ≥ 1 n0 ≥ 1 n0 ≥ 1 ∧ n0 – 1 < 1
Condition de chemin : n0 ≥ 1 ∧ n0 – 1 < 1 ⇔ n0 = 1
D. Longuet - GLA 21
Exécution symbolique (notations allégées)
E x condition de chemin
E x0 true
P1
f
S
x<>1
P1 x0 x0 ≠ 1
v
P2
P2 x0 x0 mod 2 = 0
x mod 2 == 0
v f
B1 x0/2
B1 x:=x/2 x:=3*x+1 B2 P1 x0/2 x0/2 = 1
S x0/2
Condition de chemin : x0 ≠ 1 et x0 est pair et x0/2 = 1
Satisfaite par x0 = 2
D. Longuet - GLA 22
Exécution symbolique (notations allégées)
E x condition de chemin
E x0 true
P1
f
S
x<>1
P1 x0 x0 ≠ 1
v
P2
P2 x0 x0 mod 2 ≠ 0
x mod 2 == 0
v f
B2 3x0+1
B1 x:=x/2 x:=3*x+1 B2 P1 3x0+1 3x0+1 = 1
S 3x0+1
Condition de chemin : x0 ≠ 1 et x0 est impair et 3x0+1 = 1
Impossible à satisfaire : chemin infaisable
D. Longuet - GLA 23
Tests pour un critère de couverture
Critère de couverture : Condition caractérisant un ensemble de
chemins du graphe de flot de contrôle
Génération de tests grâce à un critère de couverture :
1. Sélectionner un ensemble (minimal) de chemins satisfaisant le
critère
2. Éliminer les chemins infaisables. Chaque chemin faisable définit un
objectif de test (ensemble de conditions sur les entrées)
3. Générer un cas de test pour chaque chemin (choisir des valeurs
satisfaisant l'ensemble de conditions associé au chemin)
D. Longuet - GLA 24
Exemple fil rouge : contains
Renvoie true si et seulement si l'élément v apparaît dans le tableau
t de longueur n
boolean contains(int t[], int n, int v) {
int i = 0;
boolean res = false;
while(i < n && !res) {
if(t[i] == v) {
res = true;
}
i++;
}
return(res);
}
D. Longuet - GLA 25
Critère « toutes les instructions »
Satisfait par un ensemble de chemins T si pour chaque nœud du
graphe, il existe un chemin dans T passant par ce nœud
f x=0 P1
v Critère satisfait par le chemin
B1 x:=1
P1 B1 B2
y:=1/x B2
Limite du critère : Ne couvre pas nécessairement tous les arcs
Ici, division par 0 non couverte
D. Longuet - GLA 26
Critère « toutes les décisions »
Satisfait par un ensemble de chemins T si pour chaque nœud de
décision du graphe, il existe un chemin dans T rendant la décision
vraie et un autre chemin rendant la décision fausse
Critère satisfait par les chemins
P1 a<2 && b=a
v f
P1 B1 et P1 B2
v f
B1 x:=2-a B2 x:=a-2 Chemin P1 B1 : {a = 1, b = 1}
Chemin P1 B2 : {a = 3, b = 3}
●
Également appelé critère « tous les arcs »
●
Plus fort que critère « toutes les instructions » : couverture de
toutes les décisions implique couverture de toutes les instructions
D. Longuet - GLA 27
Critère « toutes les décisions »
Limite du critère : Ne couvre pas nécessairement toutes les valeurs
possibles des sous-conditions
Ici, cas où b ≠ a non couvert
Solution : Décomposer les conditions multiples
a<2
v f
a<2 && b=a
v f b=a b=a
f
v f v
x:=2-a x:=a-2
x:=2-a x:=a-2
D. Longuet - GLA 28
Critère « toutes les conditions multiples »
Satisfait par un ensemble de chemins T si :
●
critère « toutes les décisions » satisfait par T
●
toutes les combinaisons de toutes les valeurs de toutes les sous-
conditions couvertes
Critère satisfait par les chemins :
P1 a<2 && b=a
v f
P1 B1 avec a < 2 et b = a
P1 B2 avec a ≥ 2 et b = a
B1 x:=2-a B2 x:=a-2 P1 B2 avec a ≥ 2 et b ≠ a
P1 B2 avec a < 2 et b ≠ a
Équivalent à « toutes les décisions » avec conditions décomposées
Problème : nombre de chemins exponentiel en fonction du nombre de
sous-conditions
D. Longuet - GLA 29
Critère « toutes les conditions multiples »
if (A && (B || C))
Toutes les décisions :
A B C décision
0 1 1 0
1 1 1 1
D. Longuet - GLA 30
Critère « toutes les conditions multiples »
if (A && (B || C))
Toutes les conditions multiples :
A B C décision
0 0 0 0
0 0 1 0
0 1 0 0
Comment limiter
0 1 1 0
la combinatoire ?
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
D. Longuet - GLA 31
Critère MC/DC
Objectif : améliorer le critère de couverture toutes les décisions en
contrôlant la combinatoire
Principe : on ne considère une combinaison de valeurs faisant varier
une sous-condition que si cette sous-condition influence la décision
if (A && (B || C))
Pour A :
A B C décision
0 1 1 0
1 1 1 1
D. Longuet - GLA 32
Critère MC/DC
MC/DC : modified condition/decision coverage
Critère « toutes les conditions/décisions modifié » : Satisfait par un
ensemble de chemins T si :
●
critère « toutes les décisions » satisfait par T
●
toutes les valeurs de toutes les sous-conditions couvertes
●
chaque valeur d'une sous-condition influence la décision lorsque
les autres sous-conditions sont fixées
D. Longuet - GLA 33
Critère MC/DC
if (A && (B || C))
A B C décision
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 0 A
1 0 0 0 B et C
1 0 1 1 C
1 1 0 1 B
1 1 1 1 A
D. Longuet - GLA 34
Critères sur les conditions et décisions
E
invsum(int a[],int n):float i := 0;
i := 0; B1 sum := 0;
sum := 0;
while (i<n) do
P1
sum := sum + a[i]; f
i := i + 1; i < n S
endwhile; v
return 1/sum;
sum := sum + a[i];
B2
i := i + 1;
Critère « toutes les décisions » satisfait par le chemin E B1 P1 B2 P1 S
v f
Limite des critères sur les conditions : manque chemins à problèmes
Ici, division par 0 si tableau vide non détectée
D. Longuet - GLA 35
Critère « tous les chemins »
Satisfait seulement par l'ensemble des chemins du graphe
Problème : Impossible à satisfaire dès qu'il y a des boucles
Affaiblissements possibles :
●
« tous les chemins de longueur au plus k » (en nombre de
nœuds)
●
« tous les chemins passant entre 0 et k fois dans chaque boucle »
(aussi appelés k-chemins)
D. Longuet - GLA 36
Hiérarchie des critères de couverture
pour le graphe de flot de contrôle
toutes les conditions tous les chemins
multiples
tous les chemins de
plus fort que
MC/DC longueur au plus k
toutes les décisions
tous les noeuds
D. Longuet - GLA 37
