Using gzip As A Spam Filter

Raw data by gazbo · 2003-01-27 01:20 · Score: 5, Informative

This article will make much more sense if you look at the raw data in tabular form.

It's all spam by amigaluvr · 2003-01-27 01:21 · Score: 4, Funny

Hey if you compress all of your mail with gzip then it all looks like foreign spam anyway!

Re:It's all spam by greenjinjo · 2003-01-27 01:39 · Score: 5, Interesting

You know, I noticed something peculiar. If you're from a non-English speaking country, like I am, you can filter the spam by looking at the language of the subject. In my case, if it is English it is almost certainly spam.
Do English-speaking people receive spam in foreign languages?

Slashdot filter by fredrikj · 2003-01-27 01:22 · Score: 4, Interesting

Sounds very much like that lameness filter on Slashdot that refuses to accept a post if its contents can be compressed easily... of course, it's quite simplistic compared to gzip.

Re:Text of the full article by Anonymous Coward · 2003-01-27 01:24 · Score: 5, Insightful

> The current fad among spam filters is word-counting, with various statistical heuristics applied to the results.

The current fad is in fact Bayesian filtering, sophisticated statistical analysis.

gzip used this way can be viewed as a very poor Bayesian analysis with substantially lower effectiveness. Lets just skip the half-assed attempt and go straight to the real thing.

Meet the Bayesian Filtering Algorythm by dpete4552 · 2003-01-27 01:25 · Score: 5, Informative

http://www.paulgraham.com/spam.html

--
http://www.archive.org/details/ThePowerOfNightmares

Re:Meet the Bayesian Filtering Algorythm by coyul · 2003-01-27 03:34 · Score: 5, Informative

OTOH, it seems to me that some other model, such as a scheme that gives legitimate senders explicit advance AUTHORIZATION to send you email, might be what's needed.

I understand what you're saying, but there are a couple of problems with this, depending on how you implement it. If you allow potential correspondents to request authorization by email, you'll still have to process at least one message per originating address. That obviously won't work to eliminate spam (or even cut it down to size...) The other option is to force potential correspondents to request authorization over another channel (phone, fax, whatever), but this neatly destroys a lot of the convenience of email. It also eliminates the impersonal nature of email (by forcing a personal contact) when it is partly this impersonality that distinguishes it in the first place (and encourages some first time correspondents to make contact at all...)

May not be the ultimate filter (and I doubt it could be), but it's real interesting, I think, that this appears to have considerably greater than zero accuracy.

Actually, the Bayesian filter implemented by POPFile is remarkably accurate. A friend of mine has been using it since it debuted on slashdot in November and it has correctly classified all of the spam he's received since (76% of his email in total, unfortunately...)

You can also set up POPFile to process the headers of your messages as well as the body, so it will effectively learn the email addresses of people you're willing to receive email from anyway. Depending on how you define words (what you use as token separators), you could attempt to make it generalize to domains as well.

HTML by Pilferer · 2003-01-27 01:26 · Score: 5, Interesting

That's because most spam includes large amounts of HTML.

My friends do not use HTML in email. Ads for "Crimescene Cocksuckers" does.

Excellent by Phosphor3k · 2003-01-27 01:28 · Score: 5, Funny

Slashdot can use it to filert out duplicate stories.

It won't work for businesses by autocracy · 2003-01-27 01:29 · Score: 4, Funny

Anything from mid-level management or the marketing department would immediately be marked as spam and trashed. Maybe not very important in the first place, but you'd at least need to be able to say "yeah, I saw the memo on the TPS reports."

--
SIG: HUP

Spam Conference talk by Matts · 2003-01-27 01:30 · Score: 4, Interesting

Jason Rennie gave an extremely interesting talk about this at the MIT Spam Conference this month, although he wasn't using quite as direct a method, instead he was looking at MLD - Minimum Length Description. This is a technique to discover features in corpora that allow you to describe the classification of a corpus in the minimum number of details.

Basically it's a way to discover features in emails using compression techniques, so rather than having us SpamAssassin developers have to carefully and manually examine emails to see what's new and interesting about them, MLD techniques can automatically detect these features.

Jason Rennie's web page (talk and paper available) about this is here. Please do read it as it's extremely interesting.

The one downside of it is that Jason said at the end of his talk that it's extremely slow at doing the feature detection. When asked how slow he said that on a reasonably small corpus it took 4 months (although he said it was written in Perl, so a C port is probably a good plan).

