Method and apparatus for filtering software tests

RELATED APPLICATION

0001This application hereby claims priority under 35 U.S.C. §119(e) to U.S. Provisional Application Ser. No. 60/853,204, filed on 20 Oct. 2006, the contents of which are herein incorporated by reference.

BACKGROUND

00021. Field of the Invention

0003Embodiments of the present invention relate to techniques for testing software. More specifically, embodiments of the present invention relate to a technique for filtering sequences of operations to produce targeted software tests.

00042. Related Art

0005Software testing is a critical part of the software development process. As software is written, the software is typically subjected to an extensive battery of tests which ensure that the software operates properly. It is far preferable to fix bugs in code modules as they are written, to avoid the cost and frustration of dealing with them during large-scale system tests, or even worse, after software is deployed to end-users.

0006As software systems grow larger and more complicated, creating a set of tests that adequately exercise the software systems is becoming harder. The creation of a set of tests is difficult because the tester has to create test cases to cover all of the possible combinations of input parameters and initial system states that the system may encounter during operation. Consequently, the amount of test code required to cover the possible combinations is typically a multiple of the number of instructions in the code under test.

0007One of the challenges in creating tests for program code is to produce a sequence of operations (a “testing sequence”) that thoroughly exercises the code under test. Unfortunately, creating a testing sequence by hand, particularly for anything other than the very smallest bodies of program code, is often virtually impossible. Hence, it is desirable to generate the testing sequence automatically. However, simple automated test generators can produce extremely large testing sequences which, although they exercise a large percentage of the paths in the code, can require large amounts of time and computational resources to execute.

0008These testing sequences typically include a significant number of operations that are superfluous or redundant. Consequently, a significant percentage of the execution time for the testing sequence may be spent executing operations which provide no unique information about the correctness of the underlying program code.

0009Hence, what is needed is a method and apparatus for limiting the size of software testing sequences to the minimal necessary operations.

SUMMARY

0010Embodiments of the present invention provide a system that generates a test for a class under test. The system first receives an operation sequence to be applied to the class under test. The system then generates one or more operation subsequences from the received operation sequence. Next, the system filters each operation subsequence. The system then produces a filtered version of the operation subsequences, wherein the filtered version of the operating subsequences can be used to perform tests on the class under test more expediently.

0011In some embodiments, when receiving the operation sequence, the system receives a sequence of operations generated from program code, wherein the sequence of operations includes operations performed on at least one path through the program code.

0012In some embodiments, when receiving the operation sequence, the system prepares the operation sequence by: (1) recording operations in the operating sequence that are performed on the class under test as potential test calls; (2) instrumenting the class under test; and (3) executing the operation sequence and storing information related to each potential test call in a variable associated with the potential test call.

0013In some embodiments, when instrumenting the class under test, the system adds one or more calls to the class under test, wherein the calls record information related to the execution of the class under test.

0014In some embodiments, when generating one or more operation subsequences from the received operation sequence, the system generates an operation subsequence for each potential test call, wherein each operation subsequence includes a copy of the operations between the start of the operation sequence and the corresponding potential test call.

0015In some embodiments, filtering each operation subsequence involves pre-filtering the operation subsequence by: (1) removing setup calls from the operating subsequence when the setup calls have undesirable effects on the potential test call; (2) removing unused objects; (3) removing unrelated objects; (4) removing operations that do not produce objects or alter state from the operation subsequence; and/or (5) removing intermediate states.

0016In some embodiments, after pre-filtering is completed, the system discards operation subsequences that include more than a predetermined number of operations. Next, for operation sequences that are not discarded, the system verifies that the potential test call at the end of the operating subsequence produces the same results as the information stored in the variable associated with the potential test call.

0017In some embodiments, the system discards the operating subsequence if the potential test call at the end of the operating subsequence does not produce the same results.

0018In some embodiments, the system saves the operation subsequence as a unique operating subsequence if the potential test call at the end of the operating subsequence produces different but unique results, wherein the unique operating subsequence can subsequently be used as another test for the class under test.

0019In some embodiments, if the potential test call at the end of the operating subsequence produces the same results, the system post-filters the operation subsequence by: (1) replacing with equivalent mock objects objects that cannot be constructed due to missing operations and/or objects of any class that has consistency problems due to timing or environmental dependencies from the subsequence; (2) removing unnecessary operations; (3) normalizing data, values and/or construction sequences; and/or (4) removing unnecessary instances of objects.

0020In some embodiments, when filtering the operation subsequence, the system post-filters the operation subsequence by: (1) replacing with equivalent mock objects objects that cannot be constructed due to missing operations and/or objects of any class that has consistency problems due to timing or environmental dependencies from the subsequence; (2) removing unnecessary operations; (3) normalizing data, values and/or construction sequences; and/or (4) removing unnecessary instances of objects.

