worklist

Documentation

Overview

Contains helper method for initializing the algorithm

Index

• func DoAnalysis(path string, sourcefiles []string, sourceAndSinkFile string, allpkgs bool, ...) error
• func NewTransition(context *ValueContext, targetContext *ValueContext, node ssa.Instruction)
• type ContextCallSite
  • func NewContextCallSite(context *ValueContext, node ssa.Instruction) *ContextCallSite
  • func (c *ContextCallSite) CheckAndHandleChange() error
  • func (c *ContextCallSite) Context() *ValueContext
  • func (c *ContextCallSite) Equal(ccs2 *ContextCallSite) bool
  • func (c *ContextCallSite) GetIn() lattice.Latticer
  • func (c *ContextCallSite) GetOut() lattice.Latticer
  • func (c *ContextCallSite) Node() ssa.Instruction
  • func (c *ContextCallSite) SetIn(l lattice.Latticer)
  • func (c *ContextCallSite) SetOut(l lattice.Latticer)
  • func (c *ContextCallSite) String() string
• type ErrInFlows
  • func (e *ErrInFlows) Error() (s string)
  • func (e *ErrInFlows) Errors() []*taint.ErrLeak
  • func (e *ErrInFlows) NumberOfFlows() int
• type Transition
  • func (t1 *Transition) Context() *ValueContext
  • func (t1 *Transition) Equal(t2 *Transition) bool
  • func (t1 *Transition) Node() ssa.Instruction
  • func (t1 *Transition) String() string
  • func (t1 *Transition) TargetContext() *ValueContext
• type VCIfer
• type VCS
  • func (v VCS) String() string
• type ValueContext
  • func GetValueContext(callee *ssa.Function, pcaller []ssa.Value, lcaller lattice.Latticer, ...) (*ValueContext, error)
  • func (v *ValueContext) EntryValue() lattice.Latticer
  • func (v *ValueContext) Equal(v2 *ValueContext) bool
  • func (v *ValueContext) ExitValue() lattice.Latticer
  • func (v *ValueContext) GetID() int
  • func (v *ValueContext) GetIn() lattice.Latticer
  • func (v *ValueContext) GetOut() lattice.Latticer
  • func (v *ValueContext) INEqual(v2 *ValueContext, params []ssa.Value) (bool, error)
  • func (v *ValueContext) Method() *ssa.Function
  • func (v *ValueContext) NewEntryValue(ev lattice.Latticer)
  • func (v *ValueContext) NewExitValue(ev lattice.Latticer)
  • func (v *ValueContext) SameID(v2 *ValueContext) bool
  • func (v *ValueContext) SetIN(l lattice.Latticer)
  • func (v *ValueContext) String() string
  • func (v *ValueContext) UpdateOut(l lattice.Latticer) error
• type VcIdentifier
• type WlList
  • func NewWlList() *WlList
  • func (l *WlList) Add(c *ContextCallSite)
  • func (l *WlList) AddSucc(n *ContextCallSite)
  • func (l *WlList) Empty() bool
  • func (l *WlList) Len() int
  • func (l *WlList) RemoveFirst() *ContextCallSite
  • func (l *WlList) String() string

Functions

func DoAnalysis

func DoAnalysis(path string, sourcefiles []string, sourceAndSinkFile string, allpkgs bool, pkgs string, ptr bool) error

DoAnalysis handles the worklist algorithm. path is the relative path starting from $GOPATH sourcefiles are the source file which should be analyzed. sourceAndSinkFile is the file which contains the sources and sinks. error will be returned if an error occurs during execution. If a flow from a source to a sink occurs, the information will be packed into an error of type ErrInFlows. Comments with line xx refers to the algorithm of worklist (Figure 1)

func NewTransition

func NewTransition(context *ValueContext, targetContext *ValueContext, node ssa.Instruction)

