When using graphs and graph transformations to model systems, consistency is an important concern. While consistency has primarily been viewed as a binary property, i.e., a graph is consistent or inconsistent with respect to a set of constraints, recent work has presented an approach to consistency as a graduated property. This allows living with inconsistencies for a while and repairing them when necessary. For repairing inconsistencies in a graph, we use graph transformation rules with so-called {\em impairment-indicating and repair-indicating application conditions} to understand how much repair gain certain rule applications would bring. Both types of conditions can be derived from given graph constraints. Our main theorem shows that the difference between the number of actual constraint violations before and after a graph transformation step can be characterised by the difference between the numbers of violated impairment-indicating and repair-indicating application conditions. This theory forms the basis for algorithms with look-ahead that rank graph transformations according to their potential for graph repair. An evaluation shows that graph repair can be well-supported by rules with these new types of application conditions in terms of effectiveness and scalability.

Abstract In many recent application domains, software systems must repeatedly reconfigure themselves at runtime to satisfy changing contextual requirements. To decide which next configuration is presumably best suited is a very challenging task as it involves not only functional requirements but also non-functional properties (NFP). NFP include multiple, potentially contradicting, criteria like real-time constraints and cost measures like energy consumption. Effectiveness of context-aware reconfiguration decisions further depends on mostly uncertain future contexts which makes greedy one-step decision heuristics potentially misleading. Moreover, the computational runtime overhead for reconfiguration planning should not nullify the benefits. Nevertheless, entirely pre-planning reconfiguration decisions during design time is also not feasible due to missing knowledge about runtime contexts. In this article, we propose a model-based technique for precomputing context-aware reconfiguration decisions under partially uncertain real-time constraints and cost measures. We employ a game-theoretic approach based on stochastic priced timed game automata as reconfiguration model. This formal model allows us to automatically synthesize winning strategies for the first player (the system) which efficiently delivers presumably best-fitting reconfiguration decisions as reactions to moves of the second player (the context) at runtime. Our tool implementation copes with the high computational complexity of strategy synthesis by utilizing the statistical model checker Uppaal Stratego to approximate near-optimal solutions. We applied our tool to a real-world example consisting of a reconfigurable robot support system for the construction of aircraft fuselages. Our evaluation results show that Uppaal Stratego is indeed able to precompute effective reconfiguration strategies within a reasonable amount of time.

timeaware reconfiguration strategies based on stochastic priced timed games", written by Hendrik Göttmann, Birte Caesar,

Sequential model synchronisation is the task of propagating changes from one model to another correlated one to restore consistency. It is challenging to perform this propagation in a least-changing way that avoids unnecessary deletions (which might cause information loss). From a theoretical point of view, so-called short-cut (SC) rules have been developed that enable provably correct propagation of changes while avoiding information loss. However, to be able to react to every possible change, an infinite set of such rules might be necessary. Practically, only small sets of pre-computed basic SC rules have been used, severely restricting the kind of changes that can be propagated without loss of information. In this work, we close that gap by developing an approach to compute more complex required SC rules on-the-fly during synchronisation. These higher-order SC rules allow us to cope with more complex scenarios when multiple changes must be handled in one step. We implemented our approach in the model transformation tool eMoflon. An evaluation shows that the overhead of computing higher-order SC rules on-the-fly is tolerable and at times even improves the overall performance. Above that, completely new scenarios can be dealt with without the loss of information.

Many modern software systems continuously reconfigure themselves to (self-)adapt to ever-changing environmental contexts. Selecting presumably best-fitting next configurations is, however, very challenging, depending on functional and non-functional criteria like real-time constraints as well as inherently uncertain future contexts which makes greedy one-step decision heuristics ineffective. In addition, the computational overhead caused by reconfiguration planning at run-time should not outweigh its benefits. On the other hand, completely pre-planning reconfiguration decisions at design time is also infeasible due to the lack of knowledge about the context behavior. In this paper, we propose a game-theoretic setting for precomputing reconfiguration decisions under partially uncertain real-time behavior. We employ stochastic timed game automata as reconfiguration model to derive winning strategies which enable the first player (the system) to make fast look-ups for presumably best-fitting reconfiguration decisions satisfying the second player (the context). To cope with the high computational complexity of finding winning strategies, our tool implementation1 utilizes the statistical model-checker Uppaal Stratego to approximate near-optimal solutions. In our evaluation, we investigate efficiency/effectiveness trade-offs by considering a real-world example consisting of a reconfigurable robot support system for the construction of aircraft fuselages.

