Method and apparatus for identifying a threatening network

• US 9,276,948 B2
• Filed: 12/28/2012
• Issued: 03/01/2016
• Est. Priority Date: 12/29/2011
• Status: Active Grant

• Current Assignee: 21CT Incorporated
• Original Assignee: 21CT Incorporated
• Inventors: Hitt, Laura, McClain, Matt
• Primary Examiner(s): CHEN, SHIN HON
• Application Number:
  US13/730,191
• Publication Number:
  US 20150229662A1
• Time in Patent Office: 1,159 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection
• CPC Class Codes: H04L 63/1425 Traffic logging, e.g. anomaly detection
• CPC Class Codes: H04L 63/1433 Vulnerability analysis

Abstract

A system and method for identifying a threatening network is provided. The system comprises a network movement before/after algorithm that provides a graphical plot of changes in networks'"'"' communications activity from before to after a key event occurs, so that an analyst is able to identify anomalous behavior; a network progression algorithm that provides a graphical plot to analyze behavior in small increments of time without specification or emphasis upon a particular event, so that the analyst is able to see a trend in behavioral changes; a statistical network anomaly ranking algorithm that provides as output a ranked list of the networks; and an anomaly trend graphs algorithm that analyzes and visualizes the networks'"'"' anomaly scores over time, so that the analyst is able to see which networks are consistently suspicious, which networks accumulate more suspiciousness in response to an event, and which networks are trending toward more suspiciousness.

Claims

1. A method for identifying a threatening network, the method comprising:

providing a dataset comprising communications activity of a plurality of networks;

performing an AT-SIG algorithm on the dataset;

displaying a graphic output of the AT-SIG algorithm for each of the plurality of networks; and

identifying a network having anomalous communications activity by a visual comparison of the graphic output of the AT-SIG algorithm for each of the plurality of networks;

wherein the AT-SIG algorithm comprises providing a network movement before/after algorithm that provides a graphical plot of changes in networks'"'"' communications activity from before to after a key event occurs, wherein the network movement before/after algorithm, after accepting a date of the key event known to be of interest, accepting a selection of a social network analysis (SNA) metrics of interest, and accepting a selection of a time interval duration, performs the steps of;

1) assigning weights to edges between pairs of nodes in a network equal to the average frequency of communications between the pairs of nodes as the pairs of nodes appear in the time interval duration;

2) randomly sampling from Poisson distributions of the edges to create a sample of each of the networks, and computing a plurality of SNA metrics for the networks to generate a matrix that is N×

M in size, wherein N is the cardinality of the plurality of networks and M is the cardinality of the plurality of SNA metrics; and

3) repeating steps

     1) to

     2) multiple times to generate multiple SNA metric samples for each network,

wherein the network movement before/after algorithm generates a set of SNA metric samples for each network before the date of the key event and a set of SNA metric samples for each network after the date of the key event;

wherein the AT-SIG algorithm further comprises one or more of the following;

providing a network progression algorithm that provides a graphical plot to analyze behavior in small increments of time without specification or emphasis upon a particular event;

providing a statistical network anomaly ranking algorithm that provides as output a ranked list of the networks; and

providing an anomaly trend graphs algorithm that analyzes and visualizes the networks'"'"' anomaly scores over time.

2. The method of claim 1, wherein the network movement before/after algorithm performs the steps of:

combining the set of SNA metric samples before the date of the key event and the set of SNA metric samples after the date of the key event to determine minimum and maximum values of SNA metrics across the networks and across the samples;

normalizing all SNA metric values such that the smallest value of a SNA metric across samples and networks is 0 and the largest value of a SNA metric across samples and networks is 1;

using principal component analysis (PCA) to compute dimensionality-reducing transformations of SNA metric data that preserve the most variance in the SNA metric data;

projecting normalized set of SNA metric samples before the date of the key event and normalized set of SNA metric samples after the date of the key event;

computing, for each network, a centroid of the samples before the date of the key event and a centroid of the samples after the date of the key event;

computing centroid values in each dimension as an average sample value for the dimension; and

plotting a vector such that a tail of the vector is located at the centroid of the SNA metric samples before the key event and a head of the vector is located at the centroid of the SNA metric samples after the key event.

3. The method of claim 1, wherein the network progression algorithm, after accepting a start time and an end time of data to be analyzed, after accepting a selection of social network analysis (SNA) metrics of interest, and after accepting a specification of a length of a time interval in which the data will be divided, performs the steps of:

