（计算机软件与理论专业论文）基于聚类分析的入侵检测方法研究.pdf

摘要 摘要 入侵检测在计算机安全系统中发挥着越来越重要的作用 目前入侵检测系统 使用的规则或模式还是主要依赖于领域专家分析提取 自适应能力不强 可扩展 性差 并且由于入侵检测系统审计数据量很大 使用人工分析的代价非常昂贵 将数据挖掘技术应用于入侵检测的数据分析 可以有效的减少人工分析的工作量 和经验成分 并使入侵检测系统具有自适应和自我学习的能力 本文主要探讨数据挖掘的聚类分析及相关技术在入侵检测中的应用 传统的 异常检测方法需要从大量纯净的正常数据集中获得检测模型 而在现实网络环境 中 很难保证在数据采集阶段没有入侵的发生 也很难对采集的数据进行标识 这就使其应用受到很大的限制 本文尝试在未标记的 正常数据中混杂了少量入 侵数据的网络审计数据源上 采用聚类分析及相关技术 尽可能准确的将训练数 据集中少量的入侵数据从大量正常数据中分离开来 并自动建立一个反映系统行 为模式的检测模型 并给出使用该模型进行入侵检测的方法 该检测模型所用训 练数据集易于从实际运行环境中获得 因而有更大的实用价值 本文的研究工作主要包括以下内容 1 对构建检测模型的数据准各方法 即网络审计数据的收集与预处理方 法 进行了研究 介绍了使用网络嗅探器收集网络上传输的数据的原理与方法 以及从嗅探器原始输出中组合成t c p 连接纪录并构造记录特征属性的方法 2 提出了一种基于聚类分析和孤立点挖掘的无指导异常检测模型的构造 方法 该方法首先使用一种快速 简洁的 可以粗略检测孤立点的聚类分析算法 划分训练数据集 并标记各个聚类 正常 或为 可疑 异常 之 后提出了新颖的孤立点定义及相应的基于聚类剪枝的快速孤立点挖掘算法 从标 记为 可疑 的类中进 步标记出入侵记录和正常记录 并以记录标记为指导 将 可疑类 的记录重新聚类 从而优化聚类结果 最后 提取各聚类的类特征 形成检测模型 3 给出了利用上述检测模型检测入侵的方法 并使用k d d 9 9 数据集对 检测模型进行了性能测试 并对算法改进措施的效果进行了对比与分析 实验结 果表明 本文所采取的改进措施提高了检测模型的性能 关键词入侵检测 数据挖掘 聚类分析 孤立点挖掘 j j 奎三些銮兰j 兰罂圭 兰鲨兰 a b s t r a c t i n t r u s i o nd e t e c t i o np l a y sam o r ea n dm o r ei m p o r t a n tr o l ei nc o m p u t e ra n dn e t w o r k s y s t e ms e c u r i t y i nc o n v e n t i o n a lw a y e x p e r t sa n a l y z ed a t ac o l l e c t e db yi n t r u s i o n d e t e c t i o ns y s t e ma n de x t r a c td e t e c t i o nr u l e so rm o d e l s m a n u a la n a i y s i si sq u i t e e x p e n s i v eb e c a u s eo f e n o r m o u sa m o t m to f a u d i td a t a a p p l y i n gd a t am i n i n gt e c h n i q u e t oi n t r u s i o nd e t e c t i o nc a nr e d u c ew o r k l o a do fm a n i l a la n a l y s i sa n dd e p e n d e n c eo n e x p e r i e n c e f u r t h m o r e d a t am i n i n gt e c h n i q u ec a nm a k et h e i n t r u s i o nd e t e c t i o n s y s t e ma d a p t t on e wt y p e si n t r u s i o n s t 1 1 i sp a p e rm a k e sas t u d yo fa p p l y i n gc l u s t e r i n ga n dr e l a t e dd a t am i n i n gt e c h n i q u e t oi n t r u s i o nd a t e c t i o n c o n v e n t i o n a la n o m a l y b a s e dd e t e c t i o na p p r o a c h e ss h o u l du s e d a t ak n o w nt ob ep u r e dn o r m a la sar e f e r e n c em o d e lf o rd e t e c t i n ga n o m a l o u sd a t a h o w e v e r w ed on o th a v ep u r e dn o r l n a ld a t ar e a d i l ya v a i l a n ei n r e a ln c t w o r k e n v i r o n m e n t b e c a u s ei tc o u l dh a r d l ye n s t l r en oa t t a c k st a k i n gp l a c ei nt h ec o u r s eo f d a t ac o l l e c t i o n a n di ti sd u f f i c u l ta n dt i r e s o m et ol a b e ld a t am a n n a l l y s ot h e p r a c t i c a b i l i t yo ft h e s ea p p r o a c h e si s l i m i t e d i nt h i sp a p e r w et r yt oa u t o m a t i c a l l y l e a r nad e t e c t i o nm o d e lu s i n gc l u s t e r i n ga n do u t l i e r sm i n i n ga l g o r i t h m sf r o mn e t w o r k a u d i td a t a a n dt h ed a t as e tw eu s e da st r a i n i n gd a t ai sn o tp u r e dn o r m a l c o n t a i n i n g u n l a b e l e dl a r g en u m b e ro fn o l t n a le l e m e n t sa n dr e l a t i v e l yf e wa n o m a l i o u s t h e t r a i n i n gd a t ac a nb ea b t a i n e di nr e a ln e t w o r ke n v i r o n m e n t s oo u rm o t h e di sm o r e p r a c t i c a l t h em a i nw o r ko f t h i sp a p e ri sl i s t e da sf o l l o w i n g s 1 as t u d yo f n e t w o r ka u d i td a t ac o l i c c t i o nm e t h o da n dd a t ap r e p r o c e s s i n gm e t h o d i sm a d e t h ep r i n c i d l ea n dm e t h o df o rc o l l e c t i n gn e r o r kd a t as t r e a mb ys n i f f e ri s i n t r o d u c e d t h em e t h o df o rp r o c e s s i n gr a ws n i f f e ro u t p u ti n t oc o n n e c t i o nr e c o r d sw i t h b a s ef e a t u r e sa n de x t e n d e df e a t u r e si sp r e s e n t e d 2 am e t h o df o rl e a r n i n gau n s u p e r v i s e da n o m a l yd e t e c t i o nm o d e lu s i n gc l u s t e r i n g a n do u t l i e r sd e t e c t i o na l g o r i t h m si sr a i s e d i nt h ef a s ts t e p af a s tc l u s t e r i n ga l g o r i t h m w h i c hh a ss i m p l eo u t l i e r sd e t e c t i o nf u n c t i o ni su s e dt op a r tu n l a b e l e dt r a i n i n gd a t a i n t oc l u s t e r s a n daa l g o r i t h mf o rl a b e l i n g 出o s ee l u s t e r sa s n o r m a i d o u b t a b l e o r a n o m a l o u s i sp r o p o s e d a f t e rt h a t n o v e lo u t l i e r sd e f t n i t i o n sa n dc o r r e s p o n d i n g o u t l i e r sd e t e c t i o na l g o r i t h m sa l ep r o p o s e dt od e t e c t a n o m a l o u s r e c o r d sf r o m c l u s t e r sl a b e l e da s d o u b t a b l e a n das u p e r v i s e dc l u s t e r i n ga l g o r i t h mi sp r o p o s e dt o r e d oc l u s t e r i n gf o rr e c o r d si nt h o s ec l u s t e r s a tl a s t f e a t u r e sa r ee x t r a c t e df r o ma l l c l u s t e r st of o r mt h ed e t e c t i o nm o d e l f 3 1am e t h o df o rd e t e c t i n ga n o m a l i e su s i n gt h el e a r n e dd e t e c t i o nm o d e l i sr a i s e d a t e s to ft h el e a r n e dd e t e c t i o nm o d e lw i t hk d d 9 9d a t as e ti sd o n e c o n t r a s t i v et e s t sa r e d o n ef o rt h ei m p r o v e m e n t si no u rm e t h o d a c c o r d i n gt ot h et e s tr e s u l t s t h e i m p r o v e m e n t si no u rm e m o d r e s u l ti nab e t t e rp e r f o r m a n c e k e yw o r d si n t r u s i o nd e t e c t i o n d a t am i n i n g c l u s t e r i n g o u t l i e r sd e t e c t i o n 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果 尽我所知 除了文中特别加以标注和致谢的地方外 论文中不包含其他 人已经发表或撰写过的研究成果 也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料 与我一同工作的同志对本研究所做的任何贡献均 己在论文中作了明确的说明并表示了谢意 签名 疸趟日期 塑壁垒 量塑 关于论文使用授权的说明 本人完全了解北京工业大学有关保留 使用学位论文的规定 即 学校有权 保留送交论文的复印件 允许论文被查阅和借阅 学校可以公布论文的全部或部 分内容 可以采用影印 缩印或其他复制手段保存论文 保密的论文在解密后应遵守此规定 签名 蕉签选导师签名 叠鸯品 日期 迹垂 日西q 第1 章绪论 1 1 课题背景 第一章绪论 随着互联网的飞速普及和网络应用的深入 人们已经习惯于使用网络提供的 服务 参与各种网络活动 需要在网络上进行存储和处理的敏感信息日益增多 信息安全问题成为计算机网络系统中的首要问题 由于网络系统越来越复杂 系统需要面临的安全威胁越来越多 新的攻击手 段也层出不穷 仅仅依靠初步的防御技术是远远不够的 需要采取有效的手段对 整个系统进行主动监控 信息安全的概念和实践不断深化和扩展 目前已经存在 的网络信息安全技术主要有加密 身份认证 访问控制 防火墙及入侵检测 i n t r u s i o nd e t e c t i o n 技术等 在实践经验和一些理论研究的基础上 人们提出 了一些安全模型 其中比较有代表性的是i i s 公司提出的p p d p 模型 i 它包括 对信息的策略 p o l i c y 防护 p r o t e c t i o n 检测 d e t e c t i o n 响应 r e s p o n s e 等四个相互促进 循环上升的要素 加密 身份认证 访问控制 防火墙等几个 安全技术主要对应于p p d r 模型中的 防护 入侵检测技术则对应于 检测 和 响应 作为一种积极主动的安全技术 入侵检测提供了对内部 外部攻击 和误操作的实时保护 在网络系统受到危害之前拦截和响应入侵 成为信息安全 保障中的一个重要环节 很好的弥补了访问控制 身份认证 防火墙等传统保护 机制所不能解决的问题 因此 入侵检测系统及技术的研究是一个重要的课题 目前大多入侵检测系统采用简单模式匹配技术来发现入侵 其中用于识别判 断入侵行为的规则或模式 基本上是由领域专家人工总结提供的 这类入侵检测 系统存在的一个最大不足就是 它需要由人类专家不断总结提供有关的入侵检测 知识 自适应性差 只能发现模式规定的 已知的入侵行为 而且 随着操作系 统的日益复杂化和网络数据流量的急剧膨胀 导致了安全审计数据以惊人的速度 递增 单靠经验和人工分析无法全面的利用它们 检测异常行为成为系统管理人 员的巨大负担 数据挖掘作为一种致力于从大数据集中发现知识的智能化手段 可以从海量安全审计数据中自动提取出尽可能多的隐藏信息 尽量减少了手工和 北京工业大学工学硕士学位论文 经验的成分 使入侵检测系统具有自适应能力和自我学习的能力 提高检测效能 2 1 近年来 尝试将数据挖掘技术应用于入侵检测成为信息安全中一个研究热点 1 2 入侵检测和入侵检测系统简介 1 2 1 入侵检测的产生与发展 入侵检测 i n t r u s i o nd e t e c t i o n 的概念最早是由a n d e r s o n 在1 9 8 0 年提出来 的口 他将入侵定义为 潜在的 有预谋的 未经授权访问信息和操作信息 致 使系统不可靠或无法使用的企图 入侵行为可划分为外部闯入 内部授权用户的 越权使用和滥用三种类型 他提出了利用审计数据监视入侵行为的思想 1 9 8 7 年 d e n n i n g l 4 提出了一种通用入侵检测模型 并首次提出了异常检测的方法和 原型 在此基础上 d e n n i n g i s 和n e u m a n n 6 研究和发展了一种命名为入侵检测 专家系统 i n t r u s i o nd e t e c t i o ne x p e r ts y s t e m 简称i d e s 的实时模式的通用入 侵检测模型系统 该模型系统被称为里程碑性的入侵检测系统 i d s i d e s 包 括一个异常检测器和一个专家系统 异常检测器使用了统计学技术来描绘正常行 为模式 而专家系统使用了基于规则的特征匹配方法识别已知的入侵 1 9 9 0 h e b e r l e i n l 7 等人开发出了n s m n e t w o r ks e c u r i t ym o n i t o r 该系统第一次直接 将网络流作为审计数据来源 入侵检测系统发展史翻开了新的一页 1 2 2 入侵检测系统的基本结构 图1 给出了一个通用的入侵检测系统 i d s 的粗略的基本结构i8 1 主要包括数 据提取模块 数据分析模块 结果处理模块 图1 1 通用入侵检测系统基本结构图 f i g u r e l 1t h eb a s es t r u c t u r eo f ac o m m o ni n t r u s i o nd e t e c t i o ns y s t e m 2 第1 章绪论 数据提取模块的作用在于为系统收集提供审计数据 输入给数据分析模块 数据提取模块在获得数据之后 需要对数据进行简单的处理 如简单的过滤 数 据格式的标准化等 然后将经过处理的数据交给数据分析模块 数据分析模块的作用在于对数据进行深入的分析 发现攻击并根据分析的结 果产生事件 传递给结果处理模块 数据分析的方式多种多样 可以简单到对某 种行为的计数 如一定时间内某个特定用户登陆失败的次数 也可以是一个复 杂的智能化系统 该模块是一个入侵检测系统的核心 结果处理模块的作用是在数据分析模块发现入侵事件后 及时做出告警与反 应 保护系统免受攻击 1 2 3 入侵检测系统的主要分类 文献 9 对入侵检测的主要类型进行了介绍 基于此文献 总结入侵检测系 统的主要分类如下 1 按照数据来源分类 基于主机 h o s t b a s e d 的入侵检测系统 安装在被保护的主机上 数据源 来自所在主机的系统审计记录或应用程序日志文件 基于网络 n e t w o r k b a s e d 的入侵检测系统 监测和提取一定网段上传输 的数据包作为数据源 保护整个网段的运行 2 按照数据分析方法分类 误用检测 m i s u s ed e t e c t i o n 又称基于特征的检测 s i g n a t u r e b a s e d d e t e c t i o n 它收集非正常操作 攻击行为 的行为模式 建立相关的特征库 当待检测行为与库中特征匹配时 系统就认为这种行为是入侵 误用检测对于预 防大量己知入侵方式的攻击是简单而高效的 但其缺陷在于只能检测己知的入侵 方式 目前大多入侵检测系统都采用这种方法 异常检测 a n o m a l yd e t e c t i o n 假设 攻击者的行为模式本质上是异于正 常使用者的行为模式 它首先根据系统在过去长期正常运行中产生的大量审计 数据建立一个正常行为模型 将待检测的行为和该正常行为模型进行比较 通过 它们相异的程度来判断待检测行为是否是攻击行为 其优点是不需要知道具体的 入侵行为特征 可以发现新的未知行为特征的攻击行为 在入侵日益复杂化 入 北京工业大学工学硕士学位论文 侵行为日益翻新的变化趋势下 这种入侵检测方式具有更好的适应性 这种技术 目前还不成熟 往往有较高的误检率 是目前研究的重点 2 0 0 0 年 w e n k el e e 研究组提出了无指导异常检测的概念i 加h 13 1 在此 本文将异常检测方法细分为 有指导的异常检测和无指导的异常检测 有指导的异常检测 即传统的异常检测技术 通过观察纯净的 不掺杂入侵 行为数据的正常行为数据建立正常行为模型 然后检测那些偏离正常模型的异常 行为 无指导的异常检测 这种技术通过对掺杂了少量入侵行为数据 且没有标记 哪些是正常数据 哪些是入侵数据的数据集的分析 发现其中存在的入侵行为 并建立检测模型 无指导的异常检测与有指导的异常检测相比 它不需要纯净的 正常行为训练数据 训练数据集可以在现实网络环境中获得 3 按系统各模块运行的分布方式分类 集中式入侵检测系统 系统的各个模块 包括数据的收集与分析以及响应模 块 都集中在一台主机上运行 这种方式适用于网络环境比较简单的情况 分布式入侵检测系统 也称为基于代理的入侵检测系统 系统的各个模块可 分布在网络中不同的计算机和设各上 这种方式适用于网络环境复杂 数据量大 的情况 1 3 研究现状 1 3 1 入侵检测技术的发展方向 入侵检测技术是在不断发展的 近年来有如下主要发展方向 1 分布式入侵检测架构 随着网络系统的日益复杂 二十世纪9 0 年代研究重点转到分布式入侵检测 系统 d i d s u 4 构架上 它不再局限于单一的主机或网络架构 而是多组件协同 应用于异构系统和大规模的网络系统 d a r p a 美国国防高级研究项目署 在1 9 9 7 年提出的通用入侵检测框架 c i d f 1 5 就致力于为分布式入侵检测系统设计一套 协同入侵检测组件与协议 2 智能化的入侵检测技术 第1 章绪论 随着数据量的膨胀及入侵行为的复杂化 越来越需要入侵检测系统其有智能 化特征 1 1 9 1 1 25 尝试将各种智能化方法应用于入侵检测成为一个研究的热点 现 阶段常用的智能化检测方法有 基于神经网络的异常检测方法 1 6 基于专家系 统的误用入侵检测方法 基于免疫系统的入侵检测方法 基于数据挖掘的入侵检 测方法 基于状态转移的入侵检测方法等 这些方法用于系统用户行为模式的自 动挖掘 或入侵特征的自动辨识与泛化 但这些工作还远远不足 需要进一步的 工作来提高其自学习与自适应能力 3 实时入侵检测技术 随着大量高速网络的出现 如何实现在应用于高速网络的具有较好实时性的 入侵检测技术已经成为 个现实的问题1 1 7 1 3 2 数据挖掘在入侵检测中的应用 入侵检测系统从本质上可以归结为对安全审计数据的分析与处理的过程 数 据挖掘 d a t am i n i n g 作为数据分析的前沿技术 能够自动从海量的数据中提取 出用户感兴趣的知识 l8 1 将其作为一个智能化手段应用于入侵检测的数据分析 已经成为一个研究热点 基于数据挖掘的入侵检测分析技术与其他分析技术不同 之处在于 该方法以数据为中心 将入侵检测看作安全审计记录数据的分析与处 理过程 即使不知道各种攻击手段的作用机制 也可以从安全审计数据本身所隐 藏的规律中发现用户行为模式或攻击行为特征 从而使入侵检测系统具有更好的 自学习 自适应和自我扩展的能力 在这一领域做出卓越成果的是美国哥伦比亚大学w e n k el e e 研究组 以4 1 他们在将数据挖掘应用于入侵检测方面做了大量的研究和实践工作 本文的研究 内容也借鉴了他们的研究成果 他们提供的大量实验结果表明 将通用的数据挖 掘技术应用于入侵检测是完全可行的 目前 在入侵检测领域应用较多的数据挖掘方法有4 类 2 5 分类分析 关 联分析 序列分析和聚类分析 针对入侵检测 分类算法一般是收集足够多的关 于一个被监控主体的 正常 或 异常 活动的审计数据作为训练数据 使用分 类算法学习分类规则 构造一个分类器 再利用该分类器对其他审计数据进行分 类分析 文献 2 l 中采用了决策树方法建立分类器 w e n k el e e 研究组参与实现 北京工业大学工学硕士学位论文 的m a d a m i d 系统 2 2 中 使用了r i p p e r 算法学习分类规则 关联分析算法用 于确定审计数据的特征属性的相关性 帮助正确选择与入侵检测有关的系统特征 1 9 1 2 1 捌 序列分析有助于我们发现审计数据中频繁出现的时间序列模式 提高 对具有时间序列特征的用户行为模式或入侵行为的识别率 2 1 2 8 研究结果表明 将数据挖掘技术应用于入侵检测是可行的 国际上在这个方 面的研究非常活跃 但总体上还处于理论探讨阶段 离实际应用似乎还有相当的 距离 国内这方面的研究则刚刚起步 中国科学院的国家信息安全重点实验室 东北大学国家软件工程研究中心等走在前列 1 3 3 聚类分析在入侵检测中的应用 聚类分析作为 种无指导的学习方法 是一个获得数据分布情况的有力工 具 聚类分析在入侵检测中的典型应用是建立基于异常的入侵检测的正常行为模 型 如文献 l i 1 3 2 9 3 1 5 8 都探索将合适的聚类方法结合入侵检测问题进行 有针对性的研究 此外 聚类分析还经常用于其他分析方法的一个预处理步骤 在早期的i d e s 5 j t 6 j 中 采用了参量化统计分析的方法 来描述用户或系统的 行为模式特征 使用这种参量方法的前提条件是 所分析的数据满足某种特定的 分布 在早期的i d e s 中 都假定用户模式满足高斯分布或正态分布 如果这种 假设不成立 将会导致系统产生大量的错误报告 t u l a n eu n i v e r s i t y 的l i m a l a n k e w i c z 和m a r kb e n a r d 首先提出了使用非参量化的分析技术 聚类分析来 克服这个问题l l 同人工神经网络 分类分析等其他应用于异常检测的智能方 法相比 聚类分析可以工作于非纯净的 无标记的审计数据源上 具有更大的实 用性 2 0 0 1 年 l e o n i dp o r t n o y j 率先将聚类分析应用于无指导的异常检测 i b m 的一位研究员指出1 25 j 将聚类技术用于建立无指导的入侵检测系统的系统行为 模型 检测模型 的研究出现的较晚 不太为人们所熟悉 但它代表了一个新的 有趣的研究方向 同基于其他数据挖掘技术的入侵检测技术一样 基于聚类分析的入侵检测技 术的难点主要在于如何根据具体应用的要求 从关于安全的先验知识出发 提取 出可以有效地反映系统特性的特殊属性 然后应用合适的算法进行挖掘 而且由 6 第1 章绪论 于入侵检测需要分析的数据量很大 数据维度高 数据特征复杂 既有连续特征 又有离散特征 要求采用的聚类算法具有较小的时间复杂度 较好的伸缩性和 处理复杂数据的能力 入侵检测的审计数据源有其自身的特点 充分了解其数据 源特征 选择和改进适用于入侵检测的聚类算法是一项很有意义的工作 1 4 研究意义与研究内容 如前所述 基于异常的入侵检测具有发现未知的入侵行为的特性 是当前入 侵检测技术的研究重点 数据分析模块又是入侵检测系统的核心 数据挖掘技术 可使数据分析自动化 基于异常的入侵检测系统的数据分析模块主要涉及两个问冠 1 如何建立 计算机系统或网络的正常行为模型 此后本文将其称为检测模型 2 如何以 此模型作为检测入侵的依据 来确定待检行为是否为入侵行为 基于数据挖掘的 传统的异常检测方法需要利用大量纯净的正常行为数据集来训练和建立检测模 型 因为如果训练数据集中包涵某种攻击的数据 则训练出来的模型就不能检测 到那种攻击行为 而通常情况下难以得到纯净的正常数据 因为在现实网络环境 中 很难保证在数据采集阶段没有入侵的发生 也很难对采集的数据进行标记 因为审计数据量往往非常庞大 很难人工给予标记 即使能够通过搭建一个专门 的模拟环境来得到标记数据 也很难保证这些数据真实反映了系统实际运行情 况 这就使其应用受到很大的限制 针对上述问题 本论文将研究的重点放在了基于网络的无指导异常检测系统 的数据分析方法上 本文尝试在未标记的 正常数据中混杂了少量入侵数据的网 络审计数据源上 采用聚类分析方法及相关技术 如孤立点 o u t l i e r 挖掘方法 自动建立一个检测模型 并给出使用该模型进行入侵检测的方法 该检测模型所 用训i 练数据集易于从实际运行环境中获得 且具有一定的自动化 自我学习能力 和较好的检测性能 因而有较大的实用价值 本文的所涉及的研究和实验框架如图1 2 所示 北京工业大学工学硕士学位论文 输出结果 图1 2 研究和实验框架 f i g u r e l 2t h ef r a m e w o r ko f m yr e s e a r c ha n dt e s t 由图l 一2 可见 本文的研究工作主要包括四个模块 数据的采集 数据的预 处理 检测模型构建 检测与评估 大致可分为数据准备 模型构建 解释与评 估三大阶段 数据准备阶段包括数据收集模块 数据预处理模块 主要任务是给出从实际 环境或实验环境中收集网络流量审计数据的方法 及将收集到的原始数据定制成 适合于检测模型生成的规范格式的方法 模型构建阶段即检测模型构建模块 这是本文的核心研究内容 主要任务是 使用具体的数据挖掘算法 本文主要使用了聚类分析与孤立点分析等算法 对 准备好的数据进行处理和分析 抽象出有利于进行判断和比较的系统行为模型 从审计数据中提取出能够精确描述系统行为模式的检测模型是提高入侵检测系 统性能的关键所在旧 解释评估阶段主要是对使用检测模型进行测试与评估的模块 该模块的主要 任务是给出使用检测模型进行入侵检测的方法 并对检测结果进行测试与评估 阻得到真正符合要求的模型 1 5 论文安排 第一章为绪论 主要介绍课题的背景 研究的现状 研究内容和研究意义 并对相关的入侵检测技术进行了概述 最后说明了论文的章节安排 第二章介绍数据挖掘中的聚类分析技术 主要概述了聚类分析所面临的挑 第1 章绪论 战 技术要素和研究成果 并介绍了本文所参考的相关算法 第三章介绍数据挖掘中的孤立点挖掘技术 主要介绍了基于距离的孤立点挖 掘的概念与算法 并总结了将聚类分析与孤立点挖掘相结合的思路与方法 第四章描述了网络审计数据的收集与预处理方法 介绍了使用网络嗅探器收 集网络上传输的数据包信息的原理与方法 及从嗅探器原始输出中组合成t c p 连接记录并构造记录特征属性的方法 第五章介绍了本文的核心内容 即基于聚类分析的无指导异常检测模型的构 建算法 及使用该检测模型检测入侵的方法 第六章是实验结果与分析 使用k d d 9 9 数据集对检测模型构建方法和检测 方法进行了性能测试 并对算法改进措施的效果进行了对比与分析 最后对全文进行工作小结 并对今后的工作进行了展望 蜚重三些盔兰三兰璺土兰鳘鎏銮 2 1 聚类分析简介 第二章聚类分析 聚类 c l u s t e r i n g 就是将物理或抽象对象分组成为多个类或簇 c l u s t e o 的过 程 划分的原则是在同一个簇中的对象之间具有较高的相似度 而不同簇中的对 象差别较大 聚类分析的输入可以用一组有序对 或 奶表示 这里x 表示 一组对象 s 和d 分别是度量对象间相似度或相异度 距离 的度量 聚类分析 的输出是一个簇或类的集合c c l c z c k 其中c i 卢1 2 k 是x 的子集 即 c lu c 2u u c 女 z c n c j o i a c 中的成员c 1 c 2 c k 叫做类或簇 类内的对象按s 或d 衡量满足一定的 近似条件 而属于不同类的对象则满足一定的非近似条件 每一个类都是通过 些特征描述的 在许多应用中 可以将类中的对象作为一个整体来对待 与分类 c l a s s i f i c a t i o n 不同的是 聚类操作中要划分的类是事先未知的 类的形成完全是数据驱动的 聚类分析不依赖预先定义的类和带类标记的训练实 例 属于一种无指导的学习 u n s u p e r v i s e dl e a r n i n g 方法 作为一个数据挖掘中的一个功能 聚类分析能作为一个独立的工具来获得数 据分布的情况 帮助人们识别密集的和稀疏的区域 或者概括出每个簇的特点 或者集中注意力对特定的某些簇作进一步的分析 此外 聚类分析也可以作为其 他分析算法的预处理步骤 由于现今数据库中收集了大量的数据 聚类分析已经 成为数据挖掘研究领域中的一个活跃的领域 1 8 j 2 2 聚类分析面临的挑战 数据挖掘技术的一个突出的特点是处理巨大的 复杂的数据集 在数据挖掘 领域 目前针对聚类的研究工作大多集中于对大型数据集寻求有效的和实际的聚 1 0 第2 章聚类分析 类分析方法 它的潜在的应用对聚类分析算法提出各自特殊的要求 1 8 聚类分 析方法面临的挑战主要为 1 可伸缩性 可伸缩性是指算法要能处理大数据量的数据库对象 比如处理上百万条记 录 这就要求算法的时间复杂度不能太高 最好是多项式时间的算法 2 处理不同类型属性的能力 目前许多聚类算法被设计用来聚类数值类型 n u m e r i c a l 的数据 但是 应 用可能要求聚类其它类型的数据 如二元类型 b i n a r y 分类 标称类型 c a t e g o r i c a l n o m i n a l 数据 序数型 o r d i n a l 数据 或者这些数据类型的混合 3 发现具有任意形状地聚类的能力 许多聚类算法基于欧几里德距离或曼哈坦距离的相似性度量方法 这一类算 法发现的聚类通常是一些球状的 大小和密度相近的类 但可以想象 现实数据 库中的聚类可以是任意形状 故要求算法有发现任意形状的聚类的能力 4 输入参数对领域知识的弱依赖性 很多聚类算法都要求用户输入一些参数 例如需要发现的聚类数 聚类结果 对于输入参数往往很敏感 另一方面 对于高维数据 这些参数又是相当难以确 定的 使得分析的结果难以控制 5 处理噪声数据的能力 现实数据库中常常包含有异常数据 如孤立点 空缺 甚至错误数据 一些 聚类算法对于这样的数据敏感 可能导致低质量的聚类结果 6 结果对输入记录顺序的无关性 一些聚类算法对于输入数据的顺序是敏感的 也即 对同一个数据集 将它 以不同的顺序输入到分析算法 得到的结果会不同 这是我们不希望的 7 处理高维数据的能力 一个数据库或者数据仓库可能有很多的字段或者维 一些分析算法对处理维 数较少的数据集时表现不错 例如二 三维的数据 人类能够对二 三维数据的 聚类结果的质量做出较好的判断 但对于高维数据就没有那么直观了 所以对高 维数据进行聚类分析很具有挑战性 北京工业大学工学硕士学位论文 2 3 聚类分析算法的基本要素分析 聚类分析算法必须明确它所要处理的数据类型 采用的相异性 或相似性 度量 选取什么特征来代表类及如何度量类间相异性等基本问题 本文将其称为 聚类分析算法的基本要素 2 3 1 聚类分析中的数据类型 在数据挖掘领域 聚类分析算法通常采用关系表的形式作为数据结构 将要 聚类的数据对象表示为具有某些属性 也称为特征或维 的记录形式 对象的数据类型大致可分为三种 数值型数据 或者称连续型数据 对象的 所有属性都是数值型的 离散型数据 如 二元型 分类 标称类型 对象的所 有属性都是离散型的 混合型数据 既有数值型属性 又有离散型属性 目前 大多数的聚类算法都是基于数值型数据的 由于数据挖掘的内容经常 含有非数值的离散数据 近年来人们在处理离散数据 混合型数据方面做了许多 研究 提出了一些基于此类数据的聚类算法 如k p r o t o t y p e 33 1 k m o d e 3 3 1 r o c k 34 1 c a c t u s 3 鄂 l i m b o r 3 6 1 c o o l c a t 3 7 1 等 这些方法都侧重于针对离 散型数据或混合数据提出新的相似度或相异度度量方法 或者新的聚类特征表示 方法 类间距离计算方法等 2 3 2 相异性 或相似性 度量 一个聚类分析过程的质量很大程度上取决于对相似性 或相异性 度量标准 的选择 我们用s x 力表示对象x 和对象y 的相似度 当x 和y 相似时 s x y 的取 值较大 当x 和y 不相似时 s 0 力的取值较小 但是在许多情况下 聚类算法不是计算两个对象间的相似度 而是用某种距 离度量标准来计算两个样本间的相异度 用d x 力来表示 当x 和y 相似时 距 离a x 力的取值较小 当x 和y 不相似时 d x y 较大 通常 对象间距离的定义需要按对象的数据类型等情况具体确定 1 数值型数据的距离度量 第2 章聚类分析 对于n 维数值型数据对象x 和y 常用的距离定义有以下几种 1 欧几罩德距离 2 曼哈坦距离 0 y k y i d g y 2 1 2 2 3 明考斯基距离 d y f 窆o 一j 厂 z 明考斯基距离是欧几里德距离和曼哈坦距离的概化 这里m 是一个正整数 当m l 时 它表示曼哈坦距离 当m 2 时 它表示欧几里德距离 2 离散型数据的距离度量 前面我们所阐述的几种距离度量对于连续的数值型数据是很有效的 但不适 合离散型数据对象 对于离散型数据 经常被采用的距离度量是简单匹配系数 s m c 即统计两个对象的对应的属性离散值的总不匹配量 假定x 和y 分别是p 维离散属性的数据对象 x k 和挑分别表示x 和y 在第k 维属性的取值 则x 和y 之间的s m c 距离为 yy z 舢 生l 其中 万 以 2 4 或者 d x y 艺占 以 y 女 其中 j x k y k l o i2 儿 2 5 孔 y 女 针对离散数据 研究者不断提出一些新颖的相似度度量方法 如在r o c k 算法中 两个对象x 和y 的相似度进而以它们共同的近邻数目来表示 北京工业大学工学硕士学位论文 2 3 3 类特征 经常需要将簇或类作为一个整体来对待 因此需要给出一些类特征来代表一 个类 1 数值型数据的类特征 对于数值型数据 经常使用的类特征为 类重心 类中的一个或几个代表对 象 如中心点对象 最边缘对象 同时选用几个对象 类的直径 类的样本离 差矩阵等 其中最常用的是类重心 类重心即类中各对象的均向量 假如e 是一个有n 个对象的聚类 x 是g 内 的数据对象 即x c 那么类重心x 定义如下 薯 2 i i 薹 q 石 2 离散型数据的类特征 对于离散型数据 在选择类特征的问题上 往往比数值型数据更为复杂 为 能展示聚类的有意义的特征 不适合用平均值做类代表 而适合用实际存在的数 据对象 如中心点 或者构造有意义的模型 如k m o d e 算法中所定义的模型 c a c t u s t 3 5 埤法中定义的类摘要 s u m m a r y 2 3 4 类间距离 在聚类过程中 不仅要两个对象的距离 有时也需要计算类间的距离 常用 的类间距离计算方法有 重心法 定义两类的两个重心间的距离为类间距离 最短距离法 定义两个类中最靠近的两个对象问的距离为类间距离 最长距离法 定义两个类中最远的两个对象间的距离为类间距离 针对离散数据 研究者也提出一些新颖的类间相似度度量方法 如 r o c k 3 4 算法采用 互连性 来度量两个类的相似度 所谓 互连性 是基于来自不 同类的有相同近邻的对象的数目 文献 3 8 j 提出使用两个类合并后最大似然性降 低的程度来度量类间距离 c o o l c a t 3 7 1 提出使用信息论的 熵 值来度量类 间距离 第2 章聚类分析 2 4 聚类分析算法的分类 聚类分析是一个活跃的研究领域 已经有大量的经典的和流行的算法涌现 依据算法所采用的基本思想 聚类分析的算法可以分为以下几大类 1 8 1 1 划分法 p a r t i t i o n i n g m e t h o d s 给定一个有 个记录的数据集 划分法将构造k 个分组 每一个分组就代 表一个簇 k d o 则一个对象 o 是d 的孤立点 换句话说 若我们根据数据对象的d o 的距离 对数据对象 升序排序 在这个排序中前面n 个对象就被认为是孤立点 定义3 3 5 2 孤立点是数据集中h 个与其k 个最近邻居的平均距离最大的对 象 以上几个定义尽管不同 但都是基于距离的 区别在于对孤立点的孤立程度 的量度不同 基于距离的孤立点与基于统计的方法有几个优点 首先 它不要求 用户知道数据集服从哪种统计分布模型 同时 它克服了基于统计的孤立点检测 仅能检测单个属性的缺点 3 2 2 基于距离的孤立点挖掘算法概述 文献 1 8 中对基于距离的孤立点挖掘算法进行了介绍 基于此文献 对基于 距离的孤立点挖掘算法概述如下 1 基于索引 i n d e x b a s e d 的算法 基于索引的算法采用多维的索引结构 如r 树 x 树 来查找每个对象 在半径d 范围内的邻居 根据定义3 1 一旦 的第腑 个邻居被发现 o 就被 声明为非孤立点 这种算法现在被使用地较少了 因为除了构造索引结构的计算 量之外 它的复杂度在最坏的情况下是 陆锄 其中盯为数据对象的数目 第3 章孤立点挖掘 2 循环 嵌套 n e s t e d l o o p n l 算法 为了避免构建索引结构 减少算法的i o 次数 一种叫作循环一嵌套的方法 被提出来 其思想是 将内存缓冲区分成大小相同的两块 第一块用来保存从没 在该块保存过的数据块 同时把数据集划分为若干块 算法每次将一个数据块读 到内存缓冲区的第二块中 第一次首先将第一个数据块读到第一块 然后计算这 两块中的每对对象间的距离 对第一块中的每个对象f 用一个变量c o u n t 记录 它的d 距离邻居 一旦它的d 距离邻居数超过肘 则计数停止 开始处理下一个 对象 如果计算完第二块中的对象后 f 的c o u n t 值仍然不大于此则下一次将 另一个数据块读进内存缓冲区的第二块后 继续用r 与新读进的对象计算距离 并累计其c o u n t 值 显然 这种算法比较容易理解 它的计算复杂度是d r 七 刀0 当 增加时 复杂度的增加是线性的 3 基于单元 c e l l b a s e d 的算法 基于单元的算法试图避免 伍锄0 的计算复杂度 它的思想是 首先将数据 集划分为边长为 d 2 七的单元 每个单元有两个层围绕着它 第一层的厚度 为一个单元 第二层的厚度为2 j 该算法逐个单元地检测异常 而不是逐个 对象检测 e m x n o r r r t n g 4 9 1 等对基于单元的算法进行了详细的分析 指出它的复 杂度关于珂是线性的 但在 i 上是指数级的 仅当妖 4 时 算法