Filtering spam with behavioral blacklisting

ABSTRACT

Spam filters often use the reputation of an IP address (or IP address range) to classify email senders. This approach worked well when most spam originated from senders with fixed IP addresses, but spam today is also sent from IP addresses for which blacklist maintainers have outdated or inaccurate information (or no information at all). Spam campaigns also involve many senders, reducing the amount of spam any particular IP address sends to a single domain; this method allows spammers to stay "under the radar". The dynamism of any particular IP address begs for blacklisting techniques that automatically adapt as the senders of spam change.

This paper presents SpamTracker, a spam filtering system that uses a new technique called behavioral blacklisting to classify email senders based on their sending behavior rather than their identity. Spammers cannot evade SpamTracker merely by using "fresh" IP addresses because blacklisting decisions are based on sending patterns, which tend to remain more invariant. SpamTracker uses fast clustering algorithms that react quickly to changes in sending patterns. We evaluate SpamTracker's ability to classify spammers using email logs for over 115 email domains; we find that SpamTracker can correctly classify many spammers missed by current filtering techniques. Although our current datasets prevent us from confirming SpamTracker's ability to completely distinguish spammers from legitimate senders, our evaluation shows that SpamTracker can identify a significant fraction of spammers that current IP-based blacklists miss. SpamTracker's ability to identify spammers before existing blacklists suggests that it can be used in conjunction with existing techniques (e.g., as an input to greylisting). SpamTracker is inherently distributed and can be easily replicated; incorporating it into existing email filtering infrastructures requires only small modifications to mail server configurations.

REFERENCES

