Auswahl der wissenschaftlichen Literatur zum Thema „Inférence d'automates“

Les langages stochastiques -- des disbributions de probabilité sur des séquences -- jouent un rôle central dans de nombreux domaines. Notamment en bio-informatique, en reconnaissance vocale et plus généralement dans la plupart des domaines qui traitent un grand nombre de données représentées comme des chaînes de caractères. Nous utilisons des automates probabilistes (PA) -- un modèle équivalent aux chaînes de Markov cachées -- pour modéliser de tels langages stochastiques. Inférer des automates probabilistes à partir de données est un vaste domaine de recherche ouvert. Nous montrons qu'à partir d'une séquence de mots indépendamment et identiquement distribués selon un langage stochastique modélisé par un PA, on peut identifier celui-ci à la limite avec probabilité 1. Pour cela nous utilisons un algorithme d'inférence de PA qui n'a pas un comportement énumératif. Malheureusement, la complexité de cet algorithme est trop importante pour pouvoir en envisager une utilisation réelle. Il semble alors naturel d'essayer de trouver une sous-classe, la plus grande possible, pour laquelle nous pouvons concevoir un algorithme utilisable. Aussi, introduisons-nous une nouvelle classe d'automates probabilistes : les automates probabilistes à résiduels (PRA). La définition des PRA est basée sur une notion intrinsèque des langages stochastiques : les résiduels. Nous montrons que les PRA sont plus concis et plus expressifs que les automates probabilistes déterministes (PDA) -- une sous-classe des PA pour laquelle des algorithmes d'inférence existe. Comme les PDA, les PRA possèdent une forme canonique. De l'algorithme d'inférence de PA, nous en déduisons un algorithme d'inférence de PRA utilisable. On peut aussi modéliser les langages stochastiques avec des automates à multiplicité. Il s'agit d'un modèle qui généralise la notion de PA. Nous montrons que la classe des langages stochastiques modélisables par des MA est strictement plus grande que celle modélisée par des PA. Nous montrons de plus que l'on ne peut pas décider si un MA modélise un langage stochastique. Ce résultat négatif associé au manque de robustesse de la représentation des langages stochastiques par des MA nous permet de conclure qu'il n'existe probablement pas d'algorithme d'inférence de MA utilisable. Les MA ne semblent donc pas être une bonne représentation pour l'inférence de langages stochastiques.

Nous considérons un problème d'inférence grammaticale. Celui-ci peut être formulé comme la tâche de découvrir un concept caractérisant un ensemble de séquences, appelé aussi langage, à partir de séquences exemple. Afin de caractériser un langage, nous considérons une représentation sous forme d'automates finis non déterministes (NFA). Ceux-ci, bien que plus difficilement manipulables que les automates déterministes (DFA) habituellement utilisés, possèdent pour avantage d'être compactes et explicites (i. E. Interprétables par un expert du domaine d'application). Nous décrivons l'espace de recherche pour les NFAs, ainsi que pour différentes sous-classes des NFAs. On propose un algorithme pour l'inférence d'automates non ambigus (UFA) qui nécessite moins de données que les algorithmes usuels d'inférence de DFA pour converger. Nous proposons aussi des méthodes permettant d'introduire, dans l'inférence, des connaissances provenant de l'application (pour nous la bioinformatique).

Cette thèse propose une nouvelle approche de découverte de signatures de familles de protéines. Etant donné un échantillon (non-aligné) de séquences appartenant à une famille structurelle ou fonctionnelle de protéines, cette approche infère des automates finis non-déterministes (NFA) caractérisant la famille. Un nouveau type d'alignement multiple nommé PLMA est introduit afin de mettre en valeur les similarités partielles et locales significativement similaires. A partir de ces informations, les modèles de type NFA sont produits par un procédé relevant du domaine de l'inférence grammaticale. Les modèles NFA, présentés ici sous le nom de Protomates, sont des modèles graphiques discrets de forte expressivité, ce qui les distingue des modèles statistiques de type profils HMM ou des motifs de type Prosite. Les expériences menées sur différentes familles biologiques dont les MIP et les TNF, montrent un succès sur des données réelles
This thesis shows a new approach out of discovering protein families signatures. Given a sample of (unaligned) sequences belonging to a structural or functional family of proteins, this approach infers non-deterministic automata characterizing the family. A new kind of multiple alignment called PLMA is introduced in order to emphasize the partial and local significant similarities. Given this information, the NFA models are produced by a process stemming from the domain of grammatical inference. The NFA models, presented here under the name of Protomata, are discreet graphical models of strong expressiveness, which distinguishes them from statistical models such as HMM profiles or pattern models like Prosite patterns. The experiments led on various biological families, among which the MIP and the TNF, show a success on real data

