（计算机科学与技术专业论文）基于流量特征分析的数据流突发事件检测技术的研究与实现.pdf

国防科学技术大学研究生院下学硕十学位论文 摘要 随着计算机技术的发展和互联网应用的深入 各种网络攻击事件 d d o s 网 络蠕虫等 对网络产生了巨大危害 如何及时发现它们并采取有效的后续相应措施 己经成为计算机网络安全研究领域的一个重要课题 网络流量的突发检测作为网 络安全事件检测手段之一 对快速定位导致网络流量异常的网络安全事件 具有 重要意义 鉴于网络流量数据的海量 高速等特点 本文采用数据流的研究方法 首先 介绍了数据流及其关键技术的研究现状 并综述了现有的突发检测算法 通过分 析比较优缺点 选择基于比率的适应性聚集突发检测算法 a d a p t i v e l yd e t e c t i n g a g g r e g a t i o nb u r s t si nd a t as t r e a m s 本文简称为a d a b 算法 作为研究对象 在此基础上 给出了建立在数据流计算模型之上的三种突发的形式化定义 即突发性突发 持续性突发及变化缓慢且持续时间较长的突发 以更好地描述在 真实应用环境中的流量突发特征 在研究a d a b 算法的基础上 针对其不适合或 不能检测出网络安全流量事件中持续性突发和变化缓慢且持续时间较长的突发的 不足 提出改进的a d a b 算法 该算法基于反向直方图 i n v e r t e dh i s t o g r a m 技术 能够灵活调整突发检测的时间尺度 理论分析表明 该算法误报率及空间复杂度 较低 且保证了线性时间复杂度 基于a d a b 设计了一个基于数据流的网络安全突发事件检测原型系统 系 统按功能划分为三大部分 即管理机 检测机及数据库系统 管理机提供了友好 的人机交互界面 通过对网络数据流按协议细分 并对细分后的数据流进行突发 检测 检测机能够快速发现基于某种特定协议的网络异常行为 数据库用于记录 报警结果 方便后续的查询 分析和处理等 基于n l a n r 追踪网络流量和模拟攻击数据 分别从查全率和查准率 时间 空间复杂度等方面对a d a b 算法及突发检测原型系统进行了验证 并对各种参数 设置进行了测试和分析 验证了算法的有效性以及在突发异常描述及计算效率方 面的优越性 最后对研究工作进行了总结 同时分析了存在的问题 并对下一步的研究工 作提出了几个发展方向 包括阈值的动态设定 选取合理的窗口大小等 主题词 网络安全 数据流 突发检测 比率 第i 页 国防科学技术大学研究生院工学硕士学位论文 a b s t r a c t w i t l lt h ec o m p u t e rt e c h n o l o g yb o o m i n ga n dt h ei n t e m e ta p p l i c a t i o nd e v e l o p i n g m a n ym o r en e t w o r ka t t a c k s s u c ha sd d o sa n dw o r m s h a v eb r o u g h t o u tg r e a th a r mt o t h en e t w o r k h o wt of i n dt h e mi nt i m ea n dt a k es o m ee f f e c t i v es t e p s h a sb e c a m ea i m p o r t a n ts u b j e c to ft h ec o m p u t e rn e t w o r kr e s e a r c hd o m a i n b yw a y o fo n em e t h o do f d e t e c t i o ni nn e t w o r ks e c u r i t y t h eb u r s td e t e c t i o no fn e t w o r kt r a f f i c sh a sa ni m p o r t a n t s i g n i f i c a n c e w h i c hc o u l df i n dt h en e t w o r ks e c u r i t ym a t t e rt h a ti n d u c e sa b n o r m i t yo f n e t w o r kt r a f f i c sq u i c k l y b a s e do nt h em a s s i v en e t w o r kt r a f f i cd a t aw i t hh i g hs p e e d t h i sp a p e rt a k e sad a t a s t r e a m sa p p r o a c h a tf i r s tw ei n t r o d u c ed a t as t r e a m sa n dt h er e s e a r c ha c t u a l i t yo fi t s p i v o t a lt e c h n i q u e s a n ds u m m a r i z et h ee x i s t i n ga l g o r i t h m s o fb u r s td e t e c t i o n w e a n a l y z ea n dc o m p a r et h e i ra d v a n t a g e sa n dd i s a d v a n t a g e s c h o o s ea d a p t i v e l yd e t e c t i n g a g g r e g a t i o nb u r s t si nd a t as t r e a m s a d a ba l g o r i t h mf o rs h o r t a sr e s e a r c ho b j e c t t h e ni no r d e rt od e s c r i b i n gt h ec h a r a c t e r i s t i co ft r a f f i cb u r s t si nr e a la p p l i c a t i o n e n v i r o n m e n tb e t t e r n e wf o r m u l a t i o nd e f i n i t i o no ft h r e et y p e so fb u r s t si sp r e s e n t e d b a s e do nt h ed a t as t r e a mc o m p u t a t i o nm o d e l n a m e l yt h ea b r u p tb u r s t t h el a s t i n gb u r s t a n dt h eb u r s tw h i c hi sc h a n g i n gs l o w l ya n dc o n t i n u i n gf o ral o n gt i m e b a s e do n s t u d y i n ga d a ba l g o r i t h m w ea i ma tt h es h o r t c o m i n go ft h i sa l g o r i t h m n a m e l yi t d o e s n ta d a p tt oo rc o u l dn o td e t e c tt h el a s t i n gb u r s ta n dt h eb u r s tw h i c hi sc h a n g i n g s l o w l ya n dc o n t i n u i n gf o ral o n gt i m ei nn e t w o r ks e c u r i t y t h ei m p r o v e da l g o r i t h m v i z a d a b a l g o r i t h m i sp u tf o r w a r d i ti sc a r r i e do u tb a s e do ni n v e r t e dh i s t o g r a m a n d c a na d j u s tt i m es c a l e si nb u r s td e t e c t i o nf l e x i b l y 1 1 1 ea n a l y s e so ft h et h e o r yi n d i c a t e t h a tw ec a ns e et h a ti t sp r e c i s i o ni sh i g h e ra n ds p a c ec o s ti sl o w e r i ta l s og u a r a n t e e s t i m ec o s ti nl i n e a r i t y b a s e do na d a b a l g o r i t h m w ea p p l yi tt on e t w o r ks e c u r i t yd o m a i na n dd e s i g na p r o t o t y p es y s t e mw h i c hc a nd e t e c tb u r s ti nn e t w o r ks e c u r i t yb a s e do nd a t as t r e a m s a c c o r d i n gt ot h ef u n c t i o n t h es y s t e mi sd i v i d e di n t ot h r e ep a r t s s u c h 嬲m a n a g e r d e t e c t o ra n dd a t a b a s e m a n a g e rp r o v i d e saf r i e n d l yi n t e r f a c et h a tu s e r sc a nl i n kw i t ht h e s y s t e m a f t e rs u b d i v i d i n gd a t as t r e a m sa c c o r d i n gt op r o t o c o l w ed e t e c tb u r s t so nt h e s e f r a c t i o n s d e t e c t o rc o u l df i n da b n o r m a lb e h a v i o rb a s e do np a r t i c u l a rp r o t o c o lq u i c k l y d a t a b a s es y s t e mi su s e dt ol o g g i n ga l a r mr e s u l t s s ot h a tw ec o u l dq u e r ya n da n a l y s e c o n v e n i e n t l y b a s e do nn l a n rn e t w o r kt r a m ct r a c k sa n ds i m u l a t e da t t a c kd a t a w et e s tt h e a d a b a l g o r i t h ma n dt h ep r o t o t y p es y s t e mt h r o u g hs o m ea s p e c t s s u c ha sr e c a l l p r e c i s i o n t i m ec o s ta n ds p a c ec o s t t h es e t t i n go fp a r a m e t e r si sd i s c u s s e da n da n a l y z e d i tv a l i d a t e st h ev a l i d i t yo ft h ea l g o r i t h ma n dt h ea d v a n t a g eo fb u r s td e s c r i p t i o na n d c o m p u t i n ge f f i c i e n c y 第i i 页 k e yw o r d s n e t w o r k s e c u r i t y d a t as t r e a m b u r s td e t e c t i o n r a t i 国防科学技术大学研究生院工学硕士学位论文 表目录 表4 1 典型攻击类型与对应协议 5 刀 3 3 表4 2 实时报警记录表结构 4 2 表4 3 真实突发信息表结构 4 2 表4 4 0 0 0 0 0 8 0 0 段突发流量差量平均和表结构 4 3 表4 5 0 8 0 0 1 6 0 0 段突发流量差量平均和表结构 4 3 表4 6 1 6 0 0 2 4 0 0 段突发流量差量平均和表结构 4 3 表5 1 表t e s t d a t a 结构 4 6 第1 i i 页 国防科学技术大学研究生院工学硕十学位论文 图目录 图1 1 新增病毒数量对比 7 0 2 图1 2 网络流量突发示例i 6 6 j 3 图1 3d d o s 攻击流量模型 2 1 4 图1 4 蠕虫的传播模型 7 l 4 图2 1 数据流处理模型 6 6 7 图2 2 数据流上滑动窗口示例 吲 1 1 图2 3 迁移小波树结构 6 6 1 5 图2 4 两层小波树结构 6 6 1 6 图3 18 1 0 8 1 4 网络报文数量分布刚6 3 1 8 图3 28 4 2 8 4 8 网络报文数量分布刚6 3 1 9 图3 3v 优化直方图和反向直方图 1 1 2 l 图3 4b 位0 1 标志位串 2 4 图3 5 变化缓慢且持续时间较长的突发 2 5 图4 1 主要协议的流量比例 7 1 3 4 图4 2 网络带宽在主要协议流量上的分布 6 3 3 4 图4 3 突发检测系统体系结构 3 5 图4 4 检测机结构 3 5 图4 5 数据捕获模块 3 6 图4 6 网络流量突发检测模块 3 7 图4 7 较大的时间尺度引起的突发缓和 3 8 图4 8 使用重叠子窗口的动态变化阈值 6 7 4 0 图4 9 管理机结构 4 l 图5 1i n d i a n a p o l i s 路由器节点数据 4 5 图5 2 待检测的u d p 数据流流量变化情况 6 6 1 4 7 图5 3 查全率与查准率 4 7 图5 4 时间复杂度 4 8 图5 5 空间复杂度 4 8 图5 6 改变b 的查全率与查准率 4 9 图5 7 改变6 的查准率 4 9 图5 8 改变滑动窗口的查全率与查准率 5 0 图5 9 改变滑动窗口的突发检测时间 5 0 图5 1 0 改变时间窗口的突发检测时间 5 1 第1 v 页 国防科学技术大学研究生院工学硕士学位论文 图5 11 改变时间窗口的查全率 5 1 第v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果 尽我所知 除了文中特别加以标注和致谢的地方外 论文中不包含 其他人已经发表和撰写过的研究成果 也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料 与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意 学位论文题目 基王速量缱堑佥堑鲍熬量速塞塞童往捡型遮盔煎盈究鱼塞丑 学位论文作者签名 耋 盔 日期 加口号年i 月j 毕日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留 使用学位论文的规定 本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档 允许论文被查阅和借阅 可以将学位论文的全部或部分内容编入有关数据 库进行检索 可以采用影印 缩印或扫描等复制手段保存 汇编学位论文 保密学位论文在解密后适用本授权书 学位论文题目 基王速量挂征金堑鲍数握速塞发皇鲑捡测垫苤的盟塞生塞理 学位论文作者签名 垂盘 日期 妒孑年l 月 妒日 作者指导教师签名 彳轻垂垃 卜 日期 硎碑 乙月 垆日 国防科学技术大学研究生院工学硕士学位论文 第一章绪论弟一早三百下匕 1 1 研究背景及意义 随着计算机技术的发展 信息技术也在各行各业被广泛应用并发展起来 特 别是网络技术的发展 它改变了人类社会几千年来形成的信息传递方式 人际沟 通方式和社会管理方式 深刻影响着社会生活 使当今社会进入一个崭新的信息 时代 网络是信息技术的重要组成部分 它对信息技术的发展起到了巨大的推动作 用 网络带人们进入了一个数字化的虚拟世界 它影响到社会的各个方面 各个 层次 包括政治 经济 文化等领域 但是由于网络技术的不完善 网络安全成 为信息安全的重要研究对象 目前 许多在计算机网络中存储 传输和处理的信息是股票证券 能源资源 数据 科研数据等重要信息 其中很多是国家机密及商业秘密 由于信息网络的 安全漏洞 导致数据信息泄露 信息篡改 数据破坏 恶意发布等情况的发生 由此造成的经济损失及社会不良影响难以估计 因此它的安全问题直接影响到国 家安全 社会稳定 经济发展等各重大问题及决策 从某种意义上讲 网络安全 已不再是单纯的技术问题 它已成为整个国家安全的重要组成部分 占据极其重 要的地位 2 0 世纪6 0 年代初 美国贝尔实验室程序员编写的计算机游戏中 采用通过复 制自身的方法来摆脱对方控制 这是 病毒 的第一个雏形 7 2 1 1 9 8 3 年1 1 月 在 国际计算机安全学术研讨会上 美国计算机专家首次将病毒程序在v a x 7 5 0 计算 机上进行了实验 世界上第一个计算机病毒在实验室诞生 7 2 随着计算机技术的 发展 计算机病毒也向前发展 尤其随着近几年互联应用的不断深入 更加激发 了计算机病毒传播的活力 据统计 9 9 的大公司都发生过大的入侵事件 如世界著名的商业网站y a h o o b u y a m a z o n 等都曾被黑客入侵 造成巨大的经济损失 甚至连专门从事网络安全 的r s a 网站也受到黑客的攻击1 7 4 1 在中国 2 0 0 8 年上半年 计算机病毒 木马的 数量呈爆炸式增长 其总数已经超过了近五年的病毒数量的总和 其中新增病毒 木马1 2 4 2 2 4 4 个 较0 7 年全年病毒 木马总数增长了3 3 8 如图1 1 所示 且全 国共有2 2 3 6 7 9 9 4 台计算机感染病毒 与0 7 年同期相比增长了1 9 4 1 7 0 j 可以看 出网络的安全问题正面临着严重的威胁 面对如此严峻的网络安全问题 人们越 来越重视对它的研究 一个健全的网络信息系统安全方案应该包括如下几方面的内容 安全效用检 第1 页 国防科学技术大学研究生院工学硕士学位论文 验 安全审汜 安全技术 安全教育与培训 安全结构与程序 安全规则等 这 是一个复杂的系统工程 安全技术是其中的一个重要环节 7 3 目前 常用的安全 技术有防火墙 入侵检测系统 防病毒软件 加密技术 用户认证等 其中入侵 检测系统主要研究如何对大规模网络的宏观安全情况进行监控并及时地发现异常 等问题 具有十分重要的意义 图1 1 新增病毒数量对比 7 0 1 在网络数据包高速到达的情况下对网络数据流进行实时监测是一项极具挑战 性的工作 传统的入侵检测系统i d s 安装在主机或者低端路由器上 只能够检测 应用层或系统层的日志及捕获到的局部的网络报文 6 6 1 并且它多半是基于一些预 期的或已知的模型作为入侵的检测标准进行判断的 因此可以说入侵检测基本上 无法解决突发性问题 但是当今影响网络性能的事件多具有突发性 例如d d o s 各种蠕虫的爆发等 图1 2 为f i s hc r o w d s 事件突发时服务器主机流量变化情况以 及发生d d o s 攻击时网络流量统计情a t 6 6 可以看出 在突发点 流量值迅速增 长 变化范围超过了上千倍 这势必将严重影响网络服务和性能 另外入侵检测仍然没有达到实时的要求 它只能在适当的时候对网络进行检 测 即每隔一个很短的时间进行一次入侵检测 因为实时的入侵检测会使响应速 度变慢 但是对于一个这样的入侵检测系统 一旦如图1 2 所示的突发事件发生 在未及时报警的情况下 它的后果是很严重的 因此为解决传统方案中存在的问 题 即在尽可能短的时间内尽可能准确的发现这些异常的数据 我们需要在数据 流上研究实时的突发检测 以达到有效地检测异常数据的目的 目前关于数据流上的突发检测技术的研究有很多 主要分为基于时间序列的 检测算法和基于内容的检测算法 它们应用范围广泛 前者可以应用于天文 通 信 金融 医药及网络安全领域 而后者仅限于对文本流的突发检测 第2 页 国防科学技术大学研究生院工学硕士学位论文 同时在基于时l u j 序列的检测方法中 火部分算法 如基于小波分析的检测算 法等 主要以解决任意长度突发检测及实时性等问题为基础 仅能对单向突发进 行检测 可以看到它们忽略了网络安全中的真实数据流通常是双向变化的 针对 这一点 本文基于q i n 等人提出的基于适应性聚集突发检测算法 l j 进行研究 该算 法可检测双向突发 并且不需要绝对的阈值及满足任意时间窗口大小的突发检测 但是缺少对真实数据的突发特征的分析 导致误报和漏报的产生 因此为更好地 实现检测异常数据 有效地保证网络的安全性 结合对网络安全突发事件的流量 特征分析 研究面向网络安全的数据流突发检测技术 具有十分重要的意义 ju 喜 3 0 lz 5 量 i 5 1 i 5 0 i k h h l l j 山 口1 0 0 0 0 0 2 0 0 0 0 03 0 0 口口0q 0 0 0 0 0 5 0 0 0 0 06 0 0 0 0 07 0 0 0 0 0 l t k e 弓e c o n d a f l a s hc r o w d s 引起的流量突变 b d d o s 攻击引起的流量突变 图1 2 网络流量突发示例 删 1 2 网络安全突发事件的流量特征 在展开面向网络安全的数据流突发检测的研究之前 需要我们明确当前网络 安全突发事件的流量特征 以便确定突发检测研究的要点并制定相应的策略 因此我们结合对真实数据的分析 总结网络安全突发事件的流量特征 可以 看到它具有多样性 主要有以下几点 1 突发性的迅速增长 数据流流量的突发性迅速增长 导致流量值的变化范围在短时间内无加速的 超过了上千倍 如图1 2 所示 2 突发增长后持续保持 对于网络安全突发事件的持续性攻击 其流量特征即表现为突发性增长后 在一段时间内持续保持较正常情况高的流量值 2 0 0 0 年拒绝服务攻击 d e n yo fs e r v i c e d o s 使得世界上几家著名电子商务 提供商的站点 如雅虎 e b a y 亚马逊等 陷入瘫痪长达数小时甚至数天 造成 了巨大的经济损失 2 0 0 3 年k u n c h a r tl a n 等人 2 在u s c 的t l l ei n t e m e t 2p e e r i n gl i n k 上对d d o s 流量模型进行研究 如图1 3 所示 可以看到在d d o s 流量攻击期间 第3 页 珊 鲫 跚 螂 撕 撕 帅 名e u pug t暑0 e t 主量 国防科学技术大学研究生院工学硕十学位论文 流量较正常情况高出了近5 倍 并在一定浮动范围内持续保持了约2 0 0 s 图1 3d d o s 攻击流量模型1 2 3 缓慢增长 持续时间较长 2 0 0 5 年1 2 月9 日m s d t c 蠕虫爆发 随后2 0 0 7 年1 月一种叫做 熊猫烧香 的蠕虫病毒又在网络上疯狂传播 它严重影响了用户电脑的正常使用 甚至造成 了部分的网络瘫痪 直接经济损失超过上亿美元 蠕虫的传播主要经历三个阶段 开始的缓慢传播 接下来的快速传播和最后 的缓慢消失 如图1 4 所示 7 1 可以看到该类流量特征主要表现于蠕虫等爆发的初 期 即流量增长较为缓慢 且通常需要持续较长一段时间 才能使流量值达到一 个较高的水平 因此针对它的检测研究对于较早地实现对蠕虫等的发现和防治具 有十分重要的意义 图1 4 蠕虫的传播模型i 7 1 l 总之 可以看到网络安全突发事件的发生总是伴随着一定流量的变化 并且 表现为以上三点特征 通过对数据流突发事件的检测 可以帮助及时发现正在突 发的网络安全事件 为进一步的防范和控制提供决策依据 1 3 本文主要研究内容及组织结构 本文主要围绕如何实时准确地发现数据流突发异常并有效地应用于网络安全 这个问题进行研究 首先对数据流及其关键技术进行整体研究 明确并论证数据流突发检测中所 第4 页 宝1 巷 i e4奄 laqe星 国防科学技术大学研究生院丁学硕士学位论文 使用的研究手段 以达到实时性检测的目标 其次 针对基于比率的适应性聚集 突发检测算法的不足 提出改进算法 使准确地发现数据流中的突发异常 最后 本文讨论如何将改进的数据流突发检测算法应用于实际系统 设计出有效的基于 数据流的网络安全突发事件检测系统 并对算法及系统性能进行验证 本文剩余内容组织如下 第二章总结数据流的基本模型 剖析数据流分析中的三项关键数据处理技术 并着重分析现有的突发检测的研究方法及研究现状 第三章研究如何更加实时准确地检测基于数据流的网络安全突发事件 在分 析原有算法的基础上 针对其不足 提出改进算法 并从理论上进行分析 第四章将改进的数据流突发检测算法应用到网络安全突发事件检测当中 从 分析网络流量特征出发 设计 个基于数据流的网络安全突发事件检测原型系统 第五章对基于数据流的网络安全突发事件检测原型系统进行测试 从实践上 验证算法及系统的有效性 第5 页 国防科学技术大学研究生院工学硕 学位论文 第二章研究现状 2 1 数据流及其关键技术 3 0 多年来 数据库技术得到了迅速发展 主要经历了层次数据库 网状数据库 关系数据库 对象数据库及关系对象数据库五个阶段 尽管传统数据库获得了巨 大的成功 但是通信领域中的电话记录数据流 w e b 上的用户点击数据流 网络 监测中的数据包流 各类传感器网络中的检测数据流 金融领域的证券数据流 卫星传回的图像数据流以及零售业务中的交易数据流等形成了一种与传统数据库 中静态数据不同的数据形态 3 这对数据库技术提出了有力的挑战 2 1 1 数据流模型 数据流是一个以一定速度连续实时到达的数据项序列五 薯 该速度 与数据项到达的次序无关 并且这个数据项序列规模宏大 只能按下标i 的递增顺 序读取一次 目前 在数据流研究领域中存在多种数据流模型 不同的数据流模 型具有不同的适用范围和处理算法 可以分别按照数据流中数据描述现象的方式 和算法处理数据流时所采用的时序范围对这些模型进行划分1 3 j 假设描述信号a 定义为函数a 0 m r 的数据流 由连续的数据项 x a x j 吒 组成 按下标递增的顺序依次到达 数据项x j 可能包含多维属性 文献 4 给出了三种数据流模型 1 时间序列 t i m es e r i e s 模型 a i 薯 此时数据流中的每个数据项 都代表一个独立的信号 2 现金记帐 c a s hr e g i s t e r 模型 令而 且 0 则4 a i l 此时数据流中的多个数据项增量式地表达一个x j 如同现金记帐一样 是一种 更为普遍的数据流模式 3 十字转f t u r n s t i l e 模型 令t 则4 j 4 一 u 其中u 可 为正数 也可为负数 此时数据流中的多个数据项表达一个a i 且a j 随着数 据的流入 可能会增加 也可能会减少 该模型得名于地下铁路站上限制旅客进 入和离开站台的十字转门 适合于描述数据流动态的入队和出队状态 是研究数 据流最为通用的动态模式 由于数据流的持续到达 速度快且规模宏大 多数算法在处理数据流时并不 是以所有数据流的数据作为处理对象 而是根据应用需求选取一个时间范围 对 其中数据进行处理 按算法处理数据流时所选取的时序范围 数据流模型可分为 第6 页 国防科学技术大学研究生院1 二学硕士学位论文 以下几类吼 1 快照模型 s n a p s h o tm o d e l 将操作限制在两个预定义的时间戳之间 表示为 q q 2 界标模型 1 a n d m a r km o d e l 所要处理的数据范围从一个固定时间戳到当前 时间戳 令初始时间戳为s 当前时间戳为甩 则查询范围可以标记为q 3 滑动窗e l 模型 s l i d i n gw i n d o wm o d e l 处理数据的范围由某个固定大小的滑 动窗口确定 其终点为当前时间戳 窗口大小由一个时间区间定义 在以上3 种模型中 界标模型和滑动窗口模型的应用范围比较广 前者在进 行数据处理时 只存在插入操作 后者由于窗口随着数据的流入向前滑动 因此 存在数据的插入和删除 一个数据流处理系统通常由流处理引擎 流摘要信息和查询应答三个部分构 成 6 6 1 如图2 1 所示 数据流处理引擎主要用于处理到来的数据项 并且更新数 据流概要信息 当用户向系统提出查询请求时 流处理引擎到流概要信息中提取 结果输出 q u e r y q c i 口p c o x i n a t l t e i 塔w 盱 图2 1 数据流处理模型6 6 目前关于数据流的研究主要可分为两个应用层面 对数据流的管理以及对数 据流的挖掘 硎 首先 对数据流的管理即数据流管理系统 d a t as t r e a mm a n a g e m e n t s y s t e m 简称d s m s 包括斯坦福大学的s t r e a m 项刚6 1 施乐公司的t a p e s t r y 项 卧7 1 加州大学伯克力分校的t e l e g r a p h 项引 9 布朗大学和麻省理工学院合作 的a u r o r a 项目 1 0 等等 其次 对于数据流的挖掘 在2 1 4 节中将详细介绍 本文主要将数据流定义在基于滑动窗口的时间序列模式上进行讨论和研究 2 1 2 数据流概要 在流数据处理系统中 数据量远大于可用内存 系统无法在内存中保存所有 被扫描过的数据 但又经常需要读取那些数据 因此系统必须在内存维持一个概 第7 页 国防科学技术大学研究生院工学硕士学位论文 要数据结构以避免代价昂贵的磁盘存取 该概要结构对海量的数据进行缩减 并 同时尽可能的保持原有数据的特征 数据流概要结构的规模相对于数据流至多应 该是次线性的 即如果流的长度为 则概要数据结构大小不超过o p o l y l o g n 并且处理流上每一组数据的时间不超过o p o l y l o g n 6 目前 生成数据流概要 数据结构的主要方法有四种 包括取样 s a m p l i n g 直方图 h i s t o g r a m 小波方法 w a v e l e t 和哈希方法 h a s h 2 1 1 1 取样 抽样方法是生成概要数据结构的常用手段 它把需要处理的数据量降低到系 统可以承受的范围内 其主要思想是从数据集中抽取小部分数据代表整个数据集 并在该样本集合中操作 获得查询结果 抽样方法从概率统计的角度划分 可分 为均匀抽样 u n i f o r ms a m p l i n g 和偏倚抽样 b i a s e ds a m p l i n g 均匀抽样的样本集合 由数据集中以相同的概率被选取出的元素组成 而在偏倚抽样中 不同的元素的 入选概率可能不同 从算法删除旧数据项的方法划分 可分为水库抽样方法 r e s e r v o i rs a m p l i n g 精确抽样方法 c o n c i s es a m p l i n g 链式抽样方法和计数抽样方 法 其中前三者属于均匀抽样方法 后者属于偏倚抽样方法 下面介绍这几种抽样 方法 1 水库抽样 水库抽样方法 1 1 1 即单遍扫描数据集 生成均匀的固定大小的抽样集合 令样本集合的容量为s 在任一时刻n 数据流中的元素都以s 玎的概率均匀 地入选到样本集合中 如果样本集合大小超出s 则从中先随机删除一个样本 然 后再插入新数据项 可以证明 各元素的入选概率相等 在水库抽样方法中 影响近似程度的因素有两方面 抽样时机和样本集合大 小 抽样时机决定了样本集合的随机程度 而样本集合大小则决定了样本集合所 能代表总体特性的程度 另外该方法要求样本集合中各个元素单独占据一个位置 即使它们有相同的数值 因此表达的效率并不高 2 精确抽样 精确抽样 1 2 j 提出一种新的样本集合表示方法 即对于仅出现一次的元素 用 元素代码表示 而对于多次出现的元素 则利用 表示 其中v a l u e 代 表元素代码 c o u n t 表示样本集合中该元素的数目 可以看出 精确抽样方法比水 库抽样方法更节约空间 在精确抽样中 它维持一个初始值为1 的概率参数t 刚开始各元素以概率 l 丁加入到样本集合中 另外如果该元素已经在样本集合中存在 则相应的计数 器加1 如果样本集合溢出 改变参数丁到丁 t t 样本集合中的各个元素均 以概率r z 被删除 以便存放新数据 精确抽样方法利用逐步增大参数丁的值 第8 页 国防科学技术大学研究生院工学硕士学位论文 可以实现数据流上的均匀抽样 3 链式抽样 一 链式抽样方法l l3 是一种基于滑动窗口的均匀抽样方法 假设窗口大小为形 则在任何时间点玎 流中的元素以概率l r a i n n 形 被添加到样本集合中 并同时 为其决定一个备选元素 以便当这个元素过期时 利用备选元素代替该元素 但 是实际上 从即 1 刀 矿 中随机抽选一个数作为备选元素的时间戳t 这个备选 元素也仅能到时间点 时才最后被确定 此时它也会过期 因此又再需要为它选择 一个备选元素 方法同上 可以看出 对于样本集合中的任一元素 均有一个备 选元素的 链 当该元素过期后 马上即可用 链 上的下一个元素代替它 4 计数抽样 计数抽样方法 1 2 是精确抽样方法的一种变形 二者的区别在于如何处理样本 集合溢出的情况 在计数抽样算法中 当样本集合溢出时 首先提高参数r 至r 然后对其中任意一个元素 首先以概率r 丁 初步选出可能被删去的元素 之后 再按概率1 丁 确定元素计数器是否减去l 直到该计数器值已经降为0 或者在某 一次随机判断中计数器的值并无减小 则结束对该元素的操作 可以看出计数抽 样方法不是均匀抽样方法 但能有效地获得数据集中的热门元素列表 2 1 2 2 直方图 直方图技术1 1 4 15 即将一个大数据集划分为很多个连续的桶 b u c k e d 即小数据 集 其中每个桶都用一个数字以代表其特征 因此直方图表示法直观 简洁 能 够很好地表示大数据集的总体特性 直方图包括以下几种 如等宽直方图 e q u i w i d t hh i s t o g r a m 压缩直方图 c o m p r e s s e d1 1 i s t o g r 锄 v 一优化直方图 v o p t i m a l h i s t o g r a m 指数直方图 e x p o n e n t i a lh i s t o g r a m 等 1 等宽直方图 等宽直方图中 各个桶所含的数据量比较平均 文献 1 6 提出了一种单遍扫描 算法 它通过设置两个重要门槛值 i 限门槛和下限门槛 并判断执行两个重 要操作 拆分和合并 中的一个操作 完成数据流上的概要记录 具体地说 每 次流中的元素到达 算法首先增加该元素所属的桶的高度 即桶所含的数据量 如果桶高度高于上限门槛值 则拆分成两个小桶 反之如果桶高度低于下限门槛 值 则将该桶和相邻的桶合并 且使合并后的新桶数据量限制在上限门槛值和下 限门槛值范围内 另外维护等宽直方图还能够获得数据集的分位点 1 7 1 可以看出等宽直方图在数据分布较均匀时 它能够较好地模拟数据集 但是 一旦数据集中存在某些热门元素时 等宽直方图则会产生较大的误差 2 压缩直方图 压缩直方图 l8 是等宽直方图的一个改进 它仅仅针对热门元素的问题进行研 第9 页 国防科学技术大学研究生院工学硕士学位论文 究 提出单独为热门元素创建桶 而对其他元素仍然采用等宽直方图的方法 使 能够更真实地模拟数据集 3 v 优化直方图 v 一优化直方图 1 9 要求使各桶的方差和最小 即假设数据集中各元素的值为 h 吃 屹 然后将数据集划分成多个桶 令岛表示元素一所在桶的平均值 v 一优 化直方图要求使 m 一岛 2 的值最小 文献 2 0 1 提出了基于动态规划的算法 需要多次遍历数据集 且时间和空间复 杂性均较大 文献 2 1 改进文献 9 o l 假设数据集中的元素已经排过序 仅仅需要 次线性的空间和时间复杂度 文献 2 2 则进一步改进文献 2 1 使在任意数据集下 均可用次线性空间复杂度获得v 优化直方图 4 指数直方图 指数直方图 2 2 是最早用来生成基于滑动窗口模型的概要数据结构 它能够解 决滑动窗口模型下的很多问题 例如基本计数 b a s i cc o u n t i n g 问题 求和问题 2 引 方差问题 2 4 j 等 与传统直方图不同 它是按照元素的到达次序构建桶 并且桶的容量按照不 同级别呈指数递增 同时各个级别桶的个数均不超过一个预定义门槛值 如果某 级别桶数目超过该值 则合并本级别一对最早生成的桶 创建一个高级别桶 这 样可能会导致更高级别桶的连锁合并操作 另外指数直方图仅维护未过期的桶 一旦最 旧 的桶中的所有元素都过期 就删除该桶 释放空间 2 1 2 3 小波方法 小波分析是近几年迅速发展起来的新兴学科 具有深刻的理论意义和广泛的 应用范围 它根据输入的模拟量 变换成一系列的小波参数 并且少数几个小波 参数拥有大部分能量 2 5 1 根据这一特性 可以选择少数小波参数近似地代替原始 信号进行处理 小波种类很多 最常见且最简单的是哈尔小波 h a a rw a v e l e t 文献 2 6 1 提出了一种在数据流上基于哈尔小波技术生成直方图的算法 该算法 对整个数据集进行小波变换 生成一系列的小波参数 并且有选择地保留有限个 高能量参数 近似模拟原始数据集 该算法不能在理论上保证误差范围 文献 2 7 提出一种算法 对于时序数据 只需要保存最多l o g n 个计数器 即仅需 o b l o g n 的存储空间 就能够获得任一时刻b 个最大的小波参数 文献 2 7 1 提 出的算法则能够以概率1 6 保证结果的误差控制在一个小范围内 其中 6 是一 个接近于0 的用户定义参数 2 1 2 4 哈希方法 哈希方法 即定义一组哈希函数 将数据从一个范围映射到另一个范围 是 第1 0 页 国防科学技术大学研究生院工学硕士学位论文 一个常用手段 利用哈希函数生成概要数据结构的方法主要有b l o o mf i l t e r 方法 1 2 9 s k e t c h 方法f 3 0 和f m 方法 3 2 1 3 滑动窗口 对于滑动窗口技术的使用需求来自于算法和应用 在算法方面 滑动窗口减 少了算法处理的数据量 在应用方面 有些应用只对近期的数据感兴趣 如股票 数据和感知网 要求算法以当前时间为终点 对某个滑动窗口内的数据进行处理 2 1 3 1 滑动窗口模型i 硒i 在每个时间点t 某数据记录到达 该数据记录在时间t n 过期 n 为窗口的 大小 窗口为数据流中元素的一个连续子集 图2 2 为滑动窗口在数据流上的示 例阳 r l m e ol l 1 oc 1 l l lo 1 0 qo o loo0 00 11 0 w i n d o ws i z e 8 图2 2 数据流上滑动窗口示例陋1 为了说明滑动窗口模型对当前处理的数据的影响 我们形式化地描述了指数 衰退及滑动窗口衰退在时间t 及t 1 的算法输入值 作为对比 设数据项五 置 五 五 以流形式到达 函数f x f n o w 时间点t 的输入为 厂 五 l f 厂 五 2 t 鼍 3 t 厂 置 t t 时间点 什l 的输入为 五 l t 1 厂 置 2 1 厂 墨 3 f 1 厂 置 f 1 1 指数衰退 f x n o w 2 0 彤一 x 时间点t 的输入为 2 卜1 书五 2 卜2 辜置 l 2 奉五 l z 时间点t 1 的输入为 2 五 2 卜1 宰置 1 4 奉置 l 1 2 奉置 置 l 滑动窗口衰退 f x r n o w x 如果n o w f b j 的元素都被记录 且f z f i s n 在实 际应用中 大部分数据的出现频率都较低 由于该算法不需要记录出现频率较低 的数据 因此这样不仅能够节省计算空间 同时又保证了输出的质量 g i a n n e l l 等 岭0 j 基于数据流的时间窗口模型 实现了多时间粒度的频繁项挖掘 2 2 数据流突发 b u r s t 检测 数据流突发检测即发现数据流中明显偏离于其他邻近窗口聚集值的位置 其 应用背景广泛 如在天文学中对g a m m a 射线的突发检测 在网络管理中及时发现 在一定时间内发生的过大的访问量 在金融领域中检测短时间内出现的股票高交 易量或较大幅度的价格波动等等 针对其广泛的应用背景 数据流b u r s t 检测相关 的研究在短时间内也受到了广泛的关注 主要分为两种 一是基于时间序列的检 测算法 主要应用于天文 通信 金融 医药等领域 再就是基于内容的检测算 法 主要应用于文本流的突发检测 比如电子邮件 b l o g 等等 2 2 1 基于时间序列的检测算法 2 211 基于小波分析的检测算法 第1 4 页 国防科学技术大学研究生院工学硕士学位论文 基于小波分析的检测算法相对比较成熟 y u n y u ez h u 等人1 5 l j 提出在弹性时间 窗口 e l a s t i cw i n d o w s 上监测数据流 并设计了一种新的数据结构s w t s h i f t e d w a v e l e tt r e e 用来发现在不同时间尺度范围内发生的持续时间长短不同的聚集爆发 a g g r e g a t eb u r s t s w t 通过在原有的小波结构上加入与其大小相同的冗余部分完 成构建 使得在最底层发生的任意长度的b u r s t 都能被上层某个时间窗覆盖 如 图2 3 所示 因此算法可以检测任意起点且任意长度的窗口的突发 不会有漏报现 象 但是它要求时间序列中的值均为非负数且聚集值单调增加 即仅能检测单边 突发 在线检测处理算法的时间复杂度为o n 后 空间复杂度为 玎一1 l o g 以 其 中n 为滑动窗口大小 k 为检测到的突发