改进的遗传算法在入侵检测中的应用

魏德志林丽娜吴旭

（集美大学 诚毅学院，福建 厦门 361021）

0 引 言

计算机网络安全、信息安全已经成为一个国际性的问题，每年全球因计算机网络的安全问题而造成的经济损失高达 数百亿美元，而且这个数字每年都在增加。检测与防范入侵攻击，保障计算机系统、网络系统及整个信息基础设施的安全已经成为刻不容缓的重要课题。

近几年来入侵检测技术得到了飞速的发展，不断有新的方法和技术出现，主要的创新包括：Forrest等将免疫原理运用到分布式入侵检测领域[1]；Supeled将基因算法作为检测方法而设计得GASSATA系统[2]；Wenke Lee将数据挖掘的技术用到入侵检测中[3][4]。

受以上研究得启发，本文先采用改进的遗传算法，把关联规则应用在遗传算法的适应度函数的设计上。经过试验比较最终得出了混合算法具有较好检测效果的结论。

1.进的遗传算法的入侵检测模型

遗传算法利用了生物进化和遗传的思想，将它应用于入侵检测规则发现中与传统方法具有不同的特征：首先，它的处理对象是问题参数的编码集，而不是参数本身；其次，遗传算法在搜索空间中同时对很多点进行求解，这样就减小了收敛于局部最小的可能，增强了鲁棒性，同时也增加了处理的并行性。我们把关联规则引入遗传算法，可以实现入侵检测系统的进一步优化。在遗传算法中，通过适应度函数来确定个体的性质，而关联规则则是通过支持度、可信度和兴趣度来确定事物之间的关系，为此，我们可以把支持度、可信度和兴趣度用于遗传算法的适应度函数的构造，以实现两种算法的结合，达到共同寻求最优解的目的。

1.1.进遗传算法的概述

基于主机的入侵检测系统和基于网络的入侵检测系统各有优缺点，本文的入侵检测算法主要是用于基于主机的入侵检测系统。

一般的入侵检测模型主要包含四个个模块：事件产生器、事件分析器、事件数据库和响应单元。其中事件分析器利用主机的审计数据，产生一组用于检测的规则：在入侵检测阶段，则是利用这些规则来实时检测系统，规则产生后检测是简单和低开销的。因此入侵检测模型最主要的工作是如何生成有效的的规则库。

1.2.进遗传算法的染色体编码的设计

网络的行为都可以通过一些特征来表示，例如：源地址、目的地址、源端口号、目的端口号、协议类型以及连接时间长度等等，这些都可以表现网络行为和网络所能提供的服务等等。每一条入侵检测规则是一个“if-then”的形式，其中包含条件和结果，网络特征属性用逻辑符号“AND”连接，构成规则的条件部分，特征IsAttack是作为结果的，表示是否为攻击，下面显示了一个规则的形式，其中的字符串只是为了显示意义，在实际应用中将用例值代替。

