多检测引擎监测的动态负载均衡算法

杨忠明，梁本来，秦 勇，蔡昭权

(1.广东科学技术职业学院 计算机工程技术学院，广东 珠海 519090; 2.中山职业技术学院 信息工程学院，广东 中山 528404；3.东莞理工大学 计算机学院，广东 东莞 523808; 4.惠州学院 教育技术中心，广东 惠州 516007) (*通信作者电子邮箱 yzm8008@126.com)

多检测引擎监测的动态负载均衡算法

杨忠明1*，梁本来2，秦 勇3，蔡昭权4

(1.广东科学技术职业学院 计算机工程技术学院，广东 珠海 519090; 2.中山职业技术学院 信息工程学院，广东 中山 528404；
3.东莞理工大学 计算机学院，广东 东莞 523808; 4.惠州学院 教育技术中心，广东 惠州 516007) (*通信作者电子邮箱 yzm8008@126.com)

为解决多引擎入侵检测系统的负载均衡问题，提出一种检测引擎的动态负载调节算法。首先，监测各引擎节点计算负载；然后，以过载或空载节点出现为调度时机，以会话为单位调度重负载节点的流量到低负载节点，并遍历节点进行负载均衡的调节。由于以会话为调度单位，算法并不以负载的绝对平均为目的，只需保障各引擎节点不出现过载或空载即达到基本目标。采用KDD cup99数据集进行模拟实验，实验结果表明，与平均分配流量算法和基于较大流调整的安全分流算法相比，所提算法对检测引擎基于会话的负载均衡效果显著，运行开销较低且降低了重负载状态下的丢包率，有利于提高入侵检测系统的检测率。

入侵检测；负载均衡；流量调度；检测引擎；会话调度

0 引言

在高速网络环境下，大规模的网络数据流量以及攻击多样化导致的匹配特征规则大幅增长，使得网络入侵检测系统(Network Intrusion Detection System, NIDS)的检测引擎面临着较为严重的性能瓶颈问题[1]。而解决性能瓶颈的方式目前可大体分为两类：一类方法是提高单个检测引擎的检测算法效率，但受限于单个引擎节点的处理速度上限，难以全面解决NIDS面临的性能瓶颈问题[2]。另一类方法是多引擎的并行处理技术，近年来成为解决高速NIDS瓶颈问题的研究重点[3-5]。多引擎并行处理NIDS的关键是多引擎节点的流量负载均衡问题，负载均衡算法的设计应尽量动态均衡分流并尽量少破坏攻击数据上下文的关联性[6]。

多入侵检测引擎的负载均衡算法主要分为静态算法和动态算法[7]。静态负载均衡算法是按照预先设定好的策略进行分流，适用于特定业务系统的保护无法适应动态变化的网络服务。静态负载均衡算法的研究多数是基于HASH(Hash散列函数)方法以保证网络连接的完整性，但HASH并不能较好地均衡符合Zipf分布的网络流量[8]。动态负载均衡算法在运行过程中根据各节点或链路的负载情况，动态分配发往各引擎节点的流量，实时维持各节点流量的大致平衡，但这类算法带来较大的额外的运行开销[9]。

聚类分析的方法应用于入侵检测系统存在海量高维、高速数据的聚类计算需求，左晓军等[10]提出基于Spark框架的分布式数据流聚类方法DSCLS，启动Spark-Map任务并行化获取聚类簇质心，由于聚类簇的规模大小不一将导致计算量无法保存均衡。易发胜等[11]提出采用计数布隆过滤器(Bloom Filter, BF)技术的分布式入侵检测方法，利用分布式的思想提高了BF模式匹配算法的效率，但核心的匹配算法仍未实行计算负载并行化。

