基于遗传算法的网络入侵检测技术分析与研究

0引言

随着Internet的普及，许多企业将大量日常事务的处理转移到Web中进行，Web的开放性和资源的共享性，极大地方便了使用者，大大提高了企业的工作效率和工作质量；同时，由于数据存储的网络化，对系统的安全性也提出了更高的要求。因此，访问控制是保证系统安全必不可少的一个环节。传统的web访问控制通常和防火墙技术结合，利用防火墙技术，能够在内之间提供安全的网络保护，降低网络安全的风险；但防火墙背后可能有敞开的后门、不能阻止内部袭击以及不能防范病毒。所以，传统的web访问控制不能有效地保证网络的安全，入侵检测系统（Intrusion Detection System）是在这种背景下因运而生的新型网络安全技术。它可以和访问控制结合在一起，弥补防火墙的不足，为访问控制系统提供实时的入侵检测并采取相应的防护措施[1]。

本文介绍了一种基于遗传算法的入侵检测步骤，使用这种入侵检测技术能有效地提高网络系统的访问安全性。

1遗传算法的主要步骤

一般的遗传算法包括下面的步骤：①编码：GA在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同的组合便构成了不同的点。②初始种群的生成：随机产生N个初始串结构数据，每个串结构数据称为一个个体，N个个体构成了一个群体。GA以这N个串结构数据作为初始点开始迭代。③适应性值评估检测：适应性函数表明或解的优劣性。对于不同的问题，适应性函数的定义方式也不同。④选择：选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。遗传算法通过选择过程体现这一思想，进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。选择实现了达尔文的适者生存的原则。⑤交叉：交叉操作是遗传算法中最主要的遗传操作。通过交叉操作可以得到新一代个体，新个体组合了其父辈个体的特性。交叉体现了信息交换的思想。⑥变异：变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机地改变串结构数据中的某个串的值。同生物界一样，GA中变异发生的概率很低，通常取值在0.001~0.01之间。变异为新个体的产生提供了机会。

实际上，遗传算法有两类运算：

遗传运算：交叉和变异；进化运算：选择。

遗传算法模拟了基因在每一代中创造新后代的繁殖过程，进化运算则是种群迭代更新的过程。交叉是最主要的遗传运算，它同时对两个染色体操作，组合两者的特性产生新的后代。交叉的最简单方法是在双亲（两个父辈的个体）的染色体上随机地选择一个断点，将断点的右端互相交换，从而形成两个新的后代。这种方法对于二进制表示最为合适。遗传算法的进化功能在很大程度上取决于采用的交叉运算的性能。变异则是一种基本运算，他在染色体上自发地产生随机的变化。一种简单的变异方法是替换一个或多个基因。在遗传算法中，变异可以提供初始种群不含有的基因，或找回选择过程丢失的基因，为种群提供新的内容。

2基于遗传算法的入侵路径的检测

2.1染色体编码简单的入侵检测主要包括3部分：捕捉数据，分析数据，并且做出反映。因为分析引擎的需要和入侵检测问题的复杂性，根据强大的启发式搜索系统设计了网络入侵数据分析引擎：改进遗传算法，需要用Winpcap(Windows Packet Capture)来从计算机连接的网络中捕获大量的数据包，以收集足够的历史数据，包括正常和异常的网络数据，这些数据通过嗅探器分析，经过改进遗传算法数据分析引擎产生规则这些规则被存储在规则库中，入侵检测可以随时使用。遗传算法能产生针对网路流量的简单规则。

这些规则能转换为遗传算法的染色体。染色体编码有二进制编码和符号编码等形式，实数编码是符号的特例。由于在入侵检测中选择算法中的基因是网络中的节点，而这些节点正好是我们要检测的入侵路径，所以我在本文中采取的是实数编码方式[4]。

我们知道，染色体中的基因由两个因素表征：基因点，在染色体结构中基因所处的位置；基因值：基因携带的值。基因的位置可以代表网络中的节点，基因值代表候选网络节点作为入侵路径的权值的大小。这种编码就是权值编码。对应于给定的染色体的入侵路径有一系列始于网络节点1终于网络节点n的相继节点组成。在每一步中，通常有几个网络节点，但只有权值最高的节点加入入侵路径中。

我们可以考虑将一个网络转换为一个无向图。假设我们要寻求的入侵路径在网络节点1到网络节点10之间的路径。开始，我们试图寻找与网络节点1的下一个网络节点，然后判断其是否可能为入侵路径中的节点，在这个过程中发现，网络节点2和3都是合适的，因为它们的入侵权值分别为3和4，网络节点4具有更高的入侵权值，因此网络节点4被纳入到入侵路径中。然后我们得到了下一位的可行节点集，从中选择入侵权值更高的一条。重复这些步骤，直到得到一套完整的入侵路径（1，3，6，7，8，10）。

