Anomalous network node behavior identification using deterministic path walking

Patent metadata

Field	Value
Publication number	US-11552977-B2
Application number	US-202016738614-A
Country	US
Kind code	B2
Filing date	Jan 9, 2020
Priority date	Jan 9, 2019
Publication date	Jan 10, 2023
Grant date	Jan 10, 2023

Abstract

A computer implemented method of identifying anomalous behavior of a computer system in a set of intercommunicating computer systems, each computer system in the set being uniquely identifiable, the method including monitoring communication between computer systems in the set for a predetermined baseline time period to generate a baseline vector representation of each of the systems; monitoring communication between computer systems in the set for a subsequent predetermined time period to generate a subsequent vector representation of each of the systems; comparing baseline and subsequent vector representations corresponding to a target computer system using a vector similarity function to identify anomalous behavior of the target system in the subsequent time period compared to the baseline time period, wherein a vector representation of the target system for a time period is generated based on a deterministic walk of a graph representation of communications between the computer systems in which nodes of the graph correspond to computer systems in the set and weighted directed edges between nodes of the graph correspond to a characteristic of communication between pairs of computer systems in the set.

First claim

The invention claimed is:

1. A computer implemented method of identifying anomalous behavior of a computer system in a set of intercommunicating computer systems, each computer system in the set of intercommunicating computer systems being uniquely identifiable, the method comprising:
monitoring communication between computer systems in the set of intercommunicating computer systems for a predetermined baseline time period to generate a baseline vector representation of each of the intercommunicating computer systems;
monitoring communication between computer systems in the set of intercommunicating computer systems for a subsequent predetermined time period to generate a subsequent vector representation of each of the intercommunicating computer systems; and
comparing the baseline vector representation and the subsequent vector representation corresponding to a target computer system using a vector similarity function to identify anomalous behavior of the target computer system in the subsequent time period compared to the baseline time period,
wherein a vector representation of the target computer system for a time period is generated based on a deterministic walk of a graph representation of communications between the computer systems in which nodes of the graph correspond to computer systems in the set of intercommunicating computer systems and weighted directed edges between nodes of the graph representation correspond to a characteristic of communication between pairs of computer systems in the set of intercommunicating computer systems, wherein the deterministic walk is one of a set of deterministic walks of the graph representation, and the deterministic walks in the set of deterministic walks are conducted in an order determined at least partly by a degree nodes in the graph representation, and wherein a traversal of an edge between nodes for a walk of the graph representation triggers a decreasing of a weight of the traversed edge so as to progressively deemphasize traversed edges for subsequent walks of the graph representation.

2. The method of claim 1 , wherein the deterministic walk is a walk of the graph representation commencing at a node corresponding to the target computer system and continuing along edges of the graph representation based on a deterministic edge selection function at each node of the graph representation.

3. The method of claim 2 , wherein the edge selection function includes a determination of which edge to traverse for a current node in the graph representation based on a weight of the edge in comparison to weights of other edges for the current node.

4. The method of claim 3 , wherein multiple edges having identical edge weights are differentiated deterministically based on a characteristic of a node to which the edge leads in the graph representation such that the determination of which edge to traverse is based on the deterministic differentiation.

5. The method of claim 3 , wherein the deterministic walk is bounded to a maximum walk length.

6. The method of claim 1 , wherein, where two or more nodes have identical degree, the order of deterministic walks in the set of deterministic walks for the two or more nodes is further determined based on a deterministic ordering of a characteristic of each node.

7. The method of claim 1 , wherein the set of deterministic walks includes sufficient walks of the graph representation such that each node in the graph representation is visited at least once across all walks in the set of deterministic walks.

8. The method of claim 1 , wherein the vector similarity function is a cosine similarity function.

9. The method of claim 1 , wherein the characteristic of communication includes one or more of: a flow of network traffic from a source computer system to a target computer system; or a volume of data communicated from a source computer system to a target computer system.

10. The method of claim 1 , wherein a direction of an edge in the graph representation corresponds to a net direction of flow of network traffic between a source computer system and a target computer system in a communication.

11. The method of claim 1 , wherein a weight of an edge in a graph representation corresponds to a volume of data communicated.

12. The method of claim 1 , further comprising, responsive to the identification of anomalous behavior, implementing protective measures for one or more computer systems in the set of intercommunicating computer systems to protect against malicious communication involving the computer system exhibiting anomalous behavior.

13. The method of claim 12 , wherein the protective measures include one or more of: preventing network communication to or from a particular computer system; performing an antimalware task on one or more of the computer systems in the set of intercommunicating computer systems; disconnecting one or more of the computer systems in the set of intercommunicating computer systems; or increasing a level of monitoring of network communication with one or more computer systems in the set of intercommunicating computer systems.

14. The method of claim 1 , wherein the predetermined baseline time period corresponds to at least part of a time period when the set of intercommunicating computer systems are separated from influence by malicious agents.

15. A non-transitory computer-readable storage medium storing a computer program element comprising computer program code to, when loaded into a computer system and executed thereon, cause the computer system to perform the method as claimed in claim 1 .

16. A computer system comprising:
a processor and memory storing computer program code for identifying anomalous behavior of a computer system in a set of intercommunicating computer systems, each computer system in the set of intercommunicating computer systems being uniquely identifiable, by:
monitoring communication between computer systems in the set of intercommunicating computer systems for a predetermined baseline time period to generate a baseline vector representation of each of the intercommunicating computer systems;
monitoring communication between computer systems in the set of intercommunicating computer systems for a subsequent predetermined time period to generate a subsequent vector representation of each of the intercommunicating computer systems; and
comparing the baseline vector representation and the subsequent vector representation corresponding to a target computer system using a vector similarity function to identify anomalous behavior of the target computer system in the subsequent time period compared to the baseline time period,

wherein a vector representation of the target computer system for a time period is generated based on a deterministic walk of a graph representation of communications between the computer systems in which nodes of the graph correspond to computer systems in the set of intercommunicating computer systems and weighted directed edges between nodes of the graph representation correspond to a characteristic of communication between pairs of computer systems in the set of intercommunicating computer systems, wherein the deterministic walk is one of a set of deterministic walks of the graph representation, and the deterministic walks in the set of deterministic walks are conducted in an order determined at least partly by a degree nodes in the graph representation, and wherein a traversal of an edge between nodes for a walk of the graph representation triggers a decreasing of a weight of the traversed edge so as to progressively deemphasize traversed edges for subsequen

Assignees

• British Telecomm

Inventors

• Gibson Michael

Classifications

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F17/16

  Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} · CPC title

• H04L47/17

  Interaction among intermediate nodes, e.g. hop by hop · CPC title

• G06F21/552

  involving long-term monitoring or reporting · CPC title

• H04L63/1425 Primary

  Traffic logging, e.g. anomaly detection · CPC title