（计算机应用技术专业论文）基于数据引力的分类方法及网络异常检测模型的研究.pdf

摘要 近年来，伴随着计算机网络的飞速发展，网络入侵事件也日益猖獗，而传统的 网络安全技术如反病毒技术和防火墙技术要防范入侵比较困难，这就使得入侵检测 成为网络安全研究体系中的一个重要的组成部分。在入侵检测技术中，基于规则的 误用检测技术发展比较成熟，但由于该项技术的一些本质局限性，使其成为入侵检 测技术中的一种低级形式，发展空间也相对有限。而异常检测技术作为入侵检测技 术的一种比较高级的形式，已经成为入侵检测研究领域的热点。异常检测技术最大 的优势在于它能根据已知的入侵模式检测出未知的入侵。数据挖掘、神经网络、支 持向量机等许多技术都可以用于建立异常检测模型。 本文将物理世界中的万有引力概念和万有引力定律引入到数据分类问题中，提 出了一种新的数据分类方法d g c ( d a t ag t a v i t a t i o nb a s e dc l a s s i f i c a t i o n ) ，并基于该 理论建立了一种高效的异常检测模型。d g c 将数据空间中各数据点之间的相似性定 义为数据引力，认为数据空间中任何两个数据点之间都存在数据引力，克服了传统 数据挖掘技术中用局部联系的观点对待数据的缺陷。在数据引力的基础上，本文提 出了数据空间中数据引力定律，给出了数据引力的计算方法，并通过对数据引力大 小的比较，对数据进行分类。 在d g c 理论的基础上，本文针对异常检测中特征选择的问题，进一步提出了 特征加权的思想，并用一种尝试性随机选择算法对特征的权值优化。在d g c 算法 模型中通过对加权特征进行选择，建立了d g c 的改进算法模型w d g c ( f e a l l r e w d g l l t e dd g c ) 。 通过对数据挖掘中的高维度数据的自动子空间聚类算法( c l i q u e ) 研究，本 文借鉴c l i q u e 聚类算法关于高维度数据空间单元划分的思想，将该思想引入到异 常入侵检测中，提出了一种基于高维度数据单元划分算法h d u p ( h i g l l d i i n e i l s i o n d a t au 血p 确t i o n ) ，并基于该算法理论建立了一种对高维度入侵检测数据有效的异 常检测模型。 实验结果表明，基于d g c 愚d g c 和基于h d u p 的异常检测模型与传统的异常 检测模型如神经网络、c 4 5 决策树等相比，有着比较高的检测精度，并且在误报率 和漏报率等各项重要评价指标上均有比较理想的效果。 在异常模型建立的理论工作之外，本文研究了几类典型的攻击，分析了它们的 特征，在此基础上，研究并实现了几种原始数据的采集方式。这几种原始数据的采 集方式涵盖了主机网络数据包的采集、0 s 审计日志和网络流量统计特征的采集等 各方面。在原始数据的预处理方面，本文以) d 9 9 入侵检测数据集的特征集为框 架，采用该特征集的一个有效子集对原始数据特征提取分析。 关键词：入侵检测，异常检测，数据引力，数据分类 济南大学硕士学位论文 a b s t r a c t b yt l l ef 如td e v e l o p m e mo fc o m p u t e rn e h r 0 1 r ki i lr c c e n ty e a r s ，n e t w o r ki j l 口i l s i o n a c c i d e n t sa i s oo c c l l rm o r ea n dm o r e 矗e q u e n t l yt r a d i t i o n a in e t 、v o r ks e c u t yt e c h n o l o 舀e s s u c ha s 锄t i - v i n l sa n df i r c w a l la r en o tv e 叫e 艉c t i v ei nd e t e c t i n gi i l 仃1 l s i o n ，s oh n l s i o n d e t c c t i o nb e c o m e sa ni m p o r t a n tr e s e a r c ha r e ai nn e t 、v o r ks e c u r i t yr e s e a r c hs y s t e m a m o n g i n t m s i o nd e t e c t i o nt e c h n o l o g i e s ，m i s u s ed e t e c t i o ni sat e c h n o l o g yb a s e do n 兀l l e s m i s u s ed e t e c t i o ni sak i n do fl o wl e v e li i l 妇i o nd e t e c t i o nt e c l l n o l o g yb c c a u s eo f 蛔 e s s e i n i a ll i m i t a t i o i la sak g hl e v e lf o n no fi n 仃u s i o nd e t e c t i o nt e c l l n o l o g y a n o r n l a l y d c t e c t i o nh a sb e c 鲫et h em o s tp o pt o p i ci n i n 打1 1 s i o nd e t e c t i o nr e s e a f c h t h em o s l i n p o r t a n ta d v a n t a 窖eo fa n o m a l yd e t e c t i o ni sm a ti tc a nd e t e c t 止n o w ni n t r u s i o n s a c c o r d i n gt ok n o w ni 1 1 劬娼i o np a n e m s m a i l yt e c h n o l o 西e ss u c ha sd a t am i n j n g ，n e u r a l n e t 、o r ka n ds u p p o r tv e c t o rm a c l l i n ec a i lb eu s e dt 0b u i l da n o r n l a l yd e t e c t i o nm o d e l - t 1 1 i sp a p e ri n 舶d u c e d 呲i v e r s a l 口a v i 诅t i o na n dt h cl a wo fg r a v i t a d o ni n t od a t a c i a s s 访c a t i o np r o b l e m ，p r o p o s e dan o v e ld a t ac l a s s i f i c a t i o nm e m o dc a l l e d l cd a t a g m v i 诅t i o nb a s e dc l a s s i 矗c a t i o n ( d g c ) a n db 哂l dah i 曲e 虢c t i v ea n o r n l a i yd e t e c t i o n m o d e lb a s e do nd g c d g cd e f i n e st i l es i m i l a r i t yb e t v e nd a t ap o i n t si nd a t as p a c e 舔 d a t a 刚协c i o n ，a n dt h e r ee x i s td a t ag m v i t a t i o nb e t w e e na n y “v od a t ap o i n t si i ld a 诅 s p a c e t l l i ss t a l l d p o i n ti sd e 疵k m 舶m 也e 蛐d p o mo f 订a d i t i o 叫d a 诅m i n 访g t e c h n o l o g i e s ，b e c a u s e 仃a d i t i o n a ld a t am i i l i n ga l w a y st r e a t ed a t ap o i i l t si nal o c a ls c o p e b a s e do nd a t ag r a v i t a t i o i l t h ep 印e rp r o p o s e dt h el a wo fd a t ag r a v i 枷o n ，a n dg a v em e m e m o do fda _ t ag r a v i t a t i o nc o m p u t a t i o n b yc o m p a r i n gt l l ev a l u eo f 出曲伊a v i t a t i o n ，d a 协 c l a s s i 丘c 甜o nc a nb ep e r f b 蛳e d b a s e do nt h ed g c t h e o 彤t h ep a p e rp r o p o s e dat l l i n l d i l go fw e i 曲t e df b a n si t l o r d e r t os o l v et l l ef b 籼es e i e c t i o np r o b l e mi i la i l o 硼a l yd e t e c t i o n ，a i l ds e l e c tf e a n l r e sb y w e i g l l t si i ld g c m o d e i an e w a i g o r i t h mc a 王l e dt e n t a t i v er a n d o ms e i e c t i o na l g o 打【l l mh a s b e e nu s e dt oo p t i m i z e 也ew e j 曲t so ff b 蛔e s 1 1 1 i si m p r o v e dd g cr i l e t l l o di sc a l l e d t t t 基于数据引力的分类方法及网络异常检测模型的研究 f e a t u r e - w b i g h t e dd g c ( w d g c ) b ) ，s h i d y i n gc u q j ec l u s 蜘n ga l g o 咖n md a 诅m i 血g ，“sp a p e ra l s o i n 的d u c e dm et l l i n l ( i n go fu m tp a 砌t i o nmm 曲d i n l c n s i o n a ls p a c ei n t 0a i l o m a l y d e t e c t i o n ，a n d p m p o s e dan o v e ld e t e c d o nm e 1 0 db 鲢e do nh i g h - d i r n e n s i o nd a t au n j t p a n i t i o n d u p ) a n db l l i l t a ne 仃e c t i v ea i l o 衄a l yd c t t i o nm o d a lb yu s i n gt h i s a l g o r i t l l m e x p e 咖e n t r e s u l t ss h o 、v c dt l l a t t l l e 卸o m l a l y d e t c “o nm o d e l sb a s e do n d g c 爪，d g c 锄d 凹u p9 0 tm o f ea c c u r a c yt l a r lm l d i t i o n a lm o d e l sb a s e do na n n ，c 4 5 e t c t h e ya l s og o tl l i 曲p e 墒r r i l 趾c e 证蝴s ep o s 试v e sa n d 脚s en e g a t i v e s b e s i d e sm e o r e t i c a ls t u d yo na n o 珊a l yd e t e c d o nm o d e l ，t h ep a p e r 咖d i e df o l l rk i i l d s o ft y p i c a la n a c k s ，砌y z e dt h e i rf e a t u r e s b 髂e do nm es t u d yo fa t t a c k s ，t 1 1 ep a p e r s t l l d i e da 1 1 di m p l e m e m e ds e v e r a lo r i g m a ld a 妇g a m e r i i l gm e 血o ds t h e s eg a m e r e dd a t a i n c l u d en e m o r kp a c k a g e ，0 sa u d i tl o g sa n dn e t f l o wd a 饥t bp r o c e s st 1 1 eo r i g i n a ld a t a ， 血ep a p e rs t u d i e dt h ef e a t u r es e to fk d d 9 9i 咖s i o nd e t 嘣i o nd a t as e t ，a n da d o p t e da s u b s e to f i tt oa n a l y s i st 1 i eo r i g i i l 址d a t a k e yw o r d s ：1 1 1 n m s o nd e t e c d o n ，a n o m l a i yd e t c c t i o n ，d a t ag m v i t a 廿o i l ，d a t a c 1 a s s j f j c a t j o n 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立 进行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含 任何其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出 重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律责任由本人承担。 论文作者签名 日期：型二芦知 关于学位论文使用授权的声明 本人完全了解济南大学有关保留、使用学位论文的规定，同意学校 保留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查阅和借鉴；本人授权济南大学可以将学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和 汇编本学位论文。 ( 保密论文在解密后应遵守此规定) ：弘产日期巡t 确 济南大学硕士学位论文 第一章绪言 1 1 入侵检测概述 近年来，网络入侵事件在全球范围内的频繁发生，给各方面机构带来巨大 损失，使得越来越多的国内外学者专家致力于入侵检测技术的研究。在计算机和由 计算机为节点组成的计算机网络中，连接网络通信协议的能力是有限的f 8 】，而计算 机系统和应用软件也总是包含无法预知的弱点和漏洞，另外，软件组件与网络协议 之间的复杂而无法预测的相互作用也成为安全的隐患，如此种种因素造成计算机和 计算机网络不可避免地遭受各种入侵和攻击。使用传统的安全镶略或机制防范这种 攻击是非常困难的，因此入侵检测已经变成计算机安全中不可缺少的组成部分。 人们对计算机和网络攻击防范的研究可以追溯到上世纪7 0 年代，1 9 8 0 年， a n d e r s o n 首先提出了入侵检测的概念【l l ，他将入侵尝试或威胁定义为：潜在的、有 预谋的、未经授权的访问信息、操作信息，致使系统不可靠或无法使用的企图。他 提出审计追踪可应用于监视入侵威胁。这一设想的重要性当时并未被理解，但他的 这一份报告被认为是入侵检测的开创性工作。 d e 彻【i l l g 和n e u m 锄在1 9 8 4 年到1 9 8 6 年间研究开发了一个实时入侵检测系统 模型嘲，并把这个系统命名为i d e s ( 入侵检测专家系统) ，它是种通过使用统计 方法发现用户异常操作行为并判断检测攻击的基于主机的入侵检测系统，将异常定 义为“稀少和不寻常”( 指一些统计特征量不在正常范围内) ，他们的这个假设是许 多8 0 年代入侵检测研究和系统原型的基础。1 9 8 7 年d e l l l l i n g 提出关于这个问题的 论文被认为是另一篇入侵检测的开创之作四。1 9 8 8 年l u n t 等人进一步改进了 d e n n i n g 提出的入侵检测模型，他提出了与系统平台无关的实时检测思想。 进入9 0 年代后，入侵检测技术研究逐渐变热，新的方法和理论越来越多地引 入到入侵检测的研究特别是大量的人工智能和软计算的理论技术应用到入侵检测 中。1 9 9 4 年，j e r e n l yf m k 在他的论文中对入侵检测中的人工智能方法的应用做了 一个综述性质的回顾【5 1 ，1 9 9 4 年m u k h e 巧e e 等对先前i d s 的研究做了较为完整的回 顾和分析【4 】，对各种m s 的系统原型进行了分析和评述。1 9 9 5 年以后出现了很多不 i 基于效据引力的分类方法及罔络异常检涮模型的研究 同的新的i d s 研究方法特别是智能i d s ，包括神经网络、遗传算法、模糊识别、免 疫系统、数据挖掘等，这些方法目前都处在理论研究阶段。 1 2 入侵检测系统 入侵检测系统( i n n u s i o nd e t e c t i o ns y s t e m s ，i d s ) 指的是对网络中的若干关键节 点收集信息，然后按照预定义的分析策略和安全知识对其进行分析比较，从中发现 网络或系统中是否有违反安全策略的行为和被攻击的迹象，并进行适当的响应的安 全防护系统f 6 】。 根据通用入侵检测框架( c o 咖0 ni n 廿郴i o nd c t e c t i o n 胁n e w o r k ，c i d f ) 模型川， 入侵检测系统通常有四个组件：事件产生器( e v e n tg e n c m t o r s ) ，即信息获取子系 统，用于收集来自于网络和主机的事件信息，为检测分析提供原始数据：事件分 析器( e v e n t a n a l y z e r s ) ，即分析机子系统，是入侵检测系统的核心部分，用于对获取 的事件信息进行分析，从而判断出是否有入侵行为发生并检测出具体的攻击手段： 响应单元( r e s p o n s eu 1 1 i t s ) ，即响应控制子系统，用以向系统管理员报告分析结果 并采取适当的相应策略以响应入侵行为；事件数据库( e v e n td a 吣a s e s ) ，即数据库 子系统，用来存储系统运行的中间数据和进行规则匹配的安全知识库。 图1 1 i d s 结构 1 3 入侵检测技术分类 1 3 1 基于主机的和基于网络的入侵检测技术 对入侵检测技术的分类，从不同的角度方面人们有不同的分类方法，首先，因 为入侵检测目的是为从大量的审计数据中找出异常的数据从而发现入侵行为，所以 人们自然从审计数据来源的不同而对入侵检测技术的划分，基于这个角度，入侵检 济南大学项士学位论文 测技术可以分为基于主机的和基于网络的两大类【4 】，当然后来还出现了把二者结合 起来的混和式入侵检测系统。 1 3 1 1 基于主机的入侵检测 基于主机的入侵检测技术研究的审计数据是主机的系统日志，服务，事件和状 态变化等主机审计数据。应该说人们最早研究跟踪入侵行为是从主机开始的，早期 的黑客入侵也停留在针对单一主机并使用相对单一的手段这一较低水平上。 1 3 1 2 基于网络的入侵检测 与基于主机的入侵检测不同，基于网络的入侵检测技术研究的审计数据是实时 的网络流量数据，这些信息的采集往往是在网络的关键节点上例如路由器和网关。 显然基于网络的检测首先一个特点就是审计数据量大，而且是原始数据。由于数据 的实时性，基于网络的入侵检测能更早地检测到入侵行为，能够降低攻击造成的损 失。 1 3 2 误用和异常入侵检测技术 按照检测模型，即对数据分析的手段方法上看，入侵检测分为误用检测和异常 检测。前者使用著名的攻击或系统的弱点来定义入侵的模型【8 】：后者以确定是否与 建立的正常使用模型有偏离来定义入侵。 1 3 2 1 误用入侵检测技术 误用即不正确韵使用，然而基于误用的检测与误用的字面含义有一定的差距： 它是指收集各种所知的入侵行为的特征建立特征库，在检测时只要发现某行为与特 征库中的某一特征相符则认为该行为是入侵行为。 在误用检测系统中，入侵检测是由基于入侵过程模型的知识来确定的。它的优 点和缺点也是很明显的，由于它是对审计数据与已知攻击的模式进行匹配来发现攻 击，因而其检测精度和效率很高，这种检测方法只能检测己知攻击及其模型的变型， 不能检测系统未知的新的攻击行为。误用检测的主要方法有模型推理和专家系统例 两种。 1 3 2 1 异常入侵检测技术 h 孙村n 1 9 8 0 ) 给出了异常的本质性的定义：异常是在数据集中与众不同的数 基于赦据引力的分类方法及网络异常检铡模型的研究 据，使人怀疑这些数据并非随机偏差，而是产生于完全不同的机制；聚类算法对异 常的定义：异常是聚类嵌于其中的背景噪声。在异常探测算法中也对异常有定义： 异常是既不属于聚类也不属于背景噪声的点。他们的行为与正常的行为有很大不 同。实际上，异常探测是数据挖掘中一个重要方面，用来发现“小的模式”( 相对于 聚类) ，即数据集中间显著不同于其它数据的对象f 。从异常和异常探测的定义我 们可以看出入侵检测的异常检测模型实际上是异常探测技术的一种应用。因而很多 异常探测的方法都用以进行异常检测。 异常检测的思想是首先建立用户正常的行为轮廓，并且假定所有入侵行为都是 与正常行为不同的。在每一次用户行为产生后，都将其测量值与其正常的行为轮廓 进行比较，如果严重偏离正常值的范围( 异常行为) ，则认为产生了攻击。对于异常 阈值与特征的选择是异常检测技术的关键【l i l 。异常检测主要有统计分析【7 1 、数据挖 掘【7 1 司和神经网络等。 1 4 论文特色与创新 本文以建立高效异常入侵检测模型为目标，围绕着异常检测理论和实际检测技 术两大主题开展研究。 1 4 1 异常检测理论研究 在异常检测理论上，本文最大的特色和创新在于提出两种新的异常检测算法理 论。 基于数据引力的分类( d g c ) 算法理论的思想源自于物理学中牛顿著名的万有 引力定律。d g c 理论将万有引力和万有引力定律引入到数据分类问题中，提出了数 据引力的概念，并建立数据空间中的“万有引力定律”数据引力定律，通过对 数据引力大小的比较进行数据分类。这种数据分类理论的最大的特点在于它用一种 全局联系的观点处理数据分类问题。d g c 理论认为在数据空间中任何两个数据点之 间都存在数据引力，而传统的数据挖掘方法( 如k 均值等) 只是从局部研究数据点 之间的关系。 高维度数据单元划分算法( h d u p ) 是一种几何分类算法，该方法通过对数据 空间进行超矩形划分，将数据归入到不同性质的单元中，再根据单元性质进行分类。 4 济南大学硕士学位论文 1 4 2 实际检测技术研究 在异常模型建立的理论工作之外，本文研究了扫描攻击、缓冲区溢出攻击、s q l 注入攻击以及拒绝服务攻击等几类典型的攻击，分析了它们的特征，在此基础上， 研究并实现了几种原始数据的采集方式。这几种原始数据的采集方式涵盖了主机网 络数据包的采集、0 s 审计日志和网络流量统计特征的采集等各方面。在原始数据 的预处理方面，本文以k d d 9 9 入侵检测数据集的特征集为框架，采用该特征集的 一个有效子集对原始数据特征提取分析。 1 5 论文结构与内容 作为核心理论内容，本文在第二章中介绍了基于数据引力的分类算法d g c 及 其改进算法w d g c 的基本原理及其算法。 第三章前半部分研究了几种典型攻击，包括扫描攻击、缓冲区溢出攻击、s q l 注入攻击和拒绝服务攻击，分析了它们特征。后半部分详细介绍了基于主机网络数 据包捕获技术，o s 审计日志以及n 咖o w 网络流量数据的原始数据采集方法。 第四章在详细介绍特征提取方法后，把d g c ，、) g c 用于异常检测建立了基于 d g c 愚，d g c 的异常检测模型，4 3 部分阐述了高维度数据单元划分算法h d u p 的 基本理论和基于该理论的异常检测模型。 第五章在分析本文实验结果的基础上对各种异常检测模型进行了对比，得出了 一系列结论。 第六章对全文进行了总结，并对更进一步的研究工作作了初步的设想描述。 基于数据引力的分类方法及网络异常检测模型的研究 第二章基于数据引力的分类算法d g c 及其改进算法w d g c 2 1 引论 2 1 1 数据分类技术 数据分类是一项被广泛应用于许多领域的重要数据挖掘技术。数据分类可以有 导师监督学习，也可以无导师监督学习，分类的目标是将要分类的数据分别归入到 不同的特定数据类中。对于有导师监督的数据分类，分类的目标是根据一组给定的 训练数据建立一个分类模型，一旦模型建立之后就可以使用该模型进行数据分类。 数据分类的方法有很多种决策树毗1 4 1 、神经网络和支持向量机1 7 1 ( s v m ) 是几种比较常见的经典的分类方法，在这几种方法中，决策树技术实现比较简单， 而且比较符合人类的思维逻辑，决策树技术在实际分类应用中分类效率高，分类精 度相比神经网络却比较低；神经网络是一种模拟人类神经系统工作原理的技术，神 经网络应用于分类问题中往往可以取得比较理想的分类精度，但是神经网络的训练 却要花费大量的时间；支持向量机是一种新的基于统计学习理论的机器学习技术。 支持向量机能在分类效率和精度上都取得比较好的效果，因此该技术越来越受到关 注。但是支持向量机建立在假设样本服从某种分布的基础之上，这就限制了它的应 用范围。另外近年来，粗糙集理论例也被应用于分类问题中。人们用粗糙集技术来 进行特征选择f 3 或者与其他分类技术结合形成混和分类技术m3 2 ，3 3 - 州。 文献【2 6 】提出了一种叫“收缩”的数据处理技术，这项技术受牛顿万有引力定 律思想的启发，利用万有引力的思想来优化数据的内部结构，在文献【2 7 】中，作者 又利用该技术在高维数据分析中研究降维。文献【1 8 】提出了一种叫g 鼬w i 聚类的空 间聚类算法，该算法利用聚类中心引力的计算来达到最佳聚类效果。文献【2 8 】将自 然引力的原理应用于局部优化算法中。 2 1 2 万有引力定律 我们知道，宇宙中任何两个物体之间存在着一种服从万有引力定律的作用力， 这种作用力被称为万有引力。牛顿于1 6 8 7 年发表了一篇重要论文，在这篇论文中， 6 济南大学硕士学位论文 牛顿第一次提出了万有引力定律。他指出，两个物体之间的引力大小与它们的质量 的乘积成正比，而与它们之间距离的平方成反比，用公式表示如下： f = g 竺婴 r 由于力具有方向性，更精确的表示方式是向量表示方式 ，：g 掣 f ，1 。 其中 凡两个物体之间的引力 g ：万有引力常数 m j ：物体l 的质量 m 2 ；物体2 的质量 ，：两个物体之间的距离 rf 的向量表示形式 ，：，的向量表示形式 2 1 3 引力与数据相似性 在数据空间中的数据点( 样本) 相互是否是孤立的呢? 当我们对计算机可处理 的数据进行聚类分析时，数据空间中的两个数据点的欧氏距离越大，这两个数据点 属于同一个聚类的程度就越小。大多数聚类分析的方法都局限于对数据在局域范围 内分析，没有从全局的观点来对待数据之间的关系。例如经典的k 均值方法【1 卅就是 以距离为准，对中心邻域内的数据聚类，这样聚类就很有可能丧失一定的精度。然 而几乎所有的聚类方法都利用了数据之间的一个本质特征：数据的相似性。 为简洁起见，在不引起混淆的情况下本文将欧氏距离简称为距离。 首先我们将数据之间的相似性和现实世界中的物体之间的引力做如下比较： 1 ) 两个物体之间的引力与它们之间距离的平方成反比，而两个数据点的相似 性也与它们在数据空间中的距离成某种反比关系。数据点之间的相似性和它们的距 离的关系正好与物体之间的引力和它们的距离的关系符合。我们来看这么一个例 子：太阳系中，火星无论从体积上还是质量上都与地球比较接近，地球是距离月球 7 基于熬据引力的分类方法及网络异常检测模型的研究 最近的行星，而火星与月球之间的距离则要大得多，所阻地球对月球的引力要比火 星对月球的引力大得多，因此月球受地球引力的作用而成为地球的卫星，火星对其 作用力太小，月球无法成为火星的卫星。 同样道理，如图2 1 所示，假设一与b 是二维数据空间中的两类数据，它们都 有八个数据点，尸是一个测试数据点，j p 属于哪个数据类未知，但是有一个重要的 因素就是p 与一类数据的几何中心的距离，要大于其与占的中心的距离力。显然， p 属于爿的程度就要比它属于口的程度弱。 图2 1 数据的相似性与距离的关系 2 ) 物体的质量越大，它对其他物体的引力也就越大。在数据空间中，一个数 据类所包含的数据点越多，则一个归属未知的样本从属于该类的程度也就越强。图 2 2 中，一与b 也是两个数据类，爿有1 6 个数据点，占只有7 个，样本p 的从属未 知尸与爿、b 的距离均为r 。由于一包含的数据元素多于b ，我们说一的“质量” 大于b ，由此我们可以得出结论：尸属于一的强度大于b 。 图2 2 数据的相似性与数据密度的关系 2 2d g c 相关概念与引理 基于2 1 3 部分的分析，我们把万有引力定引入到数据分类问题中，并建立数 据空间中的“万有引力定律”。 定义l ( 数据质点) ：数据质点是数据空间中具有“数据质量”的数据单元。数 据质点_ 由数据空间中一组有特定关系的数据元素( 点) 组成，一般来说，这种关系 是指数据元素在数据空间中的几何相邻关系，这种关系在本文的2 3 2 部分中会详 细阐述。数据质点具有两个最基本的属性：数据质量和数据质心。 定义2 ( 数据质量) ：数据质量是指数据质点中所包含的数据元素个数。 定义3 ( 数据质心) ：设乩勘- ，扣j ，z 脚) 是 n 维数据空间s 中的一组数据元素，p 是由工，组成的一个数据质点，则 p 的数据质心渤= 就是x 如，在数据空间中的几何中心， 用公式表示如下： 当b x o ，2 ，f - j ，2 ，巩，；，z 肌( 3 ) 由于数据质点具有数据质量和数据质心两个基本属性，所以数据质点可以用二 元组 来表示，加入类别属性y 后可以表示为 ，其中m 是数据质点 的数据质量，x 是其数据质心。 定义4 ( 原子数据质点) ：原子数据质点是指仅包含一个数据元素的数据质点。 原子数据质点的数据质量是1 。 定义5 ( 数据引力) ：数据引力是数据之间的相似性。不同于物理世界中的引 力，数据引力是一种标量，没有方向性。不同类的数据作用于一个测试数据元素的 数据引力相互之间可以进行比较，另一方面，同一类数据作用于一个测试数据元素 上的数据引力则符合叠加原理。 引理1 ( 叠加原理) ：设p ，m ，砌是数据空间中属于同一个数据类的研个 数据质点，它们作用于另一个数据元素的数据引力分别是乃，见，r ，则它们对 该数据元素的数据引力合力为： f 。至丘( 4 ) ，= l 基于数据引力的分类方法及网络异常检测模型的研究 定义6 ( 数据引力场) ：数据质点通过数据引力相互作用，形成一个充满整个 数据空间的场，称之为数据引力场。 由于数据引力可以属于不同数据类，所以在讨论数据引力场的时候，指的是同 一类数据质点产生的引力场。 场强是数据引力场的一个关键因素，个指定点的场强等于所有同一类数据质 点在该点产生的场强的和，而单个数据质点在该点产生的场强等于它对一个位于该 点的原子数据质点的数据引力。 类似于物理场中的等势面，数据引力场中所有场强相等的点形成一个超曲面， 这种超曲面称为数据引力场的等势面。 数据引力定律 数据空间中两个数据质点之间的数据引力强度与它们的数据质量的乘积成正 比，而与它们之间的欧氏距离的平方成反比。 用公式表示如下： f ：旦磐 p 其中 凡两个数据质点之间的数据引力 卅：数据质点1 的数据质量 m 2 ：数据质点2 的数据质量 ，：两个数据质点在数据空间中的欧氏距离 若问题有，1 个特征，设数据质点l 的数据质心为 ，数据质点 2 的数据质心为 ，则 2 3d g c 分类原理 基于数据引力和数据引力场理论，本文提出了一种新的数据分类方法。该方法 的主要思想如下： 1 0 济南大学硕士学位论文 1 ) 首先根据训练数据集按照一定规则建立一个训练数据质点集。 2 ) 所有测试集中的数据都是原子数据质点并且所有的训练数据质点对任一 测试原子数据质点都有数据引力。 3 ) 训练数据质点与测试数据质点之间的引力计算遵循数据引力定律。 4 ) 一旦训练数据质点集建立以后，问题数据空间中的数据场也就形成，数据 空间中的任一点的场强都可以计算。 5 ) 一个测试数据对某类数据的从属程度由该类数据在该测试数据所在位置的 场强大小决定，而场强大小等于该类数据质点对该测试数据质点的引力总 和。 2 3 1 分类原理 引理2 ：设c ，c 2 是训练数据集中的两个数据类。对于一个归属未知的数据p ， c ，作用于p 的引力为f j ，旬作用于p 的引力为乃。如果丹 乃，则p 属于c ，的程 度要大于o 。 图2 3 描述了分类原理。 图2 3 基于数据引力的分类。引力的强度大小决定一个测试数据的归属。 黑点表示属于c j 的数据质点，圆圈表示属于c 2 的数据质点 设z = q y j ， ， ) 是n 维数据空间中的训练数据集，j ， c q ，讲，o 代表数据类f ，i 是数据类的个数，是训练数据的个数。根据原始训 练数据集创建了一个新的训练数据质点集r = ， ， ) ，f 是数据质点的个数，凭数据质点f 的质心，川，是数据质点f 基于数据引力的分类方法及网络异常检测模型的研冤 的数据质量。 训练数据质点集建立后，数据空间中任一点的数据场强度便可以计算，因此， 当给定一个测试数据时，它的归属就可以根据场强来决定。 设c “，c i 是训练数据集中的所有数据类，它们分别有f 如，厶个样本， 由训练数据集建立的训练数据质点集有，j + 如+ + “，个数据质点，其中 为第， 类数据的数据质点个数，一个给定的测试数据可以被当作原子数据质点p ，它的数 据质心就是它的位置x 。则第f 类数据质点作用于p 的数据引力为 乃：釜塑彳 j = l l j 打一j i 其中m 是第f 个数据类中第，个数据质点的数据质量，却是它的数据质心，如 果厅= m 倒 日凡，以) ，则根据引理2 ，该测试数据就属于数据类f 7 。 2 3 2 数据质点的创建 创建数据质点的最简单方法是将数据空间中每个单独的数据作为一个数据质 点。用这种方法，训i 练数据集中的每个样本都形成一个数据质点，所以，原始训练 集中有多少个样本，就形成多少个训练数据质点。显然，这种方法非常简单而且易 于实现，另外，用这种方法建立的训练数据质点集来计算数据引力场，可以取得比 较高的精度。但是这种方法的缺点也是显而易见的：随着训练数据集规模的增大， 数据质点集的规模也就随之增大，分类的计算量也就要增大，这就不可避免地影响 分类效率。 另一种创建数据质点的方法是最大距离原理( m d p ) 。 算法1 ( m d p 算法) ； 1 ) 给定一个距离阈值占和一个训练样本勋，如果在训练集中存在其他训练样本 x j ，如，与勘属于同一个数据类，并且与x d 存在如下关系：k ，嘎d l s ，f - j ，z ， m 。则x bx 乩可被归入到一个单一的数据质点 中，其中x o 为数 据质点的质心，珊。= m + 为它的数据质量。 2 ) 用新创建的数据质点 重复步骤1 ) ，将符合条件的训练样本继续归 入该数据质点，直到训练数据集中无剩下的符合条件的样本。 1 2 济南大学硕士学位论文 3 ) 将训练集中其他剩下的样本重复上述步骤，直至训练样本全部归入训练数据 质点集中。 m d p 方法的优点在于能将训练集中对数据引力场影响相近的元素归并到一起， 显然这样做大大减少了分类计算量，提高了分类效率。但这种方法影响了数据引力 场的计算精度，特别是在数据质点的质心附近，因为在数据质点质心的邻域内，由 于原始数据比较密集，该区域的数据引力场梯度变化比较快，场比较复杂，而数据 质点创建后，根据数据质点计算的数据引力场则丢失了原引力场的一些信息，因此 这就必然会影响分类精度。 2 4d g c 的特征选择 2 4 1 特征选择与d g c 特征选择在数据挖掘中非常重要，因为对于一个给定的任务来说，数据的质量 是一个直接影响挖掘算法是否成功的因素。文献 3 5 ，3 6 】对特征选择的机器学习技术 做了比较好的阐述，本文在异常检测模型建立实验中所使用的k d dc u p 9 9 入侵检 测数据集中，每条连接记录有4 1 个特征，这就意味着相应的数据空间是4 1 维空间。 如此多的特征无疑要很大程度上影响检测算法的效率，而且有的特征对检测的影响 非常小，这样就给研究者提出了一个新的问题，即怎样在不明显影响检测精度的前 提下，尽量剔除“无用”的特征。实际上，实验证明在特定的算法中选择有用的特 征对检测精度基本上没有影响阻矧。 实验证明，d g c 算法对特征的选择相当敏感。选择有效的特征不仅能大大提高 d g c 算法分类效率，甚至能提高其分类精度j 本文针对d g c 算法的特点提出了一 种基于数据投影聚类的特征选择算法。 2 4 2 基于数据投影聚类的特征选择算法 c l i q u e 算法【2 3 】是一种有效的高维度数据空间聚类算法，本文根据c l i q i = j e 算 法中的单调性定理提出了一种基于数据投影聚类的特征选择算法。d g c 异常检测模 型建立实验证明，该算法能高效地选择有用特征，提高分类效率。 c l i q u e 算法的创始人r a g r a w a l 在他的高维度数据的自动子空间聚类论文中 给出了单调性定理及其证明。 引理2 ( 单调性定理) ：若在女维数据空间的点集s 是一个聚类，则s 也是在这 个数据空间的任意一个( 七_ 1 ) 维投影中的一个聚类的一部分。 1 3 基于数据引力的分类方法强网络异常检测模墅的研究 根据这个定理，可以得出分类问题中一个评价一个特征( 维度) 的冗余性的原 则：如果两类数据在某个特征( 维) 上的投影都有聚类，则如果这两类数据的投 影聚类重叠程度越高，它们在这个特征上能区分的程度也就越低，这就意味着这个 特征对这两类数据的分类越“无用”，反之，如果这两类数据的投影聚类重叠程度 越低，这个特征对它们分类就越“有用”。 如图2 4 所示，数据集中有两类数据，它们在x 特征上的投影聚类重叠程度相 当高，所以，x 特征就是冗余特征，可以不被选择。 z o oo oo o-oo 。 d秽 图2 4 数据投影聚类和聚类重叠 由此，基于上述原则的特征选择算法如下： 设训练数据集中有c ，和句两个数据类，有厶个样本，有如个样本，饵口是两个 阈值，d 口 ，口 口 j 。 算法2 ： l ：f o r f = j t 0n 2 ：计算c ，中可聚类的样本个数，其结果为岛。再计算c 2 中可聚类的样本个 数，结果为b 3 ：证k i 口 6 ：该特征为冗余特征 7 ：e n d i f 8 ：e n d f o r 济南大学硕士学位论文 2 5 w d g c 2 5 1 特征的加权 d g c 算法效果很大程度上依赖于对问题特征的选择，在d g c 中我们采用了基 于数据投影聚类的方法来选择特征，和其他特征选择算法一样，这种特征选择方法 只是简单的将问题的某个特征选择或者不选择。 实际上我们在实际分类问题中有这样的感性认识，对于特定的分类问题，不同 的特征对分类模型的重要程度是不一样的。例如： 对于t c ps y nf l o o d 攻击，攻击者要针对同一服务端口在短时间发起大量的 “半连接”，所以必然表现出来一系列显著的统计特征，比如在主机或者网络上截 获的网络数据包中，短时间( 例如2 秒钟) 内同一主机同一端口收到大量的没有确 认应答的t c ps y n 请求包。 对于一个漏洞溢出攻击来说，由于攻击者的目标之一就是要取得r o o t 或者管 理员权限，并获取目标主机的一个s h e l l ，所以对于该类攻击的检测来说，主机审计 日志中如果有远程用户未经正式登录即取得主机s h e l l 的记录，则表明该主机很大 可能遭受了溢出攻击。 既然不同的特征在不同的具体分类问题上具有不同的重要程度，所以我们如果 进行有效的特征选择就能在很大程度上提高分类效率甚至分类精度。在以往的大多 数特征选择方法中，对特征的最终选择结果都是选择或者不选择，这样的选择方式 显然不能准确反映具体特征的重要程度。 本文在特征选择中，将具体特征加权表示其对目标分类问题的重要程度。基于 这种原则，如果某分类问题有a 、b 、c 三个原始特征，其他分类算法可能选择其中 一个或者两个来做分类，在这里我们可以把这三个特征按某种算法加权，如a 为0 3 ， b 为o 1 ，c 为0 ( 不选择) ，这样就可以相对精确地表示出各个特征的重要程度。 2 5 2 交叉验证