Human or Computer? Take This Test
(Page 2 of 2)
In October Dr.
Blum got his wish. Dr. Malik of Berkeley and Greg Mori, a student, devised
a computer program that could crack Gimpy — both the simple version used
by Yahoo and the harder one on Captcha's Web site.
Since its inception
two years ago, the Captcha effort has been building. Several research teams
have joined the Captcha effort, trying to make and break Captchas and even
using the ideas behind Captchas for new lines of research.
Researchers at the Palo Alto Research Center modified a program used for
scanning text to create a program that could solve certain types of Yahoo-Gimpy
puzzles, says Dr. Henry Baird, who was in charge of that effort. The group
is also developing a new text-based Captcha called Baffletext that it hopes
to license to e-commerce sites.
Inspired by the themes behind Captchas,
Dr. Doug Tygar, a professor of computer science at Berkeley, and his student
Monica Chew are developing alternatives to passwords that are tailored to
human skills. Humans have trouble remembering long, random strings of characters,
yet they excel at remembering faces and objects, noted Dr. Tygar.
Dr. Malik said he first became interested in the effort after attending a
Captcha conference at the Palo Alto center in January. After he and his former
student Dr. Serge Belongie, now at the University of California at San Diego,
developed a new object recognition technique modeled to have some of the
properties of human vision, Dr. Malik decided that Captchas were ideal for
testing their method.
The Yahoo-Gimpy cracking program, written by
Mr. Mori, takes a version of the easy Gimpy, a distorted word displayed in
a cluttered background, and finds some points along the boundary of each
letter, using standard techniques of computer vision theory.
applying the Malik-Belongie method, it makes a radial chart for each point
indicating where the other boundary points are in relation to it. The charts
of boundary points for that letter are compared with the charts of boundary
points for all 26 possible letters. The closest match is usually the correct
Using various tricks to make it run faster, the program can
crack an easy Gimpy puzzle in a few seconds, and it gets the right answer
over 80 percent of the time.
For the harder version of Gimpy, the
researchers devised a program that examines entire words instead of individual
letters, so its performance is in minutes rather than seconds, and it gets
the puzzle right only about a third of the time. Still, the program will
need on average only three tries to get the right answer.
and Mr. Mori are exploring ways of improving the performance of their program
on Gimpy that will also improve their general technique of recognizing objects
in a cluttered background.
"We want to keep working on this in a principled
way so we can use the same technique on an outdoor scene with buildings,
trees and cars," Dr. Malik said.
The general technique, he said, will
have many practical applications, like automated recognition of military
targets or detection of trademark infringements on the Internet.
Yahoo will have to install a new Captcha that is resistant to Dr. Mori's
program. This task will fall to Dr. Manber's successor, since Dr. Manber
moved to a new position last month as chief algorithms officer for Amazon.com.
There, he said, he plans to continue his collaborations with academic researchers.
"I'd love to foster more cooperation between industry and academica," he said. "It's great for everybody."
Technology Briefing | Internet: Starbucks Expands Web Network Service (August 22, 2002)
Technology Briefing | Internet: Bioscrypt Excels In Fingerprint Technology Tests (August 16, 2002)
Officials Link Foreign Web Sites to Cheating on Graduate Admission Exams (August 8, 2002)
BUSINESS TRAVEL; MEMO PAD (July 16, 2002)
Find more results for Computers and the Internet and Tests and Testing .