|
|
Učení se automatů pro rychlou detekci anomálií v síťovém provozu
Hošták, Viliam Samuel ; Matoušek, Petr (oponent) ; Holík, Lukáš (vedoucí práce)
Táto práca sa zaoberá rýchlou detekciou sieťových anomálií na základe učenia automatov. Popisuje a porovnáva niekoľko vybraných algoritmov učenia automatov, vrátane ich aplikácie na učenie sieťových charakteristík. Pre takto naučené automaty je navrhnutých niekoľko metód detekcie sieťových anomálií, ktoré umožňujú odhaliť tak sekvenčné, ako aj štatistické anomálie v rámci komunikácie. Za týmto účelom využívajú mechanizmy samotných automatov, ich transformáciu, či štatistickú analýzu. Navrhované metódy detekcie boli implementované a vyhodnotené na prevádzke protokolu IEC 60870-5-104 používaného v industriálnych kontrolných systémoch.
|
|
|
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.
|
|
|
Abstraction of State Languages in Automata Algorithms
Chocholatý, David ; Síč, Juraj (oponent) ; Holík, Lukáš (vedoucí práce)
We explore possibilities of using various abstractions of finite automata languages in optimization of automata algorithms used in automata reasoning. We focus on abstracting languages of states to sets of accepted lengths of word or Parikh images, represented as semi-linear sets, and explore options of using them to optimize automata constructions by pruning states based on abstractions of their languages. We propose several abstractions and work on optimizing their performance. We use two common finite automata problems, synchronous product construction and deciding the emptiness of finite automata intersection, as benchmark problems on which we test our optimizations. Nevertheless, our abstractions are applicable on many other typical automata operations, e.g., complement generation etc. Our experiments show that the proposed optimizations reduce generated state space for both benchmark problems substantially.
|
|
| |
|
|
Hledání regulárních výrazů s využitím technologie FPGA
Kaštil, Jan ; Martínek, Tomáš (oponent) ; Kořenek, Jan (vedoucí práce)
V práci je vysvětluje několik algoritmů pro vyhledávání výrazů v textu. Algoritmy pracují v software i hardware. Část práce se zabývá rozšířením konečných automatů. Další část práce vysvětluje, jak funguje hash a představuje koncept perfektního hashování a CRC. Součástí práce je návrh možné struktury vyhledávací jednotky založené na deterministických konečných automatech v FPGA. V rámci práce byly provedeny exprimenty pro zjištění podoby výsledných konečných automatů.
|
|
|
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.
|
|
|
Efektivní algoritmy pro práci s konečnými automaty
Hruška, Martin ; Rogalewicz, Adam (oponent) ; Lengál, Ondřej (vedoucí práce)
Nedeterministické konečné automaty jsou používány v mnoha oblastech informatiky, mimo jiné také ve formální verifikaci, při návrhu číslicových obvodů nebo pro reprezentaci regulárlních jazyků. Jejich výhodou oproti deterministickým konečným automatům je schopnost až exponenciálně stručnější reprezentace jazyka. Nicméně, tato výhoda může být pozbyta, jestliže je zvolen naivní přístup k implementaci některých operací, jako je na\-pří\-klad test jazykové inkluze dvojice automatů, jehož naivní implementace provádí explicitní determinizaci jednoho z automatů. V nedávné době bylo ale představeno několik nových přístupů, které právě explicitní determinizaci při testu jazykové inkluze předcházejí. Tyto přístupy využívají tzv. antichainů nebo tzv. bisimulace vzhůru ke kongruenci. Cílém této práce je vytvoření efektivní implementace zmíněných přístupů v podobě nového rozšíření knihovny VATA. Vytvořená implementace byla otestována a je až řádově rychlejší v 90% testovaných případů nežli implementace jiné
|
|
|
Lexikální analyzátor pro víceprocesorové počítače
Otáhal, Jiří ; Goldefus, Filip (oponent) ; Čermák, Martin (vedoucí práce)
Cílem práce je vymyslet metodu, která urychlí analýzu zdrojových textů na víceprocesorových počítačích. Pro tento účel aplikace využívá spuštění více procesů pod systémem UNIX. Každý takto vytvořený proces analyzuje předem určený blok ve zdrojovém souboru a poté se ukončí. Výstupem těchto procesů jsou vnitřní struktury, které reprezentují právě daný blok. Ze struktur je již sekvenčně vytvořen mezikód, který se následně interpretuje. Takto provedená paralelní analýza vedla ke zrychlení oproti klasické sekvenční.
|
|
|
Efektivní funkcionální knihovna pro konečné automaty
Říha, Jakub ; Hruška, Martin (oponent) ; Lengál, Ondřej (vedoucí práce)
Konečné automaty jsou důležitou matematickou abstrakcí. Ve formální verifikaci se konečné automaty používají ke stručné reprezentaci regulárních jazyků. V této souvislosti se používají operace nad konečnými automaty, jako je testování jazykové univerzality a inkluze. Naivní přístup k implementaci těchto operací vede k explicitní determinizaci konečného automatu, což může být nakladné a nežádoucí. Nicméně existuje pokročilejší metoda k vykonávání těchto operací nazývaná Antichains algoritmus, která se vyhýbá explicitní determinizaci. Tato práce se zabývá efektivní implementací operací nad konečnými automaty v Haskellu a také porovnává několik implementačních variant. Získané výsledky jsou poté porovnány s knihovnou VATA, což je imperativní implementace knihovny pro práci nad konečnými automaty.
|
|
|
Simulace kolektivního chování entit ve virtuálním světě
Vymazal, Tomáš ; Žák, Pavel (oponent) ; Láník, Aleš (vedoucí práce)
Tématem této práce je zhodnotit a porovnat možnosti řízení entit (agentů) ve virtuálním světě a jeden vybraný přístup realizovat ve formě programu. Pro implementaci byl vybrán přístup, kdy konečný automat, řídící agenta, podléhá evoluci pomocí genetických algoritmů. Tento přístup by měl přizpůsobit, případně vylepšit agentovo chování tak, aby odpovídalo zadaným požadavkům: zde např. aby se agent naučil težit zdroje ve virtuálním světě. Implementace je realizována pomocí modulu pro běh evoluce a pomocí modulu se 3d zobrazením, kde lze prohlížet chování agentů.
|
host ::
RSS.