📘 Approche combinatoire

1. Présentation

L'approche combinatoire considère comme point de départ les descriptions du comportement attendu du logiciel décrites au sein de sa spécification. Le but est de mettre au point suffisament de scénarios de test pour couvrir efficacement tous les comportements attendus d’un logiciel ou d’une partie d’un logiciel (par ex. une méthode). On qualifie aussi cette méthode de boîte noire car elle ne nécessite pas l’analyse du code source du logiciel.

Voici un résumé abrégé des étapes pour cette méthode (chaque étape sera détaillée par la suite dans le chapitre):

  1. Identifier le domaine des données d’entrée de la fonction testée − et donc de ses différents paramètres d’entrée.

  2. En se basant sur la spécification, identifier quelles paramètres de test des données d’entrée peuvent influencer le comportement attendu de la fonction (nature des éléments ? nombre d’éléments ? combinaison d’éléments ? etc.).

  3. Partitionner chaque paramètre de test en un ensemble de choix chaque choix étant une valeur possible ou un ensemble de valeurs possible pour cette paramètre de test. Si nécessaire, définir également des contraintes d’inclusion ou d’exclusion entre les différents choix.

    • De là, un scénario de test peut être obtenu (i) en sélectionnant une combinaison de choix, cad exactement un choix par paramètre de test, (ii) en déduisant des données d’entrée concrètes pour la combinaison, (iii) en définissant un oracle cohérent avec la spécification.

  4. Pour obtenir un ensemble pertinent et cohérent de combinaisons de choix (et donc de scénarios de test), utiliser un des nombreux critères possibles.

Voyons chacune de ces étapes ! un attribut accessible, on peut donc l’ignorer pour l’analyse du domaine d’entrée.

2. Modélisation en arbre de classification

2.1. Arbre de classification à un niveau

Une fois les paramètres d’entrée d’un logiciel bien identifiées, l’étape suivante est de déterminer comment ces données vont influencer le comportement du logiciel testé. On pourra ainsi cibler les comportements que l’on souhaite tester à l’aide de données d’entrée méticuleusement choisies.

La méthode étudiée dans ce chapitre s’intitule la Classification Tree Method (CTM). Cette méthode consiste à modéliser le domaine d’entrée sous la forme d’un arbre de classification, dans lequel sont hiérarchisés un ensemble de paramètres de test.

Au sein d’un arbre de classification, on trouve deux sortes d’éléments : les paramètres de test et les choix.

Structure d’un arbre de classification à un niveau
Figure 1. Structure d’un arbre de classification à un niveau

Un paramètre de test capture un aspect particulier des données d’entrée qui est susceptible d’influencer le comportement du logiciel testé. Un arbre de classification doit donc être réalisé à partir de la spécification du logiciel testé, qui est notre seule source d’information sur les comportements prévus du logiciel.

Ne pas confondre paramètre d’entrée (propre au logiciel testé), et paramètre de test (propre à un arbre de classification donné) !

Un paramètre de test est spécifique à une problématique de test donnée, et peut s’écrire par exemple sous la forme d’une courte question (ouverte ou fermée), soit sous la forme d’une courte description.

Trois arbres de classification à un niveau, incomplets
Figure 2. Trois arbres de classification à un niveau, incomplets
Un paramètre de test peut être propre à un seul paramètre d’entrée, ou bien peut concerner différents paramètres d’entrée, cf le paramètre de test proposé pour la fonction areClose qui concerne deux paramètres d’entrée p1 et p2. De même, plusieurs paramètres de tests peuvent concerner un même paramètre d’entrée.

Ensuite, chaque paramètre de test doit être partitionné en un ensemble de choix. Un choix représente une possibilité ou un ensemble de possibilités vis à vis d’un paramètre de test donné. On nomme partitionnement un choix de découpage en choix pour un paramètre de test donné.

Les trois arbres précédents, où chaque paramètre de test est partitionné en différents choix
Figure 3. Les trois arbres précédents, où chaque paramètre de test est partitionné en différents choix

Attention, pour être valide, il est impératif pour un partitionnement de satisfaire deux contraintes :

  • L’ensemble des choix doit être disjoint, autrement dit deux choix d’un partitionnement ne doivent pas pouvoir être valides simultanément. C’est indispensable pour bien séparer les différentes situations, autrement dit pour s’assurer qu’un scénario de test obtenu se concentre bien sur une seul aspect à la fois au sein d’un paramètre de test.

  • L’ensemble des choix doit être complet, autrement dit toutes les possibilités du paramètre de test doivent être présentes au sein des choix. C’est indispensable pour s’assurer de ne rien oublier comme possibilité pour chaque paramètre de test.

Pour un contexte donné, il est possible que différentes possibilités de paramètres de test et de partitionnements soient possibles, voire équivalents ! Ainsi il peut exister plusieurs "bonnes réponses" à un problème de approche combinatoire.

Une fois un arbre de classification établi, la dernière étape est de l’utiliser pour énumérer un ensemble pertinent de combinaisons de choix pour le logiciel que l’on souhaite tester. Chaque combinaison énumérée pourra ensuite être utilisée comme base pour construire un unique scénario de test (voir Section 3).

Pour construire une combinaison, il suffit de sélectionner un unique choix par paramètre de test. Ainsi, si on reprend l’arbre pour isEmpty(List list) présenté plus haut, les combinaisons possibles sont :

  • [1V−2A]

  • [1V−2B]

  • [1F−2A]

  • [1F−2B]

Exemple 1. Arbre de classification à un niveau pour isPalindrome

Voyons différentes tentatives d’arbres de classification à un niveau pour le composant central du logiciel PALINDROME, en vue d’effectuer du test unitaire. D’abord, rappelons l’interface Java définie par le document de conception pour ce composant :

package app;

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 
     *                                  or contains a digit, 
     *                                  or contains a special character.
     **/
    boolean isPalindrome(String word) throws IllegalArgumentException, NullPointerException;
}
L’objectif est d’obtenir un arbre de classification qui permet de représenter tous les comportements possibles du logiciel, en fonction des données d’entrée ! Il est crucial de lire soigneusement la spécification pour identifier tous les points pouvant nous aider à identifier cela.

On constate donc que le domaine d’entrée va influencer le logiciel de deux manières :

  • en fonction de la validité de la chaîne de caractères (chiffres et caractères spéciaux interdits, chaîne non vide et non null),

  • en fonction de si la chaîne de caractères saisie est un palindrome ou non.

Pour capturer cela, on peut être tenté de faire un premier arbre de classification qui repose sur un seul paramètre de test centré sur le contenu de la chaîne de caractères, avec un partitionnement en nombreux choix :

Première (et mauvaise) tentative d’arbre de classification à un niveau pour `isPalindrome`
Figure 4. Première (et mauvaise) tentative d’arbre de classification à un niveau pour isPalindrome

Problème : ces choix ne sont pas disjoints ! En effet, on peut notamment voir que (1) l’ensemble des "chaînes contenant des caractères spéciaux" peut inclure des chaînes avec des chiffres, et donc se recouper avec l’ensemble "chaînes contenant des chiffres", et (2) l’ensemble des "chaînes qui sont des palindromes" est peut inclure des chaînes avec des chiffres (exemple : "4nn4").

En se basant sur ces observations, on peut tenter un nouveau partitionnement, toujours avec le même unique paramètre de test :

Seconde (et imparfaite) tentative d’arbre de classification à un niveau pour `isPalindrome`
Figure 5. Seconde (et imparfaite) tentative d’arbre de classification à un niveau pour isPalindrome
Le choix invalide fait référence à ce qui est défini comme invalide dans la spécification, à savoir une chaîne null, ou vide, ou avec caractères spéciaux, ou avec chiffres.

Cette fois-ci le partitionnement est bien disjoint, et est donc utilisable.

En revanche, on constate que cet arbre ne permet d’obtenir que trois combinaisons différentes comportant chacune un seul choix : la combinaison [1A], la combinaison [1B], et la combinaison [1C]. La raison se cache dans le choix 1A, à savoir "chaîne invalide", qui définit en un seul bloc et de de manière très large la notion de chaîne invalide. L’inconvénient de cela est que ce choix ne permet par exemple pas de séparer le cas "chaîne invalide avec un chiffre et un caractère spécial" du cas "chaîne invalide avec un chiffre et sans caractère spécial", car ces deux cas sont couvert sans distinction dans ce même choix. Or, d’un point de vue combinatoire, c’est justement ce qui pourrait nous intéresser pour tester cette fonction : que se passe-t-il si on combine chiffres et caractères spéciaux ? ou bien comment est reconnue une chaîne palindrome mais contenant des chiffres ? etc.

On peut alors préférer un plus grand nombre de paramètres de test distincts, chacun ici avec un partitionnement booléen :

Troisième tentative d’arbre de classification à un niveau pour `isPalindrome` (attention ceci n’est pas la version finale)
Figure 6. Troisième tentative d’arbre de classification à un niveau pour isPalindrome (attention ceci n’est pas la version finale)

Cette représentation nous permet ainsi de considérer le cas "chaîne invalide avec un chiffre et un caractère spécial" (avec la combinaison de choix [1F−2F−3V−4V−5F]) séparément du cas "chaîne invalide avec un chiffre et sans caractère spécial" (avec la combinaison de choix [1F−2F−3F−4V−5F]). Cela n’était pas possible avec la solution précédente qui n’utilisait qu’un seul paramètre de test, et nous avons donc un découpage plus précis.

On remarque qu’il est recommandé d’être vigilant sur les intitulés des paramètres de test et des choix, à la fois pour la clarté et pour s’assurer qu’ils soient correctement disjoints. Ici on choisit de clarifier pour le paramètre de test 2 que "vide" est bien un cas différent de null, et on prend soin d’être précis dans le paramètre de test 5 sur le fait qu’une chaîne vide ne peut pas être un palindrome.

2.2. Contraintes entre choix

Comme déjà présenté, pour utiliser un arbre de classification, on devra sélectionner un choix par paramètre de test, pour ainsi obtenir une combinaison de choix. Il peut cependant arriver que certaines combinaisons possibles d’un arbre donné n’aient guère de sens. Par exemple, s’il existe un choix "x est strictement négatif" pour un premier paramètre, et un choix "x est positif " pour un second paramètre, alors il devrait être impossible de faire ces deux choix simultanément.

Pour résoudre cela, il est possible d’ajouter des contraintes entre choix pour interdire certaines combinaisons. Une contrainte entre choix définit de quelle manière certains choix vont forcer ou interdire la présence d’autres choix. On exprime de telles contraintes par des formules logiques du premier ordre. Dans ce cours, les ingrédients possibles d’une contrainte sont les suivants :

  • La sélection d’un choix est représentée par le nom du choix (par exemple "1A" signifie "1A est sélectionné").

  • La négation est exprimée par l’opérateur de négation '¬' (par exemple "¬1A" signifie "1A n’a pas été sélectionné")

  • La présence et/ou l’absence de plusieurs choix sont représentés à l’aide de :

    • la disjonction '∧', aussi appelée le et (par exemple "1A ∧ 2C" signifie "les choix 1A et 2C ont été sélectionnés"),

    • la conjonction '∨', aussi appelée le ou (par exemple "1A ∨ 2C" signifie "1A ou 2C a été sélectionné, ou les deux ont été sélectionnés"),

    • la disjonction exclusive '⊕', aussi appelé le ou exclusif ou encore le XOR (par exemple par exemple "1A ⊕ 2C" signifie "1A a été sélectionné, ou 2C a été sélectionné, mais pas les deux").

  • Les opérateurs d’implication '⇒' et d’équivalence '⇔' permettent de définir les relations entre choix (par exemple "1A ⇒ 2C" signifie "si 1A est sélectionné, alors 2C l’est aussi", et par exemple "1A ⇔ 2C" signifie "1A et 2C sont toujours sélectionnés ensemble").

Exemple 2. Contraintes sur l’arbre de classification à un niveau de isPalindrome

Dans le dernier arbre défini pour isPalindrome, si on regarde les cinq paramètres de test obtenus, on peut constater que certaines situations incohérentes peuvent apparaître si certaines combinaisons de choix sont faites.

Par exemple dans ce dernier arbre on peut sélectionner les choix suivants ensemble :

  • 1F ("word n’est pas null")

  • 2V (" word est vide")

  • 3V ("présence d’un caractère spécial dans word ").

Cette combinaison n’a pas de sens, car si la chaîne est vide, alors il est impossible qu’elle contienne un caractère spécial. Un problème similaire se produit si on combine 2V avec les choix 4V ("contient un chiffre") et 5V ("est un palindrome"). Et le même raisonnement s’applique avec 1V (" word est null "), qui rend impossible toute situation où la chaîne contient une valeur.

On ajoute donc à cet arbre les deux contraintes suivantes :

  • 1V ⇒ (2F ∧ 3F ∧ 4F ∧ 5F)

    • si word est null, alors tout le reste est faux

  • 2V ⇒ (3F ∧ 4F ∧ 5F)

    • si word est vide, alors ne il contient pas de chiffre ou de caractère spécial, et n’est pas un palindrome

2.3. Arbre de classification à plusieurs niveaux

Un arbre de classification à un niveau adossé à des contraintes permet de représenter n’importe quel problème de test combinatoire. Cependant, deux problèmes peuvent émerger :

  • d’une part, les contraintes à exprimer peuvent rapidement devenir complexes,

  • d’autre part, certains paramètres de test n’ont pas beaucoup de sens lorsque certains choix ont été réalisés dans d’autres paramètres de test.

Pour illustrer le deuxième problème, reprenons l’arbre suivant présenté précédemment :

Arbre de classification à simple niveau pour une fonction `isEmpty` (déjà présenté)
Figure 7. Arbre de classification à simple niveau pour une fonction isEmpty (déjà présenté)

Avec cet arbre, il est possible d’obtenir la combinaison "la liste est null est possède une taille de 0" ([1V−2A]), ainsi que la combinaison "la liste est null et possède une taille supérieure à 0" ([1V−2B]). Or, ces deux combinaisons n’ont aucun sens, car la liste ne peut même pas avoir de taille si sa valeur est null !

Ici, nous souhaiterions exprimer que si une liste est null, alors la notion même de taille de liste n’existe pas. Cela n’est pas directement exprimable à l’aide d’une contrainte entre choix, car ici c’est une contrainte entre un choix et un paramètre de test.

Pour résoudre cela, on peut utiliser un arbre de classification à plusieurs niveaux, dans lequel il est possible de décomposer un choix en un ou plusieurs paramètres de test. Une décomposition de choix signifie que certains paramètres de test ne sont "disponibles" que si le choix en question a été sélectionné au sein d’une combinaison.

On représente un tel arbre de la manière suivante :

Structure d’un arbre de classification à plusieurs niveaux
Figure 8. Structure d’un arbre de classification à plusieurs niveaux

Dans cet arbre :

  • le paramètre ➌ n’est accessible que si le choix 1B a été sélectionné au sein du paramètre ➊,

  • le paramètre ➍ n’est accessible que si le choix 2A a été sélectionné au sein du paramètre ➋.

Cela vient donc contraindre les combinaisons possibles, car il n’est par exemple plus possible d’établir la combinaison [1A−2A−3A−4A], étant donné que le paramètre ➌ n’est pas disponible si le choix 1A est sélectionné. Il en va de même pour la combinaison [1B−2B−3A−4A], impossible car le paramètre ➋ n’est pas disponible si le choix 2B est sélectionné. En revanche, [1A−2B] est une combinaison possible pour cet arbre, de même que [1A−2A−4B]. Une conséquence d’avoir plusieurs niveaux est donc que, pour un même arbre de classification, le nombre de choix au sein d’une combinaison est désormais variable.

Il est possible de faire autant de niveaux que souhaités. Ainsi, on peut décomposer un premier choix en un paramètre, puis décomposer à nouveau un choix de ce nouveau paramètre, et ainsi de suite.
Plus rare, il est également possible qu’un choix se décompose en plusieurs paramètres.

Ainsi, si maintenant on reprend la fonction isEmpty précédente sous la forme d’un arbre de classification à plusieurs niveaux, on peut obtenir la représentation suivante :

Arbre de classification à plusieurs niveaux pour une fonction `isEmpty`
Figure 9. Arbre de classification à plusieurs niveaux pour une fonction isEmpty

Cette fois-ci il n’est plus possible d’obtenir les combinaisons [1V−2A] ou [1V−2B] car le paramètre de test 2 n’est disponible que si le choix 1F (à savoir, le choix d’une liste non null) a été réalisé au préalable. Les seules combinaisons possibles ne sont plus que [1V], [1F−2A], [1F−2B], qui sont cette fois-ci toutes cohérentes.

Exemple 3. Arbre de classification à plusieurs niveaux pour isPalindrome

Les contraintes que nous avions défini pour l’arbre de classification à un niveau établi pour isPalindrome sont suffisantes pour bien modéliser le problème de test posé. Cependant, on pourrait simplifier notre modèle en passant à un arbre de classification à plusieurs niveaux, qui nous permettrait alors de nous passer entièrement de contraintes entre choix.

Pour cela, on se se propose de faire les changements suivants :

  • les paramètres ➌, ➍ et ➎, qui concernent le contenu de ma chaîne, deviennent une décomposition du choix 2F ("word non vide"),

  • le paramètre ➋, qui définit si word est vide ou non, devient une décomposition du choix 1F ("word non null").

Arbre de classification à plusieurs niveaux pour `isPalindrome` (version finale)
Figure 10. Arbre de classification à plusieurs niveaux pour isPalindrome (version finale)

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

Une fois un arbre de classification défini pour le domaine d’entrée d’un logiciel, l’étape suivante est d’utiliser cet arbre pour en déduire des combinaisons d’abord, puis des scénarios de test ensuite.

