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
Padanan berbilang corak ialah teknik utama untuk melaksanakan aplikasi keselamatan rangkaian seperti Sistem Pengesanan/Perlindungan Pencerobohan Rangkaian (NIDS/NIPSes) di mana setiap paket diperiksa terhadap puluhan ribu tandatangan serangan yang dipratentukan yang ditulis dalam ungkapan biasa (regeks). Untuk tujuan ini, Deterministic Finite Automaton (DFA) digunakan secara meluas untuk pemadanan berbilang regex, tetapi penyelidikan berasaskan DFA sedia ada telah menuntut daya pemprosesan yang tinggi dengan mengorbankan kos memori yang sangat tinggi, jadi gagal digunakan dalam peranti seperti kelajuan tinggi penghala dan sistem terbenam di mana memori yang tersedia agak terhad. Dalam makalah ini, kami mencadangkan seni bina selari DFA yang dipanggil DFA Selari (PDFA) yang mengambil kesempatan daripada jumlah besar aliran serentak untuk meningkatkan daya pengeluaran tanpa kos memori tambahan. Idea asas adalah untuk menyimpan DFA asas secara selektif dalam modul memori yang boleh diakses secara selari. Untuk meneroka keselarian potensinya, kami mengkaji secara intensif skim pemisahan DFA dari kedua-dua keadaan dan titik peralihan dalam kertas ini. Prestasi pendekatan kami dalam kedua-dua kes purata dan kes terburuk dianalisis, dioptimumkan dan dinilai oleh keputusan berangka. Penilaian menunjukkan bahawa kami memperoleh purata kelajuan 100 kali berbanding dengan pendekatan pemadanan berasaskan DFA tradisional.
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.
Salinan
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
Salinan
@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},}
Salinan
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 -