\documentclass[twocolumn]{article}

\usepackage{graphicx} 
\usepackage{amsmath}
\usepackage{amsfonts}

\newtheorem{thm}{Theorem}[section]
\numberwithin{equation}{section} %% Comment out for sequentially-numbered
\numberwithin{figure}{section} %% Comment out for sequentially-numbered
 
\begin{document}
\title{Telling Humans and Computers Apart (Automatically)\\ or\\ How Lazy
Cryptographers do AI}
\author{Luis von Ahn\footnotemark[1] \and Manuel
Blum\footnotemark[1]
\and John
Langford\footnotemark[1]
}
\date{}
\maketitle

\footnotetext[1]{Computer Science
Dept., Carnegie Mellon University, Pittsburgh PA 15213.
\{biglou,mblum,jcl\}@cs.cmu.edu
}

If you try to get a new email account at Yahoo, you will be asked to
prove that you're a human and not a computer. Why? Because a single
computer program can get thousands of free email accounts per
second. And that's bad for Yahoo. In this article, we introduce the
technology that Yahoo uses to prevent automatic registration.

This paper is about more than just one particular system.  In fact,
others have independently encountered and solved this problem (for
example \cite{Andrei_Broder}, \cite{Nancy_Chan}, and
\cite{Allison_Coates}).  Inspired by the problem posed in a visit of
Yahoo chief scientist Udi Manber, we have conducted a theoretical
investigation into when such systems \emph{can} exist and to what
other purposes these systems can be applied.

We introduce the concept of a {\sc captcha}: a program that can
differentiate between humans and computers based only on interactions
over a computer network.  Several examples of (possible) {\sc
captcha}s have been built.  This paper presents some of these systems
and discusses a theoretical framework for {\sc captcha}s.

\section*{Gotcha!}

Intuitively, a {\sc captcha} is a program that can generate and grade
tests that:
\begin{itemize} 
\item most humans can pass, but 
\item current computer programs cannot pass.\footnote{  
The words ``Most'' and ``Current'' can be precisely defined, but the
intuitive meaning is good for the purposes of this article.}
\end{itemize} 

{\sc captcha} stands for ``Completely Automated Public Turing Test to Tell
Computers and Humans Apart''. Notice how a {\sc captcha} is like an {\it
automated} version of the Turing Test \cite{TURING}, one in which the
judge is a computer. 

The {\sc p} in {\sc captcha} stands for Public: the code
for the program should be commented and easy to understand; additionally,
the commented code and all the data used by a {\sc captcha} should be
public. Thus a program that can generate and grade tests that distinguish
humans from computers but whose code or data are private is {\it not} a
{\sc captcha}. 

\subsection*{Examples}

