Comparaison de Pacogen à l’état de l’art de la génération pairwise

Un processus de test

Pour répondre au mieux à ces deux problématiques, les ingénieurs ont conçu une méthodologie de test, celle-ci est décrite ci-dessous. Cette approche se base sur deux documents : les spécifications environnementales et les exigences du logiciel. Les spécifications environnementales contiennent les informations relatives à l’environnement d’exécution du logiciel. C’est dans ce document que l’on retrouve les systèmes d’exploitation, les logiciels ou les matériels supportés. Le document décrivant les exigences du logiciel contient toutes les informations détaillant le comportement de l’application.
C’est à partir de ce document que sont créés les cas de tests à exécuter.
La méthodologie conçue permet de produire un ensemble de cas de tests concrets (qui sont exécutables sur le produit logiciel) et de sélectionner un ensemble d’environnements de tests. La figure 2.2 présente la méthodologie mise en place par Kéréval pour tester cette application.

Analyse des exigences

A l’origine, les exigences fournies par Orange sont contenues dans des fichiers Word, et arrangées par domaines fonctionnels.
Cette structure est conservée tout au long du projet, car elle permet une répartition efficace des tâches. Il y a au total 73 domaines fonctionnels dans le projet BIEW.
Pour chaque domaine fonctionnel, les exigences sont séparées en deux catégories : celles dépendant de l’environnement et celles n’en dépendant pas. Sur les 73 domaines fonctionnels, 33 contiennent des exigences dépendant de l’environnement, soit 841 exigences. Les exigences qui dépendent de l’environnement sont étiquetées avec une ou deux des huit catégories environnementales (O.S., Mobile, WiFi Interne…) identifiées précédemment. Par exemple si une exigence se réfère à une connexion à un réseau réalisée grâce à une clé 3G, alors celle-ci est marquée « Mobile ». Cette marque est utile lors de la sélection des configurations à tester. Cette activité de tri des exigences n’est pas laissée à la seule responsabilité de l’équipe de validation, elle est le résultat d’une activité collective entre les différentes parties prenantes du projet.
La figure 2.3 présente une exigence qui dépend des périphériques WiFi. Dans ce cas précis, la distinction entre WiFi interne et WiFi externe n’est pas faite, ce qui signifie que l’exigence dépend de façon générale des deux types de périphériques WiFi.

Le système de vidéo conférence de Cisco

L’application

La solution de vidéo-conférence, TéléPrésence, est une application proposée par Cisco. Cette solution est destinée à un public de professionnels. Elle fournit aux organisations qui possèdent plusieurs sites ou aux professionnels en mobilité une solution pratique et efficace pour communiquer et tenir des réunions. Cette solution vise un marché très large : des PME aux grandes entreprises. Pour répondre aux besoins de ces entreprises, Cisco propose plusieurs versions de sa solution. Chaque version diffère par son prix, ses caractéristiques techniques et le matériel utilisé. C90 est un des produits de la solution TéléPrésence. La figure 2.6 présente ses principales caractéristiques techniques. Chaque produit possède de multiples options de configurations : dans le cas de C90on peut choisir le pare-feu, la bande passante, la qualité de la vidéo… Dans cette solution de TéléPrésenceC90,ilya169éléments configurables, ce qui représente plus d’un milliard de configurations.

Approche proposée par Don Batory

Batory et el. [Bat05] proposent de lier modèle de features et logique propositionnelle.
Les auteurs montrent que l’utilisation de la logique propositionnelle permet d’aider les utilisateurs durant les activités de conception. L’approche est implémentée dans un outil, AHEAD et utilise un solveur SAT. Approche proposée par Benavides et al. Benvides et al.[TBRC + 08] proposent un environnement écrit en java nommé Fama, qui permet de raisonner sur les modèles de features. Fama propose de raisonner sur les modèles de features en utilisant des solveurs SAT et BDD. Fama implémente plusieurs des opérations présentées section 3.3 et permet d’utiliser soit un solveur BDD, soit un solveur SAT pour les accomplir. Dans leurs travaux, les auteurs suggèrent que les BDD sont plus efficaces pour compter le nombre de configurations.

Approche proposée par Mendonca

Dans leurs travaux Mendonca et al.[MWC09] utilisent des solveurs SAT pour raisonner sur les modèles de features. Les auteurs utilisent des règles de correspondances similaires à celles présentées figure 3.4 et évaluent les performances des solveurs SAT sur des modèles de features de différentes tailles générés aléatoirement. Ils montrent que les solveurs SAT sont capables de vérifier qu’un modèle de 10000 features n’est pas vide en 0.4 seconde.
Les auteurs s’intéressent aussi aux raisonnements utilisant les BDD [MWCC08]. Ils montrent qu’avec un BDD et un bon paramétrage (un bon choix dans l’ordre des variables du BDD), on peut calculer efficacement le nombre de configurations de modèles de features contenant juqu’à 2000 features. Les auteurs proposent aussi un éditeur en ligne de modèles de features appelé SPLOT [MBC09]. Ce site permet à l’utilisateur de réaliser en ligne son propre modèle de features et d’y appliquer différentes analyses (nombre de configurations, nombre de features centrales…)

