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

De Ensiwiki
Aller à : navigation, rechercher


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

Labo LIG
Equipe VASCO
Encadrants Roland.Groz@imag.fr,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 de l'algorithme optimisé
  • Evaluation des performances de l'algorithme optimisé par rapport à l'algorithme original ICTSS2015
  • Proposition et étude de nouvelles variantes pour améliorer l’algorithme

Compétences nécessaires

Connaissances en théorie des langages : automates