Verification of Graph-based Model Transformations Using Alloy

Abstract

Model transformations are fundamental in model driven development. Thus, verification of model transformations is indispensable to ensure the quality and the reliability of transformation results. In this paper we focus on graph-based model transformation systems using the double-pushout (DPO) approach and study their correctness w.r.t. conformance. It means that, given a transformation system and a valid source model, any applicable sequences of model transformations will produce a valid target model.A procedure is presented to verify firstly if a model transformation system is correct w.r.t. conformance by checking the Direct Condition, i.e., each direct model transformation produces a valid target model from a valid source model. Then, for systems not satisfying the direct condition, it checks theSequential Condition, i.e., if a direct model transformation t produces an invalid target model from a valid source model, then there exists a sequence of direct model transformations succeeding the transformation tthat produces a valid target model. The satisfiability of the latter condition cannot always promise correctness, but it ensures that, from every valid source model, a valid target model can be produced. The procedure uses a bounded verification approach based on First Order Logic (FOL). The approach encodes a transformation system and the two conditions into a relational logic specification in Alloy. Then the specification is inspected by the Alloy Analyzer to check if the system satisfies the conditions. When it violates the conditions, the analyzer presents a counterexample, that may be used to redesign the system. An example is given to illustrate the bounded verification approach in the Diagram Predicate Framework (DPF).