Let's look at few examples of {\sc captcha}s before moving on. When
reading, think about why each of these is a valid example of a {\sc
captcha}. The code and demos for all the programs described in this
section can be found online at {\it http://captcha.net}. 

\begin{itemize}

\item {\bf Gimpy.} Consider the following program, which we will refer to
as {\sc gimpy}.  {\sc gimpy} works as follows: it first picks seven words
out of a dictionary and renders the words into a distorted image (as shown
in the figure below). {\sc gimpy} then presents a test to its user, which
consists of the distorted image and the directions: {\it ``type three
words appearing in the image''}. Given the types of deformations that {\sc
gimpy} uses, most humans can read three words from the distorted image,
while current computer programs cannot.  (We still haven't {\it proved} 
that {\sc gimpy}
is a {\sc captcha}; the issues revolving around such a proof will be
discussed later.) 


  \begin{center}
    \includegraphics*[scale=.4]{gimpy_sample.ps}
  \end{center}

\item {\bf Bongo.} Another example of a {\sc captcha} is the program we
call {\sc bongo}\footnote{{\sc bongo} is named after M.M. Bongard, who
published a book of pattern recognition problems (\cite{BP}) in 1951.}. 
{\sc bongo} asks the user to solve a visual pattern recognition problem.
In particular, it displays two series of blocks (the {\sc Left} and the
{\sc Right}). The blocks in the {\sc Left} series differ from those in the
{\sc Right}, and the user must find the characteristic that sets them
apart. A possible {\sc Left} and {\sc Right} series are shown below: 

  \begin{center}
    \includegraphics*[scale=0.8]{bongo_sample1.ps}
  \end{center}

(These two series are different because everything in the {\sc Left} is
drawn
with thick lines, while everything in the {\sc Right} is drawn with thin
lines.)
After seeing the two series of blocks, the user is presented with a
single block and is asked to determine whether this block belongs to the
{\sc Right} series or to the {\sc Left}. The user passes the test if he or
she
correctly determines the side to which the block belongs to.
Try it
yourself: to which side does the isolated block belong in the figure
below?

  \begin{center}
    \includegraphics*[scale=0.8]{bongo_sample2.ps}
    \includegraphics*{bongo_sample3.ps}
  \end{center}

\item {\bf Pix.} Yet another example of a {\sc captcha} is a program that
has a large database of labeled images (such databases can be found in
\cite{GETTY,CORBIS}). All of these images should be pictures of concrete
objects (a horse, a table, a house, a flower, etc).  The program picks an
object at random, finds 6 images of that object from its database,
presents them to the user and then asks the question {\it ``what are these
pictures of?''} Current computer programs should not be able to answer
this question. 

The reader might notice that this example, as stated, is not a {\sc
captcha}. Why? Because it is very easy to write a program that can answer
the question ``what are these images of?'' Remember that all the code and
data of a {\sc captcha} should be publicly available; in particular, the
image database that {\bf pix} uses should be public. Hence,
writing a program that can answer the question ``what are these
pictures
of?'' is easy:
search the
database for the images presented and find their label.  In order for this
program to actually be a {\sc captcha}, the images need to be randomly
distorted before being presented to the user, in such a way that searching
the database for the images is hard for computer programs. 

\item {\bf Eco.} The final example we will mention is a sound-based
{\sc captcha}. The program picks a word or a sequence of numbers at
random, renders the word or the numbers into a sound clip and distorts
the sound clip.  It then presents the distorted sound clip to its user
and asks the user to type in the contents of the sound clip.  Nancy
Chan \cite{Nancy_Chan} has implemented a sound-based system of this
variety.

\end{itemize}

The creation of {\sc captcha}s is an interesting endeavor in and of itself
and
later we will see why it is good to have a wide variety of {\sc captcha}s.
We end this section by remarking that it is still an open problem to
create a text-based {\sc captcha} (one which doesn't use any images or
sound clips).  

\subsection*{The Enemy}

We will consider {\sc captcha}s from the perspective of cryptography, so
we
need the notion of an enemy. In our case, {\sc The Enemy} will be the
person trying to write a program that can pass the tests generated by a
{\sc captcha}. Intuitively, we will assume that {\sc The Enemy} is an
expert programmer with:
\begin{itemize}
\item Complete knowledge of the code and data used by the {\sc captcha}
\item Full access to the web
\item A super computer
\item Lots of free time
\end{itemize}

We want to prove or give evidence that it is hard for {\sc The Enemy} to
write a program that can pass the tests generated by a {\sc captcha}.

\subsection*{Reductions to Hard AI Problems}

How do we {\it prove} that computer programs will never pass the tests
generated by a {\sc captcha}? Unfortunately, we believe there is no way to
prove such a strong statement:  since humans can pass the tests, proving
that computer programs cannot pass them would show that there exist things
that humans can do but computers can't. We (the authors) believe that some
day computers will be as good as humans (and possibly better) in every
respect.

The best we can do is to present evidence that, given the current state of
technology, it is hard to write a program that can pass the tests
generated by a {\sc captcha}. We can do this by proving the following
statement: {\it Any program that passes the tests generated by a {\sc
captcha} can be used as an oracle to solve a hard unsolved Artificial
Intelligence (AI) problem.}

The previous statement requires explanation and justification.
(Hopefully, we will be able to convince the reader that a reduction to a
hard AI problem is the right notion of security for {\sc captcha}s.)

\begin{itemize} 

\item First, by ``[a] program that passes the tests generated by a {\sc
captcha}'', we mean a program (possibly probabilistic)  that has some (not
so small, but precisely defined) probability of passing a given random
test generated by the {\sc captcha}. 

\item What is a hard unsolved AI problem? Intuitively, it is an AI
problem that remains unsolved despite the fact that the AI community
has been working on it for several years. For the proof of this
theorem to go through, an AI problem needs to be {\it precisely}
defined. It is surprisingly difficult (but possible) to precisely
define an AI problem.

\item Why does this give evidence that it is hard to pass the tests
generated by a {\sc captcha}? If an AI problem remains unsolved after many
intelligent people have been working on it for a long time, then it is
hard to write a program that can solve this problem. Our statement says
that it is at least as hard to write a program that can pass the tests
generated by a {\sc captcha}.

\end{itemize} 

Notice that classical cryptography is laid on a foundation similar to
ours: cryptographers only {\it assume} factoring large numbers is hard, as
nobody has found a way to do it. 

\subsection*{P Stands for Public. Why?}

Several people (especially those outside the cryptography community)
have objected to {\sc captcha}s having publicly available code and data.
They claim that {\sc captcha}s would be more secure if the code was
hidden. Here, we will state why we
want all the code and data used by a {\sc captcha} to be publicly
available. 

\begin{itemize}

\item {\bf Hackers}. If a {\sc captcha} requires some private data in
order to be secure, then this {\sc captcha} is very vulnerable to
hacker attacks: once a hacker breaks into the system and finds this
secret data, the {\sc captcha} ceases to be secure forever. We want
{\sc captcha}s to generate tests that are hard to pass for all
computers; not that are hard to pass for computers that don't have a
particular secret.

\item {\bf Reverse Engineering}. If the {\sc captcha} weren't public, {\sc
The Enemy} can still learn a lot about the
way a {\sc captcha} works and all the data it uses by simply taking many
of the tests generated by a {\sc captcha}. 

