Using gzip As A Spam Filter

captainclever writes "Kuro5hin have an interesting article on detecting spam using gzip." Here's a sample: "Loosely speaking, the LZ (Zip) and the related gzip compression algorithms look for repeated strings within a text, and replace each repeat with a reference to the first occurrence. The compression ratio achieved therefore measures how many repeated fragments, words or phrases occur in the text."

Comments

Grep it instead!

[WestieDog]

Forget about gzip all the 'cool' geeks use grep! :)

Re:Grep it instead!

[Walterk]

Just egrep for '(penis|enlarge|money|auction|cash|advance|fortune )'. And hope no hot babes email you complimenting your penis, or mention they want their breasts enlarged, offer you money, auction off your award winning lego collection or anything like that.

Raw data

[gazbo]

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

It's all spam

[amigaluvr]

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

Re:It's all spam

[greenjinjo]

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

[fredrikj]

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:Slashdot filter

[pudge]

Um, except that Slash uses gzip for its compression. So, no. :-)

What is different, as has been pointed out, is that Slash compresses a particular post and looks at how well it compresses, but does not compress/compare with other posts.

Re:Slashdot filter

[fredrikj]

Oops. Well, my experience from my troll accounts is that the filter does a lousy job, I could never have guessed that something that sophisticated was behind it ;)

Err, ignore the troll account part, I never said that.

Re:Text of the full article

[Anonymous Coward]

> 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

[dpete4552]

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

Re:Meet the Bayesian Filtering Algorythm

[dilute]

Baysian filtering looks at word occurrence statistics. This is saying just compare the bulk redundancies of a message as compared to a collection of test messages of a known type, without even looking at the "words". 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.

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. How to implement that is, well, left as "an exercise for the reader" -- actually, this has been discussed on /.

Re:Meet the Bayesian Filtering Algorythm

[coyul]

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.

Right tool for right job

[WPIDalamar]

Sure, this sounds like a nice academic activity, but really ... In the real world, use the right tool for the right job. I tend to think word redundancy does not correlate directly to spaminess.

HTML

[Pilferer]

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

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

Re:HTML

[phrantic]

