具有扩展字符集的DFA，可进行快速深层数据包检查资源-CSDN文库

15 浏览量 2021-03-27 12:57:01 上传评论收藏 1.91MB PDF 举报

深度数据包检查（Deep Packet Inspection，简称DPI）技术在网络安全领域的重要性日益凸显，它不仅仅是对数据包头部结构信息的检查，还涉及到对数据包负载内容的处理。通过基于规则集的签名来识别安全威胁，DPI技术已经成为网络入侵检测系统、内容相关流量管理、内容过滤和监控等众多应用的基础。本文介绍了一种通过扩展字符集的确定性有限自动机（Deterministic Finite Automata，简称DFA）技术，该技术能够显著降低状态数量，实现快速深层数据包检查。传统数据包检查算法通常仅限于将数据包与一组字符串进行比较，而DPI系统则使用由正则表达式组成的规则集，这些正则表达式更为强大和表达丰富。例如，Snort和Bro这类网络入侵检测系统就使用了正则表达式规则集。但是，这些系统的实现需要依赖于高效的处理器，并且需要频繁更新。因此，对于那些基于通用处理器实现DPI的系统来说，成本效益和灵活性成为考虑的重点。为了改进现有的状态压缩技术，在本文中提出了一种新的解决方案，即具有扩展字符集的确定性有限自动机（DFA/EC）。通过将字符集大小翻倍，DFA/EC能够在每个字符集状态上显著减少状态数量。不同于现有的状态减少算法，本文提出的DFA/EC在处理数据包负载中的每个字节时，仅需单次主内存访问，这是最小的需求。实验表明，与传统的DFA相比，DFA/EC在最好的情况下可以小四个数量级；此外，DFA/EC占用的内存带宽小，执行速度更快。 DFA是有限自动机（Finite Automata，简称FA）的一种特殊类型，它是一种识别模式的数学模型，由一组状态、输入字母表、转移函数、一个起始状态和一个或多个终止状态组成。DFA的一个主要特点是对于任何给定的输入符号序列，DFA要么有一个明确的转换，要么没有。这使得DFA非常适合于快速匹配正则表达式，因此它被广泛应用于DPI中。扩展字符集（Extended Character-Set，简称EC）意味着在原有的字符集基础上进行扩展，这不仅包括ASCII字符集，还可能包括其他诸如Unicode字符集。扩展字符集通常用于处理那些需要更多字符类型来表示数据的应用场景。在DPI的上下文中，字符集的扩展对于处理不同语言和编码的数据包负载至关重要。文章中提到的Snort规则集是DPI技术领域内常用的规则集之一，Snort是一个开源的网络入侵预防和检测系统，能够进行实时流量分析和数据包记录。通过使用一套复杂的规则来分析网络流量，Snort可以检测各种攻击和安全威胁。而DFA/EC技术的引入则为Snort等系统在数据包负载检测方面提供了更加高效和快速的实现方法。本文所提出的DFA/EC技术为快速数据包检查领域提供了一种新的状态压缩方法，对于推动DPI技术的发展具有重要意义。通过扩展字符集来减少状态数量，不仅提高了DPI的性能，同时也降低了内存的使用量，使得在保证高效性和准确性的同时，也提升了系统的灵活性和经济性。这种创新性技术的研究和应用，为未来网络通信和安全领域的研究指明了新的方向。

资源推荐

资源详情

资源评论

A DFA with Extended Character-Set for

Fast Deep Packet Inspection

Cong Liu, Yan Pan, Ai Chen, and Jie Wu, Fellow, IEEE

Abstract—Deep packet inspection (DPI), based on regular expressions, is expressive, compact, and efﬁcient in specifying attack

signatures. We focus on their implementations based on general-purpose processors that are cost-effective and ﬂexible to update. In this

paper, we propose a novel solution, called deterministic ﬁnite automata with extended character-set (DFA/EC), which can signiﬁcantly

decrease the number of states through doubling the size of the character-set. Unlike existing state reduction algorithms, our solution

requires only a single main memory access for each byte in the trafﬁc payload, which is the minimum. We perform experiments with several

Snort rule-sets. Results show that, compared to DFAs, DFA/ECs are very compact and are over four orders of magnitude smaller in the

best cases; DFA/ECs also have smaller memory bandwidth and run faster. We believe that DFA/EC will lay a groundwork for a new type of

state compression technique in fast packet inspection.

Index Terms—Deep packet inspection (DPI), regular expression, deterministic ﬁnite automata (DFA), extended character-set (EC)

1INTRODUCTION

EEP packet inspection (DPI) processes packet payload

content in addition to the structured information in

packet headers. DPI is becoming increasingly important in

classifying and controlling network trafﬁc. Well-known in-

ternet applications of DPI include: network intrusion detec-

tion systems that identify security threats given by a rule-set of

signatures, content-based trafﬁc management that provides

quality of service and load balancing, and content-based

ﬁltering and monitoring that block unwanted trafﬁc. Due to

