Distributed Methodology for Approximate Event Counting

• US 20100332652A1
• Filed: 06/24/2010
• Published: 12/30/2010
• Est. Priority Date: 06/26/2009
• Status: Active Grant

• Current Assignee: Fortinet Inc.
• Original Assignee: AccelOps, Inc. (Fortinet Inc.)
• Inventors: Zhu, Hongbo, Chen, Sheng, Bhattacharya, Partha
• Granted Patent: US 8,510,432 B2
• Time in Patent Office: Days
• US Class Current: 709/224
• CPC Class Codes: H04L 41/069 using logs of notifications; Post-processing of notifications

Abstract

In a method and system for aggregating event information, events are received at a first plurality of nodes in a distributed system. For the events received at each node aggregated attribute information is determined in accordance with two or more rules and stored in distinct first tables, each table storing aggregated attribute information for a respective rule of the two or more rules. At each node of the first plurality of nodes, the two or more distinct first tables are transmitted to a respective node of a second set of nodes in the distributed system. At each node of the second set of nodes, two or more distinct second tables are generated by merging the aggregated attribute information in the tables transmitted to the node. Each rule of the two or more rules is evaluating using the aggregated attribute information obtained from a corresponding table of the second tables.

Claims

1. A computer-implemented method for collecting event information, comprising:

on one or more servers;

receiving events, each having attributes;

in accordance with a rule for detecting a system condition, aggregating event information for at least one attribute in a corresponding set of the received events, including;

in each table of a plurality of distinct tables that correspond to the rule, each table having an associated distinct hash function, storing aggregated attribute information in rows determined by the hash function corresponding to the table;

evaluating the rule separately with respect to each table, using the information in the table, to generate a plurality of intermediate results, including a respective intermediate result for each table;

when the intermediate results for each table indicate a potential violation of the rule, determining if the intermediate result for each table corresponds to a same group of events and an actual violation of the rule; and

producing a report in accordance with the determination.

2. The method of claim 1, including:

for each table of the plurality of tables, evaluating the rule with respect to the aggregated attribute information in individual rows of the table to produce a respective intermediate result for each row of the table; and

identifying rows of the tables for which the intermediate results indicate a potential rule violation;

determining, with respect to the rows of the tables for which the intermediate results indicate a potential rule violation, whether every one of the tables in the plurality of tables has a row for which the intermediate result indicates a potential rule violation and which corresponds to the same group of received events.

3. The method of claim 2, including, when every one of the tables in the plurality of tables has a row for which the intermediate results indicate a potential rule violation, identifying received events corresponding to the row in each of the tables for which the intermediate results indicates a potential rule violation, and determining if the rule is violated by the identified events.

4. The method of claim 1, wherein each table of the plurality of tables includes a number of sub-tables, the number of sub-tables corresponding to a number of predetermined time increments for a time window, each sub-table corresponding to a distinct time increment in the time window;

and wherein each sub-table in the plurality of tables stores aggregated attribute information corresponding to the time increment in the time window.

5. The method of claim 4, wherein the time window has a duration greater than one minute.

6. The method of claim 4, including:

determining that the time window has expired; and

in response to the determining that the time window has expired, storing aggregated attribute information in tables corresponding to a new time window.

7. A computer-implemented method for collecting event information, comprising:

receiving events at a first plurality of nodes in a distributed system, each event having attributes;

for the events received at each node of the first plurality of nodes, determining aggregated attribute information corresponding to two or more rules;

at each node of the first plurality of nodes, storing the aggregated attribute information in two or more distinct first tables, each table of the first tables storing aggregated attribute information for a respective rule of the two or more rules;

at each node of the first plurality of nodes, transmitting the two or more distinct first tables to a respective node of a second set of nodes in the distributed system, the second set of nodes comprising one or more nodes in the distributed system;

at each node of the second set of nodes, generating two or more distinct second tables by merging the aggregated attribute information in the tables transmitted to the node; and

evaluating each rule of the two or more rules using the aggregated attribute information obtained from a corresponding table of the second tables.

8. The method of claim 7, wherein the aggregated attribute information for a received event is stored in a row of a respective table determined by a hash function, wherein the hash function takes as input at least a portion of the aggregated attribute information for the received event.

9. The method of claim 8, wherein the aggregated attribute information for a received event is stored in a row of the respective table determined by applying the hash function to a set of aggregation attributes of the received event, the set of aggregation attributes determined by the rule for which aggregated attribute information is stored in the respective table.

10. The method of claim 7, wherein at each node of the first plurality of nodes, for each respective rule of the two or more rules, storing the aggregated information corresponding to the respective rule in a plurality of third tables comprising a subset of the first tables, each table of the third tables having a distinct corresponding hash function;

the storing including adding the same aggregated information to a respective row of each table of the plurality of third tables, wherein the respective row is determined by the hash function corresponding to the table.

11. The method of claim 7, wherein the aggregated attribute information stored in the two or more distinct tables correspond to events received during a time window.

12. The method of claim 7, including:

for each node of the first plurality of nodes, determining that a time window has expired; and

in response to the determination, transmitting the two or more distinct first tables to the respective node of the second set of nodes in the distributed system.

