dataflow

package
v0.1.0-alpha.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Apr 3, 2024 License: Apache-2.0 Imports: 28 Imported by: 0

Documentation

Overview

Package dataflow implements the core of the dataflow analysis. In order to run the taint or the backwards analysis, you should first run the steps to build the inter-procedural dataflow graph.

The first object to build is an instance of the AnalyzerState with some basic analyses's results already computed. Assuming you have a program prog, configuration cfg and logger log, you can build an initialized state for your program using the NewInitializedAnalyzerState function: 

state, err := dataflow.NewInitializedAnalyzerState(log, cfg, prog)

This initialization runs the pointer analysis on the program, as well as a scanning step for global variables, interface method implementations and variable bounding information.

To build the dataflow summary of a single function, run the IntraProceduralAnalysis function, which runs the intra-procedural analysis on the function: 

id := 0 // some id for the summary
isEntryPoint // some function that identifies entry points for your analyses
postBlockCallBack // optional, some function that get called after each block is analyzed
shouldBuildSummary // this indicates when the summary should be built, as opposed to simply be created
dataflow.IntraProceduralAnalysis(state, function, shouldBuildSummary, id, isEntryPoint, postBlockCallback)

Package dataflow contains abstractions for reasoning about data flow within programs.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func AccessPathsOfType 

func AccessPathsOfType(t types.Type) []string

AccessPathsOfType returns a slice of all the possible access paths that can be used on a value of type t. For example, on a value of type struct{A: map[T]S, B: string} the possible access paths are ".A", ".B", ".A[*]"

func CallGraphReachable 

func CallGraphReachable(cg *callgraph.Graph, excludeMain bool, excludeInit bool) map[*ssa.Function]bool

CallGraphReachable returns a map where each entry is a reachable function

func CheckClosureReturns 

func CheckClosureReturns(returnNode *ReturnValNode, closureNode *ClosureNode) bool

CheckClosureReturns returns true if returnNode's summary is the same as closureNode's.

func CheckIndex 

func CheckIndex(c *AnalyzerState, node IndexedGraphNode, callSite *CallNode, msg string) error

CheckIndex checks that the indexed graph node is valid in the parent node call site

func CheckNoGoRoutine 

func CheckNoGoRoutine(s *AnalyzerState, reportedLocs map[*ssa.Go]bool, node *CallNode)

CheckNoGoRoutine logs a message if node's callsite is a goroutine.

func ComputeMethodImplementations 

func ComputeMethodImplementations(p *ssa.Program, implementations map[string]map[*ssa.Function]bool,
	contracts map[string]*SummaryGraph, keys map[string]string) error

ComputeMethodImplementations populates a map from method implementation type string to the different implementations corresponding to that method. The map can be indexed by using the signature of an interface method and calling String() on it. If the provided contracts map is non-nil, then the function also builds a summary graph for each interface method such that contracts[methodId] = nil

func DoPointerAnalysis 

func DoPointerAnalysis(p *ssa.Program, functionFilter func(*ssa.Function) bool, buildCallGraph bool) (*pointer.Result,
	error)

DoPointerAnalysis runs the pointer analysis on the program p, marking every Value in the functions filtered by functionFilter as potential Value to query for aliasing.

- p is the program to be analyzed

- functionFilter determines whether to add the values of the function in the Queries or IndirectQueries of the result

- buildCallGraph determines whether the analysis must also build the callgraph of the program

If error != nil, the *pointer.Result is such that every Value in the functions f such that functionFilter(f) is true will be in the Queries or IndirectQueries of the pointer.Result

func FindIntraProceduralPath 

func FindIntraProceduralPath(begin ssa.Instruction, end ssa.Instruction) pathInformation

FindIntraProceduralPath returns a Path between the begin and end instructions. Returns nil if there is no Path between being and end inside the function.

func FindPathBetweenBlocks 

func FindPathBetweenBlocks(begin *ssa.BasicBlock, end *ssa.BasicBlock) []*ssa.BasicBlock

FindPathBetweenBlocks is a BFS of the blocks successor graph returns a list of block indexes representing a Path from begin to end. Returns nil iff there is no such Path.

func FuncNames 

func FuncNames(n *NodeTree[*CallNode]) string

FuncNames returns a string that contains all the function names in the current trace (from root to leaf)

func GetUniqueFunctionID 

func GetUniqueFunctionID() uint32

GetUniqueFunctionID increments and returns the Value of the global used to give unique function ids.

func InspectInstruction 

func InspectInstruction(state *AnalyzerState, bindMap BoundingMap, instruction ssa.Instruction)

InspectInstruction adds information to the bindMap if instruction is a closure and the pointer analysis contains information about where the bound variables are allocated.

func Instr 

func Instr(node GraphNode) ssa.Instruction

Instr returns the SSA instruction corresponding to node. Returns nil if there is no SSA instruction.

func InterfaceMethodKey 

func InterfaceMethodKey(callsite ssa.CallInstruction) (bool, string)

InterfaceMethodKey returns the contract method key of a call instruction if it can be resolved

func NodeKind 

func NodeKind(g GraphNode) string

NodeKind returns a short string representation of the node kind

func NodeSummary 

func NodeSummary(g GraphNode) string

NodeSummary returns a string summary of the node

func RunIntraProcedural 

func RunIntraProcedural(a *AnalyzerState, sm *SummaryGraph) (time.Duration, error)

RunIntraProcedural is the core of the intra-procedural analysis. It updates the summary graph *in place* using the information contained in the state. It is possible to create a graph first only using NewSummaryGraph and then run RunIntraProcedural to update the edges in the graph.

RunIntraProcedural does not add any nod except bound label nodes to the summary graph, it only updates information related to the edges.

func SetMaxAccessPathLength 

func SetMaxAccessPathLength(n int)

SetMaxAccessPathLength sets the maximum access path length for field sensitivity. This should only be set once, changing this value while the analysis is running may lead to unpredictable results.

func ShouldBuildSummary 

func ShouldBuildSummary(state *AnalyzerState, function *ssa.Function) bool

ShouldBuildSummary returns true if the function's summary should be *built* during the single function analysis pass. This is not necessary for functions that have summaries that are externally defined, for example.

Types

type AbstractValue 

type AbstractValue struct {
	// contains filtered or unexported fields
}

An AbstractValue represents an abstract value in the dataflow computation algorithm: an abstract value is an SSA value with a set of marks. If the value is represented in an (access-)path sensitive manner, then isPathSensitive must be true and the maps of accessMarks is in use. If the value is not (access-)path sensitive, the marks maps is the set of marks of that value.

func NewAbstractValue 

func NewAbstractValue(v ssa.Value, pathSensitive bool) *AbstractValue

NewAbstractValue returns a new abstract value v. If pathSensitive is true, then the abstract value is represented in an access path sensitive manner (marks on the value are different depending on the access path).

func (*AbstractValue) AllMarks 

func (a *AbstractValue) AllMarks() []MarkWithAccessPath

AllMarks returns all the marks on the abstract value, ignoring their access path.

func (*AbstractValue) GetValue 

func (a *AbstractValue) GetValue() ssa.Value

GetValue returns the ssa value of the abstract value.

func (*AbstractValue) HasMarkAt 

func (a *AbstractValue) HasMarkAt(path string, m *Mark) bool

HasMarkAt returns a boolean indicating whether the abstractValue has a mark at the given path.

func (*AbstractValue) MarksAt 

func (a *AbstractValue) MarksAt(path string) []MarkWithAccessPath

MarksAt returns all the marks with relative paths on the abstract value for a certain path. For example, if the value x is marked at ".field" by [m] and at "[*]" by [m'] then x.MarksAt(".field") will return "[{m,""}]" and x.MarksAt("[*]") will return "[{m',""}]". x.MarksAt("") will return [{m,".field"},{m',"[*]"}]

