软件形式化方法与应用专题前言

形式化方法起步于程序理论和语义的研究,历经50余年的发展,成为了计算机科学的重要领域.它使用严格的数学方法,研究并发展软件和硬件系统的建模、设计、开发、验证与演化等技术,为保障系统的正确性、可靠性和安全性提供了重要途径.本专题收录的13篇论文反映了近年来我国学者在软件形式化方法与应用领域的部分研究成果.

形式化方法概貌

形式化方法是基于严格数学基础,对计算机硬件和软件系统进行描述、开发和验证的技术.其数学基础建立在形式语言、语义和推理证明三位一体的形式逻辑系统之上.形式化方法已经以不同程度和不同方式愈来愈多地应用在计算系统生命周期的各个阶段.介绍了形式化方法的发展历程和基本方法体系;以形式规约和形式验证为主线,综述了形式化方法的理论、方法、工具和应用的现状,展示了形式化方法与软件学科其他领域的交叉和融合;分析了形式化方法的启示,并展望了其面临的发展机遇和未来趋势.形式化方法的发展和研究现状表明:其应用已经取得了长足的进步,在提高计算系统的可靠性和安全性方面发挥了重要作用.在当今软件日益成为社会基础设施的时代,形式化方法将与人工智能、网络空间安全、量子计算、生物计算等领域和方向交叉融合,得到更加广阔的应用.研究和建立这种交叉融合的理论和方法不仅重要,而且具有挑战性.

多机器人路径规划的安全性验证

近年来,伴随着人工智能领域的浪潮,机器人越来越多地出现在我们的日常生活中,例如足球机器人、无人机、无人车等.如何保证这些自治机器人尤其是多个机器人在移动过程中的安全,成为人们一直很关心的问题.混成通信顺序进程(hybrid communicating sequential process,简称HCSP)是一种针对混成系统的形式化建模语言,在通信顺序进程(communicating sequential process,简称CSP)的基础上引入了微分方程以描述混成系统中的连续行为和控制逻辑,可以方便而高效地对大型控制系统,尤其是在有通信事件发生时的情形进行形式化建模.用HCSP建模多机器人的路径控制算法,并用定理证明工具HProver进行形式化验证,结果表明,在满足一定的初始条件下,机器人团队在整个运行途中不会发生碰撞.

嵌入式软件智能合成框架及关键科学问题

程序合成是提高软件开发效率和质量的有效途径,也是计算机科学重要的前沿方向之一。首先,概述了程序合成方法的国内外研究现状及其存在的问题。在此基础上,提出了软件知识产权(intellectual property,IP)的概念和一种基于软件IP的嵌入式软件智能合成开发模式(IP-based embedded software intelligent synthesis,IPESIS)及其框架。最后,阐述了IPESIS需要解决的关键科学问题和主要研究内容。IPESIS通过定义领域需求描述语言,在更高的抽象层次上对目标软件进行刻画,以软件IP为粒度缩小程序搜索空间,采用机器学习等人工智能技术自动合成程序,有望突破现有方法的局限,进而实现嵌入式软件开发从手工编程模式到软件IP研发和基于软件IP的智能合成模式的转变。

复杂系统规约、分析与验证发展现状与展望

形式化方法包括计算系统(软硬件和网络)的规约、构造、分析与验证的数学基础、技术和工具。随着安全攸关系统在国民经济和国防等关键领域的应用越来越多,复杂系统可信性问题日益凸显。形式化方法已经成为开发安全可靠的安全攸关系统的关键技术之一,也是解决中国“缺芯少魂”的核心技术之一,同时也是国际学术前沿。文章回顾国内外形式化方法研究现状,分析国内外研究差距,并提出加强中国这方面基础研发的若干建议。

迎接人机物融合泛在计算时代,提升关键软件技术创新与供给能力