那我们的入侵权值是如何确定的呢？我们还是以n个节点的网络为例。令是包含1到n的整数集合，即Ω={1，2，…，n}；p i表示节点i的入侵权值，它是一个Ω重的随机整数。所以节点的入侵权值满足下列条件：

p

i

≠p

j

，p

i

，p

j

∈Ω，i≠j，i，j=1，2，…，n（1）因而，基于入侵权值的编码形式上可以定义为：

[p

1

，p

2

，…，p

n

]

但实际上，编码与入侵路径之间的映射是多对一的，这意味着不同的染色体可能对应着同一条入侵路径。但是很容易证明出现多对一的概率是很低的。因此，大多数的情况下，不存在有编码相关的无关重要的遗传操作。也很容易证明：任何顺序的编码对应着一条入侵路径。因此，绝大多数已有的遗传操作可以轻易地在这种编码

基于遗传算法的网络入侵检测技术分析与研究The Analysis and Research of Network Invasion Examination Technology Based on Genetic Algorithm

吴金炎Wu Jinyan

（福建教育学院信息技术研修部，福州350025）

（Fujian Institute of Education Information Technology Research Department，Fuzhou350025，China）摘要：随着互联网规模的日益扩大，网络安全问题也变得越来越尖锐。如何提高网络入侵检测技术也变为一个业界重点课题。本文主要分

析了遗传算法在网络入侵检测中的应用。

Abstract：As the Internet scale,network security issues are also becoming more acute.How to improve the network intrusion detection technology has become a key topic in the IT field.This article provides an analysis of the genetic algorithm in network intrusion detection.

关键词：遗传算法；入侵检测；染色体

Key words：genetic algorithm；invasion examination；chromosome

中图分类号：TP391文献标识码：A文章编号：1006-4311（2010）22-0145-02

——

——

——

——

——

——

——

——

——

——

——

—

作者简介：吴金炎（1976-），男，福建诏安人，计算机科学与技术硕士研究生，

讲师。

·145·价值工程上运行。同样，任何一条入侵路径拥有相应的编码。因此，遗传搜索

能到达解空间中的任意一点[5]。

2.2适应度函数的定义入侵路径选择算法的目的是找到一个

给定网络的任意两个网络节点之间可能的入侵路径，并将其屏蔽。

我们用一个大于网络中所有连通节点的权值和的数MAX表示不连

通的节点之间的路阻。定义g为从节点O到节点D所经过的路段

的路阻之和：g=Σd（v i，v j）

入侵路径选择算法的目的是要求得网络节点对间所有路径中

目标函数函数值最小的路径，即我们找到的最可能的一条入侵路

径。

2.3染色体解码成入侵路径我们这里的入侵路径是由染色体

产生的，所以就要用到一个概念。路径生长（Path Growth）过程。这一

过程的基本思想是：通过不断地添加符合条件的边到入侵路径中，

产生从初始节点1到n的路径。在每一步中，通常有几条边可供参

考。添加到局部入侵路径中的边始终是与当前节点相连接的具有最

高优先权节点的边，这就从端点延长了局部路径。这其中有一个非

常棘手的问题，就是找到一个合格的边集。

我们可以令G=（V，E）是定义在E上的具有实数赋权的连通无

向图。P k

t

是在生长中的局部路径，它包含k+1个节点，以t为端点。

如果一条边可以延长路径，但不与P k

t

中的边构成回路，则这条边对

于路径是合格的。

令V

p ∈V是局部路径P k

t

中的节点集合，V

q

=V-V

p

是V

p

的补

集，令C（V

p ，V

q

）={（i，j）襔i∈V

p

，j∈V

q

}是图的割集，T

t

={（t，j）襔j∈

V}是与端点t相关联的边的集合。对于给定的局部路径P k

t

，合格边集如下给出：

E qt =T

t

∩C（V

p

，V

q

）（2）

现在，我们考虑如何寻找E

qt

集，对于连通无向图G=（V，E），邻接矩阵A是如下定义的n×n矩阵：

a ij =

1，如果（i，j）∈E

0，其

∩

他

（3）

对于给定局部路径P k

t

，可以定义如下的网络矩阵M（k）：

m

ij =

0，如果i∈V，坌j∈V

p

1，其

∩

他

（4）

然后对于给定的局部路径P k

t

，可以定义新的邻接矩阵A（k）。

对于给定的局部路径P k

t

的动态邻接矩阵A（k）由下面的布尔矩阵交集给出：

A（k）=A∩M（k）（5）

我们将看到动态邻接矩阵A（k）移去了所有与局部路径P k

t

上的

节点相关联的边。也就是说，它仅包含有关局部路径P k

t

的邻接关

系。因为，这样的邻接关系随着P k

t

的生长而变化，所以我们称其为

动态邻接矩阵。

根据路径P k

t

，可以进一步定义矩阵U（k）：

