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

From: "Brian Azzopardi" <[email-masked]>
Date: Sat, 18 Sep 2004 13:46:19 +0200

When I said that there are 26^6 possible combinations I was referring to what a random token generator could produce. I cant imagine a tokenizer 
being limited to the 26 letters of the alphabet + 10 digits. Who would be silly enough to write a tokenizer which delimits on digits? I think your discussion on this point is moot.

Tokenizers today have to be much smarter than simply extracting single words. They should recognize HTML tags (while ignoring the non-valid ones), IPs, dates, and other relevant information. 

The basic Bayesian algorithm is sound - what needs more research though is the representation of the message that is passed to the bayesian. Currently most filters use a direct representation - that it the filter is fed the tokens found. It does not have to be like this. A trivial example: tokens which are longer than 12 characters are given a different token, say, "BAYESIAN_TOKEN_TOO_LONG" which is then fed to the Bayesian.

Most email is too short to extract any meaningful higher-level information from it. For example, Zipf's law holds for long texts but emails are usually too short for it to apply.

Brian Azzopardi

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.

_______________________________________________
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 22:42:31 +1000

On Sep 18 2004, Brian Azzopardi wrote:

> When I said that there are 26^6 possible combinations I was
> referring to what a random token generator could produce. I cant
> imagine a tokenizer being limited to the 26 letters of the alphabet
> + 10 digits. Who would be silly enough to write a tokenizer which
> delimits on digits? I think your discussion on this point is moot.

While the computation I gave was geared towards your example, the gist
of it is entirely applicable to similar questions in general. In other
words, spammers cannot control the size of their randomly generated
chaff, unless they design them to combat a particular anti-spam filter
version. I don't know why you would think that a tokenizer shouldn't
delimit on digits.  Have you tried it?

If all you delimit on is white space, you should check out several of
the open source Bayesian projects, which have extensive discussions on
mailing list archives and in source code about best token
forms. Perhaps the most interesting lesson from this is that best
token forms are quite unintuitive, and only visible with thorough
testing on real datasets. Human ideas about what works tend to be
suboptimal.

> Tokenizers today have to be much smarter than simply extracting
>single words. They should recognize HTML tags (while ignoring the
>non-valid ones), IPs, dates, and other relevant information.

I agree with you on this, and that is another facet, unrelated to the 
nonsense word problem. After filtering tags, noting IPs etc, you still
have the basic question of what constitutes an acceptable token.

>  The basic Bayesian algorithm is sound - what needs more research
> though is the representation of the message that is passed to the
> bayesian. Currently most filters use a direct representation - that
> it the filter is fed the tokens found. It does not have to be like
> this. A trivial example: tokens which are longer than 12 characters
> are given a different token, say, "BAYESIAN_TOKEN_TOO_LONG" which is
> then fed to the Bayesian.

Indeed. It does all come down to representation, after which point the
question is "which algorithm?". 

What makes the representation problem particularly interesting is that
a full and complete representation is not necessarily better than a
very simple incomplete one. Sometimes, extra information only confuses the
decision procedure, not unlike the saying "too many cooks spoil the broth".
Moreover, the best representation depends on the algorithm, and conversely.
Years of fun ahead!

> Most email is too short to extract any meaningful higher-level
>information from it. For example, Zipf's law holds for long texts but
>emails are usually too short for it to apply.

I don't know. Do you treat header content separately from body
content?  Many Bayesian filters read both header and body together,
which gives quite a lot of information. Some treat each part
separately and then combine them.  Even a spam with an empty body has
routing information and bogus sender details, which adds up to a few
quality tokens. It really depends. 

-- 
Laird Breyer.

---

From: Markus Stumpf <[email-masked]>
Date: Mon, 20 Sep 2004 18:09:06 +0200

> quality tokens. It really depends. 

The Spammers' Compendium
    http://www.jgc.org/tsc/

has a list of tricks spammers use to beat bayesian filters.

What is missing what I have seen lately is the use of e.g.

