Subject: Re: Why Spam is a problem

From: Frank Solensky <[email-masked]>
Date: 16 Aug 2002 13:27:49 -0400

Just posted on slashdot: a Bayesian approach to the problem that reports
to have rates of 0.5% on false positives and 0% false negative:

http://www.paulgraham.com/spam.html

				-- Frank

---

From: stanislav shalunov <[email-masked]>
Date: 16 Aug 2002 14:11:01 -0400

> http://www.paulgraham.com/spam.html

Nice short-term approach.

Unfortunately, easily defeated with just appending (perhaps as an HTML
comment) a long innocent-looking fragment (e.g., a 30KB piece from a
random book).

Further, in its *present* form, where unfamiliar words are given 0.2
spam probability, easily defeated by just adding a lot of randomly
generated `words' like 9nscS9Ft, iuiF0kKw, 6AycPEbU, nsUdjGeP, etc.
Given enough of these, the Bayesian probability formula will declare
even a piece of mail that consists of a sales pitch for a pornographic
web site have a probability of being spam that is arbitrarily close to
0.2.

-- 
Stanislav Shalunov		http://www.internet2.edu/~shalunov/

"Which one is worse?  Both are worse."		-- V. I. Lenin

---

From: John Stracke <[email-masked]>
Date: Fri, 16 Aug 2002 14:43:08 -0400

>web site have a probability of being spam that is arbitrarily close to
Is that true? The approach described looks only at the 15 words furthest 
from 0.5; it seems likely that most messages that would rank at 0.9 or 
above would have enough spam-words that words at 0.2 wouldn't show up.

One thing that would be necessary, and that the author doesn't mention, 
would be to decode content-encodings before applying the filter; 
otherwise spammers could just base64 all their messages.

-- 
/=============================================================\
|John Stracke      [email-masked]                    |
|Principal Engineer|http://www.centivinc.com                  |
|Centiv            |My opinions are my own.                   |
|=============================================================|
|*BOOM* "Thank you, Beaker. Now we know that is definitely too|
|much gunpowder." -- Dr. Bunsen Honeydew                      |
\=============================================================/

---

From: Keith Moore <[email-masked]>
Date: Fri, 16 Aug 2002 14:55:30 -0400

> to have rates of 0.5% on false positives and 0% false negative:

for one recipient.  try to make the same table serve more recipients, and 
the number of false positives quickly goes way up.

Keith

---

From: stanislav shalunov <[email-masked]>
Date: 16 Aug 2002 16:38:05 -0400

John Stracke <[email-masked]> writes:

> The approach described looks only at the 15 words furthest from 0.5;
> it seems likely that most messages that would rank at 0.9 or above
> would have enough spam-words that words at 0.2 wouldn't show up.

I missed that point.  Random words indeed wouldn't work then.
Guessing at `right' words still might.  If the deployment results in
spammers sending multiple copies of their spew with different sets of
decoy words, the problem would actually get worse.

One can imagine sets of decoy words for given demographics; e.g., for
networking nerds: TCP MPLS duplex route BGP...

One can imagine 1000 sets of decoy words for different categories of
people, with each message sent by the spammer in 1000 copies (so, you
might get it in 0 copies if you're very unusual -- or in 50 copies if
you discuss fishing, computer networking, investing, travel, and such
other categories in email regularly and the spammer has decoy lists
for fishing, etc.).

One can imagine software that then looks for word combinations in
messages rather than individual words, making the state much greater
and the spammer's job harder yet.  The spammers would probably retort
by using random subsets of decoy word sets.

> One thing that would be necessary, and that the author doesn't
> mention, would be to decode content-encodings before applying the
> filter; otherwise spammers could just base64 all their messages.

