Abstract
Recently, an access control for XML database is one of the key issues in database security. Given an access control policy and a query expression, static analysis determines whether the query does not access any elements nor attributes that are prohibited by the access control policies. In a related work, policies and queries were modeled as regular sets of paths in trees. However, this model loses information on the structure of the trees, and some policies cannot be represented by the model accurately. In this paper, we propose a formal model for access control of XML databases and provide a static analysis method based on tree automata theory. Both an access control policy and a query are modeled as tree automata, and a policy is provided with two alternative semantics; AND-semantics and OR-semantics. We investigate the computational complexity of the static analysis problem, and show that the problem in AND-semantics is solvable in square time while the problem in OR-semantics is EXPTIME-complete.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bertino, E., Castano, S., Ferrari, E., Mesiti, M.: Author-X: A Java-based system for XML data protection, IFIP WG 11.3 Working Conf on Database Security (2000)
Boag, S., Chamberlin, D., Fernandez, M.F., Florescu, D., Robie, J., Simeon, J.: XQuery 1.0: An XML query language. W3C working draft (August 16, 2002), http://www.w3.org/TR/xquery/
Clark, J., DeRose, S.: XML Path Language (XPath) version 1.0. W3C Recommendation (1999), http://www.w3.org/TR/xpath
Clarke, E.M., Grumberg, O., Peled, D.: Model Checking. MIT Press, Cambridge (2000)
Comon, H., Dauchet, M., Gilleron, R., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree Automata Techniques and Applications (1997), http://www.grappa.univ-lille3.fr/tata
Damiani, E., di Vimercati, S.D.C., Paraboschi, S., Samarati, P.: Securing XML documents. In: Zaniolo, C., Grust, T., Scholl, M.H., Lockemann, P.C. (eds.) EDBT 2000. LNCS, vol. 1777, pp. 121–135. Springer, Heidelberg (2000)
Esparza, J., Hansel, D., Rossmanith, P., Schwoon, S.: Efficient algorithms for model-checking pushdown systems. In: Emerson, E.A., Sistla, A.P. (eds.) CAV 2000. LNCS, vol. 1855, pp. 232–247. Springer, Heidelberg (2000)
Hopcroft, J., Motwani, R., Ullman, J.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading (2000)
Koch, M., Mancini, L., Parisi-Presicce, F.: Conflict detection and resolution in access control policy specifications. In: Nielsen, M., Engberg, U. (eds.) FOSSACS 2002. LNCS, vol. 2303, pp. 223–237. Springer, Heidelberg (2002)
Kudo, M., Harada, S.: XML document security based on provisional authorization. In: 7th ACM CCS, pp. 87–96 (2001)
Lupu, E.C., Sloman, M.: Conflicts in policy-based distributed systems management. IEEE Trans. on Software Eng. 25(6), 852–869 (1999)
Mayr, R.: Process Rewrite System. Inform. & Comput. 156, 264–286 (1999)
Murata, M., Lee, D., Mani, M.: Taxonomy of XML schema languages using formal language theory. ACM Trans. on Internet Technology 5(4) (2005), http://www.cs.wpi.edu/~mmani/publications.html
Murata, M., Tozawa, A., Kudo, M.: XML access control using static analysis. In: ACM CCS 2003, pp. 73–84 (2003)
Neven, F.: Automata theory for XML researchers. SIGMOD Record 31(3), 39–46 (2002)
Nitta, N., Takata, Y., Seki, H.: An efficient security verification method for programs with stack inspection. In: 8th ACM CCS, pp. 68–77 (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Yagi, I., Takata, Y., Seki, H. (2005). A Static Analysis Using Tree Automata for XML Access Control. In: Peled, D.A., Tsay, YK. (eds) Automated Technology for Verification and Analysis. ATVA 2005. Lecture Notes in Computer Science, vol 3707. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11562948_19
Download citation
DOI: https://doi.org/10.1007/11562948_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29209-8
Online ISBN: 978-3-540-31969-6
eBook Packages: Computer ScienceComputer Science (R0)