11institutetext: CRACS - INESCTEC
Porto, Portugal
11email<EMAIL_ADDRESS>

22institutetext: DCC-FCUP
University of Porto, Porto, Portugal
22email<EMAIL_ADDRESS>
# A Graphical Framework for the Category-Based Metamodel for Access Control
and Obligations††thanks: This work is financed by National Funds through the
Portuguese funding agency, FCT - Fundação para a Ciência e a Tecnologia,
within project UIDB/50014/2020.

Sandra Alves 1122 Jorge Iglésias 22

###### Abstract

We design a graph-based framework for the visualisation and analysis of
obligations in access control policies. We consider obligation policies in
CBACO, the category-based access control model, which has been shown to
subsume many of the most well known access control such as MAC, DAC, RBAC.
CBACO is an extension of the CBAC metamodel that deals with obligations. We
describe the implementation of the proposed model in PORGY, a strategy driven
graph-rewriting tool, based on the theory of port-graphs. CBACO policies allow
for dynamic behavior in the modelled systems, which is implemented using the
strategy language of PORGY.

Key Words: Security Policies, Access Control, Obligations, Rewriting

##  0.1 Introduction

The ability to efficiently protect resources from unauthorised access and to
preserve the integrity and confidentiality of critical data has never been
more crucial, leading to an increasing interest in models to effectively
control access to information and resources. However, despite the variety of
models, there is still a pressing need for effective methods and tools to
facilitate the tasks of policy specification and analysis. Formal
specifications of access control models and policies have used theorem
provers, purpose-built logics, functional approaches, etc, and although
textual languages and logic-based models are convenient for theoreticians or
computer experts, graphical models are more appealing to less technical users,
therefore urging the development of models that establish a bridge between
theoretical tools and the practitioners’ (mainly security administrators)
needs. The motivation for developing a graph-based framework is clear: graphs
are a natural model for distributed systems, with graphical languages being
widely used for describing complex structures in a visual and intuitive way in
a variety of domains (software modelling, representation of proofs,
microprocessor design, XML documents, communication networks, social networks,
biological systems, etc), while graph transformations, or graph rewriting, is
used to define the dynamic behaviour of the system modelled.

In this paper we develop a graph-based framework for the visualisation and
analysis of obligations in access control policies. Our basis will be CBACO
[2], an axiomatic metamodel for access control that deals with obligations in
a comprehensive way and which extends the CBAC metamodel [10] that subsumes
the most well-known access control models. The notion of obligation helps to
bridge a gap between requirements and policy enforcement. For example,
consider a hospital scenario in which any doctor may be authorised to read the
medical record of a patient in an emergency situation, but in that case there
is a requirement to inform the patient afterwards. Although access control
models deal mainly with authorisations, incorporating the notion of an
obligation facilitates the tasks of ensuring that obligations are enforced and
ensuring that obligations are compatible with authorisations. CBAC(O) focuses
on the notion of a _category_ , which is a class of entities that share some
property, and permissions are assigned to categories of users, rather than to
individual users. Categories can be defined on the basis of user attributes,
geographical constraints, resource attributes, etc. In this way, permissions
can change in an autonomous way unlike, e.g., role-based models, which require
the intervention of a security administrator. A graphical representation of
CBAC policies, including composed policies involving several local policies in
a multi-site system, was developed in [4], where static properties were
checked using basic graph properties on paths. However, to deal with realistic
scenarios one needs to be able to answer more complex and relevant questions,
based on static and/or dynamic information. In particular, there is a need for
tools to analyse the interactions between different policies which may deal
with different features of the system.

Taking the graphical model of CBAC as a basis, we develop a new graphical
model for CBACO and implement it using PORGY [6], a strategy driven graph-
rewriting tool based on the theory of port-graphs that provides a visual
modelling environment with specific simulation and verification tools, which
we believe to be well suited for the analysis of policies. PORGY is based on
the theory of port-graphs [5] and implements a strategy driven language for
port graph rewriting. In a port-graph, edges attach to nodes at specific
connection points called ports. Rules and rewriting strategies are also viewed
as port-graphs that can be rewritten into new rules, enabling the modelling of
adaptive systems. Port-graphs have been used to model complex systems in the
areas of biochemistry and interaction nets, as well as algorithm animation and
games. The main contributions of this work are:

  * •

We extend CBACO to deal with dynamic aspects of obligations;

  * •

We present a new graphical model for CBACO;

  * •

We implement our model using the PORGY framework, taking advantage of its
strategy driven graph-rewriting language to implement the dynamic aspects of
our graphical model.

_Overview:_ In Section 0.2, we recall the CBACO metamodel, extend it to deal
with the state of duties and briefly describe PORGY. Section 0.3 discusses a
graphical model for obligations, while Section 0.4 shows how our graphical
model is implemented in PORGY. In Section 0.5 we describe how the strategy
language of PORGY can be used to implement the dynamics of the modeled
systems. In Section 0.6, we discuss related work, and in Section 0.7,
conclusions are drawn and further work is suggested.

##  0.2 Preliminaries

We briefly describe below the key concepts underlying the metamodel for
category-based access control with obligations and the formalism of port-
graphs.

###  0.2.1 CBACO: Obligations in the category-based metamodel

The CBACO metamodel [2] is based on the notion of category. Informally, a
category is any of several distinct classes or groups to which entities may be
assigned. Entities are denoted by constants in a many sorted domain of
discourse, including: a countable set $\mathcal{C}$ of categories, denoted
$c_{0}$, $c_{1}$, $\dots$, a countable set $\mathcal{P}$ of principals,
denoted $p_{0}$, $p_{1}$, $\dots$, a countable set $\mathcal{A}$ of named
_actions_ , denoted $a_{0}$, $a_{1}$, $\dots$, a countable set $\mathcal{R}$
of _resource identifiers_ , denoted $r_{0}$, $r_{1}$, $\dots$, a finite set
$\mathcal{A}uth$ of possible _answers_ to access requests (e.g., {grant, deny,
undetermined}), a finite set $\mathcal{E}$ of events (denoted
$e_{1},e_{2},\dots$), a finite set $\mathcal{G}$ of event schemes (denoted
$ge_{1},ge_{2},\dots$) and a finite set $\mathcal{H}$ of event histories
(denoted $h_{1},h_{2},\dots$). More generally, entities can be represented by
a data structure (e.g., a principal could be represented by a term
$principal(p_{i},attributeList)$), but constants will be sufficient for most
examples in this paper. We start by defining some notions related to events,
permissions, prohibitions, authorisations and obligations. The definitions in
this subsection follow the notions defined in [2].

A (specific) event $e\in\mathcal{E}$ is a ground event specification
$\mathsf{spec}^{\emptyset}$, which represents an actual action/happening that
occurred in a system.

A generic event $ge\in\mathcal{G}$ represents a family of events and is given
by an event specification $\mathsf{spec}$111The definition of what an event
specification is, depends on the particular system., to which is associated a
context $ge[X_{1},\dots,X_{n}]$ where $X_{1},\dots,X_{n}$ are the term
variables in $\mathsf{spec}$. Replacing $X_{1},\dots,X_{n}$ with ground values
$v^{\emptyset}_{1},\dots,v^{\emptyset}_{n}$ will result in a ground event
specification $\mathsf{spec}^{\emptyset}$.

An event history $h\in\mathcal{H}$ is a possible sequence of events of the
system represented as a list of events of the form $[e_{1},\dots,e_{n}]$ where
every $e_{i}$ is associated to a specific time $t_{i}$ and such that if $i<j$
then $t_{i}\preceq t_{j}$, according to some notion of ordering on time. A
subsequence of $h$ is an event interval, denoted $I=(e_{i},e_{j},h)$, where
$e_{i}$ is the first event of the interval and $e_{j}$ is the last one. We say
that $e_{i}$ opens the interval and $e_{j}$ closes it. For every event $e_{k}$
in $h$ such that $t_{i}\preceq t_{k}\preceq t_{j}$ we say that
$e_{k}\in(e_{i},e_{j},h)$.

A permission is a pair $(a,r)$ of an action and a resource, and an
authorisation is a triple $(p,a,r)$ that associates a permission with a
principal.

A generic obligation $o\in\mathcal{O}$ is an action $a\in{\mathcal{A}}$ on a
resource $r\in{\mathcal{R}}$ that must be performed between two event schemes
$ge_{1},ge_{2}\in\mathcal{G}$, represented as a tuple $o=(a,r,ge_{1},ge_{2})$.
If there is no starting (resp. closing) event scheme, meaning the obligation
can be performed at any time before $ge_{2}$ (resp. after $ge_{1}$), then
$ge_{1}$ (resp. $ge_{2}$) is $\bot$. A specific/concrete obligation is an
obligation where the event schemes $ge_{1},ge_{2}$ are ground terms, therefore
corresponding to specific events. Like authorizations, obligations will be
assigned to categories, but these might not be the same as authorization
categories.