3.1. Définir une combinaison et son scénario de test

À partir d’une arbre de classification, "fabriquer" un scénario de test donné peut se faire en trois étapes :

  1. Définition d’une combinaison : On sélectionne un choix par paramètre de test (en prenant en compte les décompositions, si elles existent) afin d’obtenir une combinaison de choix.

  2. Sélection des données d’entrée : On donne une valeur à chaque paramètre d’entrée du logiciel, en prenant soin de satisfaire tous les choix de la combinaison choisie.

  3. Définition de l’oracle : Pour l’ensemble des données d’entrées choisies, on regarde dans la spécification quel est le résultat attendu lors de l’exécution du logiciel. On en déduit quel est l'oracle du scénario de test, à savoir le calcul permettant de décider si le scénario de test est une réussite ou non.

Pour une combinaison donnée, il faut choisir entre possiblement un grand nombre de données de test possibles ! Heureusement, si la modélisation en arbre a bien été faite, alors ce choix aura normalement peu d’importance.
Exemple 4. Exemple de combinaison et de scénario de test pour isPalindrome

Mettons que nous souhaitons un scénario de test correspondant à la combinaison de choix suivante :

Si on se réfère à la description de chacun des choix, cette combinaison exige un paramètre d’entrée d’entrée :

  • non null,

  • non vide,

  • avec un caractère spécial,

  • sans chiffre,

  • qui n’est pas un palindrome.

Une valeur possible pour le paramètre d’entrée est donc par exemple : "bonjour!"

Puis, on se réfère à la spécification, et on constate qu’elle indique que le logiciel doit nous produire une IllegalArgumentException.

On obtient donc comme scénario de test final pour cette combinaison :

  • word = "bonjour!" | oracle : IllegalArgumentException

3.2. Tableau de combinaisons

Quelle que soit la stratégie employée pour énumérer des combinaisons et pour en déduire des scénarios de test, on en arrive rapidement à écrire de longues et complexes listes des différentes combinaisons étudiées. Et cela empire dès lors qu’on souhaite associer un scénario de test à chaque combinaison. Pour remédier à cela, nous utilisons dans ce chapitre une notation en tableaux.

Supposons la structure suivante pour un arbre de classification à plusieurs niveaux :

Rappel de la structure d’un arbre de classification à plusieurs niveaux
Figure 11. Rappel de la structure d’un arbre de classification à plusieurs niveaux

Pour un tel arbre, un tableau de combinaisons prendra la forme suivante :

Tableau 1. Structure d’un tableau de combinaisons
➊ P1 ➋ P2 ➌ P3 ➍ P4

C1

Ⓐ Choix 1A

Ⓑ Choix 2B

−

−

C2

Ⓑ Choix 1B

Ⓑ Choix 2B

Ⓐ Choix 3A

−

C3

Ⓑ Choix 1B

Ⓐ Choix 2A

Ⓑ Choix 3B

Ⓐ Choix 4A

C4

Ⓑ Choix 1B

Ⓐ Choix 2A

Ⓑ Choix 3B

Ⓑ Choix 4B

dans lequel :

  • Chaque colonne représente un paramètre de test.

  • Chaque ligne représente une combinaison possible, notée CX. Pour chaque ligne représentant une combinaison, on sélectionne un unique choix par paramètre de test. Si aucun choix n’est possible pour un paramètre de test donné, on l’indiquera par un tiret (−).

Dans cette illustration, par un choix arbitraire, seulement quelques combinaisons ont été énumérées à partir de l’arbre utilisé. Il est bien sûr possible de faire un tableau dans lequel on énumère bien plus de combinaisons différentes.
Pour alléger la notation dans le cas d’un paramètre de test partitionné de manière booléenne (vrai/faux, true/false, oui/non, présent/absent, etc.), on pourra représenter le choix "vrai" par un V, et le choix "faux" par un F.

Enfin, une fois un tableau de combinaisons établi, on peut alors construire un tableau des scénarios correspondant, dans lequel chaque ligne (à savoir un scénario de test) correspond à une ligne du tableau de combinaisons (à savoir une combinaison).

Si la place le permet, on peut également fusionner les deux tableaux en un seul large tableau. Dans ce cas, chaque ligne d’un tel grand tableau débute par la combinaison, puis continue avec les paramètres d’entrée, et se termine avec l’oracle.
Exemple 5. Énumération de toutes les combinaisons et scénarios de test pour isPalindrome

Rappelons l’arbre de classification à plusieurs niveaux final établi pour isPalindrome :

Rappel de l’arbre de classification pour `isPalindrome`
Figure 12. Rappel de l’arbre de classification pour isPalindrome

Si on énumère toutes les combinaisons autorisées par cet arbre, le résultat est le suivant  :

Tableau 2. Tableaux de toutes les combinaisons possibles pour isPalindrome
➊ word null ➋ word vide ➌ word avec caractère spécial ➍ word avec chiffre ➎ word palindrome

C1

🅅

−

−

−

−

C2

ꜰ

🅅

−

−

−

C3

ꜰ

ꜰ

ꜰ

ꜰ

ꜰ

C4

ꜰ

ꜰ

ꜰ

ꜰ

🅅

C5

ꜰ

ꜰ

ꜰ

🅅

ꜰ

C6

ꜰ

ꜰ

ꜰ

🅅

🅅

C7

ꜰ

ꜰ

🅅

ꜰ

ꜰ

C8

ꜰ

ꜰ

🅅

ꜰ

🅅

C9

ꜰ

ꜰ

🅅

🅅

ꜰ

C10

ꜰ

ꜰ

🅅

🅅

🅅
Si nous avions utilisé l’arbre de classification à un niveau, alors nous aurions eu 2×2×2×2×2=32 combinaisons possibles. Mais la plupart de ces combinaisons n’auraient pas eu de sens (par exemple "la chaîne est nulle et possède un chiffre").

On peut ensuite en déduire un tableau des scénarios à partir des combinaisons listées :

Tableau 3. Tableau des scénarios obtenus à partir de toutes les combinaisons possibles pour isPalindrome
Paramètres d’entrée Oracle

word : string

result

IllegalArgumentException

C1

null

−

✕

C2

""

−

✕

C3

"john"

false

C4

"anna"

true

C5

"b0njour"

−

✕

C6

"4nn4"

−

✕

C7

"bonjour!"

−

✕

C8

"an!na"

−

✕

C9

"b0njour!"

−

✕

C10

"4n!n4"

−

✕

On observera que isPalindrome n’étant pas une méthode très compliquée à tester, le nombre de tests obtenu est relativement raisonnable (même si on peut considérer que cela fait beaucoup pour une méthode aussi simple).

4. Le ciblage en approche combinatoire

4.1. Problème : nombre trop important de combinaisons

Nous avons vu qu’il est facilement possible de déduire des combinaisons intéressantes à partir d’un arbre de classification bien conçu. Il est même envisageable, lorsque la combinatoire est raisonnable, d’énumérer toutes les combinaisons possibles d’un arbre, ce qui permet de s’assurer que nous testerons bien toutes les possibilités.

On constate cependant que deux problèmes se posent :

  • d’un part, si un arbre de classification est trop grand et trop complexe, il ne sera pas soutenable d’en énumérer toutes les combinaisons possibles. Il suffit par exemple d’avoir seulement 5 paramètres de test avec chacun 3 choix possibles pour devoir énumérer 3×3×3×3×3 = 243 combinaisons différentes — bon courage !

  • d’autre part, même si on arrivait à énumérer toutes les combinaisons 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 groupes de choix

Comme vu dans le chapitre précédent, 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 combinaisons parmi l’ensemble des combinaisons possibles, à savoir les combinaisons capables de couvrir les dites cibles.

En approche combinatoire, une cible donnée prend la forme d’un groupe de choix. La taille d’un groupe de choix est comprise entre 1 et le nombre de paramètres de test dans le modèle. On considère qu’une combinaison (et par extension le scénario de test résultant) couvre une telle cible si cette combinaison contient simultanément l’ensemble des choix inclus de la cible.

Exemple 6. Quelques cibles arbitraires pour isPalindome en approche combinatoire

En se basant la modélisation réalisée pour isPalindrome, soit l’ensemble arbitraire de cibles combinatoires suivant :

  1. Le groupe de choix {1F, 2V} − word non null et vide,

  2. Le groupe de choix {3V, 4F} − word avec caractère spécial, sans chiffre,

  3. Le groupe de choix {2F, 3V, 5V} − word non vide, avec caractère spécial, palindrome,

  4. Le groupe de choix {1V} − word qui vaut null.

  5. Le groupe de choix {1F, 2F, 3F, 4F, 5F} − word non null, non vide, sans caractère spécial, sans chiffre, non palindrome.

Soit une suite de tests obtenue à partir de l’ensemble de combinaisons [C1, C2, C10] (établies précédement pour ce problème de test). En terme de couverture, on peut constater que :

  • C1 couvre la cible 4,

  • C2 couvre la cible 1,

  • C10 couvre les cibles 2 et 3.

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

