A CAPTCHA Implementation Based on 3D Animation

Abstract—In order to distinguish between human users and computer programs, CAPTCHA (Completely Automated
Public Turing test to tell Computers and Human Apart) mechanism is widely applied in websites such as accounts application website. While the major implementation of
CAPTCHA method—2D still image verification code based on
OCR technology is threatened by developing artificial intelligence and image recognition technologies. In this paper, we propose a new approach to implement CAPTCHA mechanism based on 3D Animation, utilizing the weakness of computer vision, which make it robust to computer attacks and convenient for users to recognize, and implemented this method to generate a 3D animation verification code.
Keywords-CAPTCHA;VerificationCode;Moving
Three-dimensional Animation

I.

Figure 1.

objects;

INTRODUCTION

Internet is crucial to each respect of life all over the globe nowadays, through which we could retrieve and exchange information freely and efficiently. Given the fundamental relation between internet and people’ s life, vast malicious computer programs attack websites for profits, such as auto application for some mails’ accounts to send junk e-mails, etc. CAPTCHA (Completely Automated Public Turing test to tell Computers and Human Apart) system emerges to solve this problem by identifying end-users of internet whether a real person or an automated computer program[1][2][3]. It also prevents malicious computer program impropriating limited resources on internet and maintains the security of internet. The key point of
CAPTCHA is the question that human users could get answers easily while the current computer programs could not afford the right answer yet.
CAPTCHA is first proposed by a study group of
Carnegie Mellon University and studied by researchers all over the world after its appearance. Currently, CAPTCHA methods are generally divided into two groups: OCR-based methods and Non-OCR-based methods[2].
OCR-based methods provide images of words with distortion and various pictorial effects and ask users to type the words. Due to the presence of pictorial effects, computer programs encounter problems in the recognition process and only human users are capable of recognizing words easily.
This sort of method is based on the weak points of optical character recognition (OCR) programs that it is difficult to recognize reading texts printed with a low quality and reading manuscripts[4], which brings to us possibility that certain form of images of word can be recognized only by human users but not by any OCR program in a certain extent.
Now, this kind of method has become the major pattern of

978-0-7695-3843-3/09 $26.00 © 2009 IEEE
DOI 10.1109/MINES.2009.298

179

Simple OCR_based CAPTHA

However, as OCR technology based on neural network and artificial intelligence develops[9], the security of such
OCR-based CAPTCHA suffers more and more serious threats. Take some famous portal sites for example, Yahoo, as the first user website of CAPTCHA mechanism, its
CAPTCHA systems used to prevent automated registration of free Yahoo Mail accounts have been defeated by a software released by a Russian researcher with the recognition rate about 30%[6]. Microsoft live mail was also captured by the junk mail many times[7][8]. For that reason, an increasing number of OCR-based CAPTCHA designers think out the solution that they add a large amount of miscellaneous interference information into the image to reinforce verification’s robustness, which unfortunately leads difficulty for human to recognize the word, as shown in
Figure 2.
Figure 2. Complex OCR_based CAPTCHA

Non-OCR-based methods are based on the features of multimedia systems such as pictures and sounds and usually using methods like small puzzle games[4]. Such as PIX, which ask users to select pictures of certain subject among pictures of various subjects [1]. Besides this, there are a lot of methods, for example, CAPTCHA algorithm proposed by
Y. Rui is based on recognition of human face[10],
CAPTCHA technology developed by R. Datta is based on recognition of photos in daily life[11], CAPTCHA algorithm proposed by J. Elson is relied on judgment of the similarity of photos[12], etc.
In this paper we propose a Non-OCR-based CAPTCHA method in the form of 3D animation and based on the recognition of moving objects in videos. The rest part of this paper is organized as follows: In section 2, we analyze the crucial point of designing the new CAPTCHA mechanism by concerning about the defects of current tracking moving objects methods, and then we describe the major generating step of this new CAPTCHA method. In section 3 we illustrate the flow chart by implementing our method step by step. Section 4 concludes with a summary and comment on future research.

II.

DESIGN

