vta

Documentation

Overview

Package vta computes the call graph of a Go program using the Variable Type Analysis (VTA) algorithm originally described in "Practical Virtual Method Call Resolution for Java," Vijay Sundaresan, Laurie Hendren, Chrislain Razafimahefa, Raja Vallée-Rai, Patrick Lam, Etienne Gagnon, and Charles Godin.

Note: this package is in experimental phase and its interface is subject to change. TODO(zpavlinovic): reiterate on documentation.

The VTA algorithm overapproximates the set of types (and function literals) a variable can take during runtime by building a global type propagation graph and propagating types (and function literals) through the graph.

A type propagation is a directed, labeled graph. A node can represent one of the following:

• A field of a struct type.
• A local (SSA) variable of a method/function.
• All pointers to a non-interface type.
• The return value of a method.
• All elements in an array.
• All elements in a slice.
• All elements in a map.
• All elements in a channel.
• A global variable.

In addition, the implementation used in this package introduces a few Go specific kinds of nodes:

• (De)references of nested pointers to interfaces are modeled as a unique nestedPtrInterface node in the type propagation graph.
• Each function literal is represented as a function node whose core value is the (SSA) representation of the function. This is done to precisely infer flow of higher-order functions.

Edges in the graph represent flow of types (and function literals) through the program. That is, the model 1) typing constraints that are induced by assignment statements or function and method calls and 2) higher-order flow of functions in the program.

The labeling function maps each node to a set of types and functions that can intuitively reach the program construct the node represents. Initially, every node is assigned a type corresponding to the program construct it represents. Function nodes are also assigned the function they represent. The labeling function then propagates types and function through the graph.

The result of VTA is a type propagation graph in which each node is labeled with a conservative overapproximation of the set of types (and functions) it may have. This information is then used to construct the call graph. For each unresolved call site, vta uses the set of types and functions reaching the node representing the call site to create a set of callees.

Index

• func CallGraph(funcs map[*ssa.Function]bool, initial *callgraph.Graph) *callgraph.Graph

Functions

func CallGraph

func CallGraph(funcs map[*ssa.Function]bool, initial *callgraph.Graph) *callgraph.Graph

CallGraph uses the VTA algorithm to compute call graph for all functions f:true in funcs. VTA refines the results of initial call graph and uses it to establish interprocedural type flow. If initial is nil, VTA uses a more efficient approach to construct a CHA call graph.

The resulting graph does not have a root node.

CallGraph does not make any assumptions on initial types global variables and function/method inputs can have. CallGraph is then sound, modulo use of reflection and unsafe, if the initial call graph is sound.