0021In some embodiments, when producing the filtered version of the operating subsequences, the system produces the filtered version of the operating subsequence in a common programming language.

0022In some embodiments, the system performs the test on the class under test using the filtered operation subsequences.

BRIEF DESCRIPTION OF THE FIGURES

0023<figref idref="DRAWINGS">FIG. 1</figref> presents a block diagram of a computer system in accordance with embodiments of the present invention.

0024<figref idref="DRAWINGS">FIG. 2</figref> presents a flowchart illustrating the process of generating a set of tests in accordance with embodiments of the present invention.

0025<figref idref="DRAWINGS">FIG. 3</figref> presents a flowchart illustrating the process of preparing the operation sequence in accordance with embodiments of the present invention.

0026<figref idref="DRAWINGS">FIG. 4</figref> presents an operation sequence and two reduced operation sequences in accordance with embodiments of the present invention.

0027<figref idref="DRAWINGS">FIG. 5</figref> presents a flowchart illustrating the process of pre-filtering an operation sequence in accordance with embodiments of the present invention.

0028<figref idref="DRAWINGS">FIG. 6</figref> presents a flowchart illustrating a process of verifying the pre-filtered operation sequence in accordance with embodiments of the present invention.

0029<figref idref="DRAWINGS">FIG. 7</figref> presents a flowchart illustrating the process of post-filtering the operation sequence in accordance with embodiments of the present invention.

0030Table 1 presents a table of operation terms in accordance with embodiments of the present invention.

DETAILED DESCRIPTION

0031The following description is presented to enable any person skilled in the art to make and use the invention, and is provided in the context of a particular application and its requirements. Various modifications to the disclosed embodiments will be readily apparent to those skilled in the art, and the general principles defined herein may be applied to other embodiments and applications without departing from the spirit and scope of the present invention. Thus, the present invention is not limited to the embodiments shown, but is to be accorded the widest scope consistent with the claims.

0032The data structures and code described in this detailed description are typically stored on a computer-readable storage medium, which may be any device or medium that can store code and/or data for use by a computer system. This includes, but is not limited to, magnetic and optical storage devices, such as disk drives, magnetic tape, CDs (compact discs) and DVDs (digital versatile discs or digital video discs), or solid-state devices, such as flash memory, or other volatile and non-volatile storage media.

Terminology

0033We use the following terminology in addition to standard object-oriented programming terminology.

0034Atomic Type: The atomic type includes objects such as primitive values (int, char, double, etc.) and arrays. However, for our purposes, any class that is easily constructed and produces immutable, equivalent objects can be considered atomic because source code to create the object can be generated at will. Therefore, we consider all primitives and primitive wrapper classes (i.e., java.lang.integer) to be atomic as well as java.lang.String and java.lang.Class.

0035Object Reference: A class that represents a unique reference to another object. For atomic types the object reference embeds the value. For others, the object reference records the type of the object as well as the object's identity hash code (as returned from System.identityHashCode( )).

0036Operation: A single action in a sequence. Operations include method and constructor calls, but also include instructions, field accesses and mutations, and all array operations (create, access, and mutate). An operation includes a symbolic representation of the operation (“call method String.append( )” or “get field System.out”) as well as any arguments and/or parameters necessary to perform the operation represented as object references.

0037Operation Sequence: A series of operations, executed in order.

0038Setup Sequence: An operation sequence executed in order to establish the preconditions necessary for the test.

0039Test Call: An operation identified as the target for a test. The test call is a method or constructor call made on the class under test.

0040Setup Operation: An operation is a setup operation if the operation is not the test call for a particular test. An operation can be a setup operation for one test, and be the test call for another test.

0041Mock Object: An object that is declared to be the same type as a real object used in the test (by implementing the same interfaces or extending the necessary base class) but is missing the logic necessary to act as that type. Instead, the mock object is programmed by the setup sequence to respond in a predetermined way for testing purposes. Mock objects can be used in unit testing frameworks to simulate certain conditions, improve performance, or isolate failures.

Overview

0042Given any operation sequence and a class under test, some embodiments of the present invention reduce the operation sequence to a set of “tests” that demonstrate unique specifications for the class under test. These embodiments create tests that demonstrate the actual behavior of the operation sequence. In some embodiments, a human observer can identify which of the results of the generated tests reflect defects in the product (i.e., the class under test), and which ones are expected behavior.

0043There are a number of techniques for generating high quality operation sequences for a class under test. For example, one such technique is described by Marat Boshernitsan, Roongko Doong, and Alberto Savoia in “<i>From Daikon To Agitator: Lessons and Challenges in Building a Commercial Tool for Developer Testing</i>,” Proceedings of the 2006 International Symposium on Software Testing and Analysis, Portland, Me., July 2006. Note that the number and the quality of the tests generated from the operation sequence is related to the coverage and quality of the operation sequence itself.

