There are many Internet or web based services that have a need to distinguish between a human and a computer user interacting with the service. For example, there are many free e-mails services that allow a user to create an e-mail account by merely entering some basic information. The user is then able to use the e-mail account to send and receive e-mails. This ease of establishing e-mail accounts has allowed spammers to produce computer programs to automatically create e-mail accounts with randomly generated account information and then employ the accounts to send out thousands of spam e-mails. Web services have increasingly employed Turing test challenges (commonly known as a Completely Automated Public Turing test to tell Computers and Humans Apart (CAPTCHA™) or Human Interactive Proof (HIP)) in order distinguish between a human and a computer as the user of the web service. The web service will only allow the user to employ the service after the user has passed the HIP.
The HIP is designed so that a computer program would have difficulty passing the test, but a human can more easily pass the test. All HIPs rely on some secret information that is known to the challenger but not to the user being challenged. HIPs or CAPTCHAs™ can be divided into two classes depending on the scope of this secret. In what are herein referred to as Class I CAPTCHAs™, the secret is merely a random number, which is fed into a publicly known algorithm to yield a challenge. Class II CAPTCHAs™ employ both a secret random input and a secret high-entropy database. A critical problem in building a Class II CAPTCHA™ is populating the database with a sufficiently large set of classified, high-entropy entries.
Class I CAPTCHAs™ have many virtues. They can be concisely described in a small amount of software code; they have no long term secret that requires guarding; and they can generate a practically unbounded set of unique challenges. On the other hand, their most common realization, a challenge to recognize distorted text, evinces a disturbingly narrow gap between human and nonhuman success rates. FIG. 2A shows an example of a simple class 1 CAPTCHA™ displaying a random text string. The figure shows clearly segmented characters. Optical character recognition algorithms are competitive with humans in recognizing distinct characters, which has led researchers toward increasing the difficulty of segmenting an image into distinct character regions. FIGS. 2B through 2E show common ways in which class I CAPTCHAs™ are modified in an attempt to make it more difficult for a computer program to correctly recognize the characters. The text string can be distorted and noise can be added when rendered for display to a user. However, this increase in difficulty affects humans as well. The owners of web services must be careful to not make the challenge so difficult that it drives away real human users from expending the effort to user their service. Even relatively simple challenges can drive away a substantial number of potential customers.
Class II CAPTCHAs™ have the potential to overcome the main weaknesses described above. Because they are not restricted to challenges that can be generated by a low-entropy algorithm, they can exercise a much broader range of human ability, such as recognizing features of photographic images captured from the physical world. Such challenges evince a broad gulf between human and non-human success rates, not only because general machine vision is a much harder problem than text recognition, but also because image-based challenges can be made less bothersome to humans without drastically degrading their efficacy at blocking automatons.
An issue that can arise with both Class I and II CAPTCHAs™ is a human having difficulty solving the entire challenge correctly. For example, in the case of a Class I CAPTCHA™ distortions, convolutions, or noise that have been added to a text based challenge can make it difficult for a human user to correctly identify each character. The user may get all but one of the characters correct, such as mistaking the letter “e” for “c”. Similarly for a Class II CAPTCHA™ a human user may be able to correctly classify most of the images, but may get one or more images incorrect. For example, if the challenge requires classifying images as cat or dog, pictures of younger cats and dogs may be harder classify. If a human user is failed the challenge on a first attempt for getting one wrong and tries again and fails again for getting one wrong, the human user may stop trying, thereby causing the site being secured by the CAPTCHA™ to lose a real human customer. Suppose that CAPTCHA™ challenges were scored manually, by a human judge, instead of automatically by computer. Even in this seemingly straightforward task, the flexibility of human judgment would be a valuable asset. For example, a human judge may see the same user try to solve three challenges, getting 11 out of 12 images correct each time. The judge might say, “That looks like a human who is just having a little trouble. I'll let the user pass.” There is a need for an automated approach to allow for a human user to make mistakes and still be able to pass the CAPTCHA™, while still making it difficult for a non-human to pass.