The Grumpy Editor's guide to bayesian spam filters

This article is part of the LWN Grumpy Editor series.

If there is one thing which is especially effective at making your editor grumpy, it is spam. The incoming flood consumes bandwidth, threatens to drown out the stream of real mail, and creates ongoing system administration hassles. With current tools, it is possible to keep spam from destroying the utility of the email system. But it's not always easy or fun.

In recent years, much of the development energy in anti-spam circles has gone into bayesian filters. The bayesian approach was kicked off in 2002 with the publication of Paul Graham's A plan for spam. In its simplest form, a bayesian filter keeps track of words found in email messages and, for each word, a count of how many times that word appeared in spam and in legitimate mail ("ham"). Over time, these statistics can be used to examine incoming mail and come up with a probability that each is spam.

Bayesian filters have proved to be surprisingly effective. A well-trained filter can catch a high proportion of incoming spam with a very low false positive rate. The filter will adapt to each user's particular email stream, which is an important feature. It should not be surprising that different people have wildly different legitimate email. It turns out, though, that the spam stream can also vary quite a bit. An account which looks like it could belong to a woman, for example, will tend to get messages offering to alter the sizes of different parts of the recipient's anatomy than a man's account. So the ability to tune a filter to a specific mail stream - ham and spam - will increase its accuracy.

There is quite a large selection of free bayesian filters out there. Your editor decided to have a look around to see if there is any reason to prefer one over the others. To that end, a number of characteristics were examined:

• Accuracy. A filter which does not accurately classify mail will not be of much use, so good results in this area are required. In particular, false positives (legitimate mail classified as spam) must be avoided.

• Training. Bayesian filters must be trained before they become effective. Some filters, it turns out, are easier to train than others. In general, the training process is somewhat like house-training a puppy: it's a painful process, involving contact with unpleasant materials, and with a messy failure mode. And, somewhere in the process, something you care about is likely to get chewed up. So, in general, this is a process which one would like to be done with quickly and not have to do again later on.

  There are people who lovingly tweak and tune their spam filters the way an automobile enthusiast tweaks his car. Your editor is not one of those people. Life is too short - and too busy - to spend a lot of time screwing around with spam filters.

• Speed. The difference in performance between the fastest and slowest filters covers two orders of magnitude. Since filtering tends to be done in the background, speed will not be crucially important to all users. When filtering is being done on a busy mail server, however, processing speed can matter a lot.

• Ease of integration. How much work is it to hook a filter into the mail stream?

To carry out the tests, your editor collected two piles of mail from his personal stream; one was purely spam, and the other ham. Just over 1,000 messages from each pile were set aside to be used to train the filters. Then, 6,000 hams and 9,000 spams were fed to each filter, with the filter's verdict and processing time being recorded. Each mis-classified message was immediately fed back to the filter to further train it. Multiple runs were made with different parameters, but, in general, your editor resisted the urge to go tweaking knobs. Some of these filters offer a vast number of obscure parameters to set; one can only hope they come with reasonable defaults.

As a side note, your editor was surprised and dismayed at how difficult the task of producing pure sets of spam and ham was. The process started with mail sorted by SpamAssassin at delivery time. Your editor then passed over the entire set, twice, reclassifying each message which was in the wrong place. It was only after some early tests started reporting "false positives" that it became clear how much spam still lurked in the "ham" pile. It took more manual passes, and many passes with multiple filters, to clean them all out. The developers who claim that their filters do a better job than a human does are right - when that human is your editor, at least. It also turns out that a few incorrectly classified messages can badly skew the results; bayesian filters are easily confused if you train them badly.

Anyway, the results will be presented in five batches of 1200 hams and 1800 spams. Nothing special was done between these batches; this presentation is intended to show how the filter's behavior evolves as it is trained on more messages. All of the results are also pulled together in a summary table at the end of the article.

Bogofilter

Bogofilter was originally written by Eric Raymond shortly after Paul Graham's article was posted. It has evolved over time, and has picked up a wider community of contributors and maintainers. Bogofilter uses a modified version of the bayesian technique, with a number of knobs to tweak. It is written in C and is quite fast.

Training for bogofilter is somewhat complex; your editor was unable to train it into a stable configuration by feeding it hams and spams directly. The presence of several different training scripts in the source tree's "contrib" directory suggests that others have had to put some work into training as well. In the end, the contributed "trainbogo.sh" script appeared to do a reasonable job, but it required about three runs to get bogofilter into a stable state.