Computer System

0044<figref idref="DRAWINGS">FIG. 1</figref> presents a block diagram of a computer system <b>100</b> in accordance with embodiments of the present invention. Computer system <b>100</b> includes processor <b>102</b>, memory <b>104</b>, and mass storage device <b>106</b>. In some embodiments of the present invention, computer system <b>100</b> is a general-purpose computer that is used to generate a set of tests for a class under test and to execute the set of tests for the class under test.

0045Processor <b>102</b> is a central processing unit (CPU) that processes instructions for computer system <b>100</b>. For example, processor <b>102</b> can be a microprocessor, a controller, an ASIC, or any other type of computational engine. Memory <b>104</b> is volatile memory that stores instructions and data for processor <b>102</b> during operation of computer system <b>100</b>. For example, memory <b>104</b> can be DRAM, SDRAM, or another form of volatile memory. Mass storage device <b>106</b> is a non-volatile storage device that stores instructions and data for processor <b>102</b>. For example, mass storage device <b>106</b> can be a hard disk drive, a flash memory, an optical drive, or another non-volatile storage device.

0046Note that although we describe embodiments of the present invention using computer system <b>100</b>, alternative embodiments use other types of computing devices.

Generating a Set of Tests for A Class Under Test

0047<figref idref="DRAWINGS">FIG. 2</figref> presents a flowchart illustrating the process of generating a set of tests in accordance with embodiments of the present invention. As shown in <figref idref="DRAWINGS">FIG. 2</figref>, given a single arbitrarily long operation sequence, the steps in identifying and generating a set of tests that test a particular class's specifications are: <ul id="ul0001" list-style="none"><li id="ul0001-0001" num="0000"><ul id="ul0002" list-style="none"><li id="ul0002-0001" num="0048">1. Preparing the operation sequence (step <b>200</b>): which involves recording information about operations.</li><li id="ul0002-0002" num="0049">2. Filtering the operation sequence, which involves: <ul id="ul0003" list-style="none"><li id="ul0003-0001" num="0050">a. Pre-filtering the operation sequence (step <b>202</b>): which reduces the operation sequence using aggressive static filters; and</li><li id="ul0003-0002" num="0051">b. Post-filtering the operation sequence (step <b>204</b>): which further reduces the pre-filtered operation sequence using conservative dynamic filters.</li></ul></li></ul></li></ul>

0052These steps are described in more detail below. Note that in some embodiments of the present invention, the system may perform the steps in an order other than the order in which the steps are described, and/or may skip one or more steps (or one or more parts of steps) in the process.

Preparing the Operation Sequence

0053<figref idref="DRAWINGS">FIG. 3</figref> presents a flowchart illustrating the process of preparing the operation sequence in accordance with embodiments of the present invention. Preparing the operation sequence involves performing the following actions: <ul id="ul0004" list-style="none"><li id="ul0004-0001" num="0000"><ul id="ul0005" list-style="none"><li id="ul0005-0001" num="0054">1. Identifying operations directly performed on the class under test (CUT) and mark the operations as potential test calls (step <b>300</b>).</li><li id="ul0005-0002" num="0055">2. Instrumenting the CUT to gather information (step <b>302</b>). For example, calls can be added before and/or after conditional instructions in methods within the class. Each call can potentially record information about the conditional instruction (e.g., the status of the comparison value(s), the resolution of the conditional, or the type of conditional). In some embodiments, the added calls include the following: <ul id="ul0006" list-style="none"><li id="ul0006-0001" num="0056">a. Coverage by branch, which involves inserting a call to record whether a branch was traversed. For instance, each Boolean condition can get two coverage points (i.e., calls), one for true and one for false. In addition, each statement and/or line can get one coverage point.</li><li id="ul0006-0002" num="0057">b. Boundary conditions, wherein each time a number comparison is performed and one of the sides of the comparison is a constant (e.g., i>500 or s.length ( )==20), the system inserts a call to record the comparison with both the actual left-hand-side (LHS) and right-hand-side (RHS) values. The call can be used to recognize boundary cases. For instance, in the case of i>500, the tests for i==499, 500, and 501 are unique tests that are generated in the final set of tests.</li></ul></li></ul></li></ul>

00583. Executing the operation sequence (step <b>304</b>) one operation at a time. In some embodiments of the present invention, the operation sequence can be executed reflectively.

