Introduction

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 different users read and modify this data. There's been work on access control techniques for both read [1,[5][6][7][8]10] and write [2][3][4] queries over XML data.

For write queries, a special type of vulnerability has been studied: the possibility that a policy specification 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.

Example 1. The US National Library of Medicine developed Journal Publishing Tags to describe the content and metadata of journal articles. A fragment of its schema is shown in Fig. 1 1 and a sample document in Fig. 2. 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 first 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 D 2 (in Figure 5) from document D 0 (in Figure 2) since inserting journal-id elements is forbidden. However, this can be achieved by first removing from D 0 the sub-article element, which results in document D 1 in Figure 3, and then inserting the new sub-article element shown in Figure 4 below the front element of document D 1 . Thus, through two allowed updates such as deleting an inserting a sub-article element, it is possible obtain a document D 2 that is also the result of applying a forbidden update. In [2] the authors defined inconsistencies in XML access control policies for write operations, studied the problem of identifying such policies for structured DTDs, showed that finding repairs to those policies is np-complete and provided approximation algorithms to compute them. Later, in [4], authors extended those results to deal with a general kind of DTD called Chain Extended DTDs (CEDTDs for short), like the one in Fig. 1, imposing some restriction over the type of updates that were considered. For instance, it only considered updates that replaced element types belonging to a disjunction without +, * or ?. Thus, in the Journal Publishing example, the only valid replace updates would be between element types front and front-stub. In this setting, the problem of repairing inconsistent policies was shown to be np-complete.

2

In this article, we show how an access control policy can be defined 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 defined in [4]. However, the type of policies that cannot be expressed are not common in practice. This document is structured as follows. The definitions of XML documents, schemas and updates are provided in Section 2. Section 3 defines 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.

Preliminaries

An extended DTD (EDTD) is an abstraction of the two main schema definition languages for XML [9], namely DTDs and XSDs, and represented by a quintuple (Ele, Types, Rg, rt, µ) where i) Ele is a finite set of element names ii) Types is a finite set of element types iii) rt is a distinguished element name in Ele and in Types called the root iv) µ is a mapping from Types to Ele such that µ(rt) = rt, and v) Rg defines the element types: that is, Rg : Types → Reg Types , where Reg Types is a set of regular expressions r over Types, considering concatenation, disjunction, element repetition and optionality, empty and string elements. Given a type A we will refer to Rg(A) as its production rule. An element type B i that appears in the production rule of an element type A is called a subelement type of A. Given an EDTD D, we write A ≤ D B for the transitive, reflexive closure of the subelement relation.

A structured EDTD is an EDTD such that its regular expressions are defined using the grammar:

str | | B 1 , . . . , B n | B 1 + • • • + B n | B * ,

where ",", "+" and " * " stand for concatenation, disjunction and Kleene star respectively, for the EMPTY element content, str for text values and B ∈ Types.

A Chain EDTDs consists of an EDTD whose regular expressions are: (i) a sequence of terms (A

1 + • • • + A n ) q ,

where q is an optional qualifier of the form +, * , or ?; (ii) a string str; or (iii) empty [11]. Every structured EDTD is a Chain EDTD.

Example 2. The Journal Publishing Schema in Fig. 1 is a chain EDTD but it is not a structured EDTD. For example, element article contains either a front or front-stub element, optionally a body element and zero or more repetitions of sub-articles or response elements. 2

We will model an XML document as rooted unordered trees which conforms to a schema if it validates against its regular expressions. The XML document in Fig. 1 conforms to the chain EDTD in Fig. 2.

Example 3. Let t 0 be the XML document shown in Figure 6(b), also represented by the tree in Figure 6(c). Let D 0 be the chain EDTD rooted in A shown in Figure 6(a). Document t 0 conforms to schema D 0 . 2

A→(B+C) + ,D * ,(E+F+G) B → H,I C → str D → str E → str F → str G → str H → str I → (a) CEDTD D0 <A> <B> <H>Hello</H> <I></I> </B> <C>World</C> <E>!!</E> </A> (b) Document t0 A B H "Hello" I C "World" E "!!"

(c) Tree representation of t0 Fig. 6. CEDTD D0 with a document t0 that conforms to it

We consider the following updates:

op ::= delete(n) | insert(n, t) | replace(n, t) | 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.

Access Control Policies

We use the notion of update access type to specify the access authorizations. 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 U valid in t * U valid in t U valid in t + U valid in t U valid in t? insert(Bi) valid in (B1 + • • • + Bn) delete(Bi) valid in (B1 + • • • + Bn) U valid in fi U valid in f1, . . . , fn U valid in Rg(A) (A, U ) valid in D

The set of valid base UATs for a given EDTD D is denoted by valid We want to enforce restriction over the applications of insert, delete and replace update operations, but the policies, as we have defined so far, allow or forbid only insertions and deletions. Thus, we need to deduce from our policies update access types to control replacements. 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(B i , B j ) 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.

