Managing the Life Cycle of Access Rules in CEOSIS [original]

Managing the Life Cycle of Access Rules in CEOSIS

Stefanie Rinderle-Ma, Manfred Reichert

Institute of Databases and Information Systems, Ulm University, Germany

{stefanie.rinderle, manfred.reichert}@uni-ulm.de

Abstract

The definition and management of access rules (e.g., to

control the access to business documents and business func-

tions) is an important task within any enterprise informa-

tion systems (EIS). Many EIS apply role-based access con-

trol (RBAC) mechanisms to specify access rules based on

organizational models. However, only little research has

been spent on organizational changes even though they of-

ten become necessary in practice. Examples comprise the

evolution of organizational models with subsequent adap-

tation of access rules or direct access rule modifications.

In this paper, we present a change framework for the con-

trolled evolution of access rules in EIS. Specifically, we de-

fine change operations which ensure correct modification

of access rules. Finally, we define the formal semantics of

access rule changes based on operator trees which enables

their unambiguous application; i.e., we can precisely de-

termine which effects are caused by respective adaptations.

This is important, for example, to be able to efficiently adapt

user worklists in process-aware information systems. Al-

together this paper contributes to comprehensive life cycle

support for access rules in (adaptive) EIS.

1 Introduction

A fundamental aspect in the design of any enterprise in-

formation systems (EIS) concerns

access control

, i.e., grant-

ing certain rights to specific users; e.g., the right to access

a certain business document for a restriced group of users

in an EIS. There is a multitude of models for defining such

access control mechanisms; e.g., GRANT / REVOKE state-

ments in DBMS or Role Based Access Control (RBAC)

[5] in process-aware information systems (PAIS). Usually

such models comprise a set of

access rules

which are de-

fined based on organizational models capturing organiza-

tional entities and their relationships. Access rules control

which rights shall be granted to which users. In case of

PAIS, for example, access rules specify which tasks (i.e.,

work items

) shall be offered to which users in their work-

lists during the execution of a particular process.

Due to changes of the organization or evolving security

policies, access rules have to be frequently adapted. This,

in turn, must be effectively handled by the EIS in order to

be able to cope with organizational changes in a quick, flex-

ible, and reliable (secure) way. So far, only little research

has been spent on the evolution of access rules and the re-

sulting effects on the underlying EIS. In particular, access

rules might be subject to the following kind of changes:

1. Organizational Change: Access rule adaptations

might become necessary after changes of organiza-

tions and organizational models respectively [10, 11].

Assume that access control within a PAIS (i.e., the as-

signment of work items to users) is reflected by the

simple access rules depicted in Fig. 1. Assume that

these rules are based on organizational model OM. To

streamline the organization, units LoanM and LoanH

are merged into organizational unit LoanH’ and role

Clerk is deleted from OM resulting in organizational

model OM’. Obviously, access rule AR1 is not af-

fected by the organizational change whereas access

rules AR2 and AR3 now refer to entities no longer

present in OM’. If the affected access rules were not

adapted this could threaten robustness or security con-

straints of the PAIS. Worst case, for access rules which

cannot be resolved properly, the associated task is of-

fered to unauthorized users (e.g., process administra-

tor, users working on preceding tasks, etc.).

2. Direct Changes: Generally, it must be also possible to

adapt access rules directly within EIS (cf. Fig. 2). This

often becomes necessary, for example, for access rules

not specified precisely enough. Either the access rule

covers a too broad range of users (i.e., only a subset of

the users qualifying for the access rules actually work

on the associated work items) or it is too narrow (e.g.,

the related task is always delegated to substitutes). In

both cases, the specified access rules do not reflect the

real situation. As a consequence, task assignment is

handled outside the system and thus might be not prop-

erly documented. Furthermore, manual task assign-

b) Access control within

process-aware information system:

For task1: AR1 ĸ(Role = Secretary)

For task2: AR2 ĸ(Role = Clerk)

For task3: AR3 ĸ(OrgUnit = LoanM OR OrgUnit = LoanH)

MERGE

OrgUnit=

Bank

OrgUnit=

LoanD

OrgUnit=

InvestD

OrgUnit=

LoanS

OrgUnit=

LoanM

OrgUnit=

LoanH

Role=

Clerk

Role=

Secr.

ACTORS

a) Organizational

Model OM:

OrgUnit=

Bank

OrgUnit=

LoanD

OrgUnit=

InvestD

OrgUnit=

LoanS

OrgUnit=

LoanH‘

Role=

Secr.

ACTORS

Organizational

Model OM‘:

not affected by

affected by

DELETE

task1 task2 task3

AR1 AR2 AR3

Figure 1. Organizational changes affecting access rules

ment or adaptation can be complex and error-prone.

1) Access Rule

Acquisition

2) Access Rule

Definition

3) Access Rule

Deployment

4) Access Rule

Evaluation

Access Rule Mining

Direct Access

Rule Changes

Figure 2. Access rule life cycle

In [10, 11] we presented an approach for specifying or-

ganizational models and for propagating changes of such

models to access rules. In particular, such adaptations be-

come necessary to maintain correctness and consistency of

access rules; e.g., avoiding the situation where no actor

qualifies for a specific access rule anymore. However, our

previous work has not considered direct changes of access

rules so far; i.e., changes which are independent of whether

the underlying organizational model is changed. This will

become necessary, if access rules are to be optimized or

corrected (e.g., if a work item within a PAIS is manually

assigned to a more specialized role as the current one).