Abstract Model synchronization, i.e., the task of restoring consistency between two interrelated models after a model change, is a challenging task. Triple graph grammars (TGGs) specify model consistency by means of rules that describe how to create consistent pairs of models. These rules can be used to automatically derive further rules, which describe how to propagate changes from one model to the other or how to change one model in such a way that propagation is guaranteed to be possible. Restricting model synchronization to these derived rules, however, may lead to unnecessary deletion and recreation of model elements during change propagation. This is inefficient and may cause unnecessary information loss, i.e., when deleted elements contain information that is not represented in the second model, this information cannot be recovered easily. Short-cut rules have recently been developed to avoid unnecessary information loss by reusing existing model elements. In this paper, we show how to automatically derive (short-cut) repair rules from short-cut rules to propagate changes such that information loss is avoided and model synchronization is accelerated. The key ingredients of our rule-based model synchronization process are these repair rules and an incremental pattern matcher informing about suitable applications of them. We prove the termination and the correctness of this synchronization process and discuss its completeness. As a proof of concept, we have implemented this synchronization process in eMoflon, a state-of-the-art model transformation tool with inherent support of bidirectionality. Our evaluation shows that repair processes based on (short-cut) repair rules have considerably decreased information loss and improved performance compared to former model synchronization processes based on TGGs.

Abstract Software model checkers can be used to generate high-quality test cases from counterexamples of a reachability analysis. However, naïvely invoking a software model checker for each test goal in isolation does not scale to large programs as a repeated construction of an abstract program model is expensive. In contrast, invoking a software model checker for reaching all test goals in a single run leads to few abstraction possibilities and thus to low scalability. Therefore, our approach pursues a test-suite generation technique that incorporates configurable multi-goal set partitioning (MGP) including configurable partitioning strategies and simultaneous processing of multiple test goals in one reachability analysis. Our approach employs recent techniques from multi-property verification in order to control the computational overhead for tracking multi-goal reachability information. Our tool, called CPA/Tiger-MGP, uses predicate-abstraction-based program analysis in the model-checking framework CPAchecker.

Solving scheduling problems is important for a wide range of application domains including home care in the health care domain, allocation engineering in the automotive domain, and virtual network embedding in the network virtualisation domain. Standard solution approaches assume that an initially given problem definition (e.g. a set of constraints and an objective function) can be fixed, and does not have to be constantly changed and validated by domain experts. In this paper, we investigate an application where this is not the case: at dSPACE GmbH, a developer of software and hardware for mechatronic control systems, recurring manual tests must be executed in every development and release cycle. To allocate human resources (developers and testers) to perform these tests, a test schedule must be created and maintained during the testing process. Prior to our work, test scheduling at dSPACE was performed manually by a test manager, requiring more than one working day to create the initial schedule, and several hours of tedious, error-prone work every week to maintain the schedule. The novel challenge here is that an acceptable automation must be highly configurable by the test manager (the domain expert), who should be able to easily adapt and validate the problem definition on a regular basis. We demonstrate that techniques and results from consistency maintenance via triple graph grammars, and constraint solving via linear programming can be synergetically combined to yield a highly configurable and fully automated approach to test schedule generation. We evaluate our solution at dSPACE and show that it not only reduces the effort required to create and maintain schedules of acceptable quality, but that it can also be understood, configured, and validated by the test manager.

Concurrent model synchronization is the task of restoring consistency between two correlated models after they have been changed concurrently and independently. To determine whether such concurrent model changes conflict with each other and to resolve these conflicts taking domain- or user-specific preferences into account is highly challenging. In this paper, we present a framework for concurrent model synchronization algorithms based on Triple Graph Grammars (TGGs). TGGs specify the consistency of correlated models using grammar rules; these rules can be used to derive different consistency restoration operations. Using TGGs, we infer a causal dependency relation for model elements that enables us to detect conflicts non-invasively. Different kinds of conflicts are detected first and resolved by the subsequent conflict resolution process. Users configure the overall synchronization process by orchestrating the application of consistency restoration fragments according to several conflict resolution strategies to achieve individual synchronization goals. As proof of concept, we have implemented this framework in the model transformation tool eMoflon. Our initial evaluation shows that the runtime of our presented approach scales with the size of model changes and conflicts, rather than model size.