针对特定算法的负载均衡算法无法满足通用性需求，应结合入侵检测的计算特点，面向会话设计行之有效的均衡算法。陈一骄等[12]提出一种面向会话的自适应负载均衡算法MSF，该算法将IP报文进行多域分类，动态调整TCP流量，能够在不影响会话完整性的基础上进行动态负载均衡，模拟实验显示，MSF算法具有一定的负载均衡效果，并且对于会话完整性的破坏度较小，算法的实现也较为容易，但该算法尚缺乏稳定性的证明。为了改变真实网络链路较大流数目少但其所占流量比重较大的情况，陆华彪等[13]提出一种基于较大流调整的安全分流算法HAMF，经过模拟实验验证，该算法位流均衡效果较好，流破坏率相对较低，但该算法的复杂度相对偏高。王正霞等[14]基于B+树的稳定性和均衡性，提出基于B+树结构快速调优的反馈式负载均衡算法BLB，在负载不均衡时，BLB算法重映射流表，动态维持负载均衡，仿真实验表明，该算法能够有效地进行负载均衡，降低丢包率，但该算法复杂度相对较高，算法的性能分析过于理论化。

本文提出一种检测引擎负载监测调整的动态负载均衡算法——DLBAMADE(Dynamic Load Balancing Algorithm based on Monitoring and Adjusting of Detection Engines)，在多检测引擎NIDS中，利用负载监测器每间隔时间Δt动态监测各引擎节点的工作负载情况，通过负载分析器对当前时刻各检测引擎节点的负载情况按由重到轻的顺序进行排序。算法的调度时机为出现过载或空载节点，利用流量调度器将引擎中待处理的会话按调节比例依次分发给排序后的各引擎节点。

1 多引擎NIDS负载均衡架构

在高速网络环境下，入侵检测系统可以采用多检测引擎并行处理的方法解决海量数据的快速处理问题。而要充分发挥各引擎节点的作用，需要有效的负载均衡算法将数据流均衡分配至各检测引擎处理，负载均衡算法是发挥多节点并行处理作用的关键。

入侵检测的并行处理应以会话为单位进行并行计算任务的调度，本文提出的DLBAMADE算法以Δt为时间周期监测各并行处理节点的负载情况，在出现负载失衡时进行流量的调度。调度算法并不以计算负载的绝对平均为目的，只需保障各引擎节点不出现过载或空载则达到调度基本目标。多引擎并行处理的NIDS负载均衡架构如图1所示。

2 DLBAMADE算法的理论分析

面向多引擎节点NIDS的DLBAMADE算法以一定时间间隔(Δt)为监测周期，采集各引擎节点的资源消耗度及漏包率，当引擎节点出现过载或者空载节点，则触发流量调度器进行会话调度。以数据报文为调度单位会破坏入侵检测数据链路的完整性，导致漏报/误报率升高，以会话为调度单位则可以保持检测数据的完整性，所以DLBAMADE算法以会话为单位进行调度，以不出现过载或空载节点为调度目标，不以计算量的平均程度为算法的考量指标。

图1 多引擎NIDS负载均衡架构

2.1 DLBAMADE算法的具体思路

2.1.1 存在空负载节点时的DLBAMADE算法调度设计

定义1 空负载节点。如果第i个引擎节点待检数据长度ni=0，则该引擎节点即为空负载。其中ni表示第i个引擎节点的待检数据队列长度。

如图1架构所示，由负载检测器负责实时监测各引擎节点的待检数据队列长度，以待检数据包的数量为单位，计算出第i个引擎节点的待检队列长度ni。

如果出现某检测节点的负载为空，则流量调度器应负责将当前负载最重节点的待检测会话按照一定的比例调度给空负载节点，负载最重节点的查找算法参见算法1的伪代码。其中nodenum表示检测引擎节点数量，Bignode表示负载最终的引擎节点标号。

如果只有一个空检测引擎节点，使用此引擎节点。如果两个以上的检测引擎节点负载同时为空，则在其中随机抽取一个引擎节点node*，并将当前待检数据队列最长的引擎节点的待检数据包按照一定比例调度到node*，直到没有空负载的引擎节点出现。

算法1 最重负载引擎节点寻找算法。

BeginBignode=1

//初始化，从引擎节点1开始寻找负载最重点节点 for(i=1;inBignode)Bignode=i； }

End

假设应从待检队列最长的引擎节点中调度的数据包个数为pl，计算公式分析如式(1)，其中nodenon表示待检队列不为空的检测引擎节点数目，umatch表示检测引擎节点的检测速率(单位为b/s)，Δt表示负载监测调整的间隔周期(单位为s)。