One approach for the (semi-) automatic determination of

access rule optimizations is

access rule mining

[8, 14] (cf.

Fig. 2). Using special mining techniques, it can be detected

whether and how users deviate from the pre-modelled ac-

cess rules within daily business life. As first example as-

sume that a work item within a PAIS is always passed to a

subtitute. Another example could be that two users A and

B qualify for a particular task (i.e., work item), but the task

is always selected by A. Then, the associated access rules

should be optimized by applying direct access rule changes.

In this paper we present our CEOSIS1framework for

evolving access rules in a controlled and secure way. There

are two basic requirements for such a framework. First

of all, access rule changes must be conducted in a

correct

way; i.e., they must not violate any structural constraints

set out by the access rule specification. To fulfill this re-

quirement we base the definition of access rule changes on

an operator tree representation and equip respective opera-

tors with formal pre- and post-conditions which ensure their

correct application. Second, the

formal semantics

of access

rule changes must be specified. This guarantees their un-

ambigous application and supports the precise analysis of

change effects. To achieve this, we base the semantics of

access rule changes on the effects they have on associated

valid actor sets

; i.e., the set of actors who qualify for the par-

ticular access rule. This enables, for example, the analysis

of access rule change effects on user worklists in PAIS.

The remainder of this paper is organized as follows: In

Sect. 2 we provide background information. Sect. 3 defines

change operations for access rules and Sect. 4 provides their

formal semantics. In Sect. 5 we discuss related work. We

close with a summary and outlook in Sect. 6.

2 Organizational models and access rules

In this section we provide information needed for the for-

mal underpinning of our work.

1CEOSIS: Controlled Evolution of Organizational Structures in

Information Systems

2.1 Organizational (meta) model

An organizational

meta model

captures all entities and

relations an organizational model may consist of (i.e.,

the meta model can be seen as the schema which can

be instantiated by concrete organizational models). The

organizational meta model OMM used in this paper is

based on the

Role Based Access Control Model

(RBAC)

[6]. As depicted in Fig. 3 it consists of entity types

OrganizationalUnit,Actor, and Role. Concrete

organizational units (e.g., clinic) can be hierarchically

related to each other by relation is subordinated.

Similarly, concrete roles can be specialized by introducing

sub roles (relation specializes); i.e., the sub role inher-

its all abilities of the superior role, but may have additional

ones. Finally, actors can have roles (relation has) and be-

long to organizational units (belongs to).

O rgUnits Actors Roles

is subordinated

has

specializes

belongs to

(0,1)

(0,n) (0,1) (0,n) (0,n)

(0,1) (0,n)

(0,n)

Figure 3. Org. meta model (in ER notation)

In this paper, we use a well-established, but rather sim-

ple organizational meta model OMM to focus on core issues

related to access rule changes. In principle, OMM and the

subsequent considerations can be transferred to more com-

plex organizational meta models as well (e.g., capturing en-

tities such as abilities or substitution relations) [11].

Based on our OMM concrete organizational models can

be defined, i.e., an organizational model OM is an in-

stance of OMM (cf. Def. 1). One example is depicted

in Fig. 4a. OM captures three organizational units, where

treatment area and administration are hierar-

chically subordinated to unit medical clinic.The

most general role used in this model is staff which

is specialized by roles internist,assistant, and

secretary. Finally, actors are assigned to roles and be-

long to an organizational unit (e.g., actor Hunter has role

secretary and belongs to unit administration).

Definition 1 (Organizational model) An organizational

model is a tuple OM = (Actors, Roles, OrgUnits,

has, belongs to, is subordinated,

specializes), where:

•Actors corresponds to the set of actors (i.e., the people

performing activities or accessing data objects),

•Roles corresponds to the set of roles,

•OrgUnits corresponds to the set of organizational units,

•has ⊆Roles ×Actors corresponds to the relation

linking actors to roles,

•belongs to ⊆OrgUnits ×Actors corresponds

to the relation linking actors to organizational units,

•is subordinated ⊆OrgUnits ×OrgUnits de-

fines the organizational hierarchy, and

•specializes ⊆Roles ×Roles defines the role hi-

erarchy.

Furthermore, the following notions on relations are needed:

- R(x) := {y∈X|(x,y) ∈R}for any relation

R⊆X×Y∈{has, belongs to, specializes,

is subordinated}and any x ∈X

-R

∗is the transitive closure of R

Consider Fig. 4. An example for generic relation

R(x) given in Def. 1 is has(assistant) = Black

(with R = ’has’). The semantics of the two relations

is subordinated and specializes can be defined

as follows: All actors belonging to an organizational unit

also belong to its superordinated organizational units (e.g.,

actors Smith,Black,Hunter, and Dr.Smith all be-

long to org. unit medical clinic, Fig. 4). If an actor

has a particular role she will also possess all superior roles

(e.g., actor Black has roles assistant and staff).

2.2 Access rules

We provide a notion for access rules and specify their

formal semantics. We need this information later in order

to be able to reason about access rule changes.

Definition 2 (Elementary access rule) Let OM =

(Actors, ...) be an organizational model (cf. Def. 1).

An elementary access rule EAR on OM is defined as follows:

EAR ≡(EAR0 ←− τ∗)2|

(EAR1 ←− (Role = r)) |

(EAR2 ←− (OrgUnit = o)) |

(EAR3 ←− (Role+ = r)) |

(EAR4 ←− (OrgUnit+ = o)).

