25-08-2012, 12:54 PM
IMPLEMENTATION OF REVERSE TURING TEST
1IMPLEMENTATION.doc (Size: 1.5 MB / Downloads: 54)
ABSTRACT
The potential difficulty of differentiating humans from computers pretending to be humans was addressed at least as early as 1950, when Alan Turing described his now-famous Turing test. Automated tests which distinguish humans from computers for the purpose of controlling access to web services were first discussed in 1996.
Primitive CAPTCHAs seem to have been developed in 1997 at AltaVista by Andrei Broder and his colleagues to prevent bots from adding URLs to their search engine. In order to make the images resistant to OCR (Optical Character Recognition), the team simulated situations that scanner manuals claimed resulted in bad OCR. In 2000, Luis von Ahn and Manuel Blum developed and publicized the notion of a CAPTCHA, which included any program that can distinguish humans from computers. They invented multiple examples of CAPTCHAs, including the first CAPTCHAs to be widely used, which were those adopted by Yahoo!.
The term "CAPTCHA" was coined in 2000 by Luis von Ahn, Manuel Blum, Nicholas J. Hopper (all of Carnegie Mellon University), and John Langford (then of IBM).
Introduction to Reverse Turing Test
The term reverse Turing test has no single clear definition, but has been used to describe various situations based on the Turing test in which the objective and/or one or more of the roles have been reversed between computers and humans. Conventionally, the Turing test is conceived as having a human judge and a computer subject who attempts to appear human. Critical to the concept is the parallel situation of a human judge and a human subject, who also attempts to appear human. The intent of the test is for the judge to attempt to distinguish which of these two situations is actually occurring. It is presumed that a human subject will always be judged human, and a computer is then said to "pass the Turing test" if it too is judged human. Any of these roles may be changed to form a "reverse Turing test".
Reverse Turing Test is also described as CAPTCHA (Completely Automated Public Turing Test to Tell Computers and Humans Apart).
A CAPTCHA is a type of challenge-response test used in computing to ensure that the response is not generated by a computer. The process usually involves one computer (a server) asking a user to complete a simple test which the computer is able to generate and grade. Because other computers are unable to solve the CAPTCHA, any user entering a correct solution is presumed to be human. Thus, in this way the reverse Turing test is administered by a machine and targeted to a human, in contrast to the standard Turing test that is typically administered by a human and targeted to a machine. A common type of CAPTCHA requires that the user type letters or digits from a distorted image that appears on the screen.
Economic Feasibility
Economic analysis or cost/benefit analysis is most frequently used technique for evaluating the effectiveness of a proposed system. It is a procedure to determine the benefits and savings that are expected from the proposed system and compare them with costs. If the benefits overweigh the costs, a decision is taken to design and implement the system.Otherwise,Further justification or alternative in the proposed system will have to be made if it is to have a chance of being approved. This is an ongoing effort that improves in accuracy at each phase of system life cycle.
LITERATURE SURVEY
History
Moni Naor was the first person to theorize a list of ways to verify that a request comes from a human and not a bot Primitive CAPTCHAs seem to have been developed in 1997 by Andrei Broder, Martin Abadi, Krishna Bharat, and Mark Lillibridge to prevent bots from adding URLs to their search engine. In order to make the images resistant to OCR (Optical Character Recognition), the team simulated situations that scanner manuals claimed resulted in bad OCR. In 2000, Luis von Ahn and Manuel Blum coined the term 'CAPTCHA', improved and publicized the notion, which included any program that can distinguish humans from computers. They invented multiple examples of CAPTCHAs, including the first CAPTCHAs to be widely used, which were those adopted by Yahoo.
Accessibility
Because CAPTCHAs rely on visual perception, users unable to view a CAPTCHA (for example, due to a disability or because it is difficult to read) will be unable to perform the task protected by a CAPTCHA. Therefore, sites implementing CAPTCHAs may provide an audio version of the CAPTCHA in addition to the visual method. The official CAPTCHA site recommends providing an audio CAPTCHA for accessibility reasons.
Attempts at more accessible CAPTCHAs
Even an audio and visual CAPTCHA will require manual intervention for some users, such as those who have visual disabilities and also are deaf. There have been various attempts at creating CAPTCHAs that are more accessible. Attempts include the use of JavaScript, mathematical questions ("what is 1+1"), or "common sense" questions ("what color is the sky on a clear day"). However, none of these attempts meet both the criteria of being able to be automatically generated and not relying on the type of CAPTCHA being new to the attacker. Therefore, they are not CAPTCHAs and do not provide the protection that true CAPTCHAs provide.
Insecure implementation
Like any security system, design flaws in a system implementation can prevent the theoretical security from being realized. Many CAPTCHA implementations, especially those which have not been designed and reviewed by experts in the fields of security, are prone to common attacks.
Some CAPTCHA protection systems can be bypassed without using OCR simply by re-using the session ID of a known CAPTCHA image. A correctly designed CAPTCHA does not allow multiple solution attempts at one CAPTCHA. This prevents the reuse of a correct CAPTCHA solution or making a second guess after an incorrect OCR attempt. Other CAPTCHA implementations use a hash (such as an MD5 hash) of the solution as a key passed to the client to validate the CAPTCHA. Often the CAPTCHA is of small enough size that this hash could be cracked. Further, the hash could assist an OCR based attempt. A more secure scheme would use an HMAC. Finally, some implementations use only a small fixed pool of CAPTCHA images. Eventually, when enough CAPTCHA image solutions have been collected by an attacker over a period of time, the CAPTCHA can be broken by simply looking up solutions in a table, based on a hash of the challenge image.
Image-recognition CAPTCHAs
Some researchers promote image recognition CAPTCHAs as a possible alternative for text-based CAPTCHAs. To date only rapidshare made use of an image based CAPTCHA. Many amateur users of the phpBB forum software (which has suffered greatly from spam) have implemented an open source image recognition CAPTCHA system in the form of an addon called KittenAuth which in its default form presents a question requiring the user to select a stated type of animal from an array of thumbnail images of assorted animals. The images (and the challenge questions) can be customized, for example to present questions and images which would be easily answered by the forum's target userbase. Furthermore, for a time, RapidShare free users had to get past a CAPTCHA where you had to only enter letters attached to a cat, while others were attached to dogs. This was later removed because users had trouble entering the correct letters.
Image recognition CAPTCHAs face many potential problems which have not been fully studied. It is difficult for a small site to acquire a large dictionary of images which an attacker does not have access to and without a means of automatically acquiring new labelled images, an image based challenge does not meet the definition of a CAPTCHA. KittenAuth, by default, only had 42 images in its database. Microsoft's "Asirra," which it is providing as a free web service, attempts to address this by means of Microsoft Research's partnership with Petfinder.com, which has provided it with more than three million images of cats and dogs, classified by people at thousands of US animal shelters. Unfortunately for Microsoft, researchers claim to have written a program than can break the Microsoft Asirra CAPTCHA.