Efficient pattern matching algorithm for memory architecture

Cheng-Hung Lin, Shih Chieh Chang

Research output: Contribution to journalArticle

19 Citations (Scopus)

Abstract

Network intrusion detection system is used to inspect packet contents against thousands of predefined malicious or suspicious patterns. Because traditional software alone pattern matching approaches can no longer meet the high throughput of today's networking, many hardware approaches are proposed to accelerate pattern matching. Among hardware approaches, memory-based architecture has attracted a lot of attention because of its easy reconfigurability and scalability. In order to accommodate the increasing number of attack patterns and meet the throughput requirement of networks, a successful network intrusion detection system must have a memory-efficient pattern-matching algorithm and hardware design. In this paper, we propose a memory-efficient pattern-matching algorithm which can significantly reduce the memory requirement. For Snort rule sets, the new algorithm achieves 21% of memory reduction compared with the traditional AhoCorasick algorithm. In addition, we can gain 24% of memory reduction by integrating our approach to the bit-split algorithm which is the state-of-the-art memory-based approach.

Original languageEnglish
Article number5272427
Pages (from-to)33-41
Number of pages9
JournalIEEE Transactions on Very Large Scale Integration (VLSI) Systems
Volume19
Issue number1
DOIs
Publication statusPublished - 2011 Jan 1

Fingerprint

Memory architecture
Pattern matching
Data storage equipment
Intrusion detection
Computer hardware
Throughput
Scalability
Hardware

Keywords

  • AhoCorasick (AC) algorithm
  • finite automata
  • pattern matching

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Electrical and Electronic Engineering

Cite this

Efficient pattern matching algorithm for memory architecture. / Lin, Cheng-Hung; Chang, Shih Chieh.

In: IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 19, No. 1, 5272427, 01.01.2011, p. 33-41.

Research output: Contribution to journalArticle

@article{7e679a4d28f04857ba9b39ea5994bcf2,
title = "Efficient pattern matching algorithm for memory architecture",
abstract = "Network intrusion detection system is used to inspect packet contents against thousands of predefined malicious or suspicious patterns. Because traditional software alone pattern matching approaches can no longer meet the high throughput of today's networking, many hardware approaches are proposed to accelerate pattern matching. Among hardware approaches, memory-based architecture has attracted a lot of attention because of its easy reconfigurability and scalability. In order to accommodate the increasing number of attack patterns and meet the throughput requirement of networks, a successful network intrusion detection system must have a memory-efficient pattern-matching algorithm and hardware design. In this paper, we propose a memory-efficient pattern-matching algorithm which can significantly reduce the memory requirement. For Snort rule sets, the new algorithm achieves 21{\%} of memory reduction compared with the traditional AhoCorasick algorithm. In addition, we can gain 24{\%} of memory reduction by integrating our approach to the bit-split algorithm which is the state-of-the-art memory-based approach.",
keywords = "AhoCorasick (AC) algorithm, finite automata, pattern matching",
author = "Cheng-Hung Lin and Chang, {Shih Chieh}",
year = "2011",
month = "1",
day = "1",
doi = "10.1109/TVLSI.2009.2028346",
language = "English",
volume = "19",
pages = "33--41",
journal = "IEEE Transactions on Very Large Scale Integration (VLSI) Systems",
issn = "1063-8210",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "1",

}

TY - JOUR

T1 - Efficient pattern matching algorithm for memory architecture

AU - Lin, Cheng-Hung

AU - Chang, Shih Chieh

PY - 2011/1/1

Y1 - 2011/1/1

N2 - Network intrusion detection system is used to inspect packet contents against thousands of predefined malicious or suspicious patterns. Because traditional software alone pattern matching approaches can no longer meet the high throughput of today's networking, many hardware approaches are proposed to accelerate pattern matching. Among hardware approaches, memory-based architecture has attracted a lot of attention because of its easy reconfigurability and scalability. In order to accommodate the increasing number of attack patterns and meet the throughput requirement of networks, a successful network intrusion detection system must have a memory-efficient pattern-matching algorithm and hardware design. In this paper, we propose a memory-efficient pattern-matching algorithm which can significantly reduce the memory requirement. For Snort rule sets, the new algorithm achieves 21% of memory reduction compared with the traditional AhoCorasick algorithm. In addition, we can gain 24% of memory reduction by integrating our approach to the bit-split algorithm which is the state-of-the-art memory-based approach.

AB - Network intrusion detection system is used to inspect packet contents against thousands of predefined malicious or suspicious patterns. Because traditional software alone pattern matching approaches can no longer meet the high throughput of today's networking, many hardware approaches are proposed to accelerate pattern matching. Among hardware approaches, memory-based architecture has attracted a lot of attention because of its easy reconfigurability and scalability. In order to accommodate the increasing number of attack patterns and meet the throughput requirement of networks, a successful network intrusion detection system must have a memory-efficient pattern-matching algorithm and hardware design. In this paper, we propose a memory-efficient pattern-matching algorithm which can significantly reduce the memory requirement. For Snort rule sets, the new algorithm achieves 21% of memory reduction compared with the traditional AhoCorasick algorithm. In addition, we can gain 24% of memory reduction by integrating our approach to the bit-split algorithm which is the state-of-the-art memory-based approach.

KW - AhoCorasick (AC) algorithm

KW - finite automata

KW - pattern matching

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

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

U2 - 10.1109/TVLSI.2009.2028346

DO - 10.1109/TVLSI.2009.2028346

M3 - Article

AN - SCOPUS:78650922894

VL - 19

SP - 33

EP - 41

JO - IEEE Transactions on Very Large Scale Integration (VLSI) Systems

JF - IEEE Transactions on Very Large Scale Integration (VLSI) Systems

SN - 1063-8210

IS - 1

M1 - 5272427

ER -