Intelligent intrusion detection system utilizing enhanced graph-matching of network activity with context data

• US 20070209074A1
• Filed: 03/04/2006
• Published: 09/06/2007
• Est. Priority Date: 03/04/2006
• Status: Active Grant

• Current Assignee: Northrop Grumman Systems Corporation (Northrop Grumman Corporation)
• Original Assignee: 21st Century Technologies, Inc.
• Inventors: Coffman, Thayne
• Granted Patent: US 7,624,448 B2
• Time in Patent Office: Days
• US Class Current: 726/23
• CPC Class Codes: G06F 21/552 involving long-term monitoring or reporting
• 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 utilizing a mapping of activity occurring at and between devices on a computer network to detect and prevent network intrusions. An enhanced graph matching intrusion detection system (eGMIDS) is provided that provides data collection functions, data fusion techniques, graph matching algorithms, and secondary and other search mechanisms. Threats are modeled as a set of entities and interrelations between the entities and sample threat patterns are stored within a database. The eGMIDS utility initiates a graph matching algorithm by which the threat patterns are compared within the generated activity graph via subgraph isomorphism. A multi-layered approach including a targeted secondary layer search following a match during a primary layer search is provided. Searches are tempered by attributes and constraints and the eGMIDS reduces the number of threat patterns searched by utilizing ontological generalization.

Claims

1. In a network computer environment comprising an intrusion detection system (IDS) server communicatively connected to one or more host devices, a method comprising:

receiving from at least one of the one or more host devices activity data corresponding to the specific host device and operations and activity occurring on the host device and among two or more host devices;

converting the received activity data into a specialized format, which supports data fusion;

generating a graphical representation of the activity within and communication amongst the one or more host devices and the IDS server, said graphical representation being an activity graph comprising a series of interconnected nodes and edges each representing one or more of the host devices and the activities occurring at the host device and communications between host devices;

comparing one or more pre-determined threat patterns against said activity graph, wherein said threat patterns represent activities of interest; and

providing an alert when at least one of the one or more pre-determined threat patterns matches up to connected nodes and edges within the activity graph.

2. The method of claim 1, further comprising:

generating a pattern library comprising threat patterns representing known activities of interest and newly discovered threat patterns that represent potential threats to the network; and

dynamically performing subgraph isomorphism utilizing one or more of the threat patterns within the activity graph to identify suspicious activity within the activity graph, wherein distributed and coordinated attacks perpetrated by attackers are detected.

3. The method of claim 1, further comprising providing an activity archive comprising a list of alerts.

4. The method of claim 1, wherein:

said receiving comprises receiving the activity data in 21Messaging (21m) format;

said converting comprises;

un-packaging the activity data from its received format; and

translating the received activity data into a format that is usable by a graphical engine that generates the activity graph; and

said generating comprises fusing the translated activity data into the activity graph.

5. The method of claim 2, wherein said analyzing comprises:

enabling user selection of a search method from among multiple available search methods including an exhaustive search method and a non-exhaustive search method, wherein a particular search method is selected based on the size of the threat pattern.

7. The method of claim 1, wherein said comparing further comprises:

enabling an analyst to define constraints on a threat pattern that filters out matches that have similar configuration as a potential threat but are not considered harmful; and

receiving one or more constraints and parsing, compiling and integrating said constraints into the runtime environment of the IDS server.

8. The method of claim 1, wherein said comparing further comprises:

providing an ontological generalization hierarchy wherein similar events are generalized and grouped into a single ontological category, wherein the single ontological category is utilized within the search engine to discover any one of multiple attacks that are covered by the ontological generalization;

wherein further the ontological generalization hierarchy supports multiple parents per child event, such at one or more single event is a member of multiple ontological categories; and

wherein said ontological generalization hierarchy comprises multiple layers such that one or more category is a generalization of multiple other categories and multiple specific events.

9. The method of claim 1, wherein said comparing further comprises:

establishing a reduced candidate set, whereby only nodes reachable from a potential matching node within a number of steps less than or equal to the pre-established maximum distance between any two nodes in the threat pattern are considered for a match.

10. The method of claim 1, wherein said comparing further comprises:

enabling inexact matching wherein variations in a sample threat pattern are identified within the activity graph and outputted for analysis;

assigning a score to each node and edges within a pattern, said score based on one of the presence or absence of the node and edge along with the associated attribute values and constraints;

tracking a score as a threat pattern is compared within the activity graph, said score providing an indication of a level of similarity between the pattern and the found components within the activity graph;

comparing the score to a preset threshold value, said threshold value being selected by an analyst to represent a possible mutation of a known threat; and

when the score passes the threshold value, automatically forwarding the found “

match”

to the analyst for review.

11. The method of claim 1, wherein said analyzing further comprises:

analyzing a fused activity graph for primary evidence of a potential threat;

generating a request for secondary evidence from sensor(s) at specific target device(s) and forwarding the request to the device(s) sensor(s);

on receipt of the secondary evidence from the targeted device(s), fusing said secondary evidence into the fused activity graph;

