（计算机科学与技术专业论文）高速网络主机基数分布检测方法研究.pdf

r 舻 、 飞 d e t e c t i n gt h ec a r d i n a l i t yd i s t r i b u t i o no fh o s t s i n h i g h s p e e dn e t w o r k at h e s i ss u b m i t t e dt o d a l i a nm a r i t i m eu n i v e r s i t y i np a r t i a lf u l f i l l m e n to ft h er e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro f e n g i n e e r i n g b y g u o s h u m i n g ( c o m p u t e rs c i e n c ea n dt e c h n o l o g y ) t h e s i ss u p e r v i s o r ：p r o f e s s o rl i uw e i j i a n g j u n e2 0 1 1 ，。r v y 矿 y z 、 一 4 弋 - ： 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果，撰写成硕士 学位论文 = =直逮圆终圭扭基筮岔查捡型友洼班塞：。除论文中已经注明引用的内 容外，对论文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本论文中不 包含任何未加明确注明的其他个人或集体已经公开发表或未公开发表的成果。本声明的法律 责任由本人承担。 学位论文作者签名： 学位论文版权使用授权书 本学位论文作者及指导教师完全了解大连海事大学有关保留、使用研究生学位论文的规 定，即：大连海事大学有权保留并向国家有关部门或机构送交学位论文的复印件和电子版， 允许论文被查阅和借阅。本人授权大连海事大学可以将本学位论文的全部或部分内容编入有 关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论文。同意将本 学位论文收录到中国优秀博硕士学位论文全文数据库( 中国学术期刊( 光盘版) 电子杂志 社) 、中国学位论文全文数据库( 中国科学技术信息研究所) 等数据库中，并以电子出版物 形式出版发行和提供信息服务。保密的论文在解密后遵守此规定。 本学位论文属于：保密口在 年解密后适用本授权书。 不保密口( 请在以上方框内打“4 ”) 论文作者签名 导师签名： 期：加1 年 月 y z v y ，曲 中文摘要 摘要 主机基数是网络测量领域里新提出的概念。主机基数检测对于设计高效的流 量工程方案有着重要的意义。随着互联网的蓬勃发展，网络入侵事件频繁发生， 如蠕虫传播、分布式d d o s 攻击、端口扫描等。这些攻击事件在短时间内产生大 量的流量链接，导致网络堵塞甚至瘫痪。如扫描式蠕虫在进行传播时，被感染主 机通常在短时间内向大量的其他主机发送分组，这时网络中的主机基数分布会发 生变化。实时监测网络中的主机基数分布信息对于网络操作和管理有重要的作用。 本文结合了哈希( h a s h ) 、b l o o mf i l t e r 和数据流算法等技术提出了基于哈希 的测量主机基数分布的数据流算法，此算法可以应用在主机数量巨大的高速网络 中。我们的算法包含三个模块，分别是过滤模块、计数模块、输出模块。网络中 的数量巨大的报文首先到达过滤模块，该模块用四个哈希函数的b l o o mf i l t e r 对全 部报文进行过滤处理，滤除那些对测量没有意义的报文，确保每个流最多一个报 文可以通过，并且我们精心设计的四个哈希函数显著降低了因哈希冲突导致的流 丢失的现象。在计数模块中，对通过过滤模块的报文进一步哈希计数处理，得到 基于报文s i p 的基数估计值。输出模块将计数模块的结果以 的形式输出。 为了测试算法的性能，我们采用了三个不同的数据源分别进行试验。由于哈 希函数存在着不可避免的冲突误差，我们用e m 算法对实验结果进行了估计处理， 并将估计前后的实验结果分别与真实数据进行对比。采用加权平均相对差作为测 量测度，对实验所得的数据进行分析。实验结果表明，本文提出的基于哈希的数 据流算法可以准确、高效地检测高速网络中主机基数的分布信息。 、 丫： 关键词：主机基数分布；哈希；。p 流； 穸 t 、 ， v 、 l 心 英文摘要 a b s t r a c t i nt h ef i l e do fn e t w o r km e a s u r e m e n t ，t h ec a r d i n a l i t yo fh o s t si san e wc o n c e p t w h i c hh a sb e e np r o p o s e dr e c e n t l y d e t e c t i n gt h ec a r d i n a l i t yi nh i g h - s p e e dn e t w o r ki s v e r yi m p o r t a n ti nd e v e l o p i n ge f f e c t i v ea n de f f i c i e n tt r a f f i ce n g i n e e r i n gs c h e m e s w i t h t h er a p i dg r o w t ho fi n t e r n e t ，i n t e r n e ta t t a c k ss u c ha sd i s t r i b u t e dd e n i a l - o f - s e r v i c e ( d d o s ) a t t a c k sa n dw o r ma t t a c k sa r ei n c r e a s i n gi ns e v e r i t y t h e s ea t t a c k sg e n e r a t ea l o to ft r a f f i cw i t h i nas h o r tt i m e ，w h i c hm a yc a u s en e t w o r kc o n g e s t i o n f o re x a m p l e ，a c o m p r o m i s e dh o s td o i n gf a s ts c a n n i n gf o rw o r mp r o p a g a t i o no f t e nm a k e sa nu n u s u a l l y h i g hn u m b e ro fc o n n e c t i o n st od i s t i n c td e s t i n a t i o n sw i t h i nas h o r tt i m e ，a n dt h i sm u s t c h a n g et h ec a r d i n a l i t yd i s t r i b u t i o no fh o s t si nt h en e t w o r k t r a c k i n ga n dd e t e c t i n gt h e r e a l - t i m ec a r d i n a l i t yd i s t r i b u t i o no fh o s t sa n do b t a i n i n gt h ei n f o r m a t i o no ft h e s e c a r d i n a l i t ya r ev e r yu s e f u lf o rn e t w o r ko p e r a t i o na n dm a n a g e m e n t i nt h i sp a p e r , w ec o m b i n eh a s h 、b l o o mf i l t e ra n dd a t as t r e a ma l g o r i t h m s ，p r o p o s ea d a t as t r e a ma l g o r i t h mw h i c hi sh a s h b a s e da n dc a nm e a s u r et h ec a r d i n a l i t yd i s t r i b u t i o n o fh o s t s o u ra l g o r i t h mc a nw o r kw e l li nh i g h s p e e dn e t w o r kw h e r eh a sah u g en u m b e r o fh o s t s o u ra l g o r i t h mc o n s i s t so ft h r e em o d u l e s ，n a m e l y , f i l t e rm o d u l e ，c o u n t e r m o d u l ea n do u t p u tm o d u l er e s p e c t i v e l y t h el a r g en u m b e ro fp a c k e t si nn e t w o r kf i r s t r e a c ht h ef i l t e rm o d u l ew h i c hi sb a s e do nb l o o mf i l t e ru s i n gf o u rh a s hf u n c t i o n st of i l t e r a l lp a c k e t s ，t of i l t e rm e a n i n g l e s so n e sf o rt h em e a s u r e m e n t ，a n de n s u r et h a tu pt oo n e p a c k e tb e l o n gt oe a c hi pf l o wc a np a s st h ef i l t e rm o d u l e t h ef o u rh a s hf u n c t i o n sw e d e s i g n e dc a r e f u l l ys i g n i f i c a n t l yr e d u c et h ep h e n o m e n o no ff l o wl o s sa sar e s u l to fh a s h c o l l i s i o n i nc o u n t e rm o d u l e ，t h ep a c k e t sh a v ep a s s e dt h ef i l t e rm o d u l ea r ef u r t h e r p r o c e s s e d t h u sa l g o r i t h mo b t a i n ss i p b a s e dc a r d i n a l i t ye s t i m a t i o n t h eo u t p u tm o d u l e o u t p u t st h er e s u l t sb e l o n gt oc o u n t e rm o d u l ei nt h ef o r mo f p a i r s t ot e s tt h ep e r f o r m a n c eo ft h ea l g o r i t h m ，i nt h i sp a p e r , w ed oe x p e r i m e n t sb y u s i n g p a c k e th e a d e rt r a c e sg a t h e r e da tt h r e ed i f f e r e n tl o c a t i o n so ft h ei n t e m e t b e c a u s et h e r e e x i s t si n e v i t a b l ec o n f l i c te r r o ri nh a s hf u n c t i o n , w ee s t i m a t et h ee x p e r i m e n t a lr e s u l t s b a s e do ne m a l g o r i t h m ，a n dm a k et h ee x p e r i m e n t a lr e s u l t sb e f o r ea n da f t e re s t i m a t i o n , r e s p e c t i v e l y , c o m p a r ew i t ht h ea c t u a ld a t a w ea d o p tt h ew e i g h t e dm e a nr e l a t i v ed i f f e 一一 茎奎塑墨 一 _ _ _ _ _ - i - - _ _ - - _ _ - - l - _ _ _ - i _ _ _ _ _ _ - _ _ - _ - - l _ _ - _ l - _ _ _ _ _ _ - - _ _ _ _ 一一 一 r e n c e ( w m r d ) a so u re v a l u a t i o nm e t r i c t h ee x p e r i m e n t a l r e s u l t ss h o wt h a to u r a l g o r i t h mc a nt r a c ka n dd e t e c tt h er e a l t i m ec a r d i n a l i t yd i s t r i b u t i o no f h o s t sp r e c i s e l y a n de f f i c i e n t l y k e y w o r d s ：t h ec a r d i n a l i t yd i s t r i b u t i o no fh o s t s ；h a s h ；i pf l o w y ，严 r q ，、， 目录 目录 第l 章绪论l 1 1 网络测量的必要性1 1 2 主机基数的相关定义一2 1 2 1 流的定义2 1 2 2 超点的定义4 1 2 3 主机基数的定义5 1 3 主机基数的研究背景及意义5 1 4 论文的研究内容及组织结构7 第2 章网络测量的相关技术8 2 1 哈希技术( h a s h ) 8 2 2b l o o mf i l t e r 9 2 2 1 标准的b l o o mf i l t e r 9 2 2 2b l o o mf i l t e r 的精确性分析1 2 2 3 本章小结1 2 第3 章主机基数分布的相关算法研究1 3 3 1 双过滤结构探测端口扫描的算法1 3 3 2 抽样和数据流相结合的主机基数检测算法15 3 2 1 流抽样和b i t m a p 结构相结合的算法1 6 3 2 2 比特矩阵结构和报文抽样方式相结合的算法l8 3 3 基于依赖抽样的并行过滤算法2 0 3 3 1 两级过滤2 l 3 3 2 计算候选主机的基数2 3 3 4 数据流与统计推断相结合的主机基数估计算法2 6 3 4 1 数据流模块2 6 3 4 2 统计推断2 8 3 5 本章小结。2 9 第4 章基于哈希的数据流算法3 0 4 1 算法描述3 0 4 1 1 算法的总体设计3 0 4 1 2 算法的具体实施3 l 4 2 算法分析3 6 y 0 一 。一 ， 6 7 8 9 9 o o 3 7 1 2 2 2 3 4 8 3 3 3 3 3 4 4 4 4 5 5 5 5 5 5 5 、l 高速网络主机基数分布检测方法研究 第1 章绪论 1 1 网络测量的必要性 i n t e r n e t 是将全球数以万计的相互独立的终端系统通过通信设备和线路互联在 一起的，网络终端应用多样的通信协议、网络操作系统等软件实现了世界范围的 信息交换与资源共享。t c p i p 技术问世于上世纪8 0 年代，它将一系列的网络技术 和管理域进行了统一，它自身的开放性造就了t c p i p 网络体系结构的普及【l 】。本 世纪初，伴随着新一代互联网的建设与发展，网络中活跃主机的数目与日俱增， 在线服务种类越来越多，网络流量和网络行为也变得纷繁复杂。在巨大的网络流 量当中还存在着相当数量的恶意流量，这些恶意流量夹杂在正常流量中，使用户 在无从察觉的同时蒙受了巨大的损失。 计算机网络的应用涉及社会生活的各个方面。当前对经济和文化生活影响最 大的网络应用列举如下。 ( 1 ) 办公自动化：网络化办公系统的主要功能是实现信息共享和公文流转。 其功能包括电子签名、公文处理、日程安排、会议管理、档案管理、财务报销、 信息发布和安全检索等模块。在目前大力推广政府上网、企业上网的情况下，办 公软件具有越来越广阔的应用环境。 ( 2 )电子数据交换：电子数据交换( e l e c t r o n i cd a t ai n t e r c h a n g e ，e d i ) 是一 种新型的电子贸易工具，是计算机、通信和现代管理技术相结合的产物。他通过 计算机通信网络将贸易、运输、保险、银行和海关等行业信息表现为国际公信的 标准格式，实现公司之间的数据交换和处理，并完成以贸易为中心的整个交易过 程。e d i 传输的文件具有跟踪、确认、防篡改、防冒领功能，以及一系列的安全保 密功能，并有法律效力。中国共用电子数据交换业务网( c h i n a e d i ) 是面向社会 各行业开放的公用e d i 网络，其应用范围涉及电子报关、电子报数、银行托收、 港口集装箱运输和铁路运输，以及制造业和商业的订单处理等。 ( 3 ) 远程教育：远程网络教学是利用因特网技术，与教育资源相结合，在 计算机网络上进行的教学方式。通过网络进行教育最明显的优势是可以使有限的 第1 章绪论 教育资源成为近乎无限的、不受时空和资金限制的、人人可以享受的全民教育资 源。网络教学利用现代通信技术实施远程交互作用，学习者可以与远地的老师通 过子邮件、b b s 、等建立交互联系，学员之间也可进行类似的交流和互助学习。 ( 4 ) 娱乐和在线游戏：随着宽带通信与视频演播的快速发展，网络在线游 戏正在成为因特网娱乐的重要组成部分，也是互联网最富群众性和最有潜力的赢 利点。 网络测量是网络安全领域的主要课题，其目的是通过终端设备上运行的程序 或软件从完全无形的网络流量中获得能够准确描述流量各方面特性的数据，再利 用数理统计等方法对获得的数据进行分析，最后得到对被测量网络的总体描述。 由于网络流量巨大、网络行为复杂，对网络的完全监控和完整跟踪已经不可能了【2 1 。 但是网络测量仍然是探知网络运行状态，对网络实施全面管理和维护的重要手段。 随着网络用户的持续暴增，针对各类用户不同特点的网络服务也日益兴起，给人 们带来无限方便的同时也给网络测量工作带来了新的挑战。首先是针对网络安全 和异常检测的网络测量。终端计算机感染病毒或者受到病毒破坏的可能性急剧增 加，网络黑客行为无孔不入，信息公共基础设施面临安全威胁，异常检测 3 】是指先 对正常行为建立模型，从获取的数据中发现偏离正常范围的部分，这部分行为定 义为异常。其次是针对网络中实时流量的监测。在主干网中，i s p 经常会发现有拥 塞现象出现，这时需要通过网络测量重新分配路由来达到控制拥塞的目的。再次 是针对q o s 敏感应用和提供q o s 保证的网络测量。不同的网络服务对网络的性能 有所不同，为了能够满足用户所需要的高质量的端到端服务，必须对当前网络动 态参数有足够的了解，这就需要对网络进行实时的性能评估。 1 2 主机基数的相关定义 1 2 1 流的定义 终端计算机从网络获取信息时，整体的信息先要被分解成无数的小片段才能 够在网络线路中传输。i n t e r n e t 中的信息交换就是通过无数个微小的由t c p i p 封装 的报文( p a c k a g e ) 实现的。 定义1 1 i p 流：是指符合特定的流规范( s p e c i f i c a t i o n ) 和超时( t i m e o u t ) 约束的一 高速网络主机基数分布检测方法研究 系列数据报文的集合【4 ，一l 。如图1 1 所示。 假设在网络线路中设置一个观测点，通过这个观测点的流量中会包含大量的 报文，在传输过程中，每个报文的源i p 、源端口、目的i p 、目的端口、协议类型 等字段是始终不变的，以上五个字段称为报文的五元组。通常用五元组来标识一 个流。因此，流是在某段时间内通过某条线路的具有相同流标识的报文集合。 报文1 报文k报5 r n时间轴 报文流持续时间 图1 1 流定义图 f i g 1 1f l o wd e f i n i t i o ng r a p h 超时 网络中某时间点的流量无法预先估计，因此流量的大小不是时间的函数。实 际情况中，往往由于终端用户的正常请求或者恶意病毒破坏导致流量激增，但是 路由器以及其他节点的转发处理能力有限，这就导致了本应属于同一个流的相邻 报文间隔了过长时间而不能相继到达。 定义1 2 流超时：同一个流中相邻报文的相继到达的时间间隔超过了规定的 时间上限1 5 】。 流超时的情况一旦出现，说明网络中有超过负载能力的大流量，这时终端、 路由器和其他节点会采取相应的对策进行流量控制。 定义1 3 流长度：指在一定的超时约束内，一个流中所包含的报文总数。例 如：一个含有l o 个报文的流，这个流的长度为1 0 5 l 。 不同流的流长度大小不一，但是，多数情况下对网络性能产生重大影响的是 那些自身包含大量报文的巨型流，这样的流被定义为长流。 定义1 4 长流：如果某个流中包含的报文总数或总字节数超过了预先定义好 的一个值( 这个值叫做阈值) ，我们称这个流为长流【5 l 。 对于流的测量，比如：活跃流的数量，长流的大小和流标识，流的分布等是 第1 章绪论 网络测量和网络安全的基础。在高速网络中用哈希表维护每流信息来跟踪流的统 计信息对系统资源的消耗相当巨大【6 1 ，测量这样的信息是巨大的挑战。 众多文献研究表u f j t t , s , 9 1 ，i n t e m e t 中i p 流流长均服从重尾分布。重尾分布是指 集合中的大部分元素出现的次数都比较少，而只有少部分元素出现频率非常高， 并且，这少部分元素的数量和成为集合的绝大部分f l o 】。重尾分布应用到流的概念 中是指：在整体流量中，流数的大多数是短流，这些短流的数量虽然多，但每个 流所包含的报文数非常少，而在仅占流数一小部分的长流里却包含了巨大的报文 数目，以至于数目很少的长流承担了网络负载的主要部分。 1 2 2 超点的定义 网络中诸如分布式拒绝服务( d d o s ) 攻击和蠕虫( w o r m ) 攻击等恶意黑客行 为日益严重，网络安全监控可以用来检测剧烈的流量模式变化，这种剧烈变化往 往是恶意攻击的暗示，还可以识别带有恶意行为的主机或者被病毒感染的受害者。 网络安全监控在防止这些恶意攻击或者减轻恶意行为的后果方面发挥了重要作 用。在网络环境日趋复杂的背景下，超点作为网络安全领域的新概念应运而生。 定义1 5 超点：在一定的测量时间区间内，如果某台源主机连接了至少给定数 目的目的主机、或者某台目的主机连接了至少给定数目的源主机，这台源或目的 主机被称为超点i l l j 2 。 例如，一台感染蠕虫病毒的受害主机为实现蠕虫病毒的传播，在短时间内的 快速扫描可以造成面向大量不同目的地的连接，s l a m m e rw o r m 每秒可以达到 2 6 0 0 0 次扫描 1 3 】。我们把这样的主机称为超点。 假设在某监测点截获以下数据流： p = ( a c ) ( c a ) ( a b ) d b ) b d ) ( f a ) ( c b ) i b 。a ) e b ) ( c a ) ( b a ) e a ) e b ) ( a c ) ( b d ) ( c d ) b a ) ( a b ) ( b 。c ) ( d a ) ( c b ) b f ) ( c g ) c f ) 此数据流集合中包含2 4 个元素，每个元素代表一个报文，第一个字母表示报 文对应的源i p 标识，第二个字母表示报文对应的目的i p 标识。将此数据流采用 b l o o mf i l t e r 进行处理得到以下报文集合： q = = ( a b ) ( b a ) ( d b ) ( b ，d ) ( e a ) ( c b ) ( e b ) c a ) e a ) ( a 0 ( c d ) l b c ) d a ) 高速网络主机基数分布检测方法研究 ( b f ) ( c g ) ( c f ) 我们采用每个报文对应的源i p 标识进行聚合，获得如下集合： s = ( a 2 ( b 。4 ) ( d 。2 ) e1 ) ( c 5 ) i e 2 ) 其中数字代表源i p 所连接的目的i p 的数目。如果我们定义超点检测的阈值为 3 ，那么源i p 为b 和c 的主机的对外连接数目超过阈值，我们依此认定源i p 为b 和c 的主机为超点。 1 2 3 主机基数的定义 近年来，网络测量领域的科研人员一直在不懈的努力，使网络测量技术能够 紧跟高速网络发展的步伐。为了从网络流量中获得网络中主机的宏观行为分布， 2 0 0 6 年，k e i s u ki s h i b a s h i 等【1 4 1 给出了找出具有最大n 个基数主机的算法，这是第 一次明确提出网络中主机基数概念。而在这之前的一些工作中【1 5 , 1 6 , 1 7 的基数指的数 据库或文件具有重复元素的集合的势。 定义1 6 主机基数( h o s tc a r d i n a l i t y ) 是指这台主机同其它主机间存在的不 同i p 流的数量。 主机基数反映了该主机在通信方面的连通模式。在高速网络环境中，了解网 络主机联通性的总体行为对于网络监控和流量工程来说是非常重要的。这个总体 t 、。 行为的一个主要特点是不同通信终端或流终端的主机基数分布。例如：在主机所 在的网络中，当蠕虫爆发时端口扫描导致许多主机基数增加，当发生d d o s 攻击 时受害者的目的i p 收到来自于大量不同源i p 的链接，这些恶意行为都会对网络流 量产生影响，从而改变了主机基数的分布。 1 3 主机基数的研究背景及意义 在1 9 9 3 年，c l a f f y l l 8 1 系统研究抽样技术在网络流量统计分析中的应用，分析系 统抽样、简单随机抽样和分层抽样技术用于估计报文大小分布和报文到达时间分 布。1 9 9 8 年c o z z a n i t l 9 1 提出使用模式匹配技术抽取a t m 位元。在2 0 0 3 年的i m c 会议上，n i c o l a sh o h n 2 0 】比较了基于报文抽样和基于流抽样两种抽样方法的优缺 点，指出对于流长度分布这类的二阶统计量基于报文抽样估计的困难。a b h i s h e k k u m a r 等2 1 1 在2 0 0 4 年建立i p 流哈希映射，使用贝叶斯统计估计流的大小分布情 第1 章绪论 况。2 0 0 4 年t a t s u y am o r i 在文献【2 2 i 提出了一个新的识别长流的机制。这一机制的 关健是由抽样流的报文数来确定这个原始流是否为长流的阀值。这一阀值是通过 由b a y e s 定理计算在平衡错误肯定和错误否定的基础上得到的。2 0 0 5 年 v e n k a t a r a m a n 等 】提出超源i p 检测算法，他们采用流抽样算法随机抽样流，以维 护抽样到的所有流和i p 信息。2 0 0 5 年z h a o 等【2 3 】提出了抽样和数据流算法相结合 的超点检测方法。在2 0 0 6 年和2 0 0 7 年y a n gl i l i 等在文献1 2 4 , 2 5 分别讨论了流长度 和流长度分布的估计问题。2 0 0 7 年k a m i y a m a 等【2 6 】也提出了一个基于b l o o mf i l t e r 的参数化的超点检测算法。在2 0 0 9 年i n f o c o m 会议中j i nc a o 等【2 7 】提出一种新 的依赖对抽样模式( d e p e n d e n tp a i rs a m p l i n gs c h e m e ) 来识别高基数主机，a i y o u c h e n 等【2 8 】给出了一种通过构造连续的f ms k e t c h 来估计主机基数分布的数据流算 法。 中国互联网络信息中心( q 州i c ) 发布了第2 7 次中国互联网络发展状况统计 报告【2 9 1 。截至2 0 1 0 年1 2 月，中国网民规模达到4 5 7 亿，较2 0 0 9 年底增加7 3 3 0 万人；互联网普及率攀升至3 4 3 ，较2 0 0 9 年提高5 4 个百分点，如图1 2 所示。 4 0 o o 3 5 0 0 a o 0 0 一 2 5 o o 2 0 0 0 冀 1 5 0 0 l o 0 0 誓 5 0 0 o 0 0 4 5 r 3 0 一网民数 。辫 + 互联网昔及率 翳一9qfll)o 一霪露霍圈曩露墨霉蓥翟露 ，矗矿昏扩矗矗矿办扩 图1 2 中国互联网民数和互联网普及率 f i g 1 2t h ei n t e r n e tu s e r sn u m b e ra n di n t e r n e tp e n e t r a t i o nr a t eo f c h i n a 在我国网民数量逐年增加，网络成为人们相互沟通、感知世界的主要桥梁， 州 啪 嘲 耐 矗 _ 嘶 _ 啪籼姗蝴蝴o 高速网络丰机基数分布检测方法研究 因此更加凸显了网络安全的重要性。网络的安全关系到每一台终端计算机的运行 状态，关系到公民的隐私及其合法利益，关系到国家的政治经济决策和社会的平 稳健康发展。网络管理人员希望更准确地探知网络流量中的行为状况，更细致地 对网络设备实施配置和日常管理，这就需要对网络做出有针对性的精确测量和分 析【3 2 1 。 主机基数概念的提出以及后续的研究工作能够为网络测量领域注入新的活 力。在超点理论的基础上，主机基数理论可以获得针对整体网络更加宏观的测量 信息。主机基数理论为今后的网络测量领域提供了把握整体行为分布的思想。 1 4 论文的研究内容及组织结构 本论文研究高速网络中主机基数跟踪问题，将在分析现有研究成果的基础上， 提出针对主机基数检测的新算法，并用真实网络数据验证算法性能。在高速互联 网络环境中测量和分析的基础理论及其应用方面取得一些创新性成果。 本论文各章节安排如下： 第一章绪论。本章以当前互联网的发展现状为基础，阐述了网络测量在互联 网应用中的必要性，同时还介绍了流、超点、主机基数等网络测量领域的相关概 念。 第二章网络测量的相关技术。本章介绍了网络测量领域的两种技术，哈希、 b l o o mf i l t e r ，这两种技术是本文提出的算法的理论基础。 第三章主机基数分布的相关算法研究。本章介绍了四个与网络测量中主机基 数密切相关的算法，分别是：双过滤结构探测端口扫描的算法，抽样和数据流相 结合的主机基数检测算法，基于依赖抽样的并行过滤算法和数据流与统计推断相 结合的主机基数估计算法。 第四章基于哈希的数据流算法。本章介绍了我们提出的基于哈希的数据流算 法，并对算法的整体设计、算法的实施过程、算法的分析、算法的误差估计及实 验结果做了详细论述。 第五章总结与展望。总结本论文的创新点及主要工作，并对未来的工作进行 展望。 第2 章网络测量的相关技术 第2 章网络测量的相关技术 2 1 哈希技术( h a s h ) 随着高速网络的不断发展，对网络中的中继节点以及针对网络实时流量进行 检测的设备等要求越来越高，在o c - 7 6 8 ( 4 0g i g a b i t s s e c o n d ) 网络中，实时流量的平 均单个报文的到达时间为8n s 3 0 , 3 h ，要想记录并维护每个流的信息就需要高性能的 c p u 和大量存储空间，而这几乎是不可能的，哈希技术解决了这个难题。应用在网 络中的哈希技术又称为报文过滤技术，是一种高效的实时信息处理技术，通过哈 希技术可以把链路中数据量庞大的流标识映射到较小的空间进行存储，这样解决 了实时系统开销的问题，非常适合高速网络的应用。b l o o mf i l t e r 数据结构的提出 就是以哈希技术为基础的【3 3 】。 哈希函数： ，朋一d o r d 可例 ( 2 1 ) 其中m 为任意长的b i t 串，作为函数的输入，哈希函数厂通过九次迭代后输出 固定长度的字符串，哈希函数的输出空间一般远小于输入空间。哈希算法是单向 的、不可逆的，并且输入与输出是对应关系。 哈希算法好坏的衡量标准： ( 1 ) 均匀性 均匀性是哈希函数的重要测量指标，是指哈希函数将输入空间映射到输出空 间的均匀程度。研究人员总是期望哈希函数的均匀性足够好，最理想化的就是输 出空间的均匀分布。良好的均匀性可以减少哈希聚焦现象，从而降低哈希冲突， 但是现实中无法实现完全的均匀分布。 ( 2 ) 冲突性 哈希算法的输入空间远比输出空间大得多，因此不同的输入可能得到相同的 哈希值，这就是是冲突的含义。冲突只能尽量减少不能完全避免，均匀的哈希函 数可以减少冲突，冲突率也是哈希算法的重要指标，哈希算法的冲突率越低，对 最终结果影响越小，系统的性能越好。 高速网络手机基数分布检测方法研究 ( 3 ) 计算速度 高速链路中，哈希算法对实时流量的处理速度直接体现了算法性能的好坏。 采用硬件哈希表具有成本低、扩展性好等优点，同时哈希算法也受到网络系统资 源的限制，测量过程中消耗的系统资源越来越多。 2 2 bio o mfjit e r b l o o mf i l t e r 是一个精妙的随机化的数据结构，可以简明的描绘一个数据集以 提供近似的成员查询。1 9 7 0 年b u r t o nb l o o m t 4 0 】为了解决拼写核对问题发明了 b l o o mf i l t e r ，最初只有数据库优化方向的研究应用过b l o o mf i l t e r 。然而，近年来 b l o o m f i l t e r 突然被人量应用在大规模网络应用中【4 1 , 4 2 1 ，比如路由查找1 4 2 1 、网络测 量管理 4 3 4 4 j 、网络入侵检测4 5 1 、流分布估计【2 i 】等。 2 2 1 标准的b 1 0 0 1 1 1f i i t e r s 是具有n 个元素的一个集合s = 缸j ，x 2 x n ) ，b l o o mf i l t e r 将s 描述成一个长 度为m 的b i t 数组，初始时数组的m 位全部置0 。b l o o mf i l t e r 用k 个独立的哈希 函数h i ，h 2 j ，h k 每个哈希函数值域范围为 n j ，m j ) 。我们做一个很自然的假设： k 个哈希函数将每一个需要辨别的元素随机并且唯一映射到 仍j ，m j ) 。对于每一 个元素x ，x ，j ，k 个哈希函数办 h 2 , ，h 的运行结果拓( x ) ，其中，i k ，在b i t 数组中被置l 。标准的b l o o mf i l t e r 如图2 1 所示。 b i t 数组中的某个位可能被置1 多次，只有第一次是从0 到l 的变化，后面的 置l 操作不起作用。为了核对一个元素y 是否属于集合s ，我们检查所有的 ，) ， 其中j isk ，是否已被置l ，如果没有全部被置l ，那么y 一定不是s 中的元素。 如果检查发现h 。( 夕) 已全部被置l ，这时我们认为y 是s 中的元素，虽然这里会有 错误肯定( f a l s ep o s i t i v e ) 的可能。这里的错误肯定是指y 的确不是s 中的元素， 但经过七个哈希函数运算后，数组中的七个b i t 位均已被置l 。由此可见，b l o o mf i l t e r 会产生错误肯定，在许多实际应用中，错误肯定的概率只要充分小是可以被接受 的。 第2 章网络测量的相关技术 图2 1 标准b l o o mf i l t e r f i g 2 1s t a n d a r db l o o mf i l t e r 综上所述，b l o o mf i l t e r 的具体工作流程包括b i t 数组初始化( i n i t ) ，元素插入 ( i n s e r t ) 和元素查询( s e a r c h ) _ - - - 个过程。 ( 1 ) b i t 数组的初始化 b i t 数组的初始化是在存储空间中为b l o o mf i l t e r 开辟一段区域存储b i t 数组形 式的哈希表，并将b i t 数组中所有二进制位初始化为0 ，b l o o mf i l t e r 的初始状态如 图2 2 所示，其伪代码如下： b i t v e c t o rb f i n i t ( i n tm ) 初始化成为椭比特向量v 表示 b i t v e c t o r l 嘲； f o r ( i = o ；i 聊；f 十卜) 哪= o ； ) 图2 2b l o o mf i l t e r 的初始状态 f i g 2 2i n i t i a ls t a t eo f b l o o mf i l t e r ( 2 ) 元素插入 元素插入是把原本属于集合s 中的元素依次经过k 个哈希函数的运算，将与 哈希运算结果相应的b i t 数组中的二进制位置1 。如图2 3 所示，当k = 3 时，元素 高速网络主机基数分布检测方法研究 工卜x 2 被插入到b i t 数组。其伪代码如下： b i t v e c t o rb f _ i n s e r t ( i n tm ) 对数据集合采用长为聊的比特向量v 表示 扣，( ，= o j ，l + l ；+ + ) f o r ( i = l ；f k + 1 ；i + + ) v l h , ( x j ) = l ； r e t u r n 矿： ) 图2 3 元素的插入过程 f i g 2 3e l e m e n ti n s e r tp r o c e s s ( 3 ) 元素查询 元素查询是确定y 是否是集合s 中的元素的过程。用k 个哈希函数处理元素y ， 如果b t 数组中七个相应的二进制位均为1 ，那么我们认为y 是s 中的元素，即y s 。 如果b i t 数组中k 个相应的二进制位不全为l ，那么y 不属于s 。如图2 4 所示，查 询j ，、肋两个元素，拓3 ，图中结果为 不属于集合岛船有可能属于集合s ，也 有可能正好是错误肯定。其伪代码如下： b o o l e a nb f _ i o o k u p ( b i t s t r i n g 矿) 如釉属于集合j ，返回1 ，否则返回o ； 砌fi = 1 ； w h i l e ( ( v h , ( y 月2 = 1 ) & & ( f 后+ 1 ) ) f 抖； 矿( f = 七) r e t u r n0 ： e l s e r e t u r n1 ； ) 第2 章网络测量的相关技术 图2 4 元素查询过程 f i g 2 4e l e m e n ti n q u i r yp r o c e s s 2 2 2b i o o mf t a r 的精确性分析 b l o o mf i l t e r 的空间效率是以小的错误肯定的概率作为代价的，但这种代价对 实际应用的影响非常小。b l o o mf i l t e r 不会产生弃真错误，不能应用在对精确性要 求非常高比如“零错误”的场合。 假设哈希函数是完全随机的，并且非常均匀，集合s 中全部的元素都插入到 b l o o