Data processing: measuring – calibrating – or testing – Testing system – Of circuit
Reexamination Certificate
2001-01-30
2003-06-10
Hoff, Marc S. (Department: 2857)
Data processing: measuring, calibrating, or testing
Testing system
Of circuit
C707S793000
Reexamination Certificate
active
06577982
ABSTRACT:
TECHNICAL FIELD
The present invention generally relates to software development tools and relates in particular to a system and method for generating test cases.
BACKGROUND OF THE INVENTION
Many systems, whether mechanical, software, or some combination thereof, have large numbers of independent variables, which are parameters relating to factors such as, for example, system configuration, system input, and the environment in which the system is used. These systems may be tested to detect errors and correct underlying system faults. Many system failures, however, occur only upon coincidence of several variable values and exhaustive testing of all variable value combinations is often unfeasible due to the sheer number of possible combinations.
Combinatorial design is a practicable approach to testing systems with large numbers of independent variables. In combinatorial design, test cases are typically chosen to include all interactions among limited groups of independent variables. For example, a group of test cases can be generated in which all possible pairs of variable values appear in at least one test case. Generating near minimal sets of test cases covering specified combinations of variable values, however, proves to be very difficult in all but the simplest of cases.
There exist several approaches to generating test cases for combinatorial design. Orthogonal arrays or Latin squares have been widely used. These techniques were developed for experimental design and have symmetry requirements that are not conducive to generating near minimal sets of test cases. In addition, while orthogonal array-based methods can generate test cases covering all pair-wise variable combinations, or all three-way variable combinations, orthogonal array-based methods are unsuitable for mixed-order models. A mixed-order model is one specifying, for example, the some variable groups be tested in three-way combination while other variable groups only require pair-wise testing.
In recent years a graph-theoretic approach based on an adjacency matrix representation has come into use. This approach generates near minimal sets of test cases, but like orthogonal array-based approaches, is limited to fixed-order models. An additional limitation of the graph-theoretic approach is that it has very large system resource requirements. The memory requirement increases with the number of independent variables taken to the power of the model order. Processing time also increases dramatically for higher order models.
SUMMARY OF THE INVENTION
The following presents a simplified summary of the invention in order to provide a basic understanding of some aspects of the invention. This summary is not an extensive overview of the invention. It is intended to neither identify key or critical elements of the invention nor delineate the scope of the invention. Its sole purpose is to present some concepts of the invention in a simplified form as a prelude to the more detailed description that is presented later.
The present invention provides systems and methods for generating sets of test cases and extends to the sets of test cases and processes using the sets of test cases to develop applications. One aspect of the invention provides a data structure for efficiently storing a set of variable value combinations among which the number of variables can vary. Another aspect of the invention provides systems and methods for sequentially generating test cases to encompass a set of variable value combinations. Advantages of the invention include permitting efficient generation of near minimal sets of test cases that include specified variable value combinations, among which the number of variables can vary, and seed test cases. Sets of test cases produced by the invention are distinctive and have practical value in processes for application development. The test cases permit more efficient and thorough testing of applications, which results in better applications.
One aspect of the invention provides a system for generating a set of test cases comprising a component for obtaining a set of variable value combinations to be included in the set of test cases. The number of variables is permitted to vary among the variable value combinations. The system further comprises a component for sequentially generating test cases to fill out the set of test cases. The test cases are generated with reference to the set of variable value combinations and which of the variable value combinations in the set do not appear in any previously generated test case.
A further aspect of the invention provides a computer-readable medium having stored thereon a data structure for use in generating sets of test cases for systems having a plurality of independent variables. The data structure comprises a list of combination structures, wherein each combination structure comprises a structure for identifying independent variables to which the combination structure corresponds.
A further aspect of the invention provides a method for generating a set of test cases comprising obtaining a set of variable value combinations to be included in the set of test cases, wherein the number of variables is permitted to vary among the variable value combinations, and sequentially generating test cases to fill out the set of test cases, wherein the test cases are generated with reference to the set of variable value combinations and which of the variable value combinations in the set do not appear in any previously generated test case.
To the accomplishment of the foregoing and related ends, certain illustrative aspects of the invention are described herein in connection with the following description and the annexed drawings. These aspects are indicative, however, of but a few of the various ways in which the principles of the invention may be employed and the present invention is intended to include all such aspects and their equivalents. Other advantages and novel features of the invention may become apparent from the following detailed description of the invention when considered in conjunction with the drawings.
REFERENCES:
patent: 4696003 (1987-09-01), Kerr et al.
patent: 5421004 (1995-05-01), Carpenter et al.
patent: 5579476 (1996-11-01), Cheng et al.
patent: 5604895 (1997-02-01), Raimi
patent: 5805795 (1998-09-01), Whitten
patent: 5892947 (1999-04-01), DeLong et al.
patent: 6038378 (2000-03-01), Kita et al.
patent: 6041330 (2000-03-01), Carman et al.
patent: 6148277 (2000-11-01), Asava et al.
patent: 6205575 (2001-03-01), Sherman et al.
patent: 6219829 (2001-04-01), Sivakumar et al.
patent: 6336217 (2002-01-01), D'Anjou et al.
patent: 6415396 (2002-07-01), Singh et al.
Huo Yan Chen, et al.; “ROCS: An Object-Oriented Class-Level Testing System Based on the Relevant Observable ContextS Technique”, Information and Software Technology, vol. 42, No. 10, 2000, p. 677-686.
Paul E. Black, “Modeling and Marshaling: Making Tests from Model Checker Coutnerexamples”, IEEE, Digital Avionics System Conference. Proceedings., vol. 1, p. 1.B.3-1-1.B.3-6.
Brian J. Taylor, et al.; “Regressive Model Approach to the Generation of Test Trajectories”, IEEE, Proceedings 3rd IEEE Symposium on Application-Specific Systems and Software Engineering Technology, 2000, p. 49-56.
Chien-Hung Liu, et al.;“Structural Testing of Web Applications”, Proceedings Eleventh International Symposium on Software Reliability Engineering, 2000, p. 84-96.
Taylor, B.J., et al.; “Evaluation of Regressive Methods for Automated Generation of Test Trajectories”, Proceedings Eleventh International Symposium on Software Reliability Engineering, 2000, p. 97-109.
Peraire, C., et al.; “Test Selection for Object-Oriented Software Based on Formal Specifications”, Programming Concepts and Methods. PROCOMET '98. IFIP TC2/WG2.2, 2.3 International Conference, 1998, p. 385-403.
Burr, et al.; “Combinatorial Test Techniques: Table-based Automation, Test Generation and Code Coverage”, p. 1-12.
Huller, Jerry; “Reducing Time to Market with Combinatorial Design Method Testing”, p. 1-8.
Sherwood, George; “Effective Te
Amin & Turocy LLP
Hoff Marc S.
Microsoft Corporation
Raymond Edward
LandOfFree
Model-based testing via combinatorial designs does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Model-based testing via combinatorial designs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Model-based testing via combinatorial designs will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3098656