A duty $d\in\mathcal{D}$, is a tuple $(p,o)$, where $p$ is a principal, $o$ is
a concrete obligation $(a,r,e_{1},e_{2})$ such that there exists a generic
obligation $(a,r,ge_{1},ge_{2})$ assigned to $p$ and $e_{1},e_{2}$ are
instantiations of event schemes $ge_{1},ge_{2}$, respectively. If there is no
starting (resp. closing) event then $e_{1}$ (resp. $e_{2}$) is $\bot$.

The metamodel includes the following relations:

  * •

$\mathcal{P}\mathcal{C}\mathcal{A}$ $\subseteq\mathcal{P}\times\mathcal{C}$,
such that $(p,c)\in\mathcal{P}\mathcal{C}\mathcal{A}$ iff a principal
$p\in\mathcal{P}$ is assigned to the category $c\in\mathcal{C}$.

  * •

$\mathcal{A}\mathcal{R}\mathcal{C}\mathcal{A}$
$\subseteq\mathcal{A}\times\mathcal{R}\times\mathcal{C}$, such that
$(a,r,c)\in\mathcal{A}\mathcal{R}\mathcal{C}\mathcal{A}$ iff action
$a\in\mathcal{A}$ on resource $r\in\mathcal{R}$ can be performed by the
principals assigned to the category $c\in\mathcal{C}$.

  * •

$\mathcal{P}\mathcal{A}\mathcal{R}$
$\subseteq\mathcal{P}\times\mathcal{A}\times\mathcal{R}$, such that
$(p,a,r)\in\mathcal{P}\mathcal{A}\mathcal{R}$ iff a principal
$p\in\mathcal{P}$ can perform the action $a\in\mathcal{A}$ on the resource
$r\in\mathcal{R}$.

  * •

$\mathcal{BARCA}\subseteq{\mathcal{A}}\times{\mathcal{R}}\times{\mathcal{C}}$
is the prohibition-category assignment: $(a,r,c)\in\mathcal{BARCA}$ iff
members of category $c$ cannot perform action $a$ on resource $r$;

  * •

$\mathcal{BAR}\subseteq{\mathcal{P}}\times{\mathcal{A}}\times{\mathcal{R}}$ is
the prohibition-principal assignment: $(p,a,r)\in\mathcal{BAR}$ iff principal
$p$ cannot perform action $a$ on resource $r$;

  * •

$\mathcal{UNDET}\subseteq{\mathcal{P}}\times{\mathcal{A}}\times{\mathcal{R}}$
is the undetermined permission principal assignment:
$(p,a,r)\in\mathcal{UNDET}$ iff principal $p$ is neither authorized nor banned
from performing action $a$ on resource $r$;

  * •

$\mathcal{OCA}\subseteq\mathcal{O}\times{\mathcal{C}}$ is the obligation-
category assignment: $(o,c)\in\mathcal{OCA}$ iff there exists an obligation
$o=(a,r,ge_{1},ge_{2})$ such that principals of category $c$ are obliged to
perform action $a$ on resource $r$ between events that are instantiations of
event schemes $ge_{1}$ and $ge_{2}$;

  * •

$\mathcal{OPA}\subseteq{\mathcal{P}}\times\mathcal{O}$ is the obligation-
principal assignment: $(p,o)\in\mathcal{OPA}$ iff there exists an obligation
$o=(a,r,ge_{1},ge_{2})$ such that principal $p$ is obliged to perform action
$a$ on resource $r$ between events that are instantiations of event schemes
$ge_{1}$ and $ge_{2}$;

  * •

$\mathcal{DA}\subseteq\mathcal{D}$ is the duty assignment:
$d=(p,o)\in\mathcal{DA}$ iff there is a concrete obligation
$o=(a,r,e_{1},e_{2})$ such that principal $p$ is obliged to perform action $a$
on resource $r$ between events $e_{1}$ and $e_{2}$;

  * •

$\mathcal{ET}\subseteq\mathcal{E}\times\mathcal{G}$ is the event instantiation
relation: $(e,ge)\in\mathcal{ET}$ iff event $e$ is an instance of event scheme
$ge$, denoted $e::ge$, according to an instantiation relation between events
and event schemes;

  * •

$\mathcal{EI}\subseteq\mathcal{E}\times\mathcal{E}\times\mathcal{H}$ is the
event interval relation: $(e_{1},e_{2},h)\in\mathcal{EI}$ iff event $e_{2}$
closes the interval initiated by event $e_{1}$ in event history $h$.

The relations defined above satisfy the following axioms, where we assume that
there exists a partial ordering $\subseteq$ between authorisation categories
and a partial ordering $\subseteq_{\mathcal{O}}$ between obligation
categories:

$\forall p\in\mathcal{P},~{}\forall a\in\mathcal{A},~{}\forall
r\in\mathcal{R},\hfill(\exists
c,c^{\prime}\in\mathcal{C},((p,c)\in\mathcal{PCA}\wedge~{}c\subseteq
c^{\prime}~{}\wedge(a,r,c^{\prime})\in\mathcal{ARCA})\\\
\hfill\Leftrightarrow(p,a,r)\in\mathcal{PAR})$ (1) $\forall
p\in{\mathcal{P}},\forall a\in{\mathcal{A}},\forall
r\in{\mathcal{R}},((\exists
c,c^{\prime}\in{\mathcal{C}},(p,c)\in\mathcal{PCA}\wedge c^{\prime}\subseteq
c\wedge(a,r,c^{\prime})\in\mathcal{BARCA})\\\
\Leftrightarrow(p,a,r)\in\mathcal{BAR})$ (2) $\forall
p\in{\mathcal{P}},\forall a\in{\mathcal{A}},\forall
r\in{\mathcal{R}},(((p,a,r)\notin\mathcal{PAR}\wedge(p,a,r)\notin\mathcal{BAR})\\\
\Leftrightarrow(p,a,r)\in\mathcal{UNDET})$ (3)
$\mathcal{PAR}\cap\mathcal{BAR}=\emptyset$ (4) $\forall
o\in\mathcal{O}((\exists
c,c^{\prime}\in{\mathcal{C}},(p,c)\in\mathcal{PCA}\wedge
c\subseteq_{\mathcal{O}}c^{\prime}\wedge(o,c^{\prime})\in\mathcal{OCA})\Leftrightarrow(p,o)\in\mathcal{OPA})$
(5) $\forall p\in{\mathcal{P}},\forall a\in{\mathcal{A}},\forall
r\in{\mathcal{R}},\forall e_{1},e_{2}\in\mathcal{E},((\exists
ge_{1},ge_{2}\in\mathcal{G},(p,\overbrace{(a,r,ge_{1},ge_{2})}^{o})\in\mathcal{OPA},\\\
e_{1}::ge_{1},e_{2}::ge_{2})\Leftrightarrow\underbrace{(p,(a,r,e_{1},e_{2})}_{d})\in\mathcal{DA})$
(6)

###  0.2.2 State of Duties

Issued obligations, can be in one of four states: invalid, fulfilled, pending
or violated. This is unlike permissions, which are either issued or not. To
deal with that, we defined the following new relations to deal with the state
of duties:

  * •

Fulfilled:
$\mathcal{FULFILLED}\subseteq\mathcal{D}\times\mathcal{E}\times\mathcal{H}$,
such that $(d,e,h)\in\mathcal{FULFILLED}$ if the duty $d$ was fulfilled by the
event $e$ in history $h$.

  * •

Pending: $\mathcal{PENDING}\subseteq\mathcal{D}\times\mathcal{H}$, such that
$(d,h)\in\mathcal{PENDING}$ if the duty $d$ is pending in history $h$.

  * •

Violated: $\mathcal{VIOLATED}\subseteq\mathcal{D}\times\mathcal{H}$, such that
$(d,h)\in\mathcal{VIOLATED}$ if the duty $d$ is violated in history $h$.

We do not consider a relation on invalid duties, since our model does not
allow them to be issued. Furthermore, we introduce the following axioms
regarding the state of duties, where we assume that every history of events
starts with an event $\bot$.

$\begin{array}[]{l}\forall\overbrace{(p,a,r,e_{1},e_{2})}^{d}\in\mathcal{DA},\forall
h\in\mathcal{H}((e_{1}\in h,\\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \exists e_{3}\in
h,(e_{1},e_{3},h)\in\mathcal{EI},((e_{3},e_{2},h)\in\mathcal{EI}\vee(e_{1},e_{2},h)\notin\mathcal{EI}),\\\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
e_{3}.\textsf{subj}=p,e_{3}.\textsf{act}=a,e_{3}.\textsf{obj}=r)\Leftrightarrow(d,e_{3},h)\in\mathcal{FULFILLED})\\\
\forall\overbrace{(p,a,r,e_{1},e_{2})}^{d}\in\mathcal{DA},\forall
h\in\mathcal{H}((e_{1}\in h,(e_{1},e_{2},h)\notin\mathcal{EI},\nexists
e_{3}\in h,\\\ \ \ \ \ \ \
(e_{1},e_{3},h)\in\mathcal{EI},e_{3}.\textsf{subj}=p,e_{3}.\textsf{act}=a,e_{3}.\textsf{obj}=r)\Leftrightarrow(d,h)\in\mathcal{PENDING})\\\
\forall\overbrace{(p,a,r,e_{1},e_{2})}^{d}\in\mathcal{DA},\forall
h\in\mathcal{H}(((e_{1},e_{2},h)\in\mathcal{EI},\nexists
e_{3}\in(e_{1},e_{2},h),\\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\
e_{3}.\textsf{subj}=p,e_{3}.\textsf{act}=a,e_{3}.\textsf{obj}=r)\Leftrightarrow(d,h)\in\mathcal{VIOLATED})\end{array}$

