Method and apparatus for automatically isolating minimal distinguishing stimuli in design verification and software development

• US 20030051232A1
• Filed: 08/29/2001
• Published: 03/13/2003
• Est. Priority Date: 08/20/2001
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Chang, Victor, Lam, William K.
• Granted Patent: US 7,017,150 B2
• Time in Patent Office: Days
• US Class Current: 717/131
• CPC Class Codes: G06F 11/362 Software debugging
• CPC Class Codes: G06F 11/3696 Methods or tools to render software testable

Abstract

The invention provides a method for detecting and isolating software bugs and generating a minimal set of stimuli to reproduce the bugs. The present invention utilizes a recursive algorithm to compare the output of successively smaller software blocks of a program in development to a verified output sample. The smallest software blocks which are found to contain a bug are isolated. For each of these isolated blocks, the smallest input vector is determined such that the application of this vector to the block expresses the bug. The present invention utilizes a separate recursive algorithm to determine these minimal vectors.

Claims

1. A method of debugging software comprising:

obtaining a software module;

obtaining a first input test vector;

obtaining a bug list;

generating a first output vector by applying said first input test vector to said software module;

applying a comparison test to said first output vector to determine whether a bug exists in said software module;

applying a module decomposition test to said software module when the result of said comparison test is positive; and

appending said software module and said first input test vector to said bug list when the result of said module decomposition test is negative.

2. The method of claim 1 wherein said comparison test comprises:

obtaining an optimal result vector;

comparing said first output vector to said optimal result vector; and

determining whether said first output vector is at variance with said optimal result vector.

3. The method of claim 2 wherein the step of generating a bug list further comprises:

obtaining a module decomposition list comprising two or more submodules of said software module when the result of said module decomposition test is positive; and

iteratively processing said module decomposition list.

4. The method of claim 3 wherein the iterative processing step comprises:

obtaining a second input test vector such that the application of said second input test vector to said submodule will generate a second output test vector; and

recursively processing said submodule and said second output test vector.

5. The method of claim 4 wherein the trimming step comprises:

obtaining said minimal module;

obtaining said first input test vector; and

applying a vector decomposition test to said first input test vector.

6. The method of claim 5 further comprising:

generating a third output vector by applying said first input test vector to said minimal module when the result of said vector decomposition test is negative;

applying said comparison test to said third output vector to determine whether said first input test vector recreates the bug; and

appending said input test vector to a test list when the result of said comparison test is positive.

7. The method of claim 6 further comprising:

obtaining a vector decomposition list comprising two or more subvectors of said first input test vector when the result of said vector decomposition test is positive; and

iteratively processing each entry in said vector decomposition list by recursively applying said vector decomposition test to said subvectors.

8. The method of claim 7 in which said software module and said input test vector are obtained by iterating through the entries in said bug list.