Automatic construction of human interaction proof engines

• US 8,978,144 B2
• Filed: 05/19/2014
• Issued: 03/10/2015
• 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:
  US14/281,316
• Publication Number:
  US 20140259104A1
• Time in Patent Office: 295 Days
• Field of Search: 726/25
• US Class Current: 726/25
• 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. A method of generating a first human interaction proof engine, the method comprising:

using a processor to perform acts comprising;

selecting a set of human interaction proof engines from a plurality of second human interaction proof engines, wherein said second human interaction proof engines do not include said first human interaction proof engine, wherein said selecting is based on measures of quality of said second human interaction proof engines;

combining features of pairs of human interaction proof engines in said set of human interaction proof engines to produce a first set of resulting human interaction proof engines; and

mutating features of said resulting human interaction proof engines to produce a second set of resulting human interaction proof engines.

2. The method of claim 1, wherein said acts further comprise:

deploying one engine from said second set of resulting human interaction proof engines to gate access to a service.

3. The method of claim 1, wherein said features comprise distracters, backgrounds, or distortions.

4. The method of claim 1, wherein said mutating comprises:

changing a parameter of a human interaction proof engine in said first set of resulting human interaction proof engines.

5. The method of claim 4, further comprising:

determining, with a probability between zero and one hundred percent, exclusive, whether to change a parameter.

6. An automated method of generating a human interaction proof (HIP) scheme, comprising:

selecting a starting set of HIP schemes from a 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.

7. The automated method of claim 6, wherein combining aspects from each of the at least two HIP schemes includes:

combining features selected from each of the at least two HIP schemes.

8. The automated method of claim 6, wherein mutating the combined HIP scheme includes:

changing a parameter of the combined HIP scheme.

9. The automated method of claim 6, wherein the output HIP scheme defines:

an alphabet from which multiple symbols are to be selected as answers to a HIP;

multiple complications that are selectable for use in generation of the HIP; and

multiple values that define extents to which respective complications of the multiple complications are to be applied to the symbols of the alphabet.

10. The automated method of claim 6, wherein the output HIP scheme is in a HIP specification language.

11. The automated method of claim 6, wherein outputting the output HIP scheme includes:

deploying the output HIP scheme to gate access to a service.

12. The automated method of claim 6, wherein mutating the combined HIP scheme includes:

adding and/or dropping a feature of the combined HIP scheme.

13. The automated method of claim 12, wherein the feature includes a distracter, a background, and/or a distortion.

14. A computing device for generating captcha specification languages, comprising:

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

select a set of starting human interaction proof (HIP) schemes from a plurality of HIP schemes based on measures of quality of individual HIP schemes of the plurality of HIP schemes;

produce a combined HIP scheme based on at least two starting HIP schemes from the selected set of HIP schemes;

generate an output HIP scheme via mutation of the combined HIP scheme; and

output the output HIP scheme.

15. The computing device of claim 14, wherein each of the plurality of HIP schemes specifies:

an alphabet from which multiple symbols are to be selected as answers to a HIP generated by that HIP scheme;

multiple complications that are selectable for use by that HIP scheme in generation of the HIP; and

multiple values that define how respective complications of the multiple complications are to be applied to the symbols of the alphabet by that HIP scheme.

16. The computing device of claim 14, wherein output of the output HIP scheme includes:

use of the output HIP scheme to gate access to a service.

17. The computing device of claim 14, wherein the mutation of the combined HIP scheme includes:

change to a parameter of the combined HIP scheme.

18. The computing device of claim 14, wherein production of the combined HIP scheme includes:

selecting aspects from each of the starting HIP schemes for use in the combined HIP scheme.

19. The computing device of claim 18, wherein the aspects from each of the starting HIP schemes include distracters, wherein the distractors are visual elements that are to be generated in conjunction with at least one of multiple symbols.

20. The computing device of claim 18, wherein the aspects from each of the starting HIP schemes 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.