Another problem with html is that, if there is some level of sophistication on the part of the spammer they can embedd a file (a gif or jpg) in the html that has a unique name that is uniquely associated with your email address. You open the mail, the file is requested (it doesn't even have to exist) but the 404 error or the html get can be logged on the server, and then it is a simple matter of matching the requested files to the email address and you have a list of good email addresses. This is a really useful technique for "closed loop marketing" which is the corporate edition of Spam.

Excellent

[Phosphor3k]

Slashdot can use it to filert out duplicate stories.

It won't work for businesses

[autocracy]

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."

Re:It won't work for businesses

[blibbleblobble]

"Anything from mid-level management or the marketing department would immediately be marked as spam and trashed."

And the problem?

Spam Conference talk

[Matts]

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.

Re:Spam Conference talk

[ajs]

I think, at the Internet level, RBLs (mirrored by you, obviously for speed's sake) and such are your best weapon. The more of the net you have by the short patch-cables, the more significant you make each RBL that you listen to.

At the personal level, each of these newly "discovered" techniques (I remember a /. article about using gzip for analysis of other document structures years ago) will make a fine addition to statistical systems like SpamAssassin, which uses them to build a very accurate model of a piece of mail's "spamishness".

Re:Spam Conference talk

[Matts]

Actually it's the other way around. DNSBL's (not RBLs - thats a specific term for MAPS' list) are fine for personal users, and even for some businesses, but generally they have way too high a false positive rate for any kind of generic filtering. The SpamAssassin team has done lots of research into this, see for example the slide at the very end of my talk.

No, for a large scale service you need much lower rates of false positives than any of the DNSBLs provide right now. They're fine as inputs into heuristic or statistical systems, but on their own they are just not accurate enough.

Re:Spam Conference talk

[archeopterix]

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.

Re:Spam Conference talk

[ajs]

But, aren't those "false positives" (usually so-called innocent open relays and people sharing netblocks with spammers) what you want?

In the case of open relays, yes a whole company can be hosed mail-wise when the get on a list, but if multiple BLs agree, then they've got a problem that needs to be fixed.

For the case of people who share a spammers address range, I feel for them, but... do I really want to take the pressure off of them in favor of flooding the world with spam? I'd personally be pissed at my ISP for allowing such spammers to screw over MY reputation among the BLs. ISPs should behave accordingly, but right now why would they? They get far more money from spammers than from people who will leave because a few folks listening to the BLs get mail from your customers.

Spam is an ugly thing, and combating it is hard. Casualties are going to arrise. The question is: how do you minimize that list of casualties and make sure that people know the safety dance ahead of time.

Quantitive, not qualititive

[psplay]

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

[iapetus]

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?

Don't compress

[Fuzzums]

Usually I don't compress my spam.

I delete it.

This will save me a lot more space ;-)

Not that different

[Synonymous Soured]

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

[artemis67]

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

[isorox]

I usually cope by having a couple of folders in kmail I flush spam into

BODY contains "The following message was sent to you as an opt-in subscriber to RB Express."
FROM contains Trivia
TO or CC contains "johnsmith@isorox.co.ku"
FROM contains theracingpost.com
TO or CC contains "spam" (I use sitespam@isorox to sign up to sites)
BODY contains "to receive" AND "more of these offers"
Move to a Spam folder

If TO or CC doesnt contain
isorox.co.ku
exeter.ac.ku
ex.ac.ku

Move to possible Spam

That gets about 80-90% of my spam.

I skim Possible Spam when I get time, usually once or twice a day. I skim Spam about once every 2 days. i've got a couple of rules that just delete the spam straight off (known junk addresses that I'll never need, certain subjects, etc). Keep all my spam too, and check it when I get time, just in case.

Re:Same old problem...

[djmurdoch]

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

Re:Same old problem...

[ch-chuck]

If you're looking for the mathematically perfect zero fault spam solution in a world full of Msft and human beings, forget it.

What happens when I start getting 600-800 a day?

Start another account and don't give it to strangers who might sell it. Only give it to the person or persons who are going to send that really important email message. Throw in a few random numbers so if one gets leaked to spammers you can track the source (i.e., I gave my employment agency (obviously an important contact) chuck369, and nobody else. Now if chuck369 starts getting spam we know employment agency leaked it). Use 'throw away' accounts for untrusted contacts who might leak it to spammers.

Spammers will adjust their tactics

[ultrabot]

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

Alternative

[Dexter77]

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

[Baldrson]

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:

1. 2 c 2 d
2. a b

Representing the original string then is the sequence:

1 1

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

Re:Sequitur Most Likely Superior

[A55M0NKEY]

But your rule list is now getting big and still has to be stored. Compression is about minimizing the amount of stuff that has to be stored to recreate the original. It would be nice to have a few simple, very reusable rules that you can use to generate the original with a very few commands.

Re:this is nice

[gazbo]

No, the lameness filter does nothing like this. The lameness filter (strictly the postercomment compression filter) just sees how well the isolated text compresses. Too high compression implies too much repetition (hence likely repeatedy copy+pasted junk), too low compression implies random chars - English contains plenty of redundancy.

This, on the other hand, talks about gziping the mail in the context of corpora of known spam or known ham. Thus it serves as a classification of types of Englishg text, whereas the slashdot system only tries to classify whether or not it is actually English text at all.

Yay!

[Anonymous Coward]

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?

[Big Mark]

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

How to stop spam....

[oliverthered]

1: Get an email account with unlimited addresses.
2: when registering use a unique address e.g. slashdot@mydomain.com
3: Make sure you check/uncheck the give my email address to mailing lists.
4: If ever you get spam to that account get litigious.

Use something like mailinglists@mydomain.com, and block anything that doesn't come from mailing lists you've subscribed to.

Re:How to stop spam....

[Jugalator]

Still, you use hotmail (aka "spammer's heaven") here on Slashdot. But thanks for the tip, perhaps we should start trying it out? :-)

Re:How to stop spam....

[NoseyNick]

I've been doing this for years, and in practice, it just means I get 12 copies of most spams, because they got my address from 12 different places, usually web archives of the mailing-lists.

