Proposition de thèse de doctorat


Utilisation de techniques de test fonctionnel pour accélérer le test structurel dans le cadre de systèmes temps-réel

Mots-clés: test structurel, test fonctionnel, graphe de flot de contrôle, couverture de code, test à base de contraintes, temps-réel

Description du sujet

Les travaux concernant la génération de données de test à partir de code source sont devenus un enjeu majeur de recherche. Pour exemple, l'entreprise Microsoft a décidé récemment d'investir massivement dans ce domaine de recherche. En effet, à l'heure actuelle, le coût du test dans le développement logiciel occupe une place très importante (de l'ordre de 50%, valeur pouvant varier selon les sources). La longueur de ce processus réside dans deux aspects essentiels:

Les approches actuelles de génération de données de test pour un programme C rencontrent souvent des difficultés concernant l'explosion combinatoire et la détection des chemins infaisables. Les approches récentes utilisent généralement soit une approche Depth First Search sur le graphe de flot de contrôle, soit une approche consistant à choisir aléatoirement une valeur du domaine, et à appliquer une sorte de backtracking sur ce même graphe. Dans le cadre du temps réel, l'explosion combinatoire est encore plus importante, et il est donc indispensable d'utiliser des approches différentes pour obtenir des résultats.

L'objectif de la thèse est donc de mettre au point de nouvelles techniques de parcours du code source afin d'accélérer la génération de données de test. Une première idée pourrait consister à utiliser une approche par classes d'équivalences. Il pourrait aussi être envisagé de cibler la génération des données seulement sur certaines propriétés, ce qui permettrait d'éviter un parcours exhaustif du graphe de flot de contrôle, qui s'avère très coûteux. Il faudra considérer ces problèmes dans le cas d'un code pour système temps-réel.

Un outil devra être développé afin de mettre en évidence les approches proposées.

Références:

[BH08]
Sebastien Bardin and Philippe Herrmann.
Structural testing of executables.
In International Conference on Software Testing, Verification, and Validation, 2008}, pages 22--31, Los Alamitos, CA, USA, 2008. IEEE Computer Society.

[CG08]
Florence Charreteur and Arnaud Gotlieb.
Raisonnement à contraintes pour le test de bytecode Java.
In JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes}, pages 11--20, Nantes France, 2008.

[FB06]
B. Legeard. F. Bouquet, F. Dadeau.
Automated boundary test generation from jml specifications.
In FM'06, 14th Int. Conf. on Formal Methods, pages 428--443, Hamilton, Canada, august 2006. Springer.

[GBR00]
Arnaud Gotlieb, Bernard Botella, and Michel Rueher.
A clp framework for computing structural test data.
In CL '00: Proceedings of the First International Conference on Computational Logic, pages 399--413, London, UK, 2000. Springer-Verlag.

[WMMR05]
Nicky Williams, Bruno Marre, Patricia Mouy, and Muriel Roger.
Pathcrawler: Automatic generation of path tests by combining static and dynamic analysis.
In EDCC, volume 3463 of Lecture Notes in Computer Science, pages 281--292. Springer, 2005.

[GKS05]
Patrice Godefroid, Nils Klarlund, and Koushik Sen.
Dart: directed automated random testing.
SIGPLAN Not., 40(6):213--223, 2005