动态规划理论在DSAMDP方法中的优化研究

赵旭，王伟

西安工程大学计算机科学学院，西安 710048

动态规划理论在DSAMDP方法中的优化研究

赵旭，王伟

西安工程大学计算机科学学院，西安 710048

1 引言

网络入侵检测系统（NIDS）是对网络中的恶意行为进行识别和处理的系统。随着网络速度的提高，对网络入侵检测系统的检测效率提出更高的要求[1]。如何使网络入侵检测系统在提高检测效率的同时保持较低的丢包率和漏检率，成为该领域内一个研究热点。

M.Arun等人[2]提出在网络入侵检测系统中使用的特征码检测技术（SDT）来解决这一问题，Sravani，K等人[3]提出使用分类算法对待检网络流量进行数据分类，一些研究者通过聚类算法对入侵检测系统进行改进，例如刘凤珠[4]提出了一种改进的K均值聚类算法来提高入侵检测系统的检测准确率并降低漏检率，只是该方法在K取值3到6之间时，有一定的不稳定性。姜参等人[5]提出了一种改进的蚁群聚类的入侵检测方法来提高检测率，但是该方法对于未知攻击的检测效率较低。朱映映等人[6]提出一种基于深度协议分析对网络事件进行重新解构的方法来提高系统的检测精度和速度，同时大幅度地减少了规则库冗余。王明定[7]等人提出了基于自适应宏流的HASLF分流算法，该算法在丢包率、流破坏数和负载均衡度三个方面均有较强的优越性，只是对跨越多个流的攻击（如DDoS等）在进行负载均衡时如何有效地减少攻击证据的破坏，对HASLF算法的硬件实现如何进行优化这两个问题尚未提出解决方案。赵艳君[8]设计了基于数据挖掘的改进网络入侵检测系统模型，该模型在提高系统的检测率的同时，降低了漏报率。还有一些学者借助粒子群优化算法对入侵检测系统进行改进。例如吴庆涛[9]等人提出了一种基于粒子群优化的入侵特征选择算法，以减少特征选择时间。李正洁[10]将量子粒子群优化算法与免疫原理、移动Agent技术结合，提出组合入侵检测模型，该模型提高了检测速度，但是却存在陷入局部最优问题。而范轩苗[11]、燕红文[12]、董世博[13]等人另辟蹊径，通过改进模式匹配算法来提高系统的匹配效率。

在众多的研究方法中，笔者首次提出通过对网络流量中多媒体数据单独处理的方法[14]来降低网络入侵检测系统的丢包率，收效良好。在之后对此问题的研究中又提出使用DSAMDP方法[15]进一步改善效果。本文在此基础上，使用动态规划理论来优化DSAMDP方法的决策过程，使系统将有限的处理能力集中处理更危险的多媒体信息。

2 DSAMDP方法

网络入侵检测系统的常规检测方法是对所有数据包根据协议、地址、端口等特征分类后进行数千条规则的模式匹配，通常不将多媒体数据包与其他数据包区分对待。这就使占网络流量比例较大、相对而言较为安全的多媒体数据包成为消耗网络入侵检测系统硬件资源的“大户”。

为解决这一问题，曾设计了对网络流量中多媒体数据包识别和两种单独的处理方法[15]，并依此实现DSAMDP方法。这两种处理方法具体为：

（1）放行方法：考虑来自服务器的多媒体信息相对来自客户端的较为安全，所以将网络流量中从服务器发出的多媒体数据包标记，越过网络入侵检测系统常规的规则匹配过程。采用该方法可使系统获得较高的执行效率和较低的丢包率，但如遇到携带有危险信息的多媒体数据包，漏检率会提高[15]。

（2）相应媒体类型检测方法：该方法将各类多媒体数据可能携带的攻击特征都放到专门为之建立的多媒体数据规则库中，当发现流量中的多媒体数据包，就按照其携带的多媒体数据类型进行相应检测。因为针对具体多媒体类别制定的检测规则数量少于系统默认的检测规则数量，所以这种方法的执行效率虽然较放行方法低，但漏检率也降低。

经实验证明[15]，以上两种方法与系统常规检测方法相比，执行效率和丢包率阈值都有所提高（如表1和图1所示）。

表1 三种方法的检测效率、丢包率和漏检率方面比较

图1 三种不同处理方法的丢包阈值

