A semantic framework for metamodel-based languages

In the model-based development context, metamodel-based languages are increasingly being defined and adopted either for general purposes or for specific domains of interest. However, meta-languages such as the MOF (Meta Object Facility)—combined with the OCL (Object Constraint Language) for expressing constraints—used to specify metamodels focus on structural and static semantics but have no built-in support for specifying behavioral semantics. This paper introduces a formal semantic framework for the definition of the semantics of metamodel-based languages. Using metamodelling principles, we propose several techniques, some based on the translational approach while others based on the weaving approach, all showing how the Abstract State Machine formal method can be integrated with current metamodel engineering environments to endow language metamodels with precise and executable semantics. We exemplify the use of our semantic framework by applying the proposed techniques to the OMG metamodelling framework for the behaviour specification of the Finite State Machines provided in terms of a metamodel.     

Embedding domain-specific modelling languages in Maude specifications

We propose a formal approach for the definition and analysis of domain-specific modelling languages (dsml). The approach uses standard model-driven engineering artifacts for defining a language’s syntax (using metamodels) and its operational semantics (using model transformations). We give formal meanings to these artifacts by translating them to the Maude language: metamodels and models are mapped to equational specifications, and model transformations are mapped to rewrite rules between such specifications, which are also expressible in Maude due to Maude’s reflective capabilities. These mappings provide us, on the one hand, with abstract definitions of the mde concepts used for defining dsml, which naturally capture their intended meanings; and, on the other hand, with equivalent executable definitions, which can be directly used by Maude for formal verification. We also study a notion of operational semantics-preserving model transformations, which are model transformations between two dsml that ensure that each execution of a transformed instance is matched by an execution of the original instance. We propose a semi-decision procedure, implemented in Maude, for checking the semantics-preserving property. We also show how the procedure can be adapted for tracing finite executions of the transformed instance back to matching executions of the original one. The approach is illustrated on xspem, a language for describing the execution of activities constrained by time, precedence, and resource availability.     

A metamodel for the design of polychronous systems

This article presents the development of a metamodel and an open-source design environment for the synchronous language Signal in the Gme and Eclipse frameworks. This environment is intended to be used as a pivot modeling tool for a customized, aspect-oriented and application-driven, computer-aided engineering of embedded systems starting from multiple and heterogeneous initial specifications. The metamodel, called SignalMeta, is defined on top of the design workbench Polychrony, which is dedicated to Signal programming. Automated transformations are defined and implemented in order to produce, analyze, statically verify and model-check programs obtained from high-level models.The proposed approach promotes model-driven engineering within a framework that strongly favors formal validation. It aims at significantly decreasing design costs while improving the quality of systems. We demonstrate the agility of this approach by considering the design of both control-oriented and avionic systems. We start with an implementation of core polychronous¹ data-flow concepts in Gme and show the ease of its modular extension with application-specific concepts such as mode automata or integrated modular avionics concepts. This work is the first attempt to generalize the formal model of computation and the design philosophy of Polychrony.     

Model Checking Dynamic Memory Allocation in Operating Systems

Most system software, including operating systems, contains dynamic data structures whose shape and contents should satisfy design requirements during execution. Model checking technology, a powerful tool for automatic verification based on state exploration, should be adapted to deal with this kind of structure. This paper presents a method to specify and verify properties of C programs with dynamic memory management. The proposal contains two main contributions. First, we present a novel method to extend explicit model checking of C programs with dynamic memory management. The approach consists of defining a canonical representation of the heap, moving most of the information from the state vector to a global structure. We provide a formal semantics of the method that allows us to prove the soundness of the representation. Secondly, we combine temporal LTL and CTL logic to define a two-dimensional logic, in time and space, which is suitable to specify complex properties of programs with dynamic data structures. We also define the model checking algorithms for this logic. The whole method has been implemented in the well known model checker SPIN, and illustrated with an example where a typical memory reader/writer driver is modelled and analyzed.     

Using UML Action Semantics for model execution and transformation

