形式化方法与工具专刊前言

形式化方法是指有严格数学基础的软件和系统开发方法,支持计算机系统及软件的规约、设计、验证与演化等活动.随着高可信软件的兴起,形式化方法作为重要的途径,关注度日益提高.其作用不仅深化了人们对计算系统规律的认识,而且支持了计算系统开发、运行和演化之工具、平台、环境的构建.本专刊收录的11篇论文反映了近年来我国学者在形式化方法与工具领域的部分研究成果.     

轨道交通控制软件中基于场景的需求分析方法

针对轨道交通控制软件的形式化方法,在实际工程应用中存在形式化建模和系统级场景验证困难的问题。提出一种面向轨道交通领域的形式化建模和需求确认及验证方法。通过非形式化、半形式化到形式化规约三步演化过程,为形式化规约构建提供模板。在对需求的确认和验证中,根据形式化规范建立需求模型,导出相关图表,基于此检查领域专家关注的场景。同时制定场景描述规则,使场景可以在需求模型中正确执行。在此基础上,从特殊变量、效率、场景质量三方面对场景进行优化,更充分地验证需求的正确性。实验结果表明,对于典型车载控制软件,该方法较传统分析方法可多探测到10%的潜在缺陷,效率提升80%以上。     

基于场景分析的系统形式化模型生成方法

采用形式化方法对系统的安全性进行分析与验证,是构造可靠安全软件系统的一个重要途径。当前的形式化安全分析方法,面临着系统的形式化建模难的问题。以铁路车站联锁系统中基本进路建立为例,提出基于场景分析的系统形式化模型生成方法。该方法首先采用OCL前/后置条件分析法对UML时序场景作一致性分析,然后将UML时序图中对象交互的行为序列转换成FSP进程代数模型,进而得到系统的形式化模型。该方法为系统的形式化建模提供了新思路,从安全质量方面改善了安全苛求软件的设计与开发,丰厚了基于模型的软件形式化开发方法。     

计算机科学丛书——软件可靠性方法

用于创建可靠软件的形式化方法一直处于不断的开发和改进之中。最近,人们对于形式化方法工具的重要组成有了更深入的理解,从软硬件开发业界逐渐接受可靠性工具这一点就可以体现出来。     

TEFL:一种文本式特征建模语言

特征模型已经成为软件产品线工程中共性/可变性建模的事实标准.现有基于特征图的建模工具由于在模型表达能力、严谨的形式化语义等方面的不足限制了其在工业界的应用.为了消除这些建模中的缺陷,为基于特征的产品线开发提供一个坚实的支撑环境,提出文本式特征建模语言TEFL,介绍其具体语法、抽象语法,以及形式化语义;开发一个基于Eclipse的语言编辑器原型;给出了面向XML和Java语言应用转化方法和工具;分析了与现有文本式建模技术相比所具有的优势与不足,并指出在特征建模及其工具技术方面的进一步的工作方向.     

AADL模型的形式化研究

在嵌入式系统建模领域,AADL以其软硬件协同建模的特点已经逐渐成为业界的标准。围绕AADL的形式化特点,国内外众多学者展开了热烈的讨论。为了帮助系统开发人员深入了解AADL,指导软件开发进程,提高基于AADL模型的软件开发效率,分别从AADL模型可靠性分析、可调度性分析以及AADL模型测试这三个不同角度综述了已经出现的各种AADL形式化验证理论,对比分析了它们的优点和不足。简要介绍有关AADL验证工具,研究基于AADL模型的嵌入式开发平台的构建。     

AADL模型的形式化研究

在嵌入式系统建模领域,AADL以其软硬件协同建模的特点已经逐渐成为业界的标准。围绕AADL的形式化特点,国内外众多学者展开了热烈的讨论。为了帮助系统开发人员深入了解AADL,指导软件开发进程,提高基于AADL模型的软件开发效率,分别从AADL模型可靠性分析、可调度性分析以及AADL模型测试这三个不同角度综述了已经出现的各种AADL形式化验证理论,对比分析了它们的优点和不足。简要介绍有关AADL验证工具,研究基于AADL模型的嵌入式开发平台的构建。     

TCBV:一种构件时序行为建模与相容性验证工具

