Method and apparatus for detecting anomalies in aggregated traffic volume data

[0001] 1. Field of the Invention

[0002] Embodiments of the present invention generally relate to traffic monitoring in a network and, more particularly, to a method and apparatus for detecting anomalies in aggregated traffic volume data.

[0003] 2. Description of the Related Art

[0004] Networks typically monitor data traffic passing through one or more network elements in order to detect abnormal activities that may suggest some type of malicious attack is underway. One type of traffic alarm process relies on a complex frequency domain analysis of traffic volume. Other types of traffic alarm processes employ static thresholds for alarming based on traffic volume. However, Internet traffic is complex and difficult to characterize and model. The aggregated traffic is a mixture of difference applications and protocols. The traffic is evolving as the applications and protocols change. Any alarm process that uses static thresholds is only effective for a short period of time, since the traffic is dynamic and under constant change. Accordingly, there exists a need in the art for a method and apparatus for detecting anomalies in aggregated traffic volume data that can accurately detect abnormal changes in traffic and is less complex.

[0005] Method and apparatus for processing traffic of interest in a network is described. In one embodiment, a baseline profile and at least one threshold is computed using initial aggregated volume data for the traffic of interest. Aggregated volume counts for time periods in a time interval are obtained. Differences between the aggregated volume counts for the time periods and values of the baseline profile for corresponding time periods are computed. An alarm is triggered for each of the differences that exceeds the at least one threshold.

[0011] FIG. 1 is a block diagram depicting a network architecture 100 in accordance with one or more aspects of the invention. The network architecture 100 includes a network 102 in communication with a network 104 via a peering connection 118. Each of the networks 102 and 104 comprise packet networks configured to propagate packets in accordance with a particular network protocol, such as internet protocol (IP), and transport protocol, such as transmission control protocol (TCP). In the present example, the network 104 comprises an Internet Service Provider (ISP) network. The network 102 includes a peer network element 106 for receiving traffic from the ISP 104 over the peer connection 118 and providing traffic to the ISP 104 over the peer connection 118. The peer network element 106 may comprise one or more routers, switches, and the like.

[0012] In a typical peering arrangement, the network 102 and the ISP 104 forward each others packets directly across the peering connection 118, rather than using the standard Internet backbone. For example, the ISP 104 may provide Internet service to the clients 114-1 through 114-N (collectively clients 114). The network 102 may host servers 116-1 through 116-M (collectively servers 116). If the clients 114 request access to services hosted by the servers 116, the corresponding packets are communicated between the ISP 104 and the network 102 directly over the peering connection 118.

[0013] The peer network element 106 is configured to log various statistics with respect to the traffic communicated over the peer connection 118. In particular, the peer network element 106 is configured to record volumetric counts of flows, packets, and/or bytes passing over the peer connection 118. In one embodiment, a monitoring system 108 is coupled to the network. The monitoring system 108 includes an anomaly detection module 110 for detecting abnormal volume changes for traffic of interest through the peer network element 106. The monitoring system 108 is configured to periodically collect volume data for traffic of interest from the peer network element 106. The anomaly detection module 110 executes an algorithm using the volume data as parametric input. As described in more detail below, when there is a significant volume change in traffic of interest, the algorithm determines based on past data observations if the change can be attributed to normal traffic fluctuation or abnormal activities. Detection of abnormal volume changes may suggest some type of attack is underway. If such abnormal volume is detected, the anomaly detection module 110 generates an alarm.

[0014] In another embodiment, the anomaly detection module 110 is implemented by the peer network element 106. Alarms generated by the anomaly detection module 110 are detected by the monitoring system 108. Those skilled in the art will appreciate that the network architecture 100 is just one example of a network architecture in which the present invention may be employed. In general, the anomaly detection module 110 may be employed to monitor volume for traffic of interest through any network element in a network.

