Method and apparatus for debugging, verifying and validating computer software

• US 6,173,440 B1
• Filed: 05/27/1998
• Issued: 01/09/2001
• Est. Priority Date: 05/27/1998
• Status: Expired due to Term

• Current Assignee: Mcdonnell Douglas Corporation (The Boeing Co.)
• Original Assignee: Mcdonnell Douglas Corporation (The Boeing Co.)
• Inventors: Darty, Mark A.
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): Vo, Ted T.
• Application Number:
  US09/085,386
• Time in Patent Office: 958 Days
• Field of Search: 395/701, 395/702, 395/703, 395/704, 395/705, 717/1, 717/11, 717/4
• US Class Current: 717/130
• CPC Class Codes: G06F 11/3608 using formal methods, e.g. model checking, abstract interpretation theorem proving G06N5/013
• CPC Class Codes: G06F 11/3672 Test management

Abstract

A new approach for software debugging, verification and validation is disclosed. The present invention utilizes a knowledge-based reasoning approach to build a functional model of the software code for identifying and isolating failures in the software code. The knowledge-based reasoning approach of the present invention uses the software design, which is preferably based upon a flow chart or block diagram representation of the software functionality, to build the functional model. The software block diagram contributes to the functional model by defining the inputs and outputs of the various blocks of code, as well as defining data interconnections between the various blocks of code. In accordance with a method of the present invention, test points are strategically inserted throughout the code, and each test point is associated with a corresponding block of code. Expected values of the test points for an expected proper-operation execution of the computer program are generated. The computer program is then executed on a computer, and the actual values of the test points from the program execution are compared with the expected values of the test points. Failed test points which do not agree with corresponding expected values are determined. The functional model, which includes information functionally relating the various test points to one another, is then used to isolate the failed test points to one or more sources of failure in the code.

Claims

1. A method of locating a source failure test point among a plurality of test points in a computer program, the source failure test point having a greatest probability of being an originating source of failure among the plurality of test points, the method comprising the following steps:

ranking the plurality of test points in the computer program in accordance with an order of execution and a data dependency of each of the plurality of test points, to thereby define a ranked group of test points, the step of ranking comprising;

grouping lines of code of the computer program into functional blocks;

identifying inputs and outputs for each functional block;

creating a block diagram showing the interconnectivity of the functional blocks;

identifying dependency sets in the block diagram, each dependency set (fault dependency set) defining a fault propagation path, which indicates a flow of data or program operation through a number of the functional blocks;

defining a run time test point data file, the run time test point data file storing output values of test points during execution of the computer program; and

defining a dependency set matrix, the dependency set matrix defining at least one dependency set;

generating expected values for the plurality of test points for an expected, proper-operation execution of the computer program;

executing the computer program on a computer to thereby generate actual values for the plurality of test points;

comparing the expected values for the plurality of test points with the actual values for the plurality of test points;

identifying a plurality of failed test points, each failed test point having an actual value which does not correspond with an expected value for the test point;

locating at least one source failure test point in the plurality of failed test points, using the ranked group of test points, the at least one source failure test point being an earliest failed test point, in the order of execution and data dependency, among the ranked group of test points.

2. The method as recited in claim 1, wherein the ranking step includes a step of defining at least one fault propagation path.

3. The method as recited in claim 1, wherein:

the plurality of failed test points corresponds to a single ranked group of test points, the single ranked group of test points defining a fault dependency set.

4. The method as recited in claim 1, wherein:

the plurality of failed test points corresponds to a plurality of ranked groups of test points, each ranked group of test points defining a separate fault dependency set.

5. The method as set forth in claim 4, wherein the step of locating at least one source failure test point in the plurality of failed test points comprises a step of locating at least one source failure test point in the plurality of failed test points, using the plurality of ranked groups of test points.

6. The method as set forth in claim 1, wherein the step of generating expected values for the plurality of test points comprises a step of defining a reference test point data file, the reference test point data file storing the expected values for the plurality of test points.

7. The method as set forth in claim 6, wherein the step of executing the computer program on a computer to thereby generate actual values for the plurality of test points comprises a step of storing output values of test points in the run time test point data file.

8. The method as set forth in claim 7, wherein the step of comparing the expected values for the plurality of test points with the actual values for the plurality of test points comprises a step of correlating the reference test point data file with the run time test point data file.

9. The method as set forth in claim 8, wherein the step of identifying a plurality of failed test points comprises the following steps:

defining a run time pass/fail matrix, the run time pass/fail matrix being adapted to store the plurality of failed test points; and

entering the plurality of failed test points in the run time pass/fail matrix.

