Publication Details

Deep Packet Inspection in FPGAs via Approximate Nondeterministic Automata

HAVLENA, V.; ČEŠKA, M.; HOLÍK, L.; KOŘENEK, J.; LENGÁL, O.; MATOUŠEK, D.; MATOUŠEK, J.; SEMRIČ, J.; VOJNAR, T. Deep Packet Inspection in FPGAs via Approximate Nondeterministic Automata. In Proceedings - 27th IEEE International Symposium on Field-Programmable Custom Computing Machines, FCCM 2019. San Diego, CA: Institute of Electrical and Electronics Engineers, 2019. p. 109-117. ISBN: 978-1-7281-1131-5.
Czech title
Použití přibližných nedeterministických automatů pro hlubokou inspekci paketů v FPGA
Type
conference paper
Language
English
Authors
Havlena Vojtěch, Ing., Ph.D. (DITS)
Češka Milan, doc. RNDr., Ph.D. (DITS)
Holík Lukáš, doc. Mgr., Ph.D. (DITS)
Kořenek Jan, doc. Ing., Ph.D. (DCSY)
Lengál Ondřej, Ing., Ph.D. (DITS)
Matoušek Denis, Ing.
Matoušek Jiří, Ing., Ph.D. (DCSY)
Semrič Jakub, Bc.
Vojnar Tomáš, prof. Ing., Ph.D. (DITS)
Keywords

intrusion detection system, deep packet inspection, finite automata, approximate
reduction

Abstract

Deep packet inspection via regular expression (RE) matching is a crucial task of
network intrusion detection systems (IDSes), which secure Internet connection
against attacks and suspicious network traffic. Monitoring high-speed computer
networks (100 Gbps and faster) in a single-box solution demands that the RE
matching, traditionally based on finite automata (FAs), is accelerated in
hardware. In this paper, we describe a novel FPGA architecture for RE matching
that is able to process network traffic beyond 100 Gbps. The key idea is to
reduce the required FPGA resources by leveraging approximate nondeterministic FAs
(NFAs). The NFAs are compiled into a multi-stage architecture starting with the
least precise stage with a high throughput and ending with the most precise stage
with a low throughput. To obtain the reduced NFAs, we propose new approximate
reduction techniques that take into account the profile of the network traffic.
Our experiments showed that using our approach, we were able to perform matching
of large sets of REs from Snort, a popular IDS, on unprecedented network speeds.

Published
2019
Pages
109–117
Proceedings
Proceedings - 27th IEEE International Symposium on Field-Programmable Custom Computing Machines, FCCM 2019
Conference
The 27th IEEE International Symposium On Field-Programmable Custom Computing Machines -- FCCM'19, San Diego, CA, US
ISBN
978-1-7281-1131-5
Publisher
Institute of Electrical and Electronics Engineers
Place
San Diego, CA
DOI
10.1109/FCCM.2019.00025
UT WoS
000491873200016
EID Scopus
2-s2.0-85068333761
BibTeX 
@inproceedings{BUT158077,
  author="Vojtěch {Havlena} and Milan {Češka} and Lukáš {Holík} and Jan {Kořenek} and Ondřej {Lengál} and Denis {Matoušek} and Jiří {Matoušek} and Jakub {Semrič} and Tomáš {Vojnar}",
  title="Deep Packet Inspection in FPGAs via Approximate Nondeterministic Automata",
  booktitle="Proceedings - 27th IEEE International Symposium on Field-Programmable Custom Computing Machines, FCCM 2019",
  year="2019",
  pages="109--117",
  publisher="Institute of Electrical and Electronics Engineers",
  address="San Diego, CA",
  doi="10.1109/FCCM.2019.00025",
  isbn="978-1-7281-1131-5",
  url="https://www.fit.vut.cz/research/publication/11951/"
}
Files
Back to top