Computational complexity of the problem of tree generation under fine-grained access control policies

AbstractWe consider the problem of deciding whether a fine-grained access control policy for tree updates allows a particular document to be constructed. This problem arises from a number of natural questions related to document security, authenticity, and verifiability. Fine-grained access control is the problem of specifying the set of operations that may be performed on a complex structure. For tree-structured databases and documents, particularly XML, a rule-based approach is most common. In this model, access control policies consist of rules that select the allowed or disallowed targets of queries or updates based on their hierarchical relationships to other nodes.We show that, for a typical form of rule-based fine-grained access control policies based on a simple fragment of XPath, this problem is undecidable. We also prove lower bounds on the complexity of various restrictions of this problem, and demonstrate deterministic and nondeterministic polynomial-time algorithms for two restrictions in particular.These results show that, for sufficiently complex access control languages, certain forms of analysis are very difficult or even impossible, limiting the ability to verify documents, audit existing policies, and evaluate new policies. Thus rule-based access control policies based on XPath are, in some sense, too powerful, demonstrating the need for a model of access control of tree updates that bridges the gap between expressive and analyzable policies