Structural Testing and Control Flow Graph Coverage Techniques

Cette leçon traite du test structurel en génie logiciel, en particulier des techniques de couverture basées sur le graphe de contrôle. Elle s'inscrit dans un cours sur les tests logiciels et aborde les méthodes dynamiques et statiques pour analyser et valider le comportement des programmes à travers leurs structures internes.

Introduction au test structurel

Le test structurel consiste à produire des données de test (DT) qui exécutent un ensemble de comportements du programme afin de vérifier que les résultats obtenus correspondent aux résultats attendus. Il utilise la spécification, le code source et le code exécutable. Deux grandes approches existent :

• Analyse dynamique : nécessite l’exécution du code binaire. Elle inclut les techniques de couverture du graphe de contrôle (instructions, branches, chemins) et du flot de données (définitions et utilisations de variables), ainsi que le test mutationnel, l’exécution abstraite et les tests évolutionnistes.
• Analyse statique : ne nécessite pas l’exécution du code. Elle comprend la revue de code, l’estimation de la complexité, la preuve formelle, l’exécution symbolique et l’interprétation abstraite.

Couverture du graphe de contrôle

Un programme peut être représenté par un graphe de contrôle orienté et connexe G = (N, A, e, s) où :

• e est le sommet d’entrée (début du programme)
• s est le sommet de sortie (fin du programme)
• Chaque sommet représente un bloc d’instructions
• Chaque arc représente un transfert possible d’exécution entre deux nœuds

Une exécution possible correspond à un chemin de contrôle dans ce graphe. Par exemple, pour un programme simple avec des conditions sur la variable x, certains chemins comme [a, c, d, e, g] sont exécutables, tandis que d’autres comme [b, d, f, g] ne le sont pas.

Expression algébrique des chemins

Le graphe G peut être exprimé par une expression algébrique représentant l’ensemble des chemins de contrôle M. Par exemple :

M = abdfg + abdeg + acdfg + acdeg = a.(bdf + bde + cdf + cde).g = a.(b + c)d.(e + f).g

Cette expression est construite à partir des structures séquentielles, alternatives et itératives du programme.

Chemins exécutables et non exécutables

Un chemin est dit exécutable s’il existe une donnée de test (DT) qui le sensibilise, c’est-à-dire qui permet de l’exécuter. Par exemple, DT1 = {x=2} sensibilise le chemin [a, c, d, f, g]. Certains chemins ne sont pas exécutables, ce qui peut indiquer un code mal écrit ou erroné. Trouver une DT pour un chemin donné est un problème indécidable en général.

Exemples d’analyse de graphes de contrôle

Plusieurs exercices illustrent la construction de graphes de contrôle, la détermination des chemins, et la recherche de données de test pour les sensibiliser. Par exemple, un programme avec des conditions imbriquées sur les variables b, c et x conduit à un graphe complexe où certains chemins sont non exécutables. Un autre exemple traite d’un programme avec des boucles et montre que le nombre total de chemins peut être très élevé, mais qu’un seul chemin est réellement exécutable.

Critères de couverture du flot de contrôle

Différents critères permettent d’évaluer la qualité des tests structurels :

• Couverture de tous les nœuds : chaque nœud du graphe doit être visité par au moins un chemin de test. Le taux de couverture TER1 est le ratio du nombre de nœuds couverts sur le nombre total de nœuds.
• Couverture de tous les arcs : tous les arcs du graphe doivent être parcourus. Le taux TER2 est le ratio des arcs couverts sur le nombre total d’arcs. Cette couverture est plus fine que la couverture des nœuds et permet de détecter plus d’erreurs.
• Couverture de tous les chemins indépendants : basée sur le nombre cyclomatique de McCabe V(G), qui est égal à #arcs - #nœuds + 2 (ou au nombre de nœuds de décision + 1 pour des décisions binaires). Ce critère exige de couvrir un ensemble de chemins indépendants qui forment une base pour tous les chemins possibles. Le taux TER3 mesure la couverture de ces chemins.
• Couverture des PLCS (Portions Linéaires de Code Suivies d’un Saut) : une PLCS est une séquence d’instructions entre deux branchements (nœuds dits « saut »). Couvrir toutes les PLCS permet de s’assurer que toutes les portions linéaires du code sont testées. Le taux TER3 peut aussi être défini pour cette couverture.