NewTransition returns a Transition. context is the valuecontext of the "start" node. callSite is the ssa.Function which "goes" to the other context. targetContext is the valuecontext which is the "goal" of the flow. NewTransition appends the new transition to the transitions slice.

Types

type ContextCallSite

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

ContextCallSite is a data structure which holds a value context, a ssa.Instruction and the in and out lattice for this node.

func NewContextCallSite

func NewContextCallSite(context *ValueContext, node ssa.Instruction) *ContextCallSite

NewContextCallSite creates a new contextcallsite. context is the wanted value context node is the ssa.Instruction for the contextcallsite The in and out lattice is set to empty

func (*ContextCallSite) CheckAndHandleChange

func (c *ContextCallSite) CheckAndHandleChange() error

CheckAndHandleChange checks whether a value context has changed. In the case the value context has changed, it will add the successory of n's node to the worklist.

func (*ContextCallSite) Context

func (c *ContextCallSite) Context() *ValueContext

Context returns the valueContext of c

func (*ContextCallSite) Equal

func (c *ContextCallSite) Equal(ccs2 *ContextCallSite) bool

Equal tests whether two context callsites are equal

func (*ContextCallSite) GetIn

func (c *ContextCallSite) GetIn() lattice.Latticer

GetIn returns the in lattice of context c

func (*ContextCallSite) GetOut

func (c *ContextCallSite) GetOut() lattice.Latticer

GetOut returns the out lattice of context c

func (*ContextCallSite) Node

func (c *ContextCallSite) Node() ssa.Instruction

Node returns the ssa.Instruction of c

func (*ContextCallSite) SetIn

func (c *ContextCallSite) SetIn(l lattice.Latticer)

SetIn sets l to the input lattice for c. new_in = LUP(old_in, l) TODO: handle the error.

func (*ContextCallSite) SetOut

func (c *ContextCallSite) SetOut(l lattice.Latticer)

SetOut sets l to the output lattice for c. new_out = LUP(old_out, l) TODO: handle the error.

func (*ContextCallSite) String

func (c *ContextCallSite) String() string

String returns a string representation of c.

type ErrInFlows

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

ErrInFlows holds several ErrInFlow errors.

func (*ErrInFlows) Error

func (e *ErrInFlows) Error() (s string)

Error returns a string of all flows beeing in e.

func (*ErrInFlows) Errors

func (e *ErrInFlows) Errors() []*taint.ErrLeak

Error returns a string of all flows beeing in e.

func (*ErrInFlows) NumberOfFlows

func (e *ErrInFlows) NumberOfFlows() int

NumberOfFlows returns the number of taint.ErrLeaks in ErrInFlows

type Transition

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

Transition represents a transition from a value context to another value context. The transition is caused by a node which is a call in the context causing the change to the tagetContext.

func (*Transition) Context

func (t1 *Transition) Context() *ValueContext

Context returns the context of the caller

func (*Transition) Equal

func (t1 *Transition) Equal(t2 *Transition) bool

Equal tests whether two transitions are equal

func (*Transition) Node

func (t1 *Transition) Node() ssa.Instruction

Node returns the node of the transition

func (*Transition) String

func (t1 *Transition) String() string

String returns a readable string of a transition.

func (*Transition) TargetContext

func (t1 *Transition) TargetContext() *ValueContext

TagerContext returns the context of the callee

type VCIfer

type VCIfer interface {
	String() string
	// contains filtered or unexported methods
}

type VCS

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

func (VCS) String

func (v VCS) String() string

String returns a string reperesentation for v

type ValueContext

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

ValueContext is a struct to identify a value context A value context consists of a call, the entry and exit lattice. Further a value context has a unique id which helps to distinguish between different value contexts.

func GetValueContext

func GetValueContext(callee *ssa.Function, pcaller []ssa.Value, lcaller lattice.Latticer, isClosure bool) (*ValueContext, error)

GetValueContext returns a new value context, if the context is not known already. If the context is already known, the function returns the known context. If a new context is created, the in lattice will be set.

