Fakulta informačních technologií VUT v Brně

Detail publikace

NFA Reduction for Regular Expressions Matching Using FPGA

KOŠAŘ Vlastimil, ŽÁDNÍK Martin a KOŘENEK Jan. NFA Reduction for Regular Expressions Matching Using FPGA. In: Proceedings of the 2013 International Conference on Field Programmable Technology. Kyoto: IEEE Computer Society, 2013, s. 338-341. ISBN 978-1-4799-2199-7.
Název česky
Redukce NKA pro vyhledávání řetězců popsaných regulárními výrazy v FPGA
Typ
článek ve sborníku konference
Jazyk
angličtina
Autoři
Abstrakt
Bylo navrženo mnoho algoritmů pro akceleraci vyhledávání řetězců popsaných regulárními výrazy za pomoci mapování nedeterministického konečného automatu do obvodu implementovaného v FPGA. Pro dosažení vysoké propustnosti využívají tyto algoritmy unikátních vlastností FPGA. Na druhou stranu limituje omezené množství zdrojů FPGA počet implementovatelných regulárních výrazů.
V tomto článku je studována použitelnost technik redukce NKA - formální aparát umožňující redukovat počet stavů a přechodů NKA před jeho mapováním do FPGA. Článek představuje několik technik redukce NKA, každá z nic má rozdílnou redukční sílu s časovou složitost.
Pro vyhodnocení jsou použity regulární výrazy z IDS Snort a projektu L7 decoder. Nejlepší algoritmy redukce NKA dosahují více než 66% redukce počtu stavů pro modul Snortu ftp. Tato redukce odpovídá 66% redukci LUT a FF v FPGA.
Rok
2013
Strany
338-341
Sborník
Proceedings of the 2013 International Conference on Field Programmable Technology
Konference
The 2013 International Conference on Field-Programmable Technology, Kyoto, JP
ISBN
978-1-4799-2199-7
Vydavatel
IEEE Computer Society
Místo
Kyoto, JP
BibTeX
@INPROCEEDINGS{FITPUB10306,
   author = "Vlastimil Ko\v{s}a\v{r} and Martin \v{Z}\'{a}dn\'{i}k and Jan Ko\v{r}enek",
   title = "NFA Reduction for Regular Expressions Matching Using FPGA",
   pages = "338--341",
   booktitle = "Proceedings of the 2013 International Conference on Field Programmable Technology",
   year = 2013,
   location = "Kyoto, JP",
   publisher = "IEEE Computer Society",
   ISBN = "978-1-4799-2199-7",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/10306"
}
Soubory
Nahoru