[0015] In particular, aggregated traffic volume data often exhibits daily and weekly periodicity as a function of time. The algorithm operates on the assumption that the traffic pattern for a current week is similar to the pattern observed in the past weeks. Assume an aggregated volumetric count of traffic is obtained for N time periods every week. Let X_n,j be the aggregated traffic value for an nth week and jth time period, where n≧0 and 1≦j≦N. Let B_n,j be a weekly baseline profile value for the nth week and jth time period, where n≧0 and 1≦j≦N. The weekly baseline profile is established from N data points using exponential smoothing. The baseline profile value for the (n+1)th week is obtained by the following:
B_n+1,j=X_n,jα+B_n,j(1−α)  Eq. 1,
where α is an exponential smoothing constant. The initial baseline profile is formed as follows (where M is the number of points used for exponential smoothing):

[0016] $\begin{array}{cc}{B}_{1,j}=\frac{X_{1,j-M+1}+X_{1,j-M+2}+\dots +X_{1,j}}{M}\mathrm{for}M\le j\le N\mathrm{with}{B}_{1,1}=X_{1,1}\mathrm{and}{B}_{1,2}=\frac{X_{1,1}+X_{1,2}}{2},\dots ,B_{1,M}=\frac{X_{1,1}+X_{1,2}+\dots +X_{1,M}}{M}.& \mathrm{Eq}.2\end{array}$

[0017] The difference of the jth observed value (X_n,j) and the jth baseline value for the nth week is defined as:
D_j=X_n,j−B_n,j  Eq. 3.
The difference, D_j, can be empirically shown to be normally distributed with a mean of zero. A variance is updated weekly by applying exponential smoothing over the estimated variance for the past week. The variance for the nth week (S_n) is defined as follows:

[0018] $\begin{array}{cc}{S}_n=\left(1-\beta \right)S_{n-1}+\beta \frac{\sum _{j=1}^N{\left(X_{n,j}-B_{n,j}\right)}^2\mathrm{when}X_{n,j}-B_{n,j}<D_{\mathrm{cutoff}},0\mathrm{otherwise}}{N-n_{\mathrm{cutoff}}-n_{\mathrm{missing}}-1},& \mathrm{Eq}.4\end{array}$
where β is an exponential smoothing constant and the initial condition is defined as:

[0019] $\begin{array}{cc}{S}_1=\frac{\sum _{j=1}^N{\left(X_{1,j}-B_{1,j}\right)}^2}{N-1}\times \frac{M}{M-1}.& \mathrm{Eq}.5\end{array}$
When X_n,j=0, X_n,j is assigned the value B_n,j. Notably, the outliers are excluded in estimating the variance. The variable n_cutoff is the number of outliers seen in the nth week and n_missing is the number of missing data points in the nth week.

[0020] In one embodiment, when n_cutoff>N/2, the baseline profile is re-computed rather than updated. If half the data points are abnormal, then there might be some fundamental change in the data to which the algorithm needs to adapt. The baseline profile is re-computed in the same manner as the baseline profile is initialized. Essentially, the current week's data is used to build a new baseline and ignore all the historical data. Thresholds for triggering alarms for the (n+1)st week are determined from k√{square root over (S_n)} (Eq. 7), where k is greater than three. Multiple thresholds correspond to different threat levels by varying k. D_cutoff is used to determine if the data point is discarded as an outlier. D_cutoff may be smaller than the threshold. For example, D_cutoff may be equal to k₁√{square root over (S_n)} and the threshold may be equal to k₂√{square root over (S_n)}, where k₁<k₂.

[0021] FIG. 2 is a flow diagram depicting an exemplary embodiment of a method 200 for detecting anomalies in aggregated volume counts for traffic of interest in accordance with one or more aspects of the invention. The traffic of interest may be traffic flows, packets, or bytes received or transmitted over a connection. The traffic of interest may be limited to a particular application associated with the traffic, such traffic associated with different IP ports (e.g., port 80 for hypertext transfer protocol (HTTP)). The method 200 may be performed by the anomaly detection module 110. Notably, the anomaly detection module 110 may execute the method 200 for each of a plurality of different types of traffic of interest.

