📘 Approche structurelle

1. Présentation

L’approche structurelle considère comme point de départ le code source du logiciel testé. Le but est de mettre au point suffisament de scénarios de test pour couvrir efficacement le code source, selon différents critères (instructions, conditions, chemins, etc.). On qualifie aussi cette méthode de boîte blanche car elle nécessite l’analyse du code source du logiciel.

Cette méthode ne peut donc s’appliquer que si on a accès au code source, et si on en possède une compréhension suffisante.

Le point de départ de cette méthode est la modélisation du logiciel sous la forme d’un graphe de flôt de contrôle (CFG), et de s’en servir pour trouver les meilleurs données d’entrée permettant d’obtenir la meilleure couverture.

Cette méthode repose tout de même sur la spécification du logiciel pour la définition des oracles des scénarios de test.

2. Modélisation en graphe de flot de contrôle

2.1. Définition et exemples

Un graphe de flot de contrôle (en anglais, control flow graph, ou CFG) modélise l’ensemble des chemins potentiels qui existent au sein d’un programme, afin de pouvoir notamment formaliser des métriques ou des critères de couverture basés sur ces chemins.

Le graphe de flot de contrôle d’un programme est un graphe orienté composé :
- d’un ensemble de sommets, chaque sommet pouvant représenter au choix :
  - l'entrée du programme nommée E,
  - la sortie du programme nommée S,
  - un bloc élémentaire du programme, c’est à dire une séquence d’instructions et/ou de prédicats toujours exécutés ensemble − par convention on nommera chaque bloc élémentaire en fonction des lignes de code auquelles il se rapporte (ex. 1−3 signifie le bloc élémentaire pour les lignes 1 à 3),
- et d’un ensemble d'arcs pouvant représenter au choix :
  - une prise de décision, c’est à dire une des évaluations possibles d’un prédicat d’une conditionnelle ou d’une boucle,
  - le passage automatique d’un bloc élémentaire à un autre.

Pour factoriser graphiquement plusieurs arcs qui vont tous vers le même nœud, on peut dessiner un petit rond blanc de jonction qui ne correspond à aucun bloc élémentaire. ATTENTION : c’est juste une astuce graphique, cela n’ajoute pas réellement de nœud ni d’arc au CFG !

Exemple 1. Un mini programme et son CFG

Avec un petit programme on obtient le CFG suivant, avec trois sommets correspondant aux blocs élémentaires, un sommet pour l’entrée du programme, un sommet pour la sortie du programme, deux arcs correpondants aux deux évaluations possibles du prédicat a, et deux arcs correspondants aux passages automatiques vers la sortie :

if a
then  
    i1
else 
    i2

On peut ainsi représenter graphiquement les CFGs des principales structures de contrôle (if, while, for, etc.) :

Figure 1. CFGs des structures de contrôle classiques

Pour mieux comprendre, quelques exemples :

Exemple 2. Un programme un peu plus compliqué et son CFG

void function(int x) {
    if (x < -1)
        x = -x;
    else
    fi
    if (x == -1)
        x = 1;
    else
        x = x + 1;
    fi
}

Exemple 3. Exception

public static double divide(int x, int y) {
    if (y == 0) {
        throw new Exception("Cannot divide by zero!");
    }
    return (double)x / (double)y;
}

Une exception est donc juste un sommet avec une transition vers la sortie, comme un return.

Exemple 4. Comparaison de chaines de caractères et son CFG

Cette fonction a été reprise de cette page de Rosetta Code. Il n’est pas demandé de comprendre ce qu’elle fait : elle sert ici uniquement d’exercice de comprehension structurelle du code.

public static void stringMatch(String one, String two) {
    boolean match = false;
    if (one.charAt(0) == two.charAt(0)) {
        System.out.println(match = true);
    } else {
        System.out.println(match);
    }
    for (int i = 0; i < two.length(); i++) {  
        int temp = i;
        for (int x = 0; x < one.length(); x++) {
            if (two.charAt(temp) == one.charAt(x)) {
                System.out.println(match = true);
                i = two.length();
            }
        }
    }
    int num1 = one.length() - 1;
    int num2 = two.length() - 1;
    if (one.charAt(num1) == two.charAt(num2)) {
        System.out.println(match = true);
    } else {
        System.out.println(match = false);
    }
}

On peut noter qu’il est nécessaire de découper la déclaration de chaque boucle for en trois parties :

L’initialisation, (init) qui n’a lieu qu’une seule fois :
L’évaluation de la condition (cond), qui a lieu au début puis à chaque tour de boucle :
L’incrémentation (incr), qui a lieu à chaque tour de boucle.

On peut voir que des appels de la méthode charAt sont utilisés dans ce code. Or, il est possible que charAt envoie une exception si l’indice passé en argument est invalide. Ce CFG est donc légèrement incomplet, et nous allons voir juste après comment représenter les envois d’exception.

2.2. Appels de méthodes pouvant émettre des exceptions

Dans un langage comme Java, il est possible qu’un appel de méthode entraîne un envoi d’exception, et interrompe par conséquent le flot d’exécution. On peut distinguer principalement deux cas :

l’appel de méthode est réalisé au sein d’une construction try/catch, ainsi si la méthode envoie une exception on poursuit l’exécution dans le bloc catch associé,
l’appel de méthode est réalisé en dehors d’une construction try/catch, ainsi si la méthode envoie une exception on sort de la méthode (presque comme un return).

