Program boosting including using crowdsourcing for correctness

• US 9,753,696 B2
• Filed: 03/14/2014
• Issued: 09/05/2017
• Est. Priority Date: 03/14/2014
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Livshits, Benjamin, Cochran, Robert A.
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): Nilsson, Eric
• Application Number:
  US14/212,462
• Publication Number:
  US 20150262079A1
• Time in Patent Office: 1,271 Days
• Field of Search: None
• CPC Class Codes: G06F 8/20 Software design
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

The subject disclosure is directed towards crowd-based approach to boosting the correctness of a computer program. Results from candidate programs obtained from a first crowd and which may be blended with one another into synthesized programs are sent to a second crowd for evaluation. Based upon the results, a training set evolves and programs are filtered based upon fitness. The process of blending and fitness evaluation with an evolved training set may be iteratively repeated to find a most fit program.

Claims

1. In a computing environment, a method performed by at least a processing unit, the method comprising;

obtaining candidate programs related to a programming task;

synthesizing the candidate programs to produce blended programs;

providing positive examples and negative examples from the blended programs to crowd Sources;

obtaining a training set and feedback from the crowd sources;

determining fitness measures for the blended programs based on the training set and the feedback, the fitness measures including calculating an accuracy of the training set, the accuracy of the training set being based on a first symbolic finite automaton for the positive examples, a second finite automaton for the negative examples and a third symbolic finite automaton for the blended programs; and

selecting a most fit blended program from the blended programs based upon the fitness measures and using the selected most fit blended program for the programming task.

2. The method of claim 1, wherein the method further comprises evolving a next training set by combining data of the training set and feedback-related data into the next training set.

3. The method of claim 2, wherein combining the data of the training set and the feedback-related data into the next training set comprises weighing the data of the training set differently from the feedback-related data.

4. The method of claim 1, wherein obtaining the candidate programs comprises receiving the candidate programs from a first crowd source that is different from the crowd sources from which the feedback is obtained.

5. The method of claim 1, wherein obtaining the candidate programs comprises receiving programs corresponding to regular expressions.

6. The method of claim 1, wherein synthesizing the candidate programs comprises using a crossover function.

7. The method of claim 6, wherein using the crossover function comprises using a first component of a first program in a second program and using a second component of the second program in the first program.

8. The method of claim 7, further comprising detecting a set of single-entry, single-exit components as an independent part of a program and using the independent part as the first component.

9. The method of claim 1, wherein the accuracy of the training set is computed by performing one or more operations on a first intersection between the first symbolic finite automaton and the third symbolic finite automaton and a second intersection between the second symbolic finite automaton and the third symbolic finite automaton and values of the first symbolic finite automaton and the second symbolic finite automaton.

10. The method of claim 1, wherein synthesizing the candidate programs comprises using a mutation function.

11. The method of claim 1, wherein obtaining the candidate programs comprises receiving programs corresponding to regular expressions, in which the regular expressions are represented with symbolic finite automata.

12. The method of claim 1, wherein providing the positive examples and the negative examples comprises generating strings.

13. The method of claim 12, wherein generating the strings comprises using at least one of:

string edit distance, character insertion, character deletion or character replacement.

14. In a computing environment, a system comprising;

memory configured with a program selection mechanism;

at least one processor coupled to the memory to execute the program selection mechanism, and

the program selection mechanism configured to;

a) obtain candidate programs related to a programming task from a first crowd source;

b) generate results from blended programs synthesized from the candidate programs;

c) provide information corresponding to the results to a second crowd source;

d) obtain training data and feedback from the second crowd source;

e) process the feedback from the second crowd source into evaluation data;

f) determine fitness data for the blended programs based at least in part on the evaluation data, wherein determining fitness data includes calculating an accuracy of the training data, wherein the accuracy of the training data is based on a first symbolic finite automaton for positive examples in the training data, a second finite automaton for negative examples in the training data, and a third symbolic finite automaton for the blended programs; and

g) output a most fit blended program for the programming task from amongst the blended programs based upon the fitness data.

15. The system of claim 14, wherein the program selection mechanism is further configured to iteratively select and further blend programs based upon the fitness data before outputting the at least one blended program.

16. One or more machine-readable storage media or hardware logic having machine-executable instructions, which when executed by one or more processors, perform operations comprising:

a) blending a set of programs obtained from a first crowd source into synthesized programs, the set of programs relating to a programming task;

b) generating results from the synthesized programs using training data in a current state;

c) providing information corresponding to the results to a second crowd source;

d) processing feedback from the second crowd source to evolve the training data into a new current state;

e) determining fitness data for each of the synthesized programs, and associating each synthesized program with its fitness data, wherein determining the fitness data includes calculating an accuracy of the training data that is in the new current state, wherein the accuracy of the training data in the new current state is based on a first symbolic finite automaton for positive examples in the training data in the new current state, a second finite automaton for negative examples in the training data in the new current state, and a third symbolic finite automaton for the synthesized programs;

f) filtering the synthesized programs based on each synthesized program'"'"'s associated fitness data to obtain a new set of programs;

g) returning to operation a) until the fitness data associated with a program achieves a desired fitness level or another stopping criterion is met; and

h) selecting a program based upon the fitness data associated with that program for the programming task.

17. The one or more machine-readable storage media or hardware logic of claim 16, having further instructions comprising obtaining programs corresponding to regular expressions as at least part of the set of programs.

18. The one or more machine-readable storage media or hardware logic of claim 17, wherein blending the set of programs into the synthesized programs comprises using a crossover function or a mutation function, or both a crossover function and a mutation function.

19. The one or more machine-readable storage media or hardware logic of claim 18, wherein using the crossover function comprises using a first component of a first program in a second program and using a second component of the second program in the first program.

20. The one or more machine-readable storage media or hardware logic of claim 16, wherein the accuracy of the initial training set in the new current state is computed by performing one or more operations on a first intersection between the first symbolic finite automaton and the third symbolic finite automaton and a second intersection between the second symbolic finite automaton and the third symbolic finite automaton and values of the first symbolic finite automaton and the second symbolic finite automaton.