QFilter: fine-grained run-time XML access control via NFA-based query rewriting

ABSTRACT

At present, most of the state-of-the-art solutions for XML access controls are either (1) document-level access control techniques that are too limited to support fine-grained security enforcement; (2) view-based approaches that are often expensive to create and maintain; or (3) impractical proposals that require substantial security-related support from underlying XML databases. In this paper, we take a different approach that assumes no security support from underlying XML databases and examine three alternative fine-grained XML access control solutions, namely <i>primitive, pre-processing</i> and <i>post-processing</i> approaches. In particular, we advocate a pre-processing method called <i>QFilter</i> that uses Non-deterministic Finite Automata (NFA) to rewrite user's query such that any parts violating access control rules are pruned. We show the construction and execution of a QFilter and demonstrate its superiority to other competing methods.

REFERENCES

• 1: 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]
• 2: T. Bray, J. Paoli, and C. M. Sperberg-McQueen (Eds). Extensible Markup Language (XML) 1.0 (2nd Ed.). W3C Recommendation, Oct. 2000..
• 3: S. Cho, S. Amer-Yahia, L. V.S. Lakshmanan, and D. Srivastava. Optimizing the Secure Evaluation of Twig Queries. In VLDB, Hong Kong, China, Aug. 2002.
• 4: 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]
• 5: Ernesto Damiani , Sabrina de Capitani di Vimercati , Stefano Paraboschi , Pierangela Samarati, Design and implementation of an access control processor for XML documents, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.33 n.1-6, p.59-75, June 2000
• 6: Y. Diao and M. J. Franklin. High-Performance XML Filtering: An Overview of YFilter. IEEE Data Eng. Bulletin, Mar. 2003.
• 7: E. B. Fernandez , E. Gudes , H. Song, A Model for Evaluation and Administration of Security in Object-Oriented Databases, IEEE Transactions on Knowledge and Data Engineering, v.6 n.2, p.275-292, April 1994 [doi>10.1109/69.277771]
• 8: S. Godik and T. Moses (Eds). eXtensible Access Control Markup Language (XACML) Version 1.0. OASIS Specification Set, Feb. 2003.
• 9: Michiharu Kudo , Satoshi Hada, XML document security based on provisional authorization, Proceedings of the 7th ACM conference on Computer and communications security, p.87-96, November 01-04, 2000, Athens, Greece [doi>10.1145/352600.352613]
• 10: D. Lee, W. C. Lee and P. Liu. Supporting XML Security Models using Relational Databases: A Vision. In XML Database Symposium (XSym), Berlin, Germany, 2003.
• 11: 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]
• 12: Jonathan Moffett , Morris Sloman , Kevin Twidle, Specifying discretionary access control policy for distributed systems, Computer Communications, v.13 n.9, p.571-580, Nov. 1990 [doi>10.1016/0140-3664(90)90008-5]
• 13: 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]
• 14: Sylvia Osborn, Mandatory access control and role-based access control revisited, Proceedings of the second ACM workshop on Role-based access control, p.31-40, November 06-07, 1997, Fairfax, Virginia, United States [doi>10.1145/266741.266751]
• 15: Fausto Rabitti , Elisa Bertino , Won Kim , Darrell Woelk, A model of authorization for next-generation database systems, ACM Transactions on Database Systems (TODS), v.16 n.1, p.88-131, March 1991 [doi>10.1145/103140.103144]
• 16: Pierangela Samarati , Elisa Bertino , Sushil Jajodia, An Authorization Model for a Distributed Hypertext System, IEEE Transactions on Knowledge and Data Engineering, v.8 n.4, p.555-562, August 1996 [doi>10.1109/69.536249]
• 17: Ravi S. Sandhu , Edward J. Coyne , Hal L. Feinstein , Charles E. Youman, Role-Based Access Control Models, Computer, v.29 n.2, p.38-47, February 1996 [doi>10.1109/2.485845]
• 18: A. R. Schmidt , Florian Waas , Martin L. Kersten , D. Florescu , I. Manolescu , M. J. Carey , R. Busse, The XML benchmark project, CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 2001
• 19: J. Simeon and M. Fernandez. Galax V 0.3.5, Jan. 2004. http://db.bell-labs.com/galax/.
• 20: T. Yu, D. Srivastava, L. V.S. Lakshmanan, and H. V. Jagadish. Compressed Accessibility Map: Efficient Access Control for XML. In VLDB, Hong Kong, China, Aug. 2002.
• 21: Shariq Rizvi , Alberto Mendelzon , S. Sudarshan , Prasan Roy, Extending query rewriting techniques for fine-grained access control, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007631]
• 22: L. Bouganim, F. D. Ngoc,and P. Pucheral. Client-Based Access Control Management for XML documents. In VLDB, Toronto, Canada, 2004.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Security, integrity, and protection

General Terms:
Algorithms, Experimentation, Performance

Keywords:
XML security, data security and privacy, query rewriting