Subject: Re: [Asrg] March spam ratio

From: Matt Sergeant <[email-masked]>
Date: Tue, 1 Apr 2003 11:21:39 +0100

On Monday, Mar 31, 2003, at 19:59 Europe/London, Dave Crocker wrote:

> MS> Wouldn't it be more sane to ask people to check the archives for 
> that
> MS> poster? *sigh*
>
> I'm afraid I have no idea what you mean by this text.  I do not
> understand the sentence.

I've posted statistics before, hence I would hope people can find out 
the extra information I had to give.

> MS> the globe). So some has got through (about 92-98% accuracy is 
> usual).
> MS> Spam is detected by a variety of means, but most spam is detected 
> via
>
> as was noted, the link points to a virus monitor, not a spam monitor.

It seems people can't follow links. I realise I should have been more 
specific, but if you download the monthly report it contains all the 
spam details.

> MS> heuristics (and no I'm not proposing this as a long term solution 
> to
>
> Virus detection that permits labeling the specific virus -- as is done
> in the viruseye display -- does not use heuristics.  The code does
> pattern matching, but not "guessing".

Our AV stuff uses signatures for mopping up the vast majority of known 
viruses, which gives the names. For unknown viruses we use heuristics. 
Often new viruses get called "Generic" but sometimes the heuristic will 
point to it being a new variant of an old virus, so we'll have a name 
already using heuristics.

But all this is irrelevant. Follow the links. I'd have posted a direct 
download to the March monthly report but it wasn't available at the 
time I wrote. It still doesn't seem to be available. When it is, it 
will be here: http://www.messagelabs.com/data/viruseye-monthly/mar03.pdf

> When heuristics DO get used, the obvious requirement is for 
> accompanying
> statistics about rates of false positives and false negatives. That is,
> confidence levels for the heuistics.

Anti-Virus error rate is 0 FN's and 1 in 1 million FPs.
Anti-Spam error rate is about 1 in 1000 FPs based on detecting about 
95% of spam.

Matt.

_______________________________________________
Asrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/asrg

---

From: Dave Crocker <[email-masked]>
Date: Tue, 1 Apr 2003 09:06:40 -0800

Matt,

MS> Anti-Virus error rate is 0 FN's and 1 in 1 million FPs.
MS> Anti-Spam error rate is about 1 in 1000 FPs based on detecting about
MS> 95% of spam.

thanks!

hmmm. it occurs to me that a technical research group on spam might want
to consider look to agree on standard methodology for deriving false
negatives and false positives. this would allow everyone to compare
mechanisms in an equivalent way.

given the nature of spam, and the nature of most technologies for
detecting it, the determination of FNs and FPs is not automatically
obvious.  that makes it a fertile opportunity for standardization.

d/
--
 Dave Crocker <mailto:[email-masked]>
 Brandenburg InternetWorking <http://www.brandenburg.com>
 Sunnyvale, CA  USA <tel:+1.408.246.8253>, <fax:+1.866.358.5301>

---

From: [email-masked] (Justin Mason)
Date: Tue, 01 Apr 2003 10:47:15 -0800

> obvious.  that makes it a fertile opportunity for standardization.

May I suggest using Ion Androutsopoulos' metrics?   He wrote some of the
seminal papers on naive Bayesian classification's effectiveness as a spam
filter, and proposed a very helpful metric -- TCR -- which we in
SpamAssassin have used as a result for a couple of years.  It's a nice way
to get an idea of effectiveness distilled into 1 number.

TCR takes into account a concept of "wasting the user's time" with FPs and
FNs.  In summary, FPs are much more inconvenient for the user, so should
be penalised much more heavily.

Too many FPs, and you've created so much work for the user, they would be
better off without your spam filter (a TCR of < 1.0) -- for example, the
MAPS RBL blacklists are reportedly this bad, according to effectiveness
rates posted by an analyst company 1.5 years ago. ;)

He also uses recall and precision metrics, which are the traditional
2-number metrics used in classification research, as far as I can see.

A citeseer, or even Google, search for his name will throw up these papers
quickly.

PS: one issue we ran into BTW is that the current crop of bayesian filters
do not make binary classifications; instead they typically classify mail
in the set { ham, unsure, spam } -- a triple-option classification.
Dealing with "unsures" with the traditional metrics is hard...

--j.

---

From: Clifton Royston <[email-masked]>
Date: Wed, 2 Apr 2003 10:38:23 -1000

> obvious.  that makes it a fertile opportunity for standardization.

  I had spent a while this past weekend looking at appropriate metrics
for a single number to compare FP and FN rates across a range of spam
blocking or filtering solutions.  I came up with one that seems
interesting as providing a single, fairly easy to grasp, number for the
overall accuracy discrimination of an email classification system.

  This measure should be applicable to any machine classification
system for email, whether it means rejected at an SMTP gateway, flagged
in an email header. for now I'm calling it "dSpam" because it is
modelled on a decibel like scale.

  This does not take into account the differential cost of false
