Automatic Data Generation for MC/DC Test Criterion Using Metaheuristic Algorithms

Le test de logiciel a traditionnellement été l'une des principales techniques contribuant à la haute fiabilité et à la qualité des logiciels. Les activités de test consomment environ 50% des ressources de développement de logiciel, ainsi toute technique visant à réduire les coûts du test est susceptible de réduire le coût total de développement du logiciel. Le test complet d'un logiciel est souvent impossible à réaliser à cause des exécutions infinies nécessaires pour effectuer le test et le prix élevé par rapport aux limitations du budget. Les systèmes informatiques de fiabilité élevée sont souvent des systèmes appartenant aux domaines réglementés tels que le domaine aérospatial et le domaine médical. Dans de tels domaines, l'assurance de la qualité et les activités de test de logiciel sont imposées par la loi ou exigées par des normes obligatoires, telles que le DO-178B, DO-254, EN-50128, IEEE/EIA 12207, ou ISO/IEC i2207. Ces normes et règlements imposent normalement des activités de vérification et de validation, ainsi qu'ils spécifient les critères de test exigés. Proposé par la NASA en 1994, la couverture modifiée des décisions et des conditions (MC/DC) est une stratégie de test requise, entre autres, par le RTCA DO-178B. MC/DC est un critère de test en boîte blanche qui vise à prouver que chacune des clauses (expression booléenne ne contenant aucun opérateur logique tel que le z < x + y) impliquée dans une décision influence correctement la valeur de cette décision. Le critère MC/DC englobe d'autres critères structurels bien connus tels que la couverture des instructions et des décisions. Le travail présenté dans se mémoire applique des techniques d'optimisation de la recherche au problème du test. Nous explorons la façon d'intégrer la distance des branches, les dépendances de contrôles et les dépendances de données dans la recherche pour mieux la guider. Le but serait la génération automatique des données de test pour le critère MC/DC appliqué au niveau des méthodes. Notre approche est organisée en deux étapes. D'abord, pour chacune des décisions dans le code à tester, nous calculons les ensembles des cas de test nécessaire pour couvrir le critère MC/DC pour cette décision. Cet ensemble de cas de test formera alors un ensemble d'objectifs pour la recherche. Dans la deuxième étape, nous appliquons des stratégies de recherche méta-heuristiques pour produire des données de test, assignant des valeurs booléennes vraies et fausses aux clauses des décisions de sorte qu'un objectif de test calculé dans la première étape soit satisfait. Nous proposons une nouvelle fonction de coût qui sert à guider efficacement la recherche pour la génération des données test pour le critère MC/DC. En particulier nous nous inspirons de la méthode d'enchaînement qui intègre les dépendances de données dans la fonction coût. Nous avons étendu l'algorithme proposé par McMinn pour la fonction de la distance des branches, en l'adaptant au critère MC/DC.

Abstract

Testing has traditionally been one of the main techniques contributing to high software dependability and quality. Testing activity consumes about 50% of software development resources, so any technique aiming at reducing software-testing costs is likely to reduce software development costs. Indeed, exhaustive and thorough testing is often unfeasible because of the possibly infinite execution space or high cost with respect to tight budget limitations. High dependability computerized systems are often software intensive systems belonging to regulated domains such as aerospace and medical application domain. In such domains, quality assurance and testing activities are enforced by law or required by mandatory standards, such as DO-178B, DO-254, EN-50128, IEEE/EIA 12207, or ISO/IEC i2207. These standards and regulations enforce verification and validation activities and they specify the required testing coverage criteria. Proposed by NASA in 1994, the Modified Condition/Decision Coverage (MC/DC) criterion is a testing strategy required, among other practices, by the RTCA DO-178B. MC/DC is a white box testing criterion aiming at proving evidence that all clauses (Boolean expression not containing any logical operator such as z > x + y) involved in a predicate can influence the predicate value in the required way. It subsumes other well-known coverage criteria such as statement and decision coverage. This work explores the way search techniques can be integrated with branch distance, control and data dependencies to generate MC/DC test input data at method level. Our approach is organized in two steps. First, for any given predicate, we compute the sets of test cases that would cover the MC/DC criterion for this predicate. In the second step, we apply meta-heuristic search strategies to generate test input data assigning true and false Boolean values to clauses so that one of the MC/DC test case computed in step one is satisfied. We propose a novel fitness function to efficiently generate test input data satisfying the MC/DC criterion. In particular we draw inspiration from the Chaining approach integrating data dependencies in the fitness design and evaluation. We extended the algorithm proposed by McMinn for the branch distance fitness adapting it to MC/DC.