改进的否定选择算法在入侵检测系统中的应用

金 静，韩 虎，崔永君

（兰州交通大学 电子与信息工程学院，甘肃 兰州 730000）

入侵检测系统（Intrusion Detection System，IDS）是软件和硬件的组合，它对系统中的关键点进行信息的收集和分析，从而判断被保护的目标是否被恶意滥用或者非法入侵，并通过提示报警、阻断连接、通知网管等措施及时中止这些危害。它作为一种积极主动的安全防护技术，是防火墙后面的第二道安全闸门。

生物机体内的免疫系统是一个高度进化的系统，它能区分外部有害抗原和自身组织，清除病原并保持机体的稳定。生物免疫系统的特性与入侵检测系统所需要达到的目标是十分相似和一致的，因此通过模仿和借鉴生物免疫系统的一些机制和原理来进行入侵检测方面的研究，可以弥补当前IDS的不足。

1 否定选择算法

人工免疫系统（Artificial Immune System，AIS）通过否定选择算法（NSA）[1-2]实现对自体的耐受。该算法是对免疫细胞的成熟过程的模拟，目的是清除那些对自体产生应答的免疫细胞。算法的具体步骤为：

步骤1定义系统的正常状态为自体集S。

步骤2随机字符串产生器产生定长的候选检测器。

步骤3将候选检测器与自体集合S进行比较，即计算候选检测器与自体集的匹配度，达到匹配阈值的候选检测器就会被清除，否则将候选检测器加入成熟检测器集合。

步骤4重复步骤2和步骤3，直到有效检测器数目达到预定的大小。该过程流程图如图1所示。

图1 否定选择算法Fig.1 Negative select algorithm

算法中变量的定义为：

S：自体串；N：非自体串；R：检测器集合；R0：候选检测器集合；NR0：R0的规模；

Ns：自体集规模；NR：检测器规模；r：匹配长度；m：位串的字母大小；l：位串长度；

Pm：任意两个字符串匹配的概率；

Pf：任意一个非自体串不能被R中NR个检测器所匹配的概率，又称为漏检概率。

f：任意随机字符串与自体集合中的Ns个字符串都不匹配的概率。

算法中的候选检测器是随机生成的，该算法初始检测集合的大小N与自体集S的大小呈指数关系，即

2 否定选择算法的改进

2.1 相关定义

定义1 r-连续位匹配规则（r_continuous bits）如果字符串x和y至少连续r位相同，则它们满足r-连续位匹配，或称之为匹配成功。r称之为秩。

例如符号表为{0，1} x：0110100101

y：1110111101

当r≤4时，x和y匹配成功。定义2匹配概率

两个字符串匹配的总概率

pm=（1-1/m）*m-r*（l-r）+m-r（m-r<<1）其中，m为字母表长度，l为串长，r为秩。由此可见，对于r-连续位匹配规则，如果给定m和l，其匹配概率Pm是确定的。

2.2 NSA的改进

在传统的NSA中，生成的检测器中必然存在重复与冗余。这是由于候选检测器是随机生成的。同时，通过免疫耐受的候选检测器之间有可能互相匹配，即它们均包含某个长度为r的子串，而这些互相匹配的检测器只需其中之一进入成熟检测器集合即可。因此，在系统资源有限并且只能生成特定数量的检测器集合的情况下，传统否定选择算法生成的检测器必然会降低对非自体空间的覆盖率。

基于此，否定选择算法的改进是当今研究热点。例如，文献[3]提出了基于混沌理论的混合否定选择算法，文献[4]使用检测器半径可变的方法改进否定选择算法，文献[5]分别提出了实值否定选择算法。本文分析了传统NSA算法不足的产生原因，提出对免疫耐受的检测器进行重复的多次筛选的方法。考虑到时间成本，将第一次筛选得到的检测器再进行一次与成熟检测器集合的匹配检查，筛选出与已有检测器集合不匹配的元素，以提高检测器的整体覆盖率。算法流程图如图2所示。

图2 二次筛选的NSAFig.2 Screens twice-NSA

2.3 实验及其分析

实验中模拟系统使用r-连续位匹配规则（r_continuous bits）[6]，分别用传统的否定选择算法和改进后的否定选择算法产生同等规模的检测器集合，使用相同的匹配阈值比较检测器的整体覆盖率。设两个算法分别产生的检测器集合为Ra和Rb，成熟检测器的生成采用穷举法。算法具体步骤如下：

