第1章 软件及其开发

1、1软件开发的形式化方法 Formal Methods for Software Development （软件工程中的形式化方法）杜玉越 2参考资料o 古天龙，软件开发的形式化方法，高等教育出版社，2005o Alagar V.S. and Periyasamy K., Specification of Software Systems, Springer-Verlag, New York, 1998o Clark E. and Wing J., Formal Methods: State of the Art and Future Direction. CMU-CS-96-178, CMU

2、Computer Science Technical Report, 1996, 1-22 3课程的主要任务(W2H)o W(Why) 为什么要学习形式化方法?o W(What)形式化方法的基本原理是什么?o H(How) 如何将形式化方法集成到软件开发过程?4掌握内容o 软件开发中形式化的必要性o 形式化方法的数学基础o 典型形式化方法及语言o 形式化方法在软件开发中的应用5课程安排o 概述o 有限状态机及其扩展o Petri网o 进程代数o Pi演算o 时态逻辑o 动态描述逻辑6Chapter 1 软件及其开发软件及其开发概述概述 o 1.1 软件开发的历史软件开发的历史o 1.2 软件危

3、机软件危机o 1.3 软件工程软件工程o 1.4 形式化方法形式化方法 71.1 软件开发的历史软件开发的历史o 软件是与硬件相互依存，与硬件合为一体完成计算机系统功能o 1946-1964：软件费用占20%o 1965-1980: 软件费用占60%o 1981-至今： 软件费用持续上升，现在已达80%以上81.1 软件开发的历史软件开发的历史o 软件开发：把现实世界的需求反映成软件模型，并予以实现的过程o 软件及其开发经历了三个阶段o 第一阶段：程序设计阶段（1946-1956）n从第一台电子数字计算机ENIAC诞生，到高级语言的出现n计算机用于科学计算与工程计算，处理对像是数值数据n个体手

4、工编程，编程工具：汇编语言和机器语言n“软件”一词尚未出现9第二阶段：程序系统阶段（1956-1968）o 1956年J.Backus（美）研制的FORTRAN语言问世，高级语言的诞生o 应用领域：涉及到非数值数据、数据处理o 编程工具：高级语言o 此时的“软件”指程序及其说明书o 开发周期变长，出现了“软件危机”o 正确性、可靠性受到关注10第三阶段：软件工程阶段（1968-）o 1968年在德国北大西洋公约组织北大西洋公约组织 (North Atlantic Treaty Organisation-NATO)召开的软件危机问题的会议上，提出了“软件工程”的概念o 软件应用领域急剧扩大，有一

5、个庞大的市场用户群体o 软件开发方式转向工程方式o 软件开发除高级语言外，还有需求定义语言、软件设计语言等o 出现了面向对象、网络及分布式开发等技术111.2 软件危机o 软件危机（Software Crisis）n 在计算机软件的开发和维护过程中所遇到的一系列严重问题n 1968年在德国北大西洋公约组织北大西洋公约组织NATO召开的召开的国际会议上提出国际会议上提出o 包含两个方面问题包含两个方面问题n 如何开发软件，才能满足不断增长、日趋复杂如何开发软件，才能满足不断增长、日趋复杂的需求的需求n 如何维护数量不断膨胀的软件产品如何维护数量不断膨胀的软件产品121.2 软件危机o 主要表现n