You can't refuse mail from non-lists to mailinglists@your.domain, because then nobody can contact you saying "I saw your post on foo-list and was wondering if I could get a copy of foo-prog and if you could tell me how you made it foo bar baz".

Re:How to stop spam....

[DeadSea]

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.

Just use a string entropy calculation algorithm...

[Domini]

It's inefficient to have so much memory overhead.

Besides, if I were a spammer, I could pad it with high entropy data at the end to make up for my warbling.

Compression algorithms as filters...

[Jugalator]

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

Re:Maybe I am missing something here

[6Yankee]

the text in each is quite varied; e.g. longer xxx

The text in each of my spams seems to have more XXX...

Re:Text of the full article

[Anonymous Coward]

Reminds me off a program I helped with for a short time in college called "Siff" (ftp://ftp.cs.arizona.edu/reports/1993/TR93-33.ps) , which would find similar files by taking small fingerprints (32-bit hashes) of 50 byte sequences and finding groups of files that shared a lot of them. It works surprisingly well, even when the files were modified extensively.
I've often thought since that large mailhubs (yahoo, hotmail, etc) could automatically filter junk mail efficiently by a similar method, perhaps by limiting the delivery rate/fingerprint or just flagging high-occurence hashes as suspect (and then rating each mail by how many of its fingerprints are among this group, too many without an ADV: or bulk-mail tag would cause a mail to be marked as SPAM).
I wonder if it'd be possible to have a network of smaller hubs accomplish the same thing, perhaps even using an encrypting checksum instead of a simple hash so that individuals could contribute without anyone being able to recreate their original messages?

I can't figure this out...

[shivianzealot]

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?

Re:I can't figure this out...

[Motherfucking Shit]

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.

Re:I can't figure this out...

[stilwebm]

It's true that the sellers want that. However, you may have noticed spammers are not always the sellers. The seller is looking for someone to do some "email marketing" for them. They are looking for wide coverage. They want to see things like "your email can be sent to 30 million unique email addresses," which means a few million that might get through, a few thousand that will actually get read, and maybe a few purchases. Spammers are just creepy marketers who want to make it sound like emailing as many people as possible is better, and should cost the seller more. Since they use open relays and random forged "From" email addresses, they never see what email gets blocked. Using images in HTML email they can get an idea of how many emails were read (this is why you should turn off images in email). While the spammer makes a commission on every sold item, they also make money selling lists and marketing services.

The numbers are part of their pissing contest, and the pool is your inbox. Spammers are not that bright, but their customers are much, much more stupid.

Stopping Spam

[Inflatable Hippo]

> 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:Stopping Spam

[iamchris]

Think about this: Why do I get 1000's of spam emails per month and I get 10's of peices of junk snail mail/month? Simple: It costs nearly nothing to send millions of spam messages, while it costs a bundle to send junk snail mail.

A simple solution would be to find a way to charge per email...

Now, I certainly wouldn't pay per email. But, I shouldn't complain when someone abuses a messaging system that allows millions of messages to be sent out for nearly no cost. I use that system too, on a much smaller scale, for personal and legitimate business use.

All I can do is ignore as much of the mail as I can, and BOYCOTT anything that is sold via spam.

Ag.

Re:Stopping Spam

[misof]

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

I have to discourage your optimism a bit. IF the public-key encryption ever finds its way to the general public (I hope and think so), there are two possibilities:
a) Your public key will be available for the general public -- this is how it will probably work. If someone wants to send you an e-mail, he obtains your public key in a trusted way (e.g. from a trusted key server), encrypts the message and sends it. If the spammer wants to send you spam, once he gets your e-mail address, he does exactly the same. Obtains your public key, encrypts the spam and sends it. The only difference with today's situation: it will be impossible to filter spam on the server side (only to block some spamming IP addresses, no server-side spam filters).
b) You give your public key only to your friends you trust. This is exactly the approach "everything coming from an address, that's not in my address book, has to be spam." and even contradicts the basic idea: it's your public key...

Re:Moron

[ultrabot]

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.

Re:Legislation

[liquidsin]

That's pretty harsh. Once the death sentence has been carried out, I see no reason not to parole them. Have some compassion.

