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

String searching algorithms
String Algorithms
String Matching
Matching Algorithm
Unit
Intrusion detection
Processing
Data storage equipment
Network Intrusion Detection
Packet networks
State Transition
Explosions
Table
Alignment
Hardware
Cycle
Graphics
Character
Hashing
State Machine

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

A novel parallel dual-character string matching algorithm on graphical processing units. / Liao, Chung Yu; Lin, Cheng Hung.

Algorithms and Architectures for Parallel Processing - 17th International Conference, ICA3PP 2017, Proceedings. ed. / Shadi Ibrahim; Zheng Yan; Kim-Kwang Raymond Choo; Witold Pedrycz. Springer Verlag, 2017. p. 197-210 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10393 LNCS).

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

Liao, CY & Lin, CH 2017, A novel parallel dual-character string matching algorithm on graphical processing units. in S Ibrahim, Z Yan, K-KR Choo & W Pedrycz (eds), Algorithms and Architectures for Parallel Processing - 17th International Conference, ICA3PP 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10393 LNCS, Springer Verlag, pp. 197-210, 17th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 2017, Helsinki, Finland, 17/8/21. https://doi.org/10.1007/978-3-319-65482-9_13
Liao CY, Lin CH. A novel parallel dual-character string matching algorithm on graphical processing units. In Ibrahim S, Yan Z, Choo K-KR, Pedrycz W, editors, Algorithms and Architectures for Parallel Processing - 17th International Conference, ICA3PP 2017, Proceedings. Springer Verlag. 2017. p. 197-210. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-65482-9_13
Liao, Chung Yu ; Lin, Cheng Hung. / A novel parallel dual-character string matching algorithm on graphical processing units. Algorithms and Architectures for Parallel Processing - 17th International Conference, ICA3PP 2017, Proceedings. editor / Shadi Ibrahim ; Zheng Yan ; Kim-Kwang Raymond Choo ; Witold Pedrycz. Springer Verlag, 2017. pp. 197-210 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{08e0993e45e6439c8b8ed992008a978f,
title = "A novel parallel dual-character string matching algorithm on graphical processing units",
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.",
keywords = "Aho-Corasick algorithm, Graphical processing units, Multiple string matching, Perfect hashing",
author = "Liao, {Chung Yu} and Lin, {Cheng Hung}",
year = "2017",
month = "1",
day = "1",
doi = "10.1007/978-3-319-65482-9_13",
language = "English",
isbn = "9783319654812",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "197--210",
editor = "Shadi Ibrahim and Zheng Yan and Choo, {Kim-Kwang Raymond} and Witold Pedrycz",
booktitle = "Algorithms and Architectures for Parallel Processing - 17th International Conference, ICA3PP 2017, Proceedings",

}

TY - GEN

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

AU - Liao, Chung Yu

AU - Lin, Cheng Hung

PY - 2017/1/1

Y1 - 2017/1/1

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

ER -