Par exemple, si on considère la méthode suivante :

Méthode divide qui envoie une exception

/**
 * Divide two numbers.
 * @param dividend the dividend
 * @param divisor the divisor
 * @return the result of the division
 * @throws ArithmeticException if divisor is zero
 */
public static double divide(double dividend, double divisor) throws ArithmeticException { … }

On peut voir qu’il est clairement annoncé qu’une exception ArithmeticException sera envoyée en cas de diviseur égal à zéro.

Par conséquent, si on écrit le code suivant qui utilise cette méthode au sein d’un try/catch :

Utilisation de divide dans un try/catch

public void compute1(double x, double y) {
    double z = 0;
    try {
        z = divide(x, y);
    } catch (ArithmeticException e) {
        System.out.println("A problem occurred");
    }
    return z + 10;
}

On peut représenter ce code en CFG de la manière suivante :

Figure 2. CFG de compute1

Et si on écrit le code suivant qui utilise cette méthode sans try/catch :

Utilisation de divide sans try/catch

public void compute2(double x, double y) throws ArithmeticException {
    double z = divide(x, y);
    return z + 10;
}

On peut représenter ce code en CFG de la manière suivante :

Figure 3. CFG de compute2

Il peut cependant arriver qu’un appel de méthode ne puisse pas entraîner d’envoi d’exception, par exemple si une vérification est réalisée en amont de l’appel.

Par conséquent, si on écrit le code suivant :

Utilisation de divide sans envoi possible d’exception

public void compute3(double x, double y) throws ArithmeticException {
    if (y == 0) {
        return -1;
    }
    double z = divide(x, y);
    return z + 10;
}

Ici il est strictement impossible que divide envoie une exception, car y ne pourra jamais être égal à zéro.

On peut alors représenter ce code en CFG de manière simplifiée, sans prendre en compte le possible envoi d’une ArithmeticException lors de l’appel à divide :

Figure 4. CFG de compute3

Exemple 5. Usage de Objects.requireNonNull dans une méthode sum

Au sein de la classe utilitaire java.util.Objects, la librairie standard Java fournit la méthode suivante permettant de vérifier qu’un objet ne soit pas null :

Spécification de la méthode requireNonNull (reformulé depuis la documentation Java)

/**
 * Checks that the specified object reference is not null.
 *
 * @param obj the object reference to check for nullity
 * @return obj if not null
 * @throws NullPointerException if obj is null
 */
public static Object requireNonNull(Object obj) throws NullPointerException { … }

On fait usage de requireNonNull dans la méthode suivante :

Méthode sum qui utilise requireNonNull

public void sum(List<Integer> values) throws NullPointerException {
    Objects.requireNonNull(values);
    int result = 0;
    for (int value : values){
        result = result + value;
    }
    return result;
}

On peut représenter ce code en CFG de la manière suivante, en prenant bien en compte l’envoi d’exception possible de la part de requireNonNull :

Figure 5. CFG de sum

À la simple lecture du code, il n’est pas toujours facile de prévoir qu’une exception est susceptible de se produire lors d’un appel de méthode. Il est donc nécessaire d’arbitrer au cas par cas chaque appel de méthode, lors de la réalisation d’un CFG.

2.3. Décomposition des conditionnelles

Il arrive fréquemment dans un programme qu’une conditionnelle prenne la forme :

d’une disjonction : x1 ∨ x2 ∨ x3 (typiquement écrit en code x1 || x2 || x3),
ou d’une conjonction : x1 ∧ x2 ∧ x3 (typiquement écrit en code x1 && x2 && x3).

Ainsi, si un programme prend la forme suivante :

Exemple de conditionnelle avec disjonction

if (x1 || x2 || x3) {
    do();
}

On serait tenté de représenter le graphe de flot de contrôle suivant :

Figure 6. Première tentative de CFG pour une disjonction (non finale)

Cependant, deux inconvénients principaux apparaissent avec cette tentative.

D’abord, la structure de graphe ne fait pas apparaître le fait qu’il existe plusieurs manière de passer du sommet 1 au sommet 2, du fait de la disjonction : soit via la condition x1, soit via la condition x2, soit via la condition x3 Le même problème apparaît dans le cas d’une conjonction, car le CFG ne ferait pas apparaître qu’il y a plusieurs manières de ne pas passer du sommet 1 au sommet 2.

Ensuite, la structure de graphe ne reproduit pas fidèlement la réalité lorsque le calcul de la conditionnelle est effectué avec "court-circuit" − ce qui est le cas dans un grand nombre de langages de programmation, notamment Java. L’évaluation avec court-circuit, signifie qu’une disjonction/conjonction est toujours évaluée de manière à arrêter le calcul dès que le résultat est assurément vrai ou faux.

Dans le cas d’une disjonction écrite x1 ∨ x2 ∨ x3, on regarde d’abord la valeur de x1.
- Si x1 est vrai, le calcul s’arrête sans regarder x2 ou x3.
- Si x1 est faux, on regarde la valeur de x2, et ainsi de suite.
Dans le cas d’une conjonction écrite x1 ∧ x2 ∧ x3, on regarde d’abord la valeur de x1.
- Si x1 est faux, le calcul s’arrête sans regarder x2 ou x3.
- Si x1 est vrai, on regarde la valeur de x2, et ainsi de suite.

