模态顺序图uMSD 的形式语义

UML 2.0顺序图已广泛应用于业界,但其语义模糊,以至于不能有效地加以使用.模态顺序图(modal sequence diagram,简称MSD)是对UML 2.0顺序图的模态扩展,区分了强制场景(用universal MSD表示,简称uMSD)和可能场景(用existential MSD表示,简称eMSD).其中,uMSD具有较强的表达能力,能够用于表示并发系统的时态性质,故主要工作围绕uMSD展开.为了使uMSD用于形式化分析、验证和监控,给出基于自动机的uMSD语义解释,并给出各种操作符的算法,用性质规约模式度量uMSD的表达能力.最后进行了实例研究,并讨论了其应用前景.     

Polymorphic scenario-based specification models: semantics and applications

We present polymorphic scenarios, a generalization of a UML2-compliant variant of Damm and Harel??s live sequence charts (LSC) in the context of object-orientation. Polymorphic scenarios are visualized using (modal) sequence diagrams where lifelines may represent classes and interfaces rather than concrete objects. Their semantics takes advantage of inheritance and interface realization to allow the specification of most expressive, succinct, and reusable universal and existential inter-object scenarios for object-oriented system models. We motivate the use of polymorphic scenarios, formally define their trace-based semantics, and present their application for scenario-based testing and execution, as implemented in the S2A compiler developed at the Weizmann Institute of Science. We further discuss advanced semantic issues arising from the use of scenarios in a polymorphic setting, suggest possible extensions, present a UML profile to support polymorphic scenarios, consider the application of the polymorphic semantics to other variants of scenario-based specification languages, and position our work in the broader context of behavioral subtyping.     

Automatically Detecting and Visualising Errors in UML Diagrams

UML has become the de facto standard for object-oriented modelling. Currently, UML comprises several different notations with no formal semantics attached to the individual diagrams or their integration, thus preventing rigorous analysis of the diagrams. Previously, we developed a formalisation framework that attaches formal semantics to a subset of UML diagrams used to model embedded systems. This paper describes automated structural and behavioural analyses applicable to UML diagrams using our formalisation framework. In addition to intra- and inter-diagram consistency checks, we discuss how simulation and model checking can be used in tandem for behavioural analysis of the UML diagrams. Our tools also visually interpret the analysis results in terms of the original UML diagrams, thereby facilitating their correction and refinement. We illustrate these capabilities through the modelling and analysis of UML diagrams for an automotive industrial case study. Correspondence and offprint requests to: Dr B. Cheng, Software Engineering and Network Systems Laboratory, Department of Computer Science and Engineering, Michigan State University, 3115 Engineering Building, East Lansing, MI 48824, USA. Tel.: +1 517 355 8344; Fax: +1 517 432 1061; Email: chengb@cse.msu.edu     

Graphical scenarios for specifying temporal properties: an automated approach

Temporal logics are commonly used for reasoning about concurrent systems. Model checkers and other finite-state verification techniques allow for automated checking of system model compliance to given temporal properties. These properties are typically specified as linear-time formulae in temporal logics. Unfortunately, the level of inherent sophistication required by these formalisms too often represents an impediment to move these techniques from “research theory” to “industry practice”. The objective of this work is to facilitate the nontrivial and error prone task of specifying, correctly and without expertise in temporal logic, temporal properties. In order to understand the basis of a simple but expressive formalism for specifying temporal properties we critically analyze commonly used in practice visual notations. Then we present a scenario-based visual language called Property Sequence Chart (PSC) that, in our opinion, fixes the highlighted lacks of these notations by extending a subset of UML 2.0 Interaction Sequence Diagrams. We also provide PSC with both denotational and operational semantics. The operational semantics is obtained via translation into Büchi automata and the translation algorithm is implemented as a plugin of our Charmy tool. Expressiveness of PSC has been validated with respect to well known property specification patterns. Preliminary results appeared in (Autili et al. 2006a).     

The many meanings of UML 2 Sequence Diagrams: a survey

Scenario languages are widely used in software development. Typical usage scenarios, forbidden behaviors, test cases, and many more aspects can be depicted with graphical scenarios. Scenario languages were introduced into the Unified Modeling Language (UML) under the name of Sequence Diagrams. The 2.0 version of UML changed Sequence Diagrams significantly and the expressiveness of the language was highly increased. However, the complexity of the language (and the diversity of the goals Sequence Diagrams are used for) yields several possible choices in its semantics. This paper collects and categorizes the semantic choices in the language, surveys the formal semantics proposed for Sequence Diagrams, and presents how these approaches handle the various semantic choices.     

LSC Verification for UML Models with Unbounded Creation and Destruction

