A Temporal Access Control Mechanism for Database Systems.
AbstractThis paper presents a discretionary access control model in which authorizations contain temporal intervals of validity. An authorization is automatically revoked when the associated temporal interval expires. The proposed model provides rules for the automatic derivation of new authorizations from those explicitly specified. Both positive and negative authorizations are supported. A formal definition of those concepts is presented in the paper, together with the semantic interpretation of authorizations and derivation rules as clauses of a general logic program. Issues deriving from the presence of negative authorizations are discussed. We also allow negation in rules: it is possible to derive new authorizations on the basis of the absence of other authorizations. The presence of this type of rules may lead to the generation of different sets of authorizations, depending on the evaluation order. An approach is presented, based on establishing an ordering among authorizations and derivation rules, which guarantees a unique set of valid authorizations. Moreover, we give an algorithm detecting whether such an ordering can be established for a given set of authorizations and rules. Administrative operations for adding, removing, or modifying authorizations and derivation rules are presented and efficiency issues related to these operations are also tackled in the paper. A materialization approach is proposed, allowing to efficiently perform access control.
Introduction
In many real-world situations, permissions have a temporal dimension, in that they are usually limited in time
or may hold only for specific periods of time. In general, however, access control mechanisms provided as part
of commercial data management systems do not have temporal capabilities. In a typical commercial Relational
DBMS (RDBMS), for example, it is not possible to specify, by using the authorization command language, that
a user may access a relation only for a day or a week. If such a need arises, authorization management and access
control must be implemented at application program level. This approach makes authorization management very
difficult, if at all possible. Thus the need of adding temporal capabilities to access control model appears very
strong, as pointed out also by Thomas and Sandhu in [11].
In this paper, we present an authorization model that extends conventional authorization models, like those
provided by commercial RDBMSs, with temporal capabilities. Our temporal authorization model is based on
two main concepts. The first concept is the temporal interval for authorizations. Each authorization has a
time interval associated with it, representing the set of time instants for which the authorization is granted.
An authorization expires after the associated time interval has elapsed. The second concept is the temporal
dependency among authorizations. A temporal dependency can be seen as a rule allowing an authorization to be
derived from the presence (or absence) of another authorization. A temporal dependency can be used, for example,
to specify that a user has an authorization as long as another user has the same or a different authorization. Four
different temporal dependency operators are provided in our model. Temporal dependencies are expressed in
form of derivation rules. Such rules may be parametric, in that a single rule may denote a set of dependencies.
For example, a single derivation rule may specify that a user can read all the files that another user can read,
relatively to an interval of time.
Besides these temporal capabilities, the model supports both positive and negative authorizations. The
capability of supporting explicit denials, provided by negative authorizations, can be used for specifying exceptions
and for supporting a stricter control in the case of decentralized authorization administration [5]. The combination
of positive/negative authorizations with temporal authorizations results in a powerful yet flexible authorization
model.
A critical issue in our model is represented by the presence of derivation rules that allow to derive new
authorizations on the basis of the absence of other authorizations. From one point of view these rules provide
more expressiveness for the representation of temporal dependencies. From another point of view they introduce
the problem of generating a unique set of authorizations. Indeed, a given set of authorizations and derivation
rules may generate different sets of authorizations, depending on the evaluation order. To avoid this problem
we impose a syntactical restriction on the set of derivation rules and we show how this condition guarantees the
uniqueness of the set of derived authorizations. In the paper, we show also how this problem is related to the
problem of negation in logic programming.
Another issue discussed in the paper is the efficiency of the access control. Whenever an access must be
enforced, the system must check whether the appropriate authorization is present in the authorization catalogs
or whether it can be inferred from the authorizations in the catalogs through the derivation rules. The activity
of inferring an authorization can be rather expensive, like performing a query on a deductive database. Thus, a
materialization approach has been adopted. This approach is very similar to the view materialization approach
used in deductive and relational databases [6, 8]. Under such an approach, the results of a view are calculated and
stored when the view is defined, rather than being recomputed each time the view is queried. We use a similar
each time a new authorization is added, all authorizations that can be inferred from it are calculated
and stored into the authorization catalogs. Thus, access control is very efficient, since there is no difference in
costs between explicit authorizations and derived authorizations. Note that administrative operations become
more expensive, but they are much less frequent than access control. Moreover, we use proper maintenance
algorithms to update the materialized authorizations without need of recomputing them all upon execution of
administrative requests.
Time issues in access control and derivation rules for authorizations have come to the attention of the
researchers only recently. The Kerberos system [10], based on the client-server architecture, provides the notion
of ticket, needed for requiring a service to the server, with an associated validity time. The validity time is used
to save the client from the need to acquire a ticket for each interaction with the server. The ticket mechanism
is not used to grant accesses to the resources managed by the system. Rather, it is only used to denote that a
client has been authenticated by the authentication server. Thus, the scope of the temporal ticket mechanism is
very different from our access control model.
Woo and Lam in [13] have proposed a very general formalism for expressing authorization rules. Their
language to specify rules has almost the same expressive power of first order logic. A major issue in their
formalism is the tradeoff between expressiveness and efficiency which seems to be strongly unbalanced in their
approach. We think that it is important to devise more restricted languages focusing only on relevant properties.
The temporal authorization model we propose in this paper is a step in this direction.
A logic language for stating security specifications, based on modal logic, has been proposed by Abadi et Al.
in [1]. However, their logic is mainly used to model concepts such as roles and delegation of authorities and their
framework does not provide any mechanism to express temporal operators for authorization derivation.
A preliminary version of the authorization model presented in this paper was presented by Bertino, Bettini
and Samarati in [4]. The model presented in this paper has a number of major differences with respect to
the previous model. The current model supports both positive and negative authorizations, and it provides
substantial extensions to derivation rules. In particular, in the current model, derivation rules also have temporal
interval of validity. This extension coupled with negative and positive authorizations leads to several interesting
questions concerning both theory and implementation, that we investigate in the current paper. We investigate
also efficiency issues, by proposing a materialization strategy for computing the set of valid authorizations and
by giving algorithms for the maintenance of such materialization.
In this paper, we only deal with discretionary access control and not with mandatory access control. Note,
however, that the majority of DBMS only provide discretionary access control. Therefore, since the focus of
our research is how to extend the authorization facilities provided by a conventional DBMS, we only address
discretionary access control. Recent multilevel DBMS (like Trusted Oracle [9]) provide mandatory access control
coupled with discretionary access control. The new features provided by our model could be orthogonally
incorporated into such systems as well.
The remainder of this paper is organized as follows: Section 2 describes the authorization model giving the
basic definitions and examples. In Section 3 we present the formal semantics for authorizations and derivation
rules and explain the problems due to the presence of negations in rules. A sufficient condition to guarantee the
presence of a unique set of derived authorizations, and an algorithm for checking this condition are given. In
Section 4 we show how all the valid authorizations can be computed. Administrative operations that allow the
users to add, remove, or modify temporal authorizations and rules are described in Section 5. Efficiency issues
concerning the need of updating the set of valid authorizations upon administrative operations are considered in
Section 6. For lack of space we refer the reader interested in proofs to [3].
2 The authorization model
In this section we illustrate our authorization model. To keep our authorization model general and thus applicable
to the protection of information in different data models, we do not make any assumptions on the underlying
data model against which accesses must be controlled and on the access modes users can exercise in the system.
The choice of the data model and of the access modes executable on the objects of the model is to be made when
the system is initialized.
In the following U denotes the set of users, O the set of objects, and M the set of access modes executable
on the objects.
Our model allows the specification of explicit authorizations , stating the permission or denial for users to
exercise access modes on objects, and of derivation rules stating the permission or denial for users to exercise access
modes on objects conditioned on the presence or the absence of other permissions or denials. Each authorization
and derivation rule has a time interval associated with it indicating the time at which the authorization/rule is
applicable.
We assume time to be discrete. In particular, we take as our model of time the natural numbers IN with the
total order relation !.
We are now ready to introduce temporal authorizations and derivation rules.
2.1 Temporal authorizations
In our model both positive and negative authorizations can be specified. Positive authorizations indicate permissions
whereas negative authorizations indicate denials for access.
Authorizations are formally defined as follows.
Definition 2.1 (Authorization) An authorization is a 5-tuple (s,o,m,pn,g) where:
s2 U is the user to whom the authorization is granted;
o2 O is the object to which the authorization refers;
m2 M is the access mode, or privilege, for which the authorization is granted;
pn2 f+; \Gammag indicates whether the authorization is positive (+) or negative (\Gamma);
g2 U is the user who granted the authorization.
Tuple (s,o,m,+,g) states that user s has been granted access mode m on object o by user g. Tuple (s,o,m,\Gamma,g)
states that user s has been forbidden access mode m on object o by user g.
We consider a temporal constraint to be associated with each authorization. We refer to an authorization
together with a temporal constraint as a temporal authorization. Temporal authorizations are defined as follows.
Definition 2.2 (Temporal authorization) A temporal authorization is a pair (time; auth), where time is a
is an authorization.
Temporal authorization ([t 1 ,t 2 ],(s,o,m,pn,g)) states that user g has granted user s an authorization
(positive if negative if mode m on object o that holds between times t 1 and t 2 .
For example, authorization ([10,50],(John,o 1 ,read,+,Bob)) states that John can read object
instants 10 and 50 and that this authorization was granted by Bob.
Note that an authorization without any temporal constraint can be represented as a temporal authorization
whose validity spans from the time at which the authorization is granted to infinity.
In the following, given a temporal authorization A = ([t b ,t e ],(s,o,m,pn,g)) we denote with s(A), o(A),
respectively the subject, the object, the privilege, the sign of the authorization
(positive or negative), the grantor in A, and the starting and ending time of A.
2.2 Derivation rules
Additional authorizations can be derived from the authorizations explicitly specified. The derivation is based on
temporal propositions, used as rules, which allow new temporal authorizations to be derived on the basis of the
presence or the absence of other temporal authorizations. Derivation rules can be applied to both positive as well
as negative authorizations. Like authorizations, derivation rules have a time interval associated with them. The
time interval associated with a derivation rule indicates the set of instants in which the rule is applied.
Derivation rules can also contain variables in their specification. We refer to derivation rules where all the
terms in the authorizations are explicitly specified as ground derivation rules and to derivation rules containing
variables as parametric derivation rules .
2.2.1 Ground derivation rules
Ground derivation rules are defined as follows.
Definition 2.3 (Ground derivation rule) A ground derivation rule is defined as ([t b ,t e ], A 1 hopi A 2 ),
is the time interval associated with the rule, t b 2 IN; t e are
authorizations, is the user who specified the rule, and hopi is one of the following operators: whenever,
aslongas, whenevernot, unless.
Rule ([t b ,t e states that user s 1 is authorized (if pn
'+') or denied (if pn according to the presence or absence (depending on
the operator) of the authorization
The formal semantics of the temporal operators used in the derivation rules will be given in Section 3. Their
intuitive semantics is as follows:
We can derive A 1 for each instant in [t b ,t e ] for which A 2 is given or derived. For example, rule R 1
in

Figure

1, specified by Sam, states that every time, in [7,35], Ann can read object thanks to an
authorization granted by Sam, also Chris can read object
We can derive A 1 for each instant t in [t b ,t e ] such that A 2 is either given or derived for each instant from
t b to t. Note that, unlike the whenever operator, the aslongas operator does not allow to derive A 1 at
an instant t in [t b ,t e ] if there exists an instant t 0 , with t b - t 0 - t, such that A 2 is not given and cannot
be derived at t 0 .
We can derive A 1 for each instant in [t b ,t e ] for which A 2 is neither given nor derived.
We can derive A 1 for each instant t in [t b ,t e ] such that A 2 is neither given nor can be derived for each
instant from t b to t. Note that, unlike the whenevernot, the unless operator does not allow to derive
A 1 at an instant t in [t b ,t e ] if there exists an instant t 0 , with t b - t 0 - t, such that A 2 is given or derived
at t 0 .
Example 2.1 Consider the authorizations and derivation rules illustrated in Figure 1. The following temporal
authorizations can be derived:
authorizations A 1 and A 2 and rule R 1 .
authorization A 1 and rule R 2 .
([41,1], (John,o 1 ,read,+,Sam)) from rule R 3 .
(R1) ([7,35], (Chris,o1,read,+,Sam) whenever (Ann,o1,read,+,Sam))
(R2) ([10,35], (Matt,o1,read,+,Sam) aslongas (Ann,o1,read,+,Sam))

Figure

1: An example of authorizations and derivation rules
ffl ([5,9], (Bob,o 1 ,read,+,Sam)) from rule R 4 .
ffl ([5,9], (Jim,o 1 ,read,+,Sam)) from rules R 4 and R 5 .2.2.2 Authorizations and derivation rules specification
Before proceeding to illustrate the semantics of derivation rules and authorizations we need to make a remark on
authorizations and rules. In our model, only users explicitly authorized can specify authorizations and derivation
rules. Administrative privileges give users the authority of granting accesses on objects to users either directly
(explicit authorizations) or indirectly (through derivation rules). Three different administrative privileges are
considered: refer, administer, and own. The semantics of these privileges is as follows.
ffl refer: If a user has the refer privilege on an object, he can refer to the object in a derivation rule, i.e.,
the object can appear at the right of the temporal operator in a derivation rule specified by the user.
ffl administer: If a user has the administer privilege on an object, he can grant to and revoke from other
users authorizations to access the object (either explicitly or through rules).
ffl own: It indicates possession of an object. When a user creates an object he receives the own privilege on it.
The own privilege allows the user to grant and revoke access authorizations as well as to grant and revoke
administrative privileges (but own) on his object.
Administrative authorizations, i.e., authorizations for administrative privileges are not constrained to a
specific time interval but hold from the time at which they are specified until the time they are revoked by
the object's owner. However, for sake of simplicity and uniformity with respect to other authorizations, we
associate time intervals also to administrative authorizations. The time interval associated with an administrative
authorization spans from the time at which the authorization is specified to 1. Administrative authorizations
are formally defined as follows.
Definition 2.4 (Administrative authorization) An administrative authorization is defined as
is the time interval associated with the authorization, s 2 U is the user
to whom the authorization is granted, O is the object on which the authorization is specified, and p is the
administrative privilege granted to s.
For instance, administrative authorization ([20,1], (John,o 1 ,administer)) states that John has the administer
privilege on object and therefore can grant other users access authorizations on starting from time 20.
For each authorization ([t b ,t e ], A 1 ), we require to have the own or administer privilege on
Moreover, for each derivation rule both the following conditions must be satisfied:
has either the own or administer privilege on
has either the own, administer, or refer privilege on
These conditions are checked at the time an authorization/rule is specified and the insertion of the autho-
rization/rule is accepted only if the conditions are satisfied 1 .
2.2.3 Parametric derivation rules
Derivation rules can also use variables in their specification. We refer to these rules as parametric derivation
rules. To introduce parametric derivation rules, we first give the definition of authorization pattern.
Definition 2.5 (Authorization pattern) An authorization pattern AP is a tuple (s,o,m,pn,g) where s,g
\Gammag.
Symbol ' ' is a special character denoting any user, object, or access mode, depending on its position in the
authorization pattern.
Definition 2.6 (Matching authorization) An authorization A matches a pattern AP if each element of A is
equal to the corresponding element of AP, if different from ' '.
Parametric derivation rules are defined as follows.
Definition 2.7 (Parametric derivation rule) A parametric derivation rule is defined as
are authorization patterns, and all the other elements are as in
definition 2.3. Authorization patterns in the rule must verify the following conditions:
and at least one element among s(AP 1 are different from ' '
ffl if symbol ' ' is used for s(AP 1 used for the corresponding element s(AP 2 ),
We will elaborate on this in Section 5.
(R1) ([1,1], (Chris,*,+,Sam) whenever (sam-friends,*,+,Sam))

Figure

2: An example of parametric derivation rules
A parametric derivation rule can be seen as a shorthand for specifying several ground derivation rules operating
on different subjects, objects, or access modes. Given a parametric derivation rule, we refer to the ground
rules to which it corresponds as instances of the parametric rule. This is expressed by the following definition.
Definition 2.8 (Parametric rule instances) Let derivation
rule. The set of instances of R is the set composed of all possible ground derivation rules
([t b ,t e ], Am hopi An) such that Am matches AP 1 , An matches AP 2 , and such that the following conditions are
Note that instances derived from parametric rules must also satisfy the constraints on administrative privileges
illustrated in the previous section for rules.
The following example illustrates the use of parametric derivation rules.
Example 2.2 Sam wishes to grant the authorization to exercise a certain number of access modes on certain
objects to a group of friends, Chris, Matt, and Jim. Instead of specifying one authorization for every access
mode and every object for each of his friends, Sam can proceed as follows. A new user sam-friends, playing the
role of the group is defined. For each user that Sam wishes to include in the group, a whenever rule parametric
over the object and the access mode is defined where the authorization at the left of the operator has as subject
the user identifier and the authorization at the right has as subject sam-friends (see Figure 2). The time
interval associated with the rule can be interpreted as the time interval at which the user appearing on the left
is considered as a member of group sam-friends. For example, rules R 1 ,R 2 , and R 3 in Figure 2 allow given a
positive authorization specified for sam-friends, to derive the same authorization for for Chris, Matt, and Jim
respectively. Rule R 2 expires at time 100 (intuitively, after that time Matt will not be considered anymore a
member of the group); hence, the time interval associated with the authorizations derived for Matt will have
ending time equal to 100. 4
In the example above, Sam appears as grantor of the authorization on the right of the operators in rules R 1 -R 3 .
Hence, authorizations for Chris, Matt, and Jim will be derived only from authorizations granted to sam-friends
by Sam. Sam can require the rules to fire regardless of the grantor of the authorizations to sam-friends by putting
' ' as grantor in the right side of rules R 1 -R 3 .
3 Formal semantics
In this section we formalize the semantics of temporal authorizations and derivation rules. First of all it is
necessary to point out that the possibility to express negative authorizations introduces potential conflicts among
authorizations. Suppose that a negative authorization for a privilege on an object is granted to a user who has
previously obtained the same privilege on that object. We then have, for a given time interval, the presence
of both negative and positive authorizations. This is not to be intended as an inconsistency, since we consider
negative authorizations as prevailing with respect to positive authorizations.
Considering the set of authorizations and rules in Figure 2, from rule R 3 and authorization A 4 we can derive
authorization A 5 we have ([50,1],(Jim,o 2 ,write,-,John)). This
is not an inconsistency, since we apply the denials-take-precedence principle. Hence, the negative authorization
prevails, and Jim will have the authorization to write object only in the interval [10,49]. The formal semantics
obeys to the denials-take-precedence principle. We start the description of the formal semantics by introducing
the concept of a TAB.
Definition 3.1 (Temporal Authorization Base) A Temporal Authorization Base (TAB) is a set of temporal
authorizations and derivation rules.
In the rest of the paper, we denote with INST-TAB a TAB where each parametric rule has been substituted
by its set of instances according to Definition 2.8. Obviously, TAB and INST-TAB are equivalent.
The semantics of a TAB is given as a set of clauses in a general logic program corresponding to INST-TAB.
We use a logic with two sorts, the natural numbers (IN) as a temporal sort and a generic domain (D) as the other
sort. The language includes constant symbols natural numbers, a finite set of constant symbols (e.g.,
for elements in D, and temporal variable symbols t; t include the
temporal predicate symbols - and ! with the fixed interpretation of the corresponding order relation on natural
numbers, the predicate symbol F () with temporal arity 1 and domain arity 5, the predicate symbols FN () and
FG () with temporal arity 2 and domain arity 5, and the predicate symbol G() with temporal arity 1 and domain
arity 3. The resulting language is very similar to the temporal deductive language proposed in [2] with the main
difference being the presence of negation in our rules.
For each type of authorization/rule in INST-TAB, Table 1 reports its corresponding clause/set of clauses.
Intuitively, the predicate F () is used to represent the authorizations at specific instants. The fact that F (t;
is true in an interpretation corresponds to the validity of A at instant t according to that interpretation. The
predicates G(); FN () and FP () are auxiliary predicates, used to avoid quantification. Intuitively, G(t; s; o; m) is true
in an interpretation if there is at least one negative authorization, with the same s,o,m, valid at instant t according
to that interpretation. FN (t 00 ; t; A) is true in an interpretation if there is at least an instant t 0 with t 00 - t at
which authorization A is false according to that interpretation. FP (t 00 ; t; A) is true in an interpretation if there is
at least an instant t 0 with t 00 - t t at which authorization A is true according to that interpretation.
We denote the logic program corresponding to a TAB with PTAB . We consider stable model semantics of
logic programs with negation [7] to identify the models 2 of PTAB .
Definition 3.2 (Valid Authorization) Given a model M of PTAB , an authorization A is said to be valid at
time t with respect to M if F (t; A) is contained in M . If PTAB has a unique model M and M contains F (t; A),
we simply say that A is valid at time t.
3.1 Restrictions on rules
An important property that we require for our set of temporal authorizations and rules is that we must always
be able to derive a unique set of valid authorizations. This means, for example, that each set of rules together
with a fixed set of explicit authorizations should not derive different authorizations depending on the evaluation
order. We give an example illustrating how different authorizations can be derived depending on the evaluation
order.
Example 3.1 Consider the following rules:
(R
(R
Suppose that there are no explicit authorizations for A 1 or A 2 in the TAB and these are the only rules. If we
consider first R 1 we derive authorization A 1 and we cannot derive A 2 . If we consider first R 2 , we derive A 2 and not
A 1 . Hence, we have two different sets of derived authorizations. In this case there is no reason to give preference
to one set or the other. 4
From the point of view of the semantics that we have given, the property of always having a unique set
of valid authorizations is guaranteed only if there exists a unique model of the program corresponding to the
TAB. Hence, we limit derivation rules so that a unique model can be computed. In the rest of this section we
formally define sets of rules that should be avoided in order to guarantee a unique model for PTAB , and we give
an algorithm for their detection.
In the following, we use the term negative operator (negop) to refer to whenevernot or unless, and
negative rule to refer to a rule using a negative operator. Similarly, positive operator (posop) is used to refer to
whenever or aslongas, present operator (presentop) is used to refer to whenever or whenevernot, and
2 Due to the properties of the resulting program, in this case stable models are identical to well-founded models [12].
G(t; s; o; m) / F (t; s; o; m; \Gamma; g)

Table

1: Semantics of temporal authorizations and rules
past operator (pastop) is used to refer to unless or aslongas. Moreover, we use symbols A i as a shortcut for
the 5-tuple (s
binary relation ,! among the temporal authorizations appearing in INST-TAB is defined as follows:
ffl if there is a rule ([t b ,t e ], Am hopi An ) in INST-TAB, where hopi is an arbitrary operator, then An [t] ,! Am [t]
for each t with t b -t-t e . The ,! relation represents a dependency of Am at instant t from An at the same
instant. When hopi is a negative operator we say that ,! represents a strict dependency.
ffl if there is a rule ([t b ,t e ], Am hpastopi An ) in INST-TAB, then An [t] ,! Am
represents a strict dependency.
Using this relation we can define the more complex notion of priority among temporal authorizations.
Definition 3.3 (Priority) An authorization An at time t has higher priority than an authorization Am at time
one of the following conditions holds:
ffl a sequence An [t]=A 1 exists such that at least one of the ,! relationships
is a strict dependency,
ffl two sequences An [t]=A 1
l
exist such that s(A
l
l
l
ffl an authorization A l and an instant t 00 exist such that An [t] ? A l [t 00 ] and A l [t
Note that the second condition in the above definition implies that each negative authorization has higher
priority than its positive counterpart at the same instant.
We are now ready to identify critical sets of derivation rules.
Definition 3.4 (Critical set) A TAB contains a critical set of rules if and only if an authorization Am in
INST-TAB and an instant t exist such that Am at instant t has priority over itself ( Am [t] ? Am [t]).
Example 3.2 Consider the set of rules:
(R 1
(R
(R 3
These three rules form a critical set. It is easily checked that definition 3.4 applies to this set of rules. In-
deed, by the first condition in Definition 3.3 and rules R 1 and R 2 we have that (Bob,o 1 ,write,+,Jim)[41]
the second condition, and, again by the first condition and rule R 3 , we obtain (John,o
Applying twice the third condition (transitivity) we have (Bob,o 1 ,write,+,Jim)[41]
Hence, this set of rules is critical. 4
The CSD (Critical Set Detection) algorithm, described in the next subsection, can be used to recognize and
reject a TAB containing a critical set.
3.2 An algorithm for critical set detection
We use a set of disjoint 3 intervals compact notation for the set of natural numbers
included in these intervals. Hence, the operations of union (T 1 [T 2 ), intersection
have the usual semantics of set operations. However, we implement these operations so that they can be performed
using intervals and giving the result as a set of disjoint intervals. We use two kinds of set membership: t 2 T is
true if t is one of the natural numbers represented by T , exactly one
of the disjoint intervals of T .
Given a INST-TAB, the algorithm for critical set detection returns FALSE if a critical set exists in TAB;
otherwise it returns a sequence of sets (levels) hL representing a partition of the set of pairs hA; ti for
each authorization A appearing (either explicitly or in a rule) in INST-TAB and for each instant t between 1
and tmax . We define tmax to be the first instant greater than the maximum temporal constant appearing in
INST-TAB. In the following, we refer to each set L i as level i. If pair hA; T i is in level i , we say that A is in
level i for each t 2 T . Intuitively, authorizations appearing at lower levels for a certain set of instants have higher
priority for evaluation than authorizations appearing at higher levels (for the same or different sets of instants).
In this and other algorithms in the paper, we use the functions 'Add()' and `Delete()' to add/delete or modify
the pairs hA; T i. The result of the statement 'Add hA to L' is the addition of that pair to L if there is no
in L for any T , otherwise it is the replacement of hA Analogously, the result
of 'Delete hA from L' is the deletion of that pair from L if the pair hA
it is the replacement of hA
The algorithm is reported in Figures 3,4, and 5, and it works as follows. In step 1, tmax is substituted for each
occurrence of symbol '1' in time intervals associated with authorizations and rules in INST-TAB. There is no
need to consider all time instants up to 1. For instants greater than tmax the authorizations that are valid remain
unchanged. If a critical set exists, it will be found at a time lower than or equal to tmax . In step 2, max-level is
determined as the number of authorizations appearing in INST-TAB multiplied by tmax . max-level corresponds
to the number of pairs hA; ti to be partitioned. Then, the number of levels (top-level) is initialized to 1. Level
initially contains all authorizations in INST-TAB for each instant between 1 and tmax . Step 3 recursively
calls function 'check-levels()' which examines the authorizations at different levels and the dependencies among
authorizations. It possibly changes level to pairs hA; T i on the basis of the dependency. The loop at step 3 ends
when the last call of 'check-levels()' does not change any level or the level number is greater than max-level. In
the first case, the levels constructed by the algorithm are returned. In the second case, FALSE is returned.
Function 'check-levels()' is composed of three steps. In step 1, all levels from top-level to 1 are examined. If a
negative authorization An is found at a given level l for a certain set of time intervals T n;l , the level of all positive
authorizations Am having same subject, object, and access mode as An and appearing at a level lower than l is
3 Two intervals are considered disjoint if they cannot be collapsed into a single one (note that [1; 2] and [3; 4] are not disjoint).
Algorithm 3.1 Critical Set Detection (CSD) Algorithm
INPUT: INST-TAB.
OUTPUT: FALSE if a critical set is detected;
otherwise a sequence of sets representing a partition of
the set of pairs hA; ti such that A appears in INST-TAB and 1 - t - t max .
Each set L i is called level i and L
T j;i is a set of time intervals associated with A j at level i.
1. For each temporal authorization or rule having the time limit
2. max-level := n-auth*t max , where n-auth is the number of authorizations appearing in INST-TAB
top-level
For each authorization A appearing in INST-TAB Do
endfor
3. Repeat check-levels
Until there are no changes to any level or top-level ? max-level.
4. Return FALSE if top-level ? max-level, the sequence

Figure

3: An Algorithm for critical set detection
increased to l + 1 for all time instants in T n;l . In step 2, all the rules are
evaluated. Levels are examined in decreasing order starting from top-level. Every time authorization An is found
at level l for a time interval T n;l not disjoint from [t b ; t e ], function 'update()' is called to increase the level of
Am for the time instants appearing in both T n;l and [t b ; t e ]. The new level is l, if the operator in the rule is
whenever, and l + 1, if it is whenevernot. In step 2, all the rules are evaluated.
Again, levels are examined in decreasing order starting from top-level. Every time authorization An is found at
level l for a time interval T n;l not disjoint from [t b ; t e ], function 'update()' is called to increase the level of Am for
the time instants greater than or equal to the minimum instant t l in both . The new level
is l, for instant t l , and l + 1, for instants in [t b ; t e ] greater than it.
Function 'update()', given a level lev, an authorization Am , and a set of time intervals T , brings authorization Am
at level lev for each time instant for which Am appears at levels lower than lev.
Example 3.3 Consider a TAB containing the following authorizations and rules:
([40,60],A
where A
2jJohn indicates a negative authorization with same subject, object, and access mode as A 2 but with John
as grantor. The algorithm for critical set detection returns the following levels:
Correctness of the CSD algorithm and model uniqueness
The following two theorems state some properties of the levels returned by the CSD algorithm with respect to
the dependencies among authorizations.
Theorem 3.1 Let A n and A m be two authorizations appearing in INST-TAB and t; t 0 be two time instants lower
than or equal to t max such that A n [t] ,! A m [t 0 ]. Then, either the algorithm returns FALSE or, at the end of the
execution, authorization A m for instant t 0 appears at a level higher than or equal to that of authorization A n for
instant t. If ,! is a strict dependency then A m for instant t 0 appears at a level higher than that of A n for instant t.
Theorem 3.2 Let A n and A m be two authorizations appearing in INST-TAB with same subject, access mode,
and object but with different sign. Then, either the algorithm returns FALSE or, at the end of the execution,
the positive authorization appears at a level higher than that of the negative authorization for each time instant
between 1 and t max .
The correctness of the CSD algorithm is stated by the following theorem.
Theorem 3.3 Given a TAB, i) the CSD algorithm terminates and ii) it returns a FALSE value if and only if
the TAB contains a critical set.
As we have observed, for the purpose of determining the authorization state of the system at a certain instant,
the uniqueness of the PTAB model at that instant is required. The uniqueness of the model in absence of critical
sets is guaranteed by the following theorem.
Theorem 3.4 Given a TAB with no critical sets, the corresponding logic program PTAB has a unique model.
4 Materialization of authorizations
In our model, the control of whether a request to access an object for a given access mode can be authorized may
require the evaluation of several rules. Two different strategies can be used to enforce access control:
Function check-levels(hL
1. For l
partition the set of pairs hA l such that
ig such that
For each S i Do
For h :=
For each
such that s(Am)=s i , o(Am)=o i , m(Am)=m i ,
Delete
endfor
endfor
endfor
endfor
2. For each rule
TR
l := top-level
While TR 6= f[ ]g and l - 1 Do
Case hpresentopi of
endcase
TR := TR n T n;l
endif
l
endwhile
endfor
3. For each rule
l := top-level
While
case hpastopi of
aslongas: If t l ! t f then update (l
update
unless: update (l
endcase
endif
l
endwhile
endfor

Figure

4: Function check-levels
Function
If lev ? top-level then
top-level := lev
endif
While T 6= f[ ]g and h - 1 Do
Delete
endif
endwhile

Figure

5: Function update
Run-time derivation: Every time a user requires an access, the system verifies whether the access request can
be authorized on the basis of the authorizations and the derivations rules in TAB and by computing, if
necessary, the derived authorizations.
Materialization: The system permanently maintains all the valid authorizations, both explicit and derived.
Upon an access request, the system can immediately check whether a valid corresponding positive authorization
exists.
Both these approaches have some pros and cons. The first approach has the advantage that no actions are
required upon modification of the TAB; however access control becomes cumbersome since each access request
may require the computation of derived authorizations. In the second approach, this run-time computation is
avoided at the price of explicitly maintaining the derived authorizations that will have to be updated every time
the TAB is modified.
generally, access requests are considerably more frequent than administrative requests modifying authorizations
and/or rules, we argue that the second approach is preferable. Moreover, the drawback provided
by the need of recalculating the explicit authorizations upon modifications to the TAB can be overcome by the
application of efficient algorithms that update the materialized authorizations upon modifications without need
of reconsidering all rules and recomputing all the materialized authorizations.
For the reasons above, we adopt the materialization approach. In the following we illustrate how to compute,
given a TAB, the corresponding valid authorizations. In Section 6 we will provide algorithms for reflecting
changes to the TAB in the materialized authorizations without the need of recomputing all authorizations from
the beginning.
Definition 4.1 (Temporal Authorization Base Extent) The Temporal Authorization Base Extent (TABEXT )
of TAB is the set of valid authorizations derived from TAB.
TABEXT contains all the valid authorizations of TAB computed according to the semantics of explicit
authorizations and derivation rules.
Authorizations are maintained in TABEXT using a compact representation: each A k is associated with a set
T k of disjoint intervals, representing the instants at which A k is valid.
At time t=0, TABEXT does not contain any explicit or derived authorizations. Upon the execution of each
administrative operation (such as grant/revoke of authorizations or rules) TABEXT is updated to reflect the
effects of the operation execution.
If the strategy of maintaining both explicit and derived authorizations is not adopted from the beginning,
it is necessary to populate TABEXT from the explicit authorizations and derivation rules already present in
TAB. If there is no critical set, the CSD algorithm returns a sequence of levels hL such that, for each
authorization, the corresponding set of instants partitioned among the k levels. This sequence is
essential to establish an evaluation order that guarantees that the computed TABEXT contains all and only valid
authorizations.
Algorithm 4.1, reported in Figure 6, computes the TABEXT of a TAB. The algorithm receives as input the
TAB's instantiated version INST-TAB and the sequence hL given by the CSD algorithm. The algorithm
is based on the technique used to compute the model of (locally) stratified logic programs. Intuitively, rule
instances and authorizations are partitioned among a finite number of levels according to a priority relation and
inferences at a certain level are performed only when all possible inferences at lower levels have been performed.
The main step of the algorithm (step 2) is an iteration on the k levels returned by the CSD algorithm. For
each level i, starting from
a) Constructs the set X i of authorizations and rules available at level i. More precisely, X i contains pairs
is an element of INST-TAB. x can be an explicit authorization ([t b ,t e ],A m ) or a rule ([t b ,t e ],
Am hopiAn ). T 0 is the set of intervals representing all instants such that Am is in level i for instant
t.
b) Derives new authorizations drawing all possible inferences at level i by using the elements in X i and the
authorizations previously derived.
The last step of the algorithm (step 3) extends the intervals of derived authorizations on the basis of the
following observation:
If we have derived an authorization for the instant t max , we are guaranteed that the authorization can
be derived for any instant greater than t max
This fact is due to the particular form of our rules and it is formally proved as part of the proof of Theorem 4.1.
The following example illustrates an application of the algorithm for TABEXT generation.
Algorithm 4.1
INPUT: The output of the CSD Algorithm and INST-TAB.
is a valid authorization for each interval in T i g
sequence hX
with x=([t b ,te ],Am ) or x=([t b ,te ],Am hopi An ), and T 0
;g.
and each X i are initialized to be empty
For i:=1 to k Do
a) #Construction of X i #
For each element x in INST-TAB, where x=([t b ,te ],Am ) or x=([t b ,te ],Am hopiAn ) Do
endfor
b) #Construction of TABEXT#
Repeat
For each element hx; T
If
endfor
Until no new authorization can be derived
endfor
For each hA; T i in TABEXT with t with 1.
Function
Case op of
aslongas: If t b 2 I for some I 2Tn then T :=
else
unless: If
else
endif
endcase
If pn(Am
return T

Figure

An algorithm for TABEXT generation.
Example 4.1 Consider the TAB illustrated in Example 3.3. The levels computed by the CSD algorithm are
illustrated in the same example. We now apply the algorithm for TABEXT generation. Let TAB (i)
EXT be the
TABEXT resulting from the i-th iteration.
ffl For
2.b TAB (1)
since h([10; 200]; A 1 ); f[10; 200]g)i is the only element of X 1 and there
are no authorizations in TAB (1)
blocking A 1 .
ffl For
2.a
80]gig.
2.b From h([40; 60]; A
2jJohn whenevernot A 3 ); f[40; 60]gi and authorizations in TAB (1)
EXT we obtain:
From h([5; 100]; A 2 whenever A 1 ); f[5; 39]; [61; 100]gi we obtain:
Hence, TAB (2)
80]gig.
ffl For
2.a
2.b Function Derive-auth(h([5; 100]; A 2 whenever A 1 ); f[40; 60]gi, TAB (2)
returns T=;, since authorization
for the time interval [40,60].
80]gig.
ffl There are no more levels, t 201 in this example and it does not appear in TAB (3)
EXT . Hence, the
algorithm terminates returning TAB (3)
EXT .The correctness of the algorithm is stated by the following theorem:
Theorem 4.1 Given TABEXT as returned by Algorithm 4.1, an authorization A is valid at time t if and only if
there exists hA; T i in TABEXT with t 2 T .
Once we have an updated TABEXT , each access request can be checked against TABEXT . An access request
from user s 1 to exercise access mode m 1 on object o 1 at time t will be allowed only if a pair hA; T i exists in
TABEXT such that s(A)=s 1 , o(A)=o 1 , m(A)=m 1 , pn(A)= '+', and t 2 T .
5 TAB administration
Administrative operations allow the users to add, remove, or modify temporal authorizations and derivation rules
and to give or revoke other users the right to administer their objects or to refer to them in derivation rules.
Each temporal authorization, and each derivation rule in the TAB is identified by a unique label assigned by
the system at the time of its insertion. The label allows the user to refer to a specific temporal authorization or
derivation rule upon execution of administrative operations.
In the following we discuss the administrative operations considered in our model. The syntax of the
operations in BNF form is given in Table 2. With reference to the figure, non terminal symbols hsubjecti,
hobjecti,haccess-modei, hauth-ti, and hnat-numberi represent elements of the domains S, O; M; f+; \Gammag; and
IN respectively. Non terminal symbols haidi and hridi represent system labels. Symbol # can be used in the
specification of the starting time for an authorization/rule to indicate the time at which the administrative request
is submitted to the system.
Administrative requests can affect access authorizations, derivation rules, or administrative authorizations,
as follows.
Requests affecting the authorizations on an object
These are requests for granting or revoking authorizations on an object. The user requesting them must
have either the own or the administer privilege on the object.
Grant To grant an access mode on an object to a subject for a specified time interval. The grant operation
results in the addition of a new temporal authorization. The starting time of the authorization must
be greater than or equal to the time at which the authorization is inserted (it is not possible to specify
retroactive authorizations).
Deny To deny an access mode on an object to a subject for a given time interval. The deny operation
results in the addition of a new temporal negative authorization.
Revoke To revoke an access mode on an object from a subject. The revoke operation can be required with
reference to a single authorization by specifying its label (i.e., the deletion of a specific authorization is
requested) or with reference to an access mode on an object with respect to a given time interval. The
revoke operation results in the deletion or modification of all the temporal authorizations of the revokee
for the access mode on the object granted by the user who revokes the privilege. If the time interval
for which the revocation is requested spans from the time of the request to 1 all authorizations for
the access mode on the object granted by the revokee to the revoker will be deleted. If the revocation
is required for a specific time interval, all the authorizations for the access mode on the object granted
to the revokee by the revoker will be deleted or modified to exclude the interval (and possibly split in
more authorizations). Note that a user can revoke only the authorizations he granted and then the
revoke request by a user affects only the authorizations granted by that specific user.
Revoke negation To revoke the negation for an access mode on an object from a subject. It is analogous
to the Revoke operation with the only exception that it applies to negative authorizations.
ffl Requests affecting rules
These are requests for specifying or deleting rules. The user requesting them must have either the own or the
administer privilege on the object appearing at the left of the operator and either the own, administer,
or refer privilege on the object appearing at the right of the operator.
Addrule To add a new derivation rule. The grantor of the authorization appearing at the left of the
temporal operator identifies the user inserting the rule. Like for authorizations, the starting time of
the interval associated with the rule must be greater than the time at which the request is specified.
Droprule To drop a derivation rule previously specified. The operation requires, as argument, the label
of the rule to be deleted. Like for the revocation of authorizations, a user can drop only the rules that
he has specified.
ffl Requests affecting administrative authorizations
These are requests for granting or revoking administrative privileges on an object. They can be executed
only by the owner of the object.
Grantadm To grant the administer privilege on an object to a subject. It results in a new administrative
authorization spanning from the time of the request to 1.
Revokeadm To revoke the administer privilege on an object to a subject. It results in: i) the deletion
of the authorization for the administer privilege on the object previously granted to the revokee,
and ii) the deletion of the authorizations on the object and of the derivation rules where the object
appears in the authorization at the left of the operator specified by the revokee. If the revokee does
not have the reference privilege on the object, also the derivation rules where the object appears in
the authorization at the right of the operator are deleted.
To grant the refer privilege on an object to a subject.
Revokeref To revoke the refer privilege on an object to a subject. It results in the deletion of the
authorization for the refer privilege on the object previously granted to the subject and in the deletion
of all the rules granted by the revokee where the object appears in the authorization at the right of
the operator.
Grant haccess-modei on hobjecti to hsubjecti
hdenyi ::= Deny haccess-modei on hobjecti to hsubjecti
Revoke haccess-modei on hobjecti from hsubjecti
Revoke negation haccess-modei on hobjecti
from hsubjecti
hgrant-admi ::= Grantadm on hobjecti to hsubjecti
hrevoke-admi ::= Revokeadm on hobjecti from hsubjecti
hgrant-refi ::= Grantref on hobjecti to hsubjecti
hrevoke-refi ::= Revokeref on hobjecti from hsubjecti

Table

2: Syntax of administrative operations
6 TABEXT Maintenance
Execution of administrative operations illustrated in the previous section can change the set of valid authoriza-
tions. The TABEXT has to be modified accordingly. For instance, the insertion of an explicit authorization can
cause the deletion of authorizations from TABEXT . This happens if the authorization appears in the right side
of a negative rule, or if it is a negative authorization. A similar problem arises for authorization deletion.
We have devised a set of algorithms that update TABEXT upon each administrative request, without the
need of recomputing all the materialized authorizations. These algorithms use methods similar to those employed
for the maintenance of materialized recursive views with negation [8].
The maintenance algorithms make use of sequences defined in Section 4, that
are permanently stored and updated by them to reflect the changes in TAB. The approach exploits the fact that,
authorizations in TAB (i)
EXT are derived using only authorizations in TAB (i\Gamma1)
EXT and rules in X i . Thus, a change
for an authorization/rule of level i does not affect authorization in TAB (j)
EXT with Only authorizations in
EXT with need to be reconsidered.
In the following, we illustrate an algorithm for updating TABEXT upon insertion of new positive autho-
rizations, based on the Dred algorithm [8]. The methods to maintain TABEXT after the insertion/deletion of
a negative authorization and the deletion of a positive one are very similar to that for positive authorizations
insertion. We refer the reader to [3] for the description of these algorithms and for the ones for insertion/deletion
of derivation rules.
6.1 Insertion of explicit positive authorizations
The algorithm in Figure 7 implements the maintenance of TABEXT for the insertion of an explicit positive au-
thorization. It receives as input TABEXT , INST-TAB, its corresponding sequences hL
and a positive authorization and returns TAB u
EXT , the set of valid authorizations resulting from the insertion of
the positive authorization, and the updated sequences hL 0
i. The algorithm works as
follows: suppose that a positive authorization ([t b ,t e ],A k ) has been inserted. If the inserted authorization does not
appear in INST-TAB or its time interval exceeds tmax , it is necessary to recompute the sequence hL
which authorizations have been partitioned by the CSD algorithm, because the partition of the authorizations
among the levels changes and the number of levels could increase (step 1). In step 2 the positive authorization is
inserted in INST-TAB. Step 3 iteratively considers all the elements hA,T i in TABEXT and replaces each symbol
'1' in T with tmax . Step 4 initializes S INS , SDEL and TAB u
EXT . S INS and SDEL are two data structures
containing the authorizations inserted and deleted from TAB u
EXT till the current point of the computation. The
authorizations are kept in S INS and SDEL using the same representation as for TABEXT . Then (step 5), the
algorithm computes l min , the least level in which authorization A k appears in an instant t of the time interval
All the operations for TABEXT maintenance will be executed starting from level l min . Step 6 computes
the sets X 0
. In this case X 0
since the insertion of the new authorization does not change the
levels of the authorizations in INST-TAB. Step 7 is an iteration on the levels returned by the CSD algorithm,
starting from level l min . For each level i , the algorithm performs the following operations:
ffl compute the set X 0
by adding to X i the element hA is the
set of time intervals representing all the time instants in which the inserted authorization is in
level
ffl compute T , the set of time intervals representing all the time instants in which the inserted
authorization is in level i and it is not blocked by a negative authorization;
ffl insert the element hA k ; T i in S INS and in TAB u
ffl call function 'Dred-Ext()' that computes all the authorizations of level i which have to be inserted or removed
from TAB u
EXT because of the insertion of ([t b
Finally, the last step of the algorithm iteratively considers all the elements in the updated TABEXT
and substitutes each value tmax in T with symbol '1'.
Function 'Dred-Ext()', given a level l and the authorizations inserted and deleted from TAB u
EXT till the
current point in the computation, updates the TAB u
EXT according to the rules that can be fired in level l. The
function consists of three main steps: step (a) adds to SDEL and removes from TAB u
EXT an overestimate of
the authorizations that need to be deleted because of the insertion of ([t b ;t e ];A k ). An authorization is added to
SDEL by step (a) if the insertion of ([t b ;t e ];A k ) invalidates any derivation of the authorization from the elements
of
l . Step (b) reinserts in TAB u
EXT the authorizations deleted in the previous step that have an alternative
derivation. The reinserted authorizations are obviously removed from SDEL . Finally step (c) adds to S INS and to
TAB u
EXT all the new authorizations that can be derived from the derivation rules in X 0
l because of the insertion
of ([t b
Theorem 6.1 Given a TAB and a positive authorization ([t b ,t e ],A k ), i) Algorithm 6.1 terminates. Moreover
ii) the sequence hX 0
computed by the algorithm is correct. Finally iii) the TAB u
EXT , computed by the
algorithm contains all and only the valid authorizations wrt TAB [ ([t b ,t e ],A k ).
The following example illustrates how Algorithm 6.1 works.
Example 6.1 Consider the TAB illustrated in Example 3.3. The set of materialized authorizations and sets X i
for this TAB are illustrated in Example 4.1. Suppose that at time t=7 authorization ([40,50],A 3 ) is inserted in
the TAB. It is not necessary to run the CSD algorithm since the upper bound of the time interval of the inserted
authorization does not exceed tmax=201, and A 3 already appears in INST-TAB. Since l all the X 0
with 1- i - 3 will be considered.
After the first iteration of step (7) of Algorithm 6.1, X 0
inserts h[40; 50];A 3 i in TAB u
EXT .
In the second iteration, each element of X 0
(a) of function 'Dred-Ext()' searches for
elements
2 such that
n i is in S INS with T INS
;. The only
Algorithm 6.1 Insertion of an explicit positive authorization
positive authorization ([t b ,te ],A k ).
(each element denoted with hA
The sequence
The sequence hX
EXT (the updated TABEXT ).
2) The sequence hL 0
The sequence hX 0
else k:= k, L 0
For each hA; T i in TABEXT substitute each symbol '1' in T with tmax
SINS and SDEL are initialized to be empty, TAB u
For i:=lmin to k Do
(a) If 9X i then X 0
else
(b) T :=
fT u
(c) Add to SINS and TAB u
(d) hTI ,TD i := Dred-Ext(SINS,SDEL ,i)
(e) For each
(f) For each
endfor
For each
EXT , substitute each value

Figure

7: An Algorithm for positive authorization insertion
Function Dred-Ext(S I ,S D ,l)
(a) Repeat
For each hx; T
l , where
If pn(Am
else
Case op of
endcase
else
endif
endfor
Until SD does not change
For each
(b) Repeat
For each hx; T
l , where
Delete
endfor
Until SD does not change
(c) Repeat
For each hx; T
l , where
If pn(Am
else
Case op of
endcase
else
I and TAB u
endif
endfor
Until S I does not change
For each
For each
return hS I ,S D i

Figure

8: Function Dred-Ext
Function
If
Case op of
aslongas,unless: If T
ts := max(ftjt2Tg)
endif
endcase
else
If
return T

Figure

9: Function Derive
element that satisfies the condition is
is added to SDEL and removed
from TAB u
EXT . In the third iteration, step (c) of function 'Dred-Ext()' is executed and fhA 2 ; f[40; 50]gig is added
to S INS . No other changes will be made by this iteration. Hence, the algorithm terminates. The resulting
TAB u
EXT is:
TAB u
7 Conclusions and future work
In this paper we have presented an authorization model with temporal capabilities. The model introduces the
concept of temporal authorization which is an authorization together with a start and an expiration time. Both
negative as well as positive authorizations can be specified. Derivation rules can be expressed which allow new
temporal authorizations to be derived on the basis of the presence or the absence of other temporal authorizations.
Four different temporal operators can be used in the derivation rules. Administrative authorizations regulate the
insertion and removal of authorizations and rules by users.
We have given the formal semantics of temporal authorizations and derivation rules in terms of a general logic
program. The problem of ensuring the uniqueness of the derived authorizations corresponds to the theoretical
issue of the existence of a unique model for the logic program. We have presented an approach to solve this problem
based on the stratification of authorizations and derivation rules. We have provided an algorithm that determines
whether an authorization base has a stratification and proved that, if the authorization base is stratified, a unique
set of derived authorizations is always computed.
Performance issues have been addressed and a materialization approach in which derived authorizations are
explicitly stored has been proposed. Algorithms for building the materialized set of derived authorizations and
for maintaining them upon execution of administrative operations have been proposed.
The proposed model is currently under implementation to investigate the system's performance for various
characteristics of the authorization base.
We are currently extending this work in several directions. First, decentralized authorization administration
facilities are being added to the model. Second, the model is being extended with periodic authorizations. Such
capability allows to specify, for example, that a given subject may access a data item every Thursday. Also, access
control based on past access histories will be included into the model. Finally, we plan to investigate different
temporal logic formalisms and constraint logic programming as possible foundations for temporal authorization
models.

Acknowledgment

The authors wish to thank Prof. Michael Gelfond for useful discussions on problems related to the semantics of
negation.



--R

A calculus for access control in distributed systems.
On the representation of infinite temporal data and queries (extended abstract).
A temporal access control mechanism for database systems.
A temporal authorization model.
Authorizations in relational database management systems.
Deriving Production Rules for Incremental View Maintenance.
The stable model semantics for logic programming.
Maintaining Views Incrementally.

An authentication service for open network systems.
Discretionary access control in object-oriented databases: Issues and research directions
The well-founded semantics for general logic programs
Authorizations in distributed systems: A new approach.
--TR

--CTR
Elisa Bertino , Silvana Castano , Elena Ferrari , Marco Mesiti, Specifying and enforcing access control policies for XML document  sources, World Wide Web, v.3 n.3, p.139-151, 2000
Elisa Bertino , Sushil Jajodia , Pierangela Samarati, A flexible authorization mechanism for relational data management systems, ACM Transactions on Information Systems (TOIS), v.17 n.2, p.101-140, April 1999
Sushil Jajodia , Pierangela Samarati , V. S. Subrahmanian , Eliza Bertino, A unified framework for enforcing multiple access control policies, ACM SIGMOD Record, v.26 n.2, p.474-485, June 1997
Elisa Bertino , Claudio Bettini , Elena Ferrari , Pierangela Samarati, Supporting Periodic Authorizations and Temporal Reasoning in Database Access Control, Proceedings of the 22th International Conference on Very Large Data Bases, p.472-483, September 03-06, 1996
Mizuho Iwaihara , Ryotaro Hayashi , Somchai Chatvichienchai , Chutiporn Anutariya , Vilas Wuwongse, Relevancy-based access control and its evaluation on versioned XML documents, ACM Transactions on Information and System Security (TISSEC), v.10 n.1, p.3-es, February 2007
Mizuho Iwaihara , Somchai Chatvichienchai , Chutiporn Anutariya , Vilas Wuwongse, Relevancy based access control of versioned XML documents, Proceedings of the tenth ACM symposium on Access control models and technologies, June 01-03, 2005, Stockholm, Sweden
H. F. Wedde , Mario Lischka, Role-based access control in ambient and remote space, Proceedings of the ninth ACM symposium on Access control models and technologies, June 02-04, 2004, Yorktown Heights, New York, USA
Michael J. Covington , Wende Long , Srividhya Srinivasan , Anind K. Dev , Mustaque Ahamad , Gregory D. Abowd, Securing context-aware applications using environment roles, Proceedings of the sixth ACM symposium on Access control models and technologies, p.10-20, May 2001, Chantilly, Virginia, United States
Elisa Bertino , Claudio Bettini , Elena Ferrari , Pierangela Samarati, An access control model supporting periodicity constraints and temporal reasoning, ACM Transactions on Database Systems (TODS), v.23 n.3, p.231-285, Sept. 1998
Elisa Bertino , Silvana Castano , Elena Ferrari , Marco Mesiti, Controlled access and dissemination of XML documents, Proceedings of the 2nd international workshop on Web information and data management, p.22-27, November 02-06, 1999, Kansas City, Missouri, United States
Avigdor Gal , Vijayalakshmi Atluri, An authorization model for temporal data, Proceedings of the 7th ACM conference on Computer and communications security, p.144-153, November 01-04, 2000, Athens, Greece
Franois Siewe , Antonio Cau , Hussein Zedan, A compositional framework for access control policies enforcement, Proceedings of the ACM workshop on Formal methods in security engineering, p.32-42, October 30, 2003, Washington, D.C.
Xinwen Zhang , Jaehong Park , Francesco Parisi-Presicce , Ravi Sandhu, A logical specification for usage control, Proceedings of the ninth ACM symposium on Access control models and technologies, June 02-04, 2004, Yorktown Heights, New York, USA
Xinwen Zhang , Francesco Parisi-Presicce , Ravi Sandhu , Jaehong Park, Formal model and policy specification of usage control, ACM Transactions on Information and System Security (TISSEC), v.8 n.4, p.351-387, November 2005
Shermann S. Chan , Qing Li , Jos A. Pino, VideoAcM: a transitive and temporal access control mechanism for collaborative video database production applications, Multimedia Tools and Applications, v.29 n.1, p.29-53, April     2006
Sushil Jajodia , Pierangela Samarati , Maria Luisa Sapino , V. S. Subrahmanian, Flexible support for multiple access control policies, ACM Transactions on Database Systems (TODS), v.26 n.2, p.214-260, June 2001
Nabil Adam , Yelena Yesha, Strategic directions in electronic commerce and digital libraries: towards a digital agora, ACM Computing Surveys (CSUR), v.28 n.4, p.818-835, Dec. 1996
N. R. Adam , V. Atluri , E. Bertino , E. Ferrari, A Content-Based Authorization Model for Digital Libraries, IEEE Transactions on Knowledge and Data Engineering, v.14 n.2, p.296-315, March 2002
Vijayalakshmi Atluri , Avigdor Gal, An authorization model for temporal and derived data: securing information portals, ACM Transactions on Information and System Security (TISSEC), v.5 n.1, p.62-94, February 2002
Jean Bacon , Ken Moody , Walt Yao, A model of OASIS role-based access control and its support for active security, ACM Transactions on Information and System Security (TISSEC), v.5 n.4, p.492-540, November 2002
Vijayalakshmi Atluri , Soon Ae Chun, An Authorization Model for Geospatial Data, IEEE Transactions on Dependable and Secure Computing, v.1 n.4, p.238-254, October 2004
access control;temporal reasoning;general logic programs;database security;database management;temporal authorization