- If the value is marked at "", by "m”, then MarksAt(".field") will return "[{m, ""},{"m'”,""}]".

- if the value z is marked at ".f.g" by "o", then z.MarksAt(".f") will return [{m, ".g"}]

If the value is not path sensitive, then MarkAt simply returns AllMarks(), the path is ignored.

TODO: the implementation of access paths will change, and we will provide a more complete documentation then.

func (*AbstractValue) PathMappings 

func (a *AbstractValue) PathMappings() map[string]map[*Mark]bool

PathMappings returns a map from access path to set of marks. If the abstract value is no access-path (or field) sensitive, then the only access path is "".

func (*AbstractValue) Show 

func (a *AbstractValue) Show(w io.Writer)

Show writes information about the value on the writer

type AccessGlobalNode 

type AccessGlobalNode struct {
	IsWrite bool // IsWrite is true if the global is written at that location

	Global *GlobalNode // the corresponding global node
	// contains filtered or unexported fields
}

A AccessGlobalNode represents a node where a global variable is accessed (read or written) In this context, a "write" is when data flows to the node, and a "read" is when data flows from the node

func (*AccessGlobalNode) Equal 

func (a *AccessGlobalNode) Equal(node GraphNode) bool

Equal implements comparison for graph nodes

func (*AccessGlobalNode) Graph 

func (a *AccessGlobalNode) Graph() *SummaryGraph

Graph returns the parent summary graph of the node

func (*AccessGlobalNode) ID 

func (a *AccessGlobalNode) ID() uint32

ID returns the integer id of the node in its parent graph

func (*AccessGlobalNode) In 

func (a *AccessGlobalNode) In() map[GraphNode]EdgeInfo

In returns the nodes with incoming edges to the current node, with their object path

func (*AccessGlobalNode) Instr 

func (a *AccessGlobalNode) Instr() ssa.Instruction

Instr returns the instruction that accesses the global

func (*AccessGlobalNode) LongID 

func (a *AccessGlobalNode) LongID() string

LongID returns a string identifier for the node

func (*AccessGlobalNode) Marks 

func (a *AccessGlobalNode) Marks() LocSet

Marks returns the location information of the node

func (*AccessGlobalNode) Out 

func (a *AccessGlobalNode) Out() map[GraphNode]EdgeInfo

Out returns the nodes the graph node's data flows to, with their object path

func (*AccessGlobalNode) ParentName 

func (a *AccessGlobalNode) ParentName() string

ParentName returns the name of the function where the global is accessed

func (*AccessGlobalNode) Position 

func (a *AccessGlobalNode) Position(c *AnalyzerState) token.Position

Position returns the estimated position of the node in the source

func (*AccessGlobalNode) SetLocs 

func (a *AccessGlobalNode) SetLocs(set LocSet)

SetLocs sets the locations information of the node

func (*AccessGlobalNode) String 

func (a *AccessGlobalNode) String() string

func (*AccessGlobalNode) Type 

func (a *AccessGlobalNode) Type() types.Type

Type returns the type of the

type AnalyzerState 

type AnalyzerState struct {
	// The logger used during the analysis (can be used to control output.
	Logger *config.LogGroup

	// The configuration file for the analysis
	Config *config.Config

	// The program to be analyzed. It should be a complete buildable program (e.g. loaded by LoadProgram).
	Program *ssa.Program

	// A map from types to functions implementing that type
	//
	// If t is the signature of an interface's method, then map[t.string()] will return all the implementations of
	// that method.
	//
	// If t is the signature of a function, then map[t.string()] will return all the functions matching that type.
	ImplementationsByType map[string]map[*ssa.Function]bool

	// DataFlowContracts are dataflow graphs for interfaces.
	DataFlowContracts map[string]*SummaryGraph

	// The result of a pointer analysis.
	PointerAnalysis *pointer.Result

	// The global analysis
	Globals map[*ssa.Global]*GlobalNode

	// The dataflow analysis results
	FlowGraph *InterProceduralFlowGraph

	// The escape analysis state
	EscapeAnalysisState EscapeAnalysisState

	// BoundingInfo is a map from pointer labels to the closures that bind them. The bounding analysis produces such
	// a map
	BoundingInfo BoundingMap
	// contains filtered or unexported fields
}

AnalyzerState holds information that might need to be used during program analysis, and represents the state of the analyzer. Different steps of the analysis will populate the fields of this structure.

func NewAnalyzerState 

func NewAnalyzerState(p *ssa.Program, l *config.LogGroup, c *config.Config,
	steps []func(*AnalyzerState)) (*AnalyzerState, error)

NewAnalyzerState returns a properly initialized analyzer state by running essential steps in parallel.

func NewInitializedAnalyzerState 

func NewInitializedAnalyzerState(logger *config.LogGroup, config *config.Config,
	program *ssa.Program) (*AnalyzerState, error)

NewInitializedAnalyzerState runs NewAnalyzerState, and any additional steps that are commonly used in analyses. This consists in:

  • running pointer analysis
  • computing a map from interface types to the implementations of their methods
  • scanning the usage of globals in the program
  • linking aliases of bound variables to the closure that binds them

func (*AnalyzerState) AddError 

func (s *AnalyzerState) AddError(key string, e error)

AddError adds an error with key and error e to the state.

func (*AnalyzerState) CheckError 

func (s *AnalyzerState) CheckError() []error

CheckError checks whether there is an error in the state, and if there is, returns the first it encounters and deletes it. The slice returned contains all the errors associated with one single error key (as used in *AnalyzerState.AddError)

func (*AnalyzerState) CopyTo 

func (s *AnalyzerState) CopyTo(b *AnalyzerState)

CopyTo copies pointers in receiver into argument (shallow copy of everything except mutex). Do not use two copies in separate routines.

func (*AnalyzerState) HasErrors 

func (s *AnalyzerState) HasErrors() bool

HasErrors returns true if the state has an error. Unlike *AnalyzerState.CheckError, this is non-destructive.

func (*AnalyzerState) HasExternalContractSummary 

func (s *AnalyzerState) HasExternalContractSummary(f *ssa.Function) bool

HasExternalContractSummary returns true if the function f has a summary has been loaded in the DataFlowContracts of the analyzer state.

func (*AnalyzerState) IsReachableFunction 

func (s *AnalyzerState) IsReachableFunction(f *ssa.Function) bool

IsReachableFunction returns true if f is reachable according to the pointer analysis, or if the pointer analysis and ReachableFunctions has never been called.

func (*AnalyzerState) LoadExternalContractSummary 

func (s *AnalyzerState) LoadExternalContractSummary(node *CallNode) *SummaryGraph

LoadExternalContractSummary looks for contracts loaded in the DataFlowContracts of the state.

func (*AnalyzerState) PopulateBoundingInformation 

func (s *AnalyzerState) PopulateBoundingInformation(verbose bool) error

PopulateBoundingInformation runs the bounding analysis

func (*AnalyzerState) PopulateGlobals 

func (s *AnalyzerState) PopulateGlobals()

PopulateGlobals adds global nodes for every global defined in the program's packages

func (*AnalyzerState) PopulateGlobalsVerbose 

func (s *AnalyzerState) PopulateGlobalsVerbose()

PopulateGlobalsVerbose is a verbose wrapper around PopulateGlobals

func (*AnalyzerState) PopulateImplementations 

func (s *AnalyzerState) PopulateImplementations()

PopulateImplementations is a verbose wrapper around PopulateTypesToImplementationsMap.

func (*AnalyzerState) PopulatePointerAnalysisResult 

func (s *AnalyzerState) PopulatePointerAnalysisResult(functionFilter func(*ssa.Function) bool)

PopulatePointerAnalysisResult populates the PointerAnalysis field of the analyzer state by running the pointer analysis with queries on every function in the package such that functionFilter is true.

The analyzer state contains the result of the pointer analysis, or an error that can be inspected by CheckError

func (*AnalyzerState) PopulatePointersVerbose 

func (s *AnalyzerState) PopulatePointersVerbose(functionFilter func(*ssa.Function) bool)

PopulatePointersVerbose is a verbose wrapper around PopulatePointerAnalysisResult.

func (*AnalyzerState) PopulateTypesToImplementationMap 

func (s *AnalyzerState) PopulateTypesToImplementationMap()

PopulateTypesToImplementationMap populates the implementationsByType maps from type strings to implementations

func (*AnalyzerState) PrintImplementations 

func (s *AnalyzerState) PrintImplementations(w io.Writer)

PrintImplementations prints out all of the implementations that the AnalyzerState has collected, organized by type. For each type, it prints the type name followed by each implemented function name.

The implementations are printed to the given io.Writer. Typically this would be os.Stdout to print to the standard output.

This can be useful for debugging the implementations collected during analysis or for displaying final results.

func (*AnalyzerState) ReachableFunctions 

func (s *AnalyzerState) ReachableFunctions(excludeMain bool, excludeInit bool) map[*ssa.Function]bool

ReachableFunctions returns the set of reachable functions according to the pointer analysis If the pointer analysis hasn't been run, then returns an empty map.

func (*AnalyzerState) ReportMissingClosureNode 

func (s *AnalyzerState) ReportMissingClosureNode(closureNode *ClosureNode)

ReportMissingClosureNode prints a missing closure node summary message to the cache's logger.

func (*AnalyzerState) ReportMissingOrNotConstructedSummary 

func (s *AnalyzerState) ReportMissingOrNotConstructedSummary(callSite *CallNode)

ReportMissingOrNotConstructedSummary prints a missing summary message to the cache's logger.

func (*AnalyzerState) ReportSummaryNotConstructed 

func (s *AnalyzerState) ReportSummaryNotConstructed(callSite *CallNode)

ReportSummaryNotConstructed prints a warning message to the cache's logger.

func (*AnalyzerState) ResolveCallee 

func (s *AnalyzerState) ResolveCallee(instr ssa.CallInstruction, useContracts bool) (map[*ssa.Function]CalleeInfo, error)

ResolveCallee resolves the callee(s) at the call instruction instr.

If the callee is statically resolvable, then it returns a single callee.

If the call instruction appears in the callgraph, it returns all the callees at that callsite according to the pointer analysis callgraph (requires it to be computed).

If the call instruction does not appear in the callgraph, then it returns all the functions that correspond to the type of the call variable at the location.

Returns a non-nil error if it requires some information in the analyzer state that has not been computed.

func (*AnalyzerState) Size 

func (s *AnalyzerState) Size() int

Size returns the number of method implementations collected

type BindingInfo 

type BindingInfo struct {
	// MakeClosure is the instruction where the closure has been created
	MakeClosure *ssa.MakeClosure

	// BoundIndex is the index of the bound variables. It should satisfy 0 <= BoundIndex <= len(MakeClosure.Bindings)
	BoundIndex int
}

BindingInfo contains information about a closure creation location (the MakeClosure instruction) and an index for the bound variable / free variable that the binding info references.

func (BindingInfo) String 

func (b BindingInfo) String() string

func (BindingInfo) Type 

func (b BindingInfo) Type() types.Type

Type returns the types.Type of the binding

type BoundLabelNode 

type BoundLabelNode struct {
	// contains filtered or unexported fields
}

A BoundLabelNode is used to track dataflow from modified bound variables to closure bodies

func (*BoundLabelNode) DestClosure 

func (a *BoundLabelNode) DestClosure() *SummaryGraph

DestClosure returns the closure that binds the node

func (*BoundLabelNode) DestInfo 

func (a *BoundLabelNode) DestInfo() BindingInfo

DestInfo returns the information of the target bound variable

func (*BoundLabelNode) Equal 

func (a *BoundLabelNode) Equal(node GraphNode) bool

Equal implements equality checking between bound label nodes

func (*BoundLabelNode) Graph 

func (a *BoundLabelNode) Graph() *SummaryGraph

Graph returns the parent summary graph of the node

func (*BoundLabelNode) ID 

func (a *BoundLabelNode) ID() uint32

ID returns the integer id of the node in its parent graph

func (*BoundLabelNode) In 

func (a *BoundLabelNode) In() map[GraphNode]EdgeInfo

In returns the nodes with incoming edges to the current node, with their object path

func (*BoundLabelNode) Index 

func (a *BoundLabelNode) Index() int

Index returns the index of the bound variable in the closure

func (*BoundLabelNode) Instr 

func (a *BoundLabelNode) Instr() ssa.Instruction

Instr correspond to the instruction matching that synthetic node

func (*BoundLabelNode) LongID 

func (a *BoundLabelNode) LongID() string

LongID returns a string identifier for the node

func (*BoundLabelNode) Marks 

func (a *BoundLabelNode) Marks() LocSet

Marks returns the location information of the node

func (*BoundLabelNode) Out 

func (a *BoundLabelNode) Out() map[GraphNode]EdgeInfo

Out returns the nodes the graph node's data flows to, with their object path

func (*BoundLabelNode) ParentName 

func (a *BoundLabelNode) ParentName() string

ParentName returns the parent name of the bound label (its parent function)

func (*BoundLabelNode) Position 

func (a *BoundLabelNode) Position(c *AnalyzerState) token.Position

Position returns the position of the bound label

func (*BoundLabelNode) SetDestClosure 

func (a *BoundLabelNode) SetDestClosure(g *SummaryGraph)

SetDestClosure sets the closure that binds the node

func (*BoundLabelNode) SetLocs 

func (a *BoundLabelNode) SetLocs(set LocSet)

SetLocs sets the locations information of the node

func (*BoundLabelNode) String 

func (a *BoundLabelNode) String() string

func (*BoundLabelNode) Type 

func (a *BoundLabelNode) Type() types.Type

Type returns the type of the bound label

type BoundVarNode 

type BoundVarNode struct {
	// contains filtered or unexported fields
}

BoundVarNode is a node that represents the bound variable when a closure is created

func (*BoundVarNode) Equal 

func (a *BoundVarNode) Equal(node GraphNode) bool

Equal implements comparison for graph nodes

func (*BoundVarNode) Graph 

func (a *BoundVarNode) Graph() *SummaryGraph

Graph returns the parent summary graph of the node

func (*BoundVarNode) ID 

func (a *BoundVarNode) ID() uint32

ID returns the integer id of the node in its parent graph

func (*BoundVarNode) In 

func (a *BoundVarNode) In() map[GraphNode]EdgeInfo

In returns the nodes with incoming edges to the current node, with their object path

func (*BoundVarNode) Index 

func (a *BoundVarNode) Index() int

Index returns the position of the bound variable in the make closure instruction. It will correspond to the position of the matching variable in the closure's free variables.

func (*BoundVarNode) LongID 

func (a *BoundVarNode) LongID() string

LongID returns a string identifier for the node

func (*BoundVarNode) Marks 

func (a *BoundVarNode) Marks() LocSet

Marks returns the location information of the node

func (*BoundVarNode) Out 

func (a *BoundVarNode) Out() map[GraphNode]EdgeInfo

Out returns the nodes the graph node's data flows to, with their object path

func (*BoundVarNode) ParentName 

func (a *BoundVarNode) ParentName() string

ParentName returns the name of the parent function (not the parent closure node)

func (*BoundVarNode) ParentNode 

func (a *BoundVarNode) ParentNode() *ClosureNode

ParentNode returns the closure node corresponding to the bound variable

func (*BoundVarNode) Position 

func (a *BoundVarNode) Position(c *AnalyzerState) token.Position

Position returns the estimated position of the node in the source

func (*BoundVarNode) SetLocs 

func (a *BoundVarNode) SetLocs(set LocSet)

SetLocs sets the locations information of the node

func (*BoundVarNode) String 

func (a *BoundVarNode) String() string

func (*BoundVarNode) Type 

func (a *BoundVarNode) Type() types.Type

Type returns the type of the bound variable

func (*BoundVarNode) Value 

func (a *BoundVarNode) Value() ssa.Value

Value returns the ssa value of the bound variable

type BoundingMap 

type BoundingMap map[ssa.Value]map[*BindingInfo]bool

BoundingMap maps values to the binding infos that reference the closures that captured the value. In other words, for a value v and BoundingMap X, if X[v] is non-empty, then v is captured by some closure. For each y in X[v], y.MakeClosure is the instruction that captures it and y.BoundIndex is the bound variable that aliases v.

func RunBoundingAnalysis 

func RunBoundingAnalysis(state *AnalyzerState) (BoundingMap, error)

RunBoundingAnalysis computes the BoundingMap of the program in the analyzer state by iterating over the instructions of each reachable function.

type CallCtxInfo 

type CallCtxInfo struct {
	Contexts map[string]bool
	Ids      map[int]*cg.Node
}

CallCtxInfo holds information about a calling context of a function

func ComputeContexts 

func ComputeContexts(c *AnalyzerState, n int) (CallCtxInfo, error)

ComputeContexts computes all calling contexts of size at most n (the callgraph used is in c.PointerAnalysis.Callgraph.Root)

func (CallCtxInfo) KeyToNodes 

func (c CallCtxInfo) KeyToNodes(key string) []*cg.Node

KeyToNodes returns the list of nodes matching the dot-separated string used as key in a context

type CallNode 

type CallNode struct {
	CalleeSummary *SummaryGraph
	// contains filtered or unexported fields
}

CallNode is a node that represents a function call. It represents the Value returned by the function call and also points at the CallNodeArg nodes that are its arguments

func UnwindCallstackFromCallee 

func UnwindCallstackFromCallee(callsites map[ssa.CallInstruction]*CallNode, stack *CallStack) *CallNode

UnwindCallstackFromCallee returns the CallNode that should be returned upon. It satisfies the following conditions: - the CallNode is in the callsites set - the CallNode is in the stack If no CallNode satisfies these conditions, nil is returned.

func (*CallNode) Args 

func (a *CallNode) Args() []*CallNodeArg

Args returns the list of arguments of the call

func (*CallNode) CallSite 

func (a *CallNode) CallSite() ssa.CallInstruction

CallSite returns the call instruction corresponding to the call node

func (*CallNode) Callee 

func (a *CallNode) Callee() *ssa.Function

Callee returns the function called at the call node

func (*CallNode) Equal 

func (a *CallNode) Equal(node GraphNode) bool

Equal implements comparison for graph nodes

func (*CallNode) FindArg 

func (a *CallNode) FindArg(v ssa.Value) *CallNodeArg

FindArg fins the node corresponding to the value v as an argument of the call

func (*CallNode) FullString 

func (a *CallNode) FullString() string

FullString returns a long string representation of the CallNode

func (*CallNode) FuncName 

func (a *CallNode) FuncName() string

FuncName returns the name of the function being called. It can be either the method name or a function name. The function could be a Value (and not a static call), in which case the name of the Value is returned.

func (*CallNode) FuncString 

func (a *CallNode) FuncString() string

FuncString returns the string identified of the function being called. It can be either the method string or a function string. The function could be a Value (and not a static call), in which case the name of the Value is returned.

func (*CallNode) Graph 

func (a *CallNode) Graph() *SummaryGraph

Graph returns the parent summary graph of the node

func (*CallNode) ID 

func (a *CallNode) ID() uint32

ID returns the integer id of the node in its parent graph

func (*CallNode) In 

func (a *CallNode) In() map[GraphNode]EdgeInfo

In returns the nodes with incoming edges to the current node, with their object path

func (*CallNode) LongID 

func (a *CallNode) LongID() string

LongID returns a string identifier for the node

func (*CallNode) Marks 

func (a *CallNode) Marks() LocSet

Marks returns the location information of the node

func (*CallNode) Out 

func (a *CallNode) Out() map[GraphNode]EdgeInfo

Out returns the nodes the graph node's data flows to, with their object path

func (*CallNode) ParentName 

func (a *CallNode) ParentName() string

ParentName returns the name of the parent function

func (*CallNode) Position 

func (a *CallNode) Position(c *AnalyzerState) token.Position

Position returns the estimated position of the node in the source

func (*CallNode) SetLocs 

func (a *CallNode) SetLocs(set LocSet)

SetLocs sets the locations information of the node

func (*CallNode) String 

func (a *CallNode) String() string

func (*CallNode) Type 

func (a *CallNode) Type() types.Type

Type returns the type of the call site (the type of the returned value, not the signature of the function called)

type CallNodeArg 

type CallNodeArg struct {
	// contains filtered or unexported fields
}

CallNodeArg is a node that represents the argument of a function call

func (*CallNodeArg) Equal 

func (a *CallNodeArg) Equal(node GraphNode) bool

Equal implements comparison for graph nodes

func (*CallNodeArg) Graph 

func (a *CallNodeArg) Graph() *SummaryGraph

Graph returns the parent summary graph of the node

func (*CallNodeArg) ID 

func (a *CallNodeArg) ID() uint32

ID returns the integer id of the node in its parent graph

func (*CallNodeArg) In 

func (a *CallNodeArg) In() map[GraphNode]EdgeInfo

In returns the nodes with incoming edges to the current node, with their object path

func (*CallNodeArg) Index 

func (a *CallNodeArg) Index() int

Index returns the argument's position in the parent call node

func (*CallNodeArg) LongID 

func (a *CallNodeArg) LongID() string

LongID returns a string identifier for the node

func (*CallNodeArg) Marks 

func (a *CallNodeArg) Marks() LocSet

Marks returns the location information of the node

func (*CallNodeArg) Out 

func (a *CallNodeArg) Out() map[GraphNode]EdgeInfo

Out returns the nodes the graph node's data flows to, with their object path

func (*CallNodeArg) ParentName 

func (a *CallNodeArg) ParentName() string

ParentName returns the name of the parent function (not the parent call node)

func (*CallNodeArg) ParentNode 

func (a *CallNodeArg) ParentNode() *CallNode

ParentNode returns the parent call node

func (*CallNodeArg) Position 

func (a *CallNodeArg) Position(c *AnalyzerState) token.Position

Position returns the estimated position of the node in the source

func (*CallNodeArg) SetLocs 

func (a *CallNodeArg) SetLocs(set LocSet)

SetLocs sets the locations information of the node

func (*CallNodeArg) String 

func (a *CallNodeArg) String() string

func (*CallNodeArg) Type 

func (a *CallNodeArg) Type() types.Type

Type returns the type of the ssa node associated to the graph node

func (*CallNodeArg) Value 

func (a *CallNodeArg) Value() ssa.Value

Value returns the ssa value of the call argument

type CallStack 

type CallStack = NodeTree[*CallNode]

CallStack represents call stacks as trees of call nodes One can point at a specific node in the tree and extract the call stack above

func GetAllCallingContexts 

func GetAllCallingContexts(s *AnalyzerState, n *CallNode) []*CallStack

GetAllCallingContexts returns all the possible loop-free calling contexts of a CallNode in the state

func UnwindCallStackToFunc 

func UnwindCallStackToFunc(stack *CallStack, f *ssa.Function) *CallStack

UnwindCallStackToFunc looks for the callstack pointer where f was called. Returns nil if no such function can be found

type CalleeInfo 

type CalleeInfo struct {
	Callee *ssa.Function
	Type   CalleeType
}

CalleeInfo decorates a function with some CalleeType that records how the dataflow information of the function can be resolved or how the callee's identity was determined

type CalleeType 

type CalleeType int

A CalleeType gives information about how the callee was resolved 

const (
	// Static indicates the callee is a statically defined function
	Static CalleeType = 1 << iota
	// CallGraph indicates the callee is a function obtained from the call graph
	CallGraph
	// InterfaceContract indicates the callee is obtained from an interface contract (one particular instance
	// of an interface method to stand for all methods)
	InterfaceContract
	// InterfaceMethod indicates the calle is an interface method
	InterfaceMethod
)

func (CalleeType) Code 

func (t CalleeType) Code() string

Code returns a short string representation of the type of callee

type CallgraphAnalysisMode 

type CallgraphAnalysisMode uint64

CallgraphAnalysisMode is either PointerAnalysis, StaticAnalysis, ClassHierarchyAnalysis, RapidTypeAnalysis or VariableTypeAnalysis for calling ComputeCallGraph 

const (
	// PointerAnalysis is over-approximating (slow)
	PointerAnalysis CallgraphAnalysisMode = iota
	// StaticAnalysis is under-approximating (fast)
	StaticAnalysis
	// ClassHierarchyAnalysis is a coarse over-approximation (fast)
	ClassHierarchyAnalysis
	// RapidTypeAnalysis TODO: review
	RapidTypeAnalysis
	// VariableTypeAnalysis TODO: review
	VariableTypeAnalysis
)

func (CallgraphAnalysisMode) ComputeCallgraph 

func (mode CallgraphAnalysisMode) ComputeCallgraph(prog *ssa.Program) (*callgraph.Graph, error)

ComputeCallgraph computes the call graph of prog using the provided mode.

type ClosureNode 

type ClosureNode struct {

	// the closureSummary is the data flow summary of the closure
	ClosureSummary *SummaryGraph
	// contains filtered or unexported fields
}

ClosureNode represents a makeClosure instruction in the dataflow graph

func (*ClosureNode) BoundVars 

func (a *ClosureNode) BoundVars() []*BoundVarNode

BoundVars returns the list of variables bound by the closure

func (*ClosureNode) Equal 

func (a *ClosureNode) Equal(node GraphNode) bool

Equal implements comparison for graph nodes

func (*ClosureNode) FindBoundVar 

func (a *ClosureNode) FindBoundVar(v ssa.Value) *BoundVarNode

FindBoundVar returns the BoundVarNode matching the input value v, if v is a bound variable of the closure

func (*ClosureNode) Graph 

func (a *ClosureNode) Graph() *SummaryGraph

Graph is the parent of a closure node is the summary of the function in which the closure is created.

func (*ClosureNode) ID 

func (a *ClosureNode) ID() uint32

ID returns the integer id of the node in its parent graph

func (*ClosureNode) In 

func (a *ClosureNode) In() map[GraphNode]EdgeInfo

In returns the nodes with incoming edges to the current node, with their object path

func (*ClosureNode) Instr 

func (a *ClosureNode) Instr() *ssa.MakeClosure

Instr returns the makeClosure instruction corresponding to the closure node

func (*ClosureNode) LongID 

func (a *ClosureNode) LongID() string

LongID returns a string identifier for the node

func (*ClosureNode) Marks 

func (a *ClosureNode) Marks() LocSet

Marks returns the set of instructions through which data from the node flows

func (*ClosureNode) Out 

func (a *ClosureNode) Out() map[GraphNode]EdgeInfo

Out returns the nodes the graph node's data flows to, with their object path

func (*ClosureNode) ParentName 

func (a *ClosureNode) ParentName() string

ParentName returns the name of the function where the closure is created

func (*ClosureNode) Position 

func (a *ClosureNode) Position(c *AnalyzerState) token.Position

Position returns the estimated position of the node in the source

func (*ClosureNode) SetLocs 

func (a *ClosureNode) SetLocs(set LocSet)

SetLocs sets the locations information of the node

func (*ClosureNode) String 

func (a *ClosureNode) String() string

func (*ClosureNode) Type 

func (a *ClosureNode) Type() types.Type

Type returns the type of the makeClosure instruction (the signature of the closure)

type Condition 

type Condition struct {
	// IsPositive indicates whether the branch is the then- or -else branch, i.e. the condition must be taken positively
	// or negatively
	IsPositive bool

	// Value refers to the Value of the condition in the branching
	Value ssa.Value
}

Condition hold information about a conditional Path. If Positive, then the branch is the then-branch where the condition is the Value. If it is not Positive, then this refers to the else-branch

func (Condition) IsPredicateTo 

func (c Condition) IsPredicateTo(v ssa.Value) bool

IsPredicateTo returns true when the condition is a predicate that applies to v The logic behind the statement "a predicate that applies to v" must match the expectations of the dataflow analysis Currently:

  • the condition must be a call to some predicate (a function returning a boolean) Possible extensions would include computing the expression of the boolean condition, which would allow more general patterns like checking that a returned error is non-nil
  • v must hold the same data as one of the arguments of the call The logic for "same data" is in the ValuesWithSameData function of the lang package.

func (Condition) String 

func (c Condition) String() string

type ConditionInfo 

type ConditionInfo struct {
	// If Satisfiable is false, the condition info refers to an object that cannot exist
	Satisfiable bool

	// Conditions is the list of conditions in the info, which can be empty even when Satisfiable is true
	// Should be interpreted as a conjunction of its elements.
	Conditions []Condition
}

ConditionInfo holds information about the conditions under which an object may be relevant.

func SimplePathCondition 

func SimplePathCondition(path []*ssa.BasicBlock) ConditionInfo

SimplePathCondition returns the ConditionInfo that aggregates all conditions encountered on the Path represented by the list of basic blocks. The input list of basic block must represent a program Path (i.e. each basic block is one of the Succs of its predecessor).

func (ConditionInfo) AsPredicateTo 

func (c ConditionInfo) AsPredicateTo(v ssa.Value) ConditionInfo

AsPredicateTo filters the conditions in c that relate to the Value v. The returned ConditionInfo is weaker than the input.

func (ConditionInfo) String 

func (c ConditionInfo) String() string

type Contract 

type Contract struct {
	InterfaceID string
	ObjectPath  string
	Methods     map[string]summaries.Summary
}

A Contract is an object that specifies the dataflow some specific function should satisfy.

If interfaceId is not empty, then it is an interface contract: the interface id is the long name of the interface, i.e. package name followed by the type name, and a map from method names to dataflow summaries. All implementations of the specified methods must satisfy the contract.

If the objectPath is not empty, then it is a function contract: the objectPath specifies the long name of the object, either package name followed by struct name, or package name only. The methods are the dataflow summaries of the methods in question.

objectPath and interfaceId should not be both specified.

func LoadDefinitions 

func LoadDefinitions(fileName string) ([]Contract, error)

LoadDefinitions loads the dataflow definitions contained in the json file at filename returns an error if it could not read the file, or the file is not well formatted.

func (Contract) Key 

func (c Contract) Key(method string) string

Key returns a string identifying the method or function in the given contract. This can be used to store method information consistently across different usages

type EdgeInfo 

type EdgeInfo struct {
	// RelPath is the relative output object access path, e.g. ".A" for field A
	RelPath map[string]map[string]bool

	// Index is the relative tuple element reference by this Path
	// if < 0, this means it is not used
	Index int

	// Cond is the condition under which this pointer/edge is valid.
	// An example usage is in the implementation of validators.
	Cond *ConditionInfo
}

EdgeInfo contains information relative to the object pointed to.

type EscapeAnalysisState 

type EscapeAnalysisState interface {
	// IsEscapeAnalysisState ensures only the escape analysis implements this interface. Returns true.
	IsEscapeAnalysisState() bool
	// IsSummarized returns whether the escape analysis has a summary for f
	IsSummarized(f *ssa.Function) bool
	// ComputeArbitraryContext  computes a call context for f assuming it could be called from anywhere.
	// This is conservative, and
	// will result in less locality than if a correct call context is provided. If there are no arguments
	// (such as for main), then there is no loss of precision.
	ComputeArbitraryContext(f *ssa.Function) EscapeCallContext
	// ComputeInstructionLocalityAndCallsites computes locality and callsite information for a function,
	// given a particular calling context.
	// This internally performs a potentially expensive flow-sensitive monotone convergence loop. The
	// resulting locality map contains a true value for each instruction that is provably local, and false
	// for instructions that may access shared memory. The callsite infos must be resolved for each
	// possible concrete callee; see `EscapeCallsiteInfo.Resolve()`. Only calls to non-builtins are
	// available in `callsiteInfo`.
	ComputeInstructionLocalityAndCallsites(f *ssa.Function, ctx EscapeCallContext) (
		instructionLocality map[ssa.Instruction]*EscapeRationale,
		callsiteInfo map[*ssa.Call]EscapeCallsiteInfo)
}

EscapeAnalysisState Represents the state required to answer queries for a particular program. Internally, holds the escape summaries of each analyzed `ssa.Function`. Summaries are bottom-up, but useful locality information requires tracking information from callers (e.g. whether a particular argument is allocated locally). Rather than baking in a particular context-sensitivity, this interface gives the client the ability to control how context-sensitivity is handled. In particular, an EscapeCallContext encodes information about the calling context, as it is relevant to locality.

This calling context can be used to compute the instruction locality, defined as whether each instruction only manipulates local information, for a particular function. This process also computes, for each callsite in a function, the context the callee will be called under, assuming that edge is traversed. (These operations are combined because they use an identical, expensive monotone convergence loop internally.) The callsite information is initially a `EscapeCallsiteInfo`, which is generic for all callees. It can be resolved into a EscapeCallContext for a particular specific callee function. Effectively, an EscapeCallsiteInfo represents the context from the callers perspective, whereas the EscapeCallContext represents the same info from the callee's perspective.

The `Merge()` operation on a EscapeCallContext can be used to avoid a blowup in the number of contexts. Merging multiple contexts is monotone, and the `Matches()` method can be used to detect convergence in the presence of recursive functions. (Note, the context returned by ComputeArbitraryContext is not a unit of Merge; it should not be used to initialize a convergence loop.)

type EscapeCallContext 

type EscapeCallContext interface {
	// Merge returns a new EscapeCallContext that is the merge of `this` and `other`,
	// and whether the result is semantically different from `this`.
	Merge(other EscapeCallContext) (changed bool, merged EscapeCallContext)
	// Matches returns true if the two calling contexts are semantically equivalent.
	Matches(EscapeCallContext) bool
}

EscapeCallContext represents the escape-relevant context for a particular `ssa.Function`. Can be merged with another context for the same function and compared. `EscapeCallContext`s are specific to a particular ssa.Function; they cannot be shared even amongst functions with the same signature. EscapeCallContext objects are immutable.

type EscapeCallsiteInfo 

type EscapeCallsiteInfo interface {
	Resolve(callee *ssa.Function) EscapeCallContext
}

EscapeCallsiteInfo represents a call context, but from the caller's perspective at a particular callsite. This information doesn't depend on the particular callee (e.g. the implementation of an interface call), but may be `Resolve`d for a particular callee. EscapeCallsiteInfo objects are immutable.

type EscapeRationale 

type EscapeRationale struct {
	Reason string
}

EscapeRationale holds information on the rationale of why a value may escape

func NewBaseRationale 

func NewBaseRationale(reason string) *EscapeRationale

NewBaseRationale returns a new escape rationale with the reason provided as argument

func (*EscapeRationale) String 

func (r *EscapeRationale) String() string

type FlowInformation 

type FlowInformation struct {
	// Function is the function being analyzed
	Function *ssa.Function

	// user provided configuration identifying specific dataflow nodes to track and other settings (e.g. verbosity)
	Config *config.Config

	// NumBlocks is the number of blocks in the function
	NumBlocks IndexT

	// NumValues is the number of values used in the function (values defined + used)
	NumValues IndexT

	// NumInstructions is the number of instructions in the function
	NumInstructions IndexT

	// FirstInstr is the first non-ignored instruction in the function
	FirstInstr ssa.Instruction

	// ValueID maps ssa.Value to value id
	ValueID map[ssa.Value]IndexT

	// InstrID maps ssa.Instruction to instruction id
	InstrID map[ssa.Instruction]IndexT

	// MarkedValues maps instructions to abstract states, i.e. a map from values to their abstract Value, which is a
	// set of marks
	MarkedValues []*AbstractValue

	// LocSet is a map from marks to the locations associated to it. A location is associated to a mark when it
	// is used to propagate the mark during the monotone analysis. This is meant to be used by other analyses, and
	// does not contain user-interpretable information.
	LocSet map[*Mark]map[ssa.Instruction]bool
	// contains filtered or unexported fields
}

FlowInformation contains the dataflow information necessary for the analysis and function summary building.

func NewFlowInfo 

func NewFlowInfo(cfg *config.Config, f *ssa.Function) *FlowInformation

NewFlowInfo returns a new FlowInformation with all maps initialized.

func (*FlowInformation) AddMark 

func (fi *FlowInformation) AddMark(i ssa.Instruction, value ssa.Value,
	path string, s *Mark) bool

AddMark adds a mark to the tracking info structure and returns true if new information has been inserted. If false, then "fi" has not changed. In both cases, "fi" will have the mark "s" on ssa value "value" with "path" at instruction "i".

func (*FlowInformation) GetInstrPos 

func (fi *FlowInformation) GetInstrPos(i ssa.Instruction) IndexT

GetInstrPos returns the position of the instruction in the slice-based representations The instruction must be present in the array of InstrID. This is in general true if you have initialized the FlowInformation properly and you are working in the same function.

func (*FlowInformation) GetNewLabelledMark 

func (fi *FlowInformation) GetNewLabelledMark(node ssa.Node, typ MarkType,
	qualifier ssa.Value, index int, label string) *Mark

GetNewLabelledMark returns a pointer to the labelled mark with the provided arguments. Internally checks whether the mark object representing this mark already exists.

func (*FlowInformation) GetNewMark 

func (fi *FlowInformation) GetNewMark(node ssa.Node, typ MarkType, qualifier ssa.Value, index int) *Mark

GetNewMark returns a pointer to the mark with the provided arguments. Internally checks whether the mark object representing this mark already exists.

func (*FlowInformation) GetPos 

func (fi *FlowInformation) GetPos(i ssa.Instruction, v ssa.Value) (IndexT, bool)

GetPos returns the position of the abstract value at instruction i in the slice-based representation (the ValueID and InstrID map values and instructions to some ids, but a value in an instruction has a position in the MarkedValues slice that is calculated by (instruction id) * (number of instructions) + (value id) Returns the indexT (positive integer) and a boolean indicating whether the position exists.

func (*FlowInformation) GetValueID 

func (fi *FlowInformation) GetValueID(v ssa.Value) (IndexT, bool)

GetValueID returns the id of v if v in the FlowInformation and true, otherwise returns 0 and false if v is not tracked in the FLowInformation

func (*FlowInformation) HasMarkAt 

func (fi *FlowInformation) HasMarkAt(i ssa.Instruction, v ssa.Value, path string, s *Mark) bool

HasMarkAt returns true if the Value v has an abstract state at instruction i, and this abstract state contains the mark s.

func (*FlowInformation) SetLoc 

func (fi *FlowInformation) SetLoc(mark *Mark, instr ssa.Instruction)

SetLoc sets locality information for a mark. In the current representation, this adds an instruction to the set of instructions associated to a specific mark.

func (*FlowInformation) Show 

func (fi *FlowInformation) Show(w io.Writer)

Show prints the abstract states at each instruction in the function.

func (*FlowInformation) ShowAt 

func (fi *FlowInformation) ShowAt(w io.Writer, i ssa.Instruction)

ShowAt pretty-prints the abstract state of the analysis at instruction i. A line is printed for every SSA Value with an abstract Value (a set of marks).

type FreeVarNode 

type FreeVarNode struct {
	// contains filtered or unexported fields
}

FreeVarNode is a node that represents a free variable of the function (for closures)

func (*FreeVarNode) Equal 

func (a *FreeVarNode) Equal(node GraphNode) bool

Equal implements comparison for graph nodes

func (*FreeVarNode) Graph 

func (a *FreeVarNode) Graph() *SummaryGraph

Graph returns the parent summary graph of the node

func (*FreeVarNode) ID 

func (a *FreeVarNode) ID() uint32

ID returns the integer id of the node in its parent graph

func (*FreeVarNode) In 

func (a *FreeVarNode) In() map[GraphNode]EdgeInfo

In returns the nodes with incoming edges to the current node, with their object path

func (*FreeVarNode) Index 

func (a *FreeVarNode) Index() int

Index returns the free variable position in the function's signature

func (*FreeVarNode) LongID 

func (a *FreeVarNode) LongID() string

LongID returns a string identifier for the node

func (*FreeVarNode) Marks 

func (a *FreeVarNode) Marks() LocSet

Marks returns the location information of the node

func (*FreeVarNode) Out 

func (a *FreeVarNode) Out() map[GraphNode]EdgeInfo

Out returns the nodes the graph node's data flows to, with their object path

func (*FreeVarNode) ParentName 

func (a *FreeVarNode) ParentName() string

ParentName returns the name of the parent closure

func (*FreeVarNode) Position 

func (a *FreeVarNode) Position(c *AnalyzerState) token.Position

Position returns the estimated position of the node in the source

func (*FreeVarNode) SetLocs 

func (a *FreeVarNode) SetLocs(set LocSet)

SetLocs sets the locations information of the node

func (*FreeVarNode) SsaNode 

func (a *FreeVarNode) SsaNode() *ssa.FreeVar

SsaNode returns the ssa.Node the graph node models

func (*FreeVarNode) String 

func (a *FreeVarNode) String() string

func (*FreeVarNode) Type 

func (a *FreeVarNode) Type() types.Type

Type returns the type of the ssa node associated to the graph node

type GlobalNode 

type GlobalNode struct {
	WriteLocations map[GraphNode]bool
	ReadLocations  map[GraphNode]bool
	// contains filtered or unexported fields
}

GlobalNode represents a global in the dataflow analysis. Operating on globals requires locking when analyzing functions in parallel

func (*GlobalNode) String 

func (g *GlobalNode) String() string

func (*GlobalNode) Type 

func (g *GlobalNode) Type() types.Type

Type returns the type of the global

func (*GlobalNode) Value 

func (g *GlobalNode) Value() ssa.Value

Value returns the ssa value of the node

type GraphNode 

type GraphNode interface {
	// ID returns the unique id of the node (id is unique within a given summary)
	ID() uint32

	// LongID returns the unique string id of the node, including the id of the parent function
	LongID() string

	// Graph returns the graph the node belongs to
	Graph() *SummaryGraph

	// Out returns the outgoing edges from the node. The DataflowEdge specifies a possible "object Path", e.g. a field
	// or a slice index, which refines the dataflow information
	Out() map[GraphNode]EdgeInfo

	// In returns the incoming edges from the node. The DataflowEdge specifies a possible "object Path", e.g. a field
	// or a slice index, which refines the dataflow information (currently not in use, "" or "*" means everything in
	// the edge flows to the destination).
	In() map[GraphNode]EdgeInfo

	// ParentName returns a string representing the parent object of the node.
	ParentName() string

	// Position returns the position of the node in the source code.
	Position(c *AnalyzerState) token.Position

	// String prints the string representation of the node.
	// All strings methods should return sanitized output. That is, the underlying information related to the source
	// code is sanitized before being returned.
	String() string

	// Type returns the type of the node
	Type() types.Type

	// Marks returns the loc-set of the node
	Marks() LocSet

	// SetLocs sets the loc-set of the node
	SetLocs(LocSet)

	// Equal lifts equality to the interface level
	Equal(GraphNode) bool
}

GraphNode represents nodes in the function summary graph. Those nodes are either input argument nodes, callgraph nodes, call arguments nodes or return nodes.

type IfNode 

type IfNode struct {
	// contains filtered or unexported fields
}

IfNode is used to track dataflow to if-statements (includes all types of branching). For now, this just contains the value that is being branched on (the if-condition).

func (*IfNode) Equal 

func (a *IfNode) Equal(node GraphNode) bool

Equal implements equality checking between nodes.

func (*IfNode) Graph 

func (a *IfNode) Graph() *SummaryGraph

Graph returns the parent summary graph of the node.

func (*IfNode) ID 

func (a *IfNode) ID() uint32

ID returns the integer id of the node in its parent graph.

func (*IfNode) In 

func (a *IfNode) In() map[GraphNode]EdgeInfo

In returns the nodes with incoming edges to the current node, with their object path.

func (*IfNode) LongID 

func (a *IfNode) LongID() string

LongID returns a string identifier for the node.

func (*IfNode) Marks 

func (a *IfNode) Marks() LocSet

Marks returns the location information of the node.

func (*IfNode) Out 

func (a *IfNode) Out() map[GraphNode]EdgeInfo

Out returns the nodes the graph node's data flows to, with their object path.

func (*IfNode) ParentName 

func (a *IfNode) ParentName() string

ParentName returns the name of the parent function.

func (*IfNode) Position 

func (a *IfNode) Position(c *AnalyzerState) token.Position

Position returns the position of the node.

func (*IfNode) SetLocs 

func (a *IfNode) SetLocs(set LocSet)

SetLocs sets the locations information of the node.

func (*IfNode) SsaNode 

func (a *IfNode) SsaNode() *ssa.If

SsaNode returns the if-instruction.

func (*IfNode) String 

func (a *IfNode) String() string

func (*IfNode) Type 

func (a *IfNode) Type() types.Type

Type returns the type of the value in the if-condition.

type IndexT 

type IndexT = uint32

IndexT is the type used to index values and instructions

type IndexedGraphNode 

type IndexedGraphNode interface {
	// ParentNode returns the parent graph node of and indexed graph node, e.g. the CallNode of a call argument
	// or the ClosureNode of a bound variable. Returns itself for a ParamNode
	ParentNode() GraphNode

	// Index returns the position of the node in the parent node structure (argument or bound variable position)
	Index() int
}

An IndexedGraphNode is a graph node with additional information abouts its index in a parent node (e.g. argument in a call)

type InstructionValueWithAccessPath 

type InstructionValueWithAccessPath struct {
	Value       ssa.Value
	Instruction ssa.Instruction
	Path        string
}

InstructionValueWithAccessPath represents a value at an instruction with a specific access path. The boolean FromProcEntry is used by some functions to differentiate how the value was collected.

type InterProceduralFlowGraph 

type InterProceduralFlowGraph struct {
	// ForwardEdges represents edges between nodes belonging to different sub-graphs (inter-procedural version of
	// (GraphNode).Out)
	ForwardEdges map[GraphNode]map[GraphNode]bool

	// BackwardEdges represents backward edges between nodes belonging to different sub-graphs (inter-procedural
	// version of (GraphNode).In)
	BackwardEdges map[GraphNode]map[GraphNode]bool

	// Summaries maps the functions in the SSA to their summaries
	Summaries map[*ssa.Function]*SummaryGraph

	// AnalyzerState is a pointer to the analyzer state from which the dataflow graph is computed
	AnalyzerState *AnalyzerState

	// Globals are edges between global nodes and the nodes that access the global
	Globals map[*GlobalNode]map[*AccessGlobalNode]bool
	// contains filtered or unexported fields
}

InterProceduralFlowGraph represents an inter-procedural data flow graph.

func NewInterProceduralFlowGraph 

func NewInterProceduralFlowGraph(summaries map[*ssa.Function]*SummaryGraph,
	state *AnalyzerState) InterProceduralFlowGraph

NewInterProceduralFlowGraph returns a new non-built cross function flow graph.

func (*InterProceduralFlowGraph) BuildAndRunVisitor 

func (g *InterProceduralFlowGraph) BuildAndRunVisitor(c *AnalyzerState, visitor Visitor,
	isEntryPoint func(ssa.Node) bool)

BuildAndRunVisitor runs the pass on the inter-procedural flow graph. First, it calls the BuildGraph function to build the inter-procedural dataflow graph. Then, it looks for every entry point designated by the isEntryPoint predicate to RunIntraProcedural the visitor on those points (using the *InterProceduralFlowGraph.RunVisitorOnEntryPoints function).

Most of the logic of the analysis will be in the visitor's implementation by the client. This function is mostly a driver that sequences the analyses in the right order with small checks.

This function does nothing if there are no summaries (i.e. `len(g.summaries) == 0`) or if `cfg.SkipInterprocedural` is set to true.

func (*InterProceduralFlowGraph) BuildGraph 

func (g *InterProceduralFlowGraph) BuildGraph()

BuildGraph builds the cross function flow graph by connecting summaries together

func (*InterProceduralFlowGraph) InsertSummaries 

func (g *InterProceduralFlowGraph) InsertSummaries(g2 InterProceduralFlowGraph)

InsertSummaries inserts all the summaries from g2 in g

func (*InterProceduralFlowGraph) IsBuilt 

func (g *InterProceduralFlowGraph) IsBuilt() bool

IsBuilt returns true iff the cross function graph has been built, i.e. the summaries have been linked together.

func (*InterProceduralFlowGraph) Print 

func (g *InterProceduralFlowGraph) Print(w io.Writer)

Print prints each of the function summaries in the graph.

func (*InterProceduralFlowGraph) RunVisitorOnEntryPoints 

func (g *InterProceduralFlowGraph) RunVisitorOnEntryPoints(visitor Visitor,
	isEntryPointSsa func(ssa.Node) bool,
	isEntryPointGraphNode func(node GraphNode) bool)

RunVisitorOnEntryPoints runs the visitor on the entry points designated by either the isEntryPoint function or the isGraphEntryPoint function.

func (*InterProceduralFlowGraph) Sync 

func (g *InterProceduralFlowGraph) Sync()

Sync synchronizes inter-procedural information in the graph. This is useful if updating a summary generates nodes that may require edges to nodes in other functions.

type IntraAnalysisState 

type IntraAnalysisState struct {
	// contains filtered or unexported fields
}

IntraAnalysisState contains the information used by the intra-procedural dataflow analysis.

func (*IntraAnalysisState) Block 

func (state *IntraAnalysisState) Block() *ssa.BasicBlock

Block returns the current block of the analyzer state

func (*IntraAnalysisState) ChangedOnEndBlock 

func (state *IntraAnalysisState) ChangedOnEndBlock() bool

ChangedOnEndBlock indicates whether the analysis state has changed when finishing a block

func (*IntraAnalysisState) DoAlloc 

func (state *IntraAnalysisState) DoAlloc(x *ssa.Alloc)

DoAlloc is a no-op, unless that specific allocation needs to be tracked (the information will be deduced from the config)

func (*IntraAnalysisState) DoBinOp 

func (state *IntraAnalysisState) DoBinOp(binop *ssa.BinOp)

DoBinOp analyzes binary operations

func (*IntraAnalysisState) DoCall 

func (state *IntraAnalysisState) DoCall(call *ssa.Call)

DoCall analyzes a ssa.Call

func (*IntraAnalysisState) DoChangeInterface 

func (state *IntraAnalysisState) DoChangeInterface(x *ssa.ChangeInterface)

DoChangeInterface analyses ssa.ChangeInterface (a simple transferCopy)

func (*IntraAnalysisState) DoChangeType 

func (state *IntraAnalysisState) DoChangeType(x *ssa.ChangeType)

DoChangeType analyses ssa.ChangeType (a simple transferCopy)

func (*IntraAnalysisState) DoConvert 

func (state *IntraAnalysisState) DoConvert(x *ssa.Convert)

DoConvert analyzes a ssa.DoConvert (a simpleTransfer)

func (*IntraAnalysisState) DoDebugRef 

func (state *IntraAnalysisState) DoDebugRef(*ssa.DebugRef)

DoDebugRef is a no-op

func (*IntraAnalysisState) DoDefer 

func (state *IntraAnalysisState) DoDefer(_ *ssa.Defer)

DoDefer analyzes a ssa.Defer. Does nothing - defers are analyzed separately.

func (*IntraAnalysisState) DoExtract 

func (state *IntraAnalysisState) DoExtract(x *ssa.Extract)

DoExtract analyzers a ssa.Extract (a transfer with path "")

func (*IntraAnalysisState) DoField 

func (state *IntraAnalysisState) DoField(x *ssa.Field)

DoField analyzes field operations, with field-sensitivity

func (*IntraAnalysisState) DoFieldAddr 

func (state *IntraAnalysisState) DoFieldAddr(x *ssa.FieldAddr)

DoFieldAddr analyzes field addressing operations, with field sensitivity

func (*IntraAnalysisState) DoGo 

func (state *IntraAnalysisState) DoGo(g *ssa.Go)

DoGo analyses a go call like any function call. Use the escape analysis if you care about concurrency.

func (*IntraAnalysisState) DoIf 

func (state *IntraAnalysisState) DoIf(x *ssa.If)

DoIf is a no-op

func (*IntraAnalysisState) DoIndex 

func (state *IntraAnalysisState) DoIndex(x *ssa.Index)

DoIndex analyzes indexing with indexing sensitivity

func (*IntraAnalysisState) DoIndexAddr 

func (state *IntraAnalysisState) DoIndexAddr(x *ssa.IndexAddr)

DoIndexAddr analyzers operation where the address of an index is taken, with indexing sensitivity

func (*IntraAnalysisState) DoJump 

func (state *IntraAnalysisState) DoJump(*ssa.Jump)

DoJump is a no-op

func (*IntraAnalysisState) DoLookup 

func (state *IntraAnalysisState) DoLookup(x *ssa.Lookup)

DoLookup analyzes lookups without indexing sensitivity

func (*IntraAnalysisState) DoMakeChan 

func (state *IntraAnalysisState) DoMakeChan(*ssa.MakeChan)

DoMakeChan is a no-op

func (*IntraAnalysisState) DoMakeClosure 

func (state *IntraAnalysisState) DoMakeClosure(x *ssa.MakeClosure)

DoMakeClosure analyzes closures using markClosureNode

func (*IntraAnalysisState) DoMakeInterface 

func (state *IntraAnalysisState) DoMakeInterface(x *ssa.MakeInterface)

DoMakeInterface analyzers a ssa.MakeInterface (a transferCopy)

func (*IntraAnalysisState) DoMakeMap 

func (state *IntraAnalysisState) DoMakeMap(*ssa.MakeMap)

DoMakeMap is a no-op

func (*IntraAnalysisState) DoMakeSlice 

func (state *IntraAnalysisState) DoMakeSlice(*ssa.MakeSlice)

DoMakeSlice is a no-op

func (*IntraAnalysisState) DoMapUpdate 

func (state *IntraAnalysisState) DoMapUpdate(x *ssa.MapUpdate)

DoMapUpdate analyzes map updates without indexing sensitivity

func (*IntraAnalysisState) DoNext 

func (state *IntraAnalysisState) DoNext(x *ssa.Next)

DoNext transfers marks from the input of next to the output

func (*IntraAnalysisState) DoPanic 

func (state *IntraAnalysisState) DoPanic(_ *ssa.Panic)

DoPanic is a no-op; panic are handled separately

func (*IntraAnalysisState) DoPhi 

func (state *IntraAnalysisState) DoPhi(phi *ssa.Phi)

DoPhi transfers marks from all incoming edges to the phi-value

func (*IntraAnalysisState) DoRange 

func (state *IntraAnalysisState) DoRange(x *ssa.Range)

DoRange analyzes the range by simply transferring marks from the input of the range to the iterator

func (*IntraAnalysisState) DoReturn 

func (state *IntraAnalysisState) DoReturn(_ *ssa.Return)

DoReturn is a no-op

func (*IntraAnalysisState) DoRunDefers 

func (state *IntraAnalysisState) DoRunDefers(r *ssa.RunDefers)

DoRunDefers analyzes the defers of the function by simulating the defers stack

func (*IntraAnalysisState) DoSelect 

func (state *IntraAnalysisState) DoSelect(x *ssa.Select)

DoSelect iterates through each of the select states to apply the transfer function

func (*IntraAnalysisState) DoSend 

func (state *IntraAnalysisState) DoSend(x *ssa.Send)

DoSend analyzes a send operation on a channel. This does not take concurrency into account

func (*IntraAnalysisState) DoSlice 

func (state *IntraAnalysisState) DoSlice(x *ssa.Slice)

DoSlice analyzes slicing operations

func (*IntraAnalysisState) DoSliceArrayToPointer 

func (state *IntraAnalysisState) DoSliceArrayToPointer(x *ssa.SliceToArrayPointer)

DoSliceArrayToPointer analyzes a ssa.SliceToArrayPointer (a simpleTransfer)

func (*IntraAnalysisState) DoStore 

func (state *IntraAnalysisState) DoStore(x *ssa.Store)

DoStore analyzes store operations

func (*IntraAnalysisState) DoTypeAssert 

func (state *IntraAnalysisState) DoTypeAssert(x *ssa.TypeAssert)

DoTypeAssert views type assertions as a simple transfer of marks

func (*IntraAnalysisState) DoUnOp 

func (state *IntraAnalysisState) DoUnOp(x *ssa.UnOp)

DoUnOp analyzes unary operations and checks the operator to see whether is a load or a channel receive

func (*IntraAnalysisState) FlowInfo 

func (state *IntraAnalysisState) FlowInfo() *FlowInformation

FlowInfo returns the flow information of the state

func (*IntraAnalysisState) NewBlock 

func (state *IntraAnalysisState) NewBlock(block *ssa.BasicBlock)

NewBlock is called upon each new visited block

func (*IntraAnalysisState) Post 

func (state *IntraAnalysisState) Post(_ ssa.Instruction)

Post is applied after every instruction. This is necessary to satisfy the interface, and can also be used for debugging purposes.

func (*IntraAnalysisState) Pre 

func (state *IntraAnalysisState) Pre(ins ssa.Instruction)

Pre is executed before an instruction is visited. For the dataflow analysis, Pre transfers all the reachable values of the previous instruction to the current instruction; Pre ensures that the analysis is a monotone analysis.

type IntraProceduralResult 

type IntraProceduralResult struct {
	Summary *SummaryGraph // Summary is the procedure summary built by the analysis
	Time    time.Duration // Time it took to compute the summary
}

IntraProceduralResult holds the results of the intra-procedural analysis.

func IntraProceduralAnalysis 

func IntraProceduralAnalysis(state *AnalyzerState,
	function *ssa.Function,
	buildSummary bool,
	id uint32,
	shouldTrack func(*config.Config, *pointer.Result, ssa.Node) bool,
	postBlockCallback func(*IntraAnalysisState)) (IntraProceduralResult, error)

IntraProceduralAnalysis is the main entry point of the intra procedural analysis.

type KeyType 

type KeyType = string

KeyType is a value type to represents keys

type LocSet 

type LocSet = map[ssa.Instruction]bool

LocSet is a set of locations; here, a set of instructions

type Mark 

type Mark struct {
	// Node is the ssa node that the mark is tracking
	Node ssa.Node

	// MarkType is the type of the mark
	Type MarkType

	// Qualifier gives more information about which sub-Value of the current ssa Value is referred to by this mark
	Qualifier ssa.Value

	// Index specifies an index of the tuple element referred to by this mark. Node's type must be a tuple.
	// A Value of -1 indicates this can be ignored
	Index int

	// Label holds additional information about the mark, for example the original access path relative to the
	// parameter the mark is tracking
	Label string
}

Mark is a node with additional information about its type and region Path (matching the paths in pointer analysis). This is used to mark dataflow between nodes.

func NewMark 

func NewMark(node ssa.Node, typ MarkType, qualifier ssa.Value, index int, label string) Mark

NewMark creates a source with a single type. Using this as constructor enforces that users provide an explicit Value for index, whose default Value has a meaning that might not be intended

func (Mark) IsBoundVar 

func (m Mark) IsBoundVar() bool

IsBoundVar returns true if the source is a closure free variable.

func (Mark) IsCallReturn 

func (m Mark) IsCallReturn() bool

IsCallReturn returns true if the source is a call return.

func (Mark) IsCallSiteArg 

func (m Mark) IsCallSiteArg() bool

IsCallSiteArg returns true if the source is a call site argument. If it returns true, then s.qualifier must be non-nil.

func (Mark) IsClosure 

func (m Mark) IsClosure() bool

IsClosure returns true if the source is a closure

func (Mark) IsDefault 

func (m Mark) IsDefault() bool

IsDefault returns true if the source is a taint source.

func (Mark) IsFreeVar 

func (m Mark) IsFreeVar() bool

IsFreeVar returns true if the source is a closure free variable.

func (Mark) IsGlobal 

func (m Mark) IsGlobal() bool

IsGlobal returns true if the source is a global

func (Mark) IsIf 

func (m Mark) IsIf() bool

IsIf returns true if the source is an if condition.

func (Mark) IsParameter 

func (m Mark) IsParameter() bool

IsParameter returns true if the source is a function parameter.

func (Mark) IsSynthetic 

func (m Mark) IsSynthetic() bool

IsSynthetic returns true if the source is synthetic.

func (Mark) String 

func (m Mark) String() string

type MarkType 

type MarkType int

MarkType identifies different marks that can be propagated during the analysis. In the context of building function summaries, one can see the mark as a way to track where the data is flowing from. When running the taint analysis, the DefaultMark mark tracks tainted values. The design is open to the addition of other taint types. 

const (
	// Parameter is a function parameter.
	Parameter MarkType = 1 << iota
	// FreeVar is a free variable in a closure.
	FreeVar
	// DefaultMark is a Value with a mark.
	DefaultMark
	// CallSiteArg is a call site argument.
	CallSiteArg
	// CallReturn is a call site return.
	CallReturn
	// Closure is a closure creation site
	Closure
	// BoundVar is a variable bound by a closure
	BoundVar
	// Global is package global
	Global
	// Synthetic node type for any other node.
	Synthetic
	// If is an if statement.
	If
)

func (MarkType) String 

func (m MarkType) String() string

type MarkWithAccessPath 

type MarkWithAccessPath struct {
	Mark       *Mark
	AccessPath string
}

A MarkWithAccessPath is a mark with an access path

type NodeTree 

type NodeTree[T GraphNode] struct {
	// Label is the graph node linked to the current NodeTree
	Label T

	// Origin is the root of the node tree
	Origin *NodeTree[T]

	// Parent is the parent of the current node
	Parent *NodeTree[T]

	Children []*NodeTree[T]
	// contains filtered or unexported fields
}

NodeTree is a data structure to represent node trees built during the traversal of the interprocedural data flow graph.

func NewNodeTree 

func NewNodeTree[T GraphNode](initNode T) *NodeTree[T]

NewNodeTree returns a new node tree with the initial node label provided

func (*NodeTree[T]) Add 

func (n *NodeTree[T]) Add(node T) *NodeTree[T]

Add appends a node to the current node's children and return the newly created child

func (*NodeTree[T]) Append 

func (n *NodeTree[T]) Append(tree *NodeTree[T]) *NodeTree[T]

func (*NodeTree[T]) GetLassoHandle 

func (n *NodeTree[T]) GetLassoHandle() *NodeTree[T]

GetLassoHandle checks if the trace (path from root to node) is more than one node long and the current node has the same call as the last node. If the trace is a lasso, the end of the handle is returned. Otherwise, the function returns nil.

(nil safe)

func (*NodeTree[T]) Key 

func (n *NodeTree[T]) Key() string

Key returns the key of the node. If the node has been constructed only using NewNodeTree and Add, the key will be unique for each node. If the node is nil, returns the empty string.

(nil-safe)

func (*NodeTree[T]) Len 

func (n *NodeTree[T]) Len() int

Len returns the height of the node tree (length of a path from the root to the current node

func (*NodeTree[T]) String 

func (n *NodeTree[T]) String() string

func (*NodeTree[T]) SummaryString 

func (n *NodeTree[T]) SummaryString() string

SummaryString returns a short summary of n.

func (*NodeTree[T]) ToSlice 

func (n *NodeTree[T]) ToSlice() []T

ToSlice returns a slice of the nodes on the path from the root to the current node. The elements are ordered with the root first and the current node last.

type NodeWithTrace 

type NodeWithTrace struct {
	Node         GraphNode
	Trace        *NodeTree[*CallNode]
	ClosureTrace *NodeTree[*ClosureNode]
}

NodeWithTrace represents a GraphNode with two traces, a Trace for the call stack at the node and a ClosureTrace for the stack of makeClosure instructions at the node

func (NodeWithTrace) Key 

func (g NodeWithTrace) Key() KeyType

Key generates an object of type KeyType whose *value* identifies the value of g uniquely. If two NodeWithTrace objects represent the same node with the same call and closure traces, the Key() method will return the same value

type ParamNode 

type ParamNode struct {
	// contains filtered or unexported fields
}

ParamNode is a node that represents a parameter of the function (input argument)

func (*ParamNode) Equal 

func (a *ParamNode) Equal(node GraphNode) bool

Equal implements comparison for graph nodes

func (*ParamNode) Graph 

func (a *ParamNode) Graph() *SummaryGraph

Graph returns the parent summary graph of the node

func (*ParamNode) ID 

func (a *ParamNode) ID() uint32

ID returns the integer id of the node in its parent graph

func (*ParamNode) In 

func (a *ParamNode) In() map[GraphNode]EdgeInfo

In returns the nodes with incoming edges to the current node, with their object path

func (*ParamNode) Index 

func (a *ParamNode) Index() int

Index returns the parameter position of the node in the function's signature

func (*ParamNode) LongID 

func (a *ParamNode) LongID() string

LongID returns a string identifier for the node

func (*ParamNode) Marks 

func (a *ParamNode) Marks() LocSet

Marks returns the location information of the node

func (*ParamNode) Out 

func (a *ParamNode) Out() map[GraphNode]EdgeInfo

Out returns the nodes the graph node's data flows to, with their object path

func (*ParamNode) ParentName 

func (a *ParamNode) ParentName() string

ParentName returns the name of the parent function

func (*ParamNode) ParentNode 

func (a *ParamNode) ParentNode() GraphNode

ParentNode returns the node itself

func (*ParamNode) Position 

func (a *ParamNode) Position(c *AnalyzerState) token.Position

Position returns the estimated position of the node in the source

func (*ParamNode) SetLocs 

func (a *ParamNode) SetLocs(set LocSet)

SetLocs sets the locations information of the node

func (*ParamNode) SsaNode 

func (a *ParamNode) SsaNode() *ssa.Parameter

SsaNode returns the ssa.Node the graph node models

func (*ParamNode) String 

func (a *ParamNode) String() string

func (*ParamNode) Type 

func (a *ParamNode) Type() types.Type

Type returns the type of the ssa node associated to the graph node

type ParamStack 

type ParamStack struct {
	Param *ParamNode
	Prev  *ParamStack
}

ParamStack represents a stack of parameters.

type ReturnValNode 

type ReturnValNode struct {
	// contains filtered or unexported fields
}

A ReturnValNode is a node that represents a Value returned by a function

func (*ReturnValNode) Equal 

func (a *ReturnValNode) Equal(node GraphNode) bool

Equal implements comparison for graph nodes

func (*ReturnValNode) Graph 

func (a *ReturnValNode) Graph() *SummaryGraph

Graph returns the parent summary graph of the node

func (*ReturnValNode) ID 

func (a *ReturnValNode) ID() uint32

ID returns the integer id of the node in its parent graph

func (*ReturnValNode) In 

func (a *ReturnValNode) In() map[GraphNode]EdgeInfo

In returns the nodes with incoming edges to the current node, with their object path

func (*ReturnValNode) Index 

func (a *ReturnValNode) Index() int

Index returns the tuple index of the return node

func (*ReturnValNode) LongID 

func (a *ReturnValNode) LongID() string

LongID returns a string identifier for the node

func (*ReturnValNode) Marks 

func (a *ReturnValNode) Marks() LocSet

Marks returns the location information of the node

func (*ReturnValNode) Out 

func (a *ReturnValNode) Out() map[GraphNode]EdgeInfo

Out returns the nodes the graph node's data flows to, with their object path

func (*ReturnValNode) ParentName 

func (a *ReturnValNode) ParentName() string

ParentName return the name of the parent function

func (*ReturnValNode) Position 

func (a *ReturnValNode) Position(c *AnalyzerState) token.Position

Position returns the estimated position of the node in the source

func (*ReturnValNode) SetLocs 

func (a *ReturnValNode) SetLocs(_ LocSet)

SetLocs sets the locations information of the node

func (*ReturnValNode) String 

func (a *ReturnValNode) String() string

func (*ReturnValNode) Type 

func (a *ReturnValNode) Type() types.Type

Type returns the return type of the parent function

type SsaInfo 

type SsaInfo struct {
	Prog     *ssa.Program
	Packages []*ssa.Package
	Mains    []*ssa.Package
}

SsaInfo is holds all the information from a built ssa program with main packages

type SummaryGraph 

type SummaryGraph struct {
	// the unique ID of the summary
	ID uint32

	// true if summary graph is Constructed, false if it is a dummy
	Constructed bool

	// true if the summary is built from an interface's dataflow contract
	IsInterfaceContract bool

	// true if the summary is pre-summarized
	//
	// pre-summarized summaries are either:
	// - pre-defined in the summaries package, or
	// - loaded from an external summary contract file
	IsPreSummarized bool

	// the ssa function it summarizes
	Parent *ssa.Function

	// the parameters of the function, associated to ParamNode
	Params map[ssa.Node]*ParamNode

	// the free variables of the function, associated to FreeVarNode
	FreeVars map[ssa.Node]*FreeVarNode

	// the call sites of the function
	Callsites map[ssa.CallInstruction]*CallNode

	// the call instructions are linked to CallNode.
	Callees map[ssa.CallInstruction]map[*ssa.Function]*CallNode

	// the MakeClosure nodes in the function  are linked to ClosureNode
	CreatedClosures map[ssa.Instruction]*ClosureNode

	// the MakeClosure nodes referring to this function
	ReferringMakeClosures map[ssa.Instruction]*ClosureNode

	// the synthetic nodes of the function
	SyntheticNodes map[ssa.Instruction]*SyntheticNode

	// the label nodes of the function
	BoundLabelNodes map[ssa.Instruction]*BoundLabelNode

	// the nodes accessing global information
	AccessGlobalNodes map[ssa.Instruction]map[ssa.Value]*AccessGlobalNode

	// the return instructions are linked to ReturnNode, one per Value in a tuple returned
	Returns map[ssa.Instruction][]*ReturnValNode

	// the if statements of the function
	Ifs map[ssa.Instruction]*IfNode
	// contains filtered or unexported fields
}

SummaryGraph is the function dataflow summary graph.

func BuildSummary 

func BuildSummary(s *AnalyzerState, function *ssa.Function) *SummaryGraph

BuildSummary builds a summary for function and returns it. If the summary was already built, i.e. there in a summary corresponding to the function in the flow graph, then the summary is constructed by running the intra-procedural dataflow analysis. If the summary was not already in the flow graph of the state, it creates a new summary, adds it to the flow graph and then runs the intra-procedural dataflow analysis.

func NewPredefinedSummary 

func NewPredefinedSummary(f *ssa.Function, id uint32) *SummaryGraph

NewPredefinedSummary searches for a summary for f in the summaries packages and builds the SummaryGraph it represents. The resulting summary will only contain parameter and return nodes and edges between those. It will not include any call node or call argument nodes.

If f is nil, or f has no predefined summary, then the function returns nil. If f has a predefined summary, then the returned summary graph is marked as constructed. cg can be nil.

func NewSummaryGraph 

func NewSummaryGraph(s *AnalyzerState, f *ssa.Function, id uint32,
	shouldTrack func(*config.Config, *pointer.Result, ssa.Node) bool,
	postBlockCallBack func(state *IntraAnalysisState)) *SummaryGraph

NewSummaryGraph builds a new summary graph given a function and its corresponding node. Returns a non-nil Value if and only if f is non-nil. If s is nil, this will not populate the callees of the summary. If non-nil, the returned summary graph is marked as not constructed.

func (*SummaryGraph) AddAccessGlobalNode 

func (g *SummaryGraph) AddAccessGlobalNode(instr ssa.Instruction, global *GlobalNode)

AddAccessGlobalNode adds a global node at instruction instr (the location) accessing the global (the package-level global variable). This does not modify the GlobalNode

func (*SummaryGraph) ForAllNodes 

func (g *SummaryGraph) ForAllNodes(f func(n GraphNode))

ForAllNodes applies f to all graph nodes

func (*SummaryGraph) PopulateGraphFromSummary 

func (g *SummaryGraph) PopulateGraphFromSummary(summary summaries.Summary, isInterface bool)

PopulateGraphFromSummary populates the summary from a predefined summary provided as argument. isInterface indicates whether this predefined summary comes from an interface contract.

func (*SummaryGraph) PrettyPrint 

func (g *SummaryGraph) PrettyPrint(outEdgesOnly bool, w io.Writer)

PrettyPrint prints the summary graph to w in a readable format.

func (*SummaryGraph) Print 

func (g *SummaryGraph) Print(outEdgesOnly bool, w io.Writer)

Print the summary graph to w in the graphviz format. If g is nil, then prints the empty graph "subgraph {}"

func (*SummaryGraph) PrintNodes 

func (g *SummaryGraph) PrintNodes(w io.Writer)

PrintNodes writes all the nodes in the graph to the writer

func (*SummaryGraph) ReturnType 

func (g *SummaryGraph) ReturnType() *types.Tuple

ReturnType returns the return type of the function summarized

func (*SummaryGraph) ShowAndClearErrors 

func (g *SummaryGraph) ShowAndClearErrors(w io.Writer)

ShowAndClearErrors writes the errors in the graph to the writer and clears them

func (*SummaryGraph) SyncGlobals 

func (g *SummaryGraph) SyncGlobals()

SyncGlobals must be executed after the summary is built in order to synchronize the information between the global access node (write or read to a global in the function) and the GlobalNode that tracks the information about read and write locations of that global.

type SyntheticNode 

type SyntheticNode struct {
	// contains filtered or unexported fields
}

A SyntheticNode can be used to represent any other type of node.

func (*SyntheticNode) Equal 

func (a *SyntheticNode) Equal(node GraphNode) bool

Equal implements comparison for graph nodes

func (*SyntheticNode) Graph 

func (a *SyntheticNode) Graph() *SummaryGraph

Graph returns the parent summary graph of the node

func (*SyntheticNode) ID 

func (a *SyntheticNode) ID() uint32

ID returns the integer id of the node in its parent graph

func (*SyntheticNode) In 

func (a *SyntheticNode) In() map[GraphNode]EdgeInfo

In returns the nodes with incoming edges to the current node, with their object path

func (*SyntheticNode) Instr 

func (a *SyntheticNode) Instr() ssa.Instruction

Instr correspond to the instruction matching that synthetic node

func (*SyntheticNode) LongID 

func (a *SyntheticNode) LongID() string

LongID returns a string identifier for the node

func (*SyntheticNode) Marks 

func (a *SyntheticNode) Marks() LocSet

Marks returns the location information of the node

func (*SyntheticNode) Out 

func (a *SyntheticNode) Out() map[GraphNode]EdgeInfo

Out returns the nodes the graph node's data flows to, with their object path

func (*SyntheticNode) ParentName 

func (a *SyntheticNode) ParentName() string

ParentName returns the name of the parent function of the synthetic node

func (*SyntheticNode) Position 

func (a *SyntheticNode) Position(c *AnalyzerState) token.Position

Position returns the estimated position of the node in the source

func (*SyntheticNode) SetLocs 

func (a *SyntheticNode) SetLocs(set LocSet)

SetLocs sets the locations information of the node

func (*SyntheticNode) String 

func (a *SyntheticNode) String() string

func (*SyntheticNode) Type 

func (a *SyntheticNode) Type() types.Type

Type returns the type of the value the synthetic node abstracts

type ValueWithAccessPath 

type ValueWithAccessPath struct {
	Value ssa.Value
	Path  string
}

A ValueWithAccessPath is a value with an access path, e.g. a value "x" with an access path ".field1" represents member field1 of the struct x.

type Visitor 

type Visitor interface {
	Visit(s *AnalyzerState, entrypoint NodeWithTrace)
}

Visitor represents a visitor that runs an inter-procedural analysis from entrypoint.

type VisitorKind 

type VisitorKind = int

A VisitorKind should be either DefaultTracing or ClosureTracing and defines the behaviour of the Visitor 

const (
	// DefaultTracing is for the default dataflow analysis mode
	DefaultTracing VisitorKind = 1 << iota
	// ClosureTracing denotes the mode where the visitor is used to follow a closure
	ClosureTracing
)

type VisitorNode 

type VisitorNode struct {
	NodeWithTrace
	Prev        *VisitorNode
	Depth       int
	AccessPaths []string
	Status      VisitorNodeStatus
	// contains filtered or unexported fields
}

VisitorNode represents a node in the inter-procedural dataflow graph to be visited.

func (*VisitorNode) AddChild 

func (v *VisitorNode) AddChild(c *VisitorNode)

AddChild adds a child to the node

func (*VisitorNode) Key 

func (v *VisitorNode) Key() KeyType

Key returns a unique string representation for the node with its trace

type VisitorNodeStatus 

type VisitorNodeStatus struct {
	Kind        VisitorKind
	TracingInfo *closureTracingInfo
}

VisitorNodeStatus represents the status of a visitor node. It is either in default mode, in which case the Index does not mean anything, or it is in ClosureTracing mode, in which case the index represents the index of the bound variable that needs to be traced to a closure call.

func (VisitorNodeStatus) CurrentClosure 

func (v VisitorNodeStatus) CurrentClosure() *SummaryGraph

CurrentClosure returns the closure being currently traces by the node status

func (VisitorNodeStatus) PopClosure 

func (v VisitorNodeStatus) PopClosure() VisitorNodeStatus

PopClosure pops the current closure from the stack of closures being traces

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.