Memory-efficient pattern matching architectures using perfect hashing on graphic processing units

Cheng Hung Lin*, Chen Hsiung Liu, Shih Chieh Chang, Wing Kai Hon

*Corresponding author for this work

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

14 Citations (Scopus)


Memory architectures have been widely adopted in network intrusion detection system for inspecting malicious packets due to their flexibility and scalability. Memory architectures match input streams against thousands of attack patterns by traversing the corresponding state transition table stored in commodity memories. With the increasing number of attack patterns, reducing memory requirement has become critical for memory architectures. In this paper, we propose a novel memory architecture using perfect hashing to condense state transition tables without hash collisions. The proposed memory architecture achieves up to 99.5% improvement in memory reduction compared to the traditional two-dimensional memory architecture. We have implemented our memory architectures on graphic processing units and tested using attack patterns from Snort V2.8 and input packets form DEFCON. The experimental results show that the proposed memory architectures outperform state-of-the-art memory architectures both on performance and memory efficiency.

Original languageEnglish
Title of host publication2012 Proceedings IEEE INFOCOM, INFOCOM 2012
Number of pages9
Publication statusPublished - 2012
EventIEEE Conference on Computer Communications, INFOCOM 2012 - Orlando, FL, United States
Duration: 2012 Mar 252012 Mar 30

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X


OtherIEEE Conference on Computer Communications, INFOCOM 2012
Country/TerritoryUnited States
CityOrlando, FL


  • deterministic finite automaton
  • pattern matching
  • perfect hashing

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering


Dive into the research topics of 'Memory-efficient pattern matching architectures using perfect hashing on graphic processing units'. Together they form a unique fingerprint.

Cite this