MultiResolution Anomaly Detection for Long Range Dependent Time Series

Lingsong Zhang

November 13, 2006

This is the website for the paper "MultiResolution Anomaly Detection for Long Range Dependent Time Series". It is still under construction.

Here is the slides in JSM 2006. I have the chapter 4 of my thesis proposal, which can be treated as the preprint of the future paper. If you need this part, you can email me for it. To cite this part, you can use either of the following two.(.pdf)

Another slides for the job talk at University of North Carolina at Wilmington. This is a comprehensive presentation about the multiresolution anomaly detection method. For more information of this paper, please come here later for preprint and other possible talk slides. (.pdf)

1. Zhang, L., (2007) Functional Singular Value Decomposition and MultiResolution Anomaly Detection, Ph.D. thesis, Department of Statistics and Operations Research, University of North Carolina at Chapel Hill.

2. Zhang, L., Zhu, Z., and Marron, J. S., (2006) MultiResolution Anomaly Detection for Long Range Dependent Time Series, in preparation, University of North Carolina at Chapel Hill.

Two types of aggregation

In this paper, we proposed two simple ways to form multiscale time series. One is called Non-Overlapping Window Aggregation (NOWA), and the other is called Sliding Window Aggregation (SWA). The basic ideas for these two aggregations are described as following

Non-Overlapping Window Aggregation

Sliding Window Aggregation

Important theoretical properties

  1. The multiscale time series (based on NOWA) are fractional Gaussian noise with the same Hurst parameter as the original input (finest scale) time series.

  2. The marginal distribution of each cell in the outlier map (based on either NOWA or SWA) is standard Normal.

  3. The test threshold based on MRAD are conservative than the threshold based on single scale.

  4. The MRAD procedure has larger power than the average power based on single scales.

  5. The asymptotic threshold can be developed, and it is more aggressive than the usual Bonferroni procedure.

  6. An improved test threshold can be developed, and it is more aggressive than the asymptotic threshold.

Evaluation and Applications

  1. FDR, and FNR, using fractional Gaussian noise simulations

    To evaluate our analysis, we simulated fractional Gaussian noise as the background trace, and input local mean level shift into the trace. In our analysis, the Hurst parameter of a fractional Gaussian noise is set to be 0.5, 0.7, 0.9 and 0.99. The mean of the level shift is set to be a number between 0 and 1, i.e., the intensity of the mean level shift is smaller than one standard deviation of the whole trace. (Otherwise, the structure change or the anomalies are rather obvious by eye). The starting point of the level shift is simulated from a Uniform distribution, and is set to be in the first half of the time series. The duration of the level shift is simulated from the usual exponential distribution with a given parameter. These settings correspond to a low intensity attacks with rather long duration. The distribution of the starting point of an attack, or the duration of the attack, are potential future research problem.

  2. White noise and usual short range dependent time series

    This is to show that, even for short range dependent time series, our MRAD method can also be efficient to detect level shift type of outliers.

  3. Semi-experiments

    In fact, it is hard to get labeled data from the real world, because the network traces are really large data set, and it will take a lot of time to dig out what actually happened in the trace. In our research, with the help of the UNC Internet Data Study Group, a three-hour network trace was collected. After this, some pre-defined “bad” flows were filtered out. Thus, we can get a so-call “good” trace as the background normal trace. We use the center one hour as the background trace in the analysis. In the lab, several different types of network anomalies are simulated, and injected into the background noise. We will use our method to detect those anomalies, and evaluate the usefulness of the MRAD method.

  4. Real application

    This is to show more visualization tools of MRAD outlier detection procedure.

Important references

  1. Barford, P., Kline, J., Plonka, D., and Ron, A. (2002), “A Signal Analysis of Network Traffic Anomalies,” in Proceedings of the 2nd ACM SIGCOMM Workshop on Internet Measurement, pp. 71–82.

  2. Barnett, V. and Lewis, T. (1994), Outliers in Statistical Data, John Wiley & Sons, 3rd ed.

  3. Benjamini, Y. and Hochberg, Y. (1995), “Controlling the False Discovery Rate: a Practical and Powerful Approach to Multiple Testing,” Journal of Royal Statistical Society, Series B, 57, 289–300.

  4. Box, G. E. P. and Tiao, G. C. (1975), “Intervention Analysis with Applications to Economic and Environmental Problems,” Journal of the American Statistical Association, 70, 70–79.

  5. Chang, I., Tiao, G. C., and Chen, C. (1988), “Estimation of Time Series Parameters in the Presence of Outliers,” Technometrics, 30, 193–204.

  6. Fox, A. J. (1972), “Outliers in Time Series,” Journal of the Royal Statistical Society. Series B, 34, 350–363.

  7. Jeffay, K. (2005), “Course Website for COMP 290: Network Intrusion Detection,” Course of Department of Computer Science in the University of North Carolina at Chapel Hill. Materials are available at˜jeffay/courses/nidsS05/.

  8. Leadbetter, M. R., Lindgren, G., and Rootz´en, H. (1983), Extremes and Related Properties of Random Sequences and Processes, Springer-Verlag.

  9. Leland, W. E., Taqqu, M. S., Willinger, W., and Wilson, D. V. (1994), “On the Self-Similar Nature of Ethernet Traffic (Extended Version),” IEEE/ACM Transactions on Networking, 2, 1–15.

  10. McHugh, J. (2001), “Intrusion and Intrusion Detection,” International Journal of Information Security, 1, 14–35.

  11. Lakhina, A., Crovella, M., and Diot, C. (2004a), “Characterization of Network-Wide Anomalies in Traffic Flows,” in Proceedings of the ACM/SIGCOMM Internet Measurement Conference, pp. 201–206.

  12. Lakhina, A., Crovella, M., and Diot, C. (2004b), “Diagnosing Network-Wide Traffic Anomalies,” in ACM SIGCOMM Computer Communication Review, vol. 34, pp. 219–230.

  13. Lakhina, A., Papagiannaki, K., Crovella, M., Diot, C., Kolaczyk, E. D., and Taft, N. (2004c), “Structural Analysis of Network Traffic Flows,” in ACM SIGMETRICS Performance Evaluation Review, vol. 32, pp. 61–72.

  14. Willinger, W., Taqqu, M. S., Sherman, R., and Wilson, D. V. (1997), “Self-Similarity Through High-Variability: Statistical Analysis of Ethernet LAN Traffic at the Source Level,” IEEE/ACM Transactions on Networking, 3, 71–86.