Assessing query privileges via safe and efficient permission composition

ABSTRACT

We propose an approach for the selective enforcement of access control restrictions in, possibly distributed, large data collections based on two basic concepts: i) flexible authorizations identify, in a declarative way, the data that can be released, and ii) queries are checked for execution not with respect to individual authorizations but rather evaluating whether the information release they (directly or indirectly) entail is allowed by the authorizations. Our solution is based on the definition of query profiles capturing the information content of a query and builds on a graph-based modeling of database schema, authorizations, and queries. Access control is then effectively modeled and efficiently executed in terms of graph coloring and composition and on traversal of graph paths. We then provide a polynomial composition algorithm for determining if a query is authorized.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: A. V. Aho , C. Beeri , J. D. Ullman, The theory of joins in relational databases, ACM Transactions on Database Systems (TODS), v.4 n.3, p.297-314, Sept. 1979 [doi>10.1145/320083.320091]
• 3: P. Atzeni, S. Ceri, S. Paraboschi, and R. Torlone. Database Systems -- Concepts, Languages and Architectures. McGraw-Hill Book Company, 1999.
• 4: Catriel Beeri , Moshe Y. Vardi, A Proof Procedure for Data Dependencies, Journal of the ACM (JACM), v.31 n.4, p.718-741, Oct. 1984 [doi>10.1145/1634.1636]
• 5: A. Cali' and D. Martinenghi. Querying data under access limitations. In Proc. of ICDE 2008, Cancun, Mexico, April 2008.
• 6: S. Dawson, S. De Capitani di Vimercati, P. Lincoln, and P. Samarati. Maximizing sharing of protected information. Journal of Computer and System Sciences, 64(3):496--541, May 2002.
• 7: Sabrina De Capitani di Vimercati , Sara Foresti , Sushil Jajodia , Stefano Paraboschi , Pierangela Samarati, Controlled Information Sharing in Collaborative Distributed Query Processing, Proceedings of the 2008 The 28th International Conference on Distributed Computing Systems, p.303-310, June 17-20, 2008 [doi>10.1109/ICDCS.2008.62]
• 8: A. Deutsch, B. Ludascher, and A. Nash. Rewriting queries using views with access patterns under integrity constraints. In Proc. of ICDT 2005, Edinburgh, UK, January 2005.
• 9: Daniela Florescu , Alon Levy , Ioana Manolescu , Dan Suciu, Query optimization in the presence of limited access patterns, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.311-322, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 10: Georg Gottlob, Computing cores for data exchange: new algorithms and practical solutions, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065187]
• 11: Georg Gottlob , Alan Nash, Data exchange: computing cores in polynomial time, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142358]
• 12: Chen Li, Computing complete answers to queries in the presence of limited access patterns, The VLDB Journal — The International Journal on Very Large Data Bases, v.12 n.3, p.211-227, October 2003 [doi>10.1007/s00778-002-0085-6]
• 13: David Maier , Alberto Mendelzon , Yehoshua Sagiv, Testing implications of data dependencies, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582119]
• 14: Amihai Motro, An Access Authorization Model for Relational Databases Based on Algebraic Manipulation of View Definitions, Proceedings of the Fifth International Conference on Data Engineering, p.339-347, February 06-10, 1989
• 15: A. Nash and A. Deutsch. Privacy in GLAV information integration. In Proc. of ICDT 2007, Barcelona, Spain, January 2007.
• 16: 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]
• 17: A. Rosenthal and E. Sciore. View security as the basis for data warehouse security. In Proc. of DMDW'2000, Stockholm, Sweden, June 2000.
• 18: Arnon Rosenthal , Edward Sciore, Administering permissions for distributed data: factoring and automated inference, Proceedings of the fifteenth annual working conference on Database and application security, p.91-104, July 15-18, 2001, Niagara, Ontario, Canada

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing; Relational databases

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)

General Terms:
Management, Security

Keywords:
access control, authorization composition