Package 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

Fields

Modifier and Type	Field	Description
protected ClientAccessibilityOracle	accessibilityOracle
protected Map<AllocNode,Object>	alloc
protected Map<VarNode,Object>	allocInv
protected ArrayNumberer<AllocNode>	allocNodeNumberer
protected MultiMap<Pair<Node,Node>,Edge>	assign2edges
protected Map<NewInstanceNode,Object>	assignInstance
protected Map<VarNode,Object>	assignInstanceInv
HashMultiMap<InvokeExpr,Pair<Node,Node>>	callAssigns
Map<InvokeExpr,SootMethod>	callToMethod
protected CGOptions	cgOpts
protected ChunkedQueue<Node>	edgeQueue
protected static Node[]	EMPTY_NODE_ARRAY
protected Map<FieldRefNode,Object>	load
protected Map<VarNode,Object>	loadInv
protected Map<Local,LocalVarNode>	localToNodeMap
int	maxFinishNumber
NativeMethodDriver	nativeMethodDriver
protected Map<VarNode,Object>	newInstance
protected Map<NewInstanceNode,Object>	newInstanceInv
protected SparkOptions	opts
protected P2SetFactory	setFactory
protected Map<VarNode,Object>	simple
protected Map<VarNode,Object>	simpleInv
protected boolean	somethingMerged
protected Map<VarNode,Object>	store
protected Map<FieldRefNode,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

Constructors

Constructor	Description
PAG(SparkOptions opts)

Method Summary

Modifier and Type	Method	Description
boolean	addAllocEdge(AllocNode from, VarNode to)
boolean	addAssignInstanceEdge(NewInstanceNode from, VarNode to)
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	addCallTarget(MethodPAG srcmpag, MethodPAG tgtmpag, Stmt s, Context srcContext, Context tgtContext, Edge e, boolean propagateReturn)	Adds method target as a possible target of the invoke expression in s.
void	addCallTarget(Edge e)
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	addNewInstanceEdge(VarNode from, NewInstanceNode to)
boolean	addSimpleEdge(VarNode from, VarNode to)
boolean	addStoreEdge(VarNode from, FieldRefNode to)
protected <K extends Node> boolean	addToMap(Map<K,Object> m, K key, Node value)
Node[]	allocInvLookup(VarNode key)
Set<VarNode>	allocInvSources()
Iterator<VarNode>	allocInvSourcesIterator()
Node[]	allocLookup(AllocNode key)
QueueReader<AllocNode>	allocNodeListener()
Set<AllocNode>	allocSources()
Iterator<AllocNode>	allocSourcesIterator()
Node[]	assignInstanceLookup(NewInstanceNode key)
Set<NewInstanceNode>	assignInstanceSources()
void	cleanPAG()	Delete all the assignment edges.
void	cleanUpMerges()
boolean	doAddAllocEdge(AllocNode from, VarNode to)
boolean	doAddAssignInstanceEdge(NewInstanceNode from, VarNode to)
boolean	doAddLoadEdge(FieldRefNode from, VarNode to)
boolean	doAddNewInstanceEdge(VarNode from, NewInstanceNode to)
boolean	doAddSimpleEdge(VarNode from, VarNode to)
boolean	doAddStoreEdge(VarNode from, FieldRefNode to)
QueueReader<Node>	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<AllocDotField>	getAllocDotFieldNodeNumberer()
ArrayNumberer<AllocNode>	getAllocNodeNumberer()
CGOptions	getCGOpts()	Returns CGOptions for this graph.
List<VarNode>	getDereferences()	Returns list of dereferences variables.
ArrayNumberer<FieldRefNode>	getFieldRefNodeNumberer()
Map<Node,Tag>	getNodeTags()
int	getNumAllocNodes()
OnFlyCallGraph	getOnFlyCallGraph()
SparkOptions	getOpts()	Returns SparkOptions for this graph.
P2SetFactory	getSetFactory()
TypeManager	getTypeManager()
ArrayNumberer<VarNode>	getVarNodeNumberer()
Node[]	loadInvLookup(VarNode key)
Set<VarNode>	loadInvSources()
Iterator<VarNode>	loadInvSourcesIterator()
Node[]	loadLookup(FieldRefNode key)
Set<FieldRefNode>	loadSources()
Iterator<FieldRefNode>	loadSourcesIterator()
protected <K extends Node> Node[]	lookup(Map<K,Object> m, K 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(Object baseValue, Type baseType, Context context, SootMethod method)	Finds or creates the ContextVarNode for base variable baseValue and context context, of type type.
ContextVarNode	makeContextVarNode(LocalVarNode base, Context context)	Finds or creates the ContextVarNode for base variable base 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.
NewInstanceNode	makeNewInstanceNode(Value value, Type type, SootMethod method)
AllocNode	makeStringConstantNode(String s)
Node[]	newInstanceLookup(VarNode key)
Set<VarNode>	newInstanceSources()
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<VarNode>	simpleInvSources()
Iterator<VarNode>	simpleInvSourcesIterator()
Node[]	simpleLookup(VarNode key)
Set<VarNode>	simpleSources()
Iterator<VarNode>	simpleSourcesIterator()
Node[]	storeInvLookup(FieldRefNode key)
Set<FieldRefNode>	storeInvSources()
Iterator<FieldRefNode>	storeInvSourcesIterator()
Node[]	storeLookup(VarNode key)
Set<VarNode>	storeSources()
Iterator<VarNode>	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<Node> edgeQueue

allocNodeNumberer

protected final ArrayNumberer<AllocNode> allocNodeNumberer

opts

protected SparkOptions opts

cgOpts

protected CGOptions cgOpts

accessibilityOracle

protected ClientAccessibilityOracle accessibilityOracle

simple

protected Map<VarNode,Object> simple

load

protected Map<FieldRefNode,Object> load

store

protected Map<VarNode,Object> store

alloc

protected Map<AllocNode,Object> alloc

newInstance

protected Map<VarNode,Object> newInstance

assignInstance

protected Map<NewInstanceNode,Object> assignInstance

simpleInv

protected Map<VarNode,Object> simpleInv

loadInv

protected Map<VarNode,Object> loadInv

storeInv

protected Map<FieldRefNode,Object> storeInv

allocInv

protected Map<VarNode,Object> allocInv

newInstanceInv

protected Map<NewInstanceNode,Object> newInstanceInv

assignInstanceInv

protected Map<VarNode,Object> assignInstanceInv

assign2edges

protected MultiMap<Pair<Node,Node>,Edge> assign2edges

typeManager

protected TypeManager typeManager

localToNodeMap

protected Map<Local,LocalVarNode> localToNodeMap

maxFinishNumber

public int maxFinishNumber

nativeMethodDriver

public NativeMethodDriver nativeMethodDriver

callAssigns

public HashMultiMap<InvokeExpr,Pair<Node,Node>> 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)

