Balisage Paper: Secure Publishing using Schema-level Role-based Access Control Policies for Fragments of XML Documents

Documents and Document Paths

In our approach, document fragments, or views, are described using document paths based on XPath [XPath2008]. For a document D, by P_D we denote the set of paths in D. We allow disjunctions of document paths, using the | operator. To simplify the process of defining grammar path, we borrow the following two Unix/C conventions:

For example

	#define HP	/H/P
	$HP/{a, b, c/{d,e}}

stands for

      /H/P/a | /H/P/b | /H/P/c/d | /H/P/c/e

Example 3.1.

Consider a hospital, where there are three types of tests: basic, confidential and very confidential; and each patient has three attributes: name, Id, and perm (the last attribute determines whether or not patients with negative Ids will have access to very confidential tests). The path P:

	#define hp	/hospital/patient
	P: $hp{/@Id, /basic/text(), /basic, [@Id<"0" AND @perm="true"]/veryConfidential/text()}

is a document path for the following document D:

<?xml version="1.0" encoding="UTF-4"?>
<hospital>
	<patient  name="Kay" Id="-1" perm="true" >
		<basic>B1</basic>
		<confidential>C1</confidential>
		<veryConfidential>V1</veryConfidential>
	</patient>
	<patient  name="Smith" Id="-2" perm="false" >
		<basic>B2</basic>
		<confidential>C2</confidential>
		<veryConfidential>V2</veryConfidential>
	</patient>
	<patient  name="Zen" Id="200" perm="true" >
		<basic>B3</basic>
		<confidential>C3</confidential>
		<veryConfidential>V3</veryConfidential>
	</patient>
</hospital>

The above path P defines a view of D consisting of values of Id for all patients (both attribute and its value), the tagname <basic> and its text values, B1, B2 and B3; and the value of V1. □

Document-level Access Control Policies, DRBAC

In this section we define document-level RBAC, DRBAC and the related protection requirement. Here, we use a subset of XPath; a path expression p consists of one or more location steps; each location step operates on the child axis. A path is then of the form p | not p | p1 intersect p2 | p1 union p2 , and its evaluation produces an ordered sequence of nodes. A valid path is any path which does not evaluate to an empty sequence.

Definition 3.1.

For an XML document D and a finite set Ψ of roles, the document-level RBAC (DRBAC) is a mapping π_D:Ψ→P_D such that π_D(Ψ) covers the set D; i.e., each element of D belongs to at least one document path that occurs in the policy. Often, the mapping π_D is tabulated and shown as a tuple [(R₁, P₁),(R₂, P₂),...,(R_n, P_n)] □

There are various views of the document D, and each view is defined by π_D(R). The designer of the policy for an XML document D may decide to leave some parts of D unencrypted (accessible to all users) or to make them inaccessible to all users (i.e., to encrypt them, but not to provide the key used for encryption of these nodes to any user). For the former case, the symbol ♥ is used, while for the latter case we use the symbol •. Therefore, the actual definition of the document-level RBAC is that it is pair (π_D, ♦), where ♦ is either ♥ or •. For simplicity (unless specified otherwise), in the sequel, we omit the second element of this pair, and assume that by default it is always • (i.e. by default, elements of D not covered by D are inaccessible to all users).

Definition 3.2.

The document-level protection requirement is said to be satisfied under the following conditions. For an XML document D, a finite set of roles Ψ, and the document-level RBAC π_D:Ψ→P_D a user in role R can access precisely the set π_D(R), and if the policy uses ♥ also those nodes in D which are not covered by any path. □

Example 3.2.

Consider the document D from [Example 3.1], and a set of roles Ψ = {Nurse, Physician, Resident, Smith}. We define four document paths:

	#define hp	/hospital/patient
	#define Sname  	$hp[@name="Smith"]
	ND: $hp{/@Id, [@Id<0]/basic/text()}
	PD: $hp/{@Id, @name, basic/text(), confidential/text(), veryConfidential/text()}
	RD: $hp{/@Id, [@Id>"100" AND @perm= "true"]/veryConfidential/text()}
	SD: $Sname/{@perm, basic/text(), confidential/text(), veryConfidential/text() }

