Accelerating regular expression matching using hierarchical parallel machines on GPU

Cheng Hung Lin, Chen Hsiung Liu, Shih Chieh Chang

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

15 Citations (Scopus)

Abstract

Due to the conciseness and flexibility, regular expressions have been widely adopted in Network Intrusion Detection Systems to represent network attack patterns. However, the expressive power of regular expressions accompanies the intensive computation and memory consumption which leads to severe performance degradation. Recently, graphics processing units have been adopted to accelerate exact string pattern due to their cost-effective and enormous power for massive data parallel computing. Nevertheless, so far as the authors are aware, no previous work can deal with several complex regular expressions which have been commonly used in current NIDSs and been proven to have the problem of state explosion. In order to accelerate regular expression matching and resolve the problem of state explosion, we propose a GPU-based approach which applies hierarchical parallel machines to fast recognize suspicious packets which have regular expression patterns. The experimental results show that the proposed machine achieves up to 117 Gbps and 81 Gbps in processing simple and complex regular expressions, respectively. The experimental results demonstrate that the proposed parallel approach not only resolves the problem of state explosion, but also achieves much more acceleration on both simple and complex regular expressions than other GPU approaches.

Original languageEnglish
Title of host publication2011 IEEE Global Telecommunications Conference, GLOBECOM 2011
DOIs
Publication statusPublished - 2011 Dec 1
Event54th Annual IEEE Global Telecommunications Conference: "Energizing Global Communications", GLOBECOM 2011 - Houston, TX, United States
Duration: 2011 Dec 52011 Dec 9

Publication series

NameGLOBECOM - IEEE Global Telecommunications Conference

Other

Other54th Annual IEEE Global Telecommunications Conference: "Energizing Global Communications", GLOBECOM 2011
CountryUnited States
CityHouston, TX
Period11/12/511/12/9

Fingerprint

Explosions
Intrusion detection
Parallel processing systems
Data storage equipment
Degradation
Processing
Graphics processing unit
Costs

Keywords

  • graphics processing units
  • pattern matching
  • regular expression

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Cite this

Lin, C. H., Liu, C. H., & Chang, S. C. (2011). Accelerating regular expression matching using hierarchical parallel machines on GPU. In 2011 IEEE Global Telecommunications Conference, GLOBECOM 2011 [6133663] (GLOBECOM - IEEE Global Telecommunications Conference). https://doi.org/10.1109/GLOCOM.2011.6133663

Accelerating regular expression matching using hierarchical parallel machines on GPU. / Lin, Cheng Hung; Liu, Chen Hsiung; Chang, Shih Chieh.

2011 IEEE Global Telecommunications Conference, GLOBECOM 2011. 2011. 6133663 (GLOBECOM - IEEE Global Telecommunications Conference).

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

Lin, CH, Liu, CH & Chang, SC 2011, Accelerating regular expression matching using hierarchical parallel machines on GPU. in 2011 IEEE Global Telecommunications Conference, GLOBECOM 2011., 6133663, GLOBECOM - IEEE Global Telecommunications Conference, 54th Annual IEEE Global Telecommunications Conference: "Energizing Global Communications", GLOBECOM 2011, Houston, TX, United States, 11/12/5. https://doi.org/10.1109/GLOCOM.2011.6133663
Lin CH, Liu CH, Chang SC. Accelerating regular expression matching using hierarchical parallel machines on GPU. In 2011 IEEE Global Telecommunications Conference, GLOBECOM 2011. 2011. 6133663. (GLOBECOM - IEEE Global Telecommunications Conference). https://doi.org/10.1109/GLOCOM.2011.6133663
Lin, Cheng Hung ; Liu, Chen Hsiung ; Chang, Shih Chieh. / Accelerating regular expression matching using hierarchical parallel machines on GPU. 2011 IEEE Global Telecommunications Conference, GLOBECOM 2011. 2011. (GLOBECOM - IEEE Global Telecommunications Conference).
@inproceedings{92424e90c485447aa2bd8962cb9af662,
title = "Accelerating regular expression matching using hierarchical parallel machines on GPU",
abstract = "Due to the conciseness and flexibility, regular expressions have been widely adopted in Network Intrusion Detection Systems to represent network attack patterns. However, the expressive power of regular expressions accompanies the intensive computation and memory consumption which leads to severe performance degradation. Recently, graphics processing units have been adopted to accelerate exact string pattern due to their cost-effective and enormous power for massive data parallel computing. Nevertheless, so far as the authors are aware, no previous work can deal with several complex regular expressions which have been commonly used in current NIDSs and been proven to have the problem of state explosion. In order to accelerate regular expression matching and resolve the problem of state explosion, we propose a GPU-based approach which applies hierarchical parallel machines to fast recognize suspicious packets which have regular expression patterns. The experimental results show that the proposed machine achieves up to 117 Gbps and 81 Gbps in processing simple and complex regular expressions, respectively. The experimental results demonstrate that the proposed parallel approach not only resolves the problem of state explosion, but also achieves much more acceleration on both simple and complex regular expressions than other GPU approaches.",
keywords = "graphics processing units, pattern matching, regular expression",
author = "Lin, {Cheng Hung} and Liu, {Chen Hsiung} and Chang, {Shih Chieh}",
year = "2011",
month = "12",
day = "1",
doi = "10.1109/GLOCOM.2011.6133663",
language = "English",
isbn = "9781424492688",
series = "GLOBECOM - IEEE Global Telecommunications Conference",
booktitle = "2011 IEEE Global Telecommunications Conference, GLOBECOM 2011",

}

