|
|
Beat Grep with Counters, Challenge
Horký, Michal ; Češka, Milan (referee) ; Holík, Lukáš (advisor)
Vyhledávání regulárních výrazů má ve vývoji softwaru nezastupitelné místo. Rychlost vyhledávání může ovlivnit použitelnost softwaru, a proto je na ni kladen velký důraz. Pro určité druhy regulárních výrazů mají standardní přístupy pro vyhledávání vysokou složitost. Kvůli tomu jsou náchylné k útokům založeným na vysoké náročnosti vyhledávání regulárních výrazů (takzvané ReDoS útoky). Regulární výrazy s omezeným opakováním, které se v praxi často vyskytují, jsou jedním z těchto druhů. Efektivní reprezentace a rychlé vyhledávání těchto regulárních výrazů je možné s použítím automatu s čítači. V této práci představujeme implementaci vyhledávání regulárních výrazů založeném na automatech s čítači v C++. Vyhledávání je implementováno v rámci RE2, rychlé moderní knihovny pro vyhledávání regulárních výrazů. V práci jsme provedli experimenty na v praxi používaných regulárních výrazech. Výsledky experimentů ukázaly, že implementace v rámci nástroje RE2 je rychleší než původní implementace v jazyce C#.
|
|
|
Alternative Transformations of Language Models
Havel, Martin ; Beníčková, Zuzana (referee) ; Meduna, Alexandr (advisor)
This thesis provides a summary of knowledge of regular expressions, finite automatas and transformation from regular expression to finite automata. The thesis proposes new transformation focused on minimal count of states and rules of finite automatas. Concept of alternative transformation is processed into algorithms and proved by mathematical proofs. The aim of thesis is to introduce approaches to transformation with new ones in the field of regular expressions and finite automatas. Great attention is dedicated to economic perspective of final finite automata. There were created algorithms, which are capable of transformation regular expression to finite automata. This work also provides a simple recipe for implementation of these structures. We introduced generic concept of transformation, that allows to create less complicated finite automatas. Using presented techniques it is possible to expand known transformation with new ones.
|
|
|
Parametric Properties for Log Checker
Mutňanský, Filip ; Kočí, Radek (referee) ; Smrčka, Aleš (advisor)
The goal of this thesis is to implement a tool that based on user defined properties can verify sequences of events in the traces of the program, or the log file. Properties are defined in extended regular expressions. The tool is able to verify parametric properties. User can define relations between parameters of events. Input of this tool is the definition of properties and constraints of parameters. Output of the tool is the report of violated properties with its sequences of events that caused the error.
|
|
|
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.
|
|
|
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.
|
|
|
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.
|
|
|
Conversion of Models of Regular Languages
Navrkal, David ; Kučera, Jiří (referee) ; Křivka, Zbyněk (advisor)
p { margin-bottom: 0.08in; direction: ltr; color: rgb(0, 0, 0); line-height: 150%; widows: 2; orphans: 2; }p.western { font-family: "Times New Roman",serif; font-size: 11pt; }p.cjk { font-family: "Times New Roman",serif; font-size: 11pt; }p.ctl { font-family: "Times New Roman",serif; font-size: 12pt; } My thesis deals with how to didactically demonstrate models of regular languages focusing on their mutual conversions. These conversions are transformation of regular expressions to finite automata (FA), remove epsilon rules from FA and determinization FA. The goal was implement demonstration of these transformations in an application. In this thesis I document development of this application. This application was programmed in language C++ using graphic library Qt 5. The application was developed in an operating system (OS) Linux and tested in OS Microsoft Windows 7. All these conversions are implemented. The application is user-friendly, intuitive and functional. The application was not tested on a wider sample of students. As the main benefit, the application can help students of formal languages and finite automata better understand this theory using didactical examples. Source codes of this project (regularConvertor) are available online on Github server.
|
|
|
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.
|
|
|
Context-Dependent Scanner
Hatina, Peter ; Koutný, Jiří (referee) ; Čermák, Martin (advisor)
This paper is devoted to principles of a lexical analysis and to a means of context resolution of a lexeme type, depending on its source code position. The lexical analysis, process of a lexical analyzer creation and possible solution for context lexeme recognition, based on a multiple automata system, is described. Lexical analyzer functionality is extended to accept tokens in other languages code blocks.
|
|
|
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.
|
guest ::
