A Theory of Role Composition

We study the access control integration problem for web services. Organizations frequently use many services, each with its own access control policies, which must interoperate while maintaining secure access to information. The integration problem is to take the set of such services and to find a globally consistent access control policy that ensures that the system composed from the services does not have any authorization failures or information disclosures. We give a sound and complete algorithm for access control integration by reducing the problem to Boolean constraint solving. We have implemented ROLEMATCHER, a tool to infer global role-based access control schemas for a set of services, and show on examples that it can quickly infer global roles for composed systems, or determine the absence of a globally consistent role schema.