Method and apparatus for rate limiting

• US 7,917,647 B2
• Filed: 06/02/2003
• Issued: 03/29/2011
• Est. Priority Date: 06/16/2000
• Status: Active Grant

• Current Assignee: McAfee, LLC
• Original Assignee: McAfee, Inc. (McAfee, LLC)
• Inventors: Sherlock, Kieran G., Cooper, Geoffrey, Hoy, Mark
• Primary Examiner(s): Najjar; Saleh
• Assistant Examiner(s): Kim; Edward J
• Application Number:
  US10/453,824
• Publication Number:
  US 20040042470A1
• Time in Patent Office: 2,857 Days
• Field of Search: 709/233, 709/225, 709/224, 709/215, 370229-235
• US Class Current: 709/233
• CPC Class Codes: H04L 41/046 comprising network management agents or mobile agents therefor
• CPC Class Codes: H04L 41/069 using logs of notifications; Post-processing of notifications
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/22 comprising specially adapted graphical user interfaces [GUI]
• CPC Class Codes: H04L 41/5012 determining service availability, e.g. which services are available at a certain point in time
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/045 for graphical visualisation of monitoring data
• CPC Class Codes: H04L 43/06 Generation of reports
• CPC Class Codes: H04L 43/062 related to network traffic
• CPC Class Codes: H04L 43/067 using time frame reporting
• CPC Class Codes: H04L 43/14 using software, i.e. software packages network security related monitoring H04L63/1408
• CPC Class Codes: H04L 43/18 Protocol analysers
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 63/0227 Filtering policies mail message filtering H04L51/212
• CPC Class Codes: H04L 63/0263 Rule management
• CPC Class Codes: H04L 63/0823 using certificates cryptographic mechanisms or cryptographic arrangements for entity authentication involving certificates H04L9/3263
• CPC Class Codes: H04L 63/083 using passwords cryptographic mechanisms or cryptographic arrangements for entity authentication using a predetermined code H04L9/3226
• CPC Class Codes: H04L 63/1408 by monitoring network traffic monitoring network traffic per se H04L43/00
• CPC Class Codes: H04L 63/1416 : Event detection, e.g. attack signature detection
• CPC Class Codes: H04L 63/1425 : Traffic logging, e.g. anomaly detection
• CPC Class Codes: H04L 63/1433 : Vulnerability analysis
• CPC Class Codes: H04L 63/166 : at the transport layer
• CPC Class Codes: H04L 69/22 : Parsing or analysis of headers

Abstract

A method and apparatus for a network monitor internals mechanism, which serves to translate packet data into multiple concurrent streams of encoded network event data, to contribute to enterprise management, reporting, and global mechanisms for aggregating monitors at a centralized aggregation point, and to facilitate rate limiting techniques because such monitors are not in control (i.e. cannot back pressure flow) is provided.

Claims

1. An apparatus for rate limiting to control amounts of data in a passive network monitoring pipelined system, said apparatus comprising:

a processor-implemented packet filter module having a first rate limiting mechanism for discarding particular incoming packets and passing on non-discarded packets;

a monitor receiving said non-discarded packets from said packet filter module, said monitor processing said non-discarded packets and outputting corresponding events, said monitor having a second rate limiting mechanism for discarding particular incoming events and passing on non-discarded events;

a logger module having a third rate limiting mechanism for discarding unwanted data and passing on said non-discard events, said logger module within a policy monitor module receiving said outputted corresponding events from said monitor;

and a reporting module, having a fourth rate limiting mechanism wherein said non-discarded events are received from said logger module and combined with like events in a roll-up over a time interval or based on the hierarchy of objects to meet storage requirements.

2. The apparatus of claim 1, wherein said second rate limiting mechanism chooses not to send events to a security manager system when the rate at which such events arrive exceeds a specified limit.

3. The apparatus of claim 1, further comprising means for rate limiting by rolling up input data to an Enterprise Reporting system.

4. The apparatus of claim 3, wherein said means for rate limiting further comprises means for combining said rolled-up data over an interval of time or with rolled-up data from objects higher in the object hierarchy.

5. The apparatus of claim 1, further comprising means for said third rate limiting mechanism to maintain several levels of degraded service such that service degrades slowly, and to degrade service, data is discarded based on a heuristic classification of the input traffic by rule, disposition and logging severity.

6. The apparatus of claim 1, further comprising a logger algorithm for performing a filtering process on data arriving into said logger module of said policy monitor module, said algorithm escalating aggressiveness of said filtering process based on a number of violations a Policy Engine prefers to log, and based on a configuration of said filtering process, wherein said filtering process takes place on a periodic basis over intervals of time, packets, or events, with said filtering process lagging by N of said intervals.