We now define π_D as: [(Nurse, ND), (Physician, PD), (Resident, RD), (Smith, SD)], which gives:

• the user in role Nurse access to Ids of all patients, and to the textual content of the basic test for patients whose Id is negative;

• the user in role Physician access to Ids and names of all patients, and to the textual content of the basic, confidential and very confidential tests;

• the user in role Resident access to Ids of all patients, and to the textual content of the very confidential test for patients whose Id is greater than 100 and perm is set to true;

• the user in role Smith access to permissions, and the textual content of the basic, confidential and very confidential test for these patients whose name is Smith

Since by default we use the role •, other elements of D are available to nobody. In Figure 1, B1, C1, etc. stand for the text contents of the basic tag, confidential tag, etc.; elements accessible to the user in various roles are labeled with dotted boxes containing first letters of the names of these roles; nodes which are not available to any user are not labeled.

Figure 1

Labeled document tree for the hospital

Let us now use [Example 3.2] to compare super-encryption and multi-encryption. In the former case, nodes which are on the intersection of document paths would have to be encrypted and then decrypted with several keys. In the latter case, each node will be encrypted and decrypted with a single key. (In Section 6, we provide results of experiments comparing these two techniques.)

Schemas and Grammar Paths

In this paper, we consider schema-oriented XML documents which have to follow the grammar rules specified by an associated schema, rather than schema-less documents which merely have to be well-formed according to the XML language specification [XML2008]. A commonly used grammar description is XML Schema [XML-Schema2008], which we also use in this paper. Throughout this paper, by L_Σ we denote the language generated by the schema Σ. Specifically, if Σ is the schema of schemas, i.e. the grammar defining schemas, then L_Σ is the language of all schemas, and for S∈L_Σ, a document D is valid for S iff D∈L_S. We consider only schemas for which there are no anonymous types (we can do it without a loss of generality because a schema with anonymous types can always have these types replaced by named types.) In the current implementation, we consider only schema with no cycles. By the top-level typename of the schema S, we mean the typename of the root element of any document valid in S. With each schema, we will associate a schema graph. The following examples show two schema and the corresponding graphs.

Example 3.3.

Consider a reference letter, which provides a specification as to whether or not the letter is confidential, names of a referee and an applicant, and zero, one or more reviews, where each review provides the name of a supervisor, a numeric score, and a comment. The schema T for such a reference letter is given below.

<?xml version="1.0" encoding="UTF-8"?>
<xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema">
	<xs:element name="letter" type="LetterType"/>
	<xs:complexType name="LetterType">
		<xs:sequence>
			<xs:element name="referee" type="NameType"/>
			<xs:element name="applicant" type="NameType"/>
			<xs:element name="review" type="ReviewType"/>
		</xs:sequence>
		<xs:attribute name="confidential" type="xs:boolean"/>
	</xs:complexType>
	<xs:complexType name="ReviewType" maxOccurs="unbounded">
		<xs:sequence>
			<xs:element name="supervisorName" type="NameType"/>
		</xs:sequence>
		<xs:attribute name="score" type="xs:integer"/>
		<xs:attribute name="comments" type="xs:string"/>
	</xs:complexType>
	<xs:complexType name="NameType">
		<xs:sequence>
			<xs:element name="first" type="xs:string"/>
			<xs:element name="last" type="xs:string"/>
		</xs:sequence>
	</xs:complexType>
</xs:schema>

Schema graph for the Schema T (see Figure 2) replicates nodes that represent elements of the same type. This graph shows types used in the schema. The alternative representation, used by this paper, (see Figure 3) will focus on element names from the schema, and will optionally show types of these elements (shown in dotted boxes with gray background).

Figure 2

Schema graph for schema T (based on types)

Figure 3

Schema graph for schema T (based on element names)

Example 3.4.

The schema S (see the schema graph in Figure 4) is a schema for which the document D from [Example 3.1] valid.

