SI-DFA: Sub-expression integrated deterministic finite automata for deep packet inspection

Ayesha Khalid, Rajat Sen, Anupam Chattopadhyay

Research output: Contribution to conferencePaperpeer-review

4 Citations (Scopus)

Abstract

Finite automata is widely used for Deep Packet Inspection (DPI) of network traffic. Two types of automata employed for this purpose are Non-deterministic Finite Automata (NFA) and Deterministic Finite Automata (DFA). An NFA suffers from a large memory bandwidth per character due to multiple active states. A DFA, in comparison, ensures a linear processing time of O(1) for memory based architectures. However, the DFA state explosion conditions commonly occurring in today's NIDS rule-sets, render the automata with practically infeasible memory space requirements. To avoid state blowup we propose a semi-deterministic automata, Sub-expression Integrated DFA (SI-DFA), that ensures processing time of a single standard DFA. Rules are broken into sub-expressions at blowup conditions and compiled into a single DFA along with an association table, to correctly encapsulate equivalent automata. We list the rare cases in regular expressions for which sub-expression Integration is incorrect and present methodology to detect their occurrences. We evaluate SI-DFA on real-world rule-sets like Bro, Snort and Linux filters and compare their performance with the state-of-the-art hybrid automata solutions. SI-DFA renders a 66-97% reduction in processing bandwidth, up to 68% lower space requirement and an improvement trend with increasing rule complexity when compared to the traditional solutions.

Original languageEnglish
Pages164-170
Number of pages7
DOIs
Publication statusPublished - 09 Dec 2013
Event2013 IEEE 14th International Conference on High Performance Switching and Routing, HPSR 2013 - Taipei, Taiwan, Province of China
Duration: 08 Jul 201311 Jul 2013

Conference

Conference2013 IEEE 14th International Conference on High Performance Switching and Routing, HPSR 2013
CountryTaiwan, Province of China
CityTaipei
Period08/07/201311/07/2013

Keywords

  • DFA
  • DPI
  • hybrid-automata
  • kleene stars
  • NFA
  • NIDS
  • regular expression matching
  • state blowup

ASJC Scopus subject areas

  • Hardware and Architecture
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'SI-DFA: Sub-expression integrated deterministic finite automata for deep packet inspection'. Together they form a unique fingerprint.

Cite this