proposal: x/tools/go/ssa/ssautil: Reachable: conservative approximation to reachable functions, runtime types

[adonovan]

Background: The existing ssautil.AllFunctions helper performs a reachability analysis starting from all the packages in a Go SSA program, and returns the set of functions it encounters:

package ssautil

func AllFunctions(prog *ssa.Program) map[*ssa.Function]bool

Unfortunately it is poorly defined and its implementation is a bit of a historical mess; it is complicated and delivers results that are simultaneously "too much" (imprecise) and "too little" (unsound).

An example of imprecision is that it searches the body of every function in the ssa.Program for MakeInterface operations, when only those functions that are reachable from the entry points need be considered. Another example is that it uses all packages of the program as roots for reachability, even though typically the program consists of all dependencies of a few packages of interest.

An example of unsoundness is that it doesn't consider all of the types derivable from the public API of a package as potential dynamic call targets.

Furthermore, its traversal is a lost opportunity to to track information ("address-taken" status of functions) that would be useful to CHA and VTA.

Proposal: We propose to add a new function ssautil.Reachable that:

• is derived from first principles
• is analytically sound (conservative)
• returns additional information useful to CHA, VTA, and vulncheck, that will improve the precision of their results while reducing their running time.

We plan to redefine the existing AllFunctions as a shallow wrapper around the new function.

package ssautil

// Reachable returns a conservative approximation to the set of
// functions and runtime types that are potentially reachable from the
// specified packages (which need not form a whole program).
//
// Any source function in package P that is not among the functions
// (map keys) returned by Reachable(P) is unreachable ("dead
// code"--though for dead-code analysis of whole programs, we
// recommend the more precise RTA).
// Beware: the values of the functions map are not all "true": the
// result is a mapping from functions to their "address-taken" status.
//
// The runtime types returned by Reachable are those that are
// potentially converted to interfaces, making them potential targets
// of interface method calls.
//
// The results are computed using the following algorithm.
//
// First, we tabulate a set of initial functions and runtime types
// from the specified packages.
//
// For packages named "main", the initial functions are the entry
// points: the main function and the synthetic package initializer.
// There are no initial runtime types.
//
// For importable packages, the initial functions include the package
// initializer and all exported non-parameterized functions; these
// functions are assumed to be potentially callable from external
// packages not visible to the analysis. The initial runtime types are
// the types of every exported non-parameterized declaration; these
// types are accessible to reflection from external packages.
//
// Second, we compute a fixed point of the following induction rules:
//
//  1. Each function's instructions are analyzed. Any function
//     referenced by an instruction is added to the set. Any
//     non-interface type used as the operand of a MakeInterface
//     instruction is added to the set of runtime types.
//
//  2. Each type is analyzed. Every element type found by recursively
//     removing type constructors is added to the set of runtime types.
//
//  3. For each type in the set, its methods are added to the set of functions.
//
// The initial exported functions are all assumed to be
// "address-taken", making them candidate targets of dynamic function
// calls. All methods found by rule 3 are similarly considered
// address-taken. Functions found by rule 1 are considered
// address-taken unless they are used in the call position of an
// [ssa.CallInstruction].
//
// Finally, it returns the final sets of functions and runtime types.
//
// For best results, provide packages from a Program constructed with the
// [ssa.InstantiateGenerics] mode flag.
func Reachable(pkgs []*ssa.Package) (functions map[*ssa.Function]bool, runtimeTypes *typeutil.Map)

@timothy-king @zpavlinovic

[gabyhelp]

Related Issues and Documentation

• x/tools/go/ssa/ssautil: deprecate AllFunctions #69231

_{(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)}

[gopherbot]

Change https://go.dev/cl/609281 mentions this issue: go/callgraph/cha: make CHA, VTA faster and more precise

[zpavlinovic]

... // First, we tabulate a set of initial functions and runtime types // from each package in the program.

I guess you mean pkgs here?

... // For best results, provide a Program constructed with the // [ssa.InstantiateGenerics] mode flag. func Reachable(pkgs []ssa.Package) (functions map[ssa.Function]bool, runtimeTypes *typeutil.Map)

Ditto?

[gopherbot]

Change https://go.dev/cl/610939 mentions this issue: go/ssa: extract type recursion into a helper package

[gopherbot]

Change https://go.dev/cl/611535 mentions this issue: internal/callgraph/chautil: add Reachable function

[rsc]

This proposal has been added to the active column of the proposals project and will now be reviewed at the weekly proposal review meetings. — rsc for the proposal review group