###  0.2.3 PORGY

PORGY [6] is an interactive tool that has been developed to visualise and
analyse port graph reduction systems. Visually, a port graph is a graph where
edges are attached to nodes at points called _ports_. Below we give a brief
introduction to port graphs (see [5, 7] for more details and examples). We
assume a signature
$\Delta=\langle\Delta^{A},\mathcal{X}^{A},\Delta^{V},\mathcal{X}^{V}\rangle$
where $\Delta^{A}$ is a set of attributes; $\mathcal{X}^{A}$ is a set of
attribute variables; $\Delta^{V}$ is a set of values; and $\mathcal{X}^{V}$ is
a set of value variables.

We can represent elements of the graph as records (sets of pairs
$(\textit{attribute},\textit{value})$) over the signature $\Delta$. We assume
the attributes Name, Interface, Arity, Attach and Connect. Attribute Name
identifies records in the sense that if two records have the same value for
attribute Name then they have the same set of defined attributes, although
their values can differ.

A port graph over a signature $\Delta$ is defined as a tuple $G=\langle
N_{G},P_{G},E_{G},\mathcal{L}_{G}\rangle$ where: $N_{G}$ is a finite set of
nodes (denoted $n_{1},n_{2},\dots$); $P_{G}$ is a finite set of ports (denoted
$p_{1},p_{2},\dots$); $E_{G}$ is a finite set of undirected edges (denoted
$e_{1},e_{2},\dots$); $\mathcal{L}_{G}$ is a labeling function. For every
element of the sets described above, $\mathcal{L}_{G}$ returns the record
associated with it such that: for every node $n\in N_{G}$ the record contains
attribute Interface and $\mathcal{L}_{G}(n).\textit{Interface}$ returns the
set of ports of $n$; for every port $p\in P_{G}$ the record contains
attributes Attach and Arity, such that $\mathcal{L}_{G}(p).\textit{Arity}$
gives the number of edges connected to that port and
$\mathcal{L}_{G}(p).\textit{Attach}$ returns the node $n$ to which $p$
belongs; for every edge $e\in E_{G}$ the record contains attribute Connect and
$\mathcal{L}_{G}(e).\textit{Connect}$ returns $\\{p_{1},p_{2}\\}$ the ports
that $e$ is connected to.

A port graph rewrite rule is a port graph composed of two subgraphs, $L$ and
$R$, and a special node (called arrow node) that connects the two. It defines
a way of rewriting graphs in the sense that, if there is a instance of $L$, it
can be replaced by $R$ and the arrow node defines the way to reconnect $R$ to
the rest of the graph. Ports in the arrow node have attribute Type that can
have values bridge, blackhole or wire. These values define the rewriting in
the following way:

  * •

a port with Type bridge has exactly one edge connecting it to a port $p$ of
$L$ and one or more connecting it to ports $p_{i}$ of $R$. This type of port
defines that edges of the graph being rewritten that are connected to the
image of $p$ and are not in $L$ should be reconnected to every $p_{i}$;

  * •

there is at most one port with Type blackhole and it only has edges connected
to ports of $L$. It defines that edges connected to such ports should be
erased;

  * •

a port with Type wire has exactly two edges connecting it to two ports
$p_{1},p_{2}$ of $L$ and it defines that there should be created an edge
between every port $p_{1i}$ that is connected to the image of $p_{1}$ and
every port $p_{2i}$ that is connected to the image of $p_{2}$.

A rewrite rule $L\Rightarrow R$ matches a graph $G$ if there is a morphism $f$
such that $f(L)\subseteq G$ and the image of every port $p$ in $L$ not
connected to the arrow node is not connected to any port of $G\setminus f(L)$.
This last condition ensures that rewriting does not leave dangling edges.

Given a port graph $G$, a rewrite rule $L\Rightarrow R$ and a morphism $f$
such that $f(L)\subseteq G$, a rewriting step from $G$ by rule $L\Rightarrow
R$ and morphism $f$, denoted $G\rightarrow_{L\Rightarrow R}^{f}G^{\prime}$, is
defined as follows: the build phase: graph $f(R)$ is added to $G$; the
rewiring phase: edges connecting $G\setminus f(L)$ to $f(L)$ are connected to
$f(R)$ following the rules set by the arrow node; the deletion phase: $f(L)$
is erased obtaining $G^{\prime}$.

######  Example 1.

In Figure 1 the port-graph on the right is obtained from the port-graph on the
left, by applying the port-graph rewrite rule represented by the port-graph in
the middle222In this rule the top two nodes of L belong to $W$, the top two
nodes of R belong to $M$ and the bottom one to $N$..

Figure 1: Port Graph Rewriting

Given a set of rewrite rules and a graph, it will be possible to apply the
rules in different orders and places of the graph. To control that, PORGY uses
a strategy language. To define these strategies we start by defining the
notions of position and banned subgraphs of a located graph.

A located graph $G_{P}^{Q}$ is a graph such that $P\subseteq G$ is called the
position subgraph and $Q\subseteq G$ is the banned subgraph. This notion is
used in PORGY to select nodes, ports or edges where rewriting should happen
and where it cannot happen.

A located rewrite rule $L_{W}\Rightarrow R_{M}^{N}$ can be applied to a
located graph $G_{P}^{Q}$ by means of a morphism $f$ if: $f(L)\cap
Q=\emptyset$; $f(L)\cap P=W$, if $W$ is specified. In this case we write
$G_{P}^{Q}\rightarrow_{L_{W}\Rightarrow R_{M}^{N}}^{f}G_{P^{\prime}}^{\prime
Q^{\prime}}$ where $P^{\prime}=(P\setminus f(L))\cup f(M)$ and
$Q^{\prime}=Q\cup f(N)$.

In lay terms $W$ defines the elements of $L$ which images should be in the
position graph and $M$ (resp. $N$) defines the elements of $R$ which images
are to be added to the position (resp. banned) subgraph of $G^{\prime}$. In
PORGY we can use the strategy language to control both the way rewrite rules
are applied and the position and banned subgraphs (see [6] for a complete
description of PORGY’s strategy language).

##  0.3 Graph Representation of Obligations

We now define a graphical model for CBACO that extends the CBAC representation
using graphs presented in [4].

######  Definition 1 (CBACO policy graph).

A CBACO policy graph $G$ is a tuple $\langle N_{G},E_{G},ln,le\rangle$ with:

  * •

$N_{G}$ a finite set of nodes (denoted $n_{1},n_{2},\dots$);

  * •

$E_{G}$ a finite set of undirected edges (denoted $e_{1},e_{2},\dots$);

  * •

$ln:N_{G}\rightarrow\mathcal{REC}$ a labeling function for nodes such that for
every node $n\in N_{G}$,
$ln(n).ent\in{\mathcal{P}}\cup{\mathcal{C}}\cup{\mathcal{A}}\cup{\mathcal{R}}\cup\mathcal{G}\cup\mathcal{E}\cup({\mathcal{A}}\times{\mathcal{R}})\cup({\mathcal{A}}\times{\mathcal{R}}\times\mathcal{G}\times\mathcal{G})\cup({\mathcal{P}}\times{\mathcal{A}}\times{\mathcal{R}}\times\mathcal{E}\times\mathcal{E})$
and
$ln(n).type\in\\{P,C,A,R,\textit{G},\textit{E},P\textsubscript{{r}},\textit{O},\textit{D}\\}$
where:

    * –

$ln(n).type=P$ iff $ln(n).ent=p\in{\mathcal{P}}$;

    * –

$ln(n).type=C$ iff $ln(n).ent=c\in{\mathcal{C}}$;

    * –

$ln(n).type=A$ iff $ln(n).ent=a\in{\mathcal{A}}$;

    * –

$ln(n).type=R$ iff $ln(n).ent=r\in{\mathcal{R}}$;

    * –

$ln(n).type=\textit{G}$ iff $ln(n).ent=ge\in\mathcal{G}$;

    * –

$ln(n).type=\textit{E}$ iff $ln(n).ent=e\in\mathcal{E}$;

    * –

$ln(n).type=P\textsubscript{{r}}$ iff
$ln(n).ent=(a,r)\in{\mathcal{A}}\times{\mathcal{R}}$;

    * –

