反应式嵌入式系统形式化性能模型的研究

基于进程代数EACSR-VP和形式化描述语言CPSL，介绍了如何建立和描述反应式嵌入式系统的形式化性能评价模型．该模型通过抽象去掉了实现了细节，是可执行的，利用其可以对不同的设计方案进行定量的性能验证，得到不同系统的性能指标并进行分析和比较，从而使最终的系统实现满足特定性能指标要求．     

一种基于进程代数的路由器性能评价算法

性能评价是路由器设计中的一个重要环节，目前有多种方法，提出了一种基于进程代数的形式化方法，它能在系统进行正确性验证的同时得到系统的性能参数．首先定义了描述路由器模型的进程代数方法，然后介绍了建立路由器模型的方法，并给出了一个简单的例子，最后给出了计算路由器两个性能指标吞吐率和延时的算法．     

LOTOS事件结构语义模型的实现

本文以LOTOS为基础,简介了LOTOS进程代数的概念和算子。同时,以事件结构作为进程代数的语义模型,充分展示了形式化方法是如何对一个复杂系统进行静态或动态刻画。本文最后以上述理论为基础,开发出一款辅助软件工具。该软件具有两方面的用途:一是能对给定的一个LOTOS语言层次上的系统刻画,自动生成结构层次上的系统模型;二是进行等价性模型检测。此工具将形式化方法的推理过程可视化、实用化。     

基于安全进程代数的非演绎安全模型的分析与验证

就刻画安全的性质而言,基于非演绎信息流的安全模型较基于访问控制的安全模型更为确切和本质。在基于迹语义对非演绎信息流安全模型进行分析的基础上,基于安全进程代数给出非演绎模型的形式化描述,然后基于系统的安全进程代数表达式给出非演绎模型的验证算法且开发了相应的验证工具,最后通过实例说明该算法的正确性和验证工具的方便适用性。     

基于UML的计算机联锁软件的分析与建模

有效地测试、分析和验证计算机联锁软件是保证列车运行安全和旅客生命财产安全的重要手段,而形式化模型是系统测试、分析和验证的基础。以联锁软件的UML非形式化模型为基础,以有限状态机模型为系统形式化模型描述的数学工具,研究UML顺序图(场景)自动转化为有限状态机模型的方法。首先将场景的UML顺序图转化为FSP进程代数模型,然后通过合并不同对象的进程代数模型,得到系统的有限状态机模型。最后以接车进路用例为例生成系统的有限状态机模型,以验证该方法的可行性和有效性。     

SPI演算规范的建模、实现验证研究

针对安全协议安全属性是否满足,缺乏有效性能评价方法的现状,大都使用SPI演算或相近的进程代数方法进行建模。利用这种方法不仅能够有效地形式化描述安全协议,并且能够对安全协议进行多方面的系统评价,但基本上没有说明怎么样寻找设计合适的验证工具,验证其安全属性实现的正确性。本文引入基于SPI演算的验证工具SPRITE来保证建模过程正确性,并设计给出实现映射的具体方法。本方法通过对典型的WOO-LAM单向认证协议予以说明,最后SPRITE产生的具体JAVA代码,给出了安全协议的安全属性,使形式化描述的协议的安全属性是否满足更接近于人的理解而不仅只是机器的解释。     

几何代数的高阶逻辑形式化

几何代数是一种用于描述和计算几何问题的代数语言.由于它统一的表达分析和不依赖于坐标的几何计算等优点现已成为数学分析、理论物理、几何学、工程应用等领域重要的理论基础和计算工具, 然而利用几何代数进行计算和建模分析的传统方法,如数值计算方法和符号方法等都存在计算不精确或者不完备等问题.高阶逻辑定理证明是验证系统正确的一种严密的形式化方法.本文在高阶逻辑证明工具HOL-Light中建立了几何代数系统的形式化模型,主要包括片积、多重矢量、外积、内积、几何积、几何逆、对偶、基矢量运算和变换算子等的形式化定义和相关性质定理的证明.最后为了说明几何代数形式化的有效性和实用性,本文在共形几何代数空间中对刚体运动问题提供了一种新的简单有效的形式化建模与验证方法.     

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

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

工作流模式的π演算建模研究

π演算是一种移动进程代数,可用于对并发和动态变化的系统进行建模。根据π演算的语法,提出了一种新的用于工作流模式的形式化建模方法,以π演算作为工作流形式化的基础,并利用π演算对工作流模式进行了建模。     

基于Pi-演算的工作流模式描述

工作流模式包含了业务流程的基本特征和共性,其实现依赖于具体的流程建模语言或方法.Pi-演算是一种进程代数,可以应用于业务流程的形式化建模.本文使用Pi-演算作为业务流程形式化的工具,对存在多种BPMN表示的工作流模式进行形式化建模,以探究工作流模式Pi-演算的描述,检验Pi-演算对业务流程行为特征的表现能力.     

一种基于进程代数的软件体系结构描述语言PEADL

