Automatic construction of human interaction proof engines

• US 8,739,276 B2
• Filed: 06/22/2010
• Issued: 05/27/2014
• Est. Priority Date: 06/22/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hulten, Geoffrey J., Simard, Patrice Y., Kirovski, Darko, Lind, Jesper B., Meek, Christopher A.
• Primary Examiner(s): Lipman, Jacob
• Application Number:
  US12/821,124
• Publication Number:
  US 20110314537A1
• Time in Patent Office: 1,435 Days
• Field of Search: 726/17
• US Class Current: 726/17
• CPC Class Codes: G06F 21/30 Authentication, i.e. establishing the identity or authorisation of security principals
• CPC Class Codes: G06F 21/31 User authentication
• CPC Class Codes: G06F 21/577 Assessing vulnerabilities and evaluating computer system security
• CPC Class Codes: G06F 2221/2133 Verifying human interaction, e.g., Captcha
• CPC Class Codes: G06F 9/44 Arrangements for executing specific programs
• CPC Class Codes: H04L 9/32 including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials

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.

Claims

1. One or more computer-readable storage media that store computer-executable instructions to generate human interaction proofs, wherein the computer-executable instructions, when executed by a computer, cause the computer to perform acts comprising:

receiving, in a captcha specification language, a definition of a human interaction proof scheme that defines;

an alphabet from which multiple symbols are to be selected as answers to a human interaction proof,

multiple complications that are selectable for use in generation of the human interaction proof, and

multiple values that individually defines extents to which respective complications of the multiple complications are to be applied to the symbols of the alphabet, wherein a first value of the multiple values defines a fixed extent for application of a first complication of the multiple complications, and wherein a second value of the multiple values defines a random extent for application of a second complication of the multiple complications;

generating a graphical representation of the human interaction proof in accordance with the alphabet and the multiple complications by applying at least the first complication by the fixed extent to a first symbol and applying the second complication by the random extent to a second symbol; and

employing the graphical representation to selectively control access to a service.

2. The one or more computer-readable storage media of claim 1, wherein the multiple complications comprise a distracter, which constitutes a visual element that is to be drawn with at least one of the multiple symbols.

3. The one or more computer-readable storage media of claim 1, wherein the multiple complications comprise a background against which at least one of the multiple symbols is to be drawn.

4. The one or more computer-readable storage media of claim 1, wherein the multiple complications comprise an amount of skew that is to be applied to at least one of the multiple symbols.

5. The one or more computer-readable storage media of claim 1, wherein the multiple complications comprise an amount of blurring that is to be applied to at least one of the multiple symbols.

6. The one or more computer-readable storage media of claim 1, wherein the multiple complications comprises an amount of warping that is to be applied to at least one of the multiple symbols.

7. The one or more computer-readable storage media of claim 1, wherein a first one of the multiple complications is parameterized by a parameter, wherein said parameter specifies a degree to which the first one of the multiple complications is to be applied, wherein the parameter is specified, in the specification, as a Gaussian random variable, including a mean of the Gaussian random variable and a variance or standard deviation of the Gaussian random variable, and wherein generating the graphical representation comprises:

choosing a value of the parameter from a distribution defined by the Gaussian random variable.

8. The one or more computer-readable storage media of claim 1, wherein a first one of the multiple complications is parameterized by a parameter, wherein the parameter specifies a degree to which said first one of the complications is to be applied, wherein the parameter is specified, in the specification, as a uniform random variable, including upper and lower bounds of the uniform random variable, and wherein generating the graphical representation comprises:

choosing a value of the parameter from a distribution defined by the uniform random variable.

9. The one or more computer-readable storage media of claim 1, wherein the multiple complications comprises an amount of intersection between two or more of the multiple symbols in the human interaction proof, and wherein the amount of intersection is specified by a number of pixels of the two or more of the symbols that are to intersect.

10. The one or more computer-readable storage media of claim 1, wherein the multiple complications comprises an animation of one or more of the multiple symbols in the human interaction proof, and wherein the animation specifies a way in which the human interaction proof is to be shown over a duration of time.

11. The one or more computer-readable storage media of claim 1, wherein the received definition further defines:

a container comprising a first one of the multiple symbols and a first one of the multiple complications, wherein the first one of the multiple complications is applied to each symbol in the container.

12. The one or more computer-readable storage media of claim 11, wherein the container further comprises a second one of the multiple symbols that is distinct from the first one of the multiple symbols.

13. A method of generating human interaction proofs, comprising:

receiving a captcha language specification of a human interaction proof scheme, wherein the captcha language specification defines;

an alphabet of possible answers from which multiple symbols of human interaction proofs may be selected,

a set of complications from which multiple complications for the human interaction proofs may be selected, and

multiple values that individually define extents to which respective complications of the multiple complications are to be applied to the symbols of the alphabet, wherein a first value of the multiple values defines a fixed extent for application of a first complication of the multiple complications; and

generating a graphical representation of a first human interaction proof in accordance with the alphabet and the multiple complications by applying at least the first complication by the fixed extent to a first symbol.

14. The method of claim 13, wherein the set of complications includes at least one of a visual element that is to be drawn with one of more selected symbols, a background against which one of more selected symbols is to be drawn, an amount of skew that is to be applied to one of more selected symbols, an amount of blurring that is to be applied to one of more selected symbols, and an amount of warping that is to be applied to one of more selected symbols.

15. The method of claim 13, wherein the captcha language specification further defines a degree to which at least one of the multiple complications is to be applied for the generation of the graphical representation of the first human interaction proof.

16. The method of claim 13, wherein the captcha language specification further defines a number of pixels by which representations of two or more selected symbols are to overlap in the generated graphical representation.

17. The method of claim 13, wherein the method further comprises:

receiving information regarding effectiveness of the captcha language specification; and

in response to the received information, effectuating a change to the set of complications.

18. A system for generating captchas, comprising:

a memory and a processor that are respectively configured to store and execute instructions for;

receiving a captcha language specification of a human interaction proof scheme, wherein the captcha language specification defines;

an alphabet of possible answers from which multiple symbols of human interaction proofs may be selected,

a set of complications from which multiple complications for the human interaction proofs may be selected, and

multiple values that individually define extents to which respective complications of the multiple complications are to be applied to the symbols of the alphabet, wherein a first value of the multiple values defines a fixed extent for application of a first complication of the multiple complications; and

generating a first human interaction proof in accordance with the alphabet and the multiple complications defined by the received captcha language specification, the human interaction proof used during a determination of whether a human is interacting with a service, and the generation of the first human interaction proof including;

applying at least the first complication by the fixed extent to a first symbol.

19. The system of claim 18, wherein the captcha language specification further defines a degree to which at least one of the multiple complications is to be applied during generation of the human interaction proof.

20. The system of claim 18, wherein the memory and the processor are further configured to store and execute instructions for:

receiving information regarding effectiveness of the captcha language specification; and

in response to the received information, effectuating a change to the set of complications.