基于人工免疫的入侵检测系统研究与实现

[摘要] 网络入侵检测系统（IDS）是保障网络安全的有效手段，但目前的入侵检测系统仍不能有效识别新型攻击。应用人工免疫的原理，设计一种新的基于免疫的入侵检测系统。针对目前免疫算法的不足，设计了一个K分字符串匹配算法，使检测效率大大提高。实验结果表明，该系统在识别新型攻击上具有较好的性能。

[关键词] 人工免疫 编辑距离 网络安全 入侵检测

一、引言

入侵检测是网络安全的重要研究领域，主要有误用检测（misuse detection）和异常检测(anomaly detection)两类技术。其中，误用检测是根据已知的攻击特征建立一个特征库，然后将网络采集的数据与特征库征进行一一匹配，若存在匹配的特征，则表明其是一个入侵行为。而异常检测则是将用户正常的行为特征存储在特征数据库中，然后将用户当前行为与特征库中的特征进行比较，若偏离达到了一定程度，则说明发生了异常。这两种技术各有优缺点，误用检测能够准确检测到已知攻击事例，但对新型攻击行为却无能为力；异常检测可以检测到新型攻击，其误检率却比较高，且不能描述入侵行为的类别。

免疫系统是生物体信息处理系统的重要组成部分，肩负着保护机体安全的重任。它实质上是一个大规模的分布式信息处理系统，具有识别自我与非我、学习、记忆和模式识别等重要处理机制。免疫系统由许多执行免疫功能的器官、细胞、分子等组成，能将体内的细胞或分子区分为属于自体的种类和外部来源的非自体种类。

为了使入侵检测系统能检测到新型攻击，人们进行了大量的研究工作。而入侵检测系统与免疫系统有许多相似之处，它们都肩负着维护自身安全的使命，同样要对新的信息辨别是“自我”还是“非我”。因此模拟免疫系统特征，将人工免疫技术应用到入侵检测系统，是最近比较热点的研究方向。

二、人工免疫的生物学原理

免疫系统是一个极其复杂且协调周密的系统，它由具有免疫功能的器官、组织、细胞、免疫效应分子和有关的基因组成。淋巴细胞是免疫系统中最重要的一种细胞，它作为独立的“检测器”分布在体内淋巴系统中，主要由B细胞和T细胞组成。T细胞在胸腺中发育成熟，在免疫过程中起着协调的作用；B细胞则在骨髓中发育成熟，通过其表面的抗体识别特定的抗原，并与抗原结合将其消灭。

免疫系统的主要功能有：免疫防御、免疫自稳与免疫监视。其中免疫防御主要是抵抗病原体的入侵，免疫自稳维护内环境的相对稳定，免疫监视则消灭突变细胞。免疫系统的核心是免疫应答。在识别过程中，免疫系统对自身的抗原不产生免疫应答，对外来的抗原则应答并将其清除。克隆选择和否定选择也是抗体生成和深化过程中的两个重要过程。当抗原进入个体时，带有该抗原受体的淋巴细胞搜寻并结合抗原，激发增殖和分化，产生抗原特异细胞的克隆。否定选择则是机体内先产生大量随机抗体，把对“自身”抗原特质产生破坏的清除出去，以免对自身造成伤害，剩余的抗体可以检测外来物质。另外，免疫系统还具有免疫记忆功能，免疫系统将与侵入抗原反应的抗体作为记忆细胞保留下来，当有同类抗原再次侵入时，相应的记忆细胞会被激活，并产生大量的抗体，从面缩短了免疫反应的时间。

三、基于人工免疫的入侵检测模型

人工免疫系统是生物免疫系统的模拟，它具有抗噪、自主学习、自组织等特性，能够很清晰地表达学习的知识，同时结合了分类器、人工神经网络、机器学习等系统的优点。

1.人工免疫算法流程

我们将入侵检测系统模拟成生物免疫系统，把进入计算机系统的数据视为抗原。根据免疫系统的理论，为了检测出抗原是“自我”还是“非我”，需要系统生成大量的抗体。进入计算机系统的数据都是二进制字符串，所以采用固定长度的字符串表示抗体。我们设计了两种产生抗体的方法，一种在实时检测过程中生成，另一种为随机产生。其中随机产生抗体的过程即为接种疫苗的过程。其人工免疫算法流程如图1所示。

从流程图中可以看出，抗体随机产生后，先要进行否定选择，把对自身产生伤害的抗体清除。满足条件的抗体加入疫苗模式集中。检测过程中将疫苗库中的疫苗与实时抗原结合，若有匹配的抗原则报警。如果此警报为一攻击行为，则将此抗体加入抗体库中；反之则从疫苗库中删除。

2.入侵检测系统模型

目前已经有很多研究人员将免疫理论应用到入侵检测系统当中，但很多只是考虑网络数据包的包头数据，丢弃了包含重要信息的数据包负载部分，从而造成很高的漏报率。为此，我们使用tcpdump截获网络数据包，对整个数据包进行匹配检查。先将系统在正常网络流量下运行一段时间，对检测系统进行训练。训练时期截获的数据包均为正常数据，我们把它存入“自身”数据库中。入侵检测系统的模型如图2所示。

