（计算机应用技术专业论文）基于数据挖掘的网络异常检测技术的研究和实现.pdf

南京邮电大学硕士研究生学位论文基于数据挖掘的网络异常检测技术的研究和实现 摘要 随着网络技术的进步，网络应用得到了巨大的发展，已经渗透到人们的日常生活中。 t c p i p 网络体系结构与协议的巨大成功来源于其开放性和简单性，但也正是由于这种开放 性和简单性使得互联网成为一种高度异构、开放的复杂系统，带来了不少安全以及管理上 的问题。目前网络应用的多样性、网络结构的复杂性等都给网络管理带来了巨大的挑战。 传统的网络管理过多依赖于专家的知识和经验，对于网络中的突发情况以及它们之间 的联系则考虑的较少。例如，大多数的商业产品如o p m a n a g e r 在日志处理方面只考虑到告 警处理，对于日志告警之间的联系等深层次的知识则没有进行分析。这使得网络中产生的 大量数据没有被充分利用，很多对网络管理有用的知识也没有被挖掘出来。 如何从可获得的网络数据中发现存在的网络异常，并以易于理解的形式提供给管理者 是当前网络管理面临的一个难题。数据挖掘技术提供了一种数据分析方法，它能从大量的 有噪声的数据中提取出用户感兴趣的部分，并呈现给用户。本文将数据挖掘技术与网络异 常检测结合，提出了一种基于数据挖掘的异常检测模型。 文章在该模型的基础上，从日志分析和流量分析方面将数据挖掘技术运用到实际中。 在日志分析方面，传统的网络管理只涉及到故障告警匹配等方面，且日志分析多为定期审 查方式。针对上述方式的不足，文章提出了基于f p g r o w t h 的增量日志挖掘算法并将其应 用到日志分析中，对不断产生的日志进行实时分析，挖掘日志内部的联系。另外，将数据 挖掘中的聚类分析方法运用到流量异常检测中，结合流量统计技术，管理员能够更加详细 地追踪到异常的原因。最后在l i n u x 平台下实现了增量日志挖掘算法和基于聚类的流量异常 检测算法，并在实际网络环境中进行了测试，给出了实验结果分析。 关键词：数据挖掘；日志分析；聚类分析；网络异常检测 a b s t r a c t w i t ht h ed e v e l o p m e n to fn e t w o r kt e c h n o l o g ya n dn e t w o r k a p p l i c a t i o n ，n e t w o r ki sap a r to f o u rl i f e t h es u c c e s so ft c p i pp r o t o c o li sd u et oi t so p e na n ds i m p l i c i t y h o w e v e r , i n t e m e t b e c o m e sah e t e r o g e n e o u sa n dc o m p l e xs y s t e ma n dr e s u l t si nm a n yp r o b l e m so fs e c u r i t ya n d m a n a g e m e n t t o d a y , t h ed i v e r s ea p p l i c a t i o n sa n dc o m p l e xn e t w o r ks t r u c t u r eb r i n gal o to f c h a l l e n g e st om a n a g e m e n t t h et r a d i t i o n a ln e t w o r km a n a g e m e n tr e l a y so nt h ek n o w l e d g ea n de x p e r i e n c eo fe x p e r t s ， a n dc o n s i d e rl i t t e ra b o u tt h eb u r s to fs i t u a t i o na n dr e l a t i o no fn e t w o r k f o re x a m p l e ，m o s t c o m m e r c i a lp r o d u c t sl i k e o p m a n a g e r j u s tc o n s i d e rt h ea l a r mp r o c e s si nl o ga n a l y s i s ，a n dd o n t a n a l y z et h ek n o w l e d g el i k et h er e l a t i o n sb e t w e e nl o ga l a r m s t h e r e f o r e ，al o to fd a t ai nn e t w o r k c a nn o tb em a d eu s eo f , a n dm u c hk n o w l e d g ew h i c hi su s e f u lt on e t w o r k m a n a g e m e n tc a nn o tb e d i s c o v e r e d t h e r ei sap r o b l e mt h a th o wt od i s c o v e rt h en e t w o r ka n o m a l yf r o ma v a i l a b l ed a t a , a n dg e tt h e r e s u l t su n d e r s t o o db yn e t w o r km a n a g e r d a t am i n i n gp r o v i d e sad a t aa n a l y s i sm e t h o df o r r e s e a r c h e r s t h ei n t e r e s t i n gr e s u l t sc a nb ee x t r a c t e df r o mal o to fn o i s yd a t a , a n ds h o w e dt ot h e u s e r i nt h i st h e s i s ，a na n o m a l yd e t e c t i o nm o d e li sp r o p o s e dw i t ht h ec o m b i n a t i o no fd a t am i n i n g a n dn e t w o r ka n o m a l yd e t e c t i o nt e c h n o l o g y b a s e do nt h em o d e li nt h i st h e s i s ，d a t am i n i n gt e c h n o l o g yi sa p p l i e dt ot h es y s t e mf r o ml o g a n a l y s i sa n dt r a f f i ca n a l y s i s i nt h el o ga n a l y s i s ，b a s e do nf p - g r o w t h , i n c r e m e n ta l g o r i t h mi s p r o p o s e dt om a k eu pf o rt h es h o r t c o m i n g so ft h ew a yo ft r a d i t i o n a lp e r i o d i ca n a l y s i sa n di sa b l e t ok e e pr e a l t i m el o gm i n i n g c o m b i n e dw i t ht h et r a f f i cs t a t i s t i c a lt e c h n i q u e s ，c l u s t e r i n ga n a l y s i s i sa p p l i e dt ot r a f f i ca n o m a l yd e t e c t i o n t h ei n c r e m e n tl o gm i n i n ga l g o r i t h ma n da n o m a l yt r a f f i c d e t e c t i o na l g o r i t h mb a s e do nc l u s t e r i n ga r ei m p l e m e n t e du n d e rl i n u xp l a t f o r m t h es y s t e mi s t e s t e da n de x p e r i m e n tr e s u l t sa r eg i v e ni nt h i st h e s i s k e y w o r d s ：d a t am i n i n g ；l o ga n a l y s i s ；c l u s t e r i n ga n a l y s i s ；n e t w o r ka n o m a l yd e t e c t i o n i i 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：罗l 日期：兰竺塑 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名：净导师签名 南京邮电大学硕士研究生学位论文第一章引言 1 1 研究背景 第一章引言 目前，网络已经融入到人们的日常生活和工作中，也正在改变人们的工作、学习和生 活方式，同时也为我国经济的发展带来了新的机遇和挑战。对比以前，网络环境发生了巨 大的变化，经历了由结构简单到复杂、应用单- n 多样的发展过程，对于网络管理员来说， 要维护网络的正常稳定运行也成为了一个富有挑战性的难题。在以前网络结构简单的环境 下，网络管理员可能需要管理的设备只有几台或十几台。通过这些设备运行过程中产生的 日志以及现场查看发生故障的设备，管理员能够随时了解网络运行的状况，很快找出故障 原因，恢复网络的正常运行。但如今，网络管理员需要面对的网络已经发生了巨大的变化。 设备从最初的十几台已经发展到了几百台甚至上千台，网络中不稳定因素也极大地增加 了。蠕虫攻击、病毒等充斥网络，影响了网络的正常应用。虽然设备和软件运行的日志以 及其他信息记录了网络的运行情况，通过它们管理员能够了解网络故障的原因，但是依靠 传统的人工分析的方法已经不能胜任了，更不可能逐一查看现场设备，分析故障原因。所 以如何全面分析网络中获得的数据成为网络管理员急需处理的问题。 目前的网络异常分析系统存在很多局限性，主要包括： 1 缺少有效性：传统的规则匹配方法依赖专家知识的手工编码，面对复杂的网络环 境，专家知识往往不全面不精确。 2 缺少适用性：目前的网络异常检测系统针对的往往都是由于网络攻击引起的，本 文认为除了由网络攻击引起的异常外，还存在着一些其它状况引发的异常。如网 络设备运行中产生的故障和网络服务器由于配置不当而引发的安全隐患等等。 为了克服现有的异常检测系统的局限性，在设计异常检测系统时应该采用一种系统化 和自动化更好的方法。数据挖掘( d a t am i n i n g ) 就是这样一种有效的数据分析方法。数据 挖掘，就是从大量的数据中提取或“挖掘 知识，也就是从大量不安全的、有噪声的、模 糊的或者随机的数据中提取人们事先不知道的、但又有用的信息和知识。数据挖掘其实质 是知识发现的核心部分，而知识发现是在积累了大量数据后，从中识别出有效的、新颖的、 有用的知识，人们利用这些知识改进工作，提高效率和效益。它目前已经广泛应用到金融、 生物、计算机网络等领域中。 数据挖掘包含一套数据分析方法，如关联分析、分类分析、聚类分析、回归分析等。 南京邮电大学硕士研究生学位论文第一章引言 利用这些方法能够找出数据中隐藏的不为人知的信息。将数据挖掘技术应用在异常检测 中，能够在广泛搜集审计数据的基础上，通过各种分析方法捕获正常行为与异常行为的差 别。这种自动化的方法无需手工分析和编码异常模式，在创建正常行为模式时也不再像以 前一样需要凭经验来选择统计方法，而且相同的数据挖掘工具可以应用于多个数据流，这 些优势有利于建立自适应的异常检测系统。 目前，数据挖掘技术在异常检测领域还没有得到系统而充分的研究，因此，本文结合 网络中各种异常的特点进行数据挖掘算法的研究和选择，对于异常检测和数据挖掘技术都 具有一定的理论价值。 1 2 相关工作 当前，数据挖掘在异常检测中的研究重点依然是如何从数据中区分出正常行为和异常 行为。而根据采用的数据挖掘分析方法的不同，其侧重点又有区别。 h e i k k im a n n i l a 等人在1 9 9 7 年提出了频繁情节( f r e q u e n te p i s o d e ) 【1 1 ，随后又将 频繁情节挖掘用于电信网故障的发现，并实现了一个电信网故障管理系统t a s a 2 1 。相类 似的还有关联规则分析，在网络的故障发现方面也得到了应用【3 】。 聚类分析是一种不同于上述两种的分析方法，它是在事先不知道数据特性的情况下， 通过距离的度量来将数据划分为不同的类别，其目的是要找出样本空间的孤立点。目前在 网络日志分析和流量分析方面得到了应用【4 ，5 1 。 另外，神经网络作为数据挖掘中一种分类分析的方法，在网络异常分析中也得到了应 用。c o n s t a n t i n em a n i k o p o u l o s l 6 7 j 提出了将神经网络应用在网络异常检测中的方法，并与简 单网络管理协议结合起来，使得系统更加具有适用性。2 0 0 5 年，c h r i s t o ss i a t e r l i s 等人发表 了使用神经网络来检测d d o s 攻击的文章【8 】，取得了一定的效果。 但是基于数据挖掘的方法也存在着缺陷，而这些缺陷中最重要的就是实用性。正如 p e t e rc o y 指出“如果您让计算机折腾足够长的时间，对任何偏见您都能发现支持它的证据 9 1 。这种缺陷也不全是因为数据挖掘方法的问题，有时候甚至与方法无关，而是在实施数 据分析之前的计划和准备工作不够。所以，在本文的研究中，所用到的算法和处理都是围 绕实用性和准确性展开的，对于异常检测和数据挖掘技术都具有一定的理论价值。 南京邮电大学硕士研究生学位论文 第一章引言 1 3 论文的主要工作 论文主要从网络日志挖掘和流量信息分析两个方面的内容来挖掘网络中的异常。目前 成熟的网络管理软件中的日志分析功能大都只涉及到日志采集和告警处理，没有挖掘日志 之间内在的联系，如a d v e r t n e t 的o p m a n a g e r 中的e v e n t l o ga n a l y z e r 。即便有日志审查，其 方式大多以定期方式进行，这样做的缺点是不能及时地分析日志中的信息，尤其在网络故 障诊断时，定期审查的方式显得尤为不足。本文在日志分析方面主要考虑采用增量挖掘的 方法来分析日志，不仅能够发掘日志深层次的知识，而且能够在尽量使用已发现知识的前 提下，高效地对不断增长的日志数据库进行分析。在流量分析方面主要采用聚类挖掘方法， 运用流量统计技术和类别划分方法找出异常的流量信息。并在l i n u x 下实现了该挖掘系统。 本文的创新点主要有以下几点： ( 1 ) 根据网络异常的特点，提出了一个基于数据挖掘的异常检测系统模型； ( 2 ) 设计了一种关联规则的增量挖掘方法，并将其运用到网络日志的分析中，并通过 挖掘网络设备日志中非频繁的事件来发现异常； ( 3 ) 提出了在n e t f l o w 1 0 , l l 】流量统计的基础上运用聚类算法来区分异常行为的方法。 1 4 论文结构 本文主要分为五章，具体的划分如下： 第一章，论述了研究的背景，提出了要解决的问题，并给出了解决问题的步骤以及要 达到的目标，同时对一些和本文相关的工作进行了比较。 第二章，介绍了数据挖掘的模型和步骤，并阐述了其常用的分析方法。介绍了网络异 常检测的背景和目前的一些方法，并论述了数据挖掘技术在网络异常检测中的有效性。 第三章，针对目前日志分析的要求，提出了一种基于关联规则的增量挖掘算法，并探 讨了其在日志挖掘中的应用，最后对实验结果进行了分析。 第四章，详细介绍了基于n e t f l o w 的流量统计系统的实现，并提出了在此基础上运用 聚类算法分析网络异常的方法，接着对实验数据进行了分析。 第五章，总结全文，给出本文的工作和应用价值，同时对以后的研究工作进行了展望。 南京邮电大学硕士研究生学位论文第二章数据挖掘技术与异常检测 第二章数据挖掘技术与异常检测 数据挖掘( d a t am i n i n g ) 又被称为知识发现( k d d ，k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) ， 是从大量的、不完全的、有噪声的、模糊的、随机的数据中，发现隐含的、有规律的、未 知的、但又是潜在有用的并且最终可以理解的信息和知识的过程。数据挖掘是利用各种分 析工具在海量数据库中发现模型和数据间关系的过程，使用这些模型和关系可以进行预 测，它帮助分析者寻找数据间潜在的联系( 可能在我们意料之中，也可能在我们意料之外) 。 为什么我们需要对数据进行挖掘? 可以从商业需求和技术的角度来回答这个问题【1 2 】。 从商业需求的角度来看主要有三点原因： ( 1 ) 大量数据被收集和保存在数据库中，例如w e b 数据、电子商务、信用卡的支付记 录等等。 ( 2 ) 计算机已经变得越来越廉价，而功能则日益增强。 ( 3 ) 日益剧烈的商业竞争的压力。 从技术的角度来看也有三点原因： ( 1 ) 数据的存储和收集更加高速。 ( 2 ) 传统的技术对于这些大量的原始数据是不能胜任的。 ( 3 ) 数据挖掘能够帮助分类和划分数据。 基于以上的这些原因，数据挖掘被认为是解决当今时代数据爆炸而信息贫乏问题的一 种有效方法。 数据挖掘是一门交叉学科，融合了数据库、人工智能、机器学习、统计学等多个领域 的理论和技术。数据库、人工智能和数理统计是数据挖掘研究的三大技术支柱。目前k d d 的研究主要包括基础理论、发现算法、数据仓库、可视化技术、定性定量互换模型、知识 表示方法、发现知识的维护和再利用、半结构化和非结构化数据中的知识发现以及网上数 据挖掘等。 数据挖掘本身是一个数据分析的过程，但同时又是知识发现的一个重要步骤，如图2 1 所示。 4 南京邮电大学硕士研究生学位论文第二章数据挖掘技术与异常检测 数据源 图2 1 知识发现的主要步骤 知识发现的步骤包括数据选择( d a t as e l e c t i o n ) 、数据预处理( d a t ap r e p r o c e s s i n g ) 、数据 转换( d a t at r a n s f o r m a t i o n ) 、数据挖掘( d a t am i n i n g ) 、知识表达和评估( k n o w l e d g e i m e r p r e t a t i o n e v a l u a t i o n ) 。数据选择是将各种数据源集中在一起：数据预处理是从数据库 中检索与分析任务相关的数据，并除去有噪声的、不一致的数据：数据转换是将数据变换 为适合挖掘的形式，例如转换为统一的格式；数据挖掘是使用智能方法提取数据模式；模 式评估是根据某种兴趣度度量，识别表示知识的真正有趣的模式：知识表示是使用可视化 的知识表示技术，向用户提供挖掘的知识。 2 。1 数据挖掘的任务 数据挖掘是一个反复迭代的过程，在这个过程中，所取得的进步用“发现”来定义， 而这种发现是通过自动或半自动的方法取得的。在对什么将会构成一个“有趣的”结果没 有预定概念的初步探测性分析方案中，数据挖掘非常重要。它从大量的数据中搜寻有价值 的、非同寻常的新信息，是人和计算机合力的结果；它在人类描述问题和目标的知识与计 算机的搜索能力之间寻求平衡，以求获得最好的效果。 在实践中，数据挖掘的基本目标往往是预测和描述【9 1 。“预测”涉及到使用数据集中的 些变量或域来预测人们关心变量的未知或未来的值；另一方面，“描述关注的则是找 出描述可由人类解释的数据模式。因此，可以把数据挖掘活动分为下述两类： ( 1 ) 预测性数据挖掘：生成己知数据集描述的系统模型。 ( 2 ) 描述性数据挖掘：在可用数据集的基础上生成新的、非同寻常的信息。 南京邮电大学硕士研究生学位论文第二章数据挖掘技术与异常检测 在预测领域的后期，数据挖掘的目标是得出一种模型，以可执行码来表示。这种可执 行码可以用于执行分类、预测、评估或者其它相似的任务。而描述性领域的后期，数据挖 掘的目标是利用大型数据集中的未知模式和关系获得对所分析系统的理解。对特定的数据 挖掘的应用，预测和描述的相对意义有相当大的变化。预测和描述的目标都是通过数据挖 掘技术来实现的。数据挖掘的基本任务如下： ( 1 ) 分类预测学习功能的发现，此功能将一个数据项分到几个预定义类别中的一 类。 ( 2 ) 回归预测学习功能的发现，此功能将一个数据项映射到一个真实值预测变量。 ( 3 ) 聚类一种普遍的描述性任务，寻求以确定有限的一组类别或类来描述数据。 ( 4 ) 关联发现描述变量之间或者数据集或其一部分的特征值之间的重要的相关性 的模型。 ( 5 ) 偏差分析发现数据集中最重要的变化。 2 2 数据挖掘的主要流程 数据挖掘是指一个完整的过程，该过程从大型数据库中挖掘先前未知的、有效的、实 用的信息，并使用这些信息做出决策或丰富知识。 数据挖掘主要包括以下步骤，如图2 2 所示，其中各步骤内容为： 数据集成选择预处理转换 挖掘 结果表示和解释 数据源 目标数据预处理后的数据 模式知识 图2 2 数据挖掘的主要步骤 ( 1 ) 确定业务对象 清晰定义出业务问题，认清数据挖掘的目的是数据挖掘的重要一步。大多数基于数据 的模型研究都是在一个特定的应用领域内完成的。因此，为了提出一个有意义的问题的陈 述，拥有领域内详尽的知识和经验是必不可少的。挖掘的结果是不可预测的，但要探索的 问题应该是可以预见的。 ( 2 ) 数据准备 a 数据的选择 6 南京邮电大学硕士研究生学位论文第二章数据挖掘技术与异常榆测 搜索所有与业务相关的内部和外部数据信息，并从中选择出适用于数据挖掘应用的 数据。 b 数据预处理 研究数据质量，为进一步的分析做准备，并确定要进行的挖掘操作的类型。 c 数据的转换 将数据转换为一个分析模型。这个分析模型是针对挖掘算法建立的。建立一个真正适 合挖掘算法的分析模型是数据挖掘成功的关键。 ( 3 ) 数据挖掘 对所得到的经过转换的数据进行挖掘。除了选择合适的挖掘算法外，其余一切工作都 能自动完成。 ( 4 ) 结果分析 解释并评估结果。其使用的分析方法一般应以数据挖掘操作而定，通常用到可视化技 术。 ( 5 ) 知识的同化 将分析所得到的知识集成到业务信息系统的组织结构中去。 2 3 数据挖掘的常用分析方法及应用 目前数据挖掘技术在网络安全领域中的主要应用有：对安全检测对象的海量的审计数 据的分析，例如网络连接流量的分析，主机日志分析等等；对安全检测对象的行为数据分 析，例如基于用户命令序列的行为分析，对用户邮件模式的行为分析；对安全系统报警事 件的数据分析等。在特定问题中，数据挖掘的分析方法有一定的区别，这主要取决于数据 的类型和规模，以及求解的目标。目前常用的分析方法有：关联分析、分类分析、聚类分 析。 2 3 1 关联分析 关联规则挖掘用于寻找给定数据集中数据项之间的有趣的关联和相关关系。关联规则 揭示了数据项之间的未知依赖关系，依赖所挖掘的关联关系，可以从一个数据的信息来推 断另一个数据对象的信息。 关联规则的挖掘通过规则支持度( s u p p o r t ) 和置信度( c o n f i d e n c e ) 进行兴趣度衡量，这两 种衡量反映了所发现规则的有用性和确定性。一个关联规则是有趣的意味着它满足最小支 持度阈值和最小置信度阈值。阈值由专家和用户来设定。它的一般形式为：“如果一条记 南京邮电大学硕士研究生学位论文第二章数据挖掘技术与异常检测 录有确定的属性，那么它以一定的置信度拥有其它属性”。 关联分析的概念为【1 3 】： 设d 是事务数据库，i = f l ，之，乙) 是所有项目的集合，其中f ，j = l l * o * o , j m 是一个项目。 每个事务z 是一个项集，互i 。 定义1设a ，b 为项集，则a b 表示为关联规则，其中aci ，bci ，且a nb = o 定义2设d 是事务集，a ，b 为项集，且有规则ajb 。如果d 中包含a b 事务 的比例为s ，称ajb 有支持度s ，即概率p ( a b ) 。 定义3设d 是事务集，a ，b 为项集，且有规则ajb 。若d 中，c 的事务包含 a 的同时也包含b ，则称ajb 有置信度，即条件概率p ( b i a ) 。 定义4设d 是事务集，a ，b 为项集，若a j b 满足最小置信度c 和最小支持度 s ，则称a j b 为关联规则。 关联规则挖掘在网络中主要用于发现故障发生的规律和网络行为分析。例如通过对网 络设备的告警日志的关联分析，可以发现事件的属性之间的联系。通过对w e b 日志的挖掘 可以发现一些用户的上网行为规律，例如通过分析源i p ，目的i p 与流量之间的关系，发 现某个用户喜欢访问哪个网站，以便管理员能够调整网络性能。 2 3 2 分类分析 分类在数据挖掘中是一项非常重要的任务，目前在商业中应用最多。分类的目的是要 建立一个能够将数据库中数据项映射到给定类别的分类器或分类模型。分类和回归都可以 用于预测。预测的目的是从历史数据记录中自动推导出对给定数据的推广描述，从而能对 未来数据进行预测。和回归方法不同的是，分类的输出是离散的类别，而回归的输出是连 续数值。 学习分类器之前，首先要提供一个训练数据集作为分类算法的输入，训练数据集中每 一条数据记录都有己知的类型标识与之相关联，而且训练数据集中的数据记录与实际数据 集中的数据记录具有相同的数据项，训练数据集中这一点是与聚类算法的本质区别，因此 可以称为“有监督的学习方法”。分类算法对训练数据集进行分析，提取数据记录的特征 属性，为每一种类型标识生成精确的分类规则描述。分类规则在测试数据集上进行预测精 度评估后，才能用于对实际数据集中的数据记录进行分类。 分类器的构造方法有统计方法、机器学习方法、神经网络方法等等。统计方法包括贝 叶斯法和非参数法，对应的知识标识为判别函数和原型事例：机器学习方法包括决策树法 南京邮电大学硕士研究生学位论文 第二章数据挖掘技术与异常检测 和规则归纳法，前者对应的表示为决策树和判别树，后者则一般为产生规则；神经网络主 要是b p 算法，它的模型表示是前向反馈神经网络模型，b p 算法的本质是一种非线性的判 别函数。 不同的分类器有不同的特点。有三种分类器评价或比较尺度：预测准确度、计算复杂 度、模型描述的简洁度。预测准确度是用得最多的一种比较尺度，特别是对于预测型分类 任务。计算复杂度依赖具体的实现细节和硬件环境。在k d d 中，由于操作对象是巨量的 数据库，因此空间和事件的复杂问题将是非常重要的环节。对于描述性的分类任务，模型 描述越简洁越受欢迎，例如，采用规则表示的分类器构造法就更有用，而神经网络方法产 生的结果就难以理解。 分类的效果一般和数据的特点有关，有的数据噪声大，有的有缺失，有的分布稀疏， 有的字段或属性相关性强，有的属性是离散的而有的是连续的或混合式的。 2 3 3 聚类分析 与分类分析不同，聚类分析是一种无监督的模式分类方法。它依据样本间关联的量度 标准将其自动分成几个群组，且使同一群组内的样本相似，而属于不同群组的样本相异的 一种方法。目前大多数的聚类算法都是基于几种常见方法的： ( 1 ) 划分方法 给定一个包含n 个对象的数据集，划分方法将数据集划分为k ( 1 k n ) 。其中每个 子集代表一个聚类。这些类别满足如下要求：每类至少包含一个对象；每个对象必须 只属于一个类。如图2 3 所示为划分聚类。 原来的点 划分聚类后的点 图2 3 划分聚类 给定初始划分类的个数k ，一个划分方法创建一个初始划分( 往往是随机的) ，然后利 用循环迭代，通过移动不同划分类中的对象来改变划分内容。为获得聚类分析的全局最优 结果就需要穷举所有可能的对象划分。具有代表性的算法是：k r e c a l l s 算法，该算法中 9 南京邮电大学硕士研究生学位论文第二章数据挖掘技术与异常检测 的每一个聚类均用相应类中对象的均值来表示；k m e d o i d s 算法，该算法中的每一个聚类 均用相应类中离类中心最近的对象表示。因此该方法对于噪声和异常点没有k - m e a n s 法敏 感。 ( 2 ) 层次聚类 层次聚类与划分方法不同，它不需要指定要分成的类的个数。系统的输出是类的层次。 大多数层次聚类过程不是基于最优的思想，而是通过反复的分区直至收敛，找出一些近似 的、接近最佳标准的解决方案。层次聚类分析的算法有两类：分裂和凝聚。目前主要应用 的为凝聚算法，它初始将每个对象作为一个初始类，然后把这些类合并为一个更加粗略的 类，反复合并直至得到比较精细的类：所有的对象都在一个大类内，如图2 4 所示。 图2 4 分层聚类 b i r c h ( b a l a n c e di t e r a t i v er e d u c i n ga n dc l u s t e r i n gu s i n gh i e r a r c h i e s ) 【1 4 】方法就是一个 集成的层次聚类方法。它采用一种聚类特征树技术。聚类特征是有关对象子集概要信息的 一个三元组，是对给定子聚类统计信息的总结。 ( 3 ) 密度方法 与基于对象间距离进行聚类方法不同，基于密度的聚类方法实际上就是不断增长所获 得的聚类直到“邻近 ( 数据对象或点) 密度小于一定阈值为止。这种方法可以用于消除 数据中的噪声，帮助发现任意形状的聚类，而前一种方法只能发现球形或圆形的聚类。 d b s c a n ( d e n s i t y b a s e ds p a t i a lc l u s t e r i n go f a p p l i c a t i o nw i t hn o i s e ) i t 5 1 就是一个典型的基 于密度的方法，该方法根据密度阈值不断增长聚类。o p t i c ( o r d e r i n gp o i n t st oi d e n t i t yt h e c l u s t e r i n gs t r u c t u r e ) 1 6 】也是一个基于密度的方法，该方法提供聚类增长顺序以便进行自动 或交互式数据分析。 ( 4 ) 基于网格方法 基于网格方法将对象空间划分为有限数目的单元以形成网络结构。所有聚类操作均是 在这一网络结构上进行的。这种方法主要优点就是处理时间由于与数据对象个数无关而仅 与划分对象空间的网格数相关，从而显得相对较快。s t i n g ( s t a t i s t i c a li n f o r m a t i o ng r i d ) 1 7 是一个典型的基于网格的方法，它利用网格多分辨率来完成聚类分析。 l o 南京邮电大学硕士研究生学位论文 第二章数据挖掘技术与异常检测 2 4 数据挖掘与网络管理 网络管理是指监督、组织和控制网络通信服务和信息处理所必须的各种活动的总称。 从技术实现的角度来看，网络管理包括数据采集、数据处理，然后提交给管理者。而在实 际操作中，它可能还包括分析数据并提供解决方案，甚至可能在没有管理人员的情况下自 动处理一些紧急事件，进一步它还可以产生对管理网络有用的报告。 随着计算机网络的复杂性愈来愈大，要求网络管理的性能和效率也愈来愈高，为了满 足这种需求，网络管理系统必须不断地提高和发展。今后的网络管理系统将朝着网络管理 的易操作化、网络管理层次化、网络管理协议集成化、网络管理智能化和集成系统管理几 个方向发展。 网络异常检测是网络管理员所面临的一个难题。如何准确而及时地发现异常，很快地 恢复正常状态成为网络管理研究的热门课题。一提到网络异常，有人会马上联想到网络入 侵等活动，而这点确实也成为了目前引起网络异常的主要原因。 目前随着信息化程度的日渐提高，计算机网络的资源共享进一步加强，随之而来的信 息安全问题日益突出。由于在协议、服务和管理等方面存在的缺陷而造成的网络信息泄露 或站点被篡改的现象时有发生。目前存在的黑客常用的攻击方法主要有炸弹攻击、网络监 听、冒充、口令攻击、拒绝服务攻击、端口扫描、缓冲区溢出等等。这些攻击都会给网络 的性能带来一定的影响，从而造成网络异常，影响正常应用。但是，除了网络入侵所带来 的异常以外，还有其它的一些方面。例如局域网内大量的p 2 p 应用所带来的网络性能下降、 服务器不正确配置所带来的服务不可用、交换机或路由器等网络设备出现故障而引起的网 络不可用。这些都会造成网络的异常，并且事实证明这也是一个不可忽略的原因。 数据挖掘技术能从大量的原始数据中提取出有用的信息。现在数据挖掘在入侵检测中 已经得到了运用。用数据挖掘处理搜集到的审计数据，为各种入侵行为和正常操作建立精 确的行为模式，这是一个自动的过程，不需要人工分析和编码入侵模式。另外，相同的算 法可以用于多种数据处理，这样便于建立系统的可适应性。数据挖掘方法的关键点在于算 法的选取和建立一个正确的体系结构。 南京邮电大学硕士研究生学位论文第二章数据挖掘技术与异常柃测 统计信息 策略 图2 5 异常检测的数据挖掘模型 图2 5 为将数据挖掘运用到异常检测中的一个模型。“策略 包含了管理员对于一些 异常事件的定义和系统运行所需要的参数。数据挖掘的分析结果又能够对“策略 库进行 补充，这样能够使得系统能够适应环境的变化。 1 2 南京邮电大学硕士研究生学位论文第三章增量关联规则挖掘及在日忐分析中的应用 第三章增量关联规则挖掘及在日志分析中的应用 3 1 网络日志挖掘的必要性 近年来，信息技术迅猛发展，特别是基于t c p i p 协议的互联网得到广泛应用，其影响 已经渗透到了我们生活的各个角落，深刻改变了人们的生活方式。t c p i p 网络体系结构与 协议的巨大成功来源于其开放性以及简单性，但也正是由于这种开放性和简单性使得互联 网成为一种高度异构、开放的复杂系统，带来了不少安全以及管理上的问题。 为了解决日益严峻的信息安全问题，网络管理者采取了大量的安全措施，迫切希望构 建网络监视系统，实现对网络流量、资源使用情况的监视，达到加强网络管理的目的。在 这种情况下，基于日志的网络安全审计系统受到越来越多的重视。 日志对于网络的正常运营非常重要，它记录了系统每天发生的各种事件，维护人员可 以通过它来检查错误发生的原因，监控用户的使用行为，发现异常情况或者受到攻击时攻 击者留下的痕迹等。利用日志进行安全审计分析的思想，最早是在1 9 8 0 年提出的，至今 经历了2 0 余年的研究和发展，已经形成了较为完备的理论和实际应用系统。网络信息安 全审计系统现己发展成为近几年网络安全领域的研究重点之一。 网络日志的产生是由于网络中设备或软件的运行而产生的。在网络应用越来越丰富、 也越来越复杂的今天，网络日志的容量也极大地增加了。随之带来的困难也出现在网络管 理员面前，成为不可回避的问题。 在以前网络结构简单的环境下，网络管理员可能需要管理的设备只有几台或十几台。 这些设备运行过程中产生的日志能够很好的帮助管理员随时了解网络运行的状况，避免重 要故障的出现，或者能够在故障产生以后能够很快地解决故障，恢复网络的正常运行。但 在今天，网络管理员需要面对的网络已经发生了巨大的变化。设备从最初的十几台已经发 展到了几百台甚至上千台，网络中不稳定因素也极大地增加了，蠕虫攻击、病毒等充斥网 络，影响网络的正常运行。虽然设备和软件运行的日志记录下了网络的运行情况，通过它 们管理员能够了解网络故障的原因，但是依靠传统人工分析的方法已经是不可能的。所以 日志分析逐渐成为网络管理员难以处理的问题，明明知道其中包含重要的信息却难以做到 全面的分析。另外，在很多情况下，网络管理员关心的并不是那些正常的状态报告信息， 而是那些与潜在的威胁相关联的信息。例如在l i n u x 系统下的l 2 r t l 8 】攻击，如果有人利用 口令猜测，系统会记录下登陆者的i p 以及其他可以供管理员追踪的信息。 南京邮电大学硕士研究生学位论文 第三章增量关联规则挖掘及在日志分析中的应用 目前成熟的一些网络管理软件中都只包含了日志告警处理的功能，如a d v e n t n e t 的 o p m a n a g e r 产品中的e v e n t l o ga n a l y z e r 实现了对日志的搜集、分析和报告，并提供详细统 计和对一些已知异常行为的报警。但是对于这些日志并没有分析其深层次的联系，目前的 很多网络管理产品大都有这个缺陷。这种日志管理的方式一般只具备日志的收集、分类、 归档和报告功能，只是一个日志的集中存储，并没有为网络管理员减轻负担，如何从含有 大量看似杂乱的数据中分析出管理员关心的信息成为日志分析的重点。数据挖掘就是这样 一种数据分析技术。 目前的网络管理产品大都没有提供日志的深层挖掘功能，并且日志审查方式大多以定 期方式进行，这样做的缺点是不能及时地分析日志中的信息，尤其在网络故障诊断时，定 期审查的方式显得尤为不足。下面本文会介绍一种网络日志的增量关联规则挖掘算法，使 得日志挖掘系统能够对日志进行自动增量分析。 3 2 关联规则挖掘算法 3 2 1a p r i o r i 算法 a p r i o d t 9 ，19 2 0 】算法在关联规则的发现方面有很大的影响，因为它使用了频繁项集的先 验知识。该算法利用了“频繁项的子集一定是频繁项集，非频繁项的超集一定是非频繁集 【1 8 】 的特点，利用已知的频繁项集构成长度更大的项集，并将其称为候选频繁项集。算法 首先计算所有的1 项集c i 。从c 1 中找出所有的频繁一项集l l 。然后，根据l l 确定候选 2 项集的集合c 2 。如此下去直到不再有候选项集产生。其算法过程如下： 通过一次扫描事务数据库d 计算出所有1 项集的支持度，从而得到满足最小支 持度s 的频繁1 项集构成的集合l l 。 为了产生频繁k 项集构成的l k ，先生成一个候选频繁k 项集的集合c k 。若p , q l k 1 ，p = p l ，p 2 ，p k 1 ) ，q = q l ，q 2 ，q k - 2 ，q k i ，并且当1 i k 1 时，p i - - q i ，当i = k l 时，p k t ：q k 1 ，则puq = p l ，p 2 ，p k 1 ，q k 1 ) 是候选频繁k 一项集的集合c k 中的元素。 由于c k 是l k 的超集，所以有些元素不是频繁的。由于任何非频繁的( k 1 ) 项集必定 形不成频繁k 项集的子集，所以，当候选k 项集的某个( k 1 ) 子集不是l k - - 1 中的成员时， 则该候选频繁项集不可能是频繁的，可以从c k 中移去。通过单趟扫描事务数据库d ，计算 c k 中各个项集的支持度。将c k 中不满足最小支持度s 的项集移除，形成频繁k 项集构成 的集合h 。 通过迭代，重复上述步骤，直到不能产生新的频繁项集的集合为止。 1 4 南京邮电大学硕士研究生学位论文第三章增量关联规则挖掘及在日志分析中的应用 a p r i o r i 算法扫描数据库的次数完全依赖于最大的频繁项集中项的数量。目前有很多算 法对a p r i o r i 做了改进，减少了对数据库的扫描次数，但是因为a p r i o r i 算法要产生大量的 频繁候选集，而改进的算法不能完全避免这个问题。本文假定要生成一个长度为1 0 0 的频 繁模式，例如 a l ，a 2 ，a 3 ，a 1 0 0 ) ，那么所产生的候选集的数量至少为【9 】： 善( ：。) = 2 1 0 0 一，。3 。 并且需要扫描几千次数据库。计算的复杂性也呈指数增长! 这也是影响其发展的一个 重要因素。 3 2 2 频繁模式增长( f p g r o w t h ) 算法 频繁模式增长算法【2 1 】在挖掘频繁项集时不存在产生候选集的繁琐过程。当数据库很大 时，f p g r o w t h 算法首先进行数据投影，得到频繁项；然后通过构造一个压缩的数据库结 构- - f p 树来进行挖掘。 对于表3 1 的事务数据库t ，利用f p g r o w t h 方法来挖掘的步骤为( 最小支持度阈值 为3 ) ： 扫描数据库t ，得到频繁项( 出现次数为3 次或3 次以上的项) 的列表l 。它们分 别是： l = ( 4 ) ，( c ，4 ) ，仇3 ) ，( b ，3 ) ，( m ，3 ) ，( p ，3 ) 频繁项集按支持度计数的递减顺序排列。 创建树的根r o o t ，再次扫描数据库t 。对第一个事务扫描可以得到树的第一个 分支： ( 1 ) ，( c ，1 ) ，1 ) ，( r n ，1 ) ，( p ，1 ) ) 。只有那些在l 中出现的项才会被选中。分支中结 点的计数代表了树中该结点项所出现的次数，所以在第一个