In comparison to Bayesian techniques the MLD technique presents a great deal of interest - primarily because I work for a company doing spam filtering at the internet level, and so we can't feasibly do personal training which is what makes Bayesian techniques so great (see the talk I gave at the MIT spam conference). Without the personal training Bayes is only about 90-95% effective, so it should be interesting to see where these techniques lead us.

--

Matt. Want XML + Apache + Stylesheets? Get AxKit.

Re:Spam Conference talk by archeopterix · 2003-01-27 03:39 · Score: 4, Insightful

MLD, gzip, neural networks, bayesian filtering and probably a bunch of other spam-filtering methods are all based on the following scheme: get a (big) number of spam messages, a number of non-spam messages (preferably specific to the current user of the filter) and use a learning algorithm on these to produce an automatic classifier.
What bothers me about this method is that you can never be 100% sure what the learning algorithm will actually learn. My friends seldom send me HTML mail. Most of my spam is HTML. A learning algorithm will probably learn that HTML mail is spam, especially if it never gets HTML "ham" during its training period. Then if one of my clueless friends sends me a HTML message, it will not go through and this is clearly bad.
I will never trust an automatic filter so as to delete a message marked as "spam" without reading, but I think it can still be useful for ranking messages, so that spam gets read less often and deleted faster.

Quantitive, not qualititive by psplay · 2003-01-27 01:30 · Score: 5, Interesting

Its not simply the words that are used in a mail, but the way they are used (the order) that gives a sentence its meaning.

for example Two Emails:

1 (ham) "You have won a brand new Convertible, from the competition you entered."

and

2 (spam) "A brand new convertible to be won, have you entered?"

Ham would match about 80% with spam.

Word matching is a blunt instrument as mentioned. The English language is far too complex for simple calculations, this fact should be taken into consideration, when applying a 'Spam Likelihood' rating to Emails.

Re:Quantitive, not qualititive by iapetus · 2003-01-27 01:32 · Score: 4, Interesting

If I see either of those in my inbox, it's almost certainly spam. You don't think you really filled in all of those 'feedback' forms about sex toys that you keep getting responses from, do you?

--
++ Say to Elrond "Hello.".
Elrond says "No.". Elrond gives you some lunch.

Not that different by Synonymous+Soured · 2003-01-27 01:32 · Score: 5, Interesting

A Bayesian spam filter uses an underlying order-0 Markov model of email messages. gzip uses an underlying order-1 Markov model.

A Bayesian filter uses words as "symbols." gzip uses bytes as symbols.

The right thing to do would be to combine them.Ttake a gzip-style Markov model, using bytes as symbols and conditional probabilities, and plug it into a Bayesian filter. That would (1) make the filter more powerful and (2) make the filter applicable to any sort of data, arbitrary binary or readable text. Negligible computational overhead, sharper discrimination.

Same old problem... by artemis67 · 2003-01-27 01:34 · Score: 5, Insightful

Filtering is not a true spam solution. All it takes is for one false positive on a Really Important Email and be accidentally deleted to totally destroy the value of any filtering system.

Given that, the alternative to having tagged emails automativally deleted is to collect them in a folder and scan the message senders and subject lines. If you're doing that, then the spammer is getting a pitch through to you in the subject line. This therefore does not lessen the incentive for the spammer, but simply causes him to change tactics and put his best pitch in his subject line.

Right now, I get 60-80 spams a day. What happens when I start getting 600-800 a day? Again, filtering starts to break down, because I have SO MANY messages to scan everyday that the possibility of me missing a legitimate one is very high.

Re:Same old problem... by djmurdoch · 2003-01-27 01:49 · Score: 4, Interesting

Filtering is not a true spam solution. All it takes is for one false positive on a Really Important Email and be accidentally deleted to totally destroy the value of any filtering system.

One of the side effects of spam is that there are no "Really Important Emails" any more. Spam and spam filters have degraded the reliability of email to such an extent that you'd have to be crazy to send anything Really Important by email.

Right now, I get 60-80 spams a day. What happens when I start getting 600-800 a day?

That's a good point. The solution is to get less spam. You can do that by changing email addresses frequently (a really inconvenient solution that I don't recommend), or by getting spammers shut down (or yourself listwashed by the spammers).

