README
¶
Unification based pointer analysis for Go
This repository contains a Go adaptation of Steensgaard's pointer analysis algorithm.
The analysis is field-sensitive and context-insensitive.
Having field-sensitivity means that 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.) is 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
¶
Index ¶
- Variables
- func FieldIndex(t *types.Struct, fieldName string) int
- func PointerLike(t types.Type) bool
- func PrintSSAFun(fun *ssa.Function)
- type AllocationSite
- type AnalysisConfig
- type Array
- type Chan
- type Closure
- type ElementPointer
- type FieldPointer
- type Fresh
- type Interface
- type Label
- type Map
- type Pointer
- type PointsTo
- type Result
- type Struct
- type Term
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.
// This is mainly useful for soundness comparison with the analysis in
// "golang.org/x/tools/go/pointer" which does the same thing.
TreatMethodsAsRoots 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.
type Result ¶
type Result struct {
// Reachable contains all function discovered during analysis.
Reachable map[*ssa.Function]bool
CallGraph *callgraph.Graph
// contains filtered or unexported fields
}
Result exposes some public members and an API to query analysis results.
func Analyze ¶
func Analyze(config AnalysisConfig) Result
Source Files
Directories