Trends such as the Internet of Things lead to a growing number of networked devices and to a variety of communication systems. Adding self-adaptive capabilities to these communication systems is one approach to reducing administrative effort and coping with changing execution contexts. Existing frameworks can help reducing development effort but are neither tailored toward the use in communication systems nor easily usable without knowledge in self-adaptive systems development. Accordingly, in previous work, we proposed REACT, a reusable, model-based runtime environment to complement communication systems with adaptive behavior. REACT addresses heterogeneity and distribution aspects of such systems and reduces development effort. In this article, we propose REACT-ION—an extension of REACT for situation awareness. REACT-ION offers a context management module that is able to acquire, store, disseminate, and reason on context data. The context management module is the basis for (i) proactive adaptation with REACT-ION and (ii) self-improvement of the underlying feedback loop. REACT-ION can be used to optimize adaptation decisions at runtime based on the current situation. Therefore, it can cope with uncertainty and situations that were not foreseeable at design time. We show and evaluate in two case studies how REACT-ION’s situation awareness enables proactive adaptation and self-improvement.

Model synchronization, i.e., the task of restoring consistency between two interrelated models after a model change, is a challenging task. Triple Graph Grammars (TGGs) specify model consistency by means of rules. They can be used to automatically derive specifications of edit operations for single models and repair rules that propagate model changes to related models. model (re-)synchronization activities more effectively, a construction mechanism for short-cut rules has been recently developed. They describe consistency-preserving complex edit operations across model boundaries. We show that edit and repair rules can be derived from short-cut rules. As proof of concept, we implemented the construction and application of short-cut edit and repair rules in eMoflon. Our evaluation shows that short-cut -rule-based repair processes have considerably decreased data loss and improved runtime compared to former model synchronization processes in eMoflon.

Consistency management is an important task in the context of Domain-Specific Language (DSL) development. It involves operations such as program (model) transformation, synchronisation, integration, and consistency checking, which are all tasks required to enable concurrent engineering using multiple DSLs. Even though consistency management is a well-researched topic, existing approaches either implement a fixed strategy for each consistency management operation, or do not scale for large models. This has been criticised in the literature, as practical applications require not only reasonable scalability with model size, but also unite multiple consistency management tasks within one tool. To raise the adaptability of such a tool to an appropriate level, a uniform way of performing these tasks is a desirable goal. In this paper, we propose an approach to consistency management that leverages a synergetic combination of Triple Graph Grammars and Integer Linear Programming. By modelling consistency management as an optimisation problem with a configurable objective function, we are able to uniformly address a wide range of consistency management operations. We show that our approach scales acceptably in practice, while still guaranteeing that a consistent solution is found if and only if one exists.

Countless novel approaches to communication protocols, overlay networks, and distributed middleware are published every year, yet the adoption of such novel findings in the global Internet landscape progresses at a slow pace. Many of such new communication mechanisms excel (only) under specific deployment conditions, while user mobility and application usage patterns lead to dynamic operation conditions. This mismatch is one reason that makes a wide deployment of new specialized mechanisms particularly hard as observed, for example, for multipath transport protocol extensions until the emergence of multipath transmission control protocol (TCP). This paper formalizes the concept of Transitions, i.e., a method to instrumentalize adaptivity at runtime in communication systems. It allows to exchange communication mechanisms in a running system to optimize the communication quality. In the following, we describe the building blocks required to: 1) capture the features and relations within a communication system and 2) express and optimize the decision making process in such a system. We show how this concept maps intuitively to the Internet model which makes a protocol-independent deployment of applications feasible in the future Internet.

Clafer combines UML-like class- and meta-modeling with feature-oriented variability-modeling and first-order logic constraints. The considerable expressiveness of Clafer mainly stems from its built-in variability constructs, multiplicity annotations and recursive model structures which yield a potentially unbounded number of valid model instances. As a result, automated reasoning about semantic properties like model consistency (i.e., existence of valid model instances) and anomalies (e.g., false cardinality bounds) is very challenging. Recent analysis techniques are inherently incomplete as they impose an a-priori finite search space with either manually or heuristically adjusted bounds. In this paper, we present a novel approach for automated search-space restriction for a considerably rich, yet decidable fragment of the Clafer language that guarantees sound and complete detection results for a wide range of semantic anomalies. Our approach employs principles from mathematical programming by encoding Clafer models as Mixed Integer Linear Programs (MILP). Our experimental evaluation shows remarkable improvements of runtime efficiency as well as effectiveness of anomaly detection as compared to existing techniques.