$ln(n).type=\textit{O}$ iff
$ln(n).ent=(a,r,ge_{1},ge_{2})\in{\mathcal{A}}\times{\mathcal{R}}\times\mathcal{G}\times\mathcal{G}$;

    * –

$ln(n).type=\textit{D}$ iff
$ln(n).ent=(p,a,r,e_{1},e_{2})\in{\mathcal{P}}\times{\mathcal{A}}\times{\mathcal{R}}\times\mathcal{E}\times\mathcal{E}$;

  * •

$le:E_{G}\rightarrow\mathcal{REC}$ a labeling function for edges such that for
every edge $e\in E_{G}$, $le(e).adj=\\{n_{1},n_{2}\\}$ gives the two nodes
connected by the edge. We also define the function $type$ such that
$type(e)=\\{ln(n_{1}).type,ln(n_{2}).type\\}$. Furthermore if:

    * –

$type(e)=CC$ then
$le(e).\textit{target}\subseteq\\{ln(n_{1}).ent,ln(n_{2}).ent\\}$ and
$le(e).auth,le(e).obl\in\\{\top,\bot\\}$ ;

    * –

$type(e)=CP\textsubscript{{r}}$ then $le(e).auth\in\\{A,B\\}$;

    * –

$type(e)=\textit{O}\textit{G}$ then $le(e).ge\in\\{i,f\\}$;

    * –

$type(e)=\textit{D}\textit{E}$ then $le(e).ev\in\\{i,f\\}$;

    * –

$type(e)=\textit{G}\textit{G}$ then
$le(e).\textit{target}\in\\{ln(n_{1}).ent,ln(n_{2}).ent\\}$;

    * –

$type(e)=\textit{E}\textit{E}$ then
$le(e).\textit{target}\in\\{ln(n_{1}).ent,ln(n_{2}).ent\\}$;

Nodes of type E have an attribute $now$ set to either $\top$ or $\bot$. Only
one node of type E can have $now$ set to $\top$, which specifies what is the
current event. Nodes of type O represent obligations and are always connected
to a node of type $P\textsubscript{{r}}$ and zero, one or two nodes of type G.
Other connections will be to nodes of type $C$. Nodes of type D represent
duties and are always connected to a node of type $P$ a node of type
$P\textsubscript{{r}}$ and zero, one or two nodes of type $E$.

Because we represent both $\subseteq$ and $\subseteq_{\mathcal{O}}$ there is
the need to distinguish edges of type $CC$. Edges $e$ that represent the
$\subseteq$ (resp. $\subseteq_{\mathcal{O}}$) will have the $auth$ (resp.
$obl$) attribute value set to $\top$ and we write
$type(e)=CC_{P\textsubscript{{r}}}$ (resp. $type(e)=CC_{\textit{O}}$).
Edges $e$ of type CPr serve the same purpose of the edges of type CA in the
graph representation of CBAC in [4] and for that reason have attribute $auth$
defined as either $A$ or $B$ and we will write
$type(e)=\textit{CP\textsubscript{{r}}}^{A}$ and
$type(e)=\textit{CP\textsubscript{{r}}}^{B}$, respectively, to distinguish
edges corresponding to authorizations/prohibitions.

Edges of type OG (resp. DE) have the $ge$ (resp. $ev$) attribute value set to
either $i$ or $f$ to distinguish between the initial and final event scheme
(resp. event). Edges of type GG are used to represent the notion that some
event schemes are instantiations of other event schemes and have attribute
target set to the node that represents the event scheme that is more general
(the one which the other is an instantiation of). Furthermore, the type of
this edges when in terms of types of paths will have an arrow on top in the
same way edges of type $CC$ have. Edges of type EE connect events of the same
history and have attribute target set to the node that represents the one
event that comes after the other. As edges of type $CC$ and GG the type of
this edges in paths will have an arrow on top.

######  Definition 2 (Path).

Given a policy graph $G=\langle N_{G},E_{G},ln,le\rangle$ a path of length $d$
is a sequence of pairwise distinct nodes $n_{0},n_{1},\dots,n_{d}$ such that
for every $1\leq i\leq d$, $le(e).adj=\\{n_{i-1},n_{i}\\}$ for some $e\in
E_{G}$.

######  Definition 3 (Constrained path and constrained reverse path).

A constrained path of length $d$ is a sequence
$n_{0},e_{1},n_{1},\dots,e_{d},n_{d}$, with pairwise distinct nodes and edges
such that for every $1\leq i\leq d$, $le(e_{i})=\\{n_{i-1},n_{i}\\}$ and
$n_{i}\in le(e_{i}).\textit{target}$ when $le(e_{i}).\textit{target}$ exists.
A constrained inverse path of length $d$ is a sequence
$n_{0},e_{1},n_{1},\dots,e_{d},n_{d}$ with pairwise distinct nodes and edges
such that for every $1\leq i\leq d$, $le(e_{i})=\\{n_{i-1},n_{i}\\}$ and
$n_{i-1}\in le(e_{i}).\textit{target}$ when $le(e_{i}).\textit{target}$
exists.

######  Definition 4 (Types of paths).

Consider a path $n_{0},n_{1},\dots,n_{d}$ of length $d$ such that
$ln(n_{i}).type=T_{i}$ for every $0\leq i\leq d$. The type of this path is
given by the types of its edges $T_{0}T_{1},T_{1}T_{2},\dots,T_{d-1}T_{d}$.
The notation
$type(n_{0},n_{1},\dots,n_{d})=T_{0}T_{1},T_{1}T_{2},\dots,T_{d-1}T_{d}$ is
used to denote that there is a path $n_{0},n_{1},\dots,n_{d}$ and its edges
are of type $T_{0}T_{1},T_{1}T_{2},\dots,T_{d-1}T_{d}$.
If an edge $e_{i}$ of the path is connecting two nodes $n_{i-1}$ and $n_{i}$
both of type $C$ then its type will be $\overrightarrow{CC}$ if $n_{i}\in
le(e_{i}).\textit{target}$ and $\overleftarrow{CC}$ if $n_{i-1}\in
le(e_{i}).\textit{target}$.

Note that an edge might be both of type $\overrightarrow{CC}$ and
$\overleftarrow{CC}$.

######  Definition 5 (Redundant edges in the CBACO policy graph).

Consider a CBACO policy graph $G=\langle N_{G},E_{G},ln,le\rangle$. An edge
$e\in E_{G}$ is redundant if:

  * •

$type(e)=PC$, i.e. it connects nodes $n_{1},n_{2}$ such that $ln(n_{1}).ent=p$
and $ln(n_{2}).ent=c$ with $p\in{\mathcal{P}}$, $c\in{\mathcal{C}}$, and there
is a path of type $PC,(\overrightarrow{CC})^{*}$ and length greater or equal
to 2 connecting $n_{1}$ and $n_{2}$;

  * •

$type(e)=\overrightarrow{CC}_{P}\textsubscript{{r}}$, i.e. it connects nodes
$n_{1},n_{2}$ such that $ln(n_{1}).ent=c_{1}$ and $ln(n_{2}).ent=c_{2}$ with
$c_{1},c_{2}\in{\mathcal{C}}$ and $le(e).auth=\top$, and there is a path of
type $(\overrightarrow{CC}_{P\textsubscript{{r}}})^{*}$ and length greater or
equal to 2 connecting $n_{1}$ and $n_{2}$;

  * •

$type(e)=\overrightarrow{CC}_{\textit{O}}$, i.e. it connects nodes
$n_{1},n_{2}$ such that $ln(n_{1}).ent=c_{1}$ and $ln(n_{2}).ent=c_{2}$ with
$c_{1},c_{2}\in{\mathcal{C}}$ and $le(e).obl=\top$, and there is a path of
type $(\overrightarrow{CC}_{\textit{O}})^{*}$ and length greater or equal to 2
connecting $n_{1}$ and $n_{2}$;

  * •

$type(e)=\textit{CP\textsubscript{{r}}}^{A}$, i.e. it connects nodes
$n_{1},n_{2}$ such that $ln(n_{1}).ent=c$ and $ln(n_{2}).ent=(a,r)$ with
$c\in{\mathcal{C}}$, $(a,r)\in{\mathcal{A}}\times{\mathcal{R}}$ and
$le(e).auth=A$, and there is a path of type
$(\overrightarrow{CC}_{P\textsubscript{{r}}})^{*},\textit{CP\textsubscript{{r}}}^{A}$
and length greater or equal to 2 connecting $n_{1}$ and $n_{2}$;

  * •

$type(e)=\textit{CP\textsubscript{{r}}}^{B}$, i.e. it connects nodes
$n_{1},n_{2}$ such that $ln(n_{1}).ent=c$ and $ln(n_{2}).ent=(a,r)$ with
$c\in{\mathcal{C}}$, $(a,r)\in{\mathcal{A}}\times{\mathcal{R}}$ and
$le(e).auth=B$, and there is a path of type
$(\overleftarrow{CC}_{P\textsubscript{{r}}})^{*},\textit{CP\textsubscript{{r}}}^{B}$
and length greater or equal to 2 connecting $n_{1}$ and $n_{2}$;

  * •