10. The method as set forth in claim 9, wherein the step of locating at least one source failure test point in the plurality of failed test points comprises a step of determining which dependency sets contain failed test points, using the dependency set matrix.

11. The method as set forth in claim 10, wherein the step of locating at least one source failure test point in the plurality of failed test points comprises a step of locating the at least one source failure test point in the plurality of failed test points, using the dependency sets in the dependency set matrix that were determined to contain failed test points.

12. The method as set forth in claim 10, wherein the step of locating at least one source failure test point in the plurality of failed test points comprises the following steps:

defining a fault detection set matrix, the fault detection set matrix being adapted to store dependency sets therein;

storing the dependency sets that contain failed test points in the fault detection set matrix;

determining which dependency sets in the fault detection set matrix contain the same failed test points; and

locating the at least one source failure test point in the plurality of failed test points using the dependency sets that contain failed test points.

13. The method as set forth in claim 12, wherein the step of locating at least one source failure test point in the plurality of failed test points comprises the following steps:

determining whether a number of test points corresponds to a number of functional blocks; and

determining a functional block that corresponds to each test point, upon a determination that the number of test points does not correspond to a number of functional blocks.

14. A method of locating a source failure test point among a plurality of test points in a computer program, the source failure test point having a greatest probability of being a source of failure in the computer program, the method comprising the following steps:

ranking the plurality of test points in accordance with an order of data dependency of the test points, to define a ranked group of test points, wherein a highest ranked test point in the ranked group of test points is not dependent on any test point in the ranked group of test points, and wherein a lowest ranked test point in the ranked group of test points is ultimately dependent on all of the test points in the ranked group of test points, wherein the step of ranking comprises;

grouping lines of code of the computer program into functional blocks;

identifying inputs and outputs for each functional block;

creating a block diagram showing the interconnectivity of the functional blocks;

identifying dependency sets in the block diagram, each dependency set defining a fault propagation path, which indicates a flow of data or program operation through a number of the functional blocks;

defining a run time test point data file, the run time test point data file storing output values of test points during execution of the computer program; and

defining a dependency set matrix, the dependency set matrix defining at least one dependency set;

generating expected values for the plurality of test points for an expected, proper-operation execution of the computer program;

executing the computer program on a computer to thereby generate actual values for the plurality of test points;

comparing the expected values for the plurality of test points with the actual values for the plurality of test points;

identifying a plurality of failed test points, each failed test point having an actual value which does not correspond with an expected value for the test point; and

locating a source failure test point in the ranked group of test points, the source failure test point having a highest ranking among failed test points in the ranked group of test points.

15. The method as set forth in claim 14, wherein the step of generating expected values for the plurality of test points comprises a step of defining a reference test point data file, the reference test point data file storing the expected values for the plurality of test points.

16. The method as set forth in claim 15, wherein the step of executing the computer program on a computer to thereby generate actual values for the plurality of test points comprises a step of storing output values of test points in the run time test point data file.

17. The method as set forth in claim 16, wherein the step of comparing the expected values for the plurality of test points with the actual values for the plurality of test points comprises a step of correlating the reference test point data file with the run time test point data file.

18. The method as set forth in claim 17, wherein the step of identifying a plurality of failed test points comprises the following steps:

defining a run time pass/fail matrix, the run time pass/fail matrix being adapted to store the plurality of failed test points; and

entering the plurality of failed test points in the run time pass/fail matrix.

19. The method as set forth in claim 18, wherein the step of locating at source failure test point in the ranked group of test points comprises the following steps:

determining which dependency sets contain failed test points, using the dependency set matrix; and

locating the at least one source failure test point in the plurality of failed test points, using the dependency sets in the dependency set matrix that were determined to contain failed test points.

20. The method as set forth in claim 18, wherein the step of locating at source failure test point in the ranked group of test points comprises the following steps:

defining a fault detection set matrix, the fault detection set matrix being adapted to store dependency sets therein;

storing the dependency sets that contain failed test points in the fault detection set matrix;

determining which dependency sets in the fault detection set matrix contain the same failed test points; and

locating the source failure test point in the ranked group of failed test points using the dependency sets that contain failed test points.

21. A method of selecting a source failure test point from a plurality of test points in a computer program, the source failure test point having a highest probability relative to other test points of being a source of failure in the computer program, the method comprising the following steps:

forming a test point group from the plurality of test points, wherein test points in the test point group depend from one another to define a data flow path;

ranking the test points in the test point group in accordance with an order of execution and data dependency of the test points, wherein the step of ranking comprises;

grouping lines of code of the computer program into functional blocks;

identifying inputs and outputs for each functional block;

creating a block diagram showing the interconnectivity of the functional blocks;

