从UML状态图到PVS规范的自动转换、验证

将UML(统一建模语言)图形转换成形式化规范是一种精确化UML语义、扩大形式化软件方法适用范围的有效途径.PVS是一种通用高阶逻辑形式化规范语言,具有很强的描述能力以及丰富的定理证明、模型验证工具支持.本文论证了使用.PVS来对UML进行形式化的优势,并且给出了UML的状态图到PVS规范的转换模型与规则.     

一种UML2．0模型动态特性的一致性验证方法

近年来，UML已经被广泛应用于软件的分析和设计，然而，由于软件系统的复杂性，在UML模型中，难免会引入不同图表间特别是动态视图之间的不一致性。提出了一种用于验证UML2．0模型状态图和顺序图一致性的方法。首先，用XYZ／E来形式化描述状态图并将其转化为Promela输入语言；然后，用LTL来表示顺序图间的相互作用；最后利用模型检测工具Spin通过检查Promela描述的状态图是否满足LTL公式来达到检测模型一致性的目的。     

UML活动图到时间Petri网的映射方法

UML被广泛应用于嵌入式实时系统等领域的建模,而嵌入式实时系统对时间响应的要求非常严格,UML缺乏对系统时间约束的描述和形式化语义。因此,提出了一种结合MARTE与UML带有时间约束的UML活动图模型,并定义相应的映射规则,将该活动图模型映射到时间Petri 网模型,最后通过实例验证了该映射方法的正确性和实用性。     

一种复杂系统定性模型描述方法

复杂系统日益呈现出不确定性、非线性等定性特征,已有的建模方法不足以构建具有定性特征的复杂系统。基于此,提出一种复杂系统定性模型描述方法(QMDM)。QMDM结合定性仿真理论,在UML基础上对其组件图、时序图以及状态图进行扩展,可视化地表达出定性模型的建模过程。组件图用于静态的表达出定性模型包含的定性约束关系。时序图和状态图用于动态的表达出定性模型的时序性,以及状态迁移。此外,给出QMDM的形式化定义,便于以后模型验证,并将研究成果在空调制冷系统中进行了初步应用。     

基于模型检测的UML状态图和顺序图一致性检测

用户可使用UML从不同角度对系统进行建模,但不同视图间存在信息冗余,会导致视图不一致的问题。文中提出形式化与可视化UML互补建模的方法,探讨用模型检测验证UML模型中的状态图和顺序图的一致性问题。针对具有复合片段的顺序图提出分析方法,将复杂层次结构的状态图转换为有限状态机,再用模型检测工具NuSMV对建立的模型进行验证。最后通过实例对此转换方法进行验证,实验结果表明了此方法的有效性。     

一种代币智能合约的两段式模型检测方法

针对代币智能合约的形式化验证方法中模型检测存在的状态空间爆炸问题,提出了一种两段式模型检测方法.使用图转换规则对智能合约建模,利用工具生成模型状态空间.第一阶段对部分状态空间进行分支时序逻辑验证后,第二阶段先使用前一阶段的状态验证信息构造马尔可夫链,使用集束搜索结合马尔可夫链对余下状态进一步筛选,再进行验证.实验结果表明,该方法能够有效减少需验证状态数量,解决状态空间问题,完成合约验证.     

可信密码模块的模型检测分析

根据可信密码模块规范的非形式化描述,利用模型检测工具SPIN对可信密码模块安全性进行形式化分析,给出了可信密码模块形式化分析的基本框架,重点分析了AP授权协议和可信密码模块初始化子系统.指出了AP授权协议存在的缺陷,并给出了具体的改进措施;同时验证可信密码模块初始化子系统状态的一致性.     

面向模型检验的UML状态机语义

UML状态机(SM)是UML中用来对系统各种元素的离散行为建模的图.它丰富的表示符号提供了强大的描述机制,但也降低了其结构的模块性,提高了对其分析验证的难度.模型检验是自动检验有限状态并发系统的技术.通过模型检验SM描述的不同系统元素的行为是否满足某些性质,能尽早发现设计中的错误.为了将模型检验技术应用于SM的验证,本文用kripke结构定义SM的操作语义.与已有的SM语义定义不同,本文考虑到了SM中包含的不确定因素,用kripke结构描述系统所有可能的演化轨迹.通过检验从SM翻译得到的kripke结构达到模型检验SM的目的.     

数据库形式化安全策略模型建模及分析方法

目前数据库形式化安全策略模型存在抽象层次较高、缺乏对数据库状态与约束的充分描述等问题,难以辅助用户发现商用数据库设计中的微小缺陷。提出了一种基于PVS语言的数据库形式化安全策略模型建模和分析方法,该方法较以往模型能够更加贴近实际数据库,应用范围更广,安全属性描述更加完整,描述的模型具有灵活的可扩展性,并且保证了建模与验证的效率。最后,将该方法应用于数据库管理系统BeyonDB的安全策略建模分析中,帮助发现了系统若干设计缺陷,证明了方法的有效性。     

面向模型检验的UML状态机语义

UML状态机(SM)是UML中用来对系统各种元素的离散行为建模的图．它丰富的表示符号提供了强大的描述机制，但也降低了其结构的模块性，提高了对其分析验证的难度．模型检验是自动检验有限状态并发系统的技术．通过模型检验SM描述的不同系统元素的行为是否满足某些性质，能尽早发现设计中的错误．为了将模型检验技术应用于SM的验证，本文用kripke结构定义SM的操作语义．与已有的SM语义定义不同，本文考虑到了SM中包含的不确定因素，用kripke结构描述系统所有可能的演化轨迹、通过检验从SM翻译得到的kripke结构达到模型检验SM的目的．     

基于XYZ/ADL的Web服务组合描述与验证

