How Spam is Improving AI

Anti-spam puzzles are helping researchers develop smarter algorithms.

Those pesky visual puzzles that have to be completed each time you sign up for a Web mail account or post a comment to a blog are under attack. It's not just from spam-spewing computers or hackers, though; it's also from researchers who are using anti-spam puzzles to develop smarter, more humanlike algorithms.

Cats v. Dogs: A project called Asirra uses photographs of cats and dogs to distinguish between humans and computers. Normally, it is a difficult task for computers, but a new algorithm can correctly classify the images 83 percent of the time. Credit: Microsoft

The most common type of puzzle (a series of distorted letters and numbers) is increasingly being cracked by smarter AI software. And a computer scientist has now developed an algorithm that can defeat even the latest photograph-based tests.

Known as CAPTCHAs (Completely Automated Public Turing test to tell Computers and Humans Apart), these puzzles were developed in the late '90s as a way to separate real users from machines that create e-mail accounts to send out spam or log in to message boards to post ad links. The Turing Test, named after mathematician Alan Turing, involves measuring intelligence by having a computer try to impersonate a real person.

Textual CAPTCHAs are a good way to tell humans and spam-bots apart, because distorted letters and numbers can easily be read by real people (most of the time) but are fiendishly difficult for computers to decipher. However, computer scientists have long seen CAPTCHAs as an interesting AI challenge. Designers of textual CAPTCHAs have gradually introduced more distortion to prevent machines from solving them. But they have to balance security against usability: as distortion increases, even real human beings begin to find CAPTCHAs difficult to decipher.

Earlier this year, Jeff Yan, a researcher at the University of Newcastle, U.K., revealed a program capable of completing the textual CAPTCHAs used to protect Microsoft's Hotmail, MSN, and Windows Live services with a success rate of 60 percent. This might not sound like much, but it's significant, since a computer can try its attack thousands of times each minute. Yan withheld the paper until Microsoft had a chance to tweak its CAPTCHAs so that they were more difficult to crack. But at the ACM Computer and Communication Security Conference in Alexandria, VA, later this month, Yan will present details of another program that he says can crack even more widely used textual CAPTCHAs.

Story continues below

So an alternative is to ask users to solve different kinds of puzzles. But another paper to be presented at the same conference describes an algorithm that could spell trouble for even newer CAPTCHAs.

Philippe Golle of the Palo Alto Research Center has developed a program that can correctly pass an image-based CAPTCHA called Asirra, developed by Microsoft. Asirra asks users to correctly classify images of either cats or dogs using a database of three million images provided by animal-rescue organizations. This task should be even harder for computers than recognizing squiggly letters, but Golle's program can correctly identify the cats or dogs shown by Asirra 83 percent of the time.