Reversible sketches: enabling monitoring and analysis over high-speed data streams

ABSTRACT

A key function for network traffic monitoring and analysis is the ability to perform aggregate queries over multiple data streams. Change detection is an important primitive which can be extended to construct many aggregate queries. The recently proposed sketches are among the very few that can detect heavy changes online for high speed links, and thus support various aggregate queries in both temporal and spatial domains. However, it does not preserve the keys (e. g., source IP address) of flows, making it difficult to reconstruct the desired set of anomalous keys.

To address this challenge, we propose the reversible sketch data structure along with reverse hashing algorithms to infer the keys of culprit flows. There are two phases. The first operates online, recording the packet stream in a compact representation with negligible extra memory and few extra memory accesses. Our prototype single FPGA board implementation can achieve a throughput of over 16 Gb/s for 40-byte packet streams (the worst case). The second phase identifies heavy changes and their keys from the representation in nearly real time. We evaluate our scheme using traces from large edge routers with OC-12 or higher links. Both the analytical and experimental results show that we are able to achieve online traffic monitoring and accurate change/intrusion detection over massive data streams on high speed links, all in a manner that scales to large key space size. To the best of our knowledge, our system is the first to achieve these properties simultaneously.

REFERENCES

• 1: 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]
• 2: [2] G. Cormode and S. Muthukrishnan, "What's new: Finding significant differences in network data streams," in Proc. IEEE INFOCOM, 2004.
• 3: Cristian Estan , George Varghese, New directions in traffic measurement and accounting, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 4: [4] G. Cormode, F. Korn, D. Srivastava, and S. Muthukrishnan, "Finding hierarchical heavy hitters in data streams," in Proc. VLDB, 2003.
• 5: Graham Cormode , Theodore Johnson , Flip Korn , S. Muthukrishnan , Oliver Spatscheck , Divesh Srivastava, Holistic UDAFs at streaming speeds, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007575]
• 6: Gurmeet Singh Manku , Rajeev Motwani, Approximate frequency counts over data streams, Proceedings of the 28th international conference on Very Large Data Bases, p.346-357, August 20-23, 2002, Hong Kong, China
• 7: [7] R. S. Tsay, "Time series model specification in the presence outliers," J. Amer. Statistical Assoc., vol. 81, pp. 132-141, 1986.
• 8: [8] G. Cormode and S. Muthukrishnan, "Improved data stream summaries: the count-min sketch and its applications," DIMACS, Tech. Rep. 2003-20, 2003.
• 9: Philippe Flajolet , G. Nigel Martin, Probabilistic counting algorithms for data base applications, Journal of Computer and System Sciences, v.31 n.2, p.182-209, Sept. 1985 [doi>10.1016/0022-0000(85)90041-8]
• 10: [10] A. Gilbert, Y. Kotidis, S. Muthukrishnan, and M. Strauss, "Quick-SAND: Quick summary and analysis of network data," DIMACS, Tech. Rep. 2001-43, 2001.
• 11: S. Muthukrishnan, Data streams: algorithms and applications, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 12: P. Indyk, Stable distributions, pseudorandom generators, embeddings and data stream computation, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.189, November 12-14, 2000
• 13: [13] G. Cormode and S. Muthukrishnan, "Estimating dominance norms on multiple data streams," in Proc. 11th Eur. Symp. Algorithms (ESA), 2003.
• 14: [14] C. R. Hadlock, Field Theory and Its Classical Problems. Washington, DC: Mathematical Assoc. America, 1978.
• 15: Yan Gao , Zhichun Li , Yan Chen, A DoS Resilient Flow-level Intrusion Detection Approach for High-speed Networks, Proceedings of the 26th IEEE International Conference on Distributed Computing Systems, p.39, July 04-07, 2006 [doi>10.1109/ICDCS.2006.6]
• 16: 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]
• 17: [17] M. Roesch, "Snort: The lightweight network intrusion detection system," , 2001 [Online]. Available: http://www. snort.org/
• 18: [18] H.Wang, D. Zhang, and K. G. Shin, "Detecting SYN flooding attacks," in Proc. IEEE INFOCOM, 2002.
• 19: Haining Wang , Danlu Zhang , Kang G. Shin, Change-Point Monitoring for the Detection of DoS Attacks, IEEE Transactions on Dependable and Secure Computing, v.1 n.4, p.193-208, October 2004 [doi>10.1109/TDSC.2004.34]
• 20: 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]
• 21: Ramana Rao Kompella , Sumeet Singh , George Varghese, On scalable attack detection in the network, Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, October 25-27, 2004, Taormina, Sicily, Italy [doi>10.1145/1028788.1028812]
• 22: [22] J. Jung, V. Paxson, A. W. Berger, and H. Balakrishnan, "Fast portscan detection using sequential hypothesis testing," in Proc. IEEE Symp. Security and Privacy, 2004.
• 23: Nicholas Weaver , Stuart Staniford , Vern Paxson, Very fast containment of scanning worms, Proceedings of the 13th conference on USENIX Security Symposium, p.3-3, August 09-13, 2004, San Diego, CA
• 24: Vinod Yegneswaran , Paul Barford , Johannes Ullrich, Internet intrusions: global characteristics and prevalence, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA
• 25: Stuart Staniford , James A. Hoagland , Joseph M. McAlerney, Practical automated detection of stealthy portscans, Journal of Computer Security, v.10 n.1-2, p.105-136, 2002
• 26: [26] SPEEDRouter vl.l Product Specification. Xilinx Inc., 2001.
• 27: [27] Synlipfy Pro. Syplicity Inc. [Online]. Available: http://www.synplicity. com
• 28: [28] Dshield.org: Distributed Intrusion Detection System. SANS Inst. [On-line]. Available: http://www.dshield.org/
• 29: Nick Duffield , Carsten Lund , Mikkel Thorup, Properties and prediction of flow statistics from sampled packet streams, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637225]
• 30: Cristian Estan , Stefan Savage , George Varghese, Automatically inferring patterns of resource consumption in network traffic, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863972]
• 31: Chris Olston , Jing Jiang , Jennifer Widom, Adaptive filters for continuous queries over distributed data streams, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872825]
• 32: Anna C. Gilbert , Sudipto Guha , Piotr Indyk , Yannis Kotidis , S. Muthukrishnan , Martin J. Strauss, Fast, small-space algorithms for approximate histogram maintenance, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509966]

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays; Algorithms implemented in hardware

  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: High-speed (e.g., FDDI, fiber channel, ATM)

  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Hash-table representations

General Terms:
Algorithms, Design, Management