ETRI-Knowledge Sharing Plaform

KOREAN
논문 검색
Type SCI
Year ~ Keyword

Detail

Journal Article A Memory-Efficient Deterministic Finite Automaton-Based Bit-Split String Matching Scheme Using Pattern Uniqueness in Deep Packet Inspection
Cited 12 time in scopus Download 44 time Share share facebook twitter linkedin kakaostory
Authors
HyunJin Kim, Kang-Il Choi, Sang-Il Choi
Issue Date
2015-05
Citation
PLoS ONE, v.10, no.5, pp.1-24
ISSN
1932-6203
Publisher
Public Library of Science
Language
English
Type
Journal Article
DOI
https://dx.doi.org/10.1371/journal.pone.0126517
Abstract
This paper proposes a memory-efficient bit-split string matching scheme for deep packet inspection (DPI). When the number of target patterns becomes large, the memory requirements of the string matching engine become a critical issue. The proposed string matching scheme reduces the memory requirements using the uniqueness of the target patterns in the deterministic finite automaton (DFA)-based bit-split string matching. The pattern grouping extracts a set of unique patterns from the target patterns. In the set of unique patterns, a pattern is not the suffix of any other patterns. Therefore, in the DFA constructed with the set of unique patterns, when only one pattern can be matched in an output state. In the bit-split string matching, multiple finite-state machine (FSM) tiles with several input bit groups are adopted in order to reduce the number of stored state transitions. However, the memory requirements for storing the matching vectors can be large because each bit in the matching vector is used to identify whether its own pattern is matched or not. In our research, the proposed pattern grouping is applied to the multiple FSM tiles in the bit-split string matching. For the set of unique patterns, the memory-based bit-split string matching engine stores only the pattern match index for each state to indicate the match with its own unique pattern. Therefore, the memory requirements are significantly decreased by not storing the matching vectors in the string matchers for the set of unique patterns. The experimental results show that the proposed string matching scheme can reduce the storage cost significantly compared to the previous bit-split string matching methods.
KSP Keywords
Bit-split, Deterministic Finite Automaton, Finite State Machine(FSM), Matching engine, Matching vectors, Memory-based, Pattern match, State Transition, Storage Cost, deep packet inspection(DPI), memory requirements
This work is distributed under the term of Creative Commons License (CCL)
(CC BY)
CC BY