• 1: Spamhaus delisting policy, 2007. http://www.spamhaus.org/sbl/policy.html.
• 2: M. Abadi, A. Birrell, M. Burrow, F. Dabek, and T. Wobber. Bankable Postage for Network Services. In Proc. Asian Computing Science Conference, Dec. 2003.
• 3: E. Allman, J. Callas, M. Delany, M. Libbey, J. Fenton, and M. Thomas. DomainKeys Identified Mail (DKIM) Signatures, May 2007. http://www.ietf.org/rfc/rfc4871.txt.
• 4: David S. Anderson , Chris Fleizach , Stefan Savage , Geoffrey M. Voelker, Spamscatter: characterizing internet scam hosting infrastructure, Proceedings of 16th USENIX Security Symposium on USENIX Security Symposium, p.1-14, August 06-10, 2007, Boston, MA
• 5: A. Back. Hashcash. http://www.cypherspace.org/adam/hashcash/.
• 6: Alex Brodsky , Dmitry Brodsky, A distributed content independent method for spam detection, Proceedings of the first conference on First Workshop on Hot Topics in Understanding Botnets, p.3-3, April 10, 2007, Cambridge, MA
• 7: David Cheng , Ravi Kannan , Santosh Vempala , Grant Wang, A divide-and-merge methodology for clustering, ACM Transactions on Database Systems (TODS), v.31 n.4, p.1499-1525, December 2006 [doi>10.1145/1189769.1189779]
• 8: R. Clayton. Stopping Spam by Extrusion Detection. In First Conference on Email and Anti-Spam (CEAS), Mountain View, CA, July 2004.
• 9: R. Clayton. Stopping Outgoing Spam by Examining Incoming Server Logs. In Second Conference on Email and Anti-Spam (CEAS), Stanford, CA, July 2005.
• 10: Cloudmark Authority Anti-Spam. http://www.cloudmark.com/serviceproviders/authority/spam/, 2007.
• 11: Commtouch Inc. 2006 Spam Trends Report: Year of the Zombies. http://www.commtouch.com/documents/Commtouch_200_Spam_Trends_Year_of_the_Zombies.pdf.
• 12: Ernesto Damiani , Sabrina De Capitani di Vimercati , Stefano Paraboschi , Pierangela Samarati, P2P-Based Collaborative Spam Detection and Filtering, Proceedings of the Fourth International Conference on Peer-to-Peer Computing, p.176-183, August 25-27, 2004 [doi>10.1109/P2P.2004.36]
• 13: Z. Duan, K. Gopalan, and X. Yuan. Behavioral Characteristics of Spammers and Their Network Reachability Properties. In Proc. IEEE ICC, Glasgow, Scotland, June 2007.
• 14: Cynthia Dwork , Moni Naor, Pricing via Processing or Combatting Junk Mail, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.139-147, August 16-20, 1992
• 15: P. Graham. Better Bayesian Filtering. http://www.paulgraham.com/better.html.
• 16: IronPort. http://www.ironport.com/, 2007.
• 17: IronPort Carrier Grade Email Security Appliance. http://www.ironport.com/products/ironport_x1000.html, 2007.
• 18: Ravi Kannan , Santosh Vempala , Adrian Vetta, On clusterings: Good, bad and spectral, Journal of the ACM (JACM), v.51 n.3, p.497-515, May 2004 [doi>10.1145/990308.990313]
• 19: Kelly Jackson Higgins, Dark Reading. Botnets Battle Over Turf. http://www.darkreading.com/document.asp?doc_id=122116, Apr. 2007.
• 20: J. Kong et al. Scalable and Reliabile Collaborative Spam Filters: Harnessing the Global Socail Email Networks. In 3rd Annual Workshop on the Weblogging Ecosystem, 2006.
• 21: B. Laurie and R. Clayton. Proof-of-Work Proves Not to Work. In Third Annual Workshop on Economics and Information Security (WEIS), Minneapolis, MN, May 2004.
• 22: F. Li and M.-H. Hseih. An Empirical Study of Clustering Behavior of Spammers and Group-based Anti-Spam Strategies. In 3rd Conference on Email and Anti-Spam (CEAS), Mountain View, CA, July 2006.
• 23: MailAvenger, 2007. http://www.mailavenger.org/.
• 24: Mail Abuse Prevention System (MAPS). http://www.mail-abuse.com/.
• 25: Messaging Anti-Abuse Working Group. MAAWG Issues First Global Email Spam Report. http://www.prnewswire.com/cgi-bin/stories.pl?ACCT=104&STORY=/www/story/0308-2006/0004316196, Mar. 2006.
• 26: PandaLabs Blog. Zunker Spamming Bot Front-end Analysis. http://blogs.pandasoftware.com/blogs/pandalabs/archive/2007/05/08/Zunker.asx, May 2007.
• 27: V. Prakash. Vipul's Razor. http://razor.sourceforge.net/, 2007.
• 28: Pyzor. http://pyzor.sourceforge.net/, 2007.
• 29: A. Ramachandran, D. Dagon, and N. Feamster. Can DNSBLs Keep Up with Bots? In 3rd Conference on Email and Anti-Spam (CEAS), Mountain View, CA, July 2006.
• 30: Anirudh Ramachandran , Nick Feamster, Understanding the network-level behavior of spammers, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 31: Secure Computing. http://www.securecomputing.com/, 2007.
• 32: Secure Computing IronMail. http://www.securecomputing.com/index.cfm?skey=1612, 2007.
• 33: Alistair Sinclair , Mark Jerrum, Approximate counting, uniform generation and rapidly mixing Markov chains, Information and Computation, v.82 n.1, p.93-133, July 1989 [doi>10.1016/0890-5401(89)90067-9]
• 34: Spam and Open-Relay Blocking System (SORBS). http://www.sorbs.net/.
• 35: SpamAssassin, 2007. http://www.spamassassin.org/.
• 36: SpamCop. http://www.spamcop.net/.
• 37: Spamhaus, 2007. http://www.spamhaus.org/.
• 38: SpamHINTS. http://www.spamhints.org/, 2007.
• 39: Realtime uri blacklist. http://www.uribl.com/.
• 40: P. Vixie. Distributed Checksum Clearinghouse. http://www.rhyolite.com/anti-spam/dcc/, 2007.
• 41: Michael Walfish , J. D. Zamfirescu , Hari Balakrishnan , David Karger , Scott Shenker, Distributed quota enforcement for spam control, Proceedings of the 3rd conference on Networked Systems Design & Implementation, p.21-21, May 08-10, 2006, San Jose, CA
• 42: M. Wong and W. Schlitt. Sender Policy Framework (SPF) for Authorizing Use of Domains in E-Mail, Apr. 2006. RFC 4408.

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, Design, Security

Keywords:
blacklists, botnets, clustering, security, spam