Bayesian Filtering: The Spam Fights Back

by Charles Miller on September 4, 2003

eviction televises acquiring humbler pompous excresence bangor teleprocessing cousins plush pollock admirations microword abner excavating powderpuff postorder armata braveness scorers european ideology humerus portrays accrues schizophrenic exasperate cotyledons plot borderland $RANDOM IZE adopters savoring hours excavations postpone brakes playwright eutectic hospitalized poorly adorns termwise crisis expirations seaman scowls adrenaline militia scoria

That's a portion of the content of a spam I just received. The subject-line of the spam was "credulity", and the body was an HTML file containing two long lists of words such as the above (styled to be invisible in a web browser) surrounding an inline image, which I assume would have contained the spam's real payload, if I had viewed it.

As described in Paul Graham's A Plan for Spam, Bayesian spam filtering determines the probability that a particular email is spam by examining the words used in the email: words that are used often in spam but rarely in normal email (like "viagra") push the score up, words that are rarely used in spam but common in normal email push the score down.

This email was obviously written with such filters in mind. It's seeded with around 150 random, long words of the kind that you'd not expect to find in a spam, but that are varied enough that it's quite likely that at least some of them will be in your filter as high indicators of non-spamness.

Even worse, marking such emails as spam will increase the probability of false positives in the future. If you receive a lot of these mails, certain rare words will be associated very highly with spam by your filter. Then, when you get an innocent-seeming email from a friend that happens to contain the words "schizophrenic pompous playwright", that will be enough to get it black-holed.

Amusingly enough, this email would likely be shot down by a filter because of the method it uses to hide the words in the HTML file. It's only a first attempt, though. Spammers will get better at it. So long as the spammer's dictionary is big enough, and they regularly rotate their words, this could be an effective technique to weaken Bayesian filtering on two fronts: increasing both its false-negatives and false-positives.

One problem (one that Graham admits to) is that Bayesian classification assumes that the elements of the object being classified (in this case, the words of the email) are independent of each other. This is a troublesome assumption to make about language, in that the filter can't tell that the list of words does not match the patterns we would normally recognise as the language of a legitimate email.

On the other hand, if we had a more sophisticated linguistic filter, it wouldn't be hard for spammers to come up with a program that generated random, but grammatically correct sentences.

It's a war of escalation.

Previously: Reverse Engineering Is Not Theft

Next: The URL is Not Enough