SNA-BASED ANOMALY DETECTION

• US 20080109730A1
• Filed: 11/08/2006
• Published: 05/08/2008
• Est. Priority Date: 11/08/2006
• Status: Active Grant

• Current Assignee: Northrop Grumman Systems Corporation (Northrop Grumman Corporation)
• Original Assignee: 21st Century Technologies, Inc.
• Inventors: Coffman, Thayne Richard, Thomason, Braxton Eastham
• Granted Patent: US 7,739,211 B2
• Time in Patent Office: Days
• US Class Current: 715/733
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection
• CPC Class Codes: H04L 63/145 the attack involving the propagation of malware through the network, e.g. viruses, trojans or worms

Abstract

A method, system, and computer program product for enabling dynamic detection of anomalies occurring within an input graph representing a social network. More specifically, the invention provides an automated computer simulation technique that implements the combination of Social Network Analysis (SNA) and statistical pattern classification for detecting abnormal social patterns or events through the expanded use of SNA Metrics. The simulation technique further updates the result sets generated, based on observed occurrences, to dynamically determine what constitutes abnormal behavior, within the overall context of observed patterns of behavior.

Claims

1. A method comprising:

receiving a data set of social network interactions and communications data of multiple participants;

configuring metrics and tolerances, wherein the tolerances enable dynamic learning of what is within a range of normal over a period of time;

converting the data set to a graphical representation containing a node for each participant among the multiple participants;

computing social network analysis (SNA) metrics values for each node within the graphical representation;

determining, via use of a plurality of SNA metrics, when the metric value computed for a particular data point within the data set falls outside of a dynamically determined normal range bounded by the tolerances, wherein said determining automatically identifies abnormal events in a provided communication pattern, without requiring an input of a priori models for normal or abnormal behavior, wherein complex aspects of communication patterns identified within the data set are converted into a variety of simple numerical measures and wherein graphical structures are converted into numerical values utilizing SNA metrics; and

tagging the particular data point whose behavior falls outside the dynamically determined normal range as an anomaly.

2. The method of claim 1, wherein said receiving a dataset comprises:

receiving a social network graph as a data input, said social network graph being generated utilizing computer based graph representation of communication patterns within a computer network; and

when the data input is a social network graph, automatically identifying said anomaly as a potential intruder, wherein SNA anomaly identification provides enhanced intrusion detection within an graph-based intrusion detection scheme.

3. The method of claim 1, further comprising:

accessing a plurality of provided metrics and tolerances to complete the computing of the metric values and the determining step. computing a plurality of SNA metrics to be utilized, wherein said SNA metrics are measured on a plurality of people and groups, and wherein individuals and groups whose metrics are atypical in comparison with others are considered anomalous; and

wherein said determining step comprises completing a statistical pattern classification 8 for detecting abnormal social patterns or events through the use of SNA Metrics.

4. The method of claim 1, further comprising:

generating model groupings of data points having normal values from the received data set;

determining whether a threshold baseline for a minimum number of metrics for anomaly evaluation is established;

when the threshold baseline has not been established, storing the computed metrics;

determining whether a pre-set minimum number of SNA metrics have been stored to meet the baseline minimum number of metrics for anomaly evaluation; and

converting the next data block into a graph when the baseline minimum has not been met.

5. The method of claim 4, further comprising:

when the baseline minimum is established, initiating a comparison to normal function, wherein the values are compared to the normal values. comparing each data point to said normal values to complete a comparison with a defined normal;

determining if the value is a normal value;

when the value is a normal value, updating a set of normal values to include the present value; and

when the value is not a normal value, flagging the value as an anomaly.

6. The method of claim 1, wherein said determining is completed via an SNA_AD utility comprising:

(a) code for determining an anomaly from a given input of social interactions and a set of metrics;

(b) code for generating and displaying an SNA_AD console and enabling user setup, interaction and/or manipulation of processing completed by the determining code; and

(c) code for generating and displaying the output of the anomaly detection processes in user-understandable format;

wherein said code for determining comprises code for differentiating between normal and abnormal activity within the input graph.

7. The method of claim 6, wherein:

the SNA metrics are utilized within said determining code to complete anomaly detection functions, which functions include analyzing structure, behavior, and communication patterns and isolating indicators of unusual or abnormal activity;

said SNA metrics comprise one or more of;

(1) Average cycle length;

(2) Average path length;

(3) Betweenness centrality;

(4) Characteristic path length;

(5) Circumference;

(5) Cliquishness;

(6) Closeness centrality;

