Paper Info
Title
Accelerating DFA Construction by Parallelizing Subset Construction
Abstract
Recently there have been increasing research interests on regular expression matching for its widely application in network systems to recognize predefined signatures in suspicious network traffic. Deterministic Finite Automaton (DFA) is the basic data structure for regular expression matching. Though DFA satisfies the need of real-time processing of network traffic in online systems, the construction of DFA is very time-consuming that prevents it from being applied on large sets of signature. In this article, we propose two approaches to parallelize the traditional sequential subset construction algorithm, which is used to convert a non-deterministic finite automaton (NFA) to an equivalent DFA, in order to accelerate DFA construction. The first proposed algorithm PRW is based on fine-grained locks on shared data structures to ensure multiple worker threads construct a DFA in parallel safely. The second proposed algorithm ARW splits the read and write accesses on shared data structures, and distributes the read operations and write operations to the multithread stage and the single-thread stage respectively. Experiment demonstrates the efficiency of our algorithms on real signatures of open source systems, and the speed-up ratio of PRW and ARW is up to 1.72 and 2.71 respectively with 4 worker threads.
Year
DOI
Venue
2014
10.1007/978-3-662-47401-3_3
Communications in Computer and Information Science
Keywords
Field
DocType
Automaton,DFA construction,Subset construction,Parallel algorithm
Data structure,Regular expression,Parallel algorithm,Deterministic finite automaton,Computer science,Automaton,Powerset construction,Thread (computing),Finite-state machine,Theoretical computer science
Conference
Volume
ISSN
Citations 
520
1865-0929
1
PageRank 
References 
Authors
0.35
4
3
Name
Order
Citations
PageRank
yan shao110.35
Yanbing Liu215516.38
Jianlong Tan322.06