Subject: Re: [Asrg] greylisting with whitelist of good mailservers

From: "Eric A. Hall" <[email-masked]>
Date: Thu, 09 Feb 2006 01:25:25 -0500

On 1/29/2006 10:27 PM, William Leibzon wrote:

> What I'm thinking for one of the next stages is change this whitelisting
> ip database into (IP,score) where score is updated and is medium of the
> scores of the emails that came from the system before - i.e. it basicly
> is a real-time updated reputation system.

I did some work on something like this a while back by overloading the
SpamAssassin auto-whitelist database--tuples and reputation information is
already stored there, and I pass most incoming mail through SA while the
session is still active, so I get to reuse some of that info for free.
http://www.ehsco.com/misc/sagrey/ is where the SA plugin lives if you want
to look at it.

Right now I'm only using it to add an extra score for mail that appears to
be spam and originated from an unknown tuple, but what I want to do is
defer acceptance based on whether or not the rule fired (essentially
allowing me to restrict greylisting to mail that is likely spam from
unknown tuples). I couldn't do that with Postfix last time I looked
(header checks could not generate a DEFER action) and I haven't had time
to rebuild my whole mail system yet.

As to what you are pursuing, a similar approach would let you leverage the
reputation score associated with the tuple in the AWL, which seems to be
mostly what you are looking for.

-- 
Eric A. Hall                                        http://www.ehsco.com/
Internet Core Protocols          http://www.oreilly.com/catalog/coreprot/

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

---

From: [email-masked]
Date: Thu, 9 Feb 2006 01:57:53 -0800 (PST)

Thanks for the link Eric. It does look interesting and I'll take a look
at that code... My greylisting is actually done as sendmail milter and
not directly part of spamassasin. However my reputation system (I've 
already finished the initial code as spamsassin plugin) is - they will 
interface together by means of database. Spamassasin plugin code will be 
made public by end of the month or sooner since I'll need some additional 
testers to help with this research.

I do actually have quite a bit larger plans for all this and reputation 
database of single ips is just first step in it. One of the things I ran 
into is trying to decide what algorithm to use for calculating mean value
in real time. The obvious mean functions are arithmetic and harmonic mean 
and there is also geometric mean, but its arithmetical complexity is not 
likely to be worth it. The algorithms I thus intend to try are:

           MA(n)*n + S(n+1)
  MA(n+1)= ----------------   Where MA(x) is arithmetic mean at step x
                 n+1          with S(x) being actual score at step x

 	         n+1             Where MH(x) is harmonic mean at step x
  MH(n+1)= ------------------     with S(x) actual score at step x
 	  n/MH(n) + 1/S(n+1)

I also think that some kind of multiplier should be applied so that latest
data has highier weight then previous one, so this endup being:

             MA(n,w)*n + S(n+1)*w    Where MA(x,w) is arithmetic mean
  MA(n+1,w)= ------=-------------    at step x with weight w (w>1)
                    n + w

                    n + w            Where MH(x,w) is harmonic mean at
  MH(n+1,w)= --------------------    step x with weight w (w>1)
             n/MH(n,w) + w/S(n+1)

I'm actually not good with probability theories so if other can comment 
if I'm on the right track, it'd be good. Also the spam score function 
S(x) to me feel like a stochastic process, so something like bayes score 
calculations should probably be used. In any case if people here can point 
me to good book to read about real-time calculations & operations with 
stochastic functions, I'd appreciate it.

---
William Leibzon
   mailto: [email-masked]
Anti-Spam and Email Security Research Worksite:
   http://www.elan.net/~william/emailsecurity/
Whois & DNS Network Investigation Tools:
   http://www.completewhois.com

---

From: "Jon Kyme" <[email-masked]>
Date: Thu, 09 Feb 2006 10:58:16 +0000

William Leibzon:

> in real time. 

I am not a statistician, or indeed, any kind of mathematician, but I wonder
if a mean is really what you want? Aren't you kind of assuming that scores
are cardinal-ish if you're taking a mean? Are they? Do you really want a
set of scores like [5.1, 5.0, 5.2, 0.1] to give the same rep.(arithmetic
mean = 3.85) as the set [3.8, 3.9, 4.0, 3.7] ?

I know you could pick another average to get something better looking, but
I wonder if it would be more useful to refer to your threshold and count
overs/unders, spam/ham, whatever.

I don't know if you ever saw Mark Langston's (abandoned?) GOSSiP stuff? I
thought that there were some good ideas in there, although I guess you
wouldn't be interested in the distributed/co-operative aspects. I'm sure
there's some stuff on sourceforge.

---