In the field of computer vision, there are some main algorithms on detection of moving objects in video, such as frame difference method[13][14], optical flow method[19], temporal difference algorithm[17][18], background subtraction method[15][16], etc. While all of these algorithms have their own defects in tracking moving objects, for example, optical flow method can’t do real-time monitoring well[15], template matching algorithm can’t tell the difference between the target objects from the interference objects when they are in similar shape[20], and frame difference method may miss target objects or just abstract a little part of target[21], background subtraction method could not get right information when target objects and background looks similar[13]. Moving objects recognition is more difficult to solve than optical character recognition nowadays in a great extent. It’s especially difficult to track numerous real-time moving objects in a complicated background for computer[5], but easier for human users. Therefore, the implementation method of
CAPTCHA based on the recognition of moving objects could utilize those defects to improve the safety of
CAPTCHA.
A. Main idea
In the design of 3D animation, we make continuous frames to form a complete animation, which means that, we need to design each frame picture and make them show one by another to generate an animation. And the new kind of
CAPTCHA is still shown in the form of characters for users to recognize, but characters are hidden in 3D animation.
Firstly, we determine the shown location of verification code in the animation screen and the objects’ attributes like colors, shapes in the animation. From each frame to another, the objects in animation are in movement, so we need to set each object’s moving orbits at first. Secondly, in the duration of objects’ moving, we compare the shown position of the verification code to the position of each moving object, if objects are in the position of supposed verification code’s shown position, the corresponding moving objects will be changed in one attribute of themselves.
In this way, the showing process of verification code is a dynamic process comparing to the showing method of 2D still image verification code. Only when we see the moving process, we could get the right characters shown in the animation. This is the zero knowledge per frame principle in our design, which means that each frame of the animation would not leak any information of the verification code. The moving objects’ attributes changing is the key reason of the showing of verification code in the animation, so only when we see the animation we could capture the content of it. This principle assures that our method could resist the current
OCR attacks. As a result, computer programs could only retrieve characters’ information by detecting moving objects in animation.
In the field of computer vision, the current method also can’t help a lot. Firstly, because of the preset various moving orbit of each moving object and massive moving objects in animation, it’s hard to get clear distinction between frames

and focus on the obvious moving objects with crucial information, so frame difference method properly would miss tracking target of animation. What’s more, via this avenue of showing characters, it’s hard to detect the crucial moving objects with important information of CAPTCHA, because animation is full of similar moving objects. This makes our method avoid the detection method such as temporal difference algorithm and background subtraction method by taking advantages of their weak points listed above. Meanwhile, intending to get information from 3D animation requires real-time detection, while real-time monitoring is still the defect of optical flow method.
As we’ve discussed above, our new method of generating
3D animation as the carrier of verification code could suffer current OCR attacks to 2D still image verification code and recognition attacks aiming at moving objects in computer vision field.
B. Algorithm of design
According to the main design idea of new CAPTCHA, we design the flowing algorithms to implement our ideas, as
Figure 3 shows.

Figure 3. Algorithm of generating new CAPTCHA

Step 1, we choose some elements from one or more sets, such as English alphabet set or Arabic numerals set, to consist the original set of the verification code, which should meet the needs of the human’s easy recognition of these elements from the original set.
Step 2, we randomly select 3 or more elements from the original set to form the verification code and determine the position information of it in the animation screen expressed in the way of pixel coordinate according to the size of the animation screen we set.
Step 3, the aim of this step is to draw a single frame of the animation. The animation is generated by the consistent drawing of frames. At first, we set the number of drawn frame 0.
1.
When we draw the first frame in the animation, we need to decide the total number of the moving objects in the frame, the initial position information of each object, and the showing attributes such as the color, the size and the shape of the moving objects. What’s more, we should determine every object’s moving track and select one attribute of their own as the changing attribute of all the moving objects. In the following frame’s drawing, we only need to decide each object’s current position information by the position information in the prior frame and the moving track; others still the same as the prior frame.
2.
In each frame’s painting, we need to compare the pixel coordinate of each object and the pixel coordinate of

180

the verification code. If they are the same, the object’s changing attribute should be changed, which means that the current value of the object’s changing attribute should be replaced by other elements except itself in the attribute’s source set randomly.
3.
After one frame’s drawing, the drawn frame number plus 1, the pixel data of this frame is reserved in the memory areas.
Step 4, we set the total number of frames of the animation, and loop Step 3 until the drawn frame number reaches the total number of frames of the animation. All the pixel data of each frame is preserved in GIF format or AVI format. the position of elements in the matrix to the position of pixels in the animation screen, in which way we can determine the pixel coordinates of the verification code in the animation screen. For example, if the pixel coordinate in the animation screen is (i, j), then the corresponding location of the element in the matrix is the location of row (100-j) column i. As Figure 5 shows, this is number 7’s 01 matrix.

