Fast Regular Expression Matching Using FPGA

Regular expression, matching, nondeterministic automaton, FPGA

Článek se zabývá rychlým vyhledáváním regulárních výrazů s využitím technologie FPGA. Hledání regulárních výrazů je klíčovou a zároveň nejvíce výpočetně náročnou operací používanou v oblasti monitorování a bezpečnosti počítačových sítí. Současné algoritmy neumožňují konvenčním procesorům dosáhnout u této operace dostatečnou propustnost pro dnes již běžné multi-gigabitové sítě. Vznikla proto řada hardwarových architektur, které umožňují hledání řetězců nebo regulárních výrazů na gigabitových rychlostech. Vysoká rychlost vyhledávání je ale přímo spojena s omezením velikosti množiny hledaných regulárních výrazů. U přístupů založených na deterministických automatech je problém splnit požadavky na velikost a rychlost pamětí, u přístupů založených na nedeterministických automatech je problém s velikostí obvodu a kapacitou FPGA. Článek se proto zabývá redukcí hardwarových zdrojů potřebných pro mapování nedeterministických automatů do technologie FPGA s cílem umožnit hledat větší množiny regulárních výrazů než poskytují současné způsoby mapování. Byl proto navržen algoritmus, který hledá v automatu bezkolizní množiny stavů s cílem mapovat část přechodové tabulky auto- matu do paměti a redukovat tak množství spotřebovaných zdrojů FPGA v počtu look-up tabulek a flip-flop registrů. S navrženým algoritmem byly pro všechny analyzované množiny regulárních výrazů nalezeny bezkolizní množiny stavů, které tvořily v průměru 61,4 % a v jednom případě dokonce 83,6 % všech stavů automatu. Algoritmus byl dále rozšířen pro hledání obecně k bezkolizních množin, což umožnilo pro k=8 pokrýt bezkolizními množinami v průměru 84,7 % stavů u všech automatů vytvořených z analyzovaných množin regulárních výrazů. Dále byl vytvořen formální model systému paralelních částí automatu, který respektuje rozdělení automat na části podle množin stavů a umožňuje na základě vlastností jednotlivých částí optimalizovat proces mapování do FPGA. K formálnímu modelu systému paralelních částí automatu byly vytvořeny architektury NFA Split a NFA k Split, které mapují jednotlivé části automatu do samostatných jednotek s ohledem na jejich vlastnosti. S využitím architektury NFA Split byl u analyzovaných množin regulárních výrazů v průměru redukován počet flip-flop registrů na 43,3 % a počet look-up tabulek 66,8 %.