Towards Efficient Evaluation of Rule-based Permissions for Fine-grained Access Control in Collaborative Modeling Gábor Bergmann1,2 , Csaba Debreceni1,2 , István Ráth1 and Dániel Varró1,2,3 1 Budapest University of Technologies and Economics, Department of Measurement and Information Systems, Hungary 2 MTA-BME Lendület Research Group on Cyber-Physical Systems, Hungary 3 McGill University of Montreal, Department of Electrical and Computer Engineering, Canada Email: {bergmann,debreceni,rath,varro}@mit.bme.hu Abstract—In case of collaborative modeling, complex systems of a specific component needs to be revealed to certification are developed by different stakeholders, in offline submissions authorities to obtain certification credit but they need to or online sessions. To guarantee security, access control policies be hidden from competitors who might supply a different need to be enforced during the collaboration. As levels of required confidentiality and integrity may vary component in the system. Furthermore, there may be critical across model parts, we have previously proposed fine-grained aspects of the system model that may only be modified by rule-based access control, and shown how to consistently interpret domain experts having the appropriate qualifications. flexible access control policies. Capturing security policies on the storage (file) level instead Now we present an improvement on the previous results of the model level results in inflexible fragmentation of models allowing for incremental recomputation, which is vital for online collaboration scenarios. Our approach is illustrated using a case in collaborative scenarios (although flexibility is key [25]); study of the MONDO EU project. this can be solved by fine-grained access control, where each model element and its features can have its own set I. I NTRODUCTION of permissions. On the other hand, large industrial models A. Background and Motivation can have millions of model elements, thus explicitly assigning permissions for each of them, as well as maintaining the Model-based systems engineering has become an increas- permissions after changes to the model, would be labor- ingly popular approach [32] in critical cyber-physical sys- intensive and error-prone, and would make it difficult to tems followed by many system integrators like airframers understand the system of privileges. or car manufacturers to simultaneously enhance quality and A rule-based approach for concisely defining fine-grained productivity. An emerging industrial practice of such system model access control policies has been proposed in [6]. A integrators is to outsource the development of various compo- single rule may grant or deny nominal permissions for many nents to subcontractors in an architecture-driven supply chain. elements in a model. Due to this implicit nature, it is possible Distributed teams of different stakeholders (system integrators, that several rules would be in direct conflict with each other, software engineers of component providers/suppliers, hard- assigning contradictory permissions for some model element. ware engineers, specialists, certification authorities, etc.) may Indirect conflicts are also possible, if the fragment of the collaborate using models. model revealed to a user is not consistent with itself, or In an offline collaboration scenario, collaborators check out with the write permissions. In [10], we resolve conflicts in an artifact from a version control system (VCS) and commit a deterministic and customizable way to present a consistent local changes to the repository in an asynchronous long trans- and secure updateable view to each user. action. In online collaboration, engineers may simultaneously The solution in [10] relies on an algorithm that can be edit a model in short synchronous transactions which are executed for a given state of the model to derive the effective immediately propagated to all other users (similarly to online permissions from the nominal ones. However, this strategy collaborative tools like Google Docs). Several collaborative might not scale up to larger system models in case of online modeling frameworks exist [23], but security management is collaboration, as the algorithm would have to re-process the unfortunately still in a preliminary phase. permissions of all model elements after each small editing In fact, collaborative scenarios introduce significant chal- operation, leading to unacceptable response times. lenges for security management, both in terms of confiden- tiality and integrity. For instance, the detailed internal design B. Goals and Contributions In this paper, we investigate a possible way to incremen- This paper is partially supported by the MTA-BME Lendület 2015 Research Group on Cyber-Physical Systems. The first author was supported by the János talize the conflict resolution schema, so that small changes Bolyai Research Scholarship of the Hungarian Academy of Sciences. within large models would incur a small maintenance com- Module [0..*] submodules Composite Control protectedIP : EBoolean = false type : Type = Fan cycle : Cycle = high Cycle Type high Fan medium Heater low Pump Figure 1: Simplified Metamodel of Offshore Wind Turbines Figure 2: Sample Wind Turbine Instance Model putation only. Such an incremental resolution method would that oversees the entire module structure and has read and (a) supercede the limited-scope proof-of-concept incremental write access to the entire model. conflict resolver used in the online scenario experiments of [6], 2) Online Usage Scenario: The system integrator company (b) inherit the beneficial features (flexibility, consistency, de- is hosting the wind turbine control model on their collabo- terminism) of the non-incremental resolver algorithm [10], and ration server, where it is stored, versioned, etc. A group of (c) complement the incremental policy rule evaluation and en- users may participate in online collaboration, where they forcement techniques presented in [6] to guarantee acceptable are continuously connected to the central repository via an performance for online in addition to offline collaboration. appropriate client (e.g. web browser). Through their client, We achieve this goal by reformulating the original algorithm each user sees a live view of those parts of the model that of [10] as a recursive Datalog [16] query on the system model they are allowed to access. The users can modify the model (technically recursive V IATRA [5] graph patterns), for which through their client, which will directly forward the change to incremental evaluation algorithms are known. We point out the collaboration server. Then the server will decide whether subtle difficulties with the evaluation of the resulting patterns, the change is permitted under write access restrictions. If and suggest solutions for dealing with them. it is allowed, then the views of all connected users with II. C ASE S TUDY appropriate read permissions will be updated transparently and immediately. However, changes introduced by a user may A. Modeling Language influence the accessibility of model parts for other users. Several concepts will be illustrated using a simplified ver- Hence, the access control policy has to be reevaluated when sion of a modeling language for system integrators of offshore the model is changed. wind turbine controllers, which is one of the case studies of the MONDO EU FP7 project. The metamodel, defined Example 2. After the Principal Engineer changes the pro- in EMF [29] and depicted by Fig. 1, describes how the tectedIP attribute of the composite module c2 from true to system is modeled as modules organized in a containment false, the Pump Control Engineer shall be able to access hierarchy of composite modules. Composite modules may the contained pump control module ctrl4. express protected IP and they can ultimately contain control III. S ECURITY VOCABULARY unit modules that are responsible for a given type of physical device (such as pumps, heaters or fans). Here we briefly introduce a vocabulary for fine-grained access control; a more detailed treatment can be found in our Example 1. A sample instance model containing a hierarchy previous work [6] and especially [10]. of 3 Composite modules and 4 Control units is shown in A. Model Facts as Assets Fig. 2 – boxes represent objects, entries within the box are attribute values, and edges are containment references. In order to provide fine-grained access control, models have to be decomposed into smaller assets that can be separately 1) Access Restrictions: We assume that each control unit protected. For simplicity, we will consider models as a set of type (Pump, etc. . . ) is associated with a specific person (re- elementary model facts. For example, EMF models (ignoring ferred to as specialist) who is responsible for maintaining the the multi-resource case) consist of the following kinds of model of control unit modules of that specific type. Each such model facts: user is able to modify the control units that belong to them, Object facts are pairs formed of a model element (EObject) they cannot access to any control unit contained directly or with its exact type (EClass), for each model element object; indirectly by composite module that express protected IP. For e.g. obj(c1,Composite). instance, the user responsible for pump controllers (the Pump Attribute facts are triples formed of a source EObject, an Control Engineer) can modify the controller ctrl1 but cannot attribute name (EAttribute) and the attribute value, for each see the object ctrl4 as it is contained c2 which describe that (non-default) attribute value assignment; e.g. attr(ctrl3, cy- its content is protected. Finally, there is a principal engineer cle,::low). Reference facts are triples formed of a source EObject, a reference type (EReference) and the referenced EObject, for each containment link and cross-link between objects; e.g. ref(c1,submodules,ctrl2). Note that for multi-valued attributes and references, each of the multiple entries at a source EObject will be represented by a separate attribute or reference fact. In the following, we will focus on object facts, but the same formal framework applies to all assets. B. Permissions The above mentioned model facts are the assets that the Figure 3: Effective Perms. for Pump Control Engineer access control policy will protect against operations (typically read and write) that can be performed by the user. The goal of from being processed and stored in the given modeling tech- interpreting the security policy is to come up with an effective nology, as error markers can be placed on such violations. permission function that assigns a permission level to each Thus only internal consistency is essential for access control. combination of asset, user and operation. Internal consistency of the filtered view implies that the The assigned permission level takes its value from a permis- effective permissions must satisfy a some constraints that sion lattice characteristic to the operation. In the simplest case, are expressed as a strong dependency relationship between this is the two-valued lattice {deny < allow}; in general it is two values of the effective permission function: a dependant possible to use a more refined lattice instead. In the rest of the and a dependee. According to the formalization in [10], this paper, we will restrict ourselves to the case where the lattice relationship is a Galois connection. This means that if a lower is a total order, i.e. from any two levels, one is considered bound is known for the permission level of the dependant, strictly more restrictive than the other. then a lower bound on the permission level of the dependee For instance, it was previously suggested [10] to use is inferred; and conversely, an upper bound on the dependee {deny < obfuscate < allow} as read permission levels, to puts an upper bound on the dependant. For instance, (a) if an express the case where an attribute of an otherwise visible asset is writable (write permission level allow), then it must object conveys confidential information that shall not be re- also be visible (at least on the read permission level allow); vealed to the given user, but the attribute can not be completely (b) if an object is readable at least on the level obfuscate, then hidden (since it is used as e.g. an identifier or visual label). its containing object (if any) must also be visible (at least on A sample refinement of the write permission levels could the level obfuscate). All of these constraints have a converse, be {deny < dangle < allow}, where cross-references with e.g. if an object is not visible (read permission level is at most write permission level dangle can not be normally modified deny), then any contained objects have their read permission by the user, but they can be removed as the side effect of level at deny as well. deleting the target object of the reference (if that deletion is Apart from the strong dependencies discussed above, the permitted), even if the cross-link is not visible to the user. concept of weak consequences were also introduced in [10], Imagine a traceability link that points from a hidden part of to express defaults rather than strict implications. For example, the model to a visible object; the difference between assigning all contained elements and attributes of a visible object should deny or dangle is that the target object can not be deleted by also be made visible by default - unless there is another reason the user in the former case, while its deletion would be allowed to deny the read permission. Also, if the read permission for an (with an invisible side-effect of removing the traceability link) object is known to be at most obfuscate, its write permission in the latter case. must be at most dangle as a strong consequence, but (weak C. Consistency of Secure View consequence) it should be deny by default, unless specifically The view presented to a user consists of the set of assets overridden. for which they have read permissions (modulo obfuscation, Example 3. Fig. 3 depicts the effective permissions of the see above). However, an arbitrary set of model facts does not running example for the Pump Control Engineer. As c2 necessarily constitute a valid model; there may be internal expresses protected IP, read and write operations are denied consistency constraints (also called referential integrity con- for the composite c2 and its contents, visualized by dashed straints) imposed on the facts by the modeling platform to borders in case of objects and dashed edges in case of refer- ensure the integrity of the model representation and the ability ences. On the other hand, the control module ctrl1 needs to persist, read, and traverse models. A major goal stated in [6], to be modifiable, therefor also visible (strong dependency) [10] requires that secure models must be synthesized as a set denoted by RW in a square. As ctrl1 needs to be visible, of model facts compatible with all internal consistency rules. its container c1 and also the root module root need to be Note that we distinguish these low-level internal consistency visible at least in an obfuscated way (strong dependency) rules from high-level, language-specific well-formedness con- straints. Violating the latter kind does not prevent a model Listing 1 Queries for Access Control Rules Listing 2 Access Control Rules of the Example 1 pattern pumpControlPattern(ctrl:Control) 1 policy Example deny RW by default { 2 { Control.type(ctrl,::Pump)} 2 rule accessModule allow W to PumpCtrlEng 3 3 { query: pumpControlPattern } priority 1 4 pattern propectedIPPattern(c:Composite) 4 5 { Composite.protectedIP(c,true)} 5 rule hideModule deny R to PumpCtrlEng 6 { query: propectedIPPattern } priority 2 7 } denoted by O in squares. There are no explicit restrictions related to the attributes of control module ctrl1, so they Example 4. Lst. 1 specifies the graph queries for access con- inherit visibility from the object asset (weak consequence). trol rules in V IATRA syntax. Pattern pumpControlPattern selects all control module of type ::Pump while pat- IV. P REVIOUS W ORK tern propectedIPPattern queries the composite modules Using the vocabulary introduced in Sec. III, we now briefly where the protectedIP is to true. revisit the rule-based access control solution and the non- The policy described in Lst. 2 using the syntax introduced incremental conflict resolver introduced by [10]. More detailed in [10] refers these graph pattern to specify access control descriptions with concrete examples can be found in the rules. Rule accessModule allows the write operation of referenced paper. modules identified by pattern pumpControlPattern and The design goals were to allow the policy engineer to rule hideModule denies the read operation of modules declaratively, concisely but also flexibly express permissions selected by pattern propectedIPPattern. Priorities of the for a large number of assets in the form of rules. This was rules are 1 and 2, respectively. achieved by providing a (terminating, deterministic) algorithm The policy specifies the global default that all the assets that interprets these rules and resolves conflicts among them are unreadable and unmodifiable. Rule accessModule as- (also taking into account the defaults), yielding an effective signs read permissions to objects ctr1 and ctrl2 which is permission function that meets the intentions of the policy the result set of pattern pumpControlPattern) while rule engineer and satisfies the dependencies among assets. hideModule denies the read permission of c2 the result set of pattern propectedIPPattern. A. Rule-based Access Control In [6], we introduced a rule-based access control approach, B. Judgments where the rules are defined by graph queries (model queries). During the process of conflict resolution, the algorithm Such a query is essentially a formula that can be evaluated on maintains a set of (typically conflicting) direct and indirect the model. When a query is evaluated, the results consist of consequences of the access control rules. a set of pattern matches. Rules grant or deny read and write We define a permission set as a set of judgments, where each permissions to the assets identified by the pattern matches of judgment j is a tuple j = ha, o, p, ψ, πi, where a ∈ Assets is a query. Of course, a rule may only affect a subset of users, so an asset, o ∈ {R, W } is an operation (read or write) to be a selection of users/groups is given as well. Finally, a priority performed on the asset, p ∈ Levelso is a permission level class π ∈ Π is given as well, according to which conflicts are associated with the operation, ψ ∈ Ψ = {>, <} indicates resolved: the higher priority rule overrides the lower priority whether the judgment puts that permission level as an upper one according to the total order of Π. To unburden the author, respectively lower bound for the final permission decision, and the order of rules in the policy may be taken as a default π ∈ Π is a priority class. assignment of priority classes. A valid permission set is complete, i.e. for each asset and To summarize, an access control rule in the policy consists operation, it must contain at least one upper bound and one of a set of affected users/groups, a model query to identify lower bound judgment, and by the ordering of permission affected assets, a priority class π ∈ Π, an affected operation, levels, the lowest (strictest) upper bound must not be higher and an upper or lower bound on the permission level of that than the highest (strictest) lower bound. operation. The initial permission set is obtained from rules and de- We allow for compound rules as concise syntactic sugar, faults. For all assets and operations, default permissions are where the policy engineer can specify more than one rule included as a pair of judgments (one upper bound, one lower (corresponding to the above structure) in one go. For instance, bound, both with the same permission level), with a priority it shall be possible to set both read and write permissions to class that is lower than the priority of any query-based rule; deny, or to set the upper and lower bound of a read permission this ensures completeness. For each match of the queries to obfuscate simultaneously. of security rules that apply for the user, an upper or lower The conflict resolution process of one user is independent bound judgment is added; the asset is given by the pattern from any other users. Therefore in the following sections, maftch, and the operation, priority class and permission level we consider permissions from the perspective of a single are determined by the rule header. user only, and omit the user identity from the subsequently The goal is to derive the resolved permission set, where the introduced structures. highest (most permissive) lower bound is equal to the lowest Table I: Initial Judgments of the example Rules Example 6. The judgment hobj(c2,Composite), R, deny, >, 2i hobj(ctrl1,Control), W, allow, <, 1i obtained from the rule hideModule needs to be propa- hobj(ctrl4,Control), W, allow, <, 1i gated to the contained objects of composite c2 as strong hobj(c2,Composite), R, deny, >, 2i dependency. Hence, new judgments appear with exactly the same priority, operation, permission level and bound, Table II: Global Defaults on Control Module ctrl1 namely the judgments hobj(ctrl3,Control), R, deny, >, 2i and hobj(ctrl1,Control), R, deny, <, 0i hobj(ctrl4,Control), R, deny, >, 2i. However, the new judg- hobj(ctrl1,Control), R, deny, >, 0i hobj(ctrl1,Control), W, deny, <, 0i ment hobj(ctrl4,Control), R, deny, >, 2i is in local conflict hobj(ctrl1,Control), W, deny, >, 0i with the judgment hobj(ctrl4,Control), R, allow, <, 1i obtained from the rule accessModule (see Table I) as they refer to the same asset and operation and contradict on the permission upper bound for each asset and operation (thereby identifying bound (at least allow vs. at most deny). a single permission level as the effective permission), and there are no conflicts (neither directly nor indirectly though D. Dominance and the Resolution Step dependencies) between the judgments. Take any two judgments that are in conflict. Without loss of generality, we may assume that one must dominate the Example 5. The initial permission set obtained from other via its higher priority class (see [10] for the unimportant the evaluation of access control rules accessModule and nuance of conflicts within the same priority class). Due to the hideModule is collected in Table I. Global defaults deny all consequence propagation introduced in Sec. IV-C, it is enough access with 4 judgments per asset (both bounds (>, <) and to consider local conflicts, as any conflict will manifest itself operations (R,W) set to deny), e.g. the default judgments of somewhere as a local conflict. Therefore we consider pairs of the control module ctrl1 are listed in Table II. judgments on the same asset and operation, where one is an upper bound judgment, and the other is an incompatible lower C. Propagation of Consequences bound judgment with different priority. A resolution step takes two judgments that are in a local In Sec. III-C we discussed how the requirement of internal conflict, and modifies the dominated judgment to make it consistency introduces dependencies between the permission compatible with the dominant judgment. For locally conflict- levels of different assets and operations. ing judgments j = ha, o, p, ψ, πi and j 0 = ha, o, p0 , ψ 0 , π 0 i As a judgment may impose dependency constraints on other with π > π 0 the conflict resolution replaces j 0 with j 00 = assets or operations, its consequences can be propagated and ha, o, p, ψ 0 , π 0 i. Executing such a step transforms a permission directly represented as additional judgments on foreign asset/- set to a different one. operation pairs. Using the propagated consequence judgments, Observations on the resolution step: (a) j 00 relaxes j 0 , i.e. all indirect conflicts can be transformed into local conflicts. upper bounds are raised when replaced, while lower bounds The latter means that the conflict is expressed as two directly are lowered. (b) j 00 is guaranteed by the construction to be contradicting judgments for the same asset and operation, non-conflicting with j. (c) The resolution step upholds the as opposed to dependency-driven indirect conflicts between completeness of the permission set. judgments at different assets of operations. It was discussed in [10] how consequence propagation makes focusing on local Example 7. In Ex. 6 , a local conflict is introduced by conflicts sufficient. propagation of strong dependency. Due to domination, the For judgment j = ha, o, p, ψ, πi of bound ψ ∈ Ψ = judgment hobj(ctrl4,Control), R, deny, >, 2i with higher pri- {>, <}, with a dependency on asset and operation ha0 , o0 i, ority relaxes the judgment hobj(ctrl4,Control), R, allow, <, 1i the propagated strong consequence judgment is denoted as to hobj(ctrl4,Control), R, deny, <, 1i. jha0 ,o0 i := ha0 , o0 , l, ψ, πi where l is the bound associated with p by the Galois connection described in Sec. III-C. E. Resolution Process Extending the above notion, is also possible to propagate The non-incremental resolution process (see Alg. 1) pro- weak consequences that encapsulate a default effect of a posed in [10] iterates over judgments in the order of dom- given judgment, not a necessary condition. Unlike its strong inance (i.e. highest priority first), to propagate their conse- counterpart, a weak consequence does not inherit the priority quences (also the weak consequences, unless contradicted by a of the original judgment, but is assigned a lower priority previously processed judgment) and resolve any local conflicts instead, and may be overridden by more dominant judgments that are detected. without conflicting with the original judgment. It can be for- The analysis in [10] shows that this process always termi- ∗ 0 0 ∗ ∗ nates, yields a deterministic (confluent) result regardless of the mally captured as jha 0 ,o0 i := ha , o , l , ψ, π i. It was proposed in [10] to assign a priority class to these weak consequences choice of unprocessed dominant judgment, and the result is a that is lower than the priority of any user-specified rule, but complete and consistent effective permission set. higher than the priority of global defaults that such a weak consequence may override. Algorithm 1 The resolution process of [10] in pseudocode B. Naive Reformulation . The policy is assumed as an implicit global parameter For the sake of simplicity, the following discussion will function G ET E FFECTIVE P ERMISSIONS(model, user) permissionSet ← getInitialP ermissions(model, user) focus on object assets only. The conflict resolver takes the processed ← ∅ following inputs (extensional relations in Datalog parlance): while permissionSet 6⊆ processed do • The explicit judgments that are immediately obtained by j ← chooseDominant(permissionSet \ processed) evaluating the access control rules in the policy; as men- processed ← processed ∪ {j} . mark as effective for all dependencies ha0 , o0 i of j do . propagate tioned above, each match of the associated model query of conseq ← {jha0 ,o0 i } . strong consequence the rule will yield a judgment (in the initial permission set). if 6 ∃ j 0 ∈ processed conflicting jha ∗ 0 ,o0 i then • Low-priority judgments corresponding to global defaults ∗ conseq ← conseq ∪ {jha 0 ,o0 i } . weak (can be merged with the former). end if • Relations describing the connections between assets, in permissionSet ← permissionSet ∪ conseq end for order to enable the propagation of consequent judgments. conf licts ← localConf lictsOf (j, permissionSet) For instance, in case of object facts, a binary relation for all j 0 ∈ conf licts do . resolve locally describing the containment hierarchy is necessary. j 00 ← ResolutionStep(j, j 0 ) . j dominates From these extensional relations, the following incremen- permissionSet ← permissionSet ∪ {j 0 } \ {j 00 } end for tally maintained queries (intensional relations) are derived (see end while also Lst. 3): return permissionSet judgment matches all inferred judgments j = ha, o, p, ψ, πi, end function computed as the union of explicit judgments, the strong and weak consequent judgments, and the relaxed forms of dominated judgments. Example 8. The output of the algorithm on the case study relaxedJudgment identifies judgments that are dominated is presented in Ex. 3 and visualized in Fig. 3. (see next query), and computes their relaxed form (inheriting the bound of the dominant judgment). V. D ECLARATIVE R EFORMULATION domination identifies the judgments in local conflict (suf- A. Motivation ficient as per Sec. IV-C) and the dominant one among In Sec. IV, we presented the algorithm of [10] for obtain- them; this query matches pairs of dominating and dominated ing the effective permissions from the nominal permissions judgments in local conflict, respectively j = ha, o, p, ψ, πi explicitly assigned by the access control rules of the policy. and j 0 = ha, o, p0 , ψ 0 , π 0 i, that are defined on the same asset The algorithm can be run on a state of the model to produce and operation, with the dominating judgment having higher the effective permissions of all model elements. priority (π > π 0 ) and the dominated bound contradicting it This is an adequate solution for the offline collaboration (p0 ψp for ψ ∈ Ψ = {>, <}, as expressed by helper pattern scenario, which is characterized by infrequent commit actions permissionOutOfBound). For efficiency, only effective at the end of long transactions, which may change an arbitrar- judgments (see next query) are considered for the role of ily large part of the model. And even if the change themselves the dominating judgment. turn out to be relatively small, the complexity of processing the effectiveJudgment matches any judgment that is not dom- commit is at least proportional to the size of the model anyway, inated at all by any judgment, i.e. there is no corresponding unless a sophisticated fine-grained diff solution is applied. match of the domination query. Note that this is a negative On the other hand, online collaboration is characterized by composition. frequent and short transactions, each of which change only a strongConsequence computes the propagated small part of the model. In case of larger models, response consequences of effective judgments; it matches pairs times would suffer greatly if the entire model had to be of judgments j = ha, o, p, ψ, πi and j 0 = ha0 , o0 , p0 , ψ 0 , π 0 i re-processed upon each small change. Therefore, we aim to where j is an effectiveJudgment and j 0 = jha0 ,o0 i . For obtain the effective permission function by an incremental strong consequences, π = π 0 is also required. The results computation. are computed as a union of cases, two for each kinds The evaluation of access control queries and the actual en- of dependency; one where a dominant lower bound on a forcement of permissions is also performed incrementally [6]. dependant propagates a lower bound consequent judgment It would seem natural to try to express the conflict resolution to the dependee asset, and one where a dominant upper and derivation of effective permissions as model queries, and bound on a dependee propagates an upper bound consequent use the same technology [31], [5] that already provides the judgment to the dependant asset. In case of object assets, incremental evaluation of access control queries. such dependencies are found between the read and write In the following, we describe our efforts to reformulate operations of the same asset, and between contained and the algorithmic conflict resolution process into a declarative container objects (see Sec. III-C). computation. We use the formalism of recursive graph queries weakConsequence is constructed similarly, except the con- (Datalog [16]), specifically the V IATRA syntax. sequent has a constant, low priority. Listing 3 Naive solution in V IATRA syntax (extracts) 1 pattern judgment(user,asset,op,bound,dir,prio) 2 { find explicitJudgment(user,asset,op,bound,dir,prio); 3 } or { 4 find relaxedJudgment(user,asset,op,bound,dir,prio); 5 } or { 6 find strongConsequence(user,asset,op,bound,dir,prio); 7 } 8 pattern relaxedJudgment(user,asset,op,bound,dir,prio) 9 { find domination(user,asset,op,_,dir,prio,bound); 10 } 11 pattern effectiveJudgment(user,asset,op,bound,dir,prio) 12 { find judgment(user,asset,op,bound,dir,prio); 13 neg find domination(user,asset,op,bound,dir,prio,_); Figure 4: Dependency Graph of the Naive Queries 14 } 15 pattern domination(user,asset,op,dBound,dDir,dPrio,eBound) 16 { find judgment(user,asset,op,dBound,dDir,dPrio); 17 find effectiveJudgment(user,asset,op,eBound,eDir,ePrio); 18 find permissionOutOfBound(eDir,eBound,dBound); 19 eDir!=dDir; no unprocessed judgments in the permission set that could 20 } dominate it, and of course already processed judgments are 21 pattern strongConsequence(user,dAsset,dOp,dBound,dir,prio) 22 { // Case 1: read vs write, AT_LEAST not in conflict with j and thus do not dominate it (otherwise j 23 find effectiveJudgment(user,eAsset,eOp,eBound,dir,prio); would have been relaxed and removed earlier when they were 24 dAsset == eAsset; dir == BoundDirection::AT_LEAST; 25 eOp == SecurityOperation::WRITE; processed); consequently, the effectiveJudgment query 26 eBound == WriteLevels::ALLOW_WRITE; would match j. Conversely, if the effectiveJudgment 27 dOp == SecurityOperation::READ; 28 dBound == ReadLevels::ALLOW_READ; query matches the judgment j of priority π, that means no 29 } or {...} // Other cases other higher-priority effective judgment dominates it, therefore (by the induction hypothesis) the original algorithm never eliminates it from the permission set, and it is eventually Note that for a given asset and operation, in addition to the selected as an effective judgment. strictest effective upper or lower bound, there can additionally occur less strict, superfluous judgments. It is possible to C. Non-Stratifiability eliminate them based on subsumption by stricter effective judgments. If subsumed judgments are then eliminated from A significant flaw of the naive reformulation in Sec. V-B is the essential judgements, then their consequences won’t be revealed when we consider how the results of these queries propagated, and some computational cost can be saved. The are derived from each other. simplest solution is probably to adjust domination so that it Not counting extensional relations, the query judgment does not check whether the bound direction of the dominated derives from relaxedJudgment, strongConsequence and judgment is opposite to the dominant one (i.e. remove the weakConsequence as depicted in Fig. 4. The latter last line of domination in Lst. 3), then in addition to actual two also derive their results from effectiveJudgment. dominations, it will also match most such subsumed judgments The relaxedJudgment references domination, while (except for the case where a judgment is subsumed by another domination uses judgment and effectiveJudgment. Fi- one in the same priority class). nally, effectiveJudgment is computed from judgment, The effective permission function is finally obtained as permissionOutOfBound a negation of domination. the result set of the effectiveJudgment query, where the It is immediately obvious that this is a recursive query strictest lower and upper bounds will coincide (see proof structure, e.g. judgment refers indirectly to domination in [10]). Let us now investigate the correctness of this solution. which refers to judgment again. Fortunately, it is possible to Proposition: This group of queries yield the same effec- evaluate recursive queries (there are even multiple incremental tive permission set as Alg. 1. strategies [17]). Proof sketch: One has to consider the way of determining However, these strategies require a property of the the set of effective judgments, as the rest follows fairly query structure called stratification [16], which the refor- trivially. The original algorithm iteratively selected the highest- mulated conflict resolver does not exhibit. Informally, a priority yet-unprocessed judgment and designated it as an Datalog program is stratified if there are no negations effective judgment (by putting it into the processed set). used in the cyclic references between predicates (i.e. re- By contrast, here judgments are considered effective when lations or patterns). In our case, a counterexample would they are not dominated by any other judgment. It takes some be effectiveJudgment negatively referring domination, thinking to see that the two conditions yield the same results. which in turn uses effectiveJudgment. We use downwards induction by priority class; assume that Typical query engines only handle stratified query struc- the two versions of the effective permission set are equivalent tures, as non-stratified ones do not even have a single accepted above priority class π. When the original algorithm selects semantics [16], and 2-valued semantics are often not possible. a dominant judgment j of priority π as the new effective See for instance the famous example of a non-stratified Data- judgment, the priority-based ordering ensures that there are log program “this sentence is a lie”. Fortunately, there are a few relaxations of the criteria for executed with an arbitrary computation order chosen by the stratifiability. Recursions can still have definite (2-valued) query engine. Ordering by rule priority is a highly application- semantics (and evaluation algorithms) if they are locally [21], specific optimization, and there is no standard way to make a modularly or at least weakly [24] stratifiable. Informally, these query engine such as V IATRA aware of it. relaxed notions of stratification investigate the dependencies between individual tuples (so-called ground atoms) as opposed E. Improved Query Structure to whole relations; it is sufficient if there is no negation in The previous sections identified two significant issues with circular references between tuples (in the ground Datalog the naive reformulation of the access control conflict resolution program). The subtle differences between local, modular and problem, stratifiability and performance. Still, we do not weak stratification manifest themselves in the ways how give up on using a general-purpose query tool to provide already known facts are used to cull unnecessary (e.g. unsat- incremental evaluation; instead, we propose a way to modify isfiable) references before cycles are evaluated to be negation- the query structure such that it avoids both problems. free; the formal details are not explored here. Fortunately, the solutions to both issues involve the same Although the query structure of Sec. V-B is neither strat- weak ordering of tuples based on priority class. We therefore ifiable nor locally stratifiable, it is weakly and even mod- propose to apply partial grounding, where given a policy ularly stratifiable. The reason is that the only occurrence of k priority classes, we substitute all k values into each of negation is between predicates effectiveJudgment and priority variable of the query, blowing up each predicate into domination; however, a judgment may only be dominated k disjoint shard predicates (k 2 in case of domination where by higher-priority judgments. After eliminating judgment pairs two judgments of different priority are involved). Priority from domination for which the priority comparison con- comparisons can be statically evaluated in this case. straints fail (which is allowed in modular, but not in local There is one corner case where negative recursion still stratification), we are left with no tuple-level negative cycles. persists, despite sharding the predicated according to priority: Although modular stratifiability shows the existence of 2- the effectiveJudgment query for a given priority class valued semantics, it is not necessarily compatible with all negatively calls the domination relation for the same priority evaluation strategies, especially incremental ones. Even if a (of the dominated judgment), which is in turn derived from given strategy is guaranteed to yield correct results, concrete dominated judgment matches of that priority, that on one tools such as V IATRA may pessimistically refuse to evaluate branch rely on strongConsequence matches, which call a query structure that is not stratifiable (as detecting e.g. local effectiveJudgment, all of the same priority level. We stratification may be undecidable [21]). propose the following solution: we replace domination with dominationBy that will no longer imply that a dominated D. Performance Considerations judgment exists; it merely asserts that an effective judgment Beyond the question of stratification, the recursive query exists at a given priority, that would dominate any lower- structure also introduces performance challenges. priority judgment at the given asset and the given permission Imagine a single-root containment hierarchy consisting of n bound. This way the negative recursion is averted. objects altogether. Suppose we define k separate access control For priority class π, we define the following predicates (see rules in k different priority classes, each of which applies to the also Lst. 4): root object, such that every other rule (those in even priority judgmentπ matches all inferred judgments j = ha, o, p, ψ, πi classes) sets the read permission to allow, while the rest of the of priority class π, computed as the union of explicit judg- rules set it to deny. In this case, query evaluation performance ments in class π, the strong and weak consequent judgments depends greatly in the order of computations, even if the end in class π, and the relaxed forms of dominated judgments in result is guaranteed to be the same. class π. If the query engine happens to propagate tuples in the relaxedJudgmentπ identifies judgments of priority class π ascending order of the priorities of corresponding judgments, that are dominated (see next query) by any priority π 0 > π, then first all n objects are set to invisible by the lowest priority and computes their relaxed form (inheriting the bound of the rule, then the next rule is found to dominate the previous one dominant judgment). and all n objects are made visible again, etc., until finally the dominationByπ will match (independently of the existence effective permissions are obtained in O(n ∗ k) steps. of any dominated judgments) all effective judgments j = If, on the other hand, the query engine propagates tuples in ha, o, p, ψ, πi ∈ effectiveJudgmentπ of priority π and all the order of descending priority, then the final read permissions potential bounds p0 for the corresponding asset and operation are set immediately in the highest priority class , and then the that would be dominated by it in local conflict (p0 ψp for rest of the rules are merely dominated, but never propagated. ψ ∈ Ψ = {>, <}). This leads to O(n + k) steps of computation. effectiveJudgmentπ filters judgmentπ to those judg- Altogether, if the evaluation follows the original procedure ments that are not dominated, i.e. there is no corresponding in Alg. 1 and processes high-priority rules first, then (strong) match of dominationByπ0 for any π 0 > π. consequences are never overruled, minimizing the amount of strongConsequenceπ computes the propagated conse- work to be done. Unfortunately, declarative queries can be quences of effective judgments at class π. weakConsequenceπ analogously. improvements (beyond the considerations of Sec. V-D) are In the above queries, the priority class comparisons “π 0 > left as future work. π” are statically evaluated, and the generated disjunctions only include the clauses where the result is true. VI. R ELATED W ORK With this solution, the query structure is now stratifiable, File-based Access Control. Off-the-shelf file systems typ- addressing the concerns of Sec. V-C. Also, a query engine ically require resources (files and folders) to be explicitly la- evaluating (or updating, in case of incrementality) it can beled with permissions that take the form of an Access Control process individual predicates in their topological order, which List (ACL), or the simplified form user/group/others. An ACL addresses the issue raised in Sec. V-D. consists of entries (judgments) regarding which user/subject is Once stratification is achieved, let us take a look at what granted or denied permission for a given operation. Conflict forms of (positive) recursion remain, keeping in mind that resolution is usually priority-based (first entry applies) within these no longer pose an obstacle to incremental matching. the access control list, and restrictive among type II and type First, relaxedJudgmentπ contributes to judgmentπ and III conflicts (e.g. contents of a hidden folder cannot be seen, vice versa. Note that there is no circularity on the tuple level, regardless of ACLs inside). as the original dominated judgments (as well as subsumed File-based solutions can be directly applied to MDE, but ones) are always farther from the effective judgment than their cannot provide fine-grained access control, where different relaxed versions. Moreover, judgmentπ is partially expressed parts of a model file have different permissions. Our policies from strongConsequenceπ , which finds consequences of are fine-grained, use implicit rules (so that model elements effectiveJudgmentπ that of course uses judgmentπ ; in do not have to be explicitly annotated with judgments, which this case it depends on our internal consistency constraints is difficult to manually maintain as the model evolves), and whether consequences can cyclically justify each other (in the respect the modeling-specific challenges of consistency (such simple cases described in this paper, they can’t). In application as permission dependencies of cross-references); all the while scenarios where we know that there are no tuple-level cycles, being more flexible in the conflict resolution method. the fast default algorithm suffices to efficiently evaluate re- Access Control for XML Documents. A number of cursive queries; for other cases, V IATRA provides the more standards such as XACML [15] (OASIS standard) provide complex DRed algorithm [17] as well, guaranteeing correct fine-grained access control for XML documents. These type incremental maintenance for any stratified query structure. of documents are similar to models in a way, that they consists of nodes with attributes that may contain other Listing 4 Refined solution in V IATRA syntax (extracts) nodes. XACML provides several combining algorithms to 1 pattern relaxedJudgement_at_0(user,asset,op,bound,dir){ select from contradicting policies. Similarly to our solution, 2 find judgement_at_0(user,asset,op,dBound,dir); it may use external and internal priorities together (ordered- 3 find domination_by_1(user,asset,op,_dBound,bound); 4 } or { (deny/permit)-overrides) or only internal priorities (unordered- 5 find judgement_at_0(user,asset,op,dBound,dir); (deny/permit)-overrides). In [12], fine-grained access control 6 find domination_by_2(user,asset,op,_dBound,bound); 7 } or {...} is formalized using XPath for XML documents, which claims 8 pattern effectiveJudgement_at_0(user,asset,op,bound,dir){ that the visibility of a node depends on its ancestors, thus when 9 find judgement_at_0(user,asset,op,bound,dir); 10 neg find domination_by_1(user,asset,op,bound,_); a node is granted access, then access is also granted to its 11 neg find domination_by_2(user,asset,op,bound,_); descendants. However, other dependencies are not discussed 12 // ... 13 } related to XML Documents, while our approach [10] also 14 pattern domination_by_1(user,asset,op,dBound,dir){ considers e.g. cross-references. 15 find effectiveJudgment_at_1(user,asset,op,eBound,dir); 16 find permissionOutOfBound(dir,eBound,dBound); Context-aware Access Control RDF Stores. Models can 17 } // ... be persisted into triples to store them in triple or quad stores (Neo4EMF[4], EMF Triple). Graph-based access control is Finally, a note on space and time cost: a straightforward a popular strategy for many RDF stores (4store [14], Vir- upper bound on the size of the match sets can be obtained by tuoso , IBM DB2) developed for storing large RDF data. taking the Cartesian product of the domains of query variables. In case of RDF, fine-grained specification of access control In our example, there are 3 priority classes, 2 controlled permissions are defined at triple level. In [1], a graph-based operations, 3 permissions levels (both for read and write), policy specification language proposed over SPARQL [22], etc.; in the end, for a fixed security policy, the upper bound but resolution of contradicting rules are not discussed. Amit is proportional to both the model size (number of assets) and Jain et. al. [18] propose an access control model for RDF the number of active (e.g. simultaneously connected) users. In and a two-level conflict resolution strategy that also takes the non-recursive case, incrementally maintaining the result inconsistencies into account similar to our solution. But, it of queries has time complexity proportional to the size of the uses only restrictive resolution without any configuration of change (in the inputs, in the results, and also in any internal default values or priorities between rules. cache structure), regardless of the size of the unchanged parts. Collaborative Modeling Environments. Currently, fine- For recursive queries, such a straightforward linear relationship grained access control is not considered in the state of the can not always be established; performance analysis and art tools of MDE such as MetaEdit+[30], VirtualEMF[8], WebGME[19], EMFStore [28], GenMyModel [2], Obeo De- [6] Gábor Bergmann, Csaba Debreceni, István Ráth, and Dániel Varró. signer Team [20], MDEForge [3] or the tools developed Query-based Access Control for Secure Collaborative Modeling using Bidirectional Transformations. In MoDELS’16, pages 351–361, 2016. according to [13]. See also the broader survey in [23]. [7] Matt Blaze and Angelos D Keromytis. The keynote trust-management The generic framework CDO [27] (used e.g. in [20]) pro- system version 2. 1999. vides both online collaboration and role-based access control [8] Cauê Clasen, Frédéric Jouault, and Jordi Cabot. VirtualEMF: A model virtualization tool. In Advances in Conceptual Modeling. Recent with type-specific (class, package and resource-level) permis- Developments and New Directions, pages 332–335, 2011. sions, but no facility for instance level access control policy [9] Penn University DARPA VehicleFORGE. TrustForge: Flexible Access specifications. However, there is a pluggable access control Control for VehicleForge.mil Collaborative Environment, 2012. [10] Csaba Debreceni, Gábor Bergmann, István Ráth, and Dániel Varró. mechanism that can specify access on the object level; it Deriving Effective Permissions for Modeling Artifacts from Fine-grained should be possible to integrate fine-grained solutions such as Access Control Rules. In COMMitMDE@MoDELS’16, pages 17–26, the currently proposed system. 2016. [11] Matthias Farwick, Berthold Agreiter, Jules White, Simon Forster, Nor- The collaborative hardware design platform VehicleFORGE bert Lanzanasto, and Ruth Breu. A web-based collaborative metamodel- stores their model in graph-based databases and has an access ing environment with secure remote model access. In Web Engineering, control scheme TrustForge [9] that uses an implementation ICWE 2010, Vienna, Austria, July 5-9, volume 6189 of LNCS, pages 278–291. Springer, 2010. of KeyNote [7] trust management system. This system is re- [12] Irini Fundulaki and Maarten Marx. Specifying access control policies sponsible for evaluating the request addressed to the database, for XML documents with XPath. In 9th ACM Symposium on Access which can be configured in various ways. It supports unlimited Control Models and Technologies, pages 61–69, 2004. [13] Jesús Gallardo, Crescencio Bravo, and Miguel A. Redondo. A model- permission levels and it is also able to handle consistency driven development method for collaborative modeling tools. J. Network constraints by adding them as assertions. Conflict resolution and Computer Applications, 35(3):1086–1105, 2012. strategies are not discussed. AToMPM [26] provides fine- [14] Garlik. 4store. http://4store.org/trac/wiki/GraphAccessControl. [15] S. Godik and T. Moses (eds). eXtensible access control markup language grained role-based access control for online collaboration; (XACML) version 1.0. 02 2003. no offline scenario or query-based security is supported, [16] Todd J. Green, Shan Shan Huang, Boon Thau Loo, and Wenchao Zhou. though. Access control is provided at elementary manipulation Datalog and recursive query processing. Found. Trends databases, 5(2):105–195, November 2013. level (RESTful services) in the online collaboration solution [17] Ashish Gupta, Inderpal Singh Mumick, and V. S. Subrahmanian. Main- of [11]. taining views incrementally (extended abstract). In Proc. of the Int. Conf. on Management of Data, ACM, pages 157–166, 1993. VII. S UMMARY [18] Amit Jain and Csilla Farkas. Secure resource description framework: an access control model. In 11th ACM Symposium on Access Control To support rule-based fine-grained access control under Models and Technologies, pages 121–129, 2006. internal consistency constraints, we have taken a significant [19] Miklos Maroti et al. Next Generation (Meta)Modeling: Web- and Cloud- step towards efficient online collaboration by reformulating based Collaborative Tool Infrastructure. In 8th Multi-Paradigm Modeling Workshop, Valencia, Spain, 09/2014 2014. the permission assignment problem into a special class of [20] Obeo. Obeo designer team. https://www.obeodesigner.com/en/ Datalog programs that can be incrementally evaluated (taking collaborative-features. advantage of the priority hierarchy). We have also sketched a [21] Luigi Palopoli. Testing logic programs for local stratification. Theoret- ical Computer Science, 103(2):205 – 234, 1992. proof of correctness for the reformulation. As a quick proof [22] E. Prud’hommeaux and A. Seaborne. SPARQL query language for RDF. of concept 1 , we have implemented and evaluated queries 07 2016. according to this scheme for an example policy. [23] J. Di Rocco, D. Di Ruscio, L. Iovino, and A. Pierantonio. Collaborative repositories in model-driven engineering [software technology]. IEEE In the future, we plan to (a) implement an automated Software, 32(3):28–34, May 2015. translation from an arbitrary policy to such a query structure, [24] Kenneth A. Ross. Modular stratification and magic sets for datalog (b) set up benchmarks to study (and, if necessary, improve) programs with negation. J. ACM, 41(6):1216–1266, November 1994. [25] D. Di Ruscio, M. Franzago, I. Malavolta, and H. Muccini. Envisioning the performance of the solution in practice, (c) investigate the future of collaborative model-driven software engineering. In ICSE- incrementality with respect to policy changes. C’17, pages 219–221, May 2017. [26] Eugene Syriani, Hans Vangheluwe, Raphael Mannadiar, Conner Hansen, R EFERENCES Van Mierlo, and Huseyin Ergin. AToMPM: A Web-based Modeling [1] Fabian Abel et al. Enabling adanced and context-dependent access Environment. MODELS 2013 Demonstrations Track, 2013. control in RDF stores. In The Semantic Web, 6th Int. Semantic Web [27] The Eclipse Foundation. CDO. http://www.eclipse.org/cdo. Conf., 2nd Asian Semantic Web Conf., pages 1–14, 2007. [28] The Eclipse Foundation. EMFStore. http://www.eclipse.org/emfstore. [2] Axellience. GenMyModel. http://www.genmymodel.com. [29] The Eclipse Project. Eclipse Modeling Framework. http://www.eclipse. [3] Francesco Basciani, Juri Di Rocco, Davide Di Ruscio, Amleto Di Salle, org/emf/. Ludovico Iovino, and Alfonso Pierantonio. MDEForge: an extensible [30] Juha-Pekka Tolvanen. MetaEdit+: Domain-specific modeling and prod- web-based modeling platform. In CloudMDE@MoDELS, 2014. uct generation environment. In Software Product Lines, 11th Int. Conf. [4] Amine Benelallam, Abel Gómez, Gerson Sunyé, Massimo Tisi, and SPLC 2007, Kyoto, Japan, pages 145–146, 2007. David Launay. Neo4EMF, A scalable persistence layer for EMF models. [31] Zoltán Ujhelyi, Gábor Bergmann, Ábel Hegedüs, Ákos Horváth, In Modelling Foundations and Applications - 10th European Conf., Benedek Izsó, István Ráth, Zoltan Szatmári, and Dániel Varró. EMF- ECMFA 2014, pages 230–241, 2014. IncQuery: An integrated development environment for live model [5] Gábor Bergmann, István Dávid, Ábel Hegedüs, Ákos Horváth, István queries. Science of Computer Programming, (0):–, 2014. Ráth, Zoltán Ujhelyi, and Dániel Varró. Viatra 3: A reactive model [32] Jon Whittle, John Hutchinson, and Mark Rouncefield. The state of transformation platform. In Theory and Practice of Model Transforma- practice in model-driven engineering. IEEE Software, 31(3):79–85, tions - ICMT 2015, L’Aquila, Italy, July 20-21, pages 101–110, 2015. 2014. 1 Available at https://github.com/bergmanngabor/ CommitMDE17reproduction