III. THE IMPLEMENTATION OF
THREE-DIMENSIONAL ANIMATION CAPTCHA
We implemented the new design utilizing VC++ and
OPENGL. We show the details in Figure 4.

Figure 5. 01 Matrix of “7”

Step 3, it’s the step to draw the frame of the animation. In each frame, we used 150*150 points constituting a grid pattern, which means that 22500 points work as the vertexes of small quadrangles form a big quadrangle as a grid pattern.
The vertexes are expressed in the way of coordinates of X, Y and Z, which determine the position of each quadrangle in the grid pattern. The value of X and Y is a fixed, but the value of Z is determined by a sin function. We randomly set the color of each small quadrangle from the color set of red, green, and blue. At last, we set color as the changing attribute of this animation.
In the animation, after each 3 frames’ drawing, each point’s value of coordinate Z is replaced by the adjacent right point’s, and the points located in the rightmost column in the grid is replaced by the corresponding points’ value of coordinate Z in the leftmost column in the same row.

Figure 4. Example of generating a 3D animation verification code

Step 1, we choose some elements from English alphabet and Arabic numerals consisting the original source set of verification code, except some elements that may confused with each other in shape, in order to make the verification code much easier to be recognized such as the number 0 and the letter O, their shape is similar. The set is as following
{A,B,D,E,F,P,Q,R,T,U,V,X,Y,H,J,K,L,M,N,3,4,6,7,8,9}.
Then three letters are selected randomly from the original source set to form a verification code. We change the verification code in form of matrix with elements of 0 and
1in which the number of rows is 100 and the number of columns is 240.The example is shown in Figure 5, which shows the shape of number 7. The areas of element 1 in the matrix form the shape of a letter or a number as the area of the verification code, and the areas of element 0 are outside the verification code’s area.
Step 2, we set the screen size of the animation of 240 pixels*100 pixels. With the reflection function, we change

Figure 6. Example of changing of points’ value of coordinate z

Let’s take an example, in Figure 6, when exchanging happens, the Point 1’s value of coordinate Z is replaced by the value of coordinate Z of Point 2. Because Point A, B, C and D are the points in the rightmost column in the grid pattern, their value of coordinate Z should be replaced by the
Point a, b, c, and d correspondingly.

181

Meanwhile, we set the rotation angle around X axis and
Y axis and Z axis to make the grid pattern in the animation seem like a motive wave, which makes the moving track much more complex.
When this step is called the second time or more, the following measures should be taken. The total number of the small quadrangles in the grid pattern, the moving track and the changing attribute set in the first frame’s drawing remains unchanged, and the color of each quadrangle is the same as the prior frame. We only should change the position of each quadrangle by the moving track and the position in the prior frame.
Step 4, we calculate the center point of each quadrangle by the position information from Step 3 expressed in the way of 3D coordinate(x, y, z), then change it to the 2D pixel coordinate as ( i , j ).
Step5, we judge the pixel coordinate of the position of each quadrangle’s center point whether or not in the pixel coordinate regions of the verification code in the animation screen. If it is, go to Step6; else, go to Step 7.
Step 6, we change the color of the quadrangle to other colors randomly, for example, if the color of the quadrangle is red, then it may change to green or blue.
Step 7, according to the position and color of small quadrangles, we draw the grid pattern in this frame. Then there would be a loop, we call Step 3 to make the continuous drawing of frames to produce an animation showing the verification code in the screen.
Step 8, we record the animation for some time and reserved it as 3D animation CAPTCHA in the type of GIF, which would make it convenient to be utilized in the web page. [11]

CONCLUSION

[12]

In our research, we have developed design of new
CAPTCHA and implemented it in one case. In this study we make our design of CAPTCHA in a new field—the recognition of moving objects, and we propose a new design principle— zero knowledge per frame principle. In the field of computer vision, the current major methods of detecting moving objects are not much practical yet, and our design make use of the defects of these methods to provide difficulties for computer programs’ recognition of this new
CAPHTCHA. And the zero-knowledge per frame principle makes it much more impossible for computer programs to identify the content of CAPTCHA in each frame, so that computer programs using the OCR method which tackles with current 2D still image verification code cannot solve this difficulty.
What’s more, this method is convenient for human to recognize, which assures its practicality. How can make the new CAPTCHA much safer to resist attacks and much easier for human to recognize is still the main topic of our future study. V.

