When de ning Access Control Policies for XML Databases administrators need to make sure that they are not inconsistent, this is, that it is not possible to perform a forbidden operation through a sequence of allowed operations. This problem has been studied before for policies de ned using authorizations based in insert, delete, replace and replaceVal types to control updates in documents that conform to structured DTDs and chain DTDs. For those policies, consistency can be checked in polynomial time, but the problem of minimally restoring consistency is np-hard. In this article we show how the administration of authorization can be simpli ed by considering only insert and delete permissions, while still being able to control access of replace updates, in such a way that they can be checked for consistency and repaired if they are not in polynomial time. Also, this simpli ed policies allow to control a more general class of updates than the ones previously studied.
XML documents are increasingly being used not only to share data but also to store it in that format, i.e. XML Databases. For this reason, it has become important to provide ways to control the way in which di erent users read and modify this data. There's been work on access control techniques for both read [1, 5{8, 10] and write [2{4] queries over XML data.
For write queries, a special type of vulnerability has been studied: the possibility that a policy speci cation enables a user to simulate a forbidden update through a sequence of allowed updates in the same policy. These \inconsistent" policies open up security problems and as such, need to be properly detected and repaired before being enforced. 1 Each element is de ned using regular expressions. We assume that all the elements that are not de ned correspond to text(#PCDATA). Consider, for example, a policy that allows a user to insert and remove elements of type sub-article but does not allow him/her to insert new journal-id elements. This policy has an inconsistency, since it is possible to add a journal-id by rst removing the element sub-article, and then inserting a new one that includes the extra journal-id. For example, it shouldn't be possible to obtain document D2 (in Figure 5) from document D0 (in Figure 2) since inserting journal-id elements is forbidden. However, this can be achieved by rst removing from D0 the sub-article element, which results in document D1 in Figure 3, and then inserting the new sub-article element shown in Figure 4 below the front element of document D1. Thus, through two allowed updates such as deleting an inserting a sub-article element, it is possible obtain a document D2 that is also the result of applying a forbidden update. <article> <front> <journal-meta> <journal-id>BMJ</journal-id> <issn>0959-8138</issn> <publisher>BMJ</publisher> </journal-meta> <article-meta> <article-id>jBMJ</article-id> <article-id>1508</article-id> <author>Freeman,George</author> <pub-date>13-4-2002</pub-date> <volume>324</volume> <issue>7342</issue> </article-meta> </front> <sub-article> <front-stub> <journal-meta> <journal-id>SMN</journal-id> <journal-id>DKE</journal-id> <issn>7225-4139</issn> <publisher>SMN</publisher> </journal-meta> </front-stub> </sub-article>
In [
In this article, we show how an access control policy can be de ned for XML
databases that conform to CEDTDs in such a way that: (i) it deals with insert,
delete and replace updates between any two distinct element types, (ii) policy
consistency can be checked in polynomial time, (iii) repairs to inconsistent
policies can be found in polynomial time. The cost to achieve this is that it cannot
express some policies that can be de ned in [
This document is structured as follows. The de nitions of XML documents, schemas and updates are provided in Section 2. Section 3 de nes access control policies for CEDTDs. Next, in Section 4 the consistency of those policies in analyzed and for the cases in which they are inconsistent, the repair problem is studied in Section 5. Finally, the conclusions are provided in Section 6. 2
An extended DTD (EDTD) is an abstraction of the two main schema de nition
languages for XML [
A structured EDTD is an EDTD such that its regular expressions are de ned
using the grammar: str j j B1; : : : ; Bn j B1 + + Bn j B , where \;", \+"
and \ " stand for concatenation, disjunction and Kleene star respectively, for
the EMPTY element content, str for text values and B 2 Types.
A Chain EDTDs consists of an EDTD whose regular expressions are: (i) a
sequence of terms (A1 + + An)q, where q is an optional quali er of the form +; ,
or ?; (ii) a string str; or (iii) empty [
Example 3. Let t0 be the XML document shown in Figure 6(b), also represented by the tree in Figure 6(c). Let D0 be the chain EDTD rooted in A shown in Figure 6(a). Document t0 conforms to schema D0. 2 A!(B+C)+,D ,(E+F+G) B ! H,I F ! str C ! str G ! str D ! str H ! str E ! str I ! (a) CEDTD D0 <A> <B> <H>Hello</H> <I></I> </B> <C>World</C> <E>!!</E> </A> (b) Document t0
B H
I
A
C \World"
E \!!" \Hello" (c) Tree representation of t0 We consider the following updates: op ::= delete(n) j insert(n; t) j replace(n; t) j replaceVal(n; s). A delete(n) will remove node n and all its descendants. An insert(n; t) operation will add a tree t as a child node below n. A replace(n; t) operation will replace the subtree with root n by the tree t. A replaceVal(n; s) operation will replace the text value of node n with string s. An update operation is said to be valid for t and D if the result of applying it over t results in a document that conforms to D. For example, the update delete(E) would not be valid over t0, because the resulting document would not conform to D. In what follows we consider only valid updates. We denote by [[op]](t; D) the resulting XML document obtained by applying update operation op on tree t that conforms to schema D. 3
We use the notion of update access type to specify the access authorizations. De nition 1. Given a CEDTD D, a base update access type (base UAT) is an expression of the form (A; ut) where ut ::= insert(B) j delete(B) j replaceVal and A and B are types from D. 2 Intuitively, each of these UATs controls the operations that insert or delete an element of type B or operations that replace a string. The relation uat valid in D, which indicates that a base update access type uat is valid for the EDTD D, is constrained by the following inference rules:
replaceVal valid in str
U valid in t+
insert(Bi) valid in (B1 + + Bn)
U valid in f1; : : : ; fn delete(Bi) valid in (B1 +
+ Bn) The set of valid base UATs for a given EDTD D is denoted by valid(D) = fuat j uat valid in Dg.
Example 4. (example 3 cont.) Given schema D0, valid(D0) = f(A; insert(B)); (A; delete(B)); (A; insert(C)); (A; delete(C)); (A; insert(D)); (A; delete(D)); (A; insert(E)); (A; delete(E)); (A; insert(F)); (A; delete(F)); (A; insert(G)); (A; delete(G));(C; replaceVal); (D; replaceVal); (E; replaceVal); (F; replaceVal); (G; replaceVal); (H; replaceVal)g 2 De nition 2. A policy P de ned over an EDTD D, is represented by the set of allowed update access types de ned over D such that P valid(D). The set of forbidden UAT of a policy P de ned over D are F (P; D) = valid(D) r P . 2 Example 5. (example 4 cont.) A policy for D0 is PD0=f(A;insert(B));(A;delete(B)); (A; insert(C)); (A; delete(C)); (A; insert(E)); (A; delete(E));(A; insert(F));(A; delete(F)); (A; insert(G)); (A; delete(G)); (C; replaceVal); (E; replaceVal); (G; replaceVal)g: The set of UATs that are forbidden by PD0 are F (PD0 ; D0) = (A; delete(D)); (A; insert(D)); (D; replaceVal); (F; replaceVal); (H; replaceVal)g: 2 We want to enforce restriction over the applications of insert, delete and replace update operations, but the policies, as we have de ned so far, allow or forbid only insertions and deletions. Thus, we need to deduce from our policies update access types to control replacements.
De nition 3. Given a CEDTD D, an update access type (UAT) de ned over D is a base UAT or an expression of the form (A; replace(B; C)) and A, B, C are types from D. 2 In order to enforce a policy P on updates, an expanded version P " is inferred from P , adding certain replace operations that are allowed. For instance, replace(Bi; Bj ) is considered an inferred update access type, for which the permissions are obtained from the allowed and forbidden base UATs such as insert, delete and replaceVal. Since we can apply over a document only updates that result in a new document that conforms to the DTD, we need to de ne replace UATs only in the cases where the replace could take place.
Example 6. For the production rule A ! (B+C)+,D ,(E+F+G) of the ongoing
example, elements E, F and G can only be replaced between them, since a
replacement of an element E by an B, for example, would result in a document
that does not conform to the DTD. On the other hand, elements B, C and D can
only be replaced between them. 2
As the previous example shows, factor of the form (B1 +
strictions over the type of elements that can be replaced.
+ Bn) impose
reDe nition 4. An XOR factor in A is a factor of the form (B1 + + Bn) in the
production rule of A. Let XOR(A) = ffB1; ; Bngj(B1 + + Bn) is an XOR
factor in Ag. Types Bi and Bj are alternates in A if both Bi and Bj belong to
the same XOR factor in A. A types Bi is independent in A if it does not belong
to any XOR factor in A. 2
In the policies de ned in [
Example 7. The production rule A ! (B+C)+,D ,(E+F+G) has one XOR factor, namely (E+F+G). The alternates in A are fE,Fg, fE, Gg and fF, Gg. The independent types in A are B, C and D. 2 De nition 5. Given a set of UATs U , the expanded version U " is obtained from U using the following inference rules: (A; delete(Bi)) 2 U ; (A; insert(Bj )) 2 U ; i 6= j; and Bi; Bj are independent in A (A; replace(Bi; Bj )) 2 U " (A; delete(Bi)) 2 U ; (A; insert(Bj)) 2 U ; i 6= j; and Bi; Bj are alternates in A (A; replace(Bi; Bj )) 2 U " (A; insert(B)) 2 U ; and B is independent in A
(A; insert(B)) 2 U " (A; delete(B)) 2 U ; and B is independent in A (A; delete(B)) 2 U " (A; replaceVal) 2 U (A; replaceVal) 2 U " Given a schema D and a policy P , the set of extended valid UATs corresponds to valid(D)" and the expanded policy to P ". 2 This expanded policy can be used to check if an update is allowed or forbidden by a policy. Example 8. (example 4 cont.) The set of extended valid UATs valid(D)" = f(A;insert(B)); (A;insert(C)); (A;insert(D)); (A;delete(B)); (A;delete(C)); (A;delete(D)); (A; replace(E; F));(A;replace(E; G)); (A; replace(F; E)); (A;replace(F; G));(A;replace(G; E)); (A;replace(G; F));(A;replace(B;C));(A;replace(C;B));(A;replace(C;D));(A;replace(D;C)); (A; replace(B;D)); (A; replace(D; B)); (C; replaceVal); (D; replaceVal); (E; replaceVal); (F; replaceVal); (G; replaceVal); (H; replaceVal)g. It di ers from valid(D) since it adds all the replace UATs and removes some insert and delete. The set of extended valid UATs represent the types of updates that could result in a document that conforms to schema D0. The extended policy PD" 0 = f(A; insert(B)); (A; insert(C)); (A; delete(C)); (A; replace(C; B)); (A; delete(B)); (A; replace(B; C)); (A;replace(E;F)); (A;replace(F;E));(A;replace(G;E)); (A;replace(E;G)); (A;replace(F;G)); (A;replace(G;F));(C; replaceVal);(E;replaceVal); (G;replaceVal)g. The UATs that are forbidden by the policy correspond to valid(D)" r P " . 2
D Intuitively, an UAT in P " represents a set of atomic update operations. More speci cally, for t an instance of CEDTD D, op an atomic update and uat an update access type we say that op matches uat on t (op matchest uat) if one of the following inference rules applies: (n) = A t0 2 ID(B) (n) = B (parentt(n)) = A insert(n; t0) matchest (A; insert(B)) delete(n) matchest (A; delete(B)) (n) = B t0 2 ID(B0) (parentt(n)) = A (n) = str (parentt(n)) = A replace(n; t0) matchest (A; replace(B; B0)) replaceVal(n; s) matchest(A; replaceVal) Function corresponds to the unique mapping from each node in t to the element type associated to it. This uniqueness follows from the assumption that D is unambiguous.
As we said before, we will restrict only to valid update operation which given a document t and a CEDTD D the result of applying it over t results in a document that conforms with D. Since the problem of validity and authorization are orthogonal, we assume that all the operations to checked by the policy are valid.
The set of operations that are allowed by a policy P on an XML tree t in an CEDTD D, denoted by [[P ]](t; D), is the union of the atomic valid update operations matching each UAT in P ". More formally, [[P ]](t; D) = fop j op matchest uat and uat 2 P "g. Analogously, the forbidden operations are [[F ]](t; D) = fop j op matchest uat, and uat 2 (valid(D) n P ")g. A safe run t0 op!1 t1 : : : op!n tn is allowed w.r.t. P and D if for every i we have opi 2 [[P ]](ti 1; D). 4
A policy is said to be consistent if it is not possible to simulate a forbidden
update through a sequence of allowed updates. More formally:
De nition 6. [
Theorem 1. A policy P de ned over a CEDTD D is consistent if and only if for every production rule: 1. If (A;insert(B))2 P " and (A;delete(B))2 P ", then nothing is forbidden below B 2. If for every i 2 [1; : : : n], if Bi is contained in a cycle in GAP then nothing is forbidden below Bi.
Proof Sketch: Policy P and schema D can be transformed into a new policy
Pstruct de ned over a new structured schema Dstruct in such a way that P is
consistent over D if and only if Pstruct is consistent over Dstruct. In [
Proposition 1. A policy P de ned over a CEDTD D is consistent if and only if for every element types A; B and C in D: 1. If B is independent in A and f(A; insert(B)); (A; delete(B))g P then nothing is forbidden below B. 2. If B and C are alternates in A and f(A; insert(B)); (A; delete(B)); (A; insert(C)); (A; delete(C))g P then nothing is forbidden below B and C. 2 It is possible to check if conditions in Proposition 1 hold for a policy using standard polynomial-time graph algorithms over the DTD. Thus, the problem of deciding policy consistency with respect to CEDTDs is in ptime. Example 9. (example 8 cont) Policy PD0 has several inconsistencies. First, by having both (A; insert(B)) and (A; delete(B)) allowed for an independent element type B under A, but forbidding (H; replaceVal). Another one is given by having (A; insert(E)), (A; delete(E)), (A; insert(F)) and (A; delete(F)) as allowed operations under alternate types E and F, but forbidding (F; replaceVal). Finally, given by having (A; insert(F)), (A; delete(F)), (A; insert(G)) and (A; delete(G)) as allowed operations under alternate types F and G, but forbidding (F; replaceVal). 5
If a policy is inconsistent, we would like to suggest possible minimal ways of modifying it in order to restore consistency. In other words, we would like to nd repairs that are as close as possible to the inconsistent policy. We would like this repairs to be more restrictive than the original, this is, a repair should provide less access to the user.
De nition 7. [
The problem of computing a minimum-repair can be solved in ptime. In what follows we describe an algorithm to do so. By Proposition 1 we have that we need to solve two types of inconsistencies:
Type 1: if B is independent in A, f(A; insert(B)); (A; delete(B))g P and something is forbidden below B.
Type 2: if B and C are alternates in A,f(A;insert(B));(A;delete(B));(A;insert(C)); (A; delete(C))g P and something is forbidden below B or below C. Because of minimality of repairs, repairs of inconsistencies of Type 1 can be solved independently by removing either (A; insert(B)) or (A; delete(B)). This is not the case for inconsistencies of Type 2, since there might be more than one such inconsistency involving shared types.
Example 10. (example 9 continued) There is an inconsistency of Type 2 between E and F since (F; replaceVal) 62 P . To solve this inconsistency, we need to forbid either (A; insert(E)),(A; delete(E)),(A; insert(F)) or (A; delete(F)). However, choosing to forbid (A; insert(E)) or (A; delete(E)) will not result in a minimal repair since element F is involved in another inconsistency of Type 2 with G since (F; replaceVal) 62 P . Thus, when there are several inconsistencies of Type 2 it 2 jP 0j denotes the cardinality of set P 0 Algorithm 1: PolicyRepair
Input : CEDTD D = (Ele; Types; Rg; rt; ), Policy P
Output : set toRemove of UATs to remove to restore consistency of P 1 (T1; T2) DetectInconsistencies(D; P ) 2 toRemove ; 3 for A 2 Types do 4 for B 2 T1(A) do 5 U either (A; insert(B)) or (A; delete(B)) (choose randomly) 6 toRemove toRemove [ fU g else
Let E be a randomly chosen element in S
S S r fEg for C 2 S do
U either (A; insert(B)) or (A; delete(B)) (choose randomly) toRemove toRemove [ fU g
S S r fCg is necessary to choose carefully to ensure that a minimal repair is found. In this case, either (A; insert(F)) or (A; delete(F)) need to be forbidden. The policy also has a inconsistency of Type 1 that can be solved by forbidding either (A; insert(B)) or (A; delete(B)) from our policy. Thus, a minimum-repair for P is P 0 = P n f(A; insert(B)); (A; delete(F))g. 2 Algorithm PolicyRepair, takes a policy P de ned over a CEDTD D and returns a set of UATs to remove from P to restore consistency. The algorithm rst calls Algorithm DetectInconsistencies that computes with the recursive Algorithm NodeInconsistency the inconsistencies of Type 1 and Type 2 and stores them in two functions T1 and T2 using depth- rst search over schema D. Function T1 : Types ! 2Types , returns for every type A the set of Types B such that f(A; insert(B)); (A; delete(B))g P and something is forbidden below B. These inconsistencies are solved by either deleting (A; insert(B)) or (A; delete(B)) (lines 46 of Algorithm PolicyRepair). Function T2 : Types ! 22Types , returns for every type A, a set of subsets of Types in such a way that if S 2 T2(A), then every B 2 S belongs to the same XOR factor below A and f(A; insert(B)); (A; delete(B))g P and something is forbidden below B. Also, if r 2 S it means there is a type C in the same XOR factor such that f(A; insert(C)); (A; delete(C))g P but everything is allowed below C. It is easy to check that in order to solve the inconsistencies of Type 2, for every S 2 T2(A) we need to delete either (A; insert(B)) or (A; delete(B)) Algorithm 2: DetectInconsistencies
Input : CEDTD D = (Ele; Types; Rg; rt; ), Policy P Output : A tuple (T1; T2) where T1 and T2 are functions that given a type they return the inconsistencies of Type 1 and Type 2 below it 1 for A 2 Types do 2 visited(A) 1 3 if there exists (A; op) 2 F(P; D) then 4 (A) = 0 else (A)
1 T1(A)
T2(A) 7 ; 8 ; 9 NodeInconsistency(D; rt; visited; ; T1; T2) 10 return (T1; T2) for every B 2 S except for r if it belongs to F or any type if it does not (see lines 7-15 of Algorithm PolicyRepair). Algorithm 3: NodeInconsistency
Input : CEDTD D, Node A, functions:visited, , T1 and T2
Result: T1(A) and T2(A) contain inconsistencies of Type 1 and Type 2 below A 1 if visited(A) < 0 then 2 for B independent in A do 3 nodeInconsistency(M GD; visited; B) 4 if (B) = 0 then 5 (A) 0 6 if (A; insert(B)) 2 P and (A; delete(B)) 2 P then 7 T1(A) = T1(A) [ fBg 8 9 10 11 12 13 else
S = S [ frg if jSj > 1 then
T2(A) T2(A) [ fSg if (A) = 1 then
(A) 1 visited(A)
1 Example 11. (example 5 continued) Algorithm DetectInconsistencies returns T1 and T2 such that:
T1(E) = fBg for E=A ; for E6=A
T2(E) = ffF; rgg for E=A ; for E6=A To solve the only inconsistency of Type 1, it chooses from either (A; insert(B)) or (A; delete(B)) and adds it to the toRemove set. Next, for sets in T2(A), it loads them into a variable S and checks if r 2 S. If such element is in the set, it means that there are cycles inside the XOR factor involving elements that do not have something forbidden below them. In this case, the algorithm erases r from S. Then the algorithm proposes to add either (A; insert(F)) or (A; delete(F)) to the toRemove set. So, by choosing one UAT from each combination shown, and changing them from allowed to forbidden, consistency is restored. 2 Even though nding a single minimum-repair can be done in polynomial time, there might an exponential number of them.
Proposition 2. Given a policy P over a CEDTD D, a minimum-repair of it can be computed with Algorithm 1 in O(n + m) where n is the number of types in D and m is the number edges in the tree that represents D. All the repairs can be computed in O(n 2n). 2 In most of the cases m is O(n) and thus a minimum repair can be found in linear time on the number of types in the DTD. In the worst case m is O(n2). Even thought computing all the repairs requires exponential time, it is also possible to show in linear time all the inconsistencies to the designer of the policy so that he can choose how to solve each of them. 6
We have provided an access control policy de nition language based in basic update access types, that simpli es the administration of authorization, since it only requires that the policy manager de nes whether the user should be able to insert or delete elements of the DTD, and automatically deduct replace authorizations from such permissions. For these type of policies, consistency checking and repair computation problems can be solved in polynomial time. We also provided e cient algorithms that, given an inconsistent policy, computes a consistent one that is as close as possible to the inconsistent one in terms of forbidden UATs.
These policies are an improvement over the ones de ned in [