Revision as of 10:11, 18 March 2009

email... aka SMTP, aka rfc2822

There are some problems associated with email...

• spam.

Solution to spam problem

• A spam hash?

How does this solve?

A spam honeypot delivery point is known to recieve 100% spam. All incoming messages to this mailbox are then hashed with spamsum, and a database of hashes kept.

Then as a seperate filter, all incoming messages to anyone are checked against the database of hashes. If the new message rates as "similar", then it is also assumed to be spam, classified and sorted as such.

Lexicon used here

spamsum

the program that generates spamsum hashes.

hashDB

the database of spamsum scores. (currently implemented as a flat file: spamsum_scores)

spamcatches

archive of emails which were caught by being too similar to a pre-scored message

spamhashes

archive of emails that generated the hashDB

Notes

• ssdeep (based upon spamsum) is a maintained utility (in debian for eg) that can be used for some testing of effectiveness. However, it lacks the ability to accept data from STDIN, so cannot be used as a drop-in replacement to spamsum
• The hashDB should be rotated. New scores are appended at the end, so approx a month of scores to be kept. (note however that this is a flat text file with no internal dates (would spamsum mind if dates are munged in as "not formatted correctly spamsum scores"?), so rotation would likely have to be performed in a "number of lines" manner. Say, 'keep the last 10,000 scores' and rotate daily.
• filtered messages should be kept for sanity checking

Pros

• spamsum is quick, saves message being filtered by heavier bayesian/etc filters
• dynamically reacts to new spam as soon as a single message is seen.

Cons

• spampot address requires accepting messages we consider to be known spam. ie, is post-DATA - bandwidth for the spam is already consumed
  • however: could the spams caught then be datamined to generate dynamic blacklists of servers?

Scope

I expect spamsum to be equally usable at a personal and an organisation level. However, at a personal level I expect (awaiting testing) that it can be used on ALL email, on the expectation that the ONLY emails likely to match similarity to a previous email will be spam, thus allowing all ham through. This is not true for organisations, so a more dedicated spampot must be setup to create ONLY spam hashes. The accuracy of this spampot is likely to have a large impact on the false positives rate seen, though in part the same 'ham isn't duplicated' rule will apply.

Results

(Results table style taken from acme.com writeups)

Testing

Performance of the binary

I ran spamsum, ssdeep and md5sum over my 500+ meg procmail.log file. Three times over each to account for caching issues (note that procmail.log was live though, and grew 100k (over the runs). Whilst this may not be benchmark quality testing, the results I believe are so distinct as to be clear.

• spamsum averaged about 17minutes per run, using at best 23% CPU, and up to 5 mins of user time.
• ssdeep took about 5 minutes to run, using at best 35% CPU, and up to 2:20mins of user time.
• md5sum took at worst 44seconds, using at worst 2% CPU, and less than .5seconds user time.

Test run raw data

-rw------- 1 nemo nemo 562874616 Mar 17 08:42 procmail.log

spamsum procmail.log  294.56s user 4.48s system 31% cpu 15:40.24 total
ssdeep procmail.log  137.96s user 3.97s system 47% cpu 4:57.03 total
md5sum procmail.log  0.41s user 0.15s system 1% cpu 44.168 total

spamsum procmail.log  284.00s user 4.16s system 28% cpu 16:54.68 total
ssdeep procmail.log  120.85s user 3.84s system 35% cpu 5:52.64 total
md5sum procmail.log  0.31s user 0.13s system 0% cpu 44.070 total

spamsum procmail.log  264.34s user 4.19s system 23% cpu 19:22.42 total
ssdeep procmail.log  139.07s user 4.04s system 52% cpu 4:33.28 total
md5sum procmail.log  0.47s user 0.16s system 2% cpu 26.408 total

-rw------- 1 nemo nemo 562952378 Mar 17 09:57 procmail.log

TODO

Test over multiple small files (something more email-like)

Test Conclusions

Over LARGE files, the spamsum algorithm appears to be an order of magnitude slower than md5sum. The original spamsum itself is significantly slower than ssdeep - which has presumably been optimised somewhat in the intervening years.

Naive start on 100% spam honeypot

Some email addresses known to recieve spam were directed into the spamsum spampot and self-filtered (the procmail config below). After approx an hour, the spamcatches was already at 1:1 ratio of messages with the spamhashes. Remember, this is a self-teaching algorithm which at time zero has ZERO effectiveness. After the first day, it has rarely dropped below 70% for a given hour. As of 4 days, it appears to be stabilising between 85% and 90% (However: after 4 days I have a history of 3000 messages, only 450 are hashed. A spam history of a month or two (perhaps 10,000 messages?) which should improve the scoring? Additionally, If ALL caught spams are also hashed and added to the database, then not-quite-close enough variants may be caught before needing to be spamsummed

Remember however that this is on a mailbox which is assumed to be recieving 100% spam - so the possibility of false positives is not being tested yet, as such this cannot be claimed to be a 'scientific' test.

Configuration

My .procmailrc file within my spampot address

# all mail to this user is assumed to be spam. Nothing legit comes here.
# ...thus, generate a spamsum score on EVERYTHING

# note that spamhashes.d and spamcatches.d are directories (hence .d suffix)
# why? procmail will save each message as a file, allowing for easier rollover
# and also testing of messages

SHELL=/bin/sh
DROPPRIVS=yes
VERBOSE=on
LOGFILE=emailtmp/procmail.log

# (this comes first so spampot messages aren't spamsum'd twice
:0 Wc
| /usr/local/bin/spamsum -T25 -d emailtmp/spamsum_scores -C -
# 'a' means the previous recipe ran successfull. ie, this message is similar
# to a previously found spam in the spamsum score. So, we pull it now. 
:0 a
emailtmp/spamcatches.d

:0
{
       # if the message wasn't previously caught as being spam, then let's
       # mark it as potential spam now with spamsum scoring :)
       :0 c
       | /usr/local/bin/spamsum - >> emailtmp/spamsum_scores
       # and since it's a spampot, we save it seperate for now (for testing)
       :0
       emailtmp/spamhashes.d
}

# note that all deliveries could be to /dev/null as all messages are assumed to be spam. 
# safer will be to remove old messages from the caches after a short period (week?)

Thoughts

• Our test filter only determines is a spam is similar to a previously scored email. We don't know how similar. ie, we don't know how much our effectiveness would change with a different score.
  • Test this by running every spamcaught message over the hashDB and analysing scores resulting
  • Test also the spamsum cache messages to see how many more we could be capturing? (for each message in the cache, generate a spamsum, then grep -v that out from the hashDB (spamsum_scores file) so we don't get a perfect match, and generate a spamsum similarity score. Analyse... (alt: do this test with ssdeep)
• Greater efficiency: spamsum as a daemon?
• Different type of use: could the algorithm be altered to produce a hash which can validate partial messages. That way if a message was 50% recieved, but already was matching 100% score for that amount of data, we could close the connection early? (would development and in-use resource overhead be worth it just to move the scoring to the SMTP "DATA" phase?
• Is a spampot even nescessary? Couldn't this simply be run on a complete email dataset? Afterall, it works by allowing through the first instance of every unique email anyway, and ham tends to be relatively unique, whilst spam tends to come in repetitive sets...
  • Yes... in simple testing, simply quoting an email in response makes it quite dissimilar, and their reply (which should be the next that spamsum sees) will have two levels of reply! (TODO: get numbers)
  • TODO: test simply by feeding a weeks corpus of ALL my regular email through spamsum, simulating this.
    • Do this twice: Once naively, once with pre-learnt hashDB from the spampot
    • Then do it another way: over a known 100% ham corpus? (save a corpus of ham messages to MH or maildir format)
    • Expectation: this will be effective, except possibly for email memes. (if the same funny picture is sent to you twice, even by different people, they will be base64 encoded the same and thus show up as being EXTREMELY similar (how common this is should show up in the 100% ham corpus test)
• should all spams caught be spamsum'd also - ensuring a wider net? performance overhead with a blossoming hashDB? Benefit = not-quoite-close-enough to be caught spams may be close enough to other messages caught.
• Because this naturally blocks self-similar spam, might this in fact work AGAINST the effectiveness of downstream bayesian filters? (you'd not put a bayesian upstream of this, due to resource reasons)
  • I think (hope) not. Or not too much anyway. Bayesian notices fine-grained similarities, whilst spamsum only notices entire-content sized similarities.

TODO

• test spamsum memory and CPU usage over
  • LARGE files
  • LARGE hashDB dataset (say with 1000, 10,000, 100,000 results precomputed)
  • Both the above at once
  • Expectation: that memory will always be low (spamsum does not have to hold the entire file in memory to generate the spamsum?), CPU will get relatively high (yay data processing), and throughput will be limited by disk IO. (when run through procmail, the file is piped in - from disk or from ram?). Spamsum does take longer than md5 and similar cryptographic hashes, due to the nature of the hash generated. Comparing against a list of n hashes in hashDB, it is O(n) time. (see performance details in Kornblum's paper linked below)
• Check the spampot results for the timeframe that similar emails show up. (graph subject lines against dates?)
• investigate feasibility of datamining the spampot for servers that could be dynamically blacklisted, as well as generating dynamic header_checks and body_checks. Caution: apply such dynamism with extreme caution!
• graph the delivery rate to both caches (this should show spamsum cache delivery rate drop over time and level off - giving a good idea of appropriate retention policy

Links

Further spam reading here:

• A plan for Spam - Paul Graham
• http://www.acme.com/mail_filtering/ - This guy is the God of spam filterers
• http://code.google.com/p/pyspamsum/ - This is the version of spamsum I use (though I don't use the python wrapper)
• http://www.samba.org/ftp/unpacked/junkcode/spamsum/ - Tridge's original spamsum
• http://www.dfrws.org/2006/proceedings/12-Kornblum.pdf - a paper on identifying similar files. Develops ssdeep from spamsum
  • http://ssdeep.sourceforge.net/ - unlike spamsum which is effectively abandoned, this is in active development (and even in Debian!) :)
  • http://www.forensicswiki.org/wiki/Ssdeep - Discussion of ssdeep as a forensics tool