More on Bayesian Spam Filtering

michaeld writes "The "Bayesian" techniques for spam filtering recently publicized in Paul Graham's essay A Plan for Spam doesn't actually seem to have anything Bayesian about it, according to Gary Robinson (an expert on collaborative filtering). It is based on a non-Bayesian probabilistic approach. It works well enough, because it is frequently the case that technology doesn't have to be 100% perfect in order to do something that really needs to be done. The problem interested Robinson, and he posted his thoughts about trying to fix the problems in the Graham approach, including adding an actual Bayesian element to the calculations."

Comments

Re:spam

[Cyno01]

yeah, theyre all ready supposed to indicate if its pr0n spam by specifying in the subject, hot sluts inside, or whatever, but they ussually don't, and there isn't a really good way to enforce this, 9 times outa 10 when i get an e-mail from Joey, i know 3, and the subject is hey, or hows it going or something, the actual e-mail is pr0n

I still think passive euthanasia is the best way.

[tcc]

Why is such a simple problem that pisses off 99.9% of the population is so hard to manage on a global scale? I mean, EVERYONE is pissed off at getting spammed, everyone would LOVE legislation to sodomize local spammer with a baseball bat, oversea is a different problem but country/continent-wide spam is 1/2 of my problem and can be easily be taken care of with proper legislation. For once a restrictive legislation would get 99% support... you don't see that everyday. like I mentionned before, I don't get our politicians, they say they work for us, they try to find clever ways to tax us, remove control that we used to have and all, but something on which they would get unprecedented support, they are simply sitting on the issue...

Until politicians will be fed up and people will actually get SUED for spamming (for once you could have a good reason to sue real bad guys) nothing will change.

Yes I know in SOME states it's beginning, so for local spam in a few years from now I think legislation will make it's way and we'll be able to look in our mailbox and stop having TD waterhouse spamming when you already have an account with them, etc.

The other problem now is oversea spamming, especially coming from China/Taiwan. I mean.. I don't read chineese, I don't plan on buying that #.#" something oversea, so why do they spam us like that? I never get it, but I'd be all for passive euthanasia (i.e. ban their IP at router level) and if this is bad for buisness or relations or whatever, well MAYBE they will do something about it.

Here where I work, it's simple, one spam, I ban a whole class straight off the servers, if one day I get a call because someone couldn't reach us (if they really need to reach us, we have a phone anyways!) I'll be sure to mention him Why. too bad this is not happening at the backbone level, because some people would get their act together fast and apply a legislation globally.

Tutorial on Bayesian Inference

[rbrito]

The timing of this article seems impecable, since I am myself trying to learn about Bayesian Statistics.

I am a Computer Science student studying Computational Biology (more specifically, Sequence Alignments) and while I have a bit of background on Classical Statistics, I was (and still am) completely ignorant about Bayesian Statistics.

It is only now that I'm trying to learn about Hidden Markov Models and its applications to Sequence Alignment that Ifinally decided to learn the basic hypothesis about Bayesian Statistics and how it differs from the hypothesis made by the Classical Statistics.

During my searches for finding introductory material on Bayesian Statistics, I found this course page which has some nice introductory notes, including Bayesian Statistics.

I hope that other people find this resource as useful as I did.

Re:Tutorial on Bayesian Inference

[Wile E. Heresiarch]

Here are some additional references, on-line & off, about Bayesian probability.

On the web, see: Assoc. for Uncertainty in Artificial Intelligence -- this is the primary conference devoted to belief networks, which are a class of graphical (in the circles and arrows sense) Bayesian probability models. There are tutorials and other papers on the main AUAI web page, and links to the last several years of conference proceedings. By the way, Heckerman and Horvitz, now doing belief networkish work at MS Research, are in the AUAI crowd.

In print, my favorite reference is E.T. Jaynes, "Probability Theory: The Logic of Science", which is due out soon. See this web site devoted to Jaynes' work for the status. I am also fond of Castillo, Gutierrez, & Hadi, "Expert Systems and Probabilistic Network Models".

There are a vast (well, maybe just large) number of alternative models to classify things; a good introduction is Hastie, Tibshirani, & Friedman, "Elements of Statistical Learning". Incidentally, they use spam classification to illustrate several kinds of models.

Finally, if you're wondering what the heck is the difference between Bayesian probability and any other kind -- just google the posts in sci.stat.math; there is a Bayesian vs frequentist flame war about once a year. :^)

Post your results here

[Jeffrey Baker]

I'd like to head the results of anyone who has implemented one of these probabilistic filtering systems. I implemented a modifed version of Paul Graham's system and so far it kicks ass. So far it has trapped over 600 spams without any false positives. I receive almost 100 spams a day and over the last week I have generally only had to delete one or two by hand. The rest go directly to jail.

I'd like to hear about modifications to this system. I removed Graham's doubling of "good" word frequencies, and I trained my filter using digrams. I also tried all the various methods supplied by the program "rainbow", with good results, but the implmentation was too slow and klunky to place in the middle of my email delivery system. What are other possible modifications?

Re:Post your results here

[ajm]

Just out of interest what's your code written in and would you consider posting it?

Re:Post your results here

[kwerle]

I implemented Paul's system without the changes you mentioned, and am seeing >95% success (and climbing). 0 false positives. I will be submitting it to sourceforge this week.

Re:Post your results here

[Jeffrey Baker]

So have you been retraining the system as you get more spam, or did you train it initially and leave it that way. How large is your training set?

Details! My training set was 300 spams and 3500 not-spams. With digrams, my filter traps 618 out of 621 spams in my spam folder, which is 99.5%

Re:Post your results here

[Jeffrey Baker]

I hacked it together in Perl, to make use of the Berkeley DB interfaces and the MIME parsing modules. Took about 30 minutes. I'm working on a C library that could be linked into mutt or pine or whatever, but I'm finding the available MIME code in C cumbersome.

You can grab the source here, but it is specific to the exact way that my mail gets delivered (via offlineimap into maildirs).

Re:Post your results here

[kwerle]

So have you been retraining the system as you get more spam

I continue to train.

or did you train it initially and leave it that way. How large is your training set?

I started off with a base.

Details! My training set was 300 spams and 3500 not-spams.

