soot.jimple.spark.pag
Class PAG

java.lang.Object
  soot.jimple.spark.pag.PAG

All Implemented Interfaces:

PointsToAnalysis

Direct Known Subclasses:

GeomPointsTo

public class PAG
extends Object
implements PointsToAnalysis

Pointer assignment graph.

Author:

Ondrej Lhotak

Field Summary

protected Map<Object,Object>	alloc
protected Map<Object,Object>	allocInv
protected Map<Pair,Set<Edge>>	assign2edges
HashMultiMap	callAssigns
Map<InvokeExpr,SootMethod>	callToMethod
protected ChunkedQueue	edgeQueue
protected static Node[]	EMPTY_NODE_ARRAY
protected Map<Object,Object>	load
protected Map<Object,Object>	loadInv
int	maxFinishNumber
NativeMethodDriver	nativeMethodDriver
protected SparkOptions	opts
protected P2SetFactory	setFactory
protected Map<Object,Object>	simple
protected Map<Object,Object>	simpleInv
protected boolean	somethingMerged
protected Map<Object,Object>	store
protected Map<Object,Object>	storeInv
protected TypeManager	typeManager
Map<InvokeExpr,Node>	virtualCallsToReceivers

Fields inherited from interface soot.PointsToAnalysis

ARRAY_ELEMENTS_NODE, CANONICAL_PATH, CANONICAL_PATH_LOCAL, CAST_NODE, DEFAULT_CLASS_LOADER, DEFAULT_CLASS_LOADER_LOCAL, EXCEPTION_NODE, FINALIZE_QUEUE, MAIN_CLASS_NAME_STRING, MAIN_CLASS_NAME_STRING_LOCAL, MAIN_THREAD_GROUP_NODE, MAIN_THREAD_GROUP_NODE_LOCAL, MAIN_THREAD_NODE, MAIN_THREAD_NODE_LOCAL, PHI_NODE, PRIVILEGED_ACTION_EXCEPTION, PRIVILEGED_ACTION_EXCEPTION_LOCAL, RETURN_NODE, RETURN_STRING_CONSTANT_NODE, STRING_ARRAY_NODE, STRING_ARRAY_NODE_LOCAL, STRING_NODE, STRING_NODE_LOCAL, THIS_NODE, THROW_NODE

Constructor Summary

PAG(SparkOptions opts)

Method Summary

