Detecting distributed scans using high-performance query-driven visualization

ABSTRACT

Modern forensic analytics applications, like network traffic analysis, perform high-performance hypothesis testing, knowledge discovery and data mining on very large datasets. One essential strategy to reduce the time required for these operations is to select only the most relevant data records for a given computation. In this paper, we present a set of parallel algorithms that demonstrate how an efficient selection mechanism -- bitmap indexing -- significantly speeds up a common analysis task, namely, computing conditional histogram on very large datasets. We present a thorough study of the performance characteristics of the parallel conditional histogram algorithms. As a case study, we compute conditional histograms for detecting distributed scans hidden in a dataset consisting of approximately 2.5 billion network connection records. We show that these conditional histograms can be computed on interactive time scale (i.e., in seconds). We also show how to progressively modify the selection criteria to narrow the analysis and find the sources of the distributed scans.

REFERENCES

• 1: P. Amsden , J. Amweg , P. Calato , S. Bensley , G. Lyons, Cabletron's Light-weight Flow Admission Protocol Specification Version 1.0, RFC Editor, 1997
• 2: Bellman, R. 1961. Adaptive Control Processes: A Guided Tour. Princeton University Press.
• 3: Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
• 4: Berchtold, S., Jagadish, H. V., and Ross, K. A. 1998. Independence diagrams: A technique for visual data mining. In Proc. 4th Int. Conf. Knowledge Discovery and Data Mining, KDD, AAAI Press, R. Agrawal, P. E. Stolorz, and G. Piatetsky-Shapiro, Eds., 139--143.
• 5: Bethel, E. W., Campbell, S., Dart, E., Stockinger, K., and Wu, K. 2006. Accelerating network traffic analysis using query-driven visualization. In IEEE Symposium on Visual Analytics Science and Technology, IEEE Computer Society Press.
• 6: Brun, R., and Rademarkers, F. 1997. Root -- an object oriented data analysis framework. In Proceedings of the AIHENP 1996 Workshop, 81--86.
• 7: Burrescia, J., and Johnston, W., 2005. Esnet status update. Internet2 International Meeting.
• 8: Chee-Yong Chan , Yannis E. Ioannidis, Bitmap index design and evaluation, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.355-366, June 01-04, 1998, Seattle, Washington, United States
• 9: Kenneth C. Cox , Stephen G. Eick , Taosong He, 3D geographic network displays, ACM SIGMOD Record, v.25 n.4, p.50-54, Dec. 1996 [doi>10.1145/245882.245901]
• 10: Experiment, B., 2006. The babar experiment. http://wwwpublic.slac.stanford.edu/babar/.
• 11: Mike Fisk , George Varghese, Agile and scalable analysis of network events, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637245]
• 12: Fisk, M., Smith, S. A., Weber, P., Kothapally, S., and Caudell, T. 2003. Immersive Network Monitoring. In Proceedings of the 2003 Passive and Active Measurement Workshop.
• 13: Steve Romig, The OSU Flow-tools Package and CISCO NetFlow Logs, Proceedings of the 14th USENIX conference on System administration, December 03-08, 2000, New Orleans, Louisiana
• 14: Carrie Gates , Michael Collins , Michael Duggan , Andrew Kompanek , Mark Thomas, More Netflow Tools for Performance and Security, Proceedings of the 18th USENIX conference on System administration, November 14-19, 2004, Atlanta, GA
• 15: John R. Goodall , Wayne G. Lutters , Penny Rheingans , Anita Komlodi, Preserving the Big Picture: Visual Network Traffic Analysis with TN, Proceedings of the IEEE Workshops on Visualization for Computer Security, p.6, October 26-26, 2005 [doi>10.1109/VIZSEC.2005.17]
• 16: Grinstein, G., Keim, D., and Ward, M., 2002. Information visualization, visual data mining, and its application to drug design. IEEE Visualization 2002 Course #1 Notes, October.
• 17: Harry Hochheiser , Ben Shneiderman, Interactive Exploration of Time Series Data, Proceedings of the 4th International Conference on Discovery Science, p.441-446, November 25-28, 2001
• 18: Ioannidis, Y. 2003. The history of histograms (abridged). In International Conference on Very Large Data Bases.
• 19: Jacobsen, V., Leres, C., and McCanne, S., 1989. tcpdump. ftp://ftp.ee.lbl.gov/.
• 20: Theodore Johnson, Performance Measurements of Compressed Bitmap Indices, Proceedings of the 25th International Conference on Very Large Data Bases, p.278-289, September 07-10, 1999
• 21: Daniel A. Keim , Hans-Peter Krigel, VisDB: Database Exploration Using Multidimensional Visualization, IEEE Computer Graphics and Applications, v.14 n.5, p.40-49, September 1994 [doi>10.1109/38.310723]
• 22: Kindlmann, G. 1999. Semi-Automatic Generation of Transfer Functions for Direct Volume Rendering. Master's thesis, Cornell University.
• 23: Kitware, Inc. 2003. The Visualization Toolkit User's Guide, January.
• 24: Donald Ervin Knuth, The Art of Computer Programming, 2nd Ed. (Addison-Wesley Series in Computer Science and Information, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1978
• 25: Anita Komlodi , Penny Rheingans , Utkarsha Ayachit , John R. Goodall , Amit Joshi, A User-centered Look at Glyph-based Security Visualization, Proceedings of the IEEE Workshops on Visualization for Computer Security, p.3, October 26-26, 2005 [doi>10.1109/VIZSEC.2005.1]
• 26: Kornexl, S., Paxson, V., Dreger, H., Feldmann, A., and Sommer, R. 2005. Building a time machine for efficient recording and retrieval of high-volume network traffic. In Internet Measurement Conference.
• 27: Eleftherios E. Koutsofios , Stephen C. North , Russell Truscott , Daniel A. Keim, Visualizing large-scale telecommunication networks and services (case study), Proceedings of the conference on Visualization '99: celebrating ten years, p.457-461, October 1999, San Francisco, California, United States
• 28: Kiran Lakkaraju , William Yurcik , Adam J. Lee, NVisionIP: netflow visualizations of system state for security situational awareness, Proceedings of the 2004 ACM workshop on Visualization and data mining for computer security, October 29-29, 2004, Washington DC, USA [doi>10.1145/1029208.1029219]
• 29: Stephen Lau, The Spinning Cube of Potential Doom, Communications of the ACM, v.47 n.6, June 2004 [doi>10.1145/990680.990699]
• 30: M. S. Levoy, Display of surfaces from volume data, University of North Carolina at Chapel Hill, Chapel Hill, NC, 1990
• 31: Livnat, Y., Agutter, J., Moon, S., Erbacher, R., and Foresti, S. 2005. A visual paradigm for network intrusion detection. In IEEE Workshop on Information Assurance And Security.
• 32: William E. Lorensen , Harvey E. Cline, Marching cubes: A high resolution 3D surface construction algorithm, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.163-169, July 1987
• 33: Nelson Max, Optical Models for Direct Volume Rendering, IEEE Transactions on Visualization and Computer Graphics, v.1 n.2, p.99-108, June 1995 [doi>10.1109/2945.468400]
• 34: McCanne, S., Leres, C., and Jacobsen, V., 1994. libpcap. ftp://ftp.ee.lbl.gov/.
• 35: Patrick S. McCormick , Jeff Inman , James P. Ahrens , Charles Hansen , Greg Roth, Scout: A Hardware-Accelerated System for Quantitatively Driven Visualization and Analysis, Proceedings of the conference on Visualization '04, p.171-178, October 10-15, 2004 [doi>10.1109/VIS.2004.95]
• 36: Jonathan McPherson , Kwan-Liu Ma , Paul Krystosk , Tony Bartoletti , Marvin Christensen, PortVis: a tool for port-based detection of security events, Proceedings of the 2004 ACM workshop on Visualization and data mining for computer security, October 29-29, 2004, Washington DC, USA [doi>10.1145/1029208.1029220]
• 37: Gregory M. Nielson , Bernd Hamann, The asymptotic decider: resolving the ambiguity in marching cubes, Proceedings of the 2nd conference on Visualization '91, October 22-25, 1991, San Diego, California
• 38: Oetiker, T., 2006. Multi router traffic grapher. http://mrtg.hdl.com/.
• 39: Oetiker, T., 2006. Round robin database tool. http://oss.oetiker.ch/rrdtool/.
• 40: Patrick O'Neil , Dallan Quass, Improved query performance with variant indexes, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.38-49, May 11-15, 1997, Tucson, Arizona, United States
• 41: Patrick E. O'Neil, Model 204 Architecture and Performance, Proceedings of the 2nd International Workshop on High Performance Transaction Systems, p.40-59, September 28-30, 1987
• 42: Paxson, V. 1998. Bro: A system for detecting network intruders in real-time. In Proceedings of the 7th USENIX Security Symposium.
• 43: P. Phaal , S. Panchen , N. McKee, InMon Corporation's sFlow: A Method for Monitoring Traffic in Switched and Routed Networks, RFC Editor, 2001
• 44: Dave Plonka, FlowScan: A Network Traffic Flow Reporting and Visualization Tool, Proceedings of the 14th USENIX conference on System administration, December 03-08, 2000, New Orleans, Louisiana
• 45: Products, E. S., 2006. The fast light toolkit. http://www.fltk.org.
• 46: R3vis, 1999-2006. OpenRM Scene Graph. http://www.openrm.org.
• 47: Scientific Data Management Group, L. B. N. L., 2006. Fastbit. http://sdm.lbl.gov/fastbit.
• 48: Shoshani, A., Bernardo, L., Nordberg, H., Rotem, D., and Sim, A. 1999. Multidimensional indexing and query coordination for tertiary storage management. In International Conference on Scientific and Statistical Database Management, IEEE Computer Society. 1998. Proceedings of the 1998 ACM SIGMOD: International Conference on Management of Data, ACM Press, New York, NY, USA.
• 49: Kurt Stockinger , Dirk Düllmann , Wolfgang Hoschek , Erich Schikuta, Improving the Performance of High-Energy Physics Analysis through Bitmap Indices, Proceedings of the 11th International Conference on Database and Expert Systems Applications, p.835-845, September 04-08, 2000
• 50: Kurt Stockinger , Kesheng Wu , Scott Campbell , Stephen Lau , Mike Fisk , Eugene Gavrilov , Alex Kent , Christopher E. Davis , Rick Olinger , Rob Young , Jim Prewett , Paul Weber , Thomas P. Caudell , E. Wes Bethel , Steve Smith, Network Traffic Analysis With Query Driven Visualization SC 2005 HPC Analytics Results, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.72, November 12-18, 2005 [doi>10.1109/SC.2005.47]
• 51: Stockinger, K., Shalf, J., Wu, K., and Bethel, E. W. 2005. Query-driven visaulization of large data sets. In Proceedings of IEEE Visualization.
• 52: Stockinger, K., Wu, K., Brun, R., and Canal, P. 2006. Bitmap indices for fast end-user physics analysis in root. Nuclear Instruments and Methods in Physics Research, Section A - Accelerators, Spectrometers, Detectors and Associated Equipment 559, 99--102.
• 53: Systems, C., 2005. Cisco netflow collection engine. http://www.cisco.com/en/US/products/sw/netmgtsw/ps1964/.
• 54: Thomas, J. J., and Eds., K. A. C. 2005. Illuminating the Path -- The Research and Development Agenda for Visual Analytics. IEEE Computer Society Press.
• 55: Uphoff, B., and Criscuolo, P. 2004. A framework for collection and management of intrusion detection data sets. In Proceedings of the 16th Annual FIRST Conference on Computer Security Incident Handling.
• 56: Colin Ware, Information Visualization: Perception for Design, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004
• 57: Kesheng Wu , Ekow J. Otoo , Arie Shoshani, A performance comparison of bitmap indexes, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502689]
• 58: Wu, K., Otoo, E., and Shoshani, A. 2004. On the performance of bitmap indices for high cardinality attributes. In Proceedings of the International Conference on Very Large Data Bases.
• 59: Kesheng Wu , Ekow J. Otoo , Arie Shoshani, Optimizing bitmap indices with efficient compression, ACM Transactions on Database Systems (TODS), v.31 n.1, p.1-38, March 2006 [doi>10.1145/1132863.1132864]
• 60: Xiaoxin Yin , William Yurcik , Michael Treaster , Yifan Li , Kiran Lakkaraju, VisFlowConnect: netflow visualizations of link relationships for security situational awareness, Proceedings of the 2004 ACM workshop on Visualization and data mining for computer security, October 29-29, 2004, Washington DC, USA [doi>10.1145/1029208.1029214]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

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

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: Graphical user interfaces (GUI)

General Terms:
Algorithms, Design, Security

Keywords:
data mining, network connection analysis, network security, query-driven visualization, visual analytics