Hiérarchie des critères de couverture

Les critères de couverture sont hiérarchisés :

• La couverture de tous les chemins implique la couverture des chemins indépendants.
• La couverture des chemins indépendants implique la couverture de tous les arcs.
• La couverture de tous les arcs implique la couverture de tous les nœuds.
• La couverture des PLCS est plus fine que la couverture des arcs.

Couvertures basées sur le flot de données

Cette approche analyse les relations entre instructions en tenant compte des variables définies et utilisées :

• Définition d’une variable : lorsqu’une instruction modifie la valeur d’une variable (affectation, lecture).
• Utilisation d’une variable : lorsqu’une instruction utilise la valeur d’une variable. Deux types d’utilisation :
• p-utilisation : dans le prédicat d’une instruction de décision (if, while, etc.)
• c-utilisation : dans les autres cas (calculs, affectations)

Un chemin d’utilisation relie une instruction de définition d’une variable à une instruction utilisatrice, sans redéfinition intermédiaire.

Critères de couverture du flot de données

• Critère toutes-les-définitions : chaque définition de variable doit être couverte par au moins un chemin d’utilisation.
• Critère tous-les-utilisateurs : couvre tous les utilisateurs (nœuds c-utilisateurs et arcs p-utilisateurs) pour chaque définition accessible.
• Critère tous-les-du-utilisateurs : couvre tous les chemins possibles entre une définition et une référence, en se limitant aux chemins sans cycle.

Ces critères sont hiérarchisés : tous-les-utilisateurs implique toutes-les-définitions, et tous-les-du-utilisateurs est plus exigeant que tous-les-utilisateurs.

Hiérarchie globale des techniques de test structurel

La hiérarchie des critères de couverture, du plus fort au plus faible, est la suivante :

• Tous les chemins
• Tous les du-utilisateurs
• Tous les utilisateurs
• Tous les chemins indépendants
• Tous les c-utilisateurs
• Tous les p-utilisateurs
• Tous les arcs
• Toutes les définitions
• Tous les nœuds

Problèmes et limites du test structurel

Un problème majeur est la présence de chemins non exécutables dans le graphe de contrôle. Il est formellement indécidable de déterminer si un chemin donné est exécutable ou non. La présence de tels chemins est souvent le signe d’un code mal écrit ou erroné. Des outils automatiques basés sur l’interprétation abstraite ou la vérification de programmes peuvent aider à sensibiliser certains chemins, mais la difficulté reste importante.

Exemples et exercices

Plusieurs exercices illustrent la construction de graphes de contrôle, la détermination des chemins, la recherche de données de test, et la couverture selon différents critères. Par exemple :

• Un programme avec des conditions imbriquées sur les variables b, c, x, où il faut construire le graphe, identifier des chemins exécutables et non exécutables, et proposer des données de test couvrant des instructions spécifiques.
• Un programme avec une boucle for, montrant que le nombre total de chemins est très élevé, mais qu’un seul chemin est réellement exécutable.
• Un programme simple avec deux conditions if successives, où certains chemins sont non exécutables, et une proposition de modification pour améliorer la couverture.
• Un programme de recherche d’un élément dans un tableau, avec construction du graphe et calcul du nombre de chemins indépendants.
• Un programme calculant l’inverse de la somme d’éléments d’un tableau, avec calcul des taux de couverture TER1 et TER2.
• Un programme factoriel avec boucle for, pour identifier les PLCS.

Points clés

• Le test structurel vise à couvrir les chemins, nœuds, arcs ou définitions dans un graphe de contrôle représentant un programme.
• Les chemins exécutables sont ceux pour lesquels il existe une donnée de test capable de les sensibiliser ; certains chemins sont non exécutables, ce qui complique la couverture complète.
• Les critères de couverture sont hiérarchisés, du plus faible (tous les nœuds) au plus fort (tous les chemins, tous les du-utilisateurs).
• La couverture du flot de données complète la couverture du flot de contrôle en s’intéressant aux définitions et utilisations des variables.
• Le nombre cyclomatique de McCabe donne une mesure du nombre minimal de chemins indépendants à couvrir.
• Les PLCS sont des séquences d’instructions entre deux branchements et constituent une granularité intéressante pour la couverture.
• La recherche de données de test pour certains chemins est un problème indécidable en général, nécessitant des outils automatiques d’aide.