|_)      
|_)|_|\/ 
      /  
  _    ___                       
 | |  / (_)___ _____ __________ _
 | | / / / __ `/ __ `/ ___/ __ `/
 | |/ / / /_/ / /_/ / /  / /_/ / 
 |___/_/\__,_/\__, /_/   \__,_/  
	     /____/              
                                       .o. 
                                       888 
ooo. .oo.    .ooooo.  oooo oooo    ooo 888 
`888P"Y88b  d88' `88b  `88. `88.  .8'  Y8P 
 888   888  888   888   `88..]88..8'   `8' 
 888   888  888   888    `888'`888'    .o. 
o888o o888o `Y8bod8P'     `8'  `8'     Y8P 

to beat a bayesian filter.

Also spammers start poisoning headers with lines like:
    X-Literature: Once upon a time ...
which they expand for a few lines, just as they add randon words or
literature in the text part of multipart/alternative messages.

	\Maex

-- 
SpaceNet AG            | Joseph-Dollinger-Bogen 14 | Fon: +49 (89) 32356-0
Research & Development |       D-80807 Muenchen    | Fax: +49 (89) 32356-299
"The security, stability and reliability of a computer system is reciprocally
 proportional to the amount of vacuity between the ears of the admin"

---

From: Laird Breyer <[email-masked]>
Date: Tue, 21 Sep 2004 11:35:41 +1000

> has a list of tricks spammers use to beat bayesian filters.

Yes, it's a fun read. Few tricks work well, but we are seeing
evolution in action.

With regard to your example below, this is what a filter might see (frequency, token):

