Automatic software testing tool

• US 5,754,760 A
• Filed: 05/30/1996
• Issued: 05/19/1998
• Est. Priority Date: 05/30/1996
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: Integrity QA Software Incorporated
• Inventors: Warfield, Robert W.
• Primary Examiner(s): Decady, Albert
• Application Number:
  US08/655,149
• Time in Patent Office: 719 Days
• Field of Search: 395/183.13, 395/183.14, 395/702, 395/704, 395/183.01, 395/183.09, 395/183.08, 395/183.1, 395/183.11, 395/701, 364/267.19, 364/225.5
• US Class Current: 714/38.1
• CPC Class Codes: G06F 11/3676 for coverage analysis

Abstract

A method of testing a software module using a genetic algorithm to generate a best test script is provided. The software module has a number of possible states. A set of state machines is created which represent a definition for either a user interface or an application program interface (API) of the software module in terms of the possible states. From the state machines, a set of test cases is automatically generated, such that each test case consists of code for manipulating the user interface or API. A genetic algorithm creates populations of test scripts from the test cases, in which each test script includes a number of test cases. Each test script from each successive generation of test scripts is executed by applying the script as input to the software module. A code coverage analyzer provides a measure of code coverage to the genetic algorithm for each test script. The genetic algorithm uses the measure of code coverage as a fitness value in generating future populations of test scripts and in determining a best script.

Claims

1. A method of testing machine-executable code, the code having a plurality of possible states, the method comprising:

generating a first set of input operations based on a definition of the states, each input operation including machine-executable instructions for causing the code to enter at least one of the states;

causing the code to be executed in response to the first set of input operations;

assigning a fitness value to each input operation based on a result of causing the code to be executed; and

generating a second set of input operations from the first set of input operations based on the fitness values.

2. The method of claim 1, wherein the steps of generating the first set and generating the second set are performed according to a genetic algorithm.

3. The method of claim 2, wherein each of the input operations comprises a test script for testing the code.

4. The method of claim 1, wherein the code includes instructions for providing a user interface when executed by a processor, and wherein the step of generating a first set of input operations comprises the step of generating a set of operations for manipulating the user interface.

5. The method of claim 1, wherein the code includes an application program interface (API), and wherein the step of generating a first set of input operations comprises the step of generating a set of operations for manipulating the API.

6. The method of claim 1, wherein the fitness value corresponds to a measure of code coverage.

7. The method of claim 1, wherein the fitness value corresponds to a measure of data flow coverage.

8. A method of testing a software module including a plurality of machine-executable instructions, the software module including instructions for receiving a plurality of inputs when executed by a processor, the method comprising:

(a) inputting a definition of the instructions for receiving a plurality of inputs, the definition corresponding to a plurality of possible states of the software;

(b) generating a plurality of test cases from the definition, each test case including machine-executable instructions for producing at least one of the states in response to a test input;

(c) generating a first population of scripts, such that each script includes at least one of the test cases;

(d) causing the software module to be executed in response to each script;

(e) assigning a fitness value to each script based on execution of the software module according to the causing step; and

(f) generating a new population of scripts based on the first population and the fitness values.

9. The method of claim 8, wherein steps (c) and (f) are performed according to a genetic algorithm.

10. The method of claim 8, wherein the step of generating a new population of scripts comprises the step of automatically generating a modified version of at least one of the scripts of the first population of scripts.

11. The method of claim 8, wherein the method comprises the step of performing a plurality of iterations of steps (d), (e), and (f) to generate a best script.

12. The method of claim 8, wherein the instructions for receiving a plurality of inputs comprises instructions for providing an application program interface (API) when executed by a processor.

13. The method of claim 8, wherein the step of inputting the definition of the instructions for receiving a plurality of inputs comprises the step of inputting a plurality of state machine definitions.

14. The method of claim 13 wherein the instructions for receiving a plurality of inputs comprises machine-executable instructions for providing a user interface.

15. The method of claim 8, wherein the step of generating a fitness value for each script comprises the step of generating, for each script, a code coverage value, each code coverage value corresponding to a number of the instructions of the software module that were executed during execution of the software module.

16. The method of claim 8, wherein the step of causing the software module to be executed comprises the step of causing the software module to be executed over a data set;

and

wherein the step of generating a fitness value for each script comprises the step of generating, for each script, a data flow coverage value, each data flow coverage value indicating a portion of the data set that was executed during execution of the software module.

17. The method of claim 8, wherein the software module is for implementation in a computer network including a client and a server, and

wherein the step of generating a fitness value for each script comprises the step of generating a measure of a load placed upon the server for each script.

18. The method of claim 8, wherein the method further comprises the steps of:

modifying at least one of the instructions of the software module to cause a plurality of errors during execution of the software module; and

generating the fitness value for each script based on the number of errors identified as a result of the software module being executed.

19. The method of claim 8, further comprising the step of automatically modifying at least one of the instructions of the software module to test a predetermined condition during execution of the software module.

20. A method of testing a software module, the software module having an input interface, the method comprising:

(a) inputting a definition of the input interface in terms of a plurality of state machines, each state machine having a plurality of logically interconnected states;

(b) generating from the state machines a plurality of test cases, wherein each test case includes a set of instructions representing a chronological sequence of states in one of the state machines and at least one test input for causing a transition between two states in the sequence;

