Research of Intrusion Detection Arithmetic Based on Density and Grid
　　WANG Gan
　　(School of Electronic and Information Engineering, Lanzhou jiaotong University, Lanzhou 730070, China)
　　Abstract: A hybrid clustering algorithm based on density and grid is used in this paper to construct an anomaly detection algorithm which benefits intrusion detection system.By effective combination of density-based clustering algorithm and grid-based clustering algorithm,The arithmetic is used better in the present intrusion detection of high flow.In the end,the results that KDDCUP99 data set was used to test the arithmetic show that the algorithm can get ideal detection rate,false detection rate and it has better system performance.
　　Key words: density clustering；cluster grid；hybrid clustering；intrusion detection
　　随着计算机网络的迅猛发展和网络规模的不断扩大，网络安全问题日益突出。传统的杀毒软件和防火墙已经不能完全应对日趋严重的网络安全问题，主动防御的入侵检测系统（Intrusion Detection System，下称IDS）成为近年来的研究热点。现今的IDS主要分为基于误用检测算法和基于异常检测算法两种，基于误用检测算法依赖于一个特征库，正因如此，倘若该特征库中没有包含某种新型攻击，算法对该攻击将无能为力；而异常检测算法针对用户的正常行为建模，当模型建立好后，运行于网络环境中的IDS检测到网络流量或操作系统审计特征超出正常行为模型之外时，就认为入侵发生了。但因异常检测存在对整个系统的所有用户行为描述的完备性问题，涉及大量的数据处理，导致其误检率较高，系统性能不甚理想。
　　数据挖掘技术是一项通用的知识发现技术，它能较好地从海量数据中提取对用户有用的数据。其中的聚类分析近年来成为数据分析领域的一个研究热点。将聚类算法应用于入侵检测中，势必提高入侵检测的性能和减少误检率。本文就是将聚类分析中的密度聚类算法和网格聚类算法有效结合应用于入侵检测的异常检测中，下面将分别对基于密度聚类算法和基于网格密度算法进行简要介绍，并给出一种新的二者结合算法，最后给出实验后其与现有一些算法的性能对比，证明其确实提高了系统性能和拥有较小的误检率。
　　1 相关聚类算法简介
　　基于密度的代表算法DBSCAN（Density-Based Spatial Clustering of Applications with Noise）利用类的密度连通特性，可以快速发现任意形状的类，这样不再局限于只能发现类球形的簇。其算法思想是：对于一个类中的每一对象，在其给定半径（Eps）的邻域中包含的对象不能少于某一给定的最小阀值（MinPts）。但其缺点是需要大量的内存和I/O开销，时间复杂度为O(NlogN) (N为数据量)、偏高，还有对参数Eps和MinPts很敏感，不易确立。
　　基于网格聚类算法
　　该算法思想是首先将数据空间量化为有限个单元的网格结构，然后对量化后的单个的单元为对象进行聚类。典型的算法有STING（Statistical Information Grid），CLIQUE等。网格聚类法处理速度快，处理时间与数据对象的数目无关，一般由网格单元的数目决定，时间复杂度近似为O(N)。缺点是只能发现边界是水平或垂直的聚类，不能检测到斜边界，而且生成的簇精度稍差。
　　2 基于密度和网格混合聚类算法分析
　　上文已经提到基于密度聚类和基于网格聚类的各自不足，为了克服其不足，这里引入一个概念：网格相对密度（The relative density of the grid）RDG。通过计算网格单元与其非空邻接单元相对密度的平均值来定义两者之间的密度差异。本算法的思想就是结合基于密度的方法可以发现任意形状的簇和基于网格的处理速度快的优点。
　　2.1 相关定义
　　数据空间：给定一个有界的n维数据集D={D1，D2，…Dn}，取值区间为[lowi，highi ），那么DS=[low1，high1 ）*[low2，high2 ）*…[lown，highn ）就是n维数据空间；
　　网格单元：把n维数据空间划分为M个长度相等但不相交的左闭右开区间，从而数据空间DS被划分为Mn个不相交的矩形单元，这就是网格单元，记为Ui，Ui={ui1,ui2,…,uin}；
　　网格密度：落入网格单元Ui中数据点的个数即为网格密度den(Ui)；
　　邻接单元：当且仅当两个网格单元有相邻的边界或相邻点时，称这两个网格单元为邻接单元；
　　RDG：某网格的网格密度与它的非空邻接单元网格密度平均值的比；
　　核网格：如果某网格的RDG大于或等于1，意味着网格单元密度较大且一定属于某类，把该网格定义为核网格；
　　直接网格密度可达：如果两个属于邻接单元的网格单元Ui和Uj满足den( Ui)≤den(Uj)*(1+pct) 且 den(Uj)/(1+pct)≤den(Ui)pct是预先定义好的密度波动阈值，则Ui和Uj互为直接网格密度可达；
　　网格密度可达：网格序列U1，U2，…，Un满足Ui直接密度可达Ui+1，那么称U1网格密度可达Un；
　　基类：数据集中某非空子集C满足极大性（某核网格U0属于C）且连通性（任意Ui是基于U0密度可达的），则C是一基类。
　　2.2 算法描述
　　每次先从数据空间中找寻一个核网格U0，按广度优先遍历原则以U0为起点开始聚类，找出所有到核网格U0密度可达的网格单元，形成一个基类，这是一次聚类结束，接下来方法一样找寻其他核网格继续聚类形成新的基类，等基类全部搜寻完后，再对剩下的边界点进行提取，保证所有的网格都得到有效处理。
2.3 混合聚类算法步骤
　　算法输入：数据集D，网格数M，密度波动阈值pct
　　算法输出：聚类结果
　　算法步骤：
　　1）将特征提取后的n维嵌入数据空间的每一维分为M个等长的单元，从而将数据空间划分为Mn个网格单元；
　　2）① 将特征提取后数据集D中每个点映射到相应的网格单元中，进行数据分箱，以使数据规格化；② 计算网格单元的密度；
　　3）计算每个网格的网格相对密度RDG，并判断其是否为核网格；
　　4）如果存在未被聚类的网格单元中还存在着核网格，执行下面三步：① 从未被聚类的网格单元中任意取一核网格G0；② 从核网格G0开始搜索，求所有从G0基于网格密度可达的网格单元Gi；③ 进行聚簇边界点处理。 (责任编辑：南粤论文中心)转贴于南粤论文中心: http://www.nylw.net(南粤论文中心__代写代发论文_毕业论文带写_广州职称论文代发_广州论文网）