Pour déterminer un ensemble intéressant de cibles, on peut reposer sur des critères de couverture adaptés à l’approche combinatoire. Dans ce chapitre, deux familles de critères sont présentées : les critères "par choix de base" et les critères "tous les groupes de N choix".

Le choix et l’utilisation d’un critère est très dépendant du contexte (ressources disponibles, complexité du logiciel testé, etc).

5. Critères par "choix de base"

Une première famille de critères de couverture sont les critères dits par "choix de base". Un critère par "choix de base" a pour singularité d’être spécifique à un problème de test donné, au travers d’une sélection de choix considérés comme plus "importants" que les autres. Cette sélection peut se faire à l’aide de la spécification du logiciel testé. Assez pragmatiques, ces critères ont pour avantage de cibler plus précisément quels tests importants doivent réalisés.

Dans cette partie nous allons distinguer deux sortes de critères par "choix de base" : les critères "par choix de base" (Base Choice Coverage), et les critères "par choix de base multiple" (Multiple Base Choice Coverage)

5.1. Critère et algorithme Base Choice Coverage

Dans critère de type "choix de base" (en anglais, Base Choice Coverage) on appelle choix de base un choix particulier sélectionné pour un paramètre de test donné. Pour le paramètre de test considéré, ce choix doit refléter la situation la plus "nominale", "courante", "normale" lors de l’exécution du logiciel testé, autrement dit le cas correspondant au plus grand nombre de situations. Ensuite, on nomme combinaison de base la combinaison qui utilise tous les choix de base.

À partir d’une combinaison de base soigneusement choisie, le critère Base Choice Coverage définit pour cibles l’ensemble des combinaisons qui possèdent une unique différence avec la combinaison de base. Dit autrement, on souhaite couvrir toutes les combinaisons "proches" de la combinaison de base choisie.

Par ce critère, on s’assure que la suite de test obtenue corresponde aux usages les plus probables et importants du logiciel. En outre, on s’assure de s’intéresser à chaque choix non-nominal (c’est à dire souvent les cas d’erreur) "un par un", et non tous en même temps, ce qui évite de mélanger les observations.

Enfin, si on souhaite utiliser un critère pas uniquement comme une mesure de qualité, mais également comme un objectif de test, alors une solution efficace est de reposer sur un algorithme de génération de combinaisons. On peut ainsi produire ex nihilo un ensemble de combinaisons qui satisfait directement un critère, et cela de manière systématique.

Algorithme de génération Base Choice Coverage

Entrées :

  • Un arbre de classification, contenant paramètres de tests et choix.

  • Une combinaison de base cₓ.

Algorithme :

  1. Soit C l’ensemble des combinaisons résultat que l’on va construire. On initialise C avec la combinaison de base cₓ .

  2. Pour chaque paramètre de test p :

    • Soit cₓ(p) le choix effectué pour le paramètre p dans la combinaison de base cₓ.

    • Pour chaque choix q possible de p tel que q ≠ cₓ(p) :

      • Créer une nouvelle combinaison cₙ égale à cₓ,

      • Modifier cₙ tel que cₙ(p) = q,

      • Si cₙ enfreint une contrainte de l’arbre de classification, modifier un nombre minimal de choix dans cₙ de manière à satisfaire la contrainte, tout en gardant cₙ(p) = q.

      • Si cₙ n’est pas déjà dans C, ajouter cₙ à C.

Exemple 7. Application du Base Choice Coverage pour isPalindrome

Tout d’abord, définissons la combinaison de base pour les paramètres de test choisis pour isPalindrome. On peut partir du principe qu’une exécution nominale de isPalindrome se produit lorsqu’une chaîne (1) valide et (2) qui est un palindrome, est passée en paramètre d’entrée.

On choisit donc comme combinaison de base cₓ = [1F−2F−3F−4F−5V], c’est à dire une chaîne valide qui est un palindrome (par exemple une donnée d’entrée comme "anna").

On peut initialiser C avec cette première combinaison :

➊ word null ➋ word vide ➌ word avec caractère spécial ➍ word avec chiffre ➎ word palindrome

ꜰ

ꜰ

ꜰ

ꜰ

🅅

On commence avec p = ➊, et donc avec cₓ(➊) = F.

Le seul choix de possible pour p qui n’est pas F est V, on prend donc q = V. On crée une nouvelle combinaison cₙ, initialisée comme copie de cₓ ; puis on modifie cₙ pour avoir cₙ(➊) = V.

La combinaison cₙ résultante enfreint une contrainte, car le choix 1V (word = null ) implique que tous les autres paramètres ne sont pas utilisés − or, la combinaison de base utilise les autres paramètres. On modifie donc dans cₙ les choix des autres paramètres (ce qui revient ici à mettre le choix vide partout ailleurs), puis on ajoute cₙ à C :

➊ word null ➋ word vide ➌ word avec caractère spécial ➍ word avec chiffre ➎ word palindrome

ꜰ

ꜰ

ꜰ

ꜰ

🅅

🅅

−

−

−

−

On poursuit avec p = ➋, et donc avec cₓ(➋) = F, et malheureusement la même situation se produit car le choix 2V (word vide ) interdit également l’utilisation des autres paramètres On modifie donc dans cₙ les choix des paramètres concernés (ce qui revient à nouveau à utiliser le choix vide), puis on ajoute cₙ à C :

➊ word null ➋ word vide ➌ word avec caractère spécial ➍ word avec chiffre ➎ word palindrome

ꜰ

ꜰ

ꜰ

ꜰ

🅅

🅅

−

−

−

−

ꜰ

🅅

−

−

−

Ensuite avec p = ➌, et donc avec cₓ(➌) = F, on prend à nouveau la seule possibilité q = V, et on prépare une combinaison cₙ avec cₙ(➌) = V. Cette fois-ci la combinaison cₙ est valide, et on l’ajoute donc directement à C :

➊ word null ➋ word vide ➌ word avec caractère spécial ➍ word avec chiffre ➎ word palindrome

ꜰ

ꜰ

ꜰ

ꜰ

🅅

🅅

−

−

−

−

ꜰ

🅅

−

−

−

ꜰ

ꜰ

🅅

ꜰ

🅅

On poursuit sans accroc de manière similaire avec avec p = ➍ et p = ➎, et on obtient le tableau de combinaisons résultat suivant (dans lequel on ajoute l’identifiant de chaque combinaison obtenue) :

➊ word null ➋ word vide ➌ word avec caractère spécial ➍ word avec chiffre ➎ word palindrome

C4

ꜰ

ꜰ

ꜰ

ꜰ

🅅

C1

🅅

−

−

−

−

C2

ꜰ

🅅

−

−

−

C8

ꜰ

ꜰ

🅅

ꜰ

🅅

C6

ꜰ

ꜰ

ꜰ

🅅

🅅

C3

ꜰ

ꜰ

ꜰ

ꜰ

ꜰ

Et on en déduit le tableau des scénarios suivant :

Paramètres d’entrée Oracle

word : string

result

IllegalArgumentException

C4

"anna"

true

C1

null

−

✕

C2

""

−

✕

C8

"an!na"

−

✕

C6

"4nn4"

−

✕

C3

"john"

false

C’est un résultat intéressant puisqu’il énumère bien toutes les situations importantes listées dans la spécification, le tout avec seulement 6 combinaisons, et obtenu par un processus simple à appliquer.

Cependant, on peut remarquer que cette suite de test ne satisfait pas le critère Pairwise, notamment car elle ne s’intéresse pas aux chaînes invalides qui ne sont pas des palindromes.

5.2. Critère et algorithme Multiple Base Choice Coverage

Une limite peut apparaître des critère Base Choice Coverage  est que un seul choix de base est choisi pour chaque paramètre de test. Or, il n’est pas du tout improbable que différents choix d’une même paramètre de test puissent correspondre à une situation considérée comme "nominale" ou "fréquente".

Le dernier type de critère de ce chapitre est donc une généralisation du Base Choice Coverage appelée le Multiple Base Choices Coverage, où on considère qu’il puisse exister plusieurs choix de base pour un paramètre de test donné. Cela signifie travailler avec plusieurs combinaisons de bases, ce qui nécessite d’une part une boucle supplémentaire dans l’algorithme (pour traiter chaque combinaison de base), et d’autre part une passe supplémentaire pour supprimer toutes les combinaisons obtenues en doublon.

Algorithme de génération Multiple Base Choice Coverage

Entrées :

  • Un arbre de classification, contenant paramètres de tests et choix.

  • Un ensemble de combinaisons de base Cₓ.

Algorithme :

  1. Soit C l’ensemble des combinaisons résultat que l’on va construire. On initialise C avec l’ensemble des combinaisons de base Cₓ .

  2. Pour chaque combinaison de base cₓ ∈ Cₓ

    • Pour chaque paramètre de test p :

      • Soit cₓ(p) le choix effectué pour le paramètre p dans la combinaison de base cₓ.

      • Pour chaque choix q possible de p tel que q ≠ cₓ(p) :

        • Créer une nouvelle combinaison cₙ égale à cₓ,

        • Modifier cₙ tel que cₙ(p) = q,

        • Si cₙ enfreint une contrainte de l’arbre de classification, modifier un nombre minimal de choix dans cₙ de manière à satisfaire la contrainte, tout en gardant cₙ(p) = q.

        • Si cₙ n’est pas déjà dans C, ajouter cₙ à C.