00594. During execution, for each ‘potential test call’ in the operation sequence, storing information related to each potential test call in a variable associated with the potential test call for later use (step <b>306</b>). For example, some embodiments of the present invention can: <ul id="ul0007" list-style="none"><li id="ul0007-0001" num="0000"><ul id="ul0008" list-style="none"><li id="ul0008-0001" num="0060">a. Record the coverage for the class before and after the test call—to get an understanding of what branches this code covers;</li><li id="ul0008-0002" num="0061">b. Record any boundaries that were exercised by this call (for instance, i=499);</li><li id="ul0008-0003" num="0062">c. Record any unique return values (for instance, if the method returns a collection/array—a collection of size 0 and collection of non-zero size are different); and/or</li><li id="ul0008-0004" num="0063">d. Record any exceptions that the method throws (which can include recording the type of the exception thrown for uniqueness).</li></ul></li></ul>

0064Filtering the Operation Sequence

0065<figref idref="DRAWINGS">FIG. 4</figref> presents a operation sequence and two reduced operation sequences in accordance with embodiments of the present invention. Given a sequence of <b>1</b> . . . n operations (OP[<b>1</b>] . . . OP[n] in the operation sequence), with m test calls, for each test call (at a corresponding position p), filtering involves reducing the original <b>1</b> . . . p operation sequence (OS) down to the relevant set of operations. So the input to filtering is m operation sequences with the last operation on each sequence being the test call to which the filtering is related.

0066Hence, for m test calls, operation sequences OS<b>1</b> . . . OSm are provided as inputs to the filtering process. Note that OS<b>1</b> is a subset of OSm, and hence the operations in OS<b>1</b> are also part of the setup call for OSm. In fact, all calls up to last test call (at the end of the original operation sequence) are considered setup calls for operation sequences related to subsequent test calls.

0067For each OS(<b>1</b> . . . m), the following paragraphs describe the steps for filtering the reduced operation sequence down to the necessary set of operations. Note that some embodiments of the present invention perform the filtering steps in a different order and/or skip one or more steps in the filtering process.

0068Pre-Filtering/Static Filtering

0069<figref idref="DRAWINGS">FIG. 5</figref> presents a flowchart illustrating the process of pre-filtering an operation sequence in accordance with embodiments of the present invention. Pre-filtering the operation sequence removes operations from the operation sequence that are not in some way used to perform the test call at the end of the operation sequence.

0070In some embodiments of the present invention, the following actions are performed iteratively until the actions do not impact the size of the operation sequence (i.e., until no operations are removed from the operation sequence during an iteration). Note that performing the actions iteratively can result in the removal of more operations from the operation sequence, because every time an operation is removed, the removal can affect other operations that were being kept solely to construct the removed operation's parameters. <ul id="ul0009" list-style="none"><li id="ul0009-0001" num="0000"><ul id="ul0010" list-style="none"><li id="ul0010-0001" num="0071">1. Remove undesirable setup calls (step <b>500</b>). For example, this action can remove setup calls that throw exceptions, as these setup calls would likely not help getting the desired outcome from the test call. (Note that some embodiments of the present invention can be configured to keep setup calls that throw relevant exceptions.)</li><li id="ul0010-0002" num="0072">2. Remove unused objects (step <b>502</b>). Remove from the operation sequence any operation that does not: (1) produce a non-atomic object used by other operations, or (2) alter the state of the system in any other way (e.g, by mutating parameters). <ul id="ul0011" list-style="none"><li id="ul0011-0001" num="0073">a. To determine if a method could alter the state of the system, we use static analysis of the method related to the operation. In other words, we follow inter-method calls up to 2 classes away from the CUT. For example, if method <b>1</b> (M<b>1</b>) in the CUT calls M<b>2</b> in class <b>1</b> (C<b>1</b>), which in turn calls M<b>3</b> in C<b>2</b>, which calls M<b>4</b> in C<b>3</b>—our analysis stops with M<b>3</b> in C<b>2</b>.</li><li id="ul0011-0002" num="0074">b. Static analysis for mutation of parameters is conservative, so if the calls proceed beyond a predefined “depth” (i.e., M<b>3</b> in C<b>2</b> as described above) or if one of the methods in the call chain was native or on an interface that could mutate the parameters, we assume that the call would have mutated the parameters. For example, in the case above, the call to M<b>1</b> is considered mutating.</li><li id="ul0011-0003" num="0075">c. Methods that mutate class or instance fields are considered mutating by the static analysis.</li></ul></li><li id="ul0010-0003" num="0076">3. Remove unrelated objects (step <b>504</b>). Identify all operations that create non-atomic parameters to the test call, possibly mutate those parameters, or possibly mutate global state. Then identify all operations that create or possibly mutate non-atomic parameters to these operations recursively until a tree of operations is identified. Remove all other operations from the operation sequence.</li><li id="ul0010-0004" num="0077">4. Remove operations that do not produce objects or alter state (step <b>506</b>). Go back to the operations kept (i.e., not discarded in steps <b>500</b>-<b>504</b>) for “possibly” mutating state and use static analysis to remove operations which can be guaranteed not to mutate the relevant state.</li><li id="ul0010-0005" num="0078">5. Remove intermediate states (step <b>508</b>). Of the remaining operations that mutate state, use static analysis to remove operations that contain irrelevant mutations. For example, setting a value to “5” and then to “5” again without an intermediate use of the value is redundant. On the other hand, setting the value to “5” and then to “7” without an intermediate use makes the “5” setting operation irrelevant so only the “7” setting operation needs to be kept. (Note that the value set by these operations may not have an intervening use because one or more operations were removed from between these operations in steps <b>500</b>-<b>506</b>.)</li></ul></li></ul>

