关键词:
形式化方法
程序统一理论
形式语义
形式验证
信息物理系统
摘要:
伴随计算机系统和物理世界交互的不断深入,信息物理系统(Cyber-Physical Systems,CPS)的概念应运而生,它是一种融合离散的计算机行为与连续的物理行为的复杂系统。自信息物理系统问世以来,相关研究及应用蓬勃发展,目前已在工业控制、能源管理、智能交通、智慧医疗等领域发挥重要作用。然而,信息物理系统的广泛应用也预示着其安全性、可靠性亟需保障。作为一种基于数学的技术,形式化方法支持软硬件系统的描述与分析、建模与验证,对于安全攸关领域的质量保障行之有效。因此,本文采用形式化方法对信息物理系统展开理论与应用两方面的研究。具体来说,信息物理系统中计算进程和物理进程深度融合,为系统的描述与建模带来复杂性。因此,从理论层面而言,为其设计规范的建模语言并提供明确、无歧义的形式语义具有重要意义。本文聚焦于一种基于共享变量的信息物理系统建模语言CPSLsc(Cyber-Physical Systems Modeling Language with Shared-Variable Concurrency),基于程序统一理论研究其形式语义,包括操作语义、代数语义、指称语义和证明系统,通过轨迹模型刻画程序间的消息交换。另一方面,从应用的角度出发,为了保证信息物理系统的安全可靠性,本文以所提出的形式语义为理论基础,在相关模型检验工具中开展了信息物理系统的程序转换、程序模拟与形式验证工作。本文的形式语义研究为形式验证提供理论基础,反之,所开展的形式验证研究亦是形式语义的应用体现。综上,本文的主要研究内容及贡献概括如下:·理论研究:基于程序统一理论的CPS形式语义研究(1)提出了基于共享变量的信息物理系统建模语言CPSLsc的操作语义、代数语义和指称语义。本文首先基于经典的结构化操作语义,定义了CPSLsc的变迁规则以刻画程序的执行步骤。再者,通过引入卫兵选择的概念,本文给出了CPSLsc的代数语义,所定义的代数语义可以将程序转换为卫兵选择的统一形式,进而实现含有连续行为的并发组合程序线性化。此外,本文还基于轨迹模型和健康条件给出了CPSLsc的指称语义。(2)提出了基于共享变量的信息物理系统建模语言CPSLsc的证明系统。为了规避并发组合程序间共享变量互相干扰的问题,本文扩展了霍尔三元组的形式并将轨迹模型引入证明系统。本文给出了程序语句的证明规则,并以电池管理系统为例说明了该证明系统的可应用性。·应用研究:基于模型检验的CPS形式验证研究(1)基于操作语义,实现了CPSLsc程序转换及形式验证。鉴于操作语义是以状态机为数学基础,本文在以自动机为理论基础的模型检验工具Space Ex中,实现了从CPSLsc程序到自动机模型的转换,并围绕自动刹车系统开展了形式验证的案例研究。(2)基于代数语义,实现了CPSLsc程序模拟及形式验证。由于代数语义中的代数定律可视作从左至右的重写规则,本文在基于重写理论的重写引擎实时Maude中机械化实现了所定义的代数语义。此外,借助机械化实现的代数语义,本文进一步在实时Maude中实现了CPSLsc程序模拟及形式验证,并选用电池管理系统开展了相应的案例研究。