[0022] The method 200 begins at step 202, where an initial baseline profile, an initial variance, and one or more initial thresholds are computed using initial aggregated volume data for the traffic of interest. The initial baseline profile is obtained using a moving average of the initial aggregated volume data for a particular week. The initial baseline profile may be computed using Equation 2 and the initial variance may be computed using Equation 5. The initial threshold(s) are computed from the initial variance using Equation 7. The initial aggregated volume data should be for a clean week (e.g., a week without any major security events or holidays). At step 204, an aggregated volume count is obtained for the next time period in the current week. As discussed above, the current week is divided into a series of time periods. In one embodiment, a time period comprises an hour, yielding 7*24=168 time periods and thus 168 aggregated volume counts are obtained per week. Those skilled in the art will appreciate that other durations may be used for the time periods instead of hours.

[0023] At step 206, the aggregated volume count is compared with a baseline profile value for the same period. For example, the difference shown in Equation 3 is computed and compared to one or more thresholds. At step 208, a determination is made whether a difference exceeds any threshold. If so, the method 200 proceeds to step 210, where an alarm is issued. The alarm may indicate which threshold has been exceeded (e.g., multiple thresholds may be defined in accordance with multiple severity levels). The method 200 proceeds from step 210 to step 212. If the difference does not exceed any threshold at step 208, the method 200 proceeds to step 212, where the aggregated volume count for this period is stored. Notably, if the aggregated volume count triggered an alarm, then the aggregated volume count is flagged. As discussed above, missing data and alarmed data points are disregarded in the variance/threshold updates.

[0024] At step 214, a determination is made whether the week has ended. The week ends when the aggregated volume count has been obtained for the last period in the week. If the week has not ended, the method 200 returns to step 204 and repeats for the next time period in the current week. If the week has ended at step 214, the method 200 proceeds to step 216. At step 216, a determination is made whether a number of outliers in the stored aggregated volume data for the previous week exceeds a threshold. For example, as discussed above, if half of the aggregated volume counts are abnormal, then there might be some fundamental change in the data to which the algorithm needs to adapt.

[0025] If the number of outliers does not exceed the threshold, the method 200 proceeds to step 218. At step 218, the baseline profile, the variance, and the threshold(s) are updated using the stored aggregated volume data for the previous week. The baseline profile may be updated using Equation 1. The variance may be updated using Equation 4. The new threshold(s) may be computed using Equation 7. The method 200 then returns to step 204 and repeats for the next week. If the number of outliers exceeds the threshold at step 216, the method 200 proceeds to step 220. At step 220, a new baseline, a new variance, and new threshold(s) are computed using the stored aggregated volume data for the previous week. The new baseline, new variance, and new threshold(s) may be computed in the same manner as the initial baseline, initial variance, and initial threshold(s) are computed at step 202. The method 200 then returns to step 204 and repeats for the next week.

[0026] For purposes of clarity by example, the baseline profile is computed on a weekly basis. Those skilled in the art will appreciate that the baseline profile may be computed using time intervals of any duration. In general, each time interval includes a series of time periods during which aggregated volume counts are obtained. Baseline profiles, variances, and threshold(s) are updated or recomputed upon the end of the time inverval.

[0027] FIG. 3 is a block diagram depicting an exemplary embodiment of the anomaly detection module 110 in accordance with one or more aspects of the invention. The anomaly detection module 110 includes an initialization module 302, an alarm module 203, and an update module 306. The initialization module 302 is configured to receive aggregated volume data for an initial week (data 308) and a configuration file 310. The configuration file 310 includes a parameter list for each type of traffic of interest. For example, an entry in the configuration file 310 may include fields for type of traffic, the exponential smoothing constant for the baseline update (α), the exponential smoothing constant for the variance update (β), and one or more values for indicating the severity of an exceeded threshold. The configuration file 310 may include multiple entries for multiple types of traffic to monitor. The data 308 may include aggregated volume data for multiple types of traffic. The initialization module 302 determines an initial baseline profile, an initial variance, and initial threshold(s) for each entry in the configuration file. The initial results are stored in a database 312.