boolean	addAllocEdge(AllocNode from, VarNode to)
void	addCallTarget(Edge e)
void	addCallTarget(MethodPAG srcmpag, MethodPAG tgtmpag, Stmt s, Context srcContext, Context tgtContext, Edge e) Adds method target as a possible target of the invoke expression in s.
void	addDereference(VarNode base) Adds the base of a dereference to the list of dereferenced variables.
boolean	addEdge(Node from, Node to) Adds an edge to the graph, returning false if it was already there.
Pair<Node,Node>	addInterproceduralAssignment(Node from, Node to, Edge e)
boolean	addLoadEdge(FieldRefNode from, VarNode to)
boolean	addSimpleEdge(VarNode from, VarNode to)
boolean	addStoreEdge(VarNode from, FieldRefNode to)
protected boolean	addToMap(Map<Object,Object> m, Node key, Node value)
Node[]	allocInvLookup(VarNode key)
Set<Object>	allocInvSources()
Iterator<Object>	allocInvSourcesIterator()
Node[]	allocLookup(AllocNode key)
QueueReader	allocNodeListener()
Set<Object>	allocSources()
Iterator<Object>	allocSourcesIterator()
void	cleanPAG() Delete all the assignment edges.
void	cleanUpMerges()
boolean	doAddAllocEdge(AllocNode from, VarNode to)
boolean	doAddLoadEdge(FieldRefNode from, VarNode to)
boolean	doAddSimpleEdge(VarNode from, VarNode to)
boolean	doAddStoreEdge(VarNode from, FieldRefNode to)
QueueReader	edgeReader()
AllocDotField	findAllocDotField(AllocNode an, SparkField field) Finds the AllocDotField for base AllocNode an and field field, or returns null.
ContextVarNode	findContextVarNode(Object baseValue, Context context) Finds the ContextVarNode for base variable value and context context, or returns null.
FieldRefNode	findGlobalFieldRefNode(Object baseValue, SparkField field) Finds the FieldRefNode for base variable value and field field, or returns null.
GlobalVarNode	findGlobalVarNode(Object value) Finds the GlobalVarNode for the variable value, or returns null.
FieldRefNode	findLocalFieldRefNode(Object baseValue, SparkField field) Finds the FieldRefNode for base variable value and field field, or returns null.
LocalVarNode	findLocalVarNode(Object value) Finds the LocalVarNode for the variable value, or returns null.
ArrayNumberer	getAllocDotFieldNodeNumberer()
ArrayNumberer	getAllocNodeNumberer()
List<VarNode>	getDereferences() Returns list of dereferences variables.
ArrayNumberer	getFieldRefNodeNumberer()
Map<Node,Tag>	getNodeTags()
int	getNumAllocNodes()
OnFlyCallGraph	getOnFlyCallGraph()
SparkOptions	getOpts() Returns SparkOptions for this graph.
P2SetFactory	getSetFactory()
TypeManager	getTypeManager()
ArrayNumberer	getVarNodeNumberer()
Node[]	loadInvLookup(VarNode key)
Set<Object>	loadInvSources()
Iterator<Object>	loadInvSourcesIterator()
Node[]	loadLookup(FieldRefNode key)
Set<Object>	loadSources()
Iterator<Object>	loadSourcesIterator()
protected Node[]	lookup(Map<Object,Object> m, Object key)
Set<Edge>	lookupEdgesForAssignment(Pair<Node,Node> val)
AllocDotField	makeAllocDotField(AllocNode an, SparkField field) Finds or creates the AllocDotField for base variable baseValue and field field, of type t.
AllocNode	makeAllocNode(Object newExpr, Type type, SootMethod m)
AllocNode	makeClassConstantNode(ClassConstant cc)
ContextVarNode	makeContextVarNode(LocalVarNode base, Context context) Finds or creates the ContextVarNode for base variable base and context context, of type type.
ContextVarNode	makeContextVarNode(Object baseValue, Type baseType, Context context, SootMethod method) Finds or creates the ContextVarNode for base variable baseValue and context context, of type type.
FieldRefNode	makeFieldRefNode(VarNode base, SparkField field) Finds or creates the FieldRefNode for base variable base and field field, of type type.
FieldRefNode	makeGlobalFieldRefNode(Object baseValue, Type baseType, SparkField field) Finds or creates the FieldRefNode for base variable baseValue and field field, of type type.
GlobalVarNode	makeGlobalVarNode(Object value, Type type) Finds or creates the GlobalVarNode for the variable value, of type type.
FieldRefNode	makeLocalFieldRefNode(Object baseValue, Type baseType, SparkField field, SootMethod method) Finds or creates the FieldRefNode for base variable baseValue and field field, of type type.
LocalVarNode	makeLocalVarNode(Object value, Type type, SootMethod method) Finds or creates the LocalVarNode for the variable value, of type type.
AllocNode	makeStringConstantNode(String s)
GlobalNodeFactory	nodeFactory()
OnFlyCallGraph	ofcg()
PointsToSet	reachingObjects(Context c, Local l) Returns the set of objects pointed to by variable l in context c.
PointsToSet	reachingObjects(Context c, Local l, SootField f) Returns the set of objects pointed to by instance field f of the objects pointed to by l in context c.
PointsToSet	reachingObjects(Local l) Returns the set of objects pointed to by variable l.
PointsToSet	reachingObjects(Local l, SootField f) Returns the set of objects pointed to by instance field f of the objects pointed to by l.
PointsToSet	reachingObjects(PointsToSet s, SootField f) Returns the set of objects pointed to by instance field f of the objects in the PointsToSet s.
PointsToSet	reachingObjects(SootField f) Returns the set of objects pointed to by static field f.
PointsToSet	reachingObjectsOfArrayElement(PointsToSet s) Returns the set of objects pointed to by elements of the arrays in the PointsToSet s.
void	setOnFlyCallGraph(OnFlyCallGraph ofcg)
Node[]	simpleInvLookup(VarNode key)
Set<Object>	simpleInvSources()
Iterator<Object>	simpleInvSourcesIterator()
Node[]	simpleLookup(VarNode key)
Set<Object>	simpleSources()
Iterator<Object>	simpleSourcesIterator()
Node[]	storeInvLookup(FieldRefNode key)
Set<Object>	storeInvSources()
Iterator<Object>	storeInvSourcesIterator()
Node[]	storeLookup(VarNode key)
Set<Object>	storeSources()
Iterator<Object>	storeSourcesIterator()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

EMPTY_NODE_ARRAY

protected static final Node[] EMPTY_NODE_ARRAY

setFactory

protected P2SetFactory setFactory

somethingMerged

protected boolean somethingMerged

edgeQueue

protected ChunkedQueue edgeQueue

opts

protected SparkOptions opts

simple

protected Map<Object,Object> simple

load

protected Map<Object,Object> load

store

protected Map<Object,Object> store

alloc

protected Map<Object,Object> alloc

simpleInv

protected Map<Object,Object> simpleInv

loadInv

protected Map<Object,Object> loadInv

storeInv

protected Map<Object,Object> storeInv

allocInv

protected Map<Object,Object> allocInv

assign2edges

protected Map<Pair,Set<Edge>> assign2edges

typeManager

protected TypeManager typeManager

maxFinishNumber

public int maxFinishNumber

nativeMethodDriver

public NativeMethodDriver nativeMethodDriver

callAssigns

public HashMultiMap callAssigns

callToMethod

public Map<InvokeExpr,SootMethod> callToMethod

virtualCallsToReceivers

public Map<InvokeExpr,Node> virtualCallsToReceivers

Constructor Detail

PAG

public PAG(SparkOptions opts)

Method Detail

reachingObjects

public PointsToSet reachingObjects(Local l)

Returns the set of objects pointed to by variable l.

Specified by:

reachingObjects in interface PointsToAnalysis

reachingObjects

public PointsToSet reachingObjects(Context c,
                                   Local l)

Returns the set of objects pointed to by variable l in context c.

Specified by:

reachingObjects in interface PointsToAnalysis

reachingObjects

public PointsToSet reachingObjects(SootField f)

Returns the set of objects pointed to by static field f.

Specified by:

reachingObjects in interface PointsToAnalysis

reachingObjects

public PointsToSet reachingObjects(PointsToSet s,
                                   SootField f)

Returns the set of objects pointed to by instance field f of the objects in the PointsToSet s.

Specified by:

reachingObjects in interface PointsToAnalysis

reachingObjectsOfArrayElement

public PointsToSet reachingObjectsOfArrayElement(PointsToSet s)

Returns the set of objects pointed to by elements of the arrays in the PointsToSet s.

Specified by:

reachingObjectsOfArrayElement in interface PointsToAnalysis

getSetFactory

public P2SetFactory getSetFactory()

cleanUpMerges

public void cleanUpMerges()

doAddSimpleEdge

public boolean doAddSimpleEdge(VarNode from,
                               VarNode to)

doAddStoreEdge

public boolean doAddStoreEdge(VarNode from,
                              FieldRefNode to)

doAddLoadEdge

public boolean doAddLoadEdge(FieldRefNode from,
                             VarNode to)

doAddAllocEdge

