Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/inria-00520283
Contributor : Christophe Lecoutre <>
Submitted on : Wednesday, September 22, 2010 - 6:30:21 PM
Last modification on : Friday, June 25, 2021 - 9:52:03 AM
Long-term archiving on: : Thursday, December 23, 2010 - 3:15:06 AM

File

kosmatov.pdf
Explicit agreement for this submission

Identifiers

  • 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. ⟨inria-00520283⟩

Share

Metrics

Record views

259

Files downloads

188