CAPTCHAs

Have you noticed if you have tried to create a new email account or just to register for some Yahoo! Group or something like that in recent times, they ask you to type in a string of letters that can be seen in an image ??

Well the first time I noticed it, it just amused me; the second time it annoyed me; the third time I took the pains to look around and realized it is used to prevent automated registrations - and yes it made more sense then. It was not until yesterday I realised the full theory behind it all.

It is in fact a very interesting and fast-growing area of research, one area I found interesting at the onset after a long long time. This was when we had a seminar in our colloquium series on the topic yesterday. The speaker was a beautiful lady who had just graduated from Berkeley, Dr. Monica Chew, so that made it all the more interesting.

Basically, that thing which Yahoo! among other companies use is called a "Completely Automated Public Turing test to tell Computers and Humans Apart" or simply a CAPTCHA. The idea is to display a string in a form a human can read but a machine can't. So only a human would be able to type it in correctly, not a software bot.

The principle is similar to the one used in cryptography. (It is easy to compute the product of 2 prime numbers but difficult to find the prime factors of a given huge number.) Here the idea is that it is difficult for optical pattern recognition programs to recognize an image if it is distorted, while it is relatively easy to distort it. Machine Vision is a known hard AI problem, just like Prime factoring is a known hard problem in algorithmics.

Of course all CAPTCHAs which rely on strings have been broken; guesswork is the most commonly used weapon of attack. This is partly because strings used in CAPTCHAS are often dictionary words because otherwise legitimate users misspell them (in fact misspelling (or mistyping) is a horribly surprisingly common occurence). Which is why the challenge is not only to make CAPTCHAs as difficult as possible for machines to break, but at the same time as easy as possible for genuine users to use.

Hence, string CAPTCHAs will soon become obsolete and the way ahead is image CAPTCHAs. An image is displayed and the user is asked to type in what it is. This of course will create unimaginable problems as you can guess - spelling errors, language issues, user interpretations - if you put a picture of a cup, a user might describe it as a mug, cup, coffee jar what else ? and all other problems of the English language - like polysemy, synonymy and what not. Hence the next idea - an anomaly CAPTCHA - 6 pictures, 5 of which denote the same thing and one different - tell which one is different.

I think CAPTCHA is a really intriguing idea. Aim to find out more soon - when I have the time - till then: the next time you encounter a CAPTCHA, make sure you spare those 1 or 2 minutes to work it out - it is really worth the effort.