Fast and Memory-Efficient Regular Expression Matching Using Transition Sharing

Shuzhuang ZHANG  Hao LUO  Binxing FANG  Xiaochun YUN  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E92-D   No.10   pp.1953-1960
Publication Date: 2009/10/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E92.D.1953
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on New Technologies and their Applications of the Internet)
Category: DRM and Security
Keyword: 
regular expression,  memory reduction,  deep packet inspection,  transition sharing,  

Full Text: PDF(834.1KB)>>
Buy this Article




Summary: 
Scanning packet payload at a high speed has become a crucial task in modern network management due to its wide variety applications on network security and application-specific services. Traditionally, Deterministic finite automatons (DFAs) are used to perform this operation in linear time. However, the memory requirements of DFAs are prohibitively high for patterns used in practical packet scanning, especially when many patterns are compiled into a single DFA. Existing solutions for memory blow-up are making a trade-off between memory requirement and memory access of processing per input character. In this paper we proposed a novel method to drastically reduce the memory requirements of DFAs while still maintain the high matching speed and provide worst-case guarantees. We removed the duplicate transitions between states by dividing all the DFA states into a number of groups and making each group of states share a merged transition table. We also proposed an efficient algorithm for transition sharing between states. The high efficiency in time and space made our approach adapted to frequently updated DFAs. We performed several experiments on real world rule sets. Overall, for all rule sets and approach evaluated, our approach offers the best memory versus run-time trade-offs.