Secure evaluation of XML queries

The rapid emergence of XML as a standard for data exchange over the Web has led to considerable interest in the problem of securing XML documents. This thesis focuses 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.; Query evaluation engines need to ensure that user queries use and return only XML data the user is allowed to access. Secure query evaluation is possible by rewriting the query to use a recursive function that computes an element's security level. These added access control checks can considerably increase query evaluation time. Based on security information in the DTD, efficient algorithms that determine when the recursive check can be eliminated or simplified to a local check on the element's attributes are devised. This thesis experimentally evaluates the performance benefits of these techniques using a variety of XML data and queries.; To efficiently provide secure access to XML data, a family of index structures is developed, which it is referred to as security indices, obtained by enhancing R-tree indices with security levels for XML elements. The straightforward index that annotates each XML element with its (explicitly specified an inherited) security level has a very high update cost for modifying the security level of an XML element. An improved index makes explicit use of the multi-level access control model to reduce the cost of update an element's security level. Efficient algorithms for update are developed. The thesis shows experimentally that this reduced update cost can be achieved without increasing query access cost.; Finally, a prototype LockX is developed, which implements the idea of secure optimization for specifying access control policies and securely querying XML documents. LockX demonstrates access control specification, enforcement, and explanation features.