Efficient access enforcement in distributed role-based access control (RBAC) deployments

ABSTRACT

We address the distributed setting for enforcement of a centralized Role-Based Access Control (RBAC) protection state. We present a new approach for time- and space-efficient access enforcement. Underlying our approach is a data structure that we call a cascade Bloom filter. We describe our approach, provide details about the cascade Bloom filter, its associated algorithms, soundness and completeness properties for those algorithms, and provide an empirical validation for distributed access enforcement of RBAC. We demonstrate that even in low-capability devices such as WiFi network access points, we can perform thousands of access checks in a second.

REFERENCES

• 1: Martín Abadi , Michael Burrows , Butler Lampson , Gordon Plotkin, A calculus for access control in distributed systems, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.4, p.706-734, Sept. 1993 [doi>10.1145/155183.155225]
• 2: E. Al-Shaer, H. Hamed, R. Boutaba, and M. Hasan. Conflict classification and analysis of distributed firewall policies. IEEE Journal on Selected Areas in Communications (JSAC), 23(10), October 2005.
• 3: Lujo Bauer , Scott Garriss , Michael K. Reiter, Distributed Proving in Access-Control Systems, Proceedings of the 2005 IEEE Symposium on Security and Privacy, p.81-95, May 08-11, 2005 [doi>10.1109/SP.2005.9]
• 4: M. Blaze , J. Feigenbaum , J. Ioannidis , A. Keromytis, The KeyNote Trust-Management System Version 2, RFC Editor, 1999
• 5: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 6: Kevin Borders , Xin Zhao , Atul Prakash, CPOL: high-performance policy evaluation, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA [doi>10.1145/1102120.1102142]
• 7: A. Broder and M. Mitzenmacher. Network applications of bloom filters: A survey. In Proceedings of the 40th Annual Allerton Conference on Communication, Control and Computing, pages 636--646. ACM Press, 2002.
• 8: Bernard Chazelle , Joe Kilian , Ronitt Rubinfeld , Ayellet Tal, The Bloomier filter: an efficient data structure for static support lookup tables, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 9: Michael J. Clancy , Donald E. Knuth, A programming and problem-solving seminar, Stanford University, Stanford, CA, 1977
• 10: Saar Cohen , Yossi Matias, Spectral bloom filters, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872787]
• 11: Li Fan , Pei Cao , Jussara Almeida , Andrei Z. Broder, Summary cache: a scalable wide-area web cache sharing protocol, IEEE/ACM Transactions on Networking (TON), v.8 n.3, p.281-293, June 2000 [doi>10.1109/90.851975]
• 12: David F. Ferraiolo , Ravi Sandhu , Serban Gavrila , D. Richard Kuhn , Ramaswamy Chandramouli, Proposed NIST standard for role-based access control, ACM Transactions on Information and System Security (TISSEC), v.4 n.3, p.224-274, August 2001 [doi>10.1145/501978.501980]
• 13: Eric Freudenthal , Tracy Pesin , Lawrence Port , Edward Keenan , Vijay Karamcheti, dRBAC: Distributed Role-based Access Control for Dynamic Coalition Environments, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.411, July 02-05, 2002
• 14: Günter Karjoth, Access control with IBM Tivoli access manager, ACM Transactions on Information and System Security (TISSEC), v.6 n.2, p.232-257, May 2003 [doi>10.1145/762476.762479]
• 15: Ninghui Li , Mahesh V. Tripunitara, Security analysis in role-based access control, ACM Transactions on Information and System Security (TISSEC), v.9 n.4, p.391-420, November 2006 [doi>10.1145/1187441.1187442]
• 16: LinkSys. The wireless-g access point - wap54g. http://www.linksysbycisco.com/US/en/support/WAP54G, 2009.
• 17: Michael Mitzenmacher, Compressed bloom filters, IEEE/ACM Transactions on Networking (TON), v.10 n.5, p.604-612, October 2002 [doi>10.1109/TNET.2002.803864]
• 18: Anna Pagh , Rasmus Pagh, Uniform Hashing in Constant Time and Optimal Space, SIAM Journal on Computing, v.38 n.1, p.85-96, March 2008 [doi>10.1137/060658400]
• 19: Anna Pagh , Rasmus Pagh , S. Srinivasa Rao, An optimal Bloom filter replacement, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 20: M. V. Ramakrishna, Practical performance of Bloom filters and parallel free-text searching, Communications of the ACM, v.32 n.10, p.1237-1239, Oct. 1989 [doi>10.1145/67933.67941]
• 21: 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]
• 22: Kulesh Shanmugasundaram , Hervé Brönnimann , Nasir Memon, Payload attribution via hierarchical bloom filters, Proceedings of the 11th ACM conference on Computer and communications security, October 25-29, 2004, Washington DC, USA [doi>10.1145/1030083.1030089]
• 23: Sourceforge. Cpu usage limiter for linux. http://cpulimit.sourceforge.net/, 2009.
• 24: F. I. P. Standards. Secure hash standard. http://csrc.nist.gov/publications/fips/fips180-2/fips180-2withchangenotice.pdf, 2002.
• 25: M. V. Tripunitara and B. Carbunar. Efficient access enforcement in distributed role-based access control (RBAC) deployments. Technical report, ECE Department, University of Waterloo, 2009. Available from http://ece.uwaterloo.ca/~tripunit/papers/TC09a.pdf .
• 26: Qiang Wei , Jason Crampton , Konstantin Beznosov , Matei Ripeanu, Authorization recycling in RBAC systems, Proceedings of the 13th ACM symposium on Access control models and technologies, June 11-13, 2008, Estes Park, CO, USA [doi>10.1145/1377836.1377848]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Access controls

Additional Classification:
  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:
Algorithms, Security

Keywords:
access control, bloom filter, efficiency, enforcement