Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

The Asirra CAPTCHA [EDHS2007], proposed at ACM CCS 2007, relies on the problem of distinguishing images of cats and dogs (a task that humans are very good at). The security of Asirra is based on the presumed difficulty of classifying these images automatically.

In this paper, we describe a classifier which is 82.7% accurate in telling apart the images of cats and dogs used in Asirra. This classifier is a combination of support-vector machine classifiers trained on color and texture features extracted from images. Our classifier allows us to solve a 12-image Asirra challenge automatically with probability 10.3%. This probability of success is significantly higher than the estimate of 0.2% given in [EDHS2007] for machine vision attacks. Our results suggest caution against deploying Asirra without safeguards.

We also investigate the impact of our attacks on the partial credit and token bucket algorithms proposed in [EDHS2007]. The partial credit algorithm weakens Asirra considerably and we recommend against its use. The token bucket algorithm helps mitigate the impact of our attacks and allows Asirra to be deployed in a way that maintains an appealing balance between usability and security. One contribution of our work is to inform the choice of safeguard parameters in Asirra deployments.

REFERENCES

• 1: ASR Asirra: A Human Interactive Proof. On the Web at http://research.microsoft.com/asirra/
• 2: BotBarrier.com. On the web at http://www.botbarrier.com/
• 3: Chih-Chung Chang and Chih-Jen Lin. LIBSVM : a library for support vector machines, 2001. Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm
• 4: Richard Chow , Philippe Golle , Markus Jakobsson , Lusha Wang , XiaoFeng Wang, Making CAPTCHAs clickable, Proceedings of the 9th workshop on Mobile computing systems and applications, February 25-26, 2008, Napa Valley, California [doi>10.1145/1411759.1411783]
• 5: Corinna Cortes , Vladimir Vapnik, Support-Vector Networks, Machine Learning, v.20 n.3, p.273-297, Sept. 1995 [doi>10.1023/A:1022627411411]
• 6: . Douceur and J. Elson. Private communication.
• 7: Asirra: a CAPTCHA that exploits interest-aligned manual image categorization, Proceedings of the 14th ACM conference on Computer and communications security, October 28-31, 2007, Alexandria, Virginia, USA [doi>10.1145/1315245.1315291]
• 8: Philippe Golle , David Wagner, Cryptanalysis of a Cognitive Authentication Scheme (Extended Abstract), Proceedings of the 2007 IEEE Symposium on Security and Privacy, p.66-70, May 20-23, 2007 [doi>10.1109/SP.2007.13]
• 9: Google CAPTCHA. On the web at https://www.google.com/accounts/DisplayUnlockCaptcha
• 10: . Hastie, R. Tibshirani and J. Friedman. The Elements of Statistical Learning (Data Mining, Inference, and Prediction). Springer Series in Statistics, 2001.
• 11: P. Kruizinga , N. Petkov , S. E. Grigorescu, Comparison of Texture Features Based on Gabor Filters, Proceedings of the 10th International Conference on Image Analysis and Processing, p.142, September 27-29, 1999
• 12: . Lopresti. Leveraging the CAPTCHA problem. In Proc. of the Second International Workshop on Human Interactive Proofs, pp. 97--110. Springer Verlag, 2005.
• 13: . Mironov and L. Zhang. Applications of SAT Solvers to Cryptanalysis of Hash Functions. In Theory and Applications of Satisfiability Testing -- SAT 2006, pp. 102--115, 2006.
• 14: . Mori and J. Malik. Recognizing objects in adversarial clutter: Breaking a visual CAPTCHA. In Proc. of the 2003 Conference on Computer Vision and Pattern Recognition, pp. 134--144. IEEE Computer Society, 2003.
• 15: SlashDot. Yahoo CAPTCHA Hacked (posted Jan 29, 2008). On the Web at http://it.slashdot.org/it/08/01/30/0037254.shtml
• 16: Websense Blog (posted Feb 22, 2008). Google's CAPTCHA busted in recent spammer tactics. On the web at http://securitylabs.websense.com/content/Blogs/2919.aspx
• 17: Jeff Yan , Ahmad Salah El Ahmad, A low-cost attack on a Microsoft captcha, Proceedings of the 15th ACM conference on Computer and communications security, October 27-31, 2008, Alexandria, Virginia, USA [doi>10.1145/1455770.1455839]

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)

General Terms:
Security

Keywords:
captcha, classifier, machine learning, reverse turing test, support vector machine