13. The method of claim 12, including:

for each node of the first plurality of nodes, generating two or more distinct third tables, the third tables corresponding to a new time window; and

storing aggregated attribute information in the two or more distinct third tables.

14. The method of claim 7, wherein each rule of the two or more rules specifies a group-by attribute set, an aggregation condition and a time window, the time window defining a period of time, the group-by attribute set defining a set of aggregation attributes, the aggregation condition defining a Boolean expression of aggregation clauses wherein each aggregation clause includes an aggregation attribute for which aggregated attribute information is to be stored in a respective table of the first tables.

15. The method of claim 7, including:

at each node of the second set of nodes, transmitting the two or more distinct second tables to a final node in the distributed system; and

at the final node, generating two or more distinct final tables by merging the aggregated attribute information in the tables transmitted to the node.

16. The method of claim 7, wherein the event attributes for which aggregated attribute information is determined includes at least one of:

source IP address, destination IP address, destination port, protocol, source Interface, destination interface, file name, source user name, and source computer name.

17. The method of claim 7, wherein evaluating a respective rule includes:

for each table of a fourth plurality of tables, comprising second tables that store aggregated attribute information for the respective rule, evaluating the respective rule with respect to the aggregated attribute information in individual rows of the table to produce a respective intermediate result for each row of the table; and

identifying rows of the tables for which the intermediate results indicate a potential rule violation;

determining, with respect to the rows of the fourth plurality of tables for which the intermediate results indicate a potential rule violation, whether every one of the fourth plurality of tables has a row for which the intermediate result indicates a potential rule violation and which corresponds to a same group of received events.

18. The method of claim 17, including, when every one of the tables in the fourth plurality of tables has a row for which the intermediate results indicate a potential rule violation, identifying received events corresponding to the row in each of the fourth plurality of tables for which the intermediate results indicates a potential rule violation, and determining if the rule is violated by the identified events.

19. A server system, comprising:

one or more processors;

memory storing one or more programs, the one or more programs including instructions, which when executed by the one or more processors, cause the server system to;

receive events, each having attributes;

in accordance with a rule for detecting a system condition, aggregate event information for at least one attribute in a corresponding set of the received events, including;

in each table of a plurality of distinct tables, each table having an associated distinct hash function, store aggregated attribute information in rows determined by the hash function corresponding to the table;

evaluate the rule separately with respect to each table, using the information in the table, to generate a plurality of intermediate results, including a respective intermediate result for each table;

when the intermediate results for each table indicate a violation of the rule, determine if the intermediate result indicating a rule violation for each table corresponds to a same group of events; and

produce a report in accordance with the determination.

20. A computer readable storage medium storing the one or more programs including instructions, which when executed by one or more processors of a computer system, cause the computer system to:

receive events, each having attributes;

in accordance with a rule for detecting a system condition, aggregate event information for at least one attribute in a corresponding set of the received events, including, in each table of a plurality of distinct tables, each table having an associated distinct hash function, storing aggregated attribute information in rows determined by the hash function corresponding to the table;

evaluate the rule separately with respect to each table, using the information in the table, to generate a plurality of intermediate results, including a respective intermediate result for each table;

when the intermediate results for each table indicate a violation of the rule, determine if the intermediate result indicating a rule violation for each table corresponds to a same group of events; and

produce a report in accordance with the determination.

21. A server system, comprising:

one or more processors;

memory storing one or more programs, the one or more programs including instructions, which when executed by the one or more processors, cause the server system to;

receive events at a first plurality of nodes in a distributed system, each event having attributes;

for the events received at each node of the first plurality of nodes, determine aggregated attribute information corresponding to two or more rules;

at each node of the first plurality of nodes, store the aggregated attribute information in two or more distinct first tables, each table of the first tables storing aggregated attribute information for a respective rule of the two or more rules;

at each node of the first plurality of nodes, transmit the two or more distinct first tables to a respective node of a second set of nodes in the distributed system, the second set of nodes comprising one or more nodes in the distributed system;

at each node of the second set of nodes, generate two or more distinct second tables by merging the aggregated attribute information in the tables transmitted to the node; and

evaluate each rule of the two or more rules using the aggregated attribute information obtained from a corresponding table of the second tables.

22. A computer readable storage medium storing the one or more programs including instructions, which when executed by one or more processors of a computer system, cause the computer system to:

receive events at a first plurality of nodes in a distributed system, each event having attributes;

for the events received at each node of the first plurality of nodes, determine aggregated attribute information corresponding to two or more rules;

at each node of the first plurality of nodes, store the aggregated attribute information in two or more distinct first tables, each table of the first tables storing aggregated attribute information for a respective rule of the two or more rules;

at each node of the first plurality of nodes, transmit the two or more distinct first tables to a respective node of a second set of nodes in the distributed system, the second set of nodes comprising one or more nodes in the distributed system;

at each node of the second set of nodes, generate two or more distinct second tables by merging the aggregated attribute information in the tables transmitted to the node; and

evaluate each rule of the two or more rules using the aggregated attribute information obtained from a corresponding table of the second tables.