基于扩展Petri网的系统建模及形式化验证方法*

嵌入式实时系统对时间约束性、安全性和可靠性具有非常高的要求,但是传统的建模和形式化验证方法难以满足对系统的实时性和安全性的模拟和验证需求。通过对有色Petri网的时间属性进行扩展,提出了实时有色Petri网模型,能够对系统的时间属性进行模拟和评估;参考实时有色Petri网模型到时间自动机的语义转换规则对模型进行转换,可以利用时间计算树逻辑对系统的实时性、安全性和可靠性进行形式化验证。以列车通信网络控制器的双线冗余控制模块的建模和形式化验证为例,证明了该方法的有效性。     

基于扩展SysML活动图的嵌入式系统设计安全性验证方法研究

能源、交通等领域中复杂嵌入式系统设计的安全性分析与验证工作已经成为当前的重要研究热点之一;本文提出一种结合MARTE语义信息的扩展Sys ML活动图模型,用于描述安全关键应用中的嵌入式系统动态行为的设计,并对此扩展模型展开基于模型转换的系统设计安全性特征的形式化分析与验证方法的研究;包括:构建了Sys ML活动图与MARTE中非功能性质建模语义相结合的元模型,以及验证工具UPPAAL的时间自动机元模型,并且给出了二者之间的语义映射规则;建立了从时间自动机模型描述到UPPAAL工具输入格式之间的语法转换方法;设计了一个基于AMMA平台的面向扩展Sys ML活动图的模型转换与验证框架;最后,给出了一个高铁控制系统设计模型的安全性验证的实例分析.     

时变网络中国邮路问题的时间自动机模型

基于时间自动机理论,提出了时间窗、时间依赖服务代价以及时间依赖旅行时间这3类时变网络中国邮路问题的统一建模的语义模型和求解方法.首先,将中国邮路问题可行解条件和时变参数与时间自动机联系起来,建立了3类问题的统一时间自动机系统(timed automata system,简称TAS)模型;然后,将时变网络中国邮路问题归结为TAS模型上的一系列可达性判定问题,并利用形式化验证算法给出了有效的求解方法.由于TAS模型中存在O(|A|+|AR|+1)个时间自动机,限制了问题求解规模.为此,通过扩展时间自动机语义,提出了TAS模型中的时间自动机合并策略,进而将TAS模型转换为一个广义时间自动机(GTA)模型.基于GTA模型,利用UPPAAL工具对9组、共54个随机算例进行实验.实验结果表明,该方法在求解精度上明显优于运筹学领域的方法.     

AADL分级调度模型的分析与验证

针对嵌入式系统体系结构分析设计语言(architecture analysis and design language,AADL)分级调度模型的分析问题,提出了基于模型检验的可调度性分析和验证方法.基于时间自动机理论,将AADL分级调度模型转换为时间自动机网络,将待验证性质描述为时序逻辑公式,通过模型检验工具对可调度性进行分析和验证.研究结果表明,使用模型检验方法来分析AADL分级调度模型的可调度性是可行的.相对其他方法而言,该方法利用了形式化方法的穷举性来分析系统的性质,分析结果更加精确.     

模型驱动的嵌入式系统设计安全性验证方法研究

基于模型的嵌入式系统安全性分析与验证方法是近年来在安全攸关系统工程领域中出现的一个重要研究热点。提出一种基于模型驱动架构的面向SysML/MARTE状态机的系统安全性验证方法,具体包括:构建了具备SysML/MARTE扩展语义的状态机元模型,以及安全性建模与分析语言AltaRica的语义模型GTS的元模型;然后建立了从SysML/MARTE状态机模型分别到时间自动机模型以及AltaRica模型的语义映射模型转换规则,并基于AMMA平台和时间自动机验证工具UPPAAL设计实现了对SysML/MARTE状态机的模型转换与系统安全性形式化验证的框架。最后给出了一个飞机着陆控制系统设计模型的安全性验证实例分析。     

面向服务的信息物理融合系统建模与验证

针对信息物理融合系统(CPS)中建模与验证面临的问题与挑战,基于服务组合的思想,提出一种CPS建模与验证方法。首先,综合分析已有研究成果,提出一种CPS的组成结构,包含物理世界、感知系统、信息处理系统、控制系统及时间约束。基于该结构提出CPS资源的服务分类及组成框架,并利用时间自动机理论,提出CPS物理环境建模方法、CPS原子服务建模方法及服务组合方法。最后,通过案例设计和模型检测工具Uppaal,分别对系统安全性、可达性、活性及时间约束四种类型的性质进行了相关验证。结果表明,系统通过了这些性质的验证,这也证明了面向服务的CPS建模方法的正确性。     

基于时间Petri网的嵌入式系统中断建模与验证

