Evaluation and Application of Bloom Filters in Computer Network Security

Abstract

Unstructured Peer-to-Peer (P2P) networks for content distribution are decentralized and robust. Searching for content in the network is based on the Gnutella Protocol. Broadcast Updates Look-up Search Protocol (BULLS) reverses Gnutella and enables a local look-up search at the cost of storing all the files shared in the network. In this thesis we introduce the use of bloom filters in the design and evaluation of a data structure that reduces space and search time in P2P networks based on BULLS. We also discuss the main ideas of a new Space Efficient Local Look-up Search (SELLS) protocol that is based on BULLS and uses this new data structure. The new data structured is called the Inverse Bloom Filter (IBF) and uses bloom filters. A bloom filter is a space efficient probabilistic structure for membership queries. That is, they can be used to efficiently determine if a file is stored at a host. The cost is a small probability of error called false positive. The challenge is to evaluate the search efficiency (i.e., remember searches that have not been successful) of bloom filters as the primary data structure of SELLS. The empirical evaluation can be achieved using real file names from a P2P network and determining the false positive rate of the bloom filter. Novel applications of SELLS could possibly include secure key distribution; building block towards securing P2P networks.