0079<figref idref="DRAWINGS">FIG. 6</figref> presents a flowchart illustrating a process of verifying the pre-filtered operation sequence in accordance with embodiments of the present invention. (Note that embodiments of the present invention skip further processing steps for an operation sequence if the operation sequence is discarded.)

0080The system first discards the pre-filtered operation sequence if the operation sequence includes more than a predetermined number of operations (step <b>600</b>). For example, if the operation sequence includes over <b>100</b> operations, the operation sequence can be discarded because post-filtering/dynamic filtering is too expensive for operation sequences that include more operations.

0081The system then executes the pre-filtered operation sequence using reflection (step <b>602</b>) and validates that the test call still produces the same outcome as the unfiltered operation sequence (e.g., coverage, number boundaries, and return value boundaries) (step <b>604</b>). <ul id="ul0012" list-style="none"><li id="ul0012-0001" num="0000"><ul id="ul0013" list-style="none"><li id="ul0013-0001" num="0082">1. If the operation sequence performs the same outcome as before, proceed to the post-filtering (step <b>606</b>).</li><li id="ul0013-0002" num="0083">2. If the operation sequence produces a different outcome: <ul id="ul0014" list-style="none"><li id="ul0014-0001" num="0084">a. Unless step <b>608</b> has already been performed, replace all setup calls and provide parameters using equivalent mock objects (step <b>608</b>) and then repeat steps <b>602</b>-<b>604</b>.</li><li id="ul0014-0002" num="0085">b. Determine if the results (e.g., coverage, number boundaries, return value boundaries) have been seen before by other test calls in the operation sequence (step <b>610</b>). If not, save this operation sequence as a unique operation sequence to filter (OS(m+1)) (step <b>612</b>). If so, discard the operation sequence (step <b>614</b>).</li></ul></li></ul></li></ul>

0086Assertion Generation

0087Some embodiments of the present invention subsequently generate assertions on the test call for the operation sequence. For example, one such assertion is the “assert equals” assertion, which is part of common unit testing frameworks. Such unit testing frameworks are known in the art and therefore are not described.

0088The assertion generation is performed by saving the objects before and after the test call (i.e., during the last reflection-based run of the operation sequence) and performing a nested diff analysis on the pre- and post-object graphs to analyze which objects the test call changed. Assertion generation can include placing assertions to analyze return value(s) and/or exceptions. In the absence of diff and return value assertions, assertions are placed based on statically analyzing what the test call accesses from the class (for instance, GETFIELD or GETSTATIC operations).

0089Post-Filtering/Dynamic Filtering

0090After the operation sequence has completed the pre-filtering process, the operation sequence enters post-filtering (interchangeably called “dynamic filtering”). The post-filtering phase eliminates unnecessary operations from the setup sequence that cannot be identified via static filtering techniques and also normalizes the selection of test data in the setup sequence operations.

0091Each operation sequence that enters post-filtering is ensured, by the earlier checks, to be shorter than a predetermined number of operations (e.g., less than 100 operations) and to produce the desired outcome (i.e., the test call in the pre-filtered operation sequence produces the same result as the test call in the full operation sequence).

0092In some embodiments of the present invention, during post-processing, the dynamic filters make a change to the setup sequence for a given operation sequence, then execute the setup sequence and test call. For example, the dynamic filters can remove an operation from the given operation sequence and then re-execute the operation sequence. If the test results (e.g., exception, return value, covered path, and boundary conditions) are different, the change is reversed.

0093In some embodiments of the present invention, if any of these temporary changes result in unique results that are not achieved with any of the existing tests, the operation sequence can be saved as a new test and passed through the filtering process later.

0094Note that the pre-filtering modified a larger operation sequence, but only executed the operation sequence once (after the pre-filtering was complete). On the other hand, the dynamic filter executes the given sequence multiple times.

