[Greg Ward]

One of the other perennial-seeming topics on spamassassin-devel (a list that I follow only sporodically) is that careful manual cleaning of your corpus is *essential*. The concern of the main SA developers is that spam in your non-spam folder (and vice-versa) will prejudice the genetic algorithm that evolves SA's scores in the wrong direction. Gut instinct tells me the Bayesian approach ought to be more robust against this sort of thing, but even it must have a breaking point at which misclassified messages throw off the probabilities.

Like all other questions <wink>, this can be quantified if someone is willing to do the grunt work of setting up, running, and analyzing appropriate experiments. This kind of algorithm is generally quite robust against disaster, but note that even tiny changes in accuracy rates can have a large effect on *you*: say that 99% of the time the system says a thing is spam, it really is. Then say that degrades by a measly 1%: 99% falls to 98%. From *your* POV this is huge, because the error rate has actually doubled (from 1% wrong to 2% wrong: you've got twice as many false positives to deal with). So the scheme has an ongoing need for accurate human training (spam changes, list topics change, list members change, etc; the system needs an ongoing random sample of both new spam and new non-spam to adapt).

... One possibility occurs to me: we could build our own corpus by collecting spam on python.org for a few weeks.

Simpler is better: as you suggested later, capture everything for a while, and without injecting Mailman or SpamAssasin headers. That won't be a particularly good corpus for the lists in general, because over any brief period a small number of topics and posters dominate. But it will be a fair test for how systems do over exactly that brief period <wink>.

Here's a rough breakdown of mail rejected by mail.python.org over the last 10 days, eyeball-estimated messages per day:

bad RCPT 150 - 300 [1] bad sender 50 - 190 [2] relay denied 20 - 180 [3] known spammer addr/domain 15 - 60 8-bit chars in subject 130 - 200 8-bit chars in header addrs 10 - 60 banned charset in subject 5 - 50 [4] "ADV" in subject 0 - 5 no Message-Id header 100 - 400 [5] invalid header address syntax 5 - 50 [6] no valid senders in header 10 - 15 [7] rejected by SpamAssassin 20 - 50 [8] quarantined by SpamAssassin 5 - 50 [8]

We should start another category, "Messages from Tim rejected for bogus reasons" <wink>.

[1] this includes mail accidentally sent to eg. giudo@python.org, but based on scanning the reject logs, I'd say the vast majority is spam. However, such messages are rejected after RCPT TO, so we never see the message itself. Most of the bad recipient addrs are either ancient (ipc6@python.org, grail-feedback@python.org) or fictitious (success@python.org, info@python.org).

[2] sender verification failed, eg. someone tried to claim an envelope sender like foo@bogus.domain. Usually spam, but innocent bystanders can be hit by DNS servers suddenly exploding (hello, comcast.net). This only includes hard failures (DNS "no such domain"), not soft failures (DNS timeout).

[3] I'd be leery of accepting mail that's trying to hijack mail.python.org as an open relay, even though that would be a goldmine of spam. (OTOH, we could reject after the DATA command, and save the message anyways.)

[4] mail.python.org rejects any message with a properly MIME-encoded subject using any of the following charsets: big5, euc-kr, gb2312, ks_c_5601-1987

[5] includes viruses as well as spam (and no doubt some innocent false positives, although I have added exemptions for the MUA/MTA combinations that most commonly result in legit mail reaching mail.python.org without a Message-Id header, eg. KMail/qmail)

[6] eg. "To: all my friends" or "From: <>"

[7] no valid sender address in any header line -- eg. someone gives a valid MAIL FROM address, but then puts "From: blah@bogus.domain" in the headers. Easily defeated with a "Sender" or "Reply-to" header.

[8] any message scoring >= 10.0 is rejected at SMTP time; any message scoring >= 5.0 but < 10 is saved in /var/mail/spam for later review

Greg, you show signs of enjoying this job too much <wink>.

Executive summary:

* it's a good thing we do all those easy checks before involving SA, or the load on the server would be a lot higher

So long as easy checks don't block legitimate email, I can't complain about that.

* give me 10 days of spam-harvesting, and I can equal Bruce Guenter's spam archive for 2002. (Of course, it'll take a couple of days to set the mail server up for the harvesting, and a couple more days to clean through the ~2000 caught messages, but you get the idea.)

