The successful verification of the behaviour of an Autonomous driving (AD) vehicle is fundamental for the commercialization of this new technology. Formal verification can be used to exhaustively verify the correctness of a system, but it requires a formal model to do so. An exact mathematical definition of the model description of the system is required. Manually defining a model is daunting, error-prone, and intractable for large systems. Automata learning is a branch of Machine learning (ML) that automatically creates a formal model by dynamically interacting with the system. In prior research, automata learning algorithms have been shown to learn a formal model from AD software implemented in MATLAB. However, practical challenges were highlighted in addressing the state-space explosion problem and in obtaining suitable abstractions to deal with large systems. To obtain valuable insights to scale up automata learning for industrial use, this thesis investigates the topic of automatically learning an extended finite automata formalism, called register automata. The SL* algorithm, an extension of the L* algorithm, is used to learn a register automata model of AD software from MATLAB code. The new algorithm creates a register automaton that manages to deal with the data dependencies intrinsically created from the case study between the input variables. Some approximations to the original model were made to obtain the desired solution. The obtained results are presented, from establishing the learning interface, validation of the interface, and from learning the case study. Evidence has been shown that similar problems to those highlighted for DFA learning are encountered. Future works have been discussed to address the same topic and to improve the proposed methodology. / Den framgångsrika verifieringen av beteendet hos ett autonomt körande fordon är grundläggande för kommersialiseringen av denna innovativa teknik. Formella metoder kan förutses som den sista tekniken för att uppnå detta mål. Den exakta matematiska definitionen av modellbeskrivningen för systemet behövs. Tidigare verk kunde inte skapa en metod för att automatiskt beskriva beteendemodellen för SUL. Nuvarande Lateral State Manager varierar komplexiteten som förhindrade användningen av ramverk som LearnLib eller den normala L * -algoritmen. Den stora mängden ingångar och den exponentiella tillväxten av den observerbara tabellen är några av orsakerna som gör att standardalgoritmerna misslyckas. Tidigare löstes problemet delvis och introducerade viss abstraktion till SUL. I denna avhandling föreslår vi en metod baserad på en innovativ algoritm: SL *. Den är utvecklad tack vare förlängningen av LearnLib-ramverket RALib. Den nya algoritmen skapar en registerautomat som klarar av att hantera databeroendet som skapats ur studiens fall. För att få en lösning inom acceptabel tid gjorde vi en ungefärlig tillnärmning till den ursprungliga modellen som vi tror inte påverkar det slutliga resultatet och skapar en modell som kan användas för de ändamål den var tänkt för. / La corretta verifica del comportamento di un veicolo a guida autonoma è fondamentale per la commercializzazione di questa tecnologia. Diversi metodi formali possono essere previsti come una possibile tecnica al fine di raggiungere parte di questo vasto obiettivo. Al fine di utilizzare tali metodi è necessaria l’esatta descrizione matematica del modello comportamentale del sistema. Precedenti studi non sono stati in grado di creare automaticamente un metodo per descrivere il comportamento del sistema sotto esame. Il Lateral State Manager presenta varie complessità che hanno impedito l’uso di framework come LearnLib o dell’algoritmo L_. La grande quantità di input e la crescita esponenziale della tabella delle osservazioni sono alcune delle principali cause che portano i comuni algoritmi al fallimento. In precedenza il problema è stato parzialmente risolto introducendo alcune astrazioni al caso di studio. In questa dissertazione proponiamo un metodo basato su un algoritmo innovativo: SL *. Lo stesso è sviluppato grazie all’estensione del framework LearnLib, chiamato RALib. Il nuovo algoritmo crea degli automi basati sui registri che riescono a gestire la dipendenza tra i dati intrinsecamente creati dal caso di studio. Per ottenere una soluzione in tempi accettabili si sono rese necessarie alcune approssimazioni del modello originale che riteniamo non influiscano sul risultato finale, creando un modello che possa essere utilizzato per gli scopi per cui è stato pensato.

Cílem této práce bylo studium aktivního učení automatů, navržení a implementace softwarové architektury pro automatickou konstrukci hlídacího obvodu dané jednotky implementované v FPGA a ověření funkčnosti hlídacího obvodu pomocí injekce poruch. Hlídací obvod, tzv. online checker, má za úkol zabezpečovat danou jednotku proti poruchám. Checker je konstruován z modelu odvozeného pomocí aktivního učení automatů, které probíhá na základě komunikace se simulátorem. Pro implementaci učícího prostředí byla použita knihovna LearnLib, která poskytuje algoritmy aktivního učení automatů a jejich optimalizace. Byla navržena a implementována experimentální platforma umožňující řízenou injekci poruch do designu v FPGA, která slouží k otestování checkeru. Výsledky experimentů ukazují, že při použití checkeru a rekonfigurace je možné snížit chybovost designu o více než 98%.

