Detail publikace

NFA Reduction for Regular Expressions Matching Using FPGA

KOŠAŘ, V.; ŽÁDNÍK, M.; KOŘENEK, J. NFA Reduction for Regular Expressions Matching Using FPGA. Proceedings of the 2013 International Conference on Field Programmable Technology. Kyoto: IEEE Computer Society, 2013. p. 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
anglicky
Autoři
Košař Vlastimil, Ing., Ph.D. (UPSY)
Žádník Martin, Ing., Ph.D. (UPSY)
Kořenek Jan, doc. Ing., Ph.D. (UPSY)
Klíčová slova

FPGA, NFA, Reduction, Regular expressions matching

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
ISBN
978-1-4799-2199-7
Vydavatel
IEEE Computer Society
Místo
Kyoto
BibTeX 
@inproceedings{BUT104513,
  author="Vlastimil {Košař} and Martin {Žádník} and Jan {Kořenek}",
  title="NFA Reduction for Regular Expressions Matching Using FPGA",
  booktitle="Proceedings of the 2013 International Conference on Field Programmable Technology",
  year="2013",
  pages="338--341",
  publisher="IEEE Computer Society",
  address="Kyoto",
  isbn="978-1-4799-2199-7",
  url="https://www.fit.vut.cz/research/publication/10306/"
}
Nahoru