In bottom-up role mining, the input consists of a set of users and the permissions each user is authorized to perform, and the objective is to derive a role-based access control (RBAC) policy that preserves these authorizations. When the goal is to minimize the number of roles, the problem is NP-hard, and exact algorithms are infeasible on worst-case instances. Recent work introduced a maximal biclique enumeration-based approach and presented an extensive empirical evaluation on benchmark inputs. While this approach yields optimal solutions for most instances, it stalls on hard instances due to exponential growth in maximal bicliques.

Role hierarchies in Role-Based Access Control (RBAC) enable scalable administration by allowing permissions to be inherited among roles. However, deriving high-quality hierarchies from existing flat RBAC policies remains a challenging combinatorial problem. We present two new algorithms for the Role Hierarchy Mining Problem (RHMP) that construct compact and well-structured hierarchies while preserving all user--permission authorizations. The first algorithm, MinRolesRH, restructures a minimal-role RBAC policy into a multi-layer hierarchy without introducing new roles, optimizing for maximal depth and minimal edge count. The second algorithm, NewRolesRH, generalizes this approach by introducing new intermediate roles to maximize hierarchical depth. To further minimize redundant edges, we formulate Integer Linear Programs (ILPs) that prune edges while preserving authorizations. We evaluate the resulting hierarchies using both Weighted Structural Complexity (WSC) and a random-walk based navigability metric, which estimates the expected traversal steps from users to permissions. Experimental results on standard benchmarks and RMPLib datasets demonstrate that our algorithms consistently achieve lower WSC and improved navigability compared to existing algorithms, including RHMiner and Role Generation + Elimination. All implementations are available as open source.

We address least-privilege in a particular context of public cloud computing: calls to Amazon Web Services (AWS) Application Programming Interfaces (APIs). AWS is, by far, the largest cloud provider, and therefore an important context in which to consider the fundamental security design principle of least-privilege, which states that a thread of execution should possess only those privileges it needs. There have been reports of over-privilege being a root cause of attacks against AWS cloud applications, and a least-privilege set for an API call is a necessary building-block in devising a least-privilege policy for a cloud application. We observe that accurate information on a least-privilege set for an invoker of a method to possess is simply not available for most such methods in AWS. We provide a meaningful characterization of least-privilege in this context. We then propose techniques to determine such sets, and discuss a black-box process we have devised and carried out to identify such sets for all 707 API methods we are able to invoke across five AWS services. We discuss a number of interesting discoveries we have made, some of which are surprising and some alarming, that we have reported to AWS. Our work has resulted in a database of least-privilege sets for API calls to AWS, which we make available publicly. Developers can consult our database when configuring security policies for their cloud applications, and we welcome contributors that augment our database. Also, we discuss example uses of our database via an assessment of two repositories and two full-fledged serverless applications that are available publicly and have policies published alongside. We observe that the vast majority of policies are over-privileged. Our work contributes constructively to securing cloud applications in the largest cloud provider.