Exemple 8. Application du Multiple Base Choice Coverage pour isPalindrome

Cette fois-ci, considérons qu’une situation où le mot choisi n’est pas un palindrome comme étant aussi une situation "nominale".

On choisit donc comme choix de base les mêmes que précédemment − à savoir 1F, 2F, 3F, 4F, 5V − mais en ajoutant cette fois-ci 5F.

On en déduit donc deux combinaisons de base, qui constituent Cₓ :

  • [1F−2F−3F−4F−5V]

  • [1F−2F−3F−4F−5F]

À partir de la première combinaison de base, on obtient les mêmes combinaisons qu’avec le Base Choice Coverage , ce qui nous donne un premier état pour C :

➊ word null ➋ word vide ➌ word avec caractère spécial ➍ word avec chiffre ➎ word palindrome

ꜰ

ꜰ

ꜰ

ꜰ

🅅

🅅

−

−

−

−

ꜰ

🅅

−

−

−

ꜰ

ꜰ

🅅

ꜰ

🅅

ꜰ

ꜰ

ꜰ

🅅

🅅

ꜰ

ꜰ

ꜰ

ꜰ

ꜰ

Puis, pour la 2e combinaison de base, on applique le même procédé et on obtient  les combinaisons suivantes (qu’on ne met pas dans C pour le moment) :

➊ word null ➋ word vide ➌ word avec caractère spécial ➍ word avec chiffre ➎ word palindrome

ꜰ

ꜰ

ꜰ

ꜰ

ꜰ

doublon

🅅

−

−

−

−

doublon

ꜰ

🅅

−

−

−

doublon

ꜰ

ꜰ

🅅

ꜰ

ꜰ

ꜰ

ꜰ

ꜰ

🅅

ꜰ

ꜰ

ꜰ

ꜰ

ꜰ

🅅

doublon

On remarque que quatres combinaisons obtenues sont des doublons de ce que nous avions déjà dans C, suite au traitement de la première combinaison de base. On ajoute donc uniquement dans C les autres combinaisons, qui ne sont pas des doublons.

Ce qui donne le résultat final suivant pour C :

➊ word null ➋ word vide ➌ word avec caractère spécial ➍ word avec chiffre ➎ word palindrome

C4

ꜰ

ꜰ

ꜰ

ꜰ

🅅

C1

🅅

−

−

−

−

C2

ꜰ

🅅

−

−

−

C8

ꜰ

ꜰ

🅅

ꜰ

🅅

C6

ꜰ

ꜰ

ꜰ

🅅

🅅

C3

ꜰ

ꜰ

ꜰ

ꜰ

ꜰ

C7

ꜰ

ꜰ

🅅

ꜰ

ꜰ

C5

ꜰ

ꜰ

ꜰ

🅅

ꜰ

Et le tableau des scénarios correspondant :

Paramètres d’entrée Oracle

word : string

result

IllegalArgumentException

C4

"anna"

true

C1

null

−

✕

C2

""

−

✕

C8

"an!na"

−

✕

C6

"4nn4"

−

✕

C3

"john"

false

C7

"bonjour!"

−

✕

C5

"b0njour"

−

✕

Soit 8 scénarios, dont deux nouveaux qui s’intéressent à des mots qui ne sont pas des palindromes et qui ne sont pas valides, contrairement à la suite de test obtenue par le Base Choice Coverage.

En revanche, on peut là aussi remarquer que cette suite de test ne satisfait pas le critère Pairwise, car elle ne s’intéresse notamment pas aux chaînes qui possèdent à la fois un chiffre et un caractère spécial.

6. Critères "tous les groupes de N choix"

6.1. Motivation

Pour observer (et donc détecter) une défaillance, il est nécessaire de déclencher chez le logiciel le comportement qui va produire cette défaillance. Une défaillance émerge typiquement quand des interactions se produisent entre différents paramètres d’entrée. Pour cela, un ensemble de conditions doivent être réunies, ce qui correspond dans ce chapitre à un ensemble de choix sélectionnés parmi les paramètres de test identifiés.

Par exemple, si on considère cet exemple de code, deux choix doivent être combinés (pressure < 10 et volume > 300) pour que la défaillance se produise :

if (pressure < 10) {
    // do something
    if (volume > 300) {
        faulty code! BOOM!
    } else {
        good code, no problem
    }
} else {
    // do something else
}

Mais concrètement, combien de choix spécifiques doivent être sélectionnés afin de faire apparaître une défaillance ? De nombreuses études empiriques ont tenté d’estimer nombre de choix devant être combinés pour déclencher une défaillance, et les résultats obtenus sont les suivants :

interaction rule plot
Figure 13. Études empiriques sur le nombre de paramètres devant interagir pour déclencher une défaillance

Comme on peut le voir, même si un bon nombre de défaillances peuvent être détectées avec seulement un seul choix réalisé, la plupart des défaillances surgissent quand des combinaisons de deux ou trois choix sont réalisés. Seulement quelques rares défaillances nécessitent la combinaison de 4, 5 voire 6 choix pour se produire, et sont donc sont difficiles à détecter.

Pour détecter un maximum de défaillances, il faut donc essayer de déclencher un maximum d’interactions entre différents paramètres de test. Pour cela, en test logiciel, on peut faire en sorte que chaque choix soit sélectionné, voire que chaque paire de choix soit sélectionnée, voire encore que chaque groupe de trois choix soit sélectionné. C’est le principe derrière le critère de couverture "tous les groupes de N choix".

6.2. Principe

Comme son nom l’indique, un critère de couverture "tous les groupes de N choix" (en anglais, t-wise ou t-way) définit pour cibles l’intégralité des groupes de choix valides de taille N (donc chaque paire de choix si N=2, chaque groupe de trois choix si N=3, etc.). Pour les critères "tous les groupes de N choix", un algorithme couramment utilisé est l’algorithme IPOG (In Parameter Order General).

Pour satisfaire un critère "tous les groupes de N choix" donné, on admettra qu’il faut également satisfaire tous les critères inférieurs à N. Ainsi, pour satisfaire "tous les groupes de 2 choix" il faut également satisfaire le "tous les groupes de 1 choix", et ainsi de suite.

L’idée derrière un critère "tous les groupes de N choix" et de s’assurer que chaque choix aura bien été couvert avec différents autres choix, et donc que le comportement du logiciel issu de la sélection simultanée de ces différents choix soit bien traité dans la suite de test. Comme le nombre de groupes de N choix peut très rapidement grandir, un enjeu est de couvrir le maximum cibles au sein de chacune des combinaisons, de manière à satisfaire le critère avec aussi peu de combinaisons que possible.

Un avantage des critères "tous les groupes de N choix" est de pouvoir bénéficier de certaines outils d’automatisation (voir Section 6.4 pour une liste, et voir Section 7 pour la présentation de l’outil PICT).
L’algorithme IPOG

Pour les critères "tous les groupes de N choix", un algorithme de génération de combinaisons couramment utilisé est l’algorithme IPOG (In Parameter Order General). Cet algorithme ne sera pas traité en cours, mais si vous souhaitez en savoir plus vous pouvez vous rendre dans cette annexe dédiée.

6.3. Présentation des critères avec 1 ≤ N ≤ 3

Dans cette partie nous présentons trois critères "tous les groupes de N choix" différents parmi les plus connus, par ordre croissant de la valeur de N.

6.3.1. Each Choice Coverage (N=1)

On commence avec le critère le plus simple, à savoir "tous les groupes de 1 choix", qui définit exactement une cible par choix modélisé dans l’arbre de classification. On appelle plus généralement ce critère le Each Choice Coverage.

Ce critère est très facile à satisfaire, et on peut considérer que tout ensemble de combinaisons raisonnable doit le satisfaire.
Exemple 9. Critère Each Choice Coverage pour isPalindrom

Repartons de l’arbre de classification :

Rappel de l’arbre de classification pour `isPalindrome`
Figure 14. Rappel de l’arbre de classification pour isPalindrome

Dans cet arbre, les choix possibles sont les suivants : 1V, 1F, 2V, 2F, 3V, 3F, 4V, 4F, 5V, 5F. On obtient donc pour cibles :

  1. {1V}

  2. {1F}

  3. {2V}

  4. {2F}

  5. {3V}

  6. {3F}

  7. {4V}

  8. {4F}

  9. {5V}

  10. {5F}

Le plus petit ensemble de combinaisons capable de couvrir intégralement cet ensemble de cibles est le suivant :

Tableau 4. Tableaux des combinaisons pour isPalindrome, critère Each Choice Coverage
➊ word null ➋ word vide ➌ word avec caractère spécial ➍ word avec chiffre ➎ word palindrome

