（计算机应用技术专业论文）基于web服务安全的异常数据挖掘算法研究.pdf

摘要 数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提 取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。在 数据挖掘的过程中，数据库中可能包含一些数据对象，它们与数据的一般行为或 模型不一致，这些数据对象被称为异常点，对异常点的查找过程称为异常数据挖 掘，它是数据挖掘技术中的一种。异常数据挖掘又称孤立点分析、异常检测、例 外挖掘、小事件检测、挖掘极小类、偏差检测等。孤立点可能是“脏数据”，也 可能是与实际对应的有意义的事件。从知识发现的角度看，在某些应用里，那些 很少发生的事件往往比经常发生的事件更有趣、也更有研究价值，例外的检测能 为我们提供比较重要的信息，使我们发现一些真实而又出乎预料的知识。因此， 异常数据的检溯和分析是一项重要且有意义的研究工作。 本文重点讨论基于w e b 服务器日恚文件的异常数据挖掘。系统地介绍了异常 数据挖掘的基本理论，分别利用基于统计的方法、基于距离的方法和基于偏离的 方法讨论了异常点的检测。重点讨论了基于距离的异常数据挖掘算法，即基于索 引的算法、嵌套循环算法和基于单元的算法，并从时间复杂度、空间复杂度等角 度进行了优缺点分析。考虑到使用基于距离的异常数据挖掘算法其效率较低并且 需要设置参数，算法实现困难，因此提出基于距离和的孤立点定义方法，利用基 于抽样的近似检测算法来实现w e b 服务器日志文件的异常数据检溅，实验结果表 明了该算法的有效性。 关键词：异常数据挖掘w e b 服务安全孤立点距离和预处理日志文件 a b s t r a o t d a mm i n i n gi sap o t e n t i a la n du s e f u li n f o r m a t i o ne x t r a c t i n gp r o c e s sf r o m a b u n d a n t , i m p e r f e c t , i n d i s t i n c ta n dr a n d o md a t a d u r i n gt h i sp r o c e s s ，s o m ed a t a o b j e c t sd i f f e r i n gf r o mt h en o r m a ld a t am o d e l sm a y b ei n c l u d e di nd a t a b a s e ，t h e ya l e c a l l e do u f l i e r s s e a r c h i n gf o ro u t l i e r si so n co ft h ed a t am i n i n gt e c h n o l o g i e s , w h i c h c a na l s ob ec a l l e do u t l i e ra n a l y s i s ，o u t l i e rd e t e c t i o n ，e x c e p t i o n a lm i n i n g , e v e n t s d e t e c t i o n , m i n i m u mm i n i n g , d e v i a t i o nd e t e c t i o ne t c o u t l i e r sm a yb e “d i r t yd a t a ”，a l s o b em e a n i n g f u le v e n t s f r o mt h ea n g l eo fk n o w l e d g ed i s c o v e r i n g , e s p e c i a l l yi ns o m e a p p l i c a t i o n ，t h ei r r e g u l a re v e n t sm a y b em o r ei n t e r e s t i n ga n dm o r ev a l u a b l et h a nt h e r e g u l a ro u e s t h ee x c e p t i o n a ld e t e c t i o nc a np r o v i d es o m e v i t a li n f o r m a t i o n 。w h i c hi s h e l p f u lt of i n ds o m e t r u eb u tu n e x p e c t e di n f o r m a t i o n t h e r e f o r e ，o u t l i e rd a t ad c t e c t i o n a n da n a l y s i si sa s i g n i f i c a n tr e s e a r c h t h i st h e s i sp u t se m p h a s i so no u t l i e rd a t am i n i n gb a s e do nw e bs e r v i c el o g i t i n t r o d u c e ss y s t e m a t i c a l l ys o m eb a s i ct h e o r i e so fd a t am i n i n ga n dd i s c u s s e st h eo u t l i e r d e t e c t i o nm e t h o d sb a s e do ns t a t i s t i c s ，d i s t a n c ea n dd e v i a t i o n t h ea r t i c l em a i n l y d i s c u s s e so u t l i e rd a t am i n i n ga l g o r i t h m sb a s e do nd i s t a n c e ，n a m e l yi n d e x - b a s e d , n e s t e d l o o pa n dc e l l b a s e d ，a n da n a l y z e st h em e r i t sa n dd e f e c t sf r o mt h ea n g l eo ft i m e a n ds p a c ec o m p l e x i t i e s c o n s i d e r i n gt h ei n e f f i c i e n c ya n dt h et r o u b l et os e tp a r a m e t e r s m a ym a k ei td i f f i c u l tt oi m p l e m e n ts u c ham e t h o d t h e r e f o r e , t h eo u t l i e rd e f i n i n g m e t h o db a s e do nd i s t a n c es u mi sp u tf o r w a r d b ym a k i n gu s eo ft h ea p p r o x i m a t e d e t e c t i o na l g o r i t h mb a s e do ns a m p l e ，o u t l i e rd a t ad e t e c t i o no fw e bs e r v i c el o gi s i m p l e m e n t e d a ne f f e c t i v er e s u l ti so b t a i n e di nt h ee x p e r i m e n t k e yw o r d s ：o u t l i e rd a t am i n i n + g , w e bs e r v i c es e c u r i t y , o u t l i e r s ，d i s t a n c es u m ， p r e t r e a t m e n t ，l o gf i l e i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特n d l i 以标注和致谢的地方外，论文中不包括其 他人已经发表或撰写过的研究成果，也不包含为获得西北师范大学或其他教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：日期：趔z ! 璺型 关于论文使用授权的说明 本人完全了解西北师范大学有关保留、使用学位论文的规定，即：学校有 权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名： 导师签名：至墼二 日期：墨! 望：! ：! ! 西曩师蠹大学焉士论文基于w 皿晨务安全的异常薮舞挖掘算洼研究 1 1 引言 第一章绪论 2 l 世纪以来，随着网络技术的发展和网络的普及，计算机系统和网络面临 的安全问题越来越严重。从简单的、利用系统漏洞的入侵和攻击，到拒绝服务攻 击，直至分布式拒绝服务攻击；从莫里斯蠕虫，到横扫全球互联网的冲击波和冲 击波杀手病毒，以及至今仍在四处泛滥的u y d o o m 和n e t s k y 邮件病毒。网络攻击 的方法和模式经历了一次又一次革命性的变化，特别是网络蠕虫等恶意移动代 码已多次造成全球规模互联网的瘫痪。同时，互联网上可随意下载的各种攻击工 具和溢出代码也使得网络攻击的门槛变低。此时，安全问题逐渐成为网络系统应 用中的首要问题。传统的信息安全系统概括性差，只能发现模式规定的、已知的 入侵行为，难以发现新的入侵行为。然而随着数据库技术的发展，特别是数据仓 库、数据挖掘等新技术的诞生，给w e b 服务安全检测带来了新的方法。例如人们 希望能够对审计数据进行自动的、更高抽象层次的分析，从中提取出具有代表性、 概括性的系统特征模式，以减轻人们的工作量，且能够自动发现新的入侵行为； 利用数据挖掘、机器学习、人工免疫原理等智能方法作为入侵检测的数据分析技 术，可以从海量的安全事件中提取出尽可能多的隐藏安全信息，抽象出有利于进 行判断和比较分析的与安全相关的普遍特征，从而发现未知的入侵行为。所以， 利用数据挖掘技术，监测访问日志文件，对异常数据进行分析，检测和预防，对 网络服务安全具有重要意义。将数据挖掘技术应用于网络安全检测已经成为当前 的一个研究热点。 1 2 国内外研究现状 任何技术的产生总是有它的产生背景和技术背景的。数据挖掘技术的提出和 被普遍接受，是由于计算机及其相关技术的发展为其提供了研究和应用的技术基 础。由于数据库、数据仓库和i n t e r n e t 等信息技术大力发展、计算机性能的提 高和先进的体系结构的发展、统计学和人工智能等方法在数据分析中的研究和应 用，数据挖掘技术由此而产生、发展。数据库技术从2 0 世纪8 0 年代开始，已经 得到广泛的普及和应用；i n t e r n e t 的发展普及更为人们提供了丰富的数据源， 西北师蒋大学臻士论文基于w e b 服务安全的异常数据挖l 算法研究 而w e b 服务则是i n t e r n e t 上主要的服务方式。从数据库中发现知识( k d d ) 一词 首次出现在1 9 8 9 年举行的第十一届国际联合人工智能学术会议上。到目前为止， 由美国人工智能协会主办的k d d 国际研讨会的规模，由原来的专题讨论会发展到 国际学术大会，研究重点也逐渐从发现方法转向系统应用，注重多种发现策略和 技术的集成，以及多种学科之问的相互渗透。经过十几年的研究和实践，数据挖 掘技术已经吸收了许多学科的最新研究成果，形成了独具特色的研究分支。数据 挖掘技术同其它新技术发展历程一样，也经过了概念提出、概念接受、广泛研究 和探索、逐步应用和大量应用等阶段。但从目前来看，数据挖掘的研究仍然处于 广泛研究和探索阶段。 目前，国外在数据挖掘方面的发展趋势及研究主要有：对知识发现方法的进 一步研究，如近年来注重对分析方法的研究和提高；统计学回归法在k d d 中的应 用；k d d 与数据库的紧密结合；对网络信息挖掘方法的研究等。国外很多计算机 公司非常重视数据挖掘的开发应用，i b m 和微软都成立了相应的研究中心，一些 公司的相关软件也开始在国内销售，如p l a t i n u m 、b o 以及i b m 。 国内从事数据挖掘研究的人员主要在大学，也有部分在研究所或公司。所涉 及的研究领域很多，一般集中于学习算法韵研究、数据挖掘的实际应用以及有关 数据挖掘理论方面的研究。目前进行的大多数研究项目是由政府资助进行的，如 国家自然科学基金、8 6 3 计划等，在一些公司开发的针对行业的综合信息管理系 统中，数据研判、预警分析也得到了一些应用。可以看出，数据挖掘的研究和应 用受到了学术界、实业界和政府部门的越来越多的重视。 网络安全问题一直是一个永恒的话题。随着计算机和互联网的发展，w e b 服 务在现代社会扮演着越来越关键的角色，而w e b 服务安全正成为逐渐严重的问题， 受到人们的广泛关注，入侵检测技术近年来也成为网络安全研究热点之一，多种 基于数据挖掘的入侵检测技术也由此而产生。其中针对在数据库系统和系统服务 日志中检测恶意事务提出了许多数据挖掘方法，许多试验证明该方法可以有效的 检测到恶意事务。现有的大多数实用入侵检测系统通常是将收集到的审计数据与 已有的攻击模式数据库进行比较，从而发现违背安全策略的行为。这种模式匹配 的方法对已知的入侵检测效率很高，但对于一些未知的或者现有的入侵方法的变 种却无法准确的检测。由于大部分入侵属于异常事务，所以利用数据挖掘技术对 审计数据加以分析，总结出一些正常模式，对异常模式进行分析，进行异常检测， 将有助于提高入侵检测系统的检测准确性和完备性。 西北师范大学磺士论文基于w i r e 服务安全的异常薮据挖掘算法研究 1 3 论文主要研究内容与体系结构 1 3 1 论文主要研究内容 本文主要做了以下几个方面的工作： ( 1 ) 在对数据挖掘技术和w e b 服务安全问题进行研究的基础上，分析讨论了 异常数据挖掘在w e b 服务安全中的具体应用； ( 2 ) 研究了异常数据挖掘技术并给出基于距离的各种异常数据挖掘算法和基 于距离和的异常数据挖掘算法，分析并讨论了几种算法的异同点； ( 3 ) 研究讨论了基于w e b 服务器日志文件的异常数据挖掘，并做出异常数据 分析和算法讨论，最后进行实验验证。 1 3 2 论文体系结构 本文共分六章。各章节的内容概述如下： 第一章为绪论介绍了本文的研究背景以及国内外对数据挖掘技术的研究现 状，并介绍本文所做相关工作： 第二章为理论基础。介绍了本文所涉及到的相关技术： 第三章为异常数据挖掘算法研究。详细讨论了异常数据挖掘算法中基于距离 的算法并做比较； 第四章为w e b 数据挖掘和w e b 日志挖掘。主要介绍了w e b 数据挖掘和w e b 日志挖掘的相关技术，为第五章的实验做铺垫； 第五章为基于w e b 服务器日志文件的异常数据挖掘。使用w e b 服务器日志文 件进行基于距离和的异常数据分析和算法讨论并实现； 第六章为结束语。对论文所做的工作进行总结，并提出目前的不足以及对日 后的工作及前景进行展望。 1 4 本章小结 本章主要讨论了数据挖掘技术以及w e b 服务安全的国内外发展状况，并给出 本文组织结构。 西t 范丈学爵士论文基于w e b 晨务安全的异常戴謦陀算法研究 2 1 数据挖掘 第二章理论基础 2 1 1 基本概念 数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、 随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息 和知识的过程。还有很多和这一术语相近似的术语如从数据库中发现知识 ( k i ) d ) 、数据分析、数据融合以及决策支持等。人们把原始数据看作是形成知识 的源泉，就像从矿石中采矿一样。原始数据可以是结构化的，如关系型数据库中 的数据，也可以是半结构化的，如文本、图形、图像数据，甚至是分布在网络上 的异构型数据。发现知识的方法可以是数学的，也可以是非数学的；可以是演绎 的，也可以是归纳的。发现了的知识可以被用于信息管理，查询优化、决策支持、 过程控制等，还可以用于数据自身的维护。因此，数据挖掘是- - f 3 广义的交叉学 科，它汇聚了不同领域的研究者，尤其是数据库、人工智能、数理统计、可视化、 并行计算等方面的学者和工程技术人员。 特别要指出的是，数据挖掘技术从一开始就是面向应用的。它不仅是面向特 定数据库的简单检索查询调用，而且要对这些数据进行微观、中观乃至宏观的统 计、分析、综合和推理，以指导实际问题的求解，企图发现事件问的相互关联， 甚至利用已有的数据对未来的活动进行预测等。 2 1 2 数据挖掘过程 数据挖掘通常也被称为“从大型数据库提取有效、可信和可行信息的过 程”。换句话说，数据挖掘派生数据中存在的模式和趋势。这些模式和趋势可以 被收集在一起并定义为挖掘模型。挖掘模型可以应用于特定的业务方案，例如： 预测销售额； 向特定客户发送邮件； 确定可能需要措售的产品； 查找客户将产品放入购物车的顺序序列。 一个重要的概念就是生成挖掘模型是大型过程的一部分，此过程包括从定义 模型要解决的基本问题到将模型部署到工作环境的所有事情。此过程可以使用下 列六个基本步骤进行定义，如图21 说明过程中每个步骤之间的关系。 西北师范大学焉士论文羹于w 衄r 曩务安全的异常藏据挖l 算法研究 圈2 - 1 挖嗣攥垂基本步 ( 1 ) 定义问题 数据挖掘过程的第一步就是明确定义业务问题。该步骤包括分析业务需求、 定义问题的范围、定义计算模型所使用的度量、以及定义数据挖掘项目的最终目 标。这些任务可以转换为下列问题： 您在查找什么? 您要尝试预测数据集的哪个属性? 您要尝试找到什么类型的关系? 您要通过数据挖掘模型进行预测，还是仅仅查找受关注的模式和关联? 如何分发数据? 列如何关联，或者如果有多个表，则表如何关联? 若要回答这些问题，可能必须进行数据可用性研究，必须调查业务用户对可 用数据的需求。如果数据不支持用户的需求，则还必须重新定义项目。 ( 2 ) 准备数据 数据挖掘过程的第二步就是合并和清除定义问题步骤中标识的数据。步骤内 容包括转换到自动执行数据清除和合并。 在此过程中，数据可以分散在公司的各个部门并以不同的格式存储，或者可 能包含缺陷项或缺少项之类的不一致性。例如，数据可能显示客户在其出生日期 之前购买产品，或者客户在距离她家2 ，0 0 0 英里的商店定期购物。在开始生成 模型之前，必须纠正这些问题。通常，您使用的是一个非常大的数据集，并且无 法仔细查看每个事务。因此，必须使用某种自动化的形式来浏览数据并找到这些 不一致。 西t l ；t i l i 范大学硕士论文基于啪曩务安全的异常羹据挖l 算法研究 ( 3 ) 浏览数据 数据挖掘过程的第三步就是浏览已准备的数据。必须了解数据，以便在创建 模型时做出正确的决策。浏览技术包括计算最大值和最小值、计算平均偏差和标 准偏差、以及查看数据的分布。浏览完数据之后，便可确定数据集是否包含缺陷 数据，然后制订纠正这些问题的策略。 ( 4 ) 生成模型 数据挖掘过程的第四步就是生成挖掘模型。在生成模型之前，必须随机将已 准备的数据分离到单独的定型数据集和测试数据集。使用定型数据集生成模型， 并通过创建预测查询来使用测试数据集测试模型的准确性。例如可以使用百分比 抽样转换来拆分数据集。 使用从浏览数据步骤中获得的知识来帮助定义和创建挖掘模型。模型通常包 含多个输入列、一个标识列以及一个可预测列。然后可使用数据挖掘扩展插件语 言或数据挖掘向导，在新的模型内定义这些列。 定义完挖掘模型的结构之后，需要对其进行处理，使用说明模型的模式来填 充空结构。这称为“定型”模型。模式通过利用数学算法计算原始数据而得。挖 掘模型由一个数据挖掘结构对象、一个数据挖掘模型对象以及一种数据挖掘算法 定义 ( 5 ) 浏览和验证模型 数据挖掘过程的第五步就是浏览已经生成的模型并测试其有效性。我们不希 望在事先没有测试模型性能的情况下将模型部署到生产环境。同样，如果已经创 建了数个模型，并且必须确定性能最佳的模型。如果在创建模型步骤中创建的所 有模型都无法正常工作，则必须返回到此过程的上一个步骤，重新定义问题或重 新调查原始数据集中的数据。 可以使用数据挖掘设计器内的查看器来浏览算法发现的趋势和模式。还可以 使用该设计器中的工具( 如，提升图和分类矩阵) 来测试模型创建预测的性能。 这些工具要求使用在模型生成步骤中从原始数据集内分离的测试数据。 ( 6 ) 部署和更新模型 数据挖掘过程的最后一步就是将性能最佳的模型部署到生产环境。当生产环 境中部署了挖掘模型之后，便可根据需求执行许多任务。例如： 使用模型创建预测，然后可以使用这些预测做出业务决策； 直接将数据挖掘功能嵌入到应用程序； 西北舜菇大学曩士论文基于w e b 服务安全的异常数据挖算法研究 创建一个包，在这个包中，挖掘模型用于自动将传入数据分离到多个表 中： 创建可让用户直接对现有挖掘模型进行查询的报表。 更新模型是部署策略的一部分。随着单位传入的数据不断增多，必须重新处 理模型，以便提高效用。 总之，数据挖掘过程需要多次的循环反复，才有可能达到预期的效果。 2 1 3 数据挖掘知识分类 数据挖掘所能发现的知识有如下几种：广义型知识，反映同类事物共同性质 的知识；特征型知识，反映事物各方面的特征知识；差异型知识，反映不同事物 之间属性差别的知识；关联型知识，反映事物之间依赖或关联的知识；预测型知 识，根据历史的和当前的数据推测未来数据；偏离型知识，揭示事物偏离常规的 异常现象。所有这些知识都可以在不同的概念层次上被发现，随着概念树的提升， 从微观到中观再到宏观，以满足不同用户、不同层次决策的需要。例如，从一家 超市的数据仓库中，可以发现的一条典型关联规则可能是“买面包和黄油的顾客 十有八九也买牛奶”，也可能是“买食品的顾客几乎都用信用卡”，这种规则对于 商家开发和实施客户化的销售计划和策略是非常有用的。至于发现工具和方法， 常用的有分类、聚类、模式识别、可视化、决策树、遗传算法、不确定性处理等。 数据挖掘的目的是发现知识，知识要通过一定的模式给出。根据数据挖掘所 能发现的知识可以将数据挖掘分为嘲。1 ： ( 1 ) 广义知识挖掘 广义知识( g e n e r a l i z a t i o n ) 是指描述类别特征的概括性知识。一般在数据 源中存放的是细节性数据，而人们有时希望能从较高层次的视图上处理或观察这 些数据，通过数据进行不同层次上的泛化来寻找数据所蕴涵的概念或逻辑，以适 应数据分析的要求。数据挖掘的目的之一就是根据这些数据的微观特性发现有普 遍性的、更高层次概念的中观和宏观的知识。因此，这类数据挖掘系统是对数据 所蕴涵的概念特征信息、汇总信息和比较信息等的概括、精炼和抽象。广义知识 挖掘通常采用概念描述方法、多维数据分析方法和概念分层技术。被挖掘出的广 义知识可以结合可视化技术以直观的图表形式展示给用户，还可以作为其它应用 的基础知识。 ( 2 ) 关联知识挖掘 关联知识( a s s o c i a t i o n ) 反映一个事件和其他事件之间依赖或关联。数据 西囊师氟大学焉士论文 基于w e b 曩务安全的异常教据挖算法研究 库中的数据关联是现实世界中事物联系的表现。数据库作为一种结构化的数据组 织形式，一方面利用其数据模型体现数据间的关联，除此之外，大部分数据与数 据之间的关联是隐藏的，无法从表面上体现出来。所以，关联知识挖掘的主要目 的就是找出数据库中隐藏的关联信息。关联知识挖掘的最常用方法是关联规则挖 掘。其中一个典型例子就是购物篮分析“1 。该过程通过发现顾客放入其购物篮中 不同商品之间的联系，分析顾客的购买习惯。通过了解哪些商品频繁地被顾客同 时购买，这种关联的发现可以帮助零售商制定营销策略。 ( 3 ) 类知识挖掘 类知识( c l a s s ) 刻画了一类事物，这类事物具有某种意义上的共同特征， 并明显和不同类事物相区别。类知识包括数据挖掘的分类和聚类两类数据挖掘应 用所对应的知识。分类是一种重要的数据挖掘技术。分类的目的是根据数据集的 特点构造一个分类函数或分类模型( 也常常称作分类器) ，该模型能把未知类别 的样本映射到给定类别中的某一个“”；聚类是把一组个体按照相似性归成若干类 别，它的目的是使得属于同一类别的个体之间的差别尽可能的小，而不同类别上 的个体间的差别尽可能大。聚类与分类的区别在于分类是有指导的学习，即模型 的学习在被告知每个训练样本属于哪个类的指导下进行的：而聚类是无指导的学 习，即每个训练样本的类标识是未知的。分类技术主要有决策树、贝叶斯分类、 神经网络、遗传算法与进化理论、类比学习、粗糙集和模糊集等；聚类技术主要 采用基于划分、层次、密度、网格和模型五大类算法。 ( 4 ) 预测型知识挖掘 预测型知识( p r e d i c t i o n ) 是指由历史的和当前的数据产生的并能推测未来 数据趋势的知识。也可以认为是以时间为关键属性的关联知识。从预测的主要功 能上看，主要是对未来数据的概念分类和趋势输出。用预测法预测连续值为预测， 即利用历史数据产生并输出连续趋势曲线。预测型知识挖掘主要采用经典的统计 方法、神经网络和机器学习等技术。 ( 5 ) 特异型知识挖掘 特异型知识( e x c e p t i o n ) 是源数据中所蕴涵的极端特例或明显区别于其它 数据的知识描述，它揭示了事物偏离常规的异常规律，也称异常数据挖掘。例如， 在w e b 站点发现那些区别于正常登录行为的用户特点可以防止非法入侵，银行、 电信等行业的商业欺诈行为预防等，都是异常数据挖掘研究的主要内容，这也是 本章要讨论的重点。 基于岫厦务安全的异常数据挖蠢算法研究 2 2 异常数据挖掘 在数据挖掘的过程中，数据库中可能包含一些数据对象，它们与数据的一般 行为或模型不一致，这些数据对象被称为异常点，大部分数据挖掘方法将异常点 视为噪声或异常而丢弃，然而在一些应用中，如保险欺诈、违规交易、信用卡欺 诈等检验中，罕见的事件可能比正常出现的事件更有意义。对异常点的查找过程 称为异常数据挖掘，它是数据挖掘技术中的一种。 异常数据挖掘可以被形式化的描述“”：给定一个含有n 个数据点或对象的集 合及预期的异常点数目k ，发现集合中与其余数据相比显著相异的、异常的或不 一致的前k 个对象。异常点挖掘问题可以被看作两个子问题，即在给定的数据集 合中定义什么样的数据可以被认为是不一致的，找到一个有效的方法来挖掘这些 异常点集。 通俗地将，异常数据挖掘是指在数据集_ 中标识出异常点的过程。异常数据挖 掘有多种方法，包括异常点检测、序列异常分析和异常规则发现等。 2 2 1 异常点 异常点定义有多种，但具有代表性的是v b a r n e t t “”在统计学研究领域中给 出的定义。一个异常点是这样的数据点，基于某种度量而言，该数据点与数据集 中的其他数据有着显著的不同“”。除此之外，许多研究者根据特定的研究背景， 给出了不同的异常点的定义，尽管它们不尽相同，但都反映了异常点的特点：首 先，异常点看起来是令人惊讶的，它是异常点的关键特征之一；其次，异常点是 一个相对的定义。如果初始分布模型的假设不同，会产生不同的结论；最后，异 常点有较强主观性，几乎所有研究者进行异常点挖掘研究时都定义特有的挖掘背 景伽。异常点出现的原因很多，可总结为3 类： ( 1 ) 数据变量固有变化引起，即观测值在样本总体中发生了变化，这种变化 是样本总体自然发生的特征，是不可控的，并且从侧面反映了数据集的数据分布 特征： ( 2 ) 测量错误引起，由于测量仪器的一些缺陷导致部分测量值成为异常点； ( 3 ) 执行错误弓l 起，如黑客网络入侵、系统机械故障的出现导致数据集出现 异常点。 2 2 2 异常点分类 根据对异常点最终处理方式的不同，可以将异常点分为以下三类：“” 西北师范大学确士论文基于w e b 晨务安全的异常羲鬻捆算法研究 ( 1 ) 应剔除的异常点 有些数据可能是在统计时度量或执行错误所得到的，例如，在人口统计调查 的数据中，一个人的年龄为一1 0 0 岁，这一异常值可能是统计时的笔误所致，发 现后就应该从数据库中剔除。 随着计算机的普及，我们在进行某项统计工作时，一般都是利用计算机来进 行处理，而在进行统计数据的录入时，应特别小心，不要将数据输错，但一旦输 错后，对输错后的异常数据的挖掘也非常必要，否则势必会影响统计结果的质量。 ( 2 ) 应特别处理的异常点 有些异常数据并不是任何执行错误所致，而是固有的数据变异性的结果。例 如，我国在1 9 7 8 1 9 8 8 年问的经济增长率平均在1 0 左右，而在1 9 8 9 和1 9 9 0 年 只有4 1 和3 8 ，从1 9 9 1 年至今也都在7 以上，因此1 9 8 9 和1 9 9 0 年的经济 增长率可以认为是异常数据，而这一异常数据并非任何统计错误所致。对于这一 类异常数据不能简单地尉除，否则可能导致重要的隐藏信息的丢失，当然 也不应该与正常数据一样对待，因为这些异常数据出现的频率或概率还是比较小 的，因此合理的处理方法是根据它们出现的频率或概率进行加权，降低它对正 常情况反映的不利影响。 ( 3 ) 应重视的异常点 有些异常数据是非常稀有和有价值的数据。例如在培养运动员时，如果发现 一个1 3 岁的少年身高已达2 米，这种异常情况应该引起体育部门的重视，在篮 球、排球等运动项目中就可以重点培养这种“正常”的异常儿童。 在其它方面像发现保险欺诈、违规交易、信用卡诈骗等应用中，也都是查找 这些有实际意义的异常数据，都称之为应重视的异常点。 此外，根据不同分类角度，异常点还可以分为其它多种类别，例如按照数据 范围分类，可以全局异常点和局部异常点；按照变量数量分类，可以将异常点分 为单变量异常点和多变量异常点；尽管该分类不很完备，但侧面反映了数据集中 异常点类型的多样性。因此，有效发现数据集中的异常点并不是一件容易的工作， 需要采用有效的策略和算法。 2 2 3 异常点检测 数据集中可能包含一些数据对象，它们与数据的一般行为或模型不一致，这 些数据对象是异常点或孤立点。异常点属于特异型知识，是指不符合数据的一般 模型的数据，它是数据中包含的一些与其它数据的一般行为或模型不一致的数据 西北师范大学碗士论文基于期皤曩务安全的异常教藉耙夤l 女簟f 宄 对象。在挖掘正常类知识时，通常总是把它们作为噪声或异常来处理，然而，在 一些应用中可以作为某类应用( 如信用欺诈、入侵检测等) 提供有用信息时，就 为数据挖掘提供了一个新的研究课题，即异常点检测，在一些应用中，罕见的事 件可能比正常出现的那些事件更有价值，异常点检测即是对异常点挖掘( o u t l i e r m i n i n g ) 。目前异常点检测作为网络非法入侵、信用卡欺诈等安全检测手段成为 很有应用价值的研究分支。 ( 1 ) 基于统计的异常点检测 统计数据挖掘技术是数据挖掘技术中较为成熟的一种，最简单的一维样本异 常点检测方法是应用统计学。统计的方法对给定的数据集合假设了一个分布或概 率模型，然后根据模型采用不一致性检验来确定异常点。该检验要求知道数据集 参数( 例如假设的数据分布) 、分布参数( 例如均值和方差) 和预期的异常点的 数目。假定值的分布已知，必须找出基本的统计参数，如均值和方差。在这些值 和异常点期望( 预测) 数目的基础上，建立方差函数阈值是可行的，所有阈值之 外的样本都是可能的异常点。 ( z ) 基于距离的异常点检测 数据中的异常点可用聚类检测出来。聚类将类似的值组织成群或“聚类”， 直观的看，落在聚类集合之外的值被视为异常点。基于距离的异常点检测是异常 数据检测的第二种方法，它可以排除统计方法的一些局限性。两者最重要的区别 是这种方法可用于多维样本，而统计分析仅仅用于一维或个别的几维样本。这种 算法的基本复杂性在于估计n 维数据集中所有样本间的测量距离。如果样本s 中至少有一部分数据量为p 的样本到s 。的距离比d 大，那么样本s 。是数据集s 中的一个异常点。换句话说，基于距离的异常点是那些没有足够相邻点的样本， 相邻点通过样本间的多维距离来定义。 基于距离的异常点检测算法可以在未知数据分布状态下对多维数据进行分 析。挖掘基于距离的异常点的常用算法有基于索引的算法、嵌套一循环算法和基 于单元的算法等。 ( 3 ) 基于偏离的异常点检测 基于偏差的技术是第三种异常点检测方法。基于偏差的异常点检测，它通过 检查一组对象的主要特征来确定异常点，如果一个对象与给出的描述发生“偏 离”，则认为该对象是异常点，它定义样本集的基本特征，所有违背这些特征的 样本都是异常样本。这类技术不采用统计检验或基于距离的度量值来确定异常对 西北卿筢大学焉士论文基于嘞曩务安全的异常数据挖曩算法研究 象，而是通过检查组对象的主要特征来确定异常点。基于偏差的异常点探测的 两种技术是：顺序地比较一个集合中的对象和采用o l a p 数据立方体。 2 2 4 序列异常分析 序列模式分析同样也是试图找出数据之间的联系。但它的侧重点在于分析数 据之间前后因果关系，因此对数据往往要求引入时间属性。序列模式分析非常适 于寻找事物的发生趋势或重复性模式。一个数据集中往往包含一些特别的数据， 它们数据的行为和模式与一般的数据不同，这些数据对象称为“异常”。对“异 常”数据的分析称为“异常分析”。异常序列( e x c e p t i o n a ls e q u e n c e ) 分析是 指在一系列行为或事件对应的序列中发现明显不符合一般规律的特异型知识。发 现序列异常的规律对于银行、电信等行业的商业欺诈行为预防以及网络安全检测 等都是极具吸引力的，它在欺诈甄别、网络入侵检测等邻域有着广泛的应用。 2 2 5 异常规则发现 关联知识( a s s o c i a t i o n ) 反映一个事物和其它事件之问的依赖或关联，数 据之间的关联是复杂的，一些关联可以表现在数据库的数据模型中，但大部分是 隐藏的。关联知识的挖掘就是找出这些隐藏的关联信息，这些关联并不总是事先 知道的，而是通过数据库中的关联分析获得的。关联规则挖掘是关联知识发现的 最常用的方法，为了发现有意义的关联规则，给出了两个阈值：最小支持度和最 小可信度，关联规则挖掘问题就是通过用户指定最小支持度和最小可信度来寻找 强关联规则的过程。虽然典型的关联规则中，总是重视那些高支持度和可信度的 规则，因此对那些虽然具有低支持度但可能很有价值的规则，即异常规则，无法 产生和评价。因此，异常规则的挖掘需要突破传统关联规则的框架，探讨新方法。 2 3w e b 服务安全 2 3 1w e b 服务 w e b 服务，从外部使用者的角度而言，就是一种部署在w e b 上的对象组件： 即通过一定的范例，开发人员只要建立一种标准化的接口，就可以通过i n t e r n e t 对各种各样的应用服务进行拼装和组合，从而形成新的应用服务。它具有完好的 封装性，松散耦合，使用协约的规范性，使用标准协议规范和高度可集成能力。 w e b 服务体系结构如图2 - 2 所示4 1 ： w e b 服务体系由服务请求者、服务代理者和服务提供者组成： ( 1 ) 服务提供者在服务代理者处注册以配置和发布服务； 西北师花大擘焉士论文基于w e b 瑕务安全的异常羹羹挖i 淫研究 ( 2 ) 服务请求者在服务代理者处查找被发布服务登记记录来找到服务； ( 3 ) 服务请求者绑定服务提供者并使用可用服务。 田2 - 2w e b 服务体系结构 2 3 2w e b 服务安全 w e b 服务安全问题的关键不在于服务传输的连接，而在于服务内容，即要确 保数据完整性和保密性，这是通信安全中很重要的一个方面。例如一个证券交易 商通过手机来了解股票价格的变化，则必须保证股票信息在从服务器发出，经过 多个中介体后安全完整地到达用户端。 2 3 3 异常数据挖掘在w e b 服务安全中的应用 异常数据挖掘有着广泛的应用。虽然异常点不符合数据的一般规律，与数据 的其他部分不同或不一致，是数据集中远远偏离其他对象的那些小比例对象，但 是在一些应用中，例外的检测能为我们提供比较重要的信息，使我们发现一些真 实而又出乎预料的知识。正如一条一个人认为是垃圾的信息对另一个人却是如获 至宝。有些异常点是实际生活中反常行为的写照。用距离的观点来看，异常点是 那些离密度较高的大部分点较远的点。它的一般应用如下：电信和信用卡欺骗、 贷款审批、药物研究、气象预报、金融领域、客户分类和网络入侵检测等。例如， 探测不寻常的信用卡使用或电信服务，在市场分析中可用于确定极低或极高收入 的客户的消费行为；还有，税务稽查机关在选案的过程中，可先从数据仓库中根 据企业的规模、行业、地区等纬度查找出若干企业，将这些数据用数据挖掘软件 查找纳税额明显偏低的企业，再将这些企业作为有逃税嫌疑的企业进行稽查。目 前根据异常点存在的不同假设，开发了许多异常点挖掘算法，包括：基于统计学 的方法、基于距离的方法、基于偏离的方法、高维数据的异常点探测、基于规财 的分类异常点挖掘方法和基于密度的异常点挖掘方法等嗍。 日志是系统正常运行的重要保障，它会告诉我们系统发生了什么和什么没有 发生。然而，由于日志记录增加得太快了，铺天盖地的日志使系统管理员茫然无 麓t 一越大学焉士论文基于w e b 服务安全的异常教据挖掘算法研究 措，最终使日志成为浪费大量磁盘空间的垃圾。虽然日志具有无可替代的价值， 但不幸的是它们经常被忽略，因为系统管理员在并不充裕的时间里难以查看大量 的信息。标准w e b 日志提供系统管理员所需要的信息，它记录了我们感兴趣的许 多操作：对于入侵者来说，他要做的第一件事就是清除入侵的痕迹，而一旦日志 被修改，就无法追查到攻击的情况。因此，只要我们能很好地保护和检测好日志 文件，再通过数据挖掘工具，及时分析和检查，就能很好地保证w e b 服务安全。 本论文中重点讨论基于w e b 服务器日志文件的异常数据挖掘。 2 4 本章小结 本章从理论的角度介绍了数据挖掘的基本概念、数据挖掘过程以及数据挖掘 的知识分类，在此基础上引入了异常数据挖掘的概念。异常数据挖掘是指在数据 集中标识出异常点的过程，那么对异常点的识别与检测则成了本文要讨论的重 点，根据现有研究理论，着重介绍了使用统计、距离、偏离技术进行异常点检测。 最后讨论了w e b 服务、w e b 服务安全等基本概念，以及异常数据挖掘在w e b 服务 安全中的应用 西北师范大学磺士论文基于w e b 曩务安全的异常鼓舞杞一算法研究 第三章异常数据挖掘算法研究 3 1 异常数据挖掘问题的描述 3 1 1 基本概念 在数据挖掘过程中，常常存在与数据模型或数据一般规律不符合的数据对 象，这类与其他数据不一致或非常不同的数据对象就称为异常数据。这些异常数 据可能是由于测量误差、输入错误或者运行错误而造成的，也可能是由于数据内 在特性而造成的，这些数据有时也可能是具有特殊意义的数据。因此，异常数据 检测和分析是一个有意义的数据挖掘任务，这一挖掘工作就称为异常数据挖掘。 异常数据挖掘是指在数据集中标识出异常点的过程。发现异常点后，利用许 多数据挖掘算法都可以删除它们或者按不同方式处理，其中包括使用统计技术、 聚类技术、距离测度技术等。但是由于现实世界数据集不一定服从简单的数据分 布，并且大多数统计检验都假设使用单属性数值，而现实世界数据集中的数据都 是多属性的，所以使用统计技术对于真实的数据是不适用的。因此本章主要讨论 基于距离的算法，并且对所提出的算法进行比较。 3 1 2 异常数据挖掘的过程 简单地将，异常挖掘有两类基本过程： ( 1 ) 批过程。或者所有被怀疑的对象都被视为异常，或者都被视为一致数据 而被接受； ( 2 ) 连续的过程。该过程的一个例子是内部出局过程。它的主要思想是，首 先检查最不可能是异常的对象，如果它是异常，那么所有更极端的值都被认为是 异常；否则，检验下一个极端的对象，依此类推。 3 2 异常数据挖掘算法研究 3 2 1 孤立点的描述 虽然聚类分析和异常点检测是异常挖掘中一个最重要的方法，但是异常并不 等同于孤立点。一方面，一些正常的数据( 或行为) 也可能表现为孤立点，这样的 孤立点对于用户是没有意义的；另一方面，处于聚类之中的数据也有可能是异常 数据，特别是对于一些有延续性的数据来说，静态的聚类可能很难让某些异常数 西北师范大学硬士论文基于哪羼务安全的异常羲据挖舞鹾研究 据表现为孤立点，还需要结合领域专家知识和其它数据挖掘方法进行进一步的挖 掘，以发现这些隐藏的异常信息。 3 2 2 挖掘孤立点的方法 目前根据孤立点存在的不同假设，开发了许多孤立点挖掘算法，有以下几类 孤立点挖掘方法：即基于统计学的方法、基于距离的方法、基于偏离的方法、高 维数据的孤立点探测、基于规则的分类孤立点挖掘方法和基于密度的孤立点挖掘 方法。 以上每类孤立点挖掘方法都有其特别适用的范围，也有一定的缺陷和限制， 在这里介绍前三类。 l 基于统计的方法 假设给定的数据集服从一个随机分布( 如正态分布) ，用不一致性检验识别孤 立点。在大多数情况下，不能知道数据的具体分布，而且现实数据也往往不符合 任何一种理想状态的数学分布。另外即使在低维( 一维或二维) 时的数据分布已 知，在高维情况下，估计数据点的分布也是极其困难的。 最简单的一维样本孤立点检测方法是应用统计学。假定值的分布己知，必须 找出基本的统计参数，如均值和方差。在这些值和孤立点期望( 预测) 数目的基础 上，建立方差函数阈值是可行的。所有阈值之外的样本都是可能的孤立点。这种 简单方法的主要问题在于对数据分布的预先假设。 例如，所给的数据集是某地区随机选取的开始上学的2 0 名儿童的年龄，具 体的年龄特征如下： 年龄= 6 ，7 ，6 ，8 ，9 ，1 0 ，8 ，i i ，7 ，9 ，1 2 ，7 ，1 1 ，8 ，1 3 ，7 ，8 1 4 ，9 ，1 2 那么，相应的统计参数是：均值= 9 1 ；标准差= 2 3 。 如果选择数据分布的阈值为：阈值= 均值2 标准差。 故