Intelligent intrusion detection system utilizing enhanced graph-matching of network activity with context data
First Claim
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;
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;
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 Assignments
0 Petitions
Accused Products
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.
113 Citations
26 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; 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; 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. 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; 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; 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.
-
-
13. 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; 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; 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. - View Dependent Claims (14)
-
-
15. 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; 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; 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. - View Dependent Claims (16, 17, 18, 21)
-
-
19. The 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; 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; 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.
-
-
20. 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; 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; 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.
-
-
22. 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; 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; generating a pattern library comprising threat patterns representing known activities of interest and newly discovered threat patterns that represent potential threats to the network; 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; and
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. - View Dependent Claims (23, 24)
-
-
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; 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; 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.
-
-
26. 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; 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; 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.
-
Specification