  Deep packet inspection via regular expression (RE) matching is a crucial task
of network intrusion detection systems (IDSes), which secure Internet
connection against attacks and suspicious network traffic. Monitoring
high-speed computer networks (100 Gbps and faster) in a single-box solution
demands that the RE matching, traditionally based on finite automata (FAs), is
accelerated in hardware. In this paper, we describe a novel FPGA architecture
for RE matching that is able to process network traffic beyond 100 Gbps. The
key idea is to reduce the required FPGA resources by leveraging approximate
nondeterministic FAs (NFAs). The NFAs are compiled into a multi-stage
architecture starting with the least precise stage with a high throughput and
ending with the most precise stage with a low throughput. To obtain the reduced
NFAs, we propose new approximate reduction techniques that take into account
the profile of the network traffic. Our experiments showed that using our
approach, we were able to perform matching of large sets of REs from SNORT, a
popular IDS, on unprecedented network speeds.
