Abstract:
The development of programmable and resource-efficient hardware accelerators for regular expression matching is an important research direction in network security, where high throughput for streaming data processing and resilience against ReDoS (Regular Expression Denial of Service) attacks are critical. This paper presents the HOREC compiler, which is used in the high-level design loop of a programmable hardware accelerator. HOREC utilizes a novel extension of a deterministic finite automaton, enabling compact representation of interval quantifiers with a large number of repetitions, typical for rules in intrusion detection systems. Algorithms are described to reduce the number of transitions in instructions and decrease the total number of instructions. The paper presents a software model of the accelerator based on an interpreter for matching compiled patterns and defines a set of parameters for architectural design space exploration of the hardware accelerator, including available memory size, instruction format, and symbols matching modes. Experimental evaluation was performed on 7234 regular expressions extracted from ET OPEN rules. The results demonstrate the high resource efficiency of the proposed solution: up to 7000 expressions were accommodated in a 64K instruction memory. Furthermore, in 60% of cases, the number of transitions per instruction does not exceed 4, and the use of a global symbol set table for 256 frequently used elements allows each program’s local table to be limited to just 10 symbol sets. The presented results confirm HOREC's applicability for hardware implementation of regular expression matching in network security tasks and show the potential of the proposed approach for high-level design of low-hardware-cost accelerators.
Fulltext:
PDF file (1447 kB)