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算法以会话为单位进行调度，以不出现过载或空载节点为调度目标，不以计算量的平均程度为算法的考量指标。

2.1 DLBAMADE算法的具体思路 2.1.1 存在空负载节点时的DLBAMADE算法调度设计

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

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

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

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

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

Begin

 Big_node=1

      //初始化，从引擎节点1开始寻找负载最重点节点

 for(i=1; i ＜node_num; i++) {

  If(n_i>n_Bignode)

   Big_node =i；

 }

End

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

$pl=(\sum\limits_{x={i}'}^{nod{{e}_{non}}}{{{n}_{x}}})/nod{{e}_{num}}-\int_{o}^{\Delta t}{{{u}_{match}}\cdot t\text{ d}}t$

(1)

此时算法流程如图 2。

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

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

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

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

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

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

Begin

 m= node_num

 for(i=1; i＜ node_num; i++){

  k=i;

  For (j=i+1; j＜= node_num; j++)

   IF(n_k＜n_j)

    k=j;

    Table₁[i]=k;

    Table₂[i]=n_k;

    Table₃[m--]= n_k;

   IF(i!=k){

    z=n_i;

    n_i=n_k;

    n_k=z;

   }

}

End

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

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

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

在过载节点出现，则触发负载调度时机，流量调度器将Table₁[i]节点调度到Table₁[j]节点的待检数据包个数为pl_i(其中i+j= node_num且i ＜j，表示将负载最重的节点流量调度给负载最轻的节点，负载次重点节点流量调度给负载次轻度节点，依此类推)，则有式(2) 。其中null_num_i表示第i个检测引擎节点待检数据为空的次数，η表示由变量null_num_i和null_num决定调整的待检数据包的比例，M为单位时间内分配到不同引擎节点的待检数据总流量(单位为Mb/s)。

$p{l_i} = M \cdot (1 - \eta ) \cdot {{Tabl{e_3}[i]} \over {\sum\limits_{i = 0}^{nod{e_{num}}} {Tabl{e_2}[i]} }} + M \cdot \eta \cdot {{null\_nu{m_i}} \over {\sum\limits_{i = 0}^{nul{l_{num}}} {null\_nu{m_i}} }}$

(2)

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

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

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

2.3 DLBAMADE算法的完整流程

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

3 算法实验及分析

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

本实验的参数具体如表 1所示。其中检测引擎节点node₅~node₈与node₁~node₄的检测速率比例为2:1，节点node₉~node₁₀与node₁~node₄的检测速率比为4:1。

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

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

通过图 4的结果分析：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 结语

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