README
¶
Unification based pointer analysis for Go
This repository contains a Go adaptation of Steensgaard's pointer analysis algorithm. The result of the static analysis can be used to determine the set of objects that a variable may point to at run-time. It can also be used to construct a call graph where dynamically dispatched calls have been resolved using the computed points-to information.
Analysis details
The analysis is field-sensitive, context-insensitive, and aims to be sound.
Due to field-sensitivity the analysis cannot run in $O(n\cdot\alpha(n))$ time (where $n$ is the size of the program), which is the runtime of the algorithm presented in the paper. Other details, such as handling dynamic dispatch for interface methods, also prevent us from obtaining the above runtime. It should still be fast, though. The goal is that this implementation should be significantly faster than the implementation of Andersen's pointer analysis algorithm provided by the Go team (with a precision trade-off).
This implementation makes many of the same design choices as the implementation of Andersen's algorithm. Notably, arrays (and slices) are modelled as having 1 element, conversions using unsafe.Pointer are not modelled soundly, and the effects of opaque code (runtime, Cgo, etc.) are under-approximated. The API is also similar.
Contrary to the implementation of Andersen's algorithm, no special modelling is offered for reflection (which is available under a flag there). Also, in this implementation constraint generation is interleaved with constraint solving. This makes it easy to only generate constraints for reachable code, which the Andersen implementation does not do.
Documentation
¶
Overview ¶
Package pointer provides a Go adaptation of Steensgaard's pointer analysis algorithm.
Example ¶
package main
import (
"fmt"
"strings"
"github.com/BarrensZeppelin/pointer"
"github.com/BarrensZeppelin/pointer/pkgutil"
"golang.org/x/tools/go/ssa"
"golang.org/x/tools/go/ssa/ssautil"
)
func main() {
// Parse example program.
pkgs, err := pkgutil.LoadPackagesFromSource(
`package main
func main() {
ch := make(chan int, 1)
ch <- 10
}`)
if err != nil {
fmt.Println(err)
return
}
// Create SSA-form program representation.
prog, spkgs := ssautil.AllPackages(pkgs, ssa.InstantiateGenerics)
// Build SSA code for bodies of all functions in the whole program.
prog.Build()
// Get a reference to the main package.
mainPkg := spkgs[0]
// Run the pointer analysis with the main package as entrypoint.
result := pointer.Analyze(pointer.AnalysisConfig{
Program: prog,
EntryPackages: []*ssa.Package{mainPkg},
})
for _, block := range mainPkg.Func("main").Blocks {
for _, insn := range block.Instrs {
if send, ok := insn.(*ssa.Send); ok {
// Print the allocation sites of the channels that are sent on.
var labels []string
for _, ptr := range result.Pointer(send.Chan).PointsTo() {
site := ptr.Site()
labels = append(labels,
fmt.Sprintf(" %v %s", prog.Fset.Position(site.Pos()), site))
}
fmt.Printf("Send on channels:\n%s", strings.Join(labels, "\n"))
}
}
}
}
Output: Send on channels: /fake/testpackage/main.go:3:14 make chan int 1:int
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
var ErrNotImplemented = errors.New("not implemented")
Functions ¶
func PointerLike ¶
func PrintSSAFun ¶
Types ¶
type AllocationSite ¶
type AllocationSite struct {
// contains filtered or unexported fields
}
func (AllocationSite) Path ¶
func (a AllocationSite) Path() string
func (AllocationSite) Site ¶
func (a AllocationSite) Site() ssa.Value
func (AllocationSite) Type ¶
func (a AllocationSite) Type() types.Type
type AnalysisConfig ¶
type AnalysisConfig struct {
Program *ssa.Program
// Functions in this list will be treated as program entry points.
EntryFunctions []*ssa.Function
// Packages in this list will have their main & init functions treated as
// program entry points.
EntryPackages []*ssa.Package
// When TreatMethodsAsRoots is true, all methods of all types in
// prog.RuntimeTypes() are implicitly called.
TreatMethodsAsRoots bool
// Bind free variables when a closure is created instead of when it is
// called. This makes the result less precise for bound methods that are
// not called.
BindFreeVarsEagerly bool
}
type ElementPointer ¶
type ElementPointer struct {
// contains filtered or unexported fields
}
func (ElementPointer) Path ¶
func (ep ElementPointer) Path() string
func (ElementPointer) Site ¶
func (ep ElementPointer) Site() ssa.Value
func (ElementPointer) Type ¶
func (ep ElementPointer) Type() types.Type
type FieldPointer ¶
type FieldPointer struct {
Field int
// contains filtered or unexported fields
}
func (FieldPointer) Path ¶
func (fp FieldPointer) Path() string
func (FieldPointer) Site ¶
func (fp FieldPointer) Site() ssa.Value
func (FieldPointer) Type ¶
func (fp FieldPointer) Type() types.Type
type Label ¶
type Label interface {
// Allocation site of the object denoted by the label.
Site() ssa.Value
// Returns an access path to the object that is compatible with the paths
// provided for labels in the Go team implementation of Andersen's pointer
// analysis. Specifically field names are resolved from ssa indices.
Path() string
// Returns the type of a pointer pointing to the object denoted by the
// label. (Label).Type().Underlying() == (*types.Pointer) except for
// allocation sites for slices (where the returned type is (*types.Slice)).
Type() types.Type
}
Label denotes an abstract object. A label is either an AllocationSite, representing the object allocated at a given instruction, or a FieldPointer & ElementPointer, representing a subobject of another object (field of a struct or element of slice/array, respectively).
type Pointer ¶
type Pointer struct {
// contains filtered or unexported fields
}
A Pointer is an equivalence class of pointer-like values.
func (Pointer) Deref ¶ added in v0.2.4
Deref returns the abstract pointer associated with the value that is pointed to by the receiver.
type Result ¶
type Result struct {
// Reachable contains all function discovered during analysis.
Reachable map[*ssa.Function]bool
// contains filtered or unexported fields
}
Result exposes some public members and an API to query analysis results.
func Analyze ¶
func Analyze(config AnalysisConfig) Result
func (*Result) CallGraph ¶
CallGraph returns a call graph for the analysed program. Dynamically dispatched calls are resolved using the results of the pointer analysis.
Source Files
Directories