Inférence d'automates de Mealy sans ré-initialisation

Inférence d'automates de Mealy sans ré-initialisation

Labo	LIG
Equipe	VASCO
Encadrants	Catherine.Oriat@imag.fr

Thème général

Le développement rigoureux de logiciel, basé sur des méthodes formelles, exige que l'on dispose de modèles du programme. Comme de tels modèles ne sont pas toujours disponibles, différentes méthodes d'inférence ont été proposées pour reconstruire ces modèles.

On suppose que le système peut être représenté, à un certain niveau d'abstraction, par une machine à états finie ayant certaines entrées et sorties (automates de Mealy). L'équipe VASCO du LIG s'intéresse depuis plusieurs années aux techniques d'inférence "active", qui consistent construire cette machine à états en observant ses sorties en fonction de différentes entrées. Ces techniques d'apprentissage reposent sur des tests en boîte noire, ne supposent pas qu'on dispose du code source, ni même du code binaire du logiciel.

Contexte du travail

La plupart des algorithmes d'inférence supposent qu'on peut à tout moment replacer le système dans son état initial (opération de ré-initialisation). Cette hypothèse n'est pas satisfaite par tous les systèmes ; parfois cette opération est possible, mais très coûteuse en temps.

Plusieurs algorithmes ont été proposés pour inférer des automates de Mealy sans ré-initialisation, en particulier l'algorithme ICTSS2015 [GS2015]. Un certain nombre des ces algorithmes sont implémentés dans la plateforme SIMPA.

[GS2015] Roland Groz, Adenilso Simao, Alexandre Petrenko, Catherine Oriat. Inferring finite state machines without reset using state identification sequences. International Conference on Testing Software and Systems, (ICTSS 2015), Dubai, Nov 2015.

Sujet

L'objectif de ce travail de recherche consiste à étudier une optimisation de l'algorithme ICTSS2015

Résultats attendus

• Formalisation d'un algorithme d'inférence combinatoire
• Implantation de cet algorithme et de l'algoritme de Rivest et Schapire dans la plateforme d'inférence SIMPA
• Comparaison expérimentale de la complexité des deux algorithmes

Compétences nécessaires

Connaissances en théorie des langages : automates