I started with a little more than 300 spam, and around 1000 valid messages.
My count is now:
Good messages read: 1194
Bad messages read: 644

That's because I only train on deleted mail, and I don't tend to delete my mailing lists except for once a month or 2...

With digrams, my filter traps 618 out of 621 spams in my spam folder, which is 99.5%

Against my start set, I nailed about 97%, including refiling 2 false positives from my old anti-spam system as being not spam. I've noticed that the system is really good at nailing stuff it already knows about, but the learning curve is a little steep for 'new spam types'. Still, I'm pretty happy with it.

Re:Post your results here

[kwerle]

If you're hitting > 95% or even >97% with the new system, who cares about spamassassin?

Re:Post your results here

[Jeffrey Baker]

What you said is actually inverted, since my system is way faster than spamassassin. I can do 15 mails/second with my Perl code. My half-implemented C code does over 600/second. Spamassassin seems to take about 5 seconds per mail on the same hardware.

Re:Post your results here

[wdr1]

or vice-versa...

-Bill

Re:Post your results here

[pemerson]

In addition, is anyone running probabilistic filtering on a large system with lots of users? Say, 1,000,000 messages a day? I'd be curious to know how you do it while keeping your load down on your mail machines.

Re:Post your results here

[XDG]

I've implemented it in part -- my code is in perl and will flag e-mails, but I haven't worked it into a filter yet.

My experience is that I get a few percent false-negatives and about 1% false positives. I'm not seeing zero false positives, like many people are, but that probably has to do with the training sets used. Statistically speaking, you always have to trade off false negative with false positives, so it's reasonable in my 'real world' tests.

As a side note, everyone should test out of sample. E.g. set aside half your good e-mails and half your spam e-mails, build the filter on one half, and then test on the other half. That's the only way to get a fair test of the filter.

For my "good" email corpus, I dumped my entire e-mail archive since 1995. That included personal e-mail, receipts from online shopping, some mailing lists, etc. The few things that get flagged as spam (a) are almost always sent in HTML format, and (b) very short with little real content. (E.g., "Hey, looking forward to seeing you this weekend. Call me if you go out. My number is... Bye.")

The spam corpus I took from on online resource while I build up my own. The e-mails that slip by unflagged are usually (a) short and (b) phrased like friend making a suggestion. (E.g., "Hi, I just thought you'd be interested in hearing about a this new, cool website, http://...") It seems to be close enough to a real message to slip through. Thankfully, few of them are like that.

I'm including subject lines, from addresses, and the body so far. I'm not parsing ip addresses or html tags specially, however, just basic words using a simple perl regexp.

Interestingly, "COLOR" is the one of the most often flagged words indicating spam. HTML formatting text seems to be the biggest culprit in my false positives. I might explicitly exclude the ones that show up in good mail (e.g. from friends who use crappy e-mail programs like aol) like COLOR, FONT, FACE, etc., but leave in the ones that spammer use like TD, TR, etc.

-XDG

Re:Post your results here

[Eric Seppanen]

You might want to consider collaborating with the group working on bogofilter, which is basically the same thing, done in C.

Re:Post your results here

[Ian Bicking]

I'm surprised to only see one link to Bogofilter in this discussion. I started using it just a couple days ago, training it from scratch (because I am patient and lazy). I train it on all emails it doesn't mark as spam, and then retrain it on spam it misses. So far I'm up to catching about 50%-75% of spams (climbing rapidly), with one false positive (though I had to read through that email a couple times to realize it wasn't really a spam -- so the false positive is understandable, since as a human I could have made the same mistake).

Bogomail potentially captures more relevent words than as described by Graham -- IP addresses, email addresses, and other text that should be considered atomic are recorded atomically. I think even more could be done with this -- but I worry that bogofilter is going to create too large a database, as it even seems to be keeping track of words like "$20".

As an optimization, I could imagine you could double-register some words, mostly those in headers. So the word "mother" in a subject line might register both "mother" and "subject:mother". Perhaps IP addresses could be recorded with all their classes (e.g., "200.69.228.105" would be recorded as "200.69.228.105", "200.69.228", "200.69" and "200" -- maybe prefixing some text to the last three, so that "200" the number is distinguishabe from "200" the class-A address)

Ultimately, a well trained spam database could be trimmed and distributed, but bogofilter does not yet include such a database. Graham's concern about distribution and trust are, IMHO, not entirely necessary -- a well-trained database can be created by only a handful of people (who receive lots of spam), and even if non-spam must be classified on an individual basis, spam is not tailored to any individual (nearly by definition). I don't think this has as great a risk of censorship as blocking lists.

I would be interested to see an improvement in the client end of bogofilter (or similar software). Right now I'm using procmail, and forwarding miscategorizations back to myself with a changed subject line (which procmail catches and feeds to bogomail). With just a little work, this could be used to create filters besides spam, where I train bogofilter to filter based on other criteria. (Well, I can do this right now, but it would take only a little work to make this accessible even to computer novices)

The proof of the pudding...

[ajm]

...is in the eating. I think the same applies to spam. Paul showed, to his satisfaction, that the technique he used worked for his samples. Gary proposes some changes that would improve the filter's accuracy, but does not test these theories.

We will now have many slashdot posts saying "I've not tested this but I think A (or B, or C, or X)"

Here's where the scientific method comes into its own. Anyone who cares enough can actually test and post their results. I'd be interested in seeing what they look like. I don't have a database of spam to test against (and please don't volunteer to sign me up for some :) but it would be interesting to see whether what looks convincing in theory pays off in practice.

Re:The proof of the pudding...

[shadow303]

From what I can observe from the writeup, Gray appears to be one of the "experts" that I refer to as "theory whores". Hard problems need to be tested, but some people seem to think that they can arrive at good results from an unproven theory. Anybody who has actually tested difficult problems to any extent could tell you that things don't always go as planned. An improvement with might work in theory, sometimes results in disaster due to minor points that the theory does not take into account.
Also, it bothered me that he objected to Paul's work biasing one side. It was almost like he thought it was a bug, but there was a good reason for biasing (reduce false positives). So my advice for Paul is, until you actually implement your idea, don't go trying to say that it is better than somebody else's method.

Re:The proof of the pudding...

[ajm]

