Formal Analysis of Model Transformations Based on Triple Graph Grammars

in Mathematical Structures in Computer Science (2014), 24(4-08), 1-57

Triple graph grammars (TGGs) are a well-established concept for the specification and execution of bidirectional model transformations within model driven software engineering. Their main advantage is an ... [more ▼]

Triple graph grammars (TGGs) are a well-established concept for the specification and execution of bidirectional model transformations within model driven software engineering. Their main advantage is an automatic generation of operational rules for forward and backward model transformations, which simplifies specification and enhances usability as well as consistency. In this paper we present several important results for analysing model transformations based on the formal categorical foundation of TGGs within the framework of attributed graph transformation systems. Our first main result shows that the crucial properties of correctness and completeness are ensured for model transformations. In order to analyse functional behaviour, we generate a new kind of operational rule, called a forward translation rule. We apply existing results for the analysis of local confluence for attributed graph transformation systems. As additional main results, we provide sufficient criteria for the verification of functional behaviour as well as a necessary and sufficient condition for strong functional behaviour. In fact, these conditions imply polynomial complexity for the execution of the model transformation. We also analyse information and complete information preservation of model transformations, that is, whether a source model can be reconstructed (uniquely) from the target model computed by the model transformation. We illustrate the results for the well-known model transformation example from class diagrams to relational database models. [less ▲]

Triple Graph Grammars in the Large for Translating Satellite Procedures

in Theory and Practice of Model Transformations (2014, July)

Software translation is a challenging task. Several requirements are important – including automation of the execution, maintainability of the translation patterns, and, most importantly, reliability ... [more ▼]

Software translation is a challenging task. Several requirements are important – including automation of the execution, maintainability of the translation patterns, and, most importantly, reliability concerning the correctness of the translation. Triple graph grammars (TGGs) have shown to be an intuitive, well-defined technique for model translation. In this paper, we leverage TGGs for industry scale software translations. The approach is implemented using the Eclipse-based graph transformation tool Henshin and has been successfully applied in a large industrial project with the satellite operator SES on the translation of satellite control procedures. We evaluate the approach regarding requirements from the project and performance on a complete set of procedures of one satellite. [less ▲]

Correctness of source code extension for fault detection in openflow based networks

Report (2014)

Software Defined Networks using OpenFlow have to provide a re- liable way to detect network faults and attacks. This technical report shows a formal analysis of correctness for an automated code extension ... [more ▼]

Software Defined Networks using OpenFlow have to provide a re- liable way to detect network faults and attacks. This technical report shows a formal analysis of correctness for an automated code extension technique used to extend OpenFlow networks with a logging mecha- nism that is used for the detection of faults and attacks. As presented in a companion paper, we applied the code extension techniques for a framework that can extend controller programs transparently, making possible on-line fault management, debugging as well as off-line and forensic analysis. [less ▲]

Solving the FIXML2Code-case Study with HenshinTGG

in Rose, Louis M.; Krause, Christian; Horn, Tassilo (Eds.) Proceedings of the 7th Transformation Tool Contest - part of the Software Technologies: Applications and Foundations (STAF 2014) federation of conferences (2014)

Triple graph grammars (TGGs) provide a formal framework for bidirectional model transformations. As in practice, TGGs are primarily used in pure model-to-model transformation scenarios, tools for text-to ... [more ▼]

Triple graph grammars (TGGs) provide a formal framework for bidirectional model transformations. As in practice, TGGs are primarily used in pure model-to-model transformation scenarios, tools for text-to-model and model-to-text transformations make them also applicable in text-to-text transformation contexts. This paper presents a solution for the text-to-text transformation case study of the Transformation Tool Contest 2014 on translating FIXML (an XML notation for financial transactions) to source code written in Java, C# or C++. The solution uses the HenshinTGG tool for specifying and executing model-to-model transformations based on the formal concept of TGGs as well as the Xtext tool for parsing XML content to yield its abstract syntax tree (text-to-model transformation) and serialising abstract syntax trees to source code (model-to-text transformation). The approach is evaluated concerning a given set of criteria. [less ▲]

Model synchronization based on triple graph grammars: correctness, completeness and invertibility

in Software and Systems Modeling (2013)

Triple graph grammars (TGGs) have been used successfully to analyze correctness and completeness of bidirectional model transformations, but a corresponding formal approach to model synchronization has ... [more ▼]

Triple graph grammars (TGGs) have been used successfully to analyze correctness and completeness of bidirectional model transformations, but a corresponding formal approach to model synchronization has been missing. This paper closes this gap by providing a formal synchronization framework with bidirectional update propagation operations. They are generated from a given TGG, which specifies the language of all consistently integrated source and target models. As our main result, we show that the generated synchronization framework is correct and complete, provided that forward and backward propagation operations are deterministic. Correctness essentially means that the propagation operations preserve and establish consistency while completeness ensures that the operations are defined for all possible inputs. Moreover, we analyze the conditions under which the operations are inverse to each other. All constructions and results are motivated and explained by a running example, which leads to a case study, using concrete visual syntax and abstract syntax notation based on typed attributed graphs. [less ▲]