public boolean doAddAllocEdge(AllocNode from,
                              VarNode to)

lookup

protected Node[] lookup(Map<Object,Object> m,
                        Object key)

simpleLookup

public Node[] simpleLookup(VarNode key)

simpleInvLookup

public Node[] simpleInvLookup(VarNode key)

loadLookup

public Node[] loadLookup(FieldRefNode key)

loadInvLookup

public Node[] loadInvLookup(VarNode key)

storeLookup

public Node[] storeLookup(VarNode key)

storeInvLookup

public Node[] storeInvLookup(FieldRefNode key)

allocLookup

public Node[] allocLookup(AllocNode key)

allocInvLookup

public Node[] allocInvLookup(VarNode key)

simpleSources

public Set<Object> simpleSources()

allocSources

public Set<Object> allocSources()

storeSources

public Set<Object> storeSources()

loadSources

public Set<Object> loadSources()

simpleInvSources

public Set<Object> simpleInvSources()

allocInvSources

public Set<Object> allocInvSources()

storeInvSources

public Set<Object> storeInvSources()

loadInvSources

public Set<Object> loadInvSources()

simpleSourcesIterator

public Iterator<Object> simpleSourcesIterator()

allocSourcesIterator

public Iterator<Object> allocSourcesIterator()

storeSourcesIterator

public Iterator<Object> storeSourcesIterator()

loadSourcesIterator

public Iterator<Object> loadSourcesIterator()

simpleInvSourcesIterator

public Iterator<Object> simpleInvSourcesIterator()

allocInvSourcesIterator

public Iterator<Object> allocInvSourcesIterator()

storeInvSourcesIterator

public Iterator<Object> storeInvSourcesIterator()

loadInvSourcesIterator

public Iterator<Object> loadInvSourcesIterator()

reachingObjects

public PointsToSet reachingObjects(Local l,
                                   SootField f)

Returns the set of objects pointed to by instance field f of the objects pointed to by l.

Specified by:

reachingObjects in interface PointsToAnalysis

reachingObjects

public PointsToSet reachingObjects(Context c,
                                   Local l,
                                   SootField f)

Returns the set of objects pointed to by instance field f of the objects pointed to by l in context c.

Specified by:

reachingObjects in interface PointsToAnalysis

makeAllocNode

public AllocNode makeAllocNode(Object newExpr,
                               Type type,
                               SootMethod m)

makeStringConstantNode

public AllocNode makeStringConstantNode(String s)

makeClassConstantNode

public AllocNode makeClassConstantNode(ClassConstant cc)

allocNodeListener

public QueueReader allocNodeListener()

findGlobalVarNode

public GlobalVarNode findGlobalVarNode(Object value)

Finds the GlobalVarNode for the variable value, or returns null.

findLocalVarNode

public LocalVarNode findLocalVarNode(Object value)

Finds the LocalVarNode for the variable value, or returns null.

makeGlobalVarNode

public GlobalVarNode makeGlobalVarNode(Object value,
                                       Type type)

Finds or creates the GlobalVarNode for the variable value, of type type.

makeLocalVarNode

public LocalVarNode makeLocalVarNode(Object value,
                                     Type type,
                                     SootMethod method)

Finds or creates the LocalVarNode for the variable value, of type type.

findContextVarNode

public ContextVarNode findContextVarNode(Object baseValue,
                                         Context context)

Finds the ContextVarNode for base variable value and context context, or returns null.

makeContextVarNode

public ContextVarNode makeContextVarNode(Object baseValue,
                                         Type baseType,
                                         Context context,
                                         SootMethod method)

Finds or creates the ContextVarNode for base variable baseValue and context context, of type type.

makeContextVarNode

public ContextVarNode makeContextVarNode(LocalVarNode base,
                                         Context context)

Finds or creates the ContextVarNode for base variable base and context context, of type type.

findLocalFieldRefNode

public FieldRefNode findLocalFieldRefNode(Object baseValue,
                                          SparkField field)

