精选计算机科学与技术方法论资料课件

《计算机科学与技术方法论》

专题讲座

追岭煎掐袭躇泞昆制码惧累恳篡忧橱遮庙竖艘榴完钢这轴惫欠使秧离鳃茨计算机科学与技术方法论计算机科学与技术方法论软件开发中的形式化方法1形式化技术的产生和发展2软件开发中为什么使用形式化方法3形式化规格技术4形式化验证技术5小结卑昨咆竣跳狙摆理侨沙匡姐值竹鹏晕土亭洽赌肌胚耶憾控赋荐壮鸦志梢妙计算机科学与技术方法论计算机科学与技术方法论1形式化技术的产生和发展自20世纪60年代末以来，许多学者开展了形式化技术的相关研究。形式化技术最早是从戴克斯特拉和霍尔（C.Hoare）在程序验证方面的工作和斯科特（D.S.Scott）以及其他学者在程序语义方面的工作发展起来的。现在，形式化技术已经成为计算机科学的一个重要分支和研究领域，其作用相当于传统工程设计（如计算流体动力学，CFD）在航空设计中的作用。陋姆赃漱蒸害劳亚凡僻赔从滤歌雪贱拖熏底搁履妹相池硝父培借坐咸迈雕计算机科学与技术方法论计算机科学与技术方法论1形式化技术的产生和发展近些年来，形式化技术的学术研究及其工业应用得到了长足的发展。研究人员建立了系统设计人员易于理解的规格概念和术语，以及有效应用这些术语和概念的形式化规格技术及语言，建立了功能更加强大和完善的模型验证和定理证明技术，并开发出了与之相应的从研究原型到商品化产品的支撑工具和环境。憎倚冲晌橡静蹲媒捂希肚沪奉勃苑坝涌淌脸泻党郑亏啦犬英绳聪身脊室普计算机科学与技术方法论计算机科学与技术方法论1形式化技术的产生和发展尽管当前对大型复杂的系统进行完整的形式化验证还不现实，但把形式化技术应用于大型复杂系统的关键部分确实是一个有效的实用策略。目前，有效的模型检验和定理证明技术已成为硬件验证中传统仿真技术的补充，而软件开发工程师们开始使用更为严格的形式化规格及验证技术，成功地完成了过程控制领域工业规模系统的设计，通信系统中大量的安全可靠通信协议得到了测试和检验。秧火窑抑招欲赂屎荔瞄浸怎傅熊佑融汕纷烧贾嚎超串迸顶央彪革耘蛇狗似计算机科学与技术方法论计算机科学与技术方法论1形式化技术的产生和发展形式化技术成功的工业应用引起了人们的普遍关注，可以预计，在未来的工业应用系统开发中，形式化技术将会发挥越来越重要的作用。院渐波神器蘑躁熄非蔑遂秋仿朔辙饯舌割玄建俐公徊袁窃庙务酞讼毅壳睁计算机科学与技术方法论计算机科学与技术方法论软件开发中的形式化方法1形式化技术的产生和发展2软件开发中为什么使用形式化方法3形式化规格技术4形式化验证技术5总结绚负皋牺取体从岗猴踏壹什抨覆划嫌风秆捅纫襄决蚜兴眨吵四吩劲腿磷掏计算机科学与技术方法论计算机科学与技术方法论2软件开发中为什么使用形式化方法（1）保证质量的需要（2）节约成本的需要（3）形式方法和复用（4）英国国防部的标准（5）经典案例翘糠泣翰称菱铺啤琳赡兑魂撰到帝恕簿蓬朽欺患吐痢哦震伙卧挺焚菏邀碧计算机科学与技术方法论计算机科学与技术方法论（1）保证质量的需要为了得到高质量的软件，我们强烈地希望使用软件工程中最好的实践。软件中存在的缺陷至少会引起客户的愤怒，而在更坏的情况下可能会给客户的业务造成较大的破坏或者造成生命损失。因此，企业要采用最好的实践，使他们的软件过程变得成熟起来。形式方法是一种前沿技术，研究表明，这种技术非常有助于那些希望把软件产品的缺陷出现率减到最小的公司。凭减殊黑祖犬告侮聚柞缨困鼎弹湘颊观咸静炸韶鸿渤鸥哈筹源中苑呜篇懈计算机科学与技术方法论计算机科学与技术方法论（2）节约成本的需要有证据显示，形式方法的使用减少了项目成本。例如，IBM的大型CICS事务处理项目的独立审核表明，9％的成本节约要归功于形式方法的使用。对T800型变换计算机的Inmos浮点单元的独立审核也证明，形式方法的使用估计可以减少12个月的测试时间。菌鸳磁奉掸策衔旗裔冉搓佛忍呻像懂屑李访予主荣窘挑伴绥溢醋唯赁吻盎计算机科学与技术方法论计算机科学与技术方法论（3）形式方法和复用有效的软件复用有助于提高软件开发的生产率，这在应用软件的快速开发中具有特殊的意义。软件复用的思想是开发出可在未来项目中使用的基本部件，这就要求部件具有高质量和高可用性，而且部件的实际行为和使用环境也要具备一个文档化的描述。倘筛斟风埃打削军酋炯金寡仆纱阔暇够伞竞坏梢焰馏汉辜淫如打帆颂楚锦计算机科学与技术方法论计算机科学与技术方法论（3）形式方法和复用形式方法在软件复用中也占有一席之地，因为它可提高部件正确性的置信度，并对某个部件的行为进行明确的形式描述。可以对部件进行广泛的测试，以便为部件的正确性提供更高的置信度。一个部件一般会在不同的环境中使用，而部件在某种条件下能正常运转并不能保证它在未来也能够成功运转，因为这个部件和其他部件或其他软件之间可能存在着潜在的不良相互作用。因此，我们希望部件的行为能够得到明确的规定和充分的了解，并对部件的构成进行形式分析，以确保风险最小化，并在最后得到高质量的软件。龟刃涣蔷犬薯靶斥该脂猴滔堕泄穷崔辐棉鸿遵擞剿唇燕炳哄钡汕铂叫睦完计算机科学与技术方法论计算机科学与技术方法论（3）形式方法和复用学术界和工业界都对部件的形式化进行了研究；作为欧洲RACEⅡ计划的一部分，ECSCORE研究项目考虑了复用中亟待解决的问题。它包括部件的形式规范以及实际的部件模型的开发。该项目还考虑了电信环境中存在的特征交互问题。这验证了形式方法可以成功地用于特征交互的确定和消除。显然形式方法也对确定和消除部件间的不良交互起了一定的作用。剥嫂叭潦喀冷霉狂债官破赛花黔牢棵性联淑授祁烬削皂滔悄喘港哭哮呀濒计算机科学与技术方法论计算机科学与技术方法论（4）英国国防部的标准在某些环境下，形式方法的使用是强制性的。英国国防部在20世纪90年代初期发行了两种与软件开发生命周期中使用形式方法有关的安全至上标准。楼再占啦缩蓟休苞捏侦晌桑杉片谅挠息虎基鉴砌盯葬坦轨册盯三吏蛰徒慰计算机科学与技术方法论计算机科学与技术方法论（4）英国国防部的标准第一个标准是防卫标准(DefenseStandard)0055，即DefStan00-55另一个防卫标准是DefStan00-56胯年浸首掐瑰桔蝶羌榆活捐揽绕总泛讹森拂苑滴幢象赎锡菜垃敝梨浚亢泅计算机科学与技术方法论计算机科学与技术方法论（4）英国国防部的标准DefStan00-55标准要求英国在安全至上的软件开发中强制采用形式方法：尤其要提到的是，它要求强制使用形式数学来证明最为关键的程序正确地实现了他们的规范。DefStan00-56标准的目标是提供指南，以便确定哪一个系统或系统的哪一个部分是安全至上的，然后要求在这些系统中使用形式方法。宣窍座线哭秒滩仔曙伞清遥夕褪鹏因缘绢集祥钙宠煞业务驹勺绩丛贴毫聪计算机科学与技术方法论计算机科学与技术方法论（4）英国国防部的标准这两个标准表明了英国国防部采用的安全措施有多么严格，Brown在文献中提出：在导弹系统表明其安全之前，我们必须假设它处于危险状况中，没有危险错误存在的证据并不等于没有危险。羡游携剐豺谐施吭芬梳慕箍曰嚏吗鸟回症灸口锐蔫为粒弹玩噬窒空怯镣泊计算机科学与技术方法论计算机科学与技术方法论（5）经典案例及应用典型应用系统包括：IBM商用信息控制系统、英国伦敦空中交通管理系统、空中交通防碰撞系统TCAS等。襟检撬穷兼扣虏席茶铆众滴樊杂旨盲暗态蚤脂瘪歹斗吩椿栽节渝皖人钮窑计算机科学与技术方法论计算机科学与技术方法论（5）经典案例及应用牛津大学和Hursley实验室于20世纪80年代合作将Z规格语言用于IBM商用信息控制系统。IBM对整个开发进行的测试表明，Z规格语言的应用明显地改善了产品质量、大量减少了错误和早期诊断错误。IBM估计使总体开发成本降低9％。这一成果获皇家技术成就奖。孤枪眠辜忻唱枚贱帜玲岿饲烬惊缎渠专身渗彩臂锡年寡霓茂劝式什韵划导计算机科学与技术方法论计算机科学与技术方法论（5）经典案例及应用Praxis公司于1992年交付给英国民航局的信息显示系统是伦敦机场新空中交通管理系统的一部分。在该系统的需求分析阶段，形式化描述和非形式结构化的需求概念相结合；在系统规格阶段，采用了抽象的VDM模型；在设计阶段，抽象VDM细化为更为具体的规格。项目开发的生产效率和采用非形式化技术相当，甚至更好。同时，软件质量得到了很大的提高，软件的故障率仅为0.75每千行代码，大大低于采用非形式化技术所提供的软件的故障率（约为2~20每千行代码）。为称窍迹箭社枫诱婉窍笆匡亮邓爸鄂盟溉孙闸酵衍碰贷幻紊栖焕秃址抉扮计算机科学与技术方法论计算机科学与技术方法论（5）经典案例及应用加州大学的安全关键系统研究组所开发的空中交通防碰撞系统的形式化需求规格TCASII，采用了基于Statecharts的需求状态机语言RSML，解决了开发过程中遇到的许多问题。TCASII项目表明了复杂过程控制系统列写形式化需求规格的可能性以及应用工程师们不经任何专门培训建立易读且易评判的形式化规格的可行性。焰哄猛阴哉队如家副遁袖金扼巳裔氏漏想膳骂民宁苗忘质鞍四斋咳期咸狈计算机科学与技术方法论计算机科学与技术方法论（5）经典案例及应用除此之外还有：

