Thursday, February 28, 2008

Client-side spam filtering and tagging

Server side spam filtering is hopeless. The spammer has the advantage of moving second to circumvent the barrier the server administrator set up first. The devastation caused by spam is profound. It destroys communication, obstructing the free flow of ideas and information that drives forward the progress of the human race. The problem of spam is especially prevalent in bulletin boards and web fora, which are examples of online communities to which anyone can join and contribute.

Salvation lies in the client side. We need just a few components to enable "enough rope" so that the humans can win the war against automated spammers. As an example, consider an electronic bulletin board. The general framework is that the posters take certain actions to assert their post is not spam. Readers then evaluate information about those actions to filter out the spam.

Let us first consider the actions the poster takes. Along with the text of each post, the poster may attach arbitrary metadata to the post. XML would be a good language to express such metadata. In this metadata the poster tries to prove that the post is legitimate and not spam. The key idea is that this metadata format is extensible. As spammers increase in sophistication, humans may invent and add new ways of distinguishing their posts from spam, expressed in the same structured metadata attached to their post. A well-known but sadly too infrequently deployed metadata example is HashCash. The bulletin board server should attach metadata to the post as well: its date and a unique message identifier. Along with its obvious usefulness, the date is useful, for example, for a reader evaluating HashCash metadata to decide whether the amount, or "bits", of HashCash paid is sufficient given the how fast computers were around that date. The message identifier should be globally unique, allowing third parties a way of referencing the post. As an aside, a string of 28 randomly chosen letters between A and Z provide about 128 bits of entropy (64 bits of collision resistance) and if used as a message identifier is particularly amenable to search engines.

Another current technology that may be adapted to this framework is the CAPTCHA. The poster takes the unique message identifier and submits it to a third-party CAPTCHA service. After successfully solving the CAPTCHA, the service produces a certificate signing the message identifier. The poster then appends the certificate to the metadata of his or her post.

One can imagine other more exotic types of certificates, such as those for which actual money is paid or a live interview has been conducted to verify humanness.

Along with attaching metadata to his or her message, the poster may attach metadata to his or her identity. Spammers tend to like to create an identity and use it only once to thwart simple filtering by identity. Legitimate posters tend to use the same identity over and over again. Therefore, a legitimate poster can attach metadata proving that his or her identity took effort to create. Again, HashCash and CAPTCHAs are examples of how to do this.

A legitimate poster may expand the number of posts associated with his or her identity by attaching his or her cryptographic signature, as metadata, to each post. Then, if search engines can be enhanced to be able to search for all posts anywhere that have been properly signed with a given cryptographic key, then a reader can evaluate whether a certain identity posts a lot of spam. Of course, such signatures are optional, like all metadata, and a poster may wish to keep the anonymity of posting with an identity not associated with other previous posts via a common signature, at the cost of the post being slightly more likely to be mistaken for spam.

We have just mentioned search engines searching for messages signed with a given key. This is a critical piece of functionality for this overall spam solution. Not only can one search for other posts by a specific signed poster, but one can also search for posts carrying a specified third-party signature, for example, of a third-party CAPTCHA service. Using this, a reader may evaluate how good the CAPTCHA service is.

Not only may a poster may solicit third parties to prove his or her post is not spam, but third parties may independently decide to tag a post or poster. People might tag a post as spam, cryptographically signing the tag. A reader must decide whether to trust the tag, but may be aided in this determination by searching for other tags and and posts bearing the same signature.

Tags may be more sophisticated than just "spam" or "not spam". For example, Funny, Informative, Insightful, or Troll. The tag format should remain extensible again so that the humans retain second mover advantage over the spammers.

People may also post tags about other identities. For example, one person may tag that he or she trusts another person, and forming a link in a web of trust. Like the PGP web of trust model, someone can evaluate whether an unknown poster is not a spammer if he or she can find a chain of trust links to the unknown poster.

In Web 1.0, there were just a few producers of content and everyone else just passively consumed content. The hallmark of Web 2.0 is that everyone may produce content. We must reengineer Web 2.0 from the ground up to support this model -- and one of the most important engineering tasks is spam filtering as described above.

In an example of everything old is new again, I think much of what I've described here may be built upon the infrastructure of Usenet newsgroups.

No comments :