doAddNewInstanceEdge

public boolean doAddNewInstanceEdge(VarNode from,
                                    NewInstanceNode to)

doAddAssignInstanceEdge

public boolean doAddAssignInstanceEdge(NewInstanceNode from,
                                       VarNode to)

lookup

protected <K extends Node> Node[] lookup(Map<K,Object> m,
                                         K 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)

newInstanceLookup

public Node[] newInstanceLookup(VarNode key)

assignInstanceLookup

public Node[] assignInstanceLookup(NewInstanceNode key)

storeInvLookup

public Node[] storeInvLookup(FieldRefNode key)

allocLookup

public Node[] allocLookup(AllocNode key)

allocInvLookup

public Node[] allocInvLookup(VarNode key)

simpleSources

public Set<VarNode> simpleSources()

allocSources

public Set<AllocNode> allocSources()

storeSources

public Set<VarNode> storeSources()

loadSources

public Set<FieldRefNode> loadSources()

newInstanceSources

public Set<VarNode> newInstanceSources()

assignInstanceSources

public Set<NewInstanceNode> assignInstanceSources()

simpleInvSources

public Set<VarNode> simpleInvSources()

allocInvSources

public Set<VarNode> allocInvSources()

storeInvSources

public Set<FieldRefNode> storeInvSources()

loadInvSources

public Set<VarNode> loadInvSources()

simpleSourcesIterator

public Iterator<VarNode> simpleSourcesIterator()

allocSourcesIterator

public Iterator<AllocNode> allocSourcesIterator()

storeSourcesIterator

public Iterator<VarNode> storeSourcesIterator()

loadSourcesIterator

public Iterator<FieldRefNode> loadSourcesIterator()

simpleInvSourcesIterator

public Iterator<VarNode> simpleInvSourcesIterator()

allocInvSourcesIterator

public Iterator<VarNode> allocInvSourcesIterator()

storeInvSourcesIterator

public Iterator<FieldRefNode> storeInvSourcesIterator()

loadInvSourcesIterator

public Iterator<VarNode> 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<AllocNode> 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.

makeNewInstanceNode

public NewInstanceNode makeNewInstanceNode(Value value,
                                           Type type,
                                           SootMethod method)

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)

addNewInstanceEdge

public boolean addNewInstanceEdge(VarNode from,
                                  NewInstanceNode to)

addAssignInstanceEdge

public boolean addAssignInstanceEdge(NewInstanceNode from,
                                     VarNode to)

addEdge

public boolean addEdge(Node from,
                       Node to)

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

edgeReader

public QueueReader<Node> 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<AllocNode> getAllocNodeNumberer()

getVarNodeNumberer

public ArrayNumberer<VarNode> getVarNodeNumberer()

getFieldRefNodeNumberer

public ArrayNumberer<FieldRefNode> getFieldRefNodeNumberer()

getAllocDotFieldNodeNumberer

public ArrayNumberer<AllocDotField> getAllocDotFieldNodeNumberer()

getOpts

public SparkOptions getOpts()

Returns SparkOptions for this graph.

getCGOpts

public CGOptions getCGOpts()

Returns CGOptions 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 void addCallTarget(Edge e)

addCallTarget

public 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.

addCallTarget

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

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 <K extends Node> boolean addToMap(Map<K,Object> m,
                                            K key,
                                            Node value)

nodeFactory

public GlobalNodeFactory nodeFactory()