If it would be helpful for me to do research on corpora that include the headers, then the point would be to collect both spam and non-spam messages, so that they can be compared directly to each other. Those should be as close to the bytes coming off the pipe as possible (e.g., before injecting new headers of our own). As is, I've had to throw the headers away in both corpora, so am, in effect, working with a crippled version of the algorithm. Or if someone else is doing research on how best to tokenize and tag headers, I'm not terribly concerned about merging the approaches untested. If the approach is valuable enough to deploy, we'll eventually see exactly how well it works in real life.

... Perhaps that spam-harvesting run should also set aside a random selection of apparently-non-spam messages received at the same time. Then you'd have a corpus of mail sent to the same server, more-or-less to the same addresses, over the same period of time.

Yes, it wants something as close to a slice of real life as possible, in all conceivable respects, including ratio of spam to not spam, arrival times, and so on.

Oh, any custom corpus should also include the ~300 false positives and ~600 false negatives gathered since SA started running on mail.python.org in April.

Definitely not. That's not a slice of real life, it's a distortion based on how some *other* system screwed up. Train it systematically on that, and you're not training it for real life. The urge to be clever is strong, but must be resisted <0.3 wink>. What would be perfectly reasonable is to run (not train) the system against those corpora to see how it does. BTW, Barry said the good-message archives he put together were composed of msgs archived after SpamAssassin was enabled. Since about 80% of the 1% "false positive" rate I first saw turned out to be blatant spam in the ham corpus, this suggests SpamAssassin let about 160000 * 1% * 80% = 12800 spams through to the python-list archive alone. That doesn't jibe with "600 false negatives" at all. I don't want to argue about it, it's just fair warning that I don't believe much that I hear <wink>. In particular, in *this* case I don't believe python-list actually got 160000 messages since April, unless we're talking about April of 2000.

On 28 August 2002, Tim Peters said:

What's an acceptable false positive rate?

Speaking as one of the people who reviews suspected spam for python.org and rescues false positives, I would say that the more relevant figure is: how much suspected spam do I have to review every morning? < 10 messages would be peachy; right now it's around 5-20 messages per day. Currently there are probably 1-3 FPs per day, although on a bad day there can be 5-10. (Eg. on 2002-08-21, six mailman-users posts from the same guy were all caught, mainly because his ISP added X-AntiAbuse, and his messages were multipart/alternative with unwrapped plain text. This is a perfect example of SpamAssassin screwing up royally.) 1-3 FPs/day I can live with, but the real burden is the manual review: I'd much rather have 5 FPs in a pool of 10 suspects than 1 FP out of 100 suspects.

What do we get from SpamAssassin?

Recall the stats I posted this morning; the bulk of spam is in Chinese or Korean, and I have things setup so SpamAssassin never even sees it. I think the only way to meaningfully answer this question is to stash *everything* mail.python.org receives for a day or 10, spam and otherwise, and run it all through SA. Greg

[Tim, last week]

What's an acceptable false positive rate?

[my response]

Speaking as one of the people who reviews suspected spam for python.org and rescues false positives, I would say that the more relevant figure is: how much suspected spam do I have to review every morning? < 10 messages would be peachy; right now it's around 5-20 messages per day.

[Tim again]

I must be missing something. I would *hope* that you review *all* messages claimed to be spam, in which case the number of msgs to be reviewed would, in a perfectly accurate system, be equal to the number of spams received.

Good lord, certainly not! Remember that Exim rejects a couple hundred messages a day that never get near SpamAssassin -- that's mostly Chinese/Korean junk that's rejected on the basis of 8-bit chars or banned charsets in the headers. Then, probably 50-75% of what SA gets its hands on scores >= 10.0, so it too is rejected at SMTP time. Only messages that score < 10 are accepted, and those that score >= 5.0 are set aside in /var/mail/spam for review. That's 10-30 messages/day. (I do occasionally scan Exim's reject log on mail.python.org to see what's getting rejected today -- Exim kindly logs the full headers of every message that is rejected after the DATA command. I usually make it to about 11am of a given day's logfile before my eyes glaze over from the endless stream of spam and viruses.) Note that we *used* to accept messages before passing them to SpamAssassin, so never rejected anything on the basis of its SA score. Back then, we saved and reviewed probably 50-70 messages/day. Very, very, very few (if any) false positives scored >= 10.0, which is why that's the threshold for SMTP-time rejection.