$type(e)=\textit{C{O}}$, i.e. it connects nodes $n_{1},n_{2}$ such that
$ln(n_{1}).ent=c$ and $ln(n_{2}).ent=(a,r,ge_{1},ge_{2})$ with
$c\in{\mathcal{C}}$,
$(a,r,ge_{1},ge_{2})\in{\mathcal{A}}\times{\mathcal{R}}\times\mathcal{G}\times\mathcal{G}$,
and there is a path of type
$(\overrightarrow{CC}_{\textit{O}})^{*},\textit{C{O}}$ and length greater or
equal to 2 connecting $n_{1}$ and $n_{2}$;

  * •

$type(e)=\textit{E}\textit{G}$, i.e. it connects nodes $n_{1},n_{2}$ such that
$ln(n_{1}).ent=e$ and $ln(n_{2}).ent=ge$ with $e\in\mathcal{E}$,
$ge\in\mathcal{G}$, and there is a path of type
$\textit{E}\textit{G},(\overrightarrow{\textit{G}\textit{G}})^{*}$ and length
greater or equal to 2 connecting $n_{1}$ and $n_{2}$;

  * •

$type(e)=\overrightarrow{\textit{G}\textit{G}}$, i.e. it connects nodes
$n_{1},n_{2}$ such that $ln(n_{1}).ent=ge_{1}$ and $ln(n_{2}).ent=ge_{2}$ with
$ge_{1},ge_{2}\in\mathcal{G}$ and $ge_{2}\in le(e).\textit{target}$, and there
is a path of type $(\overrightarrow{\textit{G}\textit{G}})^{*}$ and length
greater or equal to 2 connecting $n_{1}$ and $n_{2}$.

######  Definition 6 (Well-formed CBACO policy graph).

A CBACO policy graph $G$ is well-formed iff for every $n_{1},n_{2}\in N_{G}$
if $ln(n_{1}).ent=ln(n_{2}).ent$ and $ln(n_{1}).type=ln(n_{2}).type$ then
$n_{1}=n_{2}$, and for every $e_{1},e_{2}\in E_{G}$ if
$le(e_{1}).adj=le(e_{2}).adj$ then either $e_{1}=e_{2}$ or $e_{1},e_{2}$ have
type CPr and $le(e_{1}).auth\neq le(e_{2}).auth$, for every $e\in E_{G}$ with
$le(e).adj=\\{n_{1},n_{2}\\}$ one of the following is true:

  * •

$ln(n_{1}).type=P\wedge ln(n_{2}).type=C$;

  * •

$ln(n_{1}).type=C\wedge ln(n_{2}).type=C\wedge
le(e).\textit{target}\subseteq\\{ln(n_{1}).ent,ln(n_{2}).ent\\}\wedge
le(e).auth,le(e).obl\in\\{\top,\bot\\}$;

  * •

$ln(n_{1}).type=C\wedge ln(n_{2}).type=P\textsubscript{{r}}\wedge
le(e).auth\in\\{A,B\\}$;

  * •

$ln(n_{1}).type=C\wedge ln(n_{2}).type=\textit{O}$;

  * •

$ln(n_{1}).type=P\textsubscript{{r}}\wedge ln(n_{2}).type=A\wedge
ln(n_{1}).ent=(a,r)\wedge ln(n_{2}).ent=a$;

  * •

$ln(n_{1}).type=P\textsubscript{{r}}\wedge ln(n_{2}).type=R\wedge
ln(n_{1}).ent=(a,r)\wedge ln(n_{2}).ent=r$;

  * •

$ln(n_{1}).type=\textit{O}\wedge ln(n_{2}).type=P\textsubscript{{r}}\wedge
ln(n_{2}).ent=(a,r)\wedge ln(n_{1}).ent=(a,r,ge_{1},ge_{2})$;

  * •

$ln(n_{1}).type=\textit{O}\wedge ln(n_{2}).type=\textit{G}\wedge
ln(n_{1})=(a,r,ge_{1},ge_{2})\wedge((le(e).ge=i\wedge
ln(n_{2}).ent=ge_{1})\vee(le(e).ge=f\wedge ln(n_{2}).ent=ge_{2}))$;

  * •

$ln(n_{1}).type=\textit{D}\wedge ln(n_{2}).type={\mathcal{P}}\wedge
ln(n_{2}).ent=p\wedge ln(n_{1}).ent=(p,a,r,e_{1},e_{2})$;

  * •

$ln(n_{1}).type=\textit{D}\wedge ln(n_{2}).type=P\textsubscript{{r}}\wedge
ln(n_{2}).ent=(a,r)\wedge ln(n_{1}).ent=(p,a,r,e_{1},e_{2})$;

  * •

$ln(n_{1}).type=\textit{D}\wedge ln(n_{2}).type=\textit{E}\wedge
ln(n_{1})=(p,a,r,e_{1},e_{2})\wedge((le(e).e=i\wedge
ln(n_{2}).ent=e_{1})\vee(le(e).e=f\wedge ln(n_{2}).ent=e_{2}))$;

  * •

$ln(n_{1}).type=\textit{E}\wedge ln(n_{2}).type=\textit{E}\wedge
le(e).\textit{target}\in\\{ln(n_{1}).ent,ln(n_{2}).ent\\}$;

  * •

$ln(n_{1}).type=\textit{E}\wedge ln(n_{2}).type=P$;

  * •

$ln(n_{1}).type=\textit{E}\wedge ln(n_{2}).type=A$;

  * •

$ln(n_{1}).type=\textit{E}\wedge ln(n_{2}).type=R$;

  * •

$ln(n_{1}).type=\textit{E}\wedge ln(n_{2}).type=\textit{G}$;

  * •

$ln(n_{1}).type=\textit{G}\wedge ln(n_{2}).type=\textit{G}\wedge
le(e).\textit{target}\in\\{ln(n_{1}).ent,ln(n_{2}).ent\\}$;

and there are no redundant edges. Moreover if a constrained path and an
inverse constrained path begin in the same node with type $P$ and end in nodes
of type $P\textsubscript{{r}}$ such that the last edges of the paths are of
type $\textit{CP\textsubscript{{r}}}^{A}$ and
$\textit{CP\textsubscript{{r}}}^{B}$, respectively, then the end node must be
different. This means that a principal cannot be both able and unable to
perform an action on a resource.

A graph $G$ defines a particular CBACO policy.

######  Definition 7 ($\mbox{CBACO}_{G}$).

Given a well-formed policy graph $G=\langle N_{G},E_{G},ln,le\rangle$ the
CBACO policy defined by $G$ is defined by the following entities and
relations:

  * •

${\mathcal{P}}_{G}=\\{ln(n).ent\mid n\in N_{G}\wedge ln(n).type=P\\}$;

  * •

${\mathcal{C}}_{G}=\\{ln(n).ent\mid n\in N_{G}\wedge ln(n).type=C\\}$;

  * •

${\mathcal{A}}_{G}=\\{ln(n).ent\mid n\in N_{G}\wedge ln(n).type=A\\}$;

  * •

${\mathcal{R}}_{G}=\\{ln(n).ent\mid n\in N_{G}\wedge ln(n).type=R\\}$;

  * •

$\subseteq=\\{(ln(n_{1}).ent,ln(n_{i}).ent)\mid\exists
n_{2},\dots,n_{i},type(n_{1},n_{2},\dots,n_{i})=(\overrightarrow{CC}_{P\textsubscript{{r}}})^{*}\\}$;

  * •

$\subseteq_{\mathcal{O}}=\\{(ln(n_{1}).ent,ln(n_{i}).ent)\mid\exists
n_{2},\dots,n_{i},type(n_{1},n_{2},\dots,n_{i})=(\overrightarrow{CC}_{\textit{O}})^{*}\\}$;

  * •

$\mathcal{E}_{G}=\\{ln(n).ent\mid n\in N_{G}\wedge ln(n).type=\textit{E}\\}$;

  * •

$\mathcal{G}_{G}=\\{ln(n).ent\mid n\in N_{G}\wedge ln(n).type=\textit{G}\\}$;

  * •

$\mathcal{H}_{G}=\\{[ln(n_{1}).ent,\dots,ln(n_{i}).ent]\mid
type(n_{1},\dots,n_{i})=(\overrightarrow{\textit{E}\textit{E}})^{*}\\}$;

  * •

$\mathcal{PCA}_{G}=\\{(ln(n_{1}).ent,ln(n_{2}).ent)\mid
type(n_{1},n_{2})=PC\\}$;

  * •

$\mathcal{ARCA}_{G}=\\{(a,r,ln(n_{1}).ent)\mid
type(n_{1},n_{2})=\textit{CP\textsubscript{{r}}}^{A}\wedge
ln(n_{2}).ent=(a,r)\\}$;

  * •