嵌入式系统为中断驱动系统,但中断触发的随机性和不确定性导致中断缺陷很难被追踪发现,并且一旦发生中断故障,往往会使整个嵌入式系统陷入崩溃。因此必须保证中断系统软件的可信性,但是目前缺乏有效的中断系统资源冲突检测方法。针对上述问题,文中首先提出了一种基于时间Petri网的中断系统建模方法,其能够对中断的并发性和时间序列进行有效建模。然后,为方便后续形式化验证,将时间Petri网模型转化为与之等价的时间自动机模型,并提出一种符号编码方法对时间自动机进行形式化编码,将系统模型与所需验证性质编码为一阶谓词逻辑公式,从而能够通过SMT对时间自动机的不变属性进行BMC验证。最后,通过SMT求解器Z3进行实验,实验结果证明了所提方法的有效性。     

基于自动机的构件实时交互行为的形式化模型

采用形式化方法对复杂实时构件系统交互行为进行描述和验证,对于提高系统的正确性、可靠性等可信性质具有重要意义.分析了基于进程代数和自动机的构件交互行为形式化建模方法各自的优缺点,在此基础上提出了基于时间构件交互自动机的建模方法,给出了时间构件交互自动机的相关定义、组合和验证算法.时间构件交互自动机引入了时间限制、时间代价、时间代价计算半环、构件组合层次等概念,既能够描述构件交互情况,又能够清楚地表示出构件系统的体系结构信息和实时信息,便于对系统进行描述和验证.最后,结合具体应用给出了应用示例.     

使用事件自动机规约的C语言有界模型检测

提出使用事件自动机对 C 程序的安全属性进行规约,并给出了基于有界模型检测的形式化验证方法。事件自动机可以规约程序中基于事件的安全属性,且可以描述无限状态的安全属性。事件自动机将属性规约与C程序本身隔离,不会改变程序的结构。在事件自动机的基础上,提出了自动机可达树的概念。结合自动机可达树和有界模型检测技术,给出将事件自动机和C程序转化为可满足性模理论SMT(satisfiability modulo theory)模型的算法。最后,使用SMT求解器对生成的SMT模型求解,并根据求解结果给出反例路径分析算法。实例分析和实验结果表明,该方法可以有效验证软件系统中针对事件的属性规约。     

基于混合自动机的PSL模型研究