(7) Closeness centrality (sum of inverse distances);

(8) Clustering coefficient;

(9) Density;

(10) Diameter;

(11) External to internal ratio;

(12) Girth;

(13) Global efficiency;

(14) Homogeneity (15) Incoming degree;

(16) Local efficiency;

(17) Number of nodes;

(187) Outgoing degree;

(19) Radiality;

(20) Radius; and

(21) Undirected degree; and

each SNA metric transforms a different aspect of the communication structure into a number, whereby an abstract concept is converted into one or more specific numbers.

8. The method of claim 1, further comprising:

dynamically implementing an unsupervised learning method, wherein observed feature values are referenced against each other rather than against an a priori model of normal, such that each event is classified relative to other unknown events, without any prior classification system, whereby the unsupervised learning method evaluates a large sample of received data and deterministically evaluates which data is normal and which other data is not normal from among all sampled data utilizing SNA metrics and tolerances provided;

wherein further said unsupervised learning is completed based solely on a comparison of at least one of (a) the objects characteristics relative to the characteristics of other data within the groups and (b) the objects observed behavior relative to the object'"'"'s own past behavior.

9. The method of claim 6, wherein said determining code comprises code for:

providing a semi-supervised alerting method, wherein potential detections of anomalies are alerted via the unsupervised anomaly detection algorithms and provided as output to an analyst to selectively determine whether the detection is a true or a false positive.

10. The method of claim 1, wherein said determining code comprises:

code for implementing static SNA, wherein said determining code completes a detection of an anomaly via analysis of a single snapshot of activity to determine which participant node is behaving differently than a set of peers; and

code for implementing dynamic SNA, wherein said determining code completes the detection of the anomaly via analysis over a series of snapshots of activity over a time period, such that said analysis compares and models behaviors and behavioral changes over time to approximate a continual time-varying stream of monitored activity, wherein said dynamic SNA enables detection of current anomaly in behavior relative to a prior different behavior previously identified, and wherein each of a sequence of snapshots of the behavior is examined for a change that falls outside of a threshold difference relative to other behavior, relative to a user-defined and dynamically adjusting anomaly threshold range.

11. The method of claim 1, further comprising:

incorporating knowledge about the user or system'"'"'s overall communication characteristics as values determined via SNA metrics applied to determine threat patterns, utilizing SNA metrics in threat signatures, including, individual, coordinated, insider, and insider-outsider threats; and

analyzing SNA metrics combined with knowledge of a communication'"'"'s broader context to provide a substantially more powerful result set, wherein said associated context is built from one or more of a social, task, and command and control structures of the actors involved, and from the time history of the SNA metrics for a set period of time.

12. A computer program product comprising:

a computer readable medium; and

program code on the computer readable medium that when executed by a processor provides the functions of;

receiving a data set of social network interactions and communications data of multiple participants;

configuring metrics and tolerances, wherein the tolerances enable dynamic learning of what is within a range of normal over a period of time;

converting the data set to a graphical representation containing a node for each participant among the multiple participants;

computing SNA metrics values for each node within the graphical representation;

determining, via use of a plurality of SNA metrics, when the metric value computed for a particular data point within the data set falls outside of a dynamically determined normal range bounded by the tolerances, wherein said determining automatically identifies abnormal events in a provided communication pattern, without requiring an input of a priori models for normal or abnormal behavior, wherein complex aspects of communication patterns identified within the data set are converted into a variety of simple numerical measures and wherein graphical structures are converted into numerical values utilizing SNA metrics; and

tagging the particular data point whose behavior falls outside the dynamically determined normal range as an anomaly.

13. The computer program product of claim 12, wherein said program code for receiving a dataset comprises code for:

receiving a social network graph as a data input, said social network graph being generated utilizing computer based graph representation of communication patterns within a computer network; and

when the data input is a social network graph, automatically identifying said anomaly as a potential intruder, wherein SNA anomaly identification provides enhanced intrusion detection within an graph-based intrusion detection scheme.

14. The computer program product of claim 12, further comprising program code for:

accessing a plurality of provided metrics and tolerances to complete the computing of the metric values and the determining step.

computing a plurality of SNA metrics to be utilized, wherein said SNA metrics are measured on a plurality of people and groups, and wherein individuals and groups whose metrics are atypical in comparison with others are considered anomalous; and

completing a statistical pattern classification for detecting abnormal social patterns or events through the use of SNA Metrics.

15. The computer program product of claim 12, further comprising program code for:

generating model groupings of data points having normal values from the received data set;

