Ing. Jan Kořenek, Ph.D.

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.
Jazyk publikace:angličtina
Název publikace:NFA Reduction for Regular Expressions Matching Using FPGA
Název (cs):Redukce NKA pro vyhledávání řetězců popsaných regulárními výrazy v FPGA
Strany:338-341
Sborník:Proceedings of the 2013 International Conference on Field Programmable Technology
Konference:The 2013 International Conference on Field-Programmable Technology
Místo vydání:Kyoto, JP
Rok:2013
ISBN:978-1-4799-2199-7
Vydavatel:IEEE Computer Society
Soubory: 
+Typ Jméno Název Vel. Poslední změna
iconpaper.pdf121 KB2014-01-06 12:35:47
^ Vybrat vše
S vybranými:
Klíčová slova
FPGA, NFA, Reduction, Regular expressions matching
Anotace
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.
BibTeX:
@INPROCEEDINGS{
   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 = {http://www.fit.vutbr.cz/research/view_pub.php.cs?id=10306}
}

Vaše IPv4 adresa: 54.80.211.135
Přepnout na IPv6 spojení

DNSSEC [dnssec]