文档介绍：Fast and Memory-Efficient Regular Expression Matching
for Deep Packet Inspection
Fang Yu1 Zhifeng Chen2 Yanlei Diao3 T. V. Lakshman4 Randy H. Katz1
1 University of California Berkeley 2 Google Inc.
3 University of Massachusetts Amherst 4 Bell Laboratories, Lucent Technologies
Abstract expression matching over the packet payload keep up
with the line-speed packet header processing.
Packet content scanning at a high speed has e Unfortunately, this requirement cannot be met in many
extremely important due to its applications work existing payload scanning implementations. For
security, network monitoring, HTTP load balancing, etc. example, when all 70 protocol filters are enabled in the
In content scanning, the packet payload pared Linux L7-filter [1], we found that the system
against a set of patterns specified as regular expressions. throughput drops to less than 10Mbps, which is well
In this paper, we first show that memory requirements below current LAN speeds. Moreover, over 90% of the
using traditional methods for fast packet scanning are CPU time is spent in regular expression matching,
prohibitively high for many patterns used working leaving little time for other intrusion detection or
applications. We then propose regular expression monitoring functions. On the other hand, although
rewrite techniques that reduce memory usage. Further, many schemes for fast string matching [4-11] have been
we develop a scheme based piling regular recently developed in intrusion detection systems, they
expressions into several engines, which dramatically focus on explicit string patterns only and cannot be
increases the regular expression matching speed easily extended to fast regular expression matching.
without significantly increasing memory usage. We
implement the DFA-based packet scanners. Our The inefficiency in regular expression matching
experiment results using real-world traffic and patterns largely results from the