Data processing: structural design – modeling – simulation – and em – Modeling by mathematical expression
Reexamination Certificate
2000-02-17
2004-10-12
Teska, Kevin J. (Department: 2123)
Data processing: structural design, modeling, simulation, and em
Modeling by mathematical expression
C703S022000, C714S025000, C714S033000, C714S037000, C714S038110
Reexamination Certificate
active
06804634
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to test engineering in systems design and more specifically to the automatic generation and regeneration of covering test cases in test engineering.
BACKGROUND
In systems design, the requirements document typically specifies the behavior of a component for a given set of conditions. Prior to implementing a system, test cases are generated to test that the system satisfies the requirements. Test cases are ordered sets of inputs and descriptions of expected responses for the system under test. A test engineer either translates the requirements directly into a test script, or translates the requirements to a test model. If a test model is built, the test engineer may manually select test cases based on specified priorities, such as to test certain requirements. Alternatively, test cases can be generated from the test model using special purpose algorithms. These algorithms may optimize certain goals, like generating the fewest number of test cases to exercise all requirements.
Once the system has been implemented, new features are typically requested and added as users exercise the system, and old features may be modified or removed. The request for new or modified features is ordinarily formalized in the requirements document as new or changed requirements. Prior to deploying added features, test cases are created to test that the software complies with the new or modified requirements. Rather than creating all new test cases, sets of test cases for a system are typically maintained to ensure that critical functionality still operates correctly in view of new functionality. These test case sets are termed regression test cases, and the activity of testing a system to ensure conformance with legacy requirements is termed regression testing. Some test cases are also maintained because they are particularly useful in exposing defects or bugs. These test cases, called productive test cases, exercise those aspects of the system that are more likely to be disrupted by software changes. Regression test case sets and productive test cases are created and maintained over the life of the system.
When a test model is constructed based on the initial set of requirements, test generation algorithms implemented in a computer based tool can be used to generate a set of test cases that meet a specified coverage criteria. When new features are added to the system, the requirements for the new features serve as the basis for extending and modifying the test model. The test engineer extends and modifies the test model for the original system to reflect the new and changed requirements imposed on the system by the added features. The system that implements the original and added features is the incremented system, and the test model that reflects the original requirements and the requirements for the added features is the incremented test model.
A test engineer using known tools and methods has two options for generating a set of covering test cases for the incremented system. In the first option, the test engineer retains the entire original set or part of the original set of tests that were selected to cover the original system. The test engineer manually inspects the incremented test model and selects additional tests to achieve a desired coverage criterion such as to test all new requirements, test all requirements, cover all transitions, etc. If the portion of the incremented test model inherited from the original test model was modified to accommodate added features, then the test engineer must manually inspect and fix the portion of the incremented test model inherited from the original model to ensure that all the retained tests are valid for the incremented system.
This first option maintains the critical tests and productive tests from the original system and uses them in the testing of the incremented system. The disadvantages of this option, however, are that no method exists for automatically generating the remainder of the tests to achieve the desired coverage of the incremented system. Tests manually selected by a test engineer may achieve the desired coverage, but at the cost of being highly redundant as compared to tests selected algorithmically with the assistance of a computer based tool. Minimizing the number of tests generated to cover the system's functionality is desirable since testing resources are constrained and the portion of time allocated to testing a system prior to deployment is limited.
The second option for generating covering test cases for incremented systems is to discard the set of tests generated for the original system and generate new tests for the incremented system from scratch. Since none of the original tests are retained, there is no need to inspect and fix any of the original test cases. The disadvantage of this approach is that any critical tests and productive tests discovered during the testing of the original system will not necessarily be included in the newly generated set of test cases. Coverage criteria can be met with a minimum number of test cases and test lengths; however, the retention of critical and productive tests is compromised.
SUMMARY OF THE INVENTION
A method and apparatus according to the principles of the invention provides for the generation and regeneration of covering test case sets directly and automatically from a model. The model can be any of the type used in testing, such as ordinary and extended finite state machines or hierarchical graphs. In an exemplary embodiment, the model is in the form of a hierarchical graph, called a directed graph. A user retains test cases of interest by either manually selecting paths through the graph or by selecting test cases previously generated by test case generation algorithms. Paths are sequences of edges, shown as arrows on the graph, or sequences of nodes or nodes and edges. After selecting these test cases, a generator applying a coverage criterion (i.e., a test goal) to the graph generates or regenerates test cases covering the graph, according to the coverage criterion. During the generation or regeneration, nodes or edges that are part of the previously selected test cases need not be included in the resulting test cases. Similarly, undesired transitions in the model can be forbidden.
In an exemplary apparatus, a model editor provides for generation and manipulation of the directed graph. Each node references a message sequence chart (MSC), the empty set, or another directed graph. Requirements can be linked to a node or edge on a graph or to an object (event, timer, text box, etc.) in the MSC. The user selects a set of paths through the directed graph. This path may exercise functions of interest, or may effectively reveal system bugs. The apparatus automatically marks the edges and nodes in the selected paths, indicating that the edges and nodes are covered by the paths. A requirement is marked as covered (or optional) if a member of the selected set of nodes and edge has a link to the requirement either directly or in the case of a node to an MSC, if the attached MSC contains a link to the requirement.
If edge coverage is the selected criterion, in a subsequent generation of test cases, a covered node, edge or requirement need not be selected as part of another test case. A covered element is selected if the element is necessary to satisfy the coverage goal. The resulting covering test cases satisfy the chosen test goal; the set comprises the selected test cases and the generated test case set, where the selection of covered nodes or edges is minimized according to the selected criterion.
REFERENCES:
patent: 4991176 (1991-02-01), Dahbura et al.
patent: 5377201 (1994-12-01), Chakradhar et al.
patent: 5490249 (1996-02-01), Miller
patent: 5652835 (1997-07-01), Miller
patent: 5870308 (1999-02-01), Dangelo et al.
patent: 6061812 (2000-05-01), Holzmann et al.
patent: 6308299 (2001-10-01), Burch et al.
patent: 6324496 (2001-11-01), Alur et al.
patent: 6389576 (2002-05-01), Lam et al.
patent: 6415396 (2002-07-01), Singh et
Holzmann Gerard J.
Holzmann Margaret H.
Striegel James J.
Yannakakis Mihalis
Lucent Technologies - Inc.
Sharon Ayal
Teska Kevin J.
LandOfFree
Automatic generation and regeneration of a covering test... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Automatic generation and regeneration of a covering test..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Automatic generation and regeneration of a covering test... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3264396