A novel parallel dual-character string matching algorithm on graphical processing units

Chung Yu Liao, Cheng Hung Lin*

*此作品的通信作者

研究成果: 書貢獻/報告類型會議論文篇章

2 引文 斯高帕斯(Scopus)

摘要

Aho-Corasick algorithm has been widely used in network intrusion detection system to inspect network packets against thousands of attack patterns. To improve the performance of network intrusion detection systems, many variations of Aho-Corasick algorithm are proposed to accelerate multiple string matching on GPUs or dedicated hardware. One of the proposed variations is to increase the number of characters that are processed per cycle. However, increasing the number of characters processed per cycle will encounter two major problems. The first problem is the input alignment problem while the second problem is the large increase of memory required for storing the state transition table. The two problems cause the multi-character approach become less feasible. In this paper, we propose a novel parallel dual-character string matching algorithm on graphical processing units. In order to solve the two major problems, the proposed algorithm presents a new state machine to solve the input alignment problem, and compresses the state transition table using perfect hashing to solve the memory explosion problem. The experimental results show that the proposed algorithm is superior to the state-of-the-art approaches in terms of performance and memory requirements.

原文英語
主出版物標題Algorithms and Architectures for Parallel Processing - 17th International Conference, ICA3PP 2017, Proceedings
編輯Shadi Ibrahim, Zheng Yan, Kim-Kwang Raymond Choo, Witold Pedrycz
發行者Springer Verlag
頁面197-210
頁數14
ISBN(列印)9783319654812
DOIs
出版狀態已發佈 - 2017 一月 1
事件17th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 2017 - Helsinki, 芬兰
持續時間: 2017 八月 212017 八月 23

出版系列

名字Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
10393 LNCS
ISSN(列印)0302-9743
ISSN(電子)1611-3349

其他

其他17th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 2017
國家/地區芬兰
城市Helsinki
期間2017/08/212017/08/23

ASJC Scopus subject areas

  • 理論電腦科學
  • 電腦科學(全部)

指紋

深入研究「A novel parallel dual-character string matching algorithm on graphical processing units」主題。共同形成了獨特的指紋。

引用此