C1

🅅

−

−

−

−

C2

ꜰ

🅅

−

−

−

C3

ꜰ

ꜰ

ꜰ

ꜰ

ꜰ

C10

ꜰ

ꜰ

🅅

🅅

🅅

De là, on peut en déduire un tableau des scénarios :

Tableau 5. Tableau des scénarios pour isPalindrome, critère Each Choice Coverage
Paramètres d’entrée Oracle

word : string

result

IllegalArgumentException

C1

null

−

✕

C2

""

−

✕

C3

"john"

false

C10

"4n!n4"

−

✕

Cet ensemble couvre bien tous les choix avec une taille très réduite. Malheureusement, même si le critère est atteint, respecter ce critère ne nous impose pas de tester le cas d’une chaîne palindrome valide passée en paramètre d’entrée, qui représente pourtant le cas le plus important.

Ce premier exemple illustre bien le fait qu’un critère de couverture n’est pas en soi toujours suffisant pour garantir les scénarios de test les plus intéressants. C’est avant tout un indicateur (ou un objectif) pratique et mesurable.

6.3.2. Pairwise coverage (N=2)

On poursuit avec le critère le plus connu, à savoir "tous les groupes de 2 choix", qui définit pour cibles l’ensemble de toutes les paires de choix valides dans l’arbre de classification. On appelle plus généralement ce critère le pairwise coverage.

L’idée du pairwise coverage est de s’assurer que chaque choix aura été sélectionné au moins une fois avec chacun des autres choix du problème posé. Cela permet en principe de tester une diversité importante de comportements, et de rigoureusement découvrir les défauts déclenchés lorsque certains choix sont effectués ensemble.

Le pairwise coverage est probablement le critère de couverture pour le test combinatoire le plus populaire dans le monde industriel et académique, car il a pour avantage de reposer sur un principe très simple, de nécessiter une quantité de tests (relativement) raisonnable, et d’être très efficace pour découvrir des défauts. On peut trouver une grande quantité de littérature sur le sujet − il suffit de taper pairwise testing dans un moteur de recherche pour s’en rendre compte !
Exemple 10. Pairwise Coverage pour isPalindrome

Repartons de l’arbre de classification :

Rappel de l’arbre de classification pour `isPalindrome`
Figure 15. Rappel de l’arbre de classification pour isPalindrome

Dans cet arbre, on rappelle que les choix possibles sont les suivants : 1V, 1F, 2V, 2F, 3V, 3F, 4V, 4F, 5V, 5F. Si on les combine exhaustivement deux par deux − en prenant soin d’éviter les appairages de choix interdits par l’arbre −, et que l’on ajoute les singletons pour également couvrir N=1, on obtient 27 cibles à couvrir :

Singletons absents des paires
➊

🅅
Paires 1−2
➊ ➋

ꜰ

🅅

ꜰ

ꜰ
Paires 1−3
➊ ➌

ꜰ

🅅

ꜰ

ꜰ
Paires 1−4
➊ ➍

ꜰ

🅅

ꜰ

ꜰ
Paires 1−5
➊ ➎

ꜰ

🅅

ꜰ

ꜰ
Paires 2−3
➋ ➌

ꜰ

🅅

ꜰ

ꜰ
Paires 2−4
➋ ➍

ꜰ

🅅

ꜰ

ꜰ
Paires 2−5
➋ ➎

ꜰ

🅅

ꜰ

ꜰ
Paires 3−4
➌ ➍

🅅

🅅

🅅

ꜰ

ꜰ

🅅

ꜰ

ꜰ
Paires 3−5
➌ ➎

🅅

🅅

🅅

ꜰ

ꜰ

🅅

ꜰ

ꜰ
Paires 4−5
➍ ➎

🅅

🅅

🅅

ꜰ

ꜰ

🅅

ꜰ

ꜰ

Un ensemble minimal possible de combinaisons qui couvre toutes ces cibles est le suivant :

Tableau 6. Tableaux des combinaisons pour isPalindrome, critère Pairwise Coverage
➊ word null ➋ word vide ➌ word avec caractère spécial ➍ word avec chiffre ➎ word palindrome

C1

🅅

−

−

−

−

C2

ꜰ

🅅

−

−

−

C4

ꜰ

ꜰ

ꜰ

ꜰ

🅅

C5

ꜰ

ꜰ

ꜰ

🅅

ꜰ

C7

ꜰ

ꜰ

🅅

ꜰ

ꜰ

C10

ꜰ

ꜰ

🅅

🅅

🅅

En effet, on peut constater que :

  • C1 couvre 1V

  • C2 couvre 1F−2V

  • C4 couvre : 1F−2F , 1F−3F , 1F−4F , 1F−5V , 2F−3F , 2F−4F , 2F−5V , 3F−4F , 3F−5V , 4F−5V

  • C5 permet de couvrir : 1F−4V, 2F−4V, 2F−5F, 3F−4V, 3F−5F, 4V−5F

  • C7 permet de couvrir : 1F−3V, 1F−5F, 2F−3V, 3V−4F, 3V−5F, 4F−5F

  • C10 permet de couvrir : 3V−4V, 3V−5V, 4V−5V

De là, on peut en déduire un tableau des scénarios :

Tableau 7. Tableau des scénarios pour isPalindrome, critère Pairwise Coverage
Paramètres d’entrée Oracle

word : string

result

IllegalArgumentException

C1

null

−

✕

C2

""

−

✕

C4

"anna"

true

C5

"b0njour"

−

✕

C7

"bonjour!"

−

✕

C10

"4n!n4"

−

✕

Ainsi, avec seulement 6 scénarios, cet ensemble permet de considérer beaucoup de combinaisons de possibilités. En revanche, malgré la satisfaction du critère Pairwise, on notera que cette solution n’inclut pas la combinaison C3 dans laquelle on analyse un mot valide qui n’est pas un palindrome.

C’est à nouveau une illustration du fait qu’un critère permet de certifier qu’un certain niveau de qualité a été atteint, mais pas que tous les cas importants ont forcément été traités.

6.3.3. 3-wise coverage (N=3)

Pour terminer, il est important d’aller jusqu’à N=3 avec le critère "tous les groupes de 3 choix", qui définit pour cibles l’intégralité des groupes valides de 3 choix. Ce critère est couramment appelé le critère 3-wise coverage (ou 3-way coverage).

Bien que le pairwise coverage soit le critère le plus connu et le plus pratiqué en test combinatoire, un nombre important d’études ont montré empiriquement qu’environ 90% des défaillances d’un logiciel sont déclenchées au maximum au travers de 3 paramètres différents. Ainsi, le 3-wise coverage apparaît comme un puissant compromis : ce critère permet de ne pas énumérer l’intégralité des combinaisons, tout en étant capable de détecter la quasi-totalité des défaillances.

Exemple 11. 3-wise coverage pour isPalindrome

Si on combine les choix possibles exhaustivement trois par trois sans prendre en compte les contraintes de l’arbre, nous obtenons une importante liste de 50 cibles. Même en supprimant les combinaisons interdites de la liste, le nombre resterait conséquent.

Nous souhaitons produire un ensemble de combinaisons où chacun de ces groupes de choix apparaît au moins une fois. Pour ce problème relativement simple qu’est isPalindrome, la seule manière de satisfaire le critère 3-wise coverage est de considérer toutes les combinaisons possibles sans exception.

On notera que, comparé au Pairwise, le critère 3-wise nous oblige cette fois-ci à prendre en compte la combinaison C3 dans laquelle on analyse un mot valide qui n’est pas un palindrome. L’explication est simple : pour qu’un mot soit considéré comme "valide" par isPalindrome, il doit combiner simultanément trois facteurs : ne pas être vide, ne pas avoir de chiffres, ne pas avoir de caractères spéciaux − ce cas devra forcément être traité afin de satisfaire le critère 3-wise.

6.4. Outils de génération pour les critères "tous les groupes de N choix"

Bien que l’algorithme IPOG soit utilisable "à la main", il existe également des outils qui implémentent directement de tels algorithmes pour obtenir rapidement des ensembles de combinaisons qui satisfont les critères "tous les groupes de N choix".

  • Parmi les outils industriels commerciaux relativement récents et modernes, on peut citer Hexawise ou Pairwiser. Les deux fournissent une interface web avec différents dashboards et différents algorithmes de génération.

  • Un des plus anciens outils est Advanced Combinatorial Testing System (ACTS), encore en activité même si on peut dire qu’il accuse un peu son âge.

  • Un peu moins récent, un autre outil industriel commercial est TESTONA. C’est un des rares outils qui permet d’organiser les paramètres de test en arbres de classification.

  • PICT est logiciel libre développé par Microsoft, plus minimaliste que les autres car s’utilise à l’aide d’un langage de description de paramètres de test et d’une ligne de commande.

  • CTWedge (Combinatorial Testing Web EDitor and GEnerator) est un logiciel libre issu d’un travail de recherche. Il fournit un langage textuel complet pour définir un problème de test combinatoire (plus complet que celui de PICT). Il peut s’exécuter soit dans le web soit dans un IDE Eclipse.

  • Tcases est un logiciel libre activement maintenu qui permet de définir un modèle combinatoire à l’aide d’un format JSON riche, et qui permet d’aller jusqu’à la génération de squelette de code JUnit pour du test Java. Il s’exécute soit en ligne de commande, soit via une API.