(1)

此时算法流程如图2。

2.1.2 无空负载节点时的DLBAMADE算法调度设计

无空负载节点时，负载分析器以一个监测周期Δt进行如下操作：

1)各引擎节点待检数据队列长度ni从大到小进行排序，依次填入降序队列表Table2[i]，形成重负载节点列表；

2)排序后的ni所对应的引擎节点序号填入数据队列标签表Table1[i]，与Table2表数组元素形成对应关系；

3)各引擎节点待检数据队列长度ni从小到大进行排序，依次填入升序队列表Table3[i]，形成轻负载节点列表；

利用选择排序法对检数据包个数ni进行排序。以上操作具体见算法2的伪代码。

Beginm=nodenumfor(i=1;i

}

End

图2 空负载节点情况下的DLBAMADE算法流程

算法2 各引擎节点待检数据队列长度排序算法。

定义2 过负载节点。在每个监测周期(Δt)计算每个负载节点的丢包率lossi，当某个节点的loss*超过设定阈值时则视为出现了过载节点。

关于负载节点的丢包率的阈值设定，依据文献[15]中对漏报率与检测比例的实验，根据防御目标的安全等级需要，丢包率可设在10%～25%灵活调整。

在过载节点出现，则触发负载调度时机，流量调度器将Table1[i]节点调度到Table1[j]节点的待检数据包个数为pli(其中i+j=nodenum且i

(2)

2.2DLBAMADE算法的计算复杂度分析

DLBAMADE算法的思想是利用流量调度器，在Δt时间段内将重负载引擎节点的待检数据包按照一定比例调度到低负载引擎节点，其核心步骤是负载分析器中的各引擎节点待检数据队列长度排序算法。通过对算法2的分析可得出DLBAMADE算法的时间复杂度为O(nodenum2)，nodenum为检测引擎节点的个数。

由于DLBAMADE算法具有实时性和连续性的特点，DLBAMADE算法每间隔周期Δt重新对各引擎节点待检数据队列长度排序并计算应调度数据包的数目，因此，分析DLBAMADE算法的实际复杂度应是与数据包的数量直接相关的，在高速网络环境下，DLBAMADE算法的计算复杂度也会急剧增加，因此，算法复杂度的数学分析仅具有一定的理论参考价值，具体的算法运行性能还需要在真实环境的中综合验证。

2.3 DLBAMADE算法的完整流程

DLBAMADE算法的完整流程如图3所示。

图3 DLBAMADE算法的完整流程

3 算法实验及分析

为了评估DLBAMADE算法的效果，基于图1所示的架构搭建实验系统。该系统中的负载检测器、分析器和流量调度器的算法实现基于Ubuntu 15环境，网络环境配置20个100 Mb/s快速以太网接口以及2个1 Gb/s以太网接口，利用多台100 Mb/s网口PC与流量调度器的100 Mb/s网口相连，采用KDD cup99数据集中20%的数据子集模拟网络流量的采集和检测。

本实验的参数具体如表1所示。其中检测引擎节点node5～node8与node1～node4的检测速率比例为2∶1，节点node9～node10与node1～node4的检测速率比为4∶1。

表1 实验参数设定表

3.1DLBAMADE的检测时延比实验对比

本实验中，将DLBAMADE算法与向各引擎节点平均分配流量以及基于较大流调整的安全分流算法HAMF[13]作对比分析，按设定的Δt进行负载的监控和调整。如果存在过载或空载节点，则触发调度时机进行会话负载分配调度。待检网络流量为500～1 300 Mb/s，以50 Mb/s的大小等差递增，实验结果如图4所示。

通过图4的结果分析：

1)在低流量状态下，三种负载均衡方法的待检数据检测时延基本一致，因为此时的检测引擎节点均能够实时监测数据，不存在待检测数据排队情况。

2)在网络总数据流量800 Mb/s之内时，HAMF算法具有微弱的优势，在网络总数据流量达到800 Mb/s～900 Mb/s区间时，DLBAMADE算法与HAMF算法的效果基本相当。