combining SNA metrics across all time intervals to determine a minimum value and a maximum value of SNA metrics across the networks and across samples;

normalizing all SNA metric values such that the smallest value of a SNA metric across samples and networks is 0 and the largest value of a SNA metric across samples and networks is 1;

using principal component analysis (PCA) to determine a linear combination of SNA metrics that provides the most variance in the data and computes a M×

M covariance matrix for the SNA metrics;

projecting normalized data for each time interval;

computing, for each network, a centroid of the samples at a plurality of time intervals between the start time and the end time;

computing centroid values in each dimension as an average sample value for the dimension; and

plotting at least two vectors such that a first vector has a tail in a location of a centroid of a network cluster in a first time interval with a head in a second time interval, and a second vector has a tail in the second time interval with a head in a third time interval, wherein the first time interval is one of the time intervals between the start time and the end time, the second time interval immediately follows the first time interval, and the third time interval immediately follows the second time interval.

4. The method of claim 1, wherein the network anomaly ranking algorithm, after accepting a date of the key event known to be of interest, accepting a selection of a social network analysis (SNA) metrics of interest, and accepting a selection of a ranking algorithm to be used, performs the steps of:

1) performing the selected ranking algorithm to identify the most anomalous network in a dataset in response to the key event, and removes data of the most anomalous network;

2) repeating step

     1) to identify the next most anomalous network until only two networks remain, wherein the two remaining networks are both ranked as the least anomalous; and

3) generating an output comprising a list of the networks and associated anomaly ranking.

5. The method of claim 4, wherein the ranking algorithm includes a principal component analysis (PCA)-based scoring algorithm or a removal rank permutation scoring algorithm.

6. The method of claim 1, wherein the anomaly trend graphs algorithm, after accepting dates of events in a dataset, performs the steps of:

computing anomaly scores for all networks for each event using the statistical network anomaly ranking algorithm; and

plotting each network'"'"'s accumulated anomaly score over time, wherein data points on line graphs correspond to the events in the dataset.

7. The method of claim 1, wherein the anomaly trend graphs algorithm provides an indication as to how the effects of a threatening event are propagating through the networks.

8. An asymmetric threat signatures (AT-SIG) system comprising:

one or more processing units;

a display device;

memory media, the memory media comprising a dataset comprising communications activity of a plurality of networks; and

instructions which when loaded into the memory media and executed by the one or more processing units cause the AT-SIG device to perform an AT-SIG algorithm on the dataset and to display on the display device a graphic output of the AT-SIG algorithm for each of the plurality of networks;

wherein the AT-SIG algorithm comprises a network movement before/after algorithm that provides a graphical plot of changes in networks'"'"' communications activity from before to after a key event occurs, wherein the network movement before/after algorithm, after accepting a date of the key event known to be of interest, accepting a selection of a social network analysis (SNA) metrics of interest, and accepting a selection of a time interval duration, performs the steps of;

1) assigning weights to edges between pairs of nodes in a network equal to the average frequency of communications between the pairs of nodes as the pairs of nodes appear in the time interval duration;

2) randomly sampling from Poisson distributions of the edges to create a sample of each of the networks, and computing a plurality of SNA metrics for the networks to generate a matrix that is N×

M in size, wherein N is the cardinality of the plurality of networks and M is the cardinality of the plurality of SNA metrics; and

3) repeating steps

     1) to

     2) multiple times to generate multiple SNA metric samples for each network,

wherein the network movement before/after algorithm generates a set of SNA metric samples for each network before the date of the key event and a set of SNA metric samples for each network after the date of the key event;

wherein the AT-SIG algorithm further comprises one or more of the following;

a network progression algorithm that provides a graphical plot to analyze behavior in small increments of time without specification or emphasis upon a particular event;

a statistical network anomaly ranking algorithm that provides as output a ranked list of the networks; and

an anomaly trend graphs algorithm that analyzes and visualizes the networks'"'"' anomaly scores over time.

9. The system of claim 8, wherein the network movement before/after algorithm:

combines the set of SNA metric samples before the date of the key event and the set of SNA metric samples after the date of the key event to determine minimum and maximum values of SNA metrics across the networks and across the samples;

normalizes all SNA metric values such that the smallest value of a SNA metric across samples and networks is 0 and the largest value of a SNA metric across samples and networks is 1;

