Optimizing the Secure Evaluation of Twig Queries
SungRan Cho
Stevens Institute of Technology
sch o@. a,t t i l a,. st evens-t ech. edu
Laks V.S.
University of British Columbia
l aks~cs.ubc.ca
Sihem Amer-Yahia
AT&T I~a, bs-Research
s ihem@research.att.com
AT&T l~abs-Research
d i vesh (@ research, a,t t. com
The rapid emergence of XML as a standard for
data exchange over the Web has led to con-
siderable interest in the problem of securing
XML documents. In this context, query eval-
uation engines need to ensure that user queries
only use and return XML data the user is al-
lowed to access. These added access control
checks can considerably increase query eval-
uation time. In this paper, we consider the
problem of optimizing the secure evaluation
of XML twig queries.
Wc focus on the simple, but useful, multi-level
access control model, where a security level
can be either specified at an XML element,
or inherited from its parent. For this model,
secure query evaluation is possible by rewrit-
ing the query to use a recursive function that
computes an element's security level. Based
on security information in the DTD, we devise
efficient algorithms that optimally determine
when the recursive check can be eliminated,
and when it can be simplified to just a local
check on the element's attributes, without vi-
olating the access control policy. Finally, we
experimentally evaluate the performance ben-
efits of our techniques using a variety of XML
data and queries.
*Lakshmanan's research was supported by grants from
Permission to copy without fee all or part of this material is
9ranted provided that the copies are not made or distributed for
direct commercial advantage, the VLDB copyright notice and
the title o/ the publication and its date appear, and notice is
9iven that copyin9 is by permission o/the Very Large Data Base
Endowment. To copy otherwise, or to republish, requires a fee
and~or special permission ]rom the Endowment.
Proceedings of the 28th VLDB Conference,
Hong Kong, China, 2002
1 Introduction
Companies are using the Web as the main means of
information dissemination, sparking interest in mod-
els and efficient mechanisms for controlled access to
information content over the Web. In this respect, se-
curing XML documcnts is an important step, because
XML is rapidly emerging as the standard for data rep-
resentation and exchange over the Web.
Much of the work on XML access control to date
(see, e.g., [4, 5, 2, 10, 9, 3]) has studied models for
the specification of XML access control policies, fo-
cusing on issues such as granularity of access (e.g.,
DTD, document, element), propagation options (e.g.,
local, inherited), and conflict resolution (e.g., most
specific, mandatory). Mechanisms for the enforcement
of these XML access control policies have been studied
for the cases of document access (e.g., [9]), and docu-
ment browsing and authoring (e.g., [5, 2]). However,
despite the importance of query access to XML (see,
e.g., [7, 6]), there has been no work on enforcement
of access control policies for the case of XML query
A naive two-step approach to secure XML query
evaluation is: (i) compute the query result using ex-
isting XML query processing techniques (see, e.g., [13,
16, 8, 1]), and (ii) filter the query results, using the ac-
cess control policies, in a post-processing step. While
this approach may appear attractive, it is not secure.
For example, consider the XML database of an online-
seller (the DTD is illustrated in Figure 1), which has
information about books and customer accounts. As-
sume that a specific user is allowed access to the book
information but not to any account information. If
query results are filtered for accessibility, then
the following XQuery path expression:
/ onl ine~sell er [. //customer/name=' smith' ] //book
would allow the user to check the existence of customer
smith, which is clearly not the desired intent of the

Get Proceedings 2002 VLDB Conference now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.