毕业设计（论文）-属性约简算法及其在入侵检测中的应用研究.doc

毕 业 论 文（设 计）题 目 属性约简算法及其在入侵检测中的应用研究 姓 名 学号 所在院(系) 数学与计算机科学学院 专业班级 信息与计算科学1101班 指导教师 完成地点 陕西理工学院 2015年 6 月3属性约简算法及其在入侵检测中的应用研究作者：（陕西理工学院数学与计算机科学学院信息与计算科学专业1101班，陕西 汉中 723000）指导教师： 摘要随着计算机网络在社会生活中各领域的广泛应用，计算机网络技术提供了巨大的信息含量和交互功能，提高了各个领域的工作效率。但随着网络技术快速发展，各种各样的问题也随之产生，其中网络安全问题更为突出，各种网络攻击日益频繁，病毒日益泛滥，网络的安全风险系数不断提高，曾经作为最主要安全防范手段的防火墙，已经不能满足人们对网络安全的需求。在这种情况下，作为计算机安全领域的重要技术之一的入侵检测技术应运而生。入侵检测是一种更加积极主动的安全防护技术，具有智能检测、实时探测、易于配置、动态响应等特点，其与静态的防火墙技术相结合会使得网络防护水平得到大幅度提高。 属性约简是指在确保信息系统决策能力不变的条件下，删除条件属性中的冗余属性，从而减少了数据挖掘中要处理的数据量，提高了数据挖掘结果的简洁性。本文采用三种不同的属性约简算法（邻域粗糙集、启发式算法、relief算法）进行实验，然后使用支持向量机进行模拟。实验结果表明邻域粗糙集属性约简算法较其他算法能更加有效提高检测率的同时降低误警率。关键词属性约简、入侵检测、邻域粗糙集、启发式算法、relief算法、支持向量机attribute reduction algorithm and its application in intrusion detectionauthor: yang yanpeng(grade11，class 1， major in information and computing science， mathematics and computer science dept. shaanxi university of technology， hanzhong 723000，shaanxi)tutor: zhao huiabstract：with the computer network technology is widely applied in various fields，computer network technology offers enormous information content and interactive features in social life，improve the efficiency of various fields. but with the rapid development of network technology，also will produce a variety of problems，including network security issues particularly prominent，attacks have become increasingly frequent，increasingly spread the virus，network security risk factor continues to improve， had served as the main security prevention means firewalls can no longer meet peoples need for network security. in this case，intrusion detection technology as a key technology in the field of computer security one emerged. intrusion detection is a proactive security protection technology，with intelligent detection， real-time detection，dynamic response，ease of configuration and other characteristics，which combined with static firewall technology will make the network protection level has been greatly improved.attribute reduction means ensuring information system decision-making capability under the same conditions, delete conditions attribute redundant attributes, data mining thereby reducing the amount of data to be processed to improve the simplicity of data mining results. this paper uses three different attributes reduction algorithm (neighborhood rough set, heuristic algorithm, relief algorithm) experiments, and then use the support vector machine simulation. experimental results show that neighborhood rough set attribute reduction algorithm can be more effective than other algorithms to improve the detection rate and reduce false detection rate.key words: attribute reduction；intrusion detection；neighborhood rough set；heuristic algorithm, relief algorithm; support vector machine (svm);目 录1.绪论11.1 引言11.2 研究的背景及意义11.3国内外研究现状21.4论文研究的主要内容及结构安排22.入侵检测概述42.1 入侵检测功能和基本原理42.2 入侵检测技术42.2.1 异常检测52.2.2误用检测62.3属性约简在入侵检测中的重要性72.4 入侵检测系统的发展趋势72.5 小结83.属性约简算法93.1属性约简算法的基本原理93.2本文中用到的属性约简算法概述93.2.1基于属性重要性的启发式算法93.2.2 relief 特征提取算法113.2.3 邻域粗糙集属性约简法133.3 小结144.仿真实验与结果分析154.1 支持向量机原理154.2 支持向量机的优势与不足164.2.1 支持向量机在入侵检测领域中的主要优势164.2.2 支持向量机在入侵检测领域中的不足164.3 小结165.仿真实验及分析175.1数据来源说明175.2 算法评价标准175.3 数据预处理175.4 仿真实验175.4.1 实验步骤175.4.2 实验结论及分析185.5 实验结论20致谢21参考文献22陕西理工学院毕业设计1.绪论1.1 引言随着互联网技术的高速发展，互联网已经成为人们日常生活中不可或缺的部分，个人、企业以及职能部门愈来愈多地依靠网络传递信息，然而网络的共享性与开放性容易使它受到外界的攻击与破坏，信息的安全性受到严重影响。信息安全问题已成为世界各国政府、企业及广大用户最关心的问题之一。在计算机上处理业务已由基于单机的数学计算、文件处理，基于简单连结的内部网络的内部业务处理等，发展到基于企业复杂的内部网、外部网、全球互联网的企业级计算机处理系统和国际性的信息共享和业务处理。在信息处理能力提高的同时，系统的连结能力也不断的提高。但在信息连结能力、流通能力提高的同时，基于网络的安全问题也日益突出，黑客攻击日益频繁，安全防范问题日趋严峻。因此，信息安全问题变得越来越重要。信息安全的最基本的目标是发展防御性的信息系统。此外，信息安全最大程度地减少相关的三个主要安全目标，即保密性，完整性和可用性的风险。而以往的一些安全防御措施诸如防火墙（firewall）、安全审计、数据加密、访问控制等，都存在一些缺陷，且功能过于单一，不能构成一个完整的安全防御体系，使网络安全问题变得越来越突出。而入侵检测(intrusion detection)采用的是一种较为主动的防御技术，可以有效地弥补防火墙的不足，能有效地发现网络入侵行为以及合法用户滥用特权的行为。若将入侵检测技术与动态防火墙技术等联合使用，那么可以大大提高系统的安全防护水平。1.2 研究的背景及意义每年全球范围内的入侵事件不计其数，由于网络安全问题造成的损失非常大。因此，网络安全是国家安全与国防安全的重要组成部分，对于入侵行为的检测、防范，保障计算机信息系统的安全就成为当前研究的重要课题。传统的防范网络入侵最常用的方法就是防火墙技术、加密策略、漏洞扫描等，它们不能确保网络中的计算机不受外来入侵者的攻击。防火墙是设置在不同网络（如企业内部网和不可信任的公共网）或网络安全域之间的一系列部件的组合，它属于基于网络层的安全技术，其作用是为了保护企业内部网络或单独节点。它是通过在相邻网络边界上建立相应的网络通信监控系统，尽可能的对外部网络屏蔽有关被保护网络的信息、结构，以达到保障网络安全的目的。它具有简单实用的特点，并且透明度高，可以在不修改原有网络应用系统的情况下达到一定的安全要求。但是，防火墙只是一种被动的防御性的网络安全工具，仅仅使用防火墙是不够的。首先，入侵者可以通过防火墙的漏洞，绕过防火墙进行攻击。其次，防火墙对来自内部的攻击无能为力。它所提供的服务方式是要么都拒绝，要么都通过，不能检查出经过他的合法流量中是否包含着恶意的入侵代码，这是远远不能满足用户复杂的应用要求的。加密策略是利用现代的数据加密技术来保护网络系统中包括用户数据在内的所有数据流，这类方法在数据传输过程中不对所经过的网络路径的安全程度作要求，从而真正实现网络通信过程端到端的安全保障；漏洞扫描是自动检测远端或本地主机安全脆弱点的技术，它查询tcp/ip端口，并记录目标的响应，收集关于某些特定项目的有用信息，从而保证计算机的安全。这些技术有一些共同点，首先，它们都是被动的安全技术，都需要人为的参与才能发现未知的安全问题，因此，它们对新出现的安全问题总是反映太慢。另外，这些安全措施多是针对外来安全威胁，对于系统内部的攻击却束手无策。针对上述问题，一个更为有效的解决途径就是入侵检测技术。在入侵检测技术之前，大量的安全机制都是根据从主观的角度设计的，他们没有根据网络攻击的具体行为来决定安全对策，因此，它们对入侵行为的反应非常迟钝，很难发现未知的攻击行为，不能根据网络行为的变化来及时地调整系统的安全策略。而入侵检测技术正是根据网络攻击行为而进行设计的，它是一种主动的网络安全技术，是对防火墙的必要补充，作为重要的网络安全工具，它可以对网络资源进行实时检测，及时发现闯入系统或网络的入侵者，也可预防合法用户对资源的误操作。它不仅能够发现已知入侵行为，而且有能力发现未知的入侵行为，并可以通过学习和分析入侵手段，及时地调整系统策略以加强系统的安全性。1.3国内外研究现状对入侵检测的研究最早可追溯到20世纪80年代初8，anderson首先提出并阐述了入侵检测概念，并指出可以通过监视和存储相关审计数据信息，建立用户正常行为审计信息模型，以发现系统中存在的异常行为。1987年，denning提出了一个经典的入侵检测模型，该模型的意义在于它是一般化的模型定义，与具体系统和具体输入无关，基本模型中的各个部件都可根据实际系统的设计要求，加以具体实现。1997年，随着通用入侵检测框架的制定，研究者提出了许多入侵检测方法，这些方法大体可分为两大类：误用入侵检测方法和异常入侵检测方法。其中专家系统、模式匹配、状态转移分析等误用入侵检测方法己比较广泛地应用于各种入侵检测产品中。在国内入侵检测的研究工作开展比较晚，科研工作主要集中在中科院信息安全国家重点实验室、北京大学、北京邮电大学、武汉大学等几个机构。在工业界的主流产品有：联想的“网御”、方正的“方通sniper”、东软的“neteye” ，中科网威公司的“天眼”、绿盟公司的“冰之眼”等。商业产品在研究方法上仍然以误用检测为主，在系统结构上向分布式发展。属性的最小约简是个np-hard问题，导致np-hard问题的主要原因是属性的组合爆炸。高效的约简算法是粗糙集应用于知识发现的基础。rough集理论是波兰数学家z.pawlak于1982年提出的一种数据分析理论，是一种新的处理模糊和不确定性知识的数学工具。在保持分类能力不变的前提下，通过知识约简，导出问题的决策或分类规则。它的一个显著特点是无须提供问题所需处理的数据集合之外的任何先验信息，而且产生的规则简单、易于理解。由于最初关于粗糙集理论的研究主要集中在波兰，因此当时并没有引起国际计算机界和数学界的重视。直到1990年前后，由于该理论在数据的决策与分析、模式识别、机器学习与知识发现等方面的成功应用，才逐渐引起了世界各国学者的广泛关注。 1991年z.pawlak的专著rough sets-theoretical aspects of reasoning about data的问世，标志着粗糙集理论及其应用的研究进入了活跃的时期。1992年在波兰召开了关于粗糙集理论的第一届国际学术会议。1995年acm将粗糙集列为新浮现的计算机科学的研究课题。目前，粗糙集理论已成为信息科学最活跃的研究领域之一。 把基于粗集理论的属性约简方法应用到入侵检测系统的思想是针对安全信息、数据量日益增加的问题而提出的。作为一种混合了误用检测技术和异常检测技术的检测方法，基于粗糙集理论的属性约简的入侵检侧方法是人们研究的新热点之一。以数据为中心，把入侵检测看作一个数据分析的过程，利用数据挖掘的方法从审计数据或数据流中提取感兴趣的知识，这些知识是隐含的、事先未知的潜在的有用信息，提取的知识表示为概念、规则、规律、模式等形式，并用这些知识去检测异常和己知的入侵。网络中的数据量巨大，数据的属性众多，相当一部分属性对最终检测结果是无用的，有些甚至会产生误导，属性约简方法将这些属性分离出来，使检测过程集中在关键数据属性上。 在国内，符海东，赵建峰提出了基于rough集理论和人工免疫的入侵检测系统，通过rough集理论对网络数据约简得到规则检测器，使用规则检测器设计了基于rough集的反向选择算法，得到免疫检测器。利用免疫检测器和规则检测器，构造了基于rough集和人工免疫的入侵检测算法。陈伟统，钱法涛提出了基于粗糙集理论的网络入侵检测方法，应用混合遗传算法求解粗糙集的约简，减少了计算时间。实验结果表明，该方法对dos和probe攻击具有很高的检测率和较低的误检率，并且对u2r和r2l攻击也有较好的检测率。1.4论文研究的主要内容及结构安排论文研究的主要内容：1.入侵检测技术，主要研究入侵检测的功能、分类、方法。2.研究属性约简的基本方法与算法，重点研究基于属性重要性的启发式属性约简算法、relief属性约简算法以及邻域粗糙集属性约简算法。研究规则的生成，及分类规则发现的算法步骤和模式。3.研究将属性约简算法应用到入侵检测技术的方法。以便得到入侵的检测框架，并将三种属性约简算法应用到其中。4.利用kdd cup 99数据集进行仿真实验，验证邻域粗糙集属性约简算法较其他两种属性约简算法中是更效性的。2.入侵检测概述2.1 入侵检测功能和基本原理入侵是指未授权用户以及合法用户有目的的从事危害计算机网络或系统信息资源的完整性、保密性或可用性的行为。作为一种主动的网络安全技术，入侵检测通过收集和分析计算机网络或系统的网络连接数据、口志文件和系统调用记录等信息，从而发现内部入侵者(越权使用系统资源的合法用户)和外部入侵者(系统的非法用户)对网络或系统信息资源的非授权操作，并作出及时响应，以保证信息资源的完整性、保密性和有用性。入侵检测系统是执行入侵检测功能的软件与硬件结合的计算机系统，其主要功能包括：监测和分析用户及系统的行为；检测系统安全配置情况和漏洞；评估计算机系统安全和关键资源和数据文件的完整性；统计分析异常行为，并做出响应。入侵检测系统是实现入侵检测功能的一系列的软件、硬件的组合。作为一种安全管理工具，它从不同的系统资源收集信息，分析反映误用或异常行为模式的信息，对检测的行为做出自动的反应，并报告检测过程的结果。入侵检测系统从其最基本的形式的角度来看就是一个分类器，它根据系统的安全策略来对收集到的事件、状态信息进行分类处理，从而判断出是入侵或非入侵行为。入侵检测的基本原理：入侵检测过程本质上是一种电子数据处理过程，安装预先确定的方法对收集到的安全审计数据进行分析处理，根据分析结果做出系统是否被入侵的结论。入侵检测基本原理如图2.1所示。其中，数据源是指ids原来检测入侵活动的原始信息，包括审计数据、系统日志、网络包、文件或程序中不期望的改变等；感应器收集上述信息，剔除无用的数据，将可疑事件传给分析器；分析器将这些事件与入侵模式库进行比较，如确定为入侵事件则向管理器发出警报；管理器是操作员与ids之间的接口，它负责向操作员通报入侵事件，而操作员可通过管理器对ids进行配置，或者对ids发布应急措施；管理员负责安全策略的实施，比如决定ids如何安装，哪些主机不允许外部网络访问等。另外需要说明的是，在实际的ids系统中，感应器和分析器的划分并不十分严格，往往交织在一起；管理员与操作员可以是同一人，也可以不是。数据源感应器入侵模式库管理器管理器管理器管理器警报事件活动通告应急图 2.1 入侵检测基本原理 2.2 入侵检测技术 虽然在几十年的发展过程中，入侵检测系统的结构随着信息系统的结构变化而不断变化，但入侵检测的方式却基本沿用至今，主要分为两种：异常检测(anomaly detection)和误用检测(misuse detection)，异常检测是抽取系统的静态形式和可接受的行为特征，然后检测对静态形式的错误改动和可疑的动态行为，误用检测是假设入侵活动可以用一种模式来表示，检测系统将检测系统内部发生的活动是否符合这些模式。 2.2.1 异常检测 异常检测分为静态异常检测和动态异常检测两种，静态异常检测在检测前保留一份系统静态部分的特征表示或者备份，在检测中，若发现系统的静态部分与以前保存的特征或备份之间出现了偏差，则表明系统受到了攻击或出现了故障。动态异常检测所针对的是行为，在检测前需要建立活动简档文件描述系统和用户的正常行为，在检测中，若发现当前行为和活动简档文件中的正常行为之间出现了超出预定标准的差别，则表明系统受到了入侵。其结构如图2.2所示：图2.2 异常入侵检测是否偏离正常行为库网络数据异常检测日志数据入侵行为正常行为描述 目前使用的异常检测方法有很多种，其中有代表性的主要由以下5种。 (1)基于特征选择的异常检测方法基于特征选择的异常检测方法，是从一组特征值中选择能够检测出入侵行为的特征值，构成相应的入侵特征库，用以预测入侵行为。其关键是能否针对具体的入侵类型选择到合适的特征值，因此理想的入侵检测特征库，需要能够进行动态的判断。 在基于特征选择的异常检测方法中，maccabe 提出的使用遗传算法对特征集合进行搜索以生成合适的入侵特征库的方法是一种比较有代表性的方法。 (2)基于机器学习的异常检测方法 基于机器学习的异常检测方法，是通过机器学习实现入侵检测，主要方法有监督学习、归纳学习、类比学习等。在基于机器学习的异常检测方法中，carla和brodley提出的实例学习方法ibl比较具有代表性，该方法基于相似度，通过新的序列相似度计算，将原始数据转化为可度量的空间，然后应用学习技术和相应的分类方法，发现异常类型事件，从而检测入侵行为。其中，阈值由成员分类概率决定。 (3)基于模式归纳的异常检测方法 基于模式归纳的异常检测方法，是假定事件的发生服从某种可辨别的模式而不是随机发生。在基于模式归纳的异常检测方法中，teng和chen提出的利用时间规则识别用户正常行为模式特征的基于时间的推理方法比较具有代表性，该方法通过归纳学习产生规则集，并对系统中的规则进行动态的修改，以提高其预测的准确性与可信度。 (4)基于数据挖掘的异常检测方法 基于数据挖掘的异常检测方法，是在对计算机网络产生的大量文件进行分析的基础上产生的，随着计算机网络的快速发展，其产生的文件数量也越来越多，单纯依靠人工方法对其进行分析以发现异常已经变得非常困难，因此数据挖掘技术被引入到了入侵检测领域。目前基于数据挖掘的异常检测方法中，有代表性的是kdd算法，其优点是适合处理大量数据，缺点在于运算量偏大，对数据的实时性分析支持不够。 (5)基于神经网络的异常检测方法 基于神经网络的异常检测方法，是利用神经网络的分类和识别功能对数据进行分析，特别适用于一些环境信息十分复杂、背景知识不详、样本有较大的缺陷和不足的情况下。基于神经网络的异常检测方法，首先要获取研究主体，如主机、用户等的行为模式特征知识，利用神经网络的识别、分类和归纳能力，实现入侵检测系统适用用户行为的动态变化特征。神经网络的缺点在于计算量较大，这将影响检测的实时性要求。2.2.2误用检测 误用入侵检测方法首先建立己知各种攻击行为的特征库，然后将当前行为特征依次同特征库中的各种攻击特征依次匹配，从而确定入侵行为的发生。误用入侵检测方法的优点在于：检测己知攻击的准确率高。但其存在攻击行为特征库维护工作量大，不能检测未知攻击，漏报率高的不足。误用检测在执行时会使用一个行为序列，称为“入侵场景”来确切地描述一个已知的入侵方式，若系统检测到该行为序列完成，则意味着一次入侵发生。早期的误用检测系统使用规则来描述所要检测的入侵，但由于规则组织上存在缺陷，所以造成规则数量过大，且难以解释和修改。为了克服这一缺点，后来的入侵检测系统使用了基于模型和基于状态转化的规则组织方法。其结构如图2.3所示：图2.3 误用入侵检测网络数据日志数据入侵行为误用检测产生规则入侵规则库规则匹配 目前使用的误用检测方法有很多种，其中有代表性的主要由以下 3 种。 (1)基于条件概率的误用检测方法 基于条件概率的误用检测方法，是基于概率论的一种通用方法，其将入侵方式对应一个事件序列，然后观测事件发生序列，应用贝叶斯定理进行推理，推测入侵行为。基于条件概率的误用检测方法是对贝叶斯方法的改进，其缺点是先验概率难以给出，而且事件的独立性难以满足。 (2)基于状态迁移分布的误用检测方法 基于状态迁移分析的误用检测方法以状态图表示攻击特征，不同状态刻画了系统某一时刻的特征。初始状态对应于入侵开始前的系统状态，危害状态对应于已成功入侵时刻的系统状态。初始状态与危害状态之间的迁移可能有一个或多个中间状态。攻击者执行一系列操作，使状态发生迁移，可能使系统从初始状态迁移到危害状态。通过检查系统的状态就能够发现系统中的入侵行为。使用基于状态迁移分布的误用检测方法的有代表性的入侵检测系统是 ustat。 (3)基于规则的误用检测方法 基于规则的误用检测方法，是指将攻击行为或入侵模式表示成一种规则，只要符合规则就认定它是一种入侵行为。基于规则的误用检测按规则组成方式分为以下两类： 1前推理规则。根据收集到的数据，规则按预定结果进行推理，直到推出结果时为止。这种方法的优点是能够比较准确地检测入侵行为，误报率低；其缺点是无法检测未知的入侵行为。目前，大部分ids采用这种方法。 2向后推理规则。由结果推测可能发生的原因，然后再根据收集到的信息判断真正发生的原因。因此，这种方法的优点是可以检测未知的入侵行为，但缺点是误报率高。采用了基于规则的误用检测方法的有代表性的入侵检测系统是 snort。2.3属性约简在入侵检测中的重要性决策表代表决策信息系统的简化，其中有海量的样本信息。而其中一个样本代表一条决策规则，全部规则又构成一个决策规则集。在现实使用里，这种决策规则集没有实用性，因为里面每个基本规则没有适用性，仅仅是机械的记下一个样本信息，没法适应别的状况。而进行属性约简后决策表的一条记录就变成了有相同规律的样本信息，决策规则于是有了非常强的适用性。在信息分析中，最开始的决策表里的属性并非都重要，不必要关系在信息库里是冗余的，冗余属性不仅占用资源，而且会扰乱人们不能作出正确、简洁的决策，故决策表中属性约简的作用就是把冗余信息从信息库中剔除，并且属性约简不影响信息库的分类功能。笼统的说，决策表的条件属性对应决策属性时相对属性约简不唯一，也就是说同一决策表可以存在多个属性约简，其中属性的数量将直接决定决策规则的繁复和功能。所以，人们都希望能找到有最少属性数量的属性约简。粗糙集理论rst是1982年由波兰华沙理工大学pawlak教授提出的一种处理不确定性和模糊知识的数学工具 经过近些年的研究和发展，rough集理论已经在人工智能机器学习数据挖掘模式识别和智能信息处理等领域取得了较为成功的应用，其中属性约简是rough集理论的核心内容之一，所谓属性约简是指在保证信息系统决策能力不变的条件下，删除条件属性中的冗余属性，从而减少数据挖掘要处理的数据量，提高数据挖掘结果的简洁性冗余属性的存在一方面会引起资源的浪费( 需要存储空间和处理时间)，另一方面会干扰人们做出正确而简洁的决策。确切的说，属性约简是对决策表中的条件属性进行简化，且约简后的决策表与原决策表具有相同的性质，但是约简后的决策表具有更少的条件属性。属性约简可以在对检测机制或数据本身内容理解的基础上，通过寻找描述入侵或系统正常行为的有效数据特征，缩小分析数据的规模，在尽可能保持分析数据原貌的前提下最大限度地精简数据量。在入侵检测中，对数据的处理过程，属性约简是关键技术，对入侵检测的准确性，高效率起到不可或缺的作用。2.4 入侵检测系统的发展趋势（1）体系结构由集中式向分布式转变 随着网络系统的日趋大型化、复杂化，以及入侵行为的协作性，入侵检测系统的体系结构由基于主机和基于网络的集中式向分布式发展，重点需要解决不同入侵检测系统之间检测信息的协同处理与入侵攻击的全局信息的提取。 （2）入侵检测系统的标准化 具有标准化接口将是入侵检测系统的下一步发展方向之一，这将有利于不同类型的入侵检测系统之间进行数据交换与协同处理以及入侵检测系统与其它安全产品之间的信息交互。ietf(internet engineering task force)下属的入侵检测工作组(idwg)已经制定了入侵检测消息交换格式(idmef)、入侵检测交换协议(idxp)、入侵报警(iap)等标准，以适应入侵检测系统之间安全数据交换的需要。 （3）安全技术综合集成 入侵检测系统能够及时识别并记录攻击，但并不能实时阻止攻击，因此，针对网络的实际安全需求，需要将入侵检测系统与防火墙、应急响应系统等逐渐融合，组成一个综合性的信息安全保障系统。 （4）面向应用的入侵检测 面向应用层的入侵检测也将是入侵检测系统的下一步发展方向之一。因为由应用程序所解释的各种不同类型的数据，其语义只有在应用层才能被理解，因此，只有入侵检测系统面向应用层，才能对其进行理解和并进行分析。2.5 小结本章首先介绍了入侵检测的概念，指出了入侵检测的用途和目的；其次，通过介绍入侵检测的原理及其分类，指出了入侵检测系统的基本原理与工作模式并阐明属性约简在入侵检测中的重要性；最后，本文作者在阅读相关文献的基础上总结了当前入侵检测技术的进展和发展趋势，指明了当前学术界对入侵检测常用的方法和技术。3.属性约简算法3.1属性约简算法的基本原理 属性约简是粗糙集理论中的一个重要的研究课题7，有很多学者作了这方向的研究工作。一般说来，知识库中的知识(属性)重要性是不一样的的，还存在大量的冗余，这不利于决策者做出正确而简洁的决策。属性约简要求在保持知识库分类和决策能力不变的前提下，删除那些不相关或不重要的属性。一般而言，成功的的属性约简有如下指标：约简后属性数比较少、约简后规则比较少、最终范化规则数比较少等。属性约简是对决策表中的条件属性进行简化，且约简后的决策表与原决策表具有相同的性质，但是约简后的决策表具有更少的条件属性。属性约简可以在对检测机制或数据本身内容理解的基础上，通过寻找描述入侵或系统正常行为的有效数据特征，极大的缩小分析数据的规模，在尽可能保持分析数据原貌的前提下最大限度地简化数据量。3.2本文中用到的属性约简算法概述3.2.1基于属性重要性的启发式算法给定信息系统是一个四元组，其中是给定网络连接的样本集，为一个非空有限集合，是从网络连接中抽取的41个特征集，为一个决策属性集合。 是特征的取值范围的集合，其中 是特征的值域。决策属性集的取值范围为，其中表示异常的网络连接，表示正常的网络连接是信息函数，它指定中每一个对象各个特征的取值。表示中所有不可省略关系的集合。定义1 给定一个信息系统，则改进的区分矩阵，定义为：其中是元组在属性上的取值，是在决策属性上的取值。定义2 设信息系统中属性有个不同的属性值，则属性的属性重要性函数为：基于属性重要性的启发式算法5-6在使用区分矩阵约简时，通常分为以下3个步骤：第一步求出区分矩阵；第二步是求核，即将区分矩阵中只包含一个属性的元素并起来；最后是求约简，对非核属性按属性的重要性从大到小依次排序，属性的重要性定义由定义2给出的属性重要性函数的值确定，值越大属性越重要。抽取最重要的属性将其加入核中，并将包括此属性的所有节点删除。一直按此方法处理直到区分矩阵为空，这时所得到的集合即为最终所求。具体算法如下 ：输入决策表。输出约简表。其中为相对于的约简。步骤 1根据定义1求出区分矩阵m。步骤 2 求相对于的核。设，按属性个数由小到大对中属性组合进行排序。查询中各个元素，若为单一属性组合则该属性的元素集合就是所求。步骤 3 设。按定义2计算属性重要性函数，取最大函数值的属性加入。并删除中所有包含此属性的元素。依次取最大的函数值对应的属性，直到为，此时 就为最终所求。步骤 4 即为属性约简后的决策表，其中为的相对于的约简， 、 由、 去除部分属性而来。标准的和声搜索算法：和声搜索(harmony search，hs)算法9是在2001年由韩国学者geem z w等人提出的一种相对新颖的智能优化算法。算法模拟了在音乐创作中乐师们凭借着自己的记忆，通过反复的调整乐队中各种乐器的音调，最终达到了一个美妙的和声状态的过程。hs算法将乐器声调的和声类比于优化问题的解向量，评价即是各对应的目标函数值。算法引入两个主要参数,即记忆库取值概率(harmony memory considering rate， hmcr) 和微调概率(pitch adjusting rate， par)。算法首先产生hms (harmony memory size)个初始解(和声)放入和声记忆库hm(harmony memory)内；然后，在和声记忆库内随机搜索新解，具体做法是: 随机产生的随机数，如果，则新解在内随机搜索得到；否则在和声记忆库外，变量可能的值域内搜索取值。再以微调概率对取自内的新解进行局部扰动。最后，判断新解目标函数值是否优于hm内的最差解，若是，则更新和声库，并不断迭代，直至达到预定迭代次数为止。目前，该方法已在多维多极值函数优化、管道优化设计、土坡稳定分析等问题中得到了广泛应用。有关研究表明，算法在解决多维函数优化问题上展示了较遗传算法、模拟退火算法等更好的优化性能。hs算法是geem等人通过类比音乐和最优化问题的相似性而提出的一种现代启发式智能进化算法。类似于遗传算法对生物进化的模仿、模拟退火算法对物理退火机制的模仿以及粒子群优化算法对鸟群鱼群的模仿等，和声搜索模拟了音乐演奏的原理。音乐和声是一种来源于审美观的，令人欢愉的美妙的声音组合。音乐演奏是要寻找一个由美学评价所决定的最佳状态(极好的和声)，同样最优算法也是寻找由目标函数值所决定的最优状态(全局最优最低花费、最大利益或效率)。美学评价是由参与演奏的乐器发出的声音集合所决定，正如目标函数值是由设计变量值所组成的集合决定的。表3.1对以上说法做出了简要的描述。表3.1 最优化与音乐演奏的对比类比元素优化过程实现过程最佳状态全局最优极好的和声被评价目标函数美学评价用评价设计变量值乐器和音调过程单元每次迭代每次练习在音乐演奏中，乐师们凭借自己的记忆，通过反复调整乐队中各乐器的音调，最终达到一个美妙的和声状态。geem z w等人受这一现象启发将乐器类比于优化问题中的第个变量，各乐器的音调相当于各变量的值，各乐器音调的和声相当于优化问题的第组解向量，音乐效果评价类比于目标函数，提出了hs算法。算法首先初始化和声记忆库，然后从和声记忆库中随机产生新的和声，如果新的和声比记忆库中最差的和声好，把新的和声放进记忆库，把最差的和声换出记忆库。如此循环直至满足停止准则。和声搜索的计算步骤如下: step1: 定义问题与参数值假设问题为最小化，其形式如下这里是目标函数，是由决策变量构成的解向量，每一个决策的值域为。对于离散型变量；而连续型变量:，为决策变量个数，为离散型变量可能值的个数。算法参数有：和声记忆库的大小、和声记忆库取值概率、音调微调概率、音调微调带宽、创作的次数，各参数在第一步均要被初始化。step2: 初始化和声记忆库随机生成个和声放入和声记忆库，这里和声记忆库可以类比于遗传算法中的种群。和声记忆库形式如下:step3: 生成一个新的和声生成新的和声，新和声的每一个音调通过以下三种机理产生: 学习和声记忆库，音调微调，随机选择音调。举例说明：新解的第一个变量有的概率选自中的任何一个值，有的概率选自外（且在变量范围内）的任何一个值。同样的，其它变量的生成方式如下：其中表示上的均匀分布的随机数。其次，如果新的和声来自和声记忆库hm，要对其进行音调微调，具体操作如下： 其中，为音调微调带宽，为音调微调概率；表示上均匀分布的随机数。step4: 更新和声记忆库对step3中的新解进行评估，如果优于中的函数值最差的一个，则将新解更新至中。具体操作如下：step5: 检查是否达到算法终止条件重复步骤step3和step4，直到创作(迭代)次数达到为止。3.2.2 relief 特征提取算法relief算法10是一种有效的特征选择算法，具有运算速度快泛化能力强的特点。relief系列算法是filter模型中的代表性算法，具有运算速度快泛化能力强的特点relief算法最早由kira提出，最初局限于两类数据的分类问题，后来拓展出relieff 和rrelieff算法。relief系列算法是一种特征权重算法，根据各个特征和类别的相关性赋予特征不同的权重，权重小于某个阈值的特征将被移除 算法中特征与类别的相关性是基于特征对近距离样本的区分能力。 算法从训练集中随机选择一个样本，然后从和同类的样本中寻找最近邻样本，称为near hit，从和不同类的样本中寻找最近邻样本，称为near miss，然后根据以下规则更新每个特征的权重: 如果和near hit在某个特征上的距离小于和near miss上的距离，则说明该特征对区分同类和不同类的最近邻是有益的，则增加该特征的权重；反之，如果和near hit在某个特征的距离大于和near miss上的距离，说明该特征对区分同类和不同类的最近邻起负面作用，则降低该特征的权重 以上过程重复次，最后得到各特征的平均权重 特征的权重越大，表示该特征的分类能力越强，反之，表示该特征分类能力越弱relief 算法的运行时间随着样本的抽样次数和原始特征个数的增加线性增加，因而运行效率非常高。relief算法的主要思想是：对属性区分样本类别的能力进行评估。该算法提出了假设间隔(hypothesis margin)，指在保持样本分类不变的情况下，分类决策面能够移动的最大距离。其可表示为 ：其中，和分别表示同类和异类样本集。通过计算假设间隔就可以估计出分类的最优特征子集。实现流程如下 ：(1) 建立模型，其中，为训练样本集，为特征维数，为迭代次数， 为同类和异类空间的样本数。权重向量表示每个属性对应的权重，初始值为0。(2) 从 开始，每次从中随机选择一个实例样本，并找出与所在类相同的 最近邻样本实例，称为nearhits(简称)以及与所在类不同的最近邻样本实例，称为nearmisses(简称)。(3) 对于每次循环，从开始，按如下公式不断更新属性的权重。其中，表示第j属性， 表示每次随机选取的实例，和表示和空间中的第元素。 和 分别表示样本实例 在属性与以及中第实例之间的差值。如果属性取值为离散型，当属性值不同时，和取值1，相同时取值为0。通过relief算法建立对属性区分样本的能力进行评估，根据何种条件从评估结果选择正确的特征直接决定了relief模型的效果。本文通过三个条件来提取适当的特征 ：(1) 选择属性值中权值大于0的属性。(2) 选择在次遍历中，权值变化次数大于10%的属性。(3) 选择在取不同值时，50% 以上次数都被选择的属性。通过实验证明，上述三种选择条件的提出，克服了原模型只重视属性评估而忽略属性选择的缺点。与原来按权值从大到小进行选择的方式相比，新的选择方式考虑到属性选择的稳定性，更加合理。relief 算法的具体描述如下:输入: 训练数据集，样本抽样次数，特征权重的阈值。输出: 特征权重大于阈值的特征组成的特征子集。(1) 置所有特征权值，为特征维数；置为空集。(2) 从1到，遍历如下过程:a) 随机选择一个样本；b) 从同类样本集中找到 的最邻近样本，从不同类样本集中找到最近邻样本；c) 对个特征权值进行更新:其中: 和分别为样本与和在特征上的距离(3) 将特征权值的特征加入子集中3.2.3 邻域粗糙集属性约简法粗糙集理论是由波兰学者pawlak于1982年提出的一种有效处理不完整、不精确信息的数学分析工具，该理论的特性是不需要任何先验信息，仅使用数据本身的内部信息便能从中发现隐含知识，揭示潜在规律，对不完整不精确数据进行有效处理。传统粗糙集理论首先要将连续数据离散化，这样会导致原始信息的丢失，计算处理的结果在很大程度上取决于离散化的效果。邻域粗糙集3是胡清华在经典粗糙集理论模型的基础上发展起来的能够直接处理连续型数据的方法，它不需要事先对连续型数据进行离散化处理，可直接用于知识约简等问题。因此，为保证入侵检测的准确性和原始信息的完整性，本文采用邻域粗糙集方法进行属性约简，在此基础上对入侵检测信息样本空间进行邻域粒化，直接计算样本距离，确定样本之间相邻关系。邻域决策系统，其中是一个样本集，称之为一个样本空间。是一个属性子集，既条件属性。是一个输出特征变量，称之为决策属性，l表示所属样本的标记。表示属性的值域，f 是一个信息函数，可表示 ，其中 。如果且，样本在中的邻域为，则，其中是一个预设的阈值，是在中的一个测度函数。设和是中的两个样本，表示样本在第维属性的值，则minkowsky距离可定义为： 。给定邻域决策表是具有决策属性类别值1到的样本集，则，所以是的一个划分，表示由属性子集产生的包括样本的邻域信息粒度，则决策属性关于属性子集的下近似和上近似表示为： 设，则属性的重要度定义为：输入： and neighborhood /is the threshold to co