DETECTING ANOMALIES IN ACCESS CONTROL LISTS

• US 20110107418A1
• Filed: 10/31/2009
• Published: 05/05/2011
• Est. Priority Date: 10/31/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Naldurg, Prasad G., Das, Tathagata, Bhagwan, Ranjita
• Granted Patent: US 8,359,652 B2
• Time in Patent Office: Days
• US Class Current: 726/22
• CPC Class Codes: G06F 21/604 Tools and structures for managing or administering access control systems

Abstract

An access control anomaly detection system and method to detect potential anomalies in access control permissions and report those potential anomalies in real time to an administrator for possible action. Embodiments of the system and method input access control lists and semantic groups (or any dataset having binary matrices) to perform automated anomaly detection. This input is processed in three broad phases. First, policy statements are extracted from the access control lists. Next, object-level anomaly detection is performed using thresholds by categorizing outliers in the policies discovered in the first phase as potential anomalies. This object-level anomaly detection can yield object-level security anomalies and object-level accessibility anomalies. Group-level anomaly detection is performed in the third phase by using semantic groups and user sets extracted in first phase to find maximal overlaps using group mapping. This group-level anomaly detection can yield group-level security anomalies and group-level accessibility anomalies.

Claims

1. A method implemented on a computing device having a processor for detecting candidate anomalies in an access control list, comprising:

using the computing device having the processor to perform the following;

inputting the access control list and a list of semantic groups;

extracting policy statements from the access control list;

detecting any candidate object-level anomalies using the extracted policy statements;

generating a real-time anomaly detection report containing the candidate object-level anomalies; and

presenting the real-time anomaly detection report in real time to an administrator for verification and correction of the candidate object-level anomalies.

2. The method of claim 1, further comprising:

detecting any candidate group-level anomalies by correlating the extracted policy statements with the semantic groups;

generating the real-time anomaly detection report containing the candidate group-level anomalies; and

presenting the real-time anomaly detection report in real time to the administrator for verification and correction of the candidate group-level anomalies.

3. The method of claim 2, further comprising:

determining a first, second, and third object-level anomaly threshold;

selecting a policy statement pair having a user portion and an object portion from the extracted policy statements;

constructing a first user comparison term and a second user comparison term from the user portion of the policy statement pair; and

constructing an object comparison term from the object portion of the policy statement pair.

4. The method of claim 3, further comprising determining that each the following is true:

a. the first user comparison term is less than or equal to the first object-level anomaly threshold;

b. the second user comparison term is less than or equal to the second object-level anomaly threshold; and

c. the object comparison term is less than or equal to the third object-level anomaly threshold.

5. The method of claim 4, further comprising determining that the current policy statement pair is a candidate object-level accessibility anomaly by finding that some users in the policy statement pair do not have access to a second object set of the policy statement pair while users in a first user set to have access to the second object set.

6. The method of claim 4, further comprising determining that the current policy statement pair is a candidate object-level security anomaly by finding that some users in the policy statement pair have access to a second object set of the policy statement pair while users in a first user set also have access to the second object set.

7. The method of claim 2, further comprising:

inputting a set of users that was extracted by mining the extracted policy statements;

obtaining a cover set and an unmatched user set for a current user of the set of users;

selecting a semantic group from the list of semantic groups;

determining that the selected semantic group is contained in the cover set; and

designating the current user in the selected semantic group as a candidate group-level accessibility anomaly.

8. The method of claim 7, further comprising:

constructing a group-level anomaly ratio from the current user and the unmatched user set;

determining a group-level anomaly threshold;

determining that the group-level anomaly ratio is less than or equal to the group-level anomaly threshold; and

designating the current user as a candidate group-level security anomaly.

9. A method implemented on a computing device having a processor for auditing an access control list to identify potential anomalies, comprising:

using the computing device having the processor to perform the following;

extracting from the access control list a policy statement pair having a user portion and an object portion;

determining a first object-level anomaly threshold, a second object-level anomaly threshold, and a third object-level anomaly threshold;

constructing a first user comparison term and a second user comparison term from the user portion;

constructing an object comparison term from the object portion;

finding object-level anomalies using the first and the second comparison terms, the object comparison term, and the first, second, and third anomaly thresholds;

determining a cover set and an unmatched user set;

finding group-level anomalies using the cover set and the unmatched user set;

