|
Intrusion Detection in Computer Network
Hank, Andrej ; Martínek, Tomáš (referee) ; Kořenek, Jan (advisor)
Continuous spreading and growing bandwidth of computer networks brings many security threats. Intrusion Detection System (IDS) is a mean to provide network security. Software IDS aplications gain only low throughput and that is why hardware accelerators are under heavy development. Probe Traffic Scanner is a hardware accelerator developed in Liberouter project with use of FPGA technology. Main core of acceleration is searching packet payload for simple suspicious strings. Regular expressions provide complex way of describing strings. This bachelor thesis adds feature of searching according to Perl Compatible Regular Expressions (PCRE) to Traffic Scanner Probe by implemented transformer. In addition design and implementation of control software allowing users to use functions provided by the Probe have been created. Conception of intrusion detection in network utilizing Traffic Scanner is outlined so as possibilities of cooperation with other security devices.
|
|
Simulation of Entities Collective Behavior in Virtual World
Vymazal, Tomáš ; Žák, Pavel (referee) ; Láník, Aleš (advisor)
Theme of this work is to evaluate and compare aviable paradigms for entity control in virtual worlds, and to implement one of these paradigms in application. Dynamic finite state machine upgraded using genetic algorithms has been chosen. This paradigm should make agent's behavior better and adapt agent to required state: i.e. make agent harvest resources in virtual world. Output of this work is application for running evolution and application for 3D view of agent's behavior.
|
|
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.
|
|
Aproximate String Matching
Toth, Róbert ; Košař, Vlastimil (referee) ; Kaštil, Jan (advisor)
This thesis deals with the problem of approximate string matching, ie. string matching allowing errors. Initially, we will define the problem itself and demonstrate variety of it's applications, followed by short survey of different approaches to cope with this problem. The remaining part of the work is focused on algorithms based on the use of deterministic finite automatons. Main algorithms in this area will be presented. Those will be implemented in Python programming language and thoroughly compared in series of experiments.
|
|
Efficient Algorithms for Finite Automata
Hruška, Martin ; Rogalewicz, Adam (referee) ; Lengál, Ondřej (advisor)
Nondeterministic finite automata are used in many areas of computer science, including, but not limited to, formal verification, the design of digital circuits or for the representation of a regular language. Their advantages over deterministic finite automata is that they may represent a language in even exponentially conciser way. However, this advantage may be lost if a naive approach to some operations is taken, in particular for checking language inclusion of a pair of automata, the naive implementation of which performs an explicit determinization of one of the automata. Recently, several new techniques for this operation that avoid explicit determinization (using the so-called antichains or bisimulation up to congruence) have been proposed. The main goal of the presented work is to efficiently implement these techniques as a new extension of the VATA library. The implementation has been evaluated and is superior to other implementations in over 90% of tested cases by the factor of 2 to 100.
|
|
Morphological Analyser Implemented as FSAs
Bezák, Jakub ; Schwarz, Petr (referee) ; Smrž, Pavel (advisor)
The aim of this paper is to introduce to its reader the field of morphemics and morphemic analysis of slovak language using morphemic analyser and to signify the difference from other world languages. In this text it is also explained the importance of finding base form of words while analysing slovak texts. Other part analyses the optimal storage of large dictionaries using finite state automata minimization. The end contains the comparison between various forms of implementation.
|
|
Implementation of the Pattern Matching Unit in the FPGA
Košař, Vlastimil ; Kořenek, Jan (referee) ; Kaštil, Jan (advisor)
This term project focuses on algorithms for pattern matching used in modern IDS. The main focus is on regular expression matching. It deals with methods based on deterministic and nondeterministic finite automata, hybrid methods and with method based on regular expressions as programing langue for specialised processors. Implementation of pattern matching units based on some of described methodologies is described in next part. Methodology for resource consumption estimation is also described. Developed software system for unit generation is described in the next part. In the final part results are presented and discused.
|
| |
|
Fast Regular Expression Matching Using FPGA
Kaštil, Jan ; Martínek, Tomáš (referee) ; Kořenek, Jan (advisor)
The thesis explains several algorithms for pattern matching. Algorithms work in both software and hardware. A part of the thesis is dedicated to extensions of finite automatons. The second part explains hashing and introduces concept of perfect hashing and CRC. The thesis also includes a suggestion of possible structure of a pattern matching unit based on deterministic finite automatons in FPGA. Experiments for determining the structure and size of resulting automatons were done in this thesis.
|
|
Lexical Analyzer for Multiprocesor Computers
Otáhal, Jiří ; Goldefus, Filip (referee) ; Čermák, Martin (advisor)
Aim of this thesis is to invent method, which should accelerate speed of the analysis of source texts with multiprocessor computers. For this purpose application runs multiple process in Unix system. Each undergoing process analyzes exact partition in source file and then closes itself. Outcome of this process are internal structures, which presents exact partition. Inter-code is sequentially built from the structures which are subsequently interpreted. This kind of parallel analysis achieves acceleration of speed on the contrary of typical sequential analysis.
|