Detecting anomalous behavior via user authentication graphs

• US 10,015,175 B2
• Filed: 04/15/2016
• Issued: 07/03/2018
• Est. Priority Date: 04/16/2015
• Status: Active Grant

• Current Assignee: New Mexico Tech University Research Park Corporation, TRIAD National Security, LLC
• Original Assignee: Los Alamos National Security LLC (Government of the United States of America), New Mexico Tech Reasearch Foundation
• Inventors: Kent, Alexander, Neil, Joshua, Liebrock, Lorie
• Primary Examiner(s): Turchen, James R
• Application Number:
  US15/099,898
• Publication Number:
  US 20160308884A1
• Time in Patent Office: 809 Days
• CPC Class Codes: G06F 18/2415 based on parametric or probabilistic models, e.g. based on likelihood ratio or false acceptance rate versus a false rejection rate
• CPC Class Codes: G06F 21/316 by observing the pattern of computer usage, e.g. typical user behaviour
• CPC Class Codes: G06F 21/552 involving long-term monitoring or reporting
• CPC Class Codes: G06F 21/554 involving event detection and direct action
• CPC Class Codes: H04L 63/08 for authentication of entities cryptographic mechanisms or cryptographic arrangements for entity authentication H04L9/32
• CPC Class Codes: H04L 63/083 using passwords cryptographic mechanisms or cryptographic arrangements for entity authentication using a predetermined code H04L9/3226
• CPC Class Codes: H04L 63/1408 by monitoring network traffic monitoring network traffic per se H04L43/00
• CPC Class Codes: H04L 67/535 Tracking the activity of the user network monitoring arrangements H04L43/00; recording of computer activity G06F11/34

Abstract

Significant and aggregate user authentication activity may be analyzed across a population of users and computers in one or more networks to differentiate between authorized users and intruders in a network, and/or to detect inappropriate behavior by otherwise authorized users. Dynamic graphs and graph models over user and computer authentication activity, including time-constrained models, may be used for the purposes of profiling and analyzing user behavior in computer networks. More specifically, an edge-based breadth first search of graphs may be used that enforces time-constraints while maintaining traditional breadth first search computational complexity equivalence.

Claims

1. A computer-implemented method, comprising:

determining, by a computing system, a set of reachable vertices and a respective distance to each of the reachable vertices from a starting vertex within a graph, wherein the set of reachable vertices represent other computers that a computer, represented by the starting vertex, has authenticated to during a period of time on behalf of its user;

outputting the set of reachable vertices and the respective distance to each of the vertices, by the computing system, as a Person'"'"'s Authentication Subgraph (PAS) for the starting vertex of the graph;

comparing, by the computing system, a plurality of PASs for a computer over a series of sliding time windows; and

determining, by the computing system, based on a statistical comparison of the PASs, whether a deviation between an estimated statistical model and observed PAS attributes at a given time window exceeds an expected deviation for a user, wherein

a level of deviation indicating potential compromise takes into account variability of a history of behavioral observations in order to report statistically significant deviations above normal variation by an externally provided threshold to allow users to receive alerts at a prescribed average reporting rate.

2. The computer-implemented method of claim 1, wherein the determining of the set of reachable vertices and the respective distance to each of the reachable vertices is time-constrained.

3. The computer-implemented method of claim 1, further comprising:

determining, by the computing system, that a computer or its user is potentially malicious by computing statistical measures to compare one or more attributes of the PAS based on user authentication events for the computer with one or more attributes indicative of normal user behavior.

4. The computer-implemented method of claim 3, further comprising:

estimating, by the computing system, a statistical model for baseline behavior of the attributes; and

evaluating probabilities of observed attributes, by the computing system, under the baseline models.

5. The computer-implemented method of claim 3, wherein the one or more attributes comprise PAS diameter, wherein potentially malicious behavior is indicated by a PAS diameter for the computer that is larger than a normal PAS diameter by an amount specific to the PAS being considered and its historical variability.

6. The computer-implemented method of claim 3, wherein one or more differentiating attributes of the one or more attributes comprise attributes that have a p-value of 0.01 or less.

7. The computer-implemented method of claim 1, further comprising:

outputting an identification of the computer, the computing system, for review by a security analyst to determine whether the computer has been compromised or a malicious user is using the computer.

8. The computer-implemented method of claim 1, wherein each sliding time window is a fixed period of time.

9. A computer-implemented method, comprising:

determining, by a computing system, that a computer or its user is potentially malicious by computing statistical measures to compare one or more attributes of a Person'"'"'s Authentication Subgraph (PAS) based on user authentication events for the computer with one or more attributes indicative of normal user behavior;

estimating, by the computing system, a statistical model for baseline behavior of the attributes;

evaluating probabilities of observed attributes, by the computing system, under the baseline models;

outputting the PAS, by the computing system, for review by a security analyst to determine whether the PAS represents a compromised computer or malicious user when the PAS exceeds a statistical threshold;

comparing, by the computing system, a plurality of PASs for a computer over a series of sliding time windows; and

determining, by the computing system, based on a statistical comparison of the PASs, whether a deviation between an estimated statistical model and observed PAS attributes at a given time window exceeds an expected deviation for a user, wherein

a level of deviation indicating potential compromise takes into account variability of a history of behavioral observations in order to report statistically significant deviations above normal variation by an externally provided threshold to allow users to receive alerts at a prescribed average reporting rate.

10. The computer-implemented method of claim 9, wherein the one or more attributes comprise PAS diameter, wherein potentially malicious behavior is indicated by a PAS diameter for the computer that is larger than a normal PAS diameter by an amount specific to the PAS being considered and its historical variability.

11. The computer-implemented method of claim 9, wherein one or more differentiating attributes of the one or more attributes comprise attributes that have a p-value of 0.01 or less.

12. A computer-implemented method, comprising:

comparing, by a computing system, a plurality of Person'"'"'s Authentication Subgraphs (PASs) for a computer over a series of sliding time windows;

determining, by the computing system, based on a statistical comparison of the PASs, whether a deviation between an estimated statistical model and observed PAS attributes at a given time window exceeds an expected deviation for a user; and

when the expected deviation for the user has been exceeded, outputting an identification of the computer, the computing system, for review by a security analyst to determine whether the computer has been compromised or a malicious user is using the computer, wherein

a level of deviation indicating potential compromise takes into account variability of a history of behavioral observations in order to report statistically significant deviations above normal variation by an externally provided threshold to allow users to receive alerts at a prescribed average reporting rate, and

each PAS comprises a set of reachable vertices and a respective distance to each of the reachable vertices from a starting vertex within a graph, the set of reachable vertices representative of other computers that a computer, represented by the starting vertex, has authenticated to during a period of time.

13. The computer-implemented method of claim 12, wherein each sliding time window is a fixed period of time.