=Paper=
{{Paper
|id=Vol-2019/commitmde_2
|storemode=property
|title=Towards Efficient Evaluation of Rule-based Permissions for Fine-grained Access Control in Collaborative Modeling
|pdfUrl=https://ceur-ws.org/Vol-2019/commitmde_2.pdf
|volume=Vol-2019
|authors=Gabor Bergman,Csaba Debreceni,Istvan Rath,Daniel Varro
|dblpUrl=https://dblp.org/rec/conf/models/BergmanDRV17
}}
==Towards Efficient Evaluation of Rule-based Permissions for Fine-grained Access Control in Collaborative Modeling==
https://ceur-ws.org/Vol-2019/commitmde_2.pdf
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