On automatic, constraint-based test-case generation for Mercury and its application to imperative languages

(eng) Creating a piece of software behaving the way the user expects it to behave is a central problem in computer science. Once a system is implemented, it needs to be evaluated in order to verify that it accurately and completely fulfils the initial expectations. Arguably the most commonly applied strategy to achieve this is testing. In testing terminology, we call a test case the combination of a single input for a software component with the expected result of its execution using that input, whereas a test suite refers to a collection of individual test cases. Testing refers to the activity of running a software component with respect to a well-chosen test suite and comparing, for each test case, the output that is produced with the expected result in order to find errors. The difficulty in software testing is due to the complexity of the systems; this complexity has never stopped growing over the years, which renders the need for constant improvement of testing techniques crucial. In particular, a test suite must be constructed in such a way that it will allow the testers to discover as many errors as possible in the program. While it is provably impossible to design test suites in such a way that the program is exercised in all the possibles ways it can possibly be, computer scientists have defined different adequacy criteria which, if satisfied by a given test suite, indicate that the successful execution of this test suite will sufficiently increase the confidence of the testers in the correctness of a program. The hard part of the testing process is constructing a test suite which satisfies the chosen adequacy criteria. This activity can be very time-consuming when performed manually; moreover, the resulting test suites are very large and complex, to such an extent that they can themselves contain errors. There exists therefore a strong interest in automating this process. In this work, we present a testing framework for the logic programming language Mercury able to generate and execute test suites that satisfy a given set of adequacy criteria. The technique we define is based on symbolic execution and constraints, and is able to deal with complex (possibly user-defined) data types. We also show how we can adapt this method in order to generate test suites satisfying sets of adequacy criteria in the context of imperative programming languages using heap-allocated pointer-based data structures.

(fre) La création de logiciels fonctionnant de la manière attendue par l'utilisateur est un problème central de l'informatique. Lorsqu'un système a été implémenté, il doit être évalué afin de vérifier s'il satisfait complètement et précisément aux attentes initiales. La stratégie la plus répandue pour effectuer cette évaluation est sans doute le test. Dans la terminologie du testing, un cas de test est la combinaison d'une donnée d'entrée pour un composant logiciel avec le résultat attendu de l'exécution de ce composant en utilisant cette donnée d'entrée ; d'autre part, une suite de test désigne un ensemble de cas de test. Le test lui-même consiste donc en l'exécution du composant logiciel avec une suite de test bien choisie et en la comparaison, pour chaque cas de test, du résultat produit en regard du résultat attendu, dans le but de détecter des erreurs. La difficulté du test de logiciels est dûe à la complexité des systèmes ; cette complexité n'a cessé de grandir avec les années, rendant crucial le besoin d'une amélioration continue des techniques de test. Plus particulièrement, la construction d'une suite de test doit être réalisée d'une façon telle qu'elle permette aux testeurs de découvrir un maximum d'erreurs présentes dans le programme. Si l'impossibilité de concevoir des suites de test éprouvant un programme de toutes les manières possible a été formellement établie, les informaticiens ont toutefois défini différents critères d'adéquation qui, s'ils sont satisfaits par une suite de test donnée, indiquent que l'exécution réussie de cette suite de test pourra suffisamment accroître la confi- ance des testeurs en l'exactitude d'un programme. La phase la plus difficile du processus de test est la construction d'une suite de test satisfaisant des critères d'adéquation sélectionnés. Cette activité peut être extrêmement consommatrice en temps lorsqu'elle est effectuée manuellement ; de plus, les suites de test qui en résultent sont généralement très longues et complexes, à tel point qu'elles peuvent elles-mêmes contenir des erreurs. Il existe dès lors un fort intérêt dans l'automatisation de cette procédure. Dans cet ouvrage, nous présentons une plate-forme de test pour le langage de programmation Mercury capable de générer et exécuter des suites de test satisfaisant un ensemble de critères d'adéquation. Notre technique basée sur l'exécution symbolique et les contraintes est capable de traiter des types de données complexes (éventuellement définis par l'utilisateur). Nous montrons ensuite une adaptation de notre méthode capable de générer des suites de test satisfaisant des ensembles de critères d'adéquation dans le contexte de langages de programmation impératifs utilisant des structures de données basées sur les pointeurs.