Article

The Halting Problem and Undecidability of Document Generation under Access Control for Tree Updates

Author:

Neil MooreAuthors Info & Claims

LATA '09: Proceedings of the 3rd International Conference on Language and Automata Theory and Applications

Pages 601 - 613

https://doi.org/10.1007/978-3-642-00982-2_51

Published: 31 March 2009 Publication History

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, <em>too</em> powerful, demonstrating the need for a model of access control of tree updates that bridges the gap between expressive and analyzable policies.

References

[1]

Bray, T., Paoli, J., Sperberg-McQueen, C.M., Maler, E., Yergeau, F., Cowan, J.: Extensible markup language (XML) 1.1. World Wide Web Consortium Recommendation (2004), http://www.w3.org/TR/2004/REC-xml11-20040204/

[2]

Bertino, E., Braun, M., Castano, S., Ferrari, E., Mesiti, M.: Author-X: A Javabased system for XML data protection. In: Proceedings IFIP TC11/WG11.3 Fourteenth Annual Working Conference on Database Security: Data and Application Security, Development and Directions, pp. 15-26 (2000)

[3]

Damiani, E., De Capitani di Vimercati, S., Paraboschi, S., Samarati, P.: Securing XML documents. In: Zaniolo, C., Grust, T., Scholl, M.H., Lockemann, P.C. (eds.) EDBT 2000. LNCS, vol. 1777, p. 121. Springer, Heidelberg (2000)

[4]

Hada, S., Kudo, M.: XML Access Control Language: Provisional authorization for XML documents. Technical Report, Tokyo Research Laboratory, IBM Research (2000), http://www.trl.ibm.com/projects/xml/xacl/xacl-spec.html

[5]

Clark, J., DeRose, S.: XML path language (XPath), version 1.0. World Wide Web Consortium Recommendation (1999), http://www.w3.org/TR/1999/REC-xpath-19991116

[6]

Deutsch, A., Tannen, V.: Containment of regular path expressions under integrity constraints. In: Knowledge Representation Meets Databases (2001)

[7]

Miklau, G., Suciu, D.: Containment and equivalence for a fragment of XPath. J. ACM 51(1), 2-45 (2004)

[8]

Cho, S., Amer-Yahia, S., Lakshmanan, L.V., Srivastava, D.: Optimizing the secure evaluation of twig queries. In: Proceedings 28th VLDB Conference (2002)

[9]

Lim, C.H., Park, S., Son, S.H.: Access control of XML documents considering update operations. In: Proceedings 2003 ACM Workshop on XML Security (2003)

[10]

Cautis, B., Abiteboul, S., Milo, T.: Reasoning about XML update constraints. In: PODS 2007: Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pp. 195-204. ACM, New York (2007)

[11]

Damiani, E., Fansi, M., Gabillon, A., Marrara, S.: Securely updating XML. In: Apolloni, B., Howlett, R.J., Jain, L. (eds.) KES 2007, Part III. LNCS, vol. 4694, pp. 1098-1106. Springer, Heidelberg (2007)

[12]

Fundulaki, I., Maneth, S.: Formalizing XML access control for update operations. In: Lotz, V., Thuraisingham, B.M. (eds.) SACMAT, pp. 169-174. ACM, New York (2007)

[13]

Bertino, E., Catania, B., Ferrari, E., Perlasca, P.: A logical framework for reasoning about access control models. ACM Trans. Inf. Syst. Secur. 6(1), 71-127 (2003)

[14]

Fundulaki, I., Marx, M.: Specifying access control policies for XML documents with XPath. In: Proceedings 9th ACM Symposium on Access Control Models and Technologies, pp. 61-69 (2004)

[15]

Laux, A., Martin, L.: XUpdate--XML update language. Working Draft (2000), http://xmldb-org.sourceforge.net/xupdate/xupdate-wd.html

[16]

Gottlob, G., Koch, C., Pichler, R.: Efficient algorithms for processing XPath queries. In: Proc. of the 28th International Conference on Very Large Data Bases (VLDB 2002) (2002)

[17]

Bravo, L., Cheney, J., Fundulaki, I.: ACCOn: checking consistency of XML write-access control policies. In: Kemper, A., Valduriez, P., Mouaddib, N., Teubner, J., Bouzeghoub, M., Markl, V., Amsaleg, L., Manolescu, I. (eds.) EDBT. ACM International Conference Proceeding Series, vol. 261, pp. 715-719. ACM, New York (2008)

Cited By

Moore N(2011)Computational complexity of the problem of tree generation under fine-grained access control policiesInformation and Computation10.1016/j.ic.2010.11.019209:3(548-567)Online publication date: 1-Mar-2011
https://dl.acm.org/doi/10.1016/j.ic.2010.11.019
Moore NDong XNaumann F(2010)Reconciling two models of multihierarchical markupProcceedings of the 13th International Workshop on the Web and Databases10.1145/1859127.1859146(1-6)Online publication date: 6-Jun-2010
https://dl.acm.org/doi/10.1145/1859127.1859146
Jacquemard FRusinowitch MKutsia TSchreiner WFernández M(2010)Rewrite-based verification of XML updatesProceedings of the 12th international ACM SIGPLAN symposium on Principles and practice of declarative programming10.1145/1836089.1836105(119-130)Online publication date: 26-Jul-2010
https://dl.acm.org/doi/10.1145/1836089.1836105

The Halting Problem and Undecidability of Document Generation under Access Control for Tree Updates
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Security and privacy
  1. Security services
  2. Systems security

Recommendations

Configuring role-based access control to enforce mandatory and discretionary access control policies

Access control models have traditionally included mandatory access control (or lattice-based access control) and discretionary access control. Subsequently, role-based access control has been introduced, along with claims that its mechanisms are general ...
Computational complexity of the problem of tree generation under fine-grained access control policies

We 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 ...
Delegation in role-based access control

User delegation is a mechanism for assigning access rights available to one user to another user. A delegation can either be a grant or transfer operation. Existing work on delegation in the context of role-based access control models has extensively ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

LATA '09: Proceedings of the 3rd International Conference on Language and Automata Theory and Applications

March 2009

751 pages

ISBN:9783642009815

Editors:
Adrian Horia Dediu
Research Group on Mathematical Linguistics, Rovira i Virgili University, Tarragona, Spain 43002
,
Armand Mihai Ionescu
Research Group on Mathematical Linguistics, Universitat Rovira i Virgili, Tarragona, Spain
,
Carlos Martín-Vide
European Research Council Executive Agency, Brussels, Belgium 1210

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 31 March 2009

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Moore N(2011)Computational complexity of the problem of tree generation under fine-grained access control policiesInformation and Computation10.1016/j.ic.2010.11.019209:3(548-567)Online publication date: 1-Mar-2011
https://dl.acm.org/doi/10.1016/j.ic.2010.11.019
Moore NDong XNaumann F(2010)Reconciling two models of multihierarchical markupProcceedings of the 13th International Workshop on the Web and Databases10.1145/1859127.1859146(1-6)Online publication date: 6-Jun-2010
https://dl.acm.org/doi/10.1145/1859127.1859146
Jacquemard FRusinowitch MKutsia TSchreiner WFernández M(2010)Rewrite-based verification of XML updatesProceedings of the 12th international ACM SIGPLAN symposium on Principles and practice of declarative programming10.1145/1836089.1836105(119-130)Online publication date: 26-Jul-2010
https://dl.acm.org/doi/10.1145/1836089.1836105

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents