Automated test generator

• US 6,378,088 B1
• Filed: 07/14/1998
• Issued: 04/23/2002
• Est. Priority Date: 07/14/1998
• Status: Expired due to Term

• Current Assignee: Autodesk, Inc.
• Original Assignee: Discreet Logic, Inc. (Autodesk, Inc.)
• Inventors: Mongan, John Thomas
• Primary Examiner(s): WRIGHT, NORMAN M
• Application Number:
  US09/115,168
• Time in Patent Office: 1,379 Days
• Field of Search: 714/25, 714/38, 714/39, 714/37, 714/47, 714/50, 714/48, 714/33, 714/28, 714/52, 703/22, 717/4
• US Class Current: 714/39
• CPC Class Codes: G06F 11/3684 for test design, e.g. generating new test cases

Abstract

A test generator generates tests by randomly traversing a description of the interface of a program being tested, thereby generating tests that contain randomly selected actions and randomly generated data. When executed, these tests randomly manipulate the program being tested.

Claims

1. An apparatus for automatically generating tests for an application program, comprising:

(a) a computer; and

(b) a test generator, executed by the computer, for;

(1) representing an interface of the application program as a graph; and

(2) automatically generating a test that exercises the application program,

wherein the test is generated by randomly traversing the graph.

2. The apparatus of claim 1 above, wherein the test contains randomly selected manipulations of the interface of the application program and randomly generated data.

3. The apparatus of claim 2 above, wherein the test performs the randomly selected manipulations on the application program when executed.

4. The apparatus of claim 1 above, wherein the test is comprised of one or more statements that perform manipulations of the interface of the application program that are randomly selected by the test generator.

5. The apparatus of claim 4 above, wherein the manipulations are generated using probabilistic techniques.

6. The apparatus of claim 4 above, wherein the manipulations are generated using Monte Carlo statistical techniques.

7. The apparatus of claim 1 above, wherein the test generator traverses the graph using Monte Carlo techniques.

8. The apparatus of claim 1 above, wherein the test generator traverses the graph using probabilistic techniques.

9. The apparatus of claim 1 above, wherein the test generator further comprises means for generating the test using information on the application program stored in one or more files.

10. The apparatus of claim 9 above, wherein the test generator further comprises means for adapting the test generator to different application programs by creating and modifying the application program information stored in the files.

11. The apparatus of claim 9 above, wherein the files comprise description files.

12. The apparatus of claim 11 above, wherein each of the description files are comprised of one or more blocks, each of the blocks represent one or more paths between states in the interface, and each block comprises one or more statements that invoke actions related to transitioning between the states.

13. The apparatus of claim 12 above, wherein the statements are selected from a group that comprise:

(1) statements that explicitly invoke one or more of the functions of the application program, (2) statements that perform one or more actions on the interface of the application program, and (3) statements that supply data to the application program.

14. The apparatus of claim 12 above, wherein the statements explicitly invoke one description from within another description.

15. The apparatus of claim 12 above, wherein the statements indicate mutually exclusive blocks of programming.

16. The apparatus of claim 15 above, wherein the blocks are mutually exclusive and each block includes a relative frequency with which the block should be evaluated by the test generator.

17. The apparatus of claim 16 above, wherein the relative frequency is a number indicating how often the block should be selected for traversal and evaluation by the test generator.

18. The apparatus of claim 16 above, wherein a probability that the block will be selected in a single selection equals the relative frequency divided by a sum of the relative frequencies of all blocks.

19. The apparatus of claim 12 above, wherein the statements identify an independent series of blocks of programming.

20. The apparatus of claim 12 above, wherein the statements are selected from a group comprising:

a statement that identifies a comment,

a statement for explicitly invoking one feature from within another feature,

a statement for identifying a block of programming that is selected from a group comprising;

(1) programming that invokes one or more of the functions of the application program, (2) programming that performs one or more actions on the interface of the application program, and (3) programming that supplies data to the application program,

a statement for declaring a description,

a statement for indicating mutually exclusive blocks,

a statement for accessing a history of values selected by the test generator,

a statement for identifying an independent series of blocks,

a statement for traversing and evaluating a designated set of independent or mutually exclusive blocks a random number of times

a statement for generating a string of randomly chosen length between one and an upper limit,

a statement for storing data in a database,

a statement for retrieving data from a database,

a statement for storing statements in a database,

a statement for storing statements in a database, and

a statement for generating a string that is unique within a test.

21. A method for automatically generating tests for an application program executed by a computer, comprising:

(a) representing an interface of the application program as a graph;

(b) randomly traversing the graph in the memory of the computer; and

(c) automatically generating a test that exercises the application program based on the random traversal of the graph.

22. The method of claim 21 above, wherein the test contains randomly selected manipulations of the interface of the application program and randomly generated data.

23. The method of claim 22 above, wherein the test performs the randomly selected manipulations on the application program when executed.

24. The method of claim 21 above, wherein the test is comprised of one or more statements that perform manipulations of the interface of the application program that are randomly selected by the test generator.

25. The method of claim 24 above, wherein the manipulations are generated using probabilistic techniques.

26. The method of claim 24 above, wherein the manipulations are generated using Monte Carlo statistical techniques.

27. The method of claim 21 above, wherein the test is generated as a representation of a random traversal of the graph using Monte Carlo techniques.

28. The method of claim 21 above, wherein the test is generated as a representation of a random traversal of the graph using probabilistic techniques.

29. The method of claim 21 above, wherein the generating step further comprises generating the test using information on the application program stored in one or more files.

