北邮信息安全专业容错计算技术课件第6章.ppt

1、第六章 软件容错技术 软件冗余.软件容错技术n概述n软件可靠性的基本概念n软件避错技术n软件容错技术n软件N版本设计技术n软件恢复技术n软件可靠性模型.概述n软件危机的产生n软件老化问题n软件可靠性技术的兴起.软件危机n1962年，“水手1号”因其机舱计算机导航程序差错未能到达进行，这是早期人类从软件差错中得到的重大教训n20世纪60年代后期，计算机用户首先意识到了软件危机：n软件产品迟迟不能交付、软件质量低劣、维护代价高昂；软件开发人员感到力不从心，对软件的正确性缺乏信心；高软件需求和低生产效率导致软件费用急剧上涨n1998年的软件工程NATO会议上，科学界和实业界终于一致承认了软件危机的存

2、在.软件故障的根源n软件错误n导致产生含有缺陷的软件的人为行动(国标GB/T 11457-1995)n软件误差n存在于软件（文档、数据、程序）之中的那些不希望或不可接受的偏差n人为操作失误n软件运行过程中的非法输入.软件老化(Software aging)n软件老化是指软件系统运行速度的降低，或者是由于操作系统资源的耗尽、碎片以及错误的积累导致的程序突然崩溃 n主要是由于软件系统资源的损耗因其的，原因包括内存泄露、未释放的文件操作符、数字舍入错误、操作环境的数据损坏等n软件的缺陷等因素都会导致软件老化现象的产生，有效地方式是主动式容错策略，比如软件再生技术n软件再生技术：定期主动停止运行程序，

3、清理程序的内部环境，清除积累错误，然后重新启动软件使之进入一个正常的初始状态，从而避免因软件老化引起的突发性失效，提高软件系统的可靠性和可用性.软件可靠性的兴起n管理技术n程序设计方法学n验证技术.管理技术n软件行业管理n包括有关软件的政策、法律和标准化等问题n项目管理n针对一个具体软件开发项目进行n过程包括：制定开发目标和验收标准，以及阶段目标。根据软件生存周期（要求、说明、设计、实现、验证、运行和维护），在每一阶段具有标准文件，通过对文件的管理控制项目的管理n组织管理n通过合理分配项目成员的工作，使每个成员能动性充分发挥并使乘员减达到良好的协调.组织管理n主程序员负责制n主程序员负责指挥整

4、个项目开发组。主程序员负责设计任务和关键代码、对外交流等。n后备主程序员，负责备选方案。同时参与计划、设计、编码和测试等工作n其他成员是编程人员，负责管理程序库、文件、测试数据和测试结果n实践表明，主程序员负责制是生产高可靠软件产品的合理体制n编程秘书制n集体编程制.软件可靠性的兴起n管理技术n程序设计方法学n包括结构程序设计、程序综合、程序推导、函数程序设计、递归程序设计以及有关的形式说明和程序变换技术n这些技术是程序具有易于理解和验证的良好结构，但以运行效率为代价n为此，可以先设计一个良好结构的程序作为理解和验证的文本，然后用程序变换技术把它变换成一个高效运行的程序，最后运行n验证技术.软

5、件可靠性的兴起n管理技术n程序设计方法学n验证技术n程序测试：以发现差错为目的的过程，通过对被测试的结构分析（静态测试）或实际运行（动态测试）来实现n程序正确性证明：在不考虑程序运行环境条件下的确认程序正确性。方法包括Floyd-Manner的不变式推理方法、MchMarchy的递归归纳法、Horare的公理化方法和Dijkstra的弱谓词变换方法.软件容错技术n概述n软件可靠性的基本概念n软件避错技术n软件容错技术n软件N版本设计技术n软件恢复技术n软件可靠性模型.软件可靠性的基本概念n软件可靠性n主要指标n软件故障、失效和错误.n软件可靠性 1983年，IEEE对出如下定义：n在规定的条件