[13]
[14]
[15]

[16]
[17]

[18]

[19]

[20]

ACKNOWLEDGEMENT
[21]

This work is supported by NSFC 60603012, NSFC
60703009.

182

”“，

[10]

，

[9]

，

[8]

，

[7]

，

[6]

，

[5]

，

[4]

，

[3]

，

[2]

L. von Ahn,M. Blum, and J. Langford, Telling Humans and
Computers Apart Automatically, Communications of the ACM,
February 2004, 57-60.
Luis von Ahn Manuel Blum and John Langford Telling Humans and Computers Apart Automatically: How Lazy Cryptographers do
AI In Communications of the ACM 2004.
Luis von Ahn Manuel Blum Nicholas J Hopper and John
Langford The CAPTCHA Web Page: http://www.captcha.net
2000.
Mohammad Shirali-Shahreza and Sajad Shirali-Shahreza, Advanced
Collage CAPTCHA, Fifth International Conference on Information
Technology: New Generations, 2008, p1234-1235.
C Hue, JP Le Cadre, P Perez, Tracking multiple objects with particle filtering, Aerospace and Electronic Systems, IEEE Transactions on,
Vol. 38, No. 3. (2002), pp. 791-812.
Thomas Claburn, “Yahoo’s CAPTCHA Security Reportedly Broken”, http://www.informationweek.com/news/internet/webdev/showArticle. jhtml?articleID=205900620..
Microsoft Live Hotmail CAPTCHA-Hacked in 6 seconds http://news.softpedia.com/news/Microsoft-Live-Hotmail-CAPTCHAHacked-In-6-Seconds-83341.shtml. Yan, J. and Salah El Ahmad, A. A Low-cost Attack on a Microsoft
CAPTCHA, In CCS'08. Proceedings of the 15th ACM Conference on
Computer and Communications Security, Alexandria, Virginia, USA,
October 27-31, 2008.
K Chellapilla, K Larson, P Simard, M Czerwinski, Computers beat humans at single character recognition in reading-based Human
Interaction Proofs”, 2nd Conference on Email and Anti-Spam
(CEAS), 2005.
Y. Rui and Z. Liu. ARTIFACIAL: Automated reverse turing test using facial features. Technical Report MSRTR-2003-48, Microsoft,
April 2003.
R. Datta, J. Li, and J. Z. Wang. IMAGINATION: a robust image-based CAPTCHA generation system. Proc. of 13th ACM Int.
Conf. on Multimedia (MULTIMEDIA 05), pp. 331–334, November
2005.
J. Elson, J. R. Douceur, J. Howell, and J. Saul. ASIRRA: a
CAPTCHA that exploits interest-aligned manual image categorization.
Proc. of 14th ACM Conf. on Computer and Communications Security
(CCS 2007), pp. 366–374, October – November 2007.
Gavrila D M, The visual analysis of human movement: a survey,
Computer Vision and Image Understanding, 1999, vol.73,p82-89.
Jia Deyun, Computer Vision, Beijing: Science publisher, 2000, p26-235. Zhou Xihan, Liu Bo and Zhou HeQin, A Motion Detection Algorithm
Based on Background Subtraction and Symmetrical Differencing,
Computer Simulation, 2005, vol.22, p117-119.
McKenna S and Jabri Z Duric Z, Tracking groups of people,
Computer Vision and Image Understanding, 2000, vol(80), p42-56.
Tian Juan and Zheng Yuzheng,Application of template matching technique in image recognition, Transducer and Microsystem
Technologies, 2008, vol.27,p112-113.
Xu Bo, Li Zhengming, A New Algorithm of Correlation Tracking
Based
on
Adaptive
Template,
Optics&
Optoelectronic
Technology,2004, vol.2,p62-64.
Barron J, Feet D, Beauchemin S. Performance of optical flow techniques, International
Journal
of
Computer
Vision,
1994,vol.12,p43-77.
Qin Xianxiang and Chen Hua, Amelioration of Template Matching
Arithemetic for Moving Target Recognition and Tracking, Journal of
Guangxi Academy of Sciences, 2008, vol.24, p293-295.
Wang Jianping, Liu Wei and Wang Jinling, A Moving Object
Detection and Recognition Method in Video Sequences, Computing
Technology and Automation, 2007, vol.26, p78-80.

，

IV.

REFERENCES
[1]