3)当网络总数据流量达到1 000 Mb/s以上， DLBAMADE对比HAMF算法调度下的数据检测时延优势越来越明显。

4)随着网络总流量的持续增加，DLBAMADE算法的优势相对趋于平稳，逐步收敛。这是由于在重负载网络环境下，不仅没有空载节点而且节点的待检数据队列长度较大，调度效果不明显。但经过DLBAMADE算法调度后的待检数据检测时延一直比平均分配流量的方法和HAMF算法更短，表明DLBAMADE算法的负载均衡效果在网络重负载情况下更为有效。

图4 三种负载均衡方法的实验结果对比

3.2 引擎节点不同检测速率的实验对比

本实验中设置两个检测引擎节点，网络总流量稳定在1 000 Mb/s左右，节点1和节点2的检测速率比从1∶1～20∶1进行递增变化，比例值按照等差数值2进行递增，比较DLBAMADE算法和平均分配流量算法以及HAMF算法的检测时延比，实验结果如图5所示。

图5 引擎检测速率比

分析图5，以DLBAMADE算法调度后的待检数据检测时延为1作为对比，当引擎节点的检测速率比增大时，平均分配流量的方法及HAMF的算法调度后的待检数据检测时延比均呈曲线上升，这是因为DLBAMADE算法中负载监测器得出各引擎节点的负载情况，并交由负载分析器计算出调度结果，指导流量调度器重新分配当前的网络流量，从而得到了相对更好的负载均衡效果。

3.3 DLBAMADE的检测率和丢包率实验对比

DLBAMADE算法与HAMF算法、平均分配流量算法均针对入侵检测引擎的待检测流量进行调度，与入侵检测系统的核心检测算法检测准确度没有直接关联，但在重负载情况下，更好的负载均衡效果可以降低丢包率，从而提高入侵检测系统的检测率，对检测的准确性提高有一定的效果。

本实验中待检网络流量为500～1 300 Mb/s，以100 Mb/s的大小等差递增，重点观察丢包率对比效果，并观察丢包率降低所带来的检测率提高的效果。在实验数据中，采用KDD cup99数据集中20%的数据子集模拟网络流量，样本总数62 205个，其中正常占20%，DoS类占74%。实验结果如图6、图7所示。

图7 丢包率对比

图6、图7，并综合图4的时延分析，随着待检流量增大，检测引擎节点处理时延升高，检测引擎将堆积大量的过期数据，入侵检测系统为保障检测的实时性将抛弃一部分的待检数据，导致丢包率的升高。

实验结果显示，DLBAMADE算法与HAMF算法比平均分配流量算法的负载均衡效果更显著；而只调整较大流的分流算法HAMF复杂度较高，DLBAMADE算法的计算复杂度相对较低，分析实验结果对比如下：

1)在轻负载段(500～700 Mb/s)，两个算法均能很好调度流量到轻负载节点，在丢包率的性能表现相近；

2)在重负载段(800～1 100 Mb/s)，DLBAMADE算法并行对节点按会话数比例排序调度，并行调度效果更优，检测率及丢包率的表现优于HAMF算法；

3)在过负载段(1200～1 300 Mb/s)，实验环境设定10个引擎节点累加的处理能力为1 000 Mb/s，在此段每个节点都已经过负载工作了，均衡调度起不到优化流量处理的效果，算法差异不大。平均分配流量算法因为不针对会话流调度，数据流的完整性被破坏导致检测率大幅下降。

4 结语

本文通过分析当前多引擎NIDS的负载均衡算法的特点，面向会话调度为分布式入侵检测的主流做法，从工程角度看越低的额外运行开销则算法的实用性越高。本文所提出的一种检测引擎负载监测调整的动态负载均衡算法DLBAMADE，以不出现过载或空载节点为调度目的，并以最小额外计算负载实现负载均衡为工程目标。算法以引擎节点的资源消耗度及漏包率为主要监测依据，以出现过载或空载节点为调度时机，避免了负载分配的频繁调度。模拟实验结果表明，在网络重负载，不同检测引擎节点的运行速率差异越大的情况下，DLBAMADE算法的优势越明显，能够取得较好的负载均衡效果，降低检测系统的丢包率可有效提高其检测率。如何智能区分不同网络业务数据流量的危险程度，分配较大比例的引擎节点重点检测危险数据是作者今后的研究重点。

