Bayesian poisoning

Last updated

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.

Contents

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 errors) 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.

Empirical results

Graham-Cumming

At the Spam Conference held at MIT in 2004 John Graham-Cumming presented two possible attacks on POPFile's Bayesian engine. [1] 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.

Wittel and Wu

At the Conference on Email and Anti-Spam in 2004, Wittel and Wu presented a paper [2] 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. [3]

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 University, [4] 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 [5] 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 (non-spam email content) 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.

See also

Related Research Articles

<span class="mw-page-title-main">Checksum</span> Data used to detect errors in other data

A checksum is a small-sized block of data derived from another block of digital data for the purpose of detecting errors that may have been introduced during its transmission or storage. By themselves, checksums are often used to verify data integrity but are not relied upon to verify data authenticity.

Bogofilter is a mail filter that classifies e-mail as spam or ham (non-spam) by a statistical analysis of the message's header and content (body). The program is able to learn from the user's classifications and corrections. It was originally written by Eric S. Raymond after he read Paul Graham's article "A Plan for Spam" and is now maintained together with a group of contributors by David Relson, Matthias Andree and Greg Louis.

<span class="mw-page-title-main">Apache SpamAssassin</span> Open-source e-mail spam filter

Apache SpamAssassin is a computer program used for e-mail spam filtering. It uses a variety of spam-detection techniques, including DNS and fuzzy checksum techniques, Bayesian filtering, external programs, blacklists and online databases. It is released under the Apache License 2.0 and is a part of the Apache Foundation since 2004.

Various anti-spam techniques are used to prevent email spam.

<span class="mw-page-title-main">Email spam</span> Unsolicited electronic advertising by e-mail

Email spam, also referred to as junk email, spam mail, or simply spam, is unsolicited messages sent in bulk by email (spamming). The name comes from a Monty Python sketch in which the name of the canned pork product Spam is ubiquitous, unavoidable, and repetitive. Email spam has steadily grown since the early 1990s, and by 2014 was estimated to account for around 90% of total email traffic.

CRM114 is a program based upon a statistical approach for classifying data, and especially used for filtering email spam.

<span class="mw-page-title-main">Naive Bayes spam filtering</span>

Naive Bayes classifiers are a popular statistical technique of e-mail filtering. They typically use bag-of-words features to identify email spam, an approach commonly used in text classification.

A word salad, or schizophasia, is a "confused or unintelligible mixture of seemingly random words and phrases", most often used to describe a symptom of a neurological or mental disorder. The term schizophasia is used in particular to describe the confused language that may be evident in schizophrenia. The words may or may not be grammatically correct, but are semantically confused to the point that the listener cannot extract any meaning from them. The term is often used in psychiatry as well as in theoretical linguistics to describe a type of grammatical acceptability judgement by native speakers, and in computer programming to describe textual randomization.

A Joe job is a spamming technique that sends out unsolicited e-mails using spoofed sender data. Early Joe jobs aimed at tarnishing the reputation of the apparent sender or inducing the recipients to take action against them, but they are now typically used by commercial spammers to conceal the true origin of their messages and to trick recipients into opening emails apparently coming from a trusted source.

A bounce message or just "bounce" is an automated message from an email system, informing the sender of a previous message that the message has not been delivered. The original message is said to have "bounced".

Email filtering is the processing of email to organize it according to specified criteria. The term can apply to the intervention of human intelligence, but most often refers to the automatic processing of messages at an SMTP server, possibly applying anti-spam techniques. Filtering can be applied to incoming emails as well as to outgoing ones.

A low-probability-of-intercept radar (LPIR) is a radar employing measures to avoid detection by passive radar detection equipment while it is searching for a target or engaged in target tracking. This characteristic is desirable in a radar because it allows finding and tracking an opponent without alerting them to the radar's presence. This also protects the radar installation from anti-radiation missiles (ARMs).

Email harvesting or scraping is the process of obtaining lists of email addresses using various methods. Typically these are then used for bulk email or spam.

Within the probability theory Markov model, Markovian discrimination in spam filtering is a method used in CRM114 and other spam filters to model the statistical behaviors of spam and nonspam more accurately than in simple Bayesian methods. A simple Bayesian model of written text contains only the dictionary of legal words and their relative probabilities. A Markovian model adds the relative transition probabilities that given one word, predict what the next word will be. It is based on the theory of Markov chains by Andrey Markov, hence the name. In essence, a Bayesian filter works on single words alone, while a Markovian filter works on phrases or entire sentences.

A hash buster is a program which randomly adds characters to data in order to change the data's hash sum.

A directory harvest attack (DHA) is a technique used by spammers in an attempt to find valid/existent e-mail addresses at a domain by using brute force. The attack is usually carried out by way of a standard dictionary attack, where valid e-mail addresses are found by brute force guessing valid e-mail addresses at a domain using different permutations of common usernames. These attacks are more effective for finding e-mail addresses of companies since they are likely to have a standard format for official e-mail aliases.

Since Internet users and system administrators have deployed a vast array of techniques to block, filter, or otherwise banish spam from users' mailboxes and almost all Internet service providers forbid the use of their services to send spam or to operate spam-support services, special techniques are employed to deliver spam emails. Both commercial firms and volunteers run subscriber services dedicated to blocking or filtering spam.

Stockade is a TCP-layer blocking tool written in C++. It denies TCP/IP access to registered IP addresses by using the ipfw packet filter. It targets spam prevention, but may also be used against other attackers

<span class="mw-page-title-main">Gary Robinson</span> American software engineer and mathematician

Gary Robinson is an American software engineer and mathematician and inventor notable for his mathematical algorithms to fight spam. In addition, he patented a method to use web browser cookies to track consumers across different web sites, allowing marketers to better match advertisements with consumers. The patent was bought by DoubleClick, and then DoubleClick was bought by Google. He is credited as being one of the first to use automated collaborative filtering technologies to turn word-of-mouth recommendations into useful data.

People tend to be much less bothered by spam slipping through filters into their mail box, than having desired e-mail ("ham") blocked. Trying to balance false negatives vs false positives is critical for a successful anti-spam system. As servers are not able to block all spam there are some tools for individual users to help control over this balance.

References

  1. ↑ "Archived copy". Archived from the original on 2006-10-12. Retrieved 2006-11-24.{{cite web}}: CS1 maint: archived copy as title (link)
  2. ↑ "Archived copy" (PDF). Archived from the original (PDF) on 2013-04-29. Retrieved 2012-02-13.{{cite web}}: CS1 maint: archived copy as title (link)
  3. ↑ "The spambayes-dev September 2004 Archive by thread".
  4. ↑ "Technical Reports - Faculty of Computer Science".
  5. ↑ "Archived copy" (PDF). www.ceas.cc. Archived from the original (PDF) on 20 March 2022. Retrieved 30 June 2022.{{cite web}}: CS1 maint: archived copy as title (link)
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.