worklist

package
v0.0.0-...-ad4f0ff Latest Latest
Warning

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

 Go to latest Published: Jun 25, 2019 License: MIT Imports: 15 Imported by: 0

Documentation

Overview

Contains helper method for initializing the algorithm

Index

Constants

This section is empty.

Variables

This section is empty.

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) 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

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.