(D) = {uat | uat valid in D}. Example 4. (example 3 cont.) Given schema D 0 , valid(D 0 ) = {(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)}2

Since we can apply over a document only updates that result in a new document that conforms to the DTD, we need to define 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 (B 1 + • • • + B n ) impose restrictions over the type of elements that can be replaced.

Definition 4. An XOR factor in A is a factor of the form (B

1 + • • • + B n ) in the production rule of A. Let XOR(A) = {{B 1 , • • • , B n }|(B 1 + • • • + B n ) is

In the policies defined in [4] updates that replaced an independent element by another were not considered.

Intuitively, an UAT in P ↑ represents a set of atomic update operations. More specifically, 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 matches t uat) if one of the following inference rules applies:

η(n) = A t ∈ ID(B) insert(n, t ) matchest (A, insert(B)) η(n) = B η(parent t (n)) = A delete(n) matchest (A, delete(B)) η(n) = B t ∈ ID(B ) η(parent t (n)) = A replace(n, t ) matchest (A, replace(B, B )) η(n) = str η(parent t (n)) = A 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 [

Consistency of Policies

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: Definition 6. [2] Consider a policy P defined over schema D. An inconsistency in P for D consists of an allowed run t 0 op1 − − → t 1 . . . We say that nothing is forbidden below an element type A in a policy P defined over D if for every B i such that A ≤ D B i and every (B i , x) ∈ valid(D), (B i , x) ∈ P .

If A has any replace operations in valid(D), then we define the replace graph

G P A = (V A , E A ) where i) V A is the set of subelements of A and ii) (B i , B j ) ∈ E A if there exists (A, replace(B i , B j )) ∈ P ↑ .

Theorem 1. A policy P defined over a CEDTD D is consistent if and only if for every production rule:

1. If (A,insert(B))∈ P ↑ and (A,delete(B))∈ P ↑ , then nothing is forbidden below

B 2. If for every i ∈ [1, . . . n], if B i is contained in a cycle in G P A then nothing is forbidden below B i .

Proof Sketch: Policy P and schema D can be transformed into a new policy P struct defined over a new structured schema D struct in such a way that P is consistent over D if and only if P struct is consistent over D struct . In [2] the authors identify three cases in which a policy defined over a structured schema is consistent: insert/delete, negative-cycle and forbidden-transitivity. Because of the characteristics of P struct only the first two can occur. By reversing the transformations, we get the conditions for CEDTDs that correspond to insert/delete and negative cycle inconsistencies.

2

The conditions in Theorem 1 are defined over the expanded policy P ↑ . In order to simplify the consistency checking problem, it is better to see how these conditions can be checked in P instead of P ↑ . Proposition 1. A policy P defined 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 {(A, insert(B)), (A, delete(B))} ⊆ P then nothing is forbidden below B. 2. If B and C are alternates in A and {(A, insert(B)), (A, delete(B)), (A, insert(C)), (A, delete(C))} ⊆ 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 P D0 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).

Repairing Inconsistent Policies

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 find 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.

Definition 7. [2]

A policy P is a repair of a policy P defined over a DTD D if and only if: i) P is defined over D, ii) P is consistent, and iii) P ⊆ P . Furthermore a repair P of P is a minimum-repair if there is no repair P such that |P | < |P |. 22

In other words a repair is a new policy over the same schema, which is consistent and contains a subset of the allowed UAT in P . For this repair to be minimal, we require that it contains the maximum number of allowed UATs or, equivalently, that a minimal number of UATs has been removed from P .

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: 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) ∈ 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) ∈ P . Thus, when there are several inconsistencies of Type 2 it 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 = P \ {(A, insert(B)), (A, delete(F))}. Even though finding 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 × 2 n ).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(n 2 ). 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.

Conclusions

We have provided an access control policy definition language based in basic update access types, that simplifies the administration of authorization, since it only requires that the policy manager defines 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 efficient 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 defined in [4], since the repair computation problem for those is np-hard. This is achieved by instead of defining policies in terms of insert, delete and replace UATs, we here define policies using only insert and delete UATs and deducing from them the replace permissions. In terms of expressive power they are not comparable since we can define policies that they cannot and vice-versa. For example, consider a DTD with the production rule A → B * , C * and B and C containing text. A policy P = {insert(C), delete(B)} with P ↑ = {insert(C), delete(B), replace(B, C)} cannot be expressed in policies defined in [4] since they do not consider replace between elements that do not belong to an XOR factor. On the other hand, we cannot write a policy P for which P ↑ = {(A, replace(B, C)), (B, replaceVal), (C, replaceVal)} even though P ↑ is a consistent policy in [4]. We believe that the gain in expressive power outweighs the loss since being able to provide permissions for replacements outside of XOR factors is a useful feature and the policies that cannot be expressed do not seem useful in practice. Thus, the policies here introduced can be used as a simple, but powerful, way to provide consistent access control to XML databases.