<?xml version="1.0" encoding="UTF-8"?>
<xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema">
	<xs:element name="hospital" type="HospitalType"/>
	<xs:complexType name="HospitalType">
		<xs:sequence>
			<xs:element name="patient" type="PatientType" maxOccurs="unbounded"/>
		</xs:sequence>
	</xs:complexType>
	<xs:complexType name="PatientType">
		<xs:sequence>
			<xs:element name="basic" type="xs:string"/>
			<xs:element name="confidential" type="xs:string"/>
			<xs:element name="veryConfidential" type="xs:string"/>
		</xs:sequence>
		<xs:attribute name="name" type="xs:string"/>
		<xs:attribute name="Id" type="xs:int"/>
		<xs:attribute name="perm" type="xs:boolean"/>
	</xs:complexType>
</xs:schema>

Figure 4

Schema graph for schema S

In Section 3.1, we defined views of XML documents using document paths. To define views of a schema S, we introduce grammar paths. For a document D valid in S, a grammar path may be materialized to produce the document path for D. This way, views of a schema determine views of documents valid in the schema. Here, we consider only absolute paths, but relative paths can be defined in the same way. We denote by Π_S the set of all grammar paths for the schema S. A triple (schema S, grammar path G, document D valid in S) defines a document path denoted by Π_S,D(G); we refer to this process as a grammar path materialization.

We start by defining an atomic grammar path, which is of the form /c₁/c₂/.../c_n. Each c_i is a tag name optionally followed by a predicate in square brackets. (If the predicate is present, then c_i is called the current context node.) A predicate is formed using standard Boolean operators: &&, ||, and ! (using standard associativity and precedence rules) and atomic predicates. There are three kinds of atomic predicates:

Note that if content of the element is mixed, i.e. contains both textual content and sub-elements then text() denotes the concatenation of all textual contents of this element.

In order to support nested conditions, atomic predicates may also be preceded by one of the following unconditional paths, where the i-th component b_i is a tag name:

Two examples of atomic grammar paths are:

	/H[@x > "1" || @x < "0" &&  @y = "0"]/P[text() = "John"]
	/H/B[../C/@z > "2" || /H/D/text() = "Mary"]/E

Atomic paths may have conditions involving nested paths, but they specify only a single node. Often it is convenient to specify subtrees, or parts thereof. Therefore, we define a simple grammar path, which is an atomic grammar path followed by a subtree operator of the form:

      <text = O3; att = O3; tag = O3>

where

The meaning of subtree operators is explained in [Example 3.5]. Finally, a grammar path is an atomic grammar path, or a simple grammar path, or one or more alternatives of such paths.

For a given schema, a grammar path is valid if it satisfies constraints imposed by the Schema, for example that an element name exists (in the given context), or the attribute value is a correct data type.

Example 3.5.

Below, we use the following terminology:

In all examples given below c is the last component of a simple grammar path:

  All text descendants of c:					c<text=*>
  All proper text descendants of c:				c<text=+>
  Text child of c (concatenated for mixed content):		c<text=.>
  All text descendants of c that are equal to "the":		c<text="the"*>
  All proper text descendants of c that are equal to "the":	c<text="the"+>
  Concatenated text children of c that is equal to "the":	c<text="the">
  All attribute descendants of c:				c<att=*>
  All proper attribute descendants of c:			c<att=+>
  All attribute children (attributes) of c:			c<at =.>
  A specific attribute foo of c:				c<att="foo">
  All "foo" attribute descendants of c:				c<att="foo"*>
  All proper "foo" attribute descendants of c:			c<att="foo"+>
  The tag of c:							c<tag="."> or c
  All element descendants of c:					c<tag=*>
  All proper element descendants of c:				c<tag=+>
  All element children (sub-elements) of c:			c<tag=.>
  A specific tag foo of c:					c<tag = "foo">
  All element descendants called "foo" of c:			c<tag="foo"*>
  All proper element descendants called "foo" of c:		c<tag="foo"+>
  All descendants of c:						c<*>
  All proper descendants f c					c<+>
  All children of c						c<.>
Finally, some examples of combined fields:
  All proper text descendants of c and all attributes of c:	c<text=*; att =*>
  Attributes foo and goo of c and the tag of c:			c<att = "foo", "goo"; tag =.>
  All element descendants "foo" and "goo" of c, all "hoo" attribute decendants, and the text of c:
   c<tag="foo"*, "goo"*; att="hoo"*; text=.> □