Let the spammers know that if they send something to you, they'll lose money, and they won't send you so much spam. SpamCop reporting makes this easy. If you want to be listwashed, don't munge your address when you send reports. (This is an option with SpamCop.)

Some people claim that you'll get more spam or get listbombed or something if you send complaints without munging; that's not my experience. I get 20-30 spams per day, total, at all of my 4 publicly available email addresses. (Ninety to 95 percent of them get caught by the SpamCop filters, which have almost never caught valid email.)

Spammers will adjust their tactics by ultrabot · 2003-01-27 01:34 · Score: 5, Interesting

Obviously it wouldn't be a big problem for the spammers to run their creative gems through gzip, and alter the content until they achieve lower compression ratio. Even including a bunch of garbage after the message might do the trick. I believe equivalent analysis can be done cheaper with non-gzip tools...

--
Save your wrists today - switch to Dvorak

Alternative by Dexter77 · 2003-01-27 01:35 · Score: 4, Interesting

When the spam is filtered at user-account level, you can only do it by parsing a single mail in some way and determine if it's spam or not. It's like trying to tell whether a movie is bad by looking at one picture. If the spam could be filtered at the server level, by comparing mails that are received into to different accounts, you could really tell which ones are part of a mass-mail (spam).

One problem with this is the right to open other people's mail. But you could use some basic scrambling (rot-13) to make sure that no one sees the inside. It wouldn't make difference to the comparing script.

Mailing lists might cause a problem too but wouldn't it be easier to allow the mailing lists you belong to than trying to block the ones you don't belong to?

Sequitur Most Likely Superior by Baldrson · 2003-01-27 01:36 · Score: 4, Interesting

The statistics generated by Sequitur are most likely superior to Gzip.

As an example of how Sequitur works, the string 'abcabdabcabd' produces the following grammar rules:

2 c 2 d
a b

Representing the original string then is the sequence:

1 1

The usage counts of the rules are available as output options.

--
Seastead this.

Yay! by Anonymous Coward · 2003-01-27 01:42 · Score: 5, Funny

What an idea!

I could use this to avoid those people who keep saying the same thing all the time, over and over again...

Now, how can I convince my mother to use e-mail?

What is spam, though? by Big+Mark · 2003-01-27 01:43 · Score: 4, Funny

The compression ratio achieved therefore measures how many repeated fragments, words or phrases occur in the text.

Ah. I thought to detect really useless, annoying, pointless, bandwith-sapping and time-consuming email all you had to do was look for "fwd:" in the subject line.

-Mark

Compression algorithms as filters... by Jugalator · 2003-01-27 01:46 · Score: 4, Insightful

.. sounds like a poor idea to me. Yes, you can measure the amount of redundancy in a message, but:

a) Spammers might not always use messages redundant enough to be detectable from regular text.

b) If I happened to use some words a little too often, especially when writing mails discussing technical stuff or posting computer code fragments, would that be classified as spam?

I think this is a nice filter when sorting out more or less repetitive mails (spam or not) from novels, but a filter based on a spam database sounds better to me.

--
Beware: In C++, your friends can see your privates!

I can't figure this out... by shivianzealot · 2003-01-27 01:52 · Score: 4, Interesting

A couple of posts above state that spammers will "just adjust their tactics." Talk like this always puzzles me; on the spammer's side, does this not help him? If I'm selling a combination weight loss drug/mail order bride/penis enlarger/cable descrambler for only three payments of $49.99 in such a manner that every spam blocker in the world filters me, logically I'm only being filtered by people who know better than to buy my "product," thus not irritating them, in effect helping to slow regulation, and I don't loose touch with any significant chunk of my target demographic. Of course, this applies with the exception of corporate environments or similiar situations where Joe Insecure has someone else managing spam.

Can anyone share some +5 Insight on the matter?

--

Bored with karma, be a fan/freak

Re:I can't figure this out... by Motherfucking+Shit · 2003-01-27 03:01 · Score: 4, Insightful

If I'm selling a combination weight loss drug/mail order bride/penis enlarger/cable descrambler for only three payments of $49.99 in such a manner that every spam blocker in the world filters me, logically I'm only being filtered by people who know better than to buy my "product," thus not irritating them, in effect helping to slow regulation, and I don't loose touch with any significant chunk of my target demographic.
This would make sense if the only people implementing spam filters were end users. Unfortunately, the logic breaks down when you consider that some ISPs do the filtering on behalf of their customers. It breaks down further when you factor in the number of situations in which a) the customer might not even know that the filtering is happening, or b) the customer blindly trusts the ISP's filtering system.

