Skip to main content

Best paper award at SACMAT '22 for Eduard and Gregory

  • Date24 June 2022

Jason Crampton (ISG), Eduard Eiben (Comp Sci), Gregory Gutin (Comp Sci), Daniel Karapetyan (U. of Nottingham) and Diptapriyo Majumdar (Indraprastha Institute of Information Technology Delhi (IIITD), India) have received the best paper award at the ACM Symposium on Access Control Models and Technologies (SACMAT) 2022.

SACMAT22-BestPaper-resized.png

The ACM SACMAT 2022 Best Paper Award

SACMAT 2022 is the 27th Symposium on Access Control Models and Technologies, which was held online 8-10 June 2022.


Title - Generalized Noise Role Mining Award (Best Paper)

Abstract - Role mining seeks to compute a set of roles R, a user-role authorization relation UA and a permission-role authorization relation PA, given a user-permission authorization relation UPA, and 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. In this paper, we introduce the Generalized Noise Role Mining problem (GNRM) – a generalization of the Min Noise Role Mining problem – which we believe has considerable practical relevance. In particular, GNRM can produce “security-aware” or “availability-aware” solutions. Extending work of Fomin et al., we show that  GNRM is fixed parameter tractable, with parameter r+k, where r is the number of roles in the solution and k is the number of discrepancies between UPA and the relation defined by the composition of UA and PA. We also introduce a further variant of GNRM in which the accuracy of the solution is defined by the number of users and permissions that are affected, rather than the number of individual discrepancies k. We show that this variant of GNRM is also fixed-parameter tractable. We then report the results of our experimental work using general-purpose solvers to solve instances of GNRM. Our key findings are that security-aware role mining seems to be easier than availability-aware role mining, based on reasonable assumptions about UPA, and security-aware Role Mining introduces a similar number of discrepancies to Min Noise Role Mining.

Authors - Jason Crampton, Eduard Eiben, Gregory Gutin, Daniel Karapetyan and Diptapriyo Majumdar 

Conference - SACMAT 2022

Related topics

Explore Royal Holloway

Get help paying for your studies at Royal Holloway through a range of scholarships and bursaries.

There are lots of exciting ways to get involved at Royal Holloway. Discover new interests and enjoy existing ones

Heading to university is exciting. Finding the right place to live will get you off to a good start

Whether you need support with your health or practical advice on budgeting or finding part-time work, we can help

Discover more about our 21 departments and schools

Find out why Royal Holloway is in the top 25% of UK universities for research rated ‘world-leading’ or ‘internationally excellent’

Royal Holloway is a research intensive university and our academics collaborate across disciplines to achieve excellence.

Discover world-class research at Royal Holloway

Discover more about who we are today, and our vision for the future

Royal Holloway began as two pioneering colleges for the education of women in the 19th century, and their spirit lives on today

We’ve played a role in thousands of careers, some of them particularly remarkable

Find about our decision-making processes and the people who lead and manage Royal Holloway today