RBL

[Penguinoflight]

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

Email to my girlfriend

[FroBugg]

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

[Hal-9001]

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.

Spammers just found another loophole..

[SystematicPsycho]

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.

32k Window...

[pridkett]

The fact is, that unless your SPAM corpus and HAM corpus are both under 32k, this won't work. Gzip is fast because it only has a 32k sliding window, meaning that it only searches for like strings in a 32k window around what you're currently compressing. Hate to break it to you, but 32k is not enough for a corpus. I think Bzip2 uses something larger (900k?), but I forget what it is.

I'll be happy with spam assassin until I get CRM114 (and mailfilter) trained and working.

Similar article on heise was published a year ago

[hanzwurst]

German newsticker heise had a similar article a year ago, altough it does not cover spam explicitly.
The article has a link to another article published in "Physical Review Letters" which deals with the topic of identifying content/author by applying compression algorithms.
The underlying idea is that LZ77 compressed data is near to the entropy of a message.

Re:Text of the full article

[NoseyNick]

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

Baysian filtering IS word-counting with (not very sophisticated) statistical heuristics applied to the results.

Sorry, that's not right

[martin-boundary]

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.

Re:Sorry, that's not right

[Synonymous Soured]

Pre-coffee fog. Sorry. Typing got ahead of brain. Tripped up confounding the words-as-symbols/bytes-as-symbols distinction with the model markovity.

You are correct about the order-1 assertion. That should indeed have been order-N, where N is the length of the longest prefix string maintained explicitly or implicitly by a Ziv-Lempel dictionary or backpointer set. The Ziv-Lempel engines can be regarded as using shortened N-grams to represent classes of longer, yet-unseen N-grams; and they do use Markov models, where the stationary and transition probabilities are all set equal. In these cases, the probabilities only count for being zero or non-zero.

A "Bayesian Spam Filter" is order-0 if it relies only on token frequencies, where the tokens are complete strings, and not conditional occurrences of word pairs. The assertion is that a spam filter mechanism would be improved if it relied on a higher-order underlying model, and if the symbols were taken to be bytes and not words. The probability of a string is thus the product of the probabilities of its symbol sequence under the order-N model. But any higher-order model, even one using within-message word digrams or trigrams, would probably be an improvement.

Even Better

[HereAllNight]

Who needs all of these complicated schemes? I just filter the sending domains as they come. Filter every sender containing "specials", "optin", "offer", "special", "deal", "email", "reward", "value", "promotion", "special" and "super, and all subject lines starting with "friend", and 85% is taken care of right away. So far my formula has had no false positives.

Yawn -- read your papers

[Anonymous Coward]

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

Correction

[misof]

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

There is a minor problem with this sentence. And with this whole gzip business. It is misleading. Words, phrases? You cannot force gzip to match words, gzip tries to exploit every likeliness found, even at the character level. E.g., if your "spam dictionary" contains words sex and pants, mail about sextants will have a good compression ratio. And there is no way how to prevent this. That's why the Bayesian filters (operating on words) outperform gzip by a league. That's (one of more reasons) why I think this article belongs not to /. but to a wastebin instead. It simply presents a worse approach to do something. Interesting idea, yes, but that's all.

(Just FYI: it is proved, that the bzip2 algorithm due to Burrows and Wheeler exploits all such repeatings in the input file nearly optimally -- within some small ratio. Hence, it is even worse to use it as a spam filter :-)

Repost?

[fulldecent]

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"

How about....

[slummerx86]

if all the email clients had a little button saying "This is Spam" and if you click it the mail gets sent to some nice spam black list agency. They'd wait for about 10 people to do this, then verify it for the spam it is and then A) black list the spammer and B) send anti-spam email (subject: spam sender here ) nice and easy :)

Re:Just use a string entropy calculation algorithm

[a2800276]

d0rk! Ignoring the fact that I was being sarcastic and artistic license would have permitted me to specify /dev/my_ass let me just say this: before you make statements trying to make people look stupid you should probably have a clue what your talking about.