It's the feeling I got as well. The change Gray suggests might be good or they might be bad. What I liked about Paul's write up was that he determined practically that it worked for him. Sure the theory may not be perfect but, to use a broad analogy, you don't need general relativity to work out how fast a ball rolls down a slope, Newtonian theory works fine. It may not be worth it to get the extra .1% of accuracy, especially if, as you point out, it increases false positives. Only testing will tell.

Re:The proof of the pudding...

[Anonymous Coward]

Paul called his method Bayesian. It wasn't. In addition to just pointing out that Paul was wrong, Gary also outlined how one might take a Bayesian approach to the problem.

He also showed how his extended solution included Paul's as a special case.

It sounds like you frequently get terminology wrong, and when someone points out that you're using the term incorrectly, and further shows how you could actually apply what you were talking about to the problem at hand, you go off on them for being a "theory whore." You're the winner of today's "Slashdot personified" award. Congratulations!

poor Hotmail users are still in the cold...

[saskboy]

I have some tricks for Hotmail users who cannot benefit from the technique above:
Filter any message without the @ in the address.
Filter Britney, Boobs, Penis, Inches, WIN, ___ ..... and your own email address userid.
Now you only have about 40 spams a day to deal with instead of 100.
Uncheck your information from being in the MSN directory too.

Enjoy :-)
John

Re: poor Hotmail users are still in the cold...

[IIRCAFAIKIANAL]

I really feel for any plastic surgeons named Britney that focus on penile and breast enlargement surgery. They can't filter squat.

Terrible Spam Filters

[DonkeyJimmy]

It's good that work is being done to make a good weigted spam filter.

It's funny how bad the standard Microsoft spam filter is (the one present in outlook). It's simply a word lookup, where if the word is present the message is marked as spam. It looks for things like "for free?". You can see the full list here, near the bottom. It's a little old, but not outdated (I think you can upgrade your spam filters, but I tested these, and the ones I tested work).

The adult filter isn't any better.

Naive Bayesian Learning

[Anonymous Coward]

Finally it is worth mentioning that if you really want to go a 100% Bayesian route, try Charles Elkan's paper, "Naive Bayesian Learning". That approach should work very well but is a good deal more complicated than the approach described above.

Here is the article[citeseer.nj.nec.com]

Let's see

[sam_handelman]

P (This is spam) = P (This is Spam | It will enlarge my penis) * P (It will enlarge my penis)

Now, given that I have prior knowledge that:
P (It will enlarge my penis)

is very low,

and given that, having never encountered anything which enlarges my penis in any permanent way, I have no knowledge of
P (This is Spam | It will enlarge my penis)

and we have the product of one probability which I know is low, and another of which I have no posterior knowledge, so we conclude that P (It is Spam) is also low, and that I must have requested more information on their new penile enlargement technique.

So, that message goes into the keepers.

Meanwhile,

P (It is Spam) = P (It is Spam | Frank is getting maried) * P (Frank is getting married)

So, I know frank is getting married, since he sent me this e-mail I'm considering filtering as Spam, and weather or not it is spam is pretty much independent of whether or not frank is getting married, so.... it's Spam. Away it goes.

P.S. I've deliberated made a hash of this for a joke. The actual rule is:

P (A & B) = P (A | B) * P (B)

filtering not the answer - maybe this is

[frovingslosh]

Sadly, unless you are an ISP or other mail service provider, filtering does nothing. The spammers work in volume. They count on hitting everyone to reach that .1% that will respond. That response is what they are after and what they get paid for. You likely know better than to ever deal with anyone who spams you or to ever respond to their spam. Filtering your own e-mail has absolutely no effect on the spammer, you were not going to respond anyway. By the time you filter they have already wasted your bandidth, and perhaps mailbox capacity and even forwarding limits from a forwarding service. Your filtering is useless, puny human!

Here is a suggestion for something that might make an impact on spammers: IF I open my firewall, I see several attempts a day from people trying to get into my mail server. Of course, I don't have a mail server, but spammers are always looking for open relay points they can spam from. My suggestion: Give the a nice open relay server they can send mail to. Of course, you don't want to piss off your service provider by sending spam, and your upstream speed might limit you to less than you can receive, so rather than run a full mail server lets modify some mail server code to just accept mail and send it to the bit bucket. Maybe we can even misconfigure existing code to do this with no programming changes.

No valid user will be affected, assuming you don't otherwise run a mail server. All that bandwidth you pay for can be used to receive e-mail from spammers before it ever goes out. Eventually their customers will see the response go from .1% to 0% and their business will dry up. This will impact spammers, blocking your own spam after it's been delivered will not.

This need not even impact your own bandwidth. You can run the server when you are done using your system (Might make a nice screen saver - a black screen that just shows how many spammed addresses were prevented from getting spammed). Or you cam impose limits on bandwidth at a firewall or router, or even restrict hours of access.

If we set up enough different false open relay servers I think we could have a real impact on the spammers.

Re:filtering not the answer - maybe this is

[stienman]

Interesting idea, but easy to verify. Send one thousand emails, and include a verifiable email in it. Check the email a few hours later - if it's not there, then don't use the relay.

-Adam

Re:filtering not the answer - maybe this is

[frovingslosh]

You might do better to send out a spam, then murder all the buyers once you get their address. Intellectual cleansing.

I've often wondered why we don't see a few spammer's heads on pikes to greatly reduce this problem, but there is a lot to be said for your solution too. Just don't do it on the day some good soul gets fed up with spammers and comes after you! ;-)

Re:filtering not the answer - maybe this is

[frovingslosh]

Interesting idea, but easy to verify. Send one thousand emails, and include a verifiable email in it. Check the email a few hours later - if it's not there, then don't use the relay.

Sure, they might test it. Still seems better than doing nothing. If a spammer passes me 1000 pieces of mail and waits a few hours, that's 999 pieces that didn't go out and a few hours of his time. If only I do this it will have little impact, but if the slashdot effect kicked in and there were so many false servers that it kept happening to him over and over again, that would be sweet!

And of course, some spammers will be lazy and not test. Jackpot!