OTOH, the false positive rate doesn't have anything to do with the number of spams received, it has to do with the number of non-spams received.

Err, yeah, good point. I make a point of talking about "suspected spam", which is any message that scores between 5.0 and 10.0. IMHO, the true nature of those messages can only be determined by manual inspection.

Maybe you don't want this kind of approach at all. The classifier doesn't have "gray areas" in practice: it tends to give probabilites near 1, or near 0, and there's very little in between -- a msg either has a preponderance of spam indicators, or a preponderance of non-spam indicators.

That's a great improvement over SpamAssassin then: with SA, the grey area (IMHO) is scores from 3 to 10... which is why several python.org lists now have a little bit of Mailman configuration magic that makes MM set aside messages with an SA score >= 3 for list admin review. (It's probably worth getting the list admin to do a bit more work in order to avoid sending low-scoring spam to the list.) However, as long as "very little" != "nothing", we still need to worry a bit about that grey area. What do you think we should do with a message whose spam probability is between (say) 0.1 and 0.9? Send it on, reject it, or set it aside? Just how many messages fall in that grey area anyways? Greg -- Greg Ward <gward@python.net> http://www.gerg.ca/ MTV -- get off the air! -- Dead Kennedys

Tim Peters wrote:

Under Graham's scheme, send it on. It doesn't have grey areas in a useful sense, becuase the scoring step only looks at a handful of extremes: extremes in, extremes out, and when it's wrong it's *spectacularly* wrong (e.g., the very rare (< 0.05%) false positives generally have "probabilties" exceeding 0.99, and a false negative often has a "probability" less then 0.01).

I noticed that as well. When the classifier goes wrong it goes badly wrong and using different thresholds would not help. It seems that increasing the number of discriminators doesn't really help either. Too bad because otherwise you could flag those messages for human classification. On the bright side, based on the number of mis-classified messages in my corpus, it looks like a human would have a very hard time doing a better job. Perhaps all that is needed is a bypass mechanism for that small fraction of non-spammers. That way if their initial message is rejected they would still have some way of getting through. Erik Naggum made an interesting comment. He said that spam should be handled at the transport level. Greg's work on doing filtering at SMTP time accomplishes this and makes a lot of sense. When a message is rejected, the sending mail server is the one that has to deal with it. In the case of spam, the sending server is often an open rely. Letting it handle the bounces is sweet justice. :-) I bring this up because "STMP time filtering" makes a bypass mechanism work much better. With a system like TMDA, confirmation notices usually generate double-bounces. Instead, we could reject the message with a 5xx error that includes instructions on how to bypass the filter (e.g. include a cookie in the body of the message). Neil

[Neil Schemenauer]

I noticed that as well. When the classifier goes wrong it goes badly wrong and using different thresholds would not help. It seems that increasing the number of discriminators doesn't really help either. Too bad because otherwise you could flag those messages for human classification.

I think it's worse than just that: suppose any scheme says "OK, this is spam, with probability 0.9995". If it's reporting accurate probabilities, then another way to read that claim is "On average, one time in 2000 this message actually isn't spam". In real life we have to accept that there's no scheme with a 0% false positive rate-- not even human review --short of the scheme that never calls anything spam. Since deciding on the largest acceptable false positive rate is far more a social than a technical issue, a group of nerds will do anything rather than face it <wink>.

Neil Schemenauer <nas@python.ca> writes:

I bring this up because "STMP time filtering" makes a bypass mechanism work much better. With a system like TMDA, confirmation notices usually generate double-bounces. Instead, we could reject the message with a 5xx error that includes instructions on how to bypass the filter (e.g. include a cookie in the body of the message).

