Automatic construction of human interaction proof engines

Abstract

Human Interaction Proofs (“HIPs”, sometimes referred to as “captchas”), may be generated automatically. An captcha specification language may be defined, which allows a captcha scheme to be defined in terms of how symbols are to be chosen and drawn, and how those symbols are obscured. The language may provide mechanisms to specify the various ways in which to obscure symbols. New captcha schemes may be generated from existing specifications, by using genetic algorithms that combine features from existing captcha schemes that have been successful. Moreover, the likelihood that a captcha scheme has been broken by attackers may be estimated by collecting data on the time that it takes existing captcha schemes to be broken, and using regression to estimate the time to breakage as a function of either the captcha's features or its measured quality.

1 . An automated method for generating Human Interaction Proofs (HIP) schemes, the method comprising:
 training one or more optical character recognition (OCR) engines on captchas generated by an input HIP scheme and on answers to the captchas generated by the input HIP scheme;   determining, by the one or more trained OCR engines, answers to captchas generated by one or more candidate HIP schemes;   determining an ability of the one or more trained OCR engines to correctly determine answers to the captchas generated by the one or more candidate HIP schemes; and   generating, based on the determined ability of the one or more trained OCR engines to correctly determine answers to the captchas generated by the one or more candidate HIP schemes, at least one output HIP scheme.   
     
     
         2 . The automated method of  claim 1 , wherein generating the at least one output HIP scheme includes:
 producing a combined HIP scheme based on at least two HIP schemes of the one or more candidate HIP schemes; and   generating the at least one output HIP scheme based on the combined HIP scheme.   
     
     
         3 . The automated method of  claim 1 , wherein the method further comprises:
 estimating a time to breakage of the at least one output HIP scheme based on the determined ability of the one or more trained OCR engines to correctly determine answers to the captchas generated by the one or more candidate HIP schemes.   
     
     
         4 . The automated method of  claim 1 , wherein the at least one output HIP scheme is generated in a HIP specification language. 
     
     
         5 . The automated method of  claim 1 , wherein the at least one output HIP scheme defines:
 an alphabet from which multiple symbols are to be selected as answers to output captchas;   multiple complications that are selectable for use in generation of the output captchas; and   multiple values that define extents to which respective complications of the multiple complications are to be applied to the symbols of the alphabet in the generation of the output captchas.   
     
     
         6 . A computing device for generating Human Interaction Proofs (HIP) schemes, comprising:
 a memory and a processor that are respectively configured to store and execute instructions that cause the computing device to perform operations for generating the HIP schemes, the operations including:
 applying one or more trained OCR engines to one or more candidate HIP schemes; 
 determining, based on the applying of the one or more trained OCR engines to the one or more candidate HIP schemes, information regarding an ability of the one or more trained OCR engines to ascertain answers to captchas generated by the one or more candidate HIP schemes; and 
 employing the information regarding the ability of the one or more trained OCR engines to generate at least one output HIP scheme. 
   
     
     
         7 . The computing device of  claim 6 , wherein the information regarding the ability of the one or more trained OCR engines includes statistics regarding a percentage of captchas generated by the one or more candidate HIP schemes that can be decoded by the one or more trained OCR engines. 
     
     
         8 . The computing device of  claim 6 , wherein employing the information regarding the ability of the one or more trained OCR engines includes:
 selecting a set of HIP schemes from the plurality of HIP schemes;   producing a combined HIP scheme based on at least two HIP schemes from the selected set of HIP schemes; and   generating the at least one output HIP scheme based on the combined HIP scheme.   
     
     
         9 . The computing device of  claim 6 , wherein the operations further comprise:
 determining, based on the applying of the one or more trained OCR engines to the one or more candidate HIP schemes, information regarding an ability of the one or more trained OCR engines to ascertain answers to captchas generated by the at least one output HIP scheme.   
     
     
         10 . The computing device of  claim 6 , wherein the operations further comprise:
 estimating a time to breakage of the at least one output HIP scheme based on the information regarding the ability of the one or more trained OCR engines to ascertain answers to captchas generated by the at least one output HIP scheme.   
     
     
         11 . The computing device of  claim 6 , wherein employing the information regarding the ability of the one or more trained OCR engines includes:
 selecting a starting set of HIP schemes from the plurality of HIP schemes based on measures of quality of individual HIP schemes of the plurality of HIP schemes;   producing a combined HIP scheme based on at least two HIP schemes from the selected starting set of HIP schemes, including:
 combining aspects from each of the at least two HIP schemes from the starting selected set of HIP schemes into the combined HIP scheme; 
   generating an output HIP scheme based on the combined HIP scheme, including:
 mutating the combined HIP scheme into the output HIP scheme; and 
   outputting, by a computing device, the output HIP scheme.   
     
     
         12 . The computing device of  claim 6 , wherein employing the information regarding the ability of the one or more trained OCR engines includes:
 combining aspects from each of at least two HIP schemes into a combined HIP scheme.   
     
     
         13 . The computing device of  claim 6 , wherein employing the information regarding the ability of the one or more trained OCR engines further includes:
 mutating the combined HIP scheme by changing a parameter of the combined HIP scheme.   
     
     
         14 . The computing device of  claim 6 , wherein the HIP schemes of the plurality of HIP schemes are in a HIP specification language. 
     
     
         15 . The computing device of  claim 6 , wherein the at least one output HIP scheme defines:
 an alphabet from which multiple symbols are to be selected as answers to output captchas;   multiple complications that are selectable for use in generation of the output captchas; and   multiple values that define extents to which respective complications of the multiple complications are to be applied to the symbols of the alphabet during generation of the output captchas.   
     
     
         16 . The computing device of  claim 15 , wherein the multiple complications include a distracter, a background, and/or a distortion. 
     
     
         17 . A computer-readable storage medium, comprising a memory and/or a disk, that stores computer-executable instructions that facilitate generation of human interaction proof (HIP) schemes, wherein the computer-executable instructions, in response to execution by a computing device, cause the computing device to perform operations, the operations comprising:
 determining, by one or more OCR engines trained on captchas generated by an input HIP scheme and on answers to the captchas, answers to captchas generated by a plurality of candidate HIP schemes;   determining an ability of the one or more OCR engines to solve the captchas generated by the plurality of candidate HIP schemes; and   producing an output HIP scheme from aspects of each of at least two of the plurality of candidate HIP schemes according to the determined ability of the one or more OCR engines to solve the captchas generated by the plurality of candidate HIP schemes.   
     
     
         18 . The computer-readable storage medium of  claim 17 , wherein the aspects include:
 a background for at least some symbols;   an amount of skew for at least some of the symbols;   an amount of blurring for at least some of the symbols; and   an amount of warping for at least some of the symbols.   
     
     
         19 . The computer-readable storage medium of  claim 17 , wherein the operations further comprise:
 adding and/or dropping a feature from the output HIP scheme, wherein the feature includes a distracter, a background, and/or a distortion.   
     
     
         20 . The computer-readable storage medium of  claim 17 , wherein the operations further comprise:
 estimating a time to breakage of the output HIP scheme according to the determined ability of the one or more OCR engines to solve the captchas generated by the plurality of candidate HIP schemes.