Detecting anomalies in behavioral network with contextual side information

• US 9,659,085 B2
• Filed: 12/28/2012
• Issued: 05/23/2017
• Est. Priority Date: 12/28/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Wang, Xiang, Stokes, III, Jack Wilson, Hardy, Edward Wilkins, Espenschied, Jonathan Andreas, Thiesson, Bo
• Primary Examiner(s): Chen, Susan
• Application Number:
  US13/730,078
• Publication Number:
  US 20140188895A1
• Time in Patent Office: 1,607 Days
• Field of Search: 707 1, 707748, 707899, 706 50, 702 85, 726 25
• CPC Class Codes: G06F 16/335 Filtering based on additional data, e.g. user or group profiles filtering in web context G06F16/9535, G06F16/9536

Abstract

Various technologies described herein pertain to detecting contextual anomalies in a behavioral network. Label propagation can be performed to construct contexts and assign respective context membership scores to users. Each context can be a respective subset of the users expected to have similar resource usages. The contexts can be constructed and the context membership scores can be assigned by combining behavioral information and contextual side information. The behavioral information can specify respective resource usages by the users within the behavioral network. Moreover, respective contextual anomaly scores for the users can be computed based on the respective context membership scores assigned to the users and the contextual side information. Further, the contextual anomalies can be detected from the contextual anomaly scores.

Claims

1. A method of detecting security threats in a computing network, the method executed by at least one processor of a computing device, the method comprising:

receiving, from the computing network, behavioral information over a time period for a set of users in the computing network, the behavioral information over the time period comprises identities of the users and identities of computing devices in the computing network respectively utilized by the users;

for the time period, constructing contexts and assigning respective context membership scores to the users by performing label propagation to combine the behavioral information over the time period and contextual side information, the contextual side information comprises at least one of attributes of the users or attributes of the computing devices, the contexts being constructed and the respective context membership scores being assigned to the users based on previous contexts and previous respective context membership scores assigned to the users for a prior time period, each context is a respective subset of the users, and a context membership score for a particular context assigned to a given user being indicative of the given user belonging to the particular context;

computing respective contextual anomaly scores for the users for the time period based on the respective context membership scores assigned to the users and the contextual side information;

detecting a security threat in the computing network for the time period based on the contextual anomaly scores; and

causing the computing device to output information specifying the security threat in the computing network for the time period.

2. The method of claim 1, computing the respective contextual anomaly scores for the users for the time period further comprising computing a contextual anomaly score for the given user based on a difference between the contextual membership score assigned to the given user and an expected contextual membership score for the given user, the expected contextual membership score for the given user being based on the contextual side information and the respective contextual membership scores assigned to other users in the set of users.

3. The method of claim 1, the contextual side information comprises the attributes of the users, the method further comprising:

converting the attributes of the users into pairwise constraints between users in the set of users, the label propagation is performed based on the pairwise constraints between the users and the respective contextual anomaly scores are computed based on the pairwise constraints between the users.

4. The method of claim 1, the attributes of the users comprise at least one of names of the users, locations of the users, groups to which the users belong, or titles of the users.

5. The method of claim 1, further comprising:

generating user-by-resource activity data that specifies interactions between the users and the computing devices in the computing network, the user-by-resource activity data is generated based on the behavioral information over the time period;

generating user-by-user affinity data based on the user-by-resource activity data, the user-by-user affinity data specifies similarities between the respective computing device usages of the users; and

generating user-by-user constraint data based on the contextual side information;

performing the label propagation further comprises combining the user-by-user affinity data and the user-by-user constraint data to construct the contexts and assign the respective context membership scores to the users.

6. The method of claim 5, the contextual side information comprises the attributes of the computing devices, and the user-by-user affinity data is generated based on the user-by-resource activity data and the attributes of the computing devices.

7. The method of claim 5, generating the user-by-user constraint data further comprises:

computing a first portion of the user-by-user constraint data that pertains to a first type of information in the contextual side information;

computing a second portion of the user-by-user constraint data that pertains to a second type of information in the contextual side information, the first type of information differs from the second type of information; and

combining at least the first portion of the user-by-user constraint data and the second portion of the user-by-user constraint data to form the user-by-user constraint data.

8. The method of claim 1, performing the label propagation further comprises:

initializing labels of the users;

propagating the labels of the users to respective neighbors of each of the users based on the contextual side information; and

subsequent to propagating the labels of the users to the respective neighbors of each of the users based on the contextual side information, propagating the labels of the users based on the behavioral information over the time period until convergence, the labels of the users after convergence are the respective context membership scores assigned to the users.

9. The method of claim 8, performing the label propagation further comprises repeating the propagating of the labels of the users to the respective neighbors of each of the users based on the contextual side information prior to propagating the labels of the users based on the behavioral information for the time step.