$\mathcal{PAR}_{G}=\\{(ln(n_{1}).ent,a,r)\mid\exists
n_{21},\dots,n_{2i},type(n_{1},n_{21},\dots,n_{2i},n_{3})=PC,(\overrightarrow{CC}_{P\textsubscript{{r}}})^{*},\textit{CP\textsubscript{{r}}}^{A}\wedge
ln(n_{3}).ent=(a,r)\\}$;

  * •

$\mathcal{BARCA}_{G}=\\{(a,r,ln(n_{1}).ent)\mid
type(n_{1},n_{2})=\textit{CP\textsubscript{{r}}}^{B}\wedge
ln(n_{2}).ent=(a,r)\\}$;

  * •

$\mathcal{BAR}_{G}=\\{(ln(n_{1}).ent,a,r)\mid\exists
n_{21},\dots,n_{2i},type(n_{1},n_{21},\dots,n_{2i},n_{3})=PC,(\overleftarrow{CC}_{P\textsubscript{{r}}})^{*},\textit{CP\textsubscript{{r}}}^{B}\wedge
ln(n_{3}).ent=(a,r)\\}$;

  * •

$\mathcal{UNDET}_{G}=\\{(ln(n_{1}).ent,ln(n_{2}).ent,ln(n_{3}).ent)\mid
ln(n_{1}).type=P,ln(n_{2}).type=A,ln(n_{3}).type=R\\}\setminus(\mathcal{PAR}_{G}\cup\mathcal{BAR}_{G})$;

  * •

$\mathcal{OCA}_{G}=\\{(a,r,ge_{1},ge_{2},ln(n_{1}).ent)\mid
type(n_{1},n_{2})=\textit{C{O}}\wedge ln(n_{2}).ent=(a,r,ge_{1},ge_{2})\\}$;

  * •

$\mathcal{OPA}_{G}=\\{(ln(n_{1}).ent,a,r,ge_{1},ge_{2})\mid\exists
n_{21},\dots,n_{2i},type(n_{1},n_{21},\dots,n_{2i},n_{3})=PC,(\overrightarrow{CC}_{\textit{O}})^{*},\textit{C{O}}\wedge
ln(n_{3}).ent=(a,r,ge_{1},ge_{2})\\}$;

  * •

$\mathcal{DA}_{G}=\\{ln(n).ent\mid n\in N_{G}\wedge ln(n).type=\textit{D}\\}$;

  * •

$\mathcal{ET}_{G}=\\{(ln(n_{1}).ent,ln(n_{2i}).ent)\mid\exists
n_{21},\dots,n_{2i},type(n_{1},n_{21},\dots,n_{2i})=\textit{E}\textit{G},(\overrightarrow{\textit{G}\textit{G}})^{*}\\}$;

  * •

$\mathcal{EI}_{G}=\\{(ln(n_{j}).ent,ln(n_{k}).ent,[ln(n_{1}).ent,\dots,ln(n_{i}).ent])\mid
type(n_{1},\dots,n_{i})=(\overrightarrow{\textit{E}\textit{E}})^{*}\wedge
1\leq j<k\leq i\\}$.

##  0.4 Representing Obligations in PORGY

We now describe how to implement the graphical representation of CBACO using
PORGY. We start by describing our choices regarding the representation of the
entities and the relations in the policies.

#### Entities

Entities are represented as nodes of the graph, their viewLabel will be the
same as $ent$ and the shape will be determined by the $type$. The number of
ports is also determined by the $type$ of the entity. With the exception of
edges representing the $\subseteq$ and $\subseteq_{\mathcal{O}}$ relations
between categories, the order of events in a history and the instantiation
relation between event schemes, every other edge is undirected. Therefore,
nodes of type $C$, E and G will have three ports while the others only have
one. The extra two ports (which have viewLabel In and Out) on these nodes are
used to make the direction of the relation visually explicit. These properties
are summarized in Table 1.

type | viewShape | number of ports
---|---|---
$P$ | Pentagon | 1
$C$ | Triangle | 3
$P\textsubscript{{r}}$ | Hexagon | 1
$A$ | Square | 1
$R$ | Diamond | 1
O | Hexagon | 1
D | Hexagon | 1
E | Circle | 3
G | Ring | 3
Table 1: Properties of nodes in a CBACO representation

#### Relations

Relations are represented as edges of the graph. The viewColor of edges is
gray except for edges of type CPr, OG and DE. Edges of type CPr are green if
its auth is $A$ and red if it is $B$ and edges of type OG (resp. DE) will be
green if $ge$ (resp. $ev$) is $i$ and red if it is $f$. Edges of type $CC$, GG
and EE will connect to the extra ports of nodes with $type$ $C$, G and E,
respectively, connecting to the In port if the $ent$ of the node is in the
target of the edge or to the Out port otherwise.

#### Color coding

In order to distinguish categories that belong to the permission/prohibition
subgraph from the ones that belong to the obligation subgraph and the ones
that are used in both, a color coding is used. This color coding was then
extended to every type of node in order to make the graph more informative.
The coding is simple, if a node belongs solely to the permission/prohibition
subgraph then its color is yellow, if it belongs solely to the obligation
subgraph then its color is blue and if it belongs to both then its color is
green. We use the color also to make explicit which of the event nodes has its
$now$ set to $\top$ by setting its color to a lighter blue.

######  Example 2.

In Figure 2 we have the graphical representation of a CBACO policy such that:

  * •

${\mathcal{P}}=\\{\textit{J. Dorian},\textit{C. Tuck}\\}$;

  * •

${\mathcal{C}}=\\{\textit{Dr(J. Lewis)},\textit{Dr(F. Mason)}\\}$;

  * •

${\mathcal{A}}=\\{\textit{Read},\textit{Declare}\\}$;

  * •

${\mathcal{R}}=\\{\textit{Rec(J. Lewis)},\textit{Rec(F. Mason)},\textit{Admin-
log}\\}$;

  * •

$\subseteq=\emptyset$;

  * •

$\subseteq_{\mathcal{O}}=\emptyset$;

  * •

$\mathcal{E}=\\{\\{\textsf{act}=\textit{Read},\textsf{subj}=\textit{C.
Tuck},\textsf{obj}=\textit{Rec(J.
Lewis)},\textsf{time}=120\\},\\{\textsf{act}=\textit{Declare},\textsf{subj}=\textit{C.
Tuck},\textsf{obj}=\textit{Admin-log},\textsf{time}=200\\}\\}$;

  * •

$\mathcal{G}=\\{\textit{gen\\_read}[\textit{J. Dorian},\textit{F.
Mason}],\textit{gen\\_read}[\textit{C. Tuck},\textit{J. Lewis}]\\}$;

  * •

$\mathcal{H}=\\{[\\{\textsf{act}=\textit{Read},\textsf{subj}=\textit{C.
Tuck},\textsf{obj}=\textit{Rec(J.
Lewis)},\textsf{time}=120\\},\\{\textsf{act}=\textit{Declare},\textsf{subj}=\textit{C.
Tuck},\textsf{obj}=\textit{Admin-log},\textsf{time}=200\\}]\\}$;

  * •

$\mathcal{PCA}=\\{(\textit{J. Dorian},\textit{Dr(J. Lewis)}),(\textit{C.
Tuck},\textit{Dr(F. Mason)})\\}$;

  * •

$\mathcal{ARCA}=\\{(\textit{Read},\textit{Rec(F. Mason)},\textit{Dr(F.
Mason)}),(\textit{Read},\textit{Rec(J. Lewis)},\textit{Dr(J. Lewis)})\\}$;

  * •

$\mathcal{PAR}=\\{(\textit{J. Dorian},\textit{Read},\textit{Rec(J.
Lewis)}),(\textit{C. Tuck},\textit{Read},\textit{Rec(F. Mason)})\\}$;

  * •

$\mathcal{BARCA}=\emptyset$;

  * •

$\mathcal{BAR}=\emptyset$;

  * •

$\mathcal{UNDET}=\\{(\textit{C. Tuck},\textit{Read},\textit{Rec(J.
Lewis)}),(\textit{J. Dorian},\textit{Declare},\textit{Rec(J. Lewis)}),\\\
(\textit{C. Tuck},\textit{Declare},\textit{Rec(J. Lewis)}),(\textit{J.
Dorian},\textit{Read},\textit{Rec(F. Mason)}),\\\ (\textit{J.
Dorian},\textit{Declare},\textit{Rec(F. Mason)}),(\textit{C.
Tuck},\textit{Declare},\textit{Rec(F. Mason)}),\\\ (\textit{J.
Dorian},\textit{Read},\textit{Admin-log}),(\textit{C.
Tuck},\textit{Read},\textit{Admin-log}),\\\ (\textit{J.
Dorian},\textit{Declare},\textit{Admin-log}),(\textit{C.
Tuck},\textit{Declare},\textit{Admin-log})\\}$;

  * •

