|
|
Fast Regular Expression Matching Using FPGA
Kubiš, Juraj ; Fukač, Tomáš (referee) ; Matoušek, Denis (advisor)
Bachelor thesis deals with the possibility of hardware acceleration of regular expression matches. The content of the thesis is to analyze existing hardware architectures and evaluate their positive and negative properties. Based on this knowledge, the architecture is designed. It is based on deterministic finite automata with implicit transitions (D2FA), is implemented in VHDL and is synthesized. The synthesis results are analyzed to determine the overall throughput of the architecture. It is designed software to convert regular expressions into a D2FA and to optimize this automaton in order to minimize memory requirements. The implementation is verified and the benefits of individual optimization techniques to reduce memory requirements are evaluated.
|
|
|
Symbolic Automata for Analysing String Manipulating Programs
Kotoun, Michal ; Rogalewicz, Adam (referee) ; Vojnar, Tomáš (advisor)
Mnoho aplikací přijímá, odesílá a zpracovává data v textové podobě. Správné a bezpečné zpracování těchto dat je typicky zajištěno tzv. ošetřením řetězců (string sanitization). Pomocí metod formální verifikace je možné analyzovat takovéto operace s řetězci a prověřit, zda jsou správně navržené či implementované. Naším cílem je vytvořit obecný nástroj pro analýzu systémů jejichž konfigurace lze kódovat pomocí slov z vhodné abecedy, a také jeho specializaci pro analýzu programů pracujících s řetězci. Nejprve jsou popsaný konečné automaty a převodníky a poté různé třídy a podtřídy symbolických převodníků, zejména pak jejich omezení. Na základě těchto informací je pak pro použití v analýze programů navržen nový typ symbolických převodníků. Dále je popsán regulární model checking, speciálně pak jeho variantu založenou na abstrakci automatů, tzv. ARMC, u kterého je známo že dokáže velmi úspěšně překonat problém stavové exploze u automatů a umožňuje nám tzv. dosáhnout pevného bodu v analýze. Poté je navržena vlastní analýza programů psaných v imperativním paradigmatu, a to zejména programů manipulujících s řetězci, založená na principech ARMC. Následuje popis vlastní implementace nástroje s důrazem na jeho praktické vlastnosti. Rovněž jsou popsaný důležité části knihovny AutomataDotNet, na které nástroj staví. Práci je uzavřena diskuzí experimentů s nástrojem provedených na příkladech z knihovny LibStranger.
|
|
|
Improvements of the ASMA Tool for Analysis of String Manipulating Programs via Symbolic Automata
Kmenta, Martin ; Lengál, Ondřej (referee) ; Vojnar, Tomáš (advisor)
V této práci se zabýváme regulárním model checkingem, což je technika pro analýzu programů, jejíchž stavový prostor může být nekonečný v důsledku práce například s neomezenými frontami, parametry, dynamicky propojenými datovými strukturami, rekurzivními procedurami nebo řetězci. Cílem této práce bylo implementovat vylepšení stávajícího prototypu nástroje ASMA implementujícího regulárním model checking nad knihovnou Automata of Microsoftu. Provedli jsme analýzu zdrojového kódu nástroje ASMA a zopakovaly analýzy všech dostupných srovnávacích programů. Identifikovali jsme některá úzká místa a několik z nich jsme vyřešili. Zejména jsme integrovali knihovnu obsahující další redukční algoritmy do nástroje ASMA, vytvořili několik nových verzí operace reverzní konkatenace, která se v benchmarcích ukázala jako velmi nákladná, vylepšili rozhraní příkazového řádku ASMA a implementovali některé další optimalizace. Výpočetní čas se při analýze větších programů snížil o 90 %.
|
|
|
Multi-Level Automata and Their Applications
Pšenák, Kamil ; Tomko, Martin (referee) ; Meduna, Alexandr (advisor)
In this thesis, we will add to already known fnite automata paradigm. We start with basic defnitions used in theoretical informatics. Afterwards we defne multi-level fnite automata, which is the base of this thesis. Then we move on to the compilation process and construction of a compiler. With that we defne lexical analysis as our example for multi-level fnite automata implementation. Once we implement the concept, we compare the new and the old way. Then we dig deeper into theoretical informatics to defne parallel right-linear grammars and languages. To prove a concept we create another concept with implementation strategy, using multi-level framework. Lastly, we mention some other areas in informatics, where this multi-level concept could be useful.
|
|
|
Efficient Algorithms for Finite Automata
Polanský, Ondřej ; Lengál, Ondřej (referee) ; Holík, Lukáš (advisor)
This thesis compares languages C++, C#, OCaml and Python based on speed, memory requirements and programming comfort. The goal of this thesis is to find out how much does the choice of a certain programming language impact the performance of programs working with finite automata. The same set of basic and advanced automata algorithms was implemented in each language and their efficiency was measured on a sample of 200 finite automata using a unix based operating system. Finally, the author presents results and discusses suitability of each language for work with finite automata. This thesis can help with selecting an appropriate programming language for multitude of purposes, including development of automata algorithm libraries or the process of designing programs and prototypes that work with finite automata.
|
|
|
Machine Learning for Formal Language Model Inference
Bardonek, Petr ; Kocman, Radim (referee) ; Křivka, Zbyněk (advisor)
This bachelor thesis deals with the formal language model inference, which is a science discipline on the research field of artificial intelligence. The aim is to create an appliaction that allows the automatic inference of model, such as the finite state machine, for an unknown formal language from the set of the strings of the unknown formal language using the modified machine learning method.
|
|
|
Efficient Algorithms for Finite Automata
Kantor, Tomáš ; Rogalewicz, Adam (referee) ; Lengál, Ondřej (advisor)
This thesis presents new algorithm for complement of nondeterministic finite automata. State-of-the-art methods require conversion to deterministic finite automata, which can have exponentially larger number of states. This new algorithm works separately on each strongly connected component of finite automata. This approach allows to create complement of each component, reduce it and combine with other parts. This algorithm was proven to create less states for specific types of finite automata than existing methods.
|
|
|
Intrusion Detection in Computer Network
Hank, Andrej ; Martínek, Tomáš (referee) ; Kořenek, Jan (advisor)
Continuous spreading and growing bandwidth of computer networks brings many security threats. Intrusion Detection System (IDS) is a mean to provide network security. Software IDS aplications gain only low throughput and that is why hardware accelerators are under heavy development. Probe Traffic Scanner is a hardware accelerator developed in Liberouter project with use of FPGA technology. Main core of acceleration is searching packet payload for simple suspicious strings. Regular expressions provide complex way of describing strings. This bachelor thesis adds feature of searching according to Perl Compatible Regular Expressions (PCRE) to Traffic Scanner Probe by implemented transformer. In addition design and implementation of control software allowing users to use functions provided by the Probe have been created. Conception of intrusion detection in network utilizing Traffic Scanner is outlined so as possibilities of cooperation with other security devices.
|
|
|
Multi-Dimensional Languages and Their Automata
Dibďák, Lukáš ; Martiško, Jakub (referee) ; Meduna, Alexandr (advisor)
The Bachelor's Thesis introduces the theory of formal languages and finite automata. It describes generalisation of one-dimensional theory into two dimensions. It introduces basic types of two-dimensional automata, especially on-line tessellation automata. This paper offers algorithms for the process of determinization of on-line tessellation automata. One of the algorithms is used in enclosed application.
|
|
|
Implementation of the Pattern Matching Unit in the FPGA
Košař, Vlastimil ; Kořenek, Jan (referee) ; Kaštil, Jan (advisor)
This term project focuses on algorithms for pattern matching used in modern IDS. The main focus is on regular expression matching. It deals with methods based on deterministic and nondeterministic finite automata, hybrid methods and with method based on regular expressions as programing langue for specialised processors. Implementation of pattern matching units based on some of described methodologies is described in next part. Methodology for resource consumption estimation is also described. Developed software system for unit generation is described in the next part. In the final part results are presented and discused.
|
guest ::
