|
|
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.
|
|
| |
|
|
Comparing Main Spectroscopic Da
Pokorny, Josef
This article deals with comparing of data in the main world spectroscopic databases NIST and Kurucz. Our target was to calculate differences in the ratio of Stark broadening and function F which depends on electron density, temperature and pressure. Stark broadening is one of pressure broadenings of spectral lines which arise from the collisions of the emitters with neighboring particles. Stark broadening is due to charged perturbers. We developed the program NKrov for the comparison of databases with the help of regular expressions and the program awk. There were some differences found in input data for the silicon between NIST and Kurucz databases. Our results can be used in further research on silicon spectral lines.
|
|
|
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.
|
|
|
Automatic Template Pattern Recognition
Kovařík, David ; Lengál, Ondřej (referee) ; Šimková, Hana (advisor)
Spam se typicky nevyskytuje ve formě samostatných zpráv, ale často bývá sdružován do takzvaných kampaní. Ty bývají automaticky generovány pomocí šablon. Díky tomu jsou jednotlivé zprávy sémanticky, ale ne syntakticky, ekvivalentní. Cílem práce je navrhnout algoritmus schopný z množiny zpráv jedné kampaně zpětně extrahovat šablonu, ze které tyto zprávy byly generovány. Práce se zaměřuje na spam v SMS komunikaci, ale navržené postupy jsou dostatečně obecné pro širší použití. Algoritmus je postaven na metodě zarovnávání dvou sekvencí, používané v bioinformatice pro nalezení podobných oblastí proteinových řetězců. Výstupem je regulární výraz popisující šablonu dané kampaně. Součástí řešení je také nástroj pro vizualizaci šablony pomocí HTML.Řešení bylo ověřeno na přibližně třech stovkách skutečných kampaní z celého světa. V naprosté většině případů je poskytnutý výsledek postačující pro identifikaci kampaně.
|
|
|
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.
|
|
|
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.
|
|
|
Comparing Speed of the Modern Systems for Regular Expression Matching
Trávníček, Jan ; Kořenek, Jan (referee) ; Kaštil, Jan (advisor)
This thesis describes how to compare the speed of modern tools for regular expressions matching. To compare the speed of each tool is used set of regular expressions from the Snort - Intrusion Detection System, which are specified in the PCRE notation. These regular expressions are evaluated by difeerent tools and the results are compared with each other. In this work is also solved difeerence between mathematical and practical perspective on the term of regular expression and transfer Perl regular expressions in POSIX regular expressions.
|
|
|
Implementation of the Network Traffic Filter by Microblaze in FPGA
Viktorin, Jan ; Korček, Pavol (referee) ; Kaštil, Jan (advisor)
The thesis explores the area of hardware acceleration of a software network traffic filter running inside processor MicroBlaze in the FPGA Spartan-3E. The accelerated application is widely used firewall from the Linux Kernel called iptables, more precisely its extension L7-filter. L7-filter performs lookups inside network traffic using regular expressions. Because of its significant influence on the application performance, it has been exchanged with a hardware unit controlled from the Linux Kernel. The performance has been increased more than twice.
|
guest ::
