Recognizing spam is not as easy as it might seem. For example, Yahoo! Groups put ads at the end of every e-mail, but if your users subscribe to such a group, they probably want to get the e-mail anyhow. Most users would just as soon discard any e-mail containing the word “Viagra,” but if you’re a pharmaceutical company, that might not be a wise policy. Press releases look a whole lot like spam, but discarding them would be a real problem for a working journalist.
Early spam-fighting products relied largely on keyword filtering to spot dubious messages, on the theory that words like “Viagra” and “FREE Offer” and “unsubscribe” only appeared in spam. There are two problems with this approach. First, unlikely though it may be, such words do appear in legitimate e-mail as well. Second, spammers quickly caught on and started sending mail with creative spellings such as “V1agra” and “FREEE Offer” and “un$ubscribe.”
The spam-fighting landscape changed dramatically in August 2002, when Paul Graham published his article “A Plan for Spam” on the Internet (www.paulgraham.com/spam.html). Graham proposed a method of detecting spam by what’s known as Bayesian statistical analysis. While you should go read the article for details, the basic idea is surprisingly simple. Start with a large corpus of spam and a large corpus of “ham” (good e-mail), say several thousand messages of each. Now count the individual words that appear in each corpus. What you’re looking for is words that tend to appear more often in spam than ham, or vice versa. For example, these days the word “Abacha” in my mail occurs exclusively in spam (of the Nigerian swindle variety), while the word “galleys” turns up only in ham (when my editors want me to review galley proofs). By looking at every word in every message, you can build up an extensive list of words and their probabilities of occurring in spam messages. Some words (like “Abacha” and “galley”) have a very high or very low probability of occurring in spam, while others (like “the” or “home”) are distributed pretty evenly.
When a new message arrives, the Bayesian algorithm compares the words in the message to those already in your corpus, looking for the most interesting (defined as having a high or low probability of occurring in spam) 15 or 20 words. Looking at the probabilities of those individual words, you can come up with a probability that the message containing the words is spam. If that probability is high enough, you can be nearly sure that the message was, in fact, spam.
Soon after Graham published his results, Bayesian spam filters started appearing—first on the client and in POP3 proxies, and then later on the server. Bayesian filters now boast a spam recognition rate of 95 percent or better in many settings. The experimental CRM-114 implementation (crm114.sourceforge.net) refines the Bayesian notion for a recognition rate over 99 percent.
The nice thing about Bayesian filters is that it doesn’t really matter what the spammers do; as long as their mail is different from real mail, the filter will learn to recognize it. Word substitutions, for example, end up working against the spammer; the likelihood that a message containing “V1agra” is spam is nearly 100 percent, and after the first few times that goes by, a good Bayesian filter will automatically stamp messages containing that word as spam.
