vasco.callgraph
Class PointsToGraph

java.lang.Object
  vasco.callgraph.PointsToGraph

public class PointsToGraph
extends Object

A data flow value representation for points-to analysis using allocation sites.

The points-to graph contains two types of edges: (1) from root variables (Local) to objects represented by allocation sites (AnyNewExpr), and (2) from objects to objects along fields (SootField).

Special artificial locals are used for string constants, class constants, return values, etc. and artificial sites are used for summary nodes. For arrays an artificial field is used to represent element access.

Author:

Rohan Padhye

Field Summary

static SootField	ARRAY_FIELD
static Constant	CLASS_CONST
static NewExpr	CLASS_SITE
static Local	GLOBAL_LOCAL
static NewExpr	GLOBAL_SITE
protected Map<AnyNewExpr,Map<SootField,Set<AnyNewExpr>>>	heap
static Local	RETURN_LOCAL
protected Map<Local,Set<AnyNewExpr>>	roots
static Local	STICKY_LOCAL
static Constant	STRING_CONST
static NewExpr	STRING_SITE
static NewExpr	SUMMARY_NODE

Constructor Summary

PointsToGraph()
Constructs a new empty points-to graph.

PointsToGraph(PointsToGraph other)
Constructs a copy of the given points-to graph.

Method Summary

void	assign(Local lhs, Local rhs) Assigns a root variable to a root variable.
void	assignConstant(Local lhs, Constant rhs) Assigns a constant to a root variable.
void	assignNew(Local lhs, AnyNewExpr allocSite) Assigns a root variable to a new object at a given allocation site.
void	assignSticky(Local sticky, Local parameter) Assigns the sticky local to a parameter.
void	assignSummary(Local lhs) Assigns a root variable to the summary node.
static boolean	canCast(SootClass fromClass, SootClass toClass) Determines whether an object of one class can be cast to another class.
boolean	containsEdge(Local var, AnyNewExpr node) Returns true only if there is an edge from the given root variable to the given heap node.
boolean	equals(Object obj)
void	gc() Removes all unreachable nodes from the edge sets.
void	getField(Local lhs, Local rhs, SootField field) Loads a field of an object into a root variable.
Set<AnyNewExpr>	getTargets(Local local) Returns the points-to set of a root variable.
int	hashCode()
void	kill(Local v) Removes all out-edges of the given variable
void	killWithoutGC(Local local)
void	setField(Local lhs, SootField field, Local rhs) Stores values pointed-to by one root variable into a field of objects pointed-to by another root variable.
void	setFieldConstant(Local lhs, SootField field, Constant rhs) Stores a constant into a field of objects pointed-to by a root variable.
void	setFieldNew(Local lhs, SootField field, AnyNewExpr allocSite) Stores a new object into a field of objects pointed-to by a root variable.
void	setFieldSummary(Local lhs, SootField field) Stores the summary node into a field of objects pointed-to by a root variable.
void	subtractHeap(PointsToGraph other) Removes nodes contained in the argument.
void	summarizeTargetFields(Local lhs)
String	toString()
void	union(PointsToGraph p, PointsToGraph q) Sets this graph to the union of the given arguments.

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Field Detail

ARRAY_FIELD

public static final SootField ARRAY_FIELD

GLOBAL_LOCAL

public static final Local GLOBAL_LOCAL

RETURN_LOCAL

public static final Local RETURN_LOCAL

STICKY_LOCAL

public static final Local STICKY_LOCAL

STRING_CONST

public static final Constant STRING_CONST

CLASS_CONST

public static final Constant CLASS_CONST

STRING_SITE

public static final NewExpr STRING_SITE

CLASS_SITE

public static final NewExpr CLASS_SITE

SUMMARY_NODE

public static final NewExpr SUMMARY_NODE

GLOBAL_SITE

public static final NewExpr GLOBAL_SITE

roots

protected Map<Local,Set<AnyNewExpr>> roots

heap

protected Map<AnyNewExpr,Map<SootField,Set<AnyNewExpr>>> heap

Constructor Detail

PointsToGraph

public PointsToGraph()

Constructs a new empty points-to graph.

PointsToGraph

public PointsToGraph(PointsToGraph other)

Constructs a copy of the given points-to graph.

Parameters:

other - the points-to graph to copy

Method Detail

containsEdge

public boolean containsEdge(Local var,
                            AnyNewExpr node)

Returns true only if there is an edge from the given root variable to the given heap node.

assign

public void assign(Local lhs,
                   Local rhs)

Assigns a root variable to a root variable.

assignConstant

public void assignConstant(Local lhs,
                           Constant rhs)

Assigns a constant to a root variable.

assignSticky

public void assignSticky(Local sticky,
                         Local parameter)

Assigns the sticky local to a parameter.

assignNew

public void assignNew(Local lhs,
                      AnyNewExpr allocSite)

Assigns a root variable to a new object at a given allocation site.

assignSummary

public void assignSummary(Local lhs)

Assigns a root variable to the summary node.

canCast

public static boolean canCast(SootClass fromClass,
                              SootClass toClass)

Determines whether an object of one class can be cast to another class.

Parameters:

fromClass - the source type

toClass - the target type

Returns:

true if and only if fromClass is a sub-type of (or implements) toClass

equals

public boolean equals(Object obj)

Overrides:

equals in class Object

gc

public void gc()

Removes all unreachable nodes from the edge sets.

getField

public void getField(Local lhs,
                     Local rhs,
                     SootField field)

Loads a field of an object into a root variable.

getTargets

public Set<AnyNewExpr> getTargets(Local local)

Returns the points-to set of a root variable.

hashCode

public int hashCode()

Overrides:

hashCode in class Object

kill

public void kill(Local v)

Removes all out-edges of the given variable

setField

public void setField(Local lhs,
                     SootField field,
                     Local rhs)

Stores values pointed-to by one root variable into a field of objects pointed-to by another root variable.

setFieldConstant

public void setFieldConstant(Local lhs,
                             SootField field,
                             Constant rhs)

Stores a constant into a field of objects pointed-to by a root variable.

setFieldNew

public void setFieldNew(Local lhs,
                        SootField field,
                        AnyNewExpr allocSite)

Stores a new object into a field of objects pointed-to by a root variable.

setFieldSummary

public void setFieldSummary(Local lhs,
                            SootField field)

Stores the summary node into a field of objects pointed-to by a root variable.

subtractHeap

public void subtractHeap(PointsToGraph other)

Removes nodes contained in the argument. This is used at call-edges.

summarizeTargetFields

public void summarizeTargetFields(Local lhs)

toString

public String toString()

Overrides:

toString in class Object

union

public void union(PointsToGraph p,
                  PointsToGraph q)

Sets this graph to the union of the given arguments.

killWithoutGC

public void killWithoutGC(Local local)