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

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

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

13 Citations (Scopus)

Abstract

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
Pages1978-1986
Number of pages9
DOIs
Publication statusPublished - 2012 Jun 4
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

Other

OtherIEEE Conference on Computer Communications, INFOCOM 2012
CountryUnited States
CityOrlando, FL
Period12/3/2512/3/30

Fingerprint

Memory architecture
Pattern matching
Data storage equipment
Graphics processing unit
Intrusion detection
Scalability

Keywords

  • deterministic finite automaton
  • pattern matching
  • perfect hashing

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering

Cite this

Lin, C. H., Liu, C. H., Chang, S. C., & Hon, W. K. (2012). Memory-efficient pattern matching architectures using perfect hashing on graphic processing units. In 2012 Proceedings IEEE INFOCOM, INFOCOM 2012 (pp. 1978-1986). [6195575] (Proceedings - IEEE INFOCOM). https://doi.org/10.1109/INFCOM.2012.6195575

Memory-efficient pattern matching architectures using perfect hashing on graphic processing units. / Lin, Cheng Hung; Liu, Chen Hsiung; Chang, Shih Chieh; Hon, Wing Kai.

2012 Proceedings IEEE INFOCOM, INFOCOM 2012. 2012. p. 1978-1986 6195575 (Proceedings - IEEE INFOCOM).

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

Lin, CH, Liu, CH, Chang, SC & Hon, WK 2012, Memory-efficient pattern matching architectures using perfect hashing on graphic processing units. in 2012 Proceedings IEEE INFOCOM, INFOCOM 2012., 6195575, Proceedings - IEEE INFOCOM, pp. 1978-1986, IEEE Conference on Computer Communications, INFOCOM 2012, Orlando, FL, United States, 12/3/25. https://doi.org/10.1109/INFCOM.2012.6195575
Lin CH, Liu CH, Chang SC, Hon WK. Memory-efficient pattern matching architectures using perfect hashing on graphic processing units. In 2012 Proceedings IEEE INFOCOM, INFOCOM 2012. 2012. p. 1978-1986. 6195575. (Proceedings - IEEE INFOCOM). https://doi.org/10.1109/INFCOM.2012.6195575
Lin, Cheng Hung ; Liu, Chen Hsiung ; Chang, Shih Chieh ; Hon, Wing Kai. / Memory-efficient pattern matching architectures using perfect hashing on graphic processing units. 2012 Proceedings IEEE INFOCOM, INFOCOM 2012. 2012. pp. 1978-1986 (Proceedings - IEEE INFOCOM).
@inproceedings{c95c60b50247418689e367bc07895d91,
title = "Memory-efficient pattern matching architectures using perfect hashing on graphic processing units",
abstract = "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.",
keywords = "deterministic finite automaton, pattern matching, perfect hashing",
author = "Lin, {Cheng Hung} and Liu, {Chen Hsiung} and Chang, {Shih Chieh} and Hon, {Wing Kai}",
year = "2012",
month = "6",
day = "4",
doi = "10.1109/INFCOM.2012.6195575",
language = "English",
isbn = "9781467307758",
series = "Proceedings - IEEE INFOCOM",
pages = "1978--1986",
booktitle = "2012 Proceedings IEEE INFOCOM, INFOCOM 2012",

}

TY - GEN

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

AU - Lin, Cheng Hung

AU - Liu, Chen Hsiung

AU - Chang, Shih Chieh

AU - Hon, Wing Kai

PY - 2012/6/4

Y1 - 2012/6/4

N2 - 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.

AB - 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.

KW - deterministic finite automaton

KW - pattern matching

KW - perfect hashing

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

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

U2 - 10.1109/INFCOM.2012.6195575

DO - 10.1109/INFCOM.2012.6195575

M3 - Conference contribution

AN - SCOPUS:84861624858

SN - 9781467307758

T3 - Proceedings - IEEE INFOCOM

SP - 1978

EP - 1986

BT - 2012 Proceedings IEEE INFOCOM, INFOCOM 2012

ER -