|
|
OPTIMIZATION OF ALGORITHMS AND DATA STRUCTURES FOR REGULAR EXPRESSION MATCHING USING FPGA TECHNOLOGY
Kaštil, Jan ; Plíva, Zdeněk (referee) ; Vlček, Karel (referee) ; Kotásek, Zdeněk (advisor)
Disertační práce se zabývá rychlým vyhledáváním regulárních výrazů v síťovém provozu s použitím technologie FPGA. Vyhledávání regulárních výrazů v síťovém provozu je výpočetně náročnou operací využívanou převážně v oblasti síťové bezpečnosti a v oblasti monitorování provozu vysokorychlostních počítačových sítí. Současná řešení neumožňují dosáhnout požadovaných multigigabitových propustností při dodržení všech požadavků, které jsou na vyhledávací jednotky kladeny. Nejvyšších propustností dosahují implementace založené na využití inovativních hardwarových architektur implementovaných v FPGA případně v ASIC. Tato disertační práce popisuje nové architektury vyhledávací jednotky, které jsou vhodné pro implementaci jak v FPGA tak v ASIC. Základní myšlenkou navržených architektur je využití perfektní hashovací funkce pro implementaci přechodové tabulky konečného automatu. Dále byla navržena architektura, která umožňuje uživateli zanést malou pravděpodobnost chyby při vyhledávání a tím snížit paměťové nároky vyhledávací jednotky. Disertační práce analyzuje vliv pravděpodobnosti této chyby na celkovou spolehlivost systému a srovnává ji s řešením používaným v současnosti. V rámci disertační práce byla provedena měření vlastností regulárních výrazů používaných při analýze provozu moderních počítačových sítí. Z provedené analýzy vyplývá, že velká část regulárních výrazů je vhodná pro implementaci pomocí navržených architektur. Pro dosažení vysoké propustnosti vyhledávací jednotky práce navrhuje nový algoritmus transformace abecedy, který umožňuje, aby vyhledávací jednotka zpracovala více znaků v jednom kroku. Na rozdíl od současných metod, navržený algoritmus umožňuje konstrukci automatu zpracovávajícího libovolný počet symbolů v jednom taktu. Implementované architektury dosahují v porovnání se současnými metodami úspory paměti zlepšení až 200MB.
|
|
|
Filtering of Texts Extracted from PDF, OCR or Web
Žigárdi, Tomáš ; Plchot, Oldřich (referee) ; Szőke, Igor (advisor)
This bachelor thesis describes normalization of texts created by conversion of other formats and creation of pronunciation dictionaries. They are important in speech processing process. Mistakes caused by conversion and original solution of this problem are analyzed. Design and implementation of normalization steps and pronunciation dictionaries is shown. Results are compared with results of original solution of this problem.
|
|
|
Construction of Effective Automata for Regex Matching in HW
Frejlach, Jakub ; Havlena, Vojtěch (referee) ; Češka, Milan (advisor)
This thesis is motivated by the application of REs in domains requiring fast matching such has deep packet inspections. To ensure sufficient speed a HW acceleration is typically employed. During the acceleration, REs are in the form of NFA synthesized on FPGA. Although HW acceleration solves the speed problems, it suffers from increased consumption of the FPGA components, specifically LUT. The goal of this thesis is to design, implement and experimentally evaluate heuristic method for approximation of FA in context of HW accelerated RE matching. The purpose of this approximation is to lower consumption of LUT components during FPGA synthesis. The key idea of the method is to add some transitions allowing to construct a smaller number of character classes and thus to reduce the number of LUT implementing the transition relation while reducing the error by modifying only less significant parts of FA. Proposed method together with evaluation pipeline is implemented in TOFA tool. Technique was evaluated on both synthetic and real data. Results of experiments shows, that transitional approximation works especially well on automatas with large number of equivalence character classes.
|
|
|
Reliability Measurement of the Pattern Matching
Dvořák, Milan ; Košař, Vlastimil (referee) ; Kaštil, Jan (advisor)
This thesis deals with the pattern matching methods based on finite automata and describes their optimizations. It presents a methodology for the measurement of reliability of pattern matching methods, by comparing their results to the results of the PCRE library. Experiments were conducted for a finite automaton with perfect hashing and faulty transition table. Finally, the resulting reliability evaluation of the algorithm is shown and possible solutions of the identified problems are proposed.
|
|
|
Parallel Lexical Analyzer
Ježek, Lukáš ; Koutný, Jiří (referee) ; Čermák, Martin (advisor)
This bachelor thesis deals with generating a lexical analyzer which analyzes a file in parallel, i.e. by several threads at a time. The analyzer is generated on the basis of regular language and is represented by finite automaton with the necessary functions. The emphasis is placed on the parallel processing. The possibility of forward and back threads processing is discussed in this thesis. The method of the forward threads was decided to be used for implementation. The problems during implementation that lead to almost none of the desired speed-up of the analysis are discussed.
|
|
| |
|
|
Regular Expression Based Searching in Text Files
Šimek, Ota ; Samek, Jan (referee) ; Rozman, Jaroslav (advisor)
This paper desribes the design, analysis and implementation of the program, whichis used to search for specific parts of text in text and xml files. To search, you must create a template using two text-matching technigues. These are the regular expressions and XPath expressions. This is desribed in the first chapter. Application allows to process large number of files or files with a high content.
|
|
|
Dictionary Up-Translation System
Schovajsa, Michal ; Kouřil, Jan (referee) ; Smrž, Pavel (advisor)
The thesis concerns with the processing of dictionaries in electronic form, converting them into an unified form, and the problems arising in the process in particular. The subject of the work is to create a system for the elimination of some of these problems in order to facilitate machine processing of dictionaries. At first, different issues of dictionaries transferred into an unified form are concerned. Then, the thesis deals with the solution of these issues and the creation of tools for this purpose. Finally, the results and the efficiency of the instruments created are evaluated.
|
|
|
Automatic Grouping of Regular Expressions
Stanek, Timotej ; Kořenek, Jan (referee) ; Kaštil, Jan (advisor)
This project is about security of computer networks using Intrusion Detection Systems. IDS contain rules for detection expressed with regular expressions, which are for detection represented by finite-state automata. The complexity of this detection with non-deterministic and deterministic finite-state automata is explained. This complexity can be reduced with help of regular expressions grouping. Grouping algorithm and approaches for speedup and improvement are introduced. One of the approches is Genetic algorithm, which can work real-time. Finally Random search algorithm for grouping of regular expressions is presented. Experiment results with these approches are shown and compared between each other.
|
|
|
Construction of the Generalized Finite Automaton
Šoka, Martin ; Košař, Vlastimil (referee) ; Kaštil, Jan (advisor)
The thesis deals with the creation of an algorithm for the construction of the generalized finite automaton. This automaton differs from the conventional finite automaton by the fact that its transitions are defined by words, therefore it is possible to reduce the number of states of the generalized finite automaton. The introduction includes definitions of terms used later in the thesis. In the next chapters I describe the algorithm itself, including the comprehensive analysis of the heuristics for finding a maximal acyclic subgraph in the graph of the automaton. It also describes implementation of the algorithm and experimentation with automatons created by the algorithm.
|
guest ::
