Adaptive problem solving method and apparatus utilizing evolutionary computation techniques

• US 6,282,527 B1
• Filed: 06/30/1998
• Issued: 08/28/2001
• Est. Priority Date: 06/27/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Sikchi, Prakash, Gounares, Alexander
• Primary Examiner(s): Powell, Mark
• Assistant Examiner(s): Holmes, Michael B.
• Application Number:
  US09/107,212
• Time in Patent Office: 1,155 Days
• Field of Search: 706/13
• US Class Current: 706/13
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

A system for adaptively solving sequential problems in a target system utilizing evolutionary computation techniques and in particular genetic algorithms and modified genetic algorithms. Stimuli to a target system such as a software system are represented as actions. A single sequence of actions is a chromosome. Chromosomes are generated by a goal-seeking algorithm that uses a hint database and recursion to intelligently and efficiently generate a robust chromosome population. The chromosomes are applied to the target system one action at a time and the change in properties of the target system is measured after each action is applied. A fitness rating is calculated for each chromosome based on the property changes produced in the target system by the chromosome. The fitness rating calculation is defined so that successive generations of chromosomes will converge upon desired characteristics. For example, desired characteristics for a software testing application are defect discovery and code coverage. Chromosomes with high fitness ratings are selected as parent chromosomes and various techniques are used to mate the parent chromosomes to produce children chromosomes. Children chromosomes with high fitness ratings are entered into the chromosome population. Defects in a target software system are minimized by evolving ever-shorter chromosomes that produce the same defect. Defect discovery rate, or any other desired characteristic, is thereby maximized.

Claims

1. A method of operating a computer system to generate chromosomes for use in an evolutionary computation system that tests a software program, the method comprising:

analyzing the software program to identify methods for objects in the software program;

determining parameters of application programming interfaces for the methods;

calling the application programming interfaces using the parameters; and

assembling the chromosomes from the application programming interfaces based on results from the application programming interface calls.

2. The method of claim 1 wherein analyzing the software program to determine the methods for the objects in the software program comprises using Java reflection.

3. The method of claim 1 wherein determining the parameters comprises retrieving hint information from a hint database, wherein the hint information identifies values for use as the parameters.

4. The method of claim 3 further comprising using reflection to associate the hint information with the application programming interfaces.

5. The method of claim 1 wherein determining the parameters comprises:

retrieving hint information from a hint database; and

recursively processing the hint information to identify values for use as the parameters.

6. The method of claim 1 further comprising:

retrieving hint information from a hint database; and

identifying a sequence of the application programming interfaces to call based on the hint information.

7. The method of claim 1 further comprising:

retrieving hint information from a hint database; and

evaluating the results from the application programming interface calls based on the hint information.

8. The method of claim 7 wherein evaluating the results further comprises identifying defects and the software program based on hint information.

9. The method of claim 1 further comprising determining targets of application programming interfaces for the methods.

10. A method of operating computer system to test a software program, the method comprising:

inputting chromosomes to the software program;

receiving results from the software program based on the chromosomes; and

evolving the chromosomes using the results to minimize select chromosomes that cause defects in the software program.

11. The method of claim 10 further comprising generating the chromosomes input to the software program.

12. The method of claim 11 further comprising calling application program interfaces for methods of objects in the software program.

13. The method of claim 12 wherein generating the chromosomes further comprises generating the chromosomes from the application programming interfaces based on results from the application programming interface calls.

14. The method of claim 13 wherein generating the chromosomes further comprises generating the chromosomes from the application programming interfaces based on results from the application programming interface calls that cause defects in the software program.

15. The method of claim 10 wherein evolving the chromosomes further comprises using crossover.

16. A memory device storing computer-executable instructions, wherein the instructions are configured to direct a computer system to generate chromosomes for use in an evolutionary computation system that tests a software program, the product comprising:

population generation instructions operational when executed to direct the computer system to analyze the software program and determine methods for objects in the software program, to determine parameters of application programming interfaces for the methods, to call the application programming interfaces using the parameters, and to assemble the chromosomes from the application programming interfaces based on results from the application programming interface calls; and

a software storage medium operational to store the population generation instructions.

17. The memory device of claim 16 wherein the population generation instructions are further operational when executed to direct the computer system to analyze the software program and determine the methods for the objects in the software program using Java reflection.

18. The memory device of claim 16 wherein the population generation instructions are further operational when executed to direct the computer system to retrieve information that identifies values for use as the parameters.

19. The memory device of claim 18 wherein the population generation instructions are further operational when executed to direct the computer system to use reflection to associate the information with the application programming interfaces.

20. The memory device of claim 16 wherein the population generation instructions are further operational when executed to direct the computer system to recursively process information to identify values for use as the parameters.

21. The memory device of claim 16 wherein the population generation instructions are further operational when executed to direct the computer system to identify a sequence of the application programming interfaces to call.

22. The memory device of claim 16 wherein the population generation instructions are further operational when executed to direct the computer system to evaluate results from the application programming interface calls to identify defects in the software program.

23. The memory device of claim 16 wherein the population generation instructions are further operational when executed to direct the computer system to determine targets of the application programming interfaces for the methods.

24. An evolutionary computation system for testing a software program, the evolutionary computation system comprising:

a computer system;

instructions stored in the computer system that are operational when executed to direct the computer system to input chromosomes to the software program, to receive results from the software program based on the chromosomes, and to evolve the chromosomes using the results to minimize select chromosomes that cause defects in the software program, and wherein the computer system is operational to store and execute the instructions.

25. The evolutionary computation system of claim 24 wherein the instructions are further operational when executed to direct the computer system to generate the chromosomes input to the software program.

26. The evolutionary computation system of claim 25 wherein the instructions are further operational when executed to direct the computer system to call application program interfaces for methods of objects in the software program.

27. The evolutionary computation system of claim 26 wherein the instructions are further operational when executed to direct the computer system to generate the chromosomes from the application programming interfaces based on results from the application programming interface calls.

28. The evolutionary computation system of claim 27 wherein the instructions are further operational when executed to direct the computer system to generate the chromosomes from the application programming interfaces based on results from the application programming interface calls that cause defects in the software program.

29. The evolutionary computation system of claim 24 wherein the instructions are further operational when executed to direct the computer system to evolve the chromosomes using crossover.