基于遗传算法的入侵检测系统研究

摘要：随着科技进步和计算机网络技术的飞速发展，网络“黑客”的攻击手段越来越先进，信息安全问题也越来越突出。本文讨论了应用自适应遗传算法到网络入侵检测系统，包括入侵检测系统、遗传算法的简单介绍和相关的检测技术，详细论述了遗传算法在入侵检测系统中应用的具体过程，特别是染色体的构造以及交叉和突变两类算子的应用。通过研究我们发现将遗传算法应用于入侵检测有着广阔的前景。

关键词：遗传算法 入侵检测系统

一、引言

入侵检测系统（IDS）就是对网络或操作系统上的可疑行为做出策略反应，及时切断资料入侵源、记录、并通过各种途径通知网络管理员，最大幅度地保障系统安全，是防火墙的合理补充，帮助系统对付网络攻击，扩展系统管理员的安全管理能力（包括安全审计、监视、进攻识别和响应），提高信息安全基础结构的完整性，被认为是防火墙之后的第二道安全闸门。遗传算法已经采用了不同的方法应用到入侵检测系统中，使其具有智能性，这些研究还处于研究阶段。有人使用不同的机器学习技术，如限定状态机器、决策树和遗传算法来为入侵检测系统产生人工智能规则。

二、遗传算法

遗传算法（GA）是自适应启发性的搜索算法，以自然界选择和基因的进化思想为先决条件。GA的基本概念是设计模拟自然界进化的过程，特别是由达尔文的适者生存原则。我们通常采用的遗传算法的工作流程的结构形式是Goldberg在天然气管道控制优化应用中首先提出的，一般称为规范遗传算法（Canonical GA，CGA）或者标准遗传算法（Standard GA，SGA）。规范遗传算法的基本流程图如下：

遗传算法所涉及到的五大要素：参数编码、初始群体的设定、适应度函数的设计、遗传操作的设计和控制参数的设定。

遗传算法的运行过程为一个典型的迭代过程，它必须完成的工作内容和基本步骤如下：

1）选择编码策略，把参数集合X和域转换为位串结构空间S；

2）定义适应度函数F(x);

3）确定遗传策略，包括选择群体大小n，选择、交叉、变异方法，以及确定交叉概率、变异概率等遗传参数；

4）随机初始化生成群体；

5）计算群体中个串解码后的适应值 F(x)；

6）按照遗传策略，运用选择、交叉和变异算子作用于群体，形成下一代群体；

7）判断群体性能是否满足某一目标，或者已完成预定迭代次数，不满足则返回

步骤 6），或者修改遗传策略再返回步骤 6）。

三、遗传算法在入侵检测系统中的应用

（一）概述

遗传算法可以用来产生入侵检测系统的规则，这些规则是根据已知的网络连接构成的数据库来自动产生的。产生的规则用来区分正常的网络连接和异常的网络连接。异常的网络连接就是指可能的入侵活动。存储在规则库中的规则一般是以下形式：

if{condition}

then{act}

这里的条件通常是指当前网络连接和IDS中的规则是否匹配，比如源IP地址、目的IP地址、端口号等等。动作通常是指安全策略定义的对异常的反应，比如给系统管理员报警、将可能的入侵存入日志等等。

应用遗产算法的最终目的就是产生只匹配异常连接的规则。这些规则在历史网络连接上测试，并且应用在过滤新的网络连接上检测可能的入侵攻击。

在本文中所述实现中，历史数据是一个预先分好类的数据库，由正常的网络连接和异常的网络连接组成。这些数据可由网络嗅探器搜集，比如Tcpdump或者Snort等。搜集到的数据由标准的聚类算法进行智能分类，这个分类的数据库用来在遗传算法的运行过程中给确定染色体的适应度提供依据。这样，通过遗传算法，一个小的随机产生的规则集就会生成一个大的包含很多规则的集合给IDS使用。这些规则就是遗传算法的足够好的解，这些规则可以用来过滤新的网络连接。

（二）编码方案

为了准确发现入侵，我们应该对一个特定网络连接的所有部分进行检查。但通常为了简单起见，我们仅考虑每一个连接的一些明显属性。对于一个网络连接（TCP/IP协议类型）我们通常考虑下表的域。