$\mathcal{OCA}=\\{(\textit{Declare},\textit{Admin-
log},\textit{gen\\_read}[\textit{J. Dorian},\textit{F.
Mason}],\bot,\textit{Dr(J. Lewis)}),\\\ (\textit{Declare},\textit{Admin-
log},\textit{gen\\_read}[\textit{C. Tuck},\textit{J.
Lewis}],\bot,\textit{Dr(F. Mason)})\\}$;

  * •

$\mathcal{OPA}=\\{(\textit{J. Dorian},\textit{Declare},\textit{Admin-
log},\textit{gen\\_read}[\textit{J. Dorian},\textit{F. Mason}],\bot),\\\
(\textit{C. Tuck},\textit{Declare},\textit{Admin-
log},\textit{gen\\_read}[\textit{C. Tuck},\textit{J. Lewis}],\bot)\\}$;

  * •

$\mathcal{DA}=\\{(\textit{C. Tuck},\textit{Declare},\textit{Admin-
log},\\{\textsf{act}=\textit{Read},\textsf{subj}=\textit{C.
Tuck},\textsf{obj}=\textit{Rec(J. Lewis)},\textsf{time}=120\\},\bot)\\}$;

  * •

$\mathcal{ET}=\\{(\\{\textsf{act}=\textit{Read},\textsf{subj}=\textit{C.
Tuck},\textsf{obj}=\textit{Rec(J. Lewis)}\\},\\\
\textit{gen\\_read}[\textit{C. Tuck},\textit{J. Lewis}])\\}$;

  * •

$\mathcal{EI}=\\{(\\{\textsf{act}=\textit{Read},\textsf{subj}=\textit{C.
Tuck},\textsf{obj}=\textit{Rec(J.
Lewis)},\textsf{time}=120\\},\\{\textsf{act}=\textit{Declare},\textsf{subj}=\textit{C.
Tuck},\textsf{obj}=\textit{Admin-
log},\textsf{time}=200\\},[\\{\textsf{act}=\textit{Read},\textsf{subj}=\textit{C.
Tuck},\textsf{obj}=\textit{Rec(J. Lewis)},\textsf{time}=120\\},\\\
\\{\textsf{act}=\textit{Declare},\textsf{subj}=\textit{C.
Tuck},\textsf{obj}=\textit{Admin-log},\textsf{time}=200\\}])\\}$.

Note that the duty is not represented in the graph, this is due to the fact
that we use rewrite rules and the strategy language to instantiate and update
the state of duties in a history of events. This process is shown in Example
3.

Figure 2: CBACO policy representation

##  0.5 The Dynamics of Obligations in PORGY

A key point of CBACO policies is that the assignment of principals,
permissions, prohibitions and obligations to categories is not static, it
depends on the system state. We will now see how we can use rewrite rules and
the strategy language to ensure that relations on the graph are correct. These
rules fall into two main groups, the rules that are general to every CBACO
policy and will not change the policy itself (the ones associated with queries
and obligations), and the rules that are scenario specific and will change the
policy.

###  0.5.1 Scenario-specific rewrite rules

This category covers a wide variety of rules that are dependant on the policy.
Their purpose is to represent the dynamics specific to the policy: ways of
creating/removing entities, updating relations or constraints of the policy.
They can be triggered either by events or by changes in the state.

    ΨΨsetBan(all(property(crtGraph,node,type=="P")));
    ΨΨwhile(not(isEmpty(crtBan)))do(
    ΨΨ  setPos(one(crtBan));
    ΨΨ  setBan(all(crtBan\crtPos));
    ΨΨ  setPos(all(crtPos[cup]ngb(crtPos,edge,type=="PC")));
    ΨΨ  while(one(auxPC))do(
    ΨΨ    repeat(one(auxPC));
    ΨΨ    setPos(all(
    ΨΨ    property(crtPos,node,type=="P")[cup]property(crtBan,node,type=="C")
    ΨΨ    ));
    ΨΨ    setBan(all(property(crtBan,node,type=="P")))
    ΨΨ))

Figure 3: A strategy for applying rule auxPC

###  0.5.2 General rewrite rules

Inside the scope of these rewrite rules we have: auxiliary rules that extract
information used in other rules; rules related to the treatment of
obligations; and rules related to visualisation and queries.

#### Auxiliary rewrite rules

Their purpose is to make implicit relations explicit, nonetheless, they will
be invisible so they can be used in rewrite rules but will not appear in the
graph visualization. Note that a policy graph does not contain redundant
edges. However, redundant edges are often necessary to establish relations
(for example, principal-category relations in the presence of the $\subseteq$
relation on categories). All the auxiliary edges will have attribute aux set
to true.

The rule in Figure 1, named auxPC, is an example of a port-graph rule used to
build auxiliary edges. Using the strategy language of PORGY this rule can be
used exhaustively, until no more new edges of type $PC$ are created (see
Figure 3 for a script implementing this strategy).

#### Obligation rewrite rules

Obligation rewrite rules will concern the dynamics of duties and its states.
In this category of rules we have rules to deal with instantiating duties and
rules for every possible update of the state of a duty. Also in this category
we put the rules concerning the iteration of events, this is due to the fact
that, although they could also be necessary for the scenario-specific rules,
they are central to the calculation of duties and their states.

######  Example 3.

(a) After first event is processed

(b) After both events are processed

Figure 4: CBACO policy representations

Recall the graphical representation of a CBACO policy in Figure 2. As we can
see the active event node is connected to an event scheme node, which is
connected to an obligation node by a green edge meaning it will trigger a
duty. This is shown in Figure 4(a). The only change in the graph is the
addition of this duty node and respective edges.

Finally, the active event in Figure 4(a) represents the action on the resource
by the subject needed to fulfill the duty, and so the final graph is shown in
Figure 4(b) where we get the representation of the duty present in the policy.

#### Visualisation and queries

Queries rewrite rules concern possible queries that can be made by a system
manager. They will rely on the rules mentioned above (auxiliary and
obligation) to get the requested answer coupled with visualization rules to
show said answer. Visualization rules are just rules to hide or show specific
nodes or edges, based on their attributes, that can be used to get different
views of the policy graph by using certain subsets of them.

##  0.6 Related Work

The use of graph based languages to model and analyse policies has mostly been
developed in the context of RBAC [9, 21, 17, 16, 22]. Most work done on CBAC
policies uses only textual languages and focuses on the expressiveness of the
model, the analysis of policies and techniques that can be used to enforce
policies[10, 11, 12, 1]. Graph based models for the analysis of CBAC policies,
were introduced in [3, 4], dealing with both permissions and prohibitions, but
neither addresses CBACO policies.

In [17, 16], inspired by Nyanchama and Osborn in [21], Koch et al. use
directed graphs to analyse RBAC policies using a graph model similar to
Baldwin’s privilege graphs [9]. One key aspect of [17, 16] is the use of graph
transformations to model administrative operations on RBAC policies. This
focus on administrative operations comes from the fact that RBAC policies are
static, whereas in CBAC the same operations are dependant on the system state
and are carried out without the need for an administrator to intervene. Using
our model we could represent the RBAC policies in [17, 16] since roles are a
particular case of category; however, the graphs in [17, 16] also deal with
sessions. In this paper we have not dealt with sessions, but since the notion
of session in RBAC is similar to the notion of session in CBAC it would be
easy to adapt the formalism used in [17, 16] to our model. In [19, 18] a
framework for the description of access control models using graph
transformations is described. With each type of access control model is
associated a typegraph for its graph based representation. Graph
transformations are used to describe both the ways that the policy can evolve
as well as positive and negative constraints. One of the focus of the work is
the integration of policies that use different access control models. As the
CBAC metamodel has been shown to subsume many of the most well known access
control models it makes it a good candidate for this purpose.

In [20] three modeling notations (viz. UML, Alloy and Graph Transformations)
are compared for the task of specification and verification of RBAC models.
The focus of the paper is on the evolution and constraints of the policies
and, with it, the possible violation of constraints that may arise. Although
we have not dealt with constraints in our implementation it would be easy to
integrate them. In [22] conceptual graphs and conceptual graph rules are used
to represent and reason on RBAC policies. Conceptual graphs are just labelled
hypergraphs, meaning edges (called hyperedges) can represent any n-ary
relationship between nodes. Rules are used to derive authorisation information
from the policy graph and to formulate constraints. One interesting aspect is
the use of backwards chaining to find inconsistencies in the policy; starting
from a rule defining a constraint they work their way backwards (using the
rules of information derivation in the opposite direction) to find if the
policy could violate said constraint. While such mechanism is not possible in
PORGY we could still check for the same constraint violations.

