Payload attribution via hierarchical bloom filters

ABSTRACT

Payload attribution is an important problem often encountered in network forensics. Given an excerpt of a payload, finding its source and destination is useful for many security applications such as identifying sources and victims of a worm or virus. Although IP traceback techniques have been proposed in the literature, these techniques cannot help when we do not have the entire packet or when we only have an excerpt of the payload.

In this paper, we present a payload attribution system (PAS) that attributes reasonably long excerpts of payloads to their source and/or destination hosts. The system we propose is based on a novel data structure called a Hierarchical Bloom Filter (HBF). An HBF creates compact digests of payloads and provides probabilistic answers to membership queries on the excerpts of payloads. We also present the performance analysis of the method and experimental results from a prototype demonstrating the practicality and efficacy of the system. The system can reliably work with certain packet transformations and is flexible enough to be used if the query string is spread across several packets. The system, however, can be evaded by splitting or by "stuffing" the payload. Future work focuses on making the system robust against such evasions.

REFERENCES

• 1: Infinistream. http://www.networkgeneral.com/.
• 2: Snort. http://www.snort.org/.
• 3: C. J. Antonelli , M. Undy , Peter Honeyman, The Packet Vault: Secure Storage of Network Data, Proceedings of the Workshop on Intrusion Detection and Network Monitoring, p.103-109, April 09-12, 1999
• 4: S. M. Bellovin, M. Leech, and T. Taylor. ICMP traceback messages. In Internet Draft draft-ietf-itrace-01.txt (Work in progress). IETF, Oct 2001.
• 5: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 6: A. Broder and M. Mitzenmatcher. Network applications of bloom filters: A survey. In Annual Allerton Conference on Communication, Control, and Computing, Urbana-Champaign, Illinois, USA, October 2002.
• 7: H. Brönnimann, K. Shanmugasundaram, and N. Memon. String matching on the internet. In Workshop on Combinatorial and Algorithmic Aspects of Networking, Banf, Canada, August 2004.
• 8: Hal Burch, Tracing Anonymous Packets to Their Approximate Source, Proceedings of the 14th USENIX conference on System administration, December 03-08, 2000, New Orleans, Louisiana
• 9: CERT. Cert incident note in-2004-1. ttp://www.cert.org/incident_notes/IN-2004-01.html.
• 10: D. Dean, M. Franklin, and A. Stubblefield. An algebraic approach to IP traceback. In Proceedings of NDSS, Feb 2001.
• 11: S. Dharmapurikar, M. Attig, and J. Lockwood. Design and implementation of a string matching system for network intrusion detection using FPGA-based bloom filters. Technical Report, CSE Dept, Washington University, 2004. Saint Louis, MO.
• 12: Sandstorm Enterprises. NetIntercept. http://www.sandstorm.com/.
• 13: Li Fan , Pei Cao , Jussara Almeida , Andrei Z. Broder, Summary cache: a scalable wide-area Web cache sharing protocol, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.254-265, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 14: I. Hamadeh and G. Kesidis. Packet marking for traceback of illegal content distribution. In Proceedings of International Conference on Cross-Media Service Delivery (CMSD), Santorini, Greece, May 2003.
• 15: I. Hamadeh and G. Kesidis. Performance of ip address fragmentation strategies for ddos traceback. In Proceedings of IEEE IPCOM, Kansas City, October 2003.
• 16: Abhishek Kumar, Jun Xu, Jia Wang, Oliver Spatschek, and Li Li. Space-code bloom filter for efficient per-flow traffic measurement. In Proceedings of IEEE INFOCOM, Hong Kong, China, March 2004.
• 17: S. Kumar and E. H. Spafford. An application of pattern matching in intrusion detection. Purdue University Technical Report CSD-TR-94-013, 1994.
• 18: A. Mankin, D. Massey, C. L. Wu, S. F. Wu, and L. Zhang. On design and evaluation of "intention-driven" ICMP traceback. In Proc. IEEE International Conference on Computer Communications and Networks, Oct 2001.
• 19: S. McCreary and K. Claffy. Trends in wide area ip traffic patterns: A view from ames internet exchange. In ITC Specialist Seminar on IP Traffic Modelling, Measurement, and Management, March 2000.
• 20: Giovanni Vigna , Andrew Mitchell, Mnemosyne: Designing and Implementing Network Short-Term Memory, Proceedings of the Eighth International Conference on Engineering of Complex Computer Systems, p.91, December 02-04, 2002
• 21: Michael Mitzenmacher, Compressed bloom filters, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.144-150, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384004]
• 22: V. Paxson. Bro: A system for detecting network intruders in real-time. 7th Annual USENIX Security Symposium, January 1998.
• 23: T. H. Ptacek and T. N. Newsham. Insertion, evasion, and denial of service: Eluding network intrusion detection. Secure Networks, Inc., January 1998.
• 24: Sean C. Rhea , Kevin Liang , Eric Brewer, Value-based web caching, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775239]
• 25: Stefan Savage , David Wetherall , Anna Karlin , Tom Anderson, Practical network support for IP traceback, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.295-306, August 28-September 01, 2000, Stockholm, Sweden
• 26: K. Shanmugasundaram, A. Savant, H. Brünnimann, and N. Memon. Fornet: A distributed forensics network. In The Second International Workshop on Mathematical Methods, Models and Architectures for Computer Networks Security, St. Petersburg, Russia, October 2003.
• 27: Alex C. Snoeren, Hash-based IP traceback, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.3-14, August 2001, San Diego, California, United States
• 28: D. Song and A. Perrig. Advanced and authenticated marking schemes for IP traceback. In IEEE Infocomm, 2001.
• 29: Eugene H. Spafford, OPUS: preventing weak password choices, Computers and Security, v.11 n.3, p.273-278, May 1992 [doi>10.1016/0167-4048(92)90207-8]
• 30: S. Staniford-Chen , L. T. Heberlein, Holding intruders accountable on the Internet, Proceedings of the 1995 IEEE Symposium on Security and Privacy, p.39, May 08-10, 1995
• 31: Y. Zhang and V. Paxson. Detecting stepping stones. In Proceedings of the 9th USENIX Security Symposium, Denver, Colorado, USA, August 2000.

INDEX TERMS

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

General Terms:
Algorithms, Performance, Security

Keywords:
ForNet, hierarchical bloom filters, payload attribution, security