determining whether a threshold baseline for a minimum number of metrics for anomaly evaluation is established;

when the threshold baseline has not been established, storing the computed metrics;

determining whether a pre-set minimum number of SNA metrics have been stored to meet the baseline minimum number of metrics for anomaly evaluation; and

converting the next data block into a graph when the baseline minimum has not been met.

16. The computer program product of claim 15, further comprising program code for:

when the baseline minimum is established, initiating a comparison to normal function, wherein the values are compared to the normal values. comparing each data point to said normal values to complete a comparison with a defined normal;

determining if the value is a normal value;

when the value is a normal value, updating a set of normal values to include the present value; and

when the value is not a normal value, flagging the value as an anomaly.

17. The computer program product of claim 12, wherein said program code for said determining comprises program code for implementing an SNA_AD utility comprising:

(a) code for determining an anomaly from a given input of social interactions and a set of metrics;

(b) code for generating and displaying an SNA_AD console and enabling user setup, interaction and/or manipulation of processing completed by the determining code; and

(c) code for generating and displaying the output of the anomaly detection processes in user-understandable format;

wherein said SNA-AD utility comprises a plurality of coded functions, including;

a configure function, a process input function, an establish normal function, a detect anomalies function, and an analyze anomaly function;

wherein said code for enabling said detect anomalies function further comprises code for enabling a compute metrics function and a compare to normal values function, wherein compute metrics function generates new metric values, which are inputted to compare to clusters function; and

wherein said code for said compare to normal values function compares the new metric values to established normal values and determines how far away from normal each new metric value is, wherein further, when a point in the input is outside of the established anomaly tolerances when compared to the normal clusters, the compare to normal values function issues an output of detected anomaly and the particular point is flagged as an anomaly;

wherein said code for determining comprises code for differentiating between normal and abnormal activity within the input graph, said code including code for;

computing a betweenness centrality of a specific node in a sociogram to generate a value that measures how often communications in the organization flows through a given person; and

computing a density and global efficiency metrics to measure how much redundancy exists in a communication structure;

wherein the SNA metrics are utilized within said determining code to complete anomaly detection functions, which functions include analyzing structure, behavior, and communication patterns and isolating indicators of unusual or abnormal activity;

wherein said SNA metrics comprise one or more of;

(1) Average cycle length;

(2) Average path length;

(3) Betweenness centrality;

(4) Characteristic path length;

(5) Circumference;

(5) Cliquishness;

(6) Closeness centrality;

(7) Closeness centrality (sum of inverse distances);

(8) Clustering coefficient;

(9) Density;

(10) Diameter;

(11) External to internal ratio;

(12) Girth;

(13) Global efficiency;

(14) Homogeneity (15) Incoming degree;

(16) Local efficiency;

(17) Number of nodes;

(187) Outgoing degree;

(19) Radiality;

(20) Radius; and

(21) Undirected degree; and

each SNA metric transforms a different aspect of the communication structure into a number, whereby an abstract concept is converted into one or more specific numbers.

18. The computer program product of claim 12, wherein said program code further comprises code for:

dynamically implementing an unsupervised learning method, wherein observed feature values are referenced against each other rather than against an a priori model of normal, such that each event is classified relative to other unknown events, without any prior classification system, whereby the unsupervised learning method evaluates a large sample of received data and deterministically evaluates which data is normal and which other data is not normal from among all sampled data utilizing SNA metrics and tolerances provided;

wherein further said unsupervised learning is completed based solely on a comparison of at least one of (a) the objects characteristics relative to the characteristics of other data within the groups and (b) the objects observed behavior relative to the object'"'"'s own past behavior.

19. The computer program product of claim 17, wherein said determining code comprises code for:

providing a semi-supervised alerting method, wherein potential detections of anomalies are alerted via the unsupervised anomaly detection algorithms and provided as output to an analyst to selectively determine whether the detection is a true or a false positive.

20. The computer program product of claim 12, wherein said determining code comprises code for:

code for implementing static SNA wherein said determining code completes a detection of an anomaly via analysis of a single snapshot of activity to determine which participant node is behaving differently than a set of peers; and

code for implementing dynamic SNA, wherein said determining code completes the detection of the anomaly via analysis over a series of snapshots of activity over a time period, such that said analysis compares and models behaviors and behavioral changes over time to approximate a continual time-varying stream of monitored activity, wherein said dynamic SNA enables detection of current anomaly in behavior relative to a prior different behavior previously identified, and wherein each of a sequence of snapshots of the behavior is examined for a change that falls outside of a threshold difference relative to other behavior, relative to a user-defined and dynamically adjusting anomaly threshold range.

