Detail publikace
NFA Reduction for Regular Expressions Matching Using FPGA
Žádník Martin, Ing., Ph.D. (UPSY FIT VUT)
Kořenek Jan, doc. Ing., Ph.D. (UPSY FIT VUT)
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.
@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" }