Formal semantics of elementary access rule EAR is defined over

the set of valid actors qualifying for EAR based on OM. We denote

this set as VAS(OM, EAR) ⊆Actors with

•VAS(OM, EAR0) = ∅

•VAS(OM, EAR1) = has(r) (where has(r) corre-

sponds to the set of actors with role r, cf. Def. 1)

•VAS(OM, EAR2) = belongs to(o) (i.e., the set of

actors belonging to unit o)

•VAS(OM, EAR3) = has(specializes∗(r))

(where has(specializes∗(r)) corresponds to the set

of actors having role ror a more specialized one, cf. Def. 1)

•VAS(OM, EAR4) = has(is subordinated∗(o))

(i.e., the set of actors belonging to organizational unit oor

a subordinated one).

2τ∗denotes an empty term.

OrgUnit = medical clinic

OrgUnit = administrationOrgUnit = treatment area

ctor = Dr. Smith

ctor = Black

ctor = Hunter

Role = internist Role = secretary

is _subordinated is subordinated

belongs_to

Role = assistant

belongs_to

has

Role = staf

has

specializes

has

a) Organizational Model OM:

b) Access Rules on OM:

AR1 ĸ Role+=‘staff’

AR2 ĸ OrgUnit=‘treatment area’

AR3 ĸ (Role=’secretary’) OR (Role=’assistant’)

AR4 ĸ NOT(OrgUnit+=’medical clinic’)

specializes

ctor = Jones

has

OrgUnit = therapy center

ctor = Walter

Role = therapist

is _subordinated

belongs_to

has

ctor = Ward

belongs_to

c) Valid Actor Sets:

VAS(OM,AR1) = {Dr. Smith, Black, Hunter, Jones}

VAS(OM,AR2) = {Dr. Smith, Black}

VAS(OM,AR3) = {Black, Hunter, Jones}

VAS(OM,AR4) = {Jones}

Figure 4. Organizational model, access rules, and valid actor sets

Fig. 4b+c show two elementary access rules AR1 and

AR2 and the associated valid actor sets based on organi-

zational model OM. Taking Def. 2 the general notion of

access rules can be formalized. It is based on elementary

access rules which can be combined by logical operators

AND, OR, and NOT. Note that we restrict the complex-

ity of access rules by using negation only in the context of

elementary access rules. However, this constitutes no re-

striction regarding the expressiveness of access rules. Any

negation contained within an access rule AR can be always

pushed to the elementary access rules contained within AR.

Definition 3 (Access rule) Let OM be an organizational

model. An access rule AR is defined as concatenation of other

access rules by using logical operators AND, OR, and NOT. For-

mally:

AR ≡EAR |NAR |CAR |DAR

where

•EAR constitutes an elementary access rule (cf. Def. 2),

•NAR ←− (NOT (EAR)) where EAR is an elementary ac-

cess rule,

•CAR ←− (AR1 AND AR2) where AR1 and AR2 are

access rules, and

•DAR ←− (AR1 OR AR2) where AR1 and AR2 are ac-

cess rules.

Formal semantics of EAR has been given in Def. 2, the one of

NAR, CAR and DAR is defined as follows:

•VAS(OM,NAR) = Actors \VAS(OM,AR) corre-

sponds to the set of actors not qualifying for access rule

AR,

•VAS(OM,CAR) = VAS(OM,AR1) ∩VAS(OM,AR2)

corresponds to the set of actors qualifying for access rules

AR1 and AR2,

•VAS(OM,DAR) = VAS(OM,AR1) ∪VAS(OM,AR2)

corresponds to the set of actors qualifying for access rules

AR1 or AR2

AROM denotes the set of all access rules over OM.

Fig. 4b depicts two non-elementary access rules AR3

and AR4.

3 Access rule changes

To be able to analyze the effects of changes of an

organizational model we introduced respective change op-

erations with precise formal semantics in [10, 11]. Sim-

ilarly, in this section, we define operations for changing

access rules directly; e.g., deleting AND-terms. The formal

semantics of these change operations is presented in Sect. 4.

It is based on the valid actor sets of the access rules before

and after the changes.

3.1 An operator-tree-based representa-

tion for access rules

In order to precisely define access rule changes, it is nec-

essary to base their definition on a representation other than

the intuitive one presented in Def. 3. Using the notion given

in Def. 3 it would be difficult to express at which substruc-

ture level of nested access rule structures, a new AND-term

shall be added. Thus we have to find a representation which

allows for the convenient access to any substructure level of

an access rule. For an access rule AR, a suitable represen-

tation for this is provided by

operator tree

OPAR =(O,L).

O denotes the set of all operator nodes and L denotes the

set of all elementary access rules AR is built of. OPAR can

be determined similarly to building the operator-tree for a

formula or SQL-statement. An example of an access rule

with corresponding operator-tree is shown in Fig. 5. Fig. 6

shows another example for an imbalanced operator tree.

AND

OR NOT

Role='secretary Role='assistant OrgUnit='administration'

AR ĸ (((Role = ’secretary’) OR (Role = ’assistant’)) AND

(NOT(OrgUnit = ’administration’)))

Figure 5. Access rule and operator tree

OPAR = (O,L) has the following characteristics.

•OP

AR is a binary tree

•O corresponds to the set of non-leaf nodes (including

the tree root) and L corresponds to leaf nodes

•The tree has to be traversed in inorder to build the as-

sociated access rule term.

•NOT is only used as direct predecessor node of a leaf