uses principal component analysis (PCA) to compute dimensionality-reducing transformations of SNA metric data that preserve the most variance in the SNA metric data;

projects normalized set of SNA metric samples before the date of the key event and normalized set of SNA metric samples after the date of the key event;

computes, for each network, a centroid of the samples before the date of the key event and a centroid of the samples after the date of the key event;

computes centroid values in each dimension as an average sample value for the dimension; and

plots a vector such that a tail of the vector is located at the centroid of the SNA metric samples before the key event and a head of the vector is located at the centroid of the SNA metric samples after the key event.

10. The system of claim 8, wherein the network progression algorithm, after accepting a start time and an end time of data to be analyzed, after accepting a selection of social network analysis (SNA) metrics of interest, and after accepting a specification of a length of a time interval in which the data will be divided:

combines SNA metrics across all time intervals to determine a minimum value and a maximum value of SNA metrics across the networks and across samples;

normalizes all SNA metric values such that the smallest value of a SNA metric across samples and networks is 0 and the largest value of a SNA metric across samples and networks is 1;

uses principal component analysis (PCA) to determine a linear combination of SNA metrics that provides the most variance in the data and computes a M×

M covariance matrix for the SNA metrics;

projects normalized data for each time interval;

computes, for each network, a centroid of the samples at a plurality of time intervals between the start time and the end time;

computes centroid values in each dimension as an average sample value for the dimension; and

plots at least two vectors such that a first vector has a tail in a location of a centroid of a network cluster in a first time interval with a head in a second time interval, and a second vector has a tail in the second time interval with a head in a third time interval, wherein the first time interval is one of the time intervals between the start time and the end time, the second time interval immediately follows the first time interval, and the third time interval immediately follows the second time interval.

11. The system of claim 8, wherein the network anomaly ranking algorithm, after accepting a date of the key event known to be of interest, accepting a selection of a social network analysis (SNA) metrics of interest, and accepting a selection of a ranking algorithm to be used:

1) performs the selected ranking algorithm to identify the most anomalous network in a dataset in response to the key event, and removes data of the most anomalous network;

2) repeats step

     1) to identify the next most anomalous network until only two networks remain, wherein the two remaining networks are both ranked as the least anomalous; and

3) generates an output comprising a list of the networks and associated anomaly ranking.

12. The system of claim 11, wherein the ranking algorithm includes a principal component analysis (PCA)-based scoring algorithm or a removal rank permutation scoring algorithm.

13. The system of claim 8, wherein the anomaly trend graphs algorithm, after accepting dates of events in a dataset:

computes anomaly scores for all networks for each event using the statistical network anomaly ranking algorithm; and

plots each network'"'"'s accumulated anomaly score over time, wherein data points on line graphs correspond to the events in the dataset.

14. The system of claim 8, wherein the anomaly trend graphs algorithm provides an indication as to how the effects of a threatening event are propagating through the networks.

15. An asymmetric threat signatures (AT-SIG) device including one or more processors that execute instructions for identifying a threatening network, the instructions comprising:

executing a network movement before/after algorithm to provide a graphical plot of changes in communications activity of a plurality of networks from before to after a key event occurs,

wherein the network movement before/after algorithm, after accepting a date of the key event known to be of interest, accepting a selection of a social network analysis (SNA) metrics of interest, and accepting a selection of a time interval duration, performs the steps of;

1) assigning weights to edges between pairs of nodes in a network equal to the average frequency of communications between the pairs of nodes as the pairs of nodes appear in the time interval duration;

2) randomly sampling from Poisson distributions of the edges to create a sample of each of the networks, and computing a plurality of SNA metrics for the networks to generate a matrix that is N×

M in size, wherein N is the cardinality of the plurality of networks and M is the cardinality of the plurality of SNA metrics; and

3) repeating steps

     1) to

     2) multiple times to generate multiple SNA metric samples for each network,

wherein the network movement before/after algorithm generates a set of SNA metric samples for each network before the date of the key event and a set of SNA metric samples for each network after the date of the key event;

executing a network progression algorithm to provide a graphical plot to analyze behavior in small increments of time without specification or emphasis upon a particular event;

executing a statistical network anomaly ranking algorithm to provide as output a ranked list of the networks; and

executing an anomaly trend graphs algorithm to analyze and visualize the networks'"'"' anomaly scores over time.