|
|
Finding Weaknesses of Hyperscan
Hrabovský, Jiří ; Vojnar, Tomáš (referee) ; Síč, Juraj (advisor)
Cilem této bakalářské práce je vysvětlit, jak funguje open source vyhledávač regulárních výrazů Hyperscan, a poskytnutí přehledu algoritmů, které interně používá. Druhým cílem je pomocí experimentů zjistit, jak moc lze ovlivnit výkon Hyperscanu skenovaným textem. Na základě zdrojového kódu a článků od autorů Hyperscanu je v kapitole 3 vysvětleno, jak Hyperscan vyhledává regulární výrazy v textu a v kapitole 4 jsou vysvětleny implementace konečných automatů používaných Hyperscanem. Různé způsoby zpomalení vyhledávačů regulárních výrazů jsou zhodnoceny a je zvolena metoda, která je založena na fungování jedné z implementací konečných automatů používaných v Hyperscanu. Na základě zvolené metody je implementován generátor, který pro vybraný výraz vygeneruje text, jehož skenování by mělo Hyperscanu zabrat výrazně déle než u normálního textu. Provedené benchmarky ukázaly, že pro některé regulární výrazy způsobil generovaný text v porovnání vůči náhodnému textu výrazné prodloužení vyhledávání Hyperscanem. U nejvíce ovlivněného regulárního výrazu trvalo skenování generovaného textu více než 8000krát déle než skenování náhodného textu.
|
|
|
Repetitive Substructures for Efficient Representation of Automata
Šedý, Michal ; Češka, Milan (referee) ; Holík, Lukáš (advisor)
Nedeterministické konečné automaty (NKA) jsou široce využívány napříč mnoha odvětvími počítačové vědy, například pro reprezentaci regulárních výrazů, při monitorování vysoko rychlostních sítí, v abstraktním regulárním model checkingu, k verifikaci programů, k rozhodování procedur logik WS1S a WS2S, lineární aritmetiky celých čísel, temporálních logik, nebo dokonce v bioinformatice při vyhledávání sekvencí nukleotidů v DNA. Automaty s velkým množstvím stavů mohou v řadě algoritmů vést k exponenciálnímu nárůstu stavového prostoru. Tento problém lze zmírnit použitím minimalizačních technik slučování stavů a prořezávání hran přechodů. Tyto metody však mohou i přes svou značnou efektivitu zanechat ve výsledných automatech duplicitní podstruktury s ekvivalentními přechody. Existují dokonce typy automatů, které nelze těmito standardními technikami minimalizovat vůbec. Tato práce představuje nový přístup k minimalizaci automatů založený na transformaci NKA na nedeterministický zásobníkový automat (NZA). Tato transformace identifikuje skupinu podobných podstruktur a nahradí ji jednou společnou strukturou (procedurou). Tímto způsobem jsme byli schopni zredukovat automaty až o dalších 67.3%. Myšlenka transformace NKA na NZA lze přirovnat k transformaci sekvenčního programu na program, který využívá funkce a zásobníkem volání.
|
|
|
Library for Fast Network Traffic Processing
Vokráčko, Lukáš ; Viktorin, Jan (referee) ; Kořenek, Jan (advisor)
This thesis is focused on time-critical operations in context of computer networks. Processed operations are packet classification, specially one-dimensional classification, longest prefix matching using binary search on prefix length and TreeBitmap, pattern matching using Aho-Corasick, regular expression matching and packet header analysis and extraction. Purpose of this work is to design API for library implementing these operations. Implementation speed of these operations is measured on Intel and ARM platforms.
|
|
|
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.
|
|
|
Scientific Web Portal Generator
Pavelka, Petr ; Schwarz, Petr (referee) ; Smrž, Pavel (advisor)
Scientific web portal generator is a large project. It's purpose is to create a system for building web portals for providing the view of science publications of authors. One of the parts of this project is module for searching of homepages. The goal of this bachelor's thesis is the implementation of of this module using the program or script. Content of this thesis is to find the best way of method of extraction the semantic information from the marked text, design and development o the system and creating the test set for the purpose of testing. The output of this thesis should be prototype of program or script, which will generate XML file with the URL adresses of homepages of authors. System should have XML input. Almost entire thesis is about analyzing of this problem and choosing the best solution.
|
|
|
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.
|
|
|
XML Dictionary Tagging
Vavrečan, Lukáš ; Škoda, Petr (referee) ; Smrž, Pavel (advisor)
This thesis deals with processing of electronic dictionaries in the LMF format, their analysis and conversion into an unified form. The aim is to create a system, that can make the machine processing of dictionaries easier, thanks to the mass changes. We will introduce the necessary technology, especially Python3, format XML and LMF.
|
|
|
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ě.
|
|
|
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.
|
|
|
Accessibility of Web Technologies and Standards
Konečná, Kateřina ; Trchalík, Roman (referee) ; Očenášek, Pavel (advisor)
This thesis deals with accessibility and web standards. It explains the importance of creating accessible web pages due to disabled users. Individual disabilities are briefly described in a separate chapter. The thesis presents a summary of Web accessibility standards in Europe, America, Australia and Asia. This analysis is completed by comparing the individual countries. The second part focuses on the formalization of different ways, where three methods are applied to three different guidelines.
|
guest ::