Bogofilter offers two approaches to ongoing training. By default, the filter is not trained by new messages as it classifies them. People who use bogofilter in this mode will set aside bogofilter's mistakes for later training. When the -u option is provided, however, bogofilter will train itself on all messages it feels sufficiently strongly about. Use of -u makes retraining on mistakes even more important, or the filter will become increasingly likely to misclassify mail. In general, training a bayesian filter on its own output must be done with care. It can help the filter to keep up with the spam stream as it evolves, but it also is a positive feedback loop which can go badly wrong if not carefully watched.

Your editor ran bogofilter (v1.01) in both modes (starting with a freshly trained database in each case). Here's the results:

Batch:	1			2			3			4			5
	Fn	Fp	T	Fn	Fp	T	Fn	Fp	T	Fn	Fp	T	Fn	Fp	T	Size
bogofilter	141	0	0.02	69	0	0.01	96	0	0.02	48	0	0.02	52	0	0.02	5
bogofilter -u	87	0	0.05	54	0	0.05	41	0	0.05	45	0	0.06	41	0	0.09	32

Legend: Fn is the number of false negatives (spam which makes it through the filter); Fp is false positives (legitimate mail misclassified as spam), and T is the processing time (clock, not CPU), in seconds per message. The Size value at the end is the final size of the word database, in MB.

Here we see that bogofilter without the -u option tends toward around 50 missed spams out of a set of 1800 (a 2.8% error rate), but with no false positives at all. If bogofilter self-trains itself, the false negative rate drops to closer to 2.2%. As we will see, these results are not as good as some of the other filters reviewed.

Without self-training, bogofilter requires a roughly constant 0.02 seconds of time to classify a message; with self-training, that time increases as the word database grows. Bogofilter is clearly fast - the fastest of all the filters reviewed here. One of the ways in which it gains that speed is to not bother with attachments in the mail. The web page says "Experience from watching the token streams suggests that spam with enclosures invariably gives itself away through cues in the headers and non-enclosure parts."

Bogofilter is intended to be integrated as a simple mail filter, optimally invoked via procmail. It can place a header in processed messages (making life easy for procmail) and also returns the spam status in its exit code (making life easy for grumpy editor testing scripts). Bogofilter has options for dumping out the word database and, for a given message, listing the words which most influenced how that message was classified. Nothing special has been done to make retraining easy; most users will probably create folders of mistakes and occasionally feed them to the filter.

CRM114

An interesting - if intimidating - offering is CRM114, subtitled "the controllable regex mutilator." While the main use of CRM114 appears to be spam filtering, it has a wider scope; it can be trained, for example, to filter interesting lines out of logfiles. According to the project page:

This tool comes with a 275-page book in PDF format, and needs every one of those pages. Setting up CRM114 is not for the faint of heart; it involves the manual creation of database files and the editing of a long configuration file which, while not quite up to sendmail.cf standards, is still one of the more challenging files your editor has encountered in some time. Once all of that is done, however, the "crm" executable can be hooked into a procmail recipe in the usual way without too much trouble.

The CRM114 documentation recommends against any sort of initial training of the filter. The developers are strong believers in the "train on errors" approach, saying that there are "mathematically complicated" reasons why pre-training leads to worse results. For users who don't get the hint, they do provide a way to perform pre-training:

The prospect of hand-decoding binary spam attachments is likely to put off most people who were pondering pre-training their filters - and, one assumes, that is the desired result. Of course, one can also use the normal training commands to feed messages into the system in a pre-training mode, but the documentation doesn't say that.

While filter training can be done on the command line, users can also retrain the filter by forwarding errors back to themselves. The message must be edited to include a training command and password; the developers also recommend removing anything which shouldn't be part of the training. Strangely, users are also told to remove the markup added by CRM114 itself - something which, one would think, could be handled automatically.

Your editor tested the 20060118 "BlameTheReavers" release of CRM114. The first test was done without training, as recommended; then, just to be stubborn, a test was run with a pre-trained filter.

Batch:	1			2			3			4			5
	Fn	Fp	T	Fn	Fp	T	Fn	Fp	T	Fn	Fp	T	Fn	Fp	T	Size
CRM114	1	1	0.06	1	1	0.06	3	2	0.06	4	6	0.06	5	6	0.07	24
CRM pretrain	6	2	0.07	1	2	0.07	5	2	0.07	1	2	0.07	1	6	0.07	24

