Scalable and Reliable Collaborative Spam Filters: Harnessing the Global Social Email Networks.
Joseph S. Kong, P. Oscar Boykin, Behnam Rezaei, Nima Sarshar, Vwani Roychowdhury · 2005
We introduce a collaborative anti-spam system that is based on pervasive global social email networks. Essentially, we provide a solution to this open research problem: given a network of N users who are willing to share information collaboratively (e.g. the digests or fingerprints of known spams), how do we search for each user's content efficiently and reliablyinadistributedmannerwithminimal traffic cost on the network? As a solution to this open problem, our proposed system employs the percolation search process, which makes the traffic generated due to queries for spam digests scale sublinearly as a function of N. However, in order to reap the benefits of this novel percolation search algorithm, the node degree distribution of the underlying network must be heavy-tailed. Interestingly, latent global social email networks comprising of personal contacts possess a power-law heavy-tailed degree distribution, which renders itself an ideal natural platform to employ the percolation search algorithm. As a result, our proposed distributed spam filter requires no dedicated peer-to-peer (P2P) systems or centralized server-based systems. We have performed large-scale simulations and we find that the system achieves a spam detection rate close to 100%, while the false positive rate is kept around zero. The bandwidth cost per user as well as the system-wide bandwidth cost are shown to be very low.