（计算机系统结构专业论文）基于复制的容忍入侵系统研究.pdf

摘要 摘要 本文充分利用容错理论研究中的优秀成果，深入的分析研究了基于复制的容 忍入侵系统的理论和技术。文中首先提出一个基于部分复制的容忍入侵系统，可 大大降低基于完全复制所带来的系统资源的浪费；给出并证明了在部分复制情况 下保证全局萨确的一个充分条件：全局串行表是非循环的。文章还介绍了一种新 的复制技术：半被动复制。它不是基于组成员服务的，所以保留了被动复制优点 的同时也提高了崩溃下的反应时间，可广泛用于容忍入侵等分布式系统中。此外， 由于全序广播和多播算法在容忍入侵等分布式系统中有着重要的应用，比如在复 制协议中主席应用全序广播和多播算法发送更新信息和决定报文给各备份。为便 于人们根据需要从众多算法中进行选择，本文还基于排序机制，从通信记录、优 先权、动态序列器、静态序列器和目的方一致五个方面进行系统分类；并对各类 算法进行定性和定量分析。 关键字：容忍入侵部分复制半被动复制全序广播和多播分类 a b s t r a c t a b s t r a c t i n t r u s i o nt o l e r a n c ea san e wa p p r o a c ht oc o m p u t e rs e c u r i t yh a ss l o w l ye m e r g e d d u r i n gt h ep a s td e c a d e ，a n dg a i n e di m p r e s s i v em o m e n t u mr e c e n t l y i nt h i sp a p e r ，w e p r o p o s eas y s t e mb a s e do np a r t i a lr e p l i c a t i o nw h a th a sal o w e rc o s to fr e s o u r c et h a n t h o s eb a s e do nf u l l r e p l i c a t i o n i nt h em o d e l ，t h em e s s a g e sa p p l y i n g f o rt h e k e y s e r v i c e s ，u s i n gt h er e p l i c a t i o np r o t o c o l ，a r ed i s t r i b u t e dt ot h eh o s t st og u a r a n t e et h e t o t a l o r d e r ，w h i l et h o s ea p p l y i n gf o rt h en o n - k e ys e r v i c e s a r ed i s t r i b u t e dt ot h e i r c o r r e s p o n d i n gh o s t sd i r e c t l y h o w e v e r , b e c a u s el o c a lo p e r a t i o n so no n es i t e a r en o t v i s i b l et ot h eo t h e r s ，p a r t i a lr e p l i c a t i o nm a yr e s u l ti ni n c o n s i s t e n ts e r i a l i z a t i o no r d e r s ， t os o l v et h i sp r o b l e m ，as u f f i c i e n tc o n d i t i o nt og u a r a n t e et h eo v e r a l lc o r r e c t n e s si sa l s o g i v e n - - w h i c hr e q u i r e st h eu n i o n o fa l ll o c a ls e r i a l i z a t i o n 铲a p h st ob ea c y c l i c t h i s p a p e r a l s o p r e s e n t s t h e s e m i - p a s s i v er e p l i c a t i o nt e c h n i q u e av a r i a n t o f p a s s i v er e p l i c a t i o n t h a t c a nb e i m p l e m e n t e d i nt h ea s y n c h r o n o u s s y s t e mm o d e l w i t h o u t r e q u i t i n gam e m b e r s h i p s e r v i c et oa g r e eo na p r i m a r y t o t a lo r d e rb r o a d c a s ta n dm u l t i c a s ti sa ni m p o r t a n tp r o b l e mi nd i s t r i b u t e ds y s t e m s s u c ha si n t r u s i o nt o l e r a n c e f o re x a m p l e ，t h ep r i m a r ys e n dt h eu p d a t em e s s a g e sa n d d e c i d em e s s a g e st ot h e b a c k u p sb yu s i n go ft o t a l o r d e rb r o a d c a s ta n dm u l t i c a s t a l g o r i t h m s s of a r ，t h e r ea r es om a n ya l g o r i t h m so n t o t a lo r d e rb r o a d c a s ta n dm u l t i c a s t t h a th a v eb e e np r o p o s e d ，f o l l o w i n gv a r i o u s a p p r o a c h e s i ti sh o w e v e r d i f f i c u l tt ok n o w w h i c hs o l u t i o ni sb e s ts u i t e dag i v e na p p l i c a t i o nc o n t e x t t h o u g hs o m ea t t e m p t sh a v e b e e nm a d ea tc l a s s i f y i n ga n dc o m p a r i n gt h e s ea l g o r i t h n a s ，n o n ei sc o m p r e h e n s i v e ，a n d h e n c el a c ko fg e n e r a l i t y s of i n a l l yi nt h i sp a p e r ，w ep r o p o s eac l a s s i f i c a t i o ns y s t e m b a s e do nt h em e c h a n i s m so fo r d e r i n g b a s e do nt h i sc l a s s i f i c a t i o n ，w ed e f i n ef i v e c l a s s e so ft o t a lo r d e rb r o a d c a s ta l g o r i t h m s ，a n dt h e nr e l a t ee x i s t i n ga l g o r i t h m st ot h o s e c 】a s s e s k e y w o r d s ：i n t r u s i o nt o l e r a n c es y s t e mp a r t i a lr e p l i c a t i o n s e m i - p a s s i v er e p l i c a t i o n t o t a lo r d e rb r o a d c a s ta n dm u l t i c a s tc l a s s i f i c a t i o n 卢明 - 6 9 5 3 7 3 v 创新性声明 本人声明所呈交的论文是我个人在导师指导卜进行的研究工作及取得的 研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外， 论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电 子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的 同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：蒸l 盘：盖 日期：2 1 1 苎! ! ! 王d 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期删论文工作的知识产权单位属西安电子科技大学。本 人保证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电 子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校 可以公布论文的全部或部分内容，可以允许采用影印、缩印、或其它复印手 段保存论文。( 保密的论文在解密后遵守此规定) 本人签名：翻垒i 益 刷稚备季豢? ， 曩j 凳! ： 日期：2 1 1 苎! f 。2 ，d 日期：2 堕。f z ，1 7 第一章绪论 第一章绪论 随着信息化的发展，网络安全问题越来越受到人们的关注。各国都提出了网 络安全保密研究计划。到目前为止，这些计划可以分为三代。 第一代安全保密研究计划基于密码学、可信计算机、防火墙、存取控制等技 术，把入侵者挡在被保护的系统之外。虽然这种方法对一些系统有效，但这种方 法对互联网络已显得力不从心。第二代安全保密研究计划使用入侵检测系统_ 驯， 堵住了一般的安全缺口。虽然使用了入侵检测这种技术，但还是有些攻击不可避 免的发生了。入侵检测和响应研究到目前为止大部分考虑的是已知的和定义好的 攻击，从理论上说入侵检测不能完全地检测出所有未知攻击。目前入侵检测系统 的性能( 误警率和检测率) 没有得到大的提高，这主要是因为现有的检测技术和 响应策略有根本的限制。 自然界生物体的免疫特性为我们解决网络入侵问题给出了一个很好的借鉴。 自然界存在各种各样的病菌和病毒，它们不断地对我们人类的肌体发动进攻和入 侵。但是由于我们人体的健壮性抵御和瓦解了大约9 1 3 以上的进攻和入侵，真正进 入人体内部的不到1 0 。换句话说人体的健壮性可以容忍大约9 0 以上的病菌和病 毒的入侵。因此人体是一种很好的容忍入侵系统。由此，启发我们的网络系统也 应象人体一样具有容忍入侵能力，成为容忍入侵系统i t s ( i n t r u s i o nt o l e r a n t s y s t e m ) 。 由此可知，要确保网络系统的安全，除了要继续研究入侵检测之外，还应研 究网络的容忍入侵 4 ，5 ，两者相辅相成，从不同侧面共同确保网络安全。入侵检测 已经有较多的研究，但容忍入侵研究国内进行的较少，国外也是刚起步。因此开 展网络容忍入侵理论与技术的研究具有非常重要的意义。 1 1 容忍入侵系统概述 l _ 1 1 容忍入侵概念 容忍入侵( i n t r u s i o nt o l e r a n c e ) 是近几年来计算机安全逐渐形成的一个新的方 法，而且越来越受到关注。网络容忍入侵系统是指，网络系统在遭受一定的入侵或 攻击的情况下，仍然能够提供所希望的服务6 7 1 。容忍入侵系统提供了第三代的安 全保障机制。网络容忍入侵的主要研究内容有三点：第一是研究专注于对服务产 生威胁的事件的入侵触发器；第二是充分利用容错理论研究中的优秀成果；第三 是利用研究所得的容忍入侵理论和技术 在某种程度上可以不用理会入侵的发生 最终能构建一个新的网络安全信息系统。 也能够保持所希望的服务级别。在这种 系统中构造了多层容忍入侵措施。第一层要实时地监视和检查。但是这一检查不 基丁复制的容忍入侵系统研究 能达到百分之百的覆盖，总有一些攻击被漏检。第二层能对漏检的攻击继续检测， 并能阻止危害的传播，保证传播危害不扩散并且能收敛。资源能重新分配，系统 至少提供降级服务。最后一层从根本上要有一个新的体系结构，这种架构能得以 应用，提供时间、空间的数据冗余以及资源的重构来提供一定的质量服务。 “容忍入侵”这个术语第一次是在文献【8 j 中被使用。在其后的几年里，许多 独立的工作相继进行，他们大部份主要是基于协议的0 8 ，9 ，1 0 , 1 1 ，1 2 ，1 3 】。直到最近，随 着美国o a s i s ( o r g a n i c a l l y a s s u r e d a n ds u r v i v a b l e i n f o r m a t i o ns y s t e m ) ，欧洲m a f i l a ( m a l i c i o u s a n da c c i d e n t a l f a u l tt o l e r a n c ef o ri n t e r n e ta p p l i c a t i o n s ) 和i t u a ( i n t r u s i o nt o l e r a n c eb yu n p r e d i c t a b i l i t ya n da d a p t a t i o n ) 这三个项目在概念、机制 和体系结构上的建设性工作，容忍入侵领域才有了显著的发展。 图1 1 容忍入侵示意图 图1 1 形象的说明了保护、检测、容忍入侵三者之间关系。所谓容忍入侵就是 指当一个网络系统遭受入侵，而一些安全技术都失效或者不能完全排除入侵所造 成的影响时，容忍入侵可以作为系统的最后一道防线。即使系统的某些组件遭受 攻击者的破坏，但整个系统仍能提供全部或者提供降级的服务。 之所以把这种方案称作容忍入侵是因为它是基于入侵检测和容错先前所做的 工作的基础之上的。入侵检测系统检测和报告安全策略冲突。容忍入侵用来提高 计算机系统和网络的安全性和可生存性。 1 1 2 容忍入侵原理 容忍入侵的系统结构如图1 2 。这种体系结构 1 4 , 15 , 1 6 】着眼于一类服务( 网络分 布式服务) 作为保护目标。 1 代理服务器 对f 在进行的请求维持最新的和一致的状态。 服务环境的有效迁移。 i d s 和请求的负载控制。 第一章绪论 图1 2 容忍入侵系统的体系结构 2 接收监视器 检查结果的合理性。 c o t s 服务器的可信状态的监视。 3 投票监视器 在投票裁决( v o t i n g a d j u d i c a t i o n ) 之前进行复杂结果的转换。 决定结果的发布者可以固定指定也可以动态选择。 4 审计控制 进行周期性诊断测试验证审计记录来检测组件中的异常行为。 维护所有系统组件的审计日志。 5 自适应性重新配置 当出现意外的或者恶意的故障时通过重新配置系统来自动执行安全策略。 1 2 复制 复制是容错中的一种主要机制，它可以提高系统的可靠性和可用性。复制技 术是在系统里引入冗余的一种常用方法。服务器的每个复制品称为一个备份。一 个复制服务器由几个备份组成，如果一个备份失败了，其他的备份仍可以提供服 务。 基丁复制的容忍入侵系统研究 1 2 1 部分复制 实际中不是所有服务都是关键性的，如果将所有服务都进行复制，那么系统 资源的开销显然是比较大的。所以完全复制( 所有服务都被复制) 是一个不太实 际的假设。为了降低资源的消耗，本论文采用部分复制的方法。所谓部分复制， 顾名思义，是指并非所有的服务都被复制的一种复制方法。在部分复制系统中， 根据其重要性可将服务分为关键服务和非关键服务。影响整个系统的服务称为关 键服务；其他的进程称为非关键服务。我们仅对关键服务进行复制。其状态一致 性由d i v 一致性( 详见第三章) 来保证。而由于非关键进程在某点的顺序对于其它 点是不可见的，所以可能会引起全局的不j 下确性。为了解决这个问题我们给出并 证明了保证全局f 确性的一个协议和一个充分条件：所有局部串行化表的合并( 全 局串行表) 是非循环的。 1 2 2 复制技术 复制技术是复制系统里的关键部分，从而引入冗余。复制是一种重要的容错 机制，它同时提高了系统的可靠性和有效性。本论文考虑的应用模型是客户一服 务器模型。客户端发布请求给远程服务。在被复制的服务里，服务器的复制品称 为备份。一个复制服务器由几个复制品组成，并且系统必须保证所有复制品之间 的状态都要保持一致。如果一个复制品失败了，其他的复制品仍可以提供服务。 复制技术主要有主动复制和被动复制两类。 1 2 2 1 主动复制 主动复制，也称为状态机复制1 7 , 1 8 。所有的备份都按相同的顺序准确地执行 相同的操作，从而保持同一性。主动复制的主要优点是即使在发生故障时反应时 间也比较快。但是，它也存在两个缺点：( 1 ) 要求所有的操作都要在确定的方式 下进行。确定是指一个操作的结果仅仅取决于个备份的初始状态和它已经执行 的操作顺序。( 2 ) 处理冗余资源开销比较高。 1 2 2 2 被动复制 被动复制技术，也称为主席备份 1 9 , 2 0 。主席备份的作用是：接收客户请求并 返回应答。其他的备份只受主席备份的影响，只能从主席备份得到状态更新消息。 被动复制技术所需要的资源开销比主动复制技术少，且可以在非确定的方式下执 行。但是，被动复制要求一个机制来和主席一致( 通常是组成员服务) 。如果主席 失败，其他备份会接替主席。但如果主席在发送一个应答给客户前崩溃，那么此 客户就会被永远终止。这个客户必须学习新主席的身份，并重发它的请求。这将 导致在出现故障时会大大增加应答时间。而且被动复制不能对客户隐藏故障。 第一章绪论 1 2 3 半被动复制 因为主动复制和被动复制的应用都有其局限性，第三章中我们将提出一种新 的复制技术半被动复制，它是被动复制的一个变形。半被动复制和被动复制 的区别就是前者不需要组成员服务。而组成员服务在故障发生时往往会引起重新 配置的延迟。同时，半被动复制又保留了被动复制的大部分优点：系统资源开销 低，且可以在非确定的状态下执行。 另外，在主动复制和半被动复制里客户和服务器之间的相互作用相似。但在 被动复制下，客户必须能够检测出主席崩溃，并且重新发送请求给新的主席。 1 _ 3 全序广播和多播 分布式系统中，广播是指给系统中所有的进程发送报文，而多播是指发送报 文给系统中进程的任意一个子集。与此相对应，全序广播要求进程按相同的顺序 把报文广播给所有的进程，而全序多播要求进程按相同的顺序把报文传送给目的 进程的任意一个子集。显然，广播和多播的界限并不是十分严格，故本文中用r 1 1 播来统称广播和多播。 全序广播和多播不仅在容忍入侵系统里占有重要位置，而且在分布式系统的 应用中也有着十分重要的作用，例如，全序传送是实现复制状态机时的一个基本 要求1 2 1 , 2 2 j 。此外，这些算法还在时间同步【2 3 】、支持互写的计算机、分布式共享存 储器、分布式时钟和容错的分布式应用等方面也都有着重要应用。迄今为止，人 们已对全序广播问题进行了大量研究，提出的算法不完全统计也有近5 0 种。然而， 这些算法都是针对不同应用所开发的，因此在实际性能、应用环境、使用模型、 算法目标、时间复杂度、报文复杂度等其他方面都各具特点。在出现新的应用需 求的情况下，人们难以从众多的算法中挑选出适当的一个加以使用。因此，需要 对这些己有的算法提出一个明确的分类，以便于人们根据现实需求与系统配置进 行适当的选择。 1 4 本文的工作 随着网络安全问题成为人们关注的焦点，容忍入侵已经是目前研究的一个热 点。本文深入的分析研究了基于复制的容忍入侵系统的理论和技术，结合目前容 忍入侵的发展状况，充分利用容错理论研究中的优秀成果，具体进行了以下几方 面的工作： ( 1 ) 提出了一个基于复制的容忍入侵系统； 基于复制的容忍入侵系统研究 ( 2 ) 针对基于完全复制资源消耗大的问题，本文提出了种部分复制的算法，并 且给出并证明了保证全局正确的一个充分条件：所有局部串行化表的合并( 全 局串行表) 是非循环的； ( 3 ) 分析已有的两种主要复制技术的优缺点，介绍了一种新的复制技术半被 动复制，并给出其完整算法和正确性证明。 ( 4 ) 根据排序机制，本文对全序广播和多播算法从通信记录、优先权、动态序列 器、静态序列器和目的方一致五个方面迸行系统分类，并从定性、定量两个 方面对各类算法进行了规范、应用模型环境以及性能的分析。 第二章基于复制的容忍入侵系统 第二章基于复制的容忍入侵系统 随着信息化的发展，网络安全问题越来越受到人们的关注。在军事、国防、 经济、航空等许多领域，如果系统遭到攻击而陷入瘫痪的话，那么它所带来的损 失是不可估量的。容忍入侵就是保证系统在受到攻击后仍能提供一定的服务。现 在，容忍入侵系统已成为研究的一个热点问题，它的好坏将直接影响到系统的性 能和稳定。 复制是容错中的一种主要机制，它可以提高系统的可靠性和可用性。复制技 术是在系统里引入冗余的一种常用方法。服务器的每个复制品称为一个备份。一 个复制服务器由几个备份组成，如果一个备份失败了，其他的备份仍可以提供服 务。所有备份之间要保持一致性。目前很多的系统都是基于完全复制技术的，如 2 4 ；2 5 。但实际中不是所有服务都是关键性的，如果将所有服务都进行复制，那么 系统资源的开销显然是比较大的。所以完全复制( 所有数据项都被复制) 是一个 不太实际的假设。为了降低资源的消耗，本文提出了一种基于部分复制的容忍入 侵模型。所谓部分复制，顾名思义，指不是所有的数据项都被复制的一种复制方 法。在部分复制系统中，根据其重要性可将服务分为关键服务和非关键服务。影 响整个系统的服务称为关键服务；其他的服务称为非关键服务。我们仅对关键服 务进行复制，其状态一致性我们应用d i v 致性来保证。而由于非关键进程在某 点的顺序对于其它点是不可见的，所以可能会引起全局的不正确性。为了解决这 个问题我们给出了保证全局正确性的协议和一个充分条件：所有局部串行化表的 合并( 全局串行表) 是非循环的。 本章的工作主要有三点。首先提出了一个基于部分复制的容忍入侵模型。前 面讲到部分复制会影响整个系统的正确性，所以本章还给出了在部分复制下保证 全局正确性的协议及其正确性的证明。最后我们通过完全复制和部分复制所占带 宽的实验来比较它们的性能，实验结果表明部分复制比完全复制的性能要好的多。 文章内容安排如下：第2 1 节介绍我们的系统模型；第2 2 节我们给出了在部 分复制下保证全局正确的协议及证明；第2 3 节是比较完全复制和部分复制的一 个实验；第2 4 节是我们的结论。 2 1 系统模型 在基于部分复制的容忍入侵中，维护着复制的服务和复制的数据集。这些复 制的服务和数据集运行在由有限个数的处理器集组成的服务器组上。服务器组中 的单个的处理器被称作复制主机或简称为主机，其中每个主机都有一个唯一的标 基于复制的容忍入侵系统研究 识符。所有主机中的数据及进程的初始状态都是相同的。我们称系统中要求服务 进程提供服务的进程或用户为客户，假定系统中客户的数目是无限的。 复制技术是复制系统里的关键部分，从而引入冗余。复制是一种重要的容错 机制，它同时提高了系统里的可靠性和有效性。本文主要考虑的应用模型是客户 服务器模型。客户端发布请求给远程服务，客户对服务的请求将引发系统中的 每个主机执行一次活动，活动定义了系统从当前状念到下一个状态的转换；“f 一 个状态完全由当前状态和活动所确定。如果系统中的各主机总是以同样的顺序执 行同样的活动集，则它们总是达到同样的状态。因此，要求各主机在执行活动之 前总是进行一致性协商。 图2 1 基于部分复制的容忍入侵系统的模型 图2 1 给出了基于部分复制的容忍入侵的系统模型。本模型里报文的传送采 用广播网络。系统中每个点在顺序保持串行下调度进程。由于半被动复制保持了 被动复制的优点，又克服了主动和被动复制的缺陷，所以本模型里复制采用半被 动复制技术。 此外，为了增强系统防止入侵渗透和访问控制的能力，我们在模型的顶部设 置了一个防火墙和访问控制层。通过该层可以过虑n i s 、n f s 等不安全的服务，拒 绝源路由和i c m p 重定向封包，同时还可以提供对系统的访问控制，对机密性、完 整性起直接的作用( 如允许从外部访问某些主机，禁止访问另外的主机) 。 第二章基于复制的容忍入侵系统 总体上讲，该模型系统主要包括4 层： 1 防火墙和访问控制层：对用户的身份进行验证，防止入侵。 2 用户请求管理器层：将服务根据重要性分为关键服务和非关键服务。关 键服务的请求进程通过半被动复制协议复制后传送给相应主机；非关键 服务的请求进程直接传送到相应主机。 3 半被动复制协议层：半被动复制协议不需要组成员服务，系统即使在出 现故障时反应速度也比较快。而且系统资源开销低，也可以在非确定的 状态下执行。各复制品之间的一致性通过d i v 一致性协议来保证。这将 在第三章中详细介绍。 4 主机层：该层可有若干个主机，每个主机存储三类数据：复制的关键数 据，不复制的非关键数据和局部串行表。每个主机的局部串行表合并起 来，构成全局串行表。前面已经讲到关键进程的一致性通过复制协议来 保证，加入非关键进程后，其一致性则通过给全局串行表来保证。这将 在后面的章节里进行详细说明。 2 部分复制下保证全局正确的协议 由于部分复制中只有通过半被动复制协议的关键服务的请求进程的顺序是全 局可见的，而局部服务进程( 非关键服务的请求进程) 在某点的顺序对于其它点 是不知道的，所以部分复制对整个系统的正确性可能会有影响，为了解决这个问 题，我们给出保证全局正确性的协议并证明其正确性。 2 2 1 部分复制对整个系统f 确性的影响； 显而易见，半被动复制协议并不能保证主机里不复制的非关键进程的顺序。 在一个主机里要保证在所有点上都是全序的一种方法是进程调度的顺序是完全确 定的。但是，即使假设在每个主机里是确定性操作，如果使用部分复制，那么每 个主机服务器会有不同的输入集合( 因为局部操作在别的点上是不可见的) ，因此 不能保证在全局所有点上以相同的顺序到达。 我们通过个例子来说明这个问题。+ 在图2 2 中，主机l 的进程执行顺序是p 2 ，p 3 ，p l ，主机2 的进程执行顺序是 p 1 ，p 4 ，p 2 。对于复制品x ，y 的读写顺序分别是w 2 y 卜 w l x 和w l x 卜 w 2 y ，易 见这两个串行化顺序虽然在局部是正确的，但是它们之间是矛盾的。 所以，部分复制可能会引起像图2 2 中的情况：虽然串行化顺序在局部是正 确的，但是全局却是矛盾的。 为了解决这个问题，下面我们给出在部分复制下保证正确性的协议。 基于复制的容忍入侵系统研究 复制数据 ： 在 机1 的操作 p ip 2p 3 在j 二机2 的操作 p ip 4p 2 八、八、f w ： i - ijr h _ 1 【x j 心 h w 2 【v w 3 i h r 1 c - 1 x n 【c _ 4 n jw 2 y r 2 c 舟上机1 的顺序= p 2 ，p 3 ，p l 在丰机2 的顺序= p l ，p 4 ，p 2 图2 2 部分复制对全局正确性影响的例子 2 2 2 部分复制下保证正确性的协议 2 2 2 1 相关定义及符号表示： 1 串行化概念：它是典型的并发流。它保证执行并发进程的调度和串行地执 行进程的调度在顺序上相同。它假设所有对服务器的访问都是应用读和写操作来 实现。如果我们可以找到一个串行调度和它是相同的，那么这个调度被称作是“正 确”的。 2 历史记录概念：历史记录h 是偏序的，记做 h ，它是进程集合的操作， 即 一个历史记录如果只包括在给定点上执行的操作，那么它是局部的；如果它 包括在所有点上执行的所有操作，那么它是全局的。 c o n f l i c te q u i v a l e n t ：女n 果两个历史记录定义在同样的进程集上，包含有同样的 操作，并以同样的顺序对冲突操作( c o n f l i c t i n g o p e r a t i o n s ) 进行排序，则这两个历 史是c o n f l i c te q u i v a l e n t 的。 如果一个历史记录与另一个串行的历史记录是c o n f l i c te q u i v a l e n t 的，则该历 史记录是可串行化的。 3 串行表：检测历史记录串行化的通常方法是应用串行表。串行表是由历 史记录里的进程作为节点，冲突联系作为边：对于任意两个冲突操作，o t e t ，0 e t ， 如果o t 。 全局串行表是局部串行表的合并。 2 2 2 2 保证全局全序的串行表协议 我们采用全局串行表来检测它们的串行化。在每个主机里都有一个局部串行 表，全局串行表是主机层里所有主机的局部串行表的合并。只要这个全局串行表 不存在循环，那么我们就可以保证全局的正确性。 尖一 一 第二章基丁复制的容忍入侵系统 下面我们给出其具体协议 协议2 1 保证全局全序的串行表协议 t a b l e p 1 。 证明：在每个点上执行保证串行化顺序。p 1 ，p 2 是全序的( 即p 2 的执行仅在 p 1 完成后) 。这在所有点上都满足。因此，由顺序保证的定义，没有一个局部串 行表可以包括p 2 一 p 1 。 由上面两个引理，我们给出定理1 。 定理2 1 ：所有局部串行化表的合并是非循环的。 证明：( 反证法) 假设存在k 个进程( k 1 ) 。合并后存在一个循环 p l p 2 一) p n 一 p l 。那么由引理2 ，我们应用传递性可以得出p l 一 p i ( p l 在p i 前 基下复制的容忍入侵系统研究 执行) ，很显然，这是不可能的，由此得证。 在定理2 1 环境下，所有执行是f 确的( 串行化的) 且在所有点上的串行化 顺序是一致的。由定理2 1 我们可以很容易的证明协议2 1 的正确性。 可见，顺序保持串行化是保证在基于由组通信协议建立的全序来执行复制进 程的复制结构里整体正确性的充分条件。协议罩由全局串行表来保证顺序串行化： 即要求全局串行表不存在循环。 2 3 实验 本节将定量地分析基于完全复制和部分复制的模型的性能。通常，部分复制 的性能要比完全复制的性能好的多。在实验里，我们比较了它们所占带宽的代价。 睦翻器 x ll o a t e t r 删 ， ； f u 1p a r t i a l r e p l i c a t i o nr e p l i c a t i o n 图2 3 完全复制和部分复制的比较 在图2 3 中黑色的部分代表数据通信量，灰色的代表无效的通信量。我们的 实验运行在两台机器上一个发送方( 客户) ，一个接收方( 主机) 。发送方对 文件进行随机写操作；接收方随机读取这些文件。在客户端生成1 0 0 0 个文件，每 个文件都时1 0 0 0 0 字节，并执行1 0 0 0 0 次随机写操作。主机端读取其中1 0 个文件。 假设接收方复制系统目录的1 0 。详细分析一下实验结果实验结果表明完全复制 所引起的带宽浪费要比部分复制大的多。 2 4 结论 本文提出了一个基于部分复制的容忍入侵模型。因为将所有的服务进行复制 对资源空间等的耗费都非常大，也不现实，所以我们采用部分复制，即只复制关 键服务。整个模型共有4 层：防火墙和访问控制层，用户请求管理器，半被动复 制协议层，主机层。主机层由若干个主机组成，每个主机存储三类数据：复制的 关键数据，不复制的非关键数据和局部串行表。每个主机的局部串行表合并起来， 可构成一个全局串行表。 u 5 一望吝融羞撬z噩_l茸富_芒0l 第二章基丁_ ；j 复制的容忍入侵系统 部分复制中只有通过半被动复制坼议的那些服务的请求进程的顺序是全局可 见的，局部服务的请求进程( 非关键服务的请求进程) 在某点的顺序刘于其它点 是不知道的，所以可能会引起虽然串行化顺序在局部是正确的，但是全局却是矛 盾的。为了解决这个问题我们给出了保证全局t f ! 确性的一个协议，并证明了其l f 确性，且从中得出了保证全局正确性的一个充分条件：所有局部串行化表的合并 ( 即全局串行表) 是非循环的。在基于组通信原语的复制结构中，为保证全局的 j f 确性，必须对系统行为做出一些假设。本文我们假设顺序要保持串行化。但顺 序串行化并不是唯一的结论，它只是个充分条件，可能存在更弱的条件就能保证 全局的f 确性。在未来的工作中应该更深入的研究哪个条件最适合复制结构中， 来确保全局的正确性。 最后，我们通过实验对完全复制和部分复制进行性能的定量分析。结果表明， 部分复制的性能要比完全复制的性能好的多。 第三章半自动复制 第三章半被动复制 在分布式系统里复制一个服务要求服务的每个备份都保持状态的致性，这 是复制协议的一个特性 2 。主要有两类保证一致性的复制技术：主动复制和被动 复制。 应用主动复制，每个请求被所有的备份执行。这个技术即使在故障情况下仍 可以快速反应。但是主动复制对资源的开销比较大而且要求请求的处理是确定性 的。最后一点对主动复制的应用带来很大的局限性。例如，典型的是在非确定情 况下的多线程。 应用被动复制，只有一个复制品( 主席) 处理请求，并且发送更新报文给其 他的复制品( 备份) 。被动复制技术需要的资源要比主动复制少的多，而且不要 求操作的确定性。但另一方面，被动复制也有其缺点：发生故障时反应速度慢。 例如，当主席崩溃时，故障必须被其他的备份检测出来，且请求必须有新的主席 来重新处理。而且在我们目前所知道应用里被动复制通常是基于组成员服务的， 它必须删除掉被怀疑崩溃的主席。 值用组成员服务进行故障检测的算法在崩溃的时候会引起重新配置所带来的 延迟。这些延迟都是由于传统的故障检测机制引起的。相反，不基于组成员服务 的算法可以承受更多的不正确怀疑，因为这类算法大大降低了资源的开销。 综上所述，被动复制和主动复制都有其局限性，所以在本论文的模型中我们 采用半被动复制技术，这在上章中已经提到。其实半被动复制不只可以用在容忍 入侵系统中，实际中它的应用非常广泛。所以本章将对半被动复制进行详细介绍。 本章的主要贡献就是介绍一个能够保留被动复制的基本优点而又不需要组成 员服务的新的复制技术( 半被动复制) 。我们还对半被动复制进行了定义，并且 证明了其正确性。半被动复制算法是基于变形的一致性问题d i v 一致性( 延 期初始值的一致性) ，我们给出其规范，完整算法和正确性证明。 本章的结构安排如下。第3 1 节介绍半被动复制的定义，优点和工作过程； 第3 2 节给出复制技术的规范；第3 3 节里给出d i v 一致性算法及其属性；第3 4 节详细描述半被动复制的算法及其正确性证明。第3 5 节是本章的结论。 3 ，l 半被动复制简介 因为半被动复制技术所需要的处理能力比主动复制小而且不必假设确定的处 理请求，所以它在实际中应用广泛。半被动复制可以看作是被动复制的一个变异， 而且又保留了被动复制的大部分特点( 例如允许非确定地处理) 。但在半被动复 制里，主席的选择是基于一个可传递的协调者机制的口7 1 ，这个机制比被动复制罩 的组成员服务要简单的多。 基于复制的容忍入侵系统研究 半被动复制的工作过程如下。客户发送请求给所有的复制品平p 1 ，p 2 ，p 3 ( 见 图3 1 ( a ) ) 。我们假设p 1 是第一个主席，p 1 处理请求并更新其他的服务器。 如果1 崩溃了，而且没有完成作为主席的工作，或者如果p 1 虽未崩溃但已经 被怀疑崩溃了，那么p 2 接管作为新的主席。详细的工作过程将在第3 节中介绍。 在图3 1 ( b ) 中在已经处理请求但未发送更新报文的时候p 1 崩溃后p 2 成为新的主 席。 ( a ) 无崩溃 ( b ) 协调者崩溃时 图3 1 、r 被动复制( 概念介绍：更新协议实际中隐藏在几个报文中) 很重要的点是在半被动复制里没有任何个进程从服务器组中删除。换句 话说，不需要被怀疑出现错误的进程执行加入( 和状态转移) 操作。这使涉及不 f 确的故障怀疑的开销显著下降。 3 2 复制技术的规范 虽然已经有被动复制的规范2 9 1 和主动复制的规范 3 0 ，但是这些规范都在特 殊情况下定义的，而没有给出所有复制技术的共同特性。所以在本节我们给出所 有复制技术都满足的四个规范。 系统里有两类进程：( 1 ) 客户和( 2 ) 复制品服务器。系统里所有客户的结 合标记为f i c ，复制品集合表示为r b 。 终止性：如果一个j 下确客户c l - i c 发送一个请求，那么它最终会受到一个应答。 全序：如果存在这样一个事件u p d a t e ( r e q ) ，一个复制品服务器执行第i 4 更新事件， 那么所有的服务器的复制品都要执行第i “更新事件u p d a t e ( r e q ) 。 完全更新：对于任意的请求r e q ，每个复制品至少执行一次u p d a t e ( r e q ) ，且仅当一 个客户先执行s e n d ( r e q ) 。 完全响应：对于客户执行的任意事件r e c e i v e ( r e s p 。q ) ，某些正确的复制品执行事件 u p d a t e ( r e q ) 。 第三章半自动复制 3 3d i v 一致性算法 这一节介绍延期初始值( d i v ) 一致性的定义和算法，这在半被动复制的算 法中将应用到。 3 3 1d i v 一致性定义 一致性问题的典型定义是，每个进程p i 从一个初始值v i 开始，且这个进程 必须和别的决定的值一致。在d i v 一致性里当调用这个一致性算法时一个进程 p i 不要求有已定义的初始值变量。因此这个算法可以在迟些的时间罩请求个初 始值。 一致性算法的接口通常用函数p r o p o s e ( v i ) 来表示，这里v j 是进程调用p r o p o s e 函数的初始值。而这延期初始值一致性里不需要。我们用函数d i v p r o p o s e ( g e t l n i t v a l ) 来表示d i v 一致性算法的接口，函数g e t l n i t v a l 最为变量。当需要 一个初始值时，g e t l n i t v a l 返回一个初始值，且在一致性算法里被调用。 - 3 3 2d i v 一致性的规范 终止性：每个正确进程最终会决定某一个值。 统一的完整性：每个进程最多决定一次。 一致性：没有两个正确进程的决定不同。 统一的有效性：如果一个进程决定v ，那么v 会被某一进程提供。 建议的完整性：每个进程至多只能提供一个值。 强d i v 性：如果两个进程p 和q 都提供一个值的话，那么p 或q 有一个是不正确 的。 只有d i v 性是和一致性问题的标准定义有关的新的特性。我们也给出弱d i v 问题 的定义。实际上，强d i v 性只在故障检测是确定的系统里才能保证。 弱d i v 性：如果两个进程p 和q 提供一个值，那么p 或q 被h s 里的某一进程怀 疑。 应用弱d i v 性，某些不正确的怀疑按照实际崩溃来处理。这意味着，在某些情况 下，一个不正确的怀疑可能会导致两个正确进程提供一个值。当出现这种情况时， 系统的实际消耗和每次个进程提供一个值的代价有关。实际上，如果故障检测 被完全接受，那么不正确地怀疑一个特定进程的性能会比较低。 基于复制的容忍入侵系统研究 3 3 3d i v 一致性算法 33 3 1 u s 故障检测器 一个故障检测器提供有关进程当前状态的信息。我们假设蚀故障检测器定义 在服务器进程兀j 的集合里，起定义如下： 强完全性：兀占里的每个崩溃进程被所有i - i s 里的正确进程永远怀疑后存在一段 时间。 最终弱正确性：在丌占里某一正确进程永远不会被任何正确进程怀疑后存在一段 时间。 3 3 3 2 应用u s 的d i v 一致性算法 d i v 一致性算法可以通过改进基于o s 故障检测器的c h a n d r a 和t o u e g 引1 算法 而得到。在d i v 一致性算法中假设大部分进程都是正确的( 厂= l 呈i ，此处f 是进 程崩溃数的最大量) 。这个算法运行在异步的轮里，且是基于协调者可转换的机制： 在每轮旱另一个进程是协调者。 算法3 1 就是解决d i v 一致性问题的完整算法。算法3 1 和蚀一致性算法基 本类似。在正常运行状态下在第一轮里只有协调者调用g e t i n i t v a l 函数，且d i v 一致性问题在一轮里被可以被解决( 见图3 2 ) 。当有崩溃时( 且没有不j 下确的 怀疑) ，需要两轮来解决：第一轮的协调者，进程p l ，调用g e t l n i t v a l ，然后崩 溃。随后的进程移到第二轮。第二轮的协调者进程p 2 依次来调用g e t i n u i t v a j 。 这旱就不在给出算法3 1 的全部解释，详细介绍见3 2 1 。我们只给出和这个算法不 相同部分的解释。 一p i f l s p 3 l 冉