O3FA: A scalable finite automata-based pattern-matching engine for out-of-order deep packet inspection

Xiaodong Yu, Wu Chun Feng, Danfeng Yao, Michela Becchi

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

18 Scopus citations

Abstract

To match the signatures of malicious traffic across packet boundaries, network-intrusion detection (and prevention) systems (NIDS) typically perform pattern matching after flow reassembly or packet reordering. However, this may lead to the need for large packet buffers, making detection vulnerable to denial-of-service (DoS) attacks, whereby attackers exhaust the buffer capacity by sending long sequences of out-of-order packets. While researchers have proposed solutions for exact-match patterns, regular-expression matching on out-of-order packets is still an open problem. Specifically, a key challenge is the matching of complex sub-patterns (such as repetitions of wildcards matched at the boundary between packets). Our proposed approach leverages the insight that various segments matching the same repetitive sub-pattern are logically equivalent to the regular-expression matching engine, and thus, interchanging them would not affect the final result. In this paper, we present O3FA, a new finite automata-based, deep packet-inspection engine to perform regular-expression matching on out-of-order packets without requiring flow reassembly. O3FA consists of a deterministic finite automaton (FA) coupled with a set of prefix-/suffix-FA, which allows processing out-of-order packets on the fly. We present our design, optimization, and evaluation for the O3FA engine. Our experiments show that our design requires 20x-4000x less buffer space than conventional buffering-and-reassembling schemes on various datasets and that it can process packets in real-time, i.e., without reassembly.

Original languageEnglish
Title of host publicationANCS 2016 - Proceedings of the 2016 Symposium on Architectures for Networking and Communications Systems
Pages1-11
Number of pages11
ISBN (Electronic)9781450341837
DOIs
StatePublished - 17 Mar 2016
Event12th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, ANCS 2016 - Santa Clara, United States
Duration: 17 Mar 201618 Mar 2016

Publication series

NameANCS 2016 - Proceedings of the 2016 Symposium on Architectures for Networking and Communications Systems

Conference

Conference12th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, ANCS 2016
Country/TerritoryUnited States
CitySanta Clara
Period17/03/1618/03/16

Fingerprint

Dive into the research topics of 'O3FA: A scalable finite automata-based pattern-matching engine for out-of-order deep packet inspection'. Together they form a unique fingerprint.

Cite this