Payload Attribution via Hierarchical Bloom Filters

• Version to appear at the ACM Symp. on Communication and Computer Security (CCS'04).
• Slides (with very small modifications and a few additions) presented at the Symposium. ,

Abstract: The anonymous nature of IP networks makes it difficult to identify the perpetrators of attacks and cybercrimes on the Internet. Over the years several methods have been proposed to identify the sources of attacks based on novel packet marking schemes. Despite its obvious benefits, no significant effort has been put forth into developing a method to trace a packet to its source based on its payload. In this paper, we introduce the payload attribution problem: given a query string, determine if this string was a portion of the payload of a packet, over some network segment in a given time window; if so, determine also what was the packet header. We present a digesting method based on Bloom filters capable of performing such an attribution, that has both low memory footprint and reasonable processing speeds, and yet achieves low false positive rates (the effectiveness increases with the size and specificity of the query string). The method is robust against certain packet transformations and flexible enough to be used if the query string is spread across several payloads as well. Performance analysis of the proposed method and experimental results from a prototype system are presented, as well as some applications to network forensics.

Related Publications:

• Fornet, with Kulesh Shanmugasundaram, Nasir Memon, and Anubhav Savant.