The approaches to automatic formal verification of UML models known up to now require a finite bound on the number of objects existing at each point in time. In [W. Damm, B. Westphal, Live and let die: LSC-based verification of UML-models, Science of of Computer Programming 55 (2005) 117–159] we have observed that the class of hardware systems with replicated components studied by McMillan [K.L. McMillan, A methodology for hardware verification using compositional model checking, Science of Computer Programming 37 (2000) 279–309] is equivalent to the class of systems where the only source of infiniteness is unbounded creation and destruction of objects, i.e. where all data-types except for object identities are finite. Exploiting the symmetry of UML models induced by objects being instances of classes, the restriction to finite bounds can be overcome applying [K.L. McMillan, A methodology for hardware verification using compositional model checking, Science of Computer Programming 37 (2000) 279–309].In this paper we report on experiences from an evaluation of this approach within the UML Verifi- cation Environment (UVE) [I. Schinz, T. Toben, C. Mrugalla and B. Westphal, The Rhapsody UML Verification Environment, in: J.R. Cuellar and Z. Liu, editors, Proceedings SEFM 2004 (2004), pp. 174–183], a state-of-the-art tool for formal verification of UML models using Live Sequence Charts (LSC) [W. Damm, D. Harel, LSCs: Breathing Life into Message Sequence Charts, Formal Methods in System Design 19 (2001) 45–80] for requirements specification.     

包含协议和语义的构件一致性验证方法

在基于构件的系统设计中,需要对构件的一致性进行验证。构件的一致性包括语义一致性和协议一致性,已有的一致性验证方法仅支持构件的协议一致性验证。而在实际应用中除了要进行构件的协议一致性验证外,还需要进行其语义一致性验证。为此提出了一种包含协议和语义的构件一致性验证方法。所提方法将方法语义与基于场景的需求规约相结合,使用语义扩展接口自动机模型(SIA)来建模构件的语义和协议信息,使用带有语义约束的UML交互概观图来表示基于场景的需求规约。通过对SIA和带语义约束的UML交互概观图的行为的理论分析,进一步形成了一种一致性验证算法,并用实例来说明其过程。该算法不仅能够检验系统中构件的协议一致性,而且能够检验其语义一致性。该算法中的方法语义包括了该方法参数的类型和详细语义信息,更符合实际应用情形。     

TURTLE: a real-time UML profile supported by a formal validation toolkit

We present a UML 1.5 profile named TURTLE (Timed UML and RT-LOTOS Environment) endowed with a formal semantics given in terms of RT-LOTOS. TURTLE relies on UML's extensibility mechanisms to enhance class and activity diagrams. Class diagrams are extended with specialized classes named Tclasses, which communicate and synchronize through gates. Also, associations between Tclasses are attributed by a composition operator (Parallel, Synchro, Invocation, Sequence, or Preemption) which provides them with a formal semantics. TURTLE extends UML activity diagrams with synchronization actions and temporal operators (deterministic delay, nondeterministic delay, time-limited offer, and time-capture). The real-time dimension of TURTLE has been further improved by the addition of two composition operators, periodic and suspend, as well as suspendable delay, latency, and time-limited offer operators at the activity diagram level. Core characteristics of TURLE are supported by TTool - the TURTLE toolkit - which includes a diagram editor, a RT-LOTOS code generator and a result analyzer. The toolkit reuses RTL, a RT-LOTOS validation tool offering debug-oriented simulation and exhaustive analysis. TTool hides RT-LOTOS to the end-user and allows him/her to directly check TURTLE modeling against logical errors and timing inconsistencies. Besides the foundations of the TURTLE profile, this paper also discusses its application in the context of space-based embedded software.     

基于通信序列进程的UML序列图形式化方法

UML2.0序列图是一种描述对象之间动态协作和事件发展时间关系的视图,但是UML序列图缺乏精确的形式化语义,所以不利于对其所描述的系统进行形式化验证。为此,根据UML2.0语义文档及组合碎片包概念,基于通信序列进程(CSP)给出了UML序列图的基本元素和消息迹的形式化定义及生成规则,实现了UML序列图的形式化,为UML序列图在描述系统准确性和有效性方面提供了形式化的检验方法。最后通过ATM实例说明UML序列图这一过程的正确性。     

基于UML交互概览图的测试线索的生成方法

针对单一UML模型测试不充分的问题,结合UML2.0交互概览图的特点开展测试方法研究,提出一种测试线索自动生成的方法。首先,给出UML类图、顺序图、交互概览图(OID)的形式化定义;通过提取交互概览图的流程信息和对象交互信息分别构造节点控制流图(NCFG)和消息序列图(MSD);将从MSD提取的消息路径嵌入到NCFG中,构造可测试交互概览图模型;最后采用两两覆盖准则生成测试线索。实验验证了该方法自动生成的测试线索在保证测试充分性的前提下可避免组合爆炸。     

UML2.0顺序图的形式化研究

在UML2.0规范中顺序图的语义仍然是以自然语言的形式描述的,为实现对顺序图的自动化分析和验证,必须为顺序图定义一种形式化的语义模型.为此首先给出了UML顺序图的一种符合BNF范式的形式化语法,然后为该语法中的非终止符定义转换规则,将UML顺序图中的基本动作转换为加标Petri网组件,最后定义了各种合成操作,利用这些合成操作可以将UML顺序图的加标Petri网组件转换为加标Petni网.     

基于时序逻辑的UML2.0通信图语义研究