(remember that NOT can be only used in the context

of elementary access rules in CEOSIS, cf. Def. 3).

How an operator tree can be built based on a given access

rule is shown in the next section.

3.2 Basic access rule change

We introduce a complete set of basic change operations

on access rules3and their operator-tree representation re-

spectively. Before we define basic notions on operator trees:

Definition 4 (Functions on op trees) Let AR ∈AR

OM be

an access rule and let OPAR be its operator tree. Then:

•The empty tree τconsists of one void node; i.e., it reflects

empty access rule EAR0 ←− τ∗.

•Let OPOM denote the set of all operator trees for access

rules over an organizational model OM. Let further Nde-

note the total set of nodes belonging to any operator tree

from OPOM . Then:

3Complete means that any access rule AR ∈AR

OM can be trans-

formed in any other access rule AR’ ∈AR

OM by applying a sequence

of change operations <op1,...,op

n>.

–pred: OPOM ×N →Nwith pred(OPAR,n)=pde-

termines direct predecessor node p of node n in OPAR

–root: OPOM →Ndetermines the root node of oper-

ator tree OPAR.

•Merge: OPOM ×OPOM ×{AND,OR,VOID4}→OPOM

Merge(S,T,op=[AND|OR|VOID]) = S’ merges two oper-

ator trees S and T using op, where T = OPEAR with EAR

being an elementary access rule. Root of S’ is op, left child

tree is S, right child tree is OPEAR

•Substitute: OPOM ×OP

OM ×OP

OM →OP

Substitute(T,S,S’) = T’ substitutes sub tree S in T by sub tree

S’ resulting in T’ (cf. Fig. 6, Step 1).

•Optimize: OPAR →OP

Optimize(T) = T’ works as follows: If operator tree T con-

tains empty tree τthen T can be optimized by merging τand

its sibling tree S resulting in optimized tree T’. More pre-

cisely: Let O be the predecessor of τand S. Then O, τ, and

S can be merged to S (cf. Fig. 6, Step 2).

Our set of basic change operations allows for adding,

deleting, and negating terms within operator trees. We

claim that these change operations can only be applied to

correct access rules resulting in correct access rules again

(i.e., access rules ∈AR

OM ). Structural correctness is pre-

served by formal pre- and postconditions for the change op-

erations. Within our ADEPT process management technol-

ogy [12, 13], we additionally ensure compliance with the

underlying organizational model OM by forbidding access

rule changes which refer to entities not being present in OM

(e.g., referring to Role=’clerk’ in Fig. 4).

Definition 5 (Basic change operations on access rules)

Let AR ∈AR

OM be an access rule with operator tree OPAR.

Let further EAR be an elementary access rule with operator tree

OPEAR. Assume that AR is transformed into another access rule

AR’ ∈AR

OM (represented by OPAR) by applying change

op ∈{addTerm, deleteTerm, negateTerm}with

•addTerm(OPAR,S,[AND|OR|VOID],EAR) = OPAR

Precond.: S is sub-tree of OPAR

Postcond.: OPAR=

Optimize(Substitute(OPAR,S,Merge(S,OPEAR)))

•deleteTerm(OPAR,S) = OPAR

Precond.: S is sub-tree of OPAR and S does not contain the

root node (the root node is deleted by tree merging if a direct

sub tree of the root node is deleted)

Postcond.: OPAR= Optimize(Substitute(OPAR,S,τ))

•negateTerm(OPAR,S) = OPAR

Precond.: S is leaf node; i.e., S = OPEAR and

pred(OPAR,EAR) =NOT (the second condition is neces-

sary to achieve operator trees where NOT is only used in

connection with leaf nodes according to the definition of ac-

cess rules.).

Postcond.: OPAR= Substitute(OPAR,S,OPNOT(EAR))

4VOID represents the empty operator.

An example for applying the delete operation is depicted

in Fig. 6. First the sub tree reflecting elementary access rule

EAR ←Role=’secretary’ (cf. Fig. 5) is substituted

by empty tree τ. Then the optimization function is run on

the resulting tree which eliminates τby lifting up remaining

elementary access rule EAR’ ←Role=’assistant’

to the next level within the operator tree.

AND

NOT

Role='assistant'

OrgUnit='administration'

a) AR ĸ (((Role = ’secretary’) OR (Role = ’assistant’)) AND

(NOT(OrgUnit = ’administration’)))

op = deleteTerm(

AR,

EAR) with EAR ĸ (Role = ‘secretary’)

b) Step 1: Substitution by Ĳ

AR’:

AND

OR NOT

Role='assistant' OrgUnit='administration'

Step 2: Optimization

AR:

Figure 6. Delete operation with subsequent

optimization

Generally, a sequence of basic change operations

<op1,...,op

n>can be used to built up the operator tree

for an access rule starting with the empty tree. Consider ac-

cess rule AR as given in Fig. 5. Then the following basic

change operations build OPAR starting from empty tree τ:

op1:OP1= addTerm(τ,τ, VOID, Role=’secretary’)

op2:OP2= addTerm(OP1,OP1, OR, Role=’assistant’)

op3:OP3= addTerm(OP2,OP2, AND, OrgU-

nit=’administrator’)

op4:OPAR = negateTerm(OP3,OPOrgUnit=assistant)

Formal semantics of these change operations is pre-

sented in Sect. 4.

3.3 High-level access rule changes

For better user support we have defined some

high-

level change operations

based on the basic change oper-

ations introduced in Def. 5. As an example consider

