Optimization of pattern matching algorithm for memory based architecture

Cheng Hung Lin, Yu Tang Tai, Shih Chieh Chang

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

9 Citations (Scopus)

Abstract

Due to the advantages of easy re-configurability and scalability, the memory-based string matching architecture is widely adopted by network intrusion detection systems (NIDS). In order to accommodate the increasing number of attack patterns and meet the throughput requirement of networks, a successful NIDS 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 total Snort string patterns, the new algorithm achieves 29% of memory reduction compared with the traditional Aho-Corasick algorithm [5]. Moreover, since our approach is orthogonal to other memory reduction approaches, we can obtain substantial gain even after applying the existing state-of-the-art algorithms. For example, after applying the bit-split algorithm [9], we can still gain an additional 22% of memory reduction.

Original languageEnglish
Title of host publicationANCS'07 - Proceedings of the 2007 ACM Symposium on Architecture for Networking and Communications
Pages11-16
Number of pages6
DOIs
Publication statusPublished - 2007 Dec 1
Event3rd ACM/IEEE Symposium on Architectures for Networking and Communications Systems, ANCS 2007 - Orlando, FL, United States
Duration: 2007 Dec 32007 Dec 4

Publication series

NameANCS'07 - Proceedings of the 2007 ACM Symposium on Architecture for Networking and Communications

Other

Other3rd ACM/IEEE Symposium on Architectures for Networking and Communications Systems, ANCS 2007
CountryUnited States
CityOrlando, FL
Period07/12/307/12/4

Fingerprint

Pattern matching
Data storage equipment
Intrusion detection
Computer hardware
Scalability
Throughput

Keywords

  • DFA
  • intrusion detection
  • pattern matching

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Hardware and Architecture
  • Electrical and Electronic Engineering

Cite this

Lin, C. H., Tai, Y. T., & Chang, S. C. (2007). Optimization of pattern matching algorithm for memory based architecture. In ANCS'07 - Proceedings of the 2007 ACM Symposium on Architecture for Networking and Communications (pp. 11-16). (ANCS'07 - Proceedings of the 2007 ACM Symposium on Architecture for Networking and Communications). https://doi.org/10.1145/1323548.1323551

Optimization of pattern matching algorithm for memory based architecture. / Lin, Cheng Hung; Tai, Yu Tang; Chang, Shih Chieh.

ANCS'07 - Proceedings of the 2007 ACM Symposium on Architecture for Networking and Communications. 2007. p. 11-16 (ANCS'07 - Proceedings of the 2007 ACM Symposium on Architecture for Networking and Communications).

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

Lin, CH, Tai, YT & Chang, SC 2007, Optimization of pattern matching algorithm for memory based architecture. in ANCS'07 - Proceedings of the 2007 ACM Symposium on Architecture for Networking and Communications. ANCS'07 - Proceedings of the 2007 ACM Symposium on Architecture for Networking and Communications, pp. 11-16, 3rd ACM/IEEE Symposium on Architectures for Networking and Communications Systems, ANCS 2007, Orlando, FL, United States, 07/12/3. https://doi.org/10.1145/1323548.1323551
Lin CH, Tai YT, Chang SC. Optimization of pattern matching algorithm for memory based architecture. In ANCS'07 - Proceedings of the 2007 ACM Symposium on Architecture for Networking and Communications. 2007. p. 11-16. (ANCS'07 - Proceedings of the 2007 ACM Symposium on Architecture for Networking and Communications). https://doi.org/10.1145/1323548.1323551
Lin, Cheng Hung ; Tai, Yu Tang ; Chang, Shih Chieh. / Optimization of pattern matching algorithm for memory based architecture. ANCS'07 - Proceedings of the 2007 ACM Symposium on Architecture for Networking and Communications. 2007. pp. 11-16 (ANCS'07 - Proceedings of the 2007 ACM Symposium on Architecture for Networking and Communications).
@inproceedings{85a6dac38ac34b1db5fe473ddc31011d,
title = "Optimization of pattern matching algorithm for memory based architecture",
abstract = "Due to the advantages of easy re-configurability and scalability, the memory-based string matching architecture is widely adopted by network intrusion detection systems (NIDS). In order to accommodate the increasing number of attack patterns and meet the throughput requirement of networks, a successful NIDS 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 total Snort string patterns, the new algorithm achieves 29{\%} of memory reduction compared with the traditional Aho-Corasick algorithm [5]. Moreover, since our approach is orthogonal to other memory reduction approaches, we can obtain substantial gain even after applying the existing state-of-the-art algorithms. For example, after applying the bit-split algorithm [9], we can still gain an additional 22{\%} of memory reduction.",
keywords = "DFA, intrusion detection, pattern matching",
author = "Lin, {Cheng Hung} and Tai, {Yu Tang} and Chang, {Shih Chieh}",
year = "2007",
month = "12",
day = "1",
doi = "10.1145/1323548.1323551",
language = "English",
isbn = "9781595939456",
series = "ANCS'07 - Proceedings of the 2007 ACM Symposium on Architecture for Networking and Communications",
pages = "11--16",
booktitle = "ANCS'07 - Proceedings of the 2007 ACM Symposium on Architecture for Networking and Communications",

}

TY - GEN

T1 - Optimization of pattern matching algorithm for memory based architecture

AU - Lin, Cheng Hung

AU - Tai, Yu Tang

AU - Chang, Shih Chieh

PY - 2007/12/1

Y1 - 2007/12/1

N2 - Due to the advantages of easy re-configurability and scalability, the memory-based string matching architecture is widely adopted by network intrusion detection systems (NIDS). In order to accommodate the increasing number of attack patterns and meet the throughput requirement of networks, a successful NIDS 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 total Snort string patterns, the new algorithm achieves 29% of memory reduction compared with the traditional Aho-Corasick algorithm [5]. Moreover, since our approach is orthogonal to other memory reduction approaches, we can obtain substantial gain even after applying the existing state-of-the-art algorithms. For example, after applying the bit-split algorithm [9], we can still gain an additional 22% of memory reduction.

AB - Due to the advantages of easy re-configurability and scalability, the memory-based string matching architecture is widely adopted by network intrusion detection systems (NIDS). In order to accommodate the increasing number of attack patterns and meet the throughput requirement of networks, a successful NIDS 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 total Snort string patterns, the new algorithm achieves 29% of memory reduction compared with the traditional Aho-Corasick algorithm [5]. Moreover, since our approach is orthogonal to other memory reduction approaches, we can obtain substantial gain even after applying the existing state-of-the-art algorithms. For example, after applying the bit-split algorithm [9], we can still gain an additional 22% of memory reduction.

KW - DFA

KW - intrusion detection

KW - pattern matching

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

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

U2 - 10.1145/1323548.1323551

DO - 10.1145/1323548.1323551

M3 - Conference contribution

AN - SCOPUS:70349728018

SN - 9781595939456

T3 - ANCS'07 - Proceedings of the 2007 ACM Symposium on Architecture for Networking and Communications

SP - 11

EP - 16

BT - ANCS'07 - Proceedings of the 2007 ACM Symposium on Architecture for Networking and Communications

ER -