buryspam

A Bayesian Spam Filter

Introduction

This page describes how to use the buryspam.rb script. For an informative and informal discussion of the practice and theory behind Bayesian spam filtering, please see Paul Graham's A Plan For Spam web page, which provided much of the inspiration for the implementation of this program.

Note that the script as well as this documentation is very much a work in progress. Please report any problems to donald@cs.mun.ca

Local Administrative Notes

The buryspam.rb script was developed using version 1.8.0 of ruby (Dated 2003-08-04). This version of ruby is currently installed on garfield. Other versions of ruby may or may not work as expected.

If the grad partition becomes inaccessible, mail delivery may be adversely affected if you call the script on the grad partition from your ~/.procmailrc file. procmail should try to recover messages that could not be processed due to a missing filter, but I've experienced mixed results in this respect.

To be safe, you may want to copy the the buryspam.rb script to your own directory instead of invoking it directly from /users/cs/grad/donald/pub/bin. This way, if the grad partition becomes inaccessible, your copy of the buryspam.rb script will still be accessible.

Is buryspam.rb appropriate for you?

Note that if you use an e-mail client that transfers messages off of garfield (using, for example, POP or IMAP), then the buryspam.rb filtering script may not be appropriate for you. This is because the script relies on having a collection of good and bad messages stored on the server for initialization purposes. It may be possible to use buryspam.rb on the client side to initialize the filter but the file resulting from the initialization would have to be transferred manually to the server. This may be more trouble than it's worth. Also, note that the buryspam.rb filter requires that all messages be stored in Unix mbox format.

buryspam.rb is more suited to those who read their e-mail using client software directly on the mail server itself (e.g. pine, mutt, elm etc.). You also have to be willing to modify configuration files and your .procmailrc file.

Getting started

1. Move legitimate and spam messages to separate directories: In order for Bayesian filtering to be effective, one must have an existing collection of legitimate e-mail (this includes messages from mailing lists and personal mailings -- both from you and to you) and also a collection of spam messages. Typically, a few thousand of each is required for accurate results, but be careful not to use too many, otherwise the generation of the word probability file may consume too much time and resources. The folders or mboxes containing legitimate messages and spam messages should be placed in separate directories. For example, it is common to keep all legitimate messages in your ~/mail directory. Spam messages can be kept in a subdirectory of this directory (e.g. ~/mail/junk).
2. Create a ~/.buryspamrc file: This file contains all the configuration options related to the bayesian filtering. Only three parameters must be set explicitly. You must set the good_dirs parameter to the directory containing the legitimate mail. If you have more than one directory that contains legitimate messages, set good_dirs to a comma delimited list of directory names. Next, you must set the bad_dirs parameter to the directory containing all the spam mail. As with the good_dirs parameter, you can specify a comma separated list of such directories. Last, you must specify the name of the file that will be used to store the word probability database (which is generated automatically below). Ideally, you should probably specify a file that is in a subdirectory of your ~/mail directory (e.g. ~/mail/lib). Make sure that you create this directory if is doesn't already exist. It is important to specify the full path name of the good/bad directories and the word database file. You may use the tilde ~ character to represent your home directory. All three of these parameters are strings and therefore must be delimited by double-quotes in the rc file. For example, the following minimal ~/.buryspamrc file indicates that legitimate messages are stored in the directories ~/mail and ~/mail/old directories; a collection of spam messages are stored in the ~/mail/junk folder and the word probability database file is ~/mail/lib/words

   
             good_dirs = "~/mail,~/mail/old"
             bad_dirs  = "~/mail/junk"
             word_file = "~/mail/lib/words"
   
   

   Again, remember that the directory containing the word probability database file (~/mail/lib in the example above) must be created if it doesn't exist. The actual word file itself will be generated in the next step.