利用形式化方法对复杂实时构件系统的时序行为进行建模与验证对于提高安全攸关实时构件系统的正确性、可靠性与安全性具有重要意义。介绍了基于时间行为协议的构件时序行为的形式化建模和相容性验证方法,给出了时间行为协议建模与相容性验证工具TCBV的系统架构与功能模块。TCBV应用方便,能够实现实时构件时序行为模型的图形化表示,并可对复杂交互行为的相容性进行自动验证。结合应用实例,介绍了如何利用TCBV对复杂实时构件系统的时序行为进行建模和验证。最后,将TCBV与其它相关工具进行了比较。     

形式化方法概貌

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

一种并发系统的规约方法

提出了并发系统的一种规约方法．这一方法可用于对并发系统进行建模和对模型的验证．将形式化工具融入到一种二维的规约方法中,这样就能使形式化工具更易于应用到并发软件的开发过程中．此外,还提出了一种并发系统的形式化抽象模型．     

ASM-based formal design of an adaptivity component for a Cloud system

The request of formal methods for the specification and analysis of distributed systems is nowadays increasing, especially when considering the development of Cloud systems and Web applications. This is due to the fact that modeling languages currently used in these areas have informal definitions and ambiguous semantics, and therefore their use may be unreliable. Thanks to their mathematical foundation, formal methods can guarantee rigorous system design, leading to precise models where requirements can be validated and properties can be assured, already at the early stages of the system development. In this paper, we present a rigorous engineering process for distributed systems, based on the Abstract State Machines (ASM) formal method. We rely on the foundational notions of ASM ground model and model refinement to obtain a precise model for a client-server application for Cloud systems. This application has been proposed to tackle the problem of making Cloud services usable to different end-devices by adapting on-the-fly the content coming from the Cloud to the different devices contexts. The ASM-based modeling process is supported by a number of validation and verification activities that have been exploited on the component under development to guarantee consistency, correctness, and reliability properties.     

Modeling and simulation-driven development of embedded real-time systems

The design and development of embedded hard real-time (RT) systems is one of the complex development practices, because of the requirements of criticality and timeliness of these systems. One critical aspect of RT systems is the production of output before specified deadline. Formal methods are promising in dealing with the design issues of these applications, although they do not scale well for complex systems. Instead, Modeling and Simulation (M&S) provides a cost-effective approach to verify the design and implementation details of very Complex RT applications. M&S methods provide dynamic and risk-free testing environments to verify different scenarios, and they are used for feasibility analysis and verification of such systems. Nevertheless, the simulation models are usually discarded in the later phases of the development.We present the application of an M&S-based method referred to as DEVSRT (Discrete EVent System Specifications in Real-Time) to solve the discontinuity between the simulation models and the final embedded application, in this paper. DEVSRT defines explicit deadline notation for DEVS transitions, draws a clear mapping between DEVS transitions and real-time tasks and provides a formal method and tool for integration of simulation models with the associated hardware components.     

基于通信的列车控制系统可信构造：形式化方法综述

基于通信的列车控制系统（communication based train control system,简称CBTC）已经成为世界范围内建造轨道交通信号系统的标准制式.CBTC采用更加灵活和精确的列车控制,并提供连续的安全列车间隔保证和超速防护,在很大程度上提高了轨道交通运输的效率和安全性.尽管CBTC能够精确地实施实时控制,但由于CBTC涉及计算、通信与控制这3个方面的实时协同,系统设计与实现异常复杂.由设计缺陷而导致严重的灾难、事故和损失屡见不鲜.作为一个典型的安全攸关系统,如何保证CBTC的可信构造已成为领域研发人员关注的焦点与面临的最大挑战.鉴于在软硬件领域的成功经验,形式化方法目前已被公认为是保障CBTC可信性的一种有效方案.围绕CBTC的可信构造,从其生命周期的3个重要阶段,即系统需求分析、设计建模与底层实现入手,针对CBTC在可信方面的典型特征,梳理分析了CBTC系统在可信构造方面面临的挑战、国内外研究现状和发展趋势,全面介绍了形式化方法在CBTC可信构造中扮演的角色.     

A Formal Verification Environment for Railway Signaling System Design