L'apprentissage de langages réguliers est un sous-ensemble de l'apprentissage automatique qui s'est révélé utile dans de nombreux domaines tels que l'intelli-gence artificielle, les réseaux de neurones, l'exploration de données, la vérification, etc. De plus, l'intérêt dans les langages définis sur des alphabets infinis ou de grande taille est croissant au fil des années. Même si plusierurs propriétés et théories se généralisent à partir du cas fini, l'apprentissage de tels langages est une tâche difficile.En effet, dans ce contexte, l'application naïve des algorithmes d'apprentissage traditionnel n'est pas possible.Dans cette thèse, nous présentons un schéma algorithmique général pour l'ap-prentissage de langages définis sur des alphabets infinis ou de grande taille, comme par exemple des sous-ensembles bornés de N or R ou des vecteurs booléens de grandes dimensions. Nous nous restreignons aux classes de langages qui sont acceptés par des automates déterministes symboliques utilisant des prédicats pour définir les transitions, construisant ainsi une partition finie de l'alphabet pour chaque état.Notre algorithme d'apprentissage, qui est une adaptation du L* d'Angluin, combine l'apprentissage classique d'un automate par la caractérisation de ses états, avec l'apprentissage de prédicats statiques définissant les partitions de l'alphabet. Nous utilisons l'apprentissage incrémental avec la propriété que deux types de requêtes fournissent une information suffisante sur le langage cible. Les requêtes du premier type sont les requêtes d'adhésions, qui permettent de savoir si un mot proposé appartient ou non au langage cible. Les requêtes du second type sont les requêtes d'équivalence, qui vérifient si un automate proposé accepte le langage cible; dans le cas contraire, un contre-exemple est renvoyé.Nous étudions l'apprentissage de langages définis sur des alphabets infinis ou de grande tailles dans un cadre théorique et général, mais notre objectif est de proposer des solutions concrètes pour un certain nombre de cas particuliers. Ensuite, nous nous intéressons aux deux principaux aspects du problème. Dans un premier temps, nous supposerons que les requêtes d'équivalence renvoient toujours un contre-exemple minimal pour un ordre de longueur-lexicographique quand l'automate proposé est incorrect. Puis dans un second temps, nous relâchons cette hypothèse forte d'un oracle d'équivalence, et nous la remplaçons avec une hypothèse plus réaliste où l'équivalence est approchée par un test sur les requêtes qui utilisent un échantillonnage sur l'ensemble des mots. Dans ce dernier cas, ce type de requêtes ne garantit pas l'obtention de contre-exemples, et par conséquent de contre-exemples minimaux. Nous obtenons alors une notion plus faible d'apprent-issage PAC (Probably Approximately Correct), permettant l'apprentissage d'une approximation du langage cible.Tout les algorithmes ont été implémentés, et leurs performances, en terme de construction d'automate et de taille d'alphabet, ont été évaluées empiriquement. / Learning regular languages is a branch of machine learning, which has been proved useful in many areas, including artificial intelligence, neural networks, data mining, verification, etc. On the other hand, interest in languages defined over large and infinite alphabets has increased in recent years. Although many theories and properties generalize well from the finite case, learning such languages is not an easy task. As the existing methods for learning regular languages depends on the size of the alphabet, a straightforward generalization in this context is not possible.In this thesis, we present a generic algorithmic scheme that can be used for learning languages defined over large or infinite alphabets, such as bounded subsets of N or R or Boolean vectors of high dimensions. We restrict ourselves to the class of languages accepted by deterministic symbolic automata that use predicates to label transitions, forming a finite partition of the alphabet for every state.Our learning algorithm, an adaptation of Angluin's L*, combines standard automaton learning by state characterization, with the learning of the static predicates that define the alphabet partitions. We use the online learning scheme, where two types of queries provide the necessary information about the target language. The first type, membership queries, answer whether a given word belongs or not to the target. The second, equivalence queries, check whether a conjectured automaton accepts the target language, a counter-example is provided otherwise.We study language learning over large or infinite alphabets within a general framework but our aim is to provide solutions for particular concrete instances. For this, we focus on the two main aspects of the problem. Initially, we assume that equivalence queries always provide a counter-example which is minimal in the length-lexicographic order when the conjecture automaton is incorrect. Then, we drop this ``strong'' equivalence oracle and replace it by a more realistic assumption, where equivalence is approximated by testing queries, which use sampling on the set of words. Such queries are not guaranteed to find counter-examples and certainly not minimal ones. In this case, we obtain the weaker notion of PAC (probably approximately correct) learnability and learn an approximation of the target language. All proposed algorithms have been implemented and their performance, as a function of automaton and alphabet size, has been empirically evaluated.

The focus of this thesis is the fast network anomaly detection based on automata learning. It describes and compares several chosen automata learning algorithms including their adaptation for the learning of network characteristics. In this work, various network anomaly detection methods based on learned automata are proposed which can detect sequential as well as statistical anomalies in target communication. For this purpose, they utilize automata's mechanisms, their transformations, and statistical analysis. Proposed detection methods were implemented and evaluated using network traffic of the protocol IEC 60870-5-104 which is commonly used in industrial control systems.