图1显示了三种处理方法的丢包阈值与网络流量之间的关系，由此提出DSAMDP方法，其基本思想[15]如下：

（1）当系统启动后首先按照常规检测方法工作，并且对网络流量进行监测，根据一段时间内相对稳定的网络流量所处的区间（即小于W1、W1至W2之间、W2至W3之间、W3以上四个区间），在常规检测、相应媒体类型检测、放行三种方法中选择适当的方法处理，使系统尽量不出现丢包。如果网络流量数值从一个区间跨越到另一个区间，应重新选择处理方法。

（2）如果当前处理方法为相应媒体类型检测，并且网络流量在W1至W2区间内（在此区间内系统还有剩余处理能力），则应在不丢包前提下，通过递增方式使用常规检测方法处理更多的多媒体数据包，如果发生丢包，立即通过递减方式减少处理多媒体数据包。

（3）如果当前处理方法为放行，并且网络流量在W2至W3区间内（在此区间内系统还有剩余处理能力），则应在不丢包的前提下，通过递增方式使用相应媒体类型检测方法处理更多的多媒体数据包，如果发生丢包，立即通过递减方式减少处理多媒体数据包[15]。

3 动态规划

动态规划是一种解决复杂系统优化问题的方法，是目前解决多阶段决策问题的基本理论之一。在多阶段决策过程中，根据每一步所选决策的不同，将随即引起状态的转移，最终在变化的状态中产生一个决策序列。动态规划的目的是使整个过程的决策序列达到最优效果。

动态规划的基本原理：

动态规划的基本原理可以略述为：不论过去的状态和决策如何，对于前面的决策形成的当前的状态而言，余下的各个决策必定构成最优策略。

动态规划的基本方程如下：

其中fn+1(xn+1)=δ(xn+1)是决策过程的终端条件，δ为一个已知函数。当xn+1只取固定的状态时称固定终端；当xn+1可在终端集合Xn+1中变动时称自由终端。最终要求的最优指标函数满足式（2）：

式（1）是一个递归公式，如果目标状态确定，可以直接利用该公式递归求出最优值，但在实际应用中通常将该递归公式改为递推公式求解，这样效率会更高一些。

4 动态规划理论对DSAMDP方法的优化过程

4.1 优化方案

虽然多媒体数据包相对安全，但也不能掉以轻心。在DSAMDP方法的步骤2和3中，在不丢包的前提下，会使用更安全的方法优先处理一些更具危险性的多媒体数据包（例如脚本程序、flash、图片等）。但是这些多媒体数据包如何选择，既要保证所选择的多媒体数据包序列不会造成系统超出负载能力，又要使该选择序列的信息危险度最大化，就成为本节研究的问题。

首先定义如下参数：

M为系统的最大载荷，可预先在同等带宽条件下通过模拟流量测得。

Xi为每时间片内待挑选的某个多媒体数据包。

Wi为多媒体数据包Xi对系统造成的负载，因为模式匹配算法的时间复杂度与待匹配字符串长度呈正相关[6]，所以Wi由数据包负载长度与数据包最大载荷的比值来确定。

Pi为多媒体数据包Xi的危险度，其值根据数据包携带的多媒体信息的危险程度而定，例如数据包携带octet-stream、x-shockwave-flash、x-javascript等类型的多媒体数据时，该数据包的Pi值会比较高些。

借鉴动态规划理论，对DSAMDP方法的优化问题可描述如下：

在图1的W1～W2（或W2～W3）区间内的每个时间片中，从X1,X2,…,Xn序列中挑选出一个危险度最大的序列使用常规检测方法（如在W2～W3，使用相应媒体类型检测方法）来处理，所以，该优化问题可以理解为求解每个时间片内选取的危险性最高的多媒体数据包序列，即：

注：Xi为0表示该数据包未被选中，为1表示被选中。

4.2 优化方案可行性的证明

根据动态规划法基本要素，能否使用动态规划理论，必须分析问题解的结构，考察它的最优解是否具有最有子结构特性，其次，应当检查分解所得的子问题是否相互独立，是否存在重叠子问题现象。