[0028] The alarm module 304 is configured to receive new aggregated volume counts periodically (data 314) and baseline and threshold data from the database 312. For each type of traffic being monitored, the alarm module 304 compares a current aggregated volume count with a baseline profile value for the same period last week and triggers an alarm if the difference exceeds any of the thresholds. The alarm module 304 is configured to store the aggregated volume counts in a database 316. The alarm module 304 is configured to provide an indication to the update module 306 when last period of the week has been processed.

[0029] The update module 306 is configured to receive aggregated volume data for the previous week from a database 316. For each type of traffic being monitored, the update module 306 updates the baseline profile, the variance, and the threshold(s) using the data from the database 316. The update module 306 is also configured to re-compute a particular baseline and associated variance and threshold(s) if a certain number of alarms are triggered during the previous week.

[0030] FIG. 4 is a block diagram depicting an exemplary embodiment of a computer 400 configured to implement the processes and methods described herein. The computer 400 may be used to implement the anomaly detection module 110 and perform the method 200. The computer 400 includes a processor 401, a memory 403, various support circuits 404, and an I/O interface 402. The processor 401 may be any type processing element known in the art, such as microprocessor. The support circuits 404 for the processor 401 include conventional cache, power supplies, clock circuits, data registers, I/O interfaces, and the like. The I/O interface 402 may be directly coupled to the memory 403 or coupled through the processor 401. The I/O interface 402 may be coupled to various input devices 412 and output devices 411, such as a conventional keyboard, mouse, printer, and the like.

[0031] The memory 403 may store all or portions of one or more programs and/or data to implement the processes and methods described herein. Notably, the memory 403 may store program code to be executed by the processor 401 for performing the method 200 of FIG. 2 and implementing the anomaly detection module 110 of FIG. 3. Although one or more aspects of the invention are disclosed as being implemented as a computer executing a software program, those skilled in the art will appreciate that the invention may be implemented in hardware, software, or a combination of hardware and software. Such implementations may include a number of processors independently executing various programs and dedicated hardware, such as ASICs.

[0032] The computer 400 may be programmed with an operating system, which may be OS/2, Java Virtual Machine, Linux, Solaris, Unix, Windows, Windows95, Windows98, Windows NT, and Windows2000, WindowsME, and WindowsXP, among other known platforms. At least a portion of an operating system may be disposed in the memory 403. The memory 403 may include one or more of the following random access memory, read only memory, magneto-resistive read/write memory, optical read/write memory, cache memory, magnetic read/write memory, and the like, as well as signal-bearing media as described below.

[0033] An aspect of the invention is implemented as a program product for use with a computer system. Program(s) of the program product defines functions of embodiments and can be contained on a variety of signal-bearing media, which include, but are not limited to: (i) information permanently stored on non-writable storage media (e.g., read-only memory devices within a computer such as CD-ROM or DVD-ROM disks readable by a CD-ROM drive or a DVD drive); (ii) alterable information stored on writable storage media (e.g., floppy disks within a diskette drive or hard-disk drive or read/writable CD or read/writable DVD); or (iii) information conveyed to a computer by a communications medium, such as through a computer or telephone network, including wireless communications. The latter embodiment specifically includes information downloaded from the Internet and other networks. Such signal-bearing media, when carrying computer-readable instructions that direct functions of the invention, represent embodiments of the invention.

[0034] While the foregoing is directed to embodiments of the present invention, other and further embodiments of the invention may be devised without departing from the basic scope thereof, and the scope thereof is determined by the claims that follow.