earpointer

Documentation

Overview

Package earpointer introduces a pointer analysis based on unifying equivalent abstract references (EAR), which implements Steensgaard's algorithm. Extensions include adding context sensitivity and field sensitivity. Abstract references defines the data structure to represent abstract heap.

Index

• Variables
• func NewState() *state
• type Context
  • func (ctx Context) String() string
• type Field
• type FieldMap
  • func (fmap FieldMap) String() string
• type Global
  • func MakeGlobal(global *ssa.Global) Global
  • func (g Global) String() string
  • func (g Global) Type() types.Type
  • func (g Global) Value() ssa.Value
• type Local
  • func MakeLocal(context *Context, reg ssa.Value) Local
  • func MakeLocalWithEmptyContext(reg ssa.Value) Local
  • func (l Local) String() string
  • func (l Local) Type() types.Type
  • func (l Local) Value() ssa.Value
• type Partitions
  • func (p *Partitions) FieldParents(ref Reference) []Reference
  • func (p *Partitions) Has(ref Reference) bool
  • func (p *Partitions) MembersForRep(rep Reference) []Reference
  • func (p *Partitions) NumPartitions() int
  • func (p *Partitions) PartitionFieldMap(ref Reference) FieldMap
  • func (p *Partitions) PartitionMembers(ref Reference) []Reference
  • func (p *Partitions) References() ReferenceSet
  • func (p *Partitions) Representative(ref Reference) Reference
  • func (p *Partitions) Representatives() ReferenceSet
  • func (p *Partitions) String() string
• type Reference
  • func MakeReference(context *Context, reg ssa.Value) Reference
• type ReferenceSet
• type SourceSinkTrace
  • func SourcesToSinks(funcSources source.ResultType, ...) []*SourceSinkTrace
• type Synthetic
  • func MakeSynthetic(kind SyntheticKind, ref Reference) Synthetic
  • func (s Synthetic) String() string
  • func (s Synthetic) Type() types.Type
  • func (s Synthetic) Value() ssa.Value
• type SyntheticKind

Variables

var Analyzer = &analysis.Analyzer{
	Name:       "earpointer",
	Doc:        "EAR pointer analysis",
	Flags:      config.FlagSet,
	Run:        run,
	ResultType: reflect.TypeOf(new(Partitions)),
	Requires:   []*analysis.Analyzer{buildssa.Analyzer},
}

Analyzer traverses the packages and constructs an EAR partitions unifying all the IR elements in these packages.

Functions

func NewState

func NewState() *state

NewState creates an empty abstract state.

Types

type Context

type Context []ssa.Instruction

Context represents the calling context of a reference. Typically, it contains a stack of call instructions.

func (Context) String

func (ctx Context) String() string

type Field

type Field struct {
	Name string
	// contains filtered or unexported fields
}

Field can be (1) a struct field linked to an IR field (Var); (2) or one with a name but not linked to any IR element (irField = nil).

type FieldMap

type FieldMap map[Field]Reference

FieldMap maps from Fields to a reference handle. It is used for maintaining points-to relationships for the fields of a reference partition. The number of fields is not expected to be high on average, so a tree map may be used instead to save memory.

func (FieldMap) String

func (fmap FieldMap) String() string

Pretty prints a field map.

type Global

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

Global is a heap partition that represents all abstract objects that a global of reference type can point to.

func MakeGlobal

func MakeGlobal(global *ssa.Global) Global

func (Global) String

func (g Global) String() string

func (Global) Type

func (g Global) Type() types.Type

func (Global) Value

func (g Global) Value() ssa.Value

type Local

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

Local is a heap partition that represents all abstract objects that a register of reference type can point to in a specific context.

func MakeLocal

func MakeLocal(context *Context, reg ssa.Value) Local

Constructs Reference for local "reg" in context "context". TODO: hashconst the object to save memory.

func MakeLocalWithEmptyContext

func MakeLocalWithEmptyContext(reg ssa.Value) Local

func (Local) String

func (l Local) String() string

func (Local) Type

func (l Local) Type() types.Type

func (Local) Value

func (l Local) Value() ssa.Value

type Partitions

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

Partitions represents the state with the partitions fully constructed, after which no more mutation operations will be performed. Its internal data structures are optimized for lookups only.

func (*Partitions) FieldParents

func (p *Partitions) FieldParents(ref Reference) []Reference

FieldParents returns the parents of a field reference. Return nil if ref has no parent. For example, return o for r if "o[x -> r]" is in partitions. This shall be called only after the partitions have been finalized.

func (*Partitions) Has

func (p *Partitions) Has(ref Reference) bool

Has returns true if "ref" is a reference present in the partitions.

func (*Partitions) MembersForRep

func (p *Partitions) MembersForRep(rep Reference) []Reference

MembersForRep gets the list of members in the partition for which "prep" is the representative. Precondition: "prep" must be a partition representative.

func (*Partitions) NumPartitions

func (p *Partitions) NumPartitions() int

NumPartitions returns the number of representatives (i.e., the size of the partition).

func (*Partitions) PartitionFieldMap

func (p *Partitions) PartitionFieldMap(ref Reference) FieldMap

PartitionFieldMap gets the partition-level field map for partition representative "ref". The result maps a field (ConstTermHandle type) to a reference that is a partition representative. Note "ref" must be a partition representative.

func (*Partitions) PartitionMembers

func (p *Partitions) PartitionMembers(ref Reference) []Reference

PartitionMembers gets the list of members in the partition to which "ref" belongs. Precondition: "ref" must be a reference present in the partitions.

func (*Partitions) References

func (p *Partitions) References() ReferenceSet

References gets all references.

func (*Partitions) Representative

func (p *Partitions) Representative(ref Reference) Reference

Representative gets the partition representative of reference "ref" ("ref" must belong to this partitions).

func (*Partitions) Representatives

func (p *Partitions) Representatives() ReferenceSet

Representatives gets all references that are partition representatives.

func (*Partitions) String

func (p *Partitions) String() string

Pretty printer

type Reference

type Reference interface {
	fmt.Stringer

	Type() types.Type // Return the data type of the underlying element
	Value() ssa.Value // Return the underlying local or global
}

Reference is the base interface for local, global, and synthetic references.

func MakeReference

func MakeReference(context *Context, reg ssa.Value) Reference

type ReferenceSet

type ReferenceSet map[Reference]bool

ReferenceSet is a hash set of references.

type SourceSinkTrace

type SourceSinkTrace struct {
	Src       *source.Source
	Sink      ssa.Instruction
	Callstack []ssa.Call
}

func SourcesToSinks

func SourcesToSinks(funcSources source.ResultType, isTaintField func(named *types.Named, index int) bool,
	heap *Partitions, conf *config.Config) []*SourceSinkTrace

Look for <source, sink> pairs by examining the heap alias information.

type Synthetic

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

Synthetic is for references created internally with an operator and an operand reference. It is for creating references not directly associated with an IR element. For example, (1) *r0 can be represented by using operator SyntheticValueOf (*); (2) a unknown field can be represented by using operator SyntheticField.

For example, when a struct is cloned, some fields may not appear in the IR,
these "unused" fields can be synthesized and stored in the heap.

func MakeSynthetic

func MakeSynthetic(kind SyntheticKind, ref Reference) Synthetic

Constructs synthetic reference.

func (Synthetic) String

func (s Synthetic) String() string

func (Synthetic) Type

func (s Synthetic) Type() types.Type

func (Synthetic) Value

func (s Synthetic) Value() ssa.Value

type SyntheticKind

type SyntheticKind int

const (
	SyntheticValueOf SyntheticKind = iota
	SyntheticField
)