证明假设(X1,X2,…,Xn)，Xi∈{0,1}是本问题每个时间片内多媒体数据包选取的最优解，则(X2,X3,…,Xn)必是子时间片内的最优解：系统最大载荷为M-W1X1，该子时间片内共有n-1个多媒体数据包，第i(1≤i≤n)个多媒体数据包对网络入侵检测系统造成的负载为Wi，该数据包的危险性为Pi(Pi＞0)。如若不然，设则(Z2,Z3,…,Zn)是子时间片内的最优解，而(X1,X2,…,Xn)不是子时间片内的最优解。那么，由此可知，必有：

显然，(X1,Z2,…,Zn)是比(X1,X2,…,Xn)危险性更高的最优解，则(X1,X2,…,Xn)不是该时间片内的最优解。这与假设相矛盾，所以(X2,X3,…,Xn)必是子时间片内的最优解。由此可见，通过动态规划理论对动态自适应多媒体数据处理方法的优化问题具有最有子结构特性，可以使用。

4.3 具体优化过程

根据动态规划理论和优化方案的定义，可获得状态转移方程：

fi(M)表示在最大载荷为M的系统中，前i个被挑选的多媒体数据包可获得的最大危险度。根据该式，即可求得待检多媒体数据包的最优选择序列。

下面是根据式（4）用递归方式实现优化方案的关键代码

在以上程序中，执行频度最大的部分是内层for循环中的语句，由于有一个两重for循环，循环次数为n×m，所以它的执行次数也是n×m次，那么该优化方法的时间复杂度为O(nm)。

5 实验结果

5.1 实验环境

本文所使用的实验数据是由麻省理工学院林肯实验室的KDD CUP 99数据集和背景流量混合而成。KDD CUP 99数据集中包括了四大类网络攻击类型[16]：DoS、R2L、U2R和PROBE，背景流量是预先在网络捕获的真实流量，含有大量多媒体数据包。实验将通过这两种混合流量来对比优化前后的效果。

实验环境配置如下：

（1）处理器：AMD A10-5800K 4核

（2）内存：4 GB DDR3

（3）操作系统：Windows 7

在测试之前，首先对不同的多媒体类型设定危险度（如表2所示），其值根据易携带危险信息的程度而定，例如octet-stream类型可携带exe文件，所以它的危险度设定较高。

表2 部分多媒体类型设定的危险度

5.2 测试结果及分析

本文设置了三组实验，第一组通过同一段流量测试优化前后多个时间片内所选多媒体数据包序列的危险度差异（如图2所示）。

图2 优化前后不同时间片内所选多媒体数据包序列的危险度对比

第二组实验通过同一段流量测试优化前后不同危险度的多媒体数据包的检测比例（如表3所示）。

表3 不同危险度的多媒体数据包在优化前后检测比例对比

在表3中可以看出，优化后危险度相对较高的多媒体数据包的检测率有了不同程度的提升，例如octet-stream类型提升了84%，x-JavaScript类型提升了75%，提升幅度较大的原因除了优化的作用以外，还考虑到优化前这些数据被随机检测，加之总数较少，所以基数较低。另一方面，也可以看出危险度较低的多媒体数据包检测率出现下降，如html类型下降18%。

第三组实验测试优化前后系统丢包率的变化（如图3所示）。

图3 优化前后丢包率对比

在图3中可以看出，优化前后的丢包率变化基本不大，优化后丢包率略高一些的原因考虑是优化过程中为选择数据包序列而耗费系统资源造成。

6 结束语

在提出的网络入侵检测系统中使用动态自适应多媒体数据处理方法降低丢包率的基础上，使用动态规划理论对该方法的决策过程进行优化，使每个时间片内选取的多媒体数据包序列的危险度达到最高。通过优化，使网络入侵检测系统将有限的处理能力集中处理那些更具危险性的多媒体数据包。实验结果表明，该方法可提高系统对高危多媒体信息的检测率。

[1]史志才，夏永祥.高速网络环境下的入侵检测技术研究综述[J].计算机应用研究，2010，27（5）：1606-1610.

[2]Arun M，Krishnan A.Functional verification of signature detection architectures for high speed network applications[J].International Journal of Automation and Computing，2012，9（4）.

[3]SravaniK，SrinivasuP.Comparativestudyofmachine learning algorithm for intrusion detection system[J].Advances in Intelligent Systems and Computing，2014，247：189-196.

[4]Liu Fengzhu.A clustering method for anomaly intrusion detection[J].Computer Security，2013，8：2-6.

