CAPTCHAs

Abstract

Nowadays, it is hard to find a popular Web site with a registration form that is not protected by an automated human proof test which displays a sequence of characters in an image, and requests the user to enter the sequence into an input field. This security mechanism is based on the Turing Test—one of the oldest concepts in Artificial Intelligence—and it is most often called Completely Automated Public Turing test to tell Computers and Humans Apart (CAPTCHA). This kind of test has been conceived to prevent the automated access to an important Web resource, for example, a Web mail service or a Social Network. There are currently hundreds of these tests, which are served millions of times a day, thus involving a huge amount of human work. On the other side, a number of these tests have been broken, that is, automated programs designed by researchers, hackers, and spammers have been able to automatically serve the correct answer. In this chapter, we present the history and the concept of CAPTCHAs, along with their applications and a wide review of their instantiations. We also discuss their evaluation, both from the user and the security perspectives, including usability, attacks, and countermeasures. We expect this chapter provides to the reader a good overview of this interesting field.

Introduction

During more than 60 years, the purpose of Artificial Intelligence (AI) has been to design and build a machine able to think as a human person. The term AI was coined by John McCarthy in the summer of 1956, during a historic meeting held at the Dartmouth College by him and other leaders of this field over decades. While first works in AI were surprising, and some of these and other researchers believed this problem would be solved in 20 years, it was not. Evaluating how far we are today from meeting this ambitious goal is out of the scope of this chapter, but no one can deny that this field has provided hundreds of ideas that have been at the heart of Computer Science, and often driven it.

For instance, Semantic Networks emerged as a mechanism to formalize the semantics of Natural Languages to enable Machine Translation and to, ultimately, make computers understand and express through human languages. While machines still do not have this ability, Semantic Networks are a representation language that has for instance evolved to languages used to describe software models, like class diagrams in Object Oriented Programming. Semantic Networks are also the underlying mechanism to the Semantic Web and several other technologies. Computer Science is plagued with subproducts of AI, and Information Technologies (IT) Security is not an exception—modern spam filters include Machine Learning and Natural Language Processing techniques; Machine Learning is also used in antivirus research, intrusion detection, etc.; and there are many other examples.

In 1950, Alan Turing, one of the fathers of AI, faced the question: “Can machines think?” He conceived a test to evaluate it, the Turing Test. Theoretically, using this test it is possible to decide if a machine has reached the human levels of communication and reasoning. Current computers are still not able to pass that test, but as with Semantic Networks, other applications of this test have emerged.

Perhaps the most prominent application of the Turing Test to the field of Information Security is the concept of CAPTCHA. This word, which stands for Completely Automated Public Turing test to tell Computers and Humans Apart,¹ makes reference to an automated test aimed at confirming that the user of an application is a human being instead of a robot, that is, a program which would probably misuse a service or resource. The concept, often named also reverse Turing test or Human Interactive Proof, has emerged in the context of Web security. This can be explained by the huge and ever-increasing popularity of Web-based services that range from low level ones like online data and information storage, to more complex and extremely popular ones like Web-based e-mail, word processors, image processors, etc., and ultimately, Social Networks as the ultimate communication platform for hundreds of millions of users. However, the concept can be applied to any other kind of IT service or tool.

The Turing Test was conceived by Alan Turing and presented in a rather philosophical paper [124] discussing the properties of a machine able to think like a human being. The test is based in the “imitation game,” described as follows: given a man and a woman, an interrogator (the player or judge) has to guess who is who by addressing questions to them. The goal of one of them is make the interrogator fail, while the other has to help the player to make a correct guess. The experiment or game is done using typewritten text, so the voices may not help the player. Questions made by the interrogator may include, for example, “Will you please tell me the length of your hair?” but the answers may be absolutely correct, partly false, etc. To answer the question “Can machines think?” Turing proposed to substitute the man or the woman by a computer. If after the game, the player makes a wrong guess, then we can deduce that the machine has reached the human levels of performance at communication and intelligence.

This test has been considered as a real “think proof” for many years, but not exempt of criticism as human intelligence is still hard to define (e.g.,  [99], [101]). Moreover, no machine has yet passed the test, although a public contest, The Loebner Prize in AI [75], is yearly carried out since 1991, and computers and programs have greatly evolved since Turing posed his question. However, a number of systems have been inspired by this test, Eliza [135] being the most popular one. Weizenbaum's Eliza is a relatively simple pattern-matching program able to simulate the conversation of a therapist or psychoanalyst. For instance, given a sentence by a person: “I believe I do not love my mother,” the program might answer: “Please tell me more about your mother,” based on an rule that fires when the person writes the word “mother.” Conversational programs have evolved to commercial products that are used for, for example, Customer Relationship Management [128].

The first mention of ideas related to Automated Turing Tests seems to appear in an unpublished manuscript by Moni Naor [85], who in 1996 proposed a theoretical framework that would serve as the first approach in testing humanity by automated means. In Naor's humanity test, the human interrogator from the original Turing Test was substituted by a computer program. The original goal of his proposal was to present a scheme that would discourage computer software robots from misusing services originally intended to be used by humans only, much in the same sense of stopping an automation based attack though human identification. Basically, he proposed an adaptation of the way identification is handled in cryptographic settings to deal with this situation. In cryptography, when one party A wants to prove its identity to another party B, the process is a proof that A can effectively compute a (keyed) function that a different user (not having the key) cannot compute. The identification process consists of a challenge selected by B and the response computed by A. What would replace the keyed cryptographic function in the proposed setting would be a task where humans excel, but machines have a hard-time competing with the performance of a 3 year old. By successfully performing such a task, the user proves that he or she is human.

