Complete, randomly ordered traversal of cyclic directed graphs6189116Abstract A test generator creates a cyclic directed graph representation of the interface of a program being tested and then generates tests from this representation. In generating the tests, the test generator iteratively selects traversal paths through the cyclic directed graph that result in traversal of every edge in the graph in a random order with a minimum number of iterations. The resulting tests contain randomly selected actions and randomly generated data, and thus when executed, these tests randomly manipulate the program being tested. Claims What is claimed is: Description CROSS-REFERENCE TO RELATED APPLICATIONS
Circle 5 circle.dsc
Pline 3 pline.dsc
The feature name must exactly match the feature name in the DESCRIBE block of the description file 126. The relative frequency is a number indicating how often the feature should be selected for evaluation. The higher the number, the more often the feature will be selected. The probability that a given feature will be selected in a single selection equals the feature's relative frequency divided by the sum of the relative frequencies of all the features. Frequencies of 0 are allowed; a zero frequency description will never be used unless it is directly CALLed by another (non-zero frequency) description. Paths are relative to the location of the map file 128. If the description file 126 is in the same directory as the map file 128, the path is optional. Blank lines and comment lines are allowed. Comment lines must begin with a double forward slash. Common Directory and Description File Scanning The map file 128 is the only way to indicate the existence of feature descriptions with non-zero frequencies, but there are two other ways for the test generator 118 to locate zero frequency feature descriptions. Zero frequency feature descriptions can be used like subroutines to facilitate code reuse and allow a modular structure for large feature descriptions. Every description file 126 that is listed in the map file 128 is scanned for other feature descriptions that may not have been explicitly listed in the map file 128. This means that a feature description can CALL any other feature description that is in the same file, regardless of whether the CALLed feature description is listed in the map file 128. This is useful for subroutine-like feature descriptions. Every file and subdirectory in the directory specified by the $CommonDir item of the configuration file 132 is automatically scanned for feature descriptions. Any feature description in this tree can be CALLed regardless of whether or not it is listed in the map file 128. This is helpful for developing libraries of shared feature descriptions. Include Files It may be necessary to declare variables or subroutines in the underlying scripting language to assist feature descriptions. Since a feature description may be called more than once in a given test 122, it can be difficult or impossible to properly declare these from inside the description file 126. The solution is to use include files 130. Whenever the test generator 118 uses a description file 126, it looks for an include file 130 with the same base name but an extension specified by $IncludeFileExtension. It then concatenates these files 126 and 130 to form a single file, named in $IncludeFilename, which can be included by the generated test 122. This is usually done automatically with a line in the $FilePre section of the configuration file 132, which is described in more detail below. Note that include files 130 are concatenated by the test generator 118, but not processed, so keywords cannot be used in them. The test generator 118 functionality is available only in description files 126. Also, beware of using any random functions the underlying scripting language may provide. Such functions may return different values each time a test 122 is run, making it difficult to reproduce failures. All randomness should come from the test generator 118, which produces different values each time a test 122 is generated, but hard-codes these values into the generated test 122 so they are the same for each run. Description File Examples The following provides an example of how description files 126 are created for the test generator 118. This example illustrates the creation of a simple description of the portions of the circle command in Autodesk's AutoCAD.TM. using the 4Test.TM. language employed by Segue's QA Partner.TM. as the underlying scripting language. As described above, the first step is to add a line to the map file 128, so that the test generator 118 can find the new feature description. The line added might look like the following:
Circle 10 circle.dsc
The next step is to create the description file 126 using a text editor (description files 126 are plain-text files). The filename for the description file 126 must match the one entered in the map file 128, which in this example is "circle.dsc" as indicated above. At minimum, the description file 126 has to contain the following lines: DESCRIBE Circle { } The DESCRIBE keyword indicates the beginning of the feature description. Following the DESCRIBE is the feature name, which must match the name specified in the map file 128. Finally, a set of braces contains the actual programming statements associated with the feature. Although the example description file 126 provided above is properly constructed, it is not particularly useful, since there is nothing specified within the braces. The following DESCRIBE block actually enables the circle feature to draw a circle: DESCRIBE Circle { ACAD_TypeE("_circle 5,5 3"); } The line added above is a 4Test.TM. programming statement that invokes a 4Test.TM. function that causes QA Partner.TM. to transmit the argument to an AutoCAD.TM. application program 120 as keystrokes. As the above example shows, underlying script code is placed directly into the feature description. Any line without a keyword is assumed to be underlying script code and is printed directly to the test 122. While the above DESCRIBE block draws a circle every time it is evaluated, there is plenty of room for improvement. For example, the RAND keyword can be used to randomly select different radii every time a circle is drawn: DESCRIBE Circle { ACAD_TypeE("_circle 5,5 RAND{4}"); } In the above example, each circle drawn will have a different radius between 0 and 4. To set a minimum radius of 1, the RAND{1,4} statement can be used, which limits the random numbers produced to the range of 1 to 4. The drawn circles could also have a randomly selected center point. This can be performed using RAND and a previously-defined POINT feature description: DESCRIBE Circle { ACAD_TypeE("_circle CALL Point{} RAND{4}"); } The test generator 118 can "remember" where these random circles were drawn, so that they can be found again for use with edit commands. The Point feature description is designed to do just that when an argument is used with the CALL. The argument is an index to store the point generated. The Point feature description uses RECORD to make an entry in the RECORD/EXTRACT database 124. The RECORD/EXTRACT database 124 used by record uses a hierarchy of categories so different kinds of data can be stored. Use of these categories makes it easier to retrieve the type of the desired data. Since a point on a circle is stored, RECORD stores it into the Pts (points) category. This can be done by using Pts.Circle as an index. A simple Circle feature description to store circles in the RECORD/EXTRACT database 124 is provided below: DESCRIBE Circle { ACAD_TypeE("_circle CALL Point{} CALL Point{{Pts.Circle}}"); } The CALL can be used to evaluate any feature description, but it is best to limit it to a few subroutine-like functions and let the test generator 118 decide when to call the true features. The above feature description draws randomly sized circles at random locations, but there are a number of different ways a circle can be drawn. It is probably best to test all these different methods. EXCLUSIVE Blocks A separate feature description could be created for each method of drawing a circle. This would be messy, however, and result in much code duplication. A better option is to keep a single circle description and add an EXCLUSIVE block, so that the test generator 118 can choose the method it will use to draw the circle. EXCLUSIVE stands for mutually exclusive, meaning that only one block of code in the EXCLUSIVE block will be evaluated. This makes sense, in this case, because only one method of drawing a circle can be used for each circle drawn. CODE blocks are used to indicate the different choices that can be made by an EXCLUSIVE block. CODE blocks are the only type of keyword allowed immediately within an EXCLUSIVE block. The inside of a CODE block is like the inside of a DESCRIBE block, in that any keyword can be used. Following is a circle description using EXCLUSIVE to allow the test generator 118 to pick the way to draw the circle:
DESCRIBE Circle {
ACAD_TypeE("_circle");
EXCLUSIVE 5,2,1 REPEAST 1 {
CODE {
CALL Point { }
CALL Point { Pts.Circle }
}
CODE {
ACAD_TypeE("_2P");
CALL Point { Pts.Circle }
CALL Point { }
}
CODE {
ACAD_TypeE("_3P");
CALL Point { Pts.Circl }
CALL Point { }
CALL Point .thrfore. }
}
}
}
Note the list of numbers after the EXCLUSIVE keyword. These are the relative frequencies that the test generator 118 will use to choose the code block it evaluates. The order of the frequencies corresponds to the order of the CODE blocks within the EXCLUSIVE. The list of frequencies is optional; if it is omitted, all CODE blocks are evaluated with equal frequency. Immediately following the list of frequencies is the optional REPEAT part of an EXCLUSIVE block. If the REPEAT keyword is included, the number following it indicates the maximum number of times the EXCLUSIVE block should be evaluated in succession. The test generator 118 picks a random number between 1 and this maximum, and evaluates the EXCLUSIVE block that many times in succession before proceeding. If REPEAT is omitted, the test generator 118 evaluates the EXCLUSIVE block once, which is the same behavior as that achieved with the REPEAT 1 statement used above. OPTION Blocks In some cases, a feature allows a number of choices that are independent of each other. Consider the choices presented in a text formatting dialog. It does not make sense to put code for setting the bold, italic and underline attributes in an EXCLUSIVE block, because the EXCLUSIVE block will choose exactly one of the CODE blocks. In this case, it would probably be preferable that the test generator 118 evaluate as many as all, or as few as none of these blocks. For situations like this, the test generator 118 provides the OPTION block. The syntax of an OPTION block is almost identical to the syntax of an EXCLUSIVE block. The only difference is that, since each of the OPTION block's CODE blocks are independent of each other, the list following the OPTION keyword is a list of probabilities, not a list of relative frequencies. Each element of the list of probabilities indicates the likelihood that its corresponding code block will be evaluated. A CODE block with a probability of 0 will never be evaluated; one with a probability of 1 will always be evaluated. If the list of probabilities is omitted, each block is assigned a probability of 0.5 (fifty-fifty chance). In an OPTION block, each probability is completely independent of the other probabilities. Changing one probability affects only that probability's corresponding CODE block, and has no affect on any other CODE block within the OPTION block. In the description below, an OPTION block is used to determine whether or not the second point will define the diameter of the circle. In this particular case, an EXCLUSIVE block could be used with equal success, but in many other cases, OPTION blocks are necessary. Although the example below includes only one CODE block, OPTION blocks, like EXCLUSIVE blocks, can contain as many CODE blocks as desired. In fact, if an OPTION block contains multiple CODE blocks, the order of the CODE blocks is shuffled before evaluation for better coverage of order-dependent bugs.
DESCRIBE Circle {
ACAD_TypeE("_circle");
EXCLUSIVE 5,2,1 REPEAT 1 {
CODE {
CALL Point { }
OPTION .3 {
CODE {ACAD_TypeE("_d");}
}
CALL Point { Pts.Circle }
}
CODE {
ACAD_TypeE("_2P");
CALL Point { Pts.Circle }
CALL Point { }
}
CODE {
ACAD_TypeE("_3P");
CALL Point { Pts.Circle }
CALL Point { }
CALL Point { }
}
}
}
Configuration Files The configuration files 132 used with the test generator 118 contain machine specific information, user specific information, and global configuration information that would be shared by everyone working on a particular project. The configuration file 132 is parsed and used to set constants that affect how the test generator 118 generates test scripts 122. The items listed in the table below are configuration parameters that are found in the configuration file 132. These configuration parameters control the size of the test scripts 122 generated by the test generator 118 and the locations of input and output files.
$TestActions The number of feature descriptions called per test
script.
$TestCases The number of test scripts generated per file.
$TestFiles The number of files generated. Files are named
based on $TestFilePath.
$AcceptMode When set to 1, the test generator 118 attempts to
evaluate every CODE block in every feature
description while generating as few test scripts as
possible. Test generation is normal when set to 0.
$MapFileDir Location of the map file.
$CommonDir Directory tree to be scanned for sub-descriptions
(Location is relative to $MapFileDir).
$OutputDir Directory in which test and include files are
written.
$StructFilename Filename for summary of feature description
graph traversal. Set to `NUL:` (Windows) or
`/dev/null` (UNIX) to suppress output
$IncludeFilename Filename for include file.
$TestFilename Filename for generated test scripts.
$ConsoleOutput Specifies the text string to use when writing the
Format status line during test generation.
The items listed in the table below are advanced configuration parameters found in configuration file 132. These parameters control the underlying structure of the database 124, as well as the test scripts 122 it generated by the test generator 118. Using these parameters, the test generator 118 can be adapted to different projects without changing the program 118 itself. Once the appropriate values are determined for a project, these items should need infrequent modification. Successfully changing these values requires a relatively thorough understanding of how the test generator 118 works.
$GlobDefault The default value to be returned if EXTRACT
cannot find a value for the specified key.
%DBDefaults A series of hierarchy-specific default values to be
returned if EXTRACT cannot find the specified
key. Each entry should be on a separate line, and
of the format "Key" => "DefaultValue", More
specific keys over-ride more general keys.
$IncludeFileExtension Extension of files that should be associated with
description files of same base name but different
extension and used to generate $IncludeFilename
$FinalizerDescription Name of feature description that should be called
at the end of every test script. This feature
description may be used to verify that the
application is in a legal state.
$TestCaseName Name pattern for test scripts. ### will be replaced
with the test script's number within the file to
ensure unique names. This should match the
names specified for test scripts in $TestPre.
$FilePre This value is written to the beginning of each file.
Before being written, any occurrences of
TESTCASENAMES are replaced with a list of
the names of all the test scripts generated in the
file. This list is based on $TestCaseName.
$FilePost This value is written to the end of every file.
$TestPre This value is written to the file immediately
before each test script. The test generator 118
resets all of its databases at the beginning of each
test script, so this should include code to reset
the application to a base state. Any occurrences of
### are replaced with the number of the test
script within the file, to ensure unique test script
names. Make sure that the pattern used to name
test scripts matches the one specified in
$TestCaseName.
$TestPost This value is written to the file after each test
script.
$ActionPre This value is written to the file before each
feature generated.
$ActionPost This value is written to the file after each feature
generated.
Acceptance Mode In normal operation of the test generator 118, sections of feature descriptions with very low frequency or probability may not be evaluated very often. In the process of debugging a set of description files 126, it may be desirable to have the test generator 118 evaluate every section of every description file 126 in a short period of time. This can be done using acceptance mode. In acceptance mode, the test generator 118 keeps track of which sections of a description file 126 it has already evaluated and will revisit these sections only when necessary to reach an unevaluated section. This behavior causes the test generator 118 to evaluate every section of every description file 126 in a relatively efficient manner. Test 122 generation is still random and based on frequencies, so higher frequency items are likely to be evaluated before those with lower frequencies. Note that the test generator 118 considers any description file 126 or CODE block with a frequency or probability of 0 to be effectively "commented out," so even in acceptance mode these sections will not be evaluated. Once all non-zero probability sections have been evaluated, the test generator 118 will report "All branches traversed" and test 122 generation will cease at the end of the current file 126. The test generator 118 can be set to run in acceptance mode through the $AcceptMode switch in the configuration file 132. Stateless Verification In addition to detection of application program 120 crashes, it is often desirable to have a description that explicitly initiates actions that detect undesirable program 120 states, such as memory leakage or inconsistency in internal data structures. This feature description, which is specified using the $FinalizerDescription statement, is called at the end of the test 122 if it can be located. If its frequency is 0, it will be called only at the end of tests 122. User Interface Graph Traversal In the present invention, the description files 126 comprise a text-based representation of the user interface of the application as a directed, cyclic graph. For purposes of quickly verifying that the descriptions are correct and match the user interface of the application being tested, it is desirable to have an "acceptance mode" in which the generator creates a series of tests that make use of every part of a set of description files 126. This can be done by traversing all edges of the graph formed by the description files 126. The present invention includes a mechanism for efficiently traversing all edges of such a graph in a random order. A graph is an abstract representation of data consisting of points (nodes) and lines (edges) connecting the nodes. As applied to the present invention, nodes represent user interface states and edges represent the data and/or actions that must be transmitted to the application to move it from one interface state to another. The term directed means that each edge may be traversed in only one direction. The graph formed by the description files has one base node, corresponding to the designated "base state" of the application's user interface (the "base state" is often defined as the first user interface state of the application after it begins execution). The term cyclic means that any path of traversal through the graph eventually returns to the base node. In understanding the structure of the graph formed by the description files 126 of the present invention, it may be helpful to appeal to higher levels of abstraction. Since all paths that exit the base node eventually return to it, at a high level of abstraction the graph can be considered to be comprised of one node with any number of edges that both exit and enter the node. Such a graph is illustrated in FIG. 2A. In the present invention, this node is roughly correspondent to the map file 128 and these edges to descriptions. In fact, a traversal path originating and terminating at the base node may pass through other nodes. Thus, the "edges" of the highly abstracted graph described in the above paragraph each represent a section or fragment of the actual graph with a single entry point and a single exit point. These fragments are composed of three basic structures. The first type of structure is comprised of an edge that enters a node from which any number of edges exit. All of these edges exiting the first node provide different paths to the same second node. FIG. 2C illustrates this type of structure, referred to hereafter as a structure of type 1. In the present invention, such a structure represents an EXCLUSIVE block. The second type of structure is different from the first in that of the edges exiting the first node, only one node continues to a second node and all the others re-enter the first node. This structure represents an OPTION block in the present invention. FIG. 2B illustrates this type of structure, referred to hereafter as a structure of type 2. The third type is that the edge in the abstracted graph simply represents a single edge in the actual graph. Just as the "edges" in the highest level abstraction of the graph represent one of the three possible graph fragment structures described above, each of the "edges" in the first two structures represents a graph fragment of one of the three types described above. Thus, one can imagine a series of abstractions of the actual graph, in which each successive abstraction has more "edges" that represent edges in the actual graph (the third type of structure) and fewer "edges" that represent one of the first two types of structures. The final "abstraction" in this series would be a graph in which all "edges" represented edges in the actual graph; in other words, a copy of the actual graph. By applying this series of abstractions, every node in the actual graph must be the base node, or the central part of one of the first two types of structures. This reasoning greatly simplifies the task of complete, random traversal. Before beginning traversal, an array of Boolean values is constructed such that there is an element representing each edge leaving the base node, each edge exiting the central node of structures of type 1 and each edge exiting and re-entering the central node of structures of type 2 in the graph. A value of true indicates the edge has been traversed. A stack that can contain references to the elements of the array is also created. Each iteration consists of a single traversal path through the graph that begins and ends at the base node. At the beginning of each iteration, an edge is randomly selected from those that exit the base node and are marked as untraversed. The Boolean for this edge is set true and a reference to the Boolean is pushed on the stack. According to the definition of the full graph given above, all edges must enter either the base node, a graph structure of type 1 or a graph structure of type 2. When the base node is encountered, the iteration is complete; another iteration begins with an empty stack. When a type 1 structure is encountered, the number of edges that exit the central node and are marked as untraversed is computed. If there is more than one, every edge referenced in the stack is marked false (untraversed). This ensures there will be at least one path of "untraversed" edges leading from the base node to this structure, since it will still contain at least one untraversed edge at the end of the current iteration. Next, an untraversed edge is selected at random, unless all edges are marked traversed, in which case a traversed edge is selected at random. This edge is then traversed: its Boolean is set true and a reference to it is pushed onto the stack. If the "edge" selected for traversal represents one or more fragments of type 1 or 2 rather than an edge in the actual graph, these structures are traversed according to the methods described in this and the following paragraph. Once the edge and any fragments it represents have been traversed, the reference to the edge is popped from the stack. When a type 2 structure is encountered, each edge that exits and reenters the central node and is marked as untraversed is sequentially traversed. This done by setting the appropriate Boolean true, pushing a reference to it, performing the appropriate procedures for the type 1 or 2 structures that the "edge" may represent, and finally popping the edge reference from the stack when the selected edge has been traversed. After all edges that reenter the central node have been traversed the edge that enters a new node is traversed. In an alternate embodiment that improves efficiency, a copy of the stack is made and the stack is cleared before beginning traversal of any edges. Sequential traversal proceeds as described above, but after each edge has been traversed the Boolean indicating the "traversal" status of the edge is examined. If the edge has been "unmarked" (the Boolean is false) due to untraversed edges within the fragments that the "edge" represents, the "edge" is traversed until it remains marked after traversal. After all edges that reenter the central node are marked as traversed (have their Booleans set true), the stack is restored from the copy and the edge that enters a new node is traversed. At the end of an iteration, an "edge" will be marked as traversed only if all of the edges in the graph fragments that it represents have been traversed. Thus, when all edges exiting the base node are marked as traversed, the graph has been completely traversed and no further iterations are necessary. While the present invention is described in the context of creation of software tests, those skilled in the art will recognize that the invention is not limited to such use and may be generally useful in any case where it is necessary to perform complete, randomly ordered traversal of a graph having the structure described here. Logic of the Test Generator FIGS. 3A and 3B together are a flowchart that illustrates the general logic of the test generator 118 when performing the steps of the present invention. Block 300 represents the test generator 118 initializing for execution on the computer 100. Block 302 represents the test generator 118 reading a specified map file 128 to identify the feature descriptions cited therein. The map file 128 may be specified interactively or via runtime parameters. Blocks 304-312 comprise a loop for processing features specified in the map file 128. Block 304 represents the test generator 118 selecting a feature. Block 306 represents the test generator retrieving the description files 126 for the feature. Alternatively, that the feature need not be read from the file (or scanned and parsed in the next step). A cache of recently used descriptions is maintained in a parsed form; if the needed description is in the cache, it can be loaded directly from there without parsing. Block 308 represents the test generator 118 scanning and parsing the feature descriptions, their associated programming statements, relative frequencies, random functions, shuffling functions, etc., from the retrieved description files 126. If the selected feature CALLs a feature, then the CALLed feature must be read, parsed and generated in an iterative manner. Block 310 representing the test generator 118 generating a test 122 action based on the feature that has been read. Block 312 is a decision block that represents the test generator 118 determining whether a specified number of actions have been generated. If not, control transfers to Block 304; otherwise, the logic ends. FIG. 3B describes an alternate mode of operation for the generator from FIG. 3A. The processes involved alter the operation of boxes 304 and 310 in FIG. 3A. In effect, it is a detail chart of a concurrent process, rather than a separate process, from FIG. 3A. Moreover, the method involves complex recursion (i.e., recursion from more than one location). Block 314 is a decision block that represents the test generator 118 determining whether it is in acceptance mode. If not, control transfers to Block 316, which terminates the logic; otherwise, control transfers to Block 318. Block 318 represents the test generator 118 creating a graph data structure in the memory 104 of the computer 100 comprised of one or more nodes connected by one or more edges, wherein the nodes represent a block of programming statements (i.e., EXCLUSIVE, OPTION, CODE blocks), and the edges represent the data. Block 318 also represents the test generator 118 constructing an array of Boolean values in the memory 104 of the computer 100, such that there is an element representing each edge leaving the base node and an element representing each interior edge for the structures of FIGS. 2B and 2C in the graph. Finally, Block 318 represents the test generator 118 creating a stack to contain references to the elements of the array. Blocks 320-342 comprise a loop for iteratively traversing the graph data structure created by the test generator 118. Block 320 is a decision block that represents the test generator 118 determining whether there are any untraversed edges exiting the base node in the graph data structure. If not, control transfers to Block 316, which terminates the logic; otherwise, control transfers to Block 322. Block 322 represents the test generator 118 randomly selecting, at the beginning of each iteration, an edge from those that exit the base node and are marked as untraversed. Any edge will enter either a FIG. 2A structure (the base node), a FIG. 2B structure, or a FIG. 2C structure. Block 322 also represents the test generator 118 writing the programming statements associated with the traversed edge to the test file 122, setting the Boolean for this edge to "true" to mark the edge as traversed, pushing a reference to the Boolean onto the stack, and traversing the edge. Block 324 is a decision block that determines whether the test generator 118 has returned to the base node, i.e., a FIG. 2A structure, which indicates that the iteration is complete. If so, control transfers to Block 320 to begin another iteration. Block 326 is a decision block that determines whether the test generator 118 has encountered a FIG. 2B structure. If so, control transfers to Block 328, which represents the test generator 118 selecting each edge in turn, setting the Boolean for the edge to "true" to mark the edge as traversed, pushing a reference to the Boolean onto the stack, and traversing the edge. After each edge is traversed, control transfers to Block 324. Block 330 is a decision block that determines whether the test generator 118 has encountered a FIG. 2C structure. If so, control transfers to Block 332; otherwise, control transfers to Block 318. Block 332 is a decision block that represents the test generator 118 determining whether the number of edges exiting the central node marked as untraversed is more than one. If so, control transfers to Block 334; otherwise, control transfers to Block 340. Block 334 represents the test generator 118 marking every edge referenced in the stack as "false" (untraversed), which ensures there will be at least one path of "untraversed" edges leading from the base node to this structure, since it will still contain at least one untraversed edge at the end of the current iteration. Block 336 represents the test generator 118 selecting an untraversed edge at random. Block 338 represents the test generator 118 traversing the selected edge, writing the programming statements associated with the traversed edge to the test file 122, setting its Boolean to "true" to mark the edge as traversed, pushing a reference to the Boolean onto the stack, performing the appropriate procedures for any FIGS. 2B or 2C structures encountered, and then finally popping the reference from the stack. Thereafter, control transfers to Block 324. Block 340 is a decision block that represents the test generator 118 determining whether there are no edges marked as untraversed. If so, control transfers to Block 342; otherwise, control transfers to Block 344. Block 342 represents the test generator 118 selecting a traversed edge at random and Block 344 represents the test generator 118 selecting the untraversed edge. Thereafter, in both instances, control transfers to Block 338, which represents the test generator 118 traversing the selected edge, setting its Boolean to "true", pushing a reference to the Boolean onto the stack, performing the appropriate procedures for any FIG. 2B structures or FIG. 2C structures that are encountered, and then finally popping the reference from the stack. Thereafter, control transfers to Block 324. When all edges exiting the base node are marked as traversed, the graph has been completely traversed and no further iterations are necessary. At this point, control transfers to Block 316, which terminates the logic. Conclusion This concludes the description of the preferred embodiment of the invention. The following describes some alternative embodiments for accomplishing the present invention. For example, any type of computer, such as a mainframe, minicomputer, workstation or personal computer, or network computer could be used with the present invention. In addition, any software program, application or operating system could benefit from the present invention. In summary, the present invention discloses a method, apparatus, and article of manufacture for performing a complete, randomly ordered traversal of a cyclic directed graph. A cyclic directed graph representation is created in the computer, which then iteratively selects traversal paths through the cyclic directed graph that result in traversal of every edge in the graph in a random order with a minimum number of iterations. In one embodiment, the cyclic directed graph represents the interface of a program being tested and tests are generated from this representation. In generating the tests, a test generator iteratively selects traversal paths through the cyclic directed graph that result in traversal of every edge in the graph in a random order with a minimum number of iterations. The resulting tests contain randomly selected actions and randomly generated data, and thus when executed, these tests randomly manipulate the program being tested. The foregoing description of the preferred embodiment of the invention has been presented for the purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise form disclosed. Many modifications and variations are possible in light of the above teaching. It is intended that the scope of the invention be limited not by this detailed description, but rather by the claims appended hereto.
|
Same subclass Same class Consider this |
||||||||||