7. Génération automatisée de combinaisons avec PICT

PICT (acronyme de Pairwise Independent Combinatorial Testing) est un logiciel de test combinatoire développé par une équipe de chez Microsoft, et distribué sous licence libre.

PICT est composé d’une part d’un langage textuel qui permet de définir des modèles combinatoires (similaires à des arbres de classification à un niveau), et d’un outil en ligne de commande capable de générer automatiquement un ensemble de combinaisons pouvant satisfaire un critère de couverture de type "groupes de N choix".

PICT n’est pas capable de travailler avec les critères de type Base Choice Coverage.

7.1. Le langage PICT

Un programme PICT doit toujours commencer par la déclaration de l’ensemble des paramètres de test, à l’aide de la syntaxe suivante :

Parametre 1: Choix 1A, Choix 1B, Choix 1C
Parametre 2: Choix 2A, Choix 2B, Choix 2C
Parametre 3: Choix 3A, Choix 3B, Choix 3C

L’intitulé d’un paramètre de test est une chaîne de caractères suivie du symbole :, puis suivie d’une décomposition en choix pour ce paramètre. Chaque choix est un symbole également écrit sous la forme d’une chaîne de caractères.

Une fois tous les paramètres de test déclarés, il est possible de définir un ensemble de contraintes pour interdire certaines combinaisons de choix. Une contrainte PICT est composée d'expressions booléennes qui reposent sur la notation suivante :

  • [Parametre 1] = "Choix 1A" signifie "le choix 1A a été fait".

  • [Parametre 1] <> "Choix 1A" signifie "le choix 1A n’a pas été fait".

  • Plusieurs expressions peuvent être combinées avec les opérateurs logiques AND et OR, si besoin en délimitant des expressions à l’aide de parenthèses ().

  • L’opérateur NOT permet la négation d’une expression existante.

Ensuite, à l’aide d’expression booléennes, une contrainte simple s’écrit avec la syntaxe suivante :

IF
    expression booléenne A
THEN
    expression booléenne B
;

Cette contrainte est sémantiquement équivalente à une implication logique : expression booléenne A ⇒ expression booléenne B

On peut également ajouter une clause ELSE à une contrainte :

IF
    expression booléenne A
THEN
    expression booléenne B
ELSE
    expression booléenne C
;

Dans ce cas la contrainte est sémantiquement équivalente à deux implications logiques reliées par une conjonction : (expression booléenne A ⇒ expression booléenne B) ∧ (¬ expression booléenne A ⇒ expression booléenne C).

La syntaxe IF…THEN…ELSE permet de relativement facilement programmer une équivalence logique (⇔) en PICT. Par exemple l’équivalence "Choix 1A ⇔ Choix 2B" peut être codée de la manière suivante :

IF
    [Parametre 1] = "Choix 1A"
THEN
    [Parametre 2] = "Choix 2B"
ELSE
    [Parametre 2] <> "Choix 2B"
;
Nous n’avons vu ici qu’un sous-ensemble du langage PICT suffisant pour les besoins du cours. Pour en découvrir les autres possibilités, se rendre dans la documentation de PICT.
Exemple 12. Modèle PICT pour isPalindrome (version "un niveau")

Repartons de l’arbre de classification à un niveau réalisé préalablement pour isPalindrome :

Diagram

N’oublions pas que nous avions complété ce premier arbre avec les deux contraintes suivantes :

  • 1V ⇒ (2F ∧ 3F ∧ 4F ∧ 5F)

    • si word est null, alors tout le reste est faux

  • 2V ⇒ (3F ∧ 4F ∧ 5F)

    • si word est vide, alors ne il contient pas de chiffre ou de caractère spécial, et n’est pas un palindrome

À l’aide du langage PICT, on peut encoder à la fois l’arbre de classification et les contraintes de la manière suivante :

# Arbre de classification (1 niveau)
1_null:                   vrai, faux
2_non_null_et_vide:       vrai, faux
3_avec_car_special:       vrai, faux
4_avec_chiffre:           vrai, faux
5_palindrome:             vrai, faux

# Contrainte 1
IF
    [1_null] = "vrai"
THEN
    [2_non_null_et_vide]     = "faux"
    AND [3_avec_car_special] = "faux"
    AND [4_avec_chiffre]     = "faux"
    AND [5_palindrome]       = "faux"
;

# Contrainte 2
IF
    [2_non_null_et_vide] = "vrai"
THEN
    [3_avec_car_special] = "faux"
    AND [4_avec_chiffre] = "faux"
    AND [5_palindrome]   = "faux"
;

7.2. Utiliser l’outil PICT

Une fois un modèlé combinatoire écrit sous la forme d’un fichier à l’aide du langage PICT, il est possible d’utiliser l’outil PICT pour générer automatiquement des combinaisons permettant de couvrir l’intégralité des cibles définies par un critère de la famille "groupes de N choix".

Cet outil s’utilise en ligne de commande avec l’exécutable pict, et prend toujours comme premier argument le chemin du fichier contenant le modèle PICT :

$ pict mon_modele.pict

Par défaut c’est le critère de couverture pairwise (N=2) qui est utilisé pour la génération. On peut spécifier un autre critère de couverture à l’aide du paramètre /o de la manière suivante (ici avec N=3) :

$ pict mon_modele.pict /o:3
Si on souhaite générer l’intégralité des combinaisons possibles, sans être limité par un critère de couverture, on peut utiliser /o:max. C’est équivalent à choisir N égal au nombre de paramètres de test du modèle.

Par défaut, l’outil produit alors une sortie textuelle sous la forme d’un tableau, dont les colonnes sont séparées par des tabulations, où la première ligne liste les différents paramètres de test et les autres lignes représentent des combinaisons générées.

Ce format de sortie textuel est similaire à la notation en tableau des combinaisons vue dans ce chapitre.

Il est également possible de demander à l’outil de produire une sortie JSON avec l’argument /f:json :

$ pict mon_modele.pict /f:json

Dans ce cas la sortie est une liste JSON contenant la liste des combinaisons. Chaque élément de cette liste (donc chaque combinaison) est un tableau d’objets, chaque objet étant un choix contenant 'une entrée key contenant le nom du paramètre de test, et une entrée value contenant la valeur du choix pour ce paramètre.

Exemple 13. Génération de combinaisons avec le modèle PICT pour isPalindrome (version "un niveau")

On suppose que notre modèle PICT pour isPalindrome (version "un niveau") a été écrit dans un fichier palindrome_un_niveau.pict. On souhaite l’utiliser pour générer un ensemble de cibles de test pour le critère de couverture pairwise. On lance donc la commande :

$ pict palindrome_un_niveau.pict

Résultat :

1_null	2_non_null_et_vide	3_avec_car_special	4_avec_chiffre	5_palindrome
faux	faux	faux	faux	vrai
faux	faux	faux	vrai	faux
faux	faux	vrai	vrai	vrai
faux	vrai	faux	faux	faux
vrai	faux	faux	faux	faux
faux	faux	vrai	faux	faux

Pour une meilleure lisibilité, on peut copier cette sortie dans un logiciel de tableur capable d’interpréter les tabulations, tel que LibreOffice Calc, :

pict palindrome example calc

On obtient 6 combinaisons permettant de satisfaire le critère de couverture pairwise. On peut voir que les contraintes sont bien respectées par ces combinaisons.

On peut également générer ces mêmes combinaisons en format JSON :

$ pict palindrome_un_niveau.pict /f:json

Résultat :