3. Run buryspam.rb --init: When supplied with the --init option, the script will scan through all the legitimate message and spam directories specified in the configuration file and count the messages and word frequencies present in each. Upon processing all the messages, the bayesian probabilities are calculated for each word and the word probability database (specified by the word_file configuration parameter above) is populated. This process will take some time (upto several minutes). If is taking too long, then you may want to terminate the process (by pressing Ctrl-C) and archive some of the older messages to other directories which will not be processed by the script.
4. Create/update your ~/.procmailrc file: Make sure you have a ~/.procmailrc file whose contents resemble the following:

   	SHELL=/bin/sh
   	PATH=/bin:/usr/bin
   	LOGFILE=$HOME/mail/.procmail.log
   	MAILDIR=$HOME/mail
   
   	:0fw
   	| /users/cs/grad/donald/pub/bin/buryspam.rb --filter
   
   	:0:
   	* ^X-Bayesian-Spam: Yes
   	junk/spam
   

   Note that the junk directory specified above in the ~/.procmailrc file must be created in your ~/mail directory (if it doesn't already exist).

That's it. After this, all messages you receive will be sent through the bayesian filter. If it detects a spam message it will add the header line X-Bayesian-Spam: Yes to the message. Otherwise, the header line X-Bayesian-Spam: No is added. The ~/.procmailrc file will then deposit any messages with the spam header to the ~/mail/junk/spam folder and leave all your legitimate messages in your default mail spool. Extra header lines containing the actual bayesian value calculated for the message as well as the words that sparked the bayesian filter's "interest" can also be generated by setting the verbose_hdr parameter in your ~/.buryspamrc file to true.

Important Notes

• False positives (legitimate messages which get filtered as spam), while very, very rare, can still occur. As a result it is a good idea to occasionally go through your spam folder and see if any legitimate messages accidentally got mis-filtered. If you do find such mis-filtered messages, move them back to a folder in one of you legitimate mail directories and re-initialize the word probability database (i.e. re-run buryspam.rb --init).
• If you had a reasonable collection of spam messages when you started bayesian filtering, it should not be necessary to regenerate the word probability database too often. As a rule of thumb you may want to regenerate the database whenever new variants of spam messages start to seep through the filter. Because the regeneration of the word probability database can consume significant resources, it is a good idea to do so only during off-peak hours.
• Generally speaking, you should not delete spam messages. They can be used again the next time you regenerate your word database. The more spam you have, the more resilient the filter becomes the next time you regenerate the word probability database.
• In order to make subsequent regenerations of the word database fast, the program generates a cache of word counts for each mail folder that it encounters during its initial scan. By default, these files are located in a subdirectory of the directory containing the word database file. During subsequent reinitializations of the word probability database, these caches are consulted and used if the corresponding mail folder has not changed.
• The filter will automatically attempt to rename spam files that have accumulated about five megabytes of data. Doing will make re-initialization the word database more efficient since the word count of the newly renamed spam file will only have to be done once more. After that, the results of the cache can be used as long as the contents of the renamed spam file remains the same. New spam messages will automatically be deposited in the a new spam file.
• If "bad things" are happening to your messages (i.e. legitimate messages are not getting through), you may want to disable the bayesian filter by temporarily commenting out the appropriate lines in the ~/.procmailrc file (you may also temporarily rename your ~/.procmailrc file). You should then check your ~/mail/.procmail.log file for any errors. It's always a good idea to check your ~/mail/.procmail.log for errors and warning messages.

Configuration File

The format of each line of the configuration file, ~/.buryspamrc, is:

parameter_name = parameter_value

Only the first three parameters given below compulsory, the remainder are optional and can be used to fine tune the filter. The defaults, many of which are from Paul Graham's web page described above, are usually sufficient.

The buryspam.rb script tries to be helpful in diagnosing errors in the rc file. If there are any errors in the configuration file, the script will simply pass any messages through unfiltered and then terminate. If the script is being run from your ~/.procmailrc file, errors will be logged to your ~/mail/.procmail.log file (provided LOGFILE is set appropriately in your ~/.procmailrc file).

The following options are supported by the buryspam.rb script in the ~/.buryspamrc configuration file.

Usage

buryspam.rb <option> [mbox files]

For most (but not all) options, if no mboxes are specified on the command line, then input will be taken from stdin.

option can be specified as follows:

If standard input is available to the running script, then ALL options are ignored and the script runs in --filter mode.

Exactly one operating mode of --initialize, --decode-only, --colour, --filter, --grep, --stats, --report xor --auto MUST be specified.

If no valid mbox files are given on the command lines for the arguments --decode-only, --colour, --filter, --report or --grep then ALL the mboxes in the good/bad directories (as specified in ~/.buryspamrc) are used.

Sample ~/.buryspamrc File

	good_dirs 	= "~/mail,~/mail/old"
	bad_dirs 	= "~/mail/junk,~/mail/more-junk,~/mail/even-more-junk"
	word_file	= "~/mail/bin/ruby/words"

	word_length	= 3..16
	ignore_probs	= 0.3..0.7
	verbose_hdr	= true
	spam_threshold  = 0.8

Potential Problems/Bugs

• Because the ruby binary and the script reside on the grad partition, mail will not be filtered if this partition is down.
• If a message is received while the word database is being reinitialized, then there is a (very) small window of time that the filter may read a corrupt database. This issue will be resolved when I find a reliable way to do file locking over NFS with ruby.
• Cache files will become wasted space whenever its corresponding mail folder is removed. Periodically removing all the files in the cache directory and regenerating the word database from scratch will correct this (but that is kind of expensive).
• Unfortunately, the processing of the ~/.buryspamrc file makes liberal use of the eval command in ruby. This allows for robust type checking of the various configuration options. However, any ruby commands present in the rc file will be executed with the same permissions of the the person running the script. Needless to say, this is a potential security hole if your rc file is ever compromised.
• I'm not sure if this method is suitable for widespread deployment. The script can take a few seconds to process each incoming message (most of the time is spent reading the word probabilities file). If a site receives hundreds of messages a second, then the filter will very quickly become a bottleneck if it is used to process every message for every user at the site.
• If you rename an mbox file (either spam or non-spam) you may have to manually delete its corresponding cache file if the contents of the mbox also change.
• The program consumes quite a bit of memory during the initialization of the word probability database. Many improvements were made since previous versions, but there is probably still room for further improvements.
• Because the filter reads the contents of the entire message before processing it, there is a potential for a DoS attack if a sufficiently large message is sent to the filter.

Potential Improvements

• One improvement may be to allow spam folders to be deleted and instead rely solely on the contents of its corresponding cache file during re-initialization. Unfortunately, this will mean that generating a new word database based using a different word_regex or word_length, for example, would not be possible.
• Compressing the cache files would help to save space. But filtering would be slightly slower.
• Rather than using md5sums to determine if an mbox was changed, it would be simpler (and faster) just to compare the timestamps of the mbox and the corresponding word cache file during word file initialization. Unfortunately, if the mbox is somehow touched (even without otherwise being changed), then the word cache would have to be regenerated. Worse, if the word cache file was accidentally touched after an mbox was updated, the updated mbox would not be processed during re-initialization.
• The ability to incrementally add/remove messages from an mbox and have the corresponding word counts/probabilities updated may be a good idea.
• The program would likely be faster if it were written in C.

--
Donald Craig (donald@cs.mun.ca)
Mon Mar 28 12:32:47 NST 2005