入侵检测模型的左边部分是训练过程。其中训练数据是不含攻击行为的学习数据，此数据全部存入“自身”库中。经过一段时间正常数据的学习之后，就可以通过与库中的数据进行比较生成疫苗。

抗体库在检测过程中不断地更新完善，使系统能检测各类新型攻击。自身产生抗体的方法如图1中所述，此方法模拟免疫系统的否定选择，对新型攻击的检测有一定的效果。另一种产生抗体的方法是，将网络上截获的数据包与“自身”库中的数据比较，跟库中数据不匹配的则认为是异已抗原，将其加入到疫苗库中。疫苗库中的数据都是与自身正常数据相偏离的，有可能是新型攻击的特征数据。

系统模型的右边部分是实时检测模块。首先将网络实时数据与疫苗库中的数据进行比较，若两数据相似，则初步判断为入侵，并向管理员报警。此警报若为误报，则说明与之匹配的疫苗不合格，将其从疫苗库中清除。警报若被确认为攻击行为，则接种此疫苗，将其加入抗体库。抗体库中的数据均为已确认的攻击数据，与之匹配的数据可判断为入侵。

该系统是自适应入侵检测系统。系统在运行过程中，对抗体库不断地接种疫苗，使系统对各种已知攻击和新型攻击都具有免疫能力。

四、K分字符串相似匹配算法

人工免疫系统中抗体与抗原的结合表现为字符串的匹配，但这种匹配跟一般的字符串匹配不同。抗原与抗体中的字符相似个数超过一定数目，我们就可以认为它与抗体相匹配，所以它并不是完全匹配。有很多人工免疫系统使用KMP算法进行匹配，其具有匹配指针不需回朔的优点，但其对串的匹配是精确匹配，在近似匹配方面效果不是很好。

由于系统频繁进行字符串的匹配操作，所以匹配算法的效率对系统至关重要。本文通过计算两字符串的编辑距离确定其相似度。当编辑距离小于设定的阈值，则认为两字符串是相似的。两字符串S1与S2的编辑距离定义为：将S2转换为S1所需最小数目的单元操作，其中单元操作包括字符的插入、删除、替换，及相邻字符的调换等。例如，字符串“allover”与“all over”之间很相似，只要进行一次删除空格的操作就完全相同，所以它们间的编辑的距离为1。

由编辑距离的定义可知，字符串间的编辑距离有两个基本性质：

distance(‘’,‘’) = 0（1）

distance(‘’,S) = |S| 其中|S|为字符串S的长度（2）

对于任意字符串S1和S2，假设|S1|=m、|S2|=n，我们使用矩阵（二维数组）M[m,n]计算它们的编辑距离。其中M[i,j] = distance(S1[1..i],S2[1..j])，因此

M[0,0]=0,

M[i,0] =i， i=1..|S1|

M[0,j] =j， j=1..|S2|

编辑距离的C语言算法描述为：

distance(S1,S2)

{

for(int i=1；i

M[i,0]=i；

for(int j=1；j

if(i==1)

M[0,j]=j；

M[i,j]=min(min(M[i-1,j]+1,M[i,j-1]+1),M[i-1,j-1] +(S1[i]==S2[j])?0:1)；

}

}

return M[m,n];

}

算法的时间复杂度为O（m*n），当|S1|=|S2|时，复杂度为O（n2）。当n的值比较大时，计算的开销也非常大。为了提高检测系统的性能，我们把需匹配的抗体与抗原都分割为K个子串。按顺序分别对这K个子串进行匹配，串S1、S2间新的距离函数定义为：

字符串分割处理后匹配的速度大为提高，还保留了更多的字符顺序信息，使得近似匹配的结果更为科学。

五、实验及结果

我们实验的数据选自KDD CUP 1999有关网络入侵的数据集，该数据集有近500万条活动事件记录数据对象，每条数据在连接记录上标记为正常或一种特定类型的攻击（总共37种不同攻击类型）。共有43个属性特征用来描述这些网络连接事件，包括连接时间、协议类型、传输字节数、文件创建和失败登录次数等属性。

首先将入侵检测系统在安全网络流量中学习，使“自身”库发育完善。系统在训练过程中将逐步产生抗体。实验对每一种攻击类型进行试验，其中每种类型使用10条记录试验，实验结果如图3所示。

检测系统在运行过程中不断地自我完善，对新型攻击的检测准确也在不断地提高。通过调整字符串相似的阈值还可以提高检测率，但误报率也会相应地提高。

六、结论

基于人工免疫的入侵检测系统具有很好的准确性、完整性、可扩展性、可适应性和自身的健壮性，具备了免疫系统各种优点，是检测新型攻击很好的方法。本文提出的基于人工免疫的检测系统模型和字符串近似匹配算法，解决了检测新型攻击的一些难题。实验结果表明，其具有较高的检测率和较好的运行效率。

参考文献:

[1]焦李成杜海峰:人工免疫系统进展与展望.电子学报, Vol.31 No.10 Oct.2003

[2]宫新保周希朗:一种新型的网络安全技术――人工免疫系统.电气电子教学学报，Vol.25No.3 Jun.2003

[3]杨向荣沈钓毅刘强:基于人工免疫原理的NIDS系统和有关算法设计.小型微型计算机系统，Vol.25 No.3 Mar.2004

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。