（计算机软件与理论专业论文）基于路由安全的改进chord算法研究.pdf

南京邮电大学硕士研究生学位论文中文摘要 中文摘要 随着p 2 p 技术的发展，其应用越来越广泛，其中基于分布式哈希表( d h t ) 的p 2 p 资源 搜索算法正是近年来p 2 p 技术领域研究的热点。对于基于d h t 系统的大量研究主要集中 在如何提高查询效率及改善算法性能等问题，而其所面临的安全问题的研究相对较少。处 于开放环境下的d h t 应用系统遭遇的各种安全威胁将制约其更好的发展，因此研究相应 的安全保障措施，改善由恶意攻击引发的安全问题也成为d h t 应用的另一个研究重点。 对于各种安全威胁，本文的研究目标是解决在d h t 资源定位过程中路由安全的问题， 从而提高资源搜索的成功率。主要是指在路由信息的传递过程中可能遭受到恶意节点的攻 击，如丢弃或错误转发路由信息等导致查询失败。因此针对c h o r d 协议的研究，本文提出 一种基于路由安全考虑的改进c h o r d 算法。该算法首先使用双向查找算法进行关键字的路 由，通过构造到达目标节点的不同路由路径来判断查找过程的正确性，并且在路由过程中 还提出一些安全措施防御相应的攻击。然后对查询获得的两个结果进行比较，结果一致则 查询正确，若结果不一致，需要提交给本模型中设置的全局检测中心，对查询结果及其路 由过程进行进一步的验证。检测中心使用选择性路由算法来获取待验证根节点的邻居节 点，并根据邻居节点信息和待验证根节点信息的一致性来验证根节点的正确性，识别恶意 节点，确定正确的关键字存储根节点，最后将验证结果返回给查询发起节点。同时该算法 是在基于一个实际的p 2 pv o l p 系统中的安全d h t 模块上进行详细设计与实现的。最后， 实验测试的结果表明，该算法能够有效地检测在路由过程中存在的恶意节点，对其各种恶 意行为有一定防御能力，较好的改善了结构化p 2 p 叠加网的路由安全问题，提高了资源搜 索的成功率。 关键词：分布式哈希表，路由安全，双向查找，选择性路由 南京邮电大学硕士研究生学位论文 a b s t r a c t a bs t r a c t w i t ht h ed e v e l o p m e n to fp 2 pt e c h n o l o g y , i t sa p p l i c a t i o nh a sb e c o m ei n c r e a s i n g l yp r e v a l e n t a m o n gt h e m ，d h t - b a s e dp 2 pr e s o u r c es e a r c ha l g o r i t h mi sah o tt o p i ci np 2 p t e c h n i c a lf i e l d m u c hr e s e a r c hh a sb e e nd e v o t e dt ot h ed e v e l o p m e n to fq u e r ye f f i c i e n c ya n dp e r f o r m a n c ef o r d h t s y s t e m s ，b u tf e wh a v ee x a m i n e dt h e i rs e c u r i t yi s s u e s t h ev a r i e t yo fs e c u r i t yt h r e a t sw i l l r e s t r i c tt h eb e r e rd e v e l o p m e n to fd h t a p p l i c a t i o ns y s t e m si na l lo p e nn e t w o r ke n v i r o n m e n t ，s o t h a tt h es t u d yo nc o r r e s p o n d i n gs e c u r i t ym e a s u r e sw h i c hc a nm i t i g a t et h es e c u r i t yp r o b l e m s c a u s e db yt a r g e t e da t t a c kh a sa l s ob e c o m ea n o t h e rf o c u s t h ep u r p o s eo ft h i sp a p e ri st or e s o l v et h es e c u r er o u t i n gp r o b l e m so nt h ep r o c e s so f s e a r c h i n gr e s o u r c e ，a n di m p r o v et h es u c c e s sr a t ef u r t h e r w ea r em a i n l ya i m e da ta t t a c k so n m e s s a g er o u t i n gc a u s e db ym i s b e h a v i n gn o d e s ，f o ri n s t a n c ea n ym a l i c i o u sn o d ec a l ld r 叩a n d m i s r o u t em e s s a g e sa tw i l l s oa i m e da tr e s e a r c ho nc h o r d ，w ep r e s e n tai m p r o v e dc h o r dm o d e l b a s e do ns e c u r er o u t i n g f i r s t l y , ab i d i r e c t i o n a lq u e r ya l g o r i t h mo nc h o r di sp r o p o s e dt oj u d g e t h ec o r r e c t n e s so fk e y r o u t i n gb yc o n s t r u c t i n gd i f f e r e n tp a t ht ot a r g e tn o d e ，s p e c i a l l ys o m es e c u r e m e c h a n i s ma g a i n s ta t t a c k so nm e s s a g er o u t i n gi s p r e s e n t e dt o o s e c o n d l y , t h er e s u l t s o f b i d i r e c t i o n a lq u e r ya r ec o m p a r e d ，t h eq u e r yi sc o r r e c ti ft h es a m e ，o t h e r w i s ew em u s tu s eg l o b a l v e r i f i c a t i o na u t h o r i t yt ov e r i f yt h er e s u l t sa n dp r o c e s so fr o u t i n gf u r t h e r t h ea u t h o r i t yw i l l v a l i d a t et h et r u e n e s so ft h en o d e sr e s p o n d i n gt oq u e r yf o rk e yb yc o m p a r i n gt h ei n f o r m a t i o no f t h e s en o d e sw i t ht h e i rn e i g h b o r sa c q u i r e db yu s i n gt h es e l e c t i v i t yr o u t i n ga l g o r i t h m ，s oi tc a l l d e t e c tt h em a l i c i o u sn o d e sa n da s c e r t a i nw h i c hn o d ei si n d e e dt h ec o r r e c th o l d e ro ft h ek e y a t l a s t ，t h ea u t h o r i t yw i l li n f o r mt h eq u e r yn o d eo fi t sv e r i f i c a t i o nr e s u l t o nt h eb a s i s o ft h i s r e s e a r c h ，w ea c h i e v et h ed e s i g na n di m p l e m e n t a t i o no ft h i si m p r o v e dc h o r di ns e c u r ed h t m o d u l ei np 2 pv o l ps y s t e m e x p e r i m e n t a lt e s tr e s u l t ss h o wt h a tt h i sm o d e lc a l ld e t e c tt h e m a l i c i o u sn o d e sw i t l l1 1 i g he f f i c i e n c ya n da c c u r a c yw h i l et h ec o s ti sc o m p a r a t i v e l yl o w i tc a n r e s o l v et h es e c u r ep r o b l e m so fs t r u c t u r e dp e e r - t o - p e e ro v e r l a y se f f e c t i v e l y , a n di m p r o v et h e s u c c e s sr a t eo fq u e r y k e y w o r d s ：d h t , s e c u r er o u t i n g ，b i d i r e c t i o n a lq u e r y , s e l e c t i v i t yr o u t i n g i i 南京邮电大学学位论文原创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名： 盔：目日期：壶翌：丝：箩 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本人所送 芒学位论文的复印件和电子文档，可以采用影印、缩印或其它复制手段保存论 文。本文电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。 论文的公布( 包括刊登) 授权南京邮电大学研究生部办理。 研究生签名：醯：盟 导师躲俐日期：竺翌：丝： 南京邮电大学硕士研究生学位论文 第一章引言 1 1 课题背景 第一章引言 v 2 v ( v e e r - t o p e e r ) 是2 0 世纪末兴起的不同于传统的c s ( 客户机服务器) 模型的一种全 新的分布式的通信模型和应用模型。参照d e j a n 在p e e r t o p e e rc o m p u t i n g 文中的定义： p 2 p 指的是一类用分布式资源( 包括计算能力、数据资料、网络带宽、以及计算机和人等 ， 等) 实现一个重要功能的系统或应用。在p 2 p 系统中所有的节点是对等的，能同时扮演服 务器和客户端的双重角色，可以充分利用网络中的空闲资源，实现更加灵活和有效的资源共 享 1 】。它有效解决了传统c s 模式中单点失效以及极大缓解了服务器端压力过大造成的性 能瓶颈问题，增强了整个系统的可扩展性。因此p 2 p 技术被广泛应用于计算机网络的各个 应用领域，如分布式科学计算、文件共享、流媒体直播与点播、语音通信及在线游戏支撑 平台等方面。 其中对等网最关键的技术之一是如何实现分布式对象的定位。目前主要采用的有两种 机制：简单泛洪方式进行的分布式搜索，如g n u t e l l a 2 和f r e e n e t 3 ，但这种方式无疑会造 成巨大的带宽和资源浪费；另一种是基于分布式哈希表( d i s t r i b u t e dh a s ht a b l e ) 技术的搜 索方式，如c h o r d 4 ，c a n 5 ，p a s 缸y 【6 和t a p e s t r y 7 等，每个节点只存储特定的信息或特 定信息索引，当用户需要在p 2 p 系统中获取信息时，他们必须知道这些信息( 或索引) 可 能存在于哪些节点中，因此极大的提高了信息搜索的效率。 基于分布式哈希表( d h d 的p 2 p 资源搜索算法正是近年来p 2 p 技术领域的突破，也是 今后p 2 p 网络分布式定位算法的发展方向，被广泛应用于分布式文件系统、p 2 p 文件共享 系统、协作式w e b c a c h i n g 、多播和域名服务等领域。基于d h t 技术的结构化p 2 p 叠加网 只要求每个节点的路由表保存少量的路由信息，然而在搜索的时候却可以利用这些路由信 息在有限的跳数内搜索到目标。此外，这些d h t 算法构成的系统在节点数量上具有很好 的弹性，同时也有很好的容错性和负载均衡性等【8 】。 基于分布式哈希表( d h t ) 的p 2 p 应用系统的资源查找是通过一系列节点的路由查询 来搜索给定的关键字，这一系列节点中的每一个节点使用本地路由表来转发路由查询，最 终到达负责该关键字的节点。然而这些应用的设计往往假设每个节点都是被信任的，并且 人们主要关注如何获得较高的查询效率。诚然，在每个节点都是可信的情况下，这些p 2 p 南京邮电大学硕士研究生学位论文 第一章7 1 言 应用能够正确的执行并且能够提供很好的特性。然而，假设每个节点都是可信的设想在很 多场景下并不现实，特别是在开放的p 2 p 网络环境下，只要有- d , 部分恶意节点就能对整 个系统造成严重的破坏。虽然大部分d h t 算法在设计时已经考虑了容错性以及成员节点 变更等因素，但事实上并不能保证每个加入到该叠加网节点的行为能和预期设计一致，因 此理论上假设的通过对给定关键字的路由查询提供了一种可靠的资源定位机制是不正确 的。在资源定位的过程中经历的一系列节点中，可能存在某些恶意节点丢弃路由信息或错 误转发路由信息，阻止正常节点找到正确的资源所有者，带有目的性的攻击以破坏和分解 原系统结构，如c h o r d 算法的环形结构被断开等等 9 】。 这些恶意节点运用各种攻击手段导致系统性能降低、资源丧失以及严重的故障。因此 在关注查询效率的同时，基于d h t 搜索方式的庞大的结构化p 2 p 系统所面临的各种安全 问题，及缓解这些问题的安全策略等等都是研究的重点和热点。 1 2 课题来源及研究目标 本课题来源于江苏省高校研究生创新工程项目基于对称查找和选择性路由的安 全c h o r d 算法研究；以及华为基金项目基于安全d h t 的p 2 pv o l p 原型系统的研究与 实现。创新工程项目是针对d h t 众多算法中的c h o r d 算法进行研究，目标在于能通过对 c h o r d 算法的改进以及相应措施的研究解决d h t 资源搜索定位过程中面临的安全问题。而 华为基金项目基于安全d h t 的p 2 pv o l p 系统旨在将p 2 p 技术与v o i p 结合起来，使用纯 p 2 p 架构构建一个无服务器的语音系统，代替现有的s i p 客户服务器架构的系统，设计分 为v o i p 客户端子系统和p e e r 端子系统。其中p e e r 端子系统包括安全d h t 模块和n a t 穿 越模块的设计和实现。安全d h t 模块是具体d h t 算法的实现，包括路由功能，以及在资 源搜索过程中达到一定的安全性要求，防御相应的安全攻击，提高资源搜索的成功率。因 此根据p 2 pv o i p 系统中p e e r 端子系统的实现需求，结合我们对c h o r d 算法及资源查找过 程中的安全问题的研究，本文的工作主要是研究基于路由安全的改进c h o r d 算法，并在这 基础上将该改进的安全算法应用到实际的p 2 p v o i p 系统的p e e r 端子系统中，针对安全d h t 模块进行详细设计与实现。 本文的主要研究目标是提出一种改进的c h o r d 算法及相应的安全机制，以缓解在关键 字查找时路由信息传递过程中存在的各种安全威胁，提高查找的正确率。相应的主要研究 内容有：对c h o r d 算法的研究，基于d h t 的p 2 p 叠加网面临的各种安全威胁，对资源查 找的安全路由算法以及查询结果的相关验证机制的研究等。 南京邮电大学硕士研究生学位论文第一章引言 1 3 本文结构安排 全文共分七个章节，内容组织如下： 第一章介绍了本课题的背景、来源，并给出了本文组织。 第二章介绍了本文所用到的相关技术，包括p 2 p 相关技术、基于d h t 的搜索定位方 法，并详细介绍了基于d h t 的结构化p 2 p 叠加网存在的安全问题的相关研究，以及为解 决相应安全问题提出过的已有的安全策略的分析研究。 第三章对基于安全d h t 的p 2 p v 0 i p 系统设计做了大致的介绍，根据其中的p e e r 端子 系统中安全d h t 模块的设计需求，利用本文研究的基于路由安全的改进c h o r d 算法实现 其具体的安全搜索功能，因此最后对该改进c h o r d d 算法的总体设计做了简要介绍。 第四章介绍了基于双向查找的路由过程及查询结果判断机制。首先描述了改进后的 c h o r d 算法的相关数据结构，然后详细介绍了基于双向查找的安全路由算法和查询结果判 别算法。 第五章介绍了基于选择性路由算法的根节点验证机制。证明了为实现选择性路由，算 法需要满足的条件，在此基础上，给出了选择性路由算法以及验证存储关键字根节点的具 体机制，从而识别潜在的恶意节点，最终定位到正确的根节点的过程。 第六章对本文提出的改进c h o r d 算法进行了理论上的性能分析和仿真测试，并对p 2 p v o i p 系统进行了功能测试，主要是测试p e e r 端p 2 p 子系统的相应功能，以验证我们所提 出的算法的可行性。 第七章总结了本文所做的工作，并对该课题进一步研究的方向进行了展望。 南京邮电大学硕士研究生学位论文 第二章相关技术简介 2 1p 2 p 相关技术 第二章相关技术简介 2 1 1p 2 p 技术特点与分类 p 2 p 是一种分布式网络，网络的参与者共享他们所拥有的一部分资源( 处理能力、存 储能力、网络连接能力、打印机等) ，这些共享资源需要由网络提供服务和内容，能被其 它对等节点( p e e r ) 直接访问而无需经过中间实体 1 1 。在此网络中的参与者既是资源( 服务 和内容) 提供者( s e r v e r ) ，又是资源( 服务和内容) 获取者( c l i e n t ) 。p 2 p 打破了传统 的c l i e n t s e r v e r ( c s ) 模式，在网络中的每个结点的地位都是对等的。每个结点既充当服务 器，为其他结点提供服务，同时也享用其他结点提供的服务。 p 2 p 技术的特点体现在以下几个方面 1 0 。 、 非中心化：网络中的资源和服务分散在所有结点上，信息的传输和服务的实现都直 接在结点之间进行，可以无需中间环节和服务器的介入，避免了可能的瓶颈。p 2 p 的非中 心化基本特点，带来了其在可扩展性、健壮性等方面的优势。 可扩展性：在p 2 p 网络中，随着用户的加入，不仅服务的需求增加了，系统整体的 资源和服务能力也在同步地扩充，始终能较容易地满足用户的需要。整个体系是全分布的， 不存在瓶颈。理论上其可扩展性几乎可以认为是无限的。 健壮性：p 2 p 架构天生具有耐攻击、高容错的优点。由于服务是分散在各个结点之 间进行的，部分结点或网络遭到破坏对其它部分的影响很小。p 2 p 网络一般在部分结点失 效时能够自动调整整体拓扑，保持其它结点的连通性。p 2 p 网络通常都是以自组织的方式 建立起来的，并允许结点自由地加入和离开。p 2 p 网络还能够根据网络带宽、结点数、负 载等变化不断地做自适应式的调整。 高性能价格比：性能优势是p 2 p 被广泛关注的一个重要原因。采用p 2 p 架构可以有 效地利用互联网中散布的大量普通结点，将计算任务或存储资料分布到所有结点上。利用 其中闲置的计算能力或存储空间，达到高性能计算和海量存储的目的r l o 。 隐私保护：在p 2 p 网络中，由于信息的传输分散在各节点之间进行而无需经过某个 集中环节，用户的隐私信息被窃听和泄漏的可能性大大缩小。在p 2 p 中，所有参与者都可 南京邮电大学硕士研究生学位论文第二章相关技术简介 以提供中继转发的功能，因而大大提高了匿名通讯的灵活性和可靠性，能够为用户提供更 好的隐私保护 1 0 。 负载均衡：p 2 p 网络环境下由于每个节点既是服务器又是客户机，减少了对传统c s 结构服务器计算能力、存储能力的要求，同时因为资源分布在多个节点，更好的实现了整 个网络的负载均衡。 根据拓扑结构的关系，对p 2 p 网络结构模式的研究与发展经历了以下几个过程：中心 化模式，全分布式非结构化模式，全分布式结构化模式( 也称d h t 网络) ，混合模式 1 2 1 3 。第一代p 2 p 网络采用的既是中心化模式，由于资源的发现依赖中心化的目录系 统，优点是维护简单发现效率高，最大的问题与传统客户机服务器结构类似，容易造成 单点故障，经典案例如n a p s t e r 1 4 。全分布式非结构化模式是纯粹的p 2 p 系统，如 g n u t e l l a 2 ，其网络模型中的每一个联网计算机功能上都是对等的，采用了基于完全随机 图的洪泛( f l o o d i n g ) 发现和随机转发( r a n d o mw a l k e r ) 机制，容错性好，支持复杂查询， 但系统可扩展性差且无法保证资源发现的效率。因此，大量的研究集中在如何构造一个高 度结构化的系统，发展出现了全分布式结构化模式，研究重点放在了如何有效查找信息上， 主要采用的是基于d h t ( d i s t r i b u t e dh a s ht a b l e ) 的分布式发现和路由算法。它通过分布式 散列函数，将输入的关键字惟一映射到某个结点上，然后通过某些路由算法同该结点建立 连接，经典的案例是t a p e s t r y 7 ，c h o r d 4 ，c a n 5 和p a s t r y 6 等，具有良好的可扩展 性、鲁棒性、结点i d 分配的均匀性和自组织能力，但维护机制较为复杂。混合模式中选择 了性能较好的节点作为超级节点，发现算法仅在超级点之间转发，优点是性能、可扩展性 较好，较容易管理，但对超级点依赖性大，易于受到攻击，容错性也受到影响。 目前，p 2 p 技术的主要应用领域有信息资源共享、普及计算、协同工作、实时通信技 术、信息检索技术、广域网络存储系统等，而随着p 2 p 核心技术的不断研究解决，将会得 到更加广泛的应用。 2 1 2 与p 2 p 技术相关的研究问题 p 2 p 计算技术可以归结为一种特殊的分布式计算技术，从而p 2 p 计算技术所面临的很 多问题都可以利用目前的分布式计算技术的研究成果来解决。但是很多问题在p 2 p 系统中 具有了其自身的特点，目前p 2 p 技术研究的问题有以下几个方面 1 5 ： p 2 p 的网络拓扑结构的研究：拓扑结构是指分布式系统中各个计算单元之间的物理或 逻辑的互联关系，目前互连网络中广泛使用集中式、层次式等拓扑结构。集中式拓扑结构 南京邮电大学硕士研究生学位论文第二章相关技术简介 系统目前面临着过量存储负载、d o s 攻击等一些难以解决的问题。层次式拓扑结构是一种 应用比较广泛的分布式拓扑结构。p 2 p 系统一般要构造一个非集中式的拓扑结构，在构造 过程中需要解决系统中所包含的大量节点如何命名、组织以及确定节点的加入、离开方式、 出错恢复等问题。c a n 7 、p a s t r y 6 、c h o r d 4 、t a p e s t r y 5 等都提出了自己的p 2 p 网 络拓扑结构模型。 数据索引、查找、定位、路由机制以及访问路径：在典型的p 2 p 网络中数据资源分布 在各个独立的节点上，如何高效地索引、查找、定位以及访问这些数据信息资源是另一个 需要关注的重要问题，在分布式系统中这些问题同样也是正在研究的热点问题。一般来说 在p 2 p 共享应用中所采用的检索方式是采用关键字来查询自己所需的信息资源，同时人们 也期望能够将数据资源的索引信息存放在系统中的每一个节点上而不是像n a p s t e r 1 4 那 样存储在中心服务器上。路由机制是指节点之间通信的消息传递路径，合适的路由机制可 以充分的利用网络带宽资源并使系统具有很好的容错性、可扩放性，目前很多系统中的路 由机制都是和这些系统的逻辑拓扑结构紧密相关的。 p 2 p 网络的支撑技术：i n t e m e t 技术的发展使得连入互联网络中的设备不再局限于计算 机，在p 2 p 的计算环境中要求任何设备都可以在任何地点很容易的加入到这个环境中，所 谓的计算设备既包括有线设备也包括无线设备，这样就需要很多很多网络传输的支撑技术 来支持各种不同设备连入整个p 2 p 网络。 p 2 p 网络安全问题：安全问题是一直伴随着互联网发展的重要问题，安全闯题包括很 多相关的问题，比如应该防止他人控制整个系统，增加恶意信息等，同时系统应能够保证 系统中信息资源的正确性。在p 2 p 系统中系统安全同样面临着巨大的挑战，p 2 p 网络的自 组性、开放性和匿名性，在给人们带来方便的同时，也存在着极大的安全隐患。p 2 p 系统 需要在没有中心节点的情况下，提供身份的认证、授权以及数据信息的安全存储、数字签 名、加密、安全传输等工具，研究如何预防d o s 攻击，控制病毒、木马不在结构分散的网 络中传播，追踪恶意信息的发布者，抵抗过量存储负载，数字版权等等问题 1 6 1 7 。p 2 p 网络的安全性研究是当前的研究热点之一，是对p 2 p 网络发展的挑战。 2 2 基于d h t 的分布式对象定位技术 2 2 1d h t 技术简介 结构化p 2 p 系统的特点是每个节点只存储特定的信息或特定信息的索引。当用户需要 南京邮电大学硕士研究生学位论文 第二章相关技术简介 在p 2 p 系统中获取信息时，他们必须知道这些信息( 或索引) 可能存在于那些节点中。由 于用户预先知道应该搜索哪些节点，避免了非结构化p 2 p 系统中使用的泛洪式查找，因此 提高了信息搜索的效率。而目前的结构化p 2 p 系统普遍采用分布式哈希表( d i s t r i b u t e dh a s h t a b l e ，d h t ) 来进行资源的定位和搜索。 d h t 算法使用分布式哈希函数来解决结构化的分布式存储问题。分布式哈希表实际上 是一张很大的散列表：每个节点被分配给一个属于自己的散列块，并成为这个散列块的管 理者。d h t 及其发现技术为p 2 p 网络中资源的组织与查找提供了一种全新的算法思想 1 8 。 该方法的原理是：每一份资源都由一组关键字进行标志，系统对其中的每个关键字进 行哈希，得到关键字标志符k e y ；网络中的每个节点也通过哈希节点i p 得到节点标志符 n o d e l d ；关键字标志符和节点标志符都是惟的；按照某种映射关系，将关键字标志符映 射到节点标志符上，该节点标志符对应的节点就存储此关键字标志符的对应信息。所有的 ( k e y , v a l u e ) 对构成一张很大的文件索引散列表，其中v 表示实际存储文件的节点的口 地址。每个节点按照某种规则维护散列表的一部分。这里的规则依协议的不同而不同。用 户搜索时，用同样的哈希算法计算出每个关键字的标志符k e y ，再根据关键字标志符知道 该关键字标志对应信息的存储位置，从而能够快速定位资源的位置 1 9 。 分布式哈希表的主要功能包括三个内容：一、标识符的生成和管理；二、提供查询定 位的路由服务；三、对提供的服务或文件的信息进行管理。其中查询定位的路由服务是d h t 的基本功能，由于整个分布式哈希表的子散列块是按照一定的组织形态存储在不同的网络 节点上，某一节点只维护自己负责的资源，而需要用到其他节点的资源时就必须在整个叠 加网中查询所要用到的资源的位置。通常的实现方式是在节点上存储一张路由表，该路由 表中记录若干标识符相近或实际物理位置相近的节点的节点号、物理位置等信息。在查询 时，资源需求节点查询自身所存储路由表，如果目标节点具体信息在路由表中，则直接完 成查询过程：如果目标节点不在路由表中，则按照一定规则向相对靠近目标节点的节点发 送查询消息，接收查询消息的节点运行与资源需求节点相同的查找过程，直到完成目标节 点的定位。 d h t 技术能够自适应结点的动态加入退出，有着良好的可扩展性、鲁棒性、结点i d 分配的均匀性和自组织能力。由于重叠网络采用了确定性拓扑结构，d h t 可以提供精确的 发现。只要目的结点存在于网络中d h t 总能发现它，发现的准确性得到了保证。代表性 的搜索算法有c h o r d 4 ，c a n 5 ，p a s t r y 6 ，t a p e s t r y 7 。 c a n ：内容寻址网络( c o n t e n ta d d r e s s a b l en e t w o r k ) 是采用多维的标识符空间来实 7 南京邮电大学硕士研究生学位论文第二章相关技术简介 现分布式散列算法。所有节点被映射到d 维的笛卡尔空间中，路由查询也在此中进行。 p a s t r y ：是微软研究院提出的可扩展的分布式对象定位和路由协议，可用于构建大规 模的p 2 p 系统。它基于位序列的前缀进行路由，其基本路由方式是通过比较路由表中邻居 节点标识符和文件标识符，选择最长匹配前缀的节点为路由下一跳节点。 t a p e s t r y ：是一种面向广域网的分布式、可容错的路由和定位模型。该算法可以对消 息进行与位置无关的路由，把查询消息传递到最近的存储有目标对象拷贝的节点。 因为本文是针对d h t 中的c h o r d 算法进行的研究和改进，以期解决在此资源定位过 程中存在的路由安全方面的问题，因此在下面的小节中重点介绍c h o r d 模型。 2 2 2c h o r d 模型介绍 c h o r d 算法是在2 0 0 1 年由麻省理工学院提出，其核心思想就是要解决在p 2 p 应用中遇 到的基本问题：如何在p 2 p 网络中找到存有特定数据的节点 4 。c h o r d 算法专门为p 2 p 应用设计，因此考虑了在p 2 p 应用中可能遇到的特殊问题。 c h o r d 算法是基于相容散y i j ( c o n s i s t e n th a s h i n g ) 的一种资源定位及查找算法。与传统的 散列相比，相容散列具有更好的稳定性和负载平衡。相容散列使用h a s h 函数，如s h a 1 ， 作用于网络中每个节点的口，从而得到每个节点的标识；同样，使用s h a - l 作用于网络 资源的“关键字”，从而得到每个网络资源的标识i d 。 相容散列按如下规则将资源指定给节点：网络节点标识以2 。为模构成环( m 为资源 和节点标识的位数，即满足2 - - 1 节点数量2 i ) 。资源k 被指定到环中等于k 的节点或 者紧跟着k 的节点，这个节点被称为k 的s u c c e s s o r 节点，可以表示为s u c c e s s o r ( k ) 。如 果节点被表示为一个从0 到2 m 1 的环，那么s u c c e s s o r ( k ) 就是在环上从k 出发顺时 针方向第一个遇到的节点。相容散列使节点加入和离开只会引起网络一小部分的变化。当 一个节点n 加入时，一些先前指定到n 的s u c c e s s o r 上的资源，现在要指定到n ；当n 节 点离开环，那么原来存储在n 中的资源将自动转存于n 的s u c c e s s o r 节点上。 c h o r d 每个节点都保存有本节点的后继和前导节点信息，除此之外还维护着一个指针 表称为f i n g e rt a b l e ，每个表有m 条记录，每条记录包含两个域。s t a r t 域是当前节点i d 加 上一个偏移量，第i 条记录的偏移量是2 1 一l ( 1 i m ) ，n o d e 域是s t a r t 节点的后继节 点地址。对关键字的查找过程是这样的：计算关键字的s h a 1 散列值k ，如果k 落在本 节点i d 与其后继节点s u c c e s s o r ( i d ) 之间，则本节点应存放关于k 的信息，否则就要查找 路由表，定位到指针表中s t a r t 域最接近k 且s t a r t k 的记录，然后把查询请求转发给该条 南京邮电大学硕士研究生学位论文第二章相关技术简介 记录中n o d e 域的节点。该节点重复类似的操作，可见，使用这种策略，每次查询都能使 达到目标节点的距离至少缩短一半，其过程类似于二分查找，查询条数仅在o ( 1 0 9 ( n ) ) 。 c h o r d 算法本身具有负载平衡性，分布性，可扩展性，可用性等优点。 2 3 基于d h t 的p 2 p 叠加网的安全问题 2 3 1 面临的相关安全威胁 通常使用b y z a n t i n e 模型来分析p 2 p 叠加网安全威胁，即恶意节点能够产生任意的行 为，系统中恶意节点被划分为多个相互独立的恶意节点集合，每个集合中的恶意节点可以 相互串通体。按照p 2 p 应用的架构，安全威胁可以分为路由层的攻击和应用层的攻击以及 混合攻击 2 0 2 1 2 6 。 1 ) 路由层攻击 a 不正确的路由转发：恶意节点可以将查询转发到不正确的或者不存在的节点： b 不正确的路由更新：在基于d h t 的p 2 p 应用中，每个节点通过和其它节点的 交互信息来建立自己的路由表，所以，恶意节点可以向其它节点传递不正确 更新信息来破坏正常节点的路由表，这就导致受到影响的正常的节点也会错 误地转发路由查询。 c 分区：新的节点在加入的时候，需要联系已经加入到系统中的节点，如果加 入节点联系的引导节点是恶意节点，它就容易被引诱到由恶意节点控制的不 正确的分区网络中。 2 ) 应用层攻击 恶意节点在路由层能够正确地完成路由转发，但是它否认它所负责的数据的存在，或 者它承认它所负责的数据的存在，但是拒绝为其它节点提供服务。 3 ) 混合攻击 a 不一致行为：如果一个恶意节点在某些情况下能够正确的处理路由转发、响 应查询，而在某些情况下又错误地转发路由或者拒绝服务，那么恶意节点的 攻击行为将很难被发现，其它节点也很难判断是否应该把该节点从路由表中 去除。 b 对特定节点攻击：恶意节点可以向目标节点产生大量的数据包，从而使目标 节点表现出已经失效。 南京邮电大学硕士研究生学位论文第二章相关技术简介 c 快速加入和退出：根据d h t 算法，在节点加入和离开系统的时候，相关节点 要进行更新操作，包括路由表更新、邻居表更新、冗余数据更新，系统的重 新平衡需要付出一定的代价，于是，恶意节点可以通过快速的加入和退出来 降低系统的效率和性能。 d s y b i l 攻击 2 2 - 2 4 ：在p 2 p 环境下，攻击者可以容易的引入大量的恶意节点， 这些恶意节点相互串通，破坏系统的安全性和降低系统性能。 通过以上的分析可以看出，构建在这些d h t 算法之上的p 2 p 应用容易受到攻击者的多 方位的攻击，在安全性要求较高的场景下，很难达到p 2 p 应用的安全要求。因此，必须研 究相应的安全策略来满足安全性要求较高的应用场景的需求。 2 3 2 已有安全策略的研究分析及本文提出的解决方案 目前关于结构化p 2 p 叠加网安全研究已经取得了一定的进展。c a s t r o 等人在文献 2 5 中提出，p 2 p 叠加网的路由安全需要满足3 个基本条件，即安全的节点i d 分配、路由表安 全维护以及安全路由，针对p a s t r y 算法，作者提出通过增加附加路由表来维护路由表安全， 并通过下面的方法来实现安全路由，在查询进行到最终有节点声称对查询的k e y 负责时， 发起节点让该节点返回它的路由表，根据返回的路由表信息判断是否路由正确，如果路由 失败则使用冗余路由再次查询获得目标节点。尽管增加附加路由表能够限制恶意节点的破 坏影响，但是同时降低了p a s t r y 算法的路由效率，在实现安全路由时对于路由是否正确的 判断算法在形式上无法证明，而且判断的结果趋向于路由是不正确的，此外，在冗余路由 的时候会带来显著的网络流量负荷。s “和m o r r i s 在文献 2 6 1 中对d h t 和构建在d h t 上 应用受到的可能的攻击进行了分类，并且提出了一些最基本的设计原则来减少被攻击的可 能性，但是没有对如何实现安全的路由和维护d h t 的安全提出具体的解决方案。m a r t 等 人在文献 2 7 1 q b 提出基于社会联系的d h t 安全路由，即节点之间的信任关系是建立在社会 联系上的，查询节点在路由的时候根据社会联系的信息来转发路由，而不是仅仅考虑路由 的效率，然后，对于社会关系建立的机制要依赖于其它已经获得广泛应用的网络服务，如 y a h o o 等，显然，这些网络服务在很多特定的应用场景下是没有提供的。在文献【2 8 】中， 作者提出了安全健壮的d h t 路由算法：m y r m i c ，该算法在非在线c a 的基础上，增加了在 线的邻居认证中心( n a ) ，在新的节点加入或者有节点离开的时候，n a 通过给一些相关 节点发布邻居证书的方式参与d h t 的网络管理，查询节点通过收集邻居节点来验证声称对 查询的k e y 负责的节点的正确性。然而n a 的证书管理对于证书失效的管理，以及在节点 南京邮电大学硕士研究生学位论文第二章相关技术简介 快速加入、离开时证书的更新存在一些问题，而且增加的n a ，本身就容易受到攻击，在 n a 失效的时候，新的节点无法加入，此外，这种结构也在一定程度上破坏了p 2 p 的结构。 a m o sf i a t 等人在文献 2 9 1 中提出了改进的c h o r d 算法：s - c h o r d ，该算法将系统中的节点 进行分群，每个群对一个k e y 负责，路由查找的时候通过群和群内所有节点之间的泛洪查 询来进行路由，其实质是通过群中大多数节点的正确性来保证该群对负责的k e y 的查询的 正确性，显然，其显著地增加了系统的复杂度，群和群之间的泛洪路由需要o ( 1 0 9 刀，消息 数。r a n d yb a d e n 在文献 3 0 】中提出了基于鸽笼定理d h t 安全算法，该算法将节点按照属 性进行分组，每个组形成一个独立的d h t ，并假设相同属性的失效节点( 恶意节点) 属于 同一个组，这样存在大量失效节点的组返回的查询结果显然也是失效的，假设系统中最大 的同时失效的组的个数为f ，则只要将k e y 复制到f + 1 个组中，就可以保证查询返回的结果 中最起码有一个是正确的结果，显然，查询发起节点如何判断返回的多个查询结果的正确 性要依赖于应用层的认证，且确定划分不同分组的属性使得失效节点分布在同一个分组 中，也是比较困难的。文献 3 1 】提出了基于实际物理网络的p 2 p 叠加网的构建方法，并获 得了相对比较安全的节点i d 分配机制，但是在i n t e m e t 中，由于其分散管理的特点，获得 实际物理网络信息并不容易。 鉴于以上分析，针对结构化p 2 p 的安全问题，目前解决方案及存在的问题总结如下： 1 ) 增加全局认证中心，通过一定的认证措施进行p 2 p 网络中的节点安全管理。通过 发放证书，认证码等形式进行安全认证。但是认证中心容易遭到攻击，存在单点 失效问题，并在一定程度上破坏了p 2 p 结构，证书等的发放与撤销管理也存在一 定的难度： 2 ) 在路由选择时，不是基于最优的效率，而是基于一种信任关系，这种信任关系包 括社会关系等，但是社会关系建立的机制一般要依赖于其它网络服务，或者是基 于信任度机制，通过节点信誉度构建信任模型，作为路由转发及安全验证的机制； 3 ) 路由选择时基于最优的路由效率，但是对路由结果的正确性进行判断，判断的依 据是根据p 2 p 结构特征的近似判断，并通过冗余路由来查找正确的目标节点。由 于是根据p 2 p 结构特征来近似判断，判断的结果也是近似的，在冗余查询的时候 容易导致显著的网络流量负载。 4 ) 根据一定规则，将节点进行分组或分群，但对k e y 的查询及验证也有一定难度。 综上所述，本文研究提出一种基于路由安全的改进c h o r d 算法。诚然，基于d h t 的 p 2 p 应用系统所面临的安全问题是多方面的，几乎不可能一次性避免和解决所有的攻击和 南京邮电大学硕士研究生学位论文第二章相关技术简介 威胁，因此本文提出的算法主要是基于对关键字查找时路由信息传递过程中的安全性的考 虑，防御在路由过程中遭到的恶意攻击，例如路由查询过程中存在有行为不端的恶意节点 不正确的执行原有的路由规则，提供错误的信息误导其他合法节点，进行不正确的路由转 发，和其他恶意节点同谋，或者丢弃查询信息等等致使