Managing DFA History with Queue for Deflation DFA |
| |
Authors: | Yi Tang Junchen Jiang Chengchen Hu Bin Liu |
| |
Affiliation: | (1) Department of Computer Science and Technology, Tsinghua Univerisity, Beijing, China;(2) Guest researcher of the State Key Laboratory of Networking and Switching Technology, University of Posts and Telecommunications, Beijing, China; |
| |
Abstract: | There is an increasing demand for network devices to perform deep packet inspection (DPI) in order to enhance network security.
In DPI, the packet payload is compared against a set of predefined patterns that can be specified using regular expressions
(regexes). It is well-known that mapping regexes to deterministic finite automaton (DFA) may suffer from the state explosion
problem. Through observation, we attribute DFA explosion to the necessity of remembering matching history. In this paper,
we investigate how to manage matching history efficiently and propose an extended DFA approach for regex matching called fcq-FA,
which can make a memory size reduction of about 1,000 times with a fully automated approach. In fcq-FA, we use pipeline queues
and counters to help record the matching history. Hence, state explosion caused by Kleene closure and length restriction can
be completely avoided. Furthermore, it achieves a fully automated signature compilation with polynomial running time and space.
The equivalence between fcq-FA and the traditional DFA is guaranteed by a strict theoretical proof, which means fcq-FA can
process all the regexes supported by the traditional DFA. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|