The halting problem and undecidability of document generation under access control for tree updates

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Scopus citations

Abstract

We show by reduction from the halting problem for Turing machines that typical rule-based models of fine-grained access control of trees make impossible certain forms of analysis, limiting the ability to audit existing policies and evaluate new ones. 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 based on their hierarchical relationships to other nodes. We consider the problem of determining whether a given document (that is, a rooted vertex-labelled tree) could have been produced in accordance with a particular access control policy for updates. We show that, for rule-based policies based on a simple fragment of XPath, this problem is undecidable. This result shows that rule-based access control policies based on XPath languages 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.

Original languageEnglish
Title of host publicationLanguage and Automata Theory and Applications - Third International Conference, LATA 2009, Proceedings
Pages601-613
Number of pages13
DOIs
StatePublished - 2009
Event3rd International Conference on Language and Automata Theory and Applications, LATA 2009 - Tarragona, Spain
Duration: Apr 2 2009Apr 8 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5457
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference3rd International Conference on Language and Automata Theory and Applications, LATA 2009
Country/TerritorySpain
CityTarragona
Period4/2/094/8/09

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science (all)

Fingerprint

Dive into the research topics of 'The halting problem and undecidability of document generation under access control for tree updates'. Together they form a unique fingerprint.

Cite this