|
|
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.
|
|
|
Construction of Nondeterministic Finite Automata
Stanek, Timotej ; Šimek, Václav (referee) ; Kaštil, Jan (advisor)
This thesis discuss about dilemma in construction of nondeterministic finite automata from PCRE expressions with respect of their parameters with use in Intrusion Detection Systems. There is showed PCRE expressions syntax too. We discussed two different approaches to construct nondeterministic finite automata from PCRE expressions. The implementation of these two algorithms is described. We constructed finite automata with them from expressions of three Intrusion Detection Systems: SNORT, Bro IDS and L7-Filter, and finally we compared their parameters and deduced conclusions.
|
|
|
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.
|
guest ::