While true that your measly Linux machine has no /dev/srandom, this device is the source for _s_ecure random data on OpenBSD and it's probably available some other places as well. Some random trivia (pun intented), checking around I noticed: AIX and Solaris both don't typically have /dev/random at all.

But anyway, back to your question: if you're sad you don't have /dev/srandom you could try the following:

ln -s /dev/srandom /dev/zero

Re:Text of the full article

[Arkham]

Baysian filtering IS word-counting with (not very sophisticated) statistical heuristics applied to the results

This may be the case, but most of the newer filters available now are not really Bayesian filtering by this definition. I use spambayes, and it has some very sophisticated algorithms to determine the statistical probability of the "spamminess" of a ham/spam.

Some of these fancier algorithms were developed by Gary Robinson and are discussed in some detail here. You can see the results of these different classification techniques (gary combining, chi-squared) in some nice graphs here.

On a related note, spambayes is VERY accurate in catching spam for me. Amazingly so in fact. It does a far better job than SpamAssassin or the Bayesian filter in Mail.app in my personal experience.

Messages from teenagers would be spam

[Adam9]

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?

Nope

[I Am The Owl]

Doesn't work for the Lameness Filter, won't work for spam .

Zip on DNA & Different Languages.

[wilgamesh]

This reminds me that about a year ago, three italian scientists came up with a way to find species relatedness by using the zip algorithm. One takes the sequence of bacteria 1, and then attaches a little bit of bacteria X sequence to the end of that. Again, one attaches a bit of bacteria X sequence to the end of bacteria 2. And then zipping is done on this concatenation. The final compression size of just the bacteria X part ended up telling us the homology (or relatedness) of bacteria X to bacteria 1 or 2.

But from reading all these posts, perhaps a Bayesian method would work just as well. There seems to be no inherent advantage to using zip. One still needs a reference piece of work (non-spam email, or bacteria 1) for comparing entropies or probabilities. Of interest also is that the researchers applied their method to generating an accurate language tree of Indoeuropean languages (grouped by relatedness of course.)

The ref & abstract of above paper is here:

Phys. Rev. Lett. 88, 048702 (2002)
Dario Benedetto,1 Emanuele Caglioti,1 and Vittorio Loreto2,3

In this Letter we present a very general method for extracting information from a generic string of characters, e.g., a text, a DNA sequence, or a time series. Based on data-compression techniques, its key point is the computation of a suitable measure of the remoteness of two bodies of knowledge. We present the implementation of the method to linguistic motivated problems, featuring highly accurate results for language recognition, authorship attribution, and language classification. ©2002 The American Physical Society

GZIP used this way ...

[fygment]

... can be universal. The principles used actually have their roots in the theories put forward by R. Solomonoff and Kolmogorov (links below). Any given string of bits can be assigned a "complexity" which is proportional to the length of the shortest program that can generate that string. It isn't usually computable BUT the size of the output file of a compression algorithm can be shown to be a reasonable if crude approximation. The beauty is that this approach (minimum description length or MDL) is clustering email in a very fundamental way without the bias' that can be introduced with assumptions required by Bayesian techniques and arguably making use of all the information (vice a subset chosen by the Bayesian user) contained in the email. Yes, the answers can be the same but the MDL approach is universal and the same classifier without modification could be used for broader clustering tasks i.e beyond binary classification of junk/not_junk to multi-class classification junk/best friend/mom/dad/wife/work/etc.

As an aside, since it could be fully automated it would be interesting to run the such an algorithm with a graphical display, say a 2D plot of compression size vs time of day just to see what shakes out.

By the way, the problematic portion for bioinformatics apps is the compression. DNA sequences often exhibit _expansion_ when put through the common compression schemes. Li has come up with a compression scheme that is more optimal called GenCompress.

Kolmogorov Complexity - http://www.idsia.ch/~marcus/kolmo.htm
Minimum Description Length - http://www3.oup.co.uk/computer_journal/hdb/Volume_ 42/Issue_04/
Bioinformatics app - http://www.cs.ucsb.edu/~mli/sam.ps
GeneCompressio n Program - http://www.cs.cityu.edu.hk/~cssamk/gencomp/GenComp ress1.htm

bzip2 results

[K-Man]

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.