Inférence d'automates de Mealy sans ré-initialisation : Différence entre versions

De Ensiwiki
Aller à : navigation, rechercher
(Thème général)
 
Ligne 19 : Ligne 19 :
 
et sorties (automates de Mealy). L'équipe VASCO du LIG s'intéresse
 
et sorties (automates de Mealy). L'équipe VASCO du LIG s'intéresse
 
depuis plusieurs années aux techniques d'inférence "active", qui
 
depuis plusieurs années aux techniques d'inférence "active", qui
consistent construire cette machine à états en observant ses sorties
+
consistent à construire cette machine à états en observant ses sorties
 
en fonction de différentes entrées. Ces techniques d'apprentissage
 
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
 
reposent sur des tests en boîte noire, ne supposent pas qu'on dispose

Version actuelle en date du 6 octobre 2015 à 14:47


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