[5]姜参，王大伟.一种改进蚁群聚类的入侵检测方法[J/OL].计算机技术与发展，2013（12）.http：//www.cnki.net/kcms/ detail/61.1450.TP.20130929.1548.060.html.

[6]朱映映，吴锦锋，朱艳艳，等.网络入侵检测中的深度协议分析方法[J].计算机应用研究，2012，29（5）：1891-1895.

[7]王明定，赵国鸿，陆华彪.基于网络流量特性分析的高速入侵检测分流算法[J].计算机应用研究，2010，27（9）：3484-3486.

[8]赵艳君，魏明军.改进数据挖掘算法在入侵检测系统中的应用[J].计算机工程与应用，2013，49（18）：69-72.

[9]吴庆涛，曹继邦，郑瑞娟.基于粒子群优化的入侵特征选择算法[J].计算机工程与应用，2013，49（7）：89-92.

[10]李正洁，李永忠，徐磊.免疫Agent和量子粒子群优化的入侵检测方法研究[J].计算机工程与应用，2012，48（1）：102-104.

[11]范轩苗，郑宁，范渊.Web入侵检测系统高效多模式匹配算法[J].计算机应用研究，2009，26（4）：1528-1531.

[12]燕红文.基于Snort的改进BMH单模式匹配算法研究[J].计算机工程与应用，2012，48（31）：78-80.

[13]董世博，李训根，殷珍珍.一种改进的字符串多模式匹配算法[J].计算机工程与应用，2013，49（8）：133-137.

[14]赵旭，王长山.Snort入侵检测系统的改进[J].西安工程大学学报，2006，21（6）：859-863.

[15]赵旭.基于Snort的动态自适应多媒体数据处理方法研究[J].计算机系统应用，2011，20（4）：211-213.

[16]Zhang Xinyou.Research of intrusion detection system dataset-KDD CUP99[J].Computer Engineering and Design，2010，31（22）：4809-4812.

ZHAO Xu,WANG Wei

College of Computer Science,Xi’an Polytechnic University,Xi’an 710048,China

There is always a high packet loss rate in the network intrusion detection system,especially when the network traffic is high.The author once raised the method of Dynamic Self-Adapting Multimedia Data Processing（DSAMDP）to reduce the packet loss rate and

good results.On the basis of the above,the idea of optimization in dynamic programming theory is applied to optimize the decision-making steps of the Dynamic Self-Adapting Multimedia Data Processing method.While taking into account of system load capacity,this method can find an optimum solution to how to select the highest risk of multimedia data packet sequence in each time unit.In this way,the limited processing power of network intrusion detection system can be focused on the more dangerous multimedia data packets.Experiments show that this method can let system improve the detection rate of the high risk of multimedia information

Network Intrusion Detection System（NIDS）;multimedia;dynamic programming theory;Dynamic Self-Adapting Multimedia Data Processing（DSAMDP）;optimizing

网络入侵检测系统在流量大的情况下经常会出现较高的丢包率，曾提出通过DSAMDP（Dynamic Self-Adapting Multimedia Data Processing，动态自适应多媒体数据处理）方法来解决这一问题，收效良好。在此基础上，使用动态规划理论对DSAMDP方法的决策过程进行优化，在兼顾系统负载能力的同时，使每个时间片内选取的多媒体数据包序列的危险度达到最高。这种方法可使网络入侵检测系统将有限的处理能力集中处理那些更具危险性的多媒体数据包。实验结果表明，该方法可提高系统对高危多媒体信息的检测率。

网络入侵；多媒体；动态规划理论；动态自适应多媒体数据处理（DSAMDP）；优化

A

TP393.08

10.3778/j.issn.1002-8331.1402-0080

ZHAO Xu,WANG Wei.Optimization research of DSAMDP method with dynamic programming theory.Computer Engineering and Applications,2014,50（22）：83-87.

陕西省教育厅科研计划项目资助（No.2010JK568）；中国博士后科学基金项目（No.20090451384）。

赵旭（1978—），男，讲师，研究领域为网络安全；王伟（1969—），男，博士后，副教授，研究领域为网络性能评估，网络信息安全。E-mail：37274679@qq.com

2014-02-12

2014-05-06

1002-8331（2014）22-0083-05

CNKI网络优先出版：2014-06-18,http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1402-0080.html