Unveiling core network-wide communication patterns through application traffic activity graph decomposition

ABSTRACT

As Internet communications and applications become more complex,operating, managing and securing networks have become increasingly challenging tasks. There are urgent demands for more sophisticated techniques for understanding and analyzing the behavioral characteristics of network traffic. In this paper, we study the network traffic behaviors using traffic activity graphs (TAGs), which capture the interactions among hosts engaging in certain types of communications and their collective behavior. TAGs derived from real network traffic are large, sparse, yet seemingly complex and richly connected, therefore difficult to visualize and comprehend. In order to analyze and characterize these TAGs, we propose a novel statistical traffic graph decomposition technique based on orthogonal nonnegative matrix tri-factorization (tNMF) to decompose and extract the core host interaction patterns and other structural properties. Using the real network traffic traces, we demonstrate that our tNMF-based graph decomposition technique produces meaningful and interpretable results. It enables us to characterize and quantify the key structural properties of large and sparse TAGs associated with various applications, and study their formation and evolution.

REFERENCES

• 1: Yin Zhang , Sumeet Singh , Subhabrata Sen , Nick Duffield , Carsten Lund, Online identification of hierarchical heavy hitters: algorithms, evaluation, and applications, Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, October 25-27, 2004, Taormina, Sicily, Italy [doi>10.1145/1028788.1028802]
• 2: Thomas Karagiannis , Andre Broido , Michalis Faloutsos , Kc claffy, Transport layer identification of P2P traffic, Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, October 25-27, 2004, Taormina, Sicily, Italy [doi>10.1145/1028788.1028804]
• 3: James Newsome , Brad Karp , Dawn Song, Polygraph: Automatically Generating Signatures for Polymorphic Worms, Proceedings of the 2005 IEEE Symposium on Security and Privacy, p.226-241, May 08-11, 2005 [doi>10.1109/SP.2005.15]
• 4: Andrew W. Moore , Denis Zuev, Internet traffic classification using bayesian analysis techniques, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 5: 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]
• 6: 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
• 7: Thomas Karagiannis , Konstantina Papagiannaki , Michalis Faloutsos, BLINC: multilevel traffic classification in the dark, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 8: Kuai Xu , Zhi-Li Zhang , Supratik Bhattacharyya, Profiling internet backbone traffic: behavior models and applications, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 9: Marios Iliofotou , Prashanth Pappu , Michalis Faloutsos , Michael Mitzenmacher , Sumeet Singh , George Varghese, Network monitoring using traffic dispersion graphs (tdgs), Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, October 24-26, 2007, San Diego, California, USA [doi>10.1145/1298306.1298349]
• 10: Graphviz. http://www.graphviz.org/.
• 11: Chris Ding , Tao Li , Wei Peng , Haesun Park, Orthogonal nonnegative matrix t-factorizations for clustering, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150420]
• 12: D. Lee and H. Seung. Learning the parts of objects. by non-negative matrix factorization. In Nature, 1999.
• 13: D. Lee and H. Seung. Algorithms for non-negative matrix factorization. In Proc. of NIPS, 2000.
• 14: Wei Xu , Xin Liu , Yihong Gong, Document clustering based on non-negative matrix factorization, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860485]
• 15: Hyunsoo Kim , Haesun Park, Extracting unrecognized gene relationships from the biomedical literature via matrix factorizations using a priori knowledge of gene relationships, Proceedings of the 1st international workshop on Text mining in bioinformatics, November 10-10, 2006, Arlington, Virginia, USA [doi>10.1145/1183535.1183549]
• 16: Tao Li , Chris Ding, The Relationships Among Various Nonnegative Matrix Factorization Methods for Clustering, Proceedings of the Sixth International Conference on Data Mining, p.362-371, December 18-22, 2006 [doi>10.1109/ICDM.2006.160]
• 17: Inderjit S. Dhillon, Co-clustering documents and words using bipartite spectral graph partitioning, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.269-274, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502550]
• 18: MX Toolbox Blacklists. http://www.mxtoolbox.com/blacklists.aspx.
• 19: J. Stewart. Inside the storm: Protocols and encryption of the storm botnet. http://www.blackhat.com/presentations/bh-usa-08/Stewart/BH_US_08_Stewart_Protocols_of_the_Storm.pdf.
• 20: Y. Jia and J. Hoberock and M. Garland and J. Hart. On the visualization of social and other scale-free networks. In Proc. of IEEE InfoVis, 2008.
• 21: Xintian Yang , Sitaram Asur , Srinivasan Parthasarathy , Sameep Mehta, A visual-analytic toolkit for dynamic interaction graphs, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1402011]
• 22: M.E.J. Newman. Detecting community structure in networks. In Eur. Phys. J. B 38, 321--330, 2004.
• 23: Yon Dourisboure , Filippo Geraci , Marco Pellegrini, Extraction and classification of dense communities in the web, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242635]
• 24: Jure Leskovec , Kevin J. Lang , Anirban Dasgupta , Michael W. Mahoney, Statistical properties of community structure in large social and information networks, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367591]
• 25: P. McDaniel, S. Sen, O. Spatscheck, J. Van der Merwe, B. Aiello, and C. Kalmanek. Enterprise security: a community of interest based approach. In Proc. of NDSS, 2006.
• 26: Inderjit S. Dhillon , Subramanyam Mallela , Dharmendra S. Modha, Information-theoretic co-clustering, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956764]
• 27: Deepayan Chakrabarti , Spiros Papadimitriou , Dharmendra S. Modha , Christos Faloutsos, Fully automatic cross-associations, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014064]

INDEX TERMS

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

General Terms:
Measurement, Security

Keywords:
anomaly detection, application classification, graph decomposition, nonnegative matrix factorization, traffic graph