References)

[1] 蒋文保,郝双,戴一奇，等.高速网络入侵检测系统负载均衡策略与算法分析[J].清华大学学报(自然科学版),2006,46(1):106-110.(JIANG W B, HAO S, DAI Y Q, et al. Load balancing algorithm for high-speed network intrusion detection systems [J]. Journal of Tsinghua University (Science and Technology), 2006, 46(1): 106-110.)

[2] 蔡志平,刘书昊,王晗,等.高性能并行入侵检测算法与框架[J].计算机科学与探索,2013,7(4):289-303.(CAI Z P, LIU S H, WANG H, et al. High performance parallel intrusion detection algorithms and framework [J]. Journal of Frontiers of Computer Science and Technology, 2013, 7(4): 289-303.)

[3] KUMAR M. Distributed intrusion detection system scalability enhancement using cloud computing [J]. Computer Science and Telecommunications, 2014, 41(1): 16-29.

[4] 张文兴,樊捷杰.基于KKT和超球结构的增量SVM算法的云架构入侵检测系统[J].计算机应用,2015,35(10):2886-2890.(ZHANG W X, FAN J J. Cloud architecture intrusion detection system based on KKT condition and hyper-sphere incremental SVM algorithm [J]. Journal of Computer Applications, 2015, 35(10): 2886-2890.)

[5] 程建,张明清,刘小虎,等.基于人工免疫的分布式入侵检测模型[J].计算机应用,2014,34(1):86-89.(CHENG J, ZHANG M Q, LIU X H, et al. Distributed intrusion detection model based on artificial immune [J]. Journal of Computer Applications, 2014, 34(1): 86-89.)

[6] 王明定,赵国鸿,陆华彪.基于网络流量特性分析的高速入侵检测分流算法[J].计算机应用研究,2010,27(9):3484-3486.(WANG M D, ZHAO G H, LU H B. Load balancing algorithm for high-speed IDS based on analysis of network traffic [J]. Application Research of Computers, 2010, 27(9): 3484-3486.)

[7] 王明定.高速网络入侵检测负载均衡算法研究与实现[D].长沙:国防科技大学,2010:4.(WANG M D. The research and implementation on load balancing algorithm in high-speed network for intrusion detection [D]. Changsha: National University of Defense Technology, 2010: 4.)

[8] SHI W, MACGREGOR M H, GBURZYNSKI P, et al. A novel load balancer for multiprocessor routers [EB/OL]. [2016- 01- 08]. http://www.cs.ualberta.ca/macg /Pubs/2005/SPECTS-LOAD/FlowBal_I.pdf.

[9] 张亚玲.高速网络入侵检测系统动态负载均衡策略的研究与实现[D].长沙:湖南大学,2010:7.(ZHANG Y L. Research and implementation on dynamic load-balancing strategy in high-speed network for intrusion detection system [D]. Changsha: Hunan University, 2010: 7.)

[10] 左晓军,董立勉,曲武.基于Spark框架的分布式入侵检测方法[J].计算机工程与设计,2015,36(7):1720-1726.(ZUO X J, DONG L M, QU W. Distributed intrusion detection approach based on the Spark framework [J]. Computer Engineering and Design, 2015, 36(7): 1720-1726.)

[11] 易发胜,龚海刚,汪海鹰.采用CBF技术的分布式入侵检测系统设计与实现[J].计算机工程与设计,2014,35(7):2339-2343.(YI F S, GONG H G, WANG H Y. Design and implementation of distributed intrusion detection systems based on counting bloom filter [J]. Computer Engineering and Design, 2014, 35(7): 2339-2343.)

[12] 陈一骄,卢锡城,时向泉,等.一种面向会话的自适应负载均衡算法[J].软件学报,2008,19(7):1828-1836.(CHEN Y J, LU X C, SHI X Q, et al. A session-oriented adaptive load balancing algorithm [J]. Journal of Software, 2008, 19(7): 1828-1836.)