substituteAccessRules(

OPAR

,S,T)

where sub tree S of op-

erator tree OPAR is substituted by another sub tree T.

At access rule level this means to substitute a part of

the access rule by another access rule. A substitution of

access rules can be accomplished by applying operation

deleteTerm(OPAR,S) first, followed by a sequence of add-

Term operations. They build up T within OPAR by insert-

ing the elementary access rules T consists of. The pre- and

postconditions of high-level change operations can be de-

rived by aggregating the pre- and postconditions of the un-

derlying basic change operations. Due to lack of space we

omit further details here.

4 Semantics of access rule changes

The formal semantics of access rule changes can be ex-

pressed based on the effects these changes have on valid

actor sets (cf. Sect. 2.2). In particular, we are interested

in statements such as ”the valid actor set of access rule AR

is reduced, expanded, or not affected by the change”. Note

that for the following considerations on semantics we as-

sume direct access rule changes; i.e., the underlying organi-

zational model is not modified.

Definition 6 (Reduction / Expansion of Actor Sets) Let

AR ∈AR

OM be an access rule (over organizational model

OM) and let ΔAR be a change which transforms AR into

another access rule AR’ ∈AR

OM . Then the effect of

ΔAR on AR is called

•reduction iff VAS(OM,AR’) ⊂VAS(OM,AR)

•expansion iff VAS(OM,AR’) ⊃VAS(OM,AR)

•zero effect iff VAS(OM,AR’) = VAS (OM,AR)

4.1 Root level and substructure level

changes

For elementary access rules the analysis of change

effects is easy to accomplish. For example, let EAR

←− (Role = ’doctor’) and EAR’ ←− (Role =

’therapist’) be two elementary access rules with op-

erator trees OPEAR and OPEARrespectively. Let further

change

op = addTerm(

OPEAR

, AND,

EAR’

)

AR transform EAR into AR. Then the effect on the actor set

of EAR is a

reduction

, more precisely, the actor sets of AR

can be determined as intersection of the actor set of EAR

and EAR’.

Things will become more complicated if the access rules

to be changed are more complex. Consider, for exam-

ple, access rule AR in Fig. 5 and elementary rule EAR’

←− (Role = ’therapist’). If we apply change

operation opa=

addTerm(

OPAR

,AND,

EAR’

)

(cf.

Fig. 7a) the effect can be determined as intersection

of the actor set of AR and EAR’ again. However,

when applying change operation opb=

addTerm(

OPAR

OPNOT(OrgUnit=administration)

, AND,

EAR’

)

(cf. Fig.

7b), effects on the valid actors sets of AR cannot be deter-

mined straightforward. Note that opaoperates at the

root

level

of AR (the formal meaning is described in the follow-

ing), whereas opboperates at a

substructure level

of AR.

The notions of root level and substructure level changes of

access rules are presented in Def. 7.

Definition 7 (Root vs. substructure level changes) Let

OPAR be the operator tree representation of access rule

AR:

opa = addTerm(

AR,

AR, AND, Role=’therapy)

opb = addTerm(

AR,

NOT(OrgUnit=’administration*), AND, Role=’therapy)

AND

NOT

Role='secretary' Role='assistant' OrgUnit='administration

AND

NOT

Role='secretary' Role='assistant' OrgUnit='administration

AND

Role='therapy'

AND

NOT

Role='secretary' Role='assistant'

OrgUnit='administration

Role='therapy'

AND

sub tree S

Figure 7. Access rule changes

AR ∈AR

OM and let op be a basic change operation which

transforms AR into another access rule AR’ ∈AR

OM .Thenwe

denote op as

•root level change if either a new root is added to operator

tree OPAR or the root of OPAR is deleted (e.g., by tree

merging after applying the delete operation). This holds for

•op = addTerm(OPAR,OPAR,[AND|OR|VOID],EAR)

•op = deleteTerm(OPAR,S) with

pred(root(S)) = root(OPAR)

•op = negateTerm(OPEAR,OPEAR) with

EAR being an elementary access rule

•substructure level change otherwise

The root level change depicted in Fig. 7a) shows

that operator tree OPAR grows by adding a new

root node, whereas the substructure level change (cf.

Fig. 7b) is conducted by substituting sub tree S =

OPNOT(OrgUnit=administration)by sub tree S’ =

OP(NOT(OrgUnit=administration))AND(Role=therapist).

As it can be seen new root AND has been added to S.

4.2 Basic access rule changes

The basic idea of our approach for determining the ef-

fects of access rule changes on valid actor sets (in terms

reduction, expansion

,or

zero effect

) is as follows: First,

it must be checked how root level changes affect valid ac-

tor sets of respective access rules. Second, for substructure

level changes the following observation can be made: A

substructure level change is a root change regarding the

af-

fected sub tree

(cf. Fig. 9); i.e., we can determine effect e

∈{

reduction, expansion, or zero effect

}on the affected sub

tree. Effect ecan then be ”propagated” upwards to the root

of the new operator tree. Then, the question is if, for exam-

ple, a reduction on the affected sub tree remains a reduction

when being propagated to the root level.

Thus, for determining the effects of basic access rule

changes on valid actor sets a first step is to present the ef-

fects of root level changes on operator trees.

Proposition 1 (Effects of root level changes) Consider the

following elements:

•OP

AR: Operator tree of access rule AR over organi-

zational model OM with S and T being sub trees of

OPAR with pred(OPAR,root(S)) = pred(OPAR,root(T)) =

