Methods for selectively pruning false paths in graphs that use high-precision state information
View Patent ↗Methods are provided that allow a false path pruner to traverse a directed acyclic graph in conjunction with one or more checker programs that are analyzing a program for defects or other artifacts of interest. While the checkers may have ways of avoiding re-traversal of portions of the graph that have already been traversed, the false path pruner may override such decisions made by the checkers as a result of a false path in order to allow re-traversal during a future different traversal when that same defect or artifact may not lie along a false path, and therefore avoid missing a valid defect or artifact. Computer programs stored on tangible media are provided that implement the methods of the invention.
1. An automated method of analysis of computer program code comprising:
providing a graph structure in computer readable memory that represents control flow of the computer program code;
using a first checker program to traverse a first path within the graph and to check for an occurrence of a first trigger in the course of the traversal of the first path;
detecting by the first checker, a trigger associated with a trigger node on the first path;
using a false path detection program to determine whether the first path is a false path;
if the false path detection program determines that the first path is a false path, then determining a false path signature comprising a combination of traversal history elements that causes the first path to be a false path and determining a first enabler node on the first path that contributes the first history element in the false path signature;
annotating nodes between the trigger and the first enabler with a traversal state;
wherein any history elements in the false path signature that are in the history of the node being annotated are included in the traversal state for that node;
wherein any history elements in the false path signature that are not in the history of the node being annotated are omitted from the traversal state for that node;
wherein if any history elements in the false path signature are omitted from the traversal state for the node being annotated, a current assignment state is included in the traversal state for each variable in the history elements in the false path signature that were included in the traversal state for the node being annotated;
using the first checker program to traverse a second path within the graph and to check for an occurrence of a first trigger in the course of the traversal of the second path;
wherein the second path merges with the first path at or above the first node and below the first enabler node;
determining by the first checker that the first checker previously traversed a portion of the second path that merges with the first path in a checker state that is the same as a current checker state of the first checker;
comparing a traversal state indicated by the annotation of the first node with a history of the second path;
comparing an assignment state of the first variable indicated by the annotation of the first node with a current assignment state of the first variable associated with the first node in the history of the second path;
if both the comparison steps result in finding matches then ending the traversal of the second path by the first checker; and
if at least one of the comparison steps does not find a match, then continuing the traversal of the second path by the first checker.