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 create and receive new edges in a computer network;

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

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, wherein

for a given source node x initiating the new edge to destination node y, a probability model of x initiating the new edge in the given time window is given by

logit( P xy )=α+β x +γ y

where P xy is the probability of the new edge initiated by x and bound for y, α is an effect for an overall rate at which new edges are produced in the computer network, β x is an effect for how often x initiates new edges, and γ y is an effect for how often y receives new edges.

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 , further comprising:

updating, by the computing system, the baseline models of behavior for each of a plurality of edges E during t using X t =0 when E does not exist in t and X t =1 when E does exist in t; and

determining, by the computing system, an asymmetric exponentially weighted moving average (“AEWMA”) for each of the plurality of edges E via

p new =[λ 1 +(1−λ 1 ) p]X t +(1−λ 2 ) p (1− X t )

where λ 1 is an AEWMA weight controlling a rate at which a probability for the edge increases, and λ 2 is an AEWMA weight controlling a rate at which the probability for the edge decreases.

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

selecting, by the computing system, the AEWMA parameters λ 1 and λ 2 according to relative sample size using

λ

=

2

N

+

1

where N is a number of effective time windows, and

λ 1 and λ 2 are selected such that non-anomalous edges become anomalous again when not observed over a period of time.

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

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; and

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

6. The computer-implemented method of claim 5 , 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:

detect creation of an anomalous new edge in a computer 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 computer network, wherein

for a given source node x initiating the new edge to destination node y, a probability model of x initiating the new edge in the given time window is given by

logit( P xy )=α+β x +γ y

where P xy is the probability of the new edge initiated by x and bound for y, α is an effect for an overall rate at which new edges are produced in the computer network, β x is an effect for how often x initiates new edges, and γ y is an effect for how often y receives new edges.

8. The computer program of claim 7 , wherein the probability models takes 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 , the program further configured to cause the at least one processor to:

update the probability models of behavior for each of a plurality of edges E during t using X t =0 when E does not exist in t and X t =1 when E does exist in t; and

determine an asymmetric exponentially weighted moving average (“AEWMA”) for each of the plurality of edges E via

p new =[λ 1 +(1−λ 1 ) p]X t +(1−λ 2 ) p (1− X t )

where λ 1 is an AEWMA weight controlling a rate at which a probability for the edge increases, and λ 2 is an AEWMA weight controlling a rate at which the probability for the edge decreases.

10. The computer program of claim 9 , the program further configured to cause the at least one processor to select the AEWMA parameters λ 1 and λ 2 according to relative sample size using

λ

=

2

N

+

1

where N is a number of effective time windows, and

λ 1 and λ 2 are selected such that non-anomalous edges become anomalous again when not observed over a period of time.

11. The computer program of claim 7 , wherein the program is further configured to cause the at least one processor 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

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

12. The computer program of claim 11 , 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 computer 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

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

flag the new edge as potentially anomalous when initiating or receiving the new edge constitutes atypical behavior by the originating node or the receiving node during a given time window t based on a probability model for the new edge, wherein

for a given source node x initiating a new edge to destination node y, the probability model of x initiating the new edge in the given time window is given by

logit( P xy )=α+β x +γ y

where P xy is the probability of the new edge initiated by x and bound for y, α is an effect for an overall rate at which new edges are produced in the computer network, β x is an effect for how often x initiates new edges, and γ y is an effect for how often y receives new edges.

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

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

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.

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

update baseline models of behavior for each of a plurality of edges E during t using X t =0 when E does not exist in t and X t =1 when E does exist in t; and

determine an asymmetric exponentially weighted moving average (“AEWMA”) for each of the plurality of edges E via

p new =[λ 1 +(1−λ 1 ) p]X t +(1−λ 2 ) p (1− X t )

where λ 1 is an AEWMA weight controlling a rate at which a probability for the edge increases, and λ 2 is an AEWMA weight controlling a rate at which the probability for the edge decreases.

16. The system of claim 15 , wherein the processing cores are further configured to select the AEWMA parameters λ 1 and λ 2 according to relative sample size using

λ

=

2

N

+

1

where N is a number of effective time windows, and

λ 1 and λ 2 are selected such that non-anomalous edges become anomalous again when not observed over a period of time.

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.

18. A computer-implemented method, comprising:

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

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

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;

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

updating, by the computing system, the baseline models of behavior for each of a plurality of edges E during t using X t =0 when E does not exist in t and X t =1 when E does exist in t; and

determining, by the computing system, an asymmetric exponentially weighted moving average (“AEWMA”) for each of the plurality of edges E via

p new =[λ 1 +(1−λ 1 ) p]X t +(1−λ 2 ) p (1− X t )

where λ 1 is an AEWMA weight controlling a rate at which a probability for the edge increases, and λ 2 is an AEWMA weight controlling a rate at which the probability for the edge decreases.

19. The computer-implemented method of claim 18 , further comprising:

selecting, by the computing system, the AEWMA parameters λ 1 and λ 2 according to relative sample size using

λ

=

2

N

+

1

where N is a number of effective time windows, and

λ 1 and λ 2 are selected such that non-anomalous edges become anomalous again when not observed over a period of time.

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

detect creation of an anomalous new edge in a computer network;

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 computer network;

update the probability models of behavior for each of a plurality of edges E during t using X t =0 when E does not exist in t and X t =1 when E does exist in t; and

determine an asymmetric exponentially weighted moving average (“AEWMA”) for each of the plurality of edges E via

p new =[λ 1 +(1−λ 1 ) p]X t +(1−λ 2 ) p (1− X t )

where λ 1 is an AEWMA weight controlling a rate at which a probability for the edge increases, and λ 2 is an AEWMA weight controlling a rate at which the probability for the edge decreases.

21. The computer program of claim 20 , the program further configured to cause the at least one processor to select the AEWMA parameters λ 1 and λ 2 according to relative sample size using

λ

=

2

N

+

1

where N is a number of effective time windows, and

λ 1 and λ 2 are selected such that non-anomalous edges become anomalous again when not observed over a period of time.

22. A system, comprising:

memory storing computer program instructions configured to detect anomalies in a computer 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;

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

flag the new edge as potentially anomalous when initiating or receiving the new edge constitutes atypical behavior by the originating node or the receiving node during a given time window t based on a probability model for the new edge;

update baseline models of behavior for each of a plurality of edges E during t using X t =0 when E does not exist in t and X t =1 when E does exist in t; and

determine an asymmetric exponentially weighted moving average (“AEWMA”) for each of the plurality of edges E via

p new =[λ 1 +(1−λ 1 ) p]X t +(1−λ 2 ) p (1− X t )

where λ 1 is an AEWMA weight controlling a rate at which a probability for the edge increases, and λ 2 is an AEWMA weight controlling a rate at which the probability for the edge decreases.

23. The system of claim 22 , wherein the processing cores are further configured to select the AEWMA parameters λ 1 and λ 2 according to relative sample size using

λ

=

2

N

+

1

where N is a number of effective time windows, and

λ 1 and λ 2 are selected such that non-anomalous edges become anomalous again when not observed over a period of time.