if

{

一个网络连接有如下特征：

源IP地址d2.0f.**.**；

目标IP地址c0.a8.a*.**；

源端口号43226；

目标口号80；

持续时间482秒；

终止状态（连接由发起连接的人终止）11；

使用协议（TCP协议）2；

发送方发送了7341个字节；

接受方接受了37761个字节；

}

then

{

终止该连接；

}

可以将上面的例子转换为染色体编码的形式：

该染色体是一57维向量，共有57个基因，为了简单，我们用十六进制来表示IP地址。

这条规则的实际有效性可以通过匹配由正常连接和异常连接组成的数据集来验证。如果这条规则匹配了一个正常连接，该染色体就会得到一个处罚。很显然没有一个单一的规则就能够从正常连接中区分出所有的异常连接。种群需要不断的进化来发现理想的规则集。

表3-1所示的例子中使用了符号*，并且在染色体中的相应基因被显示为-1.这些符号被用于表示值的一定范围，它表示IP地址和端口号的一定范围时有用。一旦空间信息被包含在规则中，IDS的能力就会大大提升，因为一个攻击可以从许多不同的地方发起。把持续时间包含进染色体保证了时间信息与网络连接的结合。网络连接时间的最大值是9999999秒，这个值是一百多天。这对确定入侵非常有用，因为复杂的入侵可以跨越小时、天、甚至月。

（三）适应度函数的建立

对于遗传算法的应用，定义一个问题的解的适应度是最难的一个问题。在定义一个染色体的适应度之前，我们先来定义两个染色体对应的网络连接的匹配问题，也就是如何定义匹配。

（1）

用上式定义两个网络连接之间的匹配值。另外定义一个值match_threshold，当Outecome＞math_threshold时，就认为两个网络连接是匹配的。式中，Matched的取值为0或1，当对应匹配时取值为1，不匹配时取值为0。weight是不同域的权重。这样计算出的Outcome值的个数与数据集中染色体的个数相同，取其中最大的一个作为被考察连接的Outcome值。

公式中权值的顺序如下图所示：

这个顺序后面的基本思想是TCP/IP包中不同域的重要性不同。这种安排简单直接。目标IP地址是攻击的目标而源IP地址是攻击的发源地，这些是为了捕捉一个入侵最重要的信息。目标端口号显示了目标系统正在运行的程序（例如FTP服务通常运行于21号端口）。一些IP地址被攻击的可能性更大――例如军事领域的IP。其它的参数例如持续时间、发起者发送的字节数、接收者发送的字节数等的重要性通常低一些，但仍然比较有用。协议和源端口号通常不是必要的，一般用于确定一些特定的攻击。

本文中这样定义适应度值：

染色体对应的规则匹配的异常网络连接越多，染色体的适应度越大；

染色体对应的规则匹配的正常网络连接越多，染色体的适应度越小。

更准确的说，假设已知的分类的网络连接集合中有m个正常的网络连接，有n个异常的网络连接。令

(2)

其中Outcomei＞match_threshold，Ranking表示一条异常连接识别的难度。如果是较难识别的异常连接，Ranking值较大；反之，Ranking值较小。令

（3）

其中Outcomei＞match_threshold，其中的Ranking表示一条异常连接识别的难度。如果是较难识别的异常连接，Ranking值较小；反之，Ranking值较大。

用F表示一个染色体的适应度值，

F=Anomalouss-Normal

(4)

这样适应度高的染色体被加入到特征库中，从而实现了特征库的智能动态更新。

（四）交叉算子的应用

通过交叉操作可以在父代的基础上产生子代，然后在父代与子代组成的种群中根据适应度函数的大小选出下一代个体。在本文中采用了单点交叉，交叉点确定在目标IP地址的后面，即染色体中的第16位后。这样做的根据是：即使源IP地址与目标IP地址都变了，如果攻击手段相同，那么染色体后面的部分应该是类似的。所以用这种交叉方式有很大机率产生出适应度比较高的新染色体。具体实现方法如下：