21. The computer program product of claim 12, further comprising program code for:

incorporating knowledge about the user or system'"'"'s overall communication characteristics as values determined via SNA metrics applied to determine threat patterns, utilizing SNA metrics in threat signatures, including, individual, coordinated, insider, and insider-outsider threats; and

analyzing SNA metrics combined with knowledge of a communication broader context to provide a substantially more powerful result set, wherein said associated context is built from one or more of a social, task, and command and control structures of the actors involved, and from the time history of the SNA metrics for a set period of time.

22. The computer program product of claim 12, further comprising program code for:

performing communication pattern analysis utilizing the SNA metrics, wherein the determining code measures an amount of information flowing between actors in counts of communications, emails, or network packets;

wherein communications patterns are analyzed with respect to related network structures to identify flows that are not well explained by the related networks, and wherein time histories of flows are utilized to build statistical representations of historical normal communications patterns, which are then utilized to identify communications flows that signify a change from the historical normal communications patterns; and

completing the anomaly detection with analyst inputs to enable a determination of whether deviations from historical normal communication patterns have an acceptable explanation or whether the deviations are the result of an infected or compromised machine or a malicious insider activity.

23. A computing device comprising:

a processor;

a memory coupled to the processor;

at least one input/output (I/O) component for receiving social network data and user inputs; and

an SNA_AD (social network analysis_anomaly detection) utility comprising program code executing on the processor that performs the functions of;

receiving a data set of social network interactions and communications data of multiple participants;

configuring metrics and tolerances, wherein the tolerances enable dynamic learning of what is within a range of normal over a period of time;

converting the data set to a graphical representation containing a node for each participant among the multiple participants;

computing metrics values for each node within the graphical representation;

determining, via use of a plurality of SNA metrics, when the metric value computed for a particular data point within the data set falls outside of a dynamically determined normal range bounded by the tolerances, wherein said determining automatically identifies abnormal events in a provided communication pattern, without requiring an input of a priori models for normal or abnormal behavior, wherein complex aspects of communication patterns identified within the data set are converted into a variety of simple numerical measures and wherein graphical structures are converted into numerical values utilizing SNA metrics; and

tagging the particular data whose behaviour falls outside the normal range as an anomaly.

24. The computing device of claim 23, wherein said program code for receiving a dataset comprises code for:

receiving a social network graph as a data input, said social network graph being generated utilizing computer based graph representation of communication patterns within a computer network; and

when the data input is a social network graph, automatically identifying said anomaly as a potential intruder, wherein SNA anomaly identification provides enhanced intrusion detection within an graph-based intrusion detection scheme.

25. The computing device of claim 23, said SNA_AD utility further comprising program code for:

accessing a plurality of provided metrics and tolerances to complete the computing of the metric values and the determining step. computing a plurality of SNA metrics to be utilized, wherein said SNA metrics are measured on a plurality of people and groups, and wherein individuals and groups whose metrics are atypical in comparison with others are considered anomalous; and

completing a statistical pattern classification for detecting abnormal social patterns or events through the use of SNA Metrics.

26. The computing device of claim 23, said SNA_AD utility further comprising program code for:

grouping data points from the received data set to generate model groupings having normal values;

determining whether a threshold baseline for a minimum number of metrics for anomaly evaluation is established;

when the threshold baseline has not been established, storing the computed metrics;

determining whether a pre-set minimum number of SNA metrics have been stored to meet the baseline minimum number of metrics for anomaly evaluation; and

converting the next data block into a graph when the baseline minimum has not been met.

27. The computing device of claim 26, said SNA_AD utility further comprising program code for:

when the baseline minimum is established, initiating a comparison to normal function, wherein the values are compared to the normal values.

comparing each data point to said normal values to complete a comparison with a defined normal;

determining if the value is a normal value;

when the value is a normal value, updating a set of normal values to include the present value; and

when the value is not a normal value, flagging the value as an anomaly.

28. The computing device of claim 23, wherein said program code for said SNA_AD utility further comprises:

(a) code for determining an anomaly from a given input of social interactions and a set of metrics;

(b) code for generating and displaying an SNA_AD console and enabling user setup, interaction and/or manipulation of processing completed by the determining code; and

(c) code for generating and displaying the output of the anomaly detection processes in user-understandable format;

wherein said SNA-AD utility comprises a plurality of coded functions, including;

a configure function, a process input function, an establish normal function, a detect anomalies function, and an analyze anomaly function;