[
  [
    {
      "key": "1_null",
      "value": "faux"
    },
    {
      "key": "2_non_null_et_vide",
      "value": "faux"
    },
    {
      "key": "3_avec_car_special",
      "value": "faux"
    },
    {
      "key": "4_avec_chiffre",
      "value": "faux"
    },
    {
      "key": "5_palindrome",
      "value": "vrai"
    }
  ],
  [
    {
      "key": "1_null",
      "value": "faux"
    },
    {
      "key": "2_non_null_et_vide",
      "value": "faux"
    },
    {
      "key": "3_avec_car_special",
      "value": "faux"
    },
    {
      "key": "4_avec_chiffre",
      "value": "vrai"
    },
    {
      "key": "5_palindrome",
      "value": "faux"
    }
  ],
  [
    {
      "key": "1_null",
      "value": "faux"
    },
    {
      "key": "2_non_null_et_vide",
      "value": "faux"
    },
    {
      "key": "3_avec_car_special",
      "value": "vrai"
    },
    {
      "key": "4_avec_chiffre",
      "value": "vrai"
    },
    {
      "key": "5_palindrome",
      "value": "vrai"
    }
  ],
  [
    {
      "key": "1_null",
      "value": "faux"
    },
    {
      "key": "2_non_null_et_vide",
      "value": "vrai"
    },
    {
      "key": "3_avec_car_special",
      "value": "faux"
    },
    {
      "key": "4_avec_chiffre",
      "value": "faux"
    },
    {
      "key": "5_palindrome",
      "value": "faux"
    }
  ],
  [
    {
      "key": "1_null",
      "value": "vrai"
    },
    {
      "key": "2_non_null_et_vide",
      "value": "faux"
    },
    {
      "key": "3_avec_car_special",
      "value": "faux"
    },
    {
      "key": "4_avec_chiffre",
      "value": "faux"
    },
    {
      "key": "5_palindrome",
      "value": "faux"
    }
  ],
  [
    {
      "key": "1_null",
      "value": "faux"
    },
    {
      "key": "2_non_null_et_vide",
      "value": "faux"
    },
    {
      "key": "3_avec_car_special",
      "value": "vrai"
    },
    {
      "key": "4_avec_chiffre",
      "value": "faux"
    },
    {
      "key": "5_palindrome",
      "value": "faux"
    }
  ]
]

On lance ensuite PICT à nouveau mais avec le critère de couverture 3-wise coverage (N=3) :

$ pict palindrome_un_niveau.pict /o:3

Résultat :

1_null	2_non_null_et_vide	3_avec_car_special	4_avec_chiffre	5_palindrome
faux	faux	faux	faux	faux
faux	faux	vrai	faux	vrai
faux	faux	faux	vrai	vrai
faux	faux	faux	vrai	faux
faux	faux	vrai	faux	faux
faux	faux	faux	faux	vrai
faux	faux	vrai	vrai	faux
vrai	faux	faux	faux	faux
faux	vrai	faux	faux	faux
faux	faux	vrai	vrai	vrai

On obtient cette fois 10 combinaisons permettant de satisfaire ce critère de couverture.

Enfin, il est possible de fournir à PICT un ensemble initial de combinaisons définies manuellement. PICT va alors calculer quelles sont les cibles déjà couvertes par cet ensemble initial, puis va dérouler son algorithme habituel pour compléter cet ensemble initial avec un lot minimal de combinaisons permettant de couvrir l’ensemble des cibles restantes. Ce procédé est extrêmement pratique pour s’assurer que certains cas nominaux sont bien pris en compte, et pour les compléter avec un ensemble minimal de combinaisons additionnelles permettant de satisfaire le critère choisi.

Cette fonctionnalité s’utilise en préparant les combinaisons initiales dans un fichier texte, puis en confiant ce fichier texte au paramètre /e de la manière suivante :

$ pict mon_modele.pict /e:mes_combinaisons_initiales.txt

Le fichier contenant les combinaisons initiales (ici mes_combinaisons_initiales.txt) doit suivre la même syntaxe que la sortie textuelle de PICT : une première ligne avec les noms des paramètres de tests, suivie d’une ligne par combinaison. Les colonnes doivent être séparées par des tabulations.

Certains éditeurs de texte comme VSCode remplacent automatiquement les tabulations par des espaces, ce qui ne fonctionnera pas avec PICT.
Exemple 14. Utilisation de combinaisons initiales avec le modèle PICT pour isPalindrome (version "un niveau")

On souhaite toujours satisfaire le critère pairwise, mais on souhaite également s’assurer que deux cas nominaux soient bien traités :

  • le cas où le mot est valide et est un palindrome,

  • le cas où le mot est valide et n’est pas un palindrome.

On prépare un fichier palindrome_combinaisons_initiales.txt contenant les lignes suivantes :

1_null	2_non_null_et_vide	3_avec_car_special	4_avec_chiffre	5_palindrome
faux	faux	faux	faux	vrai
faux	faux	faux	faux	faux

On lance ensuite PICT sur notre modèle et avec ce fichier :

$ pict palindrome_un_niveau.pict /e:palindrome_combinaisons_initiales.txt

Résultat :

1_null  2_non_null_et_vide      3_avec_car_special      4_avec_chiffre  5_palindrome
faux    faux    faux    faux    vrai
faux    faux    faux    faux    faux
faux    faux    faux    vrai    faux
faux    vrai    faux    faux    faux
vrai    faux    faux    faux    faux
faux    faux    vrai    faux    faux
faux    faux    vrai    vrai    vrai

On obtient cette fois-ci 7 combinaisons pour satisfaire le critère pairwise, soit une combinaisons supplémentaire par rapport à la génération sans combinaisons initiales. La raison pour ce changement est que les deux combinaisons initiales sont assez redondantes et ne couvrent presque que les paires faux-faux de notre modèle combinatoire. Il est donc nécessaire d’ajouter 5 combinaisons pour couvrir toutes les paires non couvertes.

Cependant, on peut noter que la combinaison "mot valide qui n’est pas un palindrome" est désormais couverte par notre ensemble résultat !

7.3. Arbres de classification à plusieurs niveaux en PICT

Nous avons pu voir qu’il était assez naturel de représenter des arbres de classification à un seul niveau avec le langage PICT. Malheureusement, le langage PICT ne permet pas de représenter directement plusieurs niveaux et leurs relations.

Une solution possible est de représenter les différents niveaux de manière indirecte à l’aide de deux principes :

  • Pour chaque paramètre de test défini après le premier niveau, on ajoute un choix abstrait représentant "l’absence de de choix". Par convention nous utiliserons l’intitulé _ pour ce non-choix.

  • Pour chaque décomposition d’un choix en un ou plusieurs paramètres de test (ce qui introduit un nouveau niveau), on ajoute une de contrainte qui oblige ces paramètres à prendre le non-choix _ dès lors que ces paramètres ne sont pas accessibles dans une combinaison donnée.

Par exemple si on prend l’arbre précédemment vu pour une fonction isEmpty :

Diagram

On observe que le paramètre ➋ est issu d’une décomposition depuis le choix 1F. En PICT, il faudra donc ajouter le non-choix au paramètre ➋, et il faudra ajouter une contrainte pour forcer dès lors que ➋ n’est pas accessible, c’est à dire dès lors qu’un choix différent de 1F est effectué pour le paramètre ➊.

On écrira donc :

1_null: vrai, faux
2_taille: zero, superieur_zero, _

IF
    [1_null] = "faux"
THEN
    [2_taille] <> "_"
ELSE
    [2_taille] = "_"
;
Le ELSE est ici crucial, car il faut non seulement s’assurer que le non-choix n’est pas pris lorsque la décomposition a lieu, et que le non-choix est pris lorsque la décomposition n’a pas lieu.
Si l’arbre possède plus de deux niveaux, ce même motif s’applique de manière identique sur des paramètres décomposés dans les niveaux suivants (voir exemple isPalindrome ci-après).
Exemple 15. Modèle PICT pour isPalindrome (version "plusieurs niveaux")

On souhaite cette fois-ci écrire en PICT la version "plusieurs niveaux" de l’arbre de classification pour isPalindrome :

Diagram

On observe que les paramètres ➋, ➌, ➍ et ➎ sont tous issus de décompositions, et sont donc tous sur des niveaux inférieurs. En PICT, on devra donc définir un non-choix _ pour chacun de ces paramètres, ainsi que les contraintes nécessaires. On écrit donc, dans un fichier palindrome_plusieurs_niveaux.pict :

# Arbre de classification (plusieurs niveaux)
1_null:                   vrai, faux
2_non_null_et_vide:       vrai, faux, _
3_avec_car_special:       vrai, faux, _
4_avec_chiffre:           vrai, faux, _
5_palindrome:             vrai, faux, _

# Contrainte pour la décomposition de 1F
IF
    [1_null] <> "faux"
THEN
    [2_non_null_et_vide] = "_"
ELSE
    [2_non_null_et_vide] <> "_"
;

# Contrainte pour la décomposition de 2F
IF
    [2_non_null_et_vide] <> "faux"
THEN
    [3_avec_car_special] = "_"
    AND [4_avec_chiffre] = "_"
    AND [5_palindrome]   = "_"
ELSE
    [3_avec_car_special] <> "_"
    AND [4_avec_chiffre] <> "_"
    AND [5_palindrome]   <> "_"
;

On exécute ensuite PICT :

$ pict palindrome_plusieurs_niveaux.pict

Résultat :

1_null  2_non_null_et_vide      3_avec_car_special      4_avec_chiffre  5_palindrome
faux    faux    vrai    vrai    faux
faux    faux    faux    faux    faux
faux    vrai    _       _       _
faux    faux    vrai    faux    vrai
vrai    _       _       _       _
faux    faux    faux    vrai    vrai

8. Références

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

  • Richard Kuhn, Raghu N. Kacker et Yu Lei. Introduction to Combinatorial Testing, Chapitre 5, 2013.

  • Grochtmann, M. and Grimm, K. (1993), Classification trees for partition testing. Softw. Test. Verif. Reliab., 3: 63-82.