Apparatus and method for generating random tests for program validation using genetic evolution

• US 6,625,760 B1
• Filed: 08/03/1999
• Issued: 09/23/2003
• Est. Priority Date: 08/03/1999
• Status: Expired due to Fees

• Current Assignee: Agilent Technologies, Inc., Hewlett-Packard Company (HP Inc.), Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Krishnaswamy, Umesh, Man, Richard F.
• Primary Examiner(s): Beausoliel, Robert
• Assistant Examiner(s): Chu, Gabriel L.
• Application Number:
  US09/368,019
• Time in Patent Office: 1,512 Days
• Field of Search: 714/26, 714/32, 714/33, 714/38, 706/13
• US Class Current: 714/33
• CPC Class Codes: G06F 11/263 Generation of test inputs, e.g. test vectors, patterns or sequences ; with adaptation of the tested hardware for testability with external testers

Abstract

Apparatus and method are described for a testing system that generates tests that share similar failure causing characteristics that can be discovered by a genetic generator quickly without going through the chance or long process of traditional random and exhaustive test generations. The testing system generates random test cases that are applied to a system under test (SUT). These tests are validated to determine whether they cause errors within the SUT. All testing programs that cause an error during the execution of the SUT are collected and are used in the genetic algorithm technique to create other testing programs that share similar characteristics.

Claims

1. A method to analyze a computer system under test, said computer system including a plurality of instructions, the method comprising the steps of:

creating a plurality of test programs, each of said test programs including a plurality of test cases;

testing said computer system under test by executing said computer system under test using each of said plurality of test programs as input data and saving any of said plurality of test programs that cause said computer system under test to fail during said execution;

selecting a pre-determined number of generations for which to perform generation tests on said computer system under test;

performing said generation tests on said computer system under test for the predetermined number of generations selected, wherein said performing comprises;

generating a plurality of new generation test programs, each new generation test program including a plurality of test cases saved when one of said plurality of test programs caused said computer system under test to fail during execution; and

combining a plurality of test fragments for each new generation test program, each of said plurality of test fragments including a predetermined number of test cases saved from said test programs that caused said computer system under test to fail during execution.

2. The method of claim 1, wherein the combining step further comprises the steps of:

determining a crossover probability that determines a ratio of test fragments created from at least one of said test programs that caused said computer system under test to fail during execution; and

determining a mutation probability that determines a ratio of test fragments that are randomly changed in said plurality of test fragments combined for each new generation test program.

3. The method of claim 1, wherein the combining step further comprises the step of:

selecting the number of test fragments to be combined for each new generation test program.

4. The method of claim 1, wherein the combining step further comprises the step of:

selecting the number of test cases to be combined in each of said plurality of test fragments for each new generation test program.

5. The method of claim 1, wherein the performing step further comprises the steps of:

next generation testing of said computer system under test, said next generation

testing further comprising the steps of;