Take Yahoo, for example. They're a popular webmail service and they also do spam filtering to some extent on inbound email. I would say that, in general, people who use Yahoo mail are not necessarily the type of people who "know better" than to buy spamvertised products. That's not a slam on Yahoo, nor on the people who use Yahoo mail, it's just the way the demographics work out. The ratio of ripe targets to clued-in antispammers is simply better at Yahoo than it is on other domains.

To that end, Yahoo's spam filters aren't helping the spammers any. A spammer's goal is to get his ad in front of as many potential targets as possible, and Yahoo is full of potential targets. But if Yahoo's filters catch the spammer's message and route it straight to everyone's Bulk Mail folder, there's (thousands|millions) of "targets" who will never see the message.

So no, I can't agree that filtering helps the spammers any, at least not the big spammers who are after volume. There's probably a bit of "collateral assistance" in that people who would report the spam may never see it, but I'd say that benefit is cancelled out by the number of possible targets lost to filters.

--
"BSD: Free as in speech. Linux: Free as in beer. Windows 10: Free as in herpes." --Man On Pink Corner in #52607549.

Stopping Spam by Inflatable+Hippo · 2003-01-27 01:55 · Score: 4, Insightful

> stupid filtering isnt gonna get you rid of spam... go complain at spammers upstream providers...

Filters only work to a limited extend, and so might shutting down the spammers, if it were possible.

But neither is going to solve this problem.

The only solution I can think of is wide-spread adoption of PGP (or equivalent) aware mailers and certification of mail.

The problem with mail addresses is that you have no control over their spread. If I give one to a company it'll usually leak out in the end and it's open season on my inbox.

However if "genuine" mail is certified and mailers use certification validity as a filtering critera then it simplifies the game hugely.

Your mailer can spot the people you've genuinely given your address to, and naturally "distrust" uncertified (effectively anonymous) mail or mail whos certificate has been revoked or is unknown to you.

The "only" things standing in the way of this are:

1. Slow adoption of certification/encryption in mass market mailers. Usually poor or missing.
2. Cost/diffiulty of getting a valid certificate (e.g. with Verisign).
3. The pain of typing a password every time you send a mail.
4. It only works if everyone joins in.

But nothing's for free and this strikes at the heart of emails useability.

I'm continually suprised by the lack of certification use at least by large corporations and governments, but I suppose it removes plausible deniability :-)

Re:Moron by ultrabot · 2003-01-27 01:59 · Score: 4, Interesting

Another moron the tdisn't read the article.

I actually read the article.

The proposal is not to see how compressible is the message but to use a compression tool to see how lookalike the message is to a corpus of spam.

Yes, and compression ratio is used to determine this.

--
Save your wrists today - switch to Dvorak

RBL by Penguinoflight · 2003-01-27 02:11 · Score: 4, Interesting

RBL blocks a lot of stuff that isn't spam. It's probably a better idea to go with bayesian filtering. You can read up on it here: http://www.paulgraham.com/better.html

--
"And we have seen and do testify that the Father sent the Son to be the Savior of the World"
1 John 4:14

Email to my girlfriend by FroBugg · 2003-01-27 02:13 · Score: 4, Funny

Unfortunately, using this my girlfriend would never get any of my emails.

"I'm sorry. Really, really, really, really sorry. I'm so very, very, very sorry. I'm sorry..."

Re:Text of the full article by Hal-9001 · 2003-01-27 02:14 · Score: 4, Informative

The scheme described in the article is not Bayesian at all. It's more like a very crude hash comparison. If two similar messages are concatenated, they should compress very well. If two dissimilar messages are concatenated, they will not compress as well.

An actual Bayesian filter would perform a statistical analysis of an existing body of spam and non-spam messages, identify key words or phrases that identify a message as spam or non-spam, and calculate the probability for every key word that a message containing that word is spam. Then every new message is classified as spam or non-spam by running a statistical analysis on its content, and the statistics of that message update and improve the probability model.

--
"It take 9 months to bear a child, no matter how many women you assign to the job."

Spammers just found another loophole.. by SystematicPsycho · 2003-01-27 02:18 · Score: 4, Interesting

I received a nice piece of spam the other day. I didn't read it but I usually scroll to the bottom to see if they have the mandatory (in some places mandatory I think) unsubscribe method. This method sure gets me mad -

