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

Chung Yu Liao, Cheng Hung Lin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationAlgorithms and Architectures for Parallel Processing - 17th International Conference, ICA3PP 2017, Proceedings
EditorsShadi Ibrahim, Zheng Yan, Kim-Kwang Raymond Choo, Witold Pedrycz
PublisherSpringer Verlag
Pages197-210
Number of pages14
ISBN (Print)9783319654812
DOIs
Publication statusPublished - 2017 Jan 1
Event17th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 2017 - Helsinki, Finland
Duration: 2017 Aug 212017 Aug 23

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10393 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other17th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 2017
CountryFinland
CityHelsinki
Period17/8/2117/8/23

    Fingerprint

Keywords

  • Aho-Corasick algorithm
  • Graphical processing units
  • Multiple string matching
  • Perfect hashing

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Liao, C. Y., & Lin, C. H. (2017). A novel parallel dual-character string matching algorithm on graphical processing units. In S. Ibrahim, Z. Yan, K-K. R. Choo, & W. Pedrycz (Eds.), Algorithms and Architectures for Parallel Processing - 17th International Conference, ICA3PP 2017, Proceedings (pp. 197-210). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10393 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-65482-9_13