root(OPAR). S corresponds to access rule ARSand T to

access rule ART

•EAR: Elementary access rule with operator tree OPEAR

•op: root level change which transforms AR into another ac-

cess rule AR’ with operator tree OPAR

Then: The effect (i.e., formal semantics) of operation op on

OPAR can be determined as follows (see Fig. 8):

op: addTerm(

OPAR

[AND|OR]

,EAR) =

OPAR

•op: addTerm(OPAR,OPAR,AND, EAR) = OPAR:

VAS(OM,AR’) = VAS(OM,AR) ∩VAS(OM, EAR)

=⇒Reduction

•op: addTerm(OPAR,OPAR,OR, EAR) = OPAR:

VAS(OM,AR’) = VAS(OM,AR) ∪VAS(OM,EAR)

=⇒Expansion

op: deleteTerm(

OPAR

,S) =

OPAR

•root(OPAR)=AND:

VAS(OM,AR) = VAS(OM,ART)∩VAS(OM,ARS)

⊆VAS(OM,ART) = VAS(OM,AR’)

=⇒Expansion

•root(OPAR)=OR:

VAS(OM,AR) = VAS(OM,T) ∪VAS(OM,S)

⊇VAS(OM,T) = VAS(OM,AR’)

=⇒Reduction

op: negateTerm(

OPEAR

OPAR

VAS(OM,AR’) = Actors \VAS(OM,EAR)

=⇒effect cannot be determined in terms of

expansion, reduction, or zero effect

Fig. 8 illustrates the different cases covered by Prop. 1.

So far, we have only considered root level changes. For

substructure level changes, we first determine the (mini-

mal) sub tree which is affected by the respective change

(

affected sub tree

). The effects of the substructure change

on the affected sub tree can be determined using Prop. 1

for root level changes and are reflected by the

resulting sub

tree

(cf. Def. 2). According to Prop. 1, it is not possible

to derive the effects of negation in terms of

reduction, ex-

pansion

,or

zero effect

. We know that VAS(OM,AR) and

AR’:

AND

EAR

1a)

AR:

AR’:

AND

EAR

1b)

AR:

2a)

AR:

AND

T S

AR’:

2b)

AR:

T S

AR’:

NOT

EAR

AR:

EAR

addTerm addTerm

deleteTerm deleteTerm

negateTerm Illustration of Proposition 1

Figure 8. Effects of root level changes

VAS(OM,AR’) are

disjoint

which can be used to describe

the semantics of the negation operation. To describe the

semantics of substructure level changes, the effects on the

affected sub tree are propagated to the root. In this paper,

we show how this can be done for effects

reduction, expan-

sion

, and

zero effect

. Obviously, for other effects (such as

disjoint) other techniques have to be applied in order to an-

alyze the effects of substructure level changes. Thus, in this

paper, we focus on operations

addTerm

and

deleteTerm

and

leave

negateTerm

to future work.

Proposition 2 (Effects of substructure level changes)

Let OPAR be the operator tree of access rule AR over organi-

zational model OM. Let further op be a change operation which

transforms AR into another access rule AR’ with operator tree

OPAR. Then: The affected and resulting sub trees of op on

OPAR can be determined as follows (see Fig. 9):

1. op: addTerm(OPAR,S,[AND|OR|VOID],EAR) = OPAR

=⇒

•affected sub tree of op on OPAR is S

•resulting sub tree of op on OPAR is S’ with root(S’) =

pred(OPAR,root(S)) having sub trees S and OPEAR

2. op: deleteTerm(OPAR,S)=OPAR=⇒

•affected sub tree of op on OPAR is S’ with root(S’) =

pred(OPAR,root(S))

•resulting sub tree of op on OPAR is T with T being a sib-

ling tree of S based on S’ in OPAR

To determine the overall effect of a substructure level

change on the whole access rule AR, the effect on the af-

fected sub tree has to be

pushed

towards the root node of

the operator tree of AR’. Pushing means that we climb up

the tree over the different operators and check the impact

on the effects. We start with pushing the effect over the pre-

decessor node of the root of the affected sub tree (

one step

push

) and extend this to a

multi step push

towards the root

afterwards. To specify the one step push we introduce no-

tion

embracing tree

of the affected sub tree. An example for

an embracing tree is shown in Fig. 10.

1) op: addTerm(

AR,S, [AND|OR|VOID], EAR) =

AR’

AR:

AR’:

EAR

Affected sub tree

Resulting sub tree S’

2) op = deleteTerm(

AR,S)

AR:

Affected sub tree S’

Resulting sub tree

AR’:

Figure 9. Affected and resulting sub trees

Definition 8 (Embracing tree) Let OPAR be an operator

tree and let S be a sub tree of OPAR. Then we denote T as

the embracing tree of S in OPAR iff

•T is sub tree of OPAR or T = OPAR

•root(T) = pred(OPAR,root(S))

BasedonDef.8,the

one step push

can be formalized.

Proposition 3 (One step push) Let OPAR be the operator

tree of access rule AR over organizational model OM. Let

further op be a change operating at substructure level with

affected sub tree S. Assume that the effect of op on S corre-

sponds to e ∈{Reduction, Expansion, Zero effect}. Then:

One step push of e towards root(OPAR) means to lift up e

over root(T) where T denotes the embracing tree of S’; i.e.,

we analyze how e is affected by lifting it over the next oper-

ator node on the way to the root. The effect of the one step