Transformation Systems with Incremental Negative Application Conditions

in Recent Trends in Algebraic Development Techniques (2013)

In several application areas, Graph Transformation Systems (GTSs) are equipped with Negative Application Conditions (NACs) that specify “forbidden contexts”, in which the rules shall not be applied. The ... [more ▼]

In several application areas, Graph Transformation Systems (GTSs) are equipped with Negative Application Conditions (NACs) that specify “forbidden contexts”, in which the rules shall not be applied. The extension to NACs, however, introduces inhibiting effects among transformation steps that are not local in general, causing a severe problem for a concurrent semantics. In fact, the relation of sequential independence among derivation steps is not invariant under switching, as we illustrate with an example. We first show that this problem disappears if the NACs are restricted to beincremental. Next we present an algorithm that transforms a GTS with arbitrary NACs into one with incremental NACs only, able to simulate the original GTS. We also show that the two systems are actually equivalent, under certain assumptions on NACs. [less ▲]

Towards Bidirectional Engineering of Satellite Control Procedures Using Triple Graph Grammars

in Jacquet, Christophe; Balasubramanian, Daniel; Jones, Edward (Eds.) et al Proc. Int. Workshop on Multi-Paradigm Modeling 2013 (MPM'13) (2013)

The development and maintenance of satellite control software are very complex, mission-critical and cost-intensive tasks that require expertise from different domains. In order to adequately address ... [more ▼]

The development and maintenance of satellite control software are very complex, mission-critical and cost-intensive tasks that require expertise from different domains. In order to adequately address these challenges, we propose to use visual views of the software to provide concise abstractions of the system from different perspectives. This paper introduces a visual language for process flow models of satellite control procedures that we developed in cooperation with the industrial partner SES for the satellite control language SPELL. Furthermore, we present a general and formal bidirectional engineering approach for automatically translating satellite control procedures into corresponding process flow visualisations. The bidirectional engineering framework is supported by a visual editor based on Eclipse GMF, the transformation tool HenshinTGG, and additional extensions to meet requirements set up by the specific application area of satellite control languages. [less ▲]

On Propagation-Based Concurrent Model Synchronization

in Electronic Communications of the EASST (2013), 57

Model transformations based on triple graph grammars (TGGs) have been applied in several practical case studies and they convince by their intuitive and descriptive way of specifying bidirectional model ... [more ▼]

Model transformations based on triple graph grammars (TGGs) have been applied in several practical case studies and they convince by their intuitive and descriptive way of specifying bidirectional model transformations. Moreover, fundamental properties have been extensively studied including syntactical correctness, completeness, termination and functional behaviour. But up to now, it is an open problem how domain specific properties that are valid for a source model can be preserved along model transformations such that the transformed properties are valid for the derived target model. In this paper, we analyse in the framework of TGGs how to propagate constraints from a source model to an integrated and target model such that, whenever the source model satisfies the source constraint also the integrated and target model satisfy the corresponding integrated and target constraint. In our main new results we show under which conditions this is possible. The case study shows how this result is successfully applied for the propagation of security constraints in enterprise modelling between business and IT models. [less ▲]

Satisfaction, Restriction and Amalgamation of Constraints in the Framework of M-Adhesive Categories

in Electronic Proceedings in Theoretical Computer Science (2012), 93

Application conditions for rules and constraints for graphs are well-known in the theory of graph transformation and have been extended already to M-adhesive transformation systems. According to the ... [more ▼]

Application conditions for rules and constraints for graphs are well-known in the theory of graph transformation and have been extended already to M-adhesive transformation systems. According to the literature we distinguish between two kinds of satisfaction for constraints, called general and initial satisfaction of constraints, where initial satisfaction is defined for constraints over an initial object of the base category. Unfortunately, the standard definition of general satisfaction is not compatible with negation in contrast to initial satisfaction. Based on the well-known restriction of objects along type morphisms, we study in this paper restriction and amalgamation of application conditions and constraints together with their solutions. In our main result, we show compatibility of initial satisfaction for positive constraints with restriction and amalgamation, while general satisfaction fails in general. Our main result is based on the compatibility of composition via pushouts with restriction, which is ensured by the horizontal van Kampen property in addition to the vertical one that is generally satisfied in M-adhesive categories [less ▲]

Parallelism and Concurrency of Stochastic Graph Transformations

in Graph Transformations (2012), 7562

Graph transformation systems (GTS) have been proposed for high-level stochastic modelling of dynamic systems and networks. The resulting systems can be described as semi-Markov processes with graphs as ... [more ▼]

Graph transformation systems (GTS) have been proposed for high-level stochastic modelling of dynamic systems and networks. The resulting systems can be described as semi-Markov processes with graphs as states and transformations as transitions. The operational semantics of such processes can be explored through stochastic simulation. In this paper, we develop the basic theory of stochastic graph transformation, including generalisations of the Parallelism and Concurrency Theorems and their application to computing the completion time of a concurrent process. [less ▲]