Saturday, December 09, 2006

CAPTCHA = Computer or Human

When you are running a popular online application you might be suffering from people writing computer programs that interact with your application in a undesired way. Take for example, they have the problem that there platform is used by spammers and people promoting there own website by setting up fake a fake weblog that is only used one time and is forwarding the traffic to for example an adult website.

In those cases the people who are using the system for this purpose would like to create a large amount of weblogs in a automated way because the load is so high it can not be done manually. For example creating a thousand new weblogs is not a job which can easily be done by hand. As you have ever developed a web application or if you, just for a moment, think about how you can automate such a procedure you will find out that this can be done quite easily.

To prevent such a use of the system and to keep automated processes out of the system you, as a developer, will need a way to tell the difference between a “hostile” automated process and a real user. This is the point where it gets tricky, all the traffic will, most likely, be http traffic with gets and posts. So by the nature of the traffic there is no way of telling the difference between a human and a computer.

For this purpose of telling the difference between humans and computers there is a thing we call CAPTCHA. Most likely you have already used a captcha several times before but never have known that this is such a captcha. You can find them when you fill in a online registration when applying for a hotmail account of a Google Gmail account or even when you post a posting to your weblog.

A captcha is the name for this little box with characters you are required to type into a textbox. Most of the times the letters are strangely curled and there is a lot of background noise in the picture. By doing it like this automated systems are unable to recognize what letters are in the picture. Only humans are able to tell this by a visual conformation.

Since CAPTCHAs are based on open problems in artificial intelligence (AI), they also offer well-defined challenges for the AI community, and induce security researchers, as well as otherwise malicious programmers, to advance the field of AI. (This is similar to research in cryptography advancing algorithms for factoring large numbers.) Several groups have created programs that can pass many CAPTCHAs over 80% of the time (see below). These algorithms represent significant progress in the area of text recognition. CAPTCHAs are thus a win-win situation: either a CAPTCHA is not broken and there is a way to differentiate humans from computers, or the CAPTCHA is broken and an AI problem is solved. Using harder AI problems, our newly developed CAPTCHAs are still not broken.

Greg Mori and Jitendra Malik of the University of California at Berkeley have written a program that can solve ez-gimpy with accuracy 83%. Thayananthan, Stenger, Torr, and Cipolla of the Cambridge vision group have written a program that can achieve 93% correct recognition rate against ez-gimpy, and Malik and Mori have matched their accuracy. Their programs represent siginifcant advancements to the field of computer

Also interesting to watch is the talk given by Luis von Ahn on the Google techtalk of July the 26e 2006. Luis von Ahn is an assistant professor in the Computer Science Department at Carnegie Mellon University, where he also received his Ph.D. in 2005. Previously, Luis obtained a B.S. in mathematics from Duke University in 2000. He is the recipient of a Microsoft Research Fellowship.

ABSTRACT Tasks like image recognition are trivial for humans, but continue to challenge even the most sophisticated computer programs. This talk introduces a paradigm for utilizing human processing power to solve problems that computers cannot yet solve. Traditional approaches to solving such problems focus on improving software. I advocate a novel approach: constructively channel human brainpower using computer games. For example, the ESP Game, described in this talk, is an enjoyable online game -- many people play over 40 hours a week -- and when people play, they help label images on the Web with descriptive keywords. These keywords can be used to significantly improve the accuracy of image search. People play the game not because they want to help, but because they enjoy it.

I describe other examples of "games with a purpose": Peekaboom, which helps determine the location of objects in images, and Verbosity, which collects common-sense knowledge. I also explain a general approach for constructing games with a purpose

No comments: