Subject: RE: [Asrg] Filtering spam by detecting 'anti-Bayesian' elements?

From: "Brian Azzopardi" <[email-masked]>
Date: Sat, 18 Sep 2004 11:34:05 +0200

First post this...

It's actually trivial for anyone to create new nonsense words: for a typical word length of 6 characters and an alphabet of 26 letters there are 26^6 possible combinations. Which is a lot...

New words don't necessarily tip the filter towards spam. Remember: a bayesian is statistical method which calculates the probabilty of an event given the past history of that event.

If the token is new the bayesian filter has no past history to go on. Such tokens are assigned a default weight based on external assumptions. Paul Graham's well known paper assigns new tokens a slighly positive, not spammy, weight of 0.4. IMHO his stated assumption is dubious. In my implementation I assign a slightly spammy weighting, on the assumption that people's vocubulary is actually quite limited and stable over time, as opposed to that of spam.

The bigger problem for bayesian filters is not the random words. It's messages which contain extracts from literature. For these kinds of messages, using the tokens individually results in lower filtering performance. For such messages the co-occurence probability of the tokens has to be used instead. And then it wouldn't be a Naïve Bayesian filter anymore...

Brian Azzopardi

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Laird Breyer
Sent: Saturday, September 18, 2004 2:54 AM
To: ASRG
Subject: Re: [Asrg] Filtering spam by detecting 'anti-Bayesian' elements?

On Sep 17 2004, Jim Witte wrote:
>    Has anyone tried making a partial spam filter by scanning messages 
> for the non-sense words they put in to try to confuse the Bayesian 
> filters?

Those nonsense rules backfire with Bayesian filters. Since nonsense
words don't occur in legitimate messages (how is the spammer going to
force people to add such words?), all such words tip the balance
towards spam. When a filter looks up the words to see if they exist in
its database, then either the word is completely new or it has already
occurred in spam.

It's very hard for a spammer to create new nonsense words, all the
time.  After a while, some spammer (not necessarily the same) has
already used that nonsense word, and the filter knows about it.

I don't know of any open source statistical filter who has serious
trouble with nonsense words over time. They stick out like a sore
thumb. It's likely that the real purpose for including them is to
evade hash/signature filters.

-- 
Laird Breyer.

_______________________________________________
Asrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/asrg

This mail was checked for malicious code and viruses
by GFI MailSecurity. GFI MailSecurity provides email content
checking, exploit detection, threats analysis and anti-virus for
Exchange & SMTP servers. Viruses, Trojans, dangerous
attachments and offensive content are removed automatically.
Key features include: multiple virus engines; email content and
attachment checking; an exploit shield; an HTML threats engine;
a Trojan & Executable Scanner; and more.

In addition to GFI MailSecurity, GFI also produces the
GFI MailEssentials anti-spam software, the GFI FAXmaker
fax server & GFI LANguard network security product ranges.
For more information on our products, please visit
http://www.gfi.com. This disclaimer was sent by
GFI MailEssentials for Exchange/SMTP.

_______________________________________________
Asrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/asrg

---

From: Laird Breyer <[email-masked]>
Date: Sat, 18 Sep 2004 21:06:58 +1000

On Sep 18 2004, Brian Azzopardi wrote:

>  It's actually trivial for anyone to create new nonsense words: for
> a typical word length of 6 characters and an alphabet of 26 letters
> there are 26^6 possible combinations. Which is a lot...

Yes and no. In principle, 26^6 is a lot, but in practice it also
depends on other things. For example, the spammer could use (26+10)^6,
including digits, which is an even bigger set of words. Even better?

It depends on the tokenizer. If the tokenizer is alpha only, then the
chance of at least one digit is 1 - (26/36)^6 = 0.85, and this digit
can be anywhere. With one digit, the tokenizer will split the token
into two purely alpha pieces, with respective sizes (0,5), (1,4) or
(2,3). So with probability 0.85 * (4/6), the tokenizer will see an
alpha token of maximum length 2, which has only 26^2 possibilities. If
a paragraph contains 20 nonsense words of length 6, then there are
about 11 words of length <= 2, and about half of those words are of
length 1. 

So the spam contains 5 examples of single letters, and there are only
26 letters in the (english) alphabet. But in English, most letters do
not occur alone as a single word, so a handful of emails with these
nonsense words will make most of the possible single letter words
known to the filter, and when single letters are found with uniform
frequencies over the alphabet in a message, these will already strongly
suggest that this message is spam.

This analysis is very simplified, because single letters also occur
often in machine generated tokens, e.g. urls etc, and bayesian filters
look at many other features. But it shows that the useful space of
nonsense words is not under the control of spammers only, because e.g.
they can't choose the filter's tokenizer.

Another reduction of the nonsense word space occurs when spammers
insert random words "by hand" instead of with a random number
generator. In that case, the layout of the keyboard reduces the
dramatically the types of likely random sequences produced.

Finally, the length of the nonsense words is often uniform, which is
not at all like real language. But therein lies another catch 22. Does
the spammer pick natural word lengths? In that case, he will include
many small words, and these small words have fewer nonsense
combinations, so they are more easily recognized. Does the spammer use
many long words? Then the surprising length of the words compared to
natural languages indicates something strange is going on.
 
> New words don't necessarily tip the filter towards spam. Remember: a
> bayesian is statistical method which calculates the probabilty of an
> event given the past history of that event. 

Yes. I'm certainly not arguing that a filter should know a priori if
nonsense words are nonsense. But as you point out, the filter can
always bias against nonsense words if it wants. The true test is the
number of errors overall. 

> The bigger problem for bayesian filters is not the random
> words. It's messages which contain extracts from literature. For
> these kinds of messages, using the tokens individually results in
> lower filtering performance. For such messages the co-occurence
> probability of the tokens has to be used instead. And then it
> wouldn't be a Naïve Bayesian filter anymore...  Brian Azzopardi

In principle, that's debatable too. Certainly, it's a better attack
than the nonsense word attack, but a quoted message still doesn't have
the correct token frequencies of any given individual's legitimate
mail. Moreover, newspaper language has its own statistical properties too,
so for individual (not corporate gateway) filters, the newspaper style
should be separable from the "family + friends" style quite quickly.
For corporate gateways, the statistical classification problem will
always have higher error rates, if all other factors are equal.

-- 
Laird Breyer.