Le test structurel

Universitylib.com

il y a 4 ans

3: Le test structurel

Statique / Dynamique

Analyse dynamique : nécessite l’exécution du code binaire

Principe : à partir du code source (ou d’un modèle) et spécification, produire des DT qui exécuteront un ensemble de comportements, comparer les résultats avec ceux attendus…

Techniques de couverture du graphe de contrôle
a) Couverture du flot de contrôle (toutes les instructions, branches, ..) b) Couverture du flot de données (toutes les définitions de variables, les utilisations…) 2. Test mutationnel (test par injection de défaut) 3. Exécution abstraite 4. Test évolutionniste (algorithme génétique) 5. …

Analyse statique : ne nécessite pas l’exécution du code binaire

Revue de code 2. Estimation de la complexité 3. Preuve formelle (prouveur, vérifieur ou model-checking) 4. Exécution symbolique 5. Interprétation abstraite

132 P.Félix ~ IUT Info Bordeaux 1 – S4 – McInfo4_ASR Tests – Janvier 2008

Test structurel dynamique avec technique de couverture du graphe de contrôle

But: produire des DT qui exécuteront un ensemble de comportements du programme

Utilise : spécification, code source et code exécutable
Un programme => un graphe de contrôle

x<=0x>0 begin x:=-x b cx:=1-x if (x<=0)then x:=-x else x:=1-x; if (x=-1)then x:=1 else x:=x+1; d x=-1x!=-1 end

x:=1

f eg

x:=x+1

Graphe orienté et connexe (N,A,e,s)

e: un sommet entrée (a)
s: un sommet sortie (g)

Writeln(x)

Un sommet = un bloc d’instructions
Un arc = la possibilité de transfert de l’exécution d’un nœud à un autre
Une exécution possible = un chemin de contrôle dans le graphe de contrôle

[a,c,d,e,g] est un chemin de contrôle [b,d,f,g] n’est pas un chemin de contrôle

133 P.Félix ~ IUT Info Bordeaux 1 – S4 – McInfo4_ASR Tests – Janvier 2008

Expression des chemins d’un graphe de contrôle

Le graphe G peut être exprimé sous une forme algébrique l’ensemble des chemins de contrôle du graphe G :

M = abdfg+abdeg+acdfg+acdeg = a.(bdf+bde+cdf+cde).g

: soit M a

x<=0x>0 x:=-x b cx:=1-x

= a.(b+c)d.(e+f).g (expression des chemins de G)

Construction de l’expression des chemins : x=-1x!=-1 séquentielle quentielle alternative alternative ititérativerative

x:=1

f ex:=x+1

a aag

Writeln(x)

b c Gbb c