push remains e; i.e., e is not affected by a one step push.

For example, if the effect on the affected sub tree is a

reduction, intuitively the effect remains a reduction if we

”climb over” an OR node. The effects of a one step push

over an AND node is illustrated by Fig. 10. The valid ac-

tor set of affected sub tree S is reduced according to Prop.

1; i.e., VAS(OM,S’) ⊆VAS(OM,S). Lifting this effect

over the root node of the embracing sub tree T’, which is an

AND node, keeps the effect of reduction.

Finally, it has to be analyzed how a

multiple step push

towards the root affects the effects of substructure level

changes. As stated in Prop. 3, a one step push does not

affect them. A multi step push can be seen as a one step

push which is applied several times. Each time the initial

effect of the substructure level change remains the same.

Thus, overall, the multi step push does not affect the effect

of the substructure level change. This means that the se-

mantics of a substructure level change can be determined as

easily as for a root level change. Thus, for any complex ac-

cess rule and any basic change operation, the effect can be

AR:

op: addTerm(

AR, S, AND, EAR) =

AR’ with EAR ĸOrgUnit='therapy center'

AR’:

AND

NOT

Role='secretary' Role='assistant'

OrgUnit='administration

AND

NOT

Role='secretary' Role='assistant'

OrgUnit='administration'

Role='therapy'

AND

OrgUnit='therapy center'

AND

resulting sub tree S’

of op on

One step push over root

node of embracing sub

tree T’ of S’

VAS(OM,T) = {Walter}

« Reduction

Embracing tree T of S on

VAS(OM,T) = {Walter, Ward}

OrgUnit='therapy center'

VAS(OM,S’) = {Walter}

« Reduction

VAS(OM,S) = {Walter,

Ward, Dr. Smith, Black}

Figure 10. Effects of one step push (example)

determined quickly. This is important, for example, in the

context of adapting user worklist in PAIS as we will discuss

in Sect. 4.4.

Proposition 4 (Multi step push) Let OPAR be the oper-

ator tree of access rule AR over organizational model OM.

Let further op be a substructure level change operation with

affected sub tree S and resulting sub tree S’. Assume that the

effect of op on S is e ∈{Reduction, Expansion,Zero effect}.

Then: Multi step pushing e towards root(OPAR) means to

lift up e over all nodes on the path to root(OPAR) starting

from root(T) where T denotes the embracing tree of S’. The

effect of a multi step push towards the root remains e; i.e., e

is not affected by the multi step push.

4.3 High-level access rule changes

A high-level access rule change Δcan be understood

as an ordered sequence of basic access rule changes

op1,...,op

n. Thus, it can be tried to aggregate the effects

of op1,...,op

nin order to determine semantics of Δ.How-

ever, such aggregation might be impossible; e.g., if the ef-

fect of opiis a reduction and the effect of opjis an

expan-

sion

(i=j). In this case, valid actor sets before and after the

high-level change have to be re-calculated and compared.

Generally, re-calculation could be used for determining the

effects of basic change operations as well. However, as we

will show in Sect. 4.4, in many applications it is benefi-

ciary to have a ”quick check” on the effects of access rule

changes. For example, if we know that a change has ef-

fect

expansion

zero effect

, we can delay the adaptation

of user worklists in PAIS until the system is offline. Con-

trary, it can be expensive to always recalculate the new valid

actor sets immediately.

Several optimizations exist regarding high-

level access rule changes. For high-level change

substituteAccessRules(OPAR,S,T), for example, ad-

ditional information from the underlying organizational

model can be used to determine the effects on the valid ac-

tor sets of the changed access rules. Assume, for example,

that for access rule AR ←Role=’R1’, we substitute R1

by role R2 resulting in AR’ ←Role=’R2’. Then, if we

knew from the underlying organizational model that R2

is a sub role of R1, it can be concluded that the effect on

the valid actor set of AR is either zero effect or reduction.

Reason is that the same set of actors or less actors will

be assigned to a sub role when compared to the superior

one. Vice versa, if a role is substituted by a superior one

within an access rule, the effect on the valid actor set will

zero effect

or an

expansion

. Same considerations hold

for the hierarchial relations between organizational units.

We omit formal definitions here.

4.4 Discussion

Using our CEOSIS approach, any basic substructure

level change can be treated as root level change since the ef-

fect remains the same when being pushed towards the root.

Thus, the effect of any access rule change can be precisely

determined in terms of

reduction, expansion

,or

zero effect

of valid actor sets. One big advantage in the context of ac-

cess control and user worklist management in PAIS is the

following: If access rules are changed, the effects on the

valid actor sets have to be propagated to user worklists at

some point in time. This point in time can be chosen de-

pending on the particular change effect. If, for example,

the valid actor set is reduced, this poses a potential security

threat on the system: Either work items might be offered to

users who are no longer qualified or, if the valid actor set

becomes empty, no actor will be qualified anymore. Hence,

user worklists should be adapted

immediately

. Contrary, if

the valid actor set is expanded, the only consequence might

be that work items are not offered to all qualified users.

Since this poses no security threat on the PAIS, the prop-

agation of the access rule change to user worklists may be

delayed

; e.g., done offline when no user is working on the

PAIS. Finally, in case of zero effect no action is required

at all. Thus, for direct access rule changes, the approach

presented in this paper supports a quick check on the ef-

fects such that adequate action can be taken; e.g., a delayed

propagation. For access rule changes triggered by organi-

zational modifications we have precisely determined the ef-

