US5754760A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Automatic software testing tool
Assignee: International Business Machines Corp
•
Filing: 1996-05-30
•
Granted: 1998-05-19
•
Expires: 2016-05-30
Abstract
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.\!
Inventors
- 👤 Robert W. Warfield
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 08:55
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/36; G06F11/3668; G06F11/3672; G06F11/3676
Claims Analysis
Total Claims: 54
Claim 1
Independent Claim
103 words
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.
Claim 2
Independent Claim
103 words
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.
Claim 3
Dependent Claim
25 words
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.
Claim 4
Dependent Claim
19 words
The method of claim 2, wherein each of the input operations comprises a test script for testing the code.
Claim 5
Dependent Claim
46 words
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.
Claim 6
Dependent Claim
39 words
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.
Claim 7
Dependent Claim
16 words
The method of claim 1, wherein the fitness value corresponds to a measure of code coverage.
Claim 8
Dependent Claim
17 words
The method of claim 1, wherein the fitness value corresponds to a measure of data flow coverage.
Claim 9
Independent Claim
156 words
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.
Claim 10
Independent Claim
156 words
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.
Claim 11
Dependent Claim
17 words
The method of claim 8, wherein steps (c) and (f) are performed according to a genetic algorithm.
Claim 12
Dependent Claim
37 words
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.
Claim 13
Dependent Claim
28 words
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.
Claim 14
Dependent Claim
28 words
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.
Claim 15
Dependent Claim
32 words
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.
Claim 16
Dependent Claim
22 words
The method of claim 13 wherein the instructions for receiving a plurality of inputs comprises machine-executable instructions for providing a user interface.
Claim 17
Dependent Claim
52 words
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.
Claim 18
Dependent Claim
77 words
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.
Claim 19
Dependent Claim
51 words
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.
Claim 20
Dependent Claim
60 words
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.
Claim 21
Dependent Claim
33 words
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.
Claim 22
Independent Claim
189 words
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.
Claim 23
Independent Claim
189 words
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.
Claim 24
Dependent Claim
13 words
The method of claim 20, wherein the input interface is a user interface.
Claim 25
Dependent Claim
15 words
The method of claim 20, wherein the input interface is an application program interface (API).
Claim 26
Dependent Claim
20 words
The method of claim 20, further comprising the step of iterating steps (d) through (g) to generate a most-fit script.
Claim 27
Dependent Claim
20 words
The method of claim 20, further comprising the step of identifying a most-fit script from the new population of scripts.
Claim 28
Dependent Claim
40 words
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.
Claim 29
Dependent Claim
29 words
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.
Claim 30
Dependent Claim
28 words
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.
Claim 31
Dependent Claim
56 words
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.
Claim 32
Dependent Claim
51 words
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.
Claim 33
Dependent Claim
60 words
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.
Claim 34
Dependent Claim
33 words
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.
Claim 35
Dependent Claim
104 words
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.
Claim 36
Dependent Claim
104 words
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.
Claim 37
Dependent Claim
32 words
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.
Claim 38
Dependent Claim
25 words
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.
Claim 39
Dependent Claim
27 words
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.
Claim 40
Dependent Claim
17 words
The program storage device of claim 32, wherein the predefined fitness attribute comprises a code coverage attribute.
Claim 41
Dependent Claim
20 words
The program storage device of claim 32, wherein the predefined fitness attribute corresponds to a measure of data flow coverage.
Claim 42
Dependent Claim
22 words
The program storage device of claim 32, wherein each of the input operations comprises a test script for testing the software module.
Claim 43
Dependent Claim
176 words
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.
Claim 44
Dependent Claim
176 words
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.
Claim 45
Dependent Claim
22 words
The program storage device of claim 39, wherein the code for receiving a plurality of inputs comprises an application program interface (API).
Claim 46
Dependent Claim
28 words
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.
Claim 47
Dependent Claim
17 words
The program storage device of claim 39, wherein the fitness value corresponds to a code coverage attribute.
Claim 48
Dependent Claim
18 words
The program storage device of claim 39, wherein the fitness value corresponds to a data flow coverage attribute.
Claim 49
Independent Claim
233 words
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.
Claim 50
Independent Claim
233 words
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.
Claim 51
Dependent Claim
15 words
The device of claim 44, wherein the test script generator further determines a best script.
Claim 52
Dependent Claim
14 words
The device of claim 44, wherein the test script generator comprises a genetic algorithm.
Claim 53
Dependent Claim
15 words
The device of claim 44, wherein the input interface is an application program interface (API).
Claim 54
Dependent Claim
15 words
The device of claim 44, wherein the fitness value corresponds to a code coverage attribute.
References Cited (Backward Citations)
US4694411A
Cited
US4809202A
Cited
US5045994A
Cited
US4972334A
Cited
US5222192A
Cited
US5255345A
Cited
US5038307A
Cited
US5163016A
Cited
US5291427A
Cited
US5375195A
Cited
US5475843A
Cited
US5513315A
Cited
US5490249A
Cited
US5394347A
Cited
US5481716A
Cited
US5548718A
Cited
US5500941A
Cited
US5539680A
Cited
US5455938A
Cited
US5590321A
Cited
US5542043A
Cited
US5572668A
Cited
US5561762A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-05-18 | 2001-11-17 | 2002-05-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-05-18 | 2005-11-17 | 2006-05-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-05-18 | 2009-11-17 | 2010-05-19 | $7700.00 | Window Closed / Lapsed |