Ainsi, pour régler ces deux inconvénients, une solution est de faire apparaître explicitement l’évaluation avec court-circuit de la manière suivante :

Figure 7. Seconde tentative de CFG pour une disjonction (version finale)

Ce graphe fait apparaître une rend visible qu’il existe différentes manières d’exécuter ce programme, en fonction des valeurs de x1, x2 et x3.

Pour une conjonction, le résultat est similaire mais inversé :

Exemple de conditionnelle avec conjonction

if (x1 && x2 && x3) {
    do();
}

Figure 8. CFG pour une conjonction

Exemple 6. Calcul de PGCD en Java et son CFG

/** 
 * Calcule le PGCD de deux nombres strictement positifs.
 * @param p le premier nombre
 * @param q le second nombre
 * @return le PGCD de p et q
 * @throws IllegalArgumentException si p ou q ne sont pas strictement positifs
*/
public static int pgcd(int p, int q) {
    if (p < 1 || q < 1) {
        throw new IllegalArgumentException("p et q doivent être strictement positifs");
    }
    while (p != q) {
        if (p > q) {
            p = p - q;
        } else {
            q = q - p;
        }
    }
    return p;
}

On peut noter l’utilisation graphique d’une jonction après les nœuds 14 et 16, pour éviter de tirer deux flèches vers le nœud 12. Attention, c’est juste une astuce graphique, car en vérité on doit bien compter qu’il existe un arc entre 14 et 12, ainsi qu’un arc entre 16 et 12 !

Exemple 7. CFG pour isPalindrome

On s’intéresse au code qui implémente l’opération principale de PALINDROME, à savoir isPalindrome :

Implémentation de PALINDROME

