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

第六章软件容错技术 软件冗余 软件容错技术 概述软件可靠性的基本概念软件避错技术软件容错技术软件N版本设计技术软件恢复技术软件可靠性模型 概述 软件危机的产生软件老化问题软件可靠性技术的兴起 软件危机 1962年 水手1号 因其机舱计算机导航程序差错未能到达进行 这是早期人类从软件差错中得到的重大教训20世纪60年代后期 计算机用户首先意识到了软件危机 软件产品迟迟不能交付 软件质量低劣 维护代价高昂 软件开发人员感到力不从心 对软件的正确性缺乏信心 高软件需求和低生产效率导致软件费用急剧上涨1998年的软件工程NATO会议上 科学界和实业界终于一致承认了软件危机的存在 软件故障的根源 软件错误导致产生含有缺陷的软件的人为行动 国标GB T11457 1995 软件误差存在于软件 文档 数据 程序 之中的那些不希望或不可接受的偏差人为操作失误软件运行过程中的非法输入 软件老化 Softwareaging 软件老化是指软件系统运行速度的降低 或者是由于操作系统资源的耗尽 碎片以及错误的积累导致的程序突然崩溃主要是由于软件系统资源的损耗因其的 原因包括内存泄露 未释放的文件操作符 数字舍入错误 操作环境的数据损坏等软件的缺陷等因素都会导致软件老化现象的产生 有效地方式是主动式容错策略 比如软件再生技术软件再生技术 定期主动停止运行程序 清理程序的内部环境 清除积累错误 然后重新启动软件使之进入一个正常的初始状态 从而避免因软件老化引起的突发性失效 提高软件系统的可靠性和可用性 软件可靠性的兴起 管理技术程序设计方法学验证技术 管理技术 软件行业管理包括有关软件的政策 法律和标准化等问题项目管理针对一个具体软件开发项目进行过程包括 制定开发目标和验收标准 以及阶段目标 根据软件生存周期 要求 说明 设计 实现 验证 运行和维护 在每一阶段具有标准文件 通过对文件的管理控制项目的管理组织管理通过合理分配项目成员的工作 使每个成员能动性充分发挥并使乘员减达到良好的协调 组织管理 主程序员负责制主程序员负责指挥整个项目开发组 主程序员负责设计任务和关键代码 对外交流等 后备主程序员 负责备选方案 同时参与计划 设计 编码和测试等工作其他成员是编程人员 负责管理程序库 文件 测试数据和测试结果实践表明 主程序员负责制是生产高可靠软件产品的合理体制编程秘书制集体编程制 软件可靠性的兴起 管理技术程序设计方法学包括结构程序设计 程序综合 程序推导 函数程序设计 递归程序设计以及有关的形式说明和程序变换技术这些技术是程序具有易于理解和验证的良好结构 但以运行效率为代价为此 可以先设计一个良好结构的程序作为理解和验证的文本 然后用程序变换技术把它变换成一个高效运行的程序 最后运行验证技术 软件可靠性的兴起 管理技术程序设计方法学验证技术程序测试 以发现差错为目的的过程 通过对被测试的结构分析 静态测试 或实际运行 动态测试 来实现程序正确性证明 在不考虑程序运行环境条件下的确认程序正确性 方法包括Floyd Manner的不变式推理方法 MchMarchy的递归归纳法 Horare的公理化方法和Dijkstra的弱谓词变换方法 软件容错技术 概述软件可靠性的基本概念软件避错技术软件容错技术软件N版本设计技术软件恢复技术软件可靠性模型 软件可靠性的基本概念 软件可靠性主要指标软件故障 失效和错误 软件可靠性1983年 IEEE对出如下定义 在规定的条件下 在规定的时间内 软件不引起系统失效的概率在规定的时间周期内 在所述条件下程序执行所要求的功能的能力经美国标准化研究所批准作为美国的国家标准1989年我国国标GB T 11457采用了这个定义 几个概念正确性软件系统本身没有故障 并能证明它完全符合要求健壮性在硬件发生故障或输入不正常或环境发生异常情况等条件下 软件仍能进行适当工作可靠性 第一节软件可靠性的基本概念 软件可靠性主要指标软件故障 失效和错误 主要指标软件可靠度函数R t 软件失效分布函数F t 对于一个系统 如果只考虑系统成功与失败 主要指标失效密度函数f t 系统在t时刻单位时间内的失效概率 主要指标软件失效率函数取一个不太长的时间t 可以假设 软件和硬件的比较 软件失效率 第一节软件可靠性的基本概念 软件可靠性主要指标软件故障 失效和错误 软件故障 失效和错误故障 fault 软件的内在缺陷称为故障 可能在软件生存期的各个阶段产生错误 error 故障所造成的后果 亦即导致运行中出现的异常状态失效 failure 错误造成系统的输出不满足最初对软件的要求和说明 软件故障的性质对人的依赖性固有性对环境的敏感性传播性 软件可靠性技术的架构 软件容错技术 概述软件可靠性的基本概念软件避错技术软件容错技术软件N版本设计技术软件恢复技术软件可靠性模型 软件避错技术 形式说明可靠性程序设计的基本技术程序验证技术 软件避错技术 形式说明 软件开发的目标是要把问题用一种严格的 数据化或逻辑化的语言把问题描述出来 得到问题的形式说明形式说明是程序设计和验证的基础分类 描述问题功能性质的说明 通常把问题描述成一个函数 问题的输入对应于函数的参数 输出则对应于函数的值描述问题逻辑性质的说明 通常把问题描述成一个过程 流程图或方框图 功能说明 功能说明有限制输入取值范围的输入说明和规定输出结果的输出说明组成例 求自然数的阶乘Functionf n Integer n 0 Integer f n Return 逻辑说明 对有些问题 给出问题的逻辑描述更容易 或者给出逻辑描述后 换换成程序更容易 在此情况下需要给出问题的逻辑说明例计算一个整数集合中大与整数a的元素个数 可靠程序设计的基本技术 程序综合技术首先把形式说明变为解的存在性定理 容纳后寻找这个存在性定理的构造型证明 最后把证明过程转换为程序递归程序设计技术软件结构化设计技术 递归程序设计技术 步骤1 定义参数上的一个良序集合 以便程序一定能中止2 对参数进行适当的分析 其中必须包括一种易于计算的特殊情形作为结束条件 非递归分支 3 计算出特殊情况下的函数值4 找出一般情况下函数值与具有较小参数的函数值之间的等式关系 得到递归分支5 把所有分支用条件表达式综合为一个程序 软件结构化设计技术 结构化设计存在于软件生存期的说明 设计和实现阶段设计阶段的数据流设计设计阶段的数据结构设计技术实现阶段的结构化程序设计技术 数据流设计 1974年作为软件系统设计的自顶向下方法有Constantine提出 突出了模块化的设计思想 力图在软件设计的开始就把所设计的系统划分为若干相互独立的模块 使每个模块要完成的任务明确而单纯 达到程序设计简单 易于理解 调试和修改的目的数据流设计以加强模块的独立性为基础 要求模块间的联系尽可能弱 信息和数据交流尽可能少 模块内部联系尽可能强 信息和数据交流尽可能多 几所谓的弱耦合性和强内聚性设计为获得耦合性弱和内聚性强的模块划分 需要按层次来组织模块 顶层模块负责主要功能变换 顶层模块下属输入 输出和变换模块 当需要输入数据时 顶层模块调用其下属输入模块 之所以需要经过模块传递和变换输入 输出信息 是为了保证设计的弱耦合性和强内聚性 数据结构设计 数据结构设计方法由Jackson提出 这种方法试图把描述问题的数据结构映射为程序结构 因为形式说明中的数据结构通常是定义明确的 所以 从同样的形式说明出发 用此方法可以得到类似的程序结构 结构化程序设计 结构 顺序型 条件选择型和循环型结构定理 任何一个适当程序在功能上等价于一个结构化程序 而且 这个结构化程序可以使用原来程序中的函数 谓词以及赋值语句 条件测试语句定理中的适当程序满足 具有一个入口和一个出口对于程序中的每一条语句都存在一个合法输入 使得程序控制流从输入出发经过这个语句然后达到输出结构化程序的实质是取消转移语句goto 软件避错技术 形式说明可靠性程序设计的基本技术程序验证技术 程序验证技术 可靠程序设计技术可以减少软件故障的发生 但像任何设计过程一样 不能避免设计故障的发生 程序验证技术通过检查程序与其说明的符合性来发现故障 消除故障 从而提高软件可靠性 程序验证技术 程序正确性证明程序的自动证明技术程序测试技术 程序正确性证明 证明定理 用满足输入说明的任一输入执行程序 程序将输出满足输出说明的结果并且终止 程序正确性证明可以分为两个独立的证明 部分正确性证明 即证明如果程序能终止 对于任意合法输入 程序给出正确输出终止性证明 即证明对于任意合法输入 程序能够终止 程序的自动证明技术 程序的正确性证明可以用机械步骤自动完成 即通过给机器提供推理规则 机器能自动完成部分正确性证明困难中间断言的自动生成很困难 致使生成程序变得很复杂如何确认证明程序的正确性 引为证明程序往往比被证明程序复杂得多 程序正确性证明技术以严格的数学分析和逻辑推理为基础 经过证明能保证程序设计的正确性 但这种方法难度大 复杂性高尔未能投入实际使用程序测试技术对常见的故障模型进行测试 尽管通过测试的程序不能保证程序的正确性 甚至也不能保证把程序的故障率或故障数控制在一个规定的量级之下 然而 由于程序测试技术的可行性和令人满意的实践结果 使它得到广泛的应用 程序测试技术 测试方法 根据测试中被测程序是否在输入数据驱动下实际运行 可以把测试分为静态测试和动态测试静态测试 检查程序的语法是否正确 程序结构是否合格 从输入不可到达的语句 不能到达输出的语句 不经入口转入循环体或过程体等都是不合适的结构 是否所有变量都赋了初值或者是否有说明而没有使用的变量动态测试 在输入数据驱动下对程序进行实际运行 然后通过输出响应分析确定程序运行中是否发生了差错 动态测试 可以按非增式的方法进行 即先测每个模块 再测由若干个模块组成的子系统 最后测整个程序系统 在测试模块或子系统时 对其中的全局变量需要构造一个虚拟的测试背景 对变量赋初值或返回值 模块测试应尽可能完全 保证模块处理的各种输入都被测到 子系统测试要求检查模块间的借口操作 包括数据接口 控制接口等 子系统的测试还要经过多级测试系统测试要涉及到整个程序的接口 数据流 控制流 数据结构 程序结构等问题 动态测试 非增式测试的缺点每个模块和子系统都要求建立测试背景子系统的组合数较大 使测试复杂性高 动态测试 增式测试 被测程序是按层次结构方法组织的 则可以按自顶向下的增式测试方法 即先顶层测试 然后依次加入底层的模块测试系统级测试次数减少首先测试和反复测试顶层模块式主要功能模块得到最完全测试高层模块自动为底层模块提供了部分测试背景当发现差错时 故障被局限在新加入的模块内或新加入模块与已测模块的接口上 动态测试 测试数据生成 无法进行穷举法 常用随机测试方法确定测试目标包括测试数据是所有输入测试数据使程序中每条通路至少执行一遍测试数据使程序中每条分支至少执行一遍测试数据使程序中每个语句至少执行一遍 测试数据生成方法 程序测试技术 自动测试工具 自动测试工具是一个综合的自动测试系统 它能够分析程序结构 检查出某些类型的差错并指出可能发生的差错 同时 它能够生成测试数据 驱动被测程序运行 并分析测试响应 输出整理成文的测试结果 SADAT的结构 软件容错技术 概述软件可靠性的基本概念软件避错技术软件容错技术软件N版本设计技术软件恢复技术软件可靠性模型 第二节软件N版本设计技术 N版本的设计方法N版本容错系统的组成N版本的管理程序 N版本的设计方法所谓NVP 就是针对同一任务 采用N N 2 种不同的程序实现方法 独立生成N个功能相同的程序 在一个管理程序的统一协调下并行执行 根据决策算法 从N个结果中选出正确结果 NVP设计原则各版本尽量的不同各版本尽量的独立NVP的生成方法采用不同的算法 产生同一功能的不同版本采用不同的语言 实现同一功能的不同版本由不同的程序员来设计用相同语言的不同版本来实现以上方法的结合 第二节软件N版本设计技术 N版本的设计方法N版本容错系统的组成N版本的管理程序 N版本容错系统的组成运行环境N版本运行在单处理器上N版本运行在多处理器上 多机 N版本的理想运行环境 N版本容错系统的组成版本间的通讯通讯的死锁问题通信信箱的规模选择问题过大会影响速度 过小则增加通信中的排队时间 N版本容错系统的组成同步问题软件N版本系统保持一种 松散的同步 为什么不进行 紧密同步 像硬件 完全同步难以实现不受同步约束 对各版本的执行有利消除共模干扰 N版本容错系统的组成N版本的检测自检测采用编码技术Watchdog专用自检测程序等比较 N版本容错系统的组成版本间的切换错误版本的切除和离线完全清除版本修复正确版本的切入和运行备用版本的初始化写入检测点信息申请在线同步处理进入运行状态 第二节软件N版本设计技术 N版本的设计方法N版本容错系统的组成N版本的管理程序 N版本的管理程序比较向量比较变量状态标志比较状态指示器比较向量比较后 应采取的措施指示各模块是否在规定的时间给出了比较向量向量结果一致 则指示继续往下执行向量结果不一致 利用多模块修改不一致模块控制同步机构 表决程序设计 注意 表决程序是NVP结构的关键 由于表决程序规模不大 程序结构也不复杂 可以用正确性证明技术来保证其正确性值得注意的是 表决程序不是完成简单的多数表决功能 因为计算机字长有限 计算结果往往是近似的 这样 按照不同的算法就可能得到不同的近似结果 因此 即使N份程序都正确 但他们的结果也可能不相等 表决必须考虑这种允许的差异 表决程序要进行故障记录表决器应知道N份程序最大的运行时间差d 当多数程序已输出结果 表决器最多再等d这样长的时间 还没有给出输出的程序被认为发生了差错 第五章软件容错技术 第一节软件可靠性的基本概念第二节软件N版本设计技术第三节软件恢复技术 第三节软件恢复技术 后向恢复技术前向恢复技术恢复块技术 后向恢复技术 Rollcack 对于软件为多模块系统 实际是多进程或多任务同时运行的系统 模块间保持的通信 因此 后向恢复是在多软件模块及其相互通信的情况下进行的 必须要一个后向恢复协议 以保证系统的正确运行 后向恢复协议协议保证 在要求恢复时 能够确定一组恢复点 使程序返回到该点时可以纠正故障影响协议应避免Domino效应 后向恢复协议协议保证 在要求恢复时 能够确定一组恢复点 使程序返回到该点时可以纠正故障影响协议应避免Domino效应协议尽量保持各软件原有的并行性使各软件模块保持独立性 以及恢复过程的透明性使恢复操作尽量减少系统开销具有完整性和一致性 实现后向错误恢复 恢复点的位置错误可能涉及的范围因此 必须要解决恢复点的设置及其保留的各有关软件模块过去的状态 要解决恢复与各软件模块通信的关系 从而解决错误范围的估价问题 向后恢复的实现方法静态规划方法在多软件模块设计中 根据各模块间的会合 设计每一恢复线 在设计中避免Domino效应 缺点是影响原有并行处理能力 容易死锁等无规划方法不考虑各软件模块间的通信关系 各模块各自设计恢复线 当一个模块需要后向恢复时 可根据过去的通信关系自动地建立恢复线动态规划方法不限制系统的动态结构 运行中自动监视系统动态结构变化 并可自动修改系统的动态结构 尽量避免Domino效应 一般情况下 通过自动地在系统中设置恢复点 来达到对动态结构的修改 该方法避开了前两种方法的缺点 但增加系统开销 第三节软件恢复技术 后向恢复技术前向恢复技术恢复块技术 前向恢复技术 第三节软件恢复技术 后向恢复技术前向恢复技术恢复块技术 恢复块技术 RecoveryBlock 恢复块可以是一个过程 子程序 进程 或者是一个任务 ensurebyelseby elsebyelse 恢复块的工作流程 嵌套的恢复块结构 软件容错技术 概述软件可靠性的基本概念软件避错技术软件容错技术软件N版本设计技术软件恢复技术软件可靠性模型 软件可靠性模型 时间模型数据模型播种模型 时间模型 时间模型与硬件可靠性的评价方法类似 把一个软件的可靠度定义为 0 t 内未输出差错的概率 并且 评价的目标也是找出风险函数可靠性增长模型公理模型 可靠性增长模型 最著名的是Shooman提出模型假设 一个软件中的故障数目在t 0时是常数 随着故障被纠正 故障数目逐渐减少经调试后 剩余故障的数目可用公式估计 可靠性增长模型 Shooman模型中 需要确定在调试前软件中的故障数目 这往往是很困难的 公理模型 对于软件故障 如果可以凭经验可以假设它服从某种分布规律 这就是所谓的公理模型最著名的是Halstead提出的 软件科学 模型 此模型假设软件中的故障数B由以下公式确定 播种模型 为了估计出软件中的故障数 可以预先在软件中随机插入s个故障 播种 然后 对软件进行测试 假设共测出n v个故障 其中 n是测出的自身故障的数目 v是测出的插入故障的数目 如果自身故障和插入故障被检测到的概率相等 则软件中自身故障总数的极大似然估计量为N sn v模型假设 自身故障与插入故障被监测到的概率相等 数据模型 在数据模型下 对于一个预先确定的输入环境 软件的可靠度定义为n次连续运行中 软件完成指定任务的概率最早的数据模型是由Nelson在1973年提出