positives and false negatives; I do want to look at the Androutsopoulos
paper for this TCR measure.  However, I think it is potentially useful.

  Begin by assuming "spam" to be identifiable on inspection by a human
being, and define ham = ! spam, because it is shorter than writing
not-spam all the time.  (For definitional purposes, we assume no middle
ground.) Define "flagged" as a classification of an email as spam by
the system under measurement.

  I define FP and FN with the provision that they are not allowed to
be = 0, but otherwise in the standard way:  

  measure     spam category       ham category 
  -------     ---------------     --------------
  flagged     N(flagged-spam)     N(flagged-ham)
  unflagged   N(unflagged-spam)   N(flagged-ham)
  -------     ---------------     --------------
  total       N(spam)             N(ham)

  Then FP = max(N(flagged-ham),0.5 ) / N(ham)
       FN = max(N(unflagged-spam),0.5) / N(spam)

  Using the minimum of 1.5 for the numerator avoids undefined values in
the log computation, and also deliberately penalizes results claiming
"zero false positives" or "zero false negatives" if they use a small
sample size.

  The tentative definition for "dSpam" is:
 10 * ( -log10(FP) - log10(FP) + log(1/4) ) 
  where the log(1/4) addition is a normalizing factor.  (This is
equivalent to -10*log(FP*FN*4), etc.)

  I would recommend that this measure always be qualified with a note
on the corpus it was based on, and a note on how the determination of
actual spam/non-spam was made.

  This measure has the following desirable properties:

1) dSpam for a random (coinflip) classification of mail as spam/nonspam
   is 0.

2) dSpam is independent of the total spam/ham ratio in an input set.

3) Increasing dSpam is "good"

4) Reducing either the FP rate or the FN rate while holding the other
   constant results in a monotonically increasing dSpam.

5) It has reasonable values over the range of rates we need to consider
   (one doesn't have to deal with exponential notations and so on)

6) The relationship between two values is fairly clear; if dSpam(A) is
   10 greater than dSpam(B), then we can say system A is roughly 10
   times "better" than system B in terms of its discrimination, in that
   FP(A)*FN(A) = (1/10) * FP(B)*FN(B).

Here are some values from the published STATISTICS.txt file for
SpamAssassin 2.50 on various thresholds, on its own testing corpus:

SpamAssassin threshold	Data surce	FP	FN		dSpam
---------------------------------------------------------------------
SA threshold 7.0	STATISTICS.txt	0.02%	16.28%		38.9
SA threshold 6.5	STATISTICS.txt	0.03%	14.42%		37.6
SA threshold 6.0	STATISTICS.txt	0.05%	10.83%		36.6
SA threshold 5.5	STATISTICS.txt	0.09%	8.88%		35.0
SA threshold 5.0	STATISTICS.txt	0.16%	6.95%		33.5
SA threshold 4.5	STATISTICS.txt	0.55%	5.52%		29.2
SA threshold 4.0	STATISTICS.txt	0.81%	4.51%		28.4
SA threshold 3.0	STATISTICS.txt	1.86%	2.91%		26.6
  
  This allows us to easily say, for instance, that SpamAssassin
discriminates more precisely at higher threshold settings.

  For another example, assume a hypothetical RBL (or perhaps a
sender-verification scheme) which rejects 98% of offered spam at the
SMTP level but also rejects mail from 3% of valid sites.  That would
stack up like this:

           Spam   Ham
 ---------------------
 flagged    98%    3%
 unflagged   2%   97%
 ---------------------
 total     100%  100%

  dSpam = -10*log(0.02*0.03*4) = 26.2, or around one order of
magnitude worse than SpamAssassin.

  Personal stats from a system I have been running here:

Filter              	 Source		FP	FN		dSpam
---------------------------------------------------------------------
Paleopala-Gold (Jan-Feb) personal	0.19%	14.70%  	29.5

  The magnitude of spam reduction that some people have talked about as
the needed breakthrough in damaging the economic model for Spam is a
thousand-fold reduction in delivered spam, with less than 0.1% false
positives (0.1% effect on normal mail.)  That's easily calculated as 
 dSpam =  -10*log(0.001*0.001*4) = 54.0, 
or about another 15 dSpam over existing solutions.

  Here are some problems with this metric, before everyone else points
them out:

1) The trivial systems which classify all mail as spam or all mail as
non-spam get arbitrarily high scores, because either lim(FN)->0 or
lim(FP)->0 as sample size increases.

2) Generally, a system which reduces either false positives or false
negatives to an extreme gets rated better than it "should"; e.g. dSpam
for 0.05% false negatives and 50% false positives = dSpam for a system
with .5% false positives and 5% false negatives, which would probably
be much more desirable.

3) The metric isn't biased against false positives, and should not be
used as the sole metric for a system.

  Its main virtue is that it allows us to start comparing different
systems with a single number which bears some relationship to the
desired attributes.  Comments on a better metric to improve or replace
this would be welcomed.

  -- Clifton

-- 
     Clifton Royston  --  LavaNet Systems Architect --  [email-masked]

  "If you ride fast enough, the Specialist can't catch you."
  "What's the Specialist?" Samantha says. 
  "The Specialist wears a hat," says the babysitter. "The hat makes noises."
  She doesn't say anything else.  
                      Kelly Link, _The Specialist's Hat_