6、 开发成本昂贵开发成本昂贵n 项目进度难控项目进度难控n 质量无法保证质量无法保证n 修改维护困难修改维护困难13 开发成本昂贵开发成本昂贵软件成本日益增长（软件成本日益增长（1）o 1968年，美国花费于软件的投资高达60亿美元，有些系统，特别是军用系统，软件费用要高出硬件费用好几倍，例如美国全球军事指挥控制系统的计算机硬件费用为1亿美元，而软件费用高达7.2亿美元。o 1980年美国政府的财政年度当中，计算机系统方面(软，硬件与服务)共耗资达570亿美元，其中320亿美元(占总数的56)用于计算机软件方面(与同年的美国汽车行业进行简单的比较，美国是当时的世界第一汽车生产大国，汽车的年销售量

7、为900万辆，总的销售额仅为720亿美元。14 开发成本昂贵开发成本昂贵软件成本日益增长（软件成本日益增长（2）o 技术的进步使得计算机硬件的成本持续降低，而软件成本则不断增长，软件成本在计算机系统总成本中所占的比例呈现日益扩大的趋势o 美国空军计算机系统的数据表明，1970年，软件费用约占总费用的60，1975年达到72，1980年达到80，1985年计达到85。（1979年，美国的国防预算为1258亿美元，其中9%用于计算机领域，约113亿美元。在这113亿美元当中，91亿美元（约占80）用于软件投资。15 项目进度难控项目进度难控o 为软件开发制定进度是很困难的事情o 通常根据其复杂性、

8、工作量及进度要求安排人力。o 软件开发不同于传统的机械制造，人多不见得软件开发不同于传统的机械制造，人多不见得力量大力量大。o 如果给落后于计划的项目增添新人，可能会更加延误项目。16 项目进度难控项目进度难控o 1998年，美国企业应用项目不成功率高达75%，其中28%的项目最终被取消，40%的项目周期被无限拖长或资金超出预算。p Brook提出的法则“在已拖延的软件项目上增加在已拖延的软件项目上增加人力只会使其更难按期完成人力只会使其更难按期完成” 。17 质量无法保证质量无法保证 o 1985年11月21日,由于计算机软件的错误,造成纽约纽约银行与美联储电子结算系统银行与美联储电子结算系

9、统收支失衡,发生了超额支付,而这个问题一直到晚上才被发现,纽约银行当日帐务出现了出现了230亿亿的短款。o Therac-25是加拿大原子能公司AECL和一家法国公司CGR联合开发的一种医疗设备，它产生的高能光束或电子流能够杀死人体毒瘤而不会伤害毒瘤附近的人体健康组织。该设备于1982年正式投入生产和使用，在1985年6月到1987年1月的不到两年的时间里，因为软件缺陷引发了因为软件缺陷引发了6起由于电子流或起由于电子流或X-光束的光束的过量使用的医疗事故，造成过量使用的医疗事故，造成4人死亡、人死亡、2人重伤的严人重伤的严重后果重后果。18 质量无法保证（续）质量无法保证（续）o1996年，

10、欧洲航天局阿丽亚娜阿丽亚娜5型（型（Ariane5）火箭火箭在发射后40秒钟后发生爆炸，发射基地上2名法国士兵当场死亡，损耗资产达10亿美元之巨，历时9年的航天计划因此严重受挫。事后专家的调查分析报告指出，爆炸原因在于惯性导航系统软爆炸原因在于惯性导航系统软件技术要求和设计的错误件技术要求和设计的错误。 o2002年，美国商务部的国立标准技术研究所（NIST）发表了一个有关软件缺陷的损失的调查报告。该报告表示：“据推测，据推测，由于软件缺陷而引起的损失额每年高达由于软件缺陷而引起的损失额每年高达595亿美元。这一数字亿美元。这一数字相当于美国国内生产总值的相当于美国国内生产总值的0.6%”。对

11、于一些安全悠关的系对于一些安全悠关的系统，软件的缺陷更是造成了灾难性的后果。统，软件的缺陷更是造成了灾难性的后果。o2007年年10月月30日，北京奥运门票网上预订系统开通首日即日，北京奥运门票网上预订系统开通首日即遭瘫痪，两小时内各个销售渠道仅售出门票约遭瘫痪，两小时内各个销售渠道仅售出门票约9000张。张。19 修改维护困难修改维护困难o 软件的维护任务特别重软件的维护任务特别重o 正式投入使用的商用软件，总是存在着一定数量的错误。o 随着时间的延伸，在不同的运行条件下，软件就会出现故障，就需要维护。o 软件维护是要纠正逻辑缺陷o 当软件系统变得庞大，问题变得复杂时，常常当软件系统变得庞大

12、，问题变得复杂时，常常会发生会发生“纠正一个错误带来更多新的错误！纠正一个错误带来更多新的错误！”的问题。的问题。 20 软件危机的原因软件危机的原因o 客观上客观上主要表现在：主要表现在：n规模的复杂性规模的复杂性n结构的复杂性结构的复杂性n环境的复杂性环境的复杂性n领域的复杂性领域的复杂性n交流的复杂性交流的复杂性 o 主观上主观上主要表现在：主要表现在：n缺乏指导或实施软件设计、开发、维护的有效理论、方缺乏指导或实施软件设计、开发、维护的有效理论、方法及技术法及技术nOR 缺乏有效解决软件设计、开发、维护中相关实际问缺乏有效解决软件设计、开发、维护中相关实际问题的理论、方法及技术题的理论

13、、方法及技术 21 规模的复杂性规模的复杂性 o 以美国宇航局的软件系统为例：以美国宇航局的软件系统为例：19631963年，水星计划的软年，水星计划的软件系统约有件系统约有 200 200万条指令；万条指令；19791979年，哥伦比亚航天飞机年，哥伦比亚航天飞机系统达到了系统达到了40004000万条指令。万条指令。o 软件庞大的规模是引起技术上和心理上挫折的一个重要因素o 在需求分析及生成规格的阶段,由于需要搜集和分析的信息量巨大，从而可能会使得信息不正确或不完整，并且在审查阶段也未能检查出来。o 有人认为：几乎所有与计算机过程控制系统有关的事故几乎所有与计算机过程控制系统有关的事故都是

14、源于这类由软件规模因素所引起的错误。都是源于这类由软件规模因素所引起的错误。22 结构的复杂性结构的复杂性 o 结构复杂性体现在管理和技术两个方面。o 在管理方面，开发小组用来组织和管理开发活动时所采用的层次的宽度和深度，决定了用来管理系统结构的复杂性；o 在技术方面，软件系统的模块结构愈加复杂，模块之间复杂的调用关系以及接口信息往往超模块之间复杂的调用关系以及接口信息往往超过了人们所能接受的程度过了人们所能接受的程度。 23 环境的复杂性环境的复杂性 o 运行中的软件总是受其所处环境的影响，在接收到外界环境的触发事件时，软件应该做出正确的响应。o 许多系统只有当成功地运行于其环境时，才能对其

15、环境进行很好的理解。o 软件运行环境的多样性和异构性给软件开发者带来了更大的挑战。 24 领域的复杂性领域的复杂性 o 软件中所操作的对象仅仅是对应用领域真实对象的模拟o 对于有的应用领域来说，这些模拟只能是近似的。其原因可能是由于对应用领域对象的认识不完全，或者是由于该模型所具有的苛刻条件限制，或者两者兼而有之。o 在某些软件应用领域中，并不存在可以认知的模型，或在某些软件应用领域中，并不存在可以认知的模型，或者没有准确的模型来描绘相应的物理对象的几何、拓扑者没有准确的模型来描绘相应的物理对象的几何、拓扑以及其它特征以及其它特征。o 在这种缺少准确认识的情况下，应用领域的某些方面很可能在软件

16、中不能体现出来。25 交流的复杂性交流的复杂性 o 团队里的每个人参与开发过程中的一个或多个活动。o 对于参与不同开发阶段的人来说，彼此之间明确的交流非常重要。o 成员间交流时使用的媒介往往是自然语言、图、表等非形式化的方式，它们很难准确地描述所开发产品的基本属性。o 这些媒介本身具有二义性，往往会使开发人员产生错误的理解，这种错误将会随着开发过程的进行而逐渐蔓延开来，最终导致灾难性的后果。 26软件危机解决方案o 一类是一类是采用工程的方法来组织和管理软件的采用工程的方法来组织和管理软件的开发，这导致了开发，这导致了软件工程软件工程的产生和发展。的产生和发展。o 一类是从理论上探讨程序正确性

17、和软件可靠从理论上探讨程序正确性和软件可靠性、可信性问题，这推动了性、可信性问题，这推动了软件形式化技术软件形式化技术的研究的研究271.31.3 软件工程软件工程 工程化的软件开发工程化的软件开发 （类似于建筑、汽车、机械等其它行业）（类似于建筑、汽车、机械等其它行业） 设计、生产、维护的规范化及科学化设计、生产、维护的规范化及科学化 不规范不规范规范；非严格规范；非严格严格；非形式严格；非形式形式；形式； 无方法无方法/ /技术技术方法方法/ /技术技术 寻求工程化的软件开发的原理、方法及技术寻求工程化的软件开发的原理、方法及技术281.3 1.3 软件工程软件工程 o19831983年年

18、IEEEIEEE给软件工程下的定义是：给软件工程下的定义是：“软件工程是开发、运行、维护和软件工程是开发、运行、维护和修复软件的系统方法修复软件的系统方法”这个定义相当概括，它主要强调软件工程是系统这个定义相当概括，它主要强调软件工程是系统方法而不是某种神秘的个人技巧。方法而不是某种神秘的个人技巧。 oFairlyFairly认为：认为：“软件工程学是为了在成本限额以内按时完成开发和修改软件工程学是为了在成本限额以内按时完成开发和修改软件产品所需要的系统生产和维护技术及管理学科。软件产品所需要的系统生产和维护技术及管理学科。”这个定义明确指这个定义明确指出了软件工程的目标是在成本限额内按时完成

19、开发和修改软件的工作，出了软件工程的目标是在成本限额内按时完成开发和修改软件的工作，同时也指出了软件工程包含技术和管理两方而的内容。同时也指出了软件工程包含技术和管理两方而的内容。 oFritz BauerFritz Bauer给出了下述定义：给出了下述定义：“软件工程是为了经济地获得可靠的且能软件工程是为了经济地获得可靠的且能在实际机器上有效运行的软件，而建立和使用的完善的工程化原则。在实际机器上有效运行的软件，而建立和使用的完善的工程化原则。”这个定义不仅指出软件工程的目标是经济地开发出高质量的软什，而且这个定义不仅指出软件工程的目标是经济地开发出高质量的软什，而且强调了软件工程是一门工程

20、学科，它应该建立并使用完善的工程化原则。强调了软件工程是一门工程学科，它应该建立并使用完善的工程化原则。o19931993年年IEEEIEEE进一步给出了一个更全面的定义进一步给出了一个更全面的定义“软件上程是：软件上程是： 把系统化把系统化的、规范的、可度量的途径应用于软件并发、运行和维护的过程，也就的、规范的、可度量的途径应用于软件并发、运行和维护的过程，也就是把工程化应用于软件中；是把工程化应用于软件中； 研究中提到的途径。研究中提到的途径。”29软件工程三要素o 方法：提供如何构造软件的技术，是完成软件工程项目的技术手段；o 工具：为软件工程方法提供自动化或半自动化的支持；o 过程：将

21、软件工程的方法和工具综合起来以达到合理、及时地进行计算机软件开发的目的。30软件工程的主要内容o 软件工程过程o 软件生存周期o 软件开发模型o 软件开发方法o 软件工具o 软件开发环境o 计算机辅助软件工程o 软件工程经济学31 软件工程过程o 规定获取、供应、开发、操作及维护软件时，所需实施的过程、活动和任务。o 为各类人员提供一个公共的框架，以便用相同的语言进行交流。o 软件工程过程包括开发过程、管理过程、供软件工程过程包括开发过程、管理过程、供应过程、获取过程、操作过程、维护过程及应过程、获取过程、操作过程、维护过程及支持过程。支持过程。32 软件生命周期o 与软件产品相关的一系列活动

22、的全周期，包括如下与软件产品相关的一系列活动的全周期，包括如下五个活动五个活动：o 需求分析和规格：需求分析，逻辑模型，需求规格；o 软件设计：总体结构设计，具体模块实现算法设计；o 程序编写：软件设计结果的编程实现；o 软件测试：模块测试，组装测试，确认测试；o 运行和维护：软件的维护与修改，时间最长、工作量最大、费用最高的一项活动。33 软件开发模型（软件生命周期模型）o 指从软件项目需求定义开始，直至软件被淘汰，跨指从软件项目需求定义开始，直至软件被淘汰，跨越整个生存期的系统开发、运行和维护所实施的全越整个生存期的系统开发、运行和维护所实施的全部过程、活动和任务的结构框架。部过程、活动和

23、任务的结构框架。o 确立了软件开发各阶段的次序及任务和活动准则，给出了开发过程中所遵守的规定和限制。o 主要软件开发模型：瀑布模型瀑布模型（Waterfall Model）、原型模型原型模型（Prototype Model）、螺旋螺旋模型模型（Spiral Model）、构件模型构件模型（Component Model）、四代技术模型四代技术模型（4GT Model）、变换变换模型模型（Transformational Model）34 软件开发方法o 指在某种思想指导下，使用已定义的一系列技术和表示工具，组织软件开发过程的方法。o 通常表述为一系列的步骤，每一步骤都与相应的技术和表示工具相关

24、。o 目的是有效地得到一个运行系统及其支持文档，并满足有关的质量要求。o 典型的传统软件开发方法：结构化方法、面向数据结构方法、面向对象方法等。35 软件工具o 指用来辅助软件开发、维护和管理的一系列软件。o 可以节省开发时间和费用，提高软件生产率和软件质量。o 从软件过程的观点有：项目管理工具、配置从软件过程的观点有：项目管理工具、配置管理工具、分析和设计工具、编码工具、测管理工具、分析和设计工具、编码工具、测试工具、维护工具等试工具、维护工具等。36 软件开发环境o 支持软件产品生产的软件系统，由软件工具支持软件产品生产的软件系统，由软件工具和集成机制组成和集成机制组成。o 软件工具用于支

25、持软件开发的相关过程、活动和任务o 集成机制为工具集成和软件的开发、管理和维护，提供统一的支持37 计算机辅助软件工程o 旨在实现软件生命周期各个环节的自动化并旨在实现软件生命周期各个环节的自动化并使之成为一个整体使之成为一个整体o 计算机辅助软件工程技术是软件工具和软件开发方法的结合o 它强调解决整个软件开发过程的效率问题，而不是解决个别阶段的问题o 它着眼于软件分析、设计和实现的自动化o 使用图形功能对软件系统进行说明并建立文档38 软件工程经济学o 旨在从经济学的观点，研究、分析如何有效旨在从经济学的观点，研究、分析如何有效地开发、发布软件产品和支持用户使用。地开发、发布软件产品和支持用

26、户使用。o 研究的问题：成本估算技术与成本估算模型的建立和使用、软件工程中不同决策的成本-效益分析、多目标决策分析、不确定性的处理和风险分析、工程估计和控制等。391.41.4 形式化方法形式化方法 （1）o 形式化方法是渗透在软件生命期中各个环节（如：需形式化方法是渗透在软件生命期中各个环节（如：需求、设计、实现、测试等）的数学方法，求、设计、实现、测试等）的数学方法， 或者或者 具有具有严格数学基础的软件开发方法严格数学基础的软件开发方法o 形式化方法的基本含义是借助数学的方法来研究计算形式化方法的基本含义是借助数学的方法来研究计算机科学中的有关问题。机科学中的有关问题。o Encyclo

27、pedia of Software EngineeringEncyclopedia of Software Engineering对形式对形式化方法定义为：化方法定义为：“用于开发计算用于开发计算机系统的形式化方法机系统的形式化方法是基于数学的用于描述系统性质的技术。这样的形式是基于数学的用于描述系统性质的技术。这样的形式化方法提供了一个框架，人们可以在该框架中以系统化方法提供了一个框架，人们可以在该框架中以系统的方式刻画、开发和验证系统的方式刻画、开发和验证系统”。 o 在软件开发的全过程中，凡是采用严格的数学语言，在软件开发的全过程中，凡是采用严格的数学语言，具有精确的数学语义的方法，都称

28、为形式化方法。具有精确的数学语义的方法，都称为形式化方法。401.41.4 形式化方法形式化方法（2 2）o 从广义角度，从广义角度，形式化方法是软件开发过程中分析、形式化方法是软件开发过程中分析、设计及实现的系统工程方法设计及实现的系统工程方法。o 狭义地，狭义地，形式化方法是软件规格（形式化方法是软件规格（specification）和验证（和验证（verification）的方法。的方法。o 形式化方法又分为形式化规格方法和形式化验证方形式化方法又分为形式化规格方法和形式化验证方法。法。o 形式化规格形式化规格是通过具有明确数学定义的文法和语义是通过具有明确数学定义的文法和语义的方法或语

29、言，对软件的期望特性或者行为进行的的方法或语言，对软件的期望特性或者行为进行的精确、简洁描述。精确、简洁描述。o 形式化验证形式化验证是基于已建立的形式化规格，对软件的是基于已建立的形式化规格，对软件的相关特性进行评价的数学分析和证明。相关特性进行评价的数学分析和证明。411.4 1.4 形式化方法形式化方法 （3）o主要目的是保证软件的正确性。主要目的是保证软件的正确性。o形式化方法基于严格的数学，能够对现象、对象、动作等进行简洁、形式化方法基于严格的数学，能够对现象、对象、动作等进行简洁、准确的描述；使得规格的本质可以被展示出来，并且还可以准确的描述；使得规格的本质可以被展示出来，并且还可

30、以以一种以一种有组织的方式来表示系统规格中的抽象层次；可使用数学证明来揭有组织的方式来表示系统规格中的抽象层次；可使用数学证明来揭示规格中的矛盾性和不完整性、以及用来展示设计和规格之间的一示规格中的矛盾性和不完整性、以及用来展示设计和规格之间的一致情况等致情况等。 o2004年年5月，月，IEEE-CS(IEEE-CS(电子电器工程师学会计算机学会电子电器工程师学会计算机学会) )和和ACMACM联联合任合任务组提交了务组提交了CCSE（Computing Curriculum-Software Engineering）最终报告，在该报告给出的最终报告，在该报告给出的SEEK（Software

31、 Engineering Education Knowledge）中，中，“软件的形式化软件的形式化方法（方法（Formal Methods in Software Engineering）”被单被单列为一门列为一门必修课程必修课程（序列号为（序列号为SE313）。421.4 1.4 形式化方法形式化方法 （4）o 形式化方法软件开发采用了软件生命周期的形式化方法软件开发采用了软件生命周期的变换模型变换模型, ,就是把现实世界的需求反映成软就是把现实世界的需求反映成软件的模型化过程。件的模型化过程。o 基于转换模型的软件开发（软件的自动生成）基于转换模型的软件开发（软件的自动生成） o 基于转

32、换模型的软件基于转换模型的软件开发过程实际上可理解开发过程实际上可理解为：为：从最高层的规格开始，通过一系列的求从最高层的规格开始，通过一系列的求精变换步骤，每一步都降低一些抽象程度或精变换步骤，每一步都降低一些抽象程度或增加一些可执行性，最终得到能够指导计算增加一些可执行性，最终得到能够指导计算机明确执行的程序代码机明确执行的程序代码。431.4 1.4 形式化方法形式化方法 （5）o 在进行求精的过程中要保证转换之间的一致在进行求精的过程中要保证转换之间的一致性和正确性，保证所得到的程序是满足最初性和正确性，保证所得到的程序是满足最初规格的规格的。o 这种正确性和一致性可以通过求精过程中所

33、这种正确性和一致性可以通过求精过程中所遵循的一系列规则来保证，也可以在事后采遵循的一系列规则来保证，也可以在事后采用验证工具来证明。用验证工具来证明。o 基于转换模型的软件基于转换模型的软件开发过程包含了三个方开发过程包含了三个方面的活动：面的活动：形式化规格、形式化验证、程序形式化规格、形式化验证、程序求精（求精（refinementrefinement）或变换。或变换。44 形式化规格形式化规格o 软件规格是指对软件系统对象及用来对系统对象进行操作的方法集合，以及对所开发系统的各对象在其生存期间的集体行为的描述。o 形式化方法具有严格的语法和语义，可以准确地描述系统模型，排除矛盾、二义性、

34、含糊性等情况。o 形式规格精确地描述了用户的需求、软件系统的功能及形式规格精确地描述了用户的需求、软件系统的功能及各种性质，其描述的是各种性质，其描述的是“做什么做什么”，而不考虑，而不考虑“怎么怎么做做”。o 要开发出良好的规格，除了应透彻理解、熟练掌握所使用的形式规格语言和方法外，更重要的是对所要描述的系统有全面深入的了解。45 一个简单生命周期模型一个简单生命周期模型 需求分析系统设计I程序开发软件测试软件运行BS行行为规格为规格 codes代码实现代码实现PS程程序规格序规格DS设设计规格计规格系统设计II46 形式化规格形式化规格形式化方法可分为三类：操作类、描述类和双重类。o操作类

35、方法操作类方法：基于状态和转移，通过可执行模型来描述系统，模型本身能够采用静态分析和模型执行而得到验证，这类方法包括有限状态机、Statecharts、Petri网等；o描述类方法描述类方法：基于数学公理和概念，通过逻辑或代数给出系统的状态空间，具有高度抽象的特点，便于通过自动工具进行验证。有：基于代数的方法，如Z、VDM、Larch等；以命题线性时态逻辑（propositional linear temporal logic，简称PLTL）、一阶线性时态逻辑（first-order linear temporal logic，简称FOLTL）、计算树逻辑（computation tree t

36、emporal logic，简称CTL）等基于逻辑的方法；o双重类方法双重类方法：兼有前面二者的特点，既能够通过数学公理和概念来高度抽象地描述系统，又具有状态和转移的可执行特征，这类方法包括扩展状态机/实时时态逻辑（extended state machine / real-time temporal logic，简称ESM/RTTL）、TRIO+、TROL等。47 形式化验证形式化验证 o 软件开发中的绝大部分错误是在需求分析和规格的早期软件开发中的绝大部分错误是在需求分析和规格的早期阶段引入的，这些错误将随着开发的深入而不断扩大，阶段引入的，这些错误将随着开发的深入而不断扩大，且发现的越晚

37、所付出的代价越大且发现的越晚所付出的代价越大。o 传统的软件开发方法中，更多的错误是到编码结束后的测试阶段被检测出来。o 形式化方法中，在开发出形式规格后就进行形式验证，形式化方法中，在开发出形式规格后就进行形式验证，使验证工作提前进行，早期发现错误，减少修改代价。使验证工作提前进行，早期发现错误，减少修改代价。o 形式化验证的主要技术包括模型检验和定理证明。o 模型检验是一种基于有限状态模型，并检验该模型期望特性的技术。模型检验主要适用于有穷状态系统，完全自动化并且验证速度快。48 形式化验证形式化验证o 模型检验方法的一个严重缺陷是“状态爆炸”问题。 o 定理证明采用逻辑公式来规格系统及其

38、性质，应用公理或推理规则证明系统具有某些性质。o 定理证明可以处理无限状态空间问题。o 自动定理证明系统是通用搜索过程，在解决各种组合问题中比较成功o 交互式定理证明系统需要与用户进行交互，要求用户能提供验证中创造性最强部分。49 形式化验证工具及案例形式化验证工具及案例o时态逻辑模型检验工具有EMC、CESAR、SMV、Mur、SPIN、UV、SVE、HyTech、Kronos等；行为一致检验工具有FDR、Cospan/Formal Check等；复合检验工具有HSIS、VIS、STeP、METAFrame等。o贝尔实验室对其高级数据链路控制器在FormalCheck下进行了模型检验功能验证

39、，6个性能进行了规格，其中5个验证无误、另外一个失败，从而进一步发现了一个影响信道流量的Bug；o对某楼宇抗震分布式主动结构控制系统设计进行了规格，所生成的系统模型有2.121019数目的状态。经过模型检验分析发现了影响主动控制效果的计时器设置错误；o基于SMV输入语言建立了IEEE Futurebus+896.1-1991标准下cache一致协议的精确模型，通过SMV验证了模型满足cache一致性的规格。并发现了先前并未找到的潜在协议设计错误。该工作是第一次从IEEE标准中发现错误；oPhilips公司音响设备的控制协议通过HyTech得到了完全自动验证，这是一个具有离散和连续特征的混杂系统

40、验证问题；oAT&T公司的7500条通信软件的SDL源代码进行了验证，从中发现112个错误，约55的初始设计需求在逻辑上不一致。50 形式化验证工具及应用形式化验证工具及应用o已有的定理证明器包括：用户导引自动推演工具有ACL2、Eves、LP、Nqthm、Reve和RRL；证明检验器有Coq、HOL、LEGO、LCF和Nuprl；复合证明器Analytica、PVS和Step；o基于符号代数运算的自动定理证明用于证明Pentium中SRT算法的正确性，检查出了一个由故障商数字选择表引起的错误；oPowerPC和System/390中寄存器传输级、门级、晶体管级的硬件设计模拟为布尔状态

41、转移函数，基于OBDD的算法用来检验不同设计级上状态转移函数的等价性；oNqthm用于Motorola 68020微处理器的规格，进而用来证明不同来源的二进制机器码的正确性；oACL2用于AMD5K86的浮点除微代码的规格和机械证明，ACL2还用来检验浮点方根微的正确性，发现了其中的Bug，并对修改后的微代码进行了正确性机械证明；oACL2用于Motorola复数算术处理器CSP的完全规格，同时对CSP的几个算法进行了验证；oPVS用于航空电子微处理器AAMP5的规格和验证，对209条AAMP5指令中的108条进行了规格，验证了11个有代表性的微代码。51 程序求精程序求精 o程序求精，又称为

42、程序变换，是将自动推理和形式化方法相程序求精，又称为程序变换，是将自动推理和形式化方法相结合而形成的一门新技术，它研究从抽象的形式规格推演出结合而形成的一门新技术，它研究从抽象的形式规格推演出具体的面向计算机的程序代码的全过程具体的面向计算机的程序代码的全过程。o用一个抽象程度低、过程性强的程序，代替一个抽象程度高、过程性弱的程序，并保持它们之间功能的一致。o程序的层次：最高层是不能直接执行的程序，即规格规格，它由抽象的描述语句构成；最低层是可以直接执行的程序，称为程序代码程序代码，它由可执行的命令语句构成；o最高层和最低层之间为一系列混合程序，其中既含有抽象的描述语句，又含有可执行的命令语句

43、。 52 程序求精程序求精o 程序求精技术是形式化方法研究的一个热点，在已出现的许多相关技术中，真正能够应用到实际软件开发过程中的并不多。o 目前比较典型的是IBM Hursly公司以及牛津大学PRG程序设计研究组提出的针对Z规格的求精方法、以及Carroll Morgan的规则求精方案。53 形式化方法的形式化方法的发展历史发展历史 20世纪50年代后期，Backus提出了巴克斯范式（Backus normal formula，简称BNF），作为描述程序设计语言语法的元语言；20世纪60年代，Floyd、Hoare和Manna等开展的程序正确性证明研究推动了形式化方法的发展，他们试图用数学方法来证明程序的正确性并发展成为了各种程序验证方法，但是受程序规模限制这些方法并未达到预期