Accelerating DFA Construction by Hierarchical Merging

Regular expression matching is widely used in many network applications to analyze suspicious traffic against predefined signatures, and to discover anomalous events. Deterministic Finite Automaton (DFA), which recognizes a set of regular expressions, is the basic data structure to scan input traffi...

Full description

Saved in:
Bibliographic Details
Main Authors: Yanbing Liu, Li Guo, Muyi Guo, Ping Liu
Format: Conference Proceeding
Language:English
Subjects:
Acceleration
Automata
Complexity theory
Data structures
Doped fiber amplifiers
Merging
Open source software
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Regular expression matching is widely used in many network applications to analyze suspicious traffic against predefined signatures, and to discover anomalous events. Deterministic Finite Automaton (DFA), which recognizes a set of regular expressions, is the basic data structure to scan input traffic byte by byte. Though DFA meets the requirement of real-time processing of network traffic, constructing a combined DFA for a set of regular expression signatures is very time-consuming, especially when the signature set is large. To attack this problem, we propose new strategies to accelerate DFA construction. The basic idea of our method is to construct the combined DFA by hierarchical merging of the DFAs of each single regular expression. Our method runs in O(|Q||Σ| In n) time, which is substantially superior to the time complexity O(|Q||Σ|(Σ i=1 n |Qi|) 2 ) of classical subset construction algorithm. Experiment on real signatures from open-source systems, such as L7-filter, BRO and SNORT, demonstrates that our method performs 45 times faster than the subset construction algorithm on average.
ISSN:2158-9178
DOI:10.1109/ISPA.2011.32