Miró [14] is a set of languages and tools for visual specification of file
system security inspired by Harel’s work on higraphs [13]. Higraphs are a
visual formalism of topological nature that combine Euler/Venn diagrams with
hypergraphs. Instead of nodes we have blobs that can contain/intersect other
blobs and can be connected by hyperedges making it a powerful formalism to
represent a wide variety of complex systems. In the case of Miró, blobs are
used to represent sets of users and files, and binary labeled directed edges
describe the granting/denial of access rights or, in some cases (constraint
language), if a blob is or is not inside another blob. There are two
languages, an instance language that describes the access rights of users to
files, and the constraint language that restricts the set of allowed instance
pictures. The blobs representing sets of users are a kind of categorisation
and as so this part of the representation is easily translated into our model.
The blobs representing sets of files is something we cannot directly translate
to our model as it is right now, but could easily be integrated as a partial
ordering of resources such as with categories. As stated edges can be used to
represent denial of access rights as in our model but, in contrast to our
model, these denials propagate from the more general blobs to the less general
as with granting. Furthermore, the lack of an edge granting some user access
to a file is interpreted as denial of access and there can be multiple edges
that apply to the same triple user, action, file, in which case a predominant
edge is searched, if there is no such edge it classifies as an ambiguity (in
our model such ambiguities are not allowed by definition). Because of these
differences, mapping a higraph in the Miró languages to a CBACO policy graph
is not trivial, nonetheless, policies described using the Miró languages could
be represented using our model.

LaSCO [15] is a policy language based on graphs. The graphs are labelled;
nodes represent objects (users, classes, resources, etc) and directed edges
represent actions (events in the LaSCO terminology). A policy graph in LaSCO
describes both the system state to which it applies and the constraints on
that state for it to be valid; this is done with the use of labels (predicates
in the LaSCO terminology). These labels can be seen as type of categorisation
and so we can map these policy graphs into policies in our model.

In [23] graphs are used to define a framework for the representation of
various access control models. Based on this framework a visual language for
the definition of constraints is also defined. Another focus of the paper is
on triggers, events that change the state of the policy or system. With some
adaptation in some cases, every model, constraint and trigger discussed could
be translated into our model.

##  0.7 Evaluation and Future Work

This paper presents a graph-based metamodel that deals with obligations in
access control, together with its implementation in the PORGY framework. This
is a prototipal implementation, for which we have not yet develop performance
evaluations. Nonetheless, we will give a brief evaluation of our framework by
highlighting its main advantages:

  * •

The proposed model can deal with obligations in a comprehensive manner, as was
shown by the comparison with the related work in the previous section.

  * •

The strategy driven language of PORGY is powerful enough to deal with the
dynamics aspects of the proposed model. Using the rewriting language it is
possible to simulate changes in a system, which are presented in a derivation
tree where each node can be inspected (see Figure 5).

Figure 5: Tracing a strategy

  * •

Rewriting systems have the advantages of being multi-paradigm and having a
well-developed theory. For example, the rewrite-based operational semantics of
the CBACO metamodel [2], allows for the analysis of compatibility between
authorisations and obligations, and we have used PORGY’s rewriting language to
evaluate the state of duties.

  * •

PORGY is being actively developed, which opens the door for further
improvement and the PORGY team is open to develop domain specific versions of
the framework, with tailored visualisation applications.

  * •

The PORGY tool is built on top of Tulip [8], an information visualization
framework dedicated to the analysis and visualization of relational data, and
both are released under the LGPL licence. The Tulip framework can be used to
import/export information from PORGY, which is a positive aspect for
integration with other prototyping and analysis tools.

Figure 6: PORGY’s interface

We now point out some less positive aspects of our framework that we would
like to further develop:

  * •

Presently there is a huge repetition of rules that result from the need to
define the rules for all the nodes of the same type that may differ in their
attributes (for example, its colour). Although this leads to a rather
cumbersome translation of the policy graphs into PORGY, this aspect could be
significantly improved by automating the generation of duplicated
graphs/rules. This could also be eased by the use of higher-order notions of
port-graphs that could facilitate the abstraction of patterns in the policy
graphs, leading to more efficient ways of writing rules that depend on
information on nodes that are not directly connected.

  * •

PORGY framework has a well-developed interface, where graphs and rules to be
constructed, strategies can be edited, applied and its trace can be followed
(see Figure 6). However, policy administrators could benefit from the
existence of user-friendly Domain Specific Languages (DSLs), that could be
translated into our modelling languages or other programming languages for
integration with existing policy analysis tools.

  * •

We would like to use the prototyping and analysis capabilities of rewriting to
analyse additional properties related to obligations, such as accountability.

## References

  * [1] A. Ali and M. Fernández.  Hybrid enforcement of category-based access control.  In S. Mauw and C. D. Jensen, editors, STM’14, pages 178–182, Cham, 2014. Springer.
  * [2] S. Alves, A. Degtyarev, and M. Fernández.  Access control and obligations in the category-based metamodel: A rewrite-based semantics.  In M. Proietti and H. Seki, editors, LOPSTR’14, pages 148–163. Springer, 2015.
  * [3] S. Alves and M. Fernández.  A framework for the analysis of access control policies with emergency management.  ENTCS, 312:89 – 105, 2015.
  * [4] S. Alves and M. Fernández.  A graph-based framework for the analysis of access control policies.  Theoretical Computer Science, 685:3 – 22, 2017.
  * [5] O. Andrei.  A Rewriting Calculus for Graphs: Applications to Biology and Autonomous Systems.  PhD thesis, Institut National Polytechnique de Lorraine, 2008.
  * [6] O. Andrei, M. Fernández, H. Kirchner, G. Melançon, O. Namet, and B. Pinaud.  PORGY: Strategy-Driven Interactive Transformation of Graphs.  In TERMGRAPH, pages 54–68, 2011.
  * [7] O. Andrei and H. Kirchner.  A higher-order graph calculus for autonomic computing.  In M. Lipshteyn, V. E. Levit, and R. M. Mcconnell, editors, Graph Theory, Computational Intelligence and Thought, pages 15–26. Springer, 2009.
  * [8] D. Auber, D. Archambault, R. Bourqui, M. Delest, J. Dubois, A. Lambert, P. Mary, M. Mathiaut, G. Melançon, B. Pinaud, B. Renoust, and J. Vallet.  Tulip 5, pages 1–28.  Springer New York, New York, NY, 2017.
  * [9] R. W. Baldwin.  Naming and grouping privileges to simplify security management in large databases.  In Proceedings. 1990 IEEE Computer Society Symposium on Research in Security and Privacy, pages 116–132, 1990.
  * [10] S. Barker.  The next 700 access control models or a unifying meta-model?  In SACMAT ’09, page 187–196, New York, NY, USA, 2009. ACM.
  * [11] C. Bertolissi and M. Fernández.  Rewrite specifications of access control policies in distributed environments.  In J. Cuellar, J. Lopez, G. Barthe, and A. Pretschner, editors, STM’11, pages 51–67, Berlin, Heidelberg, 2011. Springer.
  * [12] C. Bertolissi and M. Fernández.  A metamodel of access control for distributed environments: Applications and properties.  Information and Computation, 238:187 – 207, 2014.  Special Issue on Security and Rewriting Techniques.
  * [13] D. Harel.  On visual formalisms.  Commun. ACM, 31(5):514–530, May 1988.
  * [14] A. Heydon, M. Maimone, J. Tygar, J. Wing, and A. Zaremski.  Miro: Visual specification of security.  IEEE Trans. on Software Engineering, 16:1185–1197, 1990.
  * [15] J. A. Hoagland.  Specifying and implementing security policies using lasco, the language for security constraints on objects.  CoRR, cs.CR/0003066, 2000.
  * [16] M. Koch, L. Mancini, and F. Parisi-Presicce.  A graph-based formalism for rbac.  ACM Transactions on Information and System Security, 5(3):332–365, 2002.
  * [17] M. Koch, L. V. Mancini, and F. Parisi-Presicce.  A formal model for role-based access control using graph transformation.  In ESORICS’00, pages 122–139. Springer, 2000.
  * [18] M. Koch, L. V. Mancini, and F. Parisi-Presicce.  Foundations for a graph-based approach to the specification of access control policies.  In Foundations of Software Science and Computation Structures, pages 287–302. Springer, 2001.
  * [19] M. Koch, L. V. Mancini, and F. Parisi-Presicce.  On the specification and evolution of access control policies.  In SACMAT’01, page 121–130. ACM, 2001.
  * [20] M. Koch and F. Parisi-Presicce.  Visual specifications of policies and their verification.  In Fund. Approaches to Soft. Engineering, pages 278–293. Springer, 2003.
  * [21] M. Nyanchama and S. Osborn.  The role graph model and conflict of interest.  ACM Trans. Inf. Syst. Secur., 2(1):3–33, Feb. 1999.
  * [22] R. Thion and S. Coulondre.  Representation and reasoning on role-based access control policies with conceptual graphs.  In Conceptual Structures: Inspiration and Application, pages 427–440. Springer, 2006.
  * [23] J. E. Tidswell and J. M. Potter.  A graphical definition of authorization schema in the dtac model.  In SACMAT ’01, page 109–120. ACM, 2001.