Hierarchical state machine architecture for regular expression pattern matching

Research output: Chapter in Book/Report/Conference proceedingConference 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 languageEnglish
Title of host publicationGLSVLSI 2009 - Proceedings of the 2009 Great Lakes Symposium on VLSI
Pages133-136
Number of pages4
DOIs
Publication statusPublished - 2009 Nov 6
Event19th ACM Great Lakes Symposium on VLSI, GLSVLSI '09 - Boston, MA, United States
Duration: 2009 May 102009 May 12

Publication series

NameProceedings of the ACM Great Lakes Symposium on VLSI, GLSVLSI

Other

Other19th ACM Great Lakes Symposium on VLSI, GLSVLSI '09
CountryUnited States
CityBoston, MA
Period09/5/1009/5/12

Fingerprint

Pattern matching
Intrusion detection
Data storage equipment
Memory architecture
Explosions
Experiments

Keywords

  • Pattern matching
  • Regular expression
  • State machine

ASJC Scopus subject areas

  • Engineering(all)

Cite this

Lin, C. H., & Hsiao, H. S. (2009). Hierarchical state machine architecture for regular expression pattern matching. In GLSVLSI 2009 - Proceedings of the 2009 Great Lakes Symposium on VLSI (pp. 133-136). (Proceedings of the ACM Great Lakes Symposium on VLSI, GLSVLSI). https://doi.org/10.1145/1531542.1531576

Hierarchical state machine architecture for regular expression pattern matching. / Lin, Cheng Hung; Hsiao, Hsien Sheng.

GLSVLSI 2009 - Proceedings of the 2009 Great Lakes Symposium on VLSI. 2009. p. 133-136 (Proceedings of the ACM Great Lakes Symposium on VLSI, GLSVLSI).

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

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, 09/5/10. https://doi.org/10.1145/1531542.1531576
Lin CH, Hsiao HS. Hierarchical state machine architecture for regular expression pattern matching. In GLSVLSI 2009 - Proceedings of the 2009 Great Lakes Symposium on VLSI. 2009. p. 133-136. (Proceedings of the ACM Great Lakes Symposium on VLSI, GLSVLSI). https://doi.org/10.1145/1531542.1531576
Lin, Cheng Hung ; Hsiao, Hsien Sheng. / Hierarchical state machine architecture for regular expression pattern matching. GLSVLSI 2009 - Proceedings of the 2009 Great Lakes Symposium on VLSI. 2009. pp. 133-136 (Proceedings of the ACM Great Lakes Symposium on VLSI, GLSVLSI).
@inproceedings{9afcf71caa1f41d8adb0165837f827d0,
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",
month = "11",
day = "6",
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",

}

TY - GEN

T1 - Hierarchical state machine architecture for regular expression pattern matching

AU - Lin, Cheng Hung

AU - Hsiao, Hsien Sheng

PY - 2009/11/6

Y1 - 2009/11/6

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

ER -