TMDA doesn't do this because it would make more work for the sender to get his message delivered. Because TMDA stores the incoming messages in a local queue, the sender just has to reply to a confirmation request, and his original message gets delivered. As opposed to having to cut and paste his message from the body of a bounce and then resend it. So, not operating at the transport level saves your correspondents some work at the expense of some bandwidth. -- (http://tmda.net/)

[Charles Cazabon]

I would love to see how the results would be affected by applying the scoring scheme to the entire content of the message, instead of just the 15 (or 16 in your case) most extreme samples.

Then it would be close to a classic Bayesian classifier, and like any such would need entirely different scoring code to avoid catastrophic floating-point errors (right now an intermediate result can't become smaller than 0.01**16 = 1e-32, so fp troubles are impossible; raise the exponent to a measly 200 and you're already out of the range of IEEE double precision; classic classifiers word in logarithm space instead for this reason). You can read lots of papers on how those do; all evidence suggests they do worse than this scheme on the spam versus non-spam task.

By the way, you never said why you increased that number by one;

It's explained in the comment block preceding the MAX_DISCRIMINATORS definition. BTW, in an unreported experiment I boosted MAX_DISCRIMINATORS to 36. I don't recall what happened now, but it was a disaster for at least one of the error rates.

did it make that much difference?

Not on average. It helped eliminate a narrow class of false positives, where previously the first 15 extremes the classifier saw had 8 probs of .99 and 7 of .01. That works out to "spam". Making the # of classifiers even instead allowed for graceful ties, which favor ham in this scheme. All previous decisions "should be" revisited after each new change, though, and in this particular case it could well be that stipping HTML tags out of plain-text messages also addressed the same narrow issue but in a more effective way (without some special gimmick, virtually every message including so much as an example of HTML got scored as spam).

[Tim]

... The first 16 most extreme indicators are split 9 highly in favor of ham (.01) and 7 highly in favor of spam (.99). If I hadn't folded case away to let stinking conference announcements through <wink>, I expect it would have latched on to the SCREAMING at the start instead of looking deeper. Looking at the To: line probably would nail this one too, as "Undisclosed Recipients" has two 0.99 spam indicators right there.

Whatever, you *don't* want to look at msgs with a mix of just 0.99 and 0.01 thingies: it's not all that unusual to get such an extreme mix, in spam or ham.

I should have added that it usually gets the right result when this happens. It's the exceptions to that rule that are mondo embarrassing, because it's making a mistake then while sitting on a mountain of strong evidence (albeit pointing as extremely as possible in both directions at once <wink>). "A problem" is that when a MIN_SPAMPROB and MAX_SPAMPROB clue both appear, the math is such that they cancel out exactly. It's *almost* as if neither existed, but not quite: they also keep two lower-probability words *out* of the computation (only a grand total of the MAX_DISCRIMINATORS most extreme clues are retained). So I changed spamprob() to keep accepting more clues when MIN/MAX cancellations are inevitable, and to use the best of those in lieu of the cancelling extremes. This turned out to be a pure win: false positive percentages 0.000 0.000 tied 0.000 0.000 tied 0.050 0.050 tied 0.000 0.000 tied 0.025 0.025 tied 0.025 0.025 tied 0.050 0.050 tied 0.025 0.025 tied 0.025 0.025 tied 0.025 0.025 tied 0.075 0.075 tied 0.025 0.025 tied 0.025 0.025 tied 0.025 0.025 tied 0.075 0.025 won 0.025 0.025 tied 0.025 0.025 tied 0.000 0.000 tied 0.025 0.025 tied 0.050 0.050 tied won 1 times tied 19 times lost 0 times total unique fp went from 9 to 7 false negative percentages 0.909 0.764 won 0.800 0.691 won 1.091 0.981 won 1.381 1.309 won 1.491 1.418 won 1.055 0.873 won 0.945 0.800 won 1.236 1.163 won 1.564 1.491 won 1.200 1.200 tied 1.454 1.381 won 1.599 1.454 won 1.236 1.164 won 0.800 0.655 won 0.836 0.655 won 1.236 1.163 won 1.236 1.200 won 1.055 0.982 won 1.127 0.982 won 1.381 1.236 won won 19 times tied 1 times lost 0 times total unique fn went from 284 to 260

