Open AccessHardware acceleration of regular expression repetitions in deep packet inspection
Author(s) -
Cronin Brendan,
Wang Xiaojun
Publication year - 2013
Publication title -
iet information security
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.308
H-Index - 34
eISSN - 1751-8717
pISSN - 1751-8709
DOI - 10.1049/iet-ifs.2012.0340
Subject(s) - computer science , regular expression , deep packet inspection , network packet , automaton , expression (computer science) , parallel computing , algorithm , arithmetic , theoretical computer science , programming language , mathematics , computer network
Network Intrusion Detection Systems (NIDS) make extensive use of regular expressions (regexes) as attack signatures. Such expressions can be handled in hardware using a bit‐parallel (BP) architecture based on the Glushkov non‐deterministic finite automata (NFA). However, many expressions contain constrained {min, max} repetitions which first need to be unrolled so that they can be handled by the standard BP system. Such unrolling often leads to an excessive memory requirement which makes handling of such regexes unfeasible. This study presents a solution, based on the standard BP architecture, which incorporates a counting mechanism that renders unrolling unnecessary. As a result, many regexes, which were previously unsuitable for the standard BP system, can now be efficiently handled. Unlike many other approaches, this architecture is dynamically reconfigurable thanks to its memory, rather than logic, based engine. This is important as NIDS rule sets are regularly updated. It can also handle repetition of both single and multi‐symbol sub‐expressions.