Name
Abstract | ||
|---|---|---|
Deep packet inspection, in which packet payloads are matched against a large set of patterns, is an important algorithm in many networking applications. Nondeterministic Finite Automaton (NFA) and Deterministic Finite Automaton (DFA) are the basis of existing algorithms. However, both NFA and DFA are not ideal for real-world rule sets: NFA has the minimum storage, but the maximum memory bandwidth; while DFA has the minimum memory bandwidth, but the maximum storage. Specifically, NFA and DFA cannot handle the presence of character sets, wildcards, and repetitions of character sets or wildcards in real-world rule sets. In this paper, we propose and evaluate a dual Finite Automaton (dual FA) to address these shortcomings. The dual FA consists of a linear finite automaton (LFA) and an extended deterministic finite automaton (EDFA). The LFA is simple to implement, and it provides an alternative approach to handle the repetition of character sets and wildcards (which could otherwise cause the state explosion problem in a DFA) without increasing memory bandwidth. We evaluate the automaton in real-world rule sets using different synthetic payload streams. The results show that dual FA can reduce the number of states up to five orders of magnitude while their memory bandwidth is close to minimum. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1109/TC.2011.231 | IEEE Trans. Computers |
Keywords | Field | DocType |
fast deep packet inspection,dual fa,extended deterministic finite automaton,memory bandwidth,nondeterministic finite automaton,maximum memory bandwidth,dual finite automata,dual finite automaton,character set,minimum memory bandwidth,real-world rule set,deterministic finite automaton,inspection,deep packet inspection,finite automata,bandwidth,automata,payloads,computer network security | Generalized nondeterministic finite automaton,Deterministic automaton,Nondeterministic finite automaton,Deterministic finite automaton,Computer science,Parallel computing,Powerset construction,Algorithm,Theoretical computer science,DFA minimization,Timed automaton,Probabilistic automaton | Journal |
Volume | Issue | ISSN |
62 | 2 | 0018-9340 |
Citations | PageRank | References |
16 | 0.81 | 21 |
Authors | ||
2 | ||