The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
다중 패턴 일치는 정규식(regexes)으로 작성된 수만 개의 사전 정의된 공격 서명에 대해 모든 패킷을 검사하는 네트워크 침입 감지/보호 시스템(NIDS/NIPSes)과 같은 네트워크 보안 애플리케이션을 구현하기 위한 핵심 기술입니다. 이를 위해 다중 정규식 매칭에는 DFA(Deterministic Finite Automaton)가 널리 사용되지만, 기존 DFA 기반 연구에서는 극도로 높은 메모리 비용을 대가로 높은 처리량을 주장해 고속 등의 장치에는 적용하지 못했다. 사용 가능한 메모리가 상당히 제한된 라우터 및 임베디드 시스템. 본 논문에서는 추가 메모리 비용이 거의 없이 처리량을 높이기 위해 대량의 동시 흐름을 활용하는 PDFA(Parallel DFA)라는 DFA 병렬 아키텍처를 제안합니다. 기본 아이디어는 병렬로 액세스할 수 있는 메모리 모듈에 기본 DFA를 선택적으로 저장하는 것입니다. 잠재적인 병렬성을 탐색하기 위해 이 문서에서는 상태 및 전환 지점 모두에서 DFA 분할 방식을 집중적으로 연구합니다. 평균 사례와 최악 사례 모두에서 우리 접근 방식의 성능은 수치 결과를 통해 분석, 최적화 및 평가됩니다. 평가 결과, 기존 DFA 기반 매칭 접근 방식에 비해 평균 100배의 속도 향상을 얻은 것으로 나타났습니다.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
부
Yi TANG, Junchen JIANG, Xiaofei WANG, Chengchen HU, Bin LIU, Zhijia CHEN, "Parallel DFA Architecture for Ultra High Throughput DFA-Based Pattern Matching" in IEICE TRANSACTIONS on Information,
vol. E93-D, no. 12, pp. 3232-3242, December 2010, doi: 10.1587/transinf.E93.D.3232.
Abstract: Multi-pattern matching is a key technique for implementing network security applications such as Network Intrusion Detection/Protection Systems (NIDS/NIPSes) where every packet is inspected against tens of thousands of predefined attack signatures written in regular expressions (regexes). To this end, Deterministic Finite Automaton (DFA) is widely used for multi-regex matching, but existing DFA-based researches have claimed high throughput at an expense of extremely high memory cost, so fail to be employed in devices such as high-speed routers and embedded systems where the available memory is quite limited. In this paper, we propose a parallel architecture of DFA called Parallel DFA (PDFA) taking advantage of the large amount of concurrent flows to increase the throughput with nearly no extra memory cost. The basic idea is to selectively store the underlying DFA in memory modules that can be accessed in parallel. To explore its potential parallelism we intensively study DFA-split schemes from both state and transition points in this paper. The performance of our approach in both the average cases and the worst cases is analyzed, optimized and evaluated by numerical results. The evaluation shows that we obtain an average speedup of 100 times compared with traditional DFA-based matching approach.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E93.D.3232/_p
부
@ARTICLE{e93-d_12_3232,
author={Yi TANG, Junchen JIANG, Xiaofei WANG, Chengchen HU, Bin LIU, Zhijia CHEN, },
journal={IEICE TRANSACTIONS on Information},
title={Parallel DFA Architecture for Ultra High Throughput DFA-Based Pattern Matching},
year={2010},
volume={E93-D},
number={12},
pages={3232-3242},
abstract={Multi-pattern matching is a key technique for implementing network security applications such as Network Intrusion Detection/Protection Systems (NIDS/NIPSes) where every packet is inspected against tens of thousands of predefined attack signatures written in regular expressions (regexes). To this end, Deterministic Finite Automaton (DFA) is widely used for multi-regex matching, but existing DFA-based researches have claimed high throughput at an expense of extremely high memory cost, so fail to be employed in devices such as high-speed routers and embedded systems where the available memory is quite limited. In this paper, we propose a parallel architecture of DFA called Parallel DFA (PDFA) taking advantage of the large amount of concurrent flows to increase the throughput with nearly no extra memory cost. The basic idea is to selectively store the underlying DFA in memory modules that can be accessed in parallel. To explore its potential parallelism we intensively study DFA-split schemes from both state and transition points in this paper. The performance of our approach in both the average cases and the worst cases is analyzed, optimized and evaluated by numerical results. The evaluation shows that we obtain an average speedup of 100 times compared with traditional DFA-based matching approach.},
keywords={},
doi={10.1587/transinf.E93.D.3232},
ISSN={1745-1361},
month={December},}
부
TY - JOUR
TI - Parallel DFA Architecture for Ultra High Throughput DFA-Based Pattern Matching
T2 - IEICE TRANSACTIONS on Information
SP - 3232
EP - 3242
AU - Yi TANG
AU - Junchen JIANG
AU - Xiaofei WANG
AU - Chengchen HU
AU - Bin LIU
AU - Zhijia CHEN
PY - 2010
DO - 10.1587/transinf.E93.D.3232
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E93-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 2010
AB - Multi-pattern matching is a key technique for implementing network security applications such as Network Intrusion Detection/Protection Systems (NIDS/NIPSes) where every packet is inspected against tens of thousands of predefined attack signatures written in regular expressions (regexes). To this end, Deterministic Finite Automaton (DFA) is widely used for multi-regex matching, but existing DFA-based researches have claimed high throughput at an expense of extremely high memory cost, so fail to be employed in devices such as high-speed routers and embedded systems where the available memory is quite limited. In this paper, we propose a parallel architecture of DFA called Parallel DFA (PDFA) taking advantage of the large amount of concurrent flows to increase the throughput with nearly no extra memory cost. The basic idea is to selectively store the underlying DFA in memory modules that can be accessed in parallel. To explore its potential parallelism we intensively study DFA-split schemes from both state and transition points in this paper. The performance of our approach in both the average cases and the worst cases is analyzed, optimized and evaluated by numerical results. The evaluation shows that we obtain an average speedup of 100 times compared with traditional DFA-based matching approach.
ER -