Originally created 10/26/01

Robot solves Internet robot problem



Manuel Blum was having trouble with his hand-held computer, so he turned to an Internet chat room for advice on how to recover a lost file. A seemingly helpful reply directed him to a Web site that would supposedly solve his problem.

But what he found there was junk - a vendor trying to sell him something.

"I had gotten stung by a 'bot," Blum realized. Robots, or automated programs, now routinely scan through chat rooms and, masquerading as people, send messages designed to lure computer users to certain vendor sites.

It's become a major problem on the Internet, as has the use of 'bots to register for e-mail addresses that are later used to send unwanted advertisements, or spam, to e-mail users.

Blum's research team at Carnegie Mellon University has come up with a solution to the problem, one that the Web portal Yahoo implemented last month. Now, when computer users try to register with Yahoo, they must pass a test to verify that they are human, not a robot.

The test is administered by a computer program.

"Here you have a computer program that creates a test, administers it and grades it, but can't pass its own test," Blum said.

It's what Blum calls a "Captcha," a "gotcha"-inspired acronym that means "Completely Automatic Public Turing test to tell Computers and Humans Apart."

The Captcha is based on the fact that people can easily analyze images that flummox computers. For the Yahoo site, new registrants must read a common word that has been twisted or distorted and then type it into a box. It's easy for humans; impossible for computers.

The Captcha program is an example of a problem that had plagued Yahoo and other Internet service providers, but could easily be solved by selecting the right algorithm, or problem-solving method. Matching these real world problems with solutions already devised by theoretical computer scientists is the goal a newly funded program at Carnegie Mellon.

"If you're in academia, you're always looking for interesting problems," said Udi Manber, Yahoo's chief scientist and a former computer science professor at the University of Arizona. "If you're in industry, like me, you've got too many interesting problems."

Manber visited Carnegie Mellon about a year ago to discuss problems that faced Yahoo; Captcha was one of the projects that developed from that visit.

Manber acknowledges that computers may eventually solve the Captcha problem and that the test will need to be toughened, but Blum actually looks forward to the day that computers defeat the test.

If AI programs can learn to read distorted characters, he said, they would also be able to read words off of almost any sort of document, including the odd-sized characters often used in print advertisements. That in turn would mean that virtually any document in the Library of Congress could be scanned and made easily available to computer users. And that would be a bigger boon to society than a Captcha test.

"I am confident that computers someday are going to blow us out of the water in terms of intelligence," Blum said. "I'd like to be around when that happens."