Faculty of Information Technology, BUT

Publication Details

Hash-based Pattern Matching for High Speed Networks

FUKAČ Tomáš and KOŘENEK Jan. Hash-based Pattern Matching for High Speed Networks. In: 2019 22nd International Symposium on Design and Diagnostics of Electronic Circuits & Systems (DDECS). Cluj-Napoca: Institute of Electrical and Electronics Engineers, 2019, pp. 1-5. ISBN 978-1-72810-073-9.
Czech title
Vyhledávání vzorů založené na hash funkcích pro vysokorychlostní sítě
Type
conference paper
Language
english
Authors
Keywords
regular expression matching, pattern matching, hash function, high speed network, network security
Abstract
Regular expression matching is a complex task which is widely used in network security monitoring applications. With the growing speed of network links and the number of regular expressions, pattern matching architectures have to be improved to retain wire-speed processing. Multi-striding is a well-known technique to increase processing speed but it requires a lot of FPGA resources. Therefore, we focus on the design of new hardware architecture for fast pre-filtering of network traffic. The proposed pre-filter performs fast hash-based matching of short strings, which are specific for matched regular expressions. As the proposed pre-filter significantly reduces input traffic, exact pattern matching can operate on significantly lower speeds. Then the exact pattern match can be done by CPU or by a slow automaton with a few hardware resources. The paper provides analyses of false-positive detection of the pre-filter with respect to the length of matching strings. The number of false-positives is low, even if the length of the selected strings is short. Therefore input traffic can be significantly reduced. For 100 Gb links, the pre-filter reduced the input data to 1.83 Gbps using four-symbol strings.
Annotation
Regular expression matching is a complex task which is widely used in network security monitoring applications. With the growing speed of network links and the number of regular expressions, pattern matching architectures have to be improved to retain wire-speed processing. Multi-striding is a well-known technique to increase processing speed but it requires a lot of FPGA resources. Therefore, we focus on the design of new hardware architecture for fast pre-filtering of network traffic. The proposed pre-filter performs fast hash-based matching of short strings, which are specific for matched regular expressions. As the proposed pre-filter significantly reduces input traffic, exact pattern matching can operate on significantly lower speeds. Then the exact pattern match can be done by CPU or by a slow automaton with a few hardware resources. The paper provides analyses of false-positive detection of the pre-filter with respect to the length of matching strings. The number of false-positives is low, even if the length of the selected strings is short. Therefore input traffic can be significantly reduced. For 100 Gb links, the pre-filter reduced the input data to 1.83 Gbps using four-symbol strings.
Published
2019
Pages
1-5
Proceedings
2019 22nd International Symposium on Design and Diagnostics of Electronic Circuits & Systems (DDECS)
Conference
22nd IEEE International Symposium on Design and Diagnostics of Electronic Circuits and Systems 2019, Doubletree by Hilton hotel, 9-13 Sindicatelor Street, Cluj, 400029, Romania, RO
ISBN
978-1-72810-073-9
Publisher
Institute of Electrical and Electronics Engineers
Place
Cluj-Napoca, RO
DOI
BibTeX
@INPROCEEDINGS{FITPUB11903,
   author = "Tom\'{a}\v{s} Fuka\v{c} and Jan Ko\v{r}enek",
   title = "Hash-based Pattern Matching for High Speed Networks",
   pages = "1--5",
   booktitle = "2019 22nd International Symposium on Design and Diagnostics of Electronic Circuits \& Systems (DDECS)",
   year = 2019,
   location = "Cluj-Napoca, RO",
   publisher = "Institute of Electrical and Electronics Engineers",
   ISBN = "978-1-72810-073-9",
   doi = "10.1109/DDECS.2019.8724652",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/11903"
}
Back to top