设进行交叉操作的概率为Pm，那么种群中每次约有N・Pm个染色体进行交叉操作，其中N为种群大小。可以用下面的方法来确定交叉操作的父代：

for(int i=1;i＜=N;i++)

{

r=random();

if(r＜Pm) // r得到一个（0，1）之间的随机数

将Vi加入交叉操作的父代中； //Vi表示种群中的第i个染色体

}

对选择出的父代两两配对进行交叉操作，例如将Vi，Vj交叉后产生新染色体X，Y的方法为：

则

X=P1・Vi+P2・Vj

（5）

Y=P1・Vj+P2・Vi

（6）

（五）突变算子的应用

突变算子通常一次只改变一个染色体上的一个基因，一般认为，突变算子的重要性次于交换算子，但起作用不容忽视，通过突变可以产生仅通过选择和交叉无法产生的最优解。在本系统中突变操作是如下进行的：

设发生突变的概率为Pn，这个概率表明种群中每次约有N・Pn个染色体进行突变操作。首先要产生出进行突变操作的父代，产生方法类似交叉操作。用V表示要进行突变操作的任一父代染色体，可以用下面方法产生突变后的新染色体X：

X=V+M・d

（7）

式中d为与染色体同维数的向量，它表示随机产生的变异方向，形式为d=（0，0，……，0，1，0，……，0）。d中1所在的位置就是染色体V中要发生突变的位置。M为一个[0，F]之间的随机数，如果这样得出的X不符合表中取值范围的要求，可以将M置为[0，M]之间的一个随机数，然后继续用公式（7）计算，直到得出符合要求的X为止。最后用变异产生的染色体X代替原种群中的染色体V。

在遗传算法中还有其它一些需要考虑的参数，如种群大小、交叉率、突变率、进化代数等。这些参数可以根据系统的规模大小和机构的安全策略进行调整。

四、结论

我们发现自适应遗传算法收敛的非常快。因为时间在实时过程中是个非常重要的因素，和一系列的规则引导适应度函数，在我们事件中，收敛速度快是我们需要的。这结果显示自适应遗传算法已经发现了一种好的解决方法，所以对入侵检测来说，它能够作为一个优秀的数据分析器出色地工作。

自适应遗传算法要达到入侵检测的目的则需要更多更深入的测试。在遗传算法中，参数的详细信息该通过试验决定。通过使用自适应遗传算法为基础的数据分析器，我们能够发展为其他各种攻击使用该分析器。先进的系统将实行实时监控、分析和对入侵行为产生合适的反应。

[参考文献]

[1] J P puter Security Threat Monitoring and Surveillance.[R] James P.Anderson Co.,Fort Washington,1980.

[2] Dass M., J.Cannady and W.D.Potter to appear in the digital proceedings of the 41st ACM Sowtheast Conference, Savannah, March 7-8,2003.

[3] Wei Li, Using Genetic Algorithm for Network Intrusion Detection[J]. Proceedings of the United States Department of Energy Cyber Security Group 2004.

[4] 任庆生，叶中行等. 遗传算法中常用算子的分析[J]. 电子学报. 2000;5:113~114.

[5] B.D. Davison, H. Hirsh , Experiment in UNIX command prediction[C], Proceedings of the 14th National Conference on Artificial Intelligence, Rhodes Island, USA, April 1999.

[6]戴英侠，连一峰等编著.系统安全与入侵检测.清华大学出版社.2002，P6-9，P15.P24-25.

[7] S. E. Smaha. Haystack: An Intrusion Detection Systerm. Orlando ed .In Proceedings of the IEEE Fourth Aerospace Computer Security Applications Conference, Washington: IEEE Computer Society Press, December 1988: P37-44.

[8]李德全.冯登国著.AHost-BasedAnomaly Intrusion Detection Model Based On Genetic Programming, 软件学报，2003.14 P1120-1124.

[9]陈云芳.王汝传等著.基于用户行为分析的入侵检测应用模型的研究.微机发展.2004，12：P122－124.

[10] 徐小龙，王文国. 纵论新一代入侵检测系统[J]. 科技信息. 2005; 2:14~15.