From: "Peter J. Holzer" <[email-masked]>
Date: Thu, 9 Feb 2006 17:42:36 +0100

>                 n+1          with S(x) being actual score at step x

If n is constant, this doesn't really compute an arithmetic mean, but
the so-called "decaying average", where old values lose weight
exponentially with their age.

Of course, then the formula should be written as:

           MA(i)*n + S(i+1)
  MA(i+1)= ---------------- 
                 n+1       

to make it clear. This algorithm is used for unix load averages, for
example.

>  MA(n+1,w)= ------=-------------    at step x with weight w (w>1)

For constant n, this is equivalent to the formula above. Just divide
both numerator and denominator by w:

             MA(i,w)*n/w + S(i+1)*1
  MA(i+1,w)= ------=------------- 
                    n/w + 1

Then, you can just replace n/w with n and you have the same formula
again.

	hp

-- 
   _  | Peter J. Holzer    | Ich sehe nun ein, dass Computer wenig
|_|_) | Sysadmin WSR       | geeignet sind, um sich was zu merken.
| |   | [email-masked]         |
__/   | http://www.hjp.at/ |	-- Holger Lembke in dan-am
_______________________________________________
Asrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/asrg

---

From: Frank Ellermann <[email-masked]>
Date: Thu, 09 Feb 2006 17:51:50 +0100

[email-masked] wrote:

> The algorithms I thus intend to try are:
 
>                n+1          with S(x) being actual score at step x

That's just the normal MA.
 
> I also think that some kind of multiplier should be applied
> so that latest data has highier weight then previous one, so
> this endup being:
 
> MA(n+1,w)= ------=-------------    at step x with weight w (w>1)

You could get a similar effect for e.g. n > 99 with

            M99(n)*99 + S(n+1)
  M99(n+1)= ------------------   
                  100         
-- 
Frank

---

From: der Mouse <[email-masked]>
Date: Thu, 9 Feb 2006 12:01:49 -0500 (EST)

> the so-called "decaying average",

But the formula as written - ie, where n is the same n throughout -
*does* compute the arithmetic mean.  (Induction hypothesis: MA(n) is
the arithmetic mean of S(i<=n).  Induction step: MA(n)*n is then
sum(S(i<=n)), making the numerator sum(S(i<=n+1)) and MA(n+1) the
correct mean.)

I see no reason to insist on misreading the formula in order to get
something other than what the author claimed, when reading it as
written does get what was claimed.

/~\ The ASCII				der Mouse
\ / Ribbon Campaign
 X  Against HTML	       [email-masked]
/ \ Email!	     7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B

---

From: [email-masked]
Date: Thu, 9 Feb 2006 11:20:30 -0800 (PST)

On Thu, 9 Feb 2006, Jon Kyme wrote:

> are cardinal-ish if you're taking a mean?

That is why I said it looks like a stochastic process and was not sure if
using mean function is appropriate. It should also be noted that since
I'm using quantified (x.y) scoring data the sample space can be considered
to be a finite set - I can't yet decide if/how this would help though.

> Are they? Do you really want a

Testing will show if this concept works. But for now, yes I do want to 
them to give the same or similar score, I think with larger sample this 
would give fairly accurate information.

> overs/unders, spam/ham, whatever.

Counting spam/ham (and sometimes using spam/ham probabilities) is what
bayesean filters do. While this is somewhat similar I'm not trying to
create based on fuzzy logic but on arithmetic score. The mean score can 
thereafter be used as part of filtering process but not as yes/no answer.

[BTW - it may well be appropriate to think of every email as not being
  either spam or ham, but use fuzzy logic and apply it to every email,
  i.e. email can be considered ham for some and spam for others. Some new
  bayesian filters (spambayes in particular) appear to do that. This can
  be good research topic for discussion on this list]

> there's some stuff on sourceforge.

Distributed operation is one of the next steps after initial trial.
WPBL work can also prove useful there.

---
William Leibzon

---

From: Frank Ellermann <[email-masked]>
Date: Thu, 09 Feb 2006 22:09:36 +0100

der Mouse wrote:
 
> I see no reason to insist on misreading the formula in order
> to get something other than what the author claimed, when
> reading it as written does get what was claimed.

It wasn't absolutely clear - the comment talked about "step x"
instead of "step n+1" - and Peter wanted to explain the idea
of a "decaying mean", and why it's almost the same as William's
"weighted mean".  

My M99(n) formula was an example for this, each new S(n+1) is
represented in M99(n+1) by 1%, and 99% of it are for all older
S(n).  Works as is only for step n > 99 of course.  Bye, Frank