Error detection/correction and fault detection/recovery – Data processing system error or fault handling – Reliability and availability
Reexamination Certificate
1999-08-03
2003-09-23
Beausoliel, Robert (Department: 2184)
Error detection/correction and fault detection/recovery
Data processing system error or fault handling
Reliability and availability
C714S032000, C706S013000
Reexamination Certificate
active
06625760
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to an apparatus and method for providing efficient and exhaustive testing for system validation. More particularly, using an application of evolution (applying an application of a genetic algorithm) in the testing programs to find a new population of testing programs that will be better than the prior generation of testing programs. The new population of testing programs use the parent generation of test programs that are found to cause failures in the system under test.
2. Description of Related Art
As is known in the computer and software arts, when a software program is developed, it will contain errors. As a consequence, developers of the software program utilize many techniques to check the correctness of the program and to diagnose errors.
It is known in the art that a way of verifying any system under test is just to operate it in some representative situation and verify the behavior of the system under test is as expected. In general, it is practically impossible to test a system under test under all possible operating conditions. Thus, it is necessary to find some suitable test cases that provide enough evidence that the desired behavior will be exhibited in all the remaining cases. This is often difficult to accomplish.
Two common methods in producing program tests are to 1) generate the program tests exhaustively and 2) to generate the program tests randomly. For example, if a program is a calculator program, then exhaustive testing would provide all valid input and then check if all the calculations are correct. Random testing would provide a random input and check if the calculations are correct. Truly exhaustive testing is usually impractical since the set of valid inputs for a program is usually infinite. In either case, the actual output is checked against the expected output (which may be produced by human operation or another program). Any differences between the expected and actual output indicate a potential problem with the program or reference.
It is known in the art that the only testing of any system under test that can provide absolute certainty about the correctness of the system under test's behavior is exhaustive testing (i.e., testing the system under all possible circumstances). Unfortunately, such testing can never be performed in practice. Thus, there is the need for testing strategies, i.e., some criterion for selecting significant test cases, that will provide the most complete testing.
A significant test case is one which has a high potential to uncover the presence of an error. Thus, successful execution of a significant test case increases the programmer's confidence of the correctness of the program. Intuitively, rather than running a large number of test cases, the goal in testing should be to run a number of significant test cases that are representative of all the possible test conditions. If a significant test case set is a super set of another significant test set, one can then rely more on the super set of another significant test set. On the other hand, since testing is costly in both man-hours and machine-time, it is the object of the programmer to limit the number of possible experiments.
Heretofore, software developers have lacked an apparatus and method to accomplish program testing in an efficient way.
SUMMARY OF THE INVENTION
To achieve the advantages and novel features, the present invention is generally directed to an apparatus and method for generating random tests that share similar characteristics and that can be discovered by a genetic generator quickly without going through the chance or long process of traditional random and exhaustive generations. This allows the testing system to generate random test cases that are applied to the system under test (SUT). These random tests are validated to see if they cause errors within the SUT. All test programs that cause an error during the execution of the SUT are collected and are used in the application of a genetic algorithm to create other testing programs that share similar characteristics.
The present invention further utilizes an apparatus and method that includes an evolution technique. The genetic testing program starts with an initial population of test cases. Test cases in test programs that cause failures in the system under test are saved to form a new population of test programs with test cases that share similar.characteristics.
This is motivated by the concept that the new population of test programs will trigger more failures than the old population of test programs. Test cases from test programs that cause failures in the SUT are selected to form the new testing programs (offspring) according to their fitness (i.e., that they will have a higher chance of finding more failures in the system under test).
REFERENCES:
patent: 4935877 (1990-06-01), Koza
patent: 5136686 (1992-08-01), Koza
patent: 5394509 (1995-02-01), Winston
patent: 5708774 (1998-01-01), Boden
patent: 5729623 (1998-03-01), Omatu et al.
patent: 5742738 (1998-04-01), Koza et al.
patent: 5754760 (1998-05-01), Warfield
patent: 5764857 (1998-06-01), Suzuki
patent: 5780789 (1998-07-01), Tsuji
patent: 5781698 (1998-07-01), Teller et al.
patent: 5805795 (1998-09-01), Whitten
patent: 6058385 (2000-05-01), Koza et al.
patent: 6088690 (2000-07-01), Gounares et al.
patent: 6282527 (2001-08-01), Gounares et al.
patent: 6304833 (2001-10-01), Ferkinhoff et al.
Melanie Mitchell, “An Introduction to Genetic Algorithms”, 1999, Massachussetts Institute of Technology, Chapters 1.3, 1.5, 1.6, and 5.4.
Krishnaswamy Umesh
Man Richard F.
Beausoliel Robert
Chu Gabriel L.
LandOfFree
Apparatus and method for generating random tests for program... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for generating random tests for program..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for generating random tests for program... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3070149