|
|
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.
|
|
|
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.
|
|
|
Automatic Creation of Multi-Choice Tests for ISJ
Bambas, Tomáš ; Kouřil, Jan (referee) ; Smrž, Pavel (advisor)
This bachelor's thesis is concerned with a tests creation for the ISJ course. The aim of this work is the implementation of the application which serves for an automatic intelligent creation of tests relating to scripting languages Ruby and Python and regular expressions with support of an automatic evaluating of answers.
|
|
|
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.
|
|
| |
|
|
Creation of Process Automation Tool and Monitoring of Consequent Benefits
Nečas, Kamil ; Neuwirth, Bernard (referee) ; Dydowicz, Petr (advisor)
The bachelor thesis deals with a complete development of a process for automatic preparation of a text for its highlighting inside a DTP document in PDF format, from requirements analysis, through designing and implementation, to an identification of benefits within localization of real projects. The appropriate combination of several steps and effective use of suitable tools lead to a significant replacement of human work by an automated process.
|
|
|
Applications for Teaching Work with Regular Expressions
Heroutová, Tereza ; Čermák, Martin (referee) ; Koutný, Jiří (advisor)
The document describes the formation of an application, which allows interactiv instruction how to work with regular expressions. We stress clear interpretation of material and effective user interface to make handling intuitive as much as possible. The document describes theory of regular expressions, pedagogic side of the things and implementation with feature extensions.
|
|
|
A Tool for Creating Log Message Patterns
Hanus, Igor ; Janoušek, Vladimír (referee) ; Smrčka, Aleš (advisor)
Cieľom práce je vyvtorenie prenositeľnej webovej aplikácie na spracovanie logov pomocou kombinácie Grok vzorova a regulárnych výrazov, za účelom vytvorenia vzoru pre jednotlivé záznamy logu s možnosťou exportovania do YAML formátu, ktorý je spracovateľný nástrojom Plogchecker. Aplikácia bola implementovaná pomocou JavaScript knižnice React použitím jazyka TypeScript. Spracovanie jednotlivých regulárnych výrazov je riešené pomocou knižnice Oniguruma, ktorá je integrovaná do aplikácie pomocou WebAssembly. Dôvodom použitia Oniguruma knižnice bola nekompatibilita medzi prekladačmi regulárnych výrazov definovanými štandardom ECMAScript a prekladačmi, ktoré sú využívané pre preklad Grok výrazov. Realizacia aplikácie bola podrobená automatizovaným testom a užívateľským testom, s opravou zistených nálezov.
|
|
|
Beyond Register Automata: Pushing the Border of Decidability
Gulčíková, Sabína ; Havlena, Vojtěch (referee) ; Lengál, Ondřej (advisor)
Registrový automat (RA) pracujúci nad nekonečnou abecedou je jedným z nástrojov pre pattern matching s backreferenciami, dynamickú verifikáciu, alebo modelovanie paralelných výpočtov. Súčasné riešenia v aplikáciách pattern matchingu používajú backtrackingové algoritmy v prípade nedeterministických regulárnych výrazov. Nemožnosť determinizovať registrový automat spôsobuje, že nie je vhodným formálnym modelom pre riešenie problémov spojených s neefektívnymi aplikáciami backtrackingových algoritmov. Na druhej strane, vybavenosť konečnou pamäťou slúži ako vhodná báza pre ukladanie takzvaných capture groups použitých v takejto aplikácii. Táto práca sa zaoberá predstavením formálneho modelu registrovo množinového automatu. Veľká trieda registrových automatov môže byť transformovaná do tohto deterministického modelu, ktorý okrem iného, dovoľuje vykonávať rýchly pattern matching s backreferenciami. Definované sú vlastnosti zahŕňajúce rozhodnutelnosť testu prázdnosti, determinizovateľnosť, uzavretosť voči Booleovským operáciám. Zároveň tento model porovnávame voči iným registrovým modelom z hľadiska ich vyjadrovacej sily.
|
|
|
Efficient Algorithms for Counting Automata
Mikšaník, David ; Holík, Lukáš (referee) ; Lengál, Ondřej (advisor)
Čítací automaty (CA) jsou klasické konečné automaty rozšířené o omezené čítače. CA stále reprezentují třídu regulárních jazyků, ale kompaktněji než konečné automaty. Jelikož jsou CA nedávným modelem, chybějí zde efektivní algoritmy implementující různé operace nad nimi. V této práci se primárně soustředíme na existující podtřídu CA zvanou monadické čítací automaty (MCA). Jsou to CA s čítacími smyčkami na třídě znaků, které se často vyskytují v praxi (např. při detekci paketů v síťovém provozu nebo analýze log souborů). Pro tuto podtřídu efektivně vyřešíme problémy prázdnosti a inkluze. Navíc poskytneme dvě rozšíření třídy MCA, které jsou stále podtřídou CA, a vyřešíme pro ně efektivně problém prázdnosti. MCA přirozeně vznikají z regulárních výrazů, které jsou rozšířené o čítací operátory vyskytující se pouze na třídě znaků. Náš algoritmus řešící problém inkluze MCA tedy může být použit jako základ nové metody pro testování inkluze takových regulárních výrazů. Tento přístup jsme experimentálně vyhodnotili na regulárních výrazech z praxe a porovnali s naivní metodou. Experimenty ukazují, že metoda používající náš algoritmus je více odolná proti stavové explozi. Také překonává naivní metodu, pokud regulární výrazy obsahují čítací operátory s velkými mezemi. Podle očekávání, pro jednoduché případy je naivní metoda stále rychlejší než metoda používající náš algoritmus.
|
guest ::