The Unified Modelling Language (UML) lacks precise and formal foundations and semantics for several modeling constructs, such as transition guards or method bodies. These semantic discrepancies and loopholes prevent executability, making early testing and validation out of reach of UML tools. Furthermore, the semantic gap from high-level UML concepts to low-level programming constructs found in traditional object-oriented language prevents the development of efficient code generators.The recent Action Semantics (AS) proposal tackles these problems by extending the UML with yet another formalism for describing behavior, but with a strong emphasis on dynamic semantics. This formalism provides both, a metamodel integrated into the UML metamodel, and a model of execution for these statements. As a future OMG standard, the AS eases the move to tool interoperability, and allows for executable modeling and simulation.We explore in this paper a specificity of the AS: its applicability to the UML metamodel, itself a UML model. We show how this approach paves the way for powerful metaprogramming for model transformation. Furthermore, the overhead for designers is minimal, as mappings from usual object-oriented languages to the AS will be standardized.     

基于活动图的C4ISR能力需求过程建模及验证

当前对C⁴ISR系统能力需求的描述大多基于图形、文字等静态模型,对信息和数据的具体操作没有进行定义,以至于对象之间的行为过程没有详细说明。缺乏可执行动态语义的能力模型是不可执行的,因此提出了一种基于活动图的能力需求过程建模方法,为可执行体系结构的建模仿真提供支撑。首先给出了系统过程模型的定义,在C⁴ISR系统能力元概念模型的指导下,通过扩展UML活动图得到系统的能力需求过程元模型。然后用本体表示能力需求过程元模型语义,通过对本体的逻辑推理实现对C⁴ISR系统能力需求过程元模型的验证。     

Automated generation of test oracles using a model-driven approach

ContextSoftware development time has been reduced with new development tools and paradigms, testing must accompany these changes. In order to release software products in a timely manner as well as to minimise the impact of possible errors introduced during maintenance interventions, testing automation has become a central goal. Whilst research has produced significant results in test case generation and tools for test case (re)-execution, one of the most important open problems in testing is the automation of oracle generation. The oracle decides whether the program under test has or has not behaved correctly and then issues a pass/fail verdict. In most cases, writing the oracle is a time-consuming activity that, moreover, is manual in most cases.ObjectiveThis article automates two important steps in the test oracle: obtention of expected output and its comparison with the actual output, using a model-driven approach.MethodThe oracle automation problem is resolved using a model-driven framework, based on OMG standards: UML is used as metamodel and QVT and MOF2Text as transformation languages. The automated testing framework takes the models that describe the system as input, using UML notation and derives from them the test model and then the test code, following a model-driven approach. Test oracle procedures are obtained from a UML state machine.ResultsA complete executable test case at functional test level is obtained, composed of a test procedure with parametrized input test data and expected result automation.ConclusionThe oracle automation is obtained using a model-driven approach, test cases are obtained automatically from UML models. The model-driven testing framework was applied to an industrial application and has been useful to testing automation for the main functionalities in the system.     

Exploring system architectures in AADL via Polychrony and SynDEx

Architecture analysis & design language (AADL) has been increasingly adopted in the design of embedded systems, and corresponding scheduling and formal verification have been well studied. However, little work takes code distribution and architecture exploration into account, particularly considering clock constraints, for distributed multi-processor systems. In this paper, we present an overview of our approach to handle these concerns, together with the associated toolchain, AADL-Polychrony-SynDEx. First, in order to avoid semantic ambiguities of AADL, the polychronous/multiclock semantics of AADL, based on a polychronous model of computation, is considered. Clock synthesis is then carried out in Polychrony, which bridges the gap between the polychronous semantics and the synchronous semantics of SynDEx. The same timing semantics is always preserved in order to ensure the correctness of the transformations between different formalisms. Code distribution and corresponding scheduling is carried out on the obtained SynDEx model in the last step, which enables the exploration of architectures originally specified in AADL. Our contribution provides a fast yet efficient architecture exploration approach for the design of distributed real-time and embedded systems. An avionic case study is used here to illustrate our approach.     

Constructing language processors with algebra combinators

Modular Monadic Semantics (MMS) is a well-known mechanism for structuring modular denotational semantic definitions for programming languages. The principal attraction of MMS is that families of language constructs can be independently specified and later combined in a mix-and-match fashion to create a complete language semantics. This has proved useful for constructing formal, yet executable, semantics when prototyping languages. In this work we demonstrate that MMS has an additional software engineering benefit. In addition to composing semantics for various language constructs, we can use MMS to compose various differing semantics for the same language constructs. This capability allows us to compose and reuse orthogonal language tasks such as type checking and compilation. We describe algebra combinators, the principal vehicle for achieving this reuse, along with a series of applications of the technique for common language processing tasks.     