\item {\bf Analysis}. Moreover, there is no general way to know exactly
how much {\sc The Enemy} can learn about how a {\sc captcha} works.
Hence, we may as well assume that {\sc The Enemy} can learn {\it
everything} about 
how the {\sc captcha} works and then prove that {\it even in this case} it
is hard for {\sc The Enemy} to write a program that can pass the tests
generated by the {\sc captcha}

\item {\bf We're doing AI}. We {\it want} our {\sc captcha}s to be broken!
Why? Because if a {\sc captcha} is broken, then a previously unsolved AI
problem is solved. This is how lazy cryptographers do AI! We help {\sc The
Enemy} as much as we can.

\end{itemize}

\subsection*{Applications}

{\sc captcha}s have several applications. Here we mention just a few.

\begin{itemize} 

\item {\bf Online Polls.} Almost two years ago, {\it
http://slashdot.com} released an online poll asking for the best school in
computer science (a dangerous question to ask over the web!). As it is the
case with most online polls, IP addresses of voters were recorded in order
to prevent single users from voting more than once. However, students at
Carnegie Mellon figured out a way to stuff the ballots and wrote programs
that voted for CMU thousands of times. CMU's score started growing
rapidly.  The next day, students at MIT wrote {\it their} own program and
the poll had become a contest between voting ``bots''. MIT finished with
21,156 votes, Carnegie Mellon with 21,032 and every other school with less
than 1,000. 

The point here is that any online poll suffers from this weakness against
bots. But {\sc captcha}s offer a solution: voters should ``prove'' they
are human before being allowed to vote.

\item {\bf Free Email Services.} Several companies offer free email
services over the web. Most of these suffer from a specific type of
attack: ``bots'' that sign up for thousands of email accounts a
minute.  In particular, web pornography companies use such tactics to
obtain free email accounts from which they can send advertisements. A
solution to this problem is to have users solve a {\sc captcha} test
before they recieve an account. Yahoo has adopted this solution, and,
in fact, uses a variation of our program {\sc gimpy}.

\item {\bf Search Engine Bots.} You may not want to have your web page
indexed. It is sometimes surprising how much others can learn about you by
just typing in your name in Google or Altavista. There is an {\it html}
tag to prevent bots from reading your web page. The tag, however, doesn't
guarantee that bots will not read your web page; it only serves to say
``no bots, please''. Search engine bots, since they usually belong to
large companies, respect web pages that don't want to allow bots.
However, if you want to {\it guarantee} that bots will not enter your
web-site, you need to have your viewers prove that they are indeed human
before letting them in. 

\item {\bf Shopping Agents.} Many web sites offer free shopping to
their users, along with extremely low prices. Part of the reason these
companies can offer such a service is because of
advertisements. However, there are several ``shopping bots''
available, which visit many shopping sites, retrieve the best prices
from all of them and present them to the user.  These shopping agents
are bad for the shopping sites because users don't see the
advertisements.  A shopping site which uses a {\sc captcha} test
before revealing prices will ensure that only humans visit their site.

\end{itemize}

\subsection*{Stealing Cycles From Humans}

{\sc captcha}s aren't always a good solution the the Shopping Agent
problem.  Why? Because if shopping sites display {\sc captcha} tests
before allowing their users to see the prices, then shopping agents
can simply ask the human behind the computer to solve the {\sc
captcha} test.

This same strategy can be used to defeat {\sc captcha}s in many cases.
We call it ``stealing cycles from humans''. Consider free web porn
companies, for instance. These companies can still obtain thousands of
free email accounts even if the email provider uses a {\sc
captcha}. How? The porn companies can have bots that try to get free
email accounts, and as soon as the bots encounter a {\sc captcha}
test, they simply send the test to the porn site. Back at the porn
site, there are several thousand users seeing free pornographic
pictures, and one of them is told: ``please solve the following test
before we can show you the next picture''. {\it Voila!}

This leads to an interesting digression. Notice how stealing cycles
from humans works: humans are used in order to expand the
computational abilities of computers.  In general, how can we use
humans as oracles to expand our computational abilities?  Currently,
there are several things that humans can do but computers can't:
recognize facial expressions from any angle, understand language, read
distorted text, recognize which animal is in a picture. Can we use
humans in some way to make computers solve these problems in a
distributed manner? Can we have a kind of SETI@home project in which
web users help to classify all books in the library of congress?

What is a program that identifies your optimal hair cut?  The ``Find
Haircut'' program can be written by stealing cycles from humans.  If
you visit {\it http://hotornot.com}, you will get a picture of a
person (man or woman) and you are supposed to rate how attractive you
think the person is (on a scale from 1 to 10). After you rate the
person you learn what other users have said about this person and you
also see another person to rank.  This site is very popular: sometimes
entire offices of graduate students are found rating pictures.  The
``Find Haircut'' program is simple: you give it a pictures of yourself
with different haircuts and it posts these picture on {\it
http://hotornot.com}. Whichever picture is rated highest is the
``best'' haircut.

\subsection*{Epilogue}

As a last point, notice the whole idea of a {\sc captcha} can be seen
as ``stealing cycles''. {\sc captcha}s are the ultimate tool for
stealing cycles from intelligent people: malicious, intelligent
programmers (writing programs for getting thousands of free email
accounts, etc.) can be put to work on hard unsolved AI problems.

\begin{thebibliography}{2}

\bibitem{C} Luis von Ahn, Manuel Blum and John
Langford. The Captcha Project {\it http://www.captcha.net}. 

\bibitem{BP} Mikhail M. Bongard. (1970). {\it Pattern Recognition}.
Rochelle
Park, N.J.: Hayden Book Co., Spartan Books.

\bibitem{Andrei_Broder} Andrei Broder. {\it The Altavista Ransom Note}
(unpublished)

\bibitem{Nancy_Chan} Nancy Chan. {\it Program Byan}
{\it http://drive.to/research}

\bibitem{Allison_Coates} A. L. Coates, H. S. Baird, and
R. J. Fateman. "Pessimal Print: A Reverse Turing Test." Proc., ICDAR
2001 Int'l Conf. on Document Analysis and Recognition, Seattle, WA

\bibitem{CORBIS} Corbis. {\it http://www.corbis.com}.

\bibitem{GETTY} The Getty Images. {\it http://www.gettyimages.com}.

\bibitem{MN2} Moni Naor. Verification of a human in the loop or
Identification via the Turing Test. Unpublished.

\bibitem{TURING} Alan M. Turing. Computing Machinery and Intelligence. In:
{\it Mind, Vol. 59, No. 236, pp. 433-460}. 1950. 

\end{thebibliography}

\end{document}




