Role-Based Access Control as a Programming Challenge

(file name: rbac.pl)

This programming challenge was created for the Workshop on Logic and Practice of Programming (LPOP) at the Federated Logic Conference (FLOC), Oxford, UK, July 18, 2018, by Annie Liu. Web page and schedule is here: http://lpop.cs.stonybrook.edu. Complete challenge is here: LPOP challenge

Amy sets the roles and permissions for all the users that participate in a conference (i.e., chairs, authors, etc.). She considers the following sets:

• USERS set of users
• ROLES set of roles
• PERMS set of permissions
• UR set of user-role pairs is subset of USERS * ROLES
• RP set of role-permission pairs is subset of ROLES * PERMS
• RH set of pairs of roles, called ascendant and descendant roles, where an ascendant role inherits permissions from a descendant role. This role hierarchy is transitive.
  • For any user the set of roles of user and their transitive descendant roles is called the AuthorizedRoles for that user

After Amy decided on the above sets and assigned the roles to all the users, she realized that she defined too many roles for each user and too many permissions for every role, so she wants to find the ROLES' , UR', RP', and RH' with the smallest total size of UR', RP', and RH' such that each user has the same permissions through AuthorizedRoles as before (in RBAC this is called MinRoleAssignmentsWithHierarchy). Find this smallest total size of UR', RP', and RH'.

Input format

An input file for LP systems contains the following facts:

• One fact of the form users(Number) containing the number of users (these users are represented by numbers from 1 to Number).
• One fact of the form roles(Number) containing the number of roles (these are represented by numbers from 1 to Number).
• One fact of the form perms(Number) containing the number of different permissions (these are represented by numbers from 1 to Number).
• One fact of the form urs(Number) containing the number of pairs in UR (these are represented by numbers from 1 to Number).
• Facts of the form ur(Number,User,Role) containing the ur number and the user-role pair.
• One fact of the form rps(Number) containing the number of pairs in RP (these are represented by numbers from 1 to Number).
• Facts of the form rp(Number,Role,Permission) containing the rp number and the role-permission pair.
• One fact of the form rhs(Number) containing the number of pairs in RH (these are represented by numbers from 1 to Number).
• Facts of the form rh(Number,Role1,Role2) containing the rh number and the ascendant and descendant roles.

Output format

The output should contain exactly one fact of the form minRoleAssignmentsWithHierarchy(S), where S is the smallest total size of UR', RP', and RH'.

Acknowledgment: thanks to Annie Liu for suggesting this problem.