Method and system for identifying a threatening network

• US 9,578,051 B2
• Filed: 02/05/2016
• Issued: 02/21/2017
• 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:
  US15/017,039
• Publication Number:
  US 20160241584A1
• Time in Patent Office: 382 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 method for identifying a threatening network comprises an asymmetric threat signature (AT-SIG) algorithm comprising a network movement before/after algorithm that provides a graphical plot of changes in network transaction activity from before to after a specified time and further comprising one or more of: a network progression algorithm that provides a graphical plot to analyze behavior in small increments of time without specification or emphasis upon a particular time or 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. Also disclosed are an AT-SIG system and a software program product.

Claims

1. A method for identifying a threatening network, the method being implemented by a computer system and comprising:

providing a dataset comprising network transaction data of a plurality of networks;

performing an AT-SIG algorithm on the dataset; and

displaying a 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 network transaction activity from before to after a specified time, wherein the network movement before/after algorithm, after accepting the specified time, accepting a selection of one or more 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 transactions between the pairs of nodes as the pairs of nodes appear in the time interval duration;

2) randomly sampling from Poisson distribution of the edges to create a sample of each of the networks, and computing a plurality of 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 the metrics of interest; and

3) repeating steps

     1) to

     2) multiple times to generate multiple samples for the metrics of interest for each network,

wherein the network movement before/after algorithm generates a set of samples of metrics of interest for each network before the specified time and a set of samples of metrics of interest for each network after the specified time;

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

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

providing a statistical network anomaly ranking algorithm that provides as output a ranked list of the network; 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 samples of the metrics of interest before the specified time and the set of samples of the metrics of interest after the specified time to determine minimum and maximum values of metrics of interest across the networks and across the samples;

normalizing all metric values across samples and networks;

computing dimensionality-reducing transformations of metric data;

projecting normalized sets of samples of the metrics of interest before the specified time and normalized sets of samples of the metrics of interest after the specified time;

computing, for each network, a centroid of the samples before the specified time and a centroid of the samples after the specified time;

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 samples of the metrics of interest before the specified time and a head of the vector is located at the centroid of the samples of the metrics of interest after the specified time.

3. The method of claim 2 wherein normalizing all metric values across samples and networks comprises normalizing metric values such that the smallest value of a metric of interest across samples and networks is 0 and the largest value of a metric of interest across samples and networks is 1.

4. The method of claim 2 wherein computing dimensionality-reducing transformations of metric data comprises computing dimensionality-reducing transformations of metric data that preserve variance in the metric data.

5. The method of claim 4, wherein computing dimensionality-reducing transformations of metric data comprises computing dimensionality-reducing transformations of metric data that preserve the most variance in the metric data.

6. The method of claim 2 wherein computing dimensionality-reducing transformations of metric data comprises principal component analysis (PCA).

7. 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 one or more 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 metrics of interest across all time intervals to determine a minimum value and a maximum value of metrics of interest across the networks and across samples;

normalizing all metric values across samples and networks;

determining a linear combination of metrics of interest that provides the most variance in the data and computes a M×

M covariance matrix for the metrics of interest;

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.

8. The method of claim 1, wherein the network anomaly ranking algorithm, after accepting a specified time and a selection of one or more metrics of interest, performs the steps of:

1) performing the selected ranking algorithm to identify the most anomalous network in a dataset in relation to the specified time, 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.

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

10. The method of claim 1, wherein the anomaly trend graphs algorithm, after accepting times of one or more 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.

11. 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.

12. The method of claim 1 wherein the network transaction data comprises communications data.

13. The method of claim 1 wherein the network transaction activity comprises communications activity.

14. The method of claim 1 wherein the one or more metrics of interest comprise one or more social network analysis (SNA) metrics.

15. The method of claim 1 wherein the specified time comprises the date of a key event.

16. The method of claim 1 further comprising identifying a network having anomalous transaction activity.

17. The method of claim 16 wherein identifying a network having anomalous transaction activity comprises displaying graphic output of the AT-SIG algorithm for each of the plurality of networks for visual comparison.

18. The method of claim 16 wherein identifying a network having anomalous transaction activity comprises visual comparison of the graphic output of the AT-SIG algorithm for each of the plurality of networks.

19. An asymmetric threat signature (AT-SIG) system comprising:

one or more processing units;

a display device;

non-transitory memory media, the memory media comprising a dataset comprising network transaction data of a plurality of networks; and

instructions which when loaded into the memory media and executed by the one or more processing units perform an AT-SIG algorithm on the dataset and 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 network transaction activity from before to after a specified time, wherein the network movement before/after algorithm, after accepting the specified time, accepting a selection of one or more 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 transactions 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 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 the metrics of interest; and

3) repeating steps

     1) to

     2) multiple times to generate multiple samples for the metrics of interest for each network,

wherein the network movement before/after algorithm generates a set of metric samples for each network before the specified time and a set of metric samples for each network after the specified time;

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

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

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

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

20. A software program product, comprising:

non-transitory computer readable memory media;

program instructions on the computer readable memory media that when executed provide the functions of an AT-SIG algorithm on a dataset comprising network transaction data,

wherein the AT-SIG algorithm comprises;

a network movement before/after algorithm that provides a graphical plot of changes in network transaction activity from before to after a specified time, wherein the network movement before/after algorithm, after accepting the specified time, accepting a selection of one or more 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 transactions 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 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 the metrics of interest; and

3) repeating steps

     1) to

     2) multiple times to generate multiple samples for the metrics of interest for each network,

wherein the network movement before/after algorithm generates a set of samples of metrics of interest for each network before the specified time and a set of samples of interest for each network after the specified time; and

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

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

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

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