Example 3.6.

Below, we provide three grammar paths R, C, and N for the schema T from [Example 3.3]:

	R: /letter[review/score/text() > "7"]/referee/last<text=.>
	C: /letter[!(/referee/last/text() = "Smith" ||
           /referee/last/text() = "Kerry")]<att="comments", "score">
	N: /letter[@confidential = "false"]/{referee, applicant, review/supervisor}<text=+> |
          /letter[@confidential = "true" && review/score/text() > "5"
             || applicant/last/text() = "Brown"]/review/supervisor<text=+>

	#define HP	/hospital/patient
	#define HPN	$HP<att="Id">
	#define SS  	$HP[@name="Smith"]
	N: $HPN | $HP/[@Id<"0"]/basic<text=.>
	P: /hospital/patient<att="Id","name"; text=*>
	R: $HPN | $HP{/confidential<text=.>, [@Id>"100" &&
		@perm="true"]/veryConfidential<text=.> }
	S: $SS/{@perm, basic<text=.>, confidential<text=.>, veryConfidential<text=.>}

Introduction

Basic Notations

Let us first consider various ways keys may be assigned to documents. Since views may be overlapping, we can not assign keys per view. Indeed, if we did so, then for two overlapping views V₁ and V₂ we would have two corresponding keys k₁ and k₂, and the intersection of the two views would have to be super-encrypted (assigning keys per view would mean that for i=1,2, the user who has access to the view V_i would be given a key k_i and so other options such as encrypting V₁ with one key and V₂-V₁ with the other key would provide access to the part that is not allowed). What we need to do is to partition the set D (and at the same time each view) into disjoint sets, and then assign one key for each set in this partition. Therefore, for an arbitrary partition {P₁, P₂,...,P_n} of a set D, we need to find a disjoint partition. One way to achieve this goal is to create all possible differences of intersections of sets in the partition and remaining unions. Note that in our paper by a partition we mean a family of subsets of a set D that does not necessarily cover D.

Here, we work at the schema level, rather than at the document level, but we need to generate keys in such a way that materialized grammar paths are disjoint. Since set operations for grammar paths (such as a union) are not defined, we now introduce symbolic grammar paths that allow such operations:

Definition 4.2.

Consider a set {P_i: i=1,2,...,k} of grammar paths. By a symbolic grammar path expression we denote a finite set of string of the form:

eq42

Since document paths support the above mentioned set operations, symbolic grammar paths can be materialized.

Definition 4.3.

eq43

□

Example 4.1.

Consider first two grammar paths from [Example 3.8], and recalled below:

	#define HP	/hospital/patient
	#define HPN	$HP<att="Id">
	N: $HPN | $HP/[@Id<"0"]/basic<text=.>
	P: /hospital/patient<att="Id","name"; text=*>

