A memory efficient DFA using compression and pattern segmentation

Yeim-Kuan Chang, Yuen Shuo Li, Yu To Chen

Research output: Contribution to journalConference article

1 Citation (Scopus)

Abstract

The role of network security systems such as network intrusion detection system (NIDS) has become more important. The regular expression (a.k.a. regex) matching algorithm used for inspecting the payloads of packets is one of the most intensive tasks in NIDS. When multiple regular expressions are processed together, the corresponding Deterministic Finite Automata (DFA) becomes so complicated and needs a large amount of memory. In this paper, we propose a memory efficient parallel compatible DFA algorithm that uses the techniques of compression and pattern segmentation to reduce the memory usage. Extended from PFAC (Parallel Failureless-AC) algorithm4, the proposed compressed and segmented DFA (CSDFA) needs less numbers of states and transitions than δFA. Without considering the leading symbols "." in the regular expressions, the transition table can be compressed very efficiently by the run-length encoding. The number of transitions in CSDFA is about a half of the transitions needed in δFA, and uses only 74% of the memory consumed by δFA. Based on our experiments, the throughput of the proposed CSDFA is also much better than δFA.

Original languageEnglish
Pages (from-to)292-299
Number of pages8
JournalProcedia Computer Science
Volume56
Issue number1
DOIs
Publication statusPublished - 2015 Jan 1
Event29th European Conference on Solid-State Transducers, EUROSENSORS 2015; Freiburg; Germany; 6 September 2015 through 9 September 2015. - Freiburg, Germany
Duration: 2015 Sep 62015 Sep 9

Fingerprint

Finite automata
Data storage equipment
Intrusion detection
Network security
Security systems
Throughput
Experiments

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Cite this

Chang, Yeim-Kuan ; Li, Yuen Shuo ; Chen, Yu To. / A memory efficient DFA using compression and pattern segmentation. In: Procedia Computer Science. 2015 ; Vol. 56, No. 1. pp. 292-299.
@article{4eac3a6f7c654a70b7fb1f36d584c099,
title = "A memory efficient DFA using compression and pattern segmentation",
abstract = "The role of network security systems such as network intrusion detection system (NIDS) has become more important. The regular expression (a.k.a. regex) matching algorithm used for inspecting the payloads of packets is one of the most intensive tasks in NIDS. When multiple regular expressions are processed together, the corresponding Deterministic Finite Automata (DFA) becomes so complicated and needs a large amount of memory. In this paper, we propose a memory efficient parallel compatible DFA algorithm that uses the techniques of compression and pattern segmentation to reduce the memory usage. Extended from PFAC (Parallel Failureless-AC) algorithm4, the proposed compressed and segmented DFA (CSDFA) needs less numbers of states and transitions than δFA. Without considering the leading symbols {"}.∗{"} in the regular expressions, the transition table can be compressed very efficiently by the run-length encoding. The number of transitions in CSDFA is about a half of the transitions needed in δFA, and uses only 74{\%} of the memory consumed by δFA. Based on our experiments, the throughput of the proposed CSDFA is also much better than δFA.",
author = "Yeim-Kuan Chang and Li, {Yuen Shuo} and Chen, {Yu To}",
year = "2015",
month = "1",
day = "1",
doi = "10.1016/j.procs.2015.07.211",
language = "English",
volume = "56",
pages = "292--299",
journal = "Procedia Computer Science",
issn = "1877-0509",
publisher = "Elsevier BV",
number = "1",

}

A memory efficient DFA using compression and pattern segmentation. / Chang, Yeim-Kuan; Li, Yuen Shuo; Chen, Yu To.

In: Procedia Computer Science, Vol. 56, No. 1, 01.01.2015, p. 292-299.

Research output: Contribution to journalConference article

TY - JOUR

T1 - A memory efficient DFA using compression and pattern segmentation

AU - Chang, Yeim-Kuan

AU - Li, Yuen Shuo

AU - Chen, Yu To

PY - 2015/1/1

Y1 - 2015/1/1

N2 - The role of network security systems such as network intrusion detection system (NIDS) has become more important. The regular expression (a.k.a. regex) matching algorithm used for inspecting the payloads of packets is one of the most intensive tasks in NIDS. When multiple regular expressions are processed together, the corresponding Deterministic Finite Automata (DFA) becomes so complicated and needs a large amount of memory. In this paper, we propose a memory efficient parallel compatible DFA algorithm that uses the techniques of compression and pattern segmentation to reduce the memory usage. Extended from PFAC (Parallel Failureless-AC) algorithm4, the proposed compressed and segmented DFA (CSDFA) needs less numbers of states and transitions than δFA. Without considering the leading symbols ".∗" in the regular expressions, the transition table can be compressed very efficiently by the run-length encoding. The number of transitions in CSDFA is about a half of the transitions needed in δFA, and uses only 74% of the memory consumed by δFA. Based on our experiments, the throughput of the proposed CSDFA is also much better than δFA.

AB - The role of network security systems such as network intrusion detection system (NIDS) has become more important. The regular expression (a.k.a. regex) matching algorithm used for inspecting the payloads of packets is one of the most intensive tasks in NIDS. When multiple regular expressions are processed together, the corresponding Deterministic Finite Automata (DFA) becomes so complicated and needs a large amount of memory. In this paper, we propose a memory efficient parallel compatible DFA algorithm that uses the techniques of compression and pattern segmentation to reduce the memory usage. Extended from PFAC (Parallel Failureless-AC) algorithm4, the proposed compressed and segmented DFA (CSDFA) needs less numbers of states and transitions than δFA. Without considering the leading symbols ".∗" in the regular expressions, the transition table can be compressed very efficiently by the run-length encoding. The number of transitions in CSDFA is about a half of the transitions needed in δFA, and uses only 74% of the memory consumed by δFA. Based on our experiments, the throughput of the proposed CSDFA is also much better than δFA.

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

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

U2 - 10.1016/j.procs.2015.07.211

DO - 10.1016/j.procs.2015.07.211

M3 - Conference article

VL - 56

SP - 292

EP - 299

JO - Procedia Computer Science

JF - Procedia Computer Science

SN - 1877-0509

IS - 1

ER -