Open Access Open Access  Restricted Access Subscription or Fee Access

Anomaly Detection using Spatio-Temporal Measures

Syed Azahad, R. Lakshmi Tulasi


With the development of network technology and growing enlargement of network size, the network structure is be-coming more and more complicated. Mutual interactions of different network equipment, topology configurations, transmission protocols and cooperation and competition among the network users inevitably cause the network traffic flow which is controlled by several driving factors to appear non-stationary and complicated behavior. Because of its non-stationary property it cannot easily use traditional way to analyze the complicated network traffic. We present different approaches to characterize traffic: (i) a mod-el-free approach based on the method of types and Sanov‘s theorem, (ii) a model-based approach modeling traffic using a super statistics theory (iii) another model –based approach using Markov modulated process. Using these characterizations as a reference we continuously monitor traffic and employ large deviations and decision theory re-sults to ―compare‖ the empirical measure of the monitored traffic with the corresponding reference characterization, thus, identifying traffic anomalies in real-time. According to the super statistics theory, the complex dynamic sys-tem may have a large fluctuation of intensive quantities on large time scales which cause the system to behave as non-stationary which is also the characteristic of network traffic. Partitioning the non-stationary traffic time series into small stationary segments which can be modeled by discrete Generalized Pareto (GP) distribution. Differ-ent segments follow GP distribution with different distribution para-meters which are named slow parameters. Throughout, we compare these two approaches presenting their advantages and disadvantages to identify and classify temporal network anomalies. We also demon-strate how our framework can be used to monitor traffic from mul-tiple network elements in order to identify both spatial and temporal anomalies. We validate our techniques by analyzing real traffic traces with time-stamped anomalies.


Large Deviations, Markov Processes, Method of Types, Super Statistics, Pareto Distribution, Network Traffic

Full Text:



R. A. Kemmerer and G. Vigna, Intrusion detection: A brief History and review, Computer, vol. 35, no. 4, pp. 27–30, Apr. 2002.

B. Mukherjee, L. T. Heberlein, and K. N. Levitt, Network Intrusion detection, IEEE Netw., vol. 8, no. 3, pp. 26–41, May/Jun. 1994.

Di He Leung, H. Network Intrusion Detection Using CFAR Abrupt-Change Detectors, Instrumentation and Measurement, IEEE Transac-tions on, Volume: 57, pp: 490-497, Mar 2008

R. Lippmann, D. Fried, I. Graf, J. Haines, K. Kendall, D. McClung, D.Weber, S. Webster, D. Wyschogrod, R. Cunningham, and M. Ziss-man,―Evaluating intrusion detection systems: The 1998 DARPA off-line intrusion detection evaluation,‖ in Proc. DARPA Information Surviva-bility Conf. and Expo., Los Alamitos, CA, Jan. 2000, pp. 12–26.

R. Lippmann, J. W. Haines, D. J. Fried, J. Korba, and K. Das, ―The1999 DARPA off-line intrusion detection evaluation,‖ Computer Net-works, vol. 34, no. 4, pp. 579–595, 2000.

V. Yegneswaran, J. T. Giffin, P. Barford, and S. Jha, ―An architecture for generating semantics-aware signatures,‖ in USENIX Security Symp., Baltimore, MD, Jul. 2005, pp. 97–112.

A. Dembo and O. Zeitouni, Large Deviations Techniques and Applica-tions, 2nd ed. New York: Springer-Verlag, 1998.

W. Hoeffding, ―Asymptotically optimal tests for multinomial distribu-tions,‖ Ann. Math. Statist., vol. 36, pp. 369–401, 1965.

I. Paschalidis and S. Vassilaras, ―On the estimation of buffer overflow probabilities from measurements,‖ IEEE Trans. Inf. Theory, vol. 47, no. 1, pp. 178–191, 2001.

Rasmussen, P., Ashkar, F., Rosbjerg, D., Bobe´e, B., 1994. The POT method for flood estimation: A review. In: Hipel, K.W. (Ed.), Stochas-tic and Statistical Methods in Hydrology and Environmental Engineer-ing. Kluwer Academic Publishers, pp. 15–26.. pp. 71–86, Feb. 1997.

Spatio-Temporal Network Anomaly Detection by Assessing Deviations of Empirical Measures Ioannis Ch. Paschalidis, and Georgios Smarag-dakis IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 17, NO. 3, JUNE 2009.

Rasmussen, P., Ashkar, F., Rosbjerg, D., Bobe´e, B., 1994. The POT method for flood estimation: A review. In: Hipel, K.W. (Ed.), Stochas-tic and Statistical Methods in Hydrology and Environmental Engi-neering. Kluwer Academic Publishers, pp. 15–26..

H. Hasegawa, cond-mat/0506301.

V. Paxson and S. Floyd, ―Wide Area Traffic: The Failure of Poisson Modeling,‖ IEEE/ACM Trans. Networking, vol. 3, no. 3, 1995, pp. 226–244

K. M. C. Tan and R. A. Maxion, ―Determining the operational limits of an anomaly-based intrusion detector,‖ IEEE J. Sel. Areas Commun., vol. 21, no. 1, pp. 96–110, Jan. 2003.

Dupuis, D.J., 1996. Estimating the probability of obtaining nonfeasible parameter estimates of the generalized Pareto distribution. Journal of Statistical Computation and Simulation 54, 197–209

Rasmussen, P.F., 2001. Generalized probability weighted moments: Application to the generalized Pareto distribution. Water Resources Research 37 (6), 1745– 1751.

Davison, A.C., 1984. Modeling excesses over high thresholds, with an application.‘‘ In: Statistical Extremes and Applications, ed. J. Tiago de Oliveira, Dordrecht: D. Reidel, pp. 461–482.

F. Esponda, S. Forrest, and P. Helman, ―A formal framework for positiveand negative detection schemes,‖ IEEE Trans. Syst., Man, Cybern. B,Cybern., vol. 34, no. 1, pp. 357–373, Feb. 2004.


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.