performing detailed pattern matching on merged data portions within the augmented activity graph, directed at the merged data portion of the fused activity graph, wherein said patterns comprise primary patterns, secondary request templates and secondary patterns; and

when the second pattern matching results in a match, triggering an alert via an output mechanism.

12. The method of claim 11, wherein said comparing further comprises:

recording the activity as a threat and generating an intrusion detection alert; and

storing the matches to the threat patterns from the first and secondary evidence comparison within the pattern library.

13. The method of claim 1, wherein said signaling comprises forwarding an alert to an output mechanism to inform a system analyst of the detected pattern and the threat associated with the detected pattern.

14. The method of claim 1, further comprising:

forwarding the activity data received to an activity archive; and

maintaining a plurality of components within the activity archive, including a list of old activity graphs, a list of alerts and graphs represented by the respective alerts, and history of IDS control server performance metrics.

15. The method of claim 1, wherein a search is further defined by a constraint that utilizes attributes of one or more nodes and/or edges to refine the search criteria and improve detection of real threats, while decreasing false alarms, wherein said constraints comprise timing constraints, IP address masking, counts, and restrictions on protocols and wherein a constraint is built to restrict single attribute values or relationships between multiple attribute values.

6. The method of claim 6, wherein said first exhaustive search method comprises:

matching nodes in the pattern graph to nodes in the activity graph when the connections between the nodes within the activity graph matches the connections between the nodes of the pattern graph;

determining whether a match is found to the threat pattern within the activity graph; and

when a match is fund, generating and outputting an alert indicating the match was found within the activity graph.

17. A data processing system (DPS) comprising:

a processor and memory connected via a system bus;

a network interface device by which the data processing system connects to an external network and communicates with external network devices;

an intrusion detection system (IDS) utility comprising instruction code that when executed by the processor provides the functions of;

receiving from at least one of the one or more host devices activity data corresponding to the specific host device and operations and activity occurring on the host device and among two or more host devices;

converting the received activity data into a specialized format, which supports data fusion;

generating a graphical representation of the activity within and communication amongst the one or more host devices and the IDS server, said graphical representation being an activity graph comprising a series of interconnected nodes and edges each representing one or more of the host devices and the activities occurring at the host device and communications between host devices;

comparing one or more pre-determined threat patterns against said activity graph, wherein said threat patterns represent activities of interest; and

providing an alert when at least one of the one or more pre-determined threat patterns matches up to connected nodes and edges within the activity graph.

18. The DPS of claim 17, wherein the IDS utility further comprises code for:

generating a pattern library comprising threat patterns representing known activities of interest and newly discovered threat patterns that represent potential threats to the network;

providing an activity archive comprising a list of alerts; and

dynamically performing subgraph isomorphism utilizing one or more of the threat patterns within the activity graph to identify suspicious activity within the activity graph, wherein distributed and coordinated attacks perpetrated by attackers are detected.

19. The DPS of claim 17, wherein the IDS utility further comprises code wherein:

said receiving comprises receiving the activity data in 21Messaging (21m) format;

said converting comprises un-packaging the activity data from its received format;

translating the received activity data into a format that is usable by a graphical engine that generates the activity graph; and

said generating comprises fusing the translated activity data into the activity graph.

20. The DPS of claim 17, wherein said comparing code further comprises code for:

enabling user selection of a search method from among multiple available search methods including an exhaustive search method and a non-exhaustive search method, wherein a particular search method is selected based on the size of the threat pattern

21. The DPS of claim 17, wherein said comparing code further comprises code for:

enabling an analyst to define constraints on a threat pattern that filters out matches that have similar configuration as a potential threat but are not considered harmful; and

receiving one or more constraints and parsing, compiling and integrating said constraints into the runtime environment of the IDS server.

22. The DPS of claim 17, wherein said comparing code further comprises code for:

providing an ontological generalization hierarchy wherein similar events are generalized and grouped into a single ontological category, wherein the single ontological category is utilized within the search engine to discover any one of multiple attacks that are covered by the ontological generalization;

wherein further the ontological generalization hierarchy supports multiple parents per child event, such at one or more single event is a member of multiple ontological categories;

wherein said ontological generalization hierarchy comprises multiple layers such that one or more category is a generalization of multiple other categories and multiple specific events;

establishing a reduced candidate set, whereby only nodes reachable from a potential matching node within a number of steps less than or equal to the pre-established maximum distance between any two nodes in the threat pattern are considered for a match;

enabling inexact matching wherein variations in a sample threat pattern are identified within the activity graph and outputted for analysis;

assigning a score to each node and edges within a pattern, said score based on one of the presence or absence of the node and edge along with the associated attribute values and constraints;

tracking a score as a threat pattern is compared within the activity graph, said score providing an indication of a level of similarity between the pattern and the found components within the activity graph;

comparing the score to a preset threshold value, said threshold value being selected by an analyst to represent a possible mutation of a known threat; and

when the score passes the threshold value, automatically forwarding the found “

match”

to the analyst for review.

23. The DPS of claim 17, wherein said comparing code further comprises code for:

analyzing a fused activity graph for primary evidence of a potential threat;

generating a request for secondary evidence from sensor(s) at specific target device(s) and forwarding the request to the device(s) sensor(s);