Logique propositionnelle ou contrainte

Les deux approches qui permettent de raisonner sur les modèles de features ont chacune des avantages et des inconvénients. Dans cette section, nous détaillons les points forts et les points faibles de ces deux paradigmes. Benavides et al. sont les seuls auteurs à avoir exploré les différentes façons d’analyser un modèle de features. Malheureusement, ils ne proposent pas de comparaison des différences en terme de performances des deux paradigmes.
Les approches basées sur la logique propositionnelle montrent deux principales forces : une capacité à traiter de très grands modèles sans problèmes de passage à l’échelle, et une facilité pour compter le nombre de configurations d’un modèle.
Les approches basées sur la logique propositionnelle souffrent néanmoins d’un inconvénient : la difficulté à gérer les modèles de features attribués. En effet, les formules propositionnelles reposent sur l’utilisation de variables booléennes, ayant pour valeur 0 ou 1. Dans le cas d’un raisonnement sur un modèle à attributs, il est nécessaire d’avoir des variables qui ont un domaine de valeur plus large pour modéliser un prix, une résolution ou un poids.
Les approches à contraintes quant à elles n’ont pas été formellement évaluées sur leurs performances sur des grands modèles à contraintes.

Variabilité et Test

Dans les projets de test présentés dans le chapitre 2, les équipes de testeurs font face à une explosion combinatoire du nombre de configurations de test possibles : près de 2 millions pour le projet BIEW et plus de 1 milliard pour le projet de test du logiciel Téléprésence. Dans ce chapitre nous présentons les techniques de test existantes qui permettent de traiter ces problèmes d’explosion combinatoire.
Dans une première partie nous présentons le principe du test combinatoire, sa définition et comment cette technique de test a été traitée par le monde académique. Puis nous présentons comment ces techniques ont été combinées aux modèles de features pour sélectionner des configurations de test.

Test combinatoire

Motivations

Dans cette thèse, nous nous intéressons à l’utilisation d’objets mathématiques appelés Covering Array pour les activités de test combinatoire (Combinatorial Interaction Testing (CIT)). L’utilisation des techniques de test combinatoire pour le test logiciel a été proposée pour la première fois par Cohen et al. [CDG97].
La principale motivation quant à l’utilisation des techniques de test combinatoire est que de nombreux défauts logiciels sont dus à l’interaction de quelques paramètres logiciels [KW04], [BV05], [GOA05]. Les cas de tests générés à l’aide des techniques de test combinatoire visent à couvrir toutes les combinaisons possibles de t paramètres d’entrées. Ces suites de tests sont alors capables de détecter des fautes dues à l’interaction d’au plus t composants . Les techniques de test combinatoire ont été appliquées avec succès dans de multiples domaines et sur des problèmes différents [CE00], systèmes distribués [KW04], tests d’interfaces hommes-machines [AM03], localisation de fautes[YC06].
Dans cette section, nous présentons les principales définitions des objets mathématiques appelés Covering Arrays qui sont utilisés au cours de cette thèse, puis nous présentons les différentes approches qui permettent de créer ces objets. Ces Covering arrays sont des tableaux dont chaque ligne est une configuration de test.

Variabilité et Test

Modèle combinatoire

Le test combinatoire repose sur l’utilisation d’objets mathématiques. Dans cette section, nous présentons deux de ces objets : les covering arrays et les mixed covering arrays. Finalement, nous présentons un cas particulier de ces modèles combinatoires appelé pairwise testing. Ce cas particulier est support à de nombreuses expérimentations dans le monde académique.

Mixed Level covering Arrays et covering Array

Formellement, les techniques de test combinatoire reposent sur des structures mathématiques appelées covering Arrays (CA) et Mixed Level covering Arrays (MCA) qui permettent d’extraire des configurations de test. Ces deux structures sont proches, les Mixed Level covering Array sont une version générique des covering Arrays.

Gestion des contraintes

L’un des inconvénients majeurs est que ces approches ne peuvent pas générer des configurations pairwise sur des modèles de features. En effet, soit les outils génèrent des configurations de test sans contraintes, ce qui rend ces configurations inutilisables telles quelles. Soit les outils prennent en entrée un langage à contraintes différent du formalisme des modèles de features. Ce langage est bien souvent trop large, et même s’il est possible d’utiliser ce langage pour exprimer le formalisme des modèles de features, un travail d’adaptation est nécessaire. La figure 4.3 présente un extrait du langage utilisé par l’outil CASA pour exprimer des contraintes entre les variables. Cet exemple est extrait de la documentation de CASA . Les deux premières lignes indiquent que l’on fait du pairwise testing (deux), et que 5 variables sont impliquées (5). La troisième ligne décrit le nombre de valeurs que peuvent prendre ces 5 variables : 2 2 2 2 3. Ici il y 4 variables binaires et une ternaire. Les lignes suivantes permettent d’exprimer les contraintes entre les variables. La quatrième ligne indique qu’il y aura deux contraintes exprimées sous la forme de disjonction. La cinquième ligne signifie que pour la prochaine contrainte, 2 variables seront concernées. La ligne −0 − 8 est la contrainte elle-même et signifie qui si la variable ternaire prend la plus petite valeur, alors la première variable binaire ne peut pas prendre la valeur la plus petite.

