TY - GEN
T1 - A novel parallel dual-character string matching algorithm on graphical processing units
AU - Liao, Chung Yu
AU - Lin, Cheng Hung
N1 - Publisher Copyright:
© Springer International Publishing AG 2017.
PY - 2017
Y1 - 2017
N2 - 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.
AB - 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.
KW - Aho-Corasick algorithm
KW - Graphical processing units
KW - Multiple string matching
KW - Perfect hashing
UR - http://www.scopus.com/inward/record.url?scp=85028451617&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85028451617&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-65482-9_13
DO - 10.1007/978-3-319-65482-9_13
M3 - Conference contribution
AN - SCOPUS:85028451617
SN - 9783319654812
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 197
EP - 210
BT - Algorithms and Architectures for Parallel Processing - 17th International Conference, ICA3PP 2017, Proceedings
A2 - Ibrahim, Shadi
A2 - Yan, Zheng
A2 - Choo, Kim-Kwang Raymond
A2 - Pedrycz, Witold
PB - Springer Verlag
T2 - 17th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 2017
Y2 - 21 August 2017 through 23 August 2017
ER -