Hierarchical state machine architecture for regular expression pattern matching

Cheng Hung Lin; Hsien Sheng Hsiao

doi:10.1145/1531542.1531576

Hierarchical state machine architecture for regular expression pattern matching

Cheng Hung Lin^*, Hsien Sheng Hsiao

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

4 Citations (Scopus)

Abstract

Regular expression has been widely used in network intrusion detection system to represent attack patterns due to its expressive power and flexibility. However, the traditional memory architecture suffers from the problem of memory explosion for certain types of complex regular expressions. In this paper, we propose a hierarchical state machine architecture which can significantly reduce the memory required to accommodate complex regular expression patterns. The experiments demonstrate a significant reduction in memory for the complex regular expression patterns commonly used in network intrusion detection systems.

Original language	English
Title of host publication	GLSVLSI 2009 - Proceedings of the 2009 Great Lakes Symposium on VLSI
Pages	133-136
Number of pages	4
DOIs	https://doi.org/10.1145/1531542.1531576
Publication status	Published - 2009
Event	19th ACM Great Lakes Symposium on VLSI, GLSVLSI '09 - Boston, MA, United States Duration: 2009 May 10 → 2009 May 12

Publication series

Name	Proceedings of the ACM Great Lakes Symposium on VLSI, GLSVLSI

Other

Other	19th ACM Great Lakes Symposium on VLSI, GLSVLSI '09
Country/Territory	United States
City	Boston, MA
Period	2009/05/10 → 2009/05/12

Keywords

Pattern matching
Regular expression
State machine

ASJC Scopus subject areas

General Engineering

Access to Document

10.1145/1531542.1531576

Cite this

Lin, CH & Hsiao, HS 2009, Hierarchical state machine architecture for regular expression pattern matching. in GLSVLSI 2009 - Proceedings of the 2009 Great Lakes Symposium on VLSI. Proceedings of the ACM Great Lakes Symposium on VLSI, GLSVLSI, pp. 133-136, 19th ACM Great Lakes Symposium on VLSI, GLSVLSI '09, Boston, MA, United States, 2009/05/10. https://doi.org/10.1145/1531542.1531576

@inproceedings{051656565d5b4b37b61c40f657a678e4,

title = "Hierarchical state machine architecture for regular expression pattern matching",

abstract = "Regular expression has been widely used in network intrusion detection system to represent attack patterns due to its expressive power and flexibility. However, the traditional memory architecture suffers from the problem of memory explosion for certain types of complex regular expressions. In this paper, we propose a hierarchical state machine architecture which can significantly reduce the memory required to accommodate complex regular expression patterns. The experiments demonstrate a significant reduction in memory for the complex regular expression patterns commonly used in network intrusion detection systems.",

keywords = "Pattern matching, Regular expression, State machine",

author = "Lin, {Cheng Hung} and Hsiao, {Hsien Sheng}",

year = "2009",

doi = "10.1145/1531542.1531576",

language = "English",

isbn = "9781605585222",

series = "Proceedings of the ACM Great Lakes Symposium on VLSI, GLSVLSI",

pages = "133--136",

booktitle = "GLSVLSI 2009 - Proceedings of the 2009 Great Lakes Symposium on VLSI",

note = "19th ACM Great Lakes Symposium on VLSI, GLSVLSI '09 ; Conference date: 10-05-2009 Through 12-05-2009",

}

TY - GEN

T1 - Hierarchical state machine architecture for regular expression pattern matching

AU - Lin, Cheng Hung

AU - Hsiao, Hsien Sheng

PY - 2009

Y1 - 2009

N2 - Regular expression has been widely used in network intrusion detection system to represent attack patterns due to its expressive power and flexibility. However, the traditional memory architecture suffers from the problem of memory explosion for certain types of complex regular expressions. In this paper, we propose a hierarchical state machine architecture which can significantly reduce the memory required to accommodate complex regular expression patterns. The experiments demonstrate a significant reduction in memory for the complex regular expression patterns commonly used in network intrusion detection systems.

AB - Regular expression has been widely used in network intrusion detection system to represent attack patterns due to its expressive power and flexibility. However, the traditional memory architecture suffers from the problem of memory explosion for certain types of complex regular expressions. In this paper, we propose a hierarchical state machine architecture which can significantly reduce the memory required to accommodate complex regular expression patterns. The experiments demonstrate a significant reduction in memory for the complex regular expression patterns commonly used in network intrusion detection systems.

KW - Pattern matching

KW - Regular expression

KW - State machine

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

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

U2 - 10.1145/1531542.1531576

DO - 10.1145/1531542.1531576

M3 - Conference contribution

AN - SCOPUS:70350590856

SN - 9781605585222

T3 - Proceedings of the ACM Great Lakes Symposium on VLSI, GLSVLSI

SP - 133

EP - 136

BT - GLSVLSI 2009 - Proceedings of the 2009 Great Lakes Symposium on VLSI

T2 - 19th ACM Great Lakes Symposium on VLSI, GLSVLSI '09

Y2 - 10 May 2009 through 12 May 2009

ER -

Hierarchical state machine architecture for regular expression pattern matching

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this