Table des matières
1 Introduction 
1.1 Motivations
1.2 Problématique
1.3 Contributions
1.4 Plan
1.5 Publications liées à cette thèse
I Contexte Industriel et État de l’art
2 Cas d’étude issus de l’industrie 
2.1 Validation de l’application Business Everywhere
2.1.1 Le logiciel Business Everywhere
2.1.2 Une approche de test systématique
2.1.3 Défis rencontrés
2.2 Le système de vidéo conférence de Cisco
2.2.1 L’application
2.2.2 Une méthodologie de test empirique .
2.2.3 Défis levés
2.3 Des verrous à traiter
3 Modèles de variabilité 
3.1 Les modèles de variabilité
3.1.1 Panorama des différents modèles de variabilité .
3.1.2 Des langages textuels pour représenter la variabilité TVL et Familiar
3.2 Les modèles de features : formalisme et définition
3.2.1 Définitions
3.2.2 Un métamodèle pour les modèles de features
3.3 Raisonner sur les modèles de features
3.3.1 Opérations sur les modèles de features
3.3.2 Support à l’analyse automatique de modèles de features
3.3.3 Les modèles de features pour la recherche expérimentale
3.4 Résumé
4 Variabilité et Test 
4.1 Test combinatoire .
4.1.1 Motivations
4.1.2 Modèle combinatoire .
4.2 Test Combinatoire et variabilité
4.2.1 Test combinatoire et systèmes configurables
4.2.2 Les approches proposées par Perrouin et al
4.2.3 L’approche proposée par Oster : MosoPolite
4.2.4 L’approche proposée par Johanssen : SPLCATool
4.3 Discussion
5 Programmation par contraintes 
5.1 Principes de la programmation par contraintes
5.2 Définition d’un problème de satisfaction de contraintes
5.3 Mécanismes de résolution d’un problème à contraintes
5.3.1 La propagation des contraintes
5.3.2 Résolution des contraintes
5.3.3 Résolution de problèmes d’optimisation
5.4 Résumé
II Contributions
6 Génération de configurations de test à l’aide de la programmation par contraintes 
6.1 Introduction
6.2 Sélection de configurations de test qui couvrent pairwise à partir d’un modèle de features
6.2.1 Les modèles de features
6.2.2 Le générateur de Covering Array
6.2.3 Ensemble de configurations valides qui respecte pairwise
6.3 Défis liés à la sélection de configurations de test pairwise sur les modèles de features
6.3.1 La détection des paires invalides
6.3.2 La sélection de configurations qui respectent le modèle de features
6.3.3 Incapacité à prévoir à priori le nombre de configurations nécessaires pour couvrir pairwise
6.4 Processus de résolution
6.4.1 Transformation du modèle de features en modèle à contraintes
6.4.2 Sélection de configurations Pairwise
6.5 Des contraintes pour résoudre le problème pairwise
6.5.1 Création de la Matrice Solution
6.5.2 Génération des contraintes pairwise
6.5.3 Résolution du problème à contraintes
6.6 Optimisation
6.6.1 Les heuristiques de recherche
6.6.2 Processus de minimisation
6.7 Une contribution outillée : Pacogen
6.7.1 Implémentation
6.7.2 Validation de l’implémentation de Pacogen
6.8 Discussion
7 Configuration et évalutation expérimentale de Pacogen 
7.1 Configuration optimale de Pacogen
7.1.1 Deux classes de paramètres
7.1.2 Méthode de sélection des paramètres de classe 1
7.1.3 Configuration optimale des paramètres de classe 2
7.1.4 Configuration optimale
7.2 Comparaison de Pacogen à l’état de l’art de la génération pairwise
7.2.1 Données expérimentales
7.2.2 Résultats et analyses
7.3 Discussion
8 Pairwise et industrie : Application 
8.1 Applicabilité dans le secteur industriel
8.2 Pairwise et le logiciel BIEW
8.2.1 Problématiques
8.2.2 Application
8.2.3 Pertinence de l’approche
8.2.4 Intégration et limite
8.3 Pairwise et le logiciel Téléprésence
8.3.1 Problématiques
8.3.2 Application
8.3.3 Pertinence de l’approche
8.3.4 Conclusion
8.4 Résumé
8.5 Discussion
III Conclusion et Perspectives
9 Conclusion et Perspectives 
9.1 Conclusion
9.2 Perspectives
9.2.1 N-wise
9.2.2 Complétion des configurations à tester
2 Table des matières
9.2.3 Gestion des attributs
Bibliographie 
Table des figures 

Lire le rapport complet