Analyzing and Developing Role-Based Access Control Models

Role-based access control (RBAC) has become today's dominant access control model, and many of its theoretical and practical aspects are well understood. However, certain aspects of more advanced RBAC models, such as the relationship between permission usage and role activation and the interaction between inheritance and constraints, remain poorly understood. Moreover, the computational complexity of some important problems in RBAC remains unknown. In this thesis we consider these issues, develop new RBAC models and answer a number of these questions. We develop an extended RBAC model that proposes an alternative way to distinguish between activation and usage hierarchies. Our extended RBAC model has well-defined semantics, derived from a graph-based interpretation of RBAC state. Pervasive computing environments have created a requirement for access control systems in which authorization is dependent on spatio-temporal constraints. We develop a family of simple, expressive and flexible spatio-temporal RBAC models, and extend these models to include activation and usage hierarchies. Unlike existing work, our models address the interaction between spatio-temporal constraints and inheritance in RBAC, and are consistent and compatible with the ANSI RBAC standard. A number of interesting problems have been defined and studied in the context of RBAC recently. We explore some variations on the set cover problem and use these variations to establish the computational complexity of these problems. Most importantly, we prove that the minimal cover problem -- a generalization of the set cover problem -- is NP-hard. The minimal cover problem is then used to determine the complexity of the inter-domain role mapping problem and the user authorization query problem in RBAC. We also design a number of efficient heuristic algorithms to answer the minimal cover problem, and conduct experiments to evaluate the quality of these algorithms