Today's adaptive software systems (i) are often highly configurable product lines, exhibiting hundreds of potentially conflicting configuration options; (ii) are context dependent, forcing the system to reconfigure to ever-changing contextual situations at runtime; (iii) need to fulfill context-dependent performance goals by optimizing measurable nonfunctional properties. Usually, a large number of consistent configurations exists for a given context, and each consistent configuration may perform differently with regard to the current context and performance goal(s). Therefore, it is crucial to consider nonfunctional properties for identifying an appropriate configuration. Existing black-box approaches for estimating the performance of configurations provide no means for determining context-sensitive reconfiguration decisions at runtime that are both consistent and optimal, and hardly allow for combining multiple context-dependent quality goals. In this paper, we propose a comprehensive approach based on Dynamic Software Product Lines (DSPL) for obtaining consistent and optimal reconfiguration decisions. We use training data obtained from simulations to learn performance-influence models. A novel integrated runtime representation captures both consistency properties and the learned performance-influence models. Our solution provides the flexibility to define multiple context-dependent performance goals. We have implemented our approach as a standalone component. Based on an Internet-of-Things case study using adaptive wireless sensor networks, we evaluate our approach with regard to effectiveness, efficiency, and applicability.

Numerous topology control algorithms for wireless sensor networks exist. Typically, these algorithms optimize general network metrics like the transmission range of sensors. Being of general nature, they suit application-specific requirements insufficiently; e.g., application-specific communication patterns may favor links that the general algorithm will remove.

Mobile devices like smartphones are getting increasingly important in our daily lifes. They are used in various environments and have to dynamically adapt themselves accordingly in order to provide an optimal runtime behavior. Naturally, adapting to continuously changing environmental conditions is a challenging task because mobile devices are always limited in their resources and have to adapt in real-time. In this paper, we introduce an approach that enables resource limited devices to adapt to changing conditions using dynamic software product lines techniques. Therefore, feature models are reduced to a specific hardware context before installing the adaptive mobile application on the device. This reduces the amount of possible configurations that are compatible with the device and, thereby, minimizes the costs and the duration of an adaptation during runtime.

Many software projects are developed by globally distributed teams. The nature of the peer-to-peer paradigm fits to such an application scenario. However, existing tools to support developer require a central instance, like it is the case in version control, which is crucial for software development. This paper address the challenges version control faces in a purely peer-to-peer environment and presents a peer-to-peer based version control system we developed. We will evolve this basic approach, adding more features like change-set version control.

Nowadays, a typical software development process involves many developers which participate in the development process by using a wide variety of development tools. As a consequence, the data representing the project as a whole is distributed over different development tools. For the purpose of consistency, maintainability, and traceability it is an essential task to be aware of the relationships between semantic equivalent data in different tool repositories. The real-time systems Lab at the Technische Universitat Darmstadt performs research in the area of tool and metamodel integration to provide solutions to overcome this gap. In this demonstration we present the metamodeling framework MOFLON that addresses these issues by bringing together the latest OMG standards with graph transformations and triple graph grammars. Using MOFLON, developers can generate code for specific tools needed to perform analysis and transformation on one development tool or to incrementally integrate data of different modeling tools.

In this paper, Wiki technology proved to be an appropriate tool for sharing global knowledge, as it provides an easy way to contribute and consume information. The way wikis are used, e.g. consuming and contributing information, naturally matches the peer-to-peer (p2p) paradigm, which inherently follows the structure of its distributed users. Compared to client-server solutions, it has significantly lower maintenance costs, no bottleneck or single point of failure, and resources are used and offered by all users. We propose a purely p2p based wiki engine (PIKI) with the focus on concurrent editing, version control, and decentralized full-text search (in a structured overlay). Further we elaborate tracking semantic information between linked articles through different versions, where a typed link itself holds meta-data about the linked files.

In the automotive industry, the model driven development of software, today considered as the standard paradigm, is generally based on the use of the tool MATLAB Simulink/Stateflow. To increase the quality, the reliability, and the efficiency of the models and the generated code, checking and elimination of detected guideline violations defined in huge catalogues has become an essential task in the development process. It represents such a tremendous amount of boring work that it must necessarily be automated. In the past we have shown that graph transformation tools like Fujaba/MOFLON allow for the specification of single modeling guidelines on a very high level of abstraction and that guideline checking tools can be generated from these specifications easily. Unfortunately, graph transformation languages do not offer appropriate concepts for reuse of specification fragments - a MUST, when we deal with hundreds of guidelines. As a consequence we present an extension of MOFLON that supports the definition of generic rewrite rules and combines them with the reflective programming mechanisms of Java and the model repository interface standard JMI.

Current rule-based model transformation approaches as the Query / View / Transformation (QVT) standard or Triple Graph Grammars (TGGs) disregard means for structuring model transformation specifications. As a result large scale model transformation specifications are hard to understand and to maintain. Furthermore, these specifications cannot utilize reusing mechanisms which would reduce the size of the specifications and improve their readability. In this paper we discuss how to transfer means for structuring huge metamodels and models as provided by common modeling languages to the world of model transformation languages. We focus on generalization issues as well as on package dependencies. As a result we come up with an extension to our TGG approach that enables the user to specify structured bidirectional model transformations in a declarative way.

