Path scanning for the detection of anomalous subgraphs and use of DNS requests and host agents for anomaly/change detection and network situational awareness

Patent metadata

Field	Value
Publication number	US-9560065-B2
Application number	US-201314382992-A
Country	US
Kind code	B2
Filing date	Mar 14, 2013
Priority date	Mar 22, 2012
Publication date	Jan 31, 2017
Grant date	Jan 31, 2017

Abstract

A system, apparatus, computer-readable medium, and computer-implemented method are provided for detecting anomalous behavior in a network. Historical parameters of the network are determined in order to determine normal activity levels. A plurality of paths in the network are enumerated as part of a graph representing the network, where each computing system in the network may be a node in the graph and the sequence of connections between two computing systems may be a directed edge in the graph. A statistical model is applied to the plurality of paths in the graph on a sliding window basis to detect anomalous behavior. Data collected by a Unified Host Collection Agent (“UHCA”) may also be used to detect anomalous behavior.

First claim

The invention claimed is:

1. A computer-implemented method, comprising:
determining, by a computing system, historical parameters of a network to determine normal activity levels;
enumerating, by the computing system, a plurality of k-paths in the network as part of a graph representing the network, wherein each computing system in the network comprises a node in the graph and a sequence of connections between two computing systems comprise a directed edge in the graph;
applying, by the computing system, a Markov edge resolution model to the plurality of k-paths in the graph on a sliding window basis; and
detecting, by the computing system, anomalous behavior based on the applied Markov edge resolution model.

2. The computer-implemented method of claim 1 , further comprising:
displaying data pertaining to the detected anomalous behavior to a user.

3. The computer-implemented method of claim 1 , wherein the Markov edge resolution model comprises an Observed Markov Model (“OMM”) or a Hidden Markov Model (“HMM”).

4. The computer-implemented method of claim 3 , wherein
the OMM or the HMM comprise two-state models,
an “on” state indicates user presence, and
an “off” state indicates that the user is not present.

5. The computer-implemented method of claim 1 , wherein the computing system determines the historical parameters by taking into account at least two edge types.

6. The computer-implemented method of claim 5 , wherein a first edge type comprises member edges having sufficient data to estimate an individual model, and a second edge type comprises member edges where there is not sufficient data to estimate individual models for the member edges.

7. The computer-implemented method of claim 6 , wherein the second edge type is parameterized by a mean vector to ensure that models are not overly sensitive to low count edges.

8. The computer-implemented method of claim 1 , further comprising:
collecting data, by the computing system, from a plurality of host agents pertaining to network communications sent and received by respective hosts in the network; and
analyzing the collected data to detect anomalous behavior during a predetermined time period.

9. An apparatus, comprising:
at least one processor; and
memory storing computer program instructions, wherein the instructions, when executed by the at least one processor, are configured to cause the at least one processor to:
determine historical parameters of a network to determine normal activity levels,
enumerate a plurality of k-paths in the network as part of a graph representing the network, wherein each computing system in the network comprises a node in the graph and a sequence of connections between two computing systems comprises a directed edge in the graph,
apply a statistical model to the plurality of k-paths in the graph on a sliding window basis, and
detect anomalous behavior based on the applied statistical model.

10. The apparatus of claim 9 , wherein the computer program instructions are further configured to cause the at least one processor to display data pertaining to the detected anomalous behavior to a user.

11. The apparatus of claim 9 , wherein the statistical model comprises an Observed Markov Model (“OMM”) or a Hidden Markov Model (“HMM”).

12. The apparatus of claim 11 , wherein
the OMM or the HMM comprise two-state models,
an “on” state indicates user presence, and
an “off” state indicates that the user is not present.

13. The apparatus of claim 9 , wherein the computer program instructions are further configured to cause the at least one processor to determine the historical parameters by taking into account at least two edge types.

14. The apparatus of claim 13 , wherein a first edge type comprises member edges having sufficient data to estimate an individual model, and a second edge type comprises member edges where there is not sufficient data to estimate individual models for the member edges.

15. The apparatus of claim 14 , wherein the second edge type is parameterized by a mean vector to ensure that models are not overly sensitive to low count edges.

16. The apparatus of claim 9 , wherein the computer program instructions are further configured to cause the at least one processor to:
collect data from a plurality of host agents pertaining to network communications sent and received by respective hosts in the network, and
analyze the collected data to detect anomalous behavior during a predetermined time period.

17. A system, comprising:
memory storing computer program instructions configured to detect anomalous behavior in a network; and
a plurality of processing cores configured to execute the stored computer program instructions, wherein the plurality of processing cores is configured to:
determine historical parameters of a network to determine normal activity levels,
enumerate a plurality of k-paths in the network as part of a graph representing the network, wherein each computing system in the network comprises a node in the graph and a sequence of connections between two computing systems comprise a directed edge in the graph,
apply a statistical model to the plurality of k-paths in the graph on a sliding window basis, and
detect anomalous behavior based on the applied statistical model.

18. The system of claim 17 , wherein the plurality of processing cores are further configured to display data pertaining to the detected anomalous behavior to a user.

19. The system of claim 17 , wherein the statistical model comprises an Observed Markov Model (“OMM”) or a Hidden Markov Model (“HMM”).

20. The system of claim 19 , wherein
the OMM or the HMM comprise two-state models,
an “on” state indicates user presence, and
an “off” state indicates that the user is not present.

21. The system of claim 17 , wherein
the plurality of processing cores are further configured to determine the historical parameters by taking into account at least two edge types,
a first edge type comprises member edges having sufficient data to estimate an individual model, and
a second edge type comprises member edges where there is not sufficient data to estimate individual models for the member edges.

22. The system of claim 21 , wherein the second edge type is parameterized by a mean vector to ensure that models are not overly sensitive to low count edges.

23. The system of claim 17 , wherein the plurality of processing cores are further configured to:
collect data from a plurality of host agents pertaining to network communications sent and received by respective hosts in the network, and
analyze the collected data to detect anomalous behavior during a predetermined time period.

24. A computer-implemented method, comprising:
collecting data, by a computing system, from a plurality of host agents pertaining to network communications sent and received by respective hosts in a network;
analyzing, by the computing system, the collected data to detect anomalous behavior during a predetermined time period by applying a statistical model to a plurality of k-paths in a graph on a sliding window basis; and
when anomalous behavior is detected, providing, by the computing system, an indication that the anomalous behavior occurred during the predetermined time period.

25. The computer-implemented method of claim 24 , wherein the collected data is sent as one-way communications from the host agents via User Datagram Pr

Assignees

• Los Alamos Nat Security Llc

Inventors

• Neil Joshua Charles
• Fisk Michael Edward
• Brugh Alexander William
• Hash Jr Curtis Lee
• Storlie Curtis Byron
• Uphoff Benjamin
• Kent Alexander

Classifications

• G06N7/01

  Probabilistic graphical models, e.g. probabilistic networks · CPC title

• G06N5/045

  Explanation of inference; Explainable artificial intelligence [XAI]; Interpretable artificial intelligence · CPC title

• G06N5/022

  Knowledge engineering; Knowledge acquisition · CPC title

• G06N5/02

  Knowledge representation; Symbolic representation · CPC title

• H04L1/002

  Algorithms with memory of the previous states, e.g. Markovian models · CPC title