Génération de tests “tous-les-chemins” : quelle complexité pour quelles contraintes ?

Nikolai Kosmatov 1
1 LSL - Laboratoire Sûreté des Logiciels
DILS - Département Ingénierie Logiciels et Systèmes : DRT/LIST/DILS
Résumé : La génération automatique de tests structurels à l'aide de la programmation par contraintes se répand de plus en plus dans l'industrie du logiciel. Parmi les critères de couverture les plus stricts, le critère tous-les-chemins exige la génération d'un ensemble de cas de tests tel que tout chemin d'exécution faisable du programme sous test soit exécuté par un des cas de test. Cet article étudie des aspects de calculabilité et de complexité de la génération de tests tous-les-chemins et le rapport entre la complexité et la forme des contraintes issues du programme sous test. Nous définissons deux classes de programmes importantes pour la pratique. Nous montrons d'abord que pour une classe contenant des programmes simples avec de fortes restrictions, la génération de tests est possible en temps polynomial. Pour une classe de programmes plus large où les entrées peuvent être utilisées comme des indices de tableaux (ou décalages de pointeurs), la génération de tests tous-les-chemins s'avère NP-difficile. Quelques expérimentations montrent le temps de génération pour des exemples de programmes des deux classes.
Type de document :
Communication dans un congrès
JFPC 2010 - Sixièmes Journées Francophones de Programmation par Contraintes, Jun 2010, Caen, France. pp.187-196, 2010
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00520283
Contributeur : Christophe Lecoutre <>
Soumis le : mercredi 22 septembre 2010 - 18:30:21
Dernière modification le : mercredi 14 février 2018 - 14:18:01
Document(s) archivé(s) le : jeudi 23 décembre 2010 - 03:15:06

Fichier

kosmatov.pdf
Accord explicite pour ce dépôt

Identifiants

  • HAL Id : inria-00520283, version 1

Collections

Citation

Nikolai Kosmatov. Génération de tests “tous-les-chemins” : quelle complexité pour quelles contraintes ?. JFPC 2010 - Sixièmes Journées Francophones de Programmation par Contraintes, Jun 2010, Caen, France. pp.187-196, 2010. 〈inria-00520283〉

Partager

Métriques

Consultations de la notice

199

Téléchargements de fichiers

151