TY - GEN

T1 - Accelerating regular expression matching using hierarchical parallel machines on GPU

AU - Lin, Cheng Hung

AU - Liu, Chen Hsiung

AU - Chang, Shih Chieh

PY - 2011/12/1

Y1 - 2011/12/1

N2 - Due to the conciseness and flexibility, regular expressions have been widely adopted in Network Intrusion Detection Systems to represent network attack patterns. However, the expressive power of regular expressions accompanies the intensive computation and memory consumption which leads to severe performance degradation. Recently, graphics processing units have been adopted to accelerate exact string pattern due to their cost-effective and enormous power for massive data parallel computing. Nevertheless, so far as the authors are aware, no previous work can deal with several complex regular expressions which have been commonly used in current NIDSs and been proven to have the problem of state explosion. In order to accelerate regular expression matching and resolve the problem of state explosion, we propose a GPU-based approach which applies hierarchical parallel machines to fast recognize suspicious packets which have regular expression patterns. The experimental results show that the proposed machine achieves up to 117 Gbps and 81 Gbps in processing simple and complex regular expressions, respectively. The experimental results demonstrate that the proposed parallel approach not only resolves the problem of state explosion, but also achieves much more acceleration on both simple and complex regular expressions than other GPU approaches.

AB - Due to the conciseness and flexibility, regular expressions have been widely adopted in Network Intrusion Detection Systems to represent network attack patterns. However, the expressive power of regular expressions accompanies the intensive computation and memory consumption which leads to severe performance degradation. Recently, graphics processing units have been adopted to accelerate exact string pattern due to their cost-effective and enormous power for massive data parallel computing. Nevertheless, so far as the authors are aware, no previous work can deal with several complex regular expressions which have been commonly used in current NIDSs and been proven to have the problem of state explosion. In order to accelerate regular expression matching and resolve the problem of state explosion, we propose a GPU-based approach which applies hierarchical parallel machines to fast recognize suspicious packets which have regular expression patterns. The experimental results show that the proposed machine achieves up to 117 Gbps and 81 Gbps in processing simple and complex regular expressions, respectively. The experimental results demonstrate that the proposed parallel approach not only resolves the problem of state explosion, but also achieves much more acceleration on both simple and complex regular expressions than other GPU approaches.

KW - graphics processing units

KW - pattern matching

KW - regular expression

UR - http://www.scopus.com/inward/record.url?scp=84863158654&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84863158654&partnerID=8YFLogxK

U2 - 10.1109/GLOCOM.2011.6133663

DO - 10.1109/GLOCOM.2011.6133663

M3 - Conference contribution

AN - SCOPUS:84863158654

SN - 9781424492688

T3 - GLOBECOM - IEEE Global Telecommunications Conference

BT - 2011 IEEE Global Telecommunications Conference, GLOBECOM 2011

ER -