{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,6]],"date-time":"2026-04-06T10:15:07Z","timestamp":1775470507540,"version":"3.50.1"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,11,9]],"date-time":"2024-11-09T00:00:00Z","timestamp":1731110400000},"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. Priv. Secur."],"published-print":{"date-parts":[[2025,2,28]]},"abstract":"\n Role mining is a technique that is used to derive a role-based authorization policy from an existing policy. Given a set of users\n U<\/jats:italic>\n , a set of permissions\n P<\/jats:italic>\n , and a user\u2013permission authorization relation\n \n \\(\\mathit {UPA} \\subseteq U \\times P\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , a role mining algorithm seeks to compute a set of roles\n R<\/jats:italic>\n , a user\u2013role authorization relation\n \n \\(\\mathit {UA} \\subseteq U \\times R\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , and a permission\u2013role authorization relation\n \n \\(\\mathit {PA} \\subseteq R \\times P\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , such that the composition of\n UA<\/jats:italic>\n and\n PA<\/jats:italic>\n is close (in some appropriate sense) to\n UPA<\/jats:italic>\n . Role mining is therefore a core problem in the specification of role-based authorization policies. Role mining is known to be hard in general and exact solutions are often impossible to obtain, so there exists an extensive literature on variants of the role mining problem that seek to find approximate solutions and algorithms that use heuristics to find reasonable solutions efficiently.\n <\/jats:p>\n \n \n In this article, we first introduce the\n Generalized Noise Role Mining<\/jats:italic>\n problem (GNRM)\u2014a generalization of the\n MinNoise Role Mining<\/jats:sc>\n problem\u2014which we believe has considerable practical relevance. In particular, GNRM can produce \u201csecurity-aware\u201d or \u201cavailability-aware\u201d solutions. Extending the work of Fomin et\u00a0al., we show that GNRM is fixed parameter tractable, with parameter\n \n \\(r + k\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , where\n \n \\(r\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is the number of roles in the solution and\n \n \\(k\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is the number of discrepancies between\n \n \\(\\mathit {UPA}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and the relation defined by the composition of\n \n \\(\\mathit {UA}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and\n \n \\(\\mathit {PA}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . We further introduce a bi-objective optimization variant of GNRM, where we wish to minimize both\n \n \\(r\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and\n \n \\(k\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n subject to upper bounds\n \n \\(r \\le \\bar{r}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and\n \n \\(k\\le \\bar{k}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , where\n \n \\(\\bar{r}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and\n \n \\(\\bar{k}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n are constants. We show that the Pareto front of this bi-objective optimization problem (BO-GNRM) can be computed in fixed-parameter tractable time with parameter\n \n \\(\\bar{r} +\\bar{k}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . From a practical perspective, a solution to BO-GNRM gives security managers the opportunity to identify a mined policy offering the best tradeoff between the number of policy discrepancies and the number of roles.\n <\/jats:p>\n \n \n We then report the results of our experimental work using the integer programming solver Gurobi to solve instances of BO-GNRM. Our key findings are that (a)\u00a0we obtained strong support that Gurobi\u2019s performance is fixed-parameter tractable, and (b)\u00a0our results suggest that our techniques may be useful for role mining in practice, based on our experiments in the context of three well-known real-world authorization policies. We observed that, in many cases, our solver is capable of obtaining optimal solutions when the values of either\n k<\/jats:italic>\n or\n r<\/jats:italic>\n are small.\n <\/jats:p>","DOI":"10.1145\/3697833","type":"journal-article","created":{"date-parts":[[2024,10,14]],"date-time":"2024-10-14T12:42:13Z","timestamp":1728909733000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Bi-objective Optimization in Role Mining"],"prefix":"10.1145","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2151-8426","authenticated-orcid":false,"given":"Jason","family":"Crampton","sequence":"first","affiliation":[{"name":"Mathematics, Royal Holloway University of London, Egham, United Kingdom of Great Britain and Northern Ireland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2628-3435","authenticated-orcid":false,"given":"Eduard","family":"Eiben","sequence":"additional","affiliation":[{"name":"Computer Science, Royal Holloway University of London, Egham, United Kingdom of Great Britain and Northern Ireland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2377-0417","authenticated-orcid":false,"given":"Gregory","family":"Gutin","sequence":"additional","affiliation":[{"name":"Computer Science, Royal Holloway University of London, Egham, United Kingdom of Great Britain and Northern Ireland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4030-6525","authenticated-orcid":false,"given":"Daniel","family":"Karapetyan","sequence":"additional","affiliation":[{"name":"University of Nottingham, School of Computer Science, Nottingham, United Kingdom of Great Britain and Northern Ireland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2677-4648","authenticated-orcid":false,"given":"Diptapriyo","family":"Majumdar","sequence":"additional","affiliation":[{"name":"Indraprastha Institute of Information Technology Delhi, Department of Computer Science and Engineering, New Delhi, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,11,9]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3450569.3463571"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3532105.3535024"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.3233\/JCS-16849"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3381991.3395597"},{"key":"e_1_3_2_6_2","series-title":"LIPIcs","first-page":"41:1\u201341:16","volume-title":"43rd International Symposium on Mathematical Foundations of Computer Science (MFCS\u201918)","author":"Dan Chen","year":"2018","unstructured":"Chen Dan, Kristoffer Arnsfelt Hansen, He Jiang, Liwei Wang, and Yuchen Zhou. 2018. Low rank approximation of binary matrices: Column subset selection and generalizations. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS\u201918)(LIPIcs, Vol. 117), Igor Potapov, Paul G. Spirakis, and James Worrell (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 41:1\u201341:16."},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/1377836.1377838"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/501978.501980"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-019-00669-5"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2017.0895"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(91)90006-6"},{"key":"e_1_3_2_12_2","series-title":"International Series in Operations Research & Management Science","volume-title":"Nonlinear Multiobjective Optimization","author":"Kaisa Miettinen","year":"1999","unstructured":"Miettinen Kaisa. 1999. Nonlinear Multiobjective Optimization. International Series in Operations Research & Management Science, Vol. 12. Kluwer Academic Publishers, Boston, MA, USA."},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2022.3227241"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.11339"},{"key":"e_1_3_2_15_2","series-title":"Monographs and Textbooks in Pure and Applied Mathematics","volume-title":"Boolean Matrix Theory and Applications","author":"Kim Ki Hang","year":"1982","unstructured":"Ki Hang Kim. 1982. Boolean Matrix Theory and Applications. Monographs and Textbooks in Pure and Applied Mathematics, Vol. 70. Marcel Dekker, New York, NY, USA."},{"key":"e_1_3_2_16_2","first-page":"297","volume-title":"The 24th IEEE International Conference on Data Engineering (ICDE\u201908)","author":"Lu Haibing","year":"2008","unstructured":"Haibing Lu, Jaideep Vaidya, and Vijayalakshmi Atluri. 2008. Optimal boolean matrix decomposition: Application to role engineering. In The 24th IEEE International Conference on Data Engineering (ICDE\u201908). IEEE Computer Society, 297\u2013306."},{"issue":"4","key":"e_1_3_2_17_2","first-page":"50:1\u201350:37","article-title":"A survey of role mining","volume":"48","author":"Mitra Barsha","year":"2016","unstructured":"Barsha Mitra, Shamik Sural, Jaideep Vaidya, and Vijayalakshmi Atluri. 2016. A survey of role mining. ACM Comput. Surv. 48, 4 (2016), 50:1\u201350:37.","journal-title":"ACM Comput. Surv."},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/1542207.1542224"},{"key":"e_1_3_2_19_2","first-page":"33","volume-title":"The 7th ACM Symposium on Access Control Models and Technologies (SACMAT\u201902)","author":"Neumann Gustaf","year":"2002","unstructured":"Gustaf Neumann and Mark Strembeck. 2002. A scenario-driven role engineering process for functional RBAC roles. In The 7th ACM Symposium on Access Control Models and Technologies (SACMAT\u201902). ACM, 33\u201342."},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/2.485845"},{"key":"e_1_3_2_21_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1007\/978-3-642-22348-8_8","volume-title":"The 25th Data and Applications Security and Privacy Conference (DBSec\u201911)","volume":"6818","author":"Uzun Emre","year":"2011","unstructured":"Emre Uzun, Vijayalakshmi Atluri, Haibing Lu, and Jaideep Vaidya. 2011. An optimization model for the extended role mining problem. In The 25th Data and Applications Security and Privacy Conference (DBSec\u201911)(Lecture Notes in Computer Science, Vol. 6818). Springer, 76\u201389."},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2008.61"}],"container-title":["ACM Transactions on Privacy and Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3697833","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3697833","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:17:30Z","timestamp":1750295850000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3697833"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,9]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,2,28]]}},"alternative-id":["10.1145\/3697833"],"URL":"https:\/\/doi.org\/10.1145\/3697833","relation":{},"ISSN":["2471-2566","2471-2574"],"issn-type":[{"value":"2471-2566","type":"print"},{"value":"2471-2574","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,9]]},"assertion":[{"value":"2024-03-20","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-09-13","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}