{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,7]],"date-time":"2025-11-07T08:47:27Z","timestamp":1762505247840,"version":"3.41.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2007,5,1]],"date-time":"2007-05-01T00:00:00Z","timestamp":1177977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst. Secur."],"published-print":{"date-parts":[[2007,5]]},"abstract":"<jats:p>Separation-of-duty (SoD) is widely considered to be a fundamental principle in computer security. A static SoD (SSoD) policy states that in order to have all permissions necessary to complete a sensitive task, the cooperation of at least a certain number of users is required. Role-based access control (RBAC) is today's dominant access-control model. It is widely believed that one of RBAC's main strengths is that it enables the use of constraints to support policies, such as separation-of-duty. In the literature on RBAC, statically mutually exclusive roles (SMER) constraints are used to enforce SSoD policies. In this paper, we formulate and study fundamental computational problems related to the use of SMER constraints to enforce SSoD policies. We show that directly enforcing SSoD policies is intractable (coNP-complete), while checking whether an RBAC state satisfies a set of SMER constraints is efficient; however, verifying whether a given set of SMER constraints enforces an SSoD policy is also intractable (coNP-complete). We discuss the implications of these results. We show also how to generate SMER constraints that are as accurate as possible for enforcing an SSoD policy.<\/jats:p>","DOI":"10.1145\/1237500.1237501","type":"journal-article","created":{"date-parts":[[2007,6,6]],"date-time":"2007-06-06T14:37:11Z","timestamp":1181140631000},"page":"5","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":91,"title":["On mutually exclusive roles and separation-of-duty"],"prefix":"10.1145","volume":"10","author":[{"given":"Ninghui","family":"Li","sequence":"first","affiliation":[{"name":"Purdue University, West Lafayette, IN"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mahesh V.","family":"Tripunitara","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, IN"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ziad","family":"Bizri","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, IN"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2007,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/319171.319176"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/382912.382913"},{"key":"e_1_2_1_3_1","first-page":"359","article-title":"American national standard for information technology---role based access control","author":"ANSI.","year":"2004","journal-title":"ANSI INCITS"},{"volume-title":"Proceedings of the 4th European Symposium on Research in Computer Security (ESORICS). 44--64","author":"Atluri V.","key":"e_1_2_1_4_1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/RISP.1990.63844"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/300830.300837"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1147\/sj.403.0666"},{"volume-title":"Proceedings of the 1987 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, Washington, D.C. 184--194","author":"Clark D. D.","key":"e_1_2_1_8_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/775412.775419"},{"volume-title":"Proceedings of the 3rd Workshop on Foundations of Computer Security","year":"2004","author":"Crampton J.","key":"e_1_2_1_10_1"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1063979.1063986"},{"volume":"35","volume-title":"Satisfiability Problem: Theory and Applications. DIMACS Series in Discrete Mathematics and Theoretical Computer Science","author":"Du D.","key":"e_1_2_1_12_1"},{"volume-title":"Proceedings of the 15th National Information Systems Security Conference.","author":"Ferraiolo D. F.","key":"e_1_2_1_13_1"},{"volume-title":"Proceedings of the 11th Annual Computer Security Applications Conference (ACSAC'95)","author":"Ferraiolo D. F.","key":"e_1_2_1_14_1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/501978.501980"},{"key":"e_1_2_1_16_1","unstructured":"Ferraiolo D. F. Kuhn D. R. and Chandramouli R. 2003. Role-Based Access Control. Artech House.   Ferraiolo D. F. Kuhn D. R. and Chandramouli R. 2003. Role-Based Access Control. Artech House."},{"volume-title":"Proceedings of IEEE Symposium on Research in Security and Privacy. 142--153","author":"Foley S.","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/266420.266447"},{"key":"e_1_2_1_19_1","unstructured":"Garey M. R. and Johnson D. J. 1979. Computers And Intractability: A Guide to the Theory of NP-Completeness. Freeman San Francisco CA.   Garey M. R. and Johnson D. J. 1979. Computers And Intractability: A Guide to the Theory of NP-Completeness. Freeman San Francisco CA."},{"volume-title":"Proceedings of IEEE Symposium on Research in Security and Privacy. 172--183","author":"Gligor V. D.","key":"e_1_2_1_20_1"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/319171.319175"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/501963.501966"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/775412.775420"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2005.1"},{"volume-title":"Proceedings of the Fifteenth Annual Working Conference on Database and Application Security. Kluwer Academic Publishers","author":"Kandala S.","key":"e_1_2_1_25_1"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Knorr K. and Stormer H. 2001. Modeling and Analyzing Separation of Duties in Workflow Environments. 199--212.   Knorr K. and Stormer H. 2001. Modeling and Analyzing Separation of Duties in Workflow Environments. 199--212.","DOI":"10.1007\/0-306-46998-7_14"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/266741.266749"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1030083.1030091"},{"volume-title":"Proceedings of IEEE Symposium on Research in Security and Privacy. 201--209","author":"Nash M. J.","key":"e_1_2_1_29_1"},{"key":"e_1_2_1_30_1","unstructured":"Papadimitriou C. H. 1994. Computational Complexity. Addison Wesley Longman New York.  Papadimitriou C. H. 1994. Computational Complexity. Addison Wesley Longman New York."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1975.9939"},{"volume-title":"Proceedings of the IFIP WG11","year":"1990","author":"Sandhu R.","key":"e_1_2_1_32_1"},{"volume-title":"Proceedings of the 13th NIST-NCSC National Computer Security Conference. 526--540","author":"Sandhu R.","key":"e_1_2_1_33_1"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACSAC.1988.113349"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.485845"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/373256.373257"},{"volume-title":"Proceedings of The 10th Computer Security Foundations Workshop. IEEE Computer Society Press, Washington, D.C. 183--194","author":"Simon T. T.","key":"e_1_2_1_37_1"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/1009380.1009674"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/352600.352622"},{"volume-title":"Database Security: Status and Prospects. Results of the IFIP WG 11.3 Initial Meeting","author":"Ting T. C.","key":"e_1_2_1_40_1"}],"container-title":["ACM Transactions on Information and System Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1237500.1237501","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1237500.1237501","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:52:07Z","timestamp":1750258327000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1237500.1237501"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,5]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,5]]}},"alternative-id":["10.1145\/1237500.1237501"],"URL":"https:\/\/doi.org\/10.1145\/1237500.1237501","relation":{},"ISSN":["1094-9224","1557-7406"],"issn-type":[{"type":"print","value":"1094-9224"},{"type":"electronic","value":"1557-7406"}],"subject":[],"published":{"date-parts":[[2007,5]]},"assertion":[{"value":"2007-05-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}