In Naor's work, the collection of problems should possess the following properties:

• It is easy to generate many instances of the problem, together with their unambiguous solution, without requiring human intervention at all.

• Humans can solve a given instance effortlessly with very few errors. Providing the answer should also be easy.

• The best known programs for solving such problems fail on a nonnegligible fraction of the problems, even if the method of generating instances is known. The number of instances in a challenge will depend on this fraction.²

• An instance specification is succinct both in the amount of communication needed to describe it and in the area it takes to present it to the user.

Naor suggested a number of areas from vision and natural language processing as possible candidates for such problems: gender recognition, facial expression understanding, finding body parts, deciding nudity, naive drawing understanding, handwriting understanding, speech recognition, filling in words, and disambiguation. As will be seen later in this chapter, many of his suggestions have been applied throughout years to develop automated Turing Tests. Luis von Ahn et al. would later formalize and substantiate Naor's conceptual model in what would be known as CAPTCHA [129].

Major differences between the Turing test and Naor's proposal include:

• In a Naor test, the judge is also a computer, and the goal is not to verify that the other part in the communication is a computer as proficient as a person, but to confirm that he or she is actually a person. That is the reason why these tests are often called reverse Turing tests.

• In the Turing test, the communication is conversational. However, Naor's proposal involves a variety of sensory inputs.

• In the Turing test, the conversation lasts until the player is able to take a (possibly wrong) decision. However, in these reverse Turing tests, the player has only a chance (posing a challenge to the user and screening their answer) to take the decision. The challenge may be very difficult to verify that only a person can solve it, but not as difficult as an average human user is unable to solve it.

The first known application of reverse Turing tests (named CAPTCHAs from now on) was developed by a technical team at the search engine AltaVista. In 1997, AltaVista sought ways to block or discourage the automatic submission of URLs to their search engine. This free “add-URL” service was important to AltaVista since it broadened its search coverage. Yet some users were abusing the service by automating the submission of large numbers of URLs, in an effort to skew AltaVista's importance ranking algorithms. Andrei Broder, Chief Scientist of AltaVista, and his colleagues developed a filter. Their method is to generate an image of printed text randomly so that machine vision (optical character recognition, OCR) systems cannot read it but humans still can. In January 2002, Broder stated that the system had been in use for “over a year” and had reduced the number of “spam add-URL” by “over 95%.” A U.S. patent was issued in April 2001.

In September 2000, Udi Manber of Yahoo! described this “chat room problem” to researchers at Carnegie Mellon University (CMU): “bots” were joining online chat rooms and irritating the people there by pointing them to advertising sites. How could all bots be refused entry to chat rooms? CMU's Prof. Manual Blum, Luis A. von Ahn, and John Langford developed a (hard) GIMPY CAPTCHA, which picked English words at random and rendered them as images of printed text under a wide variety of shape deformations and image occlusions, the word images often overlapping. The user was asked to transcribe some number of the words correctly. A simplified version of GIMPY (EZ-GIMPY), using only one word-image at a time, was installed by Yahoo!, and was used in their chat rooms to restrict access to only human users. A sample of several GIMPY CAPTCHA images are shown in the Fig. 1.

Other researchers were stimulated by this particular problem, and the Principal Scientist of Palo Alto Research Center, Henry Baird, leaded the development of PessimalPrint, a CAPTCHA that uses a model of document image degradations that approximates ten aspects of the physics of machine-printing and imaging of text. This model included spatial sampling rate and error, affine spatial deformations, jitter, speckle, blurring, thresholding, and symbol size. Their paper [32] was the first refereed technical publication on CAPTCHAs.

These works and many others discussed in this chapter have been widely used by the World Wide Web-related industry, from search engines like Yahoo! or Google, to Web e-mail providers (Gmail, Hotmail, etc.), and ultimately, nearly all major Social Networking sites like Facebook or MySpace, to prevent automated subscription, posting, and in general, automated misuse of their services to human users. CAPTCHAs have evolved to become a commodity, as they are integrated as plugins in Content Management Systems (CMSs), for example, Drupal, or even as Web Services. A major instance of a reverse Turing test provided as a Web Service is reCAPTCHA [47] (shown in the Fig. 2), started by the previously mentioned researcher Louis von Ahn. This service can be integrated in any Web page to typically protect a Web form, and it has become very popular, serving more than 30 million instances of the challenge every day. Now this service is provided by Google.

Moreover, the popularity of CAPTCHAs is so big that companies have emerged to take advantage of it, by using them as a platform for serving ads to the consumers [117], as shown in Fig. 3. A very interesting feature of CAPTCHA ads is that it is the very user who writes the brand message into the text field provided, so they effectively read and even learn the message.

On the opposite side, the popularization of CAPTCHA technologies has pushed a number of (quite often successful) attempts to circumvent these kinds of challenges. Attacks include automated bots able to understand the CAPTCHA itself, attacks to the programming structure of the form to avoid solving the CAPTCHA, and crowd sourcing. These attacks are further discussed in the Section 5.1.