|
|
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.
|
|
|
Perfect Hashing in FPGA
Matušová, Lucie ; Košař, Vlastimil (referee) ; Kaštil, Jan (advisor)
This thesis deals with a design and implementation of a perfect hashing in FPGA by using an FCH method. The method requires 2.6 bits per key to be stored. For the purposes of reference implementation the CMPH library has been used. The functionality of the implemented unit was verified in simulations by the program ModelSim and by experiments on ML605 board bedded with Virtex-6 chip. An experimental part of this work applies to an analysis of enhancement possibilities of the frequency unit. Maximum achieved frequency is 191 MHz. Possible directions of this work are discussed in the conclusion.
|
|
|
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.
|
|
|
Hash functions - characteristics, implementation and collisions
Karásek, Jan ; Sobotka, Jiří (referee) ; Lambertová, Petra (advisor)
Hash functions belong to elements of modern cryptography. Their task is to transfer the data expected on the entry into a unique bite sequence. Hash functions are used in many application areas, such as message integrity verification, information authentication, and are used in cryptographic protocols, to compare data and other applications. The goal of the master’s thesis is to characterize hash functions to describe their basic characteristics and use. Next task was to focus on one hash function, in particular MD5, and describe it properly. That means, to describe its construction, safety and possible attacks on this function. The last task was to implement this function and collisions. The introductory chapters describe the basic definition of hash function, the properties of the function. The chapters mention the methods preventing collisions and the areas were the hash functions are used. Further chapters are focused on the characteristics of various types of hash functions. These types include basic hash functions built on basic bit operations, perfect hash functions and cryptographic hash functions. After concluding the characteristics of hash functions, I devoted to practical matters. The thesis describes the basic appearance and control of the program and its individual functions which are explained theoretically. The following text describes the function MD5, its construction, safety risks and implementation. The last chapter refers to attacks on hash functions and describes the hash function tunneling method, brute force attack and dictionary attack.
|
|
|
Development of generation of Content Adressable Delayed DFA from Set of Regular Expression
Hammer, Jan ; Dvořák, Milan (referee) ; Kaštil, Jan (advisor)
This work deals with contruction of enhanced types of finite automata from sets of regular expressions. The main focus is on enhancement called CD2FA - Content Addressed Delayed Input DFA, which is designed to be used for deep packet inspection throughout the net, in order to lower memory requirements and retain the throughput. Automata constructed in this manner are used to get memory requirement statistics which show that CD2FAs are about ten times more compact then original DFAs. Then some enhancements dealing with the process of CD2FA construction are presented, particularly enhancement of preparation of state addressing by perfect hashing.
|
|
|
Development of generation of Content Adressable Delayed DFA from Set of Regular Expression
Hammer, Jan ; Dvořák, Milan (referee) ; Kaštil, Jan (advisor)
This work deals with contruction of enhanced types of finite automata from sets of regular expressions. The main focus is on enhancement called CD2FA - Content Addressed Delayed Input DFA, which is designed to be used for deep packet inspection throughout the net, in order to lower memory requirements and retain the throughput. Automata constructed in this manner are used to get memory requirement statistics which show that CD2FAs are about ten times more compact then original DFAs. Then some enhancements dealing with the process of CD2FA construction are presented, particularly enhancement of preparation of state addressing by perfect hashing.
|
|
|
Perfect Hashing in FPGA
Matušová, Lucie ; Košař, Vlastimil (referee) ; Kaštil, Jan (advisor)
This thesis deals with a design and implementation of a perfect hashing in FPGA by using an FCH method. The method requires 2.6 bits per key to be stored. For the purposes of reference implementation the CMPH library has been used. The functionality of the implemented unit was verified in simulations by the program ModelSim and by experiments on ML605 board bedded with Virtex-6 chip. An experimental part of this work applies to an analysis of enhancement possibilities of the frequency unit. Maximum achieved frequency is 191 MHz. Possible directions of this work are discussed in the conclusion.
|
|
|
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.
|
|
|
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.
|
|
|
Hash functions - characteristics, implementation and collisions
Karásek, Jan ; Sobotka, Jiří (referee) ; Lambertová, Petra (advisor)
Hash functions belong to elements of modern cryptography. Their task is to transfer the data expected on the entry into a unique bite sequence. Hash functions are used in many application areas, such as message integrity verification, information authentication, and are used in cryptographic protocols, to compare data and other applications. The goal of the master’s thesis is to characterize hash functions to describe their basic characteristics and use. Next task was to focus on one hash function, in particular MD5, and describe it properly. That means, to describe its construction, safety and possible attacks on this function. The last task was to implement this function and collisions. The introductory chapters describe the basic definition of hash function, the properties of the function. The chapters mention the methods preventing collisions and the areas were the hash functions are used. Further chapters are focused on the characteristics of various types of hash functions. These types include basic hash functions built on basic bit operations, perfect hash functions and cryptographic hash functions. After concluding the characteristics of hash functions, I devoted to practical matters. The thesis describes the basic appearance and control of the program and its individual functions which are explained theoretically. The following text describes the function MD5, its construction, safety risks and implementation. The last chapter refers to attacks on hash functions and describes the hash function tunneling method, brute force attack and dictionary attack.
|
guest ::
