Automatic Test Data Generation Using Constraint Programming and Search Based Software Engineering Techniques

Prouver qu'un logiciel correspond à sa spécification ou exposer des erreurs cachées dans son implémentation est une tâche de test très difficile, fastidieuse et peut coûter plus de 50% de coût total du logiciel. Durant la phase de test du logiciel, la génération des données de test est l'une des tâches les plus coûteuses. Par conséquent, l'automatisation de cette tâche permet de réduire considérablement le coût du logiciel, le temps de développement et les délais de commercialisation. Plusieurs travaux de recherche ont proposé des approches automatisées pour générer des données de test. Certains de ces travaux ont montré que les techniques de génération des données de test qui sont basées sur des métaheuristiques (SB-STDG) peuvent générer automatiquement des données de test. Cependant, ces techniques sont très sensibles à leur orientation qui peut avoir un impact sur l'ensemble du processus de génération des données de test. Une insuffisance d'informations pertinentes sur le problème de génération des données de test peut affaiblir l'orientation et affecter négativement l'efficacité et l'effectivité de SB-STDG. Dans cette thèse, notre proposition de recherche est d'analyser statiquement le code source pour identifier et extraire des informations pertinentes afin de les exploiter dans le processus de SB-STDG pourrait offrir davantage d'orientation et ainsi d'améliorer l'efficacité et l'effectivité de SB-STDG. Pour extraire des informations pertinentes pour l'orientation de SB-STDG, nous analysons de manière statique la structure interne du code source en se concentrant sur six caractéristiques, i.e., les constantes, les instructions conditionnelles, les arguments, les membres de données, les méthodes et les relations. En mettant l'accent sur ces caractéristiques et en utilisant différentes techniques existantes d'analyse statique, i.e, la programmation par contraintes (CP), la théorie du schéma et certains analyses statiques légères, nous proposons quatre approches: (1) en mettant l'accent sur les arguments et les instructions conditionnelles, nous définissons une approche hybride qui utilise les techniques de CP pour guider SB-STDG à réduire son espace de recherche; (2) en mettant l'accent sur les instructions conditionnelles et en utilisant des techniques de CP, nous définissons deux nouvelles métriques qui mesurent la difficulté à satisfaire une branche (i.e., condition), d'o˘ nous tirons deux nouvelles fonctions objectif pour guider SB-STDG; (3) en mettant l'accent sur les instructions conditionnelles et en utilisant la théorie du schéma, nous adaptons l'algorithme génétique pour mieux répondre au problème de la génération de données de test; (4) en mettant l'accent sur les arguments, les instructions conditionnelles, les constantes, les membres de données, les méthodes et les relations, et en utilisant des analyses statiques légères, nous définissons un générateur d'instance qui génère des données de test candidates pertinentes et une nouvelle représentation du problème de génération des données de test orienté-objet qui réduit implicitement l'espace de recherche de SB-STDG. Nous montrons que les analyses statiques aident à améliorer l'efficacité et l'effectivité de SB-STDG. Les résultats obtenus dans cette thèse montrent des améliorations importantes en termes d'efficacité et d'effectivité. Ils sont prometteurs et nous espérons que d'autres recherches dans le domaine de la génération des données de test pourraient améliorer davantage l'efficacité ou l'effectivité.

Abstract

Proving that some software system corresponds to its specification or revealing hidden errors in its implementation is a time consuming and tedious testing process, accounting for 50% of the total software. Test-data generation is one of the most expensive parts of the software testing phase. Therefore, automating this task can significantly reduce software cost, development time, and time to market. Many researchers have proposed automated approaches to generate test data. Among the proposed approaches, the literature showed that Search-Based Software Test-data Generation (SB-STDG) techniques can automatically generate test data. However, these techniques are very sensitive to their guidance which impact the whole test-data generation process. The insufficiency of information relevant about the test-data generation problem can weaken the SB-STDG guidance and negatively affect its efficiency and effectiveness. In this dissertation, our thesis is statically analyzing source code to identify and extract relevant information to exploit them in the SB-STDG process could offer more guidance and thus improve the efficiency and effectiveness of SB-STDG. To extract information relevant for SB-STDG guidance, we statically analyze the internal structure of the source code focusing on six features, i.e., constants, conditional statements, arguments, data members, methods, and relationships. Focusing on these features and using different existing techniques of static analysis, i.e., constraints programming (CP), schema theory, and some lightweight static analyses, we propose four approaches: (1) focusing on arguments and conditional statements, we define a hybrid approach that uses CP techniques to guide SB-STDG in reducing its search space; (2) focusing on conditional statements and using CP techniques, we define two new metrics that measure the difficulty to satisfy a branch, hence we derive two new fitness functions to guide SB-STDG; (3) focusing on conditional statements and using schema theory, we tailor genetic algorithm to better fit the problem of test-data generation; (4) focusing on arguments, conditional statements, constants, data members, methods, and relationships, and using lightweight static analyses, we define an instance generator that generates relevant test-data candidates and a new representation of the problem of object-oriented test-data generation that implicitly reduces the SB-STDG search space. We show that using static analyses improve the SB-STDG efficiency and effectiveness. The achieved results in this dissertation show an important improvements in terms of effectiveness and efficiency. They are promising and we hope that further research in the field of test-data generation might improve efficiency or effectiveness.