If (Duration= "ANY" and Protocol_ype= "TCP" and Service=“telnet” and Flag= "ANY" and

Logged_in=false and Count=0 and Hot=” ANY” and Num_root=” ANY” Num_access_files=” ANY” Svr Count=0 and Serror rate="ANY”) then (IsAttack=“buffer_ overflow”)

上面的规则表示:如果协议类型为TCP并且服务类型为Telnet并且没有成功登陆并且在2秒内登陆同一主机的连接数和在2秒内对同一服务的连接数均为0，则该连接可能为缓冲区溢出攻击。以上仅仅是一个示例，并非真正的规则，真正的规则将在训练后系统自动给出。

为了使规则更有通用性，我们允许在网络特征表示中使用通配符，我们将通配符设置为#。则上面的例子用染色体向量表示为：{#, 1, 12,#, 0, 0, ,#, ,#, ,#,0, #, 12}

本文采用二进制编码来表示关联规则假定所有的特征属性和类别属性的取值是离散的(对于连续型的值先做离散化处理)并且取值范围已知，对每个属性的每一个取值用一个合适长度的二进制串来表示，每个二进制串代表一个基因，将所有属性值的二进制串连接在一起得到一个二进制串作为一个染色体，代表一个关联规则。

1.3.进遗传算法的适应度函数的设计

关联规则挖掘的任务就是要发现能够反映记录属性之间的关联或者是关系，这些规则应该具有一定的支持度、可信度和兴趣度。我们从支持度、可信度、兴趣度三个方面来综合评价一条规则的“好坏”，在进化的过程中，让越“好”的规则获得越高的适应度值，使其在选择竞争中获得更大的生存和交叉的机会。为了定义规则的适应度，我们采用支持度、可信度、兴趣度适应度函数，如果一条规则表示为：if X then Y，那么规则的适应度函数定义为：

S=support( X ⇒ Y )= P (X∪ Y )=|X and Y |/N

C=confidence( X ⇒ Y )=P ( Y/X)=|X and Y |/|X|

I=interest( X ⇒ Y )=log( P ( Y/X)/ P (YnotX))

定义适应度函数为：Fitness= a *S+ b* C+c* I

其中N是训练数据的总数，|X|代表训练数据中满足条件X的数据的数量，|X and Y |代表形如if X then Y的规则中满足条件X和结果Y的数据的数量。a，b，c是用来平衡三项的权值，其中：a,b,c为常数且0≤a,b, c≤1；S为规则支持度；C为规则的可信度； I为规则的兴趣度。a，b，c的值由用户根据需要调整，从而对规则评价的偏重方面可以发生变化，使进化沿着用户期望的方向进行。缺省值为：a=0.2，b=0.6，c=0.2。

1.4.进遗传算法的遗传操作的设计

遗传操作[5]主要包括选择、交叉和变异。

本文选择采用锦标赛选择算法，其基本思想是每次选取几个个体之中最高的一个个体遗传到下一代群体。由于本文的检测器采用二进制编码形式，因此交叉操作采用二进制均匀交叉的方式，其基本思想是对两个配对的个体的每一个基因位上的基因都以相同的交叉概率进行交换，从而形成两个新的个体。变异方式有实值变异和二进制变异两种，本文采用二进制变异方式，随机选取个体的某个基因位进行翻转。

1.5.进遗传算法的描述

首先利用数据挖掘属性相关分析获取信息量较大的特征属性，根据这些特征属性生成初始的种群，设置缺省参数，然后读入主机的训练数据。初始的种群需要经过若干代的进化，在每一代的进化过程中，首先计算每一个规则的适应度函数，根据适应度函数的大小来选择最适合的规则，而最终的GA的操作如变异、交叉等就施加于该选择的种群上以生成下一代的种群。

下面显示了混合算法的伪代码：

算法：利用混合算法生成检测规则

输入：网络的审计数据，本文采用Kddcup 99的训练数据

输出：一组检测规则

1.输入检测数据

2.随机初试化初试种群；

3.a=0.2；b=0.6；c=0.2；t=0.5；

4.N=训练数据集的记录数；

5.For种群中的每一个染色体{

6. X=0；XY=0

7. For训练数据集合中的每一个数据记录{

8. If当前的数据记录匹配当前染色体{

9. XY++；

10. }

11. If当前的数据记录只匹配条件{

12. X++；

13. }

14.Fitness=a*XY/N+b*XY/X+c*log( P ( Y/X)/ P (YnotX))；

15.IfFitness>T{

16.选择该染色体进入下一代的种群；

17. }

18.For 在新种群中的每一个染色体{

19. 应用遗传算法中的交叉获得新染色体加入该种群；

20. 应用遗传算法中的变异获得新染色体加入该种群；

21. }

22.如果进化代数还未到，goto 5；

23.结束。

1.6.进入侵检测算法的实现

本文的入侵检测系统是基于主机的，开发工具采用Microsoft Visual Studio.NET2005，开发语言主要有J#。训练数据和测试数据均采用了KDDCUP99的数据。入侵检测系统的实现是建立在第三方的软件开发包 ECJ[6]之上的。ECJ是由乔治梅森大学George Manson大学的ECLab开发和维护的完整的GA/GP的Java开发包，这个开发包提供了丰富的一组GA基础类库。我们通过调用ECJ的类库，实现了两个功能：1)离线的数据训练系统，利用历史数据(KDDCUP99)来推导出判断规则；2)利用推导出的规则在线实时检测网络系统中可能存在的攻击。

2.验及结果分析

本文的硬件实验环境为：Dell服务器PowerEdge 840，至强双核处理器 1.86G，4G内存；软件环境为：操作系统Windows Advance Server 2000，数据库SQL2005，开发工具Microsoft Visual Studio.NET2005。实验采用10%的训练数据来进行规则推导，改进算法的适应度函数我们用前面使用的支持度、可信度、兴趣度适应度函数，染色体采用经过属性选择完的编码，改进算法的参数a=0.2，b=0.6，c=0.2，一共训练迭代3000次，初始的染色体种群数量为500个，交叉的概率取值为0. 5，变异的概率取值为0. 02，训练结束时头20条质量最好的规则作为最终的检测规则，这些规则用来检测训练数据。同时进行遗传算法和关联算法试验，进行对比。具体试验结果见图。

三种算法检测效果图

从图标中我们可以看出改进算法在三种算法当中，它的检测率最高，误报率最低，但建规则库所需要的时间也最长。

3.束语

入侵检测目前最大的困难就是数据量大，用户的行为特征的准确描述比较困难。通过前面的试验分析讨论，改进遗传算法在入侵检测上具有较好的效果，但还有一些缺点，在建规则库所需要的时间也最长，这个是将来要改进的地方，进一步提高算法的运行速度。

[1]Forrest S,Hofmeyr S,Somayaji A.A sense of self for unix processes[A].In Proceedings of the 1996 IEEE symposium on Security and Privacy,Los Alamitos,CA 1996 IEEE Computer Society Press: 120-128.

[2]Me L.Genetic Algorithms,a biologically inspired approach for security audit trails analysis[J].short paper,presented at the 1996 IEEE Symposium on Security and Privacy,Oakland,CA, 1996.

[3]Lee W Stolfo S.Mining in a data-flow environment:Experienceinnetworkintrusiondetection[A].In:Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery&Data Mining(KDD-99)[C].1999:186-192.

[4]Lee W Stolfo S.Mining audit data to build intrusion detection models[A].In:Proceedings of the 4th International ConferenceonKnowledgeDiscoveryandData Mining[C].New York,NY,AAAI Press,1998.

[5]ECLab : Computation Fairfax, VA, 2004. evolutionary Computation laboratory,A Java-based Evolutionary(ECJ)and Genetic Programming Research System,George Mason University,USA,http://cs.gmu.edu/eclab/projects/ecj/(access ed in November 2007).

[6]王小明,曹立明.遗传算法——理论、应用与软件实现[M].

西安:西安交通大学出版社,2002.