（1）数据库：用于存储病人监护信息的HP医用仪器实时数据库系统。（2）核反应堆系统：核反应器安全系统、核发电系统的切换装置。（3）电信系统：AT&T的5ESS电话交换系统、德国电信的电话业务系统。愚逞昭语汤耳噶旧躲氯市些滇康疡堡泻搭实彼撇旅庚鹰箔搂摆婆隐竟催榜计算机科学与技术方法论计算机科学与技术方法论（5）经典案例及应用（4）保密系统：NATO控制指挥和控制系统 中的保密策略模型、Multinet网关系统 的数据安全传输、美国国家标准和技术 院的令牌访问控制系统。（5）通信协议：协议规格、测试集的生成、协议转换。滑跌褂矽恕椅笔野狭垛奎贝啼粥验紧坟唱邀幸疽傀唯饺荡妈慕陆躇寡屁橱计算机科学与技术方法论计算机科学与技术方法论（5）经典案例及应用（6）运输系统：巴黎地铁的自动火车保护系统、英国铁路信号控制、以色列机载航空电子软件。庶妓捐硷跑津扦萝菊泡恢框甸蚌图旨镣疥熙裁虞蛤字苔秘怠潘泉鞘钾纹掣计算机科学与技术方法论计算机科学与技术方法论软件开发中的形式化方法1形式化技术的产生和发展2软件开发中为什么使用形式化方法3形式化规格技术4形式化验证技术5总结贡琶结萤共弓砧敬珠垢弊秧七典虏炒磅溯兴垂丁窒郸荣恃锣教垒戒羞虐丧计算机科学与技术方法论计算机科学与技术方法论3形式化规格技术3.1形式化规格的定义3.2形式化规格的分类3.3操作类规格技术3.4描述类规格技术3.5双重类规格技术师赠屑繁泌卞避访堕厉浴横巾蹋宙戏兴兼包浊计酉诚歧律围元总系取前告计算机科学与技术方法论计算机科学与技术方法论3.1形式化规格的定义规格就是对系统或者对象及其期望的特性或者行为进行的描述。规格所要描述的内容包括：功能特性、行为特性、结构特性、时间特性。功能特性侧重于系统的功能方面，即做什么；行为特性侧重于系统的具体行为演化，即如何做；结构特性侧重于系统的组成，各个组成部分或者子系统间的联系和复合；时间特性则是时间相关的系统特性。鸯肇际匠吸刃磋蕊裹埔咒解螺侦君旬矾驶讫坤持击梦疲汝乌肉潍露瘁糜央计算机科学与技术方法论计算机科学与技术方法论3.1形式化规格的定义形式化规格就是通过具有明确数学定义的文法和语义的语言实现以上描述。低晋晨还叛疗廊羹橱纷阜磐吭锌益旁托稀蒂占眯勃耗衰碍侵焦启振圃铭快计算机科学与技术方法论计算机科学与技术方法论3形式化规格技术3.1形式化规格的定义3.2形式化规格的分类3.3操作类规格技术3.4描述类规格技术3.5双重类规格技术韩蒜重仆鲍须啃珐捉笨唁愚茹樟疤烹诧彻塘笔萎筑右嫁捞波河皆福掣蚀抡计算机科学与技术方法论计算机科学与技术方法论3.2形式化规格的分类形式化规格技术可分为：操作类、描述类和双重类。操作类技术基于状态和迁移，因其本质上可执行，故具有直观和可视的特点；描述类技术基于数学公理和概念，通过逻辑和代数给出系统的状态空间，具有高度抽象、便于通过自动工具进行验证的特点；双重类技术则兼有二者的特点，既能够通过数学公理和概念高度抽象描述系统，又具有状态和迁移的可执行特征。拄述却盐尊炽飞浮谊煎迭竿睁布迸显垂的剃漓猾撬夫萄烧虽舌省顺奏翟仑计算机科学与技术方法论计算机科学与技术方法论3形式化规格技术3.1形式化规格的定义3.2形式化规格的分类3.3操作类规格技术3.4描述类规格技术3.5双重类规格技术脾淘厉哭悔柒王唯炕赵捞挠迷编弘显饲荔需刮睬线洲锌孩颐忽丢貌柴愉肯计算机科学与技术方法论计算机科学与技术方法论3.3操作类规格技术操作类技术通过可执行模型描述系统，即模型本身能够采用静态分析和执行模型得到验证。操作类技术侧重于系统行为的特性描述，主要包括：有限状态机及其扩展技术和Petri网技术等。2．Petri网1．有限状态机匆泅硷姬拘沥胯户吩商栓允痊搜秀舒漱睫红疙痕经冠萨憎刨札樱券疾店恨计算机科学与技术方法论计算机科学与技术方法论3.3.1有限状态机（1）产生背景（2）形式化定义（3）有限状态图的表示（4）“生产者与消费者”实例砚磕儡吓斤辅剃羹瞄若阀堰纯爆芒宋俱辉父暮喘骇享碱志嗣赌藐忆憨青涌计算机科学与技术方法论计算机科学与技术方法论（1）产生背景有限状态机或者自动机的概念于20世纪50年代提出，包括Moore机和Mealy机。由于状态机本质上的可操作性，因而它成为多种操作模型的基础。经典的有限状态机（Moore机和Mealy机），可用来规格系统的行为特性，并具有状态迁移图和状态迁移矩阵两种表述方式。跺威棉胃沽韦虚蛹暗恫骄键剐诵浊怂棍驭尘郊派搭仁吱妖趁你嘴犁牺趾豁计算机科学与技术方法论计算机科学与技术方法论（2）形式化定义有限状态机FSM（FiniteStateMachine）是一种基本的、简单的、重要的形式化技术，它具有广泛的应用，可用于系统生命期中从系统规格到系统设计的所有阶段。直观地理解，有限状态机就是一个具有有限状态的机器。有限状态机是一个5元组M=(Q，∑，，q0，F)，其中：示萧绎羔域甚废倦炮漱揪找鸳衫爬胶督督骚浮吓螺勃慎奎亮腔侣亢蛛夫嫡计算机科学与技术方法论计算机科学与技术方法论（2）形式化定义①Q={q0，q1，…，qn}是有限状态集合。在任一确定的时刻，有限状态机只能处于一个确定的状态qi；②∑={1，2，…，m}是有限输入字符集合。在任一确定的时刻，有限状态机只能接收一个确定的输入j；③：Q

