System and method for improved anomaly detection using relationship graphs
An anomaly-detection system that gathers information relating to the relationships between entities and represents these relationships in a graph that interconnects each pair of related entities. The graph may represent a computer network, in which each node corresponds to a respective device in the network and each edge between two nodes indicates that the devices represented by the nodes exchanged communication with one another in the past. the system monitors each of the entities in the graph, by continually computing a single-entity anomaly score (SEAS) for the entity. If the SEAS exceeds a first threshold the system generates an alert. Otherwise, the system checks whether the SEAS exceeds a second, lower threshold. If so, the system computes a subgraph anomaly score (SAS) for the entity's subgraph. If the SAS exceeds a SAS threshold, an alert is generated. By computing the SAS in this manner resources are conserved.
1. A system for monitoring a plurality of entities, the system comprising:
a communication interface; and
a processor, configured to:
obtain a graph that represents the entities by respective nodes and, via multiple edges, interconnects each pair of the nodes that represents a respective pair of the entities that are related to one another;
receive behavior-indicating data via the communication interface;
designate one or more of the entities as entities of interest (EOIs), which are represented in the graph by respective EOI-nodes of the nodes;
identify multiple EOI subgraphs of the graph, each of the EOI subgraphs corresponding to a respective one of the EOIs and including the EOI-node representing the respective one of the EOIs,
wherein each of the EOI subgraphs includes each one of the nodes that is connected to the EOI-node representing the respective one of the EOIs via M or fewer of the edges, and excludes each one of the nodes that is connected to the EOI-node representing the respective one of the EOIs via more than M of the edges, M being a first positive integer, and
wherein the particular one of the EOI subgraphs corresponds to a particular one of the EOIs, which is represented in the graph by a particular one of the EOI-nodes;
ascertain that the particular one of the nodes belongs to a particular one of the EOI subgraphs;
based on the behavior-indicating data, compute respective single-entity anomaly scores (SEASs) for the entities, each of the SEASs quantifying a first degree to which first behavior of a respective one of the entities is anomalous;
in response to any particular one of the SEASs, for any particular one of the entities, wherein the particular one of the entities is represented by a particular one of the nodes, exceeds a predefined SEAS threshold;
(i) identify a subgraph of the graph, which represents a subset of the entities that includes the particular one of the entities, wherein the subgraph is an SAS subgraph, and the SAS subgraph includes each one of the nodes that is connected to the particular one of the EOI-nodes via N or fewer of the edges and excludes each one of the nodes that is connected to the particular one of the EOI-nodes via more than N of the edges, N being a second positive integer, and
(ii) compute a subgraph anomaly score (SAS) that quantifies a second degree to which second behavior of the subset of the entities is anomalous;
in response to the ascertaining that the particular one of the nodes belongs to the particular one of the EOI subgraphs, compare the particular one of the SEASs to the predefined SEAS threshold; and
in response to the SAS exceeding a predefined SAS threshold, generate an alert.
2. The system according to claim 1 , wherein the processor is configured to obtain the graph by:
identifying each pair of the entities that are related to one another, and
in response to identifying each pair of the entities that are related to one another, constructing the graph.
3. The system according to claim 2 , wherein the processor is configured to identify each pair of the entities that are related to one another based on the pair having communicated with one another.
4. The system according to claim 1 , wherein behavior selected includes at least one of a communication-related behavior and a location-related behavior.
5. The system according to claim 1 , wherein the entities are respective devices in a computer network.
6. The system according to claim 5 , wherein behavior selected from the group of behaviors consisting of: the first behavior and the second behavior includes computational behavior.
7. The system according to claim 1 , wherein the entities are respective persons.
8. The system according to claim 7 , wherein behavior selected from the group of behaviors consisting of: the first behavior and the second behavior includes financial behavior.
9. The system according to claim 1 , and wherein the subgraph includes each one of the nodes that is connected to the particular one of the nodes via N or fewer of the edges and excludes each one of the nodes that is connected to the particular one of the nodes via more than N of the edges, N being a positive integer.
10. The system according to claim 1 ,
wherein the processor is further configured to:
compute respective other SASs for a plurality of other subgraphs of the graph, and
identify a number of the other SASs that exceed the predefined SAS threshold, and
wherein the processor is configured to generate the alert in response to the number.
11. A method for monitoring a plurality of entities, the method comprising:
obtaining a graph that represents the entities by respective nodes and, via multiple edges, interconnects each pair of the nodes that represents a respective pair of the entities that are related to one another;
receiving behavior-indicating data;
designating one or more of the entities as entities of interest (EOIs), which are represented in the graph by respective EOI-nodes of the nodes;
identifying multiple EOI subgraphs of the graph, each of the EOI subgraphs corresponding to a respective one of the EOIs and including the EOI-node representing the respective one of the EOIs,
wherein each of the EOI subgraphs includes each one of the nodes that is connected to the EOI-node representing the respective one of the EOIs via M or fewer of the edges, and excludes each one of the nodes that is connected to the EOI-node representing the respective one of the EOIs via more than M of the edges, M being a first positive integer, and
wherein the particular one of the EOI subgraphs corresponds to a particular one of the EOIs, which is represented in the graph by a particular one of the EOI-nodes;
ascertaining that the particular one of the nodes belongs to a particular one of the EOI subgraphs;
based on the behavior-indicating data, computing respective single-entity anomaly scores (SEASs) for the entities, each of the SEASs quantifying a first degree to which first behavior of a respective one of the entities is anomalous;
in response to any particular one of the SEASs, for any particular one of the entities, wherein the particular one of the entities is represented by a particular one of the nodes, and exceeding a predefined SEAS threshold:
(i) identifying a subgraph of the graph, which represents a subset of the entities that includes the particular one of the entities, wherein the subgraph is an SAS subgraph, and the subgraph includes each one of the nodes that is connected to the particular one of the EOI-nodes via N or fewer of the edges and excludes each one of the nodes that is connected to the particular one of the EOI-nodes via more than N of the edges, N being a positive integer, and
(ii) computing a subgraph anomaly score (SAS) that quantifies a second degree to which second behavior of the subset of the entities is anomalous;
in response to the ascertaining, comparing the particular one of the SEASs to the predefined SEAS threshold; and
in response to the SAS exceeding a predefined SAS threshold, generating an alert.
12. The method according to claim 11 , wherein obtaining the graph comprises obtaining the graph by:
identifying each pair of the entities that are related to one another, and
in response to identifying each pair of the entities that are related to one another, constructing the graph.
13. The method according to claim 12 , wherein identifying each pair of the entities that are related to one another comprises identifying each pair of the entities that are related to one another based on the pair having communicated with one another.
14. The method according to claim 11 , wherein behavior comprises at least one of a communication-related behavior and a location-related behavior.
15. The method according to claim 11 , wherein the entities are respective devices in a computer network.