一种改进的自动机压缩算法在深度包检测中的应用.docxVIP

??

?

??

一种改进的自动机压缩算法在深度包检测中的应用

?

?

?

?

?

??

?

?

?

王志佳，顾健

（公安部第三研究所，上海200031）

摘要：传统的基于自动机的深度包检测算法是把正则表达式转化成确定有限自动机，在转化过程中会导致自动机状态消耗巨大运算空间。针对这个缺点，本文提出了一种改进的、基于确定有限自动机的状态压缩算法。该算法在牺牲少量运算时间的情况下，能极大地减少算法所需的运算空间。最后，本文把此算法应用于深度包检测中，设计了对比实验，验证了该算法的有效性。关键词：深度包检测；确定有限自动机；正则表达TP393.08：A

0引言

随着网络技术和网络规模的不断发展，网络遭到攻击的风险性越来越高，网络安全已经成为一个全球化的重要课题。很多恶意行为都隐藏在数据载荷中，即使数据包通过了包过滤防火墙网关的检测，数据还是可能对内部网络造成危害。因为数据包的应用载荷中可能充斥着蠕虫病毒、垃圾邮件、漏洞利用等恶意代码。由此，深度包检测技术应运而生。目前，正则表达式、自动机理论已经在深度包检测技术中得到广泛应用。其具有灵活、高效等特点，在模式匹配时比字符串表现得更加优异。然而，在实际应用网络中，一个典型的正则表达式集合往往需要上百个自动机和数以万计的状态组成。传统的基于自动机的入侵检测算法为了达到最佳的匹配速度，将整个正则表达式集合构造成一个自动机，以至于需要数百兆，甚至上千兆字节的运算空间支持。这就极大地影响了检测算法的效率，在现实应用中是很难被接受的。针对这种情况，本文提出了一种改进的基于确定有限自动机的深度包检测算法，并且通过实验数据验证了本文提出的算法能在不增加算法的运算时间的前提下，极大地减少算法所需的运算空间。

1深度包检测技术

当前日益复杂的安全威胁中，很多恶意行为都隐藏在数据包中，可能充斥着蠕虫病毒、垃圾邮件、漏洞利用等恶意代码，在各种电子商务程序的Web数据中也可能夹带着后门和木马程序在网络中传递。所以，在网络应用和网络威胁都高速增长的今天，仅仅依照数据包网络层信息的安全检测技术，已经无法满足信息安全的要求。深度包检测（DeepPacketInspection，简称DPI）是指防火墙深入探查数据包或数据流的应用程序流量，根据数据包的有效载荷来做出某种决定的能力。深度包检测主要用来确定数据流的影响力，通常典型的深度包检测是指包含试探性数据分析的特征匹配计术．

深度内容检测功能需求深度包检测技术能够深入分析TCP或UDP通信流量的内容，如图1所示。当IP数据包、TCP数据流或UDP包经过网关设备时，将会按照预定义的策略对应用内容进行操作。用户可以使用一定的规则或策略来定义这些变量，使这些策略符合基于应用的类型或者数据业务的最终目标。

2传统算法存在的问题

传统的基于自动机的深度包检测算法，将给定的正则表达式集合中的所有正则表达式构造成一个DFA。理论上，此方法可以达到最好的运算时间。然而多个正则表达式对应一个DFA的状态数要远远大于一个正则表达式对应一个DFA状态数的总和。并且在实际应用中，由于正则表达式成百上千，导致算法需要的运算空间往往超出系统物理内存大小。在这种情况下’一般情况下系统会使用虚拟内存作为补充，但是虚拟内存是操作系统在硬盘上开辟的一块磁盘空间，使用虚拟内存意味着需要增加读写硬盘的时间，结果反而会导致运算时间的迅速增加。

另一种算法与传统算法完全相反，是将给定的正则表达式集合中的每一个正则表达式都构造一个DFA。这样是最节省运算空间的办法，但是在这种情况下，对于每一个要匹配的数据包，都要对经过所有的DFA循环匹配，必然导致运算时间迅速增加。

针对这种问题，本文提出了一种构造最优DFA状态数压缩法，该算法保证在有限的运算空间下，时间复杂度最小。DFA所占据的运算空间的大小，取决于状态的数量和每个状态的转换的数量的乘积。为了表述方便，下面运算空间（内存）的大小以状态数来衡量。

3算法描述

在介绍算法之前，首先要引入一个DFA膨胀率‘卅的概念。我们知道，任意一个正则表达式都可以通过形式化的方法构造出NFA，同样，任意一个NFA也都能转化成一个DFA。然而DFA的状态数与正则表达式的长度是线性相关的。正则表达式中的每一个字符（属于字符集）、元字符和操作符，都对应着一定的DFA状态数。随着正则表达式自身结构的复杂度不同，转化成的DFA状态数会逐渐增加，甚至会发生指数级增长。我们来看下面一个例子。

如图2所示，4个正则表达式RE1、RE2、RE3和RE4都具有相同的NFA表示形式，但产生了形态完全不同的DFA，状态数分别是4、5、7和8个。其中，RE2，RE3和RE4都有计数结构，它们的DFA状态数和正则表达式的计数结构计数值存在着不同的量级关系。上述分析说明