generating a real-time anomaly detection report containing the object-level anomalies and the group-level anomalies; and

displaying the real-time anomaly detection report containing the object-level anomalies and the group-level anomalies to an administrator in real time for verification.

10. The method of claim 9, further comprising:

selecting an object from the access control list;

obtaining a set of users that is able to access the object;

determining whether a hash table contains any other objects having the same set of users;

if not, then creating a new set of objects corresponding to the set of users;

if so, then adding the object to a set of objects already stored in the hash table for the same set of users; and

updating the hash table.

11. The method of claim 10, further comprising:

creating an input matrix by processing the updated hash table to group objects having the same set of users; and

generating the policy statement pair for a unique bit-string in the input matrix.

12. The method of claim 9, further comprising determining that the first user comparison term is less than or equal to the first object-level anomaly threshold, the second user comparison term is less than or equal to the second object-level anomaly threshold, and the object comparison term is less than or equal to the third object-level anomaly threshold.

13. The method of claim 12, further comprising:

determining that some users in the policy statement pair do not have access to a second object set while users in a first user set do have access; and

designating the policy statement pair as a candidate object-level accessibility anomaly.

14. The method of claim 13, further comprising:

determining that some users in the policy statement pair have access to the second object set and users in the first user set also have access; and

designating the policy statement pair as a candidate object-level security anomaly.

15. The method of claim 9, further comprising:

inputting user sets and semantic groups;

determining a cover threshold;

constructing a mapping ratio term from a current semantic group from the semantic groups and a current user set from the user sets;

determining whether the mapping ration term is less than or equal to the cover threshold;

if not, then discarding the current semantic group; and

if so, then adding the current semantic group to generate a pruned semantic group.

16. The method of claim 15, further comprising:

selecting a minimum semantic group from the pruned semantic group for the current user set using a minimum description length principle;

adding the minimum semantic group to the cover set for a current user to generate a current user cover set;

determining whether the current user is covered;

if so, then removing the current user from the current user cover set and adding the current user to the cover set; and

if not, then adding the current user to the unmatched user set.

17. The method of claim 16, further comprising:

selecting a current semantic group from the semantic groups;

determining whether the current semantic group is contained in the cover set; and

if so, then designating the current user in the current semantic group as a group-level accessibility anomaly.

18. The method of claim 17, further comprising:

constructing a group-level anomaly ratio from the current user and the unmatched user set;

determining a group-level anomaly threshold;

finding that the group-level anomaly ratio is less than or equal to the group-level anomaly threshold; and

designating the current user as a group-level security anomaly.

19. A computer-implemented method for finding anomalies in an access control list, comprising:

grouping objects in a hash table having a same set of users to create an input matrix;

extracting a policy statement pair from the access control list by generating the policy statement pair for a unique bit-string in the input matrix;

obtaining three object-level anomaly thresholds;

constructing a first user comparison term and a second user comparison term from a user portion of the policy statement pair;

constructing an object comparison term from an object portion of the policy statement pair;

determining that the first user comparison term, the second user comparison term, and the object comparison term are less than or equal to the respective object-level anomaly thresholds;

finding a candidate object-level accessibility anomaly by determining that some users in the policy statement pair do not have access to a second object set while users in a first object set do have access;

finding a candidate object-level security anomaly by determining that some users in the policy statement pair have access to the second object set and that users in the first user set also have access;

performing group mapping to generate a cover set and an unmatched user set;

determining group-level accessibility anomalies and group-level security anomalies using the cover set and the unmatched user set;

generating a real-time anomaly detection report containing the candidate object-level accessibility anomalies, the object-level security anomalies, the group-level accessibility anomalies, and the group-level security anomalies; and

displaying the real-time anomaly detection report in real time to an administrator.

20. The computer-implemented method of claim 19, further comprising:

obtaining a set of users that was extracted by policy mining;

selecting a current semantic group from a set of semantic groups;

determining whether the current semantic group is contained in the cover set;

if so, then designating the current user in the current semantic set as a group-level accessibility anomaly;

constructing a group-level anomaly ratio from the current user and the unmatched user set;

obtaining a group-level anomaly threshold;

determining whether the group-level anomaly ratio is less than or equal to the group-level anomaly threshold; and

if so, then designating the current user as a group-level security anomaly.