Reversible sketches for efficient and accurate change detection over network data streams

ABSTRACT

Traffic anomalies such as failures and attacks are increasing in frequency and severity, and thus identifying them rapidly and accurately is critical for large network operators. The detection typically treats the traffic as a collection of flows and looks for heavy changes in traffic patterns (<i>e.g.</i>, volume, number of connections). However, as link speeds and the number of flows increase, keeping per-flow state is not scalable. The recently proposed sketch-based schemes [14] are among the very few that can detect heavy changes and anomalies over massive data streams at network traffic speeds. However, sketches do not preserve the key (<i>e.g.</i>, source IP address) of the flows. Hence, even if anomalies are detected, it is difficult to infer the culprit flows, making it a big practical hurdle for online deployment. Meanwhile, the number of keys is too large to record.

To address this challenge, we propose efficient <i>reversible hashing</i> algorithms to infer the keys of culprit flows from sketches without storing any explicit key information. No extra memory or memory accesses are needed for recording the streaming data. Meanwhile, the heavy change detection daemon runs in the background with space complexity and computational time sublinear to the key space size. This short paper describes the conceptual framework of the reversible sketches, as well as some initial approaches for implementation. See [23] for the optimized algorithms in details. comment We further apply various emph IP-mangling algorithms and emph bucket classification methods to reduce the false positives and false negatives. Evaluated with netflow traffic traces of a large edge router, we demonstrate that the reverse hashing can quickly infer the keys of culprit flows even for many changes with high accuracy.

REFERENCES

• 1: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 2: Cormode, G., et al.Finding hierarchical heavy hitters in data streams. In Proc. of VLDB (2003).
• 3: 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]
• 4: Cormode, G., and Muthukrishnan, S. Improved data stream summaries: The count-min sketch and its applications. Tech. Rep. 2003-20, DIMACS, 2003.
• 5: Cormode, G., and Muthukrishnan, S. What's new: Finding significant differences in network data streams. In Proc. of IEEE Infocom (2004).
• 6: 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]
• 7: Nick Duffield , Carsten Lund , Mikkel Thorup, Flow sampling under hard resource constraints, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 8: 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
• 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: Gilbert, A. C., et al. QuickSAND: Quick summary and analysis of network data. Tech. Rep. 2001-43, DIMACS, 2001.
• 11: Gilbert, A. C., Kotidis, Y., Muthukrishnan, S., and Strauss, M. J. Quick SAND: Quick summary and analysis of network data. Tech. Rep. 2001-43, DIMACS, 2001.
• 12: Richard W. Hamming, Coding and information theory (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1986
• 13: Hofmeyr, S., and Forrest, S. Intrusion detection using sequences of system calls. Journal of Computer Security 6 (1998).
• 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: Loyall, J. P., et al. Building adaptive and agile applications using intrusion detection and response. In Proc. of NDSS (2000).
• 16: Manku, G. S., and Motwani, R. Approximate frequency counts over data streams. In Proc. of IEEE VLDB (2002).
• 17: S. Muthukrishnan, Data streams: algorithms and applications, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 18: Moore, D., et al. The spread of the Sapphire/Slammer worm. IEEE Magazine on Security and Privacy (August 2003).
• 19: S. Muthukrishnan, Data streams: algorithms and applications, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 20: 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]
• 21: Roesch, M. Snort: The lightweight network intrusion detection system, 2001. http://www.snort.org/.
• 22: Ryutov, T., Neuman, C., Kim, D., and Zhou, L. Integrated access control and intrusion detection for web servers. IEEE Trans. on Parallel and Distributed Systems 14, 9 (2003), 841--850.
• 23: Schweller, R., Chen, Y., Parsons, E., Gupta, A., Memik, G., and Zhang, Y. Reverse hashing for sketch-based change detection on high-speed networks. Tech. Rep. NWU-CS-2004-45, Northwestern University, May 2004.
• 24: Stuart Staniford , Vern Paxson , Nicholas Weaver, How to Own the Internet in Your Spare Time, Proceedings of the 11th USENIX Security Symposium, p.149-167, August 05-09, 2002
• 25: David Wagner , Drew Dean, Intrusion Detection via Static Analysis, Proceedings of the 2001 IEEE Symposium on Security and Privacy, p.156, May 14-16, 2001
• 26: Weaver, N., Paxson, V., Staniford, S., and Cunningham, R. Large scale malicious code: A research agenda. Tech. Rep. DARPA-sponsored report, 2003.
• 27: Xilinx Inc. Virtex-II Pro and Virtex-II Pro X Platform FPGAs: Complete data sheet, 2004. www.xilinx.com/bvdocs/publications/ds083.pdf.

INDEX TERMS

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

General Terms:
Algorithms, Measurement

Keywords:
IP mangling, change detection, data stream computation, modular hashing, network anomaly detection, reverse hashing, sketch