1 |_)
1 |_)|_|\/
12 /
2 _
1 ___
5 |
1 (_)___
1 _____
1 __________
3 __
3 `/
1 ___/
1 |/
4 /_/
1 |___/_/\__,_/\__,
1 \__,_/
1 /____/
2 .o.
10 888
1 ooo.
1 .oo.
1 .ooooo.
2 oooo
1 ooo
1 `888p"y88b
1 d88'
1 `88b
2 `88.
1 .8'
2 y8p
1 `88..]88..8'
3 `8'
1 `888'`888'
2 o888o
1 `y8bod8p'

Clearly, this is entirely untypical of ordinary language. Like the
nonsense words, this sticks out (e.g. what percentage of legitimate
messages do *you* have that don't contain the word "the"?).

In fact, many sequences will recur if a spammer sends several messages
of this type. Even without splitting on punctuation, various parts of
the "typefaces" recur, such as '888' which is used in 'n', 'o', '!'.
So the filter will automatically think messages with large frequencies
of '888' tend to be junk.

> literature in the text part of multipart/alternative messages.

Again, this example is a fun step, which doesn't work as the spammer
expects.  Many (not all) bayesian filters tag token location (eg if
the token was in the header or the body). So the X-Literature attack
sticks out for several reasons, because the majority of legitimate
messages don't have an X-Literature: header, and the text "Once upon a
time" doesn't mix with body text due to tagging. 

So if now another spammer sticks a header such as e.g. "X-Literature:
time to go!", the "time" token will have been seen before, in spam headers
only. In fact, it's not necessary to go that far, the simple fact of
seeing the "X-Literature:" label is indicative of spam, because legit 
messages don't have it normally. 

A statistical filter will recognize all these things automatically.

-- 
Laird Breyer.

---

From: Jose Marcio Martins da Cruz <[email-masked]>
Date: Tue, 21 Sep 2004 09:49:16 +0200

>>has a list of tricks spammers use to beat bayesian filters.
...
> messages do *you* have that don't contain the word "the"?).

Many. Two examples : As I live in France, most messages don't contain 
the word "the" as they are written in french. Also, people at our 
organisation sends and receives messages in many other languages : 
german, italian, russian, and even chinese ... and english of course.

>>What is missing what I have seen lately is the use of e.g.

...

> A statistical filter will recognize all these things automatically.

Maybe, but there are many legitimate senders and even companies which 
use this kind of message composition (Buy ... now) to add a footer at 
all their messages. So, false positives...

In this cases, to be something acceptable, I define "ALL" as being 100%, 
and "MOST OF THE TIME" as being 99.99%.

-- 
  ---------------------------------------------------------------
  Jose Marcio MARTINS DA CRUZ           Tel. :(33) 01.40.51.93.41
  Ecole des Mines de Paris              http://j-chkmail.ensmp.fr
  60, bd Saint Michel                http://www.ensmp.fr/~martins
  75272 - PARIS CEDEX 06      mailto:[email-masked]

---

From: Laird Breyer <[email-masked]>
Date: Tue, 21 Sep 2004 19:08:37 +1000

> german, italian, russian, and even chinese ... and english of course.

Heh, you're right of course. Moreover, Markus, to whom I replied, lives
in Germany according to his sig. Double whammy ;-)

> all their messages. So, false positives...

In the short term yes, but in the long term (ie with training), the
footer is recognized. No miracles. As a general rule, tokens which
occur commonly in both ham and spam, have little effect on a filtering
decision (Bayesian algorithms can vary). The decisions depend much
more on the presence of extreme tokens which (statistically) only
occur in spam, or only occur in ham (that's what I mean by extreme
here). It's very hard for spammers to discover which tokens are
extreme for any given individual.

> and "MOST OF THE TIME" as being 99.99%.

For how many people simultaneously? Statistical filters are no miracle
workers, and I wouldn't want to give the impression they are.  Every
decision procedure has a nonzero error rate. You can approach your
target with personal filters, but of course if you also want to filter
spam on a corporate gateway it's a much more difficult problem.

I was merely pointing out that spammer attacks against statistical
filters are mostly hot air. Some attacks, such as exploiting bugs in
parsers, work. I'm not aware of any statistical attacks which work yet (ie
attacks which would make the algorithms useless). Of course, this is 
for personal filters. For corporate filters, the problem is harder 
in principle. 

-- 
Laird Breyer.

---

From: Jose Marcio Martins da Cruz <[email-masked]>
Date: Tue, 21 Sep 2004 11:36:58 +0200

...
...
> for personal filters. For corporate filters, the problem is harder 

You're completely right on all this affirmations. What I really wanted 
to say is that statistical filters are very, very good for personnal 
use, but not for corporate structures. And most of the time I hear about 
bayesian/statistical filters, this particular point is left...

---

From: Markus Stumpf <[email-masked]>
Date: Tue, 21 Sep 2004 17:00:29 +0200

> in Germany according to his sig. Double whammy ;-)

:-)
For really a lot of our customers that have <5% email communication in
English spamassassin - after some training - works like a charm with
overly high success rates (and then with - from my feeling - overly high
false positive rate if a message in English comes through).
However we're seeing a raise of German language spam lately so the
rates may change rather soon.

> extreme for any given individual.

Yes, but with all the zillions of variations the spammers are IMHO also
attacking the size of the databases.
I wasn't too good in statistics but IMHO it is getting harder for
statistical filters if the set of data the decisions are based on is
growing, even more if the set of tokens in a test have a lot of "no
decision" and only few decison making tokens. This still helps to
classify, but instead of 70:30 decisons we come close to a *lot* more
50.1:49.1 decisions which has the effect of growing false positive rates.
So I think the mere backdraw is not that more spam is coming through
but that the false positive rate is growing.

	\Maex

---

From: Laird Breyer <[email-masked]>
Date: Wed, 22 Sep 2004 10:46:38 +1000

> false positive rate if a message in English comes through).

Der, die, das... With German statistics swamping your inbound
legitimate mail, you can also try to train a second filter solely on
the English communications. Let the first filter separate the German
mail from spam, and let the second filter separate the English mail
from the spam that wasn't German.  If you have enough legitimate
English examples, this might work better than having a single filter.

> attacking the size of the databases.

Sure, they do whatever they can. If your filter can handle large token
sets efficiently, then it shouldn't matter. However, it could be
considered a DOS attack, if the filter slows down as the number of
possible tokens grows. SpamAssassin is notoriously slow, that's the
cost of using a scripting language (perl). Of course, optimized C is
harder to adapt locally.

> decision" and only few decison making tokens. This still helps to

What you forget is that the decisions that apply to any given message
are limited. For example, a typical spam message is around 1K or less.
Only the tokens found in that message are used for decisions, so the
rest of the word list shouldn't directly matter. 

Decisions which don't apply shouldn't affect the spam question
for that single message.  If this is a statistical filter, what should
matter are only the relative frequencies of seen tokens in spam or
nonspam corpora.  But individual algorithms vary of course.

> 50.1:49.1 decisions which has the effect of growing false positive rates.

It is possible that your filter is getting stale. Are you talking about 
ordinary SpamAssassin rules, or a statistical filter specifically?
Even statistical filters grow stale if not trained on new messages over time,
because new messages exhibit topic drift. 

E.g. you filter messages into spam and discussions of chocolate ice
cream. When people start talking about strawberry cake, a binary
classifier will find it difficult to decide if this cake is spam or
ice cream.

Alternatively, if the number of people you filter simultaneously for
is growing, then it is normal that a (any) filter will make more mistakes.

-- 
Laird Breyer.

---

From: Markus Stumpf <[email-masked]>
Date: Wed, 22 Sep 2004 17:28:26 +0200

> English examples, this might work better than having a single filter.

My eMails are mostly in English ;-)
The problem however is that IMHO the most use simple setups as provided
by their ISP. They don't have the skills to manage slightly sophisticated
setups, some even have problems to rate and hit - if they have the
decision "spam" or "not spam" - the correct button.
They don't want spam, but they don't want to pay the implications, be it
paying someone to manage the filters or to learn how to use them.
So, for power users it is possible to effectively fight spam and get the
spammers in a corner, but for the vast majority it is not and that is
why spammers have success and why they survive (power users wouldn't buy
from spammers, joe lusers do and that is the reason spam works :(.

> cost of using a scripting language (perl). Of course, optimized C is

Sure this is for running, but earlier or later even optimized C code
will have its side effects handling worldlists the size of all e.g.
english and german words with ratings. And with the spammers sending
extracts from literature (I've seen up to 1K of data) the databases
will grow far beyond the 800 words statistically used in person to
person emails.

> rest of the word list shouldn't directly matter. 

Sorry I was unclear. What I was trying to say is that if the spammers
with the dictionary text attacks raise the set of words and make these
words "neutral" it becomes harder to make decisions. I don't have
correct numbers but what I mean is the following:
- usually spammers use 300 different words in spam mails
- these are trained fast and easy
- classification is easy and eMails containing these words but also some
  other "good" words are not classified as spam
Now the spammers send the literature attacks. This grows the set of
words used by spammers from 300 to 3000. And it grows the average number
of words in a spam mail from 150 to 250. As - say - 2000 of the 2700 more
words are also used in "good" eMails and helped the classification they
become now worthless as they have to be classified "neutral". Even worse
if they are often used in good eMails, the use of those words grows the set
of words used in spam at all weakening the rating and they carry a
"good" weight which can outweight the "bad" count.

> because new messages exhibit topic drift. 

I wasn't talking about any specific filter, but of the problems the
literature attacks IMHO cause for statistical filters in general.

	\Maex

---

From: Jim Witte <[email-masked]>
Date: Wed, 22 Sep 2004 12:56:37 -0500

> [..] So, for power users it is possible to effectively fight spam and 
> get the

   Or the ISPs don't allow them to change the filter..  My mail-server 
uses SpamAssassin, but as far as I know, doesn't allow you to change 
the filter.  Maybe I could invoke the SA program with a different 
filter directly from my Procmail file..  But that may not really be 
germane here - I should just get a better ISP.  But perhaps not - how 
many power users are on ISPs that *don't* allow them to tweak the 
filters even if they wanted to?

Jim

---

From: Laird Breyer <[email-masked]>
Date: Thu, 23 Sep 2004 11:47:15 +1000

> My eMails are mostly in English ;-)

So you account for nearly 5% of mail traffic? ;-) Ok, I thought you were
mentioning a specific problem you were having, but we can talk in general.

> decision "spam" or "not spam" - the correct button.

In general, they don't even want those buttons. It's a hard problem...

> will grow far beyond the 800 words statistically used in person to

I'm not sure I understand what you are saying. There are two issues.

The size of a single message to be classified is small (the biggest
I've seen personally, IIRC, was about 30,000 filtered tokens, but
often much less), and that means the total time to classify is 
dominated by scripting language overhead. A C implementation
can be 10-50 times faster than the equivalent perl, simply because
perl does so many things behind the scenes that the classification time
is not enough to amortize the extra time required. If messages were
normally much, much bigger the speed gain would be less of course.

I haven't found that the total size of the word list is a problem.
You need to optimize the representation of tokens, but my current spam
category for example has 400,000 unique tokens, and 100,000 for
nonspam, and this makes no impact on performance. It could be 10 times
bigger without making a serious impact in performance. These sizes are
easily big enough to contain a full vocabulary for a person's mail
(but not necessarily a large group of diverse people). After that, you
can manage word lists, or use stemming, and finally use compression if
you like. I'd estimate that a 10,000,000 unique token list on a desktop is well
within our capabilities today, with the correct datastructures. In any
given classification, all you need to do is search 800 tokens (say)
within those 10,000,000 quickly. 

> words "neutral" it becomes harder to make decisions. I don't have

Ok, I can address this I think: In a typical "bayesian" filter, the
words are each given a weight, so they are both good and bad. The
weights depend on occurrence frequencies. When a spammer uses a
dictionary attack, he cannot convert a "good" word into a "bad" word
simply by using this word in a spam message. This is not like a game
of Othello. 

To make a word weight closer to "bad", a spammer needs your
cooperation (individual algorithms vary, this is general discussion).

> become now worthless as they have to be classified "neutral". Even worse

Ok, you appear to assume that "neutral" word weights are as important
as "extreme" word weights in making the decision. I don't think that's
true. In a typical naive Bayesian algorithm, the decision is heavily
influenced by a small number of extreme words. You could remove the
"neutral" words and have a similar result in many cases.  So those
extra 2700 words don't usually change any decisions, they were
"worthless" before the spammer used them already.

Now we have to ask, which words can the spammer convert from "good" to 
"neutral" or "bad"? If the word has a high frequency, then the spammer
must match this frequency.

If you use the word "cake" often, then the spammer can only make this
word "neutral" or "bad" by using this word more often than you have
used it yourself. And you don't stand still, you continue to use
"cake", so the spammer would have to use the word "cake" at a faster
rate than you and your friends. For example, if you have used "cake"
35 times, and the spammer has used "cake" 20 times, that would be
equivalent to if you used "cake" 15 times and the spammer never used
it. 

If the word has low frequency (once every 6 months or less), then the
spammer can stumble on that word and convert it to "neutral" or bad
very easily.  But this word never matters very much in decisions, so
it's a nearly insignificant gain for the spammer.

> "good" weight which can outweight the "bad" count.

Take a set of emails and, as a first approximation, consider the most
extreme weighted words in it only. It is not enough for the spammer to
stumble upon several words with an extreme "good" rating, he must also
*not* stumble upon several words with an extreme "bad" rating at the
same time, enough for the balance to be "good".

Now if he wants to communicate a message, he already has to use a few
extreme "bad" rated words, assuming you've trained your filter on a
representative sample. So he starts off with a handicap, and he's
looking to find random words with extreme "good" ratings, without
getting random words with extreme "bad" ratings at the same time.

How does he prevent extra "bad" ratings?  He needs the cooperation of
other spammers. If he quotes a piece from Hamlet, and several other
spammers (maybe himself) already quoted a piece from Hamlet earlier,
then those random words will easily have "bad" ratings to counterweigh
the "good" ratings he's trying to find randomly. If nobody has ever 
quoted Hamlet before, then those words don't have bad ratings yet.

Again, I want to make clear this is not an analysis of a particular
Bayesian algorithm, just general discussion of what to look for.
Also, some Bayesian filters are static, updated every 6 months
(e.g. Microsoft), so the spammers can analyse and attack these
unchanging systems, which is much easier.

-- 
Laird Breyer.