their wide application, there is a substantial body of research

work [1]–[5] on high-speed DPI algorithms, in which different

automata for single-pass high-speed inspection are proposed

based on either software or hardware implementations.

Traditional packet inspection algorithms have been limited

to comparing packets to a set of strings. Newer DPI systems,

such as Snort [6], [7] and Bro [8], use rule-sets consisting of

regular expressions, which are more expressive, compact, and

efﬁcient in specifying attack signatures. Hardware-based

approaches exploit parallelism and fast on-chip memory, and

are able to create compact automata. However, it is more cost-

effective and ﬂexible to update when small on-chip lookup

engines or general-purpose processors are used together with

automata stored in off-chip commodity memory. In this

paper, we focus on a general-purpose processor approach.

The throughput of the general-purpose processor

approaches is limited by the memory bandwidth of the

processors. Therefore, to improve inspection speed, it is

critical to minimize the number of main memory (off-chip

memory) accesses per byte in the trafﬁc payload. Some im-

plementations of the regular expressions, such as the non-

deterministic ﬁnite automata (NFAs), have a nondeterminis-

tic number of main memory accesses per byte. Another critical

issue is reducing the size of the automata stored in memory in

order to reduce the cost of memory, improving the scalability

for a larger number of rules, and increasing the inspection

speed (with the use of cache memory). While deterministic

ﬁnite automata (DFAs) implementations of regular expressions

take only one main memory accesses per byte, they often

require very large memory space to store their transition

tables, which undermines their scalability in real applications.

Therefore, conventional DFA and NFA are not ideal in real

systems.

Recent research efforts have been focused on reducing the

memory storage requirement of DFAs, and they can be

divided into the following categories: (1) reducing the number

of states [1], [9], [10], (2) reducing the number of transitions [2],

(3) reducing the bits encoding the transitions [3], [11], and

(4) reducing the character-set [12]. Unfortunately, all of these

approaches compress DFAs at the cost of increased main

memory accesses. The amount of compression in transition

reduction and character-set reduction is bounded by the size

of the character-set (e.g., the maximum reduction is

ASCII is used) due to the fact that there is at least one transition

in each state. We focus on state reduction, which is not limited

by the maximum reduction ratio of 256, and we manage to

reduce the storage size of DFAs by up to 4 orders of magni-

tude in our experiment. Moreover, our approach can be

incorporated into the other approaches to achieve further

memory reduction.

This paper proposes a novel state reduction solution, called

deterministic ﬁnite automata with extended character-set (DFA/

EC). We ﬁrst introduce DFA/EC as a general model of DFA.

This general model removes part of each DFA state and

incorporates it with the next input character. This results in

an extended the set of input characters. However, simply

•

C. Liu and Y. Pan are with Sun Yat-sen University, Guangzhou 510006,

China. E-mail: panyan5@mail.sysu.edu.cn. (corresponding author: Y. Pan.)

•

A. Chen Shenzhen Institutes of Advanced Technology, Chinese Academy of

Sciences.

•

J. Wu is with the Temple University, Philadelphia, PA 19122.

Manuscript received 14 Mar. 2012; revised 27 Oct. 2012; accepted 16 Apr. 2013.

Date of publication 18 Apr. 2013; date of current version 15 July 2014.

Recommended for acceptance by H. Shen.

For information on obtaining reprints of this article, please send e-mail to:

reprints@ieee.org, and reference the Digital Object Identiﬁer below.

Digital Object Identiﬁer no. 10.1109/TC.2013.93

IEEE TRANSACTIONS ON COMPUTERS, VOL. 63, NO. 8, AUGUST 2014 1925

See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.

doing this cannot reduce the size of the transition table since

the increase in the size of the extended character set can be

more signiﬁcant than the decrease in the number of states. Our

main contribution is an efﬁcient implementation of DFA/EC,

which contains an encoding method. This encoding method

encodes the part of the removed DFA state into a single bit. As

a result, the size of the extended character set merely doubles,

while the number of states drops by orders of magnitude. The

main contributions of this paper are summarized as follows:

1. We introduce DFA/EC, a general DFA model that in-

corporates a part of the DFA state into the set of input

characters.

2. We provide an efﬁcient implementation of the inspec-

tion program based on our DFA/EC model, which

results in a compact transition table and a fast inspection

speed.

3. We prove that DFA/EC is equivalent to DFA.

4. We perform an extensive evaluation to compare DFA/

EC with related algorithms by using several Snort

rulesets.

Compared with existing state reduction algorithms, DFA/

EC signiﬁcantly increases the inspection speed by keeping the

number of per-byte main memory accesses to one, which is the

minimum. The size of our inspection program is also small

enough to be stored entirely in the cache memory. Evaluations

with several Snort rule-sets demonstrate that DFA/ECs are

very compact and achieve high inspection speed. Speci ﬁcally,

DFA/ECs are over four orders of magnitude smaller than