10. The method of claim 1, further comprising updating the contexts as constructed and the context membership scores assigned to the users over time utilizing the label propagation based on at least one of behavioral information over a subsequent time period, alterations to the contextual side information, or feedback of an analyst.

11. The method of claim 1, the computing devices in the computing network respectively utilized by the users being the computing devices to which the users respectively connect, and the contextual side information comprises user location information.

12. The method of claim 1, further comprising detecting the security threat in the computing network for the time period from a ranked list of the contextual anomaly scores.

13. The method of claim 1, the computing network is a time-evolving heterogeneous network.

14. The method of claim 1, further comprising:

receiving, from the computing network, behavioral information over a subsequent time period for the users in the computing network;

for the subsequent time period, constructing updated contexts and assigning respective updated context membership scores to the users by performing label propagation to combine the behavioral information over the subsequent time period and the contextual side information;

computing respective updated contextual anomaly scores for the users for the subsequent time period based on the respective updated context membership scores assigned to the users and the contextual side information;

detecting a security threat in the computing network for the subsequent time period based on the updated contextual anomaly scores; and

causing the computing device to output information specifying the security threat in the computing network for the subsequent time period.

15. A system that detects security threats in a computing network, comprising:

at least one processor; and

a memory that comprises computer-executable instructions that, when executed by the at least one processor, cause the at least one processor to perform acts including;

for a time period, constructing contexts and assigning respective context membership scores to a set of users by performing label propagation to combine behavioral information over the time period for the set of users in the computing network and contextual side information, the behavioral information over the time period comprises identities of the users and identities of the computing devices in the computing network respectively utilized by the users, the contexts being constructed and the respective context membership scores being assigned to the users based on previous contexts and previous respective context membership scores assigned to the users for a prior time period, each context is a respective subset of the users, and a context membership score for a particular context assigned to a given user being indicative of the given user belonging to the particular context;

computing respective contextual anomaly scores for the users for the time period based on the respective context membership scores assigned to the users and the contextual side information;

detecting a security threat in the computing network for the time period based on the contextual anomaly scores; and

causing information specifying the security threat in the computing network for the time period to be outputted.

16. The system of claim 15, the memory further comprises computer-executable instructions that, when executed by the at least one processor, cause the at least one processor to perform acts including:

generating user-by-resource activity data based on the behavioral information, the user-by-resource activity data specifies interactions between the users and the computing devices in the computing network;

generating user-by-user affinity data based on the user-by-resource activity data, the user-by-user affinity data specifies similarities between the respective computing device usages of the users;

generating user-by-user constraint data based on the contextual side information; and

combining the user-by-user affinity data and the user-by-user constraint data during the label propagation to construct the contexts and assign the respective context membership scores to the users.

17. The system of claim 16, the memory further comprises computer-executable instructions that, when executed by the at least one processor, cause the at least one processor to perform acts including:

obtaining feedback from an analyst; and

at least one of;

updating the user-by-user affinity data based on the feedback;

or

updating the user-by-user constraint data based on the feedback.

18. The system of claim 15, the memory further comprises computer-executable instructions that, when executed by the at least one processor, cause the at least one processor to perform acts including:

computing a contextual anomaly score for the given user based on a difference between the contextual membership score assigned to the given user and an expected contextual membership score for the given user, the expected contextual membership score for the given user is based on the contextual side information and the respective contextual membership scores assigned to other users in the set of users.

19. The system of claim 15, the memory further comprises computer-executable instructions that, when executed by the at least one processor, cause the at least one processor to perform acts including:

initializing labels of the users;

propagating the labels of the users to respective neighbors of each of the users based on the contextual side information; and

propagating the labels of the user based on the behavioral information until convergence subsequent to propagation of the labels based on the contextual side information, the labels of the users after convergence are the respective context membership scores assigned to the users.

20. A computer-readable storage device including computer-executable instructions that, when executed by a processor, cause the processor to perform acts including:

for a time period, constructing contexts and assigning respective context membership scores to users in a computing network by performing label propagation to combine behavioral information over the time period and contextual side information, the behavioral information over the time period comprises identities of the users and identities of computing devices in the computing network respectively utilized by the users, the contextual side information comprises at least one of attributes of the users or attributes of the computing devices, the label propagation being performed based on previous contexts and previous respective context membership scores assigned to the users for a prior time period, each context is a respective subset of the users, and a context membership score for a particular context assigned to a given user being indicative of the given user belonging to the particular context;

computing respective contextual anomaly scores for the users for the time period based on the respective context membership scores assigned to the users and the contextual side information;

detecting a security threat in the computing network for the time period based on the contextual anomaly scores; and

causing information specifying the security threat in the computing network for the time period to be outputted.