[13] 陆华彪，赵国鸿，陈一骄,等.基于较大流调整的安全分流算法[J].计算机工程,2009,35(13):117-119.( LU H B, ZHAO G H, CHEN Y J, et al. Secure load balance algorithm based on moderate flow adjust [J]. Computer Engineering, 2009, 35(13): 117-119.)

[14] 王正霞,刘晓洁,梁刚.基于B+树快速调优的反馈式负载平衡算法[J].计算机应用,2011,31(3):609-612.(WANG Z X, LIU X J, LIANG G. Feedback pad balancing algorithm based on B+ tree fast tuning [J]. Journal of Computer Applications, 2011, 31(3): 609-612.)

[15] DAS A, NGUYEN D, ZAMBRENO J, et al. An FPGA-based network intrusion detection architecture [J]. IEEE Transactions on Information Forensics and Security, 2008, 3(1): 118-132.

This work is partially supported by the National Natural Science Foundation of China(61170193), the Science and Technology Project in the Field of Industrial High and New Technology of Guangdong Province(2013B010401036), the Training Program for Outstanding Young Teachers in Guangdong Province (YQ2014187), the Natural Science Foundation of Guangdong Province (S2013010013432), the Science and Technology Innovation Program of Guangdong Education Department (2013KJCX0178).

YANG Zhongming, born in 1980, M. S., associate professor. His research interests include information security, intelligent algorithm.

LIANG Benlai, born in 1983, M. S., lecturer. His research interests include information security, network routing.

QIN Yong, born in 1970, Ph. D., professor.His research interests include network routing optimization.

CAI Zhaoquan, born in 1970, M. S., professor. His research interests include computer network technology.

Dynamic load balancing algorithm based on monitoring and adjusting of multiple detection engines

YANG Zhongming1*, LIANG Benlai2, QIN Yong3, CAI Zhaoquan4

(1.ComputerEngineeringTechnicalCollege,GuangdongPolytechnicofScienceandTechnology,ZhuhaiGuangdong519090,China; 2.CollegeofInformationEngineering,ZhongshanPolytechnic,ZhongshanGuangdong528404,China; 3.ComputerInstitute,DongguanUniversityofTechnology,DongguanGuangdong523808,China; 4.EducationalTechnologyCenter,HuizhouUniversity,HuizhouGuangdong516007,China)

To solve the load balance problem of multi-engine intrusion detection system, a dynamic load regulation algorithm of detection engine was proposed. Firstly, load was calculated by monitoring each engine node. Then, the scheduling of the heavy load node was performed by scheduling the overload or no-load node as a scheduling opportunity, and the nodes were traversed to adjust the load balancing. As the session for the scheduling unit, the algorithm was not the absolute average load for the purpose, just to ensure that the engine node does not appear overload or no load to achieve the basic goal. The KDD cup99 data set was used to simulate experiment. The experimental results show that compared with average load allocation algorithm and secure load allocation, the proposed algorithm has a significant effect on session-based load balancing, the running cost is lower, and the packet loss rate under heavy load are lower, which improves the detection rate of intrusion detection system.

intrusion detection; load balancing; traffic scheduling; detection engine;session scheduling

2016- 08- 26;

2016- 10- 31。

国家自然科学基金资助项目(61170193);广东省工业高新技术领域科技计划项目(2013B010401036);广东省高等学校优秀青年教师培养计划项目(YQ2014187);广东省自然科学基金资助项目(S2013010013432);广东省教育厅科技创新项目(2013KJCX0178)。

杨忠明(1980—)，男，广东茂名人，副教授，硕士，CCF会员，主要研究方向：信息安全、智能算法； 梁本来(1983—)，男，山东济宁人，讲师，硕士，主要研究方向：信息安全、网络路由； 秦勇(1970—)，男，湖南邵阳人，教授，博士，主要研究方向：网络路由优化； 蔡昭权(1970—)，男，广东陆丰人，教授，硕士，主要研究方向：计算机网络技术。

1001- 9081(2017)03- 0717- 05

10.11772/j.issn.1001- 9081.2017.03.717

TP393

A