DFAs in the best cases; DFA/ECs can even have smaller

memory bandwidth than DFAs, which is not seen in previous

compression algorithms. The advantages of a DFA/EC are

summarized in the following:

1. A DFA/EC requires only one main memory access for

each byte in the packet payload, while signiﬁcantly

reducing storage in terms of table size.

2. A DFA/EC is conceptually simple, easy to implement,

and easy to update due to fast construction speed.

3. A DFA/EC can be combined with other compression

approaches to provide a better level of compression.

The rest of this paper is organized as follows. Related

work is brieﬂy covered and compared in Section 2. Section 3

introduces the concept of DFA/EC with an example. Section 4

presents the formal model of DFA/ECanditsDFA-equivalence

condition. Section 5 describes an efﬁcient implementation of

DFA/EC and proves its DFA equivalence. Section 6 evaluates

DFA/EC by using the Snort rule-sets and synthetic trafﬁc.

Section 7 concludes the paper. The notations used in this

paper are summarized in Table 1.

2RELATED WORK

Prior work on regular expression matching at line rate can be

categorized by their implementation platforms into FPGA-

based implementations [13]–[17] and general-purpose pro-

cessors and ASIC hardware implementations [1], [2], [9], [10],

[18], [19]. FPGA implementations exploit high degree of

parallelism, and the achieved high throughput is difﬁcult for

the memory-based approaches. However, FPGAs are not

available in many applications including those already de-

ployed. On the other hand, the general-purpose processor

approaches are often desirable because they provide a higher

degree of ﬂexibility and they allow for frequent update of

rule-sets.

Existing transition table compression techniques based on

general-purpose processors include: (1) DFA state compres-

sion techniques and (2) transition compression techniques.

DFA state compression techniques reduce the number of DFA

states like MDFA [1], HFA [9], XFA [20]. Transition compres-

sion techniques reduce the number of transitions in each state

such as

[2], [18]. Both kinds of techniques

effectively reduce the memory storage but introduce addi-

tional main memory accesses per byte. Note that the two

kinds of compression techniques are perpendicular and can

be combined. Our work in this paper builds upon the area of

DFA state compression.

Delayed Input Deterministic Finite Automata (

) [2]

uses default transitions to reduce the memory storage require-

ment. If two states have a large number of transitions in

common, the transition table of one state can be compressed

by referring to that of the other state. Unfortunately, when a

default transition is followed, the main memory must be

accessed once more to retrieve the transitions of the referred

state [2], [18].

Using auxiliary variables and devising a compact and

efﬁcient inspection program is challenging and is related to

our work. Two seminal papers [9], [20] use auxiliary variables

to represent the “factored out” auxiliary states in order to

reduce the DFA size. However, the auxiliary variables are

manipulated by auxiliary programs associated with each state

or transition, resulting in extra main memory accesses to

obtain the auxiliary programs in addition to the state indexes.

Secondly, H-FA [9] uses conditional transitions that require a

TABLE 1

Notations Used in This Paper

1926 IEEE TRANSACTIONS ON COMPUTERS, VOL. 63, NO. 8, AUGUST 2014

剩余12页未读，继续阅读

评论收藏

内容反馈

weixin_38679651

粉丝: 6
资源: 934

具有扩展字符集的DFA，可进行快速深层数据包检查

IDPI：支持专用AFDL语言的高级超高速深层数据包检查库

DFA.rar_DFA_DFA 判断字符串_DFA 报告_DFA串

编译原理DFA识别字符串

DFA.rar_DFA_DFA串_定义字符串dfa_正则式_正则式DFA

DFA_DFA识别_

NFA转DFA，并将DFA最小化

基于C语言模拟实现DFA识别字符串.zip

正则表达式转DFA

NFA转换为DFA可执行C代码加报告

去趋势波动分析DFA 多维DFA

DFA.zip_DFA_DFA医学信号_MFDFA_医学DFA分析_去 趋势

NFA到DFA的转换

一个简单的DFA源码C++

DeepPacketInspection:快速且内存有效的正则表达式匹配，可进行深度数据包检查

编译原理 模拟DFA

7.15 数据结构（二）: 并查集, DFA, Trie图等

构造正规式最小DFA方法

正则表达式最小化DFA

nfa转dfa以及dfa的最小化程序

DFAmatlab程序_dfa源代码_DFA程序_

DFA.rar_活前缀dfa_活前缀的DFA

自动机nfa->dfa邻接表实现

C++ 正则文法定义-正则表达式-NFA-DFA-最小化DFA-字符串匹配DFA

正则文法到DFA

NFA转DFA&DFA最小化&NFA与DFA语言子集NFA转DFA&DFA最小化&NFA与DFA语言子集

dfa.rar_DFA_DFA程序

java利用DFA算法实现敏感词过滤功能

DFA的原理文章

最新资源

DFA.zip_DFA_DFA医学信号_MFDFA_医学DFA分析_去趋势

编译原理模拟DFA