Breaking the Trade-Off

Abstract

Role-Based Access Control (RBAC) is foundational to enterprise security, yet manual role engineering remains error-prone and unscalable. Although automated role mining addresses this, existing methods face a critical trade-off: exact approaches guarantee minimal roles but fail on real-world scales, while heuristics scale but lack formal guarantees. This inconsistency forces enterprises into suboptimal, insecure configurations—increasing vulnerability risks and compliance costs. We resolve this instability
through a four-level resource-aware framework that dynamically adapts: (1) a memory-light heuristic, (2) optimality-preserving reductions, (3) a greedy heuristic with logarithmic approximation bounds, and (4) an ILP-based exact solver. Notably, our approach eliminates more than 99% of edges in 26 out of 31 real-world systems, enabling globally optimal role configurations and achieving an average 53% simplification of existing RBAC systems. Our heuristics achieve near-optimal solutions, while providing significant speedups over prior heuristics. Beyond individual components, the unified, adaptive framework minimizes suboptimal decisions at any scale. We open-source this framework to enable minimal RBAC deployment at any scale.