(c) generating a first population of scripts, each script including a plurality of the test cases;

(d) causing the software application to be executed in response to each script of the first population;

(e) generating a fitness value for each script based on a result of the software module being executed in response to said script;

(f) ranking the scripts based on the fitness values;

(g) generating a new population of scripts based on a result of the ranking step; and

(h) causing the software application to be executed in response to each script of the new population.

21. The method of claim 20, wherein the input interface is a user interface.

22. The method of claim 20, wherein the input interface is an application program interface (API).

23. The method of claim 20, further comprising the step of iterating steps (d) through (g) to generate a most-fit script.

24. The method of claim 20, further comprising the step of identifying a most-fit script from the new population of scripts.

25. The method of claim 20, wherein the software module includes a plurality of machine-executable instructions, and wherein each fitness value corresponds to a number of the instructions of the software application that were executed in response to the corresponding script.

26. The method of claim 20, wherein the step of generating a new population of scripts based on a result of the ranking step is performed using a genetic algorithm.

27. The method of claim 20, wherein the step of generating a fitness value for each script comprises the step of generating, for each script, a code coverage value.

28. The method of claim 20, wherein the step of causing the software module to be executed comprises the step of causing the software module to be executed over a data set;

and

wherein the step of generating a fitness value for each script comprises the step of generating, for each script, a data flow coverage value.

29. The method of claim 20, wherein the software module is for implementation in a computer network including a client and a server, and

wherein the step of generating a fitness value for each script comprises the step of generating a measure of a load placed upon the server for each script.

30. The method of claim 20, wherein the method further comprises the steps of:

modifying at least one of the instructions of the software module to cause a plurality of errors during execution of the software module; and

generating the fitness value for each script based on the number of errors identified as a result of the software module being executed.

31. The method of claim 20, further comprising the step of automatically modifying at least one of the instructions of the software module to test a predetermined condition during execution of the software module.

32. A program storage device readable by a machine, the program storage device tangibly embodying a program of instructions executable by the machine to perform steps for testing a test software module, the steps comprising:

building a dynamically generated test script from a population of test cases;

inputting the test script to the test software module for execution by the test software module;

generating a fitness score corresponding to the test script by comparing a result of execution of the test script with a predefined fitness attribute; and

using the fitness score to modify the test script for a subsequent iteration of the inputting step.

33. The program storage device of claim 32, wherein the steps of building a dynamically generated test script, generating a fitness score, and using the fitness score, are performed using a genetic algorithm.

34. The program storage device of claim 32, wherein the population of test cases includes operators for manipulating a user interface of the test software module.

35. The program storage device of claim 32, wherein the population of test cases includes operators for manipulating an application program interface (API) of the test software module.

36. The program storage device of claim 32, wherein the predefined fitness attribute comprises a code coverage attribute.

37. The program storage device of claim 32, wherein the predefined fitness attribute corresponds to a measure of data flow coverage.

38. The program storage device of claim 32, wherein each of the input operations comprises a test script for testing the software module.

39. A program storage device readable by a machine, the program storage device tangibly embodying a program of instructions executable by the machine to perform steps for testing software, the software including code for receiving a plurality of inputs when executed by a processor, the steps comprising:

(a) inputting a definition of the code for receiving the plurality of inputs, the definition corresponding to a plurality of possible states of the software;

(b) generating a plurality of test cases from the definition, each test case including machine-executable instructions for producing at least one of the states in response to a test input;

(c) using a genetic algorithm to generate a population of scripts for testing the software, each script including at least one of the test cases;

(d) causing the software to be executed in response to the scripts of the first population of scripts;

(e) generating a fitness value for each script based on execution of the software; and

(e) using the genetic algorithm to generate a second population of scripts based on the fitness values.

40. The program storage device of claim 39, wherein the code for receiving a plurality of inputs comprises an application program interface (API).

41. The program storage device of claim 39, wherein the code for receiving a plurality of inputs comprises code for providing a user interface when executed by a processor.

42. The program storage device of claim 39, wherein the fitness value corresponds to a code coverage attribute.

43. The program storage device of claim 39, wherein the fitness value corresponds to a data flow coverage attribute.

44. A device for testing a software module, the software module including code for providing an input interface when executed by a processor, the software module having a plurality of possible states, the device comprising:

a test case generator coupled to receive a definition of the states, the test case generator generating a plurality of test cases based on the definition of the states, each test case including instructions for causing the software module to enter at least one of the states;

a test script generator coupled to receive the test cases, the test script generator dynamically generating a first population of scripts, each script of the first population of scripts including at least one of the test cases, the script generator coupled to provide each of the test scripts to the software module as input to the input interface during execution by the processor;

a test script evaluator coupled to receive output from the software module during execution by the processor, the script generator generating a plurality of fitness values in response to the software module being executed, one fitness value for each script, the test script evaluator providing the fitness values to the test script generator; and

wherein the test script generator further dynamically generates at least one new population of scripts based on a previous population of scripts and a plurality of fitness values associated with the previous population of scripts.

45. The device of claim 44, wherein the test script generator further determines a best script.

46. The device of claim 44, wherein the test script generator comprises a genetic algorithm.

47. The device of claim 44, wherein the input interface is an application program interface (API).

48. The device of claim 44, wherein the fitness value corresponds to a code coverage attribute.