Spam e-mails have become a serious technological and economic problem. Up to now, by deploying complementary anti-spam measures, we have been reasonably able to withstand spam e-mails and use the Internet for regular communication. However, if we are to avert the danger of losing the Internet e-mail service in its capacity as a valuable, free and worldwide medium of open communication, anti-spam activities should be performed more systematically than is currently the case regarding the mainly heuristic, anti-spam measures in place. A formal framework, within which the existing delivery routes that a spam e-mail may take, and antispam measures and their effectiveness can be investigated, will perhaps encourage a shift in methodology and pave the way for new, holistic anti-spam measures. This paper presents a model of the Internet e-mail infrastructure as a directed graph and a deterministic finite automaton and draws on automata theory to formally derive the spam delivery routes. The most important anti-spam measures are then described. Methods controlling only specific delivery routes are evaluated in terms of how effectively they cover the modeled e-mail infrastructure; methods operating independently of any particular routes ceive a more general assessment.

Dwork, C., Goldberg, A. and Naor, M. (2002), "On Memory-Bound Functions for Fighting Spam", Microsoft Research Report, http://research.microsoft.com/research/sv/PennyBlack/demo/lbdgn.pdf.

Dwork, C. and Naor, M. (1993), "Pricing Via Processing Or Combatting Junk Mail", Lecture Notes in Computer Science, 740: 137-147.

Freier, A. O., Karlton, P. and Kocher, P. C. (1996), "The SSL protocol version 3.0", Internet draft.

Graham, P. (2002), 'A Plan for Spam', http://www.paulgraham.com/spam.html, August 2002.

Hall, R.. (1996), 'Channels: Avoiding Unwanted Electronic Mail'. DIMACS Symposium on Network Threats. Nov 6-8. Piscataway, N.J.

Harris, E. (2003), 'The Next Step in the Spam Control War: Greylisting', http://projects.puremagic.com/greylisting/.

ICANN (2004), 'New sTLD RFP Application .mail', http://www.icann.org/tlds/stld-apps-19mar04/mail.htm, 19 April 2004.

Ilett, D. (2004), 'Most spam generated by botnets, says expert', http://news.zdnet.co.uk/internet/security/0,39020375,39167561,00.htm, 22 September 2004.

Ioannidis, J. (2003), 'Fighting Spam by Encapsulating Policy in Email Addresses'. 10th Annual Network and Distributed System Security Symposium. February 2003. San Diego, California.

Levine, J. et al. (2004), 'Lightweight MTA Authentication Protocol (LMAP) Discussion and Comparison'. Internet Draft.

Mori, G. and Malik, J. (2003), 'Recognizing Objects in Adversarial Clutter: Breaking a Visual CAPTCHA'. 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, June 16-22, Wisconsin.

MessageLabs (2005), 'Monthly Report April 2005', http://www.messagelabs.com/emailthreats/intelligence/reports/monthlies/april05/default.asp, April 2005.

RFC 1730, Crispin, M. (1994), 'Internet Message Access Protocol - Version 4'. IETF Network Working Group.

RFC 1939, Myers, J. and Rose, M. (1996), 'Post office protocol - version 3'. IETF Network Working Group.

RFC 2033, Myers, J. (1996), 'Local Mail Transfer Protocol'. IETF Network Working Group.

RFC 2034, Freed, N. (1996), 'SMTP Service Extension for Returning Enhanced Error Codes'. IETF Network Working Group.

RFC 2476, Gellens, R. and Klensin, J. (1998), 'Message Submission'. IETF Network Working Group.

RFC 2554, Myers, J. (1996), 'SMTP Service Extension for Authentication'. IETF Network Working Group.

RFC 2616, Gettys, J., Mogul, J., Frystyk, H., Masinter, L. and Leach, P. (1999), 'Hypertext Transfer Protocol - HTTP/1.1'. IETF Network Working Group.

RFC 2821, Klensin, J. (2001), 'Simple Mail Transfer Protocol'. IETF Network Working Group.

RFC 2852, Newman, D. (2000), 'Deliver By SMTP Service Extension'. IETF Network Working Group.

RFC 3207, Hoffman, P. (2002), 'SMTP Service Extension for Secure SMTP over Transport Layer Security'. IETF Network Working Group.

Sanders, T. (2005), 'Microsoft takes on spamming botnets', http://www.vnunet.com/vnunet/news/2144976/microsoft-takes-spamming.

Sandvine (2004), 'Zombie PCs spew out 80% of spam'.

Symantec (2005), 'Spam statistics', http://www.symantec.com/region/de/PressCenter/spam.html.

The Honeynet Project & Research Alliance (2005), 'Know your Enemy: Tracking Botnets - Using honeynets to learn more about Bots', http://www.honeynet.org/papers/bots/, 13 March 2005.

Yahoo (2005), 'Domain-based Email Authentication Using Public-Keys Advertised in the DNS (DomainKeys)', Internet Draft.