_______________________________________________
Asrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/asrg

---

From: Clifton Royston <[email-masked]>
Date: Wed, 2 Apr 2003 10:52:13 -1000

Arrgh!  Following up to correct a couple critical typos below which I
didn't catch when proofreading before sending it.  Sorry, I plead
Murphy's law.

>   measure     spam category       ham category 

                         0.5
 
>  10 * ( -log10(FP) - log10(FP) + log(1/4) ) 

   10 * ( -log10(FP) - log10(FN) + log(1/4) ) 

   i.e. includes the log of both false positive rate and false negative
rate, not FP twice.

  -- Clifton

---

From: Vernon Schryver <[email-masked]>
Date: Wed, 2 Apr 2003 15:20:54 -0700 (MST)

> From: Clifton Royston <[email-masked]>

> ...
> ...

Because the differential costs of false positives and negatives differ
by orders of magnitude, any spam defense metric that consists of a
single number will have very limited utility.  Some people value not
receiving spam 100 times more than not receiving legitimate mail and
so are happy with 10% false positive rates.  Other organizatiosn will
not tolerate 0.1% false positive rates no matter how many clerks must
be hired to manually filter spam.  A metric that says one system has
a value of 10 and second has a value of 100 cannot tell you which
system (if either) is usable, not mention which is better according
to your lights.

Vernon Schryver    [email-masked]
_______________________________________________
Asrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/asrg

---

From: Clifton Royston <[email-masked]>
Date: Wed, 2 Apr 2003 14:07:30 -1000

> system (if either) is usable, not mention which is better according

  Thank you.  I do appreciate your taking the time to give me some
feedback.

  I don't fundamentally disagree with your argument; no one number can
tell you everything about a system.  You can't evaluate a car knowing
only its mpg, especially without knowing its intended use.  One
alternative is to always quote comparably computed FP *and* FN rates,
but it does seem that people have a hard time comparing those in the
common case where one pairwise comparison is greater and the other
smaller.

  However it's also true that "Almost anything can be measured in some
way that is better than not measuring it at all." (I forget what
software engineering book I stole this line from.)

  The standard truism in this area is that achieving a higher filter
rate (meaning a lower false negative rate) means accepting a higher
false positive rate; my motivation for suggesting dSpam is in part for
it to measure how much a particular system gets past that.

  The main merit to my mind of having one number is that it allows you
to make some meaningful comparisons of similar systems, where certain
factors are bounded or held constant in the comparison.  In the case
you mention above, if the organization demands FP < 0.1%, and has to
choose between tuning a system to give them 0.02% FP and 16% FN, or
0.025% FP and 2% FN, dSpam might give them an idea which to prefer.

  Liudvikas Bukys suggested to me off-list that the measure could be
parameterized to reflect the users's perceived cost of FP relative to
FN.  For example, dSpam[1000] might represent your organization which
values one lost mail more than 1000 extra spams, and dSpam[.01] might
reflect your user who cares about blocking spam 100 times more than
they care about losing mail.  This is a very attractive idea, and
though it requires some thought, it might make the measure much more
useful.

  -- Clifton

---

From: Vernon Schryver <[email-masked]>
Date: Wed, 2 Apr 2003 19:12:40 -0700 (MST)

>                                                       ....  One

People who can't handle the two unavoidable dimensions won't be able
to handle a single number.  The fact that it is hard to compare a
system that measures {10,100} with another system that measures {100,10}
cannot be swept under the rug by combining the two numbers.

> 0.025% FP and 2% FN, dSpam might give them an idea which to prefer.

If you hold the FP rate constant or bounded by a number similar
to the underlying SMTP error rate, you don't need to worry about it
and have only one, easily understood and defended number.

> though it requires some thought, it might make the measure much more

I don't see a desirable different between saying  "dSpam[1000] = 50" and
saying "FP=1/1000 and FN=1/50"

You guys might be onto something interesting for deciding how to
quantify both sorts of filtering errors, but you will lose that good
work if you melt it down into a single, simplistic puddle.

---

From: Kee Hinckley <[email-masked]>
Date: Thu, 3 Apr 2003 16:55:16 -0500

>0.025% FP and 2% FN, dSpam might give them an idea which to prefer.

I agree with Vernon.  One number doesn't cut it.  Actually, there was 
a very good talk at the MIT Spam Conference by Microsoft on this 
subject, and I think they did a good job of providing a way of 
evaluation systems.  That would be worth a check.

Of course I also was very fond of Praed's evaluation metric.  How 
well does it deal with deliberate evasion?  But that one is a little 
hard to measure.
-- 
Kee Hinckley
http://www.messagefire.com/          Junk-Free Email Filtering
http://commons.somewhere.com/buzz/   Writings on Technology and Society

I'm not sure which upsets me more: that people are so unwilling to accept
responsibility for their own actions, or that they are so eager to regulate
everyone else's.
_______________________________________________
Asrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/asrg