基于扩展Petri网模型的BPMN形式化

BPMN(Business Process Modeling Notation)作为一个在系统开发早期阶段获取业务过程模型的标准,指导系统的设计和开发,其模型的正确性是影响软件开发质量的关键。鉴于BPMN模型的形式化可以验证模型的正确性,提出了一种利用扩展Petri网模型,应用模型驱动技术实现BPMN模型形式化自动执行的方法。该方法通过细化Petri网模型中的Transition和Place元素以及增加Organization Identifier和Group Identifier容器,使其不但能够描述BPMN模型中的动态行为,而且还能描述BPMN模型中的动态行为协作和静态组织结构。从元模型结构、语法和图标记方面详细分析了扩展的Petri网模型元素,利用模型驱动开发技术设计BPMN模型元素至扩展的Petri网模型元素的转换规则,并在Eclipse平台上使用ATL模型转换语言执行映射,实现形式化的自动执行。最后在此基础上应用Travel Agency系统演示了模型形式化插件BPMN2ExtendPetrinets的执行结果。     

Deductive verification of alternating systems

Alternating systems are models of computer programs whose behavior is governed by the actions of multiple agents with, potentially, different goals. Examples include control systems, resource schedulers, security protocols, auctions and election mechanisms. Proving properties about such systems has emerged as an important new area of study in formal verification, with the development of logical frameworks such as the alternating temporal logic ATL*. Techniques for model checking ATL* over finite-state systems have been well studied, but many important systems are infinite-state and thus their verification requires, either explicitly or implicitly, some form of deductive reasoning. This paper presents a theoretical framework for the analysis of alternating infinite-state systems. It describes models of computation, of various degrees of generality, and alternating-time logics such as ATL* and its variations. It then develops a proof system that allows to prove arbitrary ATL* properties over these infinite-state models. The proof system is shown to be complete relative to validities in the weakest possible assertion language. The paper then derives auxiliary proof rules and verification diagrams techniques and applies them to security protocols, deriving a new formal proof of fairness of a multi-party contract signing protocol where the model of the protocol and of the properties contains both game-theoretic and infinite-state (parameterized) aspects.     

Tool support for the rapid composition, analysis and implementation of reactive services

We present the integrated set of tools Arctis for the rapid development of reactive services. In our method, services are composed of collaborative building blocks that encapsulate behavioral patterns expressed as UML 2.0 collaborations and activities. Due to our underlying semantics in temporal logic, building blocks as well as their compositions can be transformed into formulas and model checked incrementally in order to guarantee that important system properties are kept. The process of model checking is fully automated. Error traces are presented to the users as easily understandable animations, so that no expertise in temporal logic is needed. In addition, the results of model checking are analyzed, so that in some cases automated diagnoses and fixes can be provided as well. The formal semantics also enables the correct, automatic synthesis of the activities to state machines which form the input of our code generators. Thus, the collaborative models can be fully automatically transformed into executable Java code. We present the development of a mobile treasure hunt system to exemplify the method and the tools.     

Deriving performance-relevant infrastructure properties through model-based experiments with Ginpex

To predict the performance of an application, it is crucial to consider the performance of the underlying infrastructure. Thus, to yield accurate prediction results, performance-relevant properties and behaviour of the infrastructure have to be integrated into performance models. However, capturing these properties is a cumbersome and error-prone task, as it requires carefully engineered measurements and experiments. Existing approaches for creating infrastructure performance models require manual coding of these experiments, or ignore the detailed properties in the models. The contribution of this paper is the Goal-oriented INfrastructure Performance EXperiments (Ginpex) approach, which introduces goal-oriented and model-based specification and generation of executable performance experiments for automatically detecting and quantifying performance-relevant infrastructure properties. Ginpex provides a metamodel for experiment specification and comes with predefined experiment templates that provide automated experiment execution on the target platform and also automate the evaluation of the experiment results. We evaluate Ginpex using three case studies, where experiments are executed to quantify various infrastructure properties.     