public class BasicPalindrome implements Palindrome {
    @Override
    public boolean isPalindrome(String word) throws IllegalArgumentException, NullPointerException {
        Objects.requireNonNull(word);
        if (word.isEmpty() || !Pattern.matches("[\\p{Alpha}]*", word)) {
            throw new IllegalArgumentException();
        }
        for (int i = 0; i< word.length() / 2; i++ ) {
            char f = word.charAt(i);
            char l = word.charAt(word.length() - i - 1);
            if (f != l) {
                return false;
            }
        }
        return true;
    }

En prenant en compte la spécification de requireNonNull vue dans un précédent exemple, on en déduit le CFG suivant :

Figure 9. CFG de isPalindrome

Bien que le CFG proposé prenne en compte la possibilité que requireNonNull émette une exception, on ne représente ici pas les exceptions que pourraient en principe envoyer les méthodes matches, length et charAt, car il est garanti que word ne soit jamais null dès la ligne 4, et que word ne soit jamais vide dès la ligne 8.

2.4. Décomposition des opérateurs ternaires

L'opérateur ternaire − généralement symbolisé par ? − permet de définir des expressions conditionnelles de manière compacte, sans nécessiter de conditionnelle complète avec if. Par exemple cette ligne :

String s = x ? "Yes" : "No";

signifie que s prend la valeur "Yes" si x est vrai, et prend la valeur "No" si x est faux.

En terme de graphe de flot de contrôle, puisque cette expression occupe une seule ligne, on serait tenté de la représenter par un unique sommet. Cependant, cela ne ferait pas apparaître qu’il y structurellement deux manières différentes d’exécuter cette ligne − ou, dit autrement, que l’on peut exécuter une partie différente de cette ligne en fonction de la condition posée.

Ainsi, on dans un graphe de flot de contrôle, on préférera décomposer un opérateur ternaire de la manière suivante :

Figure 10. CFG pour un opérateur ternaire

3. Élaborer des chemins et leurs scénarios de test

3.1. Chemins d’exécution

L’idée principale de cette méthode est d’exploiter le graphe de flot de contrôle (CFG) pour choisir les données d’entrées des scénarios de test. Pour cela, on raisonne sur les différentes manières de parcourir le CFG lorsque le code est

On appelle chemin d’exécution une suite d’arcs (ou une suite de sommets) rencontrés dans le graphe, en partant du sommet d’entrée, et en allant jusqu’au sommet d’arrivée.

Dès lors qu’un CFG possède une boucle (du fait d’un while ou d’un for), alors le nombre de chemins théorique est infini. En effet, il est toujours possible de définir un chemin supplémentaire qui fait un tour supplémentaire dans la boucle !

Exemple 8. Exemples de chemins dans isPalindrome

On s’intéresse au code de PALINDROME, et plus précisément sur la méthode isPalindrome implémentée dans la classe BasicPalindrome.

Implémentation de PALINDROME

public class BasicPalindrome implements Palindrome {
    @Override
    public boolean isPalindrome(String word) throws IllegalArgumentException, NullPointerException {
        Objects.requireNonNull(word);
        if (word.isEmpty() || !Pattern.matches("[\\p{Alpha}]*", word)) {
            throw new IllegalArgumentException();
        }
        for (int i = 0; i< word.length() / 2; i++ ) {
            char f = word.charAt(i);
            char l = word.charAt(word.length() - i - 1);
            if (f != l) {
                return false;
            }
        }
        return true;
    }

On réalise un graphe de flot de contrôle :

Figure 11. CFG de isPalindrome

Dans ce CFG, quelques chemins possibles sont :

ch1: (E, 4, S)
ch2: (E, 4, 5a, 5b, 8-init, 8-cond, 9−11, 8−incr, 8−cond, 15, S)
ch3: (E, 4, 5a, 5b, 8-init, 8-cond, 15, S)

3.2. Exécutabilité d’un chemin

Bien qu’un chemin puisse formellement exister dans un graphe de flot de contrôle, cela ne signifie pas forcément que ce chemin corresponde à une exécution possible du code correspondant. Il ne sera par exemple jamais possible d’exécuter une affectation comme x=5;, puis de traverser l’intérieur d’un conditionnelle qui débute par if (x==10), et cela même si le CFG fera apparaître un chemin qui traverse ces deux lignes.

Concrètement, un chemin est dit exécutable s’il existe des données d’entrée qui vont entraîner une exécution qui passe exactement par ce chemin. Un même chemin pourra souvent être exécuté à l’aide de différentes possibilités de données d’entrée.

Exemple 9. Données d’entrée pour des chemins dans isPalindrome

Choix de donnée d’entrée possible pour emprunter ch1: word=null.
Choix de donnée d’entrée possible pour emprunter ch2: word="aa".
Mais aucune valeur de word ne permet d’emprunter ch3. En effet, ce chemin signifie ne jamais emprunter la boucle for, ce qui nécessite que word possède une taille égale à zéro. Or, une exception sera forcément envoyée en ligne 6 si word est vide. Il est donc impossible de sortir de la boucle sans avoir effectué au moins un tour de cette dernière, ce qui signifie que ce chemin est non-exécutable.

Comme en témoigne l’exemple, le fait qu’un chemin ne soit pas exécutable ne signifie pas qu’il y a un problème dans le code. C’est simplement que l’algorithme n’est pas prévu pour passer par certaines lignes avant ou après d’autres.

Il est rare que tous les chemins d’un graphe soient exécutables. Malheureusement, détecter les chemins non-exécutables est un problème indécidable. Plus généralement, étant donné un chemin, trouver des données d’entrée permettant l’exécution de ce chemin est un problème souvent difficile.

3.3. Mise au point de scénarios de test

Une fois le programme modélisé sous forme de CFG, les chemins possibles identifiés, et les données d’entrée identifiées pour les chemins exécutables, il ne reste plus qu’à :

Choisir quels chemins exécutables doivent être testés à l’aide d’un critère de couverture. C’est l’objectif des deux sections suivantes du chapitre.
Pour chaque chemin exécutable devant être testé, mettre au point un scénario de test complet, et l’ajouter à la suite de tests.

Pour ce second point, comme nous avons déjà obtenu les données d’entrées nécessaires à un chemin devant être testé, il ne manque plus qu’à définir un oracle cohérent avec ce chemin d’exécution, qui permettra de vérifier que le logiciel s’est correctement comporté sur ce chemin d’exécution.

Pour ce faire, il est nécessaire de reposer sur la spécification du logiciel testé, qui est la seule source d’information décrivant quels sont les comportements valides du logiciel. Plus précisément, pour un lot de données d’entrées correspondant à un chemin à exécuter, on ira chercher dans la spécification quel comportement est censé produire le logiciel avec de telles données d’entrée, et on définira un oracle en conséquence.

Exemple 10. Mise au point de scénarios de test pour isPalindrome

Pour pouvoir déterminer les oracles nécessaires, on regarde à nouveau la spécification de isPalindrome :

Spécification de isPalindrome

interface Palindrome {
    /**
     * Verifies that a word is a palindrome.
     * Ignores the character case.
     * 
     * @return true if word is a palindrome, false otherwise.
     * @throws NullPointerException if word is null
     * @throws IllegalArgumentException if word is empty

Puis, à partir des chemins exécutables ch1 et ch2, on établit les scénarios de test suivants :

Paramètres d’entrée Oracle

	Paramètres d’entrée	Oracle
	`word` : string	`result`	`NullPointerException`	`IllegalArgumentException`
ch1	`null`	−	✕
ch2	`"aa"`	`true`

word : string

result

NullPointerException

IllegalArgumentException

ch1

null

−

ch2

"aa"

true

4. Le ciblage en approche structurelle

4.1. Problème : nombre trop important de chemins

Nous avons vu qu’il est possible de lister des chemins d’exécution possibles à partir d’un CFG, et que chaque chemin d’exécution élaboré peut potentiellement être traduit en scénario de test. Il est même envisageable, lorsque la complexité est raisonnable, d’énumérer tous les chemins possibles d’un CFG, ce qui permet de s’assurer que nous testerons bien toutes les possibilités d’exécution.

On constate cependant que différents problèmes se posent :

si un CFG possède au moins une boucle, alors le nombre de chemins possibles est théoriquement infini, et il est alors impossible de tous les énumérer ;
si un CFG est trop grand et trop complexe, il ne sera pas soutenable d’en énumérer tous les chemins possibles, même sans boucle. Il suffit par exemple d’avoir 5 conditionnelles (if…then…else) à la suite les unes des autres pour devoir énumérer 2×2×2×2×2 = 32 chemins différents !
même si on arrivait à énumérer tous les chemins possibles, la suite de tests qui en résulterait serait très volumineuse, ce qui représente un coût important (coût de développement, coût de maintenance, temps d’exécution, etc.).

4.2. Solution : cibler des morceaux de CFG

Comme vu précédemment, pour résoudre ces problèmes, l’étape logique suivante est la génération de cibles pertinentes. Ces cibles vont permettre de se concentrer sur un sous-ensemble de chemins parmi l’ensemble des chemins possibles, à savoir les chemins capables de couvrir les dites cibles.

En approche structurelle, une cible donnée prend la forme d’un morceau de CFG. Un morceau pourra prendre différentes formes (sommets, arcs, chemins entiers). On considère qu’un chemin (et par extension le scénario de test résultant) couvre une telle cible si ce chemin contient l’intégralité du morceau défini dans la cible.

Exemple 11. Quelques cibles arbitraires pour isPalindome en approche structurelle

En se basant la modélisation en CFG réalisée précédemment pour isPalindrome, soit l’ensemble arbitraire de cibles suivantes :

Le sommet 5a − correspond à la ligne 5, condition word.isEmpty()
Le sommet 8-incr − correspond à la ligne 8, incrémentation de la boucle
L’arc 4→S − correspond au passage de la ligne 4 à la sortir de la fonction par une NullPointerException
L’arc 5b→8-init − correspond au passage de la ligne 5 à l’initialisation de la boucle en ligne 8
L’arc 9-11→12 − correspond au passage de la ligne 11 à la ligne 12
Le chemin entier (E,5a,5b,8-init,8-cond,9-11,12,S) − correspond à une exécution avec return false lors du premier passage dans la boucle

Soit une suite de tests obtenue à partir de l’ensemble des chemins exécutables [ch1, ch2] (établis précédement pour ce problème de test). En terme de couverture, on peut constater que :

ch1 couvre la cible 3
ch2 couvre les cibles 1, 2, 4

Une telle suite de tests couvrirait donc les cibles {1,2,3,4}, soit ~67% des cibles de l’ensemble arbitraire considéré.

Pour déterminer un ensemble intéressant de cibles, on peut reposer sur des critères de couverture adaptés à l’approche structurelle. Dans ce chapitre, trois types de critères sont présentés : les critères sur les sommets, les critères sur les arcs, et les critères sur les chemins.

5. Critères de couverture

Il existe de nombreux critères de couverture, tous basés sur le CFG, notamment :

Couverture de toutes les instructions du programme, autrement dit de chaque sommet du CFG.
Couverture des enchaînements d’instructions, autrement dit des arcs/chemins du CFG, avec différentes variantes :
- tous les arcs du CFG,
- tous les chemins : dans ce cas, si le programme possède des boucles, nombre de chemins potentiellement infini.
- tous les "n-chemins", cad tous les chemins mais limités à n passages maximum dans chaque boucle. En fonction de la valeur choisir de n, on parlera de critère 1-chemins, ou de critère 2-chemins, ou de critère 3-chemins, etc.

5.1. Critère "tous les sommets"

Le critère "tous les sommets" est le critère le plus faible, aussi appelé TER1 (Test Effectiveness Ratio 1). Si on exécute un ensemble de scénarios de test dont les chemins d’exécution couvrent tous les sommets du CFG, cela signifie que toutes les instructions du programme ont été exécutées au moins une fois.

Pour ce critère, on calcule le taux de couverture par le simple calcul suivant : nombre de sommets couverts ÷ nombre total de sommets.

Ce critère de couverture formel (car basé sur le CFG du programme) est presque équivalent au critère de couverture plus "informel" et très couramment utilisé, à savoir la couverture des lignes de code du programme.

Exemple 12. Application du critère "tous les sommets" sur isPalindrome

On propose l’ensemble minimal de chemins exécutables suivant pour satisfaire le critère "tous les sommets" :

ch2: (E, 4, 5a, 5b, 8-init, 8-cond, 9−11, 8−incr, 8−cond, 15, S)
ch4: (E, 4, 5a, 5b, 8-init, 8-cond, 9−11, 12, S)
ch5: (E, 4, 5a, 6, S)

En jaune sont montrés les sommets qui ne sont pas couverts par les chemins précédents. Ainsi on peut par exemple voir que, par rapport à ch2, ch4 ne sert qu’à couvrir le sommet 12.

On en déduit les scénarios de test suivants :

Paramètres d’entrée Oracle

	Paramètres d’entrée	Oracle
	`word` : string	`result`	`NullPointerException`	`IllegalArgumentException`
ch2	`"aa"`	`true`
ch4	`"xyyyyz"`	`false`
ch1	`""`	−		✕

word : string

result

NullPointerException

IllegalArgumentException

ch2

"aa"

true

ch4

"xyyyyz"

false

ch1

""

−

5.2. Critère "tous les arcs"

Le critère "tous les arcs" est le deuxième critère le plus faible, aussi appelé TER2 (Test Effectiveness Ratio 2). Si on exécute un ensemble de scénarios de test dont les chemins d’exécution couvrent tous les arcs du CFG, cela signifie que toutes les branches conditionnelles du programme ont été exécutées au moins une fois (autrement dit, chaque prédicat sera une fois "vrai" et fois "faux").

Pour ce critère, on calcule le taux de couverture par le simple calcul suivant : nombre d’arcs couverts ÷ nombre total d’arcs.

On notera que couvrir tous les arcs permet de couvrir tous les noeuds (l’inverse n’est pas vrai).

Exemple 13. Application du critère "tous les arcs" sur isPalindrome

On propose l’ensemble minimal de chemins exécutables suivant pour satisfaire le critère "tous les arcs" :

ch1: (E, 4, S)
ch2: (E, 4, 5a, 5b, 8-init, 8-cond, 9−11, 8−incr, 8−cond, 15, S)
ch4: (E, 4, 5a, 5b, 8-init, 8-cond, 9−11, 12, S)
ch5: (E, 4, 5a, 6, S)
ch6: (E, 4, 5a, 5b, 6, S)

En jaune sont montrés les arcs qui ne sont pas couverts par les chemins précédents. Ainsi on peut par exemple voir que ch5 et ch6 ne servent chacun à couvrir qu’un seul nouvel arc.

On en déduit les scénarios de test suivants :

Paramètres d’entrée Oracle

	Paramètres d’entrée	Oracle
	`word` : string	`result`	`NullPointerException`	`IllegalArgumentException`
ch1	`null`	−	✕
ch2	`"aa"`	`true`
ch4	`"xyyyyz"`	`false`
ch5	`""`	−		✕
ch6	`"azerty#"`	−		✕

word : string

result

NullPointerException

IllegalArgumentException

ch1

null

−

ch2

"aa"

true

ch4

"xyyyyz"

false

ch5

""

−

ch6

"azerty#"

−

5.3. Critère "tous les chemins"

Pour augmenter les chances de de trouver tous les défauts d’un logiciel, on peut souhaiter explorer tous les chemins d’exécutions qui le composent. C’est l’objectif du critère "tous les chemins", qui permet de couvrir tous les sommets, tous les arcs, mais aussi toutes les combinaisons de décisions.

Sur des programmes de taille "normale", le critère "tous les chemins" peut être difficile à appliquer. En effet, il y a une explosion combinatoire du nombre de chemins dès lors que le programme possède un nombre important de conditionnelles. Ce critère est en outre impossible à appliquer sur un programme contenant des boucles, puisque le nombre de chemins devient alors infini.

Exemple 14. Application du critère "tous les chemins" sur un programme simple

Soit la méthode suivante :

/**
 * Decides a new status based on the change of value.
 * A negative value is considered identical to a value of zero.
 * @param oldValue The previous value.
 * @param newValue The new value.
 * @return 1 if the value changed, 0 otherwise.
 */
public static int decideNewStatus(int oldValue, int newValue) {
    if (oldValue < 0) {
        oldValue = 0;
    }
    if (newValue < 0) {
        newValue = 0;
    }
    int newStatus = oldValue != newValue ? 1 : 0;
    return newStatus;
}

On dessine son graphe de flot de contrôle :

On pourrait se contenter de couvrir tous les arcs, en considérant les deux chemins suivants :

ch1 : (E,9,10,12,13,15-cond,15b,16,S), avec oldValue=-1 et newValue=-1,
ch2 : (E,9,12,15-cond,15a,16,S), avec oldValue=2 et newValue=4.

Mais on notera que cela ne permet même pas de tester le cas où deux valeurs sont égales sans être négatives.

Pour faire mieux, on peut satisfaire le critère "tous les chemins" avec l’ensemble suivant :

ch1 : (E,9,10,12,13,15-cond,15b,16,S),
ch2 : (E,9,12,15-cond,15a,16,S),
ch3 : (E,9,12,15-cond,15b,16,S),
ch4 : (E,9,10,12,15-cond,15a,16,S),
ch5 : (E,9,10,12,15-cond,15b,16,S),
ch6 : (E,9,10,12,13,15-cond,15a,16,S) − non exécutable, car des valeurs négatives deviennent zéro et sont forcément égales,
ch7 : (E,9,12,13,15-cond,15a,16,S),
ch8 : (E,9,12,13,15-cond,15b,16,S),

On en déduit les scénarios suivants :