Cette thèse propose une nouvelle approche de découverte de signatures de familles de protéines. Etant donné un échantillon (non-aligné) de séquences appartenant à une famille structurelle ou fonctionnelle de protéines, cette approche infère des automates fini s non déterministes (NFA) caractérisant la famille.
Un nouveau type d'alignement multiple nommé PLMA est introduit afin de mettre en valeur les similarités partielles et locales significativement similaires. A partir de ces informations, les modèles de type NFA sont produits par un procédé relevant du domaine de l'inférence grammaticale. Les modèles NFA, présentés ici sous le nom de Protomates, sont des modèles graphiques discrets de forte expressivité, ce qui les distingue des modèles statistiques de type profils HMM ou des motifs de type Prosite.
Les expériences menées sur différentes familles biologiques dont les MIP et les TNF, montrent un succès sur des données réelles.

TLS et SSH sont deux protocoles de sécurité très répandu et étudiés par la communauté de la recherche. Dans cette thèse, nous nous concentrons sur une classe spécifique de vulnérabilités affectant les implémentations TLS et SSH, tels que les problèmes de machine à états. Ces vulnérabilités sont dues par des différences d'interprétation de la norme et correspondent à des écarts par rapport aux spécifications, par exemple l'acceptation de messages non valides ou l'acceptation de messages valides hors séquence.Nous développons une méthodologie généralisée et systématique pour déduire les machines d'état des protocoles tels que TLS et SSH à partir de stimuli et d'observations, et pour étudier leur évolution au fil des révisions. Nous utilisons l'algorithme L* pour calculer les machines d'état correspondant à différents scénarios d'exécution.Nous reproduisons plusieurs vulnérabilités connues (déni de service, contournement d'authentification) et en découvrons de nouvelles. Nous montrons également que l'inférence des machines à états est suffisamment efficace et pratique dans de nombreux cas pour être intégrée dans un pipeline d'intégration continue, afin d'aider à trouver de nouvelles vulnérabilités ou déviations introduites au cours du développement.Grâce à notre approche systématique en boîte noire, nous étudions plus de 600 versions différentes d'implémentations de serveurs et de clients dans divers scénarios (versions de protocoles, options). En utilisant les machines d'état résultantes, nous proposons un algorithme robuste pour identifier les piles TLS et SSH. Il s'agit de la première application de cette approche sur un périmètre aussi large, en termes de nombre de piles TLS et SSH, de révisions ou de scénarios étudiés
TLS and SSH are two well-known and thoroughly studied security protocols. In this thesis, we focus on a specific class of vulnerabilities affecting both protocols implementations, state machine errors. These vulnerabilities are caused by differences in interpreting the standard and correspond to deviations from the specifications, e.g. accepting invalid messages, or accepting valid messages out of sequence.We develop a generalized and systematic methodology to infer the protocol state machines such as the major TLS and SSH stacks from stimuli and observations, and to study their evolution across revisions. We use the L* algorithm to compute state machines corresponding to different execution scenarios.We reproduce several known vulnerabilities (denial of service, authentication bypasses), and uncover new ones. We also show that state machine inference is efficient and practical enough in many cases for integration within a continuous integration pipeline, to help find new vulnerabilities or deviations introduced during development.With our systematic black-box approach, we study over 600 different versions of server and client implementations in various scenarios (protocol versions, options). Using the resulting state machines, we propose a robust algorithm to fingerprint TLS and SSH stacks. To the best of our knowledge, this is the first application of this approach on such a broad perimeter, in terms of number of TLS and SSH stacks, revisions, or execution scenarios studied