基于SPICE的计算机仿真方法在混合信号电路验证应用中具有较大的计算开销,讨论基于属性描述的建模方法减小计算开销的问题。通过分析PSL(property specification language)对系统属性的形式化描述方法,并分析混合自动机理论对混合信号系统抽象能力,提出了适合于混合信号电路系统快速验证的PSL模型。结合混合自动机对PSL进行了基于混合自动机语义特点的扩展,使用巴克斯—诺尔范式对其拓展后语法进行规范,提出具有描述混合信号电路行为特性的HAPSL(hybrid automata-base     

信息物理融合系统控制软件的统计模型检验

信息物理融合系统常采用嵌入式实时多任务系统作为其控制软件,这类软件的并发和非确定性给验证带来了困难.提出了一种利用统计模型检验技术分析多任务系统的功能正确性的方法.该方法构造的时间自动机模型以模块化的方式描述了实时多任务系统中的主要成分,包括实时操作系统、周期性任务、偶发任务、共享资源以及物理环境,能够展现多任务系统的细粒度的运行过程及其对物理环境的实时响应.应用该方法分析了玉兔号月球车控制软件的一个早期版本,发现了系统运行中出现的一个特殊错误,识别了实际系统出现错误的条件,再现了出现错误的场景.     

嵌入式协调设计中的系统级验证方法及应用

协同验证是在嵌入式系统协调设计过程中用以检验系统功能是否正确的有效手段。由于精确指令集模拟器模拟的细节多、速度慢，通常成为复杂嵌入式系统协同验证的瓶颈，因此提出使用RTOS软件模拟器和指令集模拟器相结合的多层次验证方法，提高了复杂嵌入式系统的验证速度，并通过某图像压缩系统的验证实例，说明该验证方法的有效性。     

嵌入式系统软硬件协同验证中软件验证方法

随着集成电路及计算机技术的发展,嵌入式系统设计变得越来越复杂．复杂的嵌入式系统设计,通常采用验证的手段检验系统设计的正确性,硬件验证通常是在硬件设计描述的基础上建立用于模拟硬件功能的硬件模拟器;软件验证常用的方法是建立处理器功能模型(指令集模拟器ISS),逐条解释嵌入式软件在目标机器上的执行过程,产生模拟输出,驱动外围电路(即硬件设计)．指令集模拟器从底层时序关系模拟嵌入式软件在目标CPU上运行过程．对于复杂嵌入式系统设计,ISS模拟速度通常成为协同模拟瓶颈．基于RTOS的嵌入式软件快速验证方法可以有效地提高软件模拟速度,扩展RTOS功能,适应协同模拟需要,建立硬件模拟驱动,实现软件和硬件模拟器通信连接和协同模拟同步控制．基于RTOS的嵌入式软件验证方法以编译代码模型为基础,从系统行为级验证嵌入式软件功能,验证速度快．在实际应用中,该方法和ISS验证相结合,能够实现更有效、更快速的嵌入式系统协同验证．最后以几个典型硬件设计为基础,编写相应的控制软件,进行软硬件协同验证实验,实验结果数据说明该验证方法实用、有效、快速．     

基于虚拟微处理器的嵌入式软件开发与系统验证环境

嵌入式系统设计过程中软件与硬件集成验证的滞后，已成为制约整个系统开发进程的重要因素．虚拟微处理器是指在嵌入式系统硬件原型形成之前构造的可仿真原型，通过对微处理器的仿真支持软件嵌入式软件开发．介绍了基于虚拟微处理器技术的嵌入式软件开发环境的设计和实现，利用该环境，设计者可在设计早期进行系统集成验证，减少设计错误并缩短设计周期．该环境已经在嵌入式系统开发过程中得到成功应用．     

Certifying software for high-assurance environments

It does not make sense to grant carte blanche high-assurance certificates to product that may be used across multiple platforms and in multiple environments. We should bind software certification to a product's known environment and operational profile. The author proposes three techniques for verifying high assurance: desirable-behavior testing, abnormal testing, and fault injection. Each uses the product's operational profile to detect software-related anomalies that might allow a catastrophic event     

嵌入式系统软硬件协同模拟验证环境设计与实现

介绍了一个嵌入式系统软硬件协同模拟验证环境，该环境以指令集模拟器和事件驱动硬件模拟器为基本框架，并由总线调度模型和总线界面模型提供软硬件模拟交互界面。重点讨论该环境中软硬件模拟器之间的接口设计与实现方法，最后给出一个嵌入式系统协同验证的应用实例。     

Formal verification and simulation for platform screen doors and collision avoidance in subway control systems

For hybrid systems, hybrid automata-based tools are capable of verification, while Matlab Simulink/Stateflow is proficient in simulation. We propose a co-verification procedure, in which the verification tool SpaceEx/PHAVer and simulation tool Matlab are integrated to analyze and verify hybrid systems. For the application of this procedure, a platform screen door system (PSDS, a subsystem of the subway control system), is modeled with hybrid automata and Simulink/Stateflow charts, respectively. The models of PSDS are simulated by Matlab and verified by SpaceEx/PHAVer. The simulation and verification results indicate that the sandwiched situation can be avoided under time interval conditions. We improve the model with four trains and four stations on a subway line and analyze the urgent control scenario for the safety distance requirement. In this paper, the Simulink/Stateflow model is a refinement of the SpaceEx/PHAVer model, which is closer to a final implementation. Moreover, the two models are complementary for some features (e.g.,visualization of simulation, correctness proving by verification), stressing different aspects of the overall system and permitting complementary analysis techniques, i.e., verification versus simulation. We conclude that this integration procedure is competent in verifying subway control systems.     

一种融合FPGA和ISS技术的软硬件协同验证方法

建立了一种基于硬件加速器FPGA 和指令集模拟器ISS对嵌入式系统功能进行软硬件协同验证的方法。针对此方法的实现,分析了协同验证过程中软硬件交互技术,并给出总线功能模型BFM结构及其实现方法。经实例验证分析表明,基于FPGA和ISS的协同验证方法,在对嵌入式应用系统验证中与其他几种常用方法比较具有较明显的优势。     

嵌入式系统虚拟原型平台的SystemC实现

提出一个基于SystemC的可配置嵌入式系统快速虚拟原型平台，它具有典型的片上系统结构，支持多层总线架构．作为SystemC事务处理级模型，该平台支持快速仿真和通信细化．将此平台应用于IEEE 802．11媒体访问控制器的设计，目前该系统正处于板级调试过程中．     

C语言系统描述的HCDFG-Ⅱ实现

C语言是系统设计中一种主要的系统描述语言，在系统级软硬件协同验证及随后的软硬件划分、接口综合和行为综合等中都需要把C语言的系统描述转化为控制数据流图。本文介绍了一种层次化控制数据流图HCDFG-Ⅱ模型，以及从C语言生成该模型的方法。HCDFG-Ⅱ的层次化模型分为函数／进程级、语句级和操作级，根据需要可以生成不同级别的模型。本文讨论了C语言中各种控制结构及数组、指针、联合和结构等复杂数据类型生成HCDFG-Ⅱ的方法。