Secure XML querying with security views

ABSTRACT

The prevalent use of XML highlights the need for a generic, flexible access-control mechanism for XML documents that supports efficient and secure query access, without revealing sensitive information unauthorized users. This paper introduces a novel paradigm for specifying XML security constraints and investigates the enforcement of such constraints during XML query evaluation. Our approach is based on the novel concept of security views, which provide for each user group (a) an XML view consisting of all and only the information that the users are authorized to access, and (b) a view DTD that the XML view conforms to. Security views effectively protect sensitive data from access and potential inferences by unauthorized user, and provide authorized users with necessary schema information to facilitate effective query formulation and optimization. We propose an efficient algorithm for deriving security view definitions from security policies (defined on the original document DTD) for different user groups. We also develop novel algorithms for XPath query rewriting and optimization such that queries over security views can be efficiently answered without materializing the views. Our algorithms transform a query over a security view to an equivalent query over the original document, and effectively prune query nodes by exploiting the structural properties of the document DTD in conjunction with approximate XPath containment tests. Our work is the first to study a flexible, DTD-based access-control model for XML and its implications on the XML query-execution engine. Furthermore, it is among the first efforts for query rewriting and optimization in the presence of general DTDs for a rich a class of XPath queries. An empirical study based on real-life DTDs verifies the effectiveness of our approach.

REFERENCES

• 1: Serge Abiteboul , Peter Buneman , Dan Suciu, Data on the Web: from relations to semistructured data and XML, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 2: Sihem Amer-Yahia , SungRan Cho , Laks V. S. Lakshmanan , Divesh Srivastava, Minimization of tree pattern queries, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.497-508, May 21-24, 2001, Santa Barbara, California, United States
• 3: Elisa Bertino , Elena Ferrari, Secure and selective dissemination of XML documents, ACM Transactions on Information and System Security (TISSEC), v.5 n.3, p.290-331, August 2002 [doi>10.1145/545186.545190]
• 4: T. Bray, J. Paoli, and C. M. Sperberg-McQueen. Extensible Markup Language (XML) 1.0 W3C Recommendation, Feb. 1998.
• 5: Silvana Castano , Maria Grazia Fugini , Giancarlo Martella , Pierangela Samarati, Database security, ACM Press/Addison-Wesley Publishing Co., New York, NY, 1995
• 6: S. Cho, S. Amer-Yahia, L. Lakshmanan, and D. Srivastava. Optimizing the secure evaluation of twig queries. In VLDB, 2002.
• 7: J. Clark and S. DeRose. XML Path Languages (XPath). W3C Working Draft, Nov. 1999.
• 8: Ernesto Damiani , Sabrina De Capitani di Vimercati , Stefano Paraboschi , Pierangela Samarati, Securing XML Documents, Proceedings of the 7th International Conference on Extending Database Technology: Advances in Database Technology, p.121-135, March 27-31, 2000
• 9: Ernesto Damiani , Sabrina De Capitani di Vimercati , Stefano Paraboschi , Pierangela Samarati, A fine-grained access control system for XML documents, ACM Transactions on Information and System Security (TISSEC), v.5 n.2, p.169-202, May 2002 [doi>10.1145/505586.505590]
• 10: Alin Deutsch , Lucian Popa , Val Tannen, Physical Data Independence, Constraints, and Optimization with Universal Plans, Proceedings of the 25th International Conference on Very Large Data Bases, p.459-470, September 07-10, 1999
• 11: Alin Deutsch , Val Tannen, Reformulation of XML Queries and Constraints, Proceedings of the 9th International Conference on Database Theory, p.225-241, January 08-10, 2003
• 12: A. Diaz and D. Lovell, XML generator, 1999.
• 13: Mary Fernández , Yana Kadiyska , Dan Suciu , Atsuyuki Morishima , Wang-Chiew Tan, SilkRoute: A framework for publishing relational data in XML, ACM Transactions on Database Systems (TODS), v.27 n.4, p.438-493, December 2002 [doi>10.1145/582410.582413]
• 14: Mary F. Fernandez , Dan Suciu, Optimizing Regular Path Expressions Using Graph Schemas, Proceedings of the Fourteenth International Conference on Data Engineering, p.14-23, February 23-27, 1998
• 15: G, Gottlob, C. Koch, and R, Pichler, Efficient algorithms for processing XPath queries. In VLDB, 2002.
• 16: S. Hada and M. Kudo. XML access control language: Provisional authorization for XML documents. http://www.trl.ibm.com/projects/xml/xacl/xacl-spec.html.
• 17: C. Koch. XML Task Force, 2003.
• 18: Gerome Miklau , Dan Suciu, Containment and equivalence for an XPath fragment, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543623]
• 19: G. Miklau and D. Suciu. controlling access to published data using cryptography. In VLDB, 2003.
• 20: R. Milner, Communication and Concurrency, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 21: Tova Milo , Dan Suciu, Index Structures for Path Expressions, Proceeding of the 7th International Conference on Database Theory, p.277-295, January 10-12, 1999
• 22: Makoto Murata , Akihiko Tozawa , Michiharu Kudo , Satoshi Hada, XML access control using static analysis, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948122]
• 23: NAA Classified advertising standard task force. Adex DTD, 1999.
• 24: Frank Neven , Thomas Schwentick, XPath Containment in the Presence of Disjunction, DTDs, and Variables, Proceedings of the 9th International Conference on Database Theory, p.315-329, January 08-10, 2003
• 25: Oasis. eXtensible Access Control Markup Language (XACML). http://www.oasis-open.org/committees/xcaml.
• 26: Yannis Papakonstantinou , Vasilis Vassalos, Query rewriting for semistructured data, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.455-466, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 27: Prakash Ramanan, Efficient algorithms for minimizing tree pattern queries, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564726]
• 28: Takao Asano , Kuniaki Hori , Takao Ono , Tomio Hirata, A Theoretical Framework of Hybrid Approaches to MAX SAT, Proceedings of the 8th International Symposium on Algorithms and Computation, p.153-162, December 17-19, 1997