Spatio-temporal network anomaly detection by assessing deviations of empirical measures

ABSTRACT

We introduce an Internet traffic anomaly detection mechanism based on large deviations results for empirical measures. Using past traffic traces we characterize network traffic during various time-of-day intervals, assuming that it is anomaly-free. We present two different approaches to characterize traffic: (i) a model-free approach based on the method of types and Sanov's theorem, and (ii) a model-based approach modeling traffic using a Markov modulated process. Using these characterizations as a reference we continuously monitor traffic and employ large deviations and decision theory results to "compare" the empirical measure of the monitored traffic with the corresponding reference characterization, thus, identifying traffic anomalies in real-time. Our experimental results show that applying our methodology (even short-lived) anomalies are identified within a small number of observations. Throughout, we compare the two approaches presenting their advantages and disadvantages to identify and classify temporal network anomalies. We also demonstrate how our framework can be used to monitor traffic from multiple network elements in order to identify both spatial and temporal anomalies. We validate our techniques by analyzing real traffic traces with time-stamped anomalies.

REFERENCES

• 1: Martin Roesch, Snort - Lightweight Intrusion Detection for Networks, Proceedings of the 13th USENIX conference on System administration, November 07-12, 1999, Seattle, Washington
• 2: Vern Paxson, Bro: a system for detecting network intruders in real-time, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.23-24, p.2435-2463, Dec. 1999 [doi>10.1016/S1389-1286(99)00112-7]
• 3: Paul Barford , Jeffery Kline , David Plonka , Amos Ron, A signal analysis of network traffic anomalies, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637210]
• 4: R. Lippmann, D. Fried, I. Graf, J. Haines, K. Kendall, D. McClung, D. Weber, S. Webster, D. Wyschogrod, R. Cunningham, and M. Zissman, "Evaluating intrusion detection systems: The 1998 DARPA off-line intrusion detection evaluation," in Proc. DARPA Information Survivability Conf. and Expo., Los Alamitos, CA, Jan. 2000, pp. 12-26.
• 5: Richard Lippmann , Joshua W. Haines , David J. Fried , Jonathan Korba , Kumar Das, The 1999 DARPA off-line intrusion detection evaluation, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.34 n.4, p.579-595, Oct. 2000 [doi>10.1016/S1389-1286(00)00139-0]
• 6: Vinod Yegneswaran , Jonathon T. Giffin , Paul Barford , Somesh Jha, An architecture for generating semantics-aware signatures, Proceedings of the 14th conference on USENIX Security Symposium, p.7-7, July 31-August 05, 2005, Baltimore, MD
• 7: A. Dembo and O. Zeitouni, Large Deviations Techniques and Applications , 2nd ed. New York: Springer-Verlag, 1998.
• 8: W. Hoeffding, "Asymptotically optimal tests for multinomial distributions," Ann. Math. Statist., vol. 36, pp. 369-401, 1965.
• 9: 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.
• 10: Ioannis Ch. Paschalidis , Spyridon Vassilaras, Model-based estimation of buffer overflow probabilities from measurements, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.154-163, June 2001, Cambridge, Massachusetts, United States
• 11: Anukool Lakhina , Mark Crovella , Christophe Diot, Diagnosing network-wide traffic anomalies, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 12: Anukool Lakhina , Mark Crovella , Christiphe Diot, Characterization of network-wide anomalies in traffic flows, Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, October 25-27, 2004, Taormina, Sicily, Italy [doi>10.1145/1028788.1028813]
• 13: Anukool Lakhina , Mark Crovella , Christophe Diot, Mining anomalies using traffic feature distributions, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 14: H. Akaike, "Information theory and an extension of the maximum likelihood principle," in Proc. 2nd Int. Symp. Information Theory, Budapest, Hungary, 1973, pp. 267-281.
• 15: Lawrence R. Rabiner, A tutorial on hidden Markov models and selected applications in speech recognition, Readings in speech recognition, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 16: O. Zeitouni, J. Ziv, and N. Merhav, "When is the generalized likelihood ratio test optimal?," IEEE Trans. Inf. Theory, vol. 38, no. 5, pp. 1597-1602, 1992.
• 17: I. C. Paschalidis and G. Smaragdakis, "A large deviations approach to statistical traffic anomaly detection," in Proc. 45th IEEE Conf. Decision and Control, San Diego, CA, 2006, pp. 1900-1905.
• 18: Jelena Mirkovic , Peter Reiher, A taxonomy of DDoS attack and DDoS defense mechanisms, ACM SIGCOMM Computer Communication Review, v.34 n.2, April 2004 [doi>10.1145/997150.997156]
• 19: Wenke Lee , Dong Xiang, Information-Theoretic Measures for Anomaly Detection, Proceedings of the 2001 IEEE Symposium on Security and Privacy, p.130, May 14-16, 2001
• 20: Balachander Krishnamurthy , Subhabrata Sen , Yin Zhang , Yan Chen, Sketch-based change detection: methods, evaluation, and applications, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948236]
• 21: Yin Zhang , Zihui Ge , Albert Greenberg , Matthew Roughan, Network anomography, Proceedings of the 5th ACM SIGCOMM conference on Internet Measurement, p.30-30, October 19-21, 2005, Berkeley, CA
• 22: Will E. Leland , Murad S. Taqqu , Walter Willinger , Daniel V. Wilson, On the self-similar nature of Ethernet traffic (extended version), IEEE/ACM Transactions on Networking (TON), v.2 n.1, p.1-15, Feb. 1994 [doi>10.1109/90.282603]
• 23: Walter Willinger , Murad S. Taqqu , Robert Sherman , Daniel V. Wilson, Self-similarity through high-variability: statistical analysis of Ethernet LAN traffic at the source level, IEEE/ACM Transactions on Networking (TON), v.5 n.1, p.71-86, Feb. 1997 [doi>10.1109/90.554723]
• 24: Mark E. Crovella , Azer Bestavros, Self-similarity in World Wide Web traffic: evidence and possible causes, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.835-846, Dec. 1997 [doi>10.1109/90.650143]
• 25: P. Abry and D. Veitch, "Wavelet analysis of long-range-dependent traffic," IEEE Trans. Inf. Theory, vol. 44, no. 1, pp. 2-15, 1998.
• 26: G. Urvoy-Keller, "On the stationarity of TCP bulk data transfers," in Proc. Passive and Active Network Measurement Workshop, Boston, MA, Mar. 2005, pp. 27-40.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network monitoring

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing; Markov processes

General Terms:
Algorithms, Design, Management, Security

Keywords:
Markov processes, large deviations, method of types, network security, statistical anomaly detection