Slashdot Mirror
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."
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.
That's because most spam includes large amounts of HTML.
My friends do not use HTML in email. Ads for "Crimescene Cocksuckers" does.
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.
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.
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.
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
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?
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.
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?
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.
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.)
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
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 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
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
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.
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.
Here is a code snippet from the comment:
-- I was raised on the command line, bitch
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 :)
... 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.
_ 42/Issue_04/o n Program - http://www.cs.cityu.edu.hk/~cssamk/gencomp/GenComp ress1.htm
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
Bioinformatics app - http://www.cs.ucsb.edu/~mli/sam.ps
GeneCompressi
"Consensus" in science is _always_ a political construct.