Bayesian poisoning
Encyclopedia
Bayesian poisoning is a technique used by e-mail spammers
to attempt to degrade the effectiveness of spam filters that rely on Bayesian spam filtering
. Bayesian filtering relies on Bayesian probability
to determine whether an incoming mail is spam or is not spam. The spammer hopes that the addition of random (or even carefully selected) words that are unlikely to appear in a spam message will cause the spam filter to believe the message to be legitimate—a statistical type II error.
Spammers also hope to cause the spam filter to have a higher false positive rate by turning previously innocent words into spammy words in the Bayesian database (statistical type I error) because a user who trains their spam filter on a poisoned message will be indicating to the filter that the words added by the spammer are a good indication of spam.
's Bayesian engine. One was unsuccessful and the other worked, but was impractical. In doing this they identified two types of poisoning attack: passive (where words are added without any feedback to the spammer) and active (where the spammer gets feedback after the spam has been received).
The passive method of adding random words to a small spam was ineffective as a method of attack: only 0.04% of the modified spam messages were delivered. The active attack involved adding random words to a small spam and using a web bug
to determine whether the spam was received. If it was, another Bayesian system was trained using the same poison words. After sending 10,000 spams to a single user he determined a small set of words that could be used to get a spam through.
The simple countermeasure of disabling remote images (web bugs) in emails eliminates this problem.
in 2004, Wittel and Wu presented a paper in which they showed that the passive addition of random words to spam was ineffective against CRM114, but effective against SpamBayes
with 100 words added per spam.
They also showed that a smarter passive attack, adding common English words, was still ineffective against CRM114, but was even more effective against SpamBayes. They needed to add only 50 words to a spam to get it past SpamBayes.
However, Wittel and Wu's testing has been criticized due to the minimal header information that was present in the emails they were using; most Bayesian spam filters make extensive use of header information and other message metadata in determining the likelihood that a message is spam. A discussion of the SpamBayes results and some counter evidence can be found in the SpamBayes mailing list archive.
All of these attacks are type II attacks: attacks that attempt to get spam delivered. A type I attack attempts to cause false positives by turning previously innocent words into spammy words in the Bayesian database.
, in which they detailed a passive type II attack. They added common English words to spam messages used for training and testing a spam filter.
In two tests they showed that these common words decreased the spam filter's precision (the percentage of messages classified as spam that really are spam) from 84% to 67% and from 94% to 84%. Examining their data shows that the poisoned filter was biased towards believing messages were more likely to be spam than "ham" (good email), thus increasing the false positive rate.
They proposed two countermeasures: ignoring common words when performing classification, and smoothing probabilities based on the trustworthiness of a word. A word has a trustworthy probability if an attacker is unlikely to be able to guess whether it is part of an individual's vocabulary. Thus common words are untrustworthy and their probability would be smoothed to 0.5 (making them neutral).
They demonstrated that adding hammy words - words that are more likely to appear in ham than spam - was effective against a naïve Bayesian filter, and enabled spam to slip through. They went on to detail two active attacks (attacks that require feedback to the spammer) that were very effective against the spam filters. Of course, preventing any feedback to spammers (such as non-delivery reports, SMTP level errors or web bugs) defeats an active attack trivially.
They also showed that retraining the filter was effective at preventing all the attack types, even when the retraining data had been poisoned.
The published research shows that adding random words to spam messages is ineffective as a form of attack, but that active attacks are very effective and that adding carefully chosen words can work in some cases. To defend against these attacks it is vital that no feedback is received by spammers and that statistical filters are retrained regularly.
The research also shows that continuing to investigate attacks on statistical filters is worthwhile. Working attacks have been demonstrated and countermeasures are required to ensure that statistical filters remain accurate.
Spam (electronic)
Spam is the use of electronic messaging systems to send unsolicited bulk messages indiscriminately...
to attempt to degrade the effectiveness of spam filters that rely on Bayesian spam filtering
Bayesian spam filtering
Bayesian spam filtering is a statistical technique of e-mail filtering. It makes use of a naive Bayes classifier to identify spam e-mail.Bayesian classifiers work by correlating the use of tokens , with spam and non spam e-mails and then using Bayesian inference to calculate a probability that an...
. Bayesian filtering relies on Bayesian probability
Bayesian probability
Bayesian probability is one of the different interpretations of the concept of probability and belongs to the category of evidential probabilities. The Bayesian interpretation of probability can be seen as an extension of logic that enables reasoning with propositions, whose truth or falsity is...
to determine whether an incoming mail is spam or is not spam. The spammer hopes that the addition of random (or even carefully selected) words that are unlikely to appear in a spam message will cause the spam filter to believe the message to be legitimate—a statistical type II error.
Spammers also hope to cause the spam filter to have a higher false positive rate by turning previously innocent words into spammy words in the Bayesian database (statistical type I error) because a user who trains their spam filter on a poisoned message will be indicating to the filter that the words added by the spammer are a good indication of spam.
Graham-Cumming and Brighenti
At the Spam Conference held at MIT in 2006 John Graham-Cumming and Stefano Brighenti presented two possible attacks on POPFilePOPFile
POPFile is a free, open source, cross-platform mail filter originally written in Perl by John Graham-Cumming and maintained by a team of volunteers. It uses a naive Bayes classifier to filter mail. This allows the filter to "learn" and classify mail according to the user's preferences. Typically...
's Bayesian engine. One was unsuccessful and the other worked, but was impractical. In doing this they identified two types of poisoning attack: passive (where words are added without any feedback to the spammer) and active (where the spammer gets feedback after the spam has been received).
The passive method of adding random words to a small spam was ineffective as a method of attack: only 0.04% of the modified spam messages were delivered. The active attack involved adding random words to a small spam and using a web bug
Web bug
A web bug is an object that is embedded in a web page or e-mail and is usually invisible to the user but allows checking that a user has viewed the page or e-mail. One common use is in e-mail tracking. Alternative names are web beacon, tracking bug, and tag or page tag...
to determine whether the spam was received. If it was, another Bayesian system was trained using the same poison words. After sending 10,000 spams to a single user he determined a small set of words that could be used to get a spam through.
The simple countermeasure of disabling remote images (web bugs) in emails eliminates this problem.
Wittel and Wu
At the Conference on Email and Anti-SpamConference on Email and Anti-Spam
The Conference on Email and Anti-Spam is an annual scientific conference sponsored by Microsoft on subjects relating to email use and abuse . The CEAS hosts a concurrent open competition for spam filters known as the CEAS Live Spam Filter Challenge.The first conference was held on July 30-31, 2004...
in 2004, Wittel and Wu presented a paper in which they showed that the passive addition of random words to spam was ineffective against CRM114, but effective against SpamBayes
SpamBayes
SpamBayes is a Bayesian spam filter written in Python which uses techniques laid out by Paul Graham in his essay "A Plan for Spam". It has subsequently been improved by Gary Robinson and Tim Peters, among others....
with 100 words added per spam.
They also showed that a smarter passive attack, adding common English words, was still ineffective against CRM114, but was even more effective against SpamBayes. They needed to add only 50 words to a spam to get it past SpamBayes.
However, Wittel and Wu's testing has been criticized due to the minimal header information that was present in the emails they were using; most Bayesian spam filters make extensive use of header information and other message metadata in determining the likelihood that a message is spam. A discussion of the SpamBayes results and some counter evidence can be found in the SpamBayes mailing list archive.
All of these attacks are type II attacks: attacks that attempt to get spam delivered. A type I attack attempts to cause false positives by turning previously innocent words into spammy words in the Bayesian database.
Stern, Mason and Shepherd
Also in 2004 Stern, Mason and Shepherd wrote a technical report at Dalhousie UniversityDalhousie University
Dalhousie University is a public research university located in Halifax, Nova Scotia, Canada. The university comprises eleven faculties including Schulich School of Law and Dalhousie University Faculty of Medicine. It also includes the faculties of architecture, planning and engineering located at...
, in which they detailed a passive type II attack. They added common English words to spam messages used for training and testing a spam filter.
In two tests they showed that these common words decreased the spam filter's precision (the percentage of messages classified as spam that really are spam) from 84% to 67% and from 94% to 84%. Examining their data shows that the poisoned filter was biased towards believing messages were more likely to be spam than "ham" (good email), thus increasing the false positive rate.
They proposed two countermeasures: ignoring common words when performing classification, and smoothing probabilities based on the trustworthiness of a word. A word has a trustworthy probability if an attacker is unlikely to be able to guess whether it is part of an individual's vocabulary. Thus common words are untrustworthy and their probability would be smoothed to 0.5 (making them neutral).
Lowd and Meek
At the 2005 Conference on Email and Anti-Spam Lowd and Meek presented a paper in which they demonstrated that passive attacks adding random or common words to spam were ineffective against a naïve Bayesian filter. (In fact, they showed, as John Graham-Cumming demonstrated back in 2004, that adding random words improves the spam filtering accuracy.)They demonstrated that adding hammy words - words that are more likely to appear in ham than spam - was effective against a naïve Bayesian filter, and enabled spam to slip through. They went on to detail two active attacks (attacks that require feedback to the spammer) that were very effective against the spam filters. Of course, preventing any feedback to spammers (such as non-delivery reports, SMTP level errors or web bugs) defeats an active attack trivially.
They also showed that retraining the filter was effective at preventing all the attack types, even when the retraining data had been poisoned.
The published research shows that adding random words to spam messages is ineffective as a form of attack, but that active attacks are very effective and that adding carefully chosen words can work in some cases. To defend against these attacks it is vital that no feedback is received by spammers and that statistical filters are retrained regularly.
The research also shows that continuing to investigate attacks on statistical filters is worthwhile. Working attacks have been demonstrated and countermeasures are required to ensure that statistical filters remain accurate.
External Links
- Does Bayesian Poisoning Exist? (registration required)