[Skip Montanaro]

... One thing I think would be worthwhile would be to run GBayes first, then only run stuff it thought was spam through SpamAssassin. Only messages that both systems categorized as spam would drop into the spam folder. This has a couple benefits over running one or the other in isolation:

* The training set for GBayes probably doesn't need to be as big

Training GBayes is cheap, and the more you feed it the less need to do information-destroying transformations (like folding case or ignoring punctuation).

* The two systems use substantially different approaches to identifying spam,

Which could indeed be a killer-strong benefit.

so I suspect your false positive rate would go way down.

I'm already having a real problem with this just looking at content: the false positive rate is already so low that I can't make statistically significant conclusions about things that may improve it (e.g., if I do something that removes just *one* false positive in a test run on 4000 hams, the false-positive rate falls by 12.5% -- I don't have enough false positives to make fine-grained judgments. And, indeed, every time I test a change to the algorithm, the most *significant* thing I find is that it turns up another class of blatant spam hiding in the ham corpus: my training data is still too dirty, and cleaning it up is labor-intensive).

False negatives would go up, but only testing can suggest by how much.

* Since SA is dog slow most of the time, SA users get a big speedup, since a substantially smaller fraction of your messages get run through it.

This sort of chaining is pretty trivial to setup with procmail. Dunno what the Windows set will do though.

There are different audiences here. Greg is keen to have a better approach for python.org as a whole, while Barry is keen about that and about doing something more generic for Mailman. Windows isn't an issue for either of those. Everyone else can eat cake <wink>.

Tim Peters <tim.one@comcast.net>:

Spammers often generate random "word-like" gibberish at the ends of msgs, and "rd" is one of the random two-letter combos that appears in the spam corpus. Perhaps it would be good to ignore "words" with fewer than W characters (to be determined by experiment).

Bogofilter throws out words of length one and two.

I expect that including the headers would have given these much better chances of getting through, given Robin and Alex's posting histories. Still, the idea of counting words multiple times is open to question, and experiments both ways are in order.

And bogofilter includes the headers. This is important, since otherwise you don't rate things like spamhaus addresses and sender names. -- <a href="http://www.tuxedo.org/~esr/">Eric S. Raymond</a>

[Tim, predicting a false-positive rate]

I expect we can end up below 0.1% here, and with a generous meaning for "not spam",

We're there now, and still ignoring the headers.

but I think *some* of these examples show that the only way to get a 0% false-positive rate is to recode spamprob like so:

def spamprob(self, wordstream, evidence=False): return 0.0

Likewise. I'll check in what I've got after this. Changes included: + Using the email pkg to decode (only) text parts of msgs, and, given multipart/alternative with both text/plain and text/html branches, ignoring the HTML part (else a newbie will never get a msg thru: all HTML decorations have monster-high spam probabilities). + Boosting MAX_DISCRIMINATORS, from 15 to 16. + Ignoring very short and very long "words" (this is Eurocentric). + Neither counting unique words once nor an unbounded number of times in the scoring. A word is counted at most twice now. This helps otherwise spamish msgs that have *some* highly relevant content, but doesn't, e.g., let spam through just because it says "Python" 80 times at the start. It helps the false negative rate more, although that may really be due to that UNKNOWN_SPAMPROB is too low (UNKNOWN_SPAMPROB is irrelevant to any of the false positives remaining, so I haven't run any tests varying that yet). I'll attach a complete listing of all false positives across the 20,000 ham msgs I've been using. People using c.l.py as an HTML clinic are out of luck. I'd personally call at least 5 of them spam, but I've been very reluctant to throw msgs out of the "good" archive -- nobody would question the ones I did throw out and replace. The false negative rate is still relatively high. In part that comes from getting the false positive rate so low (this is very much a tradeoff when both get low!), and in part because the spam corpus has a surprising number of msgs with absolutely nothing in the bodies. The latter generate no tokens, so end up with "probability" 0.5. The only thing I tried that cut the false negative rate in a major way was the special parsing+tagging of URLs in the body (see earlier msg), and that was a highly significant aid (it cut the false negative rate in half). There's good reason to hope that adding headers into the scoring would slash the false negative rate. Full results across all 20 runs; floats are percentages: Training on Data/Ham/Set1 & Data/Spam/Set1 ... 4000 hams & 2750 spams testing against Data/Ham/Set2 & Data/Spam/Set2 ... 4000 hams & 2750 spams false positive: 0.025 false negative: 2.10909090909 testing against Data/Ham/Set3 & Data/Spam/Set3 ... 4000 hams & 2750 spams false positive: 0.05 false negative: 2.47272727273 testing against Data/Ham/Set4 & Data/Spam/Set4 ... 4000 hams & 2750 spams false positive: 0.1 false negative: 2.50909090909 testing against Data/Ham/Set5 & Data/Spam/Set5 ... 3999 hams & 2750 spams false positive: 0.0500125031258 false negative: 2.8 Training on Data/Ham/Set2 & Data/Spam/Set2 ... 4000 hams & 2750 spams testing against Data/Ham/Set1 & Data/Spam/Set1 ... 4000 hams & 2750 spams false positive: 0.05 false negative: 2.8 testing against Data/Ham/Set3 & Data/Spam/Set3 ... 4000 hams & 2750 spams false positive: 0.075 false negative: 2.47272727273 testing against Data/Ham/Set4 & Data/Spam/Set4 ... 4000 hams & 2750 spams false positive: 0.15 false negative: 2.36363636364 testing against Data/Ham/Set5 & Data/Spam/Set5 ... 3999 hams & 2750 spams false positive: 0.0500125031258 false negative: 2.43636363636 Training on Data/Ham/Set3 & Data/Spam/Set3 ... 4000 hams & 2750 spams testing against Data/Ham/Set1 & Data/Spam/Set1 ... 4000 hams & 2750 spams false positive: 0.075 false negative: 3.16363636364 testing against Data/Ham/Set2 & Data/Spam/Set2 ... 4000 hams & 2750 spams false positive: 0.075 false negative: 2.43636363636 testing against Data/Ham/Set4 & Data/Spam/Set4 ... 4000 hams & 2750 spams false positive: 0.15 false negative: 2.90909090909 testing against Data/Ham/Set5 & Data/Spam/Set5 ... 3999 hams & 2750 spams false positive: 0.0750187546887 false negative: 2.61818181818 Training on Data/Ham/Set4 & Data/Spam/Set4 ... 4000 hams & 2750 spams testing against Data/Ham/Set1 & Data/Spam/Set1 ... 4000 hams & 2750 spams false positive: 0.1 false negative: 2.65454545455 testing against Data/Ham/Set2 & Data/Spam/Set2 ... 4000 hams & 2750 spams false positive: 0.1 false negative: 1.81818181818 testing against Data/Ham/Set3 & Data/Spam/Set3 ... 4000 hams & 2750 spams false positive: 0.1 false negative: 2.25454545455 testing against Data/Ham/Set5 & Data/Spam/Set5 ... 3999 hams & 2750 spams false positive: 0.0750187546887 false negative: 2.50909090909 Training on Data/Ham/Set5 & Data/Spam/Set5 ... 3999 hams & 2750 spams testing against Data/Ham/Set1 & Data/Spam/Set1 ... 4000 hams & 2750 spams false positive: 0.075 false negative: 2.94545454545 testing against Data/Ham/Set2 & Data/Spam/Set2 ... 4000 hams & 2750 spams false positive: 0.05 false negative: 2.07272727273 testing against Data/Ham/Set3 & Data/Spam/Set3 ... 4000 hams & 2750 spams false positive: 0.1 false negative: 2.58181818182 testing against Data/Ham/Set4 & Data/Spam/Set4 ... 4000 hams & 2750 spams false positive: 0.15 false negative: 2.83636363636 The false positive rates vary by a factor of 6. This isn't significant, because the absolute numbers are so small; 0.025% is a single message, and it never gets higher than 0.150%. At these rates, I'd need test coropora about 10x larger to draw any fine distinction among false positive rates with high confidence.