30. The method of claim 29 above, wherein the generating step further comprises adapting the test generator to different application programs by creating and modifying the application program information stored in the files.

31. The method of claim 29 above, wherein the files comprise description files.

32. The method of claim 31 above, wherein each of the description files are comprised of one or more blocks, each of the blocks represent one or more paths between states in the interface, and each block comprises one or more statements that invoke actions related to transitioning between the states.

33. The method of claim 32 above, wherein the statements are selected from a group that comprise:

(1) statements that explicitly invoke one or more of the functions of the application program, (2) statements that perform one or more actions on the interface of the application program, and (3) statements that supply data to the application program.

34. The method of claim 32 above, wherein the statements explicitly invoke one description from within another description.

35. The method of claim 32 above, wherein the statements indicate mutually exclusive blocks of programing.

36. The method of claim 35 above, wherein the blocks are mutually exclusive and each block includes a relative frequency with which the block should be evaluated by the test generator.

37. The method of claim 36 above, wherein the relative frequency is a number indicating how often the block should be selected for traversal and evaluation by the test generator.

38. The method of claim 36 above, wherein a probability that the block will be selected in a single selection equals the relative frequency divided by a sum of the relative frequencies of all blocks.

39. The method of claim 32 above, wherein the statements identify an independent series of blocks of programming.

40. The method of claim 32 above, wherein the statements are selected from a group comprising:

a statement that identifies a comment,

a statement for explicitly invoking one feature from within another feature,

a statement for identifying a block of programming that is selected from a group comprising;

(1) programming that invokes one or more of the functions of the application program, (2) programming that performs one or more actions on the interface of the application program, and (3) programming that supplies data to the application program,

a statement for declaring a description,

a statement for indicating mutually exclusive blocks,

a statement for accessing a history of values selected by the test generator,

a statement for identifying an independent series of blocks,

a statement for traversing and evaluating a designated set of independent or mutually exclusive blocks a random number of times,

a statement for generating a string of randomly chosen length between one and an upper limit,

a statement for storing data in a database,

a statement for retrieving data from a database,

a statement for storing statements in a database,

a statement for storing statements in a database, and

a statement for generating a string that is unique within a test.

41. A program carrier, readable by a computer, embodying one or more instructions executable by the computer to perform method steps for performing a complete, randomly ordered traversal of a cyclic directed graph, the method comprising:

(a) representing an interface of the application program as a cyclic directed graph;

(b) randomly traversing the graph in the memory of the computer; and

(c) automatically generating a test that exercises the application program based on the random traversal of the graph.

42. The program carrier of claim 41 above, wherein the test contains randomly selected manipulations of the interface of the application program and randomly generated data.

43. The program carrier of claim 42 above, wherein the test performs the randomly selected manipulations on the application program when executed.

44. The program carrier of claim 41 above, wherein the test is comprised of one or more statements that perform manipulations of the interface of the application program that are randomly selected by the test generator.

45. The method of claim 44 above, wherein the manipulations are generated using probabilistic techniques.

46. The method of claim 44 above, wherein the manipulations are generated using Monte Carlo statistical techniques.

47. The program carrier of claim 41 above, wherein the test is generated as a representation of a random traversal of the graph using Monte Carlo techniques.

48. The program carrier of claim 41 above, wherein the test is generated as a representation of a random traversal of the graph using probabilistic techniques.

49. The program carrier of claim 41 above, wherein the generating step further comprises generating the test using information on the application program stored in one or more files.

50. The method of claim 49 above, wherein the generating step further comprises adapting the test generator to different application programs by creating and modifying the application program information stored in the files.

51. The method of claim 49 above, wherein the files comprise description files.

52. The method of claim 51 above, wherein each of the description files are comprised of one or more blocks, each of the blocks represent one or more paths between states in the interface, and each block comprises one or more statements that invoke actions related to transitioning between the states.

53. The method of claim 52 above, wherein the statements are selected from a group that comprise:

(1) statements that explicitly invoke one or more of the functions of the application program, (2) statements that perform one or more actions on the interface of the application program, and (3) statements that supply data to the application program.

54. The method of claim 53 above, wherein the statements identify an independent series of blocks of programming.

55. The method of claim 53 above, wherein the statements are selected from a group comprising:

a statement that identifies a comment,

a statement for explicitly invoking one feature from within another feature,

a statement for identifying a block of programming that is selected from a group comprising;

(1) programming that invokes one or more of the functions of the application program, (2) programming that performs one or more actions on the interface of the application program, and (3) programming that supplies data to the application program,

a statement for declaring a description,

a statement for indicating mutually exclusive blocks,

a statement for accessing a history of values selected by the test generator,

a statement for identifying an independent series of blocks,

a statement for traversing and evaluating a designated set of independent or mutually exclusive blocks a random number of times,

a statement for generating a string of randomly chosen length between one and an upper limit,

a statement for storing data in a database,

a statement for retrieving data from a database,

a statement for storing statements in a database,

a statement for storing statements in a database, and

a statement for generating a string that is unique within a test.

56. The method of claim 52 above, wherein the statements explicitly invoke one description from within another description.

57. The method of claim 52 above, wherein the statements indicate mutually exclusive blocks of programming.

58. The method of claim 57 above, wherein the blocks are mutually exclusive and each block includes a relative frequency with which the block should be evaluated by the test generator.

59. The method of claim 58 above, wherein the relative frequency is a number indicating how often the block should be selected for traversal and evaluation by the test generator.

60. The method of claim 58 above, wherein a probability that the block will be selected in a single selection equals the relative frequency divided by a sum of the relative frequencies of all