wherein said code for enabling said detect anomalies function further comprises code for enabling a compute metrics function and a compare to groupings function, wherein compute metrics function generates new metric values, which are inputted to compare to clusters function; and

wherein said code for said compare to groupings function compares the new metric values to established normal groupings and determines how far away from normal each new metric value is, wherein further, when a point in the input is outside of the established anomaly tolerances when compared to the normal values, the compare to groupings function issues an output of detected anomaly and the particular point is flagged as an anomaly;

wherein said code for determining comprises code for differentiating between normal and abnormal activity within the input graph, said code for differentiating including code for;

computing a betweenness centrality of a specific node in a sociogram to generate a value that measures how often communications in the organization flows through a given person; and

computing a density and global efficiency metrics to measure how much redundancy exists in a communication structure;

wherein the SNA metrics are utilized within said determining code to complete anomaly detection functions, which functions include analyzing structure, behavior, and communication patterns and isolating indicators of unusual or abnormal activity;

wherein said SNA metrics comprise one or more of;

(1) Average cycle length;

(2) Average path length;

(3) Betweenness centrality;

(4) Characteristic path length;

(5) Circumference;

(5) Cliquishness;

(6) Closeness centrality;

(7) Closeness centrality (sum of inverse distances);

(8) Clustering coefficient;

(9) Density;

(10) Diameter;

(11) External to internal ratio;

(12) Girth;

(13) Global efficiency;

(14) Homogeneity (15) Incoming degree;

(16) Local efficiency;

(17) Number of nodes;

(187) Outgoing degree;

(19) Radiality;

(20) Radius; and

(21) Undirected degree; and

each SNA metric transforms a different aspect of the communication structure into a number, whereby an abstract concept is converted into one or more specific numbers.

29. The computing device of claim 23, wherein said SNA_AD utility further comprises code for:

dynamically implementing an unsupervised learning method, wherein observed feature values are referenced against each other rather than against an a priori model of normal, such that each event is classified relative to other unknown events, without any prior classification system, whereby the unsupervised learning method evaluates a large sample of received data and deterministically evaluates which data is normal and which other data is not normal from among all sampled data utilizing SNA metrics and tolerances provided;

wherein further said unsupervised learning is completed based solely on a comparison of at least one of (a) the objects characteristics relative to the characteristics of other data within the groups and (b) the objects observed behavior relative to the object'"'"'s own past behavior.

30. The computing device of claim 29, wherein said determining code comprises code for:

providing a semi-supervised alerting method, wherein potential detections of anomalies are alerted via the unsupervised anomaly detection algorithms and provided as output to an analyst to selectively determine whether the detection is a true or a false positive;

implementing static SNA wherein said determining code completes a detection of an anomaly via analysis of a single snapshot of activity to determine which participant node is behaving differently than a set of peers; and

implementing dynamic SNA, wherein said determining code completes the detection of the anomaly via analysis over a series of snapshots of activity over a time period, such that said analysis compares and models behaviors and behavioral changes over time to approximate a continual time-varying stream of monitored activity, wherein said dynamic SNA enables detection of current anomaly in behavior relative to a prior different behavior previously identified, and wherein each of a sequence of snapshots of the behavior is examined for a change that falls outside of a threshold difference relative to other behavior, relative to a user-defined and dynamically adjusting anomaly threshold range.

31. The computing device of claim 23, said SNA_AD utility further comprising program code for:

incorporating knowledge about the user or system'"'"'s overall communication characteristics as values determined via SNA metrics applied to determine threat patterns, utilizing SNA metrics in threat signatures, including, individual, coordinated, insider, and insider-outsider threats; and

analyzing SNA metrics combined with knowledge of a communication broader context to provide a substantially more powerful result set, wherein said associated context is built from one or more of a social, task, and command and control structures of the actors involved, and from the time history of the SNA metrics for a set period of time.

32. The computing device of claim 23, said SNA_AD utility further comprising program code for:

performing communication pattern analysis utilizing the SNA metrics, wherein the determining code measures an amount of information flowing between actors in counts of communications, emails, or network packets;

wherein communications patterns are analyzed with respect to related network structures to identify patterns that are not well explained by the related networks, and wherein time histories of flows are utilized to build statistical representations of historical normal communications patterns, which are then utilized to identify communications flows that signify a change from the historical normal communications patterns; and

completing the anomaly detection with analyst inputs to enable a determination of whether deviations from historical normal communication patterns have an acceptable explanation or whether the deviations are the result of an infected or compromised machine or a malicious insider activity.