This is my proposal for a very simple algorithm that I think would effectively stop all spam for large providers like HotMail, while allowing legitimate (opt-in) newsletters to be delivered to users. The only limitation is that it would only work for large providers like HotMail, with many user accounts. It would not work as an effective anti-spam algorithm for a small, local ISP. (The reason is because the algorithm assumes that if one user on the system gets a particular piece of spam, then a significant number of other users on the system will receive the same spam.)
Despite this limitation, it is the only algorithm I know of, that meets all of the following criteria:
If a Russian spammer sent a large number of spams from Russia, the vast majority would be
filtered out as spam
If a legitimate newsletter publisher in Russia sent a large number of newsletters from Russia to his subscribers, those would not be filtered out as spam.
These two conditions are grouped together in order to elimiate anti-spam proposals that require taking legal action against violators. A good anti-spam system should be effective against overseas spammers while also allowing foreign publishers of legitimate newsletters to send mail to their subscribers. Since even large companies cannot shut down overseas sites that are hosting obviously illegal violations of their copyrights, an anti-spam system should not rely on being able to apply legal pressure overseas.
For example, Habeas allows email publishers to pay a license fee to Habeas, in exchange for which they are allowed to insert a copyrighted poem into their email headers, provided that they agree only to send mail to people who have specifically requested it. If a mail provider recognizes the Habeas haiku as proof that a message is not spam, then any message containing the haiku in the headers will be delivered. The idea is that spammers who use the haiku without permission can be sued for violating Habeas' copyright. But if a spammer in Russia uses the haiku in order to get their spam delivered, the cost of suing them from the United States could prove prohibitive.
Other systems rely on a "pay-in-advance" model, where an emailer pays some fee to acquire a certificate which certifies them as a non-spammer. If a given mail provider recognizes those certificates as trustworthy, then any mail signed with that digital certificate can be recognized as non-spam and delivered to users. Of course, if an emailer acquires a third-party certificate and then uses it to spam, then the third-party who provided the certificate, can revoke it.
Here, the problem is that some spammers can afford to spend more money on a single spam run, than many newsletter operators can afford to spend on a permanent certificate. Suppose a certificate authority charges $25 to certify a newsletter publisher as a non-spammer. A spammer could easily pay that much money, send out hundreds of thousands of spams with his certificate, and still come out ahead even though the certificate authority would cancel his certificate after the complaints rolled in. Raise the price to $250, and you've reached the point where most newsletter publishers would not want to spend the money -- but a spammer still could. The problem is that by increasing the price, you eliminate more publishers of legitimate newsletters than you eliminate spammers.
It does not enable an attacker to get an innocent third party blacklisted
as a "spammer".
If HotMail detected a large number of spams advertising, for example, the URL http://www.peacefire.org/, and then blacklisted all incoming mail containing the string "http://www.peacefire.org/" as a result, then Peacefire's own newsletter would be blocked. So if HotMail adopted the general practice of blocking all mail containing URLs that had a high frequency of occurring in previous spams, then a third-party spammer who hated Peacefire (as a result of our anti-spam lawsuits, there are plenty of them) could get all Peacefire newsletters blocked by sending large numbers of spams containing Peacefire's URL.
The "innocent third-party" problem is a major problem with systems like SpamCop, which blacklist sites if even one person complains that a particular newsletter is "spam", even if it turns out that the complainer made a mistake (or was complaining maliciously, to get the spammer blacklisted).
It works by default, i.e. does not rely on the user to read through their "spam-filtered" mail and whitelist
This policy is disasterous for legitimate newsletter publishers who get their newsletters blocked as "spam" because they are sending similar messages to many different addresses. When Peacefire's newsletter was blocked by HotMail as "junk mail", hardly any HotMail users ever saw it. Most newsletter their subscribers, especially ones who are getting lots of spam to begin with, are not going to have time to comb through their "junk mail" folder, and even the ones that do go through it and do whitelist that particular newsletter, are not going to have any effect on all the other subscribers who will never see any future issues of that newsletter once it starts getting blocked as "spam".
The algorithm has to actually work.
This would seem like an obvious one, but it means the quality of an anti-spam system should not be defended with statements like, "Nobody is forced to use it", "The free market will decide", etc. Obviously these statements are true of any anti-spam system, no matter how bad it is; the question is whether the system is any good. If a marketer is extolling the virtues of some anti-spam system, and someone points out a flaw, the marketer should not be allowed to change the subject ;-)
The fact that ISPs choose a given anti-spam system does not mean that it works well from the user's point of view, because ISPs have an incentive to err on the side of blocking spam while also blocking some legitimate email. If an ISP lets through too much spam, then users complain, and the more dim-witted ones might blame their ISP for the problem. But if the ISP blocks spam aggressively and also happens to block some legitimate emails, then many users will never even know what is going on, and if they do later find out that someone sent them a message they never received, few of them will realize that their ISP is to blame.
On the other hand, from the user's point of view, the "annoyance cost" of missing one important email message, could be greater than the cost of having to delete 100 or even 1,000 spam messages manually, depending on how important the email was. But ISPs know that if they do get caught trashing an important message, then no matter how much harm was caused to the user, the most that the user could probably do would be to switch to another ISP. So it should not be assumed that a spam filter works from the user's point of view, just because an ISP uses it.
All incoming messages arriving at, say, HotMail, are categorized in "first-tier" and "second-tier" groups. Messages are grouped into first-tier groups based on the IP address that connected to HotMail's server to deliver the message; all messages delivered from the same IP address are considered part of the same first-tier group. Second-tier groups are determined by examining the mail headers and looking at the second-to-last IP address that relayed the mail before passing it on to the machine that finally delivered the message to HotMail. So if machine A delivers 20 messages to HotMail, and the headers indicate that 10 of those messages were relayed from machine B and 10 of those messages were relayed from machine C, then the messages would comprise two second-tier groups of 10 messages each, and all 20 messages would be in the same first-tier group.
Of course, if machine A is an untrustworthy machine operated by a spammer, then in each message delivered by machine A, it could forge the IP address used to relay the mail through machine A, and it could make up a different IP address for every message that it sends, so that they would all be in different second-tier groups. But they would still all be in the same first-tier group, because they were all relayed directly from machine A.
Now, for each group of messages (including both first-tier and second-tier groups), HotMail keeps track of: (a) how many messages in that group have been viewed by HotMail users, and (b) of those messages, how many have been reported as "spam", by users viewing the message and clicking the "Report as spam" button.
Suppose, using example numbers, that if a newsletter is spam, then 10% of HotMail users will report it as spam. But if a newsletter is not spam, then only 1% of HotMail users will (accidentally or maliciously) report it as spam.
Once HotMail detects that, say, 100 of the messages in a given group have been read by users, then it looks at the number that have been flagged as spam. If the number is around 1%, then HotMail can assume that the newsletter probably isn't spam. If the number is around 10%, then HotMail can assume that the newsletter is spam, and for all remaining users that have received a message in that group, the email is marked as spam and moved into their "Junk Mail" folder. Thus if a spammer sends a message to 10,000 HotMail addresses, only 100 of those HotMail users will have to see the message before HotMail determines that all messages in that group are spam, and prevent the other 9,900 users from seeing it.
Here is how the algorithm would play out in specific scenarios:
Spammer sending mail directly to HotMail users
If the spammer uses their own private server to send 10,000 spams to HotMail, then the messages will be reported and blocked as "spam" through the algorithm above.
If the spammer inserted forged headers into each message, to make it look like the messages were relayed through his machine from different sources, then the messages would be grouped into different second-tier groups -- but this wouldn't matter, because they would all still be part of the same first-tier group, which would cause them to be blocked.
Spammer sending mail to HotMail users through an open relay
If the spammer, connected from a single IP address, sends 10,000 spams through a given open relay, then these spams will all be part of the same second-tier group (because they're relayed to HotMail from a common IP address, and the headers indicate that they were all sent to the relay from a common IP address as well). So after 100 of the users read the message and 10% of them report it as spam, the remainder of the messages in that second-tier group get moved into the users' spam folders.
Whether or not other messages sent from that open relay get blocked as well, depends on how much legitimate mail is being sent through that relay, compared to how much spam. If, during the time period that the 10,000 spams were sent, 10,000 legitimate emails were also sent through that relay, then all of those emails will comprise a first-tier group of 20,000 messages. Of the first 100 messages in that group that users read, an average of half of them will be spam, and of that half, 10% will be flagged as spam by the users who read it, so 5% of the messages in that first-tier group will be flagged as spam. That would not be sufficient to get the entire first-tier group blocked as spam, so the legitimate messages sent through that open relay would still be delivered.
Scumbag with a vendetta tries to get someone else's newsletter wrongly blocked as "spam"
This is way too easy with systems like SpamCop, where a single false report (whether filed accidentally or on purpose) can get a newsletter publisher blacklisted. But for a system using our algorithm, in order for the scumbag to get someone's newsletter wrongly blocked, they would have to:
One possible countermeasure against this would be to look at the IP addresses that the "spam reports" for a given newsletter are coming from. If they all come from the same IP address, or from IP addresses owned by the same ISP, then it's a good sign that the spam reports are fraudulent reports being filed by the same person, and the newsletter should not be blocked as spam. But if the spam reports are coming from different IP addresses assigned to different ISPs, they are more likely to be real.
It is possible for a truly dedicated adversary to sign up for Internet access points with different ISPs, and write his script to check his HotMail accounts and submit fraudulent spam reports from each of these different IP addresses. But we submit that there is no way to stop the fraudulent reports in this case -- you can never distinguish between 10 people at 10 different ISPs who are all filing abuse reports about a given spammer, and one person signed up with 10 different ISPs who is filing abuse reports under each different account. The most you can do is to require the scumbag to go to these rather extraordinary lengths in order to get a newsletter wrongly blacklisted as spam -- without giving the scumbag a much easier way to do it.
Send any comments to firstname.lastname@example.org -- thanks!