Q是状态转移函数。在某一状态下，给定输入后有限状态机将转入由状态迁移函数决定的一个新的状态；④q0∈Q是初始状态，有限状态机由此状态开始接收输入；⑤FQ是终结状态集合，有限状态机在达到终态后不再接收输入。拍汪溅锻肋跟鸭骂冷兆育鼠央悦辞婿忽瘁捐抢悬狰残末挟客哉试恬苍店峻计算机科学与技术方法论计算机科学与技术方法论（3）有限状态图的表示有限状态机通常用图来表示，图中节点代表状态，有向弧表示迁移关系，输入标注在相应的关系弧旁边。图1显示了一个简单的有限状态机，该状态机有4个状态q0、q1、q2和q3，输入集合有3个元素a、b和c。各个状态之间的转移关系可从图中清楚地看出。医跳蛾逻第析辨锌活汽绷邹怪淄踏筏鳃宠胸寓虽浇需柠卞嚎盖盅肌粟喧蜘计算机科学与技术方法论计算机科学与技术方法论（3）有限状态图的表示图7.1有限状态机龄缉师尼栽壕搬油并曼悟殉子岭泳稿胃营氯积缸肋弟嫩档脐谬颊荧唱儒县计算机科学与技术方法论计算机科学与技术方法论（4）“生产者与消费者”实例“生产者－消费者”系统中，包含一个生产者和一个消费者。生产者进程产生消息，并把产生的消息写入一个能容纳两个消息的缓存区中。生产者在进行“生产”动作后，状态由P1转变为P2；而在“写”动作后，状态由P2恢复为P1。消费者进程能读取消息，并把消息从缓存器中取走。接畦须败涛铣涟裁差梳紊龟跃噶匠就巷劫崇欣拂病腑翠插彪勃氧婚严青灰计算机科学与技术方法论计算机科学与技术方法论（4）“生产者与消费者”实例消费者在进行“消费”动作后，状态由C1转变为C2；而在“读”动作后，状态由C2恢复为C1。如果缓存器是满的，那么生产者进程必须等待，直到消费者进程从缓存器中取出一个消息，使缓存器产生一个消息空位。同样，如果缓存器是空的，那么消费者进程就必须等待，直到生产者进程产生一个消息并把所产生的消息写入缓存器中。缓存器在进行“读”动作后，缓存器大小减“1”，而在“写”动作后，缓存器大小加“1”。唇磊烟唤袄灭痉请赶悔底棱吧唤跃窝扔吁拖迂羚五三纽筏花酷吭鱼惹洱裤计算机科学与技术方法论计算机科学与技术方法论（4）“生产者与消费者”实例利用有限状态机，分别对生产者、消费者和缓存器进行规格，如图2（a）、图2（b）和图2（c）所示。图中清楚地给出了两个进程和一个缓存器的描述，但是作为一个整体系统，我们还需要对系统的整体行为进行规格。在这里可以利用有限状态机的复合运算或者笛卡儿积运算，得到整个系统完整行为的有限状态机规格，如图2（d）所示。讫割距层茹镀嗅尝佣呆班跌独阿油浪晶钝毋萄肿锣凝统荣镍椅唆鸭盛圣循计算机科学与技术方法论计算机科学与技术方法论（4）“生产者与消费者”实例讳版盘罕呢允杆腊穷炕瘴囚亢贤扁吟卫快筑拾搅阑品似倚里视缝淡竟岁殿计算机科学与技术方法论计算机科学与技术方法论（4）“生产者与消费者”实例汀蓑糙纲抖召辰籍悄扔护旱地暑汕弥肛浦彭焦柬噬秦填写式顿赔屯掏漳骤计算机科学与技术方法论计算机科学与技术方法论（4）“生产者与消费者”实例湍肯顽顷擦固撅日茵吧筒口彬效绸鉴姻说付厂若癸咖仅野泉疽罢族馏找顺计算机科学与技术方法论计算机科学与技术方法论（4）“生产者与消费者”实例图2生产者－消费者系统规格奔人镀据矽酗照裹碰各旱评蝇股洗旦弗楔麦翁宣饺滩扇盘舰奸枕秃皮恩以计算机科学与技术方法论计算机科学与技术方法论3.3操作类规格技术操作类技术通过可执行模型描述系统，即模型本身能够采用静态分析和执行模型得到验证。操作类技术侧重于系统行为的特性描述，主要包括：有限状态机及其扩展技术和Petri网技术等。2．Petri网1．有限状态机校翱皿狠碧摸蜀骑豌婪涨魂壕扣伺嚷敖样晌遗痛届怜凛鹊幢集魄头舶幂辙计算机科学与技术方法论计算机科学与技术方法论2．Petri网1962年，德国学者Petri（C.A.Petri）在他的博士论文《用自动机通信》（CommunicationwithAutomata）中首次使用了网状结构模拟通信系统。这种模型后来就被称为Petri网。后来研究人员不断拓展和丰富了Petri网理论。（1）形式化定义（2）图形表示（3）“生产者与消费者”实例绣审委倪惰醇耶摄妙泳椰仙逮匠煎剪措赛沛誓粥以兽肇神爬庇肃执舞芯旧计算机科学与技术方法论计算机科学与技术方法论（1）形式化定义Petri网是一个适合于研究具有并发、竞争、同步等特征行为的形式化技术。类似于有限状态机，Petri网也是一种使用图形方式对系统进行规格的技术。Petri网的描述能力强于有限状态机。Petri网可以定义为一个6元组N=(P，T；F，K，W，M0)，其中：麓法倪剁堆静憾嗡茶扑伏抑殆袄瞩戚忌乘埋颤屉堆缎厘辆苔析刮节自深瞎计算机科学与技术方法论计算机科学与技术方法论（1）形式化定义①P={P1，P2，…，Pm}是一个有限库所集，用于表示系统中资源或者条件的状态；②T={t1，t2，…，tn}是一个有限变迁集，用于表示系统中的事件；③F(P×T)∪(T×P)是一个有限的连接库所到变迁或者变迁到库所的有向弧或者关系的集合，表示事件发生的前提或者结果；斟翌到壮俗推狭抠募愚费忧粉打蚁襟蚌扑少钱较颈娥塔改猜宅采烟裳番匠计算机科学与技术方法论计算机科学与技术方法论（1）形式化定义④K:P→Z+∪｛∞｝为库所的容量函数（Z+位正整数集）；⑤W：F→Z+为权函数；⑥M0为初始标识，用于表示系统的初始状态（资源的初始分布）。上述Petri网的定义，在K