6、下，在规定的时间内，软件不引起系统失效的概率n在规定的时间周期内，在所述条件下程序执行所要求的功能的能力n经美国标准化研究所批准作为美国的国家标准n1989年我国国标GB/T-11457采用了这个定义.n几个概念n正确性n软件系统本身没有故障，并能证明它完全符合要求n健壮性n在硬件发生故障或输入不正常或环境发生异常情况等条件下，软件仍能进行适当工作n可靠性.第一节 软件可靠性的基本概念软件可靠性主要指标软件故障、失效和错误.n主要指标n软件可靠度函数R(t)n软件失效分布函数F(t)对于一个系统，如果只考虑系统成功与失败tetR)(0)0(1)()(FtFtR.n主要指标n失效密度函数f(t)

7、系统在t时刻单位时间内的失效概率.n主要指标n软件失效率函数 取一个不太长的时间t，可以假设)(ttetR)()()(常数t.)(t软件 和硬件 的比较)(t.软件失效率.第一节 软件可靠性的基本概念软件可靠性主要指标软件故障、失效和错误.n软件故障、失效和错误n故障（fault）：软件的内在缺陷称为故障，可能在软件生存期的各个阶段产生n错误（error）：故障所造成的后果，亦即导致运行中出现的异常状态n失效（failure）：错误造成系统的输出不满足最初对软件的要求和说明.n软件故障的性质n对人的依赖性n固有性n对环境的敏感性n传播性.软件可靠性技术的架构.软件容错技术n概述n软件可靠性的基

8、本概念n软件避错技术n软件容错技术n软件N版本设计技术n软件恢复技术n软件可靠性模型.软件避错技术n形式说明n可靠性程序设计的基本技术n程序验证技术.软件避错技术-形式说明n软件开发的目标是要把问题用一种严格的、数据化或逻辑化的语言把问题描述出来，得到问题的形式说明n形式说明是程序设计和验证的基础n分类：n描述问题功能性质的说明，通常把问题描述成一个函数，问题的输入对应于函数的参数，输出则对应于函数的值n描述问题逻辑性质的说明，通常把问题描述成一个过程、流程图或方框图.功能说明n功能说明有限制输入取值范围的输入说明和规定输出结果的输出说明组成n例：求自然数的阶乘Function f(n:Int

9、eger,n=0):Integer;f:=n!;Return;.逻辑说明n对有些问题，给出问题的逻辑描述更容易，或者给出逻辑描述后，换换成程序更容易，在此情况下需要给出问题的逻辑说明n例计算一个整数集合中大与整数a的元素个数.可靠程序设计的基本技术n程序综合技术n首先把形式说明变为解的存在性定理，容纳后寻找这个存在性定理的构造型证明，最后把证明过程转换为程序n递归程序设计技术n软件结构化设计技术)!)(0:)(nffnIntegernn.递归程序设计技术n步骤1、定义参数上的一个良序集合，以便程序一定能中止2、对参数进行适当的分析，其中必须包括一种易于计算的特殊情形作为结束条件（非递归分支）3

10、、计算出特殊情况下的函数值4、找出一般情况下函数值与具有较小参数的函数值之间的等式关系，得到递归分支5、把所有分支用条件表达式综合为一个程序.软件结构化设计技术n结构化设计存在于软件生存期的说明、设计和实现阶段n设计阶段的数据流设计n设计阶段的数据结构设计技术n实现阶段的结构化程序设计技术.数据流设计n1974年作为软件系统设计的自顶向下方法有Constantine提出，突出了模块化的设计思想，力图在软件设计的开始就把所设计的系统划分为若干相互独立的模块，使每个模块要完成的任务明确而单纯，达到程序设计简单、易于理解、调试和修改的目的n数据流设计以加强模块的独立性为基础，要求模块间的联系尽可能弱

11、，信息和数据交流尽可能少，模块内部联系尽可能强，信息和数据交流尽可能多，几所谓的弱耦合性和强内聚性设计n为获得耦合性弱和内聚性强的模块划分，需要按层次来组织模块，顶层模块负责主要功能变换，顶层模块下属输入、输出和变换模块。当需要输入数据时，顶层模块调用其下属输入模块，。，之所以需要经过模块传递和变换输入、输出信息，是为了保证设计的弱耦合性和强内聚性.数据结构设计n数据结构设计方法由Jackson提出，这种方法试图把描述问题的数据结构映射为程序结构，因为形式说明中的数据结构通常是定义明确的，所以，从同样的形式说明出发，用此方法可以得到类似的程序结构.结构化程序设计n结构：顺序型、条件选择型和循环

12、型n结构定理：任何一个适当程序在功能上等价于一个结构化程序，而且，这个结构化程序可以使用原来程序中的函数、谓词以及赋值语句、条件测试语句n定理中的适当程序满足：n具有一个入口和一个出口n对于程序中的每一条语句都存在一个合法输入，使得程序控制流从输入出发经过这个语句然后达到输出结构化程序的实质是取消转移语句goto.软件避错技术n形式说明n可靠性程序设计的基本技术n程序验证技术.程序验证技术n可靠程序设计技术可以减少软件故障的发生，但像任何设计过程一样，不能避免设计故障的发生。程序验证技术通过检查程序与其说明的符合性来发现故障、消除故障，从而提高软件可靠性.程序验证技术n程序正确性证明n程序的自

13、动证明技术n程序测试技术.程序正确性证明n证明定理：用满足输入说明的任一输入执行程序，程序将输出满足输出说明的结果并且终止。程序正确性证明可以分为两个独立的证明：n部分正确性证明，即证明如果程序能终止，对于任意合法输入，程序给出正确输出n终止性证明，即证明对于任意合法输入，程序能够终止.程序的自动证明技术n程序的正确性证明可以用机械步骤自动完成。即通过给机器提供推理规则，机器能自动完成部分正确性证明n困难n中间断言的自动生成很困难，致使生成程序变得很复杂n如何确认证明程序的正确性？引为证明程序往往比被证明程序复杂得多.n程序正确性证明技术以严格的数学分析和逻辑推理为基础，经过证明能保证程序设计

14、的正确性。但这种方法难度大，复杂性高尔未能投入实际使用n程序测试技术对常见的故障模型进行测试，尽管通过测试的程序不能保证程序的正确性，甚至也不能保证把程序的故障率或故障数控制在一个规定的量级之下，然而，由于程序测试技术的可行性和令人满意的实践结果，使它得到广泛的应用.程序测试技术n测试方法：根据测试中被测程序是否在输入数据驱动下实际运行，可以把测试分为静态测试和动态测试n静态测试：检查程序的语法是否正确、程序结构是否合格（从输入不可到达的语句、不能到达输出的语句、不经入口转入循环体或过程体等都是不合适的结构），是否所有变量都赋了初值或者是否有说明而没有使用的变量n动态测试：在输入数据驱动下对程

15、序进行实际运行，然后通过输出响应分析确定程序运行中是否发生了差错.动态测试n可以按非增式的方法进行，即先测每个模块，再测由若干个模块组成的子系统，最后测整个程序系统。在测试模块或子系统时，对其中的全局变量需要构造一个虚拟的测试背景（对变量赋初值或返回值）。模块测试应尽可能完全，保证模块处理的各种输入都被测到。n子系统测试要求检查模块间的借口操作，包括数据接口、控制接口等。子系统的测试还要经过多级测试n系统测试要涉及到整个程序的接口、数据流、控制流、数据结构、程序结构等问题.动态测试n非增式测试的缺点n每个模块和子系统都要求建立测试背景n子系统的组合数较大，使测试复杂性高.动态测试n增式测试：被

16、测程序是按层次结构方法组织的，则可以按自顶向下的增式测试方法，即先顶层测试，然后依次加入底层的模块测试n系统级测试次数减少n首先测试和反复测试顶层模块式主要功能模块得到最完全测试n高层模块自动为底层模块提供了部分测试背景n当发现差错时，故障被局限在新加入的模块内或新加入模块与已测模块的接口上.动态测试n测试数据生成：无法进行穷举法，常用随机测试方法n确定测试目标包括n测试数据是所有输入n测试数据使程序中每条通路至少执行一遍n测试数据使程序中每条分支至少执行一遍n测试数据使程序中每个语句至少执行一遍.测试数据生成方法.程序测试技术.自动测试工具n自动测试工具是一个综合的自动测试系统，它能够分析程

17、序结构，检查出某些类型的差错并指出可能发生的差错，同时，它能够生成测试数据、驱动被测程序运行，并分析测试响应、输出整理成文的测试结果.SADAT的结构.软件容错技术n概述n软件可靠性的基本概念n软件避错技术n软件容错技术n软件N版本设计技术n软件恢复技术n软件可靠性模型.第二节 软件N版本设计技术nN版本的设计方法nN版本容错系统的组成nN版本的管理程序.nN版本的设计方法 所谓NVP，就是针对同一任务，采用N(N=2)种不同的程序实现方法，独立生成N个功能相同的程序，在一个管理程序的统一协调下并行执行，根据决策算法，从N个结果中选出正确结果.nNVP设计原则n各版本尽量的不同n各版本尽量的独

18、立nNVP的生成方法n采用不同的算法，产生同一功能的不同版本n采用不同的语言，实现同一功能的不同版本n由不同的程序员来设计n用相同语言的不同版本来实现n以上方法的结合.第二节 软件N版本设计技术N版本的设计方法N版本容错系统的组成N版本的管理程序.nN版本容错系统的组成n运行环境nN版本运行在单处理器上nN版本运行在多处理器上（多机）N版本的理想运行环境.nN版本容错系统的组成n版本间的通讯n通讯的死锁问题n通信信箱的规模选择问题 过大会影响速度，过小则增加通信中的排队时间.nN版本容错系统的组成n同步问题 软件N版本系统保持一种“松散的同步”n为什么不进行“紧密同步”（像硬件）n完全同步难以

19、实现n不受同步约束，对各版本的执行有利n消除共模干扰.nN版本容错系统的组成nN版本的检测n自检测n采用编码技术nWatchdogn专用自检测程序 等n比较.nN版本容错系统的组成n版本间的切换错误版本的切除和离线n完全清除n版本修复正确版本的切入和运行n备用版本的初始化n写入检测点信息n申请在线n同步处理n进入运行状态.第二节 软件N版本设计技术N版本的设计方法N版本容错系统的组成N版本的管理程序.nN版本的管理程序n比较向量n比较变量n状态标志n比较状态指示器 比较向量比较后，应采取的措施n指示各模块是否在规定的时间给出了比较向量n向量结果一致，则指示继续往下执行n向量结果不一致，利用多模

20、块修改不一致模块n控制同步机构.表决程序设计-注意n表决程序是NVP结构的关键。由于表决程序规模不大，程序结构也不复杂，可以用正确性证明技术来保证其正确性n值得注意的是，表决程序不是完成简单的多数表决功能。因为计算机字长有限，计算结果往往是近似的，这样，按照不同的算法就可能得到不同的近似结果，因此，即使N份程序都正确，但他们的结果也可能不相等，表决必须考虑这种允许的差异。n表决程序要进行故障记录n表决器应知道N份程序最大的运行时间差d，当多数程序已输出结果，表决器最多再等d这样长的时间，还没有给出输出的程序被认为发生了差错.第五章 软件容错技术l第一节 软件可靠性的基本概念l第二节 软件N版本

21、设计技术l第三节 软件恢复技术.第三节 软件恢复技术n后向恢复技术n前向恢复技术n恢复块技术.n后向恢复技术（Rollcack）对于软件为多模块系统，实际是多进程或多任务同时运行的系统，模块间保持的通信，因此，后向恢复是在多软件模块及其相互通信的情况下进行的，必须要一个后向恢复协议，以保证系统的正确运行。.n后向恢复协议n协议保证，在要求恢复时，能够确定一组恢复点，使程序返回到该点时可以纠正故障影响协议应避免Domino效应.n后向恢复协议n协议保证，在要求恢复时，能够确定一组恢复点，使程序返回到该点时可以纠正故障影响n协议应避免Domino效应n协议尽量保持各软件原有的并行性n使各软件模块保

22、持独立性，以及恢复过程的透明性n使恢复操作尽量减少系统开销n具有完整性和一致性.实现后向错误恢复n恢复点的位置n错误可能涉及的范围n因此，必须要解决恢复点的设置及其保留的各有关软件模块过去的状态，要解决恢复与各软件模块通信的关系，从而解决错误范围的估价问题.n向后恢复的实现方法n静态规划方法n在多软件模块设计中，根据各模块间的会合，设计每一恢复线，在设计中避免Domino效应。缺点是影响原有并行处理能力、容易死锁等n无规划方法n不考虑各软件模块间的通信关系，各模块各自设计恢复线。当一个模块需要后向恢复时，可根据过去的通信关系自动地建立恢复线n动态规划方法n不限制系统的动态结构，运行中自动监视系

23、统动态结构变化，并可自动修改系统的动态结构，尽量避免Domino效应。一般情况下，通过自动地在系统中设置恢复点，来达到对动态结构的修改。n该方法避开了前两种方法的缺点，但增加系统开销.第三节 软件恢复技术后向恢复技术前向恢复技术恢复块技术.n前向恢复技术.第三节 软件恢复技术后向恢复技术前向恢复技术恢复块技术.n恢复块技术(Recovery Block)恢复块可以是一个过程、子程序、进程，或者是一个任务ensurebyelse by.else byelse.恢复块的工作流程.嵌套的恢复块结构.软件容错技术n概述n软件可靠性的基本概念n软件避错技术n软件容错技术n软件N版本设计技术n软件恢复技术

24、n软件可靠性模型.软件可靠性模型n时间模型n数据模型n播种模型.时间模型n时间模型与硬件可靠性的评价方法类似，把一个软件的可靠度定义为0,t内未输出差错的概率，并且，评价的目标也是找出风险函数n可靠性增长模型n公理模型.可靠性增长模型n最著名的是Shooman提出n模型假设：一个软件中的故障数目在t=0时是常数，随着故障被纠正，故障数目逐渐减少n经调试后，剩余故障的数目可用公式估计：.可靠性增长模型nShooman模型中，需要确定在调试前软件中的故障数目，这往往是很困难的.公理模型n对于软件故障，如果可以凭经验可以假设它服从某种分布规律，这就是所谓的公理模型n最著名的是Halstead提出的“

25、软件科学”模型，此模型假设软件中的故障数B由以下公式确定.播种模型n为了估计出软件中的故障数，可以预先在软件中随机插入s个故障(播种)，然后，对软件进行测试。假设共测出n+v个故障，其中，n是测出的自身故障的数目，v是测出的插入故障的数目。如果自身故障和插入故障被检测到的概率相等，则软件中自身故障总数的极大似然估计量为N=sn/vn模型假设“自身故障与插入故障被监测到的概率相等”.数据模型n在数据模型下，对于一个预先确定的输入环境，软件的可靠度定义为n次连续运行中，软件完成指定任务的概率n最早的数据模型是由Nelson在1973年提出.态度决定一切态度决定一切细节影响成败细节影响成败谢谢您的关注！谢谢您的关注！.