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

Keywords

  • graphics processing units
  • pattern matching
  • regular expression

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Accelerating regular expression matching using hierarchical parallel machines on GPU'. Together they form a unique fingerprint.

  • 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