应用Petri网改进BPEL程序的正确性*

为了解决BPEL组合服务的正确性保证问题,提出一种基于Petri 网改善组合服务的正确性的集成方法。提出将BPEL程序转换成由PNML表示的Petri网的规则,实现由BPEL程序转换成Petri网和基于Petri网导出变迁触发序列的算法,借助一个开源工具PIPE2可分析与评价组合服务的正确性、活性等属性,所导出的触发序列可生成BPEL程序的单元测试的测试序列。案例研究表明,此方法有助于保证BPEL程序的正确性。     

自适应EFSM可执行测试序列生成

基于扩展有限状态机(EFSM)模型自动生成测试序列可以提高测试效率.由于EFSM模型包含丰富的变量和谓词条件,它们之间的冲突可能导致自动生成的测试序列不可执行.对EFSM变迁及变迁之间的关联关系进行了详细的讨论和分析,定义了一个邻接变迁关联图,提出了一种自适应EFSM可执行测试序列生成算法.新算法首先根据变量和谓词包含情况对变迁进行分类,然后深入挖掘了邻接变迁之间的关联关系,最后,基于自适应预测搜索函数启发式引导可达性分析树扩展生成可执行的测试序列.实验数据表明,与宽度优先可达性分析方法相比,新算法可以有效降低可达性分析过程中产生状态空间爆炸问题的概率,从而提高测试序列自动生成的效率.在最坏的情况下,新算法的计算时空复杂度也等同于宽度优先算法.     

基于改进谓词/变迁网的飞行方式指示器模型研究

为实现空客320飞行仿真中的飞行方式指示器(Flight Mode Annunciator, FMA)仿真,面向离散事件系统,提出一种基于二阶谓词/变迁网的建模方法,并对FMA建模及仿真验证。分析FMA系统功能特点,确定其可用谓词/变迁网建模,但FMA每当飞行方式改变时附带的白色方框提示使传统谓词/变迁网模型繁杂而难以实现。为简化系统模型,在谓词/变迁网的基础上提出继发网,以此为基础定义了适用于离散事件系统的通用型二阶谓词/变迁网,以FMA为例进行了建模及仿真验证。实验结果表明,二阶谓词/变迁网解决了离散事件系统建模时“系统中每一次状态更新都会激活同一个新事件”带来的传统谓词/变迁网模型结构复杂问题,实现了空客320飞行仿真中的FMA仿真。     

基于代数规约的Web服务测试

针对自动测试Web服务,提出基于代数规约测试Web服务的方法,包括描述Web服务的代数规约语言ASOWS。基于Web服务的代数规约,采用方法覆盖准则以及等式覆盖准则自动生成测试用例,在此基础上,设计并实现一个原型工具。结果表明该方法能够自动测试部署在Web应用服务器上的Web服务。     

基于DISCOVERER的Petri网不变式自动生成*

在Petri网的验证中,代数不变式起着非常重要的作用。将Petri网建模为半代数变迁系统,提出了自动生成不变式的算法,该不变式有助于更好地分析Petri网可达空间。算法首先将Petri网的不变式假定为一个含参数系统,然后通过求解半代数系统来求解不变式中的参数;最后,基于DISCOVERER和QEPCAD等Maple软件包实现了该算法,并通过实例说明了算法的有效性。     

基于有限状态进程的事件约束定义

测试分布式程序需要定义事件约束来检测程序执行产生的事件序列.事件约束需要根据程序的规约来推导.FSP是一类描述并发程序形式化规约的进程代数记法.它将并发进程描述为动作序列,其中动作可对应到规约级事件.E-CSPE约束在给定状态谓词下定义前后运行事件间的顺序关系.根据FSP的操作符和并发控制机制可推导E-CSPE约束.推导出来的E-CSPE约束考虑到并发程序的安全和进展属性,可据以判断程序运行的正确性和测试的充分性.     

基于UML时序图的集成测试序列自动生成

该文研究了基于UML时序图的集成测试序列自动生成方法。该方法分析了时序图的语义信息并添加语义约束规约生成可测试模型,从中提取相关信息生成有限状态机;然后使用Wp方法构造测试序列;最后使用中国邮递员算法对Wp方法进行改进生成最优测试序列。该方法生成的测试序列长度相对较短,并能充分满足测试用例覆盖需求。     

从Rose的规约文件自动生成测试用例

对基于状态的类测试用例自动生成进行了研究，重点放在状态预测和测试消息序列生成上：类的动态行为用uML的状态图表示，测试时直接从Rational Rose的规约文件中读取状态图规约生成测试消息序列；对状态的预测使用状态不变量；生成消息序列时对算法进行优化，减少消息序列的冗余，从而缩短消息序列的路径长度。     

基于谓词/变迁网的Agent规划研究

为解决规划形式化系统中动态、异步和并发等特征难以被表示的问题,提出一种使用谓词/变迁网表示Agent规划问题的形式化方法,利用谓词/变迁网的动态、异步、并发等特征表示规划问题,同时将抑制弧引入谓词/变迁网,并将 Agent的动作分为2类基本动作,即普通动作和测试动作,通过这2种动作的组合可以构成各种复杂动作。实例建模验证了采用带抑制弧的谓词变迁网表示Agent规划的可行性。     

面向Web服务测试的单线执行序列生成方法

测试用例自动生成是实现Web服务自动化测试的关键,基于代数规约的传统测试技术均依赖于创建、初始化和复制被测对象等操作来验证测试结果的正确性,但第三方Web服务并不支持这些操作,无法将测试用例转换成可执行操作序列。一种可行的解决方案是将测试用例转换成只包含一个被测服务实例、不包括实例初始化、只对实例进行状态修改和检查的线性执行序列。改进已有工作,提出包含逆项的测试执行图TEG-I来描述测试用例执行过程中的状态变化,设计TEG-I构造算法和单线执行序列生成算法并实现相应原型工具。实验结果表明,提出的方法能够有效地自动完成测试用例生成,提高Web服务的可测试性。     

CIMS Network Protocol and Its Net Models

Computer communication network architectures for cims are based on the OSI Reference Model.In this paper,CIMS network protocol model is set up on the basis of the corresqonding service model.Then the authors present a formal specification of transport protocols by using an extended Predicate/Transition net system that is briefly introduced in the third part.Finally,the general methods for the Petri nets based formal specification of CIMS network protocols are outlined.     

从BPMN模型导出组合服务的代数规约

针对应用规约自动测试BPEL表示组合服务时需要解决BPEL服务的规约生成问题,提出了一种从BPMN模型导出BPEL规范定义的组合Web服务的由代数规约语言CASOCC-WS表示的代数规约方法。首先,定义从BPMN模型转换成基调的规则和从BPMN结构转换成正则表达式的规则,设计由正则表达式导出构成公理的项的算法;然后,提出根据所得的项人工书写公理的启发式规则;最后,实现一个从BPMN模型导出组合服务基调的工具原型。案例研究表明,该方法可以解决BPEL服务的代数规约生成问题。     

An algebraic theory of object-oriented systems

The paper presents an algebraic specification of net objects. By net objects we mean those that are defined in object-oriented paradigms and those defined with nested relations in complex database models. An algebraic specification is set up that involves structures of net objects, accesses of net objects, and some features of object-oriented programming, such as multiple inheritance and polymorphism. Objects and their relationships are then characterized formally in the modeling, which utilizes the hierarchical approach in the algebraic theory of abstract data types, and is further developed by adding mechanisms from existing object systems. Categories of net objects are presented with the properties of accesses among them     

基于归结反演的Petri网推理新方法

本文首先在命题逻辑的库所／变迁网模型中，提出四种新的证明目标例题成立的推理算法，即求包含为迁的Ｔ－不变量并同时求出变迁发生序列的算法，它们都源于归结反演系统中的改进策略。     

An algebraic model for programming languages

The language of universal algebras is used as a model for programming language specification. BNF rules are employed for specifying the signature of the language algebra instead of the context free syntax. The algorithm for program evaluation is inductively defined by the following universal algebraic construction:

Any function defined on the generators of a free algebra taking values in the carrier of another similar algebra can be uniquely extended to a homomorphism between the two algebras.

Any conventional programming language can be specified by a finite set of BNF rules and its algebra of symbols is generated by a finite set of generator classes. Thus any function defined on the finite set of generators offers an algebraic mechanism for a universal algorithm for source language program evaluation.     

View Transformation in Visual Environments applied to Algebraic High-Level Nets

Graph transformation systems are a well-founded and adequate technique to describe the syntax of visual modeling languages and to formalize their semantics. Moreover, graph transformation tools support visual model specification, simulation and analysis on the basis of the rich underlying theory.Despite the benefits of model validation by simulation, sometimes it is preferable for users to see the model's behavior not in the abstract layout of the formal model, but as scenarios presented in the layout of the specific application domain. Hence, we propose the integration of a domain-oriented animation view with the model transformation system. An animation view allows to define scenario animations in a systematic way based on the formal model. The specification of the well-known Dining Philosophers system as algebraic high-level Petri net serves as running example for the extension of the model by an animation view and the derivation of animation rules from the model transformation system. A scenario animation then is obtained as transformation by applying the animation rules to model states. This visualizes the behavior of the model in the layout of philosophers sitting around a table and eating with chopsticks. A prototypical implementation of the concepts in GenGED, a visual language environment, is presented.     

Timed high-level nets

Petri nets have been widely used for modeling and analyzing concurrent systems. Several reasons contribute to their success: the simplicity of the model, the immediate graphical representation, the easy modeling of asynchronous aspects, the possibility of reasoning about important properties such as reachability, liveness, boundedness. However, the original model fails in representing two important features: complex functional aspects, such as conditions which rule the flow of control, and time. Due to that, two different classes of extensions of Petri nets have been proposed: high-level nets and timed Petri nets. High-level nets allow the representation of functional aspects in full details, but do not provide a means for representing time; on the other hand, timed Petri nets have been thought for time representation, but they do not provide a means for representing detailed functinal aspects. Thus, these two important aspects cannot be mastered together. In particular, it is difficult to express relationships between time and functional aspects.This paper investigates the relationships between high-level nets and timed Petri nets, thus extending a first set of results published in a previous paper, where a unifying Petri net based model for time representation has been proposed. It first recalls how time can be represented in a Petri net extension called ER nets, and assesses its generality. It then investigates the relationships of ER nets with the best known high-level nets. In particular it shows the overall equivalence of ER nets, Colored Petri nets and Predicate/Transition nets, and extends the mechanism for time representation introduced in ER nets to both Colored Petri nets and Predicate/Transition nets. It also shows that these models cannot be simplified without significantly constraining the timing aspects that can be modeled.     

代数规范描述及其语义的研究

用代数规范描述来描述抽象数据类型的基本思想是用它的标记和特征性质来说明抽象数据类型,它们的性质可用多类逻辑形式来表示,通常为受限的一价逻辑,例如等式