Finds the FieldRefNode for base variable value and field field, or returns null.

findGlobalFieldRefNode

public FieldRefNode findGlobalFieldRefNode(Object baseValue,
                                           SparkField field)

Finds the FieldRefNode for base variable value and field field, or returns null.

makeLocalFieldRefNode

public FieldRefNode makeLocalFieldRefNode(Object baseValue,
                                          Type baseType,
                                          SparkField field,
                                          SootMethod method)

Finds or creates the FieldRefNode for base variable baseValue and field field, of type type.

makeGlobalFieldRefNode

public FieldRefNode makeGlobalFieldRefNode(Object baseValue,
                                           Type baseType,
                                           SparkField field)

Finds or creates the FieldRefNode for base variable baseValue and field field, of type type.

makeFieldRefNode

public FieldRefNode makeFieldRefNode(VarNode base,
                                     SparkField field)

Finds or creates the FieldRefNode for base variable base and field field, of type type.

findAllocDotField

public AllocDotField findAllocDotField(AllocNode an,
                                       SparkField field)

Finds the AllocDotField for base AllocNode an and field field, or returns null.

makeAllocDotField

public AllocDotField makeAllocDotField(AllocNode an,
                                       SparkField field)

Finds or creates the AllocDotField for base variable baseValue and field field, of type t.

addSimpleEdge

public boolean addSimpleEdge(VarNode from,
                             VarNode to)

addStoreEdge

public boolean addStoreEdge(VarNode from,
                            FieldRefNode to)

addLoadEdge

public boolean addLoadEdge(FieldRefNode from,
                           VarNode to)

addAllocEdge

public boolean addAllocEdge(AllocNode from,
                            VarNode to)

addEdge

public final boolean addEdge(Node from,
                             Node to)

Adds an edge to the graph, returning false if it was already there.

edgeReader

public QueueReader edgeReader()

getNumAllocNodes

public int getNumAllocNodes()

getTypeManager

public TypeManager getTypeManager()

setOnFlyCallGraph

public void setOnFlyCallGraph(OnFlyCallGraph ofcg)

getOnFlyCallGraph

public OnFlyCallGraph getOnFlyCallGraph()

ofcg

public OnFlyCallGraph ofcg()

addDereference

public void addDereference(VarNode base)

Adds the base of a dereference to the list of dereferenced variables.

getDereferences

public List<VarNode> getDereferences()

Returns list of dereferences variables.

getNodeTags

public Map<Node,Tag> getNodeTags()

getAllocNodeNumberer

public ArrayNumberer getAllocNodeNumberer()

getVarNodeNumberer

public ArrayNumberer getVarNodeNumberer()

getFieldRefNodeNumberer

public ArrayNumberer getFieldRefNodeNumberer()

getAllocDotFieldNodeNumberer

public ArrayNumberer getAllocDotFieldNodeNumberer()

getOpts

public SparkOptions getOpts()

Returns SparkOptions for this graph.

addInterproceduralAssignment

public Pair<Node,Node> addInterproceduralAssignment(Node from,
                                                    Node to,
                                                    Edge e)

lookupEdgesForAssignment

public Set<Edge> lookupEdgesForAssignment(Pair<Node,Node> val)

addCallTarget

public final void addCallTarget(Edge e)

addCallTarget

public final void addCallTarget(MethodPAG srcmpag,
                                MethodPAG tgtmpag,
                                Stmt s,
                                Context srcContext,
                                Context tgtContext,
                                Edge e)

Adds method target as a possible target of the invoke expression in s. If target is null, only creates the nodes for the call site, without actually connecting them to any target method.

cleanPAG

public void cleanPAG()

Delete all the assignment edges.

addToMap

protected boolean addToMap(Map<Object,Object> m,
                           Node key,
                           Node value)

nodeFactory

public GlobalNodeFactory nodeFactory()