func (*ValueContext) EntryValue

func (v *ValueContext) EntryValue() lattice.Latticer

EntryValue returns the entryValue lattice of a valueContext

func (*ValueContext) Equal

func (v *ValueContext) Equal(v2 *ValueContext) bool

Equal returns true if the both vale contextes are equal. Comparision is based upon the method, the Lattices and the id.

func (*ValueContext) ExitValue

func (v *ValueContext) ExitValue() lattice.Latticer

ExitValue returns the exitValue lattice of a valueContext

func (*ValueContext) GetID

func (v *ValueContext) GetID() int

GetID returns the id of a valuecontext

func (*ValueContext) GetIn

func (v *ValueContext) GetIn() lattice.Latticer

func (*ValueContext) GetOut

func (v *ValueContext) GetOut() lattice.Latticer

func (*ValueContext) INEqual

func (v *ValueContext) INEqual(v2 *ValueContext, params []ssa.Value) (bool, error)

INEqual tests whether the entry Lattice of two value contexts are equal params are the parameter for the function which creates v. v2 is an arbitrary value context which should checked against .

func (*ValueContext) Method

func (v *ValueContext) Method() *ssa.Function

Method returns the ssa.Function of a valueContext

func (*ValueContext) NewEntryValue

func (v *ValueContext) NewEntryValue(ev lattice.Latticer)

NewEntryValue updates the entryValue of v with a least upper bound with ev.

func (*ValueContext) NewExitValue

func (v *ValueContext) NewExitValue(ev lattice.Latticer)

NewExitValue updated the exitValue of v with a least upper bound with ev.

func (*ValueContext) SameID

func (v *ValueContext) SameID(v2 *ValueContext) bool

SameID compares the id of v against the id of v2 and return true if v1.id == v2.id

func (*ValueContext) SetIN

func (v *ValueContext) SetIN(l lattice.Latticer)

SetIN sets the in value for a new value context. params are the parameters of the functions and only those will be added to the entry lattice. l is the entry lattice of the node which generates the new value context.

func (*ValueContext) String

func (v *ValueContext) String() string

String returns a readable version of a value context

func (*ValueContext) UpdateOut

func (v *ValueContext) UpdateOut(l lattice.Latticer) error

UpdateOut update the exit lattice of v with the lup of the current value and l.

type VcIdentifier

type VcIdentifier interface {
	// GetIn returns the entry lattice of a value context
	GetIn() lattice.Latticer
	// SetIn updates the entry lattice of a value context with l
	SetIn(l lattice.Latticer)
	// GetFunction returns the function of a value context
	GetFunction() *ssa.Function
	// SetFunction sets the function of a value context to f
	SetFunction(f *ssa.Function)
	// Equal returns true if the function and the entry lattice of two value contextes are equal
	Equal(v VcIdentifier) bool
}

VcIdentifier provides all the necessary methods to compare two value contexts

type WlList

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

WlList represents a simple implementation of a worklist. An element can only be added once and the list is a FiFo list.

func NewWlList

func NewWlList() *WlList

NewWlList returns a new worklist

func (*WlList) Add

func (l *WlList) Add(c *ContextCallSite)

Add adds a new contextCallsite to the list Does not update the position of a contextcallsite which is already in the list,

func (*WlList) AddSucc

func (l *WlList) AddSucc(n *ContextCallSite)

AddSucc adds all sccessors of n to the worklist

func (*WlList) Empty

func (l *WlList) Empty() bool

Empty returns true if no element is remaining in the worklist.

func (*WlList) Len

func (l *WlList) Len() int

Len returns the lenogth of the worklist

func (*WlList) RemoveFirst

func (l *WlList) RemoveFirst() *ContextCallSite

RemoveFirst returns the first contextcallsite of the worklit and removes it from the list.

func (*WlList) String

func (l *WlList) String() string