网络入侵检测算法研究

网络入侵检测算法研究（精选10篇）

网络入侵检测算法研究 篇1

1 引言

网络安全问题一直是世界各国政府、企业及广大网络用户最关心的问题之一。通常把试图破坏信息系统的完整性、机密性、可信性的任何网络活动都称为网络入侵。防范网络入侵最常用的方法就是防火墙，但是，防火墙只是一种被动防御性的网络安全工具，仅仅使用防火墙是不够的，一个更为有效的解决途径就是入侵检测技术。入侵检测技术是根据网络攻击行为而进行设计的，它不仅能够发现已知入侵行为，而且有能力发现未知的入侵行为，并可以通过学习和分析入侵手段，及时地调整系统策略以加强系统的安全性。入侵检测技术的方法可有多种，针对异常入侵行为检测技术的策略与方法往往也不是固定的。

2 基于异常的入侵检测技术

基于异常的入侵检测技术可以分为有监督的异常检测技术和无监督的异常检测技术，有监督的异常检测技术通过观察得到的正常数据建立正常数据模型，然后检测技术那些偏离正常模型的异常数据。这种方法能够检测技术新的攻击类型，因为这些新的攻击数据也会偏离正常的数据模型。有监督的异常检测技术的一个缺陷是需要一组完全正常的数据来训练获得模型，如果训练数据中包含攻击数据的话，这些攻击就很难检测到，因为该方法把这些攻击数据认为是正常数据，另一方面，要获取这些训练数据也是很困难的。

目前入侵检测技术研究的重点转移到了无监督的异常检测技术上，这种技术用一组没有标记的数据作为输入，发现其中存在的攻击数据，即试图从一组不知道什么是正常，什么是异常的数据集中发现那些异常的数据。无监督的异常检测技术与有监督的异常检测技术相比，它不需要完全正常的训练数据，只需要未加工的网络原始数据。无监督的异常检测技术有一个基本的假设，就是正常数据和异常数据有定性的不同，这样才可以将它们区分开来，例如通过一般的分析，可以知道拒绝服务攻击的数据在属性取值和模式上与正常的数据有很大的不同，所以可以利用无需指导的异常检测技术来有效地检测出拒绝服务攻击[1]。

利用聚类算法的异常检测技术就是一种无监督的异常检测技术，这种方法可以在未标记的数据上进行，它将相似的数据划分到同一个聚类中，而将不相似的数据划分到不同的聚类，并为这些聚类加以标记表明它们是正常还是异常，然后将网络数据划分到各个聚类中，根据聚类的标记来判断网络数据是否异常。

3 聚类算法简介

聚类算法是一个将数据集划分成若干个聚类的过程，使得同一聚类内的数据具有较高的相似性，而不同聚类中的数据不具有相似性。相似或者不相似根据描述数据的属性值来度量，通常使用基于距离的方法。通过聚类，可以发现数据的密集和稀疏的区域，从而发现数据整体的分布模式，以及数据属性间有意义的关联。

聚类算法涉及很多个领域，包括数据挖掘、统计、机器学习、空间数据库技术，目前研究重点是基于距离的聚类算法。聚类算法也是一种无指导的学习，它不像分类算法那样需要事先标记好的训练数据。聚类算法的输入是一个包含多个数据的数据集，每个数据通常用一个属性向量(x1,x2,...,xp)来表示，其中xi是一个连续的或离散的变量，代表数据的一个属性的取值。

聚类算法的输出是若干个聚类，每个聚类中至少包含一个数据，而且同一个聚类中的数据具有相似性，不同聚类的数据不具有相似性。

为了使用聚类算法，需要计算数据之间的差异，数据间的差异通常用距离来表示，距离计算方法包括欧几里德距离、Manhattan距离、Minkowski距离。其中最常用的是欧几里德距离，它的计算方法如下[2]：

其中i,j分别代表数据集中的两个数据，它们都有P个属性。

可以给不同的属性赋以不同的权值，这样计算出来的距离称为加权的欧几里德距离，定义如下：

聚类算法有很多种，可以划分为几种类别：划分方法，层次方法，基于密度的方法，基于网格的方法和基于模型的方法，同时聚类也可以用于异常值(outlier)检测技术。

4 常见的聚类算法

4.1 K-means算法

最常用的聚类算法是K-means算法，它是一种划分方法。给定一个包含n个数据的数据集和产生聚类的个数，K-means算法将数据划分成k个子集，每个子集代表一个聚类，同一个聚类中的数据之间距离较近，而不同聚类的数据间距离较远。每个聚类由其中心值来表示，通过计算聚类中所有数据的平均值可以得到它的中心值。

4.1.1 K-means算法描述如下

算法：K-means

输入：聚类的个数k和一个包含n个数据的数据集

输出：k个聚类

方法：任意选取k个数据作为初始的聚类中心

Do

将每个数据划分到一个聚类，依据数据与聚类中心值的距离最近为标准

更新聚类的中心值，即重新计算每个聚类中所有数据平均值

While划分没有发生变化时输出k个聚类

4.1.2 K-means算法在入侵检测技术中的应用原理

基于无监督聚类的入侵检测技术算法建立在两个假设上：第一个假设是正常行为的数目远远大于入侵行为的数目;第二个假设是入侵的行为和正常的行为差异非常大。该方法的基本思想就是由于入侵行为是和正常行为不同，并且数目相对很少，因此它们在能够检测到的数据中呈现出比较特殊的特性。比如可以首先假定输出10个聚类，从数据集中任选10个数据作为这个聚类初始的中心值，然后将每10个数据划分到其中的一个聚类，方法是判断该数据到哪一个聚类的中心值的距离最近，则将该数据划分到这个聚类。划分完成后，重新计算每个聚类的中心值，方法是计算聚类中所有数据的平均值，把这个平均值作为新的聚类的中心值。接下来重新将每个数据划分到其中的一个聚类，如此反复地进行若干次划分和计算中心值的操作，直到数据的划分没有变化。

4.1.3 算法的优点和缺陷

算法的优点是不需要用人工的或其他的方法来对训练集进行分类，并且能够比较有效地检测未知入侵攻击。而且算法有良好扩展性，被广泛应用于各领域。

但是像K-means算法经常在聚类开始前就获得了全部数据(即离线的)，但时常会有些对“在线聚类”的需求。比如存储空间不够记录所有的数据模式，或者系统对时间要求很高，以至于数据还没有全部出现算法就必须开始。算法设计要求中有一点就是效率与低存储量需求，所以衡量算法的复杂度有时间复杂度和空间复杂度两个方面。K-means算法的效率较高，但是得付出较大的存储空间[3]。下面介绍在该算法基础上改进的迭代最优化算法。

4.2 迭代最优化算法

输入：聚类的个数k，一个包含n个数据的数据集，每个聚类的均值mi

输出：k个聚类

方法：随机选取一个样本Xi(存在于某个均值为mi的聚类中)

While Xi离mj的距离比离mi更近

Do

将Xi转移到均值为mj的这个聚类中

更新这个聚类的中心值，即重新计算这个聚类中所有数据平均值

While划分没有发生变化时输出k个聚类

算法分析：

对这个算法稍作考虑就会发现它其实是K-means算法的一种变形。K-means算法在每次更新前都要对所有的数据点重新分类，而这个方法每次对一个样本重新分类后就进行更新。但是这种算法更易陷入局部极小值，对全局入侵检测技术效率有影响。然而它毕竟是一种逐步求精的算法，对存储空间要求不高，而且很容易作些改动使得它能处理顺序数据流或需要在线聚类的场合，这也正符合入侵检测技术的环境[4]，当然在其他许多领域也有广泛的应用。

5 新算法的构想

虽然说衡量一个算法的效率有时间和空间两方面的要求，而且时空不可能同时达到最优，但是可以适当地将时空两方面兼顾一下，使对聚类分析时的存储空间要求不太高，同时分析过程也不太长。

在这里再通过一个形象的比喻生动地描述一下K-means算法和迭代最优化算法，可以更清晰地理解这两个算法的优缺点，同时也描述一下新的构想，了解一下所设想的算法的可行性和优越性。

1)比方说某班级40位同学去一个食堂打饭，若要时间效率最高，必然要求食堂的服务员尽可能的多，但就同学人数来说40个服务员就足够了，每人打饭需要1分钟，那么1分钟就可以解决40位同学的问题，效率高，但是这对食堂方面的要求太高，对入侵检测技术来说就是对存储空间要求很高，这相当于K-means算法中的任意选取k个数据作为初始的聚类中心，而后重新计算每个聚类中所有数据平均值。

2)如果食堂条件非常有限，只有一个服务员，那么40位同学排队打饭就向一个顺序数据流，而且第一位同学打完饭就回寝室了，对于他来说他的时间效率是最优的，这就是刚才所说的迭代最优化算法更易陷入局部极小值，而对于最后一位同学来说时间效率最差，需要等39分钟才轮到他。总体来说这种方式对于食堂方面要求很低，可以节省个别同学的时间，但是对于全局的贡献很有限。

3)但若有40位同学和4个服务员，那么每个服务员负责10位学生，到最后一位同学打完饭共需要10分钟，对服务员要求的数量也不多，这种算法还可以。如果服务员充足的话，还可以再优化些：先6个服务员每人负责6位学生，余下4位学生自由选择不同的队列，总共时间为7分钟，服务员人数也挺合理。

此算法应用到入侵检测技术中去，对数据进行分析时，可以根据系统存储能力选择某些聚类优先进行分析，而后对先分析的这些聚类进行更新。

但是怎么来对聚类分析优先级进行划分呢，可以随机选择，也可以人为地按照一定的规则选择，比如二维空间可以划分为四个象限，按照1234象限逆时针的顺序在每个象限中分析这些聚类，也可划分为对称的8个区域，先从第1个象限的第1个区域和对称的第3个象限的第1个区域同时进行分析。这种人为规定其实就是一种“有监督”的方法。

6 结束语

提出的算法构想是有监督和无监督方法的结合，是K-means算法和迭代最优化算法的结合，是一种更加优化的算法。据此思路设计成一套入侵检测系统，各部分的性能要求必然较高，因此如有可能生产出成型的产品，将具有一定的社会实用价值和理论研究价值。

参考文献

[1]Bace R G.入侵检测[M].北京:人民邮电出版社,2001,59-60.

[2]姚君兰.入侵检测技术及其发展趋势[J].信息技术,2006(4):172-175.

[3]梅梦.聚类算法的分析与研究[J].科技广场,2007(11):26-27.

[4]李涵,包立辉.基于聚类算法的异常入侵检测模型的研究与实现[J].计算机应用与软件,2006(10):126-127.

网络入侵检测算法研究 篇2

1网络信息安全技术的发展

1.1加密

对于计算机网络中的加密，其实就是比较基本的一种安全机制，是使用数学函数来处理不加密的一些关键信息，并且完成信息加密的这样过程。依据不一样的密钥分发方法，还有达成加密机制分为两种类型，其中包括有私钥加密以及公钥加密。这是能够用来数据传输以及存储中，还能够避免一些不授权者的非法读取的信息。然而，它无法在前面的信息加密之前或者是之后来加密保护，而是要依赖于密钥的一个管理技术。

1.2数字签名

数字前面关键就在于可以提供拒绝识别功能，也就是说，第三方没有办法去伪造发件人去完成数据的发送，所以说发送方在发送具体数据之后没法否认。数字签名一般来说使用公钥来完成，对于签名者来说可以通过用密钥加密，并且验证方能够用签名者的公钥来完成解密签名数据操作，并且能够确定接收到的信息是否是错误的。

1.3防火墙系统

防火墙系统也就是把安全战略转化为安全控制操作，对于不一样的信任级别或者是不一样的安全级别网络设置具体安全边界，检查网络数据包或者是具体服务的一些请求，可以较为有效地控制内部网络或者是外部网络间访问或者是数据的传输，进而能够完成保护内部网络信息不会因未经授权的用户限制了内部这些用户的访问限制。不过对于防火墙系统来说，也是有局限性：诸如防火墙无法在没有经过防火墙入侵，也就是系统可以绕过性攻击。防火墙很难实现防范恶意攻击或者是一些内部用户的误操作行为发生。对于防火墙的配置和管理等等都比较复杂，容易导致安全漏洞的发生。

2入侵检侧系统的分类

2.1基于主机的入侵检测系统及特点