0095<figref idref="DRAWINGS">FIG. 7</figref> presents a flowchart illustrating the process of post-filtering the operation sequence in accordance with embodiments of the present invention. The post-filtering/dynamic filtering process includes the following actions: <ul id="ul0015" list-style="none"><li id="ul0015-0001" num="0000"><ul id="ul0016" list-style="none"><li id="ul0016-0001" num="0096">1. Tune the “mock strategy” (step <b>700</b>). This involves dynamic filtering (and verification) which uses an adjustable strategy for mock objects that selects when to remove real objects that were used in the original sequence and replace them with equivalent mock objects. Any objects that cannot be constructed due to missing operations are “mocked,” as are objects of any class that is known to have consistency problems due to timing or environmental dependencies. As part of the dynamic filtering process, the mock strategy is adjusted to find a consistently functional sequence using as few mock objects as possible.</li><li id="ul0016-0002" num="0097">2. Remove all unnecessary operations (step <b>702</b>). During this operation, each independent setup operation is removed, one at a time, to see if the setup operation is actually required to achieve the expected results. In other words, an operation is removed from the operation sequence and the sequence is run. If the results are the same without the removed operation as they were with the removed operation, the operation is discarded from the operation sequence. Otherwise, if the results are different, the result of the operation can be mocked or the operation can be put back into the sequence.</li><li id="ul0016-0003" num="0098">3. Normalize data/values and construction sequences (step <b>704</b>). For example, some embodiments of the present invention try using canonical numbers such as “100” instead of a unique numbers such as “342” in the operation sequence. Using recognizable numbers improves consistency and readability by not implying significance to a selected value when any value will do. In addition, when a sub-operation sequence is used to construct a particular object, embodiments of the present invention attempt to use the same sub-operation each time the object is constructed (as opposed to using a different sub-operation each time the object is constructed).</li><li id="ul0016-0004" num="0099">4. Remove unnecessary instances of objects (step <b>706</b>). For example, when an operation takes an object “A” and produces an object “B” of the same type, embodiments of the present invention remove the operation and replace object B with object A.</li></ul></li></ul>

Example Class and Resulting Test

0100The following section provides a “Product” class, some intermediate output from a filtering process on an operation sequence that calls constructors and methods in the Product class, a test call, and an exemplary test in accordance with embodiments of the present invention.

0000<tables id="TABLE-US-00001" num="00001"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><thead><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>package tutorial;</entry></row><row><entry /><entry>public class Product {</entry></row><row><entry /><entry>  private static final String CODE_MASK = “[A-Z]-</entry></row><row><entry /><entry>  \\d\\d\\d\\d-\\d\\d-[A-Z]”;</entry></row><row><entry /><entry>  private String code;</entry></row><row><entry /><entry>/*</entry></row><row><entry /><entry>* @param CODE_MASK Must be of the form A-9999-99-A</entry></row><row><entry /><entry>* @throws IllegalArgumentException if the code is invalid</entry></row><row><entry /><entry>*/</entry></row><row><entry /><entry>public Product(String code) throws IllegalArgumentException{</entry></row><row><entry /><entry>  validateCode(code);</entry></row><row><entry /><entry>  this.code = code;</entry></row><row><entry /><entry>}</entry></row><row><entry /><entry>public String getCode( ) {</entry></row><row><entry /><entry>  return code;</entry></row><row><entry /><entry>}</entry></row><row><entry /><entry>public String toString( ) {</entry></row><row><entry /><entry>  return code;</entry></row><row><entry /><entry>}</entry></row><row><entry /><entry>private void validateCode(String code) throws</entry></row><row><entry /><entry>IllegalArgumentException {</entry></row><row><entry /><entry>  if (!code.matches(CODE_MASK)) {</entry></row><row><entry /><entry>    throw new IllegalArgumentException(“Product code</entry></row><row><entry /><entry>    should be of the form A-9999-99-A”);</entry></row><row><entry /><entry>  }</entry></row><row><entry /><entry>  if (code == null) {</entry></row><row><entry /><entry>    throw new IllegalArgumentException(“Product code</entry></row><row><entry /><entry>    cannot be null”);</entry></row><row><entry /><entry>  }</entry></row><row><entry /><entry>}}</entry></row><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0101The Product class has a constructor that takes a product code as an argument. The product code is validated using the regular expression (regex) match in the validateCode method. Unless the product code is invalid, a new Product object is created using the product code. The Product class also includes a method for getting the code of a Product object.

0102We now present an example operation with a subsequent definition of the terms in the operation. In Java, the operation is:

0000<tables id="TABLE-US-00002" num="00002"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="35pt" align="left" /><colspec colname="1" colwidth="182pt" align="left" /><thead><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>Product p = new Product(“testString”); // throws</entry></row><row><entry /><entry>IllegalArgumentException,</entry></row><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables><br /> and the resulting operation is:

