基于排队论的分布式入侵检测系统成本优化方法

摘要

本发明公开了一种基于排队论的分布式入侵检测系统成本优化方法，具体包括如下步骤：步骤1，对分布式入侵检测系统进行模型分析和参数设定步骤2，对分布式入侵检测系统进行状态空间分析；步骤3，建立生灭过程；步骤4，确定分布式入侵检测系统平衡状态下的平稳分布；步骤5，计算分布式入侵检测系统中的相关技术指标；步骤6，基于步骤5的计算结果进行运行成本分析及优化。本发明通过排队论计算实现分布式入侵检测系统运行成本最小化的检测引擎数量，解决了现有技术中分布式入侵检测系统运行成本过高的问题。

说明书

技术领域

本发明属于信息安全技术领域，涉及一种基于排队论的分布式入侵检测系统成本优化方法。

背景技术

分布式入侵检测系统((Distributed Intrusion Detection System,DIDS)由调度器和多个检测引擎组成，由调度器将捕获的网络流量分配给检测引擎进行检测。排队论(queuing theory)是研究随机服务系统工作过程的数学理论和方法。排队论可以通过对服务对象的到来及服务时间进行统计研究，然后根据技术指标的统计规律来改进服务系统的结构，实现技术指标的最优化。

发明内容

本发明的目的是提供一种基于排队论的(各检测引擎处理能力相同的)分布式入侵检测系统成本优化方法，本发明通过排队论计算实现分布式入侵检测系统运行成本最小化的检测引擎数量，解决了现有技术中分布式入侵检测系统运行成本过高的问题。

本发明所采用的技术方案是，基于排队论的分布式入侵检测系统成本优化方法，具体包括如下步骤：

步骤1，对分布式入侵检测系统进行模型分析和参数设定

步骤2，对分布式入侵检测系统进行状态空间分析；

步骤3，建立生灭过程；

步骤4，确定分布式入侵检测系统平衡状态下的平稳分布；

步骤5，计算分布式入侵检测系统中的相关技术指标；

步骤6，基于步骤5的计算结果进行运行成本分析及优化。

本发明的特点还在于，

步骤1的具体过程为：

设分布式入侵检测系统内有n个检测引擎，流量按泊松流到达分布式入侵检测系统，单位时间内数据包的平均到达数为λ；各检测引擎独立工作，检测时间均为负指数分布，单位时间内各检测引擎的检测能力相同，对数据包的检测数都为μ；设定分布式入侵检测系统的各个检测引擎以及待检队列对数据包的容量总和为m，其中，m＞n＞1，如果有k个检测引擎被占用，那么待检队列中就有能容纳m-kμ个数据包的空间，新到的数据包将进入待检队列等待；若待检队列已满，则新来到数据包将被丢弃，不进行模式匹配。

步骤2的具体过程为：

将分布式入侵检测系统的状态空间可定义为E＝{0,1,2,...,m}。对于状态k，可分3种情况：

当0＜k＜nμ时，表示DIDS中已有k/μ个检测引擎被占用，剩余n-k/μ个检测引擎空闲，系统剩余容量为m-kμ，因为每个检测引擎单位时间内数据包的检测数为μ，所以此时DIDS的总检测数为kμ；

当nμ≤k≤m时，则表示所有的n个检测引擎都被占用，新到的数据包需要在待检队列中等待，系统剩余容量为m-kμ，此时DIDS的总检测数为nμ；

当k＞m时，表示所有检测引擎都被占用，待检队列全满，后续到达的数据包只能丢弃，系统剩余容量为0，此时DIDS的总检测数为nμ。

步骤3的具体过程为：

当μ＝1时，即每个检测引擎单位时间内只处理1个数据包，对于状态k，其中，0＜k＜n，如果有新到的处理任务，可以转移到状态k+1；如果状态k完成当前一个处理任务，可以回到状态k-1；那么从k转移到k-1的转移强度是kμ；

设ρ

当DIDS的运行到达平衡状态后，对任一状态，单位时间内进入和离开该状态的平均次数应该相等。

步骤4的具体过程为：

设p

对状态0，因为λp

对状态n，因为λp

对状态m-1，因为λp

这样可得出，对任何状态k，

步骤5的具体过程为：

步骤5.1，计算损失概率与检测概率，具体为：

损失概率即超过DIDS最大容量m的概率P

检测概率Q

步骤5.2，基于步骤5.1所得结果计算单位时间内数据包的丢包数量和检测的数量，具体为：

单位时间内数据包的丢包数量λ

λ

步骤5.3，根据步骤5.2所得结果计算被占用的检测引擎个数L

步骤5.4，根据步骤5.3所得结果计算等待队列平均长度L

L

步骤5.5，基于步骤5.4所得结果计算数据包在系统中平均逗留时间W

步骤6的具体过程为：

步骤6.1，基于步骤5所得结果计算系统整体的运行成本，具体为：

将模型的运行成本分为检测成本和内存占用成本，分布式入侵检测系统整体的运行成本计算方法为：设a为每个数据包在等待队列的内存占用成本，b为每个数据包的检测成本，那么分布式入侵检测系统整体的运行成本计算方法如下式所示

步骤6.2，基于步骤5所得结果计算被占用的检测引擎的检测成本，具体为：

设c为每个检测引擎每单位时间内的检测成本，被占用的检测引擎的检测成本计算方法如下式所示

步骤6.3，基于步骤5、步骤6.1和步骤6.2所得结果计算实现最低的运行成本的检测引擎个数，具体为：

设d为每个数据包在分布式入侵检测系统内滞留期间所造成的成本，得出，运行成本如下式所示

f(n)＝cn+dL

采用边际分析法来求得最优设备数n

将公式L

化简可得

由于c、d都是常量，代入不同的n值，因此，只要c/d的值在(L

步骤6.3中，采用如下公式(17)计算L

根据概率分布，可以得出：

将公式(18)代入公式(17)中，即得L

本发明的有益效果是，本发明基于排队论的分布式入侵检测系统(各检测引擎处理能力相同)成本优化方法，通过排队论计算实现分布式入侵检测系统运行成本最小化的检测引擎数量，解决了现有技术中分布式入侵检测系统运行成本过高的问题。

具体实施方式

下面结合具体实施方式对本发明进行详细说明。

本发明基于排队论的分布式入侵检测系统(各检测引擎处理能力相同)成本优化方法，具体按照以下步骤实施：

步骤1，模型分析和参数设定。设分布式入侵检测系统内有n个检测引擎，流量按泊松流到达分布式入侵检测系统，单位时间内数据包的平均到达数为λ；各检测引擎独立工作，检测时间均为负指数分布，单位时间内各检测引擎的检测能力相同，对数据包的检测数都为μ；设定分布式入侵检测系统的各个检测引擎以及待检队列对数据包的容量总和为m(m＞n＞1)。如果有k个检测引擎被占用，那么待检队列中就有能容纳m-kμ个数据包的空间，新到的数据包将进入待检队列等待。如果待检队列已满，那么新来到数据包将被丢弃，不进行模式匹配；

步骤2，状态空间分析。对于上述分布式入侵检测系统，其状态空间可定义为E＝{0,1,2,...,m}。对于状态k(k可以被理解为到达的数据包数量)，可分3种情况：

下面对上表进行说明：

当0＜k＜nμ时，表示DIDS中已有k/μ个检测引擎被占用，剩余n-k/μ个检测引擎空闲，系统剩余容量为m-kμ，因为每个检测引擎单位时间内数据包的检测数为μ，所以此时DIDS的总检测数为kμ。

当nμ≤k≤m时，意味着所有的n个检测引擎都被占用，新到的数据包需要在待检队列中等待，系统剩余容量为m-kμ，此时DIDS的总检测数为nμ。

当k＞m时，表示所有检测引擎都被占用，待检队列全满，后续到达的数据包只能丢弃，系统剩余容量为0，此时DIDS的总检测数为nμ。从这里可以看出，该模型符合马尔科夫链的特点，在状态序列中，某一时刻状态转移的概率只依赖前一个状态；

步骤3，建立生灭过程。当μ＝1时(即每个检测引擎单位时间内只处理1个数据包)，对于状态k(0＜k＜n)，如果有新到的处理任务，可以转移到状态k+1；如果状态k完成当前一个处理任务，可以回到状态k-1。那么从k转移到k-1的转移强度是kμ；

设ρ

步骤4，确定平衡状态下的平稳分布。设p

对状态0，因为λp

对状态n，因为λp

对状态m-1，因为λp

这样可得出，对任何状态k，

步骤5，计算分布式入侵检测系统中的相关技术指标；

步骤5.1，基于步骤4，计算损失概率与检测概率；

步骤5.1的具体过程为：

损失概率即超过DIDS最大容量m的概率P

检测概率Q

步骤5.2，基于步骤5.1所得结果计算单位时间内数据包的丢包数量和检测的数量；

步骤5.2的具体过程为：

单位时间内数据包的丢包数量λ

λ

步骤5.3，根据步骤5.2所得结果计算被占用的检测引擎个数；

步骤5.3的具体过程为：

虽然被占用的检测引擎个数L

步骤5.4，根据步骤5.3所得结果计算等待队列平均长度和平均数据包到达数；

步骤5.4的具体过程为：

等待队列平均长度的计算公式为：

平均数据包到达数可以通过待检队列和正在检测的数据包之和得出，计算公式为：

L

步骤5.5，基于步骤5.4所得结果计算数据包在系统中平均逗留时间和平均排队等待时间；

步骤5.5的具体过程为：

数据包的平均逗留时间的计算公式为：

平均排队等待时间的计算公式为：

步骤6，运行成本分析及优化。

步骤6.1，基于步骤5所得结果计算系统整体的运行成本；

步骤6.1的具体过程为：

模型的运行成本大致可分为两部分：检测成本和内存占用成本。分布式入侵检测系统整体的运行成本计算方法为：设a为每个数据包在等待队列的内存占用成本，b为每个数据包的检测成本，那么分布式入侵检测系统整体的运行成本计算方法如下式所示

步骤6.2，基于步骤5所得结果计算被占用的检测引擎的检测成本；

步骤6.2的具体过程为：

设c为每个检测引擎每单位时间内的检测成本，被占用的检测引擎的检测成本计算方法如下式所示

步骤6.3，基于步骤5、步骤6.1和步骤6.2所得结果计算实现最低的运行成本的检测引擎个数；步骤6.3的具体过程为：

分析成本的目的是为实现运行成本的最小化，在上面2个公式中，a，b，c都是常量，λ和μ不易控制，唯一能容易改变的就是n，所以优化的方法是通过计算设置多少个检测引擎，能够实现最低的运行成本。下面计算在所有检测引擎全部被占用时的成本，设d为每个数据包在分布式入侵检测系统内滞留期间所造成的成本，这样，运行成本如下式所示

f(n)＝cn+dL

L

将公式L

化简可得

c和d都是常量，代入不同的n值，所以只要c/d的值在(L

对步骤6.3所得的最低运行成本进行简化计算。

用公式L

根据概率分布，可以得出：

将公式(18)代入公式(17)中，即(可快速)得L