Some things jump out immediately from those numbers. CRM114 is quite fast. It is also quite effective very early on; the first 3000 messages were processed with exactly one false positive and one false negative - starting with an untrained filter. On the other hand, its performance appears to worsen over time, and, in particular, the false positive rate grows in a discouraging way. The false positives varied from vaguely spam-like messages (Netflix updates, for example) to things like kernel patches. Your editor concludes that CRM114 operates as a very aggressive and quick-learning filter, but that it is also relatively unstable.

DSPAM

DSPAM is a GPL-licensed filter written in C. It is clearly aimed at large installations - places with dedicated administrators and, possibly, relatively unsophisticated users. As a result, it has a few features not found in other systems. For example, it has a web interface with statistics, facilities to allow users to manage filter training, and "pretty graphs to dazzle CEOs." Users who don't want to train the filter through a web page can forward mistakes to a special address instead.

There are several ways to hook DSPAM into the mail system, including a command-line filter, a POP proxy, and an SMTP front-end which can be put between the net and the mail delivery agent. There are several choices of backend storage (SQLite, Berkeley DB, PostgreSQL, MySQL, Oracle, and more), and a number of different filtering techniques. The filter can also run in a client-server mode, much like SpamAssassin.

DSPAM is also a package with a dual-license option; companies interested in shipping the software without providing source can purchase a separate license from the developer.

The system is intended to require relatively little maintenance. It has a set of tools, meant to be run from cron, which handle much of the routine housekeeping. Among other things, DSPAM will automatically trim its word list - getting rid of terms which have not been seen for a while and which have little influence on message scoring.

Initial training can be performed using the dspam_train utility; it uses a train-on-errors approach. Thereafter, DSPAM offers several training modes. The recommended "teft" mode trains on every message passing through the system. There is a train-on-errors mode, and a "tum" mode ("train until mature") which emphasizes relatively new and uncommon words. Your editor ran DSPAM (in the standalone, command-line mode) using all three training schemes, with the following results:

Batch:	1			2			3			4			5
	Fn	Fp	T	Fn	Fp	T	Fn	Fp	T	Fn	Fp	T	Fn	Fp	T	Size
DSPAM teft	17	0	0.1	17	0	0.1	11	0	0.1	3	0	0.1	7	0	0.1	305
DSPAM toe	23	0	0.1	21	3	0.1	12	0	0.1	3	1	0.1	8	4	0.1	276
DSPAM tum	26	0	0.1	23	0	0.1	12	0	0.1	7	0	0.1	15	0	0.1	305

So DSPAM shows strong spam detection in all three modes with a mid-range execution time; it is much slower than bogofilter, but much faster than some of the alternatives. The comprehensive training mode would appear to be the most effective; the TUM mode increases the false negative rate slightly, and the TOE mode introduces false positives. Note that the DSPAM database is quite large; to a great extent, this volume is taken up by a directory full of message hashes used to keep track of which messages have been used to train the filter.

SpamAssassin

SpamAssassin, which is written in Perl, is unique among the filters tested in that it combines a bayesian filter with a large set of heuristic scoring rules. The filter, in essence, is just another rule which gets mixed in with the rest. The rule database takes a great deal of effort (on the part of the SpamAssassin developers) to maintain, and testing messages against all of those rules makes SpamAssassin relatively slow. There is a huge advantage to this approach, however: SpamAssassin works well starting with the first message it sees, and it is able to train its own bayesian filter using the results from the rules.