The clock constraint specification language for building timed causality models

The uml Profile for Modeling and Analysis of Real-Time and Embedded (RTE) systems has recently been adopted by the OMG. Its Time Model extends the informal and simplistic Simple Time package proposed by Unified Modeling Language (UML2) and offers a broad range of capabilities required to model RTE systems including discrete/dense and chronometric/logical time. The Marte specification introduces a Time Structure inspired from several time models of the concurrency theory and proposes a new clock constraint specification language (ccsl) to specify, within the context of the uml, logical and chronometric time constraints. A semantic model in ccsl is attached to a (uml) model to give its timed causality semantics. In that sense, ccsl is comparable to the Ptolemy environment, in which directors give the semantics to models according to predefined models of computation and communication. This paper focuses on one historical model of computation of Ptolemy [Synchronous Data Flow (SDF)] and shows how to build SDF graphs by combining uml models and ccsl.     

以体系结构为中心的模型转换的语义描述框架

在对类型范畴理论进行扩展的基础上,将其与进程代数相结合,为软件体系结构模型及其间的转换关系提供了一种统一的语义描述框架.模型的结构语义由类型范畴图表来指代,其行为语义则由范畴附带的进程行为迹来表示,模型间的映射关系用范畴理论中的态射和函子来形式化描述.该描述框架可用于模型转换中特性保持问题的描述、分析和判定,从而为模型驱动的软件开发提供有力的支持.     

On the relation among answer set solvers

In this paper, we study the relation among Answer Set Programming (ASP) systems from a computational point of view. We consider smodels, dlv, and cmodels ASP systems based on stable model semantics, the first two being native ASP systems and the last being a SAT-based system. We first show that smodels, dlv, and cmodels explore search trees with the same branching nodes (assuming, of course, a same branching heuristic) on the class of tight logic programs. Leveraging on the fact that SAT-based systems rely on the deeply studied Davis–Logemann–Loveland (dll) algorithm, we derive new complexity results for the ASP procedures. We also show that on nontight programs the SAT-based systems are computationally different from native procedures, and the latter have computational advantages. Moreover, we show that native procedures can guarantee the “correctness” of a reported solution when reaching the leaves of the search trees (i.e., no stability check is needed), while this is not the case for SAT-based procedures on nontight programs. A similar advantage holds for dlv in comparison with smodels if the “well-founded” operator is disabled and only Fitting’s operator is used for negative inferences. We finally study the “cost” of achieving such advantages and comment on to what extent the results presented extend to other systems.     

A generic framework: from modeling to code

Model-driven development (MDD) is a very popular technique in the area of software development, but this technique is criticized due to lack of a formal semantics. MDD is used for large-scale system development using semi-formal techniques like UML (Unified Modeling Language), which are not amenable to formal analysis and consistency checking. Formal methods with MDD may provide an assurance of correctness of the system. This paper advocates an approach to building generic framework for rigorous MDD that is based on combining semi-formal notations with formal modeling languages, correctness of the system using model checker and automatic code generation from the verified formal specification. The main objective of this work is to apply model-driven techniques and tools with formal verification and its code generation for designing critical systems. An assessment of the proposed framework is given through a case study, relative to the development of a cardiac pacemaker system.     

Balancing theEuLisp metaobject protocol

The challenge for the metaobject protocol designer is to balance the conflicting demands of efficiency, simplicity, and extensibility. It is impossible to know all desired extensions in advance; some of them will require greater functionality, while others require greater efficiency. In addition, the protocol itself must be sufficiently simple that it can be fully documented and understood by those who need to use it. This paper presents the framework of a metaobject protocol forEuLisp which provides expressiveness by a multi-leveled protocol and achieves efficiency by static semantics for predefined metaobjects and modularizing their operations. TheEuLisp module system supports global optimizations of metaobject applications. The metaobject system itself is structured into modules, taking into account the consequences for the compiler. It provides introspective operations as well as extension interfaces for various functionalities, including new inheritance, allocation, and slot access semantics. While the overall goals and functionality are close to those of Kiczaleset al. [9], the approach shows different emphases. As a result, time and space efficiency as well as robustness have been improved.