Rule-based method for testing of programming segments

• US 5,297,150 A
• Filed: 06/17/1992
• Issued: 03/22/1994
• Est. Priority Date: 06/17/1992
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Clark, Andrew L.
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): TU, CHRISTINE TRINH LE
• Application Number:
  US07/900,169
• Time in Patent Office: 643 Days
• Field of Search: 371/19, 371/15.1, 371/29.1, 364/275.5, 364/184, 364/275.6, 364/944.6, 395/575, 395/922, 395/919, 395/916
• US Class Current: 714/26
• CPC Class Codes: G06F 11/3608 using formal methods, e.g. model checking, abstract interpretation theorem proving G06N5/013
• CPC Class Codes: G06F 11/3664 Environments for testing or debugging software
• CPC Class Codes: Y10S 706/922 Computer program preparation

Abstract

A method for determining a set of f low paths in a code listing that are most likely to fail comprises the steps of: converting the code listing to a directed acyclic graph representation, the representation including nodes and directed edges, each node representing a basic block of unconditional code statements. The method loads, as facts into a knowledge base, representations of the nodes and edges, and unconditional statements from the basic blocks. The method also loads, as rules into the knowledge base, conditional statements and complexity indicator values for conditional and unconditional statements. Weights are assigned to each node based upon complexity indicator values for statements associated with the node. A determination is then made of a set of flow paths through the code listing, each path ranked in order of assigned weights, those flow paths with larger assigned weights being assumed as those paths most likely to fail.

Claims

1. A method for determining a set of flow paths in a code listing as being the most likely ones to fail, the method comprising the steps of:

(a) converting said code listing to a directed acyclic graph (DAG) representation, said DAG including nodes and directed edges, each node representing a basic block of unconditional code statements, a basic block being a code listing that terminates at an exit point once commencing at a starting point, a said exit point being an exit code statement or a conditional code statement, each edge representing an action taken upon the occurrence of a condition in a said conditional code statement;

(b) loading as facts into a knowledge base, said nodes and directed edges from said DAG and unconditional code statements from each said basic block'"'"'s code listing;

(c) loading as rules into said knowledge base, conditional statements from said code listing and determined complexity indicator values for conditional and unconditional code statements;

(d) assigning a weight in each node based upon a combination of complexity indicator values for conditional and unconditional code statements associated with a said node; and

(e) determining a set of ranked flow paths through said code listing by employing said facts and rules, said flow paths ranked in order by analysis of each flow path'"'"'s nodal weights, those flow paths with weights indicating greater complexity being those most likely to fail.

2. The method as recited in claim 1 wherein said determining step (e) is based upon an accumulation of nodal weights in each flow path.

3. The method as recited in claim 1 wherein said complexity indicator values recited in step (c) for each statement comprise indications of the kind and number of logical operators in each said statement.

4. The method as recited in claim 1 wherein said complexity indicator values for conditional statements, are recited in step (c), comprises the number of conditions required to lead to a branch action or actions.

5. The method as recited in claim 1 wherein said complexity indicator values for conditional statements recited in step (c) comprise the number of branches that are indicated by each said conditional statement.

6. The method as recited in claim 1 wherein said assigned weight to a said node is based upon a sum of complexity indicator values of conditional and unconditional statements associated with a said node.

7. The method as recited in claim 1 wherein step (c) further comprises loading as rules, heuristics that determine complexity indicator values based upon a plurality of determined statement characteristics, said characteristics giving rise to complexity of function.

8. The method as recited in claim 7 wherein step (e) further comprises:

searching flow paths in said code listing and summing nodal weights for each found flow path to arrive at a total nodal weight sum for each said found flow path.

9. The method as recited in claim 8 wherein step (e) further comprises:

iterating through a plurality of heuristics in the performance of the search of the flow paths;

modifying assigned nodal weights in accordance with findings that result from individual heuristics; and

summing said nodal weights in each path for each said heuristic, whereby a set of nodal weight sums for each path are produced for each said heuristic.

10. The method as recited in claim 1 further comprising the step of:

(f) displaying a graphical representation of flow paths in said code listing, and providing an indication in said graphical representation indicating those flow paths most likely to fail.

11. A data processing system that identifies a set of flow paths in a code listing as being the most likely ones to fail, said system comprising:

means for converting said code listing to a directed acyclic graph (DAG) representation, said DAG including nodes and directed edges, each node representing a basic block of unconditional code statements that ends with an exit code statement or a conditional code statement and each edge representing an action taken upon the occurrence of a condition in a conditional statement that terminates a basic block;

memory means, coupled to said means for converting, for including a knowledge base having facts and rules, said facts including said nodes and directed edges from said DAG and unconditional statements from each said basic block'"'"'s code listing, said rules including conditional statements from said code listing and determined complexity indicator values for said conditional and unconditional statements; and

means coupled to said memory means for assigning a weight to each node based upon a combination of complexity indicator values for conditional and unconditional statements associated with said node, said data processing system determining a set of ranked flow paths through said code listing by employing said facts and rules, said flow paths ranked in order by analysis of each flow path'"'"'s nodal weights, those flow paths with weights indicating greater complexity being those most likely to fail.

12. The system as recited in claim 11 wherein said data processing system determines said set of ranked flow paths based upon an accumulation of nodal weights in each flow path.

13. The system as recited in claim 11 wherein said complexity indicator value for each statement comprises an indication of the kind and number of logical operators in each said statement.

14. The system as recited in claim 11 wherein said complexity indicator values for conditional statements comprises the number of conditions required to lead to a branch action or actions.

15. The system as recited in claim 11 wherein said complexity indicator values for conditional statements comprise the number of branches that are indicated by each said conditional statement.

16. The system as recited in claim 11 wherein said assigned weight to a node is based upon a sum of complexity indicator values of conditional and unconditional statements associated with said node.

17. The system as recited in claim 11 wherein said data processing system searches flow paths in said code listing and sums nodal weights for each found flow path to arrive at a total nodal weight sum for each said found flow path.

18. The system as recited in claim 17 wherein said processor means iterates through a plurality of heuristics in the performance of the search of flow paths, modifies assigned nodal weights in accordance with findings that result from individual heuristics, and sums said nodal weights in each path for each said heuristic, whereby a set of nodal weight sums for each path are produced for each said heuristic.

19. The system as recited in claim 11 further comprising means for displaying a graphical representation of flow paths in said code listing, and providing an indication in said graphical representation indicating those flow paths most likely to fail.