A Generalized Bloom Filter to Secure Distributed Network Applications

Distributed applications use Bloom filters to transmit large sets in a compact form. However, attackers can easily disrupt these applications by using or advertising saturated filters. In this paper, the authors introduce the Generalized Bloom Filter (GBF), a space-efficient data structure to securely represent a set in distributed applications, such as IP traceback, web caching, and peer-to-peer networks. Different from the standard Bloom filter, the GBF has an upper bound on the false-positive probability, limiting the effect of these attacks. The key idea of the GBF is to not only set, but also reset bits of the filter at each insertion.