identifying dependency sets in the block diagram, each dependency set defining a fault propagation path, which indicates the data flow path through a number of the functional blocks;

defining a run time test point data file, the run time test point data file storing output values of test points during execution of the computer program; and

defining a dependency set matrix, the dependency set matrix defining at least one dependency set;

generating expected values for the plurality of test points for an expected, proper-operation execution of the computer program;

executing the computer program on a computer to thereby generate actual values for the plurality of test points;

comparing the expected values for the plurality of test points with the actual values for the plurality of test points;

identifying a plurality of failed test points, each failed test point having an actual value which does not correspond with an expected value for the test point; and

determining which of the plurality of failed test points belong to the test point group; and

locating the source failure test point by finding a failed test point within the test point group which does not depend from any other failed test points within the test point group and which is earliest in execution in the data flow path relative to the other failed test points within the test point group.

22. A method of selecting a source failure test point from a plurality of test points in a computer program, the source failure test point having a highest probability relative to other test points in the computer program of being a source of failure, the method comprising the following steps:

providing a plurality of test points in a computer program, including;

grouping lines of code of the computer program into functional blocks; and

identifying inputs and outputs for each functional block;

defining at least one fault propagation path, the at least one fault propagation path associating at least two of the plurality of test points in an order of data flow and data dependency within the computer program including;

creating a block diagram showing the interconnectivity of the functional blocks;

identifying a plurality of fault propagation paths in the block diagram, each fault propagation path indicating a flow of data or program operation through a number of the functional blocks;

defining a run time test point data file, the run time test point data file storing output values of test points during execution of the computer program; and

defining a dependency set matrix, the dependency set matrix defining at least one fault propagation path;

generating expected values for the plurality of test points for an expected, proper-operation execution of the computer program;

executing the computer program on a computer to thereby generate actual values for the plurality of test points;

comparing the expected values for the plurality of test points with the actual values for the plurality of test points;

identifying a plurality of failed test points, each failed test point having an actual value which does not correspond with an expected value for the test point; and

finding, for the at least one fault propagation path, the source failure test point which is earliest, relative to other failure test points in the at least one fault propagation path, in an order of data flow and data dependency.

23. The method as set forth in claim 22, wherein the step of generating expected values for the plurality of test points comprises a step of defining a reference test point data file, the reference test point data file storing the expected values for the plurality of test points.

24. The method as set forth in claim 22, wherein the step of executing the computer program on a computer to thereby generate actual values for the plurality of test points comprises a step of storing output values of test points in the run time test point data file.

25. The method as set forth in claim 24, wherein the step of comparing the expected values for the plurality of test points with the actual values for the plurality of test points comprises a step of correlating the reference test point data file with the run time test point data file.

26. The method as set forth in claim 25, wherein the step of identifying a plurality of failed test points comprises the following steps:

defining a run time pass/fail matrix, the run time pass/fail matrix being adapted to store the plurality of failed test points; and

writing the plurality of failed test points to the run time pass/fail matrix.

27. The method as set forth in claim 26, wherein the step of finding the source failure test point comprises a step of determining which fault propagation paths contain failed test points, using the dependency set matrix.

28. The method as set forth in claim 27, wherein the step of finding the source failure test point further comprises a step of locating the at least one source failure test point in the plurality of failed test points, using the fault propagation paths in the dependency set matrix that were determined to contain failed test points.

29. The method as set forth in claim 26, wherein the step of finding the source failure test point comprises the following steps:

defining a fault detection set matrix, the fault detection set matrix being adapted to store fault propagation paths therein;

storing the fault propagation paths that contain failed test points in the fault detection set matrix;

determining which fault propagation paths in the fault detection set matrix contain the same failed test points; and

locating the at least one source failure test point in the plurality of failed test points using the fault propagation path that contain failed test points.

30. A method of determining a source failure test point from a plurality of test points in a computer program, the source failure test point having a highest probability relative to other test points in the computer program of being a source of failure, the method comprising the following steps:

determining a sequential flow of data among a plurality of test points in a computer program, including;

grouping lines of code of the computer program into functional blocks;

identifying inputs and outputs for each functional blocks; and

creating a block diagram showing the interconnectivity of the functional blocks;

ranking the plurality of test points, using the determined sequential flow of data, in an order of an earliest test point in the determined sequential flow of data to a last test point in the determined sequential flow of data, to thereby generate a ranked set of test points, the step of ranking including;

identifying dependency sets in the block diagram, each dependency set indicating a flow of data or program operation through a number of the functional blocks;

defining a run time point data file, the run time test point data file storing output values of test points during execution of the computer program; and

defining a dependency set matrix, the dependency set matrix defining at least one dependency set;

