Limits...
A memory-efficient deterministic finite automaton-based bit-split string matching scheme using pattern uniqueness in deep packet inspection.

Kim H, Choi KI, Choi SI - PLoS ONE (2015)

Bottom Line: 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.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.

View Article: PubMed Central - PubMed

Affiliation: School of Electronics and Electrical Engineering, Dankook University, Yongin-si, Republic of Korea.

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.

No MeSH data available.


Ratio of unique patterns by sweeping the average pattern length.
© Copyright Policy
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC4418843&req=5

pone.0126517.g010: Ratio of unique patterns by sweeping the average pattern length.

Mentions: Firstly, the average pattern length was swept from 10 to 60 with several generated rule sets, where each rule set had 10,000 different patterns. Fig 10 shows the ratio of unique patterns by sweeping the average pattern length, where the average pattern length was denoted as mean. As shown in Fig 10, the ratio of unique patterns was 70.6% when mean was 10. When mean was 60, the ratio of unique patterns reached up to 96.3%. Therefore, as mean increased, the ratio of unique patterns increased. In addition, even though the average pattern length was short, the ratio of unique patterns was over 70%, which means that the proposed string matching scheme can utilize the pattern uniqueness to reduce the memory requirements without the PMV table. Fig 11 shows the ratio of unique patterns by sweeping the number of generated patterns from 1,000 to 32,000. In this case, it was assumed that the average pattern length was 20. As the number of patterns in a rule set increased, the ratio of unique patterns decreased slightly. In addition, 86% percent of patterns were in the set of unique patterns when the number of patterns was 32,000. Fig 12 shows the ratio of unique patterns by sweeping the standard deviation from 2 to 20, where the average pattern length was 20. When the standard deviation was small, the ratio of unique patterns was high. As the standard deviation increased, the ratio of unique patterns decreased slightly. However, the ratio of unique patterns was over 86% when the standard deviation was 20. Considering the experimental data for the pattern uniqueness, it was expected that the ratio of unique patterns can be high in a general rule set, which can reduce the memory requirements with the proposed scheme.


A memory-efficient deterministic finite automaton-based bit-split string matching scheme using pattern uniqueness in deep packet inspection.

Kim H, Choi KI, Choi SI - PLoS ONE (2015)

Ratio of unique patterns by sweeping the average pattern length.
© Copyright Policy
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC4418843&req=5

pone.0126517.g010: Ratio of unique patterns by sweeping the average pattern length.
Mentions: Firstly, the average pattern length was swept from 10 to 60 with several generated rule sets, where each rule set had 10,000 different patterns. Fig 10 shows the ratio of unique patterns by sweeping the average pattern length, where the average pattern length was denoted as mean. As shown in Fig 10, the ratio of unique patterns was 70.6% when mean was 10. When mean was 60, the ratio of unique patterns reached up to 96.3%. Therefore, as mean increased, the ratio of unique patterns increased. In addition, even though the average pattern length was short, the ratio of unique patterns was over 70%, which means that the proposed string matching scheme can utilize the pattern uniqueness to reduce the memory requirements without the PMV table. Fig 11 shows the ratio of unique patterns by sweeping the number of generated patterns from 1,000 to 32,000. In this case, it was assumed that the average pattern length was 20. As the number of patterns in a rule set increased, the ratio of unique patterns decreased slightly. In addition, 86% percent of patterns were in the set of unique patterns when the number of patterns was 32,000. Fig 12 shows the ratio of unique patterns by sweeping the standard deviation from 2 to 20, where the average pattern length was 20. When the standard deviation was small, the ratio of unique patterns was high. As the standard deviation increased, the ratio of unique patterns decreased slightly. However, the ratio of unique patterns was over 86% when the standard deviation was 20. Considering the experimental data for the pattern uniqueness, it was expected that the ratio of unique patterns can be high in a general rule set, which can reduce the memory requirements with the proposed scheme.

Bottom Line: 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.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.

View Article: PubMed Central - PubMed

Affiliation: School of Electronics and Electrical Engineering, Dankook University, Yongin-si, Republic of Korea.

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.

No MeSH data available.