1人机物融合泛在计算打开了应用需求的新空间近10年来,云计算、物联网、大数据、人工智能等信息领域技术浪潮风起云涌,推动信息世界、物理世界和人类社会日趋交叉融合,正在逐渐形成万物互联、人机交互、天地一体的泛在计算环境,从而催生人机物融合应用场景不断涌现。一方面,包括汽车、建筑、车间、企业、社区、园区、城市等在内的人机物融合应用场景孕育出一批人机物融合应用需求;另一方面,这些人机物融合应用场景还各自汇聚了一批泛在软硬件异构资源系统,包括计算、网络、感知、数据、服务系统等,正如中国科学院院士吕建所说“应用场景就是计算机”。

高阶时段演算及其完备性

研究如何用时段演算来刻画程序的实时行为 .在实时程序设计里 ,程序变量被解释成时间的函数 .为了定义局部变量声明的语义 ,必须引进关于程序变量的量词 .因此 ,建立高阶时段演算是必要的 .首先建立了高阶时段演算理论 ,然后 ,用高阶时段演算去验证了一些程序的实时性质 ;最后 ,在假设所有程序变量均有穷可变的条件下 ,证明了高阶时段演算在抽象时间域上是完备的 .

中国高速铁路列控系统的形式化分析与验证

高速铁路列控系统的安全与否直接涉及人民的生命财产安全,对高速铁路列控系统进行严格的形式化验证具有重要意义.但是随着高速铁路列控系统软件以及硬件规模的不断增大,系统的复杂性有了很大的提高,直接对高速铁路列控系统进行形式化验证已经变得越来越困难.另一方面,由于图形化建模和仿真表现方式直观且易于理解,在工程实践中已经得到了广泛的应用.因此,为了更好地保证铁路系统的安全,对系统进行仿真,排除部分安全隐患显得尤为重要.本文通过使用Simulink/Stateflow建模工具对高速铁路列控系统的行车许可,等级升级及部分模式转换场景进行了建模.该模型具有普适性,通过修改参数信息,可以对不同的等级转换和模式转换的组合情况进行仿真.本文使用该模型对10种组合情况进行了仿真,发现在某些情况下可能会出现不正常停车或者等级转换失败的现象.类似于测试,仿真仅仅能够发现错误,如未发现错误,也不能证明系统是正确的.因为仿真的这种不完备性,对仿真辅助形式验证在安全攸关系统设计中非常必要.为此,取其中一个不正常停车的场景进行了形式验证,验证结果证明在任何情况下都不能正常停车.

A higher-order duration calculus and its completeness

This paper studies how to describe the real-time behaviour of programs using duration calculus. Since program variables are interpreted as functions over time in real-time programming, and it is inevitable to introduce quantifications over program variables in order to describe local variable declaration and declare local channel and so on. Therefore to establish a higher-order duration calculus (HDC) is necessary. We first establish HDC, then show some real-time properties of programs in terms of HDC, and then, prove that HDC is complete on abstract domains under the assumption that all program variables vary finitely.

An Intuitive Formal Prooffor Deadline Driven Scheduler

This paper presents another formal proof for the correctness of the Deadline Driven Scheduler (DDS). This proof is given in terms of Duration Calculus which provides abstraction for random preemption of processor. Compared with other approaches, this proof relies on many intuitive facts. Therefore this proof is more intuitive, while it is still formal.

时延混成系统的切换控制器合成

如何设计安全、可靠的信息物理融合系统是计算机科学和控制理论面临的一个重大挑战.时延现象在信息物理融合系统中普遍存在,时延对系统的稳定性、安全性和控制性能具有实质性影响.但是在已有时延系统验证和控制器合成的工作中往往忽略时延因素,这会导致在不考虑时延情况下能保证稳定和安全的系统在实际运行时因为时延原因而不再稳定和安全.因为时延使得系统的行为演化不仅与当前状态有关,还依赖于系统的历史状态,所以时延混成系统的验证和控制合成更加困难.本文研究信息物理融合系统在考虑时延情形下切换控制器合成问题,提出基于不变式生成技术的控制器合成方法.首先,利用谱分析和线性化技术将时延系统的微分不变式生成问题归结为有界时间的可达集计算问题;然后,提出基于抽象精化的算法计算时延系统有界时间可达集的上近似;最后,实现本文算法并使用实例验证该方法的有效性.