Web服务组合是当前Web服务领域的一个研究热点,目前已有一些相关的描述与验证方法,本文从软件体系结构角度研究Web服务组合描述与验证方法.基于软件体系结构描述语言XYZ/ADL和精化检验/模型检测方法,提出了一种Web服务组合的描述与验证方法.XYZ/ADL是时序逻辑语言XYZ/E的扩展,考虑到多数Web服务具有实时特征,采用XYZ/E的实时扩展语言XYZ/RE表示系统应满足的时间约束.针对Web服务组合系统,根据XYZ/RE到时间自动机的映射规则将系统描述转换为对应的时间自动机,分别采用精化检验和模型检测两种技术验证Web服务组合的正确性;最后通过两个实例分析分别阐述了上述方法的可行性和有效性.     

Applying infinite state model checking and other analysis techniques to tabular requirements specifications of safety-critical systems

Although it is most often applied to finite state models, in recent years, symbolic model checking has been extended to infinite state models using symbolic representations that encode infinite sets. This paper investigates the application of an infinite state symbolic model checker called Action Language Verifier (ALV) to formal requirements specifications of safety-critical systems represented in the SCR (Software Cost Reduction) tabular notation. After reviewing the SCR method and tools, the Action Language for representing state machine models, and the ALV infinite state model checker, the paper presents experimental results of formally analyzing two SCR specifications using ALV. The application of ALV to verify or falsify (by generating counterexample behaviors) the state and transition invariants of SCR specifications and to check Disjointness and Coverage properties is described. The results of formal analysis with ALV are then compared with the results of formal analysis using techniques that have been integrated into the SCR toolset. Based on the experimental results, strengths and weaknesses of infinite state model checking with respect to other formal analysis approaches such as explicit and finite state model checking and theorem proving are discussed.     

数字电路设计中的符号模型检验技术

符号模型检验把有序二叉判定图OBDD技术引入到模型检验中，有效地缓解了状态组合爆炸问题。文章主要介绍了CTL模型检验基本概念和原理，给出了符号模型检验算法，验证了模4计数器的某些特性。     

Cohesive Coverage Management: Simulation Meets Formal Methods

It has been advocated by many experts in design verification that the key to successful verification convergence lies in developing the verification plan with adequate formal rigor. Traditionally, the verification plans for simulation and formal property verification (FPV) are developed in different ways, using different formalisms, and with different coverage goals. In this paper, we propose a framework where the difference between formal properties and simulation test points is diluted by using methods for translating one form of the specification to the other. This allows us to reuse simulation coverage to facilitate formal verification and to reuse proven formal properties to cover simulation test points. We also propose the use of inline assertions in procedural (possibly randomized) test benches, and show that it facilitates the use of hybrid verification techniques between simulation and bounded model checking. We propose the use of promising combinations of formal methods presented in our earlier papers to shape a hierarchical verification flow where simulation and formal methods aim to cover a common design intent specification. The proposed flow is demonstrated using a detailed case study of the ARM AMBA verification benchmark. We believe that the methods presented in this work will stimulate new thought processes and ultimately lead to wider adoption of cohesive coverage management techniques in the design intent validation flow.     

Formal Methods in Communication Protocol Design

While early protocol design efforts had to rely largely on seat-of-the-pants methods, a variety of more rigorous techniques have been developed recently. This paper surveys the formal methods being applied to the problems of protocol specification, verification, and implementation. In the specification area, both the service that a protocol layer provides to its users and the internal operations of the entities that compose the layer must be defined. Verification then consists of a demonstration that the layer will meet its service specification and that each of the components is correctly implemented. Formal methods for accomplishing these tasks are discussed, including state transition models, program verification, symbolic execution, and design rules.     

Analyzing encryption protocols using formal verification techniques

An approach to analyzing encryption protocols using machine-aided formal verification techniques is presented. The properties that the protocol should preserve are expressed as state invariants, and the theorems that must be proved to guarantee that the cryptographic facility satisfies the invariants are automatically generated by the verification system. A formal specification of an example system is presented, and several weaknesses that were revealed by attempting to verify and test the specification formally are discussed.<>     

一种基于学分制排课系统的Z规格说明

运用形式化方法建模在软件开发过程中可提高目标系统的正确性和可靠性,在此提出了一种利用Z语言进行语义分析的方法。该方法在序列图Z规范的基础上,用属性集表示对象状态,并将序列图的上下文表示为Z形式约束,通过检查上下文约束与对象状态间的一致性对序列图进行语义分析。在此以一个基于学分制的排课系统为例,使用面向对象的形式规格说明语言Z,描述了一个精确、完整的高校排课系统的形式化数学模型。过程显示,该方法具有精确的描述性和很强的抽象性,能为软件系统的开发和验证提供科学的框架。     

Learning from Constraints for Formal Property Checking

Constraints are commonly used in both simulation and formal verification in order to specify expected input conditions and state transitions. Constraint solving is a process to determine input vectors which satisfy the set of constraints during constrained random simulation. Even though constraints are used in formal property checking to restrict the search space, constraint solving has never had direct application to formal property checking. There are often many simple, yet powerful, invariants that can be learned from constraint solving during constrained random simulation. These invariants are shown in this paper to significantly simplify the formal verification problem. We use approximate constraint solving to compute an approximate set of valid input vectors. The approximate set of valid input vectors are a strict superset of the set of all legal input vectors. We use BDD techniques to compute these input vectors during constrained random simulation, then process the resulting BDDs for learning invariants which can be used during formal property checking. This paper presents efficient BDD algorithms to learn invariants from the BDDs generated from approximate constraint solving. We also present how these learned invariants can be applied to the formal property checking. Experimental results show that invariants learned during constraint solving can significantly improve the performance of formal property checking with many industrial designs.