Of course, the servers should look different. Some Linux, some Windows, some something else. Claim to be different applications. We might even start building smarts into the servers (if you get only one email, and it's going to an address that is likely a test address (his own domain, a mailbox service like Hotmail, or a local ISP that serves the same area his packets came from), wait one minute and then send it on. Worst that can happen is your false relay gets blacklisted (not a problem).

The bottom line is, which will have any impact on spammers, a lot of false relays out there that discard their e-mail destined for victims that keep the system going, or filtering e-mail that you were never going to read anyway?

Re:filtering not the answer - maybe this is

[frovingslosh]

As I mentioned (in a post that sadly was sent before being previewed), I can open my port 23 on my system and get several hits in a night for people trying to find a open relay server. Maybe they do look to the blacklists, since some of the mail on a blacklisted server still gets through, but they are spending a lot of time to find those open relay servers in the first place. If you're on the Internet, open a mail server (real or not) and it will be found the first day. I'm suggesting we make it much harder for the spammers to find a real open relay server - by giving them lots of decoy servers that will at a minimum cost them a lot of time and at best might even receive their bulk spamming rather than a real open relay.

Re:filtering not the answer - maybe this is

[Jeremi]

Filtering your own e-mail has absolutely no effect on the spammer, you were not going to respond anyway.

You're missing the point. I could care less what the spammer does. The benefit is that with a good filter, I don't have to look at spam. Currently I spend maybe 15 minutes a day recognizing and deleting spam emails, and occasionally screw it up and delete something important by mistake. If a filter program can reduce that load, it's useful to me even if it doesn't stop the spammer from spamming.

And in any case, in a year or two, when such intelligent filters are a standard feature on AOL and Outlook and etc, the spammer's "hit rates" will likely drop dramatically, at which point they will have less incentive to spam.

Re:filtering not the answer - maybe this is

[Phil Gregory]

Die.net's approach seems like a good implementation of this.

--Phil (Sadly, I'm on a cable modem, so I don't have the bandwidth for this.) Gregory

Re:filtering not the answer - maybe this is

[frovingslosh]

> Sadly, unless you are an ISP or other mail service provider, filtering does nothing

Oh, I don't think that's fair statement. What if I'm a company and I have 1000 employees all recieving email .....

..... like I do for my 1200 users I have to deal with.

If you are providing mail for 1200 users then I certainly would include you in the "service provider" group that I mentioned. I'm glad to see you doing it. I don't discount the technology, I wished my ISP used it, and more importantly I wish my forwarding service used it before it counted spam against my quota.

Another advantage to false news servers that would just be used by spammers: As the technology evolved I would envision that a network of such decoy relays could build up information that could be provided instantly to the service providers quickly to help make their filters more accurate and responsive.

Re:filtering not the answer - maybe this is

[frovingslosh]

No. It's another good thing that can be done, but it's not what I'm advocating. Basically he has set up a mail server expecting to get mail for his own addresses. He then wastes as much time as he can of the open relay the spammer is using. This at least slows things down for the spammer, and he might just get the attention of someone in charge of the server. Aother good thing to do, I think we need to do lots of things like this to stay ahead of the spammers. The dummy open relay would be another but different tool. Rather than slow down the conection it should take as much spam as it can, so that it doesn't go elsewhere and so that the paying client of the spammer would eventually see that he is getting no results.

Re:filtering not the answer - maybe this is

[MrDemeanour]

I've written a relay honeypot in Java. It's a real relay, that relays messages only if:

• there's less than recipients (configurable);
• the relay request arrived not less than seconds after the previous request.

It can bounce messages addressed to the local machine, in case the spammer checks for bounces (buggy, at the moment).

It whitelists relay test-addresses, as specified by its operator, and relays to those addresses even if it thinks it's in a spam-run. It adds any address to which it relays to its whitelist (i.e. it collects relay-test addresses).

It also posts all the data it collects to a website, which it can serve itself (i.e., it's a webserver too).

It has quite a number of other frills (not all of which are documented yet - it's still in test, but it's getting more stable every day).

It is a valid objection to a honeypot that does relay test-messages, that it is sending spam. There is a risk of the program being subverted by a spammer. Honeypotting this way isn't for children - you could get complaints for running this program.

Having said that, you can download the current Beta build at My site. (Damn, how do you get rid of that crap in square brackets???) It's highly configurable, but it runs out-of-the-box on Win NT/2K/ME systems (it needs a JVM, of course).

Jack.

Neural Net Spam Filtering

[ShakaUVM]

At UCSD, Bob Boyer and I wrote a neural net spam filter. Neural Nets, as everyone knows, are not really like biological brains, but really just statistical engines similar to the approach the guy above claimed to do.

Our approach worked pretty well (95-97% accuracy), and we had to deal with the same issues that the above "Bayesian" approach did. I.e., weighing the neurons so that false positives occur much less frequently than false negatives, etc. We built it using data on spam collected from the UCI machine learning repository.

It ties in with procmail. I'm not really a windows guy, so if anyone knows how to put a filter between an IMAP server and Microsoft Outlook/Netscape Communicator, I'd be interested in hearing how it's done.

The README for it is at: http://www-cse.ucsd.edu/~wkerney/spamfilter.README
And you can download it at:
http://www-cse.ucsd.edu/~wkerney/spamfilter.t ar.gz

-Bill Kerney
wkerney at ucsd.edu

Re:Neural Net Spam Filtering

[Trinition]

The thing that struck me here is that you chose the 57 attributes up front and determine the value of these attributes for each spam. These values are then the input to the spam.

How did you arrive that these attributes? Are there any others you considered but didn't include?

Is there any way a nueral network, or somethng else, perhaps could b used to determine other, less-obvious attributes? For example, Paul's filter found that the color #ff0000 (bright red) was a high indicator for spam. While that is the value of an an attribute (value = red, attriibute = color) that is the sort of unanticipated tell-tale sign of spam I'm referring to, except I wonder if there are unanticipated attributes to be found.

SpamAssassin - duh

[Gothmolly]

SpamAssassin works great for me. It eats about 90% of my spam, you just hack up a little procmail file for it, and you're done.

With so many people using SpamAssassin these days, I can't see how this is a timely or newsworthy item. More like from the been-there-done-that-dept..

Re:SpamAssassin - duh

[Eric Seppanen]

Reasons why I don't use SpamAssassin:

1. It tends to rely on blocklists, many of which have demonstrated unfair practices in the past.
2. The more SpamAssassin is used, the more spammers will specifically avoid doing things SpamAssassin checks for.
3. It's a gigantic heap of perl, the Write-Only (tm) language. I hate the fact that every perl program demands I mess up the package manager on my system by blindly downloading a half-dozen new modules. And it's slow!
4. Bogofilter is better. duh.

Re:SpamAssassin - duh

[ansible]

It tends to rely on blocklists, many of which have demonstrated unfair practices in the past.

True. Spamassassin does use block lists as part of the score, but you can lower the scores for those, not use them at all. The scores aren't high enough to kill a message by itself, I believe the highest score for a block list is 3.0 with the default threshold being 5.0.

The more SpamAssassin is used, the more spammers will specifically avoid doing things SpamAssassin checks for.

And if spammers decide not to send me pr0n or other crap, that's a bad thing?

The only real problem I've had with SpamAssassin lately is that I'm stuck on version 2.20. My ISP needs to upgrade Perl before I can run more recent versions. :-(

I'm not a big fan of Perl either.

Re:SpamAssassin - duh

[Fweeky]

It tends to rely on blocklists, many of which have demonstrated unfair practices in the past.

I've turned them off; it's still 95% effective.

The more SpamAssassin is used, the more spammers will specifically avoid doing things SpamAssassin checks for.

As spam changes, so does SpamAssassin. It includes phrase frequency checks etc, too.

It's a gigantic heap of perl, the Write-Only (tm) language. I hate the fact that every perl program demands I mess up the package manager on my system by blindly downloading a half-dozen new modules. And it's slow!

Oh, hell, yes. It's really quite nasty code, badly speghettified and relying on things like looped evals.

Look at SpamAssassin/PerMsgStatus.pm -- it performs (body regep rules * body message lines) regexp matches per message. It doesn't take long to see how nasty that'll get on a large message with over 200 rules :)

Bogofilter is better. duh.

Mmm, might have a look at that, thanks.

How do you pronounce "Bayesian" anyways?

[mblase]

While I love everything there is to love about open source (code and ideas), I kind of worry when I read how successful all these new Bayesian/Grahamian filtering techniques work.

Not being a coder or statistician myself, I'm left wondering if the spammers can exploit it for a workaround. Is there something "built in" to these filtering techniques that can be used by spammers to effectively circumvent them?

Re:How do you pronounce "Bayesian" anyways?

[KieranElby]

> Is there something "built in" to these filtering techniques that can be used by spammers to effectively circumvent them?

Yes and no.

To defeat a bayesian filter, the spammer needs to make his email contain similar words, and combinations of words, to your genuine email, while at the same time making sure that the words used are different to those in known spam.

So saying 'click here to make $$$' won't work any more, since most of your regular emails don't contain the word combinations 'click here' and 'make $$$', whereas known spam emails will.

However, we're already beginning to see spammers making their emails less obviously spam.

For example, the spammer may use an email along the lines of:

"How's things?

Have you seen yet?

Don't forget to mail me those documents.

Regards,
A Spammer"

Even a bayesian filter will struggle to distinguish that from:

"Have you seen the story on slashdot yet?

Don't forget those reports.

Regards,
Your Boss"

Re:How do you pronounce "Bayesian" anyways?

[KieranElby]

Oh, and "Bayesian" is pronounced "BAY - ZEE - UHNN".

Re:How do you pronounce "Bayesian" anyways?

[PurpleBob]

I bet they could get around it by picking a few random words from a dictionary and adding it to the end of the spam. If one of them were an obscure word that you've received in one or two legitimate e-mails, the filter would decide "Hey, I've never gotten a spam with the word 'yarborough' in it before, so it must be real".

Well...

[ccarter]

I hate to give any kind of credit to M$ but they patented the idea of using Bayesian analysis for spam filtering circa 1995. They even had it in one of thier beta's. However the filters were tagging some of those fricking Blue Mountain greeting cards as spam (imagine that!) so Blue Mountain sued them on anti-competitive grounds and M$ pulled it. Blue Mountain wanted to have the spam filters universally pass Blue Mountain content but MS refused that on the grounds that if a user considers it spam then it is in fact spam to them (Hurray for the "bad guys"!). The law suit has been settled/dropped/died for reasons I don't know.

Anyway I hear that the next version of MSN will have a Bayesian filter and that it will be introduced in an up coming version of Outlook Express (no idea about Exchange and Outlook).

BTW I believe internally MS uses this technique for spam control and that they don't seem to have any spam problems.

Brain exploded

[operagost]

Note to statisticians: the product of the probabilities is monotonic with the Fisher inverse chi-square combined probability technique from meta-analysis. The null hypothesis is that the probabilities are independent and uniformly distributed.

Ouch! My brain is hurting, Doc!

Re:I still think passive euthanasia is the best wa

[ivan256]

For once a restrictive legislation would get 99% support... you don't see that everyday. like I mentionned before, I don't get our politicians, they say they work for us, they try to find clever ways to tax us, remove control that we used to have and all, but something on which they would get unprecedented support, they are simply sitting on the issue...


Perhaps the problem is that the law would gain them less votes then a few hundred thousand dollars in campaing financing would. A large portion of the population isn't online, and a large portion of those who are don't care about spam, so your politician doesn't care either.

Since this is such a trivial technical problem to solve, it's not really a big deal either way. I daily reduce 800 spam messages to five or six that make it through to my inbox just using procmail scoring, and I haven't had a false positive in years. I spend five minutes updating my procmailsc every six months to keep it effective. I suppose that I could use an automated system to generate my score file similar to what Paul Graham described, but when I only spend ten minutes a year updating my rules, it's going to be alot of years before it was faster to have written all that code. No need for sweeping legislation.

anti-spam laws

[McFly777]

While in many respects I agree that "There oughta be a Law" against spam, there are some problems with that approach. Not the least is that generally a social solution is much better (or at least has less side effects) than any law that a government will enact.

Laws have the distinct problem of either going too far (false positive) or being too weak and thereby legitimizing the spam that would manage to work through the loopholes. Taken to the extreme that seems to commonly occur in the US legal system, I can envision spammers suing ISPs for blacklisting their "legit per US act ####" spam.

I would much rather statistical methods such as are being discussed. This combined with "whitelist" methods seem to work very well by all accounts.

Mmmm, I wouldn't try it

[mblase]

This need not even impact your own bandwidth.

Last week (I can't find the article yet), Slashdot had a link to a column by someone who was (in his opinion) unjustly blacklisted for hosting an easily-accessible mail server. The moment his name hit that blacklist, he became a target for what may as well be every spammer on the planet. Even though he didn't actually have an open relay (just an easily-guessed password), the incoming traffic from so many e-mail spammers effectively brought his server to its knees. Changing his domain name and IP address was the only cure.

Building a "honeypot" mail server for spammers is appealing, but could be more trouble than its worth, especially since it's more or less irreversible. I'd advice against it.

Re:Mmmm, I wouldn't try it

[GigsVT]

He was running an open relay. He was too ignorant to know it.

Re:Mmmm, I wouldn't try it

[Deagol]

I've always wondered what it would take to modify a sendmail or postfix configuration to become a "mail sink". Sure, there are tarpits that slow spammers down, but why not make a server that acts and smells like an open relay, but simply dumps the mail to /dev/null and tells the sender they were delivered? Maybe bandwidth might be an issue, but it may more effective than a tar pit.

A human watching over his spam software might notice if the target relay is delivering at a rate of 1 message per day and find another. If, however, he sees that the "server" is ripping through deliveries at a massive rate, he might stay with that server and all of his spam will vanish into the bit bucket.

Re:Mmmm, I wouldn't try it

[frovingslosh]

Actually, he did have an open relay, he just wants to hide behind a lame claim that it wasn't open because the spammer had to lie to use it! Imagine that, a spammer lying. He was a lawyer, and we know they never lie ;-). IMHO he got a lot less punishment than he deserved.

And what was the reported problem he cried about? Not an overload on his network, that was not his complaint. But his domain name being blacklisted. With good reason, IMHO. He was running a server that spammers used, and could even see this when the people he invited to test his system got right in. He then claimed they misused his system because they gave a false name and suggested he should sue them!

Maybe this guy was just too stupid to block a port on an incoming firewall to keep the outside mail server users out. It seems unlikely though, particularly if he had the ability to set up a mail server (supposedly for the use of his own local network). It sounded more to me like there was a good chance he knew exactly what he was doing and wanted to set up a server for spamming, and was blowing smoke when he got black holed.

Getting black holed will not be a problem for a dummy server that never actually sends mail (the black hole people are not out there port scanning like the spammers are). Even if your dummy mail server were to be blacklisted, so what? That in no way would affect your normal e-mail that you send through your service provider.

Re:Mmmm, I wouldn't try it

[FFFish]

...and into a Bayesian filter mangler, providing it with a diet of 100% unadulterated spam. The filter can then be distributed a la virus updates...

Re:Mmmm, I wouldn't try it

[AndroidCat]

Google and Googlegroups for spam honeypot.

And search Slashdot too. I think there was an article about a Russian honeypot a few months ago. Because of bandwidth costs, they "throttled down" their honeypot to reduce the truely huge amount of hits by clueless spammers. (But I repeat myself..)

There are arguements both ways about relay honeypots. The downside is that you have to let some relay tests go through so that when the spammer tests it, the tests go through. But then when the actual spam-run happens, it has to choke it off completely.

Re:filtering not the answer - maybe SPOOFSERVERS

[netringer]

I'm fairly sure a false relay won't work. Just like snail mail list sellers, the spammers salt their victim lists with their own valid addresses that they can check to see if the message is getting out.

BUT, an early spam filter at an ISP worked just like that. The design parameters were 1) that spam filtering require no more resources than actual delivery of the message, and 2) the filter give no indication to the spammer that the message was not going to delivered. This gives the spammer no feedback and forces THEM to waste CPU cycles which will slow them down.

keyword matching isnt the answer

[mack knife]

sites like yahoo, hotmail, etc are in a unique position to rid their users of spam.

i don't see why they cant implement some system that scans incoming mail for its users' mailboxes, maybe does a checksum for each message or something, and if it finds that a number of its users are receiving exactly (or nearly exactly) the same message, assume it's spam. nuke the messages, and any new incoming ones.

yeah, if such a system only scans a small number of mailboxes, it may filter out mailing list posts and so on. but it gets more and more reliable the higher number of mailboxes it tracks.

this avoids searching for certain keywords and eliminates false positives. after all, how well would these keyword searching methods do if i were to quote a spam message in an email to a friend?

optimistic

[McFly777]

I think the original poster's point would be to make commercial e-mail illegal unless properly tagged. That way an untagged spam could be handed over to the FBI and treated like wire-fraud or something.

Big problem would be prosecuting the spammer. Either they would all move overseas or the court would be so backlogged as to become ineffective.

Bayesian vs not isn't really the point

[XDG]

Gary is both right in some respects and irrelevant in others. Here's the key line in his article that deflates it a bit:

It is untested as of now. It is based purely on theoretical reasoning. If anyone wants to try and it test it in comparison to other techniques, I'd be very interested in hearing the outcome.

On the other hand Paul Graham has actually tested his model and it works. I've worked it up in perl and tested it on my own data set and it works there, too. Paul acknowledges that he's being a bit fast and dirty, but the proof is in the pudding. The rest is just academic quibbling over the fine points.

I'm not sure why this particular article needed to be posted, as it's just one of several alternative approaches and an untested one at that. On Paul's page, he also lists several published academic papers with other alternatives -- all actually tested, of course.

Gary is basically right in questioning the use of the word "Bayesian". Paul's approach is more about weighing "evidence" as given by the appearance of certain words, rather than in figuring out the probability of spam assuming a "prior". See Paul's explanation, but if you check the article he references at the end, you'll note that the method Paul uses is only one of several methods to solve an underspecified problems. It's a reasonable guess, not necessarily the only guess.

Looking at another article Paul references, given the word independence assumption, the more formal Naive Bayesian approach calculates as follows:
p(spam) = [ p(spam)*p(word1|spam)*...*p(wordn|spam) ] / [ p(spam)*p(word1|spam)*...*p(wordn|spam) + p(!spam)*p(word1|!spam)*...*p(wordn|!spam)]

This is similar to Paul's approach except for including a "prior" assumption of p(spam) -- the expected probability of any email being spam, calcuated from the historically observed frequency of spam. By leaving it out, Paul implicitly assumes that 50% of mail is spam -- that's his "prior" estimate of the spam rate. Given the other adjustments he makes to his sample, that appears to be acceptable in practice. (Paul overweights the spam prior, but also overweights the effects of "good" words.)

I'd personally prefer to overweight the "good" e-mails entirely rather than just put a "good-multiplier" on them like Paul does, but that's just quibbling over small bits.

As to the bit that Gary raises about Paul assuming a spam probability for an unknown word -- Paul originally said .2, then revised to .4, but really should have put it at .5 or just excluded it from all calculations. A new word has no robustness as a predictor (which is why Paul dropped words that didn't appear five times anyway). In practice, a new word at .4 isn't going to be among the 15 most interesting words to make the calculation from, anyway.

-XDG

Re:Why just spam?

[McFly777]

Easy. Just re-run the spam filter on your 'cleaned' mail using a ruleset generated by splitting the mail into topical vs. everything else.

Re:Why just spam?

[shrikel]

Have you tried Ms Outlook? It's got extensive rule-based sorting capability. It doesn't work for IMAP, and you mentioned IMAP leter in your message, but it's not clear that that's all you're dealing with.

How long until we throw out the current e-mail sys

[aengblom]

How long until we throw out the current e-mail system.

I own my own domain, which makes it easier, but we really need a system designed to filter. And make it easier. This is my uninformed proposal. Perhaps it won't work, but it seems something is needed.

People should have a private/public e-mail address. They should all go the same "account" and be part of the basic plan for any e-mail user.

privateauthentication~myemail@myhost.com

I know this is important and relevant

publicauthentication~myemail@myhost.com

I gave this person my e-mail address

myemail@myhost.com will go into the crap bin and be deleted eventually. Perhaps some program could be used to alert users of possible important mail pieces there.

Then we could also have some system to CHANGE the private authentication or public authentication that is form based. I.e. This address has been disconnected. Please apply for the new password.

Jaguar

[Have Blue]

Apple's new spam detector works amazingly well for me. After some initial jitters it pretty much never gets false positives these days.

microsofts trademark

[portal9]

why are we even considering this method when microsoft has a trademark on it? nothing can be done.. they have a lock on it. trademark here

Re:microsofts trademark

[Kevinv]

minor nit-picking detail: they have a patent. patent and trademark are completely different.

Re:microsofts trademark

[thogard]

another stupid patent? This isn't new, its been done with spam on usenet for years. Maybe someone should digout the cancelmoose's freiends as prior art?

Google for email... Re:Why just spam?

[WolfWithoutAClause]

Yes, I've always wanted google for email. You know, a small program that finds all the words in my email and then instantly pops up the emails with particular words in.

I don't actually see the point in putting emails into different folders, if you have that feature.

Re:Google for email... Re:Why just spam?

[Chirs]

I don't know what mail client you use, but Netscape at least has the ability to search through specified mail directories for keywords, dates, authors, etc.

I imagine most of the major clients have this ability.

Re:Google for email... Re:Why just spam?

[WolfWithoutAClause]

Nah... I think you're greviously underestimating my inbox. My inbox and the web are of comparable size; ok, I exagerate slightly, but the search doesn't come back in less than 5 minutes.

In contrast, Google preindexes everything and comes back in under a second.

Re:Dictionary spam?

[wirelessbuzzers]

yep. anything containing the words etesian and realgar and mangelwurzel has a 99.9% probability of being spam :-)

How does Apple's mail spamfilter work?

[wirelessbuzzers]

All it says in the help is that it is adaptive and trains itself on your previous spam. It would be nice to see some source... and be able to patch it if we don't like it.... oh well, whining won't get me anywhere.

Re:Why filter spam?

[kaladorn]

Maybe we can feed the spammers' children.
Hopefully to something large and hungry.

A call for suggestions, and coders...

[doorbot.com]

Let me start by saying I know very little about coding, otherwise I'd probably already be rushing off to a night of coding by the glow from my monitor.

When the first Bayesian spam filtering article was posted, I thought it was a great idea, and this article just reinforces that idea. However, it would be interesting to build some sort of Sendmail module (or whatever MTA you like), but add some additional functionality:

1. Option to return a 550 error if the message is determined to be spam: "550 Delivery blocked; Bayesian filter reports spam probability of nn%"
- Right before reporting this error, wait n seconds or alternately, slow connection to n bps for n minutes.
- After reporting the error, "deliver" the Subject and Body of the email to the spam words database.
2. Inclusion of a whitelist, by IP, reverse DNS, MAIL FROM address, or RCPT TO address, header To: address, header From: address, etc.
3. Configuration of account where spams can be forwarded to, for automatic addition to the database.
- Perhaps this could be combined with the blacklist/whitelist. For example, any emails to spamthis@antispamdomain.com are always added to the DB. The entry could be as follows (similar to the Sendmail access map):
spamthis@antispamdomain.com <tab> BAYESIAN:SILENT
- This would allow for either silent addition to the filter (sender thinks mail was delivered -- good for spam harvesting emails, or for users to send their spam to), or a more "vocal" addition much like item #1 above, where a 550 error is reported... eg, BAYESIAN:550 or perhaps BAYESIAN:REJECT

I realize this would block a lot of mail, but I have my Sendmail currently configured to actually block spam (or what it considers spam) and have had very few issues with valid messages bouncing. Obviously, results may vary, but I'm a firm believer in rejecting spam during the SMTP conversation, not accepting it and then deleting it silently.

Does anyone else have any suggestions?

Already Patented by Microsoft...

[barfy]

This whole methodology is already patented by Microsoft. ANY implementation not licensed by Microsoft is going to be a violation... And now that you know, it is treble damages...

patent 6,161,130

We can fight them!

[frovingslosh]

Another problem is that spammers might start automatically sending the same spams to the same lists via several different open relays. Thus, we might increase the volume of spam, at least in the early stages.

I doubt that there are many spammers out there who are not using all of their available bandwidth to send spam already, I can't see how setting up dummy port 23's would make spam worse. Just the opposite: While this can be started by a few changes to an open source mail server, or maybe even by misconfiguring an existing mail server, it should grow and evolve. I think we can beat the spammers, but not just by being impressed on how well we can filter our own mail. Heck, as they add smarts, we could add smarts too. If we can identify the test messages with reasonable certainty we can elect to send them through. We could even build a nice P2P network of systems cooperating to stay one step ahead of the spammers.

Can anyone get us started on this? Provide some Windows and/or Linux code to start the roach motel e-mail server (spammers log in but they don't send out)? I'll get one running tonight if I can get a good dummy mail server for Windows (and just slightly longer to put the hardware together if I have to build up a Linux system).

Re:We can fight them!

[flonker]

I know you didn't start this, but port 23 is telnet. SMTP is port 25.

Bayesian filtering software

[Roadmaster]

Seems like everyone jumped on the bandwagon and implemented a bayesian spam filter shortly after Graham's article hit the net. Best part is, theory or not, the damn thing actually works.

Paul's article lists a few of the bayesian spam filters, but here's a short list of the ones I've tried:
Gary Arnold's bayespam is implemented in perl and geared towards qmail using maildir storage.

Brian Burton's spamprobe, written in C++, tries to remember already-seen messages, so that you can dump your spams/good mails on separate folders, have spamprobe learn from them, and delete them afterwards. Spamprobe remembers which ones it already processed, and won't reprocess a message if it's already seen it.

Eric Raymond's bogofilter is a typical ESR tool: concise, with a baroquely written man page, and quite simplistic, but does its job and does it well. ESR even uses some funny terms, like "spamicity", and "ham" (the opposite of spam). I don't like its dependency on the Judy libraries for dynamic arrays but what the heck.

Matthew Walker's BayesSpam plugin for Squirrelmail provides squirrelmail users with bayesian spam filtering capabilities, no longer restricting use of the technique to those with access to procmail/mailfilter systems.

One problem with that approach...

[Big Sean O]

One person's spam is another person's 'useful email'. For instance, I may want a particular type of email (eg: a pr0n mailing list, or a "George Foreman Grill" user group, or lots of Korean friends). It might be considered spam by the ISP's filters, but not by me.

That's why it's best to train _my_ filter against _my_ received mail.

And as more email gets received and I add the uncaught messages to the spam filter, my filter 'learns' what I consider spam.

Assholes.

[Perianwyr Stormcrow]

So, if they own the damn thing, why can't they sit down and make a real implementation of it for Hotmail? I'm sure everyone involved would be happier.

Sounds good

[Perianwyr Stormcrow]

If the spammers have to jack a 75k file onto the end of their spams, suddenly they are sending 75 GB of data per spam run. This is about as stealthy as dancing naked on the piano in the middle of a wedding reception.

Also, it would only work once- the first dictionary spam I got would be marked spam and then all the junk words would get marked in the list.

POPFile does this

[Perianwyr Stormcrow]

It can use the filter to get any result you want, not just a binary trash/don't trash.

It puts an "X-Text-Classification" header in mails you get saying what category it determined, so that you can just write simple filter rules in whatever program you use to sort it all.

Except for user datagram protocol.

[Perianwyr Stormcrow]

So, if someone sends you mail about which UDP ports to unblock on a firewall to play a game, you've just lost communication.

Single word "zero-tolerance" rules are unwise, to say the least.

Re:Whatever Jaguar (Mac OS X 10.2) uses works!

[marmoset]

I've see the same effect. I almost never see spam anymore, and get almost no false positives. I wish I could find the quote, but one of the Jaguar engineers confirmed that there's some "serious math" behind Mail.app's spam handling. I can't find any technical reference about the algorithms being used, though.

Download it.

[mcrbids]

You can download the source here if you like.

It's not from the same guy, but it's definitely derivative work.

Re:Could someone tell me...

[Broccolist]

Based on the probability theory of Thomas Bayes, an 18th century philosopher. In a nutshell, whereas orthodox statistics emphasises a "distribution function" that wholly describes everything about a random variable, Bayesian methods take a more ground-up approach that works with incomplete information and revises probabilistic beliefs as new evidence comes to light. It's been attracting a lot of attention and research lately.

Method seems easily breakable.

[guybarr]

IIUC, The proposed method normalizes (with Ln norm) over the number of words, for "spammishness" and "unspammishness" of words, combining the results.

whats stoping the spammers from attaching, say, a random scientific article longer than the spam at the end of the spam message ? This will give the spam a high grade in these bayesian method in general, but more so with his normalizing metric.

Re:Method seems easily breakable.

[jtdubs]

It depend if the bayesian method is naive or not.

If for the top 1000 highest and lowest words you build a pair-wise table of each highest paired with each lowest and keep probabilities for these pairs as well then that would solve the problem.

For regular email that contain no spam words, no problem. For spam that contain only spam words, no problem. For spam that contain both kinds of words the pair table would catch them.

I mean, how many valid emails can you possibly have that both have scientific terms and words like "hot teen sex." Unless, of course, it's a scientific study about either spam, or hot teen sex.

Unless, of course, I'm completely wrong about this whole thing and just don't realize it, which is sometimes far more likely than I approve of.

Justin Dubs

Re:Method seems easily breakable.

[guybarr]

I mean, how many valid emails can you possibly have that both have scientific terms and words like "hot teen sex." Unless, of course, it's a scientific study about either spam, or hot teen sex.

well, for "hot teen sex", or "novel penis enlargement techniques available today !!" spam, I guess you're right. but for "get your mortguage now!", or for "cheap toner at amazing prices!" kind of spam this seems more tricky.

Unless, of course, I'm completely wrong about this whole thing and just don't realize it, which is sometimes far more likely than I approve of.

I'm no expert either, just skepticaly paranoid ...

available for KMail /Evolution/Mozilla?

[egghat]

Lot of implementations mentioned in this thread, but does anyone know of an implementation for the most wildly used E-Mail clients under Linux/BSD: KMail, Evolution and Mozilla?

TIA for any links.

Bye egghat.

Anyone tried TMDA?

[fanatic]

I lkie the soun of this one - seems like it should eliminate all false positives sent by real peope and all false negatives. I worry about auto-responders and auto-reminders, though. TMDA (Tagged Message Delivery Agent)

a few things

[Gumber]

1. it is a patent, not a trademark
2. just because someone has a patent doesn't mean the patent can't be challenged.
3. just because someone has a patent doesn't mean a patent will be enforced.
4. Some things are worth fighting for