u ij =

0，如果j=t

1，其

∩

他

（6）

然后，我们有关于网络矩阵的有如下的递归方程和第k步的邻接矩阵：

M（k）=M（k-1）∩U（k），M（0）=[1]n×n（7）A（k）=A（k-1）∩U（k）=A（k-1）∩M（k）

=A∩M（k），A（0）=A（8）令E（k）={（t，j）襔a

ij

（k）=1，坌j∈V}，我们有：

E（k）=E

qt

（9）从A（k）很容易得到集合E（k），A（k）采用递归的形式，容易编程实现。路径生长过程的基本思想是每一步通过增加一条集合E

（k）中的新边延伸路径P k

t 。运用这种方法生长的路径有可能会在某

一点悬挂住，也就是说，从这一点我们不能到达最终节点n。

对于给定局部路径P k

t

，当且仅当：（1）E（k）≠0；（2）t≠n时，端

点t是悬挂点。事实上，在V

q

中存在这样一些特殊点，它们根本无法

达到终点n。如果这样的点被加入局部路径中的话，他必定会将误

导路径至悬挂节点。那我们又如何区分这些悬挂节点呢？

给定t≠n的局部路径P k

t

，对于某节点i∈V q，令P（i）表示从节

点i到终点n的所有可能路径，V

l

i

是包含在路径l

i

中的节点集合。如

果：V

p

∩V

l

i

≠Φ，坌l

i

∈P（i）（10）

则节点i是死点。即，如果从该节点到节点n的任一条可能路

径至少包含V

p

中的一个节点，则这个节点就是死点。

利用可达矩阵可以判别死点。令A是给定图G=（V，E）的相邻

矩阵。A的k阶相邻矩阵可由如下的布尔乘法定义：

A k=A k-1A，A0=1（11）

k阶矩阵描述了节点i和j之间的关系：两者不直接相邻，但可

以通过长度为k-1的路径从节点i到达节点j。如果a k

ij

=1，则节点i

与节点j是k阶相邻的。

令E

p

={（t，j）襔i∈V

p

，j∈V}为与P k

t

上所有节点相关联的边的集

合。我们可以定义图G（k）=（V-V

p

，E-E

p

）是除去V

p

中所有节点及

与之相连的边的图G的子图。图G（k）的可达矩阵R（k）定义如下：

R（k）=[A（k）+I]n-k-2，k其中，I是单位矩阵，A（k）是路径P k

t

的动态连接矩阵。可达矩阵

描述了任意两点间的关系，即它们是至多n-k-2相邻的。

理论上，当程序进行到每一步时，我们都可以根据（1）式来检验

某个节点是否是死点，并从集合V中除去所有的死点。对于规模大

的问题，这样的检验需要消耗大量的计算成本。我们知道进化计算

的优势在于：它利用惩罚机制允许不可行的染色体进入种群，与可

行的染色体一起进化。在进化过程中不可行的染色体可能提供一些

有用的基因，因此，不必每步都检验死点，而只是简单地通过或轻或

重的惩罚，在终端死点和终点n之间建立一种虚拟连接。下面的路

径生长过程就是基于这些考虑的。

第1步：初始化。令k←0，V k

p

←{1}，A（k）←1。

第2步：执行终止测试。如果t k=n，执行第9步；否则，继续。

第3步：确定合格边集。根据动态邻接矩阵A（k）得到边集E（k）。

第4部：执行悬挂节点测试。如果E（k）=Φ，令t k+1←n，V k+1

p

←V k

p

∪{n}，给出虚拟连接（t k，n）的惩罚，执行第9步；否则，继续。

第5步：延伸路径。从V k

p

中选择优先权最高的t k+1，满足（t k，t

k+1

）∈E（k）。

第6步：执行mesh矩阵更新。新的mesh矩阵M（k+1）←M（k）

∩U（k+1）。

第7步：执行动态邻接矩阵更新。令A（k+1）←A（k）∩M（k+1）

第8步：执行迭代标记更新。k←k+1，执行第2步。

第9步：返回完整的路径。

3结论

随着互联网规模的日益扩大，网络安全问题也变得越来越尖

锐。如何提高网络入侵检测技术也成为一个业界重点课题。本文主

要分析了遗传算法在网络入侵检测中的应用。

本文主要讲网络中的节点转换为遗传算法中的染色体，通过对

染色体的分析，找到网络中最可能为入侵路径中的节点。

参考文献：

[1]陈国良，王煦法.遗传算法及其应用[M].北京:人民邮电出版社，1999.

[2]（日）玄光男，程润伟.遗传算法与工程设计[M].北京:科学出版社，

2000.

[3]Marcus Goncalves.防火墙技术指南[M].机械工业出版社，2000，11，161-

184.

[4]Paul E Proctor.入侵检测实用手册[M].中国电力出版社，2002，10：8-

10.

·146·