Even scarier: Spammers like to use Javascript even now to `encrypt'
interesting parts of messages, such as URLs (this way, they make it
harder to determine where a given web page is hosted).  If Javascript
works in the recipient's MUA, then you have a Turing-complete way of
hiding.  Rice theorem works against you.

Sex is the mathematics urge sublimated.                 -- M. C. Reed.

---

From: John Stracke <[email-masked]>
Date: Fri, 16 Aug 2002 17:20:55 -0400

>other categories in email regularly and the spammer has decoy lists
Mmm, but that pours gasoline on the villagers' torches.  It'd be much 
more clearly a crime, since it's so obviously an attempt to evade the 
recipient's filters.  Sending me one message customized to get through 
can masquerade as free expression; sending me 1000 is a dictionary 
attack on my security.  At that point, spammers will start going to jail.

>If Javascript
>works in the recipient's MUA, then you have
>  
>
...an idiotic MUA.  (Yeah, I know I'm using one that supports it; but 
it's turned off.)

-- 
/=================================================================\
|John Stracke      [email-masked]                        |
|Principal Engineer|http://www.centivinc.com                      |
|Centiv            |My opinions are my own.                       |
|=================================================================|
|Vote for Ron, and nobody gets hurt! --actual campaign poster from|
|Chicago                                                          |
\=================================================================/

---

From: "Perry E. Metzger" <[email-masked]>
Date: 16 Aug 2002 18:21:10 -0400

> http://www.paulgraham.com/spam.html

The problem is that, naturally, the spammers will start running the
tool over their spam before sending it and tweaking it until it
passes. This has happened for previous techniques.

As with system security and cryptosystems, you have to assume that the
enemy knows what techniques you are using and will move to evade them.

Not, of course, that I won't add this to my armamentarium for
now. Anything to reduce the flood for as long as it will work.

-- 
Perry E. Metzger		[email-masked]
--
"Ask not what your country can force other people to do for you..."

---

From: "Perry E. Metzger" <[email-masked]>
Date: 16 Aug 2002 18:23:08 -0400

John Stracke <[email-masked]> writes:
> recipient's filters.

Are you kidding? They've been doing thing to explicitly evade filters
for years now. For example, ever notice groups of random characters at
the end of spam Subject: lines? those are there to evade some of the
early filtering techniques based on having trap addresses that got
spam and rapidly distributed block lists based on what arrived.

---

From: Dave Crocker <[email-masked]>
Date: Fri, 16 Aug 2002 15:46:46 -0700

>enemy knows what techniques you are using and will move to evade them.

Indeed.

As folks talk about their favorite magic bullet to "solve" the problem, 
they need to take note of the above point.  It exemplifies why the task is 
difficult:

  *      Some spammers are subject to local laws.
         Many are not.

  *      Some spammers are relatively cooperative and
         seek to have a reasonable good community
         relationship.  Many do not.

  *      Some spammers are straightforward and even
         cooperative.  Others are highly deceptive.

So as we suggest mechanisms, we need to think hard about how effective they 
will be and at what cost.

d/

----------
Dave Crocker <mailto:[email-masked]>
TribalWise, Inc. <http://www.tribalwise.com>
tel +1.408.246.8253; fax +1.408.850.1850

---

From: stanislav shalunov <[email-masked]>
Date: 16 Aug 2002 19:09:46 -0400

John Stracke <[email-masked]> writes:

> Mmm, but that pours gasoline on the villagers' torches.  It'd be
> much more clearly a crime, since it's so obviously an attempt to
> evade the recipient's filters.

Right now, they add random garbage in various parts of the message to
make Brightmail-style blocking harder, forge return addresses, use
open relays, masquerade as legitimate mail by using deceptive subject
lines, masquerade as occidentally misdirected mail, use Javascript to
obstruct investigation of the URLs they provide, use .EXE files for
the same purpose, insert misleading stuff in HTML comments, etc.

Do you think one more technique will do much damage to their
reputation?  Every time there's a popular spam-blocking method, the
spammers would evade it.

>> If Javascript works in the recipient's MUA, then you have

I think you missed the point.  I don't have a Javascript interpreter
in my version of Emacs.  That wouldn't help me at all if spammers have
the expectation that most people's MUAs will process Javascript.  For
me, their spam would be unreadable.  Do they care?

But we must show them that they cannot terrorize the greatest nation on
the face of the Earth.  And we won't.       -- George W. Bush, 20011017

---

From: Fred Baker <[email-masked]>
Date: Fri, 16 Aug 2002 16:14:24 -0700

At 05:20 PM 8/16/2002 -0400, John Stracke wrote:
>Sending me one message customized to get through can masquerade as free 
>expression; sending me 1000 is a dictionary attack on my security

really? Then what's the Klez worm doing? Ever day I get a few dozen emails 
that purport to be from me, and rather a number of emails that claim to be 
from someone else. The obvious outcome is that somebody is going to put my 
email address into a "kill klez traffic" filter, meaning that I can no 
longer communicate with them. Klez is in essence a dictionary attack on my 
(and many others) ability to communicate with people using email.

---

From: John Stracke <[email-masked]>
Date: Mon, 19 Aug 2002 10:10:06 -0400

>passes. This has happened for previous techniques.
That would be less somewhat useful in this case, though, since each user 
has their own table of keywords.

-- 
/===========================================\
|John Stracke      [email-masked]  |
|Principal Engineer|http://www.centivinc.com|
|Centiv            |My opinions are my own. |
|===========================================|
|"Who died and made you king?" "My father." |
\===========================================/

---

From: John Stracke <[email-masked]>
Date: Mon, 19 Aug 2002 10:12:24 -0400

Fred Baker wrote:

>> Sending me one message customized to get through can masquerade as 
>> free expression; sending me 1000 is a dictionary attack on my security
>
> Klez is in essence a dictionary attack on my (and many others) ability 
> to communicate with people using email.

Well, yeah.  The worm writers don't try to claim that their activities 
are legal.  Spammers do.

---

From: John Stracke <[email-masked]>
Date: Mon, 19 Aug 2002 10:13:52 -0400

Perry E. Metzger wrote:

>the end of spam Subject: lines?
>  
>
A spammer can claim that those there for legitimate technical reasons, 
to help them to track responses/bounces.  Sending 1000 messages gets 
harder to justify.

---

From: Vernon Schryver <[email-masked]>
Date: Mon, 19 Aug 2002 09:08:44 -0600 (MDT)

> From: John Stracke <[email-masked]>

> ...

That contradicts other assumptions about this mechanism and it points
out a major problem.  One assumption is that spam is a more rather
than less uniformly distributed flood.  If it is not uniform, how can
you hope that the statistical characteristics of previous samples will
be related to future samples from new spammers?  If spam is uniform,
then why do users need private tables of keywords?  Spam distribution
does have non-uniformities for language and character set, but as the
Russian, Spanish, and Asian spam that English speakers receive shows,
spammers try very hard to make spam distribution uniform.

(As I've said, based on DCC counts and other data, I figure there
there are fewer than 2000 whack-a-mole spammers on the net at any
time, and there is an average 100% turnover very 6 months, with even
the worst whack-a-mole spammers giving up after a few years.
"Whack-a-mole" is the recognized technical term for the spammers that
flog Viagra, porn, and loansharking as opposed to the big outfits
like American Express and Dell Computers that never give up their
"push advertising" campaigns.)

The major problem is that the mechanism requires a significant and
continuing false-negative rate to keep the scoring tuned as spammers
come and go.  For example, notice that the proposal talks about
filtering based on "words" that are in fact domain names.  A mail
message today containing "cyberpromo" is almost certainly not spam,
but almost certainly was spam not very long ago.  What if the long
established and very well known (except evidently to Mr. Graham)
spam haus 263.com also reforms itself?

You might answer that problem by having a centralized service run a lot
of spam traps and distribute keyword scores.  Brightmail has long
been operating a system that does that, but I understand they distribute
regular expressions and checksums instead of keyword scores.  I'm not
sure that difference is significant.  Another issue is that spam traps
get a distinct, atypical sample of spam. 

I used the word "scoring" instead of "probabilities" as others in this
thread because I cannot see a major operational difference between
the "probabilities" of this proposal and the "scoring" of systems such
as SpamAssassin.  Recall that SpamAssassin also computes a score based
on the presence or absence of words, as well as other features.  Using
a computer program to tune your keyword SpamAssassin or similar scoring
is not a bad idea, but it's not going to end spam as we know it.

Of course, the main problem with any and every such system is that it
is looking for characteristics other than "unsolicited" and "bulk."

Vernon Schryver    [email-masked]

---

From: John Stracke <[email-masked]>
Date: Mon, 19 Aug 2002 11:54:39 -0400

Vernon Schryver wrote:

>That contradicts other assumptions about this mechanism
>
Whose? The author of the original article was very explicit that he was 
advocating users have individual tables.

>and it points
>then why do users need private tables of keywords?
>
I think it was to reduce false positives--because the profile of 
different users' legitimate mail is nonuniform.

>come and go.
I dunno; keeping the tuning up to date sounds like a strength to me.  It 
requires some level of effort, but a much lower level than deleting 
every piece of spam by hand.

>is looking for characteristics other than "unsolicited" and "bulk."
Yes, and the main problem with the DCC is that it does not.

When I moved last fall, I went through old mail, harvested the addresses 
of old friends, and sent out mail with my new address.  Some of these 
people had never received email from me (they and I were CC:ed on the 
same messages from other friends), so I would not have been on their 
whitelist.  I don't know how many people I sent to, but it was certainly 
more than 10--which you say counts as bulk.  So, if at least 10 of those 
people had been using the DCC, then my message would have been tagged as 
UBE, and some of them would not have gotten it.  I suppose one might 
argue this message was bulk email, but I knew every one of those people 
personally, considered them friends (even if I hadn't seen them since 
college), and had reason to believe that they would be at least somewhat 
pleased to keep track of me.  Why should that be filtered?

I'm not advocating the Bayesian approach as a silver bullet, mind you; 
but I think it's an interesting area to look into.  Even if it doesn't 
work, the general idea of filtering based on personalized statistics 
could lead to something that works better.

-- 
/===============================================================\
|John Stracke      [email-masked]                      |
|Principal Engineer|http://www.centivinc.com                    |
|Centiv            |My opinions are my own.                     |
|===============================================================|
|Both candidates are better than a megalomaniac mutant lab mouse|
|bent on world domination...but it's pretty close.              |
\===============================================================/

---

From: Vernon Schryver <[email-masked]>
Date: Mon, 19 Aug 2002 11:01:48 -0600 (MDT)

> advocating users have individual tables.

please read what I wrote instead of what you wish I had written.

> different users' legitimate mail is nonuniform.

I think the purpose is to reduce false negative at least as much as to
reduce false positives.  As far as I can tell, the nature of the system
makes it at best difficult to adjust per-user tables to reduce false
positives.  (The standard usage is that a "false positive" is rejected
legitimate mail while a "false negative" is spam that leaks past a
filter.)  I've assumed that if implemented in production, the system
would use a corpus of manually identified spam and that the system
would automatically recompute the scoring with only the the samples
from the last year or so.

> every piece of spam by hand.

That's a straw man.  Of course it's good to keep your filters up to
date, but there are many other tactics that require less work of
individuals and fewer false positive than this scheme.  The reason
the spam problem exists is that more than 99.99% of users cannot be
bothered to report spam to ISPs.  This scheme requires false positives,
probably at least 5% or 10%.  That's a lot of spam users would have
to read compared to some other tactics.

> pleased to keep track of me.  Why should that be filtered?

If those friends had send mail to you, you might well be on their
whitelists.  If they had never sent mail to you, and since you had
never sent mail to them, then why would you presume to clutter their
mailboxes with news of your move?

One good reason to filter such mail is that contrary to your hope, it
would have been viewed as "spam" or at least useless by many recipients
in similar situations, albeit not necessarily those friends of yours.
Most of us receive more than enough "new address" mail from people
we don't know very well and have never sent mail to.

Another reason to filter such mail is that in general it is useless
noise even from the point of view of its sender, if the sender sets
asside the normal human perspective of being the unique center of the
universe.  It is useless noise because unless you send only a very
little mail, because you cannot hope to reach more than a small fraction
of your correspondents with your change of address notice.  The only
workable tactics to deal with moving is to make new friends, hope your
old friends can track you down, or to get a permanent address.

Such change of address mail is usually motiviated by the same human
frailty that causes spam.  Everyone thinks that spam is something that
other people do.

A better way to summarize the main problem with the DCC is that it
requires the use of per-user or at least per-enterprise white lists.
It is not a small problem.

> could lead to something that works better.

We agree about that.  

I'm irritated by the hype this notion has received, such as the use
of the phrase "Bayesian approach" to imply it is a revolutionary
invention.  That phrase has some relevance for tuning the scoring but
more as a formal description and about computerizing what people have
been doing informally and manually for years.

---

From: David Morris <[email-masked]>
Date: Mon, 19 Aug 2002 07:57:26 -0700 (PDT)

The only solution to spam will have to be economic.

Legislation must be crafted to make enforcement economical. If the
enforcing entity recovers more in fines/penalties than the enforcement
activities cost, there will be adequate incentives to pursue enforcement
and I suspect that the size of such recoveries will deter violation of the
laws.

Since my spam may not be your spam, a cornerstone to legislation will be
in the definition of spam and marking required on such email.

Technical solutions will be required to allow identification of the origin
of the spam. This is a two tier issue ... identification of the 'entry'
server and protocols for use by such servers for identification of the
originating client.

Watching other recent email threads, it is clear we still haven't achieved
a management oversite structure for the domain name system so I wonder if
the internet community can converge an an organizational solution to
manage non-repudiatable identification as well as a way for humans to
report spam experiences, but perhaps the cost of spam vs. the lack of cost
associated with failures in the DNS infrastructure might provide greater
incentives.

Any spam solutions will need to work for the vast majority of email users
and any 'training' of the solution will need to be simple.

The approach I've been noodling for a while now is:

1)  Define and start implemting protocol extensions to support
identification and distributed authentication
2)  Likewise, protocol extensions to support a parallel email
infrastructure where there is a charge, say $.20, for each email sent.
Technically, I think this would be mostly a new DNS record so that a
domain could define its for fee provider(s) and perhaps some accounting
records or related support to insure interoperability for postage meter
operations.
3) Probably some IMAP extensions to allow management of shared servers
4) Probably support for exchange between mail services much line the USPS
can forward mail to an address in Canada, etc.

Based on this technical infrastructure, I would envision I would configure
my 'free' server to only accept mail from authenticated sources such as
the IETF, W3C, or perhaps specific sources by address.

I would expect one or more public or commercial entities would provide
mail services based on these protocols.  For example, the USPS and FedEx
in the US.

To use a commerical service to send mail, I'd have to purchase a roll of
'stamps' or a postage meter account. I would expect that for each email
accepted by my server, I'd receive a credit in my account, say $.10.

If you aren't in my pre-configured whitelist and you attempt to send free
mail, you'd get a bounce message telling you that free mail wasn't
accepted and to use a service which is part of the USPS or whatever
network.

Once the required protcols were defined and there was a minimal
infrastructure in place, individuals / companies owning servers could
adopt at their own pace and begin receiving value.

Some thought in the protocol definition process  to bridging to the new
world would be good, but at least some of the thoughts I've had are really
features of the user's client and server ... for example ... if you reply
to my mail with proper use of my message id, you are automatically allowed
thru my 'free' entrance.

Dave Morris

---

From: [email-masked]
Date: Tue, 20 Aug 2002 14:12:43 -0400

> the IETF, W3C, or perhaps specific sources by address.

Guess I'd have to post to the IETF list in order for you to get any comments
I might have about your proposal, if your proposal was in effect.  That's
assuming I'd bother commenting at all - in the last 60 days, I've sent 544
pieces of e-mail.  At $0.20 a pop, that's $60/month I'm certainly not going
to pay out of MY pocket, nor is my employer likely to pick up the tab for.

And of course, my mail server wouldn't be configured to accept from you,
since I wouldn't have whitelisted you either.

So I end up having to spam the list in order to get around the anti-spam
restriction you have - what's wrong with this picture?

There's also the problem that there's no good micropayment system out there
at the moment - how am I to remit you the $0.20? Remember that it's going
to get *pounded* on - a recent stat said that MSN and Hotmail were seeing
2 billion pieces of e-mail a day, and 80% of it was spam.  This however leaves
some 400 million non-spam a day - which will turn into 400 million hits per
day on your hypothetical micropayment server (come ON, you don't expect any
of the large services like AOL or MSN or Yahoo to whitelist people and turn off
a potential revenue source, do you? ;)

I'll leave it as an exercise for the reader to figure out how we'll manage
the "specific sources by address" list for 50K or 100K mailboxes in our
user community.

Other than those showstopper issues, it sounds like a great idea. ;)
-- 
				Valdis Kletnieks
				Computer Systems Senior Engineer
				Virginia Tech

---

From: "Eric A. Hall" <[email-masked]>
Date: Tue, 20 Aug 2002 13:31:05 -0500

on 8/19/2002 9:57 AM David Morris wrote:

> Legislation must be crafted to make enforcement economical.

Clarification here. When we talk about 5c per recipient, we are talking
about economic solutions. When we talk about $500 per recipient in fines,
we are talking about punative (social) solutions.

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