Callpath finder

Patent metadata

Field	Value
Publication number	US-10042746-B2
Application number	US-201514963841-A
Country	US
Kind code	B2
Filing date	Dec 9, 2015
Priority date	Nov 19, 2013
Publication date	Aug 7, 2018
Grant date	Aug 7, 2018

Abstract

Techniques and systems for creating a function call graph for a codebase are disclosed. Graph creation includes identifying functions in the codebase by a function signature and representing a function as a first node in the call graph. For that function, identifying call-to functions, call-from functions, and inheritance parents and children, and a base class from the function signature of that function; adding child nodes to the first node based on the identified call-to and call-from functions; for an interface call to a base class method in the function, adding child nodes to the first node based on implementations of an override of the base class method; for an added child node, removing that child node from the first node if a source file that includes an implementation of an override and a source code file that includes the function don't share at least one common binary file.

First claim

The invention claimed is:

1. A method of determining a likely call path between two functions in a code base, the method comprising:
receiving, as inputs, a source function and a destination function;
identifying, in a function call graph, a starting node associated with the source function and an ending node associated with the destination function;
searching possible paths in the function call graph between the starting node and the ending node, said searching including, for each node at a level of the graph:
evaluating the node against a list of common dependencies shared by the starting node and the ending node;
for an evaluated node having a dependency included in the list of common dependencies, including the evaluated node in a possible path list;
for an evaluated node not having a dependency included in the list of common dependencies, excluding the evaluated node from any possible path list;

ranking the nodes included in the possible path list;
for each ranked node, expanding the ranked node to determine if the ranked node includes child nodes;
responsive to a determination that the ranked node has child nodes, treating the ranked node as a starting node and performing said searching possible paths for each child node of the ranked node; and
responsive to a determination that the ranked node has no child nodes, identifying a function call path including the ranked node as a possible function call path;
sorting the possible function call paths between the starting node and the ending node; and
returning, as a likely call path, at least one of the sorted possible function call paths.

2. The method of claim 1 , the said sorting all possible function call paths including:
ordering said all possible function call paths from shortest to longest;
identifying, from among the ordered function call paths, those function call paths entirely within a single codebase;
applying weight factors to the ordered function call paths such that said all possible function call paths are ordered from most likely to least likely based on function call path length and weight factor, the weight factor including indicating as more likely those function call paths entirely within a single codebase; and
returning, as a likely call path, at least the most likely function call path after said applying weight factors.

3. The method of claim 2 , said applying weight factors including generating weight factors based on historical trace data generated from previous function executions such that function call paths indicated by the historical trace data are associated with weight factors indicating those function call paths as more likely.

4. The method of claim 2 , said applying weight factors including applying class-based weight factors such that call paths including commonly used object classes will be indicated as more likely.

5. The method of claim 1 , said searching possible paths including performing a bi-directional search originating from both the starting and ending nodes.

6. The method of claim 1 , said evaluating the node against a list of common dependencies including applying a Bloom filter associated with the node to at least one binary file compiled from a source code file that includes at least one of the source function and the destination function;
the node being evaluated as having a dependency included in the list of common dependencies in response to said at least one binary file passing the applied Bloom filter.

7. The method of claim 6 , the method further comprising:
in response to a determination that at least one of the source function and the destination function are remote procedure calls, said Bloom filter being configured to pass those binary files that include at least one of the source function and the destination function;
in response to a determination that at least one of the source function and the destination function are not remote procedure calls, said Bloom filter being configured to pass those binary files that include both of the source function and the destination function.

8. The method of claim 6 , where a size of the Bloom filter is based on a number of binary files the Bloom filter is configured to pass.

9. A non-transitory computer-readable medium having embodied thereon instructions for causing one or more processors to execute a method of determining a likely call path between two functions in a code base, the method comprising:
receiving, as inputs, a source function and a destination function;
identifying, in a function call graph, a starting node associated with the source function and an ending node associated with the destination function;
searching possible paths in the function call graph between the starting node and the ending node, said searching including, for each node at a level of the graph:
evaluating the node against a list of common dependencies shared by the starting node and the ending node;
for an evaluated node having a dependency included in the list of common dependencies, including the evaluated node in a possible path list;
for an evaluated node not having a dependency included in the list of common dependencies, excluding the evaluated node from any possible path list;

ranking the nodes included in the possible path list;
for each ranked node, expanding the ranked node to determine if the ranked node includes child nodes;
responsive to a determination that the ranked node has child nodes, treating the ranked node as a starting node and performing said searching possible paths for each child node of the ranked node; and
responsive to a determination that the ranked node has no child nodes, identifying a function call path including the ranked node as a possible function call path;

sorting the possible function call paths between the starting node and the ending node; and
returning, as a likely call path, at least one of the sorted possible function call paths.

10. The non-transitory computer-readable medium of claim 9 , the said sorting all possible function call paths including:
ordering said all possible function call paths from shortest to longest;
identifying, from among the ordered function call paths, those function call paths entirely within a single codebase;
applying weight factors to the ordered function call paths such that said all possible function call paths are ordered from most likely to least likely based on function call path length and weight factor, the weight factor including indicating as more likely those function call paths entirely within a single codebase; and
returning, as a likely call path, at least the most likely function call path after said applying weight factors.

11. The method of claim 9 , said applying weight factors including generating weight factors based on historical trace data generated from previous function executions such that function call paths indicated by the historical trace data are associated with weight factors indicating those function call paths as more likely.

12. The non-transitory computer-readable medium of claim 9 , said applying weight factors including applying class-based weight factors such that call paths including commonly used object classes will be indicated as more likely.

13. The non-transitory computer-readable medium of claim 9 , said searching possible paths including performing a bi-directional search originating from both the starting and ending nodes.

14. The non-transitory computer-readable medium of claim 9 , said evaluating the node against a list of common dependencies including applying a Bloom filter associated with the node to at least one binary file compiled

Assignees

• Google Inc
• Google Llc

Inventors

• Rajanna Ramakrishna
• Gupta Deepank
• Velayutham Arul Siva Murugan
• Sheopory Abhishek
• Agarwal Ankit

Classifications

• G06F11/3676

  for coverage analysis · CPC title

• G06F8/70 Primary

  Software maintenance or management · CPC title

• G06F8/43 Primary

  Checking; Contextual analysis · CPC title

• G06F11/3688 Primary

  for test execution, e.g. scheduling of test suites · CPC title

• G06F8/75

  Structural analysis for program understanding · CPC title