Another nice feature in SpamAssassin is its word list maintenance. Most bayesian filters seem to grow their word lists without bound. Since spam can contain a great deal of random nonsense (actually, much of your editor's ham does as well), the word list can quickly fill up with tokens which are highly unlikely to ever help in classifying messages. Documentation for some other filters suggests occasionally dumping the word list and starting over. SpamAssassin, instead, will occasionally (and automatically) delete tokens which have not been seen for some time. So the word list stays within bounds. In general, SpamAssassin is relatively good at minimizing the need for the user to perform maintenance tasks.

The sa-learn utility is used for most bayesian filter tasks. It can retrain the filter on mistakes, dump out word information, and force cleanup operations. SpamAssassin can be run in a client/server mode, which improves performance on busy systems. The client/server mode can also help to put a bound on SpamAssassin's memory use, which can be a little frightening. Standalone SpamAssassin on a small-memory system can create severe thrashing.

Your editor ran two sets of tests with SpamAssassin 3.1.0, running in the client/server mode, with network blacklist tests enabled. (Before somebody asks: the test was run on a standalone system to avoid any possible contamination by your editor's regular mail stream). Exactly one scoring tweak was made: the score for BAYES_99 (invoked when the bayesian filter is absolutely sure that the message is spam) was set to 5.0, enabling the filter to condemn messages on its own. That change helps to emphasize the bayesian side of SpamAssassin, and, in your editor's experience, makes it more effective. The first test involved a pre-trained database, as was done with the other filters. The second test, instead, started with an empty bayesian database in an effort to see how well the tool trains itself. Here's the results:

Batch:	1			2			3			4			5
	Fn	Fp	T	Fn	Fp	T	Fn	Fp	T	Fn	Fp	T	Fn	Fp	T	Size
SpamAssassin	8	0	1.1	3	0	1.1	5	0	1.1	3	0	1.0	2	0	1.0	10
SA untrained	32	0	0.6	9	0	1.0	18	0	1.0	15	0	1.0	7	0	1.0	10

The results here show that SpamAssassin filters up to 99.9% of incoming spam, at the cost of significant amounts of CPU time. The untrained run shows higher error rates, but does eventually converge on something similar to the pre-trained version. But, at over one second per message, each testing run (comprising 15,000 messages) took a rather long time.

SpamAssassin operates as a filter, adding a header to messages as they pass through. That header can be used in procmail recipes; the thunderbird mail agent is also set up to optionally use the SpamAssassin header.

SpamBayes

SpamBayes is a filter written in Python. The SpamBayes hackers have, perhaps more than some of the other filter developers, made tweaks to the bayesian algorithm in an attempt to improve performance. Those hackers have also put more effort into mail system integration than some; as a result, SpamBayes comes with an Outlook plugin, POP and IMAP proxy servers, and a filter for Lotus Notes. It is still possible to use SpamBayes as a command-line filter with procmail, however.

There is a separate script (sb_mboxtrain.py) which is used to train the filter. Your editor followed the instructions and found it seemingly easy to use - it nicely understands things like MH and Maildir folders. However, when used as documented, sb_mboxtrain.py happily (and silently) puts the resulting word database in an undisclosed location, and filtering works poorly. Adding a few options to make the database location explicit took care of the problem.

SpamBayes 1.0.4 was tested in two modes: retraining just on errors, and training on all messages.

Batch:	1			2			3			4			5
	Fn	Fp	T	Fn	Fp	T	Fn	Fp	T	Fn	Fp	T	Fn	Fp	T	Size
SpamBayes	71	0	0.4	44	0	0.4	29	0	0.4	21	0	0.4	20	1	0.4	4
SB train all	90	0	0.8	58	0	0.8	54	0	0.8	46	0	0.9	46	0	0.9	16

SpamBayes takes a while to truly train itself, but it does eventually get to a 98.9% filtering rate - better than some, but not truly amazing. The word database remains relatively small, but processing time is significant - especially if comprehensive training is used. Everything gets worse with comprehensive training, however - the spam detection rate drops while processing time increases. SpamBayes is able to avoid false positives in both modes, however.

SpamProbe

SpamProbe is a filter written in C++ and released under the Q Public License. Unlike most filters, which record statistics on individual words, SpamProbe is also able to track pairs of words (DSPAM can do that too). SpamProbe looks at text attachments, discarding other types of attachments with one exception: there is a simple parser for GIF images. This parser creates various words describing images in a message (based on sizes, color tables, GIF extensions, etc.) and uses them in evaluating each message.

SpamProbe is packaged as a single command with a vast number of options. There is an "auto-train" mode for getting the filter trained in the first place. There are two filtering modes which the author calls "train" and "receive." Both will filter the message; the "train" mode only updates the word database "if there was insufficient confidence in the message's score," while "receive" always updates the database. The author recommends "train" mode; your editor tested SpamProbe 1.4a in both modes:

Batch:	1			2			3			4			5
	Fn	Fp	T	Fn	Fp	T	Fn	Fp	T	Fn	Fp	T	Fn	Fp	T	Size
SpamProbe train	80	0	0.2	39	1	0.1	37	1	0.1	39	1	0.1	27	0	0.1	81
SP receive	90	0	0.6	51	2	0.6	39	1	0.6	42	0	0.7	35	1	0.9	201

SpamProbe's "receive" mode demonstrates that, with bayesian filters, more training is not always better. The added training slows down processing significantly, to the point that SpamProbe is almost as slow as SpamAssassin, but the end results are worse than those obtained without comprehensive training. SpamProbe has a significant false positive rate in either mode, but the "receive" mode makes it worse. In either mode, SpamProbe generates vast amounts of disk traffic, rather more than was observed with the other filters.

Unlike most other filters, SpamProbe does not insert a header in filtered mail. Instead, it emits a single line giving its verdict; the author then suggests using a tool like formail to create a header using that score. So integration of SpamProbe is a little harder than with some other tools.

Summary

Here is a summary table combining all of the filter runs described above:

Test	False neg.		False pos.		Time	Size
bogofilter	406	5.5%			0.02	5
bogofilter -u	268	3.0%			0.06	32
CRM114	14	0.1%	16	0.3%	0.06	24
CRM114 pretrain	14	0.2%	15	0.3%	0.06	24
DSPAM teft	50	0.6%			0.1	305
DSPAM toe	67	0.7%	15	0.3%	0.1	276
DSPAM tum	83	0.9%			0.1	305
SpamAssassin	21	0.2%			1.1	10
SpamAssassin untrained	81	0.9%			0.9	10
SpamBayes	185	2.1%	1	0.02%	0.4	4
SpamBayes train all	294	3.3%			0.8	16
SpamProbe train	222	2.5%	3	0.05%	0.1	81
SpamProbe receive	257	2.9%	4	0.07%	0.7	201

In the above table, the "false positives" columns were left blank for tests in which there were none. Since false positives will be the bane of any spam filter, it is good if they stand out.

One should, of course, take all of the above figures with a substantial grain of salt. They reflect performance on your editor's particular mail stream; things could be very different with somebody else's mail. Still, your editor's mail stream is varied enough that, perhaps, a few conclusions can be drawn.

One of those would be that SpamAssassin is still hard to beat. It is, by far, the slowest of the filters, but it is highly effective with a minimum amount of required setup and maintenance on the user's part. For the most part, it Just Works, and it works quite well. In situations where an administrator is setting things up for a large group of users, DSPAM may well be indicated. The broad flexibility of that tool make it easy to integrate into just about any mail system, and the web interface makes its operation relatively transparent to users. Just be sure you have a big disk for its databases.

CRM114 is an interesting project; its combination of technologies has the potential to make it the most accurate of all the filters. It has the look of a hardcore power tool. This tool, however, is not ready for prime time at this point. It is a major hassle to set up, and, for your editor at least, keeping the filter stable was a challenge. The other three filters all have their strong points, but none of them had the level of spam detection that your editor would like to see.

There are, of course, other filters out there as well. Some of the graphical mail clients have started to integrate their own filters. There is a great convenience in having a "junk" button handy, but the integrated filters sacrifice transparency and, in your editor's (admittedly limited) experience, they do not seem to develop the same level of accuracy. There is also ifile, which is intended to be a more general mail classifier. That tool is no longer under development, however.

In the end, none of the filters reviewed is perfect - it would be nice to see no spam at all. But some of them are surprisingly close. Think back, for a minute, to the days when were complaining about getting a dozen spams per day - or per week. Who would have thought that we would be able to cope with thousands of spams per day and still deal with our mail? The developers of these filters have, in a significant way, saved the net, and your editor thanks them.

---

to post comments

1.0 Thoughts about increasing spam annoyance
    1.1 Bouncing messages do no good
    1.2 Rule based systems are not the solution
    1.3 Challenge-Response systems make matters worse
       1.3.1 Challenge-Response is not a doorbell but a  gun shooting decoys
       1.3.2 Modern C-R systems are no better
       1.3.3 Questioning Challenge-Response system implementations
       1.3.4 Summary - What are the effects of Challenge-Response systems
       1.3.5 Further reading - Mail, C-R systems, Spam
       1.3.6 Further reading - Some known C-R systems
    1.4 Spam appearing in your yard - a story

2.0 A  lightweight UBE block system with pure procmail
    2.1 Suitable for accounts which ...
    2.2 Where to put "pure procmail" UBE checks?
    2.3 Using Procmail Module Library to fight spam

3.0 A heavyweight UBE blocking system
    3.1 Advice for Debian Exim 4 mail system administrator
    3.2 Advice for the normal account
    3.3 Configuring  Bayesian programs
    3.4 A heavyweight spam catch setup using procmail