Breaking Text-Based CAPTCHAs using Average Vertical Partition

摘要

CAPTCHA, which stands for Completely Automated Public Turing Test to Tell Computers and Humans Apart, has been widely used as a security mechanism to defend against automated registration, spam and malicious bot programs. There have been many successful attacks on CAPTCHAs deployed by popular websites, e.g., Google, Yahoo!, and Microsoft. However, most of these methods are ad hoc, and they have lost efficacy with the evolution of CAPTCHA. In this paper, we propose a simple but effective attack on text-based CAPTCHA that uses machine learning to solve the segmentation and recognition problems simultaneously. The method first divides a CAPTCHA image into average blocks and attempts to combine adjacent blocks to form individual characters. A modified K-Nearest Neighbor (KNN) engine is used to recognize these combinations, and using a Dynamic Programming (DP) graph search algorithm, the most likely combinations are selected as the final result. We tested our attack on the popular CAPTCHAs deployed by the top 20 Alexa ranked websites. The success rates range from 5.0% to 74.0%, illustrating the effectiveness and universality of our method. We also tested the applicability of our method on three well-known CAPTCHA schemes. Our attack casts serious doubt on the security of existing text-based CAPTCHAs; therefore, guidelines for designing better text-based CAPTCHAs are discussed at the end of this paper.