fects on the valid actor sets in [11]. For the third possibility,

i.e., the interplay between organizational modifications and

direct access rule changes, interesting effects on each other

might occur, on which we will report in future papers.

5 Related work

In literature many approaches have been presented deal-

ing with challenging issues related to access control (e.g.,

[7, 1, 18, 17]). Most of these approaches apply

Role-Based

Access Control (RBAC)

models for defining and manag-

ing user privileges [6, 9, 1, 5]; e.g., to control the access

to business documents and database objects, or to resolve

the set of actors that qualify for a newly activated task

in a PAIS [3, 2, 16, 18, 17]. Practical issues related to

RBAC (e.g., NIST’s proposed RBAC standard, integration

of RBAC with EIS infrastructures, RBAC in commercial

products) are summarized in [5].

There are only few approaches [15, 7, 4] which address

the problem of organizational change. In [7] eight cate-

gories of structural changes on organizational models are

identified which can be captured by our change framework

as well. We additionally follow a rigorous formal approach

in order to be able to derive the effects of organizational

changes on related access rules as well. The approach in-

troduced in [4] deals with the evolution of access rules in

workflow systems. However, only very simple scenarios

are described without any formal foundation. Furthermore,

the compact definition of access rules is aggravated by the

lack of adequate abstraction mechanisms (e.g., hierarchical

structures). In [15] important issues related to the controlled

change of organizational models are discussed. However,

no concrete solution approach is provided (like, for exam-

ple, formal change operators with well-defined semantics or

mechanisms for adapting access rules after model changes).

6 Summary and outlook

In this paper, we introduced an approach for managing

the life cycle of access rules. In our previous work, the im-

pact of organizational changes on access rules have already

been elaborated. Here, we focused on direct access rule

changes (e.g., due to optimizations or access rule mining).

To be able to directly change access rules, a complete set

of change operations was presented. Furthermore, we pre-

cisely defined the formal semantics of these change opera-

tions in order to avoid any ambiguity when applying these

operations. The correct definition of change operations re-

quired the introduction of a tree-based representation of ac-

cess rules with associated tree operations.

In future work, we will elaborate the effects of access

rule changes (direct or due to organizational changes) on

user worklists in process-aware information systems. For

this we plan to build up cost models to measure the effi-

ciency of different adaptation strategies. Furthermore, we

will dig deeper into the area of access rule mining.

References

[1] E. Bertino. Data security. Data & Knowl. Eng., 25(1–

2):199–216, March 1998.

[2] E. Bertino, E. Ferrari, and V. Alturi. The specification and

enforcement of authorization constraints in WFMS. ACM

Trans. on Inf. and Sys. Sec., 2(1):65–104, 1999.

[3] R. Botha and J. Eloff. A framework for access control in

workflow systems. Information Management and Computer

Security., 9(3):126–133, 2001.

[4] D. Domingos, A. Rito-Silva, and P. Veiga. Authorization

and access control in adaptive workflows. In Proc. ES-

ORICS’03, pages 23–28, 2003.

[5] D. Ferraiolo and D. Kuhn. Role based access control. In

15th National Computer Security Conference, 1992.

[6] D. Ferraiolo, D. Kuhn, and R. Chandramouli. Role–Based

Access Control. Artech House, 2003.

[7] J. Klarmann. A comprehensive support for changes in or-

ganizational models of workflow management systems. In

Proc. ISM’01, pages 375–387, 2001.

[8] T. Ly, S. Rinderle, P. Dadam, and M. Reichert. Mining staff

assignment rules from event-based data. In Int’l Workshop

BPI’05, pages 177–190, 2005.

[9] NIST. Proposed Standard for Role-Based Access Control.

http://csrc.nist.gov/rbac/rbacSTDACM.pdf, 2004.

[10] S. Rinderle and M. Reichert. On the controlled evolu-

tion of access rules in cooperative information systems. In

CoopIS’05, pages 238–255, 2005.

[11] S. Rinderle and M. Reichert. A formal framework for adap-

tive access control models. Int’l Journal of Data Semantics,

IX(9):82–112, 2007.

[12] S. Rinderle, M. Reichert, and P. Dadam. Correctness criteria

for dynamic changes in workflow systems – a survey. Data

and Knowl. Engineering, 50(1):9–34, 2004.

[13] S. Rinderle, M. Reichert, and P. Dadam. Flexible support of

team processes by adaptive workflow systems. Distributed

and Parallel Databases, 16(1):91–116, 2004.

[14] S. Rinderle-Ma and W. van der Aalst. Life-cycle support

for staff assignment rules in information systems. Techni-

cal Report WP-213, Beta Research School for Operations

Management and Logistics, TU Eindhoven, 2007.

[15] W. v.d. Aalst and S. Jablonski. Dealing with workflow

change: Identification of issues an solutions. Int’l Journal

of Comp. Systems, Science and Eng., 15(5):267–276, 2000.

[16] J. Wainer, P. Barthelmess, and A. Kumar. W–RBAC – a

workflow security model incorporating controlled overrid-

ing of constraints. International Journal of Collaborative

Information Systems, 12(4):455–485, 2003.

[17] B. Weber, M. Reichert, W. Wild, and S. Rinderle. Balanc-

ing flexibility and security in adaptive process management

systems. In CoopIS’05, pages 59–76, 2005.

[18] M. zur Muehlen. Resource modeling in workflow applica-

tions. In 1999 Workflow Management Conf., pages 137–153,

1999.