	Paramètres d’entrée		Oracle
	`oldValue` : int	`newValue` : int	`result` : int
ch1	-1	-1	0
ch2	2	4	1
ch3	3	3	0
ch4	-1	4	1
ch5	-1	0	0
ch7	2	-1	1
ch8	0	-1	0

Exemple 15. Application du critère "tous les chemins" sur isPalindrome

Comme isPalindrome possède une boucle, elle possède un nombre infini de chemins. Il n’est donc pas possible de tous les énumérer, et donc de satisfaire le critère "tous les chemins".

5.4. Critère "tous les n-chemins"

Le critère "tous les n-chemins" est une limitation choisie du critère "tous les chemins" afin de le rendre utilisable même en présence de boucles. Le nombre n spécifie ici le nombre maximal de passages par boucle (itérations) que l’on souhaite considérer dans un chemin d’exécution.

En pratique, il est courant de considérer le critère "tous les 1-chemins" voire éventuellement "tous les 2-chemins" lors de l’utilisation d’une approche structurelle.

Exemple 16. Application du critère "tous les 1-chemins" sur isPalindrome

L’ensemble des 1-chemins de isPalindrome est le suivant :

ch1: (E, 4, S)
ch2: (E, 4, 5a, 5b, 8-init, 8-cond, 9−11, 8−incr, 8−cond, 15, S)
ch3: (E, 4, 5a, 5b, 8-init, 8-cond, 15, S)
ch4: (E, 4, 5a, 5b, 8-init, 8-cond, 9−11, 12, S)
ch5: (E, 4, 5a, 6, S)
ch6: (E, 4, 5a, 5b, 6, S)

En jaune sont marqué les passages de boucles. On observe bien que les chemins ch2 et ch4 présentent chacun un seul tour de boucle.

Cependant, comme déjà établi, ch3 n’est pas exécutable. Si on retire ch3 de l’ensemble, on obtient le même ensemble déterminé pour le critère "Tous les arcs", et donc les mêmes scénarios de test.

Exemple 17. Application du critère "tous les 2-chemins" sur isPalindrome

L’ensemble des 2-chemins de isPalindrome est le suivant :

ch1: (E, 4, S)
ch2: (E, 4, 5a, 5b, 8-init, 8-cond, 9−11, 8−incr, 8−cond, 15, S)
ch3: (E, 4, 5a, 5b, 8-init, 8-cond, 15, S)
ch4: (E, 4, 5a, 5b, 8-init, 8-cond, 9−11, 12, S)
ch5: (E, 4, 5a, 6, S)
ch6: (E, 4, 5a, 5b, 6, S)
ch7: (E, 4, 5a, 5b, 8-init, 8-cond, 9−11, 8−incr, 8−cond, 9−11, 12, S)
ch8: (E, 4, 5a, 5b, 8-init, 8-cond, 9−11, 8−incr, 8−cond, 9−11, 8-incr, 8−cond, 15, S)

En jaune sont marqué les passages de boucles. On observe bien que les nouveaux chemins ch7 et ch8 présentent chacun deux tours de boucle.

On notera cependant à nouveau que ch3 n’est pas exécutable, on se retrouve donc avec 7 chemins. On en déduit les scénarios suivants :

Paramètres d’entrée Oracle