Here, we have three symbolic grammar paths: N-P, P-N and N*P. To show materializations of the paths, consider the document D valid in S (see Figure 1. For this document, we have:

eq44

Note that the above materializations cover the same subset of D as materializations of original grammar paths, but unlike the original grammar paths, they are disjoint. □

Key Generation

To generate keys for the schema S one can use the following technique. For every symbolic grammar path, generate a key for that path, and then use these keys to multi-encrypt materializations of document valid in S. However, by following this approach, we would not avoid generating keys for symbolic grammar paths that will always be materialized to empty document paths. Therefore, we use a different approach, described below.

A target of a grammar path G is a single node in SG, or a node and a subgraph rooted at the node. An abstract value of G is a list of targets with the associated information about values of conditions that appear in G. Our algorithm finds abstract values of symbolic grammar paths corresponding to grammar paths in the SRBAC policy. We then use these values to avoid generating keys for these symbolic grammar paths whose abstract values are empty. Note that our algorithm additionally avoids creating redundant keys for two or more grammar paths whose abstract values are subsets; for example if the abstract value of G₁ is a subset of the abstract value of G₂ then the symbolic grammar path G₁ - G₂ evaluates to empty. Since at the schema level we do not know values of conditions that appear in grammar paths, we proceed as follows. By a configuration we refer to a bit-vector that represents true/false values of all conditions that appear in symbolic grammar paths (i.e., if the i-th condition evaluates to true, the i-th bit is set to 1, and 0 otherwise). We annotate every node of the schema graph with the list of pairs of the form (configurations, key).

Configurations

A configuration is a binary value of size k that represents true/false values of conditions. For a given grammar path X and a configuration C, values of all conditions in X are known, and therefore we can find an abstract value of X, which consists of one or more targets for the configuration C. A configuration index value is the integer decimal value corresponding to the binary value of this configuration. When it does not lead to confusion, we identify a configuration and its index value. Some configurations should be excluded e.g. if they specify true values for two conditions (involving the same attribute) that cannot be true at the same time (and arbitrary values for other conditions).

Algorithm 4.1

A condition (with k variables) is a Boolean Expression B(x₁,x₂,...,x_k) built from comparisons of the form:

x_i RelationalOperator c; where x_i and a constant c are of the same data type that supports linear order (such as real or integer) and three standard Boolean operators: and, or and not, with the standard associativity and precedence rules, and brackets, and a RelationalOperator is one of: >, <, <=, >=, =, !=. For example, the expression B(x,y): x>"0" && y>"100" || x>="4" && !(x="99") is a condition.

For given conditions B₁,...,B_k with k variables x₁,x₂,...,x_k, Algorithm 4.1 tests if for any subset (i₁,...,i_m) with 0<=m<=k of the set (1,...,n) the expression of the form D(x₁,x₂,...,x_k) = B_i1&&B_i2&&...&&B_im&&!B_j1&&!B_j2&&...&&!B_jr where {j₁,j₂,...,j_r} = {1,2,...,k} - {i₁,i₂,...,i_m}, is a falsehood; i.e. is false for all variables x₁,x₂,...,x_k.

Finding abstract values

An abstract value of a grammar path G is defined to be a list consisting of the pairs (target, list of configuration ids). If this list contains all non-excluded configurations, then it is omitted.

Algorithm 4.2.

Input: A schema S, and an SRBAC policy π_S:Ψ→Π_S, where Π_S ={G _i: i=1,2,...,n} is a set of grammar paths, and role R_i is associated with the path G_i.

Output: A table called Results storing abstract values of symbolic grammar paths.

Outline of the algorithm. While here we say a "table", the actual implementation may use a different, more efficient data structure. However, in our explanation of the algorithm, we will assume that the table is used. There are two steps of the algorithm:

In more details, the table Products[i] stores an abstract value of products G_i1*...*G_ij where 1<=i₁<=...<=i_j<=n and 1<=j<=k. Here, the index i is a decimal value of the binary word of size k in which bits at positions i_m are set to 1 and remaining bits are set to 0. For example, for k=4, Products[5] stores an abstract value represented by 0101, i.e. of the product G₂*G₄ and Result[5] will store the value of G₂*G₄ − (G₁+G₃).

Execution of step 2 involves:

Example 4.2.

In our running example, we have four conditions:

C1: (@Id<"0"), C2: (@Id>"100"), C3: (@perm="true") and C4: (@name="Smith")

and there are 16 configurations; starting with configuration 0, for which all conditions are false, and ending with configuration 15, for which all conditions are true. Now, consider configuration (1100) with the index value equal to 12. However, C1 and C2 cannot be true at the same time, and so any configuration of the form 11xx is excluded. Therefore, the list of non-excluded configurations consists of integers from 0 to 11, and an abstract value of the grammar path N is (Id, basic/text(), (9,10,11)).

Abstract values of all symbolic grammar paths are shown below (starting with abstract values of four paths), using the following abbreviations:

	{N} = <Id, (B,8,9,10,11)>
	{P} = <name,Id,B,C,V>
	{R} = <Id, C, (V,6,7)>
	{S} = <(B,I), (V,I), (C,I), (Perm,I)>

	Results[1] = S-(P+R+N) = (perm,I)
	Results[2] = R-(N+P+S) = 0
	Results[3] = R*S-(P+N) = 0
	Results[4] = P-(N+R+S) = <name,(B,0,2,4,6),(V,0,2,4,8,10)>
	Results[5] = P*S-(N+R) = <(B,1,3,5,7),(V,I)>
	Results[6] = P*R-(N+S) = <(C,0,2,4,6,8,10),(V,6)>
	Results[7] = P*R*S-N = <(C,I), (V,7)>
	Results[8] = N-(P+R+S) = 0
	Results[9] = N*S-(P+R) = 0
	Results[10] = N*R-(P+S) = 0
	Results[11] = N*P*R-S = 0
	Results[12] = N*P-(R+S) = <B,8,10>
	Results[13] = N*P*S-R = <B,9,11>
	Results[14] = N*P*R-S= <Id>
	Results[15] = N*P*R*S = 0

Schema-based Keyrings and Role-accessible Keyrings

For a schema S and a schema-level access control policy π_S:Ψ→Π_S, we use Algorithm 4.1, and for each non-empty value from the table Results, we generate one key. The keyring K_S consists of all keys generated this way. Note that in our running example, out of 16 symbolic grammar paths, only 8 are non-empty. Therefore, where a brute-force approach would generate 16 keys for four roles for our running example, our optimized algorithm will instead generate only 8 keys. Now, we show how for each role R∈Ψ the keyring K_S defines the set K_S(R) of R-accessible keys. A user in role R will be provided with the R-accessible keys so that for any document D valid for S, she can decrypt the view π_S,D(R), where π_S,D is the schema-induced document policy.

Algorithm 4.3.

Input: A schema S, a schema-level access control policy π_S:Ψ→Π_S and a role R∈Ψ.

Output: Role R-accessible keyring K_S(R).

Method: K_S(R) = {k∈K_S for some symbolic grammar path G, the abstract value of {G} is a subset of the abstract value of the grammar path π_S(R)} □

Example 4.3.

For our running example, let us denote by ri a key corresponding to the value of Results[i] which is not empty. Therefore, K_S= {r1, r4, r5, r6, r7, r12, r13, r14}. Two examples of role-accessible keyrings are K_S(Nurse) ={r12, r13, r14}, and K_S(Physician) ={r4, r5, r6, r7, r12, r13, r14}.□

One can show that given a schema-level access control policy π_S:Ψ→Π_S and XML document D valid in S, if the user U in role R is provided only with R-accessible keys created by Algorithm 4.3 then the protection requirement is satisfied; in particular U can access precisely the view V = π_S,D(R). □

Schema Graph Annotations

Based on the information stored in the table Results, we now annotate the syntax graph with a list of pairs (key, list of integers representing configuration index values). We use ♦ to denote a key for the default role; one of • or ♥. If the list consists of all permissible index values, then it is omitted. The annotated schema graph will be used to guide the process of multi-encrypting an XML document D during its SAX-based parsing. To annotate the schema graph, we traverse the table Results, and collect information about all keys. Next, we traverse the schema graph again, and if the annotation is missing at any node we add the annotation of the form (♦). For nodes that have already been annotated, we check if these annotations contain all permissible index values, if any such values are missing they are added with the default key ♦.

Example 4.4.

Consider our running example. To annotate the node "veryConfidential" in the schema graph, we look in Results[] for the value V, and so its annotation is <(r4,0,2,4,8,10), (r5,I), (r6,6), (r7,7)>. For the complete annotated schema graph see Figure 8.

Figure 8

Annotated syntax graph for schema S

Multi-encryption of Documents

The encryption of the document D valid in the Schema S results in single well-defined XML m-document MD, which always has a root element <encrypteddocument>. Each part of the document D that is encrypted with a key "k" will be represented as a child of the <encrypteddocument> node using this format: <edata key = "k"> encrypted_data </edata>. Note that the structure of the document D is hidden inside of the encrypted_data part and is therefore not visible to users who are not authorized to decrypt the document (the <edata> tags are not nested inside of other <edata> tags). The encryption is performed by efficient, single-pass SAX parsing of D (performed in parallel with the traversal of the previously annotated schema graph GS). For each node d of D, the corresponding node s in GS is located, and its annotation is examined to determine which key should be used to encrypt this node (note that at that time we can determine values of all conditions and so we know which configuration should be used; unless nested conditions are used, which require additional treatment). Recall that the same key always encrypts the attribute and its value.

Example 4.5.

Consider the document D from [Example 3.1], (see Figure 9), in which dotted boxes attached to elements and attributes show the key that is used to encrypt this element. To explain the choice of keys, note that there are three patients; when the attributes of the first patient are processed, we know that that the name is not "Smith", Id is negative, and perm is true, and so the configuration 10 is used. Similarly, configuration 9 is used for the second patient, and configuration 6 for the third one. This information is used to retrieve the key to be used for encryption from the annotated schema graph.

Figure 9

Document D and keys used to encrypt this document.

The m-document M_D looks like this (assuming that by default ♦ indicates that the node is not available to any user, so the corresponding <edata> nodes are omitted; below, we show details of the leftmost "patient" subtree and leave out other subtrees; encrypted data are also omitted):

<encrypteddocument>
	<edata key="r4">...</edata>
	<edata key="r14">...</edata>
	<edata key="r6">...</edata>
	<edata key="r2">...</edata>
	<edata key="r4">...</edata>
</encrypteddocument>

Decryption of Multi-Encrypted Documents

When the user U can prove that is entitled to play role R, she will first obtain the R-accessible keyring K_S(R) via a secure channel, and then proceed to decrypt an m-document M_D, to produce a document M_D,R. The software system available for U will first identify a sub-keyring K1 of K_S(R) consisting of keys needed to decrypt M, and then apply keys available in K1 to perform decryption. The output from the decryption is a single XML document. Given this document, U may use the system to create a sanitized schema (showing only accessible parts of schemas), which would allow them to efficiently apply XML tools, such as XQuery for XML databases. One can show that given a schema-level access control policy and XML document D valid in S, if the user U in role R is provided only with R-accessible keys K_S(R), then the protection requirement is satisfied. □

Example 4.6.

Consider the m-document from [Example 4.5], using the schema-based ACP policy from [Example 3.8]. Recall from [Example 4.3] that K_S(Physician) ={r4, r5, r6, r7, r12, r13, r14}. Assuming that the user plays the role Physician, the decrypted file will look as follows (note that in this example, tags are encrypted and so their respective values have been concatenated):

	<encryptedtag name="Kay" Id="-1">B1C1V1</encryptedtag>

□

Implementation

Our implementation uses the C++ language, with external libraries to support XML usage and cryptographic functions; specifically the Xerces-C++ XML toolkit from Apache [Xerces2008], and Crypto++ [Crypto++2008]. First, the schema file is parsed and loaded into memory represented as a tree like structure (a schema graph). Once the tree is constructed, the access control policy file will be parsed and can be validated for semantic correctness against the schema in memory (although this is not currently completed). Lastly, all of the information that the encryption process requires will be saved into a file that can be loaded at a later point in time. Currently, this file is a simple xml file that contains the generated keys, schema graph and annotations, as well as the set of conditions specific in the access control policy.

The encryption process works by firstly re-loading (if necessary) the data saved to the xml file back into memory, and next the document to be encrypted is parsed with a SAX parser. Each node in the document will be encrypted in the order they appear in the document, with nodes being queued if there is not enough information available to encrypt them at the time they are first encountered (this can happen when the access control policy specified a condition for this node which cannot be calculated until a node later in the document is parsed). The encryption process is implemented in such a way that the algorithm used to perform the encryption can be changed very easily, so either a symmetric or asymmetric algorithm can be used based on user preference. It is also possible to extend the implementation to provide a run time facility for selecting an encryption algorithm.

Nested paths to arbitrary nodes in conditions are supported through a combination of data caching and a queue. During encryption, each node to be encrypted is added to the end of the encryption queue. Additionally, if the node is an attribute or text node that is referenced by conditions, the value of this node is cached in the global value table. The encryption queue is then flushed, by trying to encrypt as many nodes from the front of the queue as possible. A node can only be encrypted and removed from the queue if all of its dependencies are met. A node with no condition has no dependencies, and can be always encrypted. A node with a condition has dependencies, and the global value table is searched to ensure that all dependent attribute and text nodes have values within this table. If any dependent node is missing a value, this node cannot be encrypted, and no further nodes flushed from the queue. Otherwise, the condition can be evaluated (determining the key to use for encryption) and then the node is encrypted.