abab a.(b+c).d a.(b+c).d a.(a.(baba)*.*.c c a.(a.(baba)4.c.c

134 P.Félix ~ IUT Info Bordeaux 1 – S4 – McInfo4_ASR Tests – Janvier 2008

Notation utilisée (pour rappel…)

Soit X={a,b,c} un alphabet

ε le mot vide
(cb)2=cbcb
b+=b+b2+b3+b4+b5+ …
b*=ε+b+b2+b3+b4+b5+ …
b4=ε+b+b2+b3+b4

135 P.Félix ~ IUT Info Bordeaux 1 – S4 – McInfo4_ASR Tests – Janvier 2008

Chemin exécutable

Read(x) if (x<=0)then x:=-x else x:=1-x; if (x=-1)then x:=1 else x:=x+1; Writeln(x)

DT1={x=2}

DT1 chemin sensibilise exécutable le chemin [acdfg] : [acdfg] est un [abdgf] capable est un de chemin sensibiliser non exécutable ce chemin : aucune DT Sensibiliser intérêt problème chemin des est un de outils non chemin trouver décidable) automatiques peut des parfois DT qui (mais être sensibilise difficile attention un : Existence mauvais de codage chemins ? non exécutables : signe de

136 P.Félix ~ IUT Info Bordeaux 1 – S4 – McInfo4_ASR Tests – Janvier 2008

Read(x) a

x<=0x>0 x:=-x b cx:=1-x

x=-1x!=-1 x:=1

f eg

x:=x+1

Writeln(x)

Chemin exécutable / chemin non exécutable

Nombre de chemins de contrôle de G :
se déduit directement de l’expression des chemins de G
a(b+c)d(e+f)g => 1.(1+1).1.(1+1).1 = 4 chemins de contrôle
Nb chemins exécutables + Nb chemins non exécutables
Parfois le Nb chemins non exécutables peut être important :

begin as:=0 i:=1 s:=0; for i:=1 to 1000 do s:=s+a[i]; bi>1000 end

i<=1000

Expression des chemins de G2 : a.b.(cb)1000.d

c s:=s+a[i] i:=i+1

Nombre de chemins :

1.1.(1.1)1000.1 = 11000 = 1+11+12+ … +11000=1001

Parmi ces 1001 chemins, un seul est exécutable: a.b.(cb)1000.d

137 P.Félix ~ IUT Info Bordeaux 1 – S4 – McInfo4_ASR Tests – Janvier 2008

Exercice 1

lire(b,c,x); if b<c then begin

Donner le graphe de contrôle G(P3) associé au programme P3.

d :=2*b ; f :=3*c if x>=0 then begin y := x ;

e := c ; if (y=0) then begin

a :=f-e ; if d<a then begin writeln(a) end else begin writeln (d) end end end end

Donner 3 chemins de contrôle du graphe G(P3).
Donner l’expression des chemins de contrôle de G(P3).
Soit DT1={b=1,c=2,x=2}. Donner le chemin sensibilisé par DT1.
On s’intéresse aux instructions en italique… Donner des DT qui vont couvrir ces instructions.
Donner un chemin de contrôle non exécutable de G(P3).

138 P.Félix ~ IUT Info Bordeaux 1 – S4 – McInfo4_ASR Tests – Janvier 2008

Problème des chemins non exécutables

Étant donné un chemin qu’on a envie de sensibiliser, comment trouver une DT qui exécute ce chemin ? Problème très difficile:

décider si le chemin est exécutable ou pas; 2. s’il l’est trouver une DT.

Le problème 1 est indécidable.

[indécidable = formellement impossible de construire un algorithme général qui décide de l’exécutablilité ou de la non exécutabilité de n’importe quel chemin]

La présence de chemins non-exécutables est souvent signe de code mal écrit, voire erroné !

Il existe des outils (plus ou moins automatiques) de sensibilisation de chemins (basés sur l’interprétation abstraite ou sur des techniques de vérification de programmes)

141 P.Félix ~ IUT Info Bordeaux 1 – S4 – McInfo4_ASR Tests – Janvier 2008

Exercice 2

Lire(choix)

Donner le graphe de contrôle

if choix=1

then x=x+1 ;

if choix=2

then x=x-1 ;

writeln(choix ;

correspondant au programme P4.

Donner l’expression des chemins de contrôle de G(P4). En déduire le nombre de chemins de contrôle.
Donner les chemins de contrôle non

exécutables. Conclure.

Proposer une nouvelle solution pour ce programme. Construisez son graphe de contrôle et donner l’expression des chemins de contrôle ainsi que le nombre de chemins de contrôle.

142 P.Félix ~ IUT Info Bordeaux 1 – S4 – McInfo4_ASR Tests – Janvier 2008

Exercice 3

Écrivez un algorithme de recherche de l’emplacement d’un

élément e dans un tableau T.

Donner le graphe de contrôle associé.
Donner l’expression des chemins.
Dans le cas où le tableau a une taille de 3, donner le nombre de

chemins de contrôle.

145 P.Félix ~ IUT Info Bordeaux 1 – S4 – McInfo4_ASR Tests – Janvier 2008

Interro

lire(b,c,x) if b<c then begin

d :=2*b f :=3*c if x>=0 then begin y := x

Donnez un graphe de contrôle associé

au code source fourni.

Votre graphe de contrôle a-t-il des

possibilités de réduction ?

e := c if (y=0) then begin

a :=f-e while d<a

begin d:=d+2 end end end else begin b:=b-1 end end

Si oui, réduisez votre graphe de

contrôle.

148 P.Félix ~ IUT Info Bordeaux 1 – S4 – McInfo4_ASR Tests – Janvier 2008

lire b,c,x

Interro (correction) b>=c

b<c

d:=2*b; f:=3*c lire(b,c,x)/*0*/ if b<c /*1*/ x<0

then begin d :=2*b /*2*/ y:=x; e:=cf :=3*c if x>=0 /*3*/ then begin y!=0

y := x /*4*/ e := c 6

a:=f-e

if (y=0) /*5*/ then begin a :=f-e /*6*/ 7while d<a /*7*/

begin d<a 83 9

d:=d+2 /*8*/ end end end else begin b:=b-1/*9*/ end end x>=0

b:=b-1

5y=0

d>=a

d:=d+2

lire b,c,x

Interro (correction) b>=c

b<c

d:=2*b; f:=3*c lire(b,c,x)/*0*/ if b<c /*1*/ x<0

then begin d :=2*b /*2*/ y:=x; e:=cf :=3*c if x>=0 /*3*/ then begin y!=0

y := x /*4*/ e := c 6

a:=f-e

if (y=0) /*5*/ then begin a :=f-e /*6*/ 7while d<a /*7*/

begin d<a 83 9

d:=d+2 /*8*/ end end end else begin b:=b-1/*9*/ end end x>=0

b:=b-1

5y=0

d>=a

d:=d+2

b>=c

lire b,c,x

b<c

Interro (correction)

d:=2*b; f:=3*c lire(b,c,x)/*0*/ if b<c /*1*/ x<0

x>=0

then begin d :=2*b /*2*/ 9

b:=b-1

45 y:=x; e:=c f :=3*c if x>=0 /*3*/ then begin y!=0

y=0

y := x /*4*/ e := c 6

a:=f-e

if (y=0) /*5*/ then begin a :=f-e /*6*/ 7d>=a

while d<a /*7*/ begin d<a

8d:=d+2

d:=d+2 /*8*/ end end end else begin b:=b-1/*9*/ end end

Satisfaction d’un test structurel avec couverture

Soit T un test structurel qui nécessite la couverture d’un ensemble de chemins {δ1, …, δk} du graphe de contrôle.

On notera : T= {δ1, …, δk}

Soit DT une donnée de test qui sensibilise le chemin de contrôle C.

Définition: DT satisfait T ssi C couvre tous les chemins de T.
Exemple : Soient et T1= {δ1, δ2}. le graphe de contrôle G5, δ1=cdebcde, δ2=ce DT1 ={a[1]=-2, a[2]=3, a[3]=17,i=1} satisfait-il T1 ?

DT1 sensibilise M1=abcebcdebcdebf M1= abcebcdebcdebf couvre δ1=cdebcde M1=abcebcdebcdebf couvre δ2=ce Donc DT1 satisfait T1

DT2 ={a[1]=-2, a[2]= 3, a[3]=-17,i=1} satisfait-il T1 ?

aread(i); s:=0;

bi>3i<=3

c a[i]>0

a[i]<=0

e d

i:=i+1;

s:=s+a[i]; G5

152 P.Félix ~ IUT Info Bordeaux 1 – S4 – McInfo4_ASR Tests – Janvier 2008

Hiérarchie des techniques de test structurel

Exemple : considérons le graphe de contrôle G5 et les 2 tests structurels avec couverture T1 et T2 définis par :

δ1=cdebcde, δ2=ce et T1= {δ1, δ2}

δ3=de, δ4=b, δ5=cd et T2= {δ3, δ4 , δ5}.

Lorsque T1 est satisfait, T2 l’est aussi : pourquoi ?

T1 est un test plus fiable (ie. ‘fort’) que T2 et on notera :

T1 ⇒ T2

⇒ est une relation d’ordre partielle (réflexive, antisymétrique, transitive)
⇒ permet de définir une hiérarchie entre les différentes techniques structurelles de test (relation d’ordre partielle)

153 P.Félix ~ IUT Info Bordeaux 1 – S4 – McInfo4_ASR Tests – Janvier 2008

Deux catégories de critère de couverture

Approche ‘Flot de contrôle’ avec couverture de tous les arcs :

DT1={x=-2, y=0} sensibilise le chemin

M1=abcd DT2={x=1, y=0} sensibilise le chemin

M2=ace

Si l’affectation du nœud b est erronée, cette erreur ne sera pas détectée par DT1 et DT2.
Approche ‘Flot de données’

L’affectation de y au nœud b n’est pas

utilisée par DT1 et DT2 : il faudrait tester le chemin abce sensibilisé par la DT3={x=2, y=0}

read(x,y)

x pairx impair y:=y+x/2 b c x<0x>=0 y:=-x writeln(y) d G4ewriteln(y)

154 P.Félix ~ IUT Info Bordeaux 1 – S4 – McInfo4_ASR Tests – Janvier 2008

Couverture sur le flot de contrôle

Critère de couverture « tous-les-nœuds »

But : sensibiliser tous les chemins de contrôle qui nous

permettent de visiter tous les nœuds du graphe de contrôle. Taux de couverture : TER1 (Test Effectiveness Ratio 1 ou C1) TER1 = |{nœuds couverts}| / |{nœuds}|

Critère de couverture « tous-les-arcs »

Si on chercher à couvrir tous les nœuds sans couvrir tous les

arcs, on risque de ne pas détecter certains défauts sur les arcs non couverts… But : sensibiliser tous les chemins de contrôle qui nous

permettent de visiter tous les arcs du graphe de contrôle. TER2 = |{arcs couverts}| / |{arcs}|

Hiérarchie des tests

« tous-les-arcs » ⇒ « tous-les-noeuds »

155 P.Félix ~ IUT Info Bordeaux 1 – S4 – McInfo4_ASR Tests – Janvier 2008

Exercices 4

Donner un graphe de contrôle G et des données de test DTi montrant que le critère « tous les noeuds » est insuffisant pour détecter une erreur.

Calculer le taux de couverture TER1 et TER2 pour votre DT.

Complétez le programme suivant qui calcule l’inverse de la somme des éléments, d’indice entre inf et sup, d’un tableau a contenant des entiers strictement positifs : lire (inf,sup); i:=inf; sum:=0; while (i<= sup) do begin

sum:=sum+a[i]; …/…

Tester le programme avec DT1={a[1]=1; a[2]=2; a[3]=3;inf=1;sup=3}. Que se passe-t-il ?
Calculer TER1 et TER2.

156 P.Félix ~ IUT Info Bordeaux 1 – S4 – McInfo4_ASR Tests – Janvier 2008

Couverture sur le flot de contrôle (suite)

Critère de couverture «tous-les- chemins- indépendants »

V(G) (le nombre de Mc Cabe ou nombre cyclomatique) donne le nombre de chemins indépendants. V(G)=#arcs – #noeuds + 2 [Si que des décisions binaires : V(G)=Nombre de nœuds de décision + 1] (Ce nombre est aussi le nombre de régions du graphe) Taux de couverture : |{chemins indépendants couverts}| / V(G) • Hiérarchie des tests « tous-les-chemins-indépendants » ⇒ « tous-les-arcs »

Exercice 5: Donner le nombre Mc Cabe du graphe associé au programme suivant : if C1 then while (C2) do X1; else X2; X3;

159 P.Félix ~ IUT Info Bordeaux 1 – S4 – McInfo4_ASR Tests – Janvier 2008

Exercices 6

Donner le nombre de chemins indépendants du graphe G. 2. Donner une DT1 qui sensibilise M1=[abcbcbcbd]. 3. Donner une DT2 qui sensibilise M2=[abd]. 4. (M1,M2) constitue une base : donner une relation qui lie M1,

M2 et M3=[abcbd]. 5. Calculer le taux de couverture du critère tous-les-chemins-

indépendants associé à DT1 U DT2.

alire u1

bc d i:=inf; som:=0;

(inf,sup); i>sup

u3 u2 i<=sup

som:=som+a[i] i:=i+1écrire(1/som); Graphe G

161 P.Félix ~ IUT Info Bordeaux 1 – S4 – McInfo4_ASR Tests – Janvier 2008

Couverture sur le flot de contrôle (suite)

Couverture des PLCS (Portion Linéaire de Code Suivie d’un Saut)

PLCS : « séquence d’instructions entre deux branchements »

Principes : 2 types de nœuds dans le graphe de flot de contrôle Type a (ou nœud ‘saut’) : l’entrée, la sortie et les nœuds qui

constituent l’arrivée d’un branchement Type b : les autres nœuds

Définition : On appelle PLCS un chemin partant d’un nœud ‘saut’ et aboutissant à un nœud ‘saut’ ; l’avant dernier et le dernier nœud doivent constituer le seul saut du chemin.

164 P.Félix ~ IUT Info Bordeaux 1 – S4 – McInfo4_ASR Tests – Janvier 2008

Couverture du critère PLCS : Exemple

Soit le programme : 005 INPUT A, C 010 B= 2*A 020 A=A+1 030 IF A<0 THEN GOTO 60 040 B= -A 050 PRINT A+B 060 IF B=2*C THEN GOTO 80 070 A=1:GOTO 90 080 A=-2:GOTO 20 090 PRINT A 100 END Donner le graphe de contrôle. Repérer les nœuds de type ‘saut’. Donner les PLCS.

K05 K05

K20 K20

K30 K30

K40 K40

K60 K60

K70 K70

K80 K80

K90 K90

K05 Type ‘saut’ K100 K100

saut

165 P.Félix ~ IUT Info Bordeaux 1 – S4 – McInfo4_ASR Tests – Janvier 2008

Couverture du critère PLCS : Exemple

Le programme contient 9 PLCS : [5, 20, 30, 60] [5, 20, 30, 40, 60, 80] [5, 20, 30, 40, 60, 70, 90] [20, 30, 60] [20, 30, 40, 60, 80] [20, 30, 40, 60, 70, 90] [60, 80] [60, 70, 90] [80, 20]

K05

K20

K30

K40

Incluses dans les 3 premières…

K60

K70

Si on exécute les 3 chemins :

K80

B1 = [5, 20, 30, 60, 70, 90, 100] B2 = [5, 20, 30, 40, 60, 80, 20, 30, 60, 70, 90, 100]

K90 B3 = [5, 20, 30, 40, 60, 70, 90, 100] => Couverture de la totalité des PLCS

K100

166 P.Félix ~ IUT Info Bordeaux 1 – S4 – McInfo4_ASR Tests – Janvier 2008

Couverture sur le flot de contrôle (suite)

Taux de couverture

TER3 (Test Effectiveness Ratio 3 ou C3) TER3 = |{PLCS couvertes}| / |{ PLCS }|

Hiérarchie des tests

Hiérarchie : TER3=1 ⇒ TER2=1

Autres critères de type PLCS

Chemins composés de 2 PLCS TER4 = |{chemins composés de 2 PLCS couverts}| / |{chemins

composés de 2 PLCS }|

Chemins composés de 3 PLCS, TER5 =

167 P.Félix ~ IUT Info Bordeaux 1 – S4 – McInfo4_ASR Tests – Janvier 2008

Couverture sur le flot de contrôle (suite)

Hiérarchie des tests basés sur le flot de contrôle

tous-les-chemins

tous-les-chemins-indépendants

tous-les-arcs (TER2)

tous-les-nœuds (TER1)

TER5

TER4

TER3

168 P.Félix ~ IUT Info Bordeaux 1 – S4 – McInfo4_ASR Tests – Janvier 2008

Exercice 7

Donnez les PLCS du programme suivant: main() {int i,factoriel; cin>>n;factoriel=1; for(i=1;i<=n;i++) factoriel=factoriel*i; printf(« %d\n »,factoriel); }

169 P.Félix ~ IUT Info Bordeaux 1 – S4 – McInfo4_ASR Tests – Janvier 2008

PLCS : une autre définition

Autre définition…

Définition. Un saut est une arête (s,s’) du graphe de contrôle tq :

– s est le sommet initial du graphe ou bien – s’ est le sommet terminal du graphe ou bien – s est une condition et s’ est le sommet atteint dans le cas ou

s est évalué à faux ou bien – s’ est la condition d’une boucle et s le sommet terminal du

corps de cette boucle

Définition. Une PLCS est un couple [c,s] où c est un chemin c=s1s2…sk tel que :

– s1 est le sommet d’arrivée d’un saut – s1s2…sk est sans saut – (sk,s) est un saut

171 P.Félix ~ IUT Info Bordeaux 1 – S4 – McInfo4_ASR Tests – Janvier 2008

173 P.Félix ~ IUT Info Bordeaux 1 – S4 – McInfo4_ASR Tests – Janvier 2008

Couverture sur le flot de contrôle : pas assez fine !

read(x,y)

x pairx impair y:=y+x/2

b c writeln(y/x) x<0x>=0 y:=-x writeln(y) d eG4writeln(y)

Couvertures basées sur le flot de données

Analyse des relations entre instructions en tenant compte des variables qu’elles utilisent/définissent : on cherchera à couvrir les différentes façons de définir et d’utiliser les variables…

variable définie si sa valeur est modifiée (affectation, lecture)
variable utilisée : si sa valeur est utilisée. 2 classes d’utilisation : 1. p-utilisation : dans le prédicat d’une instruction de décision (if,

while,…) 2. c-utilisation : dans les autres cas (utilisation de la valeur d’une variable pour un calcul) while (i<N) do begin

s := s + i; i := i + 1; end; writeln (s);

← i et N sont p-utilisées

← s et i sont c-utilisées, s est définie ← i est c-utilisée puis définie

← s est c-utilisée

174 P.Félix ~ IUT Info Bordeaux 1 – S4 – McInfo4_ASR Tests – Janvier 2008

Couvertures basées sur le flot de données

Une instruction I est utilisatrice d’une variable x par rapport à une instruction de définition J si :

x est définie en I et référencé en J
x n’est pas redéfinie entre I et J

read(x,y);

Exemple: 2• L’arc (2, 4) est p-utilisateur de x par

x >=100

rapport au nœud 1

x<100

L’instruction ‘x:=x*y’ est c-utilisatrice de y par rapport au nœud 1 3

4 x:=x*y; y:=y+1;

175 P.Félix ~ IUT Info Bordeaux 1 – S4 – McInfo4_ASR Tests – Janvier 2008

Couvertures basées sur le flot de données

Un chemin d’utilisation (c-utilisation ou p-utilisation) est un chemin reliant l’instruction de définition d’une variable à une instruction utilisatrice.

read(x,y);

x >=100

x<100

4 x:=x*y; y:=y+1; 2Exemple : [1,2,4] est un chemin p-utilisation

pour la variable x.

176 P.Félix ~ IUT Info Bordeaux 1 – S4 – McInfo4_ASR Tests – Janvier 2008

Couvertures basées sur le flot de données

Critères

Le critère tous-les-utilisateurs nécessite la couverture de tous les

utilisateurs (nœuds c-utilisateurs ou arcs p-utilisateurs) pour chaque définition et pour chaque référence accessible à partir de cette définition. [tous-les-p-utilisateurs et tous-les-c- utilisateurs]

Le critère toutes-les-définitions nécessite que l’on couvre au

moins un chemin d’utilisation pour chaque définition du graphe.

tous-les-utilisateurs ⇒ toutes-les-définitions

177 P.Félix ~ IUT Info Bordeaux 1 – S4 – McInfo4_ASR Tests – Janvier 2008

Read(x) a

x<=0x>0 y:=-1 b cy:=1

x2>1x2<=1 z:=2

f eg

z:=-2

Writeln(y*z)

178 P.Félix ~ IUT Info Bordeaux 1 – S4 – McInfo4_ASR Tests – Janvier 2008

Critère tous-les-du-utilisateurs

Couverture du critère toutes-les-définitions :

[abdfg] [acdeg]

Couverture du critère tous-les-utilisateurs :

[abdfg] [acdeg]

Remarque : Ces 2 tests ne couvrent pas tous les

chemins d’utilisations : si on rajoute au critère tous- les-utilisateurs le fait qu’on doit couvrir tous les chemins possibles entre définition et référence (en se limitant aux chemins sans cycle) on obtient le critère tous-les-du-utilisateurs

Couverture du critère tous-les-du-utilisateurs :

[abdfg] [abdeg] [acdfg] [acdeg]

TER5

tous-les-du-utilisateurs

TER4

tous-les-utilisateurs

TER3

tous-les-c-utilisateurs

tous-les-p-utilisateurs toutes-les-définitions

179 P.Félix ~ IUT Info Bordeaux 1 – S4 – McInfo4_ASR Tests – Janvier 2008

Hiérarchie des tests structurels

tous-les-chemins

tous-les-chemins-indépendants

tous-les-arcs (TER2)

tous-les-nœuds (TER1)

télécharger gratuitement Le test structurel :