Paper Info
Title
O3FA: A Scalable Finite Automata-based Pattern-Matching Engine for Out-of-Order Deep Packet Inspection.
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, inter-changing 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.
Year
DOI
Venue
2016
10.1145/2881025.2881034
ANCS
Keywords
Field
DocType
scalable finite automata-based pattern-matching engine,out-of-order deep packet inspection,malicious traffic signature,packet boundary,network-intrusion detection system,network-intrusion prevention,NIDS,flow reassembly,packet reordering,packet buffer,denial-of-service attack,DoS attack,buffer capacity,out-of-order packet,exact-match pattern,repetitive subpattern,regular-expression matching engine,finite automata-based deep packet-inspection engine,deterministic finite automaton,O3FA engine,buffer space,buffering-and-reassembling scheme,packet processing
Deep packet inspection,Regular expression,Deterministic finite automaton,Computer science,Network packet,Computer network,Real-time computing,Finite-state machine,Intrusion detection system,Packet generator,Pattern matching
Conference
ISBN
Citations 
PageRank 
978-1-5090-6606-3
4
0.41
References 
Authors
21
4
Name
Order
Citations
PageRank
Xiao Yu17012.14
Wu-chun Feng22812232.50
Danfeng Yao396574.85
Michela Becchi4106457.20