on receipt of the secondary evidence from the targeted device(s), fusing said secondary evidence into the fused activity graph;

performing detailed pattern matching on merged data portions within the augmented activity graph, directed at the merged data portion of the fused activity graph, wherein said patterns comprise primary patterns, secondary request templates and secondary patterns;

when the second pattern matching results in a match, triggering an alert via an output mechanism; and

storing the matches to the threat patterns from the first and secondary evidence comparison within the pattern library.

24. The DPS of claim 17, wherein said IDS utility further comprises code for:

forwarding the activity data received to an activity archive; and

maintaining a plurality of components within the activity archive, including a list of old activity graphs, a list of alerts and graphs represented by the respective alerts, and history of IDS control server performance metrics.

25. A computer program product comprising:

a computer readable medium; and

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

receiving from at least one of the one or more host devices activity data corresponding to the specific host device and operations and activity occurring on the host device and among two or more host devices;

converting the received activity data into a specialized format, which supports data fusion;

generating a graphical representation of the activity within and communication amongst the one or more host devices and the IDS server, said graphical representation being an activity graph comprising a series of interconnected nodes and edges each representing one or more of the host devices and the activities occurring at the host device and communications between host devices;

comparing one or more pre-determined threat patterns against said activity graph, wherein said threat patterns represent activities of interest; and

providing an alert when at least one of the one or more pre-determined threat patterns matches up to connected nodes and edges within the activity graph.

26. The computer program product of claim 25, further comprising:

code for generating a pattern library comprising threat patterns representing known activities of interest and newly discovered threat patterns that represent potential threats to the network; and

code wherein;

said receiving comprises receiving the activity data in 21Messaging (21m) format;

said converting comprises un-packaging the activity data from its received format; and

translating the received activity data into a format that is usable by a graphical engine that generates the activity graph;

said generating comprises fusing the translated activity data into the activity graph;

said comparing code comprises code;

for enabling user selection of a search method from among multiple available search methods including an exhaustive search method and a non-exhaustive search method, wherein a particular search method is selected based on the size of the threat pattern; and

dynamically performing subgraph isomorphism utilizing one or more of the threat patterns within the activity graph to identify suspicious activity within the activity graph, wherein distributed and coordinated attacks perpetrated by attackers are detected.

27. The computer program product of claim 25, wherein said code for performing said first exhaustive search method comprises code for:

matching nodes in the pattern graph to nodes in the activity graph when the connections between the nodes within the activity graph matches the connections between the nodes of the pattern graph;

determining whether a match is found to the threat pattern within the activity graph; and

when a match is fund, generating and outputting an alert indicating the match was found within the activity graph.

28. The computer program product of claim 25, wherein said comparing code further comprises code for:

enabling an analyst to define constraints on a threat pattern that filters out matches that have similar configuration as a potential threat but are not considered harmful; and

receiving one or more constraints and parsing, compiling and integrating said constraints into the runtime environment of the IDS server;

providing an ontological generalization hierarchy wherein similar events are generalized and grouped into a single ontological category, wherein the single ontological category is utilized within the search engine to discover any one of multiple attacks that are covered by the ontological generalization;

wherein further the ontological generalization hierarchy supports multiple parents per child event, such at one or more single event is a member of multiple ontological categories;

wherein said ontological generalization hierarchy comprises multiple layers such that one or more category is a generalization of multiple other categories and multiple specific events;

establishing a reduced candidate set, whereby only nodes reachable from a potential matching node within a number of steps less than or equal to the pre-established maximum distance between any two nodes in the threat pattern are considered for a match;

enabling inexact matching wherein variations in a sample threat pattern are identified within the activity graph and outputted for analysis;

assigning a score to each node and edges within a pattern, said score based on one of the presence or absence of the node and edge along with the associated attribute values and constraints;

tracking a score as a threat pattern is compared within the activity graph, said score providing an indication of a level of similarity between the pattern and the found components within the activity graph;

comparing the score to a preset threshold value, said threshold value being selected by an analyst to represent a possible mutation of a known threat; and

when the score passes the threshold value, automatically forwarding the found “

match”

to the analyst for review.

29. The computer program product of claim 25, wherein said comparing code further comprises code for:

analyzing a fused activity graph for primary evidence of a potential threat;

generating a request for secondary evidence from sensor(s) at specific target device(s) and forwarding the request to the device(s) sensor(s);

on receipt of the secondary evidence from the targeted device(s), fusing said secondary evidence into the fused activity graph; and

performing detailed pattern matching on merged data portions within the augmented activity graph, directed at the merged data portion of the fused activity graph, wherein said patterns comprise primary patterns, secondary request templates and secondary patterns;

when the second pattern matching results in a match, triggering an alert via an output mechanism; and

storing the matches to the threat patterns from the first and secondary evidence comparison within the pattern library.

30. The computer program product of claim 25, further comprising code for:

forwarding the activity data received to an activity archive; and

maintaining a plurality of components within the activity archive, including a list of old activity graphs, a list of alerts and graphs represented by the respective alerts, and history of IDS control server performance metrics.