Using new edges for anomaly detection in computer networks

1. A computer-implemented method, comprising:

analyzing, by a computing system, historical data of a frequency with which nodes in a network create and receive new edges;

establishing, by the computing system, baseline models of behavior among the edges in the network based on the analysis of the historical data;

determining, by the computing system, whether each edge in a path or other subgraph is a new edge or a previously existing edge;

when an edge is new, calculating, by the computing system, a probability for the edge based on a probability of an originating node initiating a new edge and a receiving node receiving the new edge;

when an edge previously exists, applying, by the computing system, a model based on observed behavior to obtain the probability for the edge;

detecting, by the computing system, a new edge whose appearance is deemed rare, according to a baseline statistical model, such that a probability of observing the new edge is lower than a predetermined threshold during a time window t; and

flagging the new edge, by the computing system, as potentially anomalous when the deviation from the respective baseline model is detected.

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

performing, by the computing system, method of moments estimation on the probability model.

3. The computer-implemented method of claim 1 , wherein the analysis of the historical data further comprises applying a logical regression to the creation and receipt of new edges by the nodes.

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

assigning a p-value to each edge; and

combining p-values for each edge in a path to produce a score for the overall path.

5. The computer-implemented method of claim 1 , wherein the analysis of the historical data further comprises:

calculating, by the computing system, an empirical distribution of scores under the historical conditions; and

defining a threshold, by the computing system, such that the computing system produces alarms at a predetermined rate based on the empirical distribution.

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

combining, by the computing system, probabilities for each edge in the path or other subgraph to obtain a score for the overall path or other subgraph; and

obtaining a threshold, by the computing system, by calculating an empirical distribution of scores under historical conditions.

7. A computer program embodied on a non-transitory computer-readable medium, the computer program configured to cause at least one processor to:

establish baseline models of behavior among edges in a network based on analysis of historical data;

determine whether each edge in a path or other subgraph is a new edge or a previously existing edge;

calculate a probability for an edge based on a probability of an originating node initiating a new edge and a receiving node receiving the new edge when the edge is new;

apply a model based on observed behavior to obtain the probability for an edge when the edge previously exists;

detect creation of an anomalous new edge in the network; and

flag the new edge as anomalous when creation or receipt of the new edge constitutes atypical behavior by a pair of nodes on either end of communication during a given time window t based on probability models for a plurality of edges in the network.

8. The computer program of claim 7 , wherein the probability models take into account a frequency at which source and destination nodes make and receive new edges from other nodes.

9. The computer program of claim 7 , wherein the program is further configured to cause the at least one processor to:

analyze historical data of a frequency with which the pair of nodes in the network create and receive new edges by applying a logical regression to the creation and receipt of new edges by the pair of nodes.

10. The computer program of claim 9 , wherein the program is further configured to cause the at least one processor to:

establish baseline models of behavior among edges in the network based on the analysis of the historical data;

calculate an empirical distribution of scores under the historical conditions; and

define a threshold such that alarms are produced at a predetermined rate based on this empirical distribution.

11. The computer program of claim 7 , the program further configured to cause the at least one processor to establish a probability of communicating between two computers that have never communicated before.

12. The computer program of claim 7 , the program further configured to cause the at least one processor to:

combine probabilities for each edge in the path or other subgraph to obtain a score for the overall path or other subgraph; and

obtain a threshold by calculating an empirical distribution of scores under historical conditions.

13. A system, comprising:

memory storing computer program instructions configured to detect anomalies 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 whether each edge in a path or other subgraph is a new edge or a previously existing edge;

calculate a probability for an edge based on a probability of an originating node initiating a new edge and a receiving node receiving the new edge when the edge is new; and

establish a probability that a source computer x and a destination computer y that have not communicated before will communicate based on historical data;

provide an indication that a new edge between x and y is anomalous when the probability is below a threshold in a given time window t; and

apply a model based on observed behavior to obtain the probability for an edge when the edge previously exists.

14. The system of claim 13 , wherein the calculating of the probability further comprises establishing a probability of communicating between two computers that have never communicated before.

15. The system of claim 13 , wherein the calculating of the probability further comprises applying a logical regression to the creation and receipt of new edges by the nodes.

16. The system of claim 13 , wherein the plurality of processing cores is further configured to:

assign a p-value to each edge; and

combine p-values for each edge in a path to produce a score for the overall path.

17. The system of claim 13 , wherein the processing cores are further configured to:

combine probabilities for each edge in the path or other subgraph to obtain a score for the overall path or other subgraph; and

obtain a threshold by calculating an empirical distribution of scores under historical conditions.