Patent Publication Number: US-9413598-B2

Title: Graph structures for event matching

Description:
BACKGROUND 
     1. Field 
     The present disclosure generally relates to computer software, and more particularly to electronic security. 
     2. Description of the Related Art 
     The rapid development of electronic devices, the Internet, World Wide Web and E-commerce has made it increasingly important to be able to monitor the traffic going into and coming out of an electronic device. Monitoring such traffic, such as in a computer network, allows for the discovery of abnormal traffic that may be an indication of attacks from hackers or misuse of resources. 
     For computer networks, various network and computer security software, such as firewalls, Intrusion Detection Systems (IDS), network monitors, and vulnerability assessment tools, have been developed to protect a network or host computer from abuse and hacking. IDSs are used to spot, alert, and stop intrusions. Typically running on dedicated computers connected to the network, IDS systems actively monitor network traffic for suspicious activities. 
     IDS generally implement a signature-based approach in which attacks are detected by analyzing an incoming event (e.g., activity on the network or in the host) against every rule in a predefined set of rules (“rule set”) that generally describe the IDS-specific set of network features (e.g., destination port, payload content) or system events (e.g., privileged file access, login time) and deploying a response action in case the event matches the description set in a predefined rule. The size of rule sets continues to increase according to the increasing use of computer systems. Although the time it takes to determine if an incoming event matches a rule in the rule set (“event matching”) increases proportionately to the increase in size of the rule set, there remains a demand for near real-time event matching. 
     SUMMARY 
     There is a need for an event matching system that is capable of more quickly matching an incoming event against a detection rule in a set of detection rules without having to evaluate every rule in a rule set. According to certain embodiments of the present disclosure, the disclosed systems and methods provide for the efficient analysis of detection rules in a set of detection rules. Certain embodiments of the systems and methods include a rule management data structure and algorithms for event matching using the rule management data structure. The rule management data structure is, in certain embodiments, a rule relations graph that stores rules from a rule set as a partially ordered set. 
     In certain embodiments of the disclosure, a system for matching a system event to a rule is provided. The system includes a computer-readable data structure comprising a plurality of system event rules organizable as a partially ordered set. The system also includes a processor configured to analyze the computer-readable data structure to determine whether an event matches a description set of at least one rule from the plurality of system event rules. 
     In certain embodiments of the disclosure, a method for matching a system event to a rule is provided. The method includes generating a match set based an incoming system event, and identifying at least one node, in a rule relations graph, associated with a set of fields that is a subset of, or equal to, the set of fields associated with the match set. The method also includes processing, using a computer, at least one rule associated with the at least one node. 
     In certain embodiments of the disclosure, a system for matching a system event to a rule is provided. The system includes a computer-readable data structure comprising a plurality of detection rules organizable as a partially ordered set. The system also includes a processor configured to generate a match set based on the system event, and identify whether at least one rule, from a plurality of detection rules, is associated with a set of fields that is a subset of or equal to, a set of fields associated with the match set, and whether the values associated with the set of fields associated with the at least one rule match the values associated with the set of fields associated with the match set. The processor is further configured to initiate at least one response action associated with the at least one rule if the set of fields associated with the at least one rule is a subset of, or equal to, a set of fields associated with the match set, and if the values associated with the set of fields associated with the at least one rule match the value associated with the set of fields associated with the match set. 
     In certain embodiments of the disclosure, a machine-readable medium encoded with instructions for matching a system event to a rule is provided. The instructions include code for generating a match set based an incoming system event, and identifying at least one node, in a rule relations graph, associated with a set of fields that is a subset of, or equal to, the set of fields associated with the match set. The instructions also include code for processing at least one rule associated with the at least one node. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The accompanying drawings, which are included to provide further understanding and are incorporated in and constitute a part of this specification, illustrate disclosed embodiments and together with the description serve to explain the principles of the disclosed embodiments. In the drawings: 
         FIG. 1A  illustrates an exemplary rule table for network events according to one embodiment. 
         FIG. 1B  illustrates a directed graph representing the table of  FIG. 1A , according to certain embodiments of the disclosure. 
         FIG. 2A  is exemplary pseudo-code for inserting a rule into a rule relations graph. 
         FIG. 2B  is a flow chart illustrating an exemplary operation for inserting a rule into a rule relations graph based on the pseudo-code of  FIG. 2A . 
         FIG. 3A  is exemplary pseudo-code for removing a rule from a rule relations graph. 
         FIG. 3B  is a flow chart illustrating an exemplary operation for removing a rule from a rule relations graph based on the pseudo-code of  FIG. 3A . 
         FIG. 4A  is exemplary pseudo-code for traversing a rule relations graph to locate a rule matching an event. 
         FIG. 4B  is a flow chart illustrating an exemplary operation for traversing a rule relations graph to locate a rule matching an event based on the pseudo-code of  FIG. 4A . 
         FIG. 5  is a block diagram illustrating an example of a computer system with which the disclosed systems and methods can be implemented. 
         FIG. 6A  illustrates an exemplary rule table for any type of event according to one embodiment. 
         FIG. 6B  illustrates a directed graph representing the table of  FIG. 6A  according to certain embodiments of the disclosure. 
         FIG. 7A  illustrates an exemplary rule table for a home alarm monitoring system according to one embodiment. 
         FIG. 7B  illustrates a directed graph representing the table of  FIG. 7A  according to certain embodiments of the disclosure. 
         FIG. 8A  illustrates an exemplary rule table for a host security monitoring system according to one embodiment. 
         FIG. 8B  illustrates a directed graph representing the table of  FIG. 8A  according to certain embodiments of the disclosure. 
     
    
    
     DETAILED DESCRIPTION 
     There is a problem in intrusion detection systems of an increasingly unacceptable amount of time being necessary to match a system event to a rule in a rule set as the size of the rule set increases. This and other problems are solved, at least in part, by embodiments of the present disclosure, which include a system for matching a system event to a rule. The system includes a computer-readable data structure comprising a plurality of system event rules organizable as a partially ordered set. The system also includes a processor configured to analyze the computer-readable data structure to determine whether an event matches a description set of at least one rule from the plurality of system event rules. 
     In the following detailed description, numerous specific details are set forth to provide a full understanding of the present disclosure. It will be obvious, however, to one ordinarily skilled in the art that the embodiments of the present disclosure may be practiced without some of these specific details. In other instances, well-known structures and techniques have not been shown in detail so as not to obscure the disclosure. 
     As discussed herein, an event on a system (“system event”) is an occurrence of significance to a task of the system in a network or host environment. Exemplary events can include completion or failure of an operation on the network, a user action on the network, or the change in state of a process on the network. 
       FIG. 1A  illustrates an exemplary rule table  100  for network events according to one embodiment. The rule table  100  includes a plurality of rules, R 1  to R 4 , each rule associated with a set of fields, F 1  to F 4 , and each set associated with a set of values, V 1  to V 4 . The rule table  100  also includes weights  102  associated with each field. As discussed herein, in the context of intrusion detection, a rule can be defined as a set of conditions to be met, referred to as a conditional part of the rule, for an action to be triggered. The action defines measures to be taken if the conditional part of the rule is satisfied. In certain embodiments, a rule is associated with a description set that includes at least one field (e.g., a condition to be matched) including a value associated with the field, and at least one action to be taken if all of the fields are matched. Exemplary fields include, for example, a port number field, a payload size field, a network type field, an IP protocol field, a TCP flag field, and a file access field. 
     In certain embodiments, a rule can be formally defined as a tuple R i =(C i ,A i ), where C i  is a predicate defined on a set of conditions c 1 , c 2 , . . . , c n  and A i  is an action. A condition c C i  is defined as a (f, v) tuple, where f F i  is a field monitored by an IDS and v  V i  represents the numerical or descriptive value (or range of values) assigned to the corresponding field. F=∪F i  denotes the set of all fields represented in the rule collection. 
       FIG. 1B  illustrates a directed graph representing the table of  FIG. 1A , according to certain embodiments of the disclosure. 
     A rule relations graph as discussed herein is, in certain embodiments, a partially ordered set of rules. In certain embodiments, a rule relation graph RG={N, E, V} is a partially ordered set comprised of a set of distinct nodes N, a set of edges E, and a set of value sets V. A node n N is defined as {CF, S} tuple, where CF is the set of fields {f 1 , f 2 , . . . , f k }  F, S is the set of rules defined as S={R i , R i   RuleCollection, F i =CF}. An edge e E connects two nodes n 1  and n 2  such that n 1 (CF) n 2 (CF). Then, n 2  is called a child node of n 1 , Child(n 1 ), n 1  is denoted as a parent node of n 2 , Parent(n 2 ) and consequently, a set of all child nodes of n 1  is considered as Children(n 1 ), and a set of all parent nodes of n 2  is denoted as Parents(n 2 ). A value set V i   V corresponds to each of the nodes n i   N, where |CF|=1 and presents a set of all values v of a field f i   CF found in all R Rule Collection, where f i   F R . 
     In certain embodiments, a rule relations graph can be stored as a data structure. The data structure can be, for example, a lattice data structure. In certain embodiments, a rule relations graph can be represented as a directed graph  150 , e.g., where any two vertices (or “nodes”) are connected by one path (or “edge” or “link” or “connection”). For example, nodes  118  and  124  are connected by path  136 . A node in the graph can be used to represent a rule from the rule set (e.g., node  120  is associated with rule R 2   126 ), or at least one field associated with the rule set. In certain embodiments, the rule relations graph does not include all permutations of the fields from the rule set. The directed graph  150  is a rooted graph in that one node  102  is designated as the root node  102 . As discussed herein, in a directed graph  150 , the parent of a node is the node connected to it on the path to the root node  102 ; every node except the root node  102  has a parent. A child of a node v is a node of which v is the parent. A leaf node is a node without children. For example, node  112  is the parent of node  120 , and node  132 , a leaf node, is the child of node  120 . The child nodes of the root node of the directed graph  150  are also associated with value sets  104 ,  106 ,  108 , and  110 , illustrated in  FIG. 1B  in phantom. Each value set is associated with a field included in the rule relations graph, and, in certain embodiments, includes all values associated with that field in the rule relations graph. For example, value set  104  is associated with the field “dstPort” and the values “1434” and “81,” for the field “dstPort.” 
     The directed graph  150  is partially ordered in accordance with the rule relations graph it represents. Excluding the root node  102 , each node in the graph is a superset of each of its parents and equal to all its parents combined. For example, the set of fields “dstPort” and “protocol” associated with node  120  is a superset of field “dstPort” associated with parent node  112 . 
       FIG. 2A  is exemplary pseudo-code for inserting a rule into a rule relations graph.  FIG. 2B  is a flow chart illustrating an exemplary process  200  for inserting a rule into a directed graph  150  based on the pseudo-code of  FIG. 2A . 
     The process  200  proceeds from beginning step  201  to loop step  202 . The loop represented by steps  202  to  213  repeats for each field of the target rule (e.g., the new rule to be added). Beginning with the first field listed in the set of fields associated with the target rule, in step  202 , the process  200  proceeds to decision step  203  in which a determination is made as to whether the root node  102  has a child node with the current field of the target rule. If, in decision step  203 , the root node  102  has a child node with the current field of the target rule, then the process  200  proceeds to step  204  in which the value of the current field is added to the value set of the current node. If, in decision step  205 , the target rule only has the current field (e.g., it is only associated with one field, the current field), then the process  200  proceeds to decision step  206 . If, in decision step  206 , the any of the rules associated with the current node match the target rule, the process  200  proceeds to end step  231 . If, however, the target rule does not match any of the rules associated with the current node, as determined in decision step  206 , then the process  200  proceeds to step  207  in which the target rule is associated with the current node and then to step  213  and the loop restarts at beginning loop step  202 . 
     Returning to decision step  203 , if the root node  102  does not have a child node associated with the current field of the target rule, then the process  200  proceeds to step  208 , in which a new child node is created for the root node  102 , the child node being associated with the current field, and the “new node” value being set as true. The process  200  then proceeds to step  204  as discussed above. In decision step  205 , if the target rule is not only associated with the current field, then the process  200  proceeds to decision step  209  in which it is determined whether the “new node” value is set as true. If the new node value is not set as true, the process  200  proceeds to beginning loop step  214 . If, however, the new node value is set as true in decision step  209 , the value is reset to false, and the process  200  proceeds to decision step  210  in which it is determined whether the target rule has already been inserted in the graph. If the target rule is determined to already have been inserted in the graph, the process  200  proceeds to step  212 , in which the links between the current node and any parent or child nodes are updated. If, however, in decision step  210  it is determined that the target rule has not already been inserted in the graph, then the process  200  proceeds to step  211 , in which a child node of the current node is created. The process  200  then proceeds to step  207 , as discussed above. 
     Loop steps  214  to  220  repeat for each child node of the current child of the root node  102  of the directed graph  150 . In decision step  215 , a decision is made as to whether any of the rules associated with the current node match the target rule to be inserted into the graph. If any of the rules associated with the current node do match the target rule to be inserted into the graph, the process  200  proceeds to end loop step  213 . If, however, in decision step  215 , it is determined that none of the rules associated with the current node match the target rule to be inserted into the directed graph  150 , the process  200  proceeds to decision step  216 . In decision step  216 , if it is determined that the fields associated with the target rule are the same as the fields associated with the current node, then the process  200  proceeds to step  207  to associate the target node with the current node. If, however, in decision step  216 , it is determined that the fields associated with the target rule are not the same as the fields associated with the current node, then the process  200  proceeds to decision step  217 . In decision step  217 , if it is determined that the fields associated with the target rule are a subset of the fields associated with the current node, then the process  200  proceeds to step  221 . In step  221 , if the target rule is not already inserted, the target rule is inserted as a parent of the current node. The process  200  then proceeds to step  224  in which the links between any parent nodes of the current node and any child node of the current nodes are updated. The process  200  then moves from step  224  to end loop step  220 . 
     Returning to decision step  217 , if it is determined that the set of fields associated with the target rule is not a subset of the set of fields associated with the current node, the process  200  proceeds to decision step  218 . In decision step  218 , if it is determined that the set of fields associated with the target rule is a superset of the fields associated with the current node, then the process  200  proceeds to step  222  in which the current node is added to the superset list, and the process  200  then proceeds to end loop step  220 . 
     Returning to decision step  218 , if it is determined that the set of fields associated with the target rule is not a superset of the fields associated with the current node, then the process  200  proceeds to decision step  219 . In decision step  219 , if it is determined that any of the fields associated with the current node are shared with the fields of the target rule to be inserted into the directed graph  150 , then the process  200  proceeds to step  223 . In step  223 , an intermediate node is inserted as a parent of the current node that is associated with the shared fields. A child of the new intermediate node is then inserted and associated with the target rule. If, however, a parent node already exists that is identical to the intermediate node, then the intermediate node and the existing node are merged. The process  200  then proceeds from step  223  to step  224  as discussed above. 
     Returning to decision step  219 , if it is determined that any of the fields associated with the current node are not shared with the fields of the target rule, then the process  200  proceeds to end loop step  220  in which the loop returns to step  214  for the next child node. 
     After the completion of the loop represented by steps  214  to  220 , the process  200  proceeds to the loop represented by steps  225  to  230 , which is repeated for each node in the superset list. Proceeding from beginning loop step  225  to decision step  226 , if it is determined in decision step  226  that the current node has a child node, then the process  200  proceeds to step  227  in which the process  200  proceeds to step  214  to process the children nodes of the current node. If, however, in decision step  226 , it is determined that the current node does not have a child node, then the process  200  proceeds to step  228  in which, if the target rule is not already inserted, a new node is inserted as a child of the current node and that new node is associated with the target rule. The process  200  then proceeds from step  228  to step  229  in which any node links are updated, and from step  229  to end loop step  230 , which, as discussed above, returns to beginning loop step  225  for each node in the superset list. After the loop represented by steps  225  to  230  completes, e.g., after there are no nodes remaining in the superset list, the process  200  proceeds to step  213 . 
     Having set forth in  FIG. 2B  a process  200  by which a rule is inserted into the directed graph  150  of  FIG. 1 , an example will now be presented using the process  200  of  FIG. 2B  and a new rule to be inserted, R 5  (not illustrated), that is associated with the field “protocol” and the value “icmp” 
     The process  200  proceeds from beginning step  201  to loop step  202 . Beginning with the first field listed in the set of fields associated with the target rule, the field “protocol,” in step  202 , the process  200  proceeds to decision step  203  where it is determined that the root node  102  has a child node, node  114 , with the current field “protocol” of the target rule. The process  200  proceeds to step  204  in which the value of the current field, “icmp,” is added to the value set  106  of the current node. In decision step  205 , it is determined that the target rule R 5  only has the current field “protocol,” so the process  200  proceeds to decision step  206  where it is determined that there are no rules associated with the current node, and then the process  200  proceeds to step  207  in which the target rule R 5  is associated with the current node  114 . Then the process  200  proceeds to end loop step  213 . 
       FIG. 3A  is exemplary pseudo-code for removing a rule from a rule relations graph.  FIG. 3B  is a flow chart illustrating an exemplary operation for removing a rule from a directed graph  150  based on the pseudo-code of  FIG. 3A . The process  300  starts at the root node  102  and proceeds from beginning step  301  to step  302  where a child of the current node is found that is associated with a set of fields that is equal to or a subset of the set of fields associated with the rule to be removed (“target rule”). Once the child of the current node is found, the child, now the current node, is evaluated in decision step  303  to determine whether it is associated with the target rule. 
     If the current node is associated with the target rule, the process  300  proceeds to decision step  304  in which it is determined whether there is only one rule associated with the current node. If there is only one rule associated with the current node, the process  300  proceeds to step  307  in which the current node is removed and the associated node connections are updated. The process  300  then proceeds to step  306  in which the values associated with the target rule are removed from the corresponding value nodes (e.g.,  104 ,  106 ,  108 , and  110 ), and the process  300  then ends in step  310 . 
     Returning to decision step  304 , if it is determined that there is more than one rule associated with the current node, the process  300  then proceeds to step  305  in which the target rule is disassociated with the current node. The process  300  then proceeds to step  306 , as discussed above. 
     Returning to decision step  303 , if it is determined that the current node is not associated with the target rule, then the process  300  proceeds to step  308  in which a child of the current node is found that is associated with a set of fields that is equal to or a subset of the set of fields associated with the target rule. Next, in decision step  309 , if it is determined the set of fields associated with the child node is equal to the set of fields associated with the target rule, then the process  300  proceeds to decision step  304  as discussed above. If, however, it is determined that the set of fields associated with the child node is not equal to the set of fields associated with the target rule, then the process  300  returns to step  308 . 
     Having set forth in  FIG. 3B  a process  300  by which a rule is removed from the directed graph  150  of  FIG. 1 , an example will now be presented using the process  300  of  FIG. 3B  and rule R 3   130  associated with node  124  from  FIG. 1B . 
     The process  300  proceeds from beginning step  301  to step  302  where a child of the current node, the root node  102 , is found that is associated a set of fields that is equal to or a subset of the set of fields associated with the rule to be removed (“target rule”). The found child node is node  112 , since the set of fields associated with the node  112 , field “dstPort,” is a subset of the set of fields, “dstPort” and “network,” associated with the target rule, R 3   130 . The child  112  is now the current node  112 . In decision step  303  it is determined that node  112  is not associated with the target rule, so the process  300  proceeds to step  308  in which a child of the current node  112  is found that is associated with a set of fields that is equal to or a subset of the set of fields associated with the target rule. In this case, the child node that is found is node  124 , since the set of fields associated with the node  124 , fields “dstPort” and “network,” are equal to the set of fields, “dstPort” and “network,” associated with the target rule, R 3   130 . Next, in decision step  309 , it is determined the set of fields associated with the child node  124  is equal to the set of fields associated with the target rule R 3   130 , so the process  300  proceeds to decision step  304 , in which it is determined that there is only one rule associated with the current node, R 3   130 . The process  300  proceeds to step  307  in which the current node  124  is removed and the associated node connections are updated. In this case, only a parent connection is updated since node  124  is a leaf node, e.g., node  124  has no child nodes. The process  300  then proceeds to step  306  in which the values “81” and “external” associated with the target rule are removed from the respective value nodes dstPort value node  104  and network value node  110  (unless these values are associated with other rules), and the process  300  then ends in step  310 . 
       FIG. 4A  is exemplary pseudo-code for traversing a rule relations graph to locate a rule matching an event.  FIG. 4B  is a flow chart illustrating an exemplary process  400  for traversing a directed graph  150  to locate a rule matching an event based on the pseudo-code of  FIG. 4A . For embodiments of the disclosure that feature weighted nodes, optional steps shown in phantom are included. 
     The process  400  proceeds from beginning step  401  to beginning loop step  402 . The loop represented by steps  402  to  405  repeats for each field associated with the event. In decision step  403 , if it is determined that the current field associated with the event and its value matches a field and its value in the directed graph  150 , the process  400  proceeds to step  404  in which the current field, including its associated value, is added to a match set, and the process returns from end loop step  405  to beginning loop step  402  for the next field of the event, if there is another field. Otherwise, in decision step  403 , if it is determined that the current field associated with the event and its value does not match a field and its value in the directed graph  150 , the process  400  proceeds to end loop step  405 , and from there to beginning loop step  402  for the next field of the event, if there is another field. 
     After the loop represented by steps  402  to  405  is completed, it is determined in decision step  406  whether the match set is empty (e.g., if there are no fields in the set of fields associated with the match set). If the match set is empty, the process ends in step  425 , because there is no rule in the directed graph  150  that matches the event (e.g., there are no nodes in the directed graph  150  that are associated with any of the same fields that are associated with the event). If the match set is not empty, the process  400  proceeds to optional step  407 , in which the order of the fields in the set of fields associated with the match set (the “match set&#39;s fields”) is ordered by the respective ascending weights of those fields. By sorting the match set&#39;s fields by weight, fields with lighter weights are evaluated first by the process  400  of  FIG. 4  before fields with heavier weights. 
     The loop represented by steps  408  to  424  repeats for each node in the directed graph  150  that corresponds to a field in the match set. Proceeding from beginning loop step  408  to decision step  409 , if it is determined that the current node has already been processed (e.g., visited), the process  400  proceeds to decision step  419 . If, however, it is determined that the current node has not already been processed, the process  400  proceeds to decision step  410 , in which it is determined whether the set of fields associated with the current node (“current node&#39;s fields”) is equal to or a subset of the match set&#39;s fields. If it is determined that the current node&#39;s fields are not equal to or a subset of the match set&#39;s fields, the process  400  proceeds to decision step  419 , otherwise the process  400  proceeds to decision step  411 . In decision step  411 , if it is determined that the current node is not associated with any rules, then the process  400  proceeds to decision step  419 , otherwise the process  400  proceeds to beginning loop step  412 . 
     The loop represented by steps  412  to  418  repeats for each rule associated with the current node. In optional step  413 , for the current rule associated with the current node, each of the current rule&#39;s fields is evaluated if their weight is not greater than the weight of the match set&#39;s currently processed field. In decision step  414 , if it is determined that the values of the current rule&#39;s fields processed in step  413  are equal to the values of the event&#39;s fields, then the process  400  proceeds to decision step  415 , otherwise the process  400  proceeds to decision step  419 . In decision step  415 , if it is determined that all the event&#39;s fields have been processed, and their respective values are equal to the values of the current rule&#39;s fields, then the current rule is added to a set of matching rules in step  417 , otherwise the rule is added to a queue of potentially matching rules for later processing in step  416 . In end loop step  418 , the process  400  returns to beginning loop step  412  for the next rule, if any, associated with the current node. 
     In decision step  419 , if it is determined that the next node to evaluate is a child of the root node  102 , then the process  400  proceeds to decision step  420 , otherwise the process  400  proceeds to step  424 . In decision step  420 , it is determined whether, during traversal of the current child node&#39;s branch of the graph, any rules were added to the set of matching rules discussed above or to the queue of rules for later processing. If so, the process  400  proceeds to optional decision step  422 , otherwise the process  400  proceeds to step  421 . In step  421 , the field associated with the current child node of the root  102  is removed from the match set, and the process  400  proceeds to optional decision step  422 . 
     In optional decision step  422 , it is determined, for all rules in the queue of matching rules for later processing, whether there are any fields whose associated weight is not larger than the weight of the next field to be processed from the set of fields associated with the match set. If there is such a field whose associated weight is not larger, then the process  400  proceeds to optional step  423 , in which the remaining rules in the queue of matching rules for later processing are processed to determine if any rules in the queue correspond to the match set. The fully matching rules are added to the matching rule set, any unmatching rules are removed, and any remaining rules are left in the queue of matching rules for later processing. If, however, it is determined in optional decision step  422  that there is no such field whose associated weight is not larger than the weight of the next field to be processed from the set of fields associated with the match set, then the process  400  proceeds to end loop step  424 . 
     In end loop step  424 , the process  400  returns to beginning loop step  408  first for the next child node of the current node, then for the next sibling node of the current node when no child nodes remain, and finally to the parent node when no child or sibling nodes remain. After the loop represented by steps  408  to  424  completes, the process  400  ends in step  425 . 
     Having set forth in  FIG. 4  a process  400  for traversing a directed graph  150  to locate a rule matching an event, an example will now be presented using the process  400  of  FIG. 4  and the following event registered by a network intrusion detection system: field “dstPort” value “81,” field “payload” value “something,” and field “protocol” value “udp.” 
     The process  400  proceeds from beginning step  401  to beginning loop step  402 . In decision step  403 , it is determined that the current field “dstPort” and its value “81” matches a field and its value in the directed graph  150  (e.g., value node  104 ), so the process  400  proceeds to step  404  in which the current field and its associated value is added to a match set. The match set is currently {dstPort}. The process  400  returns from end loop step  405  to beginning loop step  402  for the next field of the event, “payload,” and onto decision step  403 . In decision step  403 , it is determined that the current field “payload” and its value “something” matches a field and its value in the directed graph  150  (e.g., value node  108 ), so the process  400  proceeds to step  404  in which the current field and its associated value is added to a match set. The match set is currently {dstPort, payload}. The process  400  returns from end loop step  405  to beginning loop step  402  for the next field of the event, “protocol,” and again onto decision step  403 . In decision step  403 , it is determined that the current field “protocol” and its value “udp” matches a field and its value in the directed graph  150  (e.g., value node  106 ), so the process  400  proceeds to step  404  in which the current field and its associated value is added to a match set. The match set is currently {dstPort, payload, protocol}. The process  400  proceeds to end loop step  405 , and as there are no remaining fields left in the set of fields associated with the event, the loop ends, and the process  400  proceeds to decision step  406 . The match set is {dstPort, payload, protocol}. 
     It is determined in decision step  406  that the match set is not empty, so the process  400  proceeds to optional step  407 , in which the match set&#39;s fields are ordered by the respective ascending weights of those fields. Rule table  100  of  FIG. 1  assigns a weight of 1 to field “dstPort,” a weight of 9 to field “payload,” and a weight of 1 to field “protocol.” Accordingly, in optional step  407 , the match set {dstPort, payload, protocol} is sorted by ascending weight as {dstPort, protocol, payload}. 
     The loop represented by steps  408  to  423  repeats for each node in the directed graph  150  that corresponds to a field in the match set. Thus, beginning with “dstPort” node  112 , and the currently processed field set as “dstPort,” in decision step  409  it is determined that the current node  112  has not already been processed, and then in decision step  410  it is determined the current node&#39;s  112  fields, {dstPort}, are a subset of the match set&#39;s fields, {dstPort, protocol, payload}, so the process  400  proceeds to decision step  411 . In decision step  411 , it is determined that the current node is not associated with any rules, so the process  400  proceeds to decision step  419 . 
     In decision step  419 , it is determined that the next node to evaluate, node  120 , is not a child of the root node  102 , so the process  400  proceeds to step  424 , which indicates to return to the beginning of loop step  408  for the child of node  112 , node  120 . 
     Now with “dstPort, protocol” node  120 , in decision step  409  it is determined that the current node  120  has not already been processed, and then in decision step  410  it is determined the current node&#39;s  112  fields, {dstPort, protocol}, are a subset of the match set&#39;s fields, {dstPort, protocol, payload}, so the process  400  proceeds to decision step  411 . In decision step  411 , it is determined that the current node is associated with a rule, rule R 2   126 , so the process  400  proceeds to beginning loop step  412 . 
     The loop represented by steps  412  to  418  occurs only once since only one rule, rule R 2   126 , is associated with the current node, node  120 . In optional step  413 , for each of rule R 2 &#39;s  126  fields, “dstPort” and “protocol,” it is determined that the fields&#39; weights, each of which is 1, is not greater than the weight of the match set&#39;s currently processed field, “dstPort.” In decision step  414 , and with reference to the rule table  100  of  FIG. 1A , it is determined that the values “1434” and “tcp” of rule R 2 &#39;s  126  fields, “dstPort” and “protocol,” respectively, are not equal to the values of the event&#39;s fields, value “81” for field “dstPort” and value “udp” for field “protocol,” so the process  400  proceeds to decision step  419 . In decision step  419 , it is determined that the next node to evaluate, node  132 , is not a child of the root node  102 , so the process  400  proceeds to step  424 , which indicates to return to the beginning of loop step  408  for the child of node  120 , node  132 . 
     Now with “dstPort, protocol, payload” node  132 , in decision step  409  it is determined that the current node  132  has not already been processed, and then in decision step  410  it is determined the current node&#39;s  132  fields, {dstPort, protocol, payload}, are equal to the match set&#39;s fields, {dstPort, protocol, payload}, so the process  400  proceeds to decision step  411 . In decision step  411 , it is determined that the current node is associated with a rule, rule R 4   134 , so the process  400  proceeds to beginning loop step  412 . 
     The loop represented by steps  412  to  418  occurs only once since only one rule, rule R 4   134 , is associated with the current node, node  132 . In optional step  413 , it is determined that the weight of the field “payload” is greater than the weight of the match set&#39;s currently processed field, “dstPort,” so the field “payload” will not be evaluated, while the remaining fields “dstPort” and “protocol” will be evaluated. In decision step  414 , and again with reference to the rule table  100  of  FIG. 1A , it is determined that the values “81” and “udp” of the rule R 4 &#39;s  134  fields, “dstPort” and “protocol,” respectively, are equal to the values of the event&#39;s fields, so the process  400  proceeds to step  416 , in which rule R 4   134  is added to a queue of potentially matching rules for later processing of the remaining field, “payload.” Since no other rules are associated with node  132 , the loop represented by steps  412  to  418  ends, and the process  400  proceeds to decision step  419 . In decision step  419 , it is determined that the next node to evaluate, node  132 , is not a child of the root node  102 , so the process  400  proceeds to step  424 , which indicates to return to the beginning of loop step  408  for the next child of node  112 , node  122 . 
     Proceeding beginning loop step  408  with “dstPort, payload” node  122 , in decision step  409  it is determined that the current node  122  has not already been processed, and then in decision step  410  it is determined the current node&#39;s  122  fields, {dstPort, payload}, are a subset of the match set&#39;s fields, {dstPort, protocol, payload}, so the process  400  proceeds to decision step  411 . In decision step  411 , it is determined that the current node is associated with a rule, rule R 1   128 , so the process  400  proceeds to beginning loop step  412 . 
     The loop represented by steps  412  to  418  occurs only once since only one rule, rule R 1   128 , is associated with the current node, node  122 . In optional step  413 , it is determined that the weight of 9 of field “payload” is greater than the weight of 1 of the match set&#39;s currently processed field, “dstPort,” so the field “payload” will not be evaluated, and the remaining field, “dstPort,” will be evaluated. In decision step  414 , and with reference to the rule table  100  of  FIG. 1A , it is determined that the value “1434” of the rule R 1 &#39;s  126  only evaluated field, “dstPort,” is not equal to the value “81” of the event&#39;s “dstPort” field, so the process  400  proceeds to decision step  419 . In decision step  419 , it is determined that the next node to evaluate, node  132 , is not a child of the root node  102 , so the process  400  proceeds to step  424 , which indicates to return to the beginning of loop step  408  for the child of node  122 , node  132 . 
     Now with “dstPort, protocol, payload” node  132 , in decision step  409  it is determined that the current node  132  has already been processed, so the process  400  proceeds to decision step  419 . In decision step  419 , it is determined that the next node to evaluate, node  124 , is a child of the root node  102 , so the process  400  proceeds to decision step  420 . In decision step  420 , it is determined that during traversal of the “dstPort” branch of the graph (e.g., nodes  112 ,  120 ,  122 ,  124  and  132 ) that rule R 4   134  was added to the queue of rules for later processing, so the process  400  proceeds to optional decision step  422 . 
     In optional decision step  422 , it is determined, for rule R 4   134 , that there are no fields for rule R 4   134  that have not been processed that have a weight not larger than the next field to be processed, field “protocol” (e.g., the only remaining field to be processed for rule R 4   134  is the field “payload” that has a weight of 9). The process  400  proceeds to step  424 , which indicates to return to the beginning of loop step  408  for the next child of the root node  102 , node  114 . 
     Now with “protocol” node  114 , and the currently processed field set as “protocol,” in decision step  409  it is determined that the current node  114  has not already been processed, and then in decision step  410  it is determined the current node&#39;s  114  fields, {protocol}, are a subset of the match set&#39;s fields, {dstPort, protocol, payload}, so the process  400  proceeds to decision step  411 . In decision step  411 , it is determined that the current node is not associated with any rules, so the process  400  proceeds to decision step  419 . 
     In decision step  419 , it is determined that the next node to evaluate, node  120 , is not a child of the root node  102 , so the process  400  proceeds to step  424 , which indicates to return to the beginning of loop step  408  for the child of node  114 , node  120 . 
     Now with “dstPort, protocol” node  120 , in decision step  409  it is determined that the current node  120  has already been processed, so the process  400  proceeds to decision step  419 . In decision step  419 , it is determined that the next node to evaluate, node  132 , is not a child of the root node  102 , so the process  400  proceeds to step  424 , which indicates to return to the beginning of loop step  408  for the child of node  120 , node  132 . 
     Now with “dstPort, protocol, payload” node  132 , in decision step  409  it is determined that the current node  132  has already been processed, so the process  400  proceeds to decision step  419 . In decision step  419 , it is determined that the next node to evaluate, “payload” node  116 , is a child of the root node  102 , so the process  400  proceeds to decision step  420 . In decision step  420 , it is determined that during traversal of the “protocol” branch of the graph (e.g., nodes  114 ,  120 , and  132 ) that no rules were added to the queue of rules for later processing, so the process  400  proceeds to step  421  in which the field “protocol” is removed from the match set. The match set is now {dstPort, payload}. Next, in optional decision step  422 , it is determined, for rule R 4   134 , that there is a field, “payload,” for rule R 4   134  that has not been processed that has a weight that is not larger than the weight of the next field to be processed, field “payload” (e.g., the only remaining field to be processed for rule R 4   134  is the field “payload” that has a weight of 9, and since the remaining field to be processed on the directed graph  150  is also the field “payload,” the weights are equal). The process  400  proceeds to step  423 , in which the processing of rule R 4   134  is completed (e.g., the remaining field “payload” and its value of “something” in the match set is equal to the value of field “payload” in rule R 4   134 ), whereby it is determined that rule R 4   134  matches the match set and rule R 4   134  is added to the matching rule set. The process  400  proceeds to step  424 , which indicates to return to the beginning of loop step  408  for the child of root node  102 , “payload” node  116 . 
     Now with “payload” node  116 , and the currently processed field set as “payload,” in decision step  409  it is determined that the current node  116  has not already been processed, and then in decision step  410  it is determined the current node&#39;s  116  fields, {payload}, are a subset of the match set&#39;s fields, {dstPort, payload}, so the process  400  proceeds to decision step  411 . In decision step  411 , it is determined that the current node is not associated with any rules, so the process  400  proceeds to decision step  419 . In decision step  419 , it is determined that the next node to evaluate, node  122 , is not a child of the root node  102 , so the process  400  proceeds to step  424 , which indicates to return to the beginning of loop step  408  for the child of node  116 , node  122 . 
     Now with “dstPort, payload” node  122 , in decision step  409  it is determined that the current node  122  has already been processed, so the process  400  proceeds to decision step  419 . In decision step  419 , it is determined that the next node to evaluate, node  132 , is not a child of the root node  102 , so the process  400  proceeds to step  424 , which indicates to return to the beginning of loop step  408  for the child of node  122 , node  132 . 
     Now with “dstPort, protocol, payload” node  132 , in decision step  409  it is determined that the current node  132  has already been processed, so the process  400  proceeds to decision step  419 . In decision step  419 , it is determined that the next node to evaluate is not a child of the root node  102  because there are no additional nodes to evaluate in the directed graph  150  (e.g., the next node, “network” node  118 , is not evaluated because the field “network” is not part of the match set as required by beginning loop step  408 ). The process  400  proceeds to step  424 , which indicates there are no additional nodes to evaluate, so the process  400  ends in step  425 . 
     The matching rule set contains one rule, rule R 4   134 . All rules in the set of rules did not need to be evaluated to find the rules that matched the event. In this case, three of the four rules were evaluated. The matching rule set can be processed at a time determined by the user in accordance with the needs of the system implementing the features, data structures, and processes disclosed above. 
       FIG. 5  is a block diagram that illustrates a computer system  500  upon which an embodiment of the present disclosure may be implemented in accordance with one aspect of the present disclosure. In certain embodiments, computer system  500  can be used to implement, store, and execute the disclosed data structures, algorithms, and processes discussed above. In certain embodiments, the computer system  500  may be implemented using software, hardware, or a combination of both, either in a dedicated server, or integrated into another entity, or distributed across multiple entities. 
     Computer system  500  includes a bus  508  or other communication mechanism for communicating information, and a processor  502  coupled with bus  508  for processing information (e.g., for executing the processes discussed above). By way of example, the computer system  500  may be implemented with one or more processors  502 . Processor  502  may be a general-purpose microprocessor, a microcontroller, a Digital Signal Processor (DSP), an Application Specific Integrated Circuit (ASIC), a Field Programmable Gate Array (FPGA), a Programmable Logic Device (PLD), a controller, a state machine, gated logic, discrete hardware components, or any other suitable entity that can perform calculations or other manipulations of information. Computer system  500  also includes a memory  510  (e.g., for storing the data structure(s) discussed above), such as a Random Access Memory (RAM), a flash memory, a Read Only Memory (ROM), a Programmable Read-Only Memory (PROM), an Erasable PROM (EPROM), registers, a hard disk, a removable disk, a CD-ROM, a DVD, or any other suitable storage device, coupled to bus  508  for storing information and instructions to be executed by processor  502 . The instructions may be implemented according to any method well known to those of skill in the art, including computer languages such as system languages (e.g., C, C++, Assembly), architectural languages (e.g., Java), and application languages (e.g., PHP, Ruby, Perl, Python). Memory  510  may also be used for storing temporary variable or other intermediate information during execution of instructions to be executed by processor  502 . Computer system  500  further includes a data storage device  506 , such as a magnetic disk or optical disk, coupled to bus  508  for storing information and instructions. 
     Computer system  500  may be coupled via I/O module  504  to a display device, such as a cathode ray tube (“CRT”) or liquid crystal display (“LCD”) for displaying information to a computer user. An input device, such as, for example, a keyboard, or a mouse may also be coupled to computer system  500  via I/O module  504  for communicating information and command selections to processor  502 . 
     According to one aspect of the present disclosure, the structures, algorithms, and processes discussed above may be implemented using a computer system  500  in response to processor  502  executing one or more sequences of one or more instructions contained in memory  510 . Such instructions may be read into memory  510  from another machine-readable medium, such as data storage device  506 . Execution of the sequences of instructions contained in main memory  510  causes processor  502  to perform the process steps described herein. One or more processors in a multi-processing arrangement may also be employed to execute the sequences of instructions contained in memory  510 . In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions to implement various embodiments of the present disclosure. Thus, embodiments of the present disclosure are not limited to any specific combination of hardware circuitry and software. 
     The term “machine-readable medium” as used herein refers to any medium or media that participates in providing instructions to processor  502  for execution. Such a medium may take many forms, including, but not limited to, non-volatile media, volatile media, and transmission media. Non-volatile media include, for example, optical or magnetic disks, such as data storage device  506 . Volatile media include dynamic memory, such as memory  506 . Transmission media include coaxial cables, copper wire, and fiber optics, including the wires that comprise bus  508 . Transmission media can also take the form of acoustic or light waves, such as those generated during radio frequency and infrared data communications. Common forms of machine-readable media include, for example, floppy disk, a flexible disk, hard disk, magnetic tape, any other magnetic medium, a CD-ROM, DVD, any other optical medium, punch cards, paper tape, any other physical medium with patterns of holes, a RAM, a PROM, an EPROM, a FLASH EPROM, any other memory chip or cartridge, a carrier wave, or any other medium from which a computer can read. 
     Although the processes and data structures described above have been discussed with reference to events in a network security system, the processes and data structures disclosed herein are equally applicable to other systems. For example,  FIG. 6A  illustrates an exemplary rule table for any type of event according to one embodiment, and  FIG. 6B  illustrates a directed graph representing the table of  FIG. 6A  according to certain embodiments of the disclosure.  FIG. 7A  illustrates an exemplary rule table for a home alarm monitoring system according to one embodiment, and  FIG. 7B  illustrates a directed graph representing the table of  FIG. 7A  according to certain embodiments of the disclosure.  FIG. 8A  illustrates an exemplary rule table for a host security monitoring system according to one embodiment, and  FIG. 8B  illustrates a directed graph representing the table of  FIG. 8A  according to certain embodiments of the disclosure. 
     The embodiments of the present disclosure provide a system in which system events are more quickly processed and matched against rules by organizing the rules according to a rule relations graph. The rule relations graph, which can be represented as a partially ordered graph, facilitates the processing of system events against rules associated with nodes in the graph. 
     Those of skill in the art would appreciate that the various illustrative blocks, modules, elements, components, methods, and algorithms described herein may be implemented as electronic hardware, computer software, or combinations of both. Furthermore, these may be partitioned differently than what is described. To illustrate this interchangeability of hardware and software, various illustrative blocks, modules, elements, components, methods, and algorithms have been described above generally in terms of their functionality. Whether such functionality is implemented as hardware or software depends upon the particular application and design constraints imposed on the overall system. Skilled artisans may implement the described functionality in varying ways for each particular application. 
     It is understood that the specific order or hierarchy of steps or blocks in the processes disclosed is an illustration of exemplary approaches. Based upon design preferences, it is understood that the specific order or hierarchy of steps or blocks in the processes may be rearranged. The accompanying method claims present elements of the various steps in a sample order, and are not meant to be limited to the specific order or hierarchy presented. 
     The previous description is provided to enable any person skilled in the art to practice the various aspects described herein. Various modifications to these aspects will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other aspects. Thus, the claims are not intended to be limited to the aspects shown herein, but is to be accorded the full scope consistent with the language claims, wherein reference to an element in the singular is not intended to mean “one and only one” unless specifically so stated, but rather “one or more.” Unless specifically stated otherwise, the term “some” refers to one or more. Pronouns in the masculine (e.g., his) include the feminine and neuter gender (e.g., her and its) and vice versa. All structural and functional equivalents to the elements of the various aspects described throughout this disclosure that are known or later come to be known to those of ordinary skill in the art are expressly incorporated herein by reference and are intended to be encompassed by the claims. Moreover, nothing disclosed herein is intended to be dedicated to the public regardless of whether such disclosure is explicitly recited in the claims. No claim element is to be construed under the provisions of 35 U.S.C. §112, sixth paragraph, unless the element is expressly recited using the phrase “means for” or, in the case of a method claim, the element is recited using the phrase “step for.”