对性能评价进程代数(PEPA)扩展,提出具有时序特征的随机进程代数(ESPA)。在此基础上进一步提出一种软件体系结构描述语言(PEADL)。介绍PEADL的语法和语义,并通过三层C/S结构应用系统展示PEADL的表述能力。     

An efficient algorithm for aggregating PEPA models

Performance Evaluation Process Algebra (PEPA) is a formal language for performance modeling based on process algebra. It has previously been shown that, by using the process algebra apparatus, compact performance models can be derived which retain the essential behavioral characteristics of the modeled system. However, no efficient algorithm for this derivation was given. We present an efficient algorithm which recognizes and takes advantage of symmetries within the model and avoids unnecessary computation. The algorithm is illustrated by a multiprocessor example     

Web服务编排中信息对齐交互建模方法研究

针对Web服务编排标准WS-CDL中信息对齐交互模式的异步特性,提出了一种基于进程代数的Web服务编排方法（PA4WS）,该方法新增WS-CDL工作单元描述算子,通过设置工作单元算子的卫式条件和循环条件来描述异步交互,进而完成对信息对齐交互的建模。     

基于CCS的软件规范描述及实例研究

软件规范描述方法主要是软件工程化的UML方法与形式化方法二类方法。论文主要给出了基于CCS的软件规范描述,首先根据系统需求画出进程派生树和迁移图,再根据操作语义和系统约束条件得到进程表达式,并用Java语言实现了系统原型代码。笔者的工作证明了CCS具有细节化地描述系统内部状态,便于系统软件实现的能力;在手工转换进程迁移图到进程表达式的基础上,提出了自动转换的进一步研究思路。     

Formal techniques for performance analysis: blending SAN and PEPA

In this paper we consider two performance modelling techniques from the perspectives of model construction, generation of an underlying continuous time Markov process, and the potential for reduction in the Markov process. Such careful comparison of modelling techniques allows us to appreciate the strengths and weaknesses of different approaches, and facilitates cross-fertilization between them. In the present case we take a characteristic of one formalism, functional rates in Stochastic Automata Networks, and introduce it to the other formalism, Performance Evaluation Process Algebra. We investigate the benefits of this cross-fertilization, particularly from the perspectives of Markov process generation and reduction.     

A note on an expressiveness hierarchy for multi-exit iteration

Multi-exit iteration is a generalization of the standard binary Kleene star operation. The addition of this construct to Basic Process Algebra (BPA) yields a more expressive language than that obtained by augmenting BPA with the standard binary Kleene star. This note offers an expressiveness hierarchy, modulo bisimulation equivalence, for the family of multi-exit iteration operators proposed by Bergstra, Bethke and Ponse.     

Formal enforcement of security policies on concurrent systems

This paper introduces a formal and modular technique allowing to automatically enforce a security policy on a given concurrent system. Given a concurrent program P and a security policy ?, we automatically generate another program P^′ that satisfies ? and behaves like P, except that it stops when P tries to violate the security policy ?. We use extended version of process algebra ACP (Algebra of Communicating Process) and BPA (Basic Process Algebra) as formal languages to specify both concurrent system and security policy.     

A fast stationary iterative method for a partial integro-differential equation in pricing options

A jump-diffusion model for the pricing of options leads to a partial integro-differential equation (PIDE). Discretizing the PIDE by certain method, we get a sequence of systems of linear equations, where the coefficient matrices are Toeplitz matrices. In this paper, we decompose the coefficient matrix as the sum of a tridiagonal matrix and a near low-rank matrix, and approximate the near low-rank matrix by low-rank matrices. Then we introduce a stationary iterative method for the approximate systems of linear equations. Comparison of the performance of our algorithm to that proposed in Pang et al. (Linear Algebra Appl. 434:2325–2342, 2011) is presented.     

Logic of transition systems

Labeled transition systems are key structures for modeling computation. In this paper, we show how they lend themselves to ordinary logical analysis (without any special new formalisms), by introducing their standard first-order theory. This perspective enables us to raise several basic model-theoretic questions of definability, axiomatization and preservation for various notions of process equivalence found in the computational literature, and answer them using well-known logical techniques (including the Compactness theorem, Saturation and Ehrenfeucht games). Moreover, we consider what happens to this general theory when one restricts attention to special classes of transition systems (in particular, finite ones), as well as extended logical languages (in particular, infinitary first-order logic). We hope that this puts standard logical formalisms on the map as a serious option for a theory of computational processes. As a side benefit, our approach increases comparability with several other existing formalisms over labeled transition systems (such as Process Algebra or Modal Logic). We provide some pointers to this effect, too.     

面向CPS时空性质验证的混成AADL建模与模型转换方法

随着信息物理融合系统CPS(cyber physical system)研究的深入,CPS的安全性问题越来越受到人们的广泛关注,如何验证CPS时空不一致的安全性问题已经成为研究热点.针对该问题,提出了面向CPS时空性质验证的混成AADL(architecture analysis&design language)建模与...