7. The apparatus of claim 6, wherein said configuration is in part defined by, but not limited to, the following parameters:

FILTER_ENABLE, set to 1 enables rate based filtering, and if set to 0 no rate limiting takes place;

FILTER_START_HIGH_VOLUME_VIOL=a first predetermined number, wherein for each interval of time, packets, or events, and once such percentage of violations occur, start filtering the highest volume rule/disposition combinations;

FILTER_START_LOW_PRIORITY=a second predetermined number, wherein for each said interval, and once such percentage of violations is reached, start filtering off all but CRITICAL violations;

FILTER_START_ALL=a third predetermined number, wherein for each said interval, and once such percentage of violations is reached, logging of further violations is disabled;

and FILTER_ER_LAG=a fourth predetermined number, indicating how many of said intervals are logged in a non-limited way even though the filtering threshold is met.

8. The apparatus of claim 1, further comprising means for tracking discarded events, said means for tracking comprising counters to indicate the following during a collection process of the a current interval of time, packets, or events:

number of NetworkEvents that are logged;

number of NetworkEvents that are discarded;

and total number of Network Events that occurred.

9. The apparatus of claim 8, wherein information from said collection process is passed on to an Enterprise Manager periodically.

10. The apparatus of claim 4, further comprising an algorithm to combine rollups to fit a predetermined amount of storage wherein:

MT=Target available space;

MC=current available space;

and MaxRollup=maximum interval over which events are currently rolled up, said algorithm operating as follows;

1. If MC<

=MT then the algorithm terminates;

2. MaxRollup=N*MaxRollup (where N may be 2 or a greater integer);

3. Combine N adjacent rollups in data into rollups with the new MaxRollup interval;

4. Optionally combine rollups based on object hierarchy, using one or more of the following;

Combine host groups with containing host groups;

Combine host groups with containing subnets; and

Combine host groups based on reporting element;

wherein said combination performed by incrementing the count of the containing group and removing the contained group, so that the total count of events remains the same; and

5. Continue with step 1.

11. The apparatus of claim 2, further comprising an algorithm, wherein said algorithm has the following arguments:

Iv=interval length, in seconds;

avgN=number of intervals to time average;

S=maximum events per Iv (input specification);

M=measured events per last Iv;

and Ma=time averaged value of M;

NB=a number of bytes to write at once;

wherein said algorithm comprises the steps of;

measuring M;

rate limiting a succeeding interval of Iv seconds based on M and S;

to smooth out the performance of said algorithm, time averaging M over a last avgN intervals using said algorithm, as follows;

Ma=(Ma*(avgN−

1)+M)/avgN

from Ma and S, deriving a number of events that should have been discarded by rate limiting over said last interval, as well as deriving a fraction of said events that should have been discarded, as follows;

D=Ma−

S, (when Ma>

S, 0 otherwise); and

frac=D/Ma;

for applying said number to a next interval, adding frac to a sum every time there is a new event;

when frac crosses an integer boundary, do not pass on said event.

12. The apparatus of claim 2, wherein said rate limiting mechanism accepts as a first input parameter a buffer size for encoding DME data to said policy monitor module, and accepts as a second input parameter a specification of a fraction of said buffer to reserve for rate limiting.

13. The apparatus of claim 12, further comprising an algorithm, said algorithm comprising the steps of:

when writing DME data to a socket for transmission to said policy monitor module, said monitor maintaining a large output buffer as a queue data structure;

conceptually dividing said buffer into a working section and a reserved section;

modifying a TCP socket to said policy monitor module to use non-blocking I/O mode, so that said monitor process can determine when said socket is full;

placing generated DME data in said output buffer;

every NB bytes, said monitor attempting to write said buffered data to said socket, stopping only when said buffer is empty or said socket is full;

if said buffer is empty, said monitor continue processing;

if said socket is full, leaving said DME data in said output buffer and continue processing until another NB bytes of data is added to said output buffer;

if said output buffer is full, placing said socket in blocking I/O mode, whereby said monitor waits until at least NB bytes of data are processed by said policy monitor module before continuing processing;

when said monitor determines a new event appears, providing means for said monitor determining if said output buffer is currently using said reserved section;

if said output buffer is using said working section, then processing said new event and sending all DME data from said event to said policy monitor module as it is produced.

14. The apparatus of claim 1, wherein said packet filter module further comprises:

a streams process, wherein said streams process comprises the following steps;

a stream using a predetermined hash for identifying said stream;

optionally keeping a most recently used (MRU) queue for all events with a given hashID, wherein said hashID indexes into a hash_struct array; and

providing command line parameters for streams as follows;

conTime=t1, average connection time for a stream connection;

\

discTime=t2, disconnect timer, used in disabling streams;