0000<tables id="TABLE-US-00003" num="00003"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217pt" align="center" /><thead><row><entry namest="1" nameend="1" rowsep="1">TABLE 1</entry></row><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row><row><entry>Operation Terms</entry></row><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>#19605997 tutorial/Product.<init>.(Ljava/lang/String;)V</entry></row><row><entry /><entry>[[ref[java.lang.String:“testString”]]] [ref[NULL]] Ex:</entry></row><row><entry /><entry>[ref[java.lang.IllegalArgumentException@1c2ec05/notnull]].</entry></row><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="98pt" align="left" /><colspec colname="2" colwidth="119pt" align="left" /><tbody valign="top"><row><entry>#19605997</entry><entry>System.identityHashCode( ) value for</entry></row><row><entry /><entry>the operation.</entry></row><row><entry>tutorial/Product.<init></entry><entry>Indicates that this operation is a</entry></row><row><entry /><entry>constructor call for the Product</entry></row><row><entry /><entry>class.</entry></row><row><entry>(Ljava/lang/String;)V</entry><entry>Indicates that the constructor</entry></row><row><entry /><entry>which has 1 string parameter is the</entry></row><row><entry /><entry>one being invoked.</entry></row><row><entry>[[ref[java.lang.String:“test</entry><entry>Represents the object references</entry></row><row><entry>String”]]]</entry><entry>for the parameter. (In this case,</entry></row><row><entry /><entry>all the object references are for</entry></row><row><entry /><entry>atomic types, hence the values are</entry></row><row><entry /><entry>embedded in the object references.</entry></row><row><entry /><entry>So the constructor was invoked with</entry></row><row><entry /><entry>the code value of “testString.”)</entry></row><row><entry>[ref[NULL]] Ex:</entry><entry>Represents the return value from</entry></row><row><entry>[ref[java.lang.IllegalArgume</entry><entry>the call, as well as any exceptions</entry></row><row><entry>ntException@1c2ec05/notnull]</entry><entry>thrown. In this case the</entry></row><row><entry>]</entry><entry>constructor threw an</entry></row><row><entry /><entry>IllegalArgumentException. ref[NULL]</entry></row><row><entry /><entry>is a special object reference to</entry></row><row><entry /><entry>represent a null value.</entry></row><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0103The following paragraphs present an example of a simple input operation sequence that is reduced to the final sequence (with comments on the filtered operations showing which filtering step was used to eliminate the operation). The test call is the last operation for ‘Product.toString( ).’ Note that the operations that make it through the filtering processes are accented using bold typeface (and that “filtered” operations are removed from the operation sequence).