executing said computer system under test, said computer system under test using one of said plurality of new generation test pro(grams as input data;

saving a plurality of new generation test cases included in said one of said plurality of new generation test programs that cause said computer system under test to fail during execution; and

repeating said next generation testing step a predetermined number of times using a different one of said plurality of new generation test programs as input data for each testing.

6. The method of claim 5, wherein the performing step further comprises the step of:

generating a plurality of newer generation test programs, each one of said newer generation test programs including a plurality of newer generation test cases from said plurality of new generation test cases saved when said plurality of new generation test programs caused said computer system under test to fail during execution.

7. An apparatus for analyzing a computer system, said computer system including a plurality of instructions, said analysis apparatus comprising:

means for creating a plurality of test programs, each of said test programs including a plurality of test cases;

means for testing said computer system under test by executing said computer system under test using each of said plurality of test programs as input data and saving any of said plurality of test programs that caused said computer system under test to fail during said execution;

means for selecting a pre-determined number of generations for which to perform generation tests on said computer system under test;

means for performing said generation tests on said computer system under test for the pre-determined number of generations selected, wherein said means for performing comprises;

means for generating a plurality of new generation test programs, each new generation test program including a plurality of test cases saved when one said plurality of test programs caused said computer system under test to fail during execution; and

means for combining a plurality of test fragments for each new generation test program, each of said plurality of test fragments including a predetermined number of test cases saved from said test programs that caused said computer system under test to fail during execution.

8. The apparatus of claim 7, wherein said combining means further comprises:

means for determining a crossover probability that determines a ratio of test fragments created from at least one of said test programs that caused said computer system under test to fail during execution; and

means for determining a mutation probability that determines a ratio of test fragments that are randomly changed in said plurality of test fragments combined for each new generation test program.

9. The apparatus of claim 7, wherein said combining means further comprises:

means for determining a number of test fragments to be combined for each new generation test program.

10. The apparatus of claim 7, wherein said combining means further comprises:

means for determining a number of test cases to be combined in each of said plurality of test fragments for each new generation test program.

11. The apparatus of claim 7, wherein the means for performing step further comprises:

means for next generation testing of said computer system under test, said next generation testing means further comprising;

means for executing said computer system under test using one of said plurality of new generation test programs as input data;

means for saving a plurality of new generation test cases included in said one of said plurality of new generation test programs that cause said computer system under test to fail during execution; and

means for repeating said next generation testing means for a predetermined number of times using a different one of said plurality of new generation test programs as input data for each testing.

12. The apparatus of claim 7, wherein the means for performing further comprises:

means for generating a plurality of newer generation test programs, each one of said newer generation test programs including a newer generation of a plurality of test cases from said plurality of new generation test cases saved when said plurality of new generation test programs caused said computer system under test to fail during execution.

13. A computer readable medium having a program for testing a computer system, the program comprising:

logic configured to create a plurality of test programs, each of said test programs including a plurality of test cases;

logic configured to test said computer system under test by executing said computer system under test using each of said plurality of test programs as input data and saving any of said plurality of test programs that cause said computer system under test to fail during said execution;

logic configured to select a pre-determined number of generations for which to perform generation tests on said computer system under test; and

logic configured to perform said generation tests on said computer system under test for the pre-determined number of generations selected, wherein said logic configured to perform comprises;

logic configured to generate a plurality of new generation test programs by combining a plurality of test fragments in each new generation test program, each of said plurality of test fragments includes a predetermined number of test cases saved from said test programs that caused said computer system under test to fail during execution;

logic configured to retest said computer system under test, said retest logic further comprising;

retesting processor logic configured to execute said computer system under test, said computer system under test using one of said plurality of new generation test programs as input data;

resaving logic configured to save a plurality of test cases included in said one of said plurality of new generation test programs that cause said computer system under test to fail during execution; and

logic configured to repeat said retest logic a predetermined number of times using a different one of said plurality of new generation test programs as input data for each testing.

14. The computer system testing program of claim 13, wherein the logic configured to generate comprises:

logic configured to determine a crossover probability that ascertains a ratio of said test fragments created from at least one of said test programs that caused said computer system under test to fail during execution; and

logic configured to determine a mutation probability that ascertains a ratio of said test fragments that are randomly changed in said plurality of test fragments combined for said new generation test program.

15. The computer system testing program of claim 14, wherein the logic configured to perform further comprises:

newer generation logic configured to generate a newer generation test program combining a plurality of new generation test fragments in a new generation test program, each of said plurality of new generation test fragments includes a predetermined number of test cases saved from said new generation test programs that caused said computer system under test to fail during execution;

newer generation testing processor logic configured to execute said computer system under test, said computer system under test using one of a plurality of newer generation test programs as input data;

newer generation saving logic configured to save said plurality of test cases included in said one of plurality of newer generation test programs that cause said computer system under test to fail during execution; and

logic configured to repeat said newer generation test logic a predetermined number of times using a different one of said plurality of newer generation test programs as input data for each testing.

16. The computer system testing program of claim 13, wherein the logic configured to perform further comprises:

logic configured to determine a number of test fragments to be combined for each of said new generation test programs; and

logic configured to determine a number of test cases to be combined in each of said plurality of test fragments for each of said new generation test programs.