|
|
Finding Weaknesses of Hyperscan
Hrabovský, Jiří ; Vojnar, Tomáš (oponent) ; Síč, Juraj (vedoucí práce)
This Bachelor's thesis aims to explain how the open sourced regular expression matcher Hyperscan works, and provide overview of algorithms it uses internally. The second objective is conducting experiments to determine how much can the performance of the matcher be affected by the scanned text. Based on the source code and articles by the authors of Hyperscan the overview of how Hyperscan scans the text for patterns is provided in chapter 3 and the implementations of NFA (Nondeterministic Finite Automata) used by the Hyperscaned are explained in chapter 4. How could the matcher be slowed down by input text is discussed and approach focusing on specific implementation of NFA used by Hyperscan is proposed. Generator using the proposed approach that is able to generate text for some expressions, that when scanned using Hyperscan with the given expression takes significantly longer that normal text. Conducted benchmark showed that for some expressions the generated text caused the Hyperscan to scan significantly longer. The most affected regular expression took more than 8000 times longer when scanning the generated text than the random text.
|
|
|
Repetitive Substructures for Efficient Representation of Automata
Šedý, Michal ; Češka, Milan (oponent) ; Holík, Lukáš (vedoucí práce)
Nondeterministic finite automata (NFAs) are widely used across almost every field of computer science, such as for the representation of regular expressions, monitoring high-speed networks, in abstract regular model checking, program verification, in decision procedures of WS1S and WS2S logics, linear integer arithmetic, temporal logics, or even in bioinformatics for searching sequences of nucleotides in DNA. Automata with a large number of states can lead to an exponential increase in the state space in many algorithms. To address this issue, minimization techniques, such as state merging and transition pruning, are used. Despite the strong minimization potential of these methods, the resulting automata can still contain duplicate substructures with equivalent transition sequences. There are even types of automata that cannot be minimized by these standard methods at all. This work presents a novel automata minimization approach based on a transformation of an NFA into a nondeterministic pushdown automaton (NPDA). The transformation identifies multiple similar substructures and replaces them with one common structure (called a procedure). By doing so, we were able to further reduce automata by up to 67.3%. The principle of transforming NFA into NPDA can be understood as a transformation of a purely sequential program into a program with functions and a call stack.
|
|
|
Knihovna pro rychlé zpracování síťových dat
Vokráčko, Lukáš ; Viktorin, Jan (oponent) ; Kořenek, Jan (vedoucí práce)
Tato práce se zabývá časově kritickými operacemi v oblasti počítačových sítích a zahrnuje návrh API pro knihovnu implementující tyto operace. Mezi zpracované operace patří vyhledání nejdelšího shodného prefixu pomocí algoritmů TreeBitmap a binárního vyhledávání na délce prefixu, hledání řetězců algoritmem Aho-Corasick, hledání regulárních výrazů, analýza a extrakce hlaviček paketů a klasifikace paketů. V práci je zhodnocena dosažená rychlost implementace těchto operací na platformách Intel a ARM.
|
|
|
Srovnání rychlosti moderních systémů pro vyhledávání regulárních výrazů
Trávníček, Jan ; Kořenek, Jan (oponent) ; Kaštil, Jan (vedoucí práce)
Tato bakalářská práce popisuje způsob srovnání rychlosti moderních nástrojů pro vyhledávání regulárních výrazů. Pro srovnání rychlosti jednotlivých nástrojů je použita množina regulárních výrazů z IDS systému Snort, kde jsou zadány v PCRE notaci. Tyto regulární výrazy jsou vyhodnocovány různými nástroji a získané výsledky jsou porovnávány mezi sebou. V této práci je také řešen matematický a praktický pohled na pojem regulární výraz a převod regulárních výrazů jazyka Perl do notace regulárních výrazů POSIX.
|
|
|
Generátor vědeckých webových portálů
Pavelka, Petr ; Schwarz, Petr (oponent) ; Smrž, Pavel (vedoucí práce)
Generátor vědeckých webových portálů je rozsáhlý projekt, jehož cílem je vytvoření systému, který umožní budování webových portálů za účelem poskytování přehledu vědeckých prací z konkrétních oblastí. Jednou z částí tohoto projektu je i modul pro vyhledávání domovských stránek autorů publikací. Cílem této bakalářské práce je implementace právě tohoto modulu formou skriptu nebo programu. Náplní mé práce je nalezení vhodné metody extrakce sémantické informace ze značkovaného textu, návrh a vývoj systému, který tuto metodu realizuje a sestavení množiny, na které bude systém otestován. Výstupem bakalářské práce je prototyp programu nebo skriptu, který na základě vstupního souboru ve formátu XML se jmény vědeckých pracovníků vygeneruje výstupní XML soubor s URL adresami na jejich domovské stránky a stránky se seznamem publikací. Převážná část mé práce je věnována důkladné analýze daného problému z různých hledisek, rozčlenění na podproblémy a výběru nejvhodnějších variant řešení.
|
|
|
Efficient Algorithms for Counting Automata
Mikšaník, David ; Holík, Lukáš (oponent) ; Lengál, Ondřej (vedoucí práce)
Counting automata (CAs) are classical finite automata extended with bounded counters. They still denote the class of regular languages but in a more compact way than finite automata. Since CAs are a recent model, there is a gap in the knowledge of efficient algorithms implementing various operations on the CAs. In this thesis, we mainly focus on an existing subclass of CAs called monadic counting automata (MCAs), i.e., CAs with counting loops on character classes, which are common in practice (e.g., detection of packets in network traffic, log analysis). For this subclass, we efficiently solve the emptiness and inclusion problems. Moreover, we provide two extensions of the class of MCAs (but not beyond the class of CAs) and efficiently solve the emptiness problem for them. MCAs naturally arise from regular expressions that are extended by the counting operator limited only to character classes. Thus our algorithm solving the inclusion problem of MCAs can be used in a new method for solving the inclusion problem of such regular expressions. We experimentally evaluated this method on regular expressions from a wide range of applications and compared it with the naive method. The experiments show that the method using our algorithm is less prone the explode. It also outperforms the naive method if the regular expressions contain counting operators with large bounds. As expected, for the easy cases, the naive method is still faster than the method based on our algorithm.
|
|
|
Formát XML pro značkování slovníků
Vavrečan, Lukáš ; Škoda, Petr (oponent) ; Smrž, Pavel (vedoucí práce)
Bakalářská práce se zabývá zpracováním elektronických slovníků ve formátě LMF, jejich analýzou a převodem do jednotné podoby. Cílem je vytvořit systém, který díky hromadným změnám ulehčí strojové zpracování slovníků. Přiblížíme si potřebné technologie, zejména Python3, formát XML a LMF.
|
|
|
Automatic Template Pattern Recognition
Kovařík, David ; Lengál, Ondřej (oponent) ; Šimková, Hana (vedoucí práce)
Spam does not occur as separate messages, but it is sent in so-called campaigns. They are usually generated by a certain template which allows producing large amount of semantically, but not syntactically, equivalent messages. The goal of this work is to design an algorithm able to reversely extract a template of a campaign from a set of concrete messages. The main focus is on spam in SMS communication. However, proposed method is general enough for wider use. The proposed algorithm is based on a method of aligning to sequences, which is used in bioinformatics to detect similar regions of protein strings. Resulting templates are represented as regular expressions. The tool is able to visualize extracted templates using HTML.Results of the tool were validated on more than three hundred real-world campaigns. In most cases extracted regular expressions were able to identify their source campaign.
|
|
|
Implementace filtru síťového provozu v FPGA procesorem Microblaze
Viktorin, Jan ; Korček, Pavol (oponent) ; Kaštil, Jan (vedoucí práce)
Práce se zabývá možnostmi hardwarové akcelerace softwarového filtru síťového provozu běžícímu na procesoru MicroBlaze v FPGA čipu Spartan-3E. Akcelerovanou aplikací je standardní firewall Linuxového jádra názývaný iptables, konkrétně jeho rozšíření L7-filter. L7-filter vyhledává regulární výrazy v provozu procházejícím systémem, a tím umožňuje rozpoznávat různé protokoly aplikační vrstvy. Pro jeho významný vliv na výkonnost aplikace byl nahrazen hardwarovou jednotkou řízenou z vlastního modulu Linuxového jádra. Profilací a měřením propustnosti bylo zjištěno, že je takto možné zvýšit propustnost systému i více než dvojnásobně.
|
|
|
Přístupnost webových technologií a její standardy
Konečná, Kateřina ; Trchalík, Roman (oponent) ; Očenášek, Pavel (vedoucí práce)
Tato bakalářská práce se zabývá přístupností a webovými standardy. Vysvětluje důleţitost vytváření přístupných webových stránek vzhledem k zdravotně postiţeným uţivatelům. Jednotlivá postiţení jsou stručně popsána v samostatné kapitole. Práce prezentuje souhrn webových standardů přístupnosti v Evropě, v Americe, Austrálii a Asii. Tento rozbor je završen srovnáním jednotlivých zemí. Druhá část je zaměřena na různé moţnosti formalizace, kde tři způsoby jsou aplikované na tři různé směrnice.
|
host ::
RSS.