0000<tables id="TABLE-US-00004" num="00004"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><thead><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>/* filtered - setup call throws exceptions - undesirable */</entry></row><row><entry /><entry>#19605997 tutorial/Product.<init>.(Ljava/lang/String;)V</entry></row><row><entry /><entry>[[ref[java.lang.String:“testString”]]] [ref[NULL]] Ex:</entry></row><row><entry /><entry>[ref[java.lang.IllegalArgumentException@1c2ec05/notnull]]</entry></row><row><entry /><entry>/* filtered - setup call throws exceptions - undesirable */</entry></row><row><entry /><entry>#13472381 tutorial/Product.<init>.(Ljava/lang/String;)V</entry></row><row><entry /><entry>[[ref[java.lang.String:“D1”]]] [ref[NULL]] Ex:</entry></row><row><entry /><entry>[ref[java.lang.IllegalArgumentException@442c76/notnull]]</entry></row><row><entry /><entry>/* filtered - setup call throws exceptions - undesirable */</entry></row><row><entry /><entry>#5002799 tutorial/Product.<init>.(Ljava/lang/String;)V</entry></row><row><entry /><entry>[[ref[java.lang.String:“Product code should be of the form A-</entry></row><row><entry /><entry>999999-A”]]] [ref[NULL]] Ex:</entry></row><row><entry /><entry>[ref[java.lang.IllegalArgumentException@16a23cf/notnull]]</entry></row><row><entry /><entry>/* filtered - setup call throws exceptions - undesirable */</entry></row><row><entry /><entry>#4018462 tutorial/Product.<init>.(Ljava/lang/String;)V</entry></row><row><entry /><entry>[[ref[NULL]]] [ref[NULL]] Ex:</entry></row><row><entry /><entry>[ref[java.lang.NullPointerException@ecf608/notnull]]</entry></row><row><entry /><entry>/* filtered - setup call throws exceptions - undesirable */</entry></row><row><entry /><entry>#26780509 tutorial/Product.<init>.(Ljava/lang/String;)V</entry></row><row><entry /><entry>[[ref[java.lang.String:“”]]] [ref[NULL]] Ex:</entry></row><row><entry /><entry>[ref[java.lang.IllegalArgumentException@1412b61/notnull]]</entry></row><row><entry /><entry>/* filtered - setup call throws exceptions - undesirable */</entry></row><row><entry /><entry>#6610297 tutorial/Product.<init>.(Ljava/lang/String;)V</entry></row><row><entry /><entry>[[ref[java.lang.String:“?????????????????????????????”]]]</entry></row><row><entry /><entry>[ref[NULL]] Ex:</entry></row><row><entry /><entry>[ref[java.lang.IllegalArgumentException@1064a6d/notnull]]</entry></row><row><entry /><entry><b>/* not-filtered - setup call produces the ‘this’ object for the</b></entry></row><row><entry /><entry><b>test call */</b></entry></row><row><entry /><entry><b>#11698353 tutorial/Product.<init>.(Ljava/lang/String;)V</b></entry></row><row><entry /><entry><b>[[ref[java.lang.String:“V-3496-55-F”]]]</b></entry></row><row><entry /><entry><b>[ref[tutorial.Product@170a650/notnull]] Ex: [ref[NULL]]</b></entry></row><row><entry /><entry>/* filtered - setup call produces an object that's not used by the</entry></row><row><entry /><entry>test call */</entry></row><row><entry /><entry>#18817368 tutorial/Product.<init>.(Ljava/lang/String;)V</entry></row><row><entry /><entry>[[ref[java.lang.String:“H-7858-51-X”]]]</entry></row><row><entry /><entry>[ref[tutorial.Product@5113f0/notnull]] Ex: [ref[NULL]]</entry></row><row><entry /><entry>/* filtered - setup call produces an object that's not used by the</entry></row><row><entry /><entry>test call and doesn't mutate state */</entry></row><row><entry /><entry>#33371659 tutorial/Product.getCode.( )Ljava/lang/String;</entry></row><row><entry /><entry>[[ref[tutorial.Product@170a650/notnull]]]</entry></row><row><entry /><entry>[ref[java.lang.String:“V-3496-55-F”]] Ex: [ref[NULL]]</entry></row><row><entry /><entry>/* filtered - setup call throws exceptions - undesirable */</entry></row><row><entry /><entry>#29478849 tutorial/Product.<init>.(Ljava/lang/String;)V</entry></row><row><entry /><entry>[[ref[java.lang.String:“testString”]]] [ref[NULL]] Ex:</entry></row><row><entry /><entry>[ref[java.lang.IllegalArgumentException@1bdbf9d/notnull]]</entry></row><row><entry /><entry>/* filtered - setup call produces an object that's not used by the</entry></row><row><entry /><entry>test call, and doesn't mutate state */</entry></row><row><entry /><entry>#9124787 tutorial/Product.toString.( )Ljava/lang/String;</entry></row><row><entry /><entry>[[ref[tutorial.Product@170a650/notnull]]]</entry></row><row><entry /><entry>[ref[java.lang.String:“V-3496-55-F”]] Ex: [ref[NULL]]</entry></row><row><entry /><entry><b>/* the test call */</b></entry></row><row><entry /><entry><b>#16555646 tutorial/Product.toString.( )Ljava/lang/String;</b></entry></row><row><entry /><entry><b>[[ref[tutorial.Product@170a650/notnull]]]</b></entry></row><row><entry /><entry><b>[ref[java.lang.String:“V-3496-55-F”]] Ex: [ref[NULL]]</b></entry></row><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0104Given this sequence of operations and the corresponding test call, the final test that is generated looks like this:

0000<tables id="TABLE-US-00005" num="00005"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><thead><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>public void testToString( ) throws Throwable {</entry></row><row><entry /><entry>  String result = new Product(“V-3496-55-F”).toString( );</entry></row><row><entry /><entry>  assertEquals(“result”, “V-3496-55-F”, result);</entry></row><row><entry /><entry>}</entry></row><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0105In some embodiments of the present invention, the final test from the filtering process is in a common language, instead of a more difficult to interpret proprietary language (which is used in some unit testing frameworks). For example, some embodiments of the present invention output the final test in the Java programming language.

0106After the filtering processes are completed on the operation sequence, the number of operations in the operation sequence has been reduced so the operation sequence can be run in a significantly reduced time (in comparison with the time required to run the original operation sequence). Although the operation sequence has been reduced, the verification process ensures that the outcome of the operation sequence matches the expected outcome (i.e., the outcome produced by the original operation sequence).

0107The foregoing descriptions of embodiments of the present invention have been presented only for purposes of illustration and description. They are not intended to be exhaustive or to limit the present invention to the forms disclosed. Accordingly, many modifications and variations will be apparent to practitioners skilled in the art. Additionally, the above disclosure is not intended to limit the present invention. The scope of the present invention is defined by the appended claims.