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.