To unsubscribe by postal mail, please send your request to:
P.O Box 272521
Boca Raton, FL 33427
Ref # XXXXXX -- scd

(XXXX.. replaced real reference number)

It seems that the unsubscription method doesn't have to be by email - just as long as it's by something and it's there. They musn't be specific in the law. Of course, no one is going to go write a letter by snail mail to unsubscribe to spam, although sending them some dog shit through the mail is tempting. I forgot the site that provides that service. Hrmm I should change my sig.

--
Analytic & algebraic topology of locally Euclidean meterization of infinitely differentiable Riemmanian manifold

Re:Grep it instead! by Walterk · 2003-01-27 02:19 · Score: 5, Funny

--

"If anyone needs me, I'm in the angry dome."

Sorry, that's not right by martin-boundary · 2003-01-27 02:35 · Score: 5, Interesting

Only naive bayesian models are 0-order Markov. The "naive" refers precisely to the zero order independence assumption. You can have 1-order, 2-order, n-th order bayesian models if you like. Those are called n-gram models. After that, you can have bayesian phrase based models if you like, or paragraph based also.

Bayesian only refers to how you use the probabilities.

Now gzip implements similar ideas to LZW compression, which uses variable sized prefixes, which is quite different from an 1-order Markov model. For example, and order 1 Markov model is not allowed to depend on more than the current and immediately preceding symbol.

Yawn -- read your papers by Anonymous Coward · 2003-01-27 03:01 · Score: 4, Informative

There was a paper published in PRL a couple of years ago that wanted to identify languages using gzip (Benedetto et al: Language Trees and Zipping). It sure sounded cool, but was quickly forgotten when Joshua Goodman took a closer look (link is down at the moment, probably IIS, Text version in Google Cache).

Re:How to stop spam.... by DeadSea · 2003-01-27 03:13 · Score: 4, Interesting

You need to expand on your step 4.

When I started getting spam, I wanted it to stop. I realized I couldn't just disable the email address because there might be somebody out there counting on it to contact me. I could disable it and send an autoreply with my current email address, but then spammers would just be able to look at the reply. I needed some solution where people could send me email even if the address they used had been disabled, but spammers wouldn't be able to get my current address. I decided to put a contact form on my website. Now I autorespond to a disabled email address with the contact form url. In addition, I was able to remove email addresses from my website which was a large source of spam.

Not being able to find a contact form that was secure, I ended up writing my own and releasing it under the GPL. You can get it at http://ostermiller.org/contactform/.

I also realized that no matter how hard you try, your email address will leak to spammers. Ever giving an email address only to your closest friends and family will not prevent it from leaking out. Between the klez virus, gift certificates, invitation, greeting card, and crushlink websites, even my most personal email address leaked to spammers. You can't be afraid to disable an email address and send your friends the new one. Now even if I missed a friend, they can still get a message to me.

Repost? by fulldecent · 2003-01-27 03:16 · Score: 4, Interesting

This post looks like it came from my previous reply on a way to detect entropy (non-repititious content)in P2P files

Here is a code snippet from the comment:

#!/bin/bash # Entropic analysis by Full Decent SIZE=$(cat $1 | wc -c).0 CSIZE=$(gzip -c --best $1 | wc -c).0 ENTROPY=$(echo "scale=4; $CSIZE / $SIZE * 100" | bc) echo "$1 is ${ENTROPY}% entropic"

--

-- I was raised on the command line, bitch

Messages from teenagers would be spam by Adam9 · 2003-01-27 04:01 · Score: 4, Funny

Don't use this filtering if you're a high school teacher or something else that involves getting messages from teenagers..

[E-mail from skittles9333@some.email marked as spam and deleted] So like, I was like sick, and like, I didn't go to school today. So like, I was told like, that Jim like said, that like you might like, have some homework due like tomorrow. Could you like, tell me what like that homework would like be?

bzip2 results by K-Man · 2003-01-27 07:31 · Score: 4, Informative

Several knowledgeable people pointed out that the first try was limited by gzip's 32k window size, so I did a quick run with bzip2, which uses a 900k block, and put the results here. Somewhat different, but still a spread between spam/ham.

And, of course, do try this at home.

--
---- "If we have to go on with these damned quantum jumps, then I'm sorry that I ever got involved" - Erwin Schrodinger

38 of 268 comments (clear)