	Paramètres d’entrée	Oracle
	`word` : string	`result`	`NullPointerException`	`IllegalArgumentException`
ch1	`null`	−	✕
ch2	`"aa"`	`true`
ch4	`"xyyyyz"`	`false`
ch5	`""`	−		✕
ch6	`"azerty#"`	−		✕
ch7	`"exyyyyze"`	`false`
ch8	`"abba"`	`true`

word : string

result

NullPointerException

IllegalArgumentException

ch1

null

−

ch2

"aa"

true

ch4

"xyyyyz"

false

ch5

""

−

ch6

"azerty#"

−

ch7

"exyyyyze"

false

ch8

"abba"

true

5.5. Comparaison des critères

On peut observer qu’il existe une hierarchie formelle permettant de classer les critères de couverture vus dans cette partie, à savoir :

« Tous les chemins » ≥ « Tous les n-chemins » ≥ « Tous les arcs » ≥ « Tous les sommets ».

Cette hierarchie se lit de la manière suivante : tout chemin couvert par un critère situé plus à droite, est forcément couvert par un critère situé plus à gauche.

6. Mesure automatisée de la couverture avec JaCoCo

Alors que pour l’approche combinatoire nous avions étudié un outil permettant de générer des propositions permettant de couvrir toutes les cibles considérées, pour l’approche structurelle la plupart des outils ne permettent que de mesurer le taux de converture d’une suite de test préalablement définie. Autrement dit, on réalise une vérification en aval plutôt qu’une génération automatisée de solutions.

6.1. Présentation de JaCoCo

JaCoCo (Java Code Coverage Library) est un logiciel capable d’établir quelles parties du code source d’un logiciel Java a été couverte par une ou plusieurs exécutions du code. Pour ce faire, JaCoCo repose sur la possiblité offerte par la machine virtuelle Java d’y attacher ce qu’on appelle un agent, à savoir un composant logiciel qui peut transformer en mémoire et à la volée le code source exécuté (procédé autrement appelé l'instrumentation du code source). Cet agent ajoute des points observations partout dans le code, et permet à JaCoCo de savoir précisément comment il a été exécuté.

Les mesures de JaCoCo sont réalisées à l’aide d’un CFG généré à partir du bytecode Java et non au niveau du code Java. Une conséquence est que les nombres de sommets/arcs découverts par JaCoCo sont différents de ce qui serait découvert avec l’approche vue dans ce chapitre, mais permettent d’extraire des taux de couverture très similaires, voire équivalents.

JaCoCo permet d’effectuer les mesures de couverture suivantes (détails diponibles à cette page de la documentation) :

Instructions : proportion d’instructions bytecode exécutées − correspond approximativement au critère de couverture tous les sommets.
Branches : proportion de branches bytecode exécutées − correspond approximativement au critère de couverture tous les arcs.
Cyclomatic Complexity (Cxty) : pourcentage de chemins linéairement indépendants exécutés − critère qui repose sur la métrique de complexité cyclomatique (non étudiée) ;
Lines : proportion de lignes de code exécutées − ressemble à la mesure "Instructions" mais est moins précis et moins intéressant car une même ligne de code peut correspondres à plusieurs instructions de bytecode.
Methods : proportion de méthodes exécutées (même partiellement).
Classes : proportion de classes exécutées (même partiellement).

Ainsi, pour une suite de tests donnée, JaCoCo peut nous permettre de vérifier si nous avons bien appliqué l’approche structurelle étudiée, au moins en ce qui concerne les critères tous les sommets et tous les arcs. Cependant, on peut voir que JaCoCo ne permet pas de mesurer la couverture du critère tous les n-chemins.

6.2. Ajouter le plugin Maven JaCoCo

Une manière d’utiliser JaCoCo est d’utiliser le plugin Maven officiel de l’outil, qui permet d’utiliser automatiquement l’agent JaCoCO lors de l’exécution d’une suite de tests JUnit présente dans le projet Maven.

Pour ce faire, on peut ajouter la suivante à la partie <build> d’un projet Maven :

<build>
    …
    <plugins>
        …
        <plugin>
            <groupId>org.jacoco</groupId>
            <artifactId>jacoco-maven-plugin</artifactId>
            <version>0.8.15</version>
                <executions>

                    <!-- Active l'agent JaCoCo lors de l'exécution -->
                    <execution>
                        <id>prepare-agent-exe</id>
                        <goals>
                            <goal>prepare-agent</goal>
                        </goals>
                    </execution>

                     <!-- Génère un rapport HTML avant la génération du site -->
                    <execution>
                        <id>report-exe</id>
                        <phase>pre-site</phase>
                        <goals>
                            <goal>report</goal>
                        </goals>
                    </execution>

                </executions>
        </plugin>
    </plugins>
</build>

Cela ajoute le plugin Maven JaCoCo et active deux de ses goals, à savoir prepare-agent qui prépare l’agent JaCoCo, et report qui génère le rapport HTML − ce dernier est explicitement attaché à la phase pre-site pour s’assurer qu’il soit bien généré lors d’un appel à mvn site.

On peut également ajouter la partie suivante dans la partie <reporting>, afin de lister le rapport JaCoCo dans la page Project Reports du site généré :

<reporting>
    …
    <plugins>
        …
        <plugin>
            <groupId>org.jacoco</groupId>
            <artifactId>jacoco-maven-plugin</artifactId>
            <reportSets>
                <reportSet>
                    <reports>
                        <report>report</report>
                    </reports>
                </reportSet>
            </reportSets>
        </plugin>
    </plugins>
</reporting>

Le rapport généré est accessible via le fichier target/site/jacoco/index.html, et permet d’obtenir une synthèse des résultats pour chaque package Java.

6.3. Lire les résultats produits par JaCoCo

On peut distinguées deux catégories de résultats produits dans le rapport JaCoCo :

Pour les critères Instructions et Branches, les informations sont présentées à la fois sous la forme d’un graphique (en vert, la proportion d’éléments couverts) et sous la forme d’un pourcentage d’éléments couverts.
Pour chaque autre critère, on trouve à chaque fois deux colonnes qui se suivent : d’abord une colonne "Missed" qui indique le nombre d’éléments non couverts pour ce critère, puis une colonne portant le nom du critère qui indique le nombre d’éléments total à couvrir.

Si on clique sur une classe, on peut consulter une représentation visuelle et annotée de son code source :

Les lignes surlignées en vert ou en jaune sont celles qui ont été exécutées, tandis que les lignes en rouge sont celles qui n’ont pas été exécutées.
- Les lignes vertes ont été exécutées "entièrement",
- Les lignes jaunes ont été exécutées "partiellement" (par exemple une partie de conditionnelle non utilisée ou une instruction non exécutée).
Les diamants colorés indiquent les conditionnelles, et sont verts si toutes les branches de la conditionnelle sont couvertes, jaunes si seulement une partie des branches de la conditionnelle sont couvertes, rouges si aucune branche de la conditionnelle n’a été couverte.

Exemple 18. Exemple de rapport JaCoCo

Supposons la suite de tests suivante pour isPalindrome :

package app;

import static org.junit.jupiter.api.Assertions.assertFalse;
import static org.junit.jupiter.api.Assertions.assertTrue;

import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Test;

public class SimplerBasicPalindromeTest {
        @Test
    @DisplayName("Can detect that a word is a palindrome")
    public void testCanDetectPalindrome() throws IllegalArgumentException {
        // Given
        Palindrome palindrome = new BasicPalindrome();

        // When
        boolean result = palindrome.isPalindrome("anna");

        // Then
        assertTrue(result);
    }

    @Test
    @DisplayName("Can detect that a word is not a palindrome")
    public void testCanDetectNotPalindrome() throws IllegalArgumentException {
        // Given
        Palindrome palindrome = new BasicPalindrome();

        // When
        boolean result = palindrome.isPalindrome("john");

        // Then
        assertFalse(result);
    }
}

Le premier scénario correspond au chemin ch8, et le second scénario correspond au chemin ch4.

On exécute cette suite de tests en activant JaCoCo, et ce dernier nous produit le rapport suivant pour la classe BasicPalindrome :

Si on s’intéresse aux mesures pour la méthode isPalindrome (que nous souhaitions tester) :

Instructions : 90% des instructions bytecode couvertes.
Branches : 70% des branches bytecode couvertes.
Cyclomatic Complexity (Cxty) : 3/6 chemins linéairement indépendants non couverts, donc 50% de couverts.
Lines : 1/8 lignes non couvertes, donc 87,5% de couvertes.

Pour comprendre certains de ces résultats, on peut également accéder à une visualisation annotée du code source de isPalindrome :

On peut voir que seule la ligne 11 n’est pas couverte, et est donc affichée en rouge. Cela correspond au sommet non couvert numéroté 6 dans le CFG de la méthode. En effet, notre suite de tests ne contient pas de scénario avec chaîne de caractères invalide, cette ligne n’est donc jamais exécutée.

La ligne 10 est elle affichée en jaune, ce qui signifie qu’elle été exécutée partiellement. Le diamant jaune à gauche signifie que toutes les branches issues de la conditionnelle n’ont pas été explorées. Cela correspond aux arcs non couverts 5a→6 et 5b→6 dans le CFG de la méthode.

7. Références

Paul Ammann, and Jeff Offutt. Introduction to software testing, Chapitre 2. Cambridge University Press, 2008.