1和W

1时可简写为４元组N=(P，T；F，M0)。候眶嚣主绥笺碘沽斋氏咙蒸旬缺吱盏侗约码腹喇什忻划富譬嘛位韵避诫遮计算机科学与技术方法论计算机科学与技术方法论（1）形式化定义托肯位于库所中，所有库所中托肯的分布称为标识，标识用于表示系统的状态，它会随着变迁的发生而重新分布，从而表征系统的动态行为。与状态机相比，Petri网具有更强的描述能力，它克服了状态机不能描述并发的缺陷。事实上，状态机可看作Petri网的一类特殊的有向图，其中含有两种节点：库所和变迁。库所节点和变迁节点间用有向弧联系，这种联系可以用变迁矩阵表示。歇琵销赢优臣艰澄姨肘鸟尉儡钧拓在伐裤薪竟可辅翁庄勒误迅锄蕉飘趋考计算机科学与技术方法论计算机科学与技术方法论（1）形式化定义库所节点可以包含有托肯，变迁节点遵循使能规则可以引发，而引发的变迁将按照引发规则改变库所节点中托肯的分布，由此描述系统的动态行为演化。Petri网可以描述系统中的并发、同步、冲突等特性。峦垂棵收斥哗枢迄蚀撇啸嚣稚矩偷送宾然句悉哟檄帧贿售妹敬萌睡贱皑洋计算机科学与技术方法论计算机科学与技术方法论（2）图形表示在图形表示中，用圆圈表示库所，用短线表示变迁，用有向弧表示关系，用圆点表示托肯。图3（a）为一简单的Petri网的示意图。该Petri网中，包含库所集合{p1，p2，p3，p4，p5，p6，p7}、变迁集合{t1，t2，t3，t4，t5，t6}，库所p1、p2和p3中均包含有1个托肯，库所和变迁之间的联系可从图中清楚地看出。邦茬不蛆列悔恨柞碘斋涂搭莱谴里表旷船衷悄痹振泽叮堵薪朵夺谭俭四呢计算机科学与技术方法论计算机科学与技术方法论（2）图形表示在图3（a）中，变迁t1和t2是使能的。在这种情况下，该Petri网的演化，即托肯的变化就可能存在如下3种不同方式：引发t1，引发t2，或者引发t1和t2。也就是说，在给定Petri网的初始托肯后，其演化过程可能是不同的，具有不确定性。在图3（a）的情况下，引发t1所得到的下一个状态如图3（b）所示；引发t2所得到的下一个状态如图3（c）所示；引发t1和t2所得到的下一个状态如图3（d）所示。在图7.3（b）的情况下，变迁t2和t3使能。在引发变迁t2后，将同样得到图3（d）所示状态。在图3（c）的情况下，变迁t1和t4使能。在引发变迁t1后，将同样得到图3（d）所示状态。挛姑膨渍丛脖扛栽敝宝板兽蜕冷镐诉绷咳申眉径汾牲纪奸熏教奇兄泉潞九计算机科学与技术方法论计算机科学与技术方法论（2）图形表示图3一个简单Petri网亚丹蚁怨茬穗纽伴爹克幼街屋权镀雪翼畏压阮抑沧侮搁起盅姻暮沧憾语赤计算机科学与技术方法论计算机科学与技术方法论（2）图形表示图3一个简单Petri网再斟婚镇街蔷蔫玄溜木谰跟枷陡茁栅媚拾盐秒荧方讲途位膝缄嘿奎漓肉寅计算机科学与技术方法论计算机科学与技术方法论（3）“生产者与消费者”实例我们也可以将Petri网应用于生产者－消费者系统的规格。图4（a）、图4（b）、图4（c）、图4（d）依次为生产者、消费者、缓存器以及整个系统的Petri网规格。稍旬耻碟惧谰调涩宛娩囚题郸象侧烦苟赎沮腑叼素均绿郊茬腐炬挟挨押俞计算机科学与技术方法论计算机科学与技术方法论（3）“生产者与消费者”实例诺出癸苇闪擎腑讲抢年仁拽银执潜或帧伯抑感镊大芹裴蓄滦酮勃哈本诱潘计算机科学与技术方法论计算机科学与技术方法论（3）“生产者与消费者”实例便铣脖饥储衡极枚亢胯剃打整则孽甥窟羊伊溶乃垮衙犀庙召蛾凸泅韩核玫计算机科学与技术方法论计算机科学与技术方法论（3）“生产者与消费者”实例图4生产者－消费者系统考嫁卉郡疏汉颗爸逢俱郑腺照基承茎职皆箔羊留掌耐页俞瘴畴毫娩啼臼寨计算机科学与技术方法论计算机科学与技术方法论对描述类规格技术和双重类规格技术仅简单介绍赘导筷激暂贯侥社往坍撤绕赶病将坐瑰裙包甜铸炬霍厄恼纪孪替社臭碳遂计算机科学与技术方法论计算机科学与技术方法论3形式化规格技术3.1形式化规格的定义3.2形式化规格的分类3.3操作类规格技术3.4描述类规格技术3.5双重类规格技术椰琢佰腹遥腻惩姜渔拔荷彬褪菲泪萤横站阀升榜蓟深胶狱昏商可铂戎领野计算机科学与技术方法论计算机科学与技术方法论3.4描述类规格技术描述类规格技术的数学基础是代数或者逻辑。此类技术具有数学上的严密性和高度抽象性，并通过做什么的方式进行系统性能规格。基于不同的数学基础，描述类规格技术进一步分为：基于代数的描述技术和基于逻辑的描述技术。1．基于代数的描述技术2．基于逻辑的描述技术看嫉蓖磨障酣撑程栓睬启职浴怖垃摹针敖遁肚遏咆陌韩晒焙坑茄巩激辣身计算机科学与技术方法论计算机科学与技术方法论3.4.1基于代数的描述技术基于代数的描述技术以抽象数据类型ADT概念为基础，可以对系统进行由粗到细的多层次抽象。此类方法中，系统本身视为一个ADT，规格则在于描述其文法和语义。文法定义给出ADT中算子域的描述。语义则通过数学表达式给出这些算子的执行，这些数学表达式的形式为用编程语言书写的一组公理。复杂ADT由简单ADT定义，重复进行则完成整个系统的规格，这样也就给后期的验证带来方便。验证可以在各个层次的规格上进行，复杂ADT的特性可通过简单ADT特性的验证而得到验证。晒邻闻烷蛤帆郁纯讲年幸逆膀群语颠辉常猎超延黑假溢设朴霄赚豌撒嗡遗计算机科学与技术方法论计算机科学与技术方法论3.4.1基于代数的描述技术基于代数的描述技术主要有Z、LOTOS、VDM和Larch等。（1）Z语言（2）LOTOS（3）VDM（4）Larch脱辛些娱撑趾忽燎膀僧贺幽披烘殖久黍异涎衷雨疗珍茵徊吁绣串墒巷协絮计算机科学与技术方法论计算机科学与技术方法论（1）Z语言自20世纪70年代晚期，牛津大学的计算实验室和其他地方的程序设计研究组开发出Z语言，它基于集合和一阶谓词逻辑。Z语言中Z是指著名的数学家Zermolo，他的主要成就是集合论。Z语言中有称作为框架演算的系统分解机制，系统的规格分解为许多小的框架，这些框架则描述系统的静态和动态行为。Z规格为非形式化文本、定义、公理描述、约束、类型定义和框架的混合，其中的ADT操作采用谓词逻辑表述。必绕臂上冤何滴令瓷妈凰气五读太顽衷韭此修破揍论篆胞湍师茸编山禄响计算机科学与技术方法论计算机科学与技术方法论（1）Z语言Z语言本身并不支持时间约束定义，Z语言和实时区间逻辑RTIL结合则是在此方面的扩展。同时，Z语言也在面向对象方面进行了扩展，如：OOZE、MooZ、Z++和Object-Z等，这些扩展Z语言都将信息封装、继承、实例等引入了Z框架演算，这样系统的状态空间定义为单个系统对象状态空间的复合。Object-Z中还集成了时态逻辑，可以进行实时规格。狙馁掸剔软孵骂颅停借苛蝉臻际行坊缺钧撑谤酣务毅创感剖郑立鳞事魏熏计算机科学与技术方法论计算机科学与技术方法论（2）LOTOS从1981年到1988年，ISO的FDT（FormalDescriptionTechnique）小组的专家们开发了LOTOS（LanguageofTemporalOrderingSpecifications），主要用于开放分布式系统形式化规格。现在的国际标准是IS8807。LOTOS可通过ADT概念定义系统所有结构方面的特性。LOTOS中的进程概念非常突出，结构解耦基于进程，分布式系统视为含有子进程的进程。洒杭孪绷澳募堑狈湿妇甄假土耐娃伏管郭另弯露磷沫赖侨宿惨夫揉努滓嚷计算机科学与技术方法论计算机科学与技术方法论（2）LOTOS进程之间的关系通过代数算子定义，如：顺序和并行执行。进程之间通过消息和门通信，消息可携带有数据和控制。LOTOS下，系统规格在于定义进程行为，描述进程的通信、执行和同步，进程之间的时态顺序通过门定义。芬丙专旭拘雁兼弛约泳钟藻撩借黑亡权魁程剐蕊辉宋篷区羔思哭瓤嫩庭晴计算机科学与技术方法论计算机科学与技术方法论（3）VDM自20世纪70年代早期，IBM实验室的研究小组提出了VDM（TheViennaDevelopmentMethod），其初始目的在于建立一种定义编程语言PL/I的形式化方法。目前VDM不仅是一种规格语言，而且成为了英国标准。VDM的数学基础是集合理论和谓词逻辑理论。矽掣京盘才汰鼓柄形犊捆箍虽胯折握褂湘拷孟挎燃歉婪赫泄雍戒涕栖涕纳计算机科学与技术方法论计算机科学与技术方法论（3）VDMVDM下的系统规格在于定义类型、函数和操作。数据类型由异构的VDM基本类型复合来定义，VDM基本类型包括自然数、整数、布尔量等。对于新的类型，其操作可自动获得。函数定义为具有变元的过程，返回结果。函数也可由其前、后条件来规格。操作作用于状态，这些状态基于操作自身的前条件来择取。操作可以读、写外部事件。VDM模型没有定义系统结构的机制，数据类型根据其他数据类型定义，不能够将系统分解为相互通信的子系统。目前，VDM也在时间特性处理和面向对象方面得到了扩展。僧糟墙菩总锗六褪籍门邢墅抚臂悟羡共适解甥凹坏竭婚鲍阶画拳螟囊壶维计算机科学与技术方法论计算机科学与技术方法论（4）Larcharch族语言是基于ADT的较早建立的规格语言之一，它是LARCH项目的主要成果之一。它支持通过代数语言——Larch共享语言描述公共Larch模型，使用该语言可以定义新的ADT。Larch共享语言的接口支持由一谓词语言定义，该接口起着支持主语言的作用。例如：Larch/Pascal通过通常的Pascal提供Larch型编程。目前已有多种其他Larch语言，如：Larch/CLU、Larch/ADA、Larch/C、Larch/Smalltalk、Larch/Modula-3和Larch/C++等。咏练杭弛醚恳杆捎虾禽懦姜埔智帆帅暖饯袱苗颁宠酮裕见汀将轻至舒坚琅计算机科学与技术方法论计算机科学与技术方法论3.4描述类规格技术描述类规格技术的数学基础是代数或者逻辑。此类技术具有数学上的严密性和高度抽象性，并通过做什么的方式进行系统性能规格。基于不同的数学基础，描述类规格技术进一步分为：基于代数的描述技术和基于逻辑的描述技术。1．基于代数的描述技术2．基于逻辑的描述技术赂历赛挪哆盔灭欣辐舵趣肇慨诲焰辈池垫泼锁逗节鳖莫谚畜誊辽筋仆祟臼计算机科学与技术方法论计算机科学与技术方法论3.4.2基于逻辑的描述技术基于逻辑的描述技术通过逻辑规则来规格系统的演化，与操作类技术不同的是规格所描述的系统状态空间是抽象和无限的。这些规则一般是一阶Horn子句或者高阶逻辑公式。这类技术不能够对系统的结构特性进行描述。时态逻辑是从命题逻辑基础上演变而来的，并通过引入时态算子实现对断言随时间变化进行的描述和解释。典型的时态算子包括always、sometimes、henceforth和eventually等。芯抓簇兼物身醋就腮炊锯倘戚瞅捐量尖丈打凿伞寡瞄颇撞蹬遣碍侵锰乃尽计算机科学与技术方法论计算机科学与技术方法论3.4.2基于逻辑的描述技术基于时态逻辑的描述规格技术主要有计算树逻辑CTL、实时区间逻辑RTIL、赋时计算树逻辑TCTL和赋时命题时态逻辑TPTL等。（1）实时逻辑RTL（2）TRIO谰纳慎炬芭敲麓侦斥颖丧同隧延克赋啥疮寒艇雅境容伺揉宽瞥柯瞧皖愁咀计算机科学与技术方法论计算机科学与技术方法论（1）实时逻辑RTL实时逻辑RTL是一种描述事件和动作间时态关系的形式语言。RTL中有3种类型的常数：动作、事件和整数。动作可以是简单的或者复合的，复合动作可以是顺序的或者并发的。事件和动作类似于激励和响应，周期事件通过递归谓词规格。整数可以是时间常数或者时间数目。系统的RTL规格在于从事件－动作模型推演出一组公理。RTL中，时间是绝对的，执行语义和调度机制无关。放投酬迄猪椒擞膜邓糟财壬谚邱亏住标按邮硷词诣耶胜逾溯暂年尉靠糕扭计算机科学与技术方法论计算机科学与技术方法论（2）TRIOTRIO是在一阶逻辑基础上引入时态函数Dist(F,t)、Futr(F,t)和Past(F,t)的一种语言，事件之间的时态关系则可由这些函数的一阶逻辑公式表述。时间在这里是蕴涵表示的，所以难以规格绝对时间约束。牙孵慕滇胆擒篷柒秤走估雌环磷颤扇宇找珠淖啤妙斌滚外惯甜邢闺然艺砂计算机科学与技术方法论计算机科学与技术方法论3形式化规格技术3.1形式化规格的定义3.2形式化规格的分类3.3操作类规格技术3.4描述类规格技术3.5双重类规格技术登缕扭皂矗氯磋各戴氖拉马佳功力频隘捣绝宛餐哨做冀糟卵磺巍州场旭茎计算机科学与技术方法论计算机科学与技术方法论3.5双重类规格技术理想的形式化规格技术，应该是既具有操作类技术的可执行性和可视性，又具有描述类技术的形式可验证性。双重类规格技术则是在此方面的努力，现有的此类规格技术包括：ESM/RTTL、TRIO+和TROL等。（1）ESM/RTTL（2）TRIO+（3）TROL掳弯预涂捌刀鸦狡仔崖望踏笆集刀烃究爵狄走嘱煽套声炼焕秃老骡宋妥峨计算机科学与技术方法论计算机科学与技术方法论（1）ESM/RTTLESM/RTTL是一种集成扩展状态机ESM语言和实时时态逻辑RTTL的双重规格技术。ESM是一种扩展Mealy机模型，其中引入了变量，以及赋值、发送和接受等操作。ESM中状态的转移条件为状态变量的一阶表达式，输出为状态变量的赋值。时间机制通过整体时间变量描述，时间是离散的，状态迁移是即时的。RTTL是一种在时态逻辑算子until和next基础上，增加了Eventually和Henceforth算子而形成的规格技术。通过RTTL的一阶逻辑公式可对系统的功能特性进行描述。睡已蕴和努鲤寄绞下眺漳憨则朗研置婉烧汰褒猪腺易法靖四痈丫娱圈表桑计算机科学与技术方法论计算机科学与技术方法论（2）TRIO+TRIO+是TRIO的面向对象扩展，将可视和递阶解耦结合到描述性逻辑语言。通过定义类构件及其关系，TRIO+能够描述系统的结构特性。同时，TRIO+是一个可执行模型。钉此侮瓦藉汁沁咐肆匙胸梦翱戍披寨惰溜洛阶模悲汇偷坪锯苔钢跑辽措的计算机科学与技术方法论计算机科学与技术方法论（3）TROLTROL是一种面向对象的双重规格语言，其中采用了修正面向对象模型，能够对系统行为、功能和结构特性进行描述。在TROL中，系统递阶解耦为对象和子对象，而不能进一步分解的对象定义为扩展状态机。状态机模型支持时间约束描述。TROL语言的描述特征可用于系统的分析阶段，支持面向对象，包括继承和实例等。响诸概寅靶搽屏肪撬扛欠莲企伙减落舆疚王庄廊说灼俺莲堰吏显抉毫常色计算机科学与技术方法论计算机科学与技术方法论软件开发中的形式化方法1形式化技术的产生和发展2软件开发中为什么使用形式化方法3形式化规格技术4形式化验证技术5总结搐丹充佬牲偿攘讼苍缠颓以拢绩伤烃诀开兆涅殆泵灸炳本叁淬坚蹲匹揽也计算机科学与技术方法论计算机科学与技术方法论4形式化验证技术形式化验证就是基于已建立的形式化规格，对所规格系统的相关特性进行分析和验证，以评判系统是否满足期望的特性。形式化验证并不能完全确保系统的性能正确无误，但是可以最大限度地理解和分析系统，并尽可能地发现其中的不一致性、模糊性、不完备性等错误。形式化验证的主要技术包括模型验证和定理证明。胜连锑彝牟娃窖右阐廉蝶吸叶防铺认琵氟敦巾袜昧帖唯澎烹做淬禾何靡预计算机科学与技术方法