lowWater=LLLL, set low water mark for capture; and

hiWater=HHH, set high water mark for capture;

wherein lowWater=LLLL is a rate limiting point;

a discard policy, comprising;

each event has a hash_state;

HASH_UNUSED, HASH_RECEIVING or HASH_DISCARDING;

initially said hash_state is HASH_UNUSED and switches to HASH_RECEIVING when a stream is first encountered;

when below lowWater all streams are collected;

when above lowWater any new stream of data is ignored, wherein a packet on a current data stream in (HASH_RECEIVING) times out after conTime and is placed into said HASH_DISCARDING state for a period of discTime; and

when above the hiWater mark, all streams are discarded and each discarded stream stays in said HASH_DISCARDING state for said discTime.

15. The apparatus of claim 14, wherein if an MRU queue is kept, and

wherein said hashStruct is associated with an element of said MRU queue, then said MRU element is moved to the top of said MRU queue when said hashStruct is referenced by data in an associated stream, or

wherein if said hashStruct does not have an associated MRU element when data arrives on said stream, then a second MRU element is removed from the bottom of said MRU queue, said second MRU element disassociated with any other hashStruct, and associated with said hashStruct, and said second MRU element is moved to the top of said MRU queue.

16. The apparatus of claim 15, further providing an MRU circular queue, wherein when during rate limiting only streams with an MRU object are processed, and when a stream is processed in non-rate limiting mode, a least recently used (LRU) object is assigned to said stream and set as the MRU for every packet.

17. A method for rate limiting to control amounts of data in a passive network monitoring pipelined system, said method comprising:

providing a processor-implemented packet filter module having a first rate limiting mechanism for discarding particular incoming packets and passing on non-discarded packets;

providing a monitor receiving said non-discarded packets from said packet filter module, said monitor processing said non-discarded packets and outputting corresponding events, said monitor having a second rate limiting mechanism for discarding particular incoming events and passing on non-discarded events;

providing a logger module having a third rate limiting mechanism for discarding unwanted data and passing on said non-discard events, said logger module within a policy monitor module receiving said outputted corresponding events from said monitor;

and providing a rate limiting module, having a fourth rate limiting mechanism wherein said non-discarded events are received from said logger module and abstracted over a predetermined time interval to meet storage requirements.

18. The method of claim 17, wherein said second rate limiting mechanism chooses not to send events to a security manager system when the rate at which such events arrive exceeds a specified limit.

19. The method of claim 17, further comprising rate limiting by rolling up input data to an Enterprise Reporting system.

20. The method of claim 19, wherein said rate limiting further comprises means for combining said rolled-up data over an interval of time or with rolled-up data from objects higher in the object hierarchy.

21. The method of claim 17, further comprising said third rate limiting mechanism maintaining several levels of degraded service such that service degrades slowly, and to degrade service, discarding based on a heuristic classification of the input traffic by rule, disposition, and logging severity.

22. The method of claim 17, further comprising providing a logger algorithm for performing a filtering process on data arriving into said logger module of said policy monitor module, said algorithm escalating aggressiveness of said filtering process based on a number of violations a Policy Engine prefers to log, and based on a configuration of said filtering process, wherein said filtering process takes place on a periodic basis over intervals of time, packets, or events, with said filtering process lagging by N of said intervals.

23. The method of claim 22, wherein said configuration is in part defined by, but not limited to, the following parameters:

FILTER_ENABLE, set to 1 enables rate based filtering, and if set to 0 no rate limiting takes place;

FILTER_START_HIGH_VOLUME_VIOL=a first predetermined number, wherein for each interval of time, packets, or events, and once such percentage of violations occur, start filtering the highest volume rule/disposition combinations;

FILTER_START_LOW_PRIORITY=a second predetermined number, wherein for each said interval, and once such percentage of violations is reached, start filtering off all but CRITICAL violations;

FILTER_START_ALL=a third predetermined number, wherein for each said interval, and once such percentage of violations is reached, logging of further violations is disabled;

and FILTER_ER_LAG=a fourth predetermined number, indicating how many of said intervals are logged in a non-limited way even though the filtering threshold is met.

24. The method of claim 17, further comprising means for tracking discarded events, said tracking comprising counters to indicate the following during a collection process of the a current interval of time, packets, or events:

number of NetworkEvents that are logged;

number of NetworkEvents that are discarded;

and total number of Network Events that occurred.

25. The method of claim 24, wherein information from said collection process is passed on to an Enterprise Manager periodically.

26. The method of claim 18, further comprising providing an algorithm, wherein said algorithm has the following arguments:

Iv=interval length, in seconds;

avgN=number of intervals to time average;

S=maximum events per Iv (input specification);

M=measured events per last Iv; and

