1	Algorithms and Experience in Increasing the Intelligibility and Hygiene of Access Control in Large Organizations

Marc Donner - Morgan Stanley Dean Witter                       
David Nochlin - Morgan Stanley Dean Witter                     
Dennis Shasha - New York University                                

2	The Audit Problem

Large organizations have security policies expressed in natural language that reflect regulations or internal danger, e.g., no person should be able to transfer money and change the books.

Some are quite vague, e.g. each person’s permissions should reflect the permissions needed for the department he or she works in.

Security administrators must manage hundreds of thousands of permissions owned by tens of thousands of employees in an effort to satisfy these policies. We call their task The Audit Problem.

In a better world, each permission (resource-privilege) would fit into a single role and each employee would have one or a small number of roles. 
Adding an employee would involve assigning roles to that employee.
Adding a permission would entail putting it into a role.

The current world is different from the ideal one in several ways:
1.	Employees are given a set of  individual permissions as well as a set of roles.
2.	There are thousands of roles.
3.	The total number of permission assertions (of the form individual I has permission P or individual I has role R) numbers in the hundreds of thousands.

Solving the audit problem in this environment is impractical with manual tools. 

We propose an algorithm to reduce the number of permission assertions by a factor of 10 to 100. Such reductions can ease the job of the security administrator and make it possible to satisfy security policies.

Model

An atomic permission assertion is of the form 
  (User, Asset, Privilege).

Our model consists of grouping users into user groups, assets into asset groups, and privileges into privilege groups. The user groups constitute a cover but not necessarily a partition of the users. Similarly for the asset and privilege groups. (Variants of the model may require that the groups are partitions.)

A molecular permission is of the form:
  (User Group, Asset Group, Privilege Group)

The goal of our algorithm is to replace the atomic permissions by molecular permissions with the following correctness criteria:
:
If (a, u, p) is in PermissionsAtom, then there exists a row (c, g, r) in PermissionsMolecule such that a is in Asset Group c, u is in User Group g, and p is in Privilege Group r. 

If (c,g,r) is in PermissionsMolecule then for all a, u, p such that a is in Asset Group c, u is in User Group g, and p is in Privilege Group r, (a, u, p) is in PermissionsAtom.

These conditions together say that PermissionsMolecule expresses the same permission assertions as PermissionsAtom. 

Our Reduction Algorithm transforms Atomic Permissions to Molecular Permissions while satisfying the correctness conditions. The algorithm forms a set of equivalence classes that become the User, Asset, and Privilege groups.

Example of Reduction Algorithm

Suppose we start with

Asset	User	Privilege	
a1	u1	p1	
a1	u2	p1	
a1	u3	p2	
a2	u1	p2	
a2	u1	p1	

We might reduce first by asset to get:

Asset Group	User	Privilege	
{a1, a2}	u1	p1	
{a1} 	u2	p1	
{a1} 	u3	p2	
{a2} 	u1	p2	

Notice that a1 and a2 are grouped together with respect to u1 and p1 because both are associated with u1 and p1 in the atomic table. This causes the number of rows to be reduced. 
The next step consists of grouping the privileges into privilege groups.  The strategy is to perform groupings based on user and asset group to create sets of privileges. This gives us:
	
Asset Group	User	Privilege Group	
{a1, a2} 	u1	{p1}	
{a1} 	u2	{p1}	
{a1} 	u3	{p2}	
{a2} 	u1	{p2}	
2.1.1	

The next step consists of grouping users into groups.  This is the final step and creates the molecular level of grouping that we seek.
	
PermissionsMolecule
Asset group	User group	Privilege Group	
{a1, a2} 	{u1}	{p1}	
{a1} 	{u2}	{p1}	
{a1} 	{u3}	{p2}	
{a2} 	{u1}	{p2}	
2.1.2	
Questions

This example suggests several questions:
0. Is this algorithm correct? (Yes, see paper.)
1.	Could a different order of reduction yield a molecular table with fewer rows? (Yes and we will show this.)
2.	Might further reductions help? (No, see paper.)
3.	Does the algorithm really help in practice? (Yes, we will show figures.)
4.	Can this help with hygiene? (Yes, by uncovering unreduced table portions.)

Different Order of Reduction

If instead of starting by reducing the asset, we reduce the user first, we go from

Asset	User	Privilege	
a1	u1	p1	
a1	u2	p1	
a1	u3	p2	
a2	u1	p2	
a2	u1	p1	

If we reduce user first, we get:
User group	Asset	Privilege	
{u1, u2}	a1	p1	
{u3}	a1	p2	
{u1}	a2	p2	
{u1}	a2	p1	

Now, if we reduce privilege next, we get:

User Group	Asset	Privilege Group	
{u1, u2}	a1	{p1}	
{u3}	a1	{p2}	
{u1}	a2	{p1, p2}	

This gives us three rather than four rows in the result.
3	Quantitative Results
Reducing atomic relationships to molecular relationships seems to be a plausible idea, but does it really help?  We set out to answer this question using several actual sets of authorization data in daily use within Morgan Stanley Dean Witter.  The numbers we cite are:
3.1.1	The size of the atomic permissions table.
3.1.2	The size of the molecular permissions table,
3.1.3	
1.1.1	
3.2	

The number of atoms is roughly 10 to 100 times the number of molecules

Improving Data Hygiene
An algorithm for data cleaning is an open problem, but we think the following idea is worth exploring: 
•	Suppose that our grouping to the molecular level produces several sets of users that are large and are mutually similar.  The fact that they are not identical might be an indication of inconsistent treatment of these users.  The same holds for assets and for privileges. We may be able to infer that permissions are missing or are superfluous.

Consider the following example of atomic permissions:

A	B	C	
a1	b1	c1	
a1	b1	c2	
a1	b2	c1	
a1	b2	c2	
a1	b3	c1	
a1	b3	c2	
a2	b1	c1	
a2	b1	c2	
a2	b2	c1	
a2	b2	c2	
a2	b3	c1	
a2	b3	c2	

As it stands this can be reduced to one row:

AG	BG	CG	
{a1,a2}	{b1,b2,b3}	{c1,c2}	

Now, we notice that any break in that symmetry, for instance by removing one row, will cause the groups to break up quite a lot.  For instance, if we remove the last row to give:

A	B	C	
a1	b1	c1	
a1	b1	c2	
a1	b2	c1	
a1	b2	c2	
a1	b3	c1	
a1	b3	c2	
a2	b1	c1	
a2	b1	c2	
a2	b2	c1	
a2	b2	c2	
a2	b3	c1	

Then grouping will lead to more rows in the result:

AG	BG	CG	
{a1,a2}	{b1,b2,b3}	{c1}	
{a1,a2}	{b1,b2}	{c2}	
{a1}	{b3}	{c2}	

In this case, we'd want to infer that we were missing:

a2	b3	c2	

Future Work

Human judgement plays the critical role in managing security.  Our hope is to provide tools that help people manage this sometimes-overwhelming task.  This algorithm is one step in that direction.

Other steps include clustering algorithms still under development that contribute to the identification of individuals who might have permissions that are not directly associated with the mission of their department.

4	References

[1] "Role Based Access Control," D. Ferraiolo and R. Kuhn, NIST, http://hissa.ncsl.nist.gov/rbac/

[2] "Guide to the SQL Standard," H. Darwen and C. J. Date, 1997, Addison-Wesley, ISBN 0201964260.

[3] "A Unified Framework For Enforcing Multiple Access Control Policies," S. Jajoida, P. Samarati, V. S. Subrahmanian, and E. Bertino, Proceedings of ACM SIGMOD International Conference on Management of Data, 1997, pp 474-485.