generating expected values for the plurality of test points for an expected, proper-operation execution of the computer program;

executing the computer program on a computer to thereby generate actual values for the plurality of test points;

comparing the expected values for the plurality of test points with the actual values for the plurality of test points;

identifying a plurality of failed test points from among the plurality of test points, each failed test point having an actual value which does not correspond with an expected value for the test point and thereby indicating an erroneous program operation or result of the computer program at the failed test point; and

determining a failed test point of the plurality of failed test points which ranks earliest among failed test points in the ranked set of test points, the earliest-ranked failed test point being the source failure test point.

31. The method as set forth in claim 30, wherein the step of generating expected values for the plurality of test points comprises a step of defining a reference test point data file, the reference test point data file storing the expected values for the plurality of test points.

32. The method as set forth in claim 31, wherein the step of executing the computer program on a computer to thereby generate actual values for the plurality of test points comprises a step of writing output values of test points to the run time test point data file.

33. The method as set forth in claim 32, wherein the step of comparing the expected values for the plurality of test points with the actual values for the plurality of test points comprises a step of correlating the reference test point data file with the run time test point data file.

34. The method as set forth in claim 33, wherein the step of identifying a plurality of failed test points comprises the following steps:

defining a run time pass/fail matrix, the run time pass/fail matrix being adapted to store the plurality of failed test points; and

writing the plurality of failed test points to the run time pass/fail matrix.

35. The method as set forth in claim 34, wherein the step of locating at least one source failure test point in the plurality of failed test points comprises the following steps:

defining a fault detection set matrix, the fault detection set matrix being adapted to store dependency sets therein;

storing the dependency sets that contain failed test points in the fault detection set matrix;

determining which dependency sets in the fault detection set matrix contain the same failed test points; and

locating the at least one source failure test point in the plurality of failed test points using the dependency sets that contain failed test points.

36. The method as set forth in claim 34, wherein the step of locating at least one source failure test point in the plurality of failed test points comprises the following steps:

determining which dependency sets contain failed test points, using the dependency set matrix; and

locating the at least one source failure test point in the plurality of failed test points, using the dependency sets in the dependency set matrix that were determined to contain failed test points.

38. The method as set forth in claim 31, wherein the step of generating expected values for the plurality of test points comprises a step of defining a reference test point data file, the reference test point data file storing the expected values for the plurality of test points.

39. The method as set forth in claim 38, wherein the step of executing the computer program on a computer to thereby generate actual values for the plurality of test points comprises a step of storing output values of test points in the run time test point data file.

40. The method as set forth in claim 39, wherein the step of comparing the expected values for the plurality of test points with the actual values for the plurality of test points comprises a step of correlating the reference test point data file with the run time test point data file.

41. The method as set forth in claim 40, wherein the step of identifying at least two failed test points comprises the following steps:

defining a run time pass/fail matrix, the run time pass/fail matrix being adapted to store the plurality of failed test points; and

entering the plurality of failed test points in the run time pass/fail matrix.

42. The method as set forth in claim 41, wherein the step of associating the at least two failed test points with the at least one data propagation path comprises a step of determining which data propagation paths contain failed test points, using the dependency set matrix.

43. The method as set forth in claim 42, wherein the step of locating the source failure test point comprises a step of locating the source failure test point, using the data propagation paths in the dependency set matrix that were determined to contain failed test points.

37. A method of locating a source failure test point among a plurality of test points, the source failure test point having a greatest probability of being a source of failure in a computer program, the method comprising the following steps:

placing a plurality of test points into a computer program;

determining an order of data flow among the plurality of test points, the order of data flow defining at least one data propagation path among the plurality of test points, the step of determining including;

grouping lines of code of the computer program into functional blocks;

identifying inputs and outputs for each functional block;

creating a block diagram showing the interconnectivity of the functional blocks;

identifying data propagation paths in the block diagram, each data propagation path defining a fault propagation path, which indicates a flow of data or program operation through a number of functional blocks;

defining a run time test point data file, the run time test point data file storing output values of test points during execution of the computer program; and

defining a dependency set matrix, the dependency set matrix defining at least one data propagation path;

generating expected values for the plurality of test points for an expected, proper-operation execution of the computer program;

executing the computer program on a computer to thereby generate actual values for the plurality of test points;

comparing the expected values for the plurality of test points with the actual values for the plurality of test points;

identifying at least two failed test points from the plurality of test points, each failed test point having an actual value which does not correspond with an expected value for the test point; and

associating the at least two failed test points with the at least one data propagation path; and

locating the source failure test point from among the at least two associated failed test points by selecting a failed test point which is earliest in the at least one data propagation path.