A Memory Efficient Pattern Matching Scheme for Regular Expressions

Yeim-Kuan Chang, Ching Hsuan Shih

Research output: Contribution to journalConference article

1 Citation (Scopus)

Abstract

Many malicious packets are common and spread over the Internet in recent years when the scale of Internet traffic grows at a rapid speed. Thus, the regular expression matching in Network Intrusion Detection System (NIDS) that supervises network activities needs to be very fast and consume small memory. In this paper, we propose a memory efficient regular expression matching algorithm called Failureless Segmented Finite Automata (FSFA) with an acceptable searching speed. In FSFA, We eliminate Kleene closures by using additional data structures to reduce a large amount of states. We further reduce the transitions by using default state compression technique. Our performance results implemented on a PC software environment show that our scheme only needs 1% of states needed in DFA and 2 to 22% of states needed in JFA.

Original languageEnglish
Pages (from-to)250-257
Number of pages8
JournalProcedia Computer Science
Volume110
DOIs
Publication statusPublished - 2017 Jan 1
Event14th International Conference on Mobile Systems and Pervasive Computing, MobiSPC 2017 - Leuven, Belgium
Duration: 2017 Jul 242017 Jul 26

Fingerprint

Pattern matching
Finite automata
Internet
Data storage equipment
Intrusion detection
Data structures

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Cite this

@article{4dc5aa5f6d814f508a461723483b67c0,
title = "A Memory Efficient Pattern Matching Scheme for Regular Expressions",
abstract = "Many malicious packets are common and spread over the Internet in recent years when the scale of Internet traffic grows at a rapid speed. Thus, the regular expression matching in Network Intrusion Detection System (NIDS) that supervises network activities needs to be very fast and consume small memory. In this paper, we propose a memory efficient regular expression matching algorithm called Failureless Segmented Finite Automata (FSFA) with an acceptable searching speed. In FSFA, We eliminate Kleene closures by using additional data structures to reduce a large amount of states. We further reduce the transitions by using default state compression technique. Our performance results implemented on a PC software environment show that our scheme only needs 1{\%} of states needed in DFA and 2 to 22{\%} of states needed in JFA.",
author = "Yeim-Kuan Chang and Shih, {Ching Hsuan}",
year = "2017",
month = "1",
day = "1",
doi = "10.1016/j.procs.2017.06.092",
language = "English",
volume = "110",
pages = "250--257",
journal = "Procedia Computer Science",
issn = "1877-0509",
publisher = "Elsevier BV",

}

A Memory Efficient Pattern Matching Scheme for Regular Expressions. / Chang, Yeim-Kuan; Shih, Ching Hsuan.

In: Procedia Computer Science, Vol. 110, 01.01.2017, p. 250-257.

Research output: Contribution to journalConference article

TY - JOUR

T1 - A Memory Efficient Pattern Matching Scheme for Regular Expressions

AU - Chang, Yeim-Kuan

AU - Shih, Ching Hsuan

PY - 2017/1/1

Y1 - 2017/1/1

N2 - Many malicious packets are common and spread over the Internet in recent years when the scale of Internet traffic grows at a rapid speed. Thus, the regular expression matching in Network Intrusion Detection System (NIDS) that supervises network activities needs to be very fast and consume small memory. In this paper, we propose a memory efficient regular expression matching algorithm called Failureless Segmented Finite Automata (FSFA) with an acceptable searching speed. In FSFA, We eliminate Kleene closures by using additional data structures to reduce a large amount of states. We further reduce the transitions by using default state compression technique. Our performance results implemented on a PC software environment show that our scheme only needs 1% of states needed in DFA and 2 to 22% of states needed in JFA.

AB - Many malicious packets are common and spread over the Internet in recent years when the scale of Internet traffic grows at a rapid speed. Thus, the regular expression matching in Network Intrusion Detection System (NIDS) that supervises network activities needs to be very fast and consume small memory. In this paper, we propose a memory efficient regular expression matching algorithm called Failureless Segmented Finite Automata (FSFA) with an acceptable searching speed. In FSFA, We eliminate Kleene closures by using additional data structures to reduce a large amount of states. We further reduce the transitions by using default state compression technique. Our performance results implemented on a PC software environment show that our scheme only needs 1% of states needed in DFA and 2 to 22% of states needed in JFA.

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

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

U2 - 10.1016/j.procs.2017.06.092

DO - 10.1016/j.procs.2017.06.092

M3 - Conference article

AN - SCOPUS:85028629886

VL - 110

SP - 250

EP - 257

JO - Procedia Computer Science

JF - Procedia Computer Science

SN - 1877-0509

ER -