A fundamental problem in the design and development of embedded control systems is the verification of safety requirements. Formal methods, offering a mathematical way to specify and analyze the behavior of a system, together with the related support tools can successfully be applied in the formal proof that a system is safe. However, the complexity of real systems is such that automated tools often fail to formally validate such systems.This paper outlines an experience on formal specification and verification carried out in a pilot project aiming at the validation of a railway computer based interlocking system. Both the specification and the verification phases were carried out in the JACK (Just Another Concurrency Kit) integrated environment. The formal specification of the system was done by means of process algebra terms. The formal verification of the safety requirements was done first by giving a logical specification of such safety requirements, and then by means of model checking algorithms. Abstraction techniques were defined to make the problem of safety requirements validation tractable by the JACK environment.     

航空装备测试仪器应用验证方法研究

针对航空装备用测试仪器应用验证需求,基于系统工程方法,提出了夯实基础、统筹推进、分类分阶段验证的验证工作思路.研究确定了调研应用验证需求、构建验证指标体系、明确验证要素、建立验证程序、实施验证试验、给出综合评价结论的应用验证流程.遵循满足航空装备要求、结合使用场景、聚焦关键指标等原则,提出了仪器功能性能、质量与可靠性、环境适应性等基础级和适装性、软硬件兼容性等系统级验证内容,以及相应的验证方法,可为国产测试仪器应用验证工作提供技术支持.     

Ready for testing: ensuring conformance to industrial standards through formal verification

The design of distributed, safety-critical real-time systems is challenging due to their high complexity, the potentially large number of components, and complicated requirements and environment assumptions that stem from international standards. We present a case study that shows that despite those challenges, the automated formal verification of such systems is not only possible, but practicable even in the context of small to medium-sized enterprises. We considered a wireless fire alarm system, regulated by the EN 54 standard. We performed formal requirements engineering, modeling and verification and uncovered severe design flaws that would have prevented its certification. For an improved design, we provided dependable verification results which in particular ensure that certification tests for a relevant regulation standard will be passed. In general we observe that if system tests are specified by generalized test procedures, then verifying that a system will pass any test following those test procedures is a cost-efficient approach to improve the product quality based on formal methods. Based on our experience, we propose an approach useful to integrate the application of formal methods to product development in SME.     

A service creation environment based on scenarios

Scenarios are often constructed for illustrating example runs through reactive system. Scenarios that describe possible interactions between a system and its environment are widely used in requirement engineering, as a means for users to communicate their functional requirements. Various software development methods use scenarios to define user requirements, but often lack tool support. Existing tools are graphical editors rather than tool support for design. This paper presents a service creation environment for elicitation, integration, verification and validation of scenarios. A semi-formal language is defined for user oriented scenario representation, and a prototype tool implementing an algorithm that integrates them for formal specification generation. This specification is then used to automatically find and report inconsistencies in the scenarios.     

The specification and verified decomposition of system requirementsusing CSP

A formal method for decomposing the critical requirements of a system into requirements of its component processes and a minimal, possibly empty, set of synchronization requirements is described. The trace model of Hoare's communicating sequential processes (CSP) is the basis for the formal method. The method is applied to an abstract voice transmitter and describes the role that the EHDM verification system plays in the transmitter's decomposition is described. In combination with other verification techniques, it is expected that this method will promote the development of more trustworthy systems     

Formal Techniques for Analysing Scenarios using Message Sequence Charts

This paper describes light-weight formal techniques based on Message Sequence Charts (MSCs) for capturing and validating early requirements and design. Our focus is on ease of use in specifying, simulating and validating scenarios, and checking their desired properties efficiently. We discuss how the formalism of High Level Message Sequence Charts (HMSCs or MSC'96), can be used to capture scenarios in use cases, thus enabling the use of tools for analysing them. We then present two formal semantics for HMSCs – an intuitive linear time semantics based on runs, and an operational semantics in terms of a labelled transition system. Next we present a way of describing desired properties of use case scenarios using templates, for validating scenarios with respect to informal requirements. The correctness properties of a collection of MSCs can then be established by efficient algorithms for finding paths in a directed graph representing the precedence relation on the events of the MSCs. We have implemented the operational semantics and the verification algorithms in the form of a simulation and verification tool for analysing scenarios.