对于主机的入侵检测系统能够把一个主机上面得到数据作为计算机网络安全中入侵系统分析的数据源，另外基于网络的入侵检测系统能够从互联网中得到一些数据来当成是数据源。一般来说基于主机的这样入侵检测系统只可以检测到一个主机的系统，但是基于网络的入侵检测系统能够检测多个主机系统，对于较多分布在不同网段的基于网络的入侵检测系统能够一起工作，从而实现更加强大的入侵检测的效果。计算机网络安全系统中，对于主机的入侵检测系统检测模块位于被保护系统，利用提取这些运行数据且对入侵分析来完成入侵检测的具体功能。主机的入侵检测系统现在的不足有，这个入侵检测取决于整个系统的可靠性，它需要系统本身有基本的安全特性，然后你可以提取这些入侵信息。

2.2基于网络的入侵检测系统

计算机网络的入侵检测系统可以利用网络监视来完成数据的提取。在工作中，局域网通常使用以太网协议。对于这个协议期间主机子网无线的数据传输方法，没一台的主机能够发送数据包，还可以通过子网完成广播，其实就是说，对于每一台主机发送以及接收数据能够收到同一子网内的其他主机数据。在通常的环境中，每个到来的主机网卡的`数据包会先完成过滤，一般到目标地址是本机或者是广播地址的数据包接收缓冲区，把其他的这些数据包丢弃，所以说，在通常的情况下，主机的网络性能就是关心和自己有关的一些数据包，不过设置网卡接收模式正确过滤策略能够完成网卡过滤方式的变动，使网卡再接收所有的数据包这一时期之后，不管这些包的最后目标是否是主机。对于卡的接收模式被叫做混合模式，大多数卡将提供这些设置，所以说，必要时，合理设置网卡可以通过这段时间的所有信息的交流，完成网络监控的效果。

3网络入侵检测系统需要解决的关键技术

3.1入侵检测模块间的协作

入侵检测模块的合作关键就是对不同检测模块之间数据共享的解析，同时对模块间增强功能，利用合作可以达成工作时无法实现的具体功能。分布式网络入侵检测系统的框架结构、功能模块的异构性，数据检测系统还有探测器分布在网络的情况，同时继承这些不同的开发人员研制，用不同的具体检测机制，还有入侵检测功能模块运行在各异的系统以及不一样的检测子系统，还要去考虑它们之间的这些数据共享以及协作等等，还需要去提供分布式数据采集、并且利用数据接口来完成不一样的检测器之间的互操作性，考虑分布在整个组织在分布式入侵检测系统和探测器测试结果融合技术。对于分布式数据共享也应该是对收集到的数据格式完成一个转换，从而能够保证这些数据的可用性。这些关键是涉及到网络入侵检测系统的一些功能模块之间的合作机制还有技术，其中包括计算机网络安全中入侵检测系统的具体通信机制，数据预处理和数据融合技术以及功能模块间的协作机制等等。

3.2入侵检测数据分析的层次性

即使对于各种入侵检测系统概念是一样的：不过整体来说都是通过探测器还有分析仪和用户界面来构成的。入侵检测系统在特定方法的基础上，通过分析数据和收集数据，这些方面是非常不同的。每一种的入侵检测系统的分析数据源上有水平，从入侵检测系统基于应用程序跨多个网络入侵检测系统，来完成这些分析数据以及监控的能力逐渐增强，范围也不断地扩大，并且这入侵检测系统数据可以是源于水平不高于它的入侵检测系统的输出。其实就是代表，入侵检测系统检测的具体结果以及输出能够在水平不低于其入侵检测系统使用和进一步的具体分析。

4结语

图像边缘检测相关算法研究 篇3

关键词:图像边缘检测;算法

中图分类号:TP301.6 文献标识码:A文章编号:1007-9599 (2010) 09-0000-01

Research on Image Edge Detection Algorithms

Zhang Benqun

(Guizhou Xingyi Normal University for Nationalities,Xingyi562400,China)

Abstract:In this paper,two types of image edge detection methods is firstly introduced.

Image edge judging indices,which are wrong detection rate and positioning accuracy,then illustrated.Finally,corresponding traditional image edge detection algorithms,such as Roberts Operator,Sobel Operator,LOG operator and Otsu Operator are all discussed in details.

Keywords:Image edge detection;Algorithm

作為计算机视觉的经典性研究课题,图像边缘的研究已有较长历史,涌现了许多方法,本文将这些方法分为两大类:①基于空间域上微分算子的经典方法。②基于图像滤波的检测方法,并论述其中一些经典的图像边缘检测算法。

一、两类图像边缘检测方法

(一)基于空间域上微分算子的经典方法。在阶跃型边缘的正交切面上,阶跃边缘点周围的图像灰度I(x)表现为一维阶跃函数I(x)=μ(x),边缘点位于图像灰度的跳变点。根据边缘点的特性,人们提出了基于图像灰度一阶导数、梯度、二阶导数以及更为复杂的LaPlace算子等提取图像边缘的方法。

(二)基于图像滤波的检测方法。在实际图像中,边缘和噪声均表现为图像灰度有较大的起落,同是高频信号,但相对来说边缘具有更高的强度。

二、图像边缘评价指标

为了评估边缘提取效果,人们提出了形式多样的评价指标,其中误检率和定位精度是两个最常用的指标。前者指实际边缘点漏检和虚假边缘点误检两种错误发生的概率。设原图像E(x,y)和滤波后图像的信噪比为SNR,当SNR大时,噪声对边缘检测的干扰小,真实边缘容易被检测,噪声引起的虚假边缘点相对减少,图像边缘的误检率降低;反之,当SNR小时,边缘的误检率将升高。由此可见,图像边缘的误检率是滤波后图像户的信噪比(SNR)单调下降函数,我们可以用图像的信噪比(SNR)近似表示图像边缘的误检率。用大尺度的滤波器去抑制原图像的噪声,可靠地识别噪声;而用小尺度滤波器为图像边缘精确定位。这就是常说的多尺度边缘提取算法。多尺度的图像边缘检测方法已成为图像边缘检测的重要发展方向。

三、几种经典的边缘检测算法论述

(一)Roberts算子。RobertS边缘检测算子根据任意一对互相垂直方向上的差分可用来计算梯度的原理,采用对角线方向相邻两像素之差,即:

(1)

有了△xf和△yf之后,很容易计算出Roberts的梯度幅值R(i,j),适当取门限T,作如下判断:R(i,j>T,(i,j)为阶跃状边缘点,{R(i,j)}为边缘图像。RobertS算子采用对角线方向相邻两像素之差近似梯度幅值检测边缘。它适合于得到方向不同的边缘,对不同方向的边缘都比较敏感,检测水平和万垂直边缘的效果好于斜向边缘,定位精度高。但是在进行差分计算的过程中对噪声敏感,即有噪声影响的像素点可能被检测为边缘点。

(二)Sobel算子。对数字图像{f(i,j)}的每个像素点,考察它上、下、左、右邻点灰度加权差,与之接近的邻点的权值大。定义Sobel算子如(2),其中卷积算子如(3)所示。取适当门限T,作如下判断:若S(i,j)>T,即(i,j)为阶跃状边缘点,{S(i,j)}为边缘图像。

S(i,j)=∣△xf∣+∣△yf∣=∣(f(i-1,j-1)+2f(i-1,j)+f(i-1,j+1)-f(i+1,j-1)+2f(i+1,j)+f(i+1,j+1))∣+∣(f(i-1,j-1)+2f(i,j-1)+f(i+1,j-1)-f(i-1,j+1)+2f(i,j+1)+f(i+1,j+1))∣(2)

(3) (4)

Sobel算子很容易在空间上实现,Sobel边缘检测器不但产生较好的边缘检测效果,而且受噪声的影响也比较少。

(三)LOG算子。前面介绍的梯度算子和拉普拉斯算子实际上都是微分或差分算法,因此算法对噪声十分敏感。所以,在边缘检测前,必须滤除噪声。Marr和Hildreth将高斯滤波和拉普拉斯边缘检测结合在一起,形成LOG(Laplace-Gauss)算法。LOG边缘检测器的基本特征是:1.平滑滤波器是高斯滤波器;2.增强步骤采用二阶导数(二维拉普拉斯函数);3.边缘检测判断依据是二阶导数零交叉点并对应一阶导数的较大峰值;4.使用线性内插方法在子像素分辨率水平上估计边缘的位置。

(四)Otsu算法。Otsu算法正是利用概率论的知识,通过计算最大类间方差而得到分割阈值的。

结束语:本文对相关的经典图像边缘检测算法进行了回顾和分析,并论述了其实用优势和不足,这些算法在实际的计算数学工程中,得到了广泛的应用,并不断被人们改进。

参考文献:

[1]朱红高.图像边缘检测技术研究现状[J].制造业自动化,2010,01

僵尸网络检测算法的比较研究 篇4

僵尸网络(Botnet)是指采用一种或多种传播手段,使大量主机感染僵尸程序,从而在控制者和被感染主机之间形成一个可以一对多控制的网络[1],进而构成一个攻击平台,利用这个平台可以有效地发起各种各样的攻击行为,导致整个基础信息网络或者重要应用系统瘫痪,致使大量机密或个人隐私泄漏,还被用来从事网络欺诈等其他违法犯罪活动。

目前,僵尸网络的威胁已经成为国际上十分关注的问题,与此同时,我国国内网上Botnet的威胁比较严重,已经成为了僵尸网络的生产大国,这需要引起网络用户的高度重视,需要国内外信息安全方面对其更进一步的发现、跟踪和反制。

1 僵尸网络检测算法

僵尸网络的活动情况分为四个阶段[2]:传播、感染、通信、攻击,其中,通信是僵尸网络活动必不可少的阶段。根据僵尸网络的工作原理,攻击者必须通过C&C控制信道与僵尸主机交互,再经过网络传输,所以,通信阶段是最薄弱的、最易被发现的。因此,目前大部分的检测方法都是建立在此阶段上的。下文通过列举一些主流的僵尸网络检测算法,进行剖析和对比,提出每种检测算法的优点和不足。

1.1 基于TCP扫描权重的启发式异常检测算法[3]

该算法基于IRC僵尸网络中大量僵尸主机连接到同一IRC频道,并接受网络传播命令进行大量的TCP SYN扫描,设置TCP扫描权重,通过识别该权重超出正常阀值的被感染IP地址及其连接的IRC频道对僵尸网络进行检测:

式中,Ss为发送的SYN包和SYN|ACK包数量,Fs为发送的FIN包数量,Rr为接收的RESET包数量,Tsr为全部TCP数据包数量,w为TCP扫描权重即TCP控制报文数与总TCP报文数的比重。该方法只能适用于明文方式传播控制信道命令的IRC僵尸网络。

1.2 狩猎女神项目

该项目主要包括2个主要步骤:

(1)通过部署蜜罐对僵尸程序进行捕获样本;

(2)通过对网络行为进行监视和分析僵尸网络控制信道信息。

该算法利用恶意软件收集器对恶意软件样本进行收集,通过对恶意软件样本的分析判断其是否为僵尸程序,并取出其所连接的僵尸网络控制信道信息,从而在僵尸网络的早期传播阶段就能发现。

系统部署的恶意软件收集器是针对最主流的僵尸程序感染方式——主动攻击漏洞感染,首先将会模拟一系列常见的操作系统漏洞(如RPC DCOM漏洞、LSASS漏洞等),当恶意软件通过攻击这些漏洞试图感染蜜罐机时,恶意软件收集器将通过分析恶意软件攻击所使用的Shellcode获取其中包含的恶意软件链接URL,并根据此URL下载获得恶意软件样本。

对收集到的恶意软件样本,系统采用了沙箱、蜜网两种各有优势的技术对其进行分析,确认其是否是僵尸程序,并对僵尸程序所要连接的僵尸网络控制信道的信息进行提取,作行为分析。

1.3 AT&T实验室[4]

该实验室提出了一种在ISP骨干网层面上检测和刻画僵尸网络行为的方法,由以下步骤组成:

(1)底层传感器触发的事件进行聚合,识别出具有可疑行为的主机;

(2)基于缺省IRC服务端口,识别到集中服务器的连接以及IRC流量模型特征这3个启发式规则,识别出可能的僵尸网络命令与控制连接;

(3)分析可能的连接,计算出连接同一服务器的可疑僵尸主机数量,计算出可疑连接与IRC流量模型的相似性距离,并结合两者计算该可疑连接为僵尸网络命令与控制信道的得分;

(4)通过与其他数据源的关联、DNS域名验证和人工验证确认检测到的僵尸网络。

1.4 基于决策树的僵尸流量检测方法

僵尸主机与控制者之间的会话特征,包括以下4种:

(1)僵尸主机与控制者之间的会话消息是短消息;

(2)由于僵尸程序具有可传播性,因此在极短的时间内会有大量的僵尸主机加入同一IRC服务器的同一频道中;

(3)如果控制者在较长的时间内没有向僵尸主机发送命令,则僵尸主机就会“长期发呆”,没有任何响应;

(4)IRC僵尸网络中的控制者在所控制的频道内向所控制的僵尸主机发送广播命令,让所有的僵尸主机去执行同一条命令。

决策树算法描述如下:对于捕获到的IRC网络流量,转换成适合数据挖掘的数据格式。根据特征(1),可以推断出异常IRC数据包长度的平均值小于正常的。利用类内距离小,类间距离大的分类识别方法,设计针对数据包大小这一属性的属性函数为:f=(li-l1)2-(li-l2)2,其中l1为异常IRC数据包长度的平均值,l2为正常IRC数据包长度的平均值,li为任一个数据包长度。如果f≤0,则将该数据包归类为疑似的IRC僵尸数据包,否则为正常。根据特征(2),设置一个很短的时间t0和阀值n。如果在t0时间内,有大于阀值的数据包具有相同目的IP和不同源IP,则可以认为这些为僵尸数据包。根据特征(3),设置一个较长的时间段t1和一个阀值p。如果在t1时间内IRC频道内某些IP出现次数小于阀值,则可以认为以该IP为目的IP或源IP的数据包为僵尸数据包。根据特征(4),设置很短的时间t2和一个阀值m。如果在t2时间内有超过阀值的数据包具有相同源IP和不同目的IP,则可以认为这些数据包是受感染的。

1.5 BotHunter系统[5]

该系统将僵尸程序感染过程视为一台内网主机与外网一台或多台主机间的信息交互序列,包括目标扫描、破解攻击、二进制代码注入以及执行、命令与控制信道连接和对外扫描等步骤。底层采用Snort入侵检测系统的特征检测方法以及两个关注僵尸程序的异常检测插件SLACE和SCADE,对僵尸程序感染的各个步骤进行检测。SLACE插件实现了对流入连接的有损性n-gram负载分析方法,通过对执行协议负载的字节分布异常检测出恶意代码攻击;SCADE插件进行针对恶意代码的平行及垂直端口扫描分析,可以检测出流入连接和流出连接中的扫描事件。BotHunter关联分析器将底层IDS报告的流入扫描报警、破解攻击报警和外出控制信道报警、对外扫描报警等事件联系在一起,从而给出一个详细的包含所有相关事件的僵尸程序感染会话场景。

1.6 RiShi系统[6]

该算法的基本思路是被动监听流量,通过开源的ngrep工具获取其中包含的IRC连接信息,然后用n-gram分析方法实现评分函数,通过对IRC昵称的异常评定,检测出内部网络中被IRC僵尸网络感染的僵尸主机。

从技术实现和系统整合的角度考虑,相比较而言,该系统无疑是最具优势的算法。而现阶段的实验数据体现出该系统存在着以下不足:依赖正则表达式来检测和评价一个僵尸程序的昵称,但目前存在一些僵尸程序使用与IRC用户类似的昵称命名结构,或者一旦改变僵尸程序昵称命名结构就可以轻松绕开检测;此外该算法对于基于HTTP和P2P的僵尸网络无能为力。

与此同时,可以显见的是,即使是最新型的Bot程序通信,它们也是需要通过端口来实现的[7]。IRC(端口6667)和其他大号端口(比如31337和54321)仍然被绝大部分的Bot使用着。1024以上的所有端口除非所在组织给定某个端口有特殊的应用需要,否则必须设置为阻止Bot进入。与此同时,也可以对开放的端口制定通信策略,如“办公时间才可开放”或是“除了以下IP地址列表,其他一切所有访问”等。Web通信通常需要使用80或是7这样的端口。而僵尸网络也通常是在凌晨1时~5时之间进行升级,因为这个时候升级不易被人发现。因此人们有必要养成在早晨查看系统日志的好习惯,同时应该警惕并进行调查那些发现没有人存在但却有网页浏览的活动。

2 结束语

僵尸网络作为一种从传统恶意代码形态进化而来的高级攻击方式,其具有活动隐蔽、反应敏捷并且效率较高的一对多命令与控制机制,因而攻击者广泛采用僵尸网络并藉此达到实现窃取敏感信息、发送分布式拒绝服务攻击和发送垃圾邮件等攻击目的。目前,僵尸网络已经进入迅速发展时期,而且已经对网络安全造成了严重威胁。

除此之外,根据最新的僵尸网络相关研究表明,僵尸网络开始逐渐呈现出如下的发展趋势[8]:命令与控制机制从最原始的只基于IRC协议逐步转向基于HTTP协议以及很多不同类型的P2P协议,从而使僵尸网络的隐蔽性和鲁棒性得到增强;在网络传播方法上学习并掺杂了许多种传统恶意代码的传播方式,包括某些最新的通过实时通信软件以及P2P文件共享软件进行传播[9];通过增强认证和信道加密机制,对僵尸程序进行多型化和变态混淆,加入Rootkit隐蔽机制从而使得开展对僵尸网络的检测、跟踪及分析活动的难度加大了。

人们预计,研究僵尸网络在未来一段时间内所必须关注的重点方向包括:(1)新型的僵尸网络命令与控制机制及其应对策略;(2)进一步研究对僵尸网络传播模型并在实验测试环境中得到验证;(3)针对新型的僵尸网络命令与控制机制开发出具有更加准确和高效性能的僵尸网络检测机制;(4)在一定程度上具有自动化概念的僵尸网络反制辅助平台的研究与实现[10]。

鉴于僵尸网络所呈现的技术特点及其发展趋势,安全领域研究者必须加强僵尸网络的研究,并协调反病毒业界和应急响应部门进行有效反制,开发出更具准确性和高效性的僵尸网络检测机制,特别是针对新型的僵尸网络命令与控制机制,才能有效遏制其快速发展的势头。

摘要：僵尸网络是由许多台被恶意代码感染控制并与互联网相互连接的计算机所组成,其正步入快速发展期,并已对因特网安全造成了严重威胁。文章针对目前国际上主流僵尸网络检测算法进行分析和比较,给出每种检测算法的优点和不足。

关键词：僵尸网络,通信阶段,检测算法,比较研究

参考文献

[1]诸葛建伟,韩心慧,周勇林,等.僵尸网络研究与进展[J].软件学报,2008,19(3):702-715.

[2]霍建滨,白凤娥.僵尸网络的检测技术研究[J].科技情报开发与经济,2007,17(3).

[3]Binkley J R,Singh S.An algorithm for anomaly-based botnetd etection[C]//Proc.of the USENIX2nd Workshop on Steps toR educing Unwanted Traffic on the Internet(SRUTI2006).2006:43-48.

[4]Karasaridis A,Rexroad B,Hoeflin D.Wide-Scale botnet detec-t ion and characterization[C]//Proc.of the1st Workshop on HotT opics in Understanding Botnets(HotBots2007).2007.

[5]Gu G,Porras P,Yegneswaran V,et al.BotHunter:Detectingm alware infection through IDS-driven dialog correlation[C]//P roc.of the16th USENIX Security Symp(Security2007),2007.

[6]Goebel J,Holz T.Rishi:Identify bot contaminated hosts by IRCn ickname evaluation[C]//Proc.of the1st Workshop on Hot Top-i cs in Understanding Botnets(HotBots2007),2007.

[7]Alden W.Jackson,David Lapsley,Christine Jones,et al.S LINGbot:A system for live investigation of next generationb otnets catch[C]//Cybersecurity Applications&TechnologyC onference for Homeland Security.2009:313-318.

[8]吴莉娅.关于botnet若干问题的探讨[J].惠州学院学报:自然科学版,2009(03):78-80.

[9]Stock B,Goebel J,Engelberth M,et al.Walowdac:Analysis of aP eer-to-Peer Botnet[C]//European Conference on ComputerN etwork Defense.2009.

网络信息理入侵检测技术研究论文 篇5

(2)现阶段入侵检测技术的主要流程。通常情况下,入侵检测技主要可以分为两个阶段。第一个阶段便是信息采集,主要便是对于用户的各种信息使用行为和重要信息进行收集,这些信息的收集主要是通过对于重点信息部位的使用信息进行查询得出的,所以说在现代应用之中,入侵检测技术一方面应用了现代的检测技术,另外一方面也对于多种信息都进行了收集行为,保证了收集信息的准确性;第二个阶段便是处理相关信息,通过将收集的信息和过往的信息进行有效对比,然后如果对比出相关错误便进行判断,判断使用行为是否违背了网络安全管理规范,如果判断结果为肯定,那么便可以认定其属于入侵行为,对于使用用户进行提醒,帮助用户对于入侵行为进行清除。

2现阶段入侵检测技术的使用现状

(1)网络信息管理中入侵检测系统的问题。入侵检测技术作为一种网络辅助软件去,其本身在现阶段并不是完善的,自身也存在漏洞。所以说很多非法分子的入侵不仅仅是面对系统的,很多先通过入侵技术的漏洞来进行。针对现阶段的使用过程而言,入侵检测技术仍然存在自身的漏洞危险,也存在主要使用风险。在现阶段存在危险的方面主要有两个方面。一方面便是由于入侵检测系统存在漏洞;另外一方面便是现代计算机技术的发展。无论是相关的检测系统亦或是相关病毒,都是现代编程人员利用C语言进行编程,伴随着相关编程水平的不断提高,两种技术同样得到了自我发展,所以说很多hacker高手在现代的入侵行为之中,已经不能以旧有的眼光来进行相关分析。所以说新的时期,入侵检测技术也应该得到自我的发展,同样针对于应用网络的相关企业做好安全保证,保证信息技术在现代之中的发展。

网络入侵检测算法研究 篇6

在信息爆炸的时代,海量数据的安全问题是云计算面临的最大问题,云平台的入侵检测和预防是大数据时代安全关注的核心。本文在大数据的背景下,面对海量数据的安全问题,从数据安全问题的处理速度和处理精度方面改进传统的入侵检测算法,通过分析现在云环境中网络数据的特点,建立了一个适用于云环境下的入侵检测算法——MRGA⁃BP均值法算法[1],最终通过实验证明,此算法可以保证在一定的入侵检测精度下,提升检测的效率,更适合当下大数据环境入侵检测[2]。

1 基于云计算平台的网络入侵检测算法建立

1.1 MRGA⁃BP算法的网络拓扑结构的确定

BP神经网络是由网络层数、节点个数、激活函数、初始权值系数、学习算法、系统误差确定的,确定这些需要一定的原则:

(1)隐含层数的选择

根据先前的经验,优先考虑3层BP神经网络:输出层,输入层,隐含层。

(2)每层节点数的确定

在精度确保的前提下,以隐含层节点数最少为目标。隐含层和很多因素有关,例如样本数据的特点和转换函数的型式、输入与输出节点数都有关系。

(3)初始权值系数的确定

初始权值是在一定范畴的数随机生成的,一般情况下,初始权值分布在0~1之间。在本文中,利用random随机生成。

(4)算法的确定:

式中:t为学习次数;η取0.01~0.8。

(5)结束条件

BP神经网络算法的结束条件就是全局误差降到可接受的范围或者学习次数达到最大[3]。本文中只是应用遗传算法进行BP神经网络权值的优化,所以在本文中只控制其进化的次数,当进化次数达到最大时终止。

1.2 并行化思想

首先将数据模块化,然后将这些数据模块分给各个机器进行并行处理,他们之间处理的过程没有关联,所以在处理效率上会有很大提高。

并行化有两种思路:一种是物理节点的并行化,即将网络节点分布在不同的机器节点上进行计算;第二种是数据的并行化,每个计算节点都有一个完整的网络,且网络的初始状态是一样的[4]。并行化体现在进行训练时,每个节点都是取一部分样本数据进行BP神经网络的训练,计算节点内达到某个收敛要求后再进行汇总,汇总之后决定是否进行下一场迭代。

1.3 MRGA⁃BP算法描述

提出的MRGA⁃BP均值法算法的主体思路是:GA算法的Map阶段,随机产生N个个体,上传到HDFS文件系统,读入每个个体的值,每一个个体代表的是每一个BP网络的权值,调用BP神经网络算法,每个个体的输入权值和每个样本的值,进行BP神经算法,求出每个个体对应所有样本的误差和,这个误差和称为全局误差值,全局误差值作为GA遗传算法Map阶段的输出值,Redcue阶段的输入值为Map的输出值,计算每个个体的适应度,接着遗传算法的选择,交叉,变异等。经过数次迭代后,筛选出最优个体,输出到HDFS文件,作为BP神经算法的初始权值。

1.4 MRGA-BP均值法算法原理

(1)MRGA-BP均值法描述

提出的MRGA⁃BP均值法,在BP神经网络阶段用map输出的是每个样本的所有权值变化量,然后将每个样本所有权值的变化量输出,在reduce阶段,将所有样本相对应的权值相加求出算数平均值,并且更新权值一次上传到HDFS,之后再使用新的权值HDFS文件进行第二次迭代,将产生的权值上传到HDFS[5]。迭代Hadoop作业,迭代结束的标志是迭代次数达到最大或者误差在范围内。

(2)BP神经网络算法的Map Reduce化

对BP神经算法的Map Reduce过程,算法可以拆成三个过程:

第一个过程,训练神经网络。Map类调用map函数,接收数据样本和权值样本,开始训练BP神经网络,这个过程相当于三个大型矩阵在相乘,可以先让两个矩阵相乘,再和第三个矩阵相乘,Reduce最终生成一个实际计算出来的结果,作为输出矩阵。

第二个过程,主要是为了将实际输出结果和输入的样本进行合并,为第三个阶段进行调整权值准备。

第三个过程,读入第二阶段生成的Text,计算每一个样本所有权值的变化量。最终求出新的权值。

(3)GA遗传算法的Map Reduce化

应用GA遗传算法优化神经网络的权值。采用实数编码,将BP神经网络中的权值标记为“染色体”,适应度为误差的倒数,接着选择,交叉,变异,选出最优权值。GA算法Map Reduce的流程图如图1所示。

Map阶段读取HDFS上的群体信息,计算每一个个体经过一次BP神经网络迭代学习时所有样本的学习全局误差,作为Map的输出[6]。Reduce阶段的输入是每个权值个体所对应的误差,因为误差计算比较复杂,所以将误差值设定为全局变量,按照误差,求出每个个体的适应度,适应度为误差的倒数,适应度最高的个体不进行下边的步骤。而剩下的个体,使用赌盘算法选择、交叉、变异,选出一个最优个体。

1.5 基于云计算的入侵检测流程

为了更好地在云环境下检测入侵行为,提出了基于云平台下的海量数据的入侵检测系统,流程图如图2所示,具体的检测过程如下:

(1)将入侵检测数据源以分布式的形式存储到HDFS上;

(2)将随机产生的权值以分布式的形式存储到HDFS上;

(3)运用Map Reduce GA开始BP神经网络初始权值的优化,优化出较小的解空间,提高收敛率;

(4)使用Map Reduce GA优化数据源权值,用BP神经网络计算出每一个权值对应的所有样本的误差和,作为GA遗传算法的适应度函数的基础;

(5)将Map Reduce GA遗传算法优化完的权值作为训练BP神经网络的初始权值,开始Map Reduce BP神经网络训练,训练一定的次数,使样本的误差和达到人们所能接受的范围之内,或者预设定的迭代次数[7];

(6)训练完成后,使用检测样本统计比较检测结果[8]。

2 网络入侵检测系统设计与实现

2.1 系统的整体结构

提出的解决方案主要是针对当下海量数据,传统的入侵检测系统因为数据量大,不能快速、即时地进行检测,而且由于数据量大,致使权值调整过程是一个巨大的程序运行过程,最终要使检测率很低,通过使用本文提出的MRGA⁃BP均值法算法解决上述传统入侵检测的缺点。

基于云平台的入侵检测系统的检测流程一般为:首先使用一些工具收集数据,再对收集到的数据源进行预处理,然后再使用基于Hadoop云平台下的MRGA⁃BP均值法进行分析,根据已经训练好的神经网络预测改数据或者流量是否为正常行为,做出相应的预警,其流程见图3。

2.2 数据源采集

在数据源获取阶段,常用的获取数据源的部件是收发器、代理、适配器,获取的数据源主要来自于主机、网络、日志等。

2.3 数据源的预处理

由于数据预处理需要为后续进行入侵检测分析提供数据源,因此它对整个过程影响极为关键。在本次研究中,后续的处理是在Hadoop平台下BP神经网络中完成的,在进行训练时,需要特定的数据格式,因此在数据预处理阶段要对数据进一步处理,转换成BP神经网络能够处理的格式。在本阶段,预处理的数据源直接保存到Hadoop的分布式文件系统中。

因此,对数据源的预处理过程为:首先将源数据去除多余的字段以及多余的格式;将处理好的数据源保存到HDFS中。

2.4 数据存储

对于来自不同环境的数据源,可以将数据源先进行分类,在分类后的基础上进行存储,可以加快机器的运行速度。使用一个HBase分布式实时数据库,HBase是面向列的多维排序key⁃value表,可以对其进行实时操作。使用HDFS分布式数据存储,HDFS将数据放入集群中的每一个机器上,并且可以同时备份。

2.5 入侵检测Hadoop平台下MRGA⁃BP均值法

2.5.1 MRGA⁃BP均值法整体思路

在云平台下的详细流程图如图4所示。

(1)先使用Map Reduce GA算法实现对BP神经网络训练的初始权值的优化,将GA遗传算法优化后的初始权值输出到HDFS文件中,作为下一步神经网络的初始权值。

(2)使用预处理后的数据源,同时,输入初始权值开始神经网络的训练。直到训练结果的误差达到预期值或者迭代次数已经达到预先设定的值。

(3)输入测试样本,使用建立的BP神经网络预测出结果,与期望结果进行对比,判断检测率、误报率。

2.5.2 GA遗传算法的Map Reduce

因为GA遗传算法是对初始值的优化,将其应用到入侵检测领域就是对初始权值的优化,所以,要经过以下几个步骤:

(1)随机生成初始权值,这个初始值的生成由函数random()生成,每一个初始的权值是种群中一个个体,生成一定数量的初始权值,称为一个种群。

(2)执行Map函数,使用随机生成的初始权值计算种群中每个个体对应所有样本的误差,求和,误差之和作为种群中每个个体的适应度倒数。

(3)开始Reduce函数,通过Map输出误差,计算群体中每个个体的适应度fitness()。在Reduce()函数中,执行select(),cross(),muta()。到达最大迭代次数时停止。

2.5.3 BP神经网络算法的Map Reduce

利用BP神经算法是对神经网络的训练。它首先使用训练样本和Map Reduce GA优化后的权值训练网络,开始BP神经网络的多次训练,BP神经网络的训练在Hadoop平台下,相当于三个大型矩阵进行相乘,计算之后会得到样本的计算结果,和原来初始的入侵检测数据源形成一个新的HDFS文件,作为下一步进行Map Re⁃duce GA⁃BP均值法算法的输入,由于GA算法只是对初始权值的一个大致的优化,所以利用BP神经网络算法对权值进一步优化,让样本的误差和取到人们可以接受的范围,直到误差达到设定的范围内,或者是迭代次数达到最大时,停止训练,之后再使用测试样本,对样本是否为入侵行为进行预测。

在本次研究中,以海量入侵检测数据为数据源,经过预处理,保留对BP神经网络训练有益的数据属性,将字符串过滤掉,利用Map Reduce GA算法优化出来的数据源,通过分解出输入分量和预期结果,开始多次BP神经网络的训练。训练之后,将测试样本的数据源进行预处理,预测出测试样本的结果。

3 实验与实验结果分析

3.1 基于Eclipse的Hadoop程序开发环境

Hadoop平台搭建好之后,在Ecliepse环境下能够方便地开始Hadoop并行程序的开发和测试,将hadoop⁃1.2.1⁃eclipse⁃plugin.jar复制到eclipseplugins中,启动Eclipse。

在Eclipse界面下有一个Map/Reduce Location栏目,选择New Hadoop location,在相应的位置设置Hadoop运行环境。验证Hadoop环境配置是否成功,在浏览器的地址栏中输入:http://localhost:50070,检查namenode是否配置正确。

在浏览器输入http://localhost:50030检查9001端口是否正常。

创建一个Map Reduce Project,在项目src创建Package,bpnetwork和ga,分别添加Mapper类,Reducer类以及Map Reducer Driver类。

3.2 程序数据源说明

为了验证本文提出的基于云计算平台的入侵检测算法MRGA⁃BP均值法的可行性,测试使用该算法的预测入侵检测数据的精度,收敛速度,所以使用的测试数据和训练数据源均为KDDCUP99。该数据集包含多种入侵行为和正常行为,该数据类似于云环境中的数据,具有一定的意义。本文中试验检测的数据源分为训练样本和测试样本。

训练样本共有494 019个样本记录,正常行为97 276个,入侵行为396 743个。

设置实验的参数如下:

(1)输入:KDDCUP99中每一个样本共有38个属性值参与计算。因为本文预测是否为入侵数据源,所以将数据源最后的预期结果根据是否是正常数据源设定为1和0两个参数,0表示入侵检测病毒,1为正常数据源。

输入还有随机产生的权值文件。当网络训练结束后,可以进行预测。预测样本文件的处理和训练样本处理的方式一样。

(2)输出:程序的输出为网络的权值。输出还有预测结果。BP神经网络算法中的参数说明如表1所示。

3.3 实验结果与分析

实验的目的是对比在Hadoop平台下实现Map Re⁃duce BP神经网络、MRGA⁃BP均值法,MRGA⁃BP三种实现运行效率和效果。

3.1.1算法的收敛速度运行效率测试

对比项:Map Reduce BP、MRGA⁃BP算法、本文提出的MRGA⁃BP均值法。

数据源:完整的数据集为708.2 MB,10%的KDD⁃CUP99数据集(71.4MB)。

实验验证了本文提出的MRGA⁃BP均值法相比MRGA⁃BP在训练速度上确实有提高,原因是MRGA⁃BP中间产生很多结果,这些结果放入到内存中,当超出内存容量,数据就会在磁盘中写入临时文件,在这个过程中,有很多I/O操作,此外,每一次的Map阶段会输出很多结果传到Reduce端,这也是将时间延长的一个原因。根据以上分析,这两个原因导致MRGA⁃BP算法耗时较长。

3.3.2 算法的训练精度测试

对比项:Map Reduce BP,MRGA-BP均值法

评价指标:

通过上述实验,证明提到的MRGA⁃BP均值法和Map Reduce BP以及MRGA⁃BP在学习速度上有很大提高。对于相同的数据源,Map Reduce BP神经算法以及MRGA⁃BP均值法算法的比较结果证明GA⁃BP均值法在学习有效性方面也有较大的提高,同时也证明了本文的MRGA⁃BP算法的可行性。最终结果表明,该算法在执行的时间上也有提高,同时和Map Reduce BP相比具有更高的检测率。

4 结论

本文提出了MRGA⁃BP均值法作为入侵检测算法的核心,该算法采用并行化思想,首先利用遗传算法寻找最优的权值,寻找到最优权值后开始进行神经网络的训练,整个过程采用分布式计算平台Hadoop框架,将遗传算法和神经网络算法在云计算平台下实现,同时将算法进行改进,在入侵检测的效率和精度上有所提升。

参考文献

[1]颜谦和,颜珍平.遗传算法优化的神经网络入侵检测系统[J].计算机仿真,2011,28(4):141-144.

[2]胡宏,陈彦萍.基于随机森林算法的混合入侵检测系统研究[J].西安文理学院学报(自然科学版),2013,16(3):68-71.

[3]王杰,李冬梅.数据挖掘在网络入侵检测系统中的应用[J].重庆工学院学报(自然科学版),2008,22(8):135-138.

[4]陈真.Hadoop云平台的入侵检测系统优化设计[J].西安工业大学学报,2012,32(9):716-722.

[5]张新有,曾华燊,贾磊.入侵检测数据集KDDCUP99研究[J].计算机工程与设计,2010,31(22):4809-4812.

[6]陈英和,慕德芳,郝嘉佳.有效测量元认知监控的新方法:Master Mind任务分析[J].心理科学,2011(3):750-754.

[7]李军华,黎明,袁丽华.基于个体相似度交叉率自适应的遗传算法[J].系统工程,2006,24(9):108-111.

网络入侵检测算法研究 篇7

关键词：入侵检测,稀有类,集成学习,C4.5算法,AdaBoost算法

0 引言

网络入侵检测实际上是通过分析网络数据包来识别出正常和异常信息,从这个角度看,入侵检测过程可以看成是一个分类问题。而在大量的网络数据包中,只有少数的攻击信息,通常如果目标类在数据集中所占比例非常小(通常远低于10%)就称为稀有类,所以入侵检测问题又可以看成是稀有类分类问题。本文对现有的稀有类分类问题进行了研究,在对高速网络入侵检测系统模型研究的基础上,对网络数据包按照协议类型进行了数据分流,然后交给各个检测器[1],每个检测器都以C4.5分类器作为基分类器,用集成学习Ada Boost算法构造一个加强的总检测函数。实验数据采用DARPA(Defense Advanced Research Projects Agency)为1999年KDD(Knowledge Discovery and Data Mining)竞赛所建立的评估入侵检测系统的基准数据集,实验结果表明采用该方法可有效提高对稀有类的检测。

1 稀有类分类问题概述

由于许多实际问题的数据是不平衡的,如疾病诊断、欺诈识别、入侵检测等,因此对不平衡数据的分类问题是当前机器学习领域的又一研究热点。目前对该问题的研究主要有两个方面,一方面是在数据层面的处理,即把不平衡数据处理为一般数据集,对数据进行重抽样,包括过抽样和欠抽样两种。前者通过复制少数稀有类数据使之平衡而后者是通过删除多数普通类数据使之平衡。最简单的重抽样方法就是随机增加(复制)或删除部分样本,但其效果通常不理想,人们考虑得更多的是启发式的做法,如过抽样技术SMOTE。欠抽样常用的技术包括Tomeklink、一致子集、编辑技术(常用的是Wilson's editing)以及单边选择等,这些技术主要是启发式地利用(加权)欧氏距离以及K-近邻规则去识别可以合理剔除的样本[2]。

另一方面是研究特定的稀有类分类算法,主要有Ramesh Agarwal和Mhaesh.V.Joshi提出的PNrule方法及Hmad Alhammday和Kotgari Ramamohanarao最近提出的EPRC算法,Wei Fan等提出的Adacost基于代价敏感的学习算法、单类学习、集成学习等,其中集成学习方法在稀有类问题上的应用是当前的研究热点之一。集成学习方法是从机器学习领域逐渐发展起来的用于提升弱分类器分类准确率的技术,被认为是近十年来提出的最有效的学习思想之一。Bagging和Boosting就是通过改变学习样本进行集成学习的两种常见技术,虽然他们提高算法准确率的数学基础不完全相同,但是都试图通过合并多个弱分类器的输出以产生有效的“委员会”,从而改善算法性能。现有的集成学习方法主要使用决策树、神经网络及贝叶斯方法作为基分类器,并且主要用于提高普通分类器的分类准确率。

2 集成学习算法在入侵检测中的应用

2.1 AdaBoost算法

在PAC学习理论下,如果存在一个多项式计算法来学习一组概念,并且学习正确率很高,那么这组概念是强可学习的;而如果算法学习一组概念的正确率仅比随机猜测略好,那末这组学习是弱可学习的。M.Kearns和L.G.Valiant提出了弱可学习算法与强可学习算法的等价性问题,即是否可以将弱可学习算法提升成强可学习算法。如果两者等价,那么在机器学习中,我们只要找到一个比随机猜测略好的弱学习算法,就可以将其提升为强可学习算法,而不必直接去找通常情况下很难获得的强可学习算法。R.E.Schapire对这个重要问题作出了构造性证明,其构造过程就是Boosting。但这一算法要求事先知道学习算法的泛化能力下界,而这通常是难以获知的,因此并不能解决实际问题。Y.Freud和R.E.Schapire作了进一步工作提出了AdaBoost算法,这一算法不再要求事先知道泛化下界,具有较强的适用性[3]。

算法的主要思想是给定一弱学习算法和一训练集,初始化时对每一个训练实例赋以相等的权重,然后用该学习算法对训练集训练T轮,每次训练后,对训练失败的训练实例赋以较大的权重,也就是让学习算法在后续的学习中集中对比较难的训练实例进行学习,从而得到一个预测函数序列,其中也有一定的权重,预测效果好的预测函数权重较大,反之则较小。最终的预测函数对分类问题采用有权重的投票方式对新实例进行判断[4]。

Ada Boost算法(二值分类)的描述如下:

输入:

(1)一训练集S={(x1,y1)…,(xm,ym)}

其中xi∈X,yi∈Y={-1,1},i=1,…,m;

(2)弱分类学习算法WeakLearn;

(3)整型数T,表示训练最大轮数。

初始化:对每一个训练实例赋以相等的权重:

循环:t=1 to T

(1)调用弱分类学习算法WeakLearn,传递实例权值Dt;

(2)返回弱分类器ht:X→R;

(3)使用弱分类器ht对训练数据集S进行分类;

(4)选择αt∈R+;

(5)更新权值:

2.2 基分类器的选择

目前常用的分类模型主要有决策树分类、贝叶斯分类、神经网络分类、基于规则的分类、K-最近临分类等,其中C4.5决策树分类算法和Ripper基于规则的归纳学习算法是两种常用的入侵检测算法,在相同数据集上采用两种方法从准确率、召回率、F-度量等角度进行了比较,结果显示二者都表现出较好的分类效果,在实验一所用的数据集上的比较如表1所示,但从建模所用的时间上看C4.5算法所用的时间0.06秒比Ripper算法0.33秒要快的多,很适合高速网络实时入侵检测需要,所以本文采用了C4.5算法作为基分类器。

2.3 过抽样

过抽样方法通过增加少数类样本来提高少数类的分类性能,最简单的过抽样方法是复制少数类样本,但这样做不仅没有给少数类增加任何新的信息,反而会使分类器学到的决策域变小,从而导致过度拟合。Chawla提出了SMOTE技术[5],采用合成而不是简单的复制的方法进行增加少数类,从而有效避免了过度拟合。其基本思想是对每个少数类样本求k个最近邻数,然后随机选择的一个最近的多数类邻居样本,求与原少数类样本的全部属性差值,最后根据随机产生界于0、1之间的随机数字,产生少数类合成样本,直到每个少数类都产生n倍的合成样本。

3 实验与结果分析

本文所使用的实验数据是目前入侵检测领域比较权威的KDD CPU 1999数据集。该数据集是从一个模拟的局域网上采集来的9个星期的网络连接数据,数据集分为训练数据集和测试数据集两部分。其中训练数据包含了4898430个连接数据,测试数据集包含了311026个连接数据,其中一个完整TCP连接会话被认为是一个连接记录,每个UDP和ICMP包也被认为是一个连接记录,每条连接信息包含41个特征,分别属于4类特征集:基本特征、领域特征、流量特征和主机流量特征。其中基本特征是每条连接信息固有的特征,领域特征、流量特征和主机流量特征是Wenke Lee等人采用数据挖掘的方法,通过正常模式和入侵模式比较,提取出来的与入侵检测相关的特征。所有的数据记录划分为五类,分别是正常行为和四类入侵行为(Dos,U2R,Probing,R2L),每一类入侵行为中还包含若干种攻击。

3.1 数据预处理

实验选取kddcup.data_10_percent数据集,共有494021个连接记录,23个不同的连接标志,除“正常”外,其余22个代表攻击类型。由于在高速网络环境下数据流量大,为进行有效的入侵检测,采用了基于负载均衡机制的检测模型,其基本思想是将截获的大流量分割成几部分,每一部分由一个检测器进行检测,检测的结果提交给分析主机进行分析报警[1],因此本文按照协议类型对数据集进行了分类,即分为TCP、UDP、ICMP三个子数据集,每个数据集中记录特点如表2所示。

从表2可以看出,大部分的攻击都会在TCP数据集中出现,而UDP、ICMP数据集中的攻击类型较少,而且一些攻击只出现在某种数据集中,如pod、smurf攻击只出现在ICMP数据集中,而teardrop攻击只出现在UDP数据集中。同时,从数据分布看整个数据集严重不平衡,neptune、smurf所占比例较大,其余攻击所占数据集的比例都小于10%,甚至,除back在TCP数据集中所占比例为1.16%外,其余攻击所占数据集的比例都小于1%,因此,在KDD数据集中对攻击进行检测,实际是对稀有类的检测,必须采用有效的稀有类分类算法,才能提高系统的检测效率。

3.2 实验数据处理

本文所有实验均是在Intel core2 Q6600 2.4G CPU、3.25G内存、500G硬盘,操作系统Microsoft Windows XP,数据挖掘工作平台WEKA 3.5.8下完成,并采用了分层10折交叉验证方法统计了分类结果。下面列出了UDP数据集的实验结果。

实验选取了8000条normal记录以及全部的攻击数据。采用C4.5算法、用Ada Boost提升的C4.5算法(Ada Boost+C4.5)以及采用SMOTE增加少数类后,再对Ada Boost+C4.5的分类进行比较(SMOTE+Ada Boost+C4.5),如表3所示,其中SMOTE采用求5个最近邻数,产生1倍少数类的合成样本。结果显示对稀有类rootkit攻击的分类精度分别为0%、66.7%、88.3%。

3.3 实验结果分析

从实验结果可以看到,C4.5对稀有类的处理效果差,但如果采用Ada Boost算法对C4.5进行加强,可以提高检测率,但效果并不十分明显,主要是在原有的数据集中的攻击数量太少。如果采用SMOTE技术增加一些少数类,可以提高少数类的分类效果,如rootkit的分类精度从66.7%增加到88.3%,但对其他类分类效果基本没有影响,因此,今后将对算法做进一步的修改,来提高其他类的检测率,降低误报率和漏报率。

4 结束语

在网络入侵检测系统中如何从海量的数据包中准确、快速检测出攻击是当前急需解决的问题。本文在仿真环境下,以C4.5分类器为弱分类器,用集成学习方法Ada Boost算法提高弱学习器的网络入侵检测模型的分类性能,并用SMOTE过抽样技术对稀有类进行了合成,实验结果表明采用该方法可有效提高对稀有类的检测。但今后还需要采用一种更有效的抽样技术进行数据集预处理,以提高各类攻击的检测率。

参考文献

[1]赵月爱,彭新光.高速网络环境下的入侵检测技术研究[J].计算机工程与设计,2006,27(16):2985-2987.

[2]杨武,云晓春,李建华.一种基于强化规则学习的高效入侵检测方法[J].计算机研究与发展,2006,43(7):1252-1259.

[3]王珏,周志华,周傲英.机器学习及其应用[M].清华大学出版社,2006:170-171.

[4]Freund Y,Schapire R E.A decision-theortic generalization of on-line learning and an application to boosting[C]//proceedings of the2nd European Conference on Computational learning Theory.(Conf Euro COLT96),Barcelona,Spain:23-37.

网络入侵检测算法研究 篇8

基于免疫原理的入侵检测系统和免疫系统具有一定程度的相似性。它们要解决的问题都可以被描述为:识别“自体”和“非自体”, 并消除“非自体”。 在免疫入侵检测过程中, 使用免疫匹配规则都应该是针对二进制字符串的。采用何种二进制字符串的匹配算法, 这是一个十分关键的问题, 因为只有采用了合适的匹配算法, 才能有效地构造免疫检测器集。理想的计算机免疫系统应该是利用相对少的探测器字符串, 有效检测出更多的非自体, 并且使误报和漏报概率最小。毫无疑问, 两个二进制字符串之间最佳的匹配是两者相应位置上的字符都一样, 即两字符串完全相同。但是免疫系统中, 淋巴细胞检测NonSelf细胞很少出现最佳匹配, 绝大多都是局部匹配进行检测的。目前有很多的近似匹配算法, 如r连续位的匹配算法、海明距离匹配算法等。r连续位匹配规则能更好地反映抗体绑定的真实提取, 即能更真实地反映检测器字符串与被检测字符串的匹配情况, 所以它比海明匹配规则更常用, 因此文章采用r连续位的匹配算法作为研究对象。

1r连续位匹配算法

r连续位的匹配算法描述如下:对于任意的两个字符串 (x, y) , 如果两个字符串 (x, y) 相应位置上至少连续r位相同, 那么这两个字符串是r连续位匹配的, 即Match (x, y) |r=true。如图1所示, 对于r=4, 字符串x=“10101011”和字符串y=“10101101”, 由于它们在相应位置2～5位上都为“0101”, 所以是匹配的。

2r值对检测集生成的影响

2.1检测器的生成

检测器的生成是一个阴性选择的过程, 它与免疫系统的免疫耐受相似。阴性选择算法把Self作为系统的正常模式, 按照一定的匹配算法将随机生成的模式 (称为候选检测器) 与所有的被监测系统的正常模式进行匹配检测, 如果匹配成功, 说明该候选检测器对自体不耐受, 它将不能成为成熟检测器而被删除, 这样做能够有效地避免自免疫。该算法如图2所示。

该算法可以分为以下4步:①定义自体集合;②随机生成一个候选检测器;③将随机生成的候选检测器与自体集合中的每一个自体进行阴性选择, 若存在匹配就丢掉该候选检测器;如不存在匹配则该候选检测器成为成熟检测器;④重复②、③, 直至生成足够多的成熟检测器。

该算法中候选检测器是随机生成的, 因此生成的候选检测器只有很少一部分能通过筛选成为成熟检测器, 这降低了成熟检测器的生成效率。

2.2r值对检测集生成的影响

首先计算产生一个成熟检测器需要的迭代代数, 在r连续位匹配算法下, 任意两个长度为l的字符串x、y相匹配的概率是:

undefined

其中, 匹配参数r直接影响两个字符串之间的匹配概率, 当r减1, 两个字符串之间的匹配概率就成倍增加。因此当r越小, 则匹配的概率越高, 取极限, 当r=0, 则任意的两个字符串都能匹配;当r越大, 则匹配的概率越低, 取极限, 当r=l, 则任意一个字符串都需要一个与之每一位都相同的字符串才能匹配。

在r连续位匹配规则下, 式 (1) 已经列出了任意两个长度为l的字符串x, y相匹配的概率, 那么任意两个长度为l的字符串x, y不匹配的概率为1减去PM, 对于数目为NS的自体集, 那么任意一个随即产生的字符串与所有自体不匹配的概率是:

undefined

因此产生一个成熟检测器需要的迭代代数为:

undefined

3实验与分析

选用1999年DARPA为KDD (知识发现与数据挖掘) 竞赛提供的一个异常检测的标准数据集, 作为实验数据集。KDD CUP 99数据集是网络入侵检测的标准测试集, 为IDS研究人员提供训练数据集和测试数据集, 以期比较不同入侵检测方法的优劣。尽管该数据集是1998年建立的, 但仍是现在研究最多的IDS数据集。许多论文及研究成果都基于该数据集为研究基础。并从kddcup.data_10 _percent.gz中随机抽取3 595个正常数据集作为自体集。

实验首先经过阴性选择产生3 000个检测器, 产生的过程中采用r值的范围为[13, 15, 17, 19]。表1列出了不同r产生3 000个检测器所需候选检测器数目。

然后将不同匹配阈值r产生的3 000个检测器分别对测试集进行检测, 检测过程中匹配阈值rD=[r, 19]。试验测试集仍从kddcup.data_10_ percent.gz中随机抽取3 205个异常数据集和3 595个正常数据集作为测试集。这里假设自体集是完备的。将不同检测集分别对测试集进行检测, 检测结果如表2所示。

由表2中的数据可以得到以下结论:

(1) 在检测器数目相等的情况下, 较小r值产生的检测器在其对应的检测匹配阈值下具有更好的检测率。这是因为在r值较小的情况下, 较少的检测器就能很好地覆盖非自体空间。

(2) 随着检测匹配阀值rD的增大, 检测率逐渐降低。这是因为当rD越大, 则匹配的概率越低, 而检测的精确度就越高, 但需要检测器数量就越多。

接下来, 观察在候选检测器数目 (NDH) 相等的情况下, 采用不同r值产生的检测集的检测率。表3列出了不同NDH在不同r匹配阈值下对应产生的成熟检测集数。

图3显示了在不同NDH下, r值产生的检测集 (ND) 与检测率的关系。

由表3和图3可以得出以下结论:

当r值比较大时, 检测率提高的变化尤其明显, 而r值较小时, 这种变化不是很明显。这说明, 在r值较小的情况下, 较少的检测器就能很好地覆盖非自体空间。因此即使增多检测器数目, 只会造成检测空间的重叠, 而不会增大覆盖面。可以预测, 当检测器数目ND增大到一定数目时r=20的检测率会最高。

虽然随着检测集数目ND的增大, 检测率会随着增大。但这样会出现另一个问题, 就是检测时间的增加。在NDH=50 000的情况下, r=12产生的检测集对测试集进行检测的时间为15min, 而r=20产生的检测集对测试集进行检测的时间为53min。由此可见, 在固定r连续位匹配规则下, 检测精度和检测效率不能很好地兼顾。

4结语

文章主要研究r连续位匹配算法中匹配阀值r对检测器生成、检测精度和检测效率的影响。实验结果表明, 对于基于免疫机制的入侵检测系统, 检测精度和检测效率不能很好地兼顾, 也就是说如果需要提高检测精度, 就必须产生更多的检测规则, 因此也就需要更多的时间去运行。而检测规则的生成又依赖于匹配算法中的匹配阈值, 较小的r值固然可以降低检测规则生成时间, 但检测精度的改进空间不大, 而较大的r值的检测规则生成时间又比较长, 且检测精度的提高是以牺牲检测时间为代价的。因此如何改进匹配算法和检测规则生成方法是以后要研究的重点。

摘要：基于免疫原理的入侵检测系统中, 很重要的一环就是字符串的匹配, 现在的研究中主要采用的匹配规则是r连续位匹配。在r连续位匹配算法中, r值的大小决定着系统的时间开销和检测效率。因此, 研究r连续位匹配算法中r值的选择十分必要, 选择正确的r值可以在保持较少时间开销的情况下保证检测器的质量。

关键词：入侵检测,免疫原理,r连续位匹配,检测集生成

参考文献

[1]OSCAR A, FABIO A G, FERNANDO N, et al.Search and optimi-zation:a solution concept for artificial immune networks:a Coevo-lutionary perspective[C].Proceedings of 6th international confer-ence on Artificial Immune systems, Brazil, 2007.

[2]HOFMEYR S, FORREST S.Immunity by design:an artificialimmune system[A].Proceedings of the 1999Genetic and Evolu-tionary Computation Conference[C].1999.

[3]杨进, 刘晓洁, 李涛, 等.人工免疫中匹配算法研究[J].四川大学学报:工程科学版, 2008 (3) .

[4]唐俊, 赵晓娟.一种用于入侵检测系统的可变r匹配算法[J].计算机应用研究, 2010 (2) .

[5]张衡, 吴礼发, 张毓森, 等.一种r可变阴性选择算法及其仿真分析[J].计算机学报, 2005 (10) .

[6]王辉.可变模糊匹配阴性选择免疫算法研究[D].哈尔滨:哈尔滨工程大学, 2008.

[7]CANTU-PAZ E.Feature subset selection, class separability, andgenetic algorithms[A].Proceedings of the Genetic and Evolution-ary Computation Conf[C].2004.

网络入侵检测算法研究 篇9

计算机网络的广泛应用已经对经济、文化、教育、科技的发展产生了重要影响, 许多重要的信息、资源都与网络相关。客观上, 几乎没有一个网络能够免受安全的困扰。依据Financial Times曾经做过的统计, 平均每20秒钟就有一个网络遭到入侵, 而安全又是网络发展的根本。尤其是在信息安全产业领域, 其固有的敏感性和特殊性, 直接影响着国家的安全利益和经济利益。因此, 在网络化、信息化进程不可逆转的形势下, 如何最大限度地减少或避免因信息泄漏、破坏所造成的经济损失, 是摆在我们面前亟需妥善解决的一项具有重大战略意义的课题。

而入侵检测技术便是为保证计算机系统的安全而设计与配置的一种能够及时发现并报告系统中未授权或异常现象的技术, 是一种用于检测计算机网络中违反安全策略行为的技术。在检测机制中最重要的组成部分是多模式匹配算法, 它能有效地进行精确的模式匹配并且能够适应网络中数据量的不断增长。然而, 传统的模式匹配算法对于数据包的检测是不切实际的[1]。因为在庞大的模式库中, 一个有效的检测机制必须同时搜索整个模式集, 而不是重复执行单模式匹配。包的处理过程不仅受到计算时间的影响, 更重要的是受到访问外部存储器次数的影响。众所周知, 近年来处理器速度的性能提高超过存储器速度的性能提高。例如, 一个外部存储器访问时间是网络处理器系统Intel IXP2x00检测反应时间的150-250倍[2]。因此, 一个快速的多模式匹配算法应减少外部存储器的访问次数。

1 传统的模式匹配

根据需要匹配的模式串数目可以把模式匹配问题划分为两类:单模式匹配和多模式匹配。两者之间的不同在于单模式匹配算法是在文本中通过一次搜索仅仅匹配一个给定的模式, 而多模式匹配算法则要在整个文本中搜索一个模式集给出的所有模式。

1.1 Boyer-Moore (BM) 算法

单模式匹配是在长度为n的文本串y=y[0.n-1]中, 寻找一个或多个长度为m的模式串x=x[0.m-1]。

经典的单模式匹配算法有:Knuth Morris Pratt (KMP) 算法, Boyer-Moore (BM) 算法, KarpRabin (KR) 算法。在KMP算法中, 模式在文本串上从左向右滑动, 搜索每一个可能的匹配, 文本串中的每一个字符仅仅被检测一次。因此, KMP算法的时间复杂度是O (n+m) , n和m分别是文本串和模式串的长度。在BM算法中, 模式匹配是从右端而不是左端开始。当出现一个字符不能匹配时, 模式向右滑动, 文本串中的一些字符没有被检测而直接跳过了。在最坏情况下, BM算法的时间复杂度为O (n+r*m) , 其中, n和m分别为文本串和模式串的长度, r为文本中出现的模式串总数目。BM算法在一般情况下不需要检测文本串中的每一个字符, 这一点在英文字符串中尤为突出[3]。

在实际应用中BM算法是最有效的模式匹配算法。与其它经典算法相比较, BM算法能提供最好的平均匹配速度。一些模式匹配算法对每一个模式重复应用BM算法来解决多模式匹配问题。然而这些算法原本是为单模式匹配设计的。因为不同的模式长度、模式集范围以及内存存储能力, BM方法不适合网络中数据包的检查。表1显示了这些不同[4]。

1.2 Aho-Corasick (AC) 算法

多模式匹配是从文本串string[1.n]中一次查找多个模式串P1, P2, …, Pq;所有这些模式串形成模式串集合{P}, 其中q为模式串的数目, q=1时, 多模式匹配蜕化为单模式匹配。

多模式匹配的经典算法是基于有限自动机DFSA (deterministic finite state automata) 的算法[1], 该算法在匹配前对模式串集合进行预处理, 转换成树型有限自动机。然后只需对文本串进行一次扫描就可找出所有模式串, 其时间复杂度是O (n) 。这些基于DFSA的算法主要是通过软件或硬件来实现的。

Aho-Corasick (AC) 算法是一个基于自动机的算法, 它提供了最好的最坏情况下的计算时间复杂度[5]。通过用一个简单的数据结构, 存储状态转移矩阵的存储空间需求是O (|□|×S) , 其中S是自动机的状态数目, □是字符集, |□|表示字符集中的字符的数目。用一个压缩结构, Tuck等改进了AC算法 (AC-C) , 降低了AC算法内存需求的2%[6]。然而, AC-C算法的数据结构仍然很大, 不能放在片上的缓冲中。虽然, AC算法有最好的最坏情况下的计算时间复杂度, 但是对外部存储器访问的反应时间仍然是处理过程的主要影响因素而不是计算时间。另外, 即使仅仅只有一个模式改变了, AC算法必须重建失败表, 因为它的失败表是通过全部模式集的相互关联建成的。当增加或减少模式的时候, AC-C也需要重建完整的状态机。结果, 对于模式更新, 基于AC的检测机制不得不暂停, 暂停时间与P中所有模式的总长度成比例。

2 改进分级多模式匹配算法 (HMA)

BM算法主要应用于单模式匹配, AC算法对存储空间的需求又比较大, 以至于出现频繁访问外存的情况, 所以它们都不适合于实时网络数据包中多模式的匹配。基于以上原因提出了分级多模式匹配算法 (HMA) 。此算法包括两个阶段:线外预处理阶段和线上匹配阶段。线外阶段为线上阶段构造了两张小表:H1和H2[4]。HMA算法能有效地减少外存的访问次数和不以内存空间为代价的串匹配。

为了构造H1和H2表, 提出了一个频繁字符搜索算法 (FCS) 和一个集群平衡策略 (CBS) [4]。FCS是用来从模式集P中找出频繁字符集合F, 用它来建立第一层表:H1;用F和CBS建立第二层表:H2。H1和H2作为两个过滤器来避免不必要的外存访问和模式匹配。第二层匹配仅仅在第一层得到一个匹配之后才进行。HMA仅仅将P中的一些选定模式与包中的可疑子串进行比较, 而不是将包中的所有子串与所有模式进行比较。实验表明, HMA能有效地改善匹配的性能。

2.1 FCS算法

定义PC为P的子集, 在PC中的所有模式包含一个字符c, 即PC={pi|c∈pi和pi∈P}。显而易见, 假如一个字符在不同的模式中较其它字符出现的频繁, 它将被作为F中的一个元素, 这样则出现了小集合F。基于这一推论, 用FCS算法来查找P中的频繁字符集, 设为F={fi|fi∈□}, F是代表模式集P中模式的最小字符集, 其中fi是一个频繁代码, □为字符集。FCS算法如下所示。

输入:一个模式集P。

输出:一个频繁代码集F。

用一个|□|维向量M= (mi) 和一个|□|×|□|矩阵R= (rij) 作为临时存储, 其中0≤i, j<|□|。M是一个位图, 记录模式中每一个字符的出现。R用来记录发生的频率。对于rij, i≠j, 表示模式集P中ai与aj同时出现的次数。rii记录字母ai∈□在不同模式中出现的频率。例如, rij=2表示当前P中有两个模式包含ai与aj。首先, FCS算法在位图M中记录每个模式的字符出现, 然后积累M中的元素到R中各自相对应的元素 (2-4行) 。然后, FCS找到最大的出现频率rff, 把相应的字符af作为F中的一个元素, 然后把R中与af相关的元素进行值调整 (6-9行) 。FCS重复这一过程, 直到R中对角线上的元素全为零。

FCS从P中找到F之后, 就可以构造第一层表 (H1) 。H1的第a个条目表示为H1 (a) , 每一个条目有两个字段:频繁代码ID, 即H1 (a) .fid;单字符模式ID, H1 (a) .pid。即H1 (a) .fid={i|a=fi∈F}, H1 (a) .pid={i||pi|=1, pi=’a’和pi∈P}, H1中不用的字段置为NULL。由于H1是一个小表, 例如仅仅256个条目, 它能被放在片上缓存中。H1作为第一层线上阶段过滤器, 它能很快的发现是否一个包包含一个模式。即, HMA利用F减小了搜索范围。

2.2 引入模式树的集群平衡策略

通常, 大多数包是没有危害的, 有危害的包也仅仅包含一部分模式。假如能够根据P中模式的相似性将P分成不同的小集群, 然后仅仅一个集群的模式与输入串相类似需要比较。这样, 匹配过程的效率将会提高。

定义集群关键点作为划分模式的标准, 其中每一个集群关键点是模式中的字符。两个普通代码作为一对集群关键点, 称作一个关键对, 记作 (a, b) , 其中第一个关键点是F中的频繁字符, 第二个关键点是普通字符。用Pa, b表示选定模式 (模式的子集) 的集群, 它包含关键对 (a, b) , 即Pa, b={pi|’ab’奂pi, a∈F且b∈□}, 其中’ab’是两个串a和b的联合, 是一个pi的子串。因为一个模式可能有几种方式选择一个集群, 一个好的分配能够均衡集群的大小, 因此能够改善HMA在最坏情况下的执行效率。

为了降低最坏匹配时间, CBS用来平衡集群大小。在CBS中, 一个|F|×|□|阶矩阵N= (na, b) 用来记录一个集群Pa, b的当前大小。算法如下:首先, CBS从P中读出一个模式并扫描它。根据FCS, 对于任何给定的pi, 存在一个字符pi[k]∈F, 1≤k<|pi|。为了平衡集群大小, CBS在pi的所有关键对中找到最小的na, b, 记作 (a, b) , 其中a∈F和’ab’∈pi。在pi进入最小集群Pa, b之后, 相应的na, b是增加了。按照这一方法, 所有模式分进了指定的集群中。

在集群分配的基础上构造了第二层表H2。因为每个集群Pa, b都有很多个模式, 这些模式都含有子串’ab’, 要在这些模式中找到一个模式与数据包T中的某个含有’ab’的子串相匹配仍然是耗时的。所以, 将一个集群Pa, b的所有模式以关键对 (a, b) 为根节点向前向后分别建立两颗模式树。H2每个条目H2 (a, b) 由4个字段组成:模式ID H2 (a, b) .pid, 模式内容H2 (a, b) .data, 同一个集群中指向向后模式树指针H2 (a, b) .next和指向向前模式树指针H2 (a, b) .late。

图1描述了HMA中H1、H2的构造, 假定字符表是26个英文字母。图中有6个模式:a, red, orange, green, yellow, black。由FCS算法可知’e’和’a’是最频繁字符, 它们都出现在三个不同的模式中, 所以F={e, a}作为这6个模式的频繁字符集。由于H1仅仅有|□| (=26) 个字段, 所以它能够存放在片上缓存中。第一个模式’a’是单模式, 它存放在H1表中。模式’red’有’e’∈F以及关键对 (e, d) , 所以根据CBS, ’red’被放到集群Pe, d。剩下的模式使用同样的集群策略。

2.3 HMA算法的在线匹配过程

2.3.1 第一层匹配

在这个匹配阶段, 从左到右扫描T, 每个字符T[t]作为索引关键字去查找H1中的条目H1 (T[t]) 。由于H1是很小的可以放在微处理机制的内存中, 所以访问内存的时间与访问外存相比较小得多。

在第一层匹配中, 假如H1 (T[t]) .pid不是NULL, 那么T[t]是一个单字符模式, 这个被匹配的模式将被放入成功匹配模式集PM。无论H1 (T[t]) .pid是不是NULL, 这第一层匹配程序都检测fid字段。

假如H1 (T[t]) .fid是NULL, 则T[t]埸F, T[t]不进行模式匹配而跳过。然后, 在线匹配停留在第一层匹配, 进入下一个字符T[t+1], 检查H1 (T[t+1]) .pid。由于|F|比|□|小, T大多数字符能够发生跳动而不进行第二层匹配。因此, 字符比较的数目和外存访问的次数都能减小。

假如T[t]F, T可能包含一个模式pi∈P, 其中T[t]∈pi。也就是说, 由于H1 (T[t]) .fid不是NULL, T可能有一个模式 (或者多个) 属于集群PT[t], T[t+1]。然后第二层匹配开始执行。

2.3.2 第二层匹配

在第一层匹配之后, 只要H1 (T[t]) .fid不是NULL, 这匹配过程进行第二层匹配。根据输入T, H2 (T[t], T[t+1]) 显示相对应的集群PT[t], [t+1]的位置。

在第二层匹配中, 首先是检查H2的pid字段。假如H2 (T[t], T[t+1]) .pid是NULL, 它意味着集群PT[t], [t+1]没有模式。然后, 扫描下一个字符T[t+1], 匹配过程返回到第一层匹配。否则, 假如H2 (T[t], T[t+1]) .pid是有效的, 意味着集群PT[t], [t+1]中可能有模式匹配于T中的子串。然后, HMA将H2 (T[t], T[t+1]) 中的模式串内容与T中对应部分相比较。比较时先搜索向前模式树, 若成功, 再搜索向后模式树, 若还成功, 则将匹配成功的模式加入PM。以此类推, 最后得到包含所有匹配成功的模式集PM。

3 实验及分析

通过实验模拟, 将HMA算法与目前常用的BM算法、AC算法相比较, 其中BM算法、AC算法都已经用在IDSs中。Snort是最著名的NIDS, 其中的模式是由VRT提供和检测的。在这一模拟中, 不同的模式有200-2000个, 字符集|□|=256。含有可疑信息的数据包是通过随机选择模式和随机分布产生的[4]。攻击系数λ表示一个数据包中可疑模式的期望数。得出如图2所示的实验数据。

从图2可以看到HMA算法的性能要优于BM算法和AC算法, 即使|P|和λ增加也是如此。HMA的曲线随着λ的增加逐渐上升, 这是因为当数据包中有比较多的可疑模式时, HMA访问外存的次数会增加。

4 结束

网络安全在当今社会的各行各业越来越引起重视, 高效的多模式匹配方法是网络信息审计系统好坏的主要评价标准。本文章提出了一种分级的多模式匹配算法 (HMA) , 该算法在性能上明显优于其它类似的算法, 例如BM算法、AC算法。当然, 网络在迅速发展着, 攻击网络的方式方法也在不断变化着, 所以要求多模式匹配的模式库要不断更新, HMA算法的模式库更新还需要在以后的学习中深入研究。

摘要：多模式匹配的效率是网络内容检测的主要技术之一。本文在分析现有模式匹配方法的基础上——主要是BM算法和AC算法, 提出了分级的多模式匹配算法 (HMA) , 该算法适合网络数据包中模式数量大、长度小的特点。实验表明该算法能有效减少访问外存的次数, 性能明显优于其它算法, 这样可以有效保证网络信息安全。

关键词：网络安全,内容检测,多模式匹配

参考文献

[1]A.V.AHO, M.J.CORASICK, Efficient string matching:an aid to bibliographic search[J].Communications of the ACM18 (6) (1975) 330-340.

[2]Sridhar Lakshmanamurthy, Kin-Yip Liu, Yim Pun, Larry Huston, Uday Naik, Network pro-cessor performance analysis methodology[J].In-tel Technology Journal6 (2002) 19-28.

[3]FAN JANG-JONG, SU KEH-YIH.An effi-cient algorithm for match multiple patterns[J].IEEE Trans on Knowledge and Data Engineer-ing, 1993, 5 (2) :339-351.

[4]Tzu-Fang Sheu, Neu-Fu Huang, Hsiao-Ping Lee.Hierarchical multi-pattern matching algo-rithm for network content inspection[J].Informa-tion Science178 (2008) :2880-2898.

[5]GRAHAM A.STEPHEN, String Matching Algorithms[J].World Scientific, 1994, ISBN981-02-1829-X.

网络入侵检测算法研究 篇10

1 蚂蚁聚类算法

基于蚁堆原理的聚类算法是蚂蚁聚类算法的一种,该算法是一种基于群体智能(Swarm Intelligence,SI)的仿生算法,它模仿的是蚂蚁战争过后蚂蚁清扫战场的行为。蚂蚁在战争后会在“战场”上遗留下很多尸体,负责清扫“战场"的蚂蚁通过在“战场"内移动、背负蚂蚁尸体、放下蚂蚁尸体等操作最终将分散的尸体堆积成一些尸体堆,这实际上是一种聚类的行为。通过这种行为衍生的聚类算法模拟蚂蚁通过对局部环境进行判断来对数据进行“拾起”和“放下”操作,各个蚂蚁间完全独立,无需通信。一般的聚类算法如K-平均算法等对聚类初始化聚类个数很敏感,初始化聚类个数的多少直接影响到聚类的结果。而蚂蚁聚类算法不需要预先指定初始化聚类个数,因此它能够克服传统聚类中初始化敏感度高的缺陷,改善聚类的效果。

算法流程如下:

Step 1初始化蚂蚁数number,二维平面大小,循环次数count,记忆空间长度L,循环计数值c=l等等。

Step 2将数据对象和蚂蚁都随机置于二维平面上,二维平面上的任何一个位置最:多只能放置一个数据或者一个蚂蚁。

Step 3开始聚类循环,c←c+1,如果c≤count,转到Step 4;否则转到Step 10。

Step 4选择一只蚂蚁。

Step 5蚂蚁在二维平面上随机运动,如果蚂蚁遇到一个数据对象,计算蚂蚁拾起该对象的概率Ppick(i)。

Step 6如果拾起概率Ppick(i)较小,蚂蚁不拾起数据对象,蚂蚁仍然是无负载状态,并继续随机运动,转至Step5;如果拾起概率Ppick(i)较大,蚂蚁拾起该对象,蚂蚁的状态改为有负载,并继续随机运动。

Step 7若蚂蚁是有负载状态,当它运动到一个空的位置时,计算放下该数据的概率Pdrop(i)。

Step 8如果放下概率Pdrop(i)较小,蚂蚁不放下数据对象,蚂蚁仍然是有负载状态,并继续随机运动,转至step 7;如果放下概率Pdrop(i)较大,蚂蚁放下该对象,蚂蚁的状态改为无负载,继续随机运动并拾起一个数据对象。

Step 9若组内所有的蚂蚁结束移动则转到Step 3,否则转到Step 4。

Step 10循环的次数达到count,输出聚类结果,程序结束。

文献[1]中将该模型用于几个数据集上,经过一段时间的迭代后,结果呈现出较为明显的聚类特征。该模型以其并行和分布式特征引起了许多研究人员的关注。该模型有一些不完善的地方:数据的实际类数未知时,f(i)无法求取;蚂蚁的种类单一,导致所聚得的类数过多等缺点。针对这些缺点,本文提出了一种改进的蚂蚁算法。算法改进的目的是解决原算法中聚类分散、存在较多孤立点等问题,改善聚类的效果。通过增加“新聚类蚂蚁”,在“聚类蚂蚁”进行随机运动操作数据元素的同时,“新聚类蚂蚁”在所属的簇周围进行搜索,将与该簇类似的数据元素归并到簇中,并进行相似簇的融合操作,加速聚类的进程。同时,“聚类蚂蚁”找出周围最不相似的数据元素,用于当“聚类蚂蚁”运动到该簇所在位置时,让“聚类蚂蚁”优先“拾起”该数据元素,提高了聚类的正确性。

2 改进的蚂蚁算法

基于蚂蚁堆尸原理的聚类算法与大多数聚类算法不同,它是通过每一只蚂蚁的无规则运动,根据数据间的相似度来自动地进行数据聚集,蚂蚁需要的信息仅仅是它所处的局部环境中的数据分布,不需要预先指定聚类数目信息。而大多数聚类算法如K-MEANS算法等,都需要预先指定聚类地数目,如果预先给定的聚类数目过大或者过小,将直接影响到聚类的结果。蚂蚁算法不需要预先知道聚类的数目,这对于无监督的异常入侵检测来说是很有利的。根据文献[1]中的假设,正常数据与异常数据由于其本身的差异较大,将最终被聚类到不同的簇中。对于未知的入侵,根据它与正常数据的差异性,也将被聚类到另外的簇中。蚂蚁算法可以自动地将数据聚类,而聚类的结果则反映了数据本身的相似性,不同类型的数据会被聚类到不同的簇中,所以蚂蚁算法的思想很适合用于入侵检测的。但是蚂蚁聚类算法还有诸如效果不是很好、会出现较多游离点等缺点,本文将结合无监督异常入侵检测的特点,对蚂蚁算法进行改进,提出一种增强型蚂蚁聚类算法,让其更好地应用于入侵检测。

新的算法主要改进点有:

1)添加一种“新聚类蚂蚁”。

2)给“聚类蚂蚁"添加快速能动的能力。

3)改进蚂蚁的“拾起”操作,增强“聚类蚂蚁”在“拾起”操作中对数据元素的选择性。

4)改进蚂蚁的“放下”操作,优先尝试将数据元素“放下”到已经存在的簇中。

5)密度和速度相关的算法操作。

3 新算法的实现

3.1 定义数据元素的结构体

struct DataObject

{

int x;∥数据元素在二维网格平面上的X坐标

int y;∥数据元素在二维网格平面上的Y坐标

double*m_pDate;∥指向数据元素的指针

int clusterId;∥该数据元素所在簇的标号

bool isMoved;∥该数据元素是否被操作过

bool isClustered;∥该数据元素是否已经被归并到某个簇中

bool isOccupied;∥是否被“聚类蚂蚁”占据

};

3.2 定义“聚类蚂蚁”的类

class ClusterAnt

{

public:

int m_nX;∥蚂蚁在二维网格平面上的X坐标

int m_nY;∥蚂蚁在二维网格平面上的Y坐标

int m_nPropNum;∥数据元素的维度数据元素的维度

bool m_bIsLoad;∥蚂蚁是否是负载状态

int m_nDataPosition;∥蚂蚁背负数据元素在整个数据元素∥数组中的序号

}

3.3 定义“新聚类蚂蚁”的类

因为“新聚类蚂蚁”与它所在的簇是一一对应的,所以该类同样也表示一个簇

class NewClusterAnt

{public:

int clusterId;∥聚类标号,及聚类蚂蚁的标号

int memberNum;∥“维护蚂蚁"所在簇中成员总数

double clusterR;∥“维护蚂蚁”所在簇的真实半径

int clusterS;∥“维护蚂蚁"的搜索半径

DataObject*m_ptrue;∥“维护蚂蚁”所在簇的真实中心的向量

int centX;∥“维护蚂蚁"所在簇的“虚中心”X坐标

int centY;∥“维护蚂蚁"所在簇的“虚中心”X坐标

int maxdiffId;∥簇周围最不相似数据元素在数据元素数组中的序号

Cluster*next;∥指向下个簇的指针

};

3.4 算法伪代码

增强蚂蚁算法依据“新聚类蚂蚁"的存在与否,可以分为两个阶段:(1)“新聚类蚂蚁”产生前,即初始聚类阶段;(2)“新聚类蚂蚁”作用阶段。

1)初始聚类阶段

2)“新聚类蚂蚁”阶段

4 基于增强蚂蚁聚类算法的入侵检测方法的实验模型设计

基于增强蚂蚁算法的入侵检测主要有四个模块组成:数据收集模块,数据处理模块,增强蚂蚁聚类处理模块,检测模块。

4.1 数据收集模块

该模块是整个入侵检测的基础。入侵检测的数据源有系统日志、安全审计、网络数据包等。本文中,采用KDD CUP99数据集作为训练数据集和检测数据源。KDD CUP99是真正的网络数据集,对于KDD CUP99中的每一条记录,都通过检测记录中是否包含有攻击行为或者攻击行为的类别,把该记录标记成为正常记录或者是某种攻击的记录,这些标记都是正确可信的。因此,在基于蚂蚁聚类算法的入侵检测中,将每一个特征向量作为聚类的对象,对其进行聚类处理和分析,并将得出的结果与该数据集的真实情况进行比较,从而可以得出这种入侵检测方法的效果。

4.2 数据处理模块

KDD数据集中包括了通过模拟得到的大量不同类型的攻击数据,包含大约490万条数据记录,每条记录包含41个特征值。如果将所有记录都用于入侵检测中,必然耗费大量的时间。由于本文的蚂蚁聚类算法是应用于无监督聚类的入侵检测中,这种入侵检测方法对于数据集中的入侵记录所占的比率十分敏感,如果入侵的数量太大,入侵在表现形式上就不会被看作是入侵,最终归为正常数据,影响检测的结果。同时,由于每一条记录中41个特征向量有的是字符型数据,有的是数值型,有的是连续型,有的是离散型,没有统一的标准,这将影响蚂蚁聚类算法中数据元素相似度的计算。所以必须首先对数据集进行分割、过滤,对所选的特征值进行标准化,然后再运用算法进行实验。

4.3 增强蚂蚁聚类处理模块

增强蚂蚁聚类模块是整个入侵检测的核心部分,该模块主要是通过增强蚂蚁聚类算法对训练记录进行聚类分析,将训练记录归并为不同的簇。

4.4 检测模块

检测部分首先将聚类结果进行标记分类,这根据文献[1]中提出的两个假设来判别:1)正常行为的数目远远大于入侵行为的数目;2)入侵的行为和正常的行为差异非常大。所以,对于聚类的结果,先设定一个表示簇中数据元素个数的阈值。将簇中数据元素个数小于这个阈值的簇标记为入侵记录的簇,而数据元素个数大于这个阈值的簇标记为正常记录的簇。然后将检测记录在标记过的聚类基础上再进行聚类操作。通过计算每一条连接记录与每一个聚类中心的距离,找出距离最小的聚类中心,将该连接记录聚类到该类中。如果该类在被标记为正常记录类,则认为该条连接记录是正常记录;如果该类被标记为入侵记录类,则认为该条连接记录是入侵记录。将检测数据聚类完毕以后,要分析检测的效果。对于入侵检测来说,检测的主要标准有两个:

检测率=算法检测到的入侵记录数/数据集中的入侵记录数

误报率=被误认为入侵的正常记录数/数据集中的正常记录数

该模块最后通过计算检测结果的检测率和误报率来分析检测的效果。

5 实验结果和分析

本文实验主要分二步,第一步是计算增强蚂蚁算法生成的训练集的检测率和误报率,分析增强蚂蚁聚类算法用来建立训练集模型的效果。第二步是计算所生成的训练集对检测数据的检测率和误报率,分析算法对于入侵检测的效果。同时,本文使用另外一种算法进行实验:需要初始划分信息的经典聚类算法之一的K-MEANS算法,用它与增强蚂蚁聚类算法进行对比。

5.1 训练结果比较

选取记录总数为500条、800条、1000条、2000条和3000条的5个KDDCUP 99数据集的子集,他们的入侵数据比例都为5%,利用增强蚂蚁算法进行聚类分析,然后对聚类结果进行分析,计算所得的训练结果的检测率和误报率。同时,将3000条记录的子集用K-MEANS算法进行聚类分析,然后计算训练结果的检测率和误报率。双重蚂蚁算法的训练结果如表1所示,K-MEANS算法的训练结果如表2所示。

从表1检测出的检测率和误报率结果来看,在5%的入侵记录比例下,对于入侵的检测率比较高,而且记录条数的多少对检测率的影响不大。这主要是由于在结果分析时,将数据元素个数少于训练集记录总数10%的簇中的全部数据元素认为是入侵记录。由于入侵记录本来较少,它们形成的簇也很小,能够被正确地划分为入侵记录。因此,检测率很高。但同时由于不可避免地有一些正常记录数据会形成一些很小的簇,或者有的正常记录被划分到入侵记录组成的簇中,这些正常记录被误认为是入侵记录,造成有误报率的结果。同时,通过实验发现随着记录总数的增加,误报率也会变大,这主要是小型簇增加的结果。

从表2可以看出,K-MEANS算法的训练结果随着K值的变化而变化,这正是此类算法对于初始聚类信息的敏感性所在。在表中,K=20时的训练效果最好。

通过比较增强蚂蚁算法和K-MEANS算法的训练结果可以看出,增强蚂蚁算法在无需知道初始划分信息的情况下,能够得到较好的训练结果,检测率比K-MEANS算法要高。虽然误报率比K-MEANS算法高,但综合起来还是增强蚂蚁算法的效果好。

5.2 检测结果比较

用记录总数为3000的训练集分别用增强蚂蚁算法和K-MEANS算法(K取值为20,由实验一可以看出K=20的训练效果最好进行训练,然后选取了记录总数为5000的检测数据在此训练集上进行检测。检测结果如表3所示。

从实验结果可以看出,通过增强蚂蚁聚类算法进行训练的训练集,对检测数据有较高的检测率和较低的误报率。同K-MEANS算法相比,虽然增强蚂蚁算法的误报率相对较高一些,但是检测率比K-MEANS算法要高的多。

6 结束语

通过实验发现,增强蚂蚁聚类算法在应用于入侵检测时,有较高的检测率和较低的误报率。所以增强蚂蚁聚类算法应用于基于无监督聚类的异常入侵检测,是可行且有效的。

参考文献

[1]Lumer,E.&Faieta,B.Diversity and adaptation in populations of clustering ants.InProceedings of the Third International Conference Oil Simulation of Adaptive Behaviour:From Animals to Animats3.Cambridge,MA:MIT Press.[C]1994:501-508.

[2]张云涛,龚玲.数据挖掘原理与技术[M].北京:电子工业出版社,2004.

[3]赵伟丽,孙艳蕊,张志国,李金娜.基于信息熵的蚁群聚类算法的改进[J].沈阳化工学院学报,2005,19(4):296-300.

[4]余研,黄皓.基于改进多目标遗传算法的入侵检测集成方法[J].软件学报,2007,18(6):1369-1378.

[5]肖立中,邵志清,钱夕元.一种用于网络入侵检测的杂交聚类算法研究[J].计算机工程,2007,33(4):125-127.