Model transformation (MT) is a key technology in the model-driven development approach of software engineering that provides automated means to capture the evolution of models and mappings between modeling languages. The pattern and rule-based paradigm of graph transformation is considered a very popular approach for specifying such model transformations. While the expressiveness of different MT specification techniques is frequently compared on well-known transformation problems (e.g. UML-to-XMI, or UML-to-EJB mappings), no such benchmarks exist currently for comparing the performance of different model transformation tools. In the paper, we propose a systematic method for quantitative benchmarking in order to assess the performance of graph transformation tools. Typical features of the graph transformation paradigm and various optimization strategies exploited in different toots are identified and categorized. Moreover, the performance of several popular graph transformation tools is measured and compared on a well-known distributed mutual exclusion problem.

Object-oriented modeling languages, tools, and methods are attracting the interest of embedded (real-time) system developers. This is especially true if embedded (real-time) system software has to cooperate with interactive multimedia software, as is becoming the case in automotive systems. It is still an open question whether and how the standard OO modeling language UML and its accompanying tools have to be adapted to the regarded application domain. This paper evaluates the development of a rapid prototype for an air conditioning controller with the popular CASE tool Rational Rose/RT(R). We point out weaknesses of the presented solution and propose an extension to Rose/RT(R), which overcomes the weaknesses by combining Rose/RT's UML dialect with data flow equations.

Designing a software system's architecture properly is one of the most important tasks of any software engineering project. Nevertheless there exists no common definition of the term "software architecture" and no standard software architecture description language (ADL). The paper discusses whether the standard OO modeling language UML is a standard ADL, explains some deficiencies if used for this purpose, and makes a proposal of how to eliminate these deficiencies. The proposal is based on the widely accepted idea that elements of the component based OO modeling language, ROOM, should be integrated with UML. It explains why the idea of merging static structure diagrams of ROOM with behaviour-describing collaboration diagrams of UML is not sufficient and presents an additional approach for the integration problem.

Many software applications require the construction and manipulation of graphs. In standard programming languages, this is accomplished using low-level mechanisms such as pointer manipulation or array indexing. In contrast, graph productions are a convenient high-level visual notation for coding graph modifications. A graph production replaces one subgraph by another subgraph. Graph productions can define a graph grammar and graph language, or can directly transform an input graph into an output graph. Graph transformation has been applied in many areas, including the definition of visual languages and their tools, the construction of software development environments, the definition of constraint programming algorithms, the modeling of distributed systems, and the construction of neural networks. One application is presented in detail: the interpretation of mathematical notation in scanned document images. The graph models the set of mathematical symbols, and their spatial and logical relationships. This graph is transformed by productions written in the PROGRES language. Copyright © 1999 John Wiley & Sons, Ltd.

No abstract available.

In this paper, we introduce a new concept for the structured development of rule-based graph transformation systems that allows to build up large systems from small pieces in a modular way. The concept is called nested graph transformation unit and consists of a network of local graph transformation units. While each local unit provides a set of rules and control conditions (including input and output descriptions), the net reflects the import structure of the system where each local unit can use its direct neighbours without any restrictions. In particular, the import structure may contain cycles. It is shown that nested graph transformation units have a reasonable operational semantics by iterating the so-called interleaving operator, which interleaves local rule applications with calls of used units according to the local control conditions. It turns out that the iterated interleaving semantics is the smallest fixed point of the interleaving operator provided that the involved control conditions are continuous in a certain sense.

This paper presents a new logic based framework for the formal treatment of graph rewriting systems as special cases of programmed rewriting systems for arbitrary relational structures. Considering its expressive power, the new formalism surpasses al

The conceptual modeling approach of the IPSEN (Integrated Project Support Environment) project for building highly integrated environments is based on using attributed graphs to model and implement arbitrary object structures, in particular all kinds of software documents and their relationships. A language based on graph grammars, called PROGRESS (PROgrammed Graph REwriting SyStems), and a suitable method for the application of this language, called graph grammar engineering, have been developed over the last ten years. This language and method are being extensively used for specifying the complex graph structures of internal document representations as well as for specifying the functionality of all tools (editors, browsers, analyzers, debuggers) working on these internal rpresentations. This paper explains the language and the method for applying the language based on a pragmatic nontrivial example of a software production process and its corresponding documents. In particular, it is shown why and how a graph grammar-based strongly typed language is perfectly suitable to formally specify highly integrated software tools. In addition, it is shown that the implementation of these tools (i.e., an environment composed of these tools) is systematically being derived from the formal specifications.