Inconsistency Detection in Distributed Model Driven Software Engineering Environments ∗ Alix Mougenot Xavier Blanc Marie-Pierre Gervais LIP6, UPMC - Paris LIP6, UPMC - Paris LIP6, UPMC - Paris Universitas, Paris France Universitas, Paris France Universitas, Paris France alix.mougenot@lip6.fr xavier.blanc@lip6.fr marie- pierre.gervais@lip6.fr ABSTRACT Each software designer only partially contributes to the global Model driven development uses more and more complemen- design. Only some of the global design’s model elements are tary models. Indeed, large-scale industrial systems are cur- interesting to each software designer. In [5], authors de- rently developed by hundreds of developers working on hun- fine the notion of viewpoint for addressing this concern. A dreds of models by different distributed teams. In such a viewpoint is defined by the knowledge, responsibilities and context, model inconsistency detection is gaining a lot of at- understandings of some part of the system. Each software tention as the overlap between all these models, which are designer has his own view of the global system to design. For often maintained by different persons, are a common source work efficiency reasons each view contains only the model el- of inconsistencies. This paper proposes a method to detect ements of the global design the designer is concerned with. inconsistencies when models are scattered on different edit- It should be noted that views do not provide a partitioning ing sites using partial replication. The method provides a of the global design as they have elements in common. way to check the consistency of a single view against the ones that are related to it regarding consistency. It relies Views allow different software designers to concurrently ac- on Praxis, an operation based representation of models, to cess elements of the global design. Since these concurrent determine what information needs to be collected for con- modifications are done from different point-of-views of the sistency checking and the DPraxis protocol to find where it global design, inconsistencies arise between and within the can be. views. View Consistency is then a key matter in software engineering. In order to control the consistency of global de- sign, consistency rules are defined and checked against the Categories and Subject Descriptors global design. When an inconsistency is detected, it is re- D.2 [Software Engineering]: ported and logged for further resolving. Consistency checks should be regularly done in order to make sure that the sep- Keywords aration of concerns granted by the use of views does not Consistency, Model, View. introduce inconsistencies due to the distribution of the in- formation. Detection of inconsistencies between views is a well known research domain (the interested reader will find 1. INTRODUCTION a precise description in [14, 4]). Many approaches have been Model driven development uses more and more complemen- proposed in this domain [7, 5, 6, 3, 10, 8, 1] and many tools tary models. Indeed, large-scale industrial systems are cur- are available for model consistency validation (Object Con- rently developed by hundreds of developers working on hun- straint Language checkers, Eclipse Model Framework vali- dreds of models by different distributed teams [13]. In such dation tools, Epsilon Validation Language, Praxis . . . ), but a context, model inconsistency detection is gaining a lot of except [10] they have all been proposed on single machine attention as the overlap between all these models, which architectures and don’t cover how to perform inconsistency are often maintained by different persons and from different detection in a distributed environment. The actual chal- perspectives, are a common source of inconsistency. lenges of modeling concerns huge systems that are modeled ∗This work was founded by the French Weapon Agency by distant teams, in a distributed fashion, assuming possible disconnections and delays between the designing sites, is not (DGA) and the MOVIDA ANR Project answered by the state of the art. A designer can produce, modify or delete model elements that belong to his view. During the execution of the de- velopment process, designers will collaborate. Hence, they will need to access model elements on other sites. Once a designer has accessed model elements from any other view, these model elements can be incorporated to his view as he now relies on it. Also, a designer’s view always remains par- tial for sake of the separation of concerns. Respecting the 2 separation of concern principle inevitably leads to inconsis- – remRef erence(me, r, met) removes the target model ele- tency between the different views. Inconsistencies need to ment met of the reference r for the model element me. be detected as soon as possible to avoid project failures. In this article, we address the problem of inconsistency detec- tion when the views are distributed. More precisely, we want to tackle with this problem when each designer’s site only holds the designer’s view. The focus of this work is then to provide a method for detecting single-view inconsistencies, that are all the inconsistencies related to a particular view. In other words, we want to provide a method that only de- Figure 1: Sample UML model tect inconsistencies that the view’s designer can understand and resolve. 1 create(C1,class) 2 addProperty(C1,name, ’TOTO’) We identified two problems that need to be tackled regard- 3 addProperty(C1,visibility, ’private’) ing single-view inconsistency detection. The first one is to 4 addProperty(C1,isabstract, ’false’) be able to identify the needed information from other views. 5 create(P1,property) This point is handled in section 2. The second lock con- 6 addProperty(P1, name, ’Alice’) cerns the problem of finding in which view the interesting 7 addProperty(P1, visibility, ’public’) information is, which is dealt with in section 3. 8 addReference(C1, attribute, P1) 9 addReference(C1, ownedElement, P1) 10 addReference(P1, class, C1) 2. WHAT TO GET 11 addReference(P1, namespace, C1) If no information is available about what kind of data is relevant to each inconsistency rule, the consistency check of Figure 2: Praxis illustrative operation sequence a single view will need to download the entirety of the related views; and possibly the entirety of the views related to the related views, which can quickly end-up in downloading the Figure 2 is a simplified Praxis construction sequence σc entire design. The gathering of such a wasteful amount of used to produce the model of Figure 1 that consists of a data can be avoided using filters that can be deduced from private UML class named T OT O which owns a public at- the consistency rules’ code. tribute Alice. The diagram comes from the Eclipse UML2 Tools Editor that does not display visibilities. In this section we briefly revisit the three elements from our previous work [1, 9, 2] on which we rely to determine which parts of a model are useful for checking a particular 2.2 Inconsistency detection rules rule. These three elements are the Praxis model construction In Praxis, an inconsistency rule is a logic formula over the that is the model representation used in our approach, the sequence of model editing operations (interested readers can Praxis inconsistency rule formalism that is used for the rep- refer to [1] for a more detailed description of the rules’ for- resentation of inconsistency rules and the consistency impact malism). In these rules the following predicates are used to matrix which is the data-structure used by the single-view access model editing operations within a sequence: inconsistency checker to determine the needed information for each inconsistency rule. – lastCreate(id, M etaClass) is used to fetch within the se- quence, the operations that create model elements. The ’last’ prefix of this logic constructor means that the element 2.1 Praxis Model Construction is never deleted further in the sequence. We propose a formalism to represent models as sequences of unitary editing operations [1, 9]. This formalism, named – lastAddRef erence(id, M etaRef erence, T arget) is used to Praxis, is used to represent any model as well as any set fetch within the sequence, the operations that did assign of model changes. It represents models using six unitary to a source model element (id), one value (T arget) for the operations that are revisited here: reference (MetaReference). The ’last’ prefix of this logic constructor means that this reference value is not removed – create(me, mc) creates a model element me instance of further in the sequence (with the remRef erence or delete the meta-class mc. operation). – delete(me) deletes the model element me. A deleted ele- – lastAddP roperty(id, M etaP roperty, V alue) is used to fetch ment does not have properties, nor references. within the sequence, the operations that did assign to a source model element (id), one value (V alue) for its prop- – addP roperty(me, p, v) assigns the value v to the property erty MetaProperty. The ’last’ prefix of this logic constructor p of the model element me. means that the value is not removed further in the sequence. – remP roperty(me, p, v) removes the value v of the property Let us illustrate inconsistency rules with two examples that p for the model element me. are defined in the class diagram part of the UML 2.1 speci- fication [11]: – addRef erence(me, r, met) assigns a target model element met to the reference r for the model element me. The Ownership rule specifies that: An element may not 3 directly or indirectly own itself. change a reference for the same meta-reference, (3) they change values for the same meta-property, (4) they delete The Visibility rule specifies that: An element that has a model element. Thanks to such a partition, the number a public visibility can only be in a namespace with a public of equivalence classes is bound to the number of the meta- visibility. classes, plus the number of the references, plus the number of properties, plus one (the equivalent class corresponding to These two rules cover two typical aspects of inconsistency the deletion).The impact matrix is automatically derived detection. The rule Ownership (figure 4), specifies that con- from the metamodel and the inconsistency rules [2]. tainments should not cycle, which is quite complex to check because containments relationships are spread over the en- Equivalence class OwnedElement Visibility tire design. The rule Visibility (figure 3) on the contrary, CClass false false is less complex, and has its locality restricted to each names- CAttribute false false pace. SPN ame false false SPV isibility false true SROwnedElement true false V isibility ⇐⇒ {∃ M e, N 1 · SRClass false false lastAddP roperty(M e, visibility, “public00 ) ∧ SRAttribute false false lastAddRef erence(M e, namespace, N 1) ∧ SRN amespace false true Delete false false lastAddP roperty(N 1, visibility, V ) ∧ not(V = “public00 ). Figure 3: Visibility rule for Praxis Figure 5: Extract of the Impact matrix for the illustrative inconsistency rules (C=Create, Ownership ⇐⇒ {∃ X · Owns(X, X)} With SP=PropertyChange, SR=ReferenceChange) Owns(A, B) ⇐⇒ { lastAddRef erence(A, ownedElement, B) ∨ {∃ Y · lastAddRef erence(A, ownedElement, Y ) ∧ Owns(Y, B)}} An extract of the impact matrix for the illustrative incon- sistency rules we previously introduced is shown in figure 5. Figure 4: Ownership rule for Praxis The extract shows nine equivalence classes from the meta- model partition, of which only three have an effect on an inconsistency rule. In this matrix, regarding the Visibil- To illustrate Praxis rules, we present the Praxis version of ity inconsistency rule, the operation classes that may have rule Visibility and Ownership in figure 3 and 4. The Vis- an impact on this rule are SPV isibility and SRN amesapce . ibility rule has two variables (M e, N 1) that both corre- The operations that may have an impact on this rule are spond to identifiers of UML elements. This rule matches any those that modify a reference to the namespace of an ele- Praxis model construction sequence that results in a model ment, which all belong to the operation class SRN amespace , containing an element with a public visibility for which its and those that modify the visibility of an element, which namespace is not public. The sequence presented in Fig- all belong to SPV isibility . Note that the Delete equivalence ure 2 corresponds to an inconsistent model regarding this class has no impact because deletion occurs only for model rule. Launching an inconsistency detection on this sequence elements that are not referenced and do not reference other would detect the inconsistency Visibility(P1,C1). model elements. 2.3 Consistency Impact Matrix Our method for single-view consistency detection uses the The effect that editing operations may have on inconsistency impact matrix that was originally intended for incremental rules can be described in a two dimensional boolean matrix inconsistency detection [2]. For checking a particular ruleset, we called impact matrix [2]. This matrix was designed for only operations members of the operation classes that have incremental inconsistency detection. Its rows correspond to an impact on an inconsistency rules are relevant. Knowing Praxis operations and its columns to the inconsistency rules. which operation classes are interesting reduces the amount A ’true’ in a cell of such matrix means that the correspond- of data that needs to be considered to the relevant part of ing editing operation may have an effect on the correspond- the views. ing inconsistency rule. When an editing operation appears in a model change (a model change is also a sequence of uni- tary operations), the inconsistency rules marked as ’true’ in 3. WHERE TO FETCH the matrix for these operations have to be re-checked. In Having the information about what classes of operations are our context this matrix can be used to know which informa- useful for checking a particular rule is not enough in prac- tion needs to be downloaded from the other views to check tice. It does not tackle the problem of gathering data that a particular rule. is actually related to the view for which we want to check the consistency. Indeed, the interesting information is scat- tered among the views, and not all of the information that As there is an infinity of possible editing operations (infinity belongs to the identified operation classes is interesting to of possible parameter’s values), we group them in equiva- the view’s designer. In this section we describe how we use lence classes to bound the matrix’s size. We defined four group of interest tables from peer-to-peer model editing en- rules to partition the editing operations for any metamodel. gines to identify where in the net of views is the information Two editing operations are equivalent if (1) they create a to consider for inconsistency detection. model element instance of the same meta-class, (2) they 4 3.1 DPraxis Partial Replication Model want to continue its work in an other view. They corre- Partial replications allows each model designer to restrict spond to elements for which the local view only has a partial his workspace to its strict minimum: his view. The over- knowledge and where it is necessary to jump to other views laps between the views are maintained up-to-date thanks to to complete this knowledge. Inconsistency rules navigate a complex background update protocol. We defined such through the model thanks to references, which can point to a protocol, named DPraxis, for distributed model editing other views elements that are not replicated locally. The tools [9]. DPraxis is a peer-to-peer fully distributed model first step of single view inconsistency detection is then to update protocol that is designed to maintain the related find these local elements that may point to model elements views of a model up-to-date without having to replicate the that are not known locally, and may be the source of incon- entirety of its content in each designer’s workspace. In this sistencies. section we revisit the use of this protocol, which is used by the method for single-view inconsistency detection. Definition 1. Jump Point: An inconsistency rule’s jump point is a model element which is the source (res. the target) In distributed systems using replication, replicated elements of a reference that points to an element outside of the local are called replicas [12]. A replica is accessed in the same way view and that can be navigated by the inconsistency rule. as a regular element, but it can be modified by the propaga- tion of modifications issued from other sites. The replication is handled thanks to interest groups that are used to know In Praxis, references are accessed using the logical predicate which sites are interested in which information. Depending lastAddReference(source, reference, target). The Im- on the replication protocol and the data that needs to be pact matrix presented previously can be used to know which replicated, the size and the nature of the replication unit references can be crossed by an inconsistency rules. These can vary. An interest group links one replication unit to the references correspond to true in the matrix for operation sites that have it. classes of type SRref erence . For instance the rule V isibility only navigates through relations of the class SRN amespace . In DPraxis, replicas are maintained up-to-date thanks to in- DPraxis uses the model element as the replication unit. Con- terest group tables that can be used to know which elements sequently, views contain replicas for the parts that overlap are replicated, and where. with at least one other view, and model elements that are proper to the view. The use of the model element as the replication unit allows to fine tune the parts of the model a In practice we determine the jump points following this pro- designer want to import in his view. As DPraxis does not cedure: allow dangling links, reference between elements are shared between views only if both the source and the target of a reference are in the site’s view. This allows to choose the 1. Determine the references that can be crossed by the perimeter of the view by not importing elements pointed by inconsistency rule by looking for true in the Impact unwanted references. Matrix for classes of operations that correspond to ref- erences. The DPraxis protocol maintains a table with routing infor- 2. Determine which elements are replicas using the group mation on each site to propagate changes to the interested of interest table. sites. Thanks to this table it is possible to know which ele- ments are replicas, and to know, for each replica, on which 3. Confront the two informations to find all the repli- site it is replicated. This two informations are exploited by cas for which there is a locally crossable reference. the single-view inconsistency detection method to contact These elements will be considered as the only inter- other views when checking consistency. esting Jump Points. 3.2 Single-view consistency detection The following method focuses on the use of partial repli- It is difficult in practice to determine all the possible Jump cation. Nevertheless, the method described here for single- Points using DPraxis because references in the view can only view inconsistency detection could be used in centralized target elements of the view — if a reference is interesting to architectures as well. We describe in this section how to one view, then its target has to be imported. Therefore, check one inconsistency rule for one view, plus the elements there can be references of replicas that are not known to the of other views that are related to the considered view re- local view. We chose to ignore such jump points because in garding the rule to check. DPraxis the user decides whether the target (res. source) of a replicated element is interesting or not. It is then reason- 3.2.1 Determining Jump Points able to hide inconsistencies for which the user clearly stated The intent of single view inconsistency detection is to simu- that the reference was not relevant to him/her. We only late an inconsistency check where the detection engine can consider as a jump point elements for which there is at least jump from the original view to the related ones. To achieve one reference of the considered type locally. Nevertheless this goal we propose to begin with the identification of what the Jump points we ignore could be capture by looking out we call Jump Points. A jump point is a replicated model el- in the meta-model if the replica’s type can admit crossable ement from which the inconsistency detection engine would references. 5 3.2.2 Simulating Jumps View One The next step of the single-view inconsistency method is to 1 create(P1,package) allow inconsistency rules to follow jump points’ references 2 addProperty(P1,name, ’A’) to other views. We chose to download data of other views 3 create(P2,package) locally for simulating the jumps. This choice allows to use a 4 addProperty(P2, name, ’B’) regular inconsistency detection engine to do the single-view 5 addReference(P1, ownedElement, P2) inconsistency detection. Not all the information from the 6 addReference(P2, namespace, P1) distant view is to be downloaded. First, only information View Two that is interesting to the considered rule matters, which is 3 create(P2,package) specified in the Impact matrix. Second, only elements that 4 addProperty(P2, name, ’B’) are linked to the jump point need to be downloaded. 7 create(P3,package) The gathering of the unitary actions for realizing the single- 8 addProperty(P3,name, ’C’) view inconsistency detection can be done this way: 9 addReference(P2, ownedElement, P3) 10 addReference(P3, namespace, P2) View Three 1. Determine Jump points following the previous proce- 1 create(P1,package) dure. 2 addProperty(P1,name, ’A’) 2. Contact all the sites that have a replica of a jump 7 create(P3,package) point for the considered rule. Ask them to send all 8 addProperty(P3,name, ’C’) the unitary operations that are interesting for this rule 11 addReference(P3, ownedElement, P1) plus the operations that are necessary to fulfill their 12 addReference(P1, namespace, P3) preconditions. Wait for the answer. Figure 6: Three distributed views 3. Contacted sites then recursively apply the two previous steps of the procedure as long as new jump points are discovered. Then they send back to the caller all the P1-> View One, View Three gathered data. P2-> View One, View Two P3-> View Two, View Three The implementation of the procedure is detailed in section Figure 7: Simplified routing table 4. At the end of this procedure the calling site has gath- ered all the information that is interesting to the rule from the other views, and that is linked to its jump points. An inconsistency detection on the view plus the gathered data • Request from View one to View two: All actions in implements a single-view inconsistency detection: It detects SROwnedElement regarding P 2, P 1, plus dependencies. the local inconsistencies, plus the inconsistencies that are – Identified operations: 9:addReference(P2, owned- due to the overlapping parts of the views. Element, P3). 3.3 Example – Dependencies: 7:create(P3,package). In this section we present an illustrative example of the – Recursive Call from View two to View three: P 3 single-view inconsistency detection. is identified as a new jumping point. Requesting all actions in SROwnedElement regarding P 1, P 2, P 3, In figure 6 is shown three sequences corresponding to three plus dependencies. different views, where each of the views is consistent, but ∗ Identified operation: 11:addReference(P3, together make a cycle for the ownedElement relationship. ownedElement, P1) The number correspond to a total ordering of the actions ∗ Dependencies: None. P3 and P1 are known that is granted by D-Praxis. to the caller. ∗ Recursive Call: None, no new jump point dis- Let us consider a single-view inconsistency detection for covered. View One regarding the Ownership inconsistency rule. – Returned operations: 7:create(P3,package); 9:ad- The first step is to determine the jump points: P 1 and P 2 dReference(P2, ownedElement, P3); 11:addRef- are replicas (they are in the routing table from figure 7). erence(P3, ownedElement, P1). From the Impact Matrix in figure 5 we can deduce that • Request from View one to View three is symmetric to this rule can only cross references from the operation class the previous one, it returns the same operations. SROwnedElement . There is a local OwnedElement reference in the view that both concerns P 1 and P 2, thus the jump points for this view and for the rule Ownership are P 1 and At the end of the procedure, the view one has gathered: P 2. 7 create(P3,package) 9 addReference(P2, ownedElement, P3) The simulation of the jump needs to contact View two con- 11 addReference(P3, ownedElement, P1) cerning P 2 and View three concerning P 1. The following requests are sent in order to gather the data without cycling Using both the local and the distant operations, the inconsis- indefinitely: tency detection engine will detect an inconsistency for the 6 rule Ownership, indeed P 1, P 2, P 3 are in a cycle for the The next step of this work is a quantitative evaluation of relation OwnedElement. The procedure only gathers the the method to asses its performances both empirically and minimal information that matters to the rule, and that has theoretically. a link to the local data. The designer of view one is now aware of the cycle problem and can contact the designers 7. REFERENCES responsible for the two other implicated views to resolve the [1] X. Blanc, A. Mougenot, I. Mounier, and T. Mens. problem. Detecting model inconsistency through operation-based model construction. In Robby, editor, 3.4 Limitations Proc. Int’l Conf. Software engineering (ICSE’08), The method described here is based on the fact that incon- volume 1, pages 511–520. ACM, 2008. sistency rules navigate through models using the relations [2] X. Blanc, A. Mougenot, I. Mounier, and T. Mens. between model elements. This condition does not hold in Incremental detection of model inconsistencies based general, for instance a rule that counts elements of a partic- on model operations. In Proceedings of the 21st ular type may not use references for the navigation. Rules International Conference on Advanced Information that do not use navigation must be checked by gathering all Systems, CAISE’09, pages 32–46. Springer, 2009. the interesting operations from all the other views. [3] A. Egyed. Instant consistency checking for UML. In Proceedings Int’l Conf. Software Engineering (ICSE 4. VALIDATION ’06), pages 381–390. ACM Press, 2006. We implemented the method in our inconsistency detection [4] M. Elaasar and L. Brian. An overview of UML tool 1 that runs on top of Eclipse. The implementation adds consistency management. Technical Report one optimization to the described procedure. We imple- SCE-04-18, August 2004. mented a hashing system to avoid to constantly download [5] A. C. W. Finkelstein et al. Inconsistency handling in the same operations over and over: A hash of the known multiperspective specifications. In IEEE Trans. Softw. operations for each operation class is sent prior to the pro- Eng., volume 20, pages 569–578. IEEE Press, 1994. cedure, if the hashes matches, the procedure does not con- [6] P. Fradet, D. Le Metayer, and M. Peiin. Consistency tinue. checking for multiple view software architectures. In Proc. Joint Conf. ESEC/FSE’99, volume 41, pages 410–428. Springer, September 1999. 5. RELATED WORK [7] D. Leblang and R. Chase Jr. Computer-aided software The naive method to tackle with distributed views consis- engineering in a distributed workstation environment. tency consists in downloading all the views on a central Proceedings of the first ACM SIGSOFT/SIGPLAN repository and then perform the inconsistency detection on software engineering symposium on Practical software the re-united global design [10]. This technique is accept- development environments, pages 104–112, 1984. able when the latency of the technique is not an issue, or [8] T. Mens et al. Detecting and resolving model when the consistency of the entire design needs to be assed. inconsistencies using transformation dependency Nevertheless, it does not scale to large designs regarding analysis. In Model Driven Engineering Languages and answer speed because: First, downloading all the views on Systems, volume 4199 of LNCS, pages 200–214. one central place is slow if the views are large. Second, Springer, October 2006. the merge of all the distant view into one big model is not easy. To address this problem this paper introduces the [9] A. Mougenot, X. Blanc, and M.-P. Gervais. D-praxis : notion of single-view inconsistency detection, which detects A peer-to-peer collaborative model editing framework. distributed inconsistencies in a light-weight fashion. In Distributed Applications and Interoperable Systems, 9th IFIP WG 6.1 International Conference, DAIS Unfortunately we could not find many research approaches 2009, Lisbon, Portugal, June 9-11, 2009. Proceedings, that address the problem of inconsistency detection in dis- pages 16–29, 2009. tributed model. However, this general problem is not new, [10] C. Nentwich, W. Emmerich, and A. Finkelstein. traceability maintenance systems in distributed developing Consistency management with repair actions. In Proc. environment that can manage dependencies and ensure trace- Int’l Conf. Software Engineering (ICSE’03), pages ability between documents were developed in a quite central- 455–464, Washington, DC, USA, 2003. IEEE ized fashion [7]. The consistency in this tool was managed Computer Society. at a code and documentation level, plus a monitor system [11] OMG. Unified Modeling Language: Super Structure was available for user defined dependency needs. version 2.1, january 2006. [12] Y. Saito and M. Shapiro. Optimistic replication. ACM Computing Surveys, 37(1):42–81, 2005. 6. CONCLUSION This paper presents the notion of single-view inconsistency [13] B. Selic. The pragmatics of model-driven development. detection. This method aims at detecting distributed in- IEEE Software, 20(5):19–25, 2003. consistencies in a light-weight fashion by only reasoning on [14] G. Spanoudakis and A. Zisman. Inconsistency elements that are relevent for both the considered inconsis- management in software engineering: Survey and open tency rules and the considered view. The method is based research issues. Handbook of Software Engineering and on the notion of inconsistency rules’ jump point which is Knowledge Engineering, pages 329–380, 2001. computed thanks to two of our previous contributions [1, 9]. 1 http://meta.lip6.fr 7