Cited By
View all- Lu JXin YZhang ZPeng HHan J(2018)Supporting user authorization queries in RBAC systems by role–permission reassignmentFuture Generation Computer Systems10.1016/j.future.2018.01.01088(707-717)Online publication date: Nov-2018
Hard Instances for Verification Problems in Access Control
Pages 161 - 164
Abstract
We address the generation and analysis of hard instances for verification problems in access control that are NP-hard. Given the customary assumption that P ≠ NP, we know that such classes exist. We focus on a particular problem, the user-authorization query problem (UAQ) in Role-Based Access Control (RBAC). We show how to systematically generate hard instances for it. We then analyze what we call the structure of those hard instances. Our work brings the important aspect of systematic investigation of hard input classes to access control research.
References
[1]
MiniSat. http://minisat.se/, Feb 2015.
[2]
A. Armando, S. Ranise, F. Turkmen, and B. Crispo. Efficient Run-time Solving of RBAC User Authorization Queries: Pushing the Envelope. In Proceedings of the ACM Conference on Data and Applications Security and Privacy (CODASPY'12). ACM, Feb. 2012.
[3]
L. Chen and J. Crampton. Set covering problems in role-based access control. In Proceedings of the 14th European conference on Research in computer security, ESORICS'09, pages 689--704. Springer-Verlag, 2009.
[4]
S. Du and J. B. D. Joshi. Supporting authorization query and inter-domain role mapping in presence of hybrid role hierarchy. In Proceedings of the eleventh ACM symposium on Access control models and technologies, SACMAT '06, pages 228--236. ACM, 2006.
[5]
A. Ene, W. Horne, N. Milosavljevic, P. Rao, R. Schreiber, and R. E. Tarjan. Fast Exact and Heuristic Methods for Role Minimization Problems. In Proceedings of the 13th ACM Symposium on Access Control Models and Technologies, SACMAT '08, pages 1--10. ACM, 2008.
[6]
M. Gofman, R. Luo, A. Solomon, Y. Zhang, P. Yang, and S. Stoller. RBAC-PAT: A Policy Analysis Tool for Role Based Access Control. In S. Kowalewski and A. Philippou, editors, Tools and Algorithms for the Construction and Analysis of Systems, volume 5505 of Lecture Notes in Computer Science, pages 46--49. Springer Berlin Heidelberg, 2009.
[7]
V. Gogate and R. Dechter. A Complete Anytime Algorithm for Treewidth. In Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence, UAI '04, pages 201--208. AUAI Press, 2004.
[8]
R. Halin. S-functions for graphs. Journal of Geometry, 8(1-2):171--186, 1976.
[9]
K. Jayaraman, M. Tripunitara, V. Ganesh, M. Rinard, and S. Chapin. Mohawk: Abstraction-Refinement and Bound-Estimation for Verifying Access Control Policies. ACM Trans. Inf. Syst. Secur., 15(4):18:1--18:28, Apr. 2013.
[10]
A. Koster, H. Bodlaender, and S. Van Hoesel. Treewidth: Computational experiments. Technical report, Universiteit Utrecht, 2001.
[11]
N. Li and M. V. Tripunitara. Security Analysis in Role-based Access Control. ACM Trans. Inf. Syst. Secur., 9(4):391--420, Nov. 2006.
[12]
N. Li, M. V. Tripunitara, and Q. Wang. Resiliency Policies in Access Control. In Proceedings of the 13th ACM Conference on Computer and Communications Security, CCS '06, pages 113--123. ACM, 2006.
[13]
N. Mousavi. Algorithmic Problems in Access Control. Ph.D. thesis, University of Waterloo, 2014. Available from https://uwspace.uwaterloo.ca/.
[14]
N. Mousavi and M. V. Tripunitara. Mitigating the Intractability of the User Authorization Query Problem in Role-Based Access Control (RBAC). In L. Xu, E. Bertino, and Y. Mu, editors, Proceedings of the 6th International Conference on Network and System Security (NSS), volume 7645 of Lecture Notes in Computer Science, pages 516--529. Springer, 2012.
[15]
S. J. Russell and P. Norvig. Artificial Intelligence - A Modern Approach (3rd ed.). Pearson Education, 2010.
[16]
R. S. Sandhu, E. J. Coyne, H. L. Feinstein, and C. E. Youman. Role-Based Access Control Models. IEEE Computer, 29(2):38--47, February 1996.
[17]
J. Vaidya, V. Atluri, and Q. Guo. The Role Mining Problem: Finding a Minimal Descriptive Set of Roles. In Proceedings of the 12th ACM Symposium on Access Control Models and Technologies, SACMAT '07, pages 175--184. ACM, 2007.
[18]
Q. Wang and N. Li. Satisfiability and Resiliency in Workflow Authorization Systems. ACM Trans. Inf. Syst. Secur., 13(4):40:1--40:35, Dec. 2010.
[19]
G. T. Wickramaarachchi, W. H. Qardaji, and N. Li. An efficient framework for user authorization queries in RBAC systems. In Proceedings of the 14th ACM symposium on Access control models and technologies, SACMAT '09, pages 23--32. ACM, 2009.
[20]
K. Xu, F. Boussemart, F. Hemery, and C. Lecoutre. A simple model to generate hard satisfiable instances. In Proceedings of the 19th international joint conference on Artificial intelligence (IJCAI'05), pages 337--342. Morgan Kaufmann Publishers Inc., 2005.
[21]
K. Xu and W. Li. Many Hard Examples in Exact Phase Transitions. Theor. Comput. Sci., 355(3):291--302, Apr. 2006.
[22]
Y. Zhang and J. B. D. Joshi. UAQ: a framework for user authorization query processing in RBAC extended with hybrid hierarchy and constraints. In Proceedings of the 13th ACM symposium on Access control models and technologies, SACMAT '08, pages 83--92. ACM, 2008.
Index Terms
- Hard Instances for Verification Problems in Access Control
Recommendations
Configuring role-based access control to enforce mandatory and discretionary access control policies
Access control models have traditionally included mandatory access control (or lattice-based access control) and discretionary access control. Subsequently, role-based access control has been introduced, along with claims that its mechanisms are general ...
Delegation in role-based access control
User delegation is a mechanism for assigning access rights available to one user to another user. A delegation can either be a grant or transfer operation. Existing work on delegation in the context of role-based access control models has extensively ...
Discretionary access control with the administrative role graph model
SACMAT '07: Proceedings of the 12th ACM symposium on Access control models and technologiesPrevious research examining the mapping of discretionary access control (DAC) to role-based access control (RBAC) has considered neither ownership nor further granting of privileges. We show how to accomplish this by mapping from a relational database ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2015
242 pages
ISBN:9781450335560
DOI:10.1145/2752952
- General Chair:
- Edgar Weippl,
- Program Chairs:
- Florian Kerschbaum,
- Adam J. Lee
Copyright © 2015 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 June 2015
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
SACMAT '15
Sponsor:
SACMAT '15: 20th ACM Symposium on Access Control Models and Technologies
June 1 - 3, 2015
Vienna, Austria
Acceptance Rates
SACMAT '15 Paper Acceptance Rate 17 of 59 submissions, 29%;
Overall Acceptance Rate 177 of 597 submissions, 30%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 113Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)0
Reflects downloads up to 12 Nov 2024
Other Metrics
Citations
Cited By
View all- Lu JXin YZhang ZPeng HHan J(2018)Supporting user authorization queries in RBAC systems by role–permission reassignmentFuture Generation Computer Systems10.1016/j.future.2018.01.01088(707-717)Online publication date: Nov-2018
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in