Ma=time averaged value of M;

NB=a number of bytes to write at once;

wherein said algorithm comprises the steps of;

measuring M;

rate limiting a succeeding interval of Iv seconds based on M and S;

to smooth out the performance of said algorithm, time averaging M over a last avgN intervals using said algorithm, as follows;

Ma=(Ma*(avgN−

1)+M)/avgN

from Ma and S, deriving a number of events that should have been discarded by rate limiting over said last interval, as well as deriving a fraction of said events that should have been discarded, as follows;

D=Ma−

S, (when Ma>

S, 0 otherwise); and

frac=D/Ma;

for applying said number to a next interval, adding frac to a sum every time there is a new event;

when frac crosses an integer boundary, do not pass on said event.

27. The method of claim 18, wherein said rate limiting mechanism accepts as a first input parameter a buffer size for encoding DME data to said policy monitor module, and accepts as a second input parameter a specification of a fraction of said buffer to reserve for rate limiting.

28. The method of claim 27, further comprising providing an algorithm, said algorithm comprising the steps of:

when writing DME data to a socket for transmission to said policy monitor module, said monitor maintaining a large output buffer as a queue data structure;

conceptually dividing said buffer into a working section and a reserved section;

modifying a TCP socket to said policy monitor module to use non-blocking I/O mode, so that said monitor process can determine when said socket is full;

placing generated DME data in said output buffer;

every NB bytes, said monitor attempting to write said buffered data to said socket, stopping only when said buffer is empty or said socket is full;

if said buffer is empty, said monitor continue processing;

if said socket is full, leaving said DME data in said output buffer and continue processing until another NB bytes of data is added to said output buffer;

if said output buffer is full, placing said socket in blocking I/O mode, whereby said monitor waits until at least NB bytes of data are processed by said policy monitor module before continuing processing;

when said monitor determines a new event appears, providing means for said monitor determining if said output buffer is currently using said reserved section;

if said output buffer is using said working section, then processing said new event and sending all DME data from said event to said policy monitor module as it is produced.

29. The method of claim 17, wherein said packet filter module further comprises:

a streams process, wherein said streams process comprises the following steps;

a stream using a predetermined hash for identifying said stream;

optionally keeping a most recently used (MRU) queue for all events with a given hashID, wherein said hashID indexes into a hash_struct array; and

providing command line parameters for streams as follows;

conTime=t1, average connection time for a stream connection;

discTime=t2, disconnect timer, used in disabling streams;

lowWater=LLLL, set low water mark for capture; and

hiWater=HHH, set high water mark for capture;

wherein

lowWater=LLLL is a rate limiting point;

a discard policy, comprising;

each event has a hash_state;

HASH_UNUSED, HASH_RECEIVING or HASH_DISCARDING;

initially said hash_state is HASH_UNUSED and switches to HASH_RECEIVING when a stream is first encountered;

when below lowWater all streams are collected;

when above lowWater any new stream of data is ignored, wherein a packet on a current data stream in (HASH_RECEIVING) times out after conTime and is placed into said HASH_DISCARDING state for a period of discTime; and

when above the hiWater mark, all streams are discarded and each discarded stream stays in said HASH_DISCARDING state for said discTime.

30. The method of claim 29, wherein if an MRU queue is kept, and

wherein said hashStruct is associated with an element of said MRU queue, then said MRU element is moved to the top of said MRU queue when said hashStruct is referenced by data in an associated stream, or

wherein if said hashStruct does not have an associated MRU element when data arrives on said stream, then a second MRU element is removed from the bottom of said MRU queue, said second MRU element disassociated with any other hashStruct, and associated with this said hashStruct, and said second MRU element is moved to the top of said MRU queue.

31. The method of claim 30, further comprising providing an MRU circular queue, wherein when during rate limiting only streams with an MRU object are processed, and when a stream is processed in non-rate limiting mode, a least recently used (LRU) object is assigned to said stream and set as the MRU for every packet.

32. The method of claim 20, further comprising providing an algorithm to combine rollups to fit a predetermined amount of storage wherein:

MT=Target available space;

MC=current available space;

and MaxRollup=maximum interval over which events are currently rolled up, said algorithm operating as follows;

1. If MC<

=MT then the algorithm terminates;

2. MaxRollup=N*MaxRollup (where N may be 2 or a greater integer);

3. Combine N adjacent rollups in data into rollups with the new MaxRollup interval;

4. Optionally combine rollups based on object hierarchy, using one or more of the following;

Combine host groups with containing host groups;

Combine host groups with containing subnets;

and Combine host groups based on reporting element;

wherein said combination performed by incrementing the count of the containing group and removing the contained group, so that the total count of events remains the same;

and

5. Continue with step 1.