Procedure Improve_NSA

begin

初始化各种参数：串长l，匹配阈值r，检测器的数量n；

构造长为l的模式空间作为自体集合S；

while（Ra规模

{

随机产生候选位串p；

if（p 与 S 匹配）

{丢弃 p； continue；}

else将 p加入 Ra；

if（p 与 Ra不匹配）

将 p加入 Rb；

}

end

对于生成的检测器集合Ra和Rb，分别记录它们对于给定的非我集合的空间覆盖率及检测时间。取l=16，r=9时，结果如图4所示，其中‘*’表示改进前算法生成的检测器，‘+’表示改进后算法生成的检测器：

图3 两种算法总执行时间和覆盖率的比较Fig.3 Comparison of two algorithms in execution timeand coverage rate

由图3可见，检测器Rb的覆盖率比Ra有明显提高，检测器的分布也更均匀。

2.4 改进算法在入侵监测模型中的应用

模拟生物免疫系统的相关运行机制，构建一个基于免疫机理的网络入侵检测系统（Network IDS）模型[7]，模型的框架如图4所示。

分别将传统的NSA和改进的二次筛选的NSA应用于成熟检测器生成模块，检验其检测率和漏检率的变化。为保证实验数据的权威性和多样性，本文选用美国国防部高级研究计划局（DARPA）和麻省工学院（MIT）的林肯实验室共同推出的一批网络连接记录集KDD Cup 1999 Data[8]作为数据来源。实验测试数据集合具体组成如表1所示。

两种算法对应的检测效果如表2所示。其中，TP为正确检测率，即准确检测出非自体的概率；FP为错误检测率，表示

图4 基于免疫原理的入侵检测系统模型Fig.4 Immune IDSmodel

表1 测试集的组成Tab.1 Composition of the test sets

自体被错误检测成非自体的概率。

表2 两种算法检测率对比Tab.2 Comparison of two algorithm in detection rate

由此检测结果可见，由于降低了检测器的冗余度，改进的否定选择算法应用于基于免疫原理的IDS中可以有效提高系统的正确检测率，降低错误检测率。

3 结 论

采用筛选两次的否定选择算法，在自体集规模和检测器规模相同的条件下，可以生成覆盖率更高的检测器集合。改进算法可以降低成熟检测器的重复率和冗余率，从而有效提高检测器的正确检测率。改进算法的不足在于时间效率的降低，但是在现如今计算机硬件配置水平及运算速度十分理想的条件下，这种改进是有意义的。后续研究中应考虑进一步提高算法的时间效率。

[1]李涛.计算机免疫学[M].北京：电子工业出版社，2004．

[2]Forrest.S.Self-Nonself Discrimination in a Computer.Proceeding of 1994 IEEE Symposium on Research in Security and Privacy[M].Los Alamos.CA:IEEE Computer Society Press，1994．

[3]Aydin I，Karakose M，Akin E.Chaotic-based hybrid negative selection algorithm and its applications in fault and anomaly detection[J]．Expert Systems with Applications，2010，3（7）：5285-5294.

[4]伍海波.一种改进的否定选择算法在入侵检测中的应用[J].计算机应用与软件，2013，2（30）:174-176.WUHai-bo.Application of improved negative select algorithm in intrusion detection system[J].Computer Applications and Software，2013，2（30）:174-176.

[5]柴争义．用于异常检测的实值否定选择算法[J]．吉林大学学报，2012，42（1）:176-181．CHAI Zhen-yi.Real negative select algorithm in anomaly detection[J].JiLing University Journal，2012，42（1）:176-181．

[6]DASGUPTAA D，YUA S，NINO F.Recent advances in artificial immune systems:models and applications[J].Applied Soft Computing，2011（11）:1574-1587.

[7]陈岳兵.面向入侵检测的集成人工免疫系统[J].通信学报，2012，2（33）：126-131.CHEN Yue-bing.The integration of artificial immune system for intrusion detection[J].Communication Journal，2012，2（33）：126-131

[8]Lincoln Laboratory.Information Systems Technology[EB/OL].[2009-10-05]．http://www．ll．mit．edu/IST/ideval/data/1999/1999_data_in-dex.html．