（计算机软件与理论专业论文）粗糙集在入侵检测中的应用与研究.pdf

摘要 数据挖掘是目前数据库和决策支持领域的最前沿的研究领域之一。 而粗集方法是数据挖掘中的个重要方法。入侵检测系统( i d s ) 是一种 从计算机网络或者计算机系统中收集信息并分析是否存在攻击行为的 主动式防御工具。入侵检测技术也是目前信息安全研究的重点之一。本 文主要研究粗集方法在入侵检测系统中的应用。本文在标准的网络数据 集和对粗集方法的研究基础上，分析了目前粗集方法中主流的几个约简 算法在处理网络数据时的性能，提出了目前存在的一些不足。并提出了 一种新的约简算法。通过大量的实验表明，这种改进在用于处理标准网 络数据的时候是非常有效的。 关键词：数据挖掘粗糙集( 粗集) 入侵检测遗传算法 a b s t r a c t t h ed a t a m i n i n gi so n eo ft h em o s t 行o mr e s e a r c ha r c ai nd a t a b a s e a n dd c c i s i o n m a k i n gs u p p ( ns y s t e m r o u g hs e t si sai m p o r t a n tm e l o di n d a t “m i n i n g h l 虮l s i o nd e t e c t i o ns y s t e n li sai n i t i a t i v ed e f 两d i l l 窟s y s t e m w h i c ha n a l y s ei n f b 彻a t i o nc o l l e c t e df b mi n t e m e to rc o m p u t e rs y s t e m i tc a n d e t e n n i n ew h e t h e rt h e r ei sa t t a c ka c t i o ni nm e s ei n f o n n a t i o n a tp r e s e n t ， 玎) s ( i n t m s i o nd e t e c t i o ns y s t e m ) i sai m p o r t a n tp a ni ni n l o n n a t i o ns a f e r e s e a r c h t m sd o c 啪e n tf b c u so nt l l ea p p l i c a t i o no fr o u 咖s e t si n ) s b a s e d o nt h er e s e a r c ho nd a t as e t sf b mt h eh l t e n l e ta n dt h er e s e a r c ho nm er o u 曲 s e t s ，w ea n a l y s em ep e r f o n n a n c eo fs o m er e d u c t i o na l g o r i t l l e m b r i n g f o r w a r ds o m es h o n a g ea n dp r o p o s ean e w “窖o r i t h e m m a s se x p e r i e m e n t i n d i c a t e so u rn e wa l g o r i t h e mi se m c i e n ti nh a i l d l i n 窟t h ed a t a 疗d mt h e s t a n d a r ds e t s k e y w o r d s ：d a t a m i n i n gr o u g h s e t si d s ( i n t r u s i o nd e t e c t i o ns y s t e m ) g a ( g 阻e t i ca i g o r i t h e m ) 2 1 1 研究的目的和意义 第1 章概述 网络与安全技术越来越密不可分。目前，许多机构都依赖计算机网 络开展日常业务。有时候，网络甚至已经影响到企业能否生存。随着依 赖程度的提高，数据被盗的成本逐渐升高，恶意代码和拒绝服务( d o s ) 攻击造成的危害也越来越大。事实上，计算机安全局( c s i1 与圣弗朗西 斯科联邦调查局( f b i ) 计算机入侵科所作的“2 0 0 4 年计算机犯罪和安 全调查”表明，美国大约每2 0 秒种就发生一次计算机犯罪，去年给企 业造成的损失高达1 4 l 亿美元【ij 。 在网络犯罪形势日益严峻的背景下，对于网络信息安全技术的研究 显的尤为重要。目前，用于防范网络犯罪，网络入侵和计算机病毒的主要 工具有防火墙、入侵检测系统、以及各种的口令认证和加密系统。 入侵检测是为系统管理员提供的一种保护他的网络免遭入侵的工 具。入侵检测方法主要分为两大类：滥用检测( m i s u s ed e t e c t i o n l 和异常 检测( 觚o m a l yd e t e c t i o n ) 。滥用检测的基础是建立攻击行为特征库，采用 模式匹配的方法确定攻击事件。它的优点是检测的误报率低，检测速度 快。但滥用检测通常不能发现攻击特征库中没有事先指定的攻击行为， 所以无法检测出新的攻击形式。异常检测则是通过建立用户正常行为模 型，以是否显著偏离该模型为依据进行入侵检测。同滥用检测相比，异常 检测有一定的误报率，但因为它只根据当前的系统行为同正常模型的相 似度来判断是否存在入侵行为，因此有可能发现新的入侵行为。但是， 这两种方法都需要建立大量的规则或特征，尤其是对滥用检测，而人工建 立这些规则库或特征库的现状已经远远不能适应现实对入侵检测的要 求。因此必须采取一定手段进行规则库或特征库的自动建立，才能使入 侵检测系统具有可扩充性和移植性【2 l 。 数据挖掘是一个从已知数据集合中发现各种模型，概要和导出值的 过程f ”。粗集方法是进行数据挖掘的主要方法之一【3 1 。粗集方法的前提 是许多企业的数据库中存在着大量的对于知识发现规则来说不必要的 和冗余的属性，如果不去掉这些冗余的属性，不仅发现规则的时间复杂 性大大增长，而且发现规则的质量下降。粗集方法是一种通过属性约简 ( 去掉冗余属性) 来处理不确定性知识的数学方法。通过属性约简除去 冗余的属性，从而提高发现知识的效率和质量。粗集理论的主要优势之 一就在于它不需要关于数据的任何预备的或者额外的信息。 在信息时代，随着计算机应用的普及，每年都要积累大量的信息， 即数据。同样对于网络来说，同时间网络的各个节点间会有大量的数 据传输，这其中包含正常数据的同时也包含着入侵或者病毒。同时也包 含着大量噪音数据或者说不相关的数据。 将粗集方法应用于入侵检测的自动规则的生成，能够提升整个入侵 检测系统的工作效率，使实时性入侵检测系统成为可能。 1 2 国内外研究现状 粗集理论( r o u 曲s e t ) 是波兰数学家z p a w l a k 于1 9 8 2 年提出的，是 一种新的处理含糊性( v a g i l e n e s s ) 和不确定性( u n c e n a i m y ) 问题的数学工 具。相对于概率统计，证据理论，模糊集等处理含糊性和不确定性问题 的数学工具而言，粗集理论既与它们有一定的联系，又有这些理论不具 备的优越性。统计学需要概率分布，证据理论需要基本概率赋值，模糊 集理论需要隶属函数，而粗集理论的主要优势之一就在于它不需要关于 数据的任何预备的或额外的信息。 1 9 9 1 年，z p a w l a k 教授撰写了第一本关于粗集理论的专著r o u 譬h s e t s t h e o r e t i c a l a s p e c t so f r e a s o n i n g a b o u t d a t a 。1 9 9 2 年在波兰召开了 第一界国际粗集研讨会，以后每年都有以粗集理论为主题的国际研讨 会。1 9 9 5 年，第n 期的a c mc o 舢蚰i c a t i o n 将粗集列为人工智能及认 知科学领域新浮现的研究课题，并发表了p a w l a k 等人的“r o u 曲s e t s ” 一文。该文概括性地介绍了粗集理论的基本概念及粗集在部分领域的研 究及进展。 入侵检测技术在2 0 世纪8 0 年代最早提出。1 9 8 0 年，a n d e r s o n 在 其完成的一份技术报告中提出了改进安全审计系统的建议，以便用于检 测计算机用户的非授权活动。同时，提出了基本的检测思路。 1 9 8 7 年，d o r o m yd e 衄i n g 发表的经典论文“a nh n m s i o nd e t e c t i o n m o d e l ”中提出入侵检测的基本模型，并提出了几种可用于入侵检测的 统计分析模型。d e n l l i n g 的论文正式启动了入侵检测领域的研究工作。 1 9 9 0 年，加州大学d a v i s 分校的t 0 d dh e b e d i e n 发表在匝e e 上的 论文“an e 铆o r ks e c 谢t ym o n i t o r ”，标志着入侵检测第一次将网络数据 包作为实际输入的信息源。n s m 系统截获t c p ，碑分组数据，可用于监 控异构网络环境下的异常活动。 1 9 9 2 年，加州大学圣巴巴拉分校的p o n a s 和n g u n 提出了状态转移 分析的入侵检铡技术，并实现了原型系统u s 丑灯，之后发展出n s l a 1 ， n e t st a t 等系统。 1 9 9 5 年，普渡大学的s k u m a r 在s 仉盯的思路基础上，提出了基于 有色p e 啊网的模式匹配计算模型，并实现了i d i o t 原型系统。 1 9 9 7 年，c i s c o 公司开始将入侵检测技术嵌入到路由器，同时，i s s 公司发布了基于w i n d o w s 平台的r e a l s e c u r e 入侵检测系统，自此拉开 商用网络入侵检测系统的发展序幕。 2 0 0 0 年，酱渡大学的d i e g oz 锄b o n i 和e s p a 舶r d 提出了入侵检测 的自治代理结构，并实现了原型系统丸氏f i d 系统。 目前对先进入侵检测技术的研究主要集中在神经网络、数据挖掘 、数据融合、计算机免疫学等方面【4 】。 从现有的实际商用系统来看，大多数都是基于滥用入侵检测技术， 这也反应了市场和用户的某种对确定性功能的心理需求。不过，在若干 种优秀的入侵检测系统中，也采用了不同形式的异常入侵检测技术和对 应的检测模块。将滥用检测和异常检测结合已经成为目前入侵检测技术 研究的热点。而基于数据挖掘的入侵检测系统的研究正是将滥用检测和 异常检测相结合的先进入侵检测技术研究的方向之一。 1 9 9 9 年美国哥伦比亚大学的w e l l l ( el e e 应用m p p e r 软件包 5 】，从 系统调用序列中挖掘正常和异常的模式，以规则的形式来描述系统的运 行状态，建立了一个简洁有效的系统正常模型【6 1 。从此国内外开始了将 数据挖掘应用于入侵检测系统的研究。 将数据挖掘应用于入侵检测，旨在对网络上截获到的海量数据进行 智能化处理，试图在大量的数据中提取人们感兴趣的数据信息及安全相 关的系统特征属性，建立基于数据挖掘的入侵检测模型，包括数据源的 选择、数据预处理、算法选择，创建数据挖掘模型、挖掘结果分析处理 及其可视化等。 从9 9 年至目前，数据挖掘与入侵检测结合的研究主要在分类，关 联分析，序列分析等模式的挖掘方面。 将粗集方法应用于入侵检测，目的在于通过对数据所包含的属性集 的约简，去除那些冗余的属性，也就是与本文的目标属性不相关的或者 相关度低的属性，经过约简后的属性集将极大的提高规则库的生成效 率，满足入侵检测系统实时性的要求。 1 3 主要研究内容 本文主要研究粗集方法在入侵检测系统中的应用。集中讨论了使用 粗集方法挖掘规则的流程，重点讨论了使用粗集约简算法简化入侵检测 中需要处理的属性集，通过约简提高入侵检测系统的实时性。本文分析 了使用不同的约简算法约简网络数据集后的效果。并在此基础上，提出 了一种新的基于知识量和属性依赖度的启发式约简算法，该算法以属性 子集与决策属性的依赖度为目标函数，通过设定合适的终止条件，输出 个与决策属性依赖度较高并且相对于以往的研究更小的属性子集，这 个子集用于入侵检测规则的生成，在不失检测的准确性的基础上，将极 大的提高系统的实时性。最后设计了一个采用该算法的入侵检测原型系 统。 4 第2 章数据挖掘与粗集理论 本章将介绍与数据挖掘和粗糙集相关的理论知识。这将成为我们研 究工作的基础。 2 1 数据挖掘简介 科技的进步，特别是信息产业的发展，把我们带入了个崭新的信 息时代。随着数据库技术的发展和数据库管理系统的广泛应用，最近十 几年中，数据库中存储的数据量急剧增大。然丽，目前的数据库系统所 能作到的只是对数据库中已有的信息进行存取，通过这种手段获得的信 息量仅占整个数据库信息量的一小部分，因为用来对这些数据进行分析 处理的工具很少。而且有局限性。隐藏在这些数据之后的更深层次，更 重要的信息能够描述数据的整体特征，可以预测发展趋势，这些信息在 决策生成的过程中具有重要的参考价值。面对海量数据库和大量繁杂信 息，如何才能从中提取有价值的知识，进步提高信息的利用率，由此 引发了一个新的研究方向：基于数据库的知识发现( k 1 1 0 w l e d g e d i s c o v e r yi nd a t 曲a s e ) 及相应的数据挖掘( d a t am i n i n 曲理论和技术的研 究。 2 1 1 什么是数据挖掘 人们给k d d 下过很多定义，内涵也各不相同，目前公认的定义是 由f a y v a d 等人提出的。所谓基于数据库的知识发现( k d d ) 是指从大量 数据中提取有效的，新颖的，潜在有用的，最终可被理解的模式的非平 凡过程 7 1 数据挖掘是k d d 过程的一个重要步骤，其中包含特定的数据 挖掘算法。算法能在可接受的计算效率下，在，上产生一系列的模式威。 也有些文献将k d d 和数据挖掘混用。 数据：指一个有关事实f 的集合，用以描述事物的基本信息。如学 生档案数据库中有关学生基本情况的记录。 模式：语言l 中的表达式e ，e 所描述的数据是集合f 的一个子集 f 。f 表明数据集f 中的数据具有特性e 。作为一个模式，e 比枚举数 据子集如更简单。如“如果分数在8 1 到9 0 之问，则成绩优良”可称 为一个模式。 非平凡过程：k d d 是由多个步骤构成的处理过程，包括数据预处 理，模式提取，知识评估及过程优化。所谓非平凡是指具有一定程度的 智能性和自动性，而绝不仅仅是简单的数值统计和计算。 有效性( 可信性) ：从数据中发现的模式必须有一定的可信度，通过 函数c 将表达式映射到度量空间地，c 表示模式昱的可信度，产c ( e ， 刃。其中e 三，e 所描述的数据集合r 凡 2 ，1 ，2 数据挖掘的步骤 数据挖掘的过程可粗略的分为：问题定义，数据收集和预处理擞据 挖掘算法执行以及结果的解释和评估蝴，如图2 1 所示： 图2 1 ：数据挖掘过程示意图 1 问题定义：数据挖掘的目的是为了在大量数据中发现有用的令人 感兴趣的信息。因此发现何种知识就成为整个过程中第一个也是最重要 的一个阶段。在问题定义过程中，数据挖掘人员必须和领域专家以及最 终用户紧密协作，一方面明确实际工作对数据挖掘的要求；另一方面通 过对各种学习算法的对比进而确定可用的学习算法。后续的学习算法的 选择和数据集准备都是在此基础上进行的。 2 数据准备和数据预处理：数据准备又可以分成三个子步骤：数据 选取，数据预处理和数据变换。数据选取的目的是确定发现任务的操作 对象，即目标数据，他是根据用户的需要从原始数据库中抽取的一组数 据。数据预处理一般可能包括消除噪声，推导计算缺值数据，消除重复 记录，完成数据类型转换等。当数据开采的对象是数据仓库时，一般来 说，数据预处理已经在生成数据仓库时完成了。数据变换的主要目的是 消除数据维数或者降维。即从初始特征中找出真正有用的特征以减少数 据挖掘时要考虑的特征或变量个数。 3 擞据挖掘：数据挖掘算法执行阶段首先根据对问题的定义明确挖 掘的任务或目的，如数据总结，分类、聚类、关联规则发现或序列模式 发现等。确定了挖掘任务后，就要决定使用什么样的挖掘算法。同样的 任务可以用不同的算法实现，选择挖掘算法主要有两个考虑因素：一是 不同的数据有不同的特点，因此需要用与之相关的算法来挖掘；二是用 户或实际运行系统的要求，有的用户可能希望获取描述型的，容易理解 的知识，而有的用户或系统的目的是获取预测准确性尽可能高的预测型 知识。 4 姑果的解释和评价：数据挖掘阶段发现出来的模式，经过评估。 可能存在冗余或无关的模式，这时需要将其剔除；也有可能模式不满足 用户的需求，这时则需要整个发现过程回退到前一个阶段，如重新选取 数据，采用新的数据变换方法，设定新的参数值，甚至换一种算法等。 另外，k d d 由于最终是面向人类用户的，因此可能需要将发现的模式 进行可视化处理，或者把结果转换成用户易懂的另一种表示，如把分类 决策树转换成“i f 一t h 肌”规则。 数据挖掘算法执行，是整个过程中的一个重要步骤。数据挖掘质量 的好坏有两个影响因素：一是采用数据挖掘技术的有效性；二是用于挖 掘的数据的质量和数量。如果选择了错误的数据或不适当的属性，或对 数据进行了不适当的转换，挖掘的结果是不会好的。可以说，它决定了 整个k d d 过程的效果和效率。 整个数据挖掘的过程是一个不断反馈的过程。比如，用户在挖掘途 中发现选择的数据不太好，或使用的挖掘技术产生了不期望的结果，这 时，用户需要重复先前的过程。甚至从头重新开始，如图中的虚线所示。 2 1 3 数据挖掘的任务 数据挖掘的任务就是要从数据集中发现模式，模式有很多种。按功 能可以分为两大类。一为描述性挖掘，对数据中存在的规则做种描述， 或者根据数据的相似性把数据分组。描述型模式不能直接用于预测。例 如，在地球上，7 0 的表面被水覆盖，3 0 是土地；二是预测性挖掘， 主要任务在当前数据上进行推断，以进行预测。在实际应用中根据预测 模式的实际作用又分为以下几种；分类，聚类，关联，序列等。 关联分析：关联分析产生关联规则。关联规则反映一个事物与其他 事物之间的相互依赖性或相互关联性。如果两个或多个事物之间存在关 联，那么，其中一个事物就能从其他已知事物中预测得到。所谓关联规 则是指数据集中支持度和信任度分别满足给定阈值的规则。关联分析的 典型例子是对大型超市的销售数据库建立关联规则模型和数据挖掘算 法。得到的信息有助于规划市场，合理安排货架等。关联规则形式如： “购买面包和黄油的顾客中有9 0 的人也购买了牛奶”，规则的前件是 面包和黄油，后件是牛奶。在基于关联规则的算法中最著名的算法是 r a 掣a w a l 等人提出的a 鲫o d 算法m “ 。 分类：分类数据挖掘是先分析一个训练数据集，找到一个描述并区 分数据类的模型，然后使用这个模型对类中标记未知的对象类进行分 类。分类的方法有很多，有决策树法，贝叶斯法，神经网络法，近邻学 习或基于事例的学习等方法。 聚类：聚类( c l u s t 耐n 西是将物理或抽象的对象集合分成多个组的过 程。聚类生成的组称为簇( c l u s t e r ) ，即簇是数据对象的集合。聚类就是 要让生成的簇内部的任意两个对象之间具有较高的相似度，而属于不同 簇的两个对象问具有较高的相异度。主要的数据挖掘聚类方法有：划分 的方法，层次的方法，基于密度的方法，基于网格的方法，基于模型的 方法等。 序列模式：序列模式与关联模式相仿，而把数据之间的关联性与时 间联系起来。为了发现序列模式，不仅需要知道事件是否发生，而且需 要确定事件发生的时间。例如，在购买彩电的人们当中，6 0 的人会在 3 个月内购买影碟机。 孤立点分析：数据库中可能包含一些数据对象，它们与数据的一般 行为或模型偏离很大，这些数据对象就是孤立点。大部分数据挖掘方法 将孤立点视为噪声或异常丢弃：而在有些应用中( 如信用卡欺诈) 。罕见 的事件可能比正常出现的更有趣。在市场分析中，可用于确定极低或者 极高收入客户的消费行为。 2 2 粗集( r o u 曲s e t ) 理论 粗集理论是一种应用于分类发现来进行数据挖掘的理论，由波兰数 学家z p a w l a l ( 于1 9 8 2 年提出，是一种新的处理含糊性( v a g i l e n e s s ) 和不 确定性( u n c e n a i n t v ) 问题的数学工具。 相对于概率统计，证据理论，模糊集等处理含糊性和不确定性问题 的数学工具而言，粗糙集理论既与它们有一定的联系，又具有这些理论 所不具备的优越性。统计学需要概率分布，证据理论需要基本概率赋值， 模糊集理论需要隶属函数，而粗集理论的主要优势之一就在于它不需要 关于数据的任何预备的或额外的信息。 给定的对象集合由若干个属性描述，对象按照属性的取值情况形成 若干等价类( 同一个等价类中对象的各个属性取值相同) ，同一个等价类 中的对象不可分辨。给定集合4 ，粗集基于不可分辨关系，定义集合爿 的上近似和下近似，用这两个精确集合表示给定集合。根据现有关于对 象的知识，下近似由肯定属于集合4 的对象组成，上近似由可能属于集 合4 的对象组成。 在实际应用中，可以将数据库中一个关系表看作个对象集合，表 中的每条记录看作一个对象。这给粗集方法的应用提供了极大的方便。 2 2 1 近似空间和不可分辨关系 设u 为所讨论对象的非空有限集合，称为论域；r 为建立在u 上 的一个等价关系，称二元有序组4 s = ( r ) 为近似空间( a p p r o x i m a t e s p a c e ) 。 近似空间构成论域u 的一个划分；若r 是u 上的一个等价关系， 以旺h 表示z 的r 等价类，【，r 表示r 的所有等价类构成的集合，即商 集：胄的所有等价类构成u 的个划分，划分块与等价类相对应。 令r 为等价关系族，设p r ，且p g ，则户中所有等价关系的 交集称为p 上的不可分辨关系( h l d i s c e m i b i l i t yr e l a t i o n ) ，记作j n d ( p ) ，即 有： 肋( d2 4 y 瑚 显然优d ( p ) 也是等价关系。 ( 2 1 ) 例2 1 设论域l k z ，x 玉幻，勘，扔 皿= 月，r 2 ，风) 是恒等关系，胄， 彤，飓定义如下： r 广f ， ， ， u ， r 2 = ， ， 工如工户， ，u j r 3 = ， ， ， ， ， ， ，a d ( p ) ，则称对象工与y 是p 不可分辨的，即x ，y 存在于不可 分辨关系n r d ( p ) 的同一个等价类中。依据等价关系族尸形成的分类知 识，x 与y 无法区分。彻( p ) 中的各等价类称为p 基本集。基本集是 粗糙集理论中构成知识的基本模块。若集合z 可以表示成某些基本集的 并时，称x 是p 可定义集，否则称为p 不可定义集。 2 2 2 近 以与粗糙集的基本概念 设集合x 量【，r 是一个等价关系，定义 星x = 扛i z 【，) 且h r ( 2 2 ) r x = x j x u ) 且嘲 n a )( 2 _ 3 ) 分别称鱼及r x 为x 的r 下近似集( l 0 w e r a p p r o x i m a t i o n ) 和尺上 近似集( u p p e ra p p r o x i m a t i o n ) 。 称集合占p ( ) = 砑掣为的r 边界域：尸d s p ( z ) = 丛为 的r 正域； 旧g 。似j ) = u 见y 为石的r 负域。 由( 2 2 ) 和( 2 3 ) 可知，在依据知识月判断时，里z 是由必定属于x 的 对象组成的集合；见y 是由可能属于z 的对象组成的集合；曰。( x ) 是 由既不能明确判断属于z 也不能明确判断属于似的对象组成的集合； 脚。( z ) 则是由一定不属于x 的对象组成的集合。 j 当删p ( x ) 一0 时，即肼= 丛时，称是胄精确集( 或r 可定义 集) 。当引v p ( ) o 时，即尺j 堡z 时，称为r 粗糙集( 或r 不可 定义集) 。 蹦是包含于石的最大矗可定义集，肘是包含x 的最小尺可定义 集。若集合x 是粗糙集，则对应于一个粗糙概念，只能通过一对精 确概念( 即上近似集和下近似集) “近似”地描述。 2 2 3 约简和核 约简和核是知识约简的两个基本概念。这两个概念是信息系统属性 约简的基础。 o 设r 是一个等价关系族，r 置，若有删d 俾) = 肌d ( 矗一俾) ) ，则称r 为等价关系族r 中可省的，否则称为不可省的。若胄中任意个等价 关系r 都是不可省的，则称且是独立的，否则称为依赖的。 设q 尸，若q 是独立的，且价口( q ) = w d ( p ) ，则称q 是等价关系 族p 的一个约简( r e d u c t ) 。p 中所有不可省关系的集合称为等价关系族p 的核( c b 撑) ，记作c 0 r 聃。 显然，p 可以有多个约简，以剧( 尸) 表示p 的所有约简的集合。 等价关系族p 的核等于p 的所有约简的交集，即有： c d r e ( p ) = n 艘d ( p )( 2 4 ) ( 2 4 ) 揭示了核与约简的关系。由于计算所有约简是n p 完全问题。 因此，虽然给出了所有约简与核的关系，但作为核的计算方法显然是不 妥的。它的意义在于，一方面，核可以作为所有约简的计算基础，并且 计算是直接的；另一方面，核可以解释为知识库中最重要的部分，是知 识约简时不能消去的知识。如在例2 1 中，p 就是r 的一个约简。 2 2 4 相对约简和相对核 相对约简和相对核的概念反映了一个分类与另一个分类的关系。 这两个概念是决策属性约简的基础。 设p 和q 为论域u 上的等价关系，q 的| p 正域记作p ( q ) ，定义 为： 尸吲q ) 。x 昌q ( 2 5 ) q 的j p 正域是u 中所有根据分类( 知识) 【p 的信息准确分类到关 系q 的等价类中去的对象构成的集合。 设p 和q 为论域u 上的等价关系族，只e p 。若：p d d ( p ) n d ( q ) ) = p 0 勘似p _ ) ( j d ( q ) ) 则称月为尸中q 可省的，否则称胄为p 中q 不 可省的。若p 中的任一关系r 都是q 不可省的，则称p 是q 独立的( 相 对于q 独立) 。 设s p ，称s 为p 的q 约简，当且仅当s 是p 的q 独立子族，且 p o s “q ) = p d ，q ) 。p 中所有q 不可省的原始关系构成的集合称为p 的 q 核，记作a 猁d 。尸的所有q 约简构成的集合记作r 肋d p ) ，p 的q 约简称为相对约简，p 的q 核称为相对核。 p 的q 核等于p 的所有q 约简的交集 c 唰p ) = n r 肋q 沪)( 2 6 ) p 的q 核是知识p 的本质部分。为了保证将对象分类到q 的概念 中去的分类能力不变，q 核知识是不可消去的。知识| p 的q 约简是p 的子集，该子集是q 独立的，且具有与知识p 相同的分类能力( 把对象 分类到知识q 的概念中去) 。 例2 2 ，- 孔声2 ，粕) 矾尸= 缸1 ) ， 靶 ，缸3 m ，缸5 j 6 ) ， 却一8 ) ) 洲( 声“x l 乒2 ) ，辑3 毒4 ) ，缸5 ，x 6 ) ， 0 7 ) ， 翔 ) 则p d 蹦q ) = ) u 缸2 ) u 胁m ) u 扛5 舶 = 轧托# 3 m 声5 j 6 2 2 5 知识库与知识的依赖性 粗糙集理论将分类方法看成知识，分类方法的族集是知识库。等价 关系对应论域【，的一个划分，即关于论域中对象的一个分类。 因此，通过一个等价关系可以形成与之对应的论域知识( 即等价类 的集合一商集) 。从而得到不可分辨关系对应论域u 上的知识。 称论域u 的子集为【，上的概念。约定a 也是一个概念，概念的族 集称为u 上的知识：u 上知识( 分类) 的族集构成关于u 的知识库，也就 是说，知识库是分类方法的结合。 近似空间对应u 的一个划分，所以，近似空间形成关于论域u 的 知识。 设己，为论域，r 为等价关系族，p r 且p a ，则不可分辨关系 胁，d c p ) 的所有等价类的集合，即商集啪( p ) 称为【，的p 基本知识， 相应等价类称为知识p 的基本概念。特别的，若等价关系q r ，则称 叫q 为【，的q 初等知识，相应等价类称为q 初等概念。由于选取r 的 不同子集p 可以得到u 上的不同知识，故称j 仁f u ，励为知识库。 出。 知识库中的知识并不是同等重要的，有些知识可以由其他知识导 设e ( 【，尺) 为知识库，p ，q r ： 1 ) 知识q 依赖于知识p ，记作p jq ，当且仅当上 d ( p ) 冬删d ( q ) 2 ) 知识户与知识q 等价，记作p ；q ，当且仅当p ；q ，且q j p 3 ) 知识p 与知识q 独立，记作p q ，当且仅当p j q 与q j p 均 不成立。 当知识q 依赖于知识p 时，也称知识p 可推导出知识q 。p = q 当 且仅当肋( p ) = w d ( q ) 。 知识的依赖性也可能是部分的，也就是说，知识p 可部分推导出知 识q 。知识q 部分依赖于知识j p 可由知识的正域来定义。 设肛u ，r ) 为一个知识库，且p ，q 胄，令 扣y d ( q ) = i p 0 蹦q ) i | 卅 ( 2 7 ) 称知识q 依赖于p ，依赖度为七，记作p j t q 。 例如例2 2 中的y d ( q ) = 6 8 = o 7 5 2 2 6 决策表与决策规则的生成 知识的表达方式在智能数据处理中有十分重要的地位。信息系统是 一种知识表达方式，利用信息系统和决策表来解释粗糙集的相关概念更 容易理解，并有助于粗糙集最终通过约简后生成易懂的决策规则。 称4 元有序组蹦u 一，e ，) 为信息系统，其中u 为所考虑对象的非 空有限集合，称为论域；爿为属性的非空有限集合； 肛o 1u 圪，而为属性d 的值域；，：u 爿一y 是一个信 盘爿h “ 息函数，v 工u ，d 4 ，( x ，口) e ，对于给定对象x ，o ，口) 赋予对 象x 在属性一a 下的属性值。信息系统也可简记为肛( l 翻) 。 信息系统可以用数据表格来表示，表格的行对应论域中的对象，列 对应描述对象的属性。一个对象的全部信息由表中一行属性的值来反 映。对于信息系统骆( l 埘) 来说，爿的每个属性对应一个等价关系，而 属性子集对应不可分辨关系。信息系统与一个知识库相对应，因此一个 数据表格可以看成一个知识库。 设辟( 以4 ，k 厂) 为信息系统，若爿可划分为条件属性集c 和决策属 性集d ，即c u d 刊，c n d = 0 ，则称信息系统为决策表( d e c i s i o nt a b l e l 。 孙，d ( c ) 的等价类称为条件类，n 口( 聊的等价类称为决策类。 决策表的分类： 1 称决策表是一致的当且仅当d 依赖于c ，即c 等d ； 2 称决策表是不一致的当且仅当c 等k d ( o j 酞1 ) ，也就是d 不完 全依赖c ，依赖度为k 。 可以通过求决策表的分辨矩阵和分辨函数的方法进一步求得条件 属性c 相对于决策属性d 的约简和核。具体的求约简的方法留待后续 章节讨论。 从给定的决策表中生成决策规则是粗糙集的主要应用之一。决策规 则用于对已知对象的分类，或对新对象的分类进行预测。 设黔( 【埘，) 是决策表，4 = c u d ，c 为条件属性集，d 为决策属 性集。令x i 和y i 分别表示条件类和决策类。 d 船( x i ) 表示条件类x ，的描述，定义为： d 部( x f 产 ( 口，屹) ，o ，口) 2 屹，v n c ) ( 2 8 ) d 甜( y i ) 表示决策类y ，的描述，定义为： d 邸( y ，) 。 0 ，屹) l ，o ，n ) 5 屹，v 口d ( 2 ，9 ) 决策规则定义为： 弓：d 甜( 鼍) 一胁( 】= ，) tny ，a ( 2 1 0 ) 规则巧，的确定性因子： ( 工，y ，) ：i 兰! 型 ( 2 1 1 ) 。 f 爿f 显然o “1 。 决策表中所有决策规则的集合称为决策算法。 4 第3 章粗集与入侵检测 本章主要介绍入侵检测的基本内容和粗集在入侵检测过程中的应 用。 3 1 入侵检测 3 1 1 基本概念 通常，计算机安全的3 个基本目标是：机密性，完整性和可用性。 相应的安全的计算机系统应该实现上述3 个目标，保护自身的信息和资 源，不被非授权访问，修改和拒绝服务攻击。 对于计算机系统的威胁来自于多方面，包括： 外部入侵者：系统的非授权用户 内部入侵者：超越合法权限的系统授权用户。 违法者：在计算机系统上执行非法活动的合法用户。 次入侵可以被定义为以破坏计算机网络安全为目的的一组行为 ”“。更为具体的有美国国家安全通信委员会( n s w 疋1 下属的入侵检测小 组( i d s g ) 在1 9 9 7 年给出的关于“入侵”的定义为： 入侵是对信息系统的非授权访问以及( 或者) 未经许可在信息系统中 进季亍的操作。 该小组同年给出的关于“入侵检测”的定义为： 入侵检测是对企图入侵，正在进行入侵或者已经发生入侵进行识别 的过程。 3 1 2 入侵检测的过程 入侵检测的过程可以分为三个阶段：信息收集，信息分析以及告警 和响应。 入侵检测的第一步是信息收集。即从入侵检测系统的信息源收集信 息，包括系统、网络、数据以及用户活动的状态和行为等。而且需要在 计算机网络系统的若干不同关键点( 不同网段和不同主机) 收集信息，这 样可以尽可能地扩大检测范围，一而且从一个信息源收集到的信息可能看 不出疑点，但从几个信息源收集到的信息的不一致性却是可疑行为或入 侵的最好标识。 信息分析是入侵检测过程的核心环节，没有信息分析功能，入侵检 测也就无从谈起。入侵检测的信息分析方法很多，如模式匹配，统计分 析，完整性分析等。每种方法都有其各自的优缺点，也都有其各自的应 用对象和范围。 当入侵检测系统检测到攻击或事件以后，系统根据攻击或事件的类 型和性质，作出相应告警与响应，即通知管理员系统正在遭受不良行为 的入侵，或者采取一定的措施阻止入侵行为的继续。常见的告警与响应 方式包括： 1 自动终止攻击。 2 终止用户连接。 3 禁止用户帐号。 4 重新配置防火墙阻塞攻击的源地址。 5 向管理控制台发出警告指出事件的发生。 6 ，向网络管理平台发出s mt r a p 。 7 记录事件的日志，包括日期、时间、源地址、目的地址、描述 以及事件相关的原始数据。 8 向安全管理人员发出提示性的电子邮件。 9 ，执行一个用户自定义程序。 3 1 3 入侵检测的信息源 按照数据来源的不同，入侵检测通常可以分为两类：基于主机的入 侵检测和基于网络的入侵检测。 基于主机的入侵检测通常从主机的审计记录和日志文件中获得所 需要的主要数据，并辅之以主机上的其他信息，例如文件系统属性，进 程状态等，在此基础上完成检测攻击行为的任务。从技术发展的历程来 看，入侵检测是从主机审计的基础上开始发展的，因而早期的入侵检测 系统都是基于主机的入侵检测技术。 特别的，从主机入侵检测技术中还可以单独分离出基于应用的入侵 检测类型，这是特别针对某个特定任务的应用程序而设计的入侵检测技 术，采用的输入数据源是应用程序的日志信息。 在获取审计数据的过程中主要需要考虑下列问题。 1 确定审计数据的来源和类型。根据目标系统的不同类型和主机入 侵检测的不同要求，需要收集的审计数据是不同的，如u 】n 系统和 w 小d o w s 操作系统的审计机制设计就是不同的。 2 审计数据的预处理工作，其中包括记录标准格式的设计，过滤和 映射操作等。 3 审计数据的获取方式，包括审计数据获取模块的结构设计和传输 模式等。 基于网络的入侵检测的信息源就是指通过各种方式从网络上截获 的数据包，根据网络类型的不同，网络数据截获可以通过两种方法实现 一种是利用以太网络的广播特性，另一种是通过设置路由器的监听端 口。 3 2 粗集与入侵检测 在逐步完善入侵检测系统的过程中，系统的实时性始终是一个非常 困扰的问题。尤其对于网络入侵检测系统，针对那些每天都有可能接收 到成千上万的数据的网络节点来说，如果不能满足实时性的要求就会发 生数据包的遗失，如果遗失的数据中包括恶意的数据，那么将会使得入 侵检测系统变的如同虚设。为了满足实时性的要求，我们考虑需要缩减 处理的信息量，将所有的数据和对应的属性列一张表，从中删除那些与 决策属性( 即我们感兴趣的目标属性) 关联度非常小的属性，那么就可以 从中提取一个所有属性的子集，这个子集必须能够在保证不损失性能的 基础上充分满足效率的需求，也就是说这个子集要足够小以满足实时处 理但同时又不能降低入侵检测系统的性能。这个时候引入粗集方法， 应用不同的约简算法来约简属性集。约简后的属性集可以用于其他算法 的输入，也可以直接推导出规则集。采用粗集方法的入侵检测系统的步 骤为数据的采集和预处理、数据过滤、数据离散化处理、属性约简、 规则的生成和过滤。本文将在下一章重点讲述采用 且集约简算法对来自 于网络的数据集进行约简。 3 2 1 数据的采集和预处理 在网络入侵检测系统中，主要的数据来自于对网络数据包的截获。 通常通过两种方式获得来自网络的数据。 第一种方式是通过将网卡设罱为混杂模式( p r o m i s c u o u s l ，使之接收 目标m a c 地址不是本机m a c 地址的数据包。然后直接访问数据链路层， 截获相关数据，由应用程序而非上层协议对数据进行过滤处理。通常使 用由美国洛仑兹伯克利国家实验室( h w e n c eb e r k e l e vn a t i o n l l a b o r a t o r y ) 所编写的专用于数据包截获功能的a p i 函数库l i b p c a p 。 l i b p c a p 库函数对上层程序屏蔽了底层系统的不同数据包截获方法，提 供了统一的编程接口，使得采用该编程接口的数据包截获模块可以十分 方便地在不同平台上进行移植。 第二种方式是当许多网络采取了交换运行环境( 交换机，路由器等1 ， 利用交换机或者路由器上设置监听端口或者镜像端口。 然而，通常从网络直接得到的数据是t c p d 啪p 格式的，并不适合于 直接构建分类模型。将得到的数据进行预处理，从中提取出以一次连接 为单位的信息，以便进行分类。这些经过预处理的数据具有一些固有属 性：d u r a t i o n ，s e n ，i c e ，s r c - h o s t ，d s t h o s t ，利用这些特征属性加上每条记录的 类型标识，可以初步建立入侵检测的分类模型。 3 2 2 数据过滤 数据过滤的目的就是减少入侵检测系统直接处理的数据量。有些数 据对入侵检测而言可能是没用，在处理前就去掉，可以减少存储空间和 处理时间，但数据过滤必须谨慎进行，以免删掉有用的数据。 3 2 3 数据的离散化处理 经过预处理和过滤后的数据仍然无法直接用于数据挖掘。需要将属 性值为连续值的属性离散化处理。 入侵检测系统中属性按照性质可以分为定量属性和定性属性 13 1 。定 量属性是指可被测量的对象属性，如接收到的字节数等；定性属性是指 可以用语言表达的对象属性，如使用的协议为t c p 或者u d p 等。 基于粗糙集理论的许多算法可以直接使用定性属性值，而不能直接 处理定量属性值。因此如何把定量属性转化为适合粗糙集处理的形式是 一个关键问题，定量属性的离散化是粗糙集数据分析的一项重要内容。 根据是否利用类信息，离散化方法一般可分为有监督和无监督两种类型 ”“。等距离散化和等频离散化是常用的两种无监督算法，前者将每一属 性的值域划分成距离相等的区间，适用于属性值均匀分布的情形；后者 将每个属性值域划分成区间，使每个区间包含相同数量的对象。由于上 述两种无监督算法不考虑决策属性，所以分类效果一般不理想，文献 1 5 】 根据统计学中频率分析的思想，利用每个定量属性的值域和标准差，确 定由小到大的属性区间，给每一个区间赋以一个标识符，由于每个对象 的属性值均落在某一特定区间，此区间的的标识符就作为该对象离散化 后的属性值。文献【1 6 利用决策表相容性的反馈信息，提出了一种领域 独立的基于动态层次聚类的连续属性离散化算法，为r s 理论处理离散 与连续属性提供了一种统一的框架。 有监督算法主要有，1 ) 自然算法 1 ”，该算法根据需要离散化的某属 性值将对象排序，按照对象的顺序，只要对象的决策值改变，就产生一 新区间，该算法产生保持决策系统一致性水平所需的所有分割点。2 1 半 自然算法【l ”，该算法的思想和自然算法相似