UML2.0通信图可以表示对象之间的交互,很适合用于对系统的交互行为建模,但由于UML缺乏精确语义,使得难以对其所表示的系统行为进行分析和验证.XYZ/E是可执行线性时序逻辑语言,既可描述系统的静态语义和动态语义.在定K.UML2.0通信图的形式化语法的基础上,给出了通信图的XYZ/E时序逻辑语义,为进一步的系统分析和验证提供了形式化基础.     

从活性顺序图到时态逻辑的转化方法

为了将活性顺序图用于模型检测,方便描述系统的场景需求,提出了一种将活性顺序图转换成时态逻辑的转化方法.分析活性顺序图语言并且定义一种基于路径的语义,用活性顺序图表述系统的场景需求.根据提出的语义,给出了一个将场景需求显式转化为时态逻辑的一般方法,针对并发消息较多的系统扩展和优化此方法,以得到更简短的时态逻辑公式.通过实例说明活性顺序图到线性时态逻辑的转化过程.     

UML2．0顺序图的XYZ／E时序逻辑语义研究

UML2．0顺序图适合于描述软件体系结构的各个组件之间和复合组件内部各个子组件之间的动态交互行为，但由于UML2．0顺序图的语义不够精确，使得它的描述结果不利于进一步的分析和验证。基于此，本文在定义UML2．0顺序图的语法和语法约束的基础上，给出了UML2．0顺序图的XYZ／E时序逻辑语义，为使用UML2．0顺序图与XYZ／E相结合的方式来描述软件体系结构的动态交互行为奠定了基础。     

基于时序描述逻辑的UML顺序图形式化研究

在统一建模语言（UML）规范中顺序图的语义是以自然语言的形式描述的,是一种半形式化的语言,不能对系统的交互行为进行形式化分析及论证.针对UML顺序图缺乏精确的形式化描述问题,根据顺序图的时序特征,提出了增加交互操作符的UML顺序图的六元组形式化方法.对描述逻辑进行时序扩展,得到可表示动态和时序语义的形式化规范——时序描述逻辑.应用时序描述逻辑的时态算子得到时序描述逻辑语义形式的UML顺序图.用UML顺序图描述完整的C语言执行过程,将其形式化描述,实验结果表明,这种方法是可行的.     

UML2．0类图的一种形式化描述方法

UML类图是根据系统中的类，以及各个类之间的关系来描述系统的静态视图。基于UML缺乏精确语义描述的不足，我们提出了基于时序逻辑语言XYZ／E来表示类图形式化语义的方法。通过对UML2．0类图元素及其特点的分析，找出类图元素的形式化描述规则，利用转换法实现了对UML2．0类图的XYZ／E形式化描述。     

Modelling concurrent interactions

In UML 2.0 sequence diagrams have been considerably extended but their expressiveness and semantics remains problematic in several ways. In other work we have shown how sequence diagrams combined with an OCL liveness template gives us a much richer language for inter-object behaviour specification. In this paper, we give a semantics of these enriched diagrams using labelled event structures. Further, we show how sequence diagrams can be embedded into a true-concurrent two-level logic interpreted over labelled event structures. The top level logic, called communication logic, is used to describe inter-object specification, whereas the lower level logic, called home logic, describes intra-object behaviour. An interesting consequence of using this logic relates to how state-based behaviour can be synthesised from inter-object specifications. Plans of extending the Edinburgh Concurrency Workbench in this context are discussed.     

Semantics and Verification of Data Flow in UML 2.0 Activities

One of the major changes in going from UML 1.5 to UML 2.0 is the reengineering of activity diagrams. This paper examines activity diagramies as described in the current version of the UML 2.0 standard by defining a denotational semantics. It covers basic control flow and data flow, but excludes hierarchy, expansion nodes, and exception handling (see [Störrle, H., Semantics of Control-Flow in UML 2.0 Activities, in: P. Bottoni, C. Hundhausen, S. Levialdi and G. Tortora, editors, Proc. IEEE Symposium on Visual Languages and Human-Centric Computing (VL/HCC) (2004), pp. 235–242, Störrle, H., Semantics of Exceptions in UML 2.0 Activities (2004), submitted to Journal of Software and Systems Modeling, May, 9^th, available at www.pst.informatik.uni-muenchen.de/~stoerrle, Störrle, H., Semantics of Expansion Nodes in UML 2.0 Activities, in: I. Porres, editor, Proc. 2^nd Nordic Ws. on UML, Modeling, Methods and Tools (NWUML'04), 2004] for these issues). The paper shows, where the constructs proposed in the standard are not so easily formalized, and how the formalisation may be used for formal analysis.     

UML2.0顺序图的时序描述逻辑语义

针对UML2.0顺序图用于对象间交互行为建模时存在动态语义缺乏精确形式化描述的问题,提出一种基于时序描述逻辑的UML2.0顺序图形式化方法。对描述逻辑进行时序扩展,得到可表示动态和时序语义的形式化规范——时序描述逻辑,根据UML2.0新增的交互操作符将UML2.0顺序图分成一个或多个最大顺序片段,通过形式化最大顺序片段和交互操作符得到UML2.0顺序图的时序描述逻辑语义。实例检验结果表明,该方法具有可行性。