Diagnosing network-wide traffic anomalies

ABSTRACT

Anomalies are unusual and significant changes in a network's traffic levels, which can often span multiple links. Diagnosing anomalies is critical for both network operators and end users. It is a difficult problem because one must extract and interpret anomalous patterns from large amounts of high-dimensional, noisy data.In this paper we propose a general method to diagnose anomalies. This method is based on a separation of the high-dimensional space occupied by a set of network traffic measurements into disjoint subspaces corresponding to normal and anomalous network conditions. We show that this separation can be performed effectively by Principal Component Analysis.Using only simple traffic measurements from links, we study volume anomalies and show that the method can: (1) accurately detect when a volume anomaly is occurring; (2) correctly identify the underlying origin-destination (OD) flow which is the source of the anomaly; and (3) accurately estimate the amount of traffic involved in the anomalous OD flow.We evaluate the method's ability to diagnose (i.e., detect, identify, and quantify) both existing and synthetically injected volume anomalies in real traffic from two backbone networks. Our method consistently diagnoses the largest volume anomalies, and does so with a very low false alarm rate.

REFERENCES

• 1: 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]
• 2: Jake D. Brutlag, Aberrant Behavior Detection in Time Series for Network Monitoring, Proceedings of the 14th USENIX conference on System administration, December 03-08, 2000, New Orleans, Louisiana
• 3: NetFlow. At www.cisco.com/warp/public/732/Tech/netflow/.
• 4: D. Donoho and G. Flesia and N. El-Karoui and M. Elad. Inferring Sparse Causes for Extreme Network Events. In Network Modeling and Simulation Workshop at Dartmouth College, 2002.
• 5: R. Dunia and S. J. Qin. Multi-dimensional Fault Diagnosis Using a Subspace Approach. In American Control Conference, 1997.
• 6: R. Dunia and S. J. Qin. A subspace approach to multidimensional fault identification and reconstruction. American Institute of Chemical Engineers (AIChE) Journal, pages 1813--1831, 1998.
• 7: Frank Feather , Dan Siewiorek , Roy Maxion, Fault detection in an Ethernet network using anomaly signature matching, Conference proceedings on Communications architectures, protocols and applications, p.279-288, September 13-17, 1993, San Francisco, California, United States
• 8: Anja Feldmann , Albert Greenberg , Carsten Lund , Nick Reingold , Jennifer Rexford , Fred True, Deriving traffic demands for operational IP networks: methodology and experience, IEEE/ACM Transactions on Networking (TON), v.9 n.3, p.265-280, June 2001 [doi>10.1109/90.929850]
• 9: G. Golub and C. F. V. Loan. Matrix Computations. The Johns Hopkins University Press.
• 10: Cynthia S. Hood , Chuanyi Ji, Proactive Network Fault Detection, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.1147, April 09-11, 1997
• 11: J. E. Jackson and G. S. Mudholkar. Control procedures for residuals associated with Principal Component Analysis. Technometrics, pages 341--349, 1979.
• 12: D. R. Jensen and H. Solomon. A Gaussian Approximation to the Distribution of a Definite Quadratic Form. J. of the American Statistical Association, pages 898--902, 1972.
• 13: Irene Katzela , Mischa Schwartz, Schemes for fault identification in communication networks, IEEE/ACM Transactions on Networking (TON), v.3 n.6, p.753-764, Dec. 1995 [doi>10.1109/90.477721]
• 14: 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]
• 15: A. Lakhina, M. Crovella, and C. Diot. Characterization of Network-Wide Anomalies in Traffic Flows. Technical Report BUCS-2004-020, Boston University, 2004.
• 16: Anukool Lakhina , Konstantina Papagiannaki , Mark Crovella , Christophe Diot , Eric D. Kolaczyk , Nina Taft, Structural analysis of network traffic flows, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 17: A. A. Lazar, W. Wang, and R. Deng. Models and algorithms for network fault detection and identification: A review. In ICC, 1992.
• 18: A. Medina , N. Taft , K. Salamatian , S. Bhattacharyya , C. Diot, Traffic matrix estimation: existing techniques and new directions, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 19: M. Misra, H. H. Yue, S. J. Qin, and C. Ling. Multivariate process monitoring and fault diagnosis by multi-scale PCA. Computers and Chemical Engineering, pages 1281--1293, 2002.
• 20: Marc Moonen , Paul van Dooren , Joos Vandewalle, A singular value decomposition updating algorithm for subspace tracking, SIAM Journal on Matrix Analysis and Applications, v.13 n.4, p.1015-1038, Oct. 1992 [doi>10.1137/0613061]
• 21: Matthew Roughan , Tim Griffin , Morley Mao , Albert Greenberg , Brian Freeman, Combining routing and traffic data for detection of IP forwarding anomalies, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 22: Juniper Traffic Sampling. At www.juniper.net/techpubs/software/junos/junos60/swconfig60-policy/html/sampling-overview.html.
• 23: Y. Vardi. Network Tomography: Estimating Source-Destination Traffic Intensities from Link Data. J. of the American Statistical Association, pages 365--377, 1996.
• 24: N. Ye. A Markov Chain Model of Temporal Behavior for Anomaly Detection. In Workshop on Information Assurance and Security, 2000.
• 25: Yin Zhang , Matthew Roughan , Carsten Lund , David Donoho, An information-theoretic approach to traffic matrix estimation, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863990]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations

General Terms:
Measurement, Performance, Security

Keywords:
anomaly detection, network traffic analysis