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 java.lang.Object
implements PointsToAnalysis

Pointer assignment graph.

Field Summary

Fields

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

Method Summary

Modifier and Type	Method and Description
boolean	addAllocEdge(AllocNode from, VarNode to)
boolean	addAssignInstanceEdge(NewInstanceNode 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	addNewInstanceEdge(VarNode from, NewInstanceNode to)
boolean	addSimpleEdge(VarNode from, VarNode to)
boolean	addStoreEdge(VarNode from, FieldRefNode to)
protected <K extends Node> boolean	addToMap(java.util.Map<K,java.lang.Object> m, K key, Node value)
Node[]	allocInvLookup(VarNode key)
java.util.Set<VarNode>	allocInvSources()
java.util.Iterator<VarNode>	allocInvSourcesIterator()
Node[]	allocLookup(AllocNode key)
QueueReader<AllocNode>	allocNodeListener()
java.util.Set<AllocNode>	allocSources()
java.util.Iterator<AllocNode>	allocSourcesIterator()
Node[]	assignInstanceLookup(NewInstanceNode key)
java.util.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(java.lang.Object baseValue, Context context) Finds the ContextVarNode for base variable value and context context, or returns null.
FieldRefNode	findGlobalFieldRefNode(java.lang.Object baseValue, SparkField field) Finds the FieldRefNode for base variable value and field field, or returns null.
GlobalVarNode	findGlobalVarNode(java.lang.Object value) Finds the GlobalVarNode for the variable value, or returns null.
FieldRefNode	findLocalFieldRefNode(java.lang.Object baseValue, SparkField field) Finds the FieldRefNode for base variable value and field field, or returns null.
LocalVarNode	findLocalVarNode(java.lang.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.
java.util.List<VarNode>	getDereferences() Returns list of dereferences variables.
ArrayNumberer<FieldRefNode>	getFieldRefNodeNumberer()
java.util.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)
java.util.Set<VarNode>	loadInvSources()
java.util.Iterator<VarNode>	loadInvSourcesIterator()
Node[]	loadLookup(FieldRefNode key)
java.util.Set<FieldRefNode>	loadSources()
java.util.Iterator<FieldRefNode>	loadSourcesIterator()
protected <K extends Node> Node[]	lookup(java.util.Map<K,java.lang.Object> m, K key)
java.util.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(java.lang.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(java.lang.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(java.lang.Object baseValue, Type baseType, SparkField field) Finds or creates the FieldRefNode for base variable baseValue and field field, of type type.
GlobalVarNode	makeGlobalVarNode(java.lang.Object value, Type type) Finds or creates the GlobalVarNode for the variable value, of type type.
FieldRefNode	makeLocalFieldRefNode(java.lang.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(java.lang.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(java.lang.String s)
Node[]	newInstanceLookup(VarNode key)
java.util.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)
java.util.Set<VarNode>	simpleInvSources()
java.util.Iterator<VarNode>	simpleInvSourcesIterator()
Node[]	simpleLookup(VarNode key)
java.util.Set<VarNode>	simpleSources()
java.util.Iterator<VarNode>	simpleSourcesIterator()
Node[]	storeInvLookup(FieldRefNode key)
java.util.Set<FieldRefNode>	storeInvSources()
java.util.Iterator<FieldRefNode>	storeInvSourcesIterator()
Node[]	storeLookup(VarNode key)
java.util.Set<VarNode>	storeSources()
java.util.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

opts

protected SparkOptions opts

cgOpts

protected CGOptions cgOpts

accessibilityOracle

protected ClientAccessibilityOracle accessibilityOracle

simple

protected java.util.Map<VarNode,java.lang.Object> simple

load

protected java.util.Map<FieldRefNode,java.lang.Object> load

store

protected java.util.Map<VarNode,java.lang.Object> store

alloc

protected java.util.Map<AllocNode,java.lang.Object> alloc

newInstance

protected java.util.Map<VarNode,java.lang.Object> newInstance

assignInstance

protected java.util.Map<NewInstanceNode,java.lang.Object> assignInstance

simpleInv

protected java.util.Map<VarNode,java.lang.Object> simpleInv

loadInv

protected java.util.Map<VarNode,java.lang.Object> loadInv

storeInv

protected java.util.Map<FieldRefNode,java.lang.Object> storeInv

allocInv

protected java.util.Map<VarNode,java.lang.Object> allocInv

newInstanceInv

protected java.util.Map<NewInstanceNode,java.lang.Object> newInstanceInv

assignInstanceInv

protected java.util.Map<VarNode,java.lang.Object> assignInstanceInv

assign2edges

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

typeManager

protected TypeManager typeManager

maxFinishNumber

public int maxFinishNumber

nativeMethodDriver

public NativeMethodDriver nativeMethodDriver

callAssigns

public HashMultiMap<InvokeExpr,Pair<Node,Node>> callAssigns

callToMethod

public java.util.Map<InvokeExpr,SootMethod> callToMethod

virtualCallsToReceivers

public java.util.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(java.util.Map<K,java.lang.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 java.util.Set<VarNode> simpleSources()

allocSources

public java.util.Set<AllocNode> allocSources()

storeSources

public java.util.Set<VarNode> storeSources()

loadSources

public java.util.Set<FieldRefNode> loadSources()

newInstanceSources

public java.util.Set<VarNode> newInstanceSources()

assignInstanceSources

public java.util.Set<NewInstanceNode> assignInstanceSources()

simpleInvSources

public java.util.Set<VarNode> simpleInvSources()

allocInvSources

public java.util.Set<VarNode> allocInvSources()

storeInvSources

public java.util.Set<FieldRefNode> storeInvSources()

loadInvSources

public java.util.Set<VarNode> loadInvSources()

simpleSourcesIterator

public java.util.Iterator<VarNode> simpleSourcesIterator()

allocSourcesIterator

public java.util.Iterator<AllocNode> allocSourcesIterator()

storeSourcesIterator

public java.util.Iterator<VarNode> storeSourcesIterator()

loadSourcesIterator

public java.util.Iterator<FieldRefNode> loadSourcesIterator()

simpleInvSourcesIterator

public java.util.Iterator<VarNode> simpleInvSourcesIterator()

allocInvSourcesIterator

public java.util.Iterator<VarNode> allocInvSourcesIterator()

storeInvSourcesIterator

public java.util.Iterator<FieldRefNode> storeInvSourcesIterator()

loadInvSourcesIterator

public java.util.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(java.lang.Object newExpr,
                               Type type,
                               SootMethod m)

makeStringConstantNode

public AllocNode makeStringConstantNode(java.lang.String s)

makeClassConstantNode

public AllocNode makeClassConstantNode(ClassConstant cc)

allocNodeListener

public QueueReader<AllocNode> allocNodeListener()

findGlobalVarNode

public GlobalVarNode findGlobalVarNode(java.lang.Object value)

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

findLocalVarNode

public LocalVarNode findLocalVarNode(java.lang.Object value)

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

makeGlobalVarNode

public GlobalVarNode makeGlobalVarNode(java.lang.Object value,
                                       Type type)

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

makeLocalVarNode

public LocalVarNode makeLocalVarNode(java.lang.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(java.lang.Object baseValue,
                                         Context context)

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

makeContextVarNode

public ContextVarNode makeContextVarNode(java.lang.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(java.lang.Object baseValue,
                                          SparkField field)

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

findGlobalFieldRefNode

public FieldRefNode findGlobalFieldRefNode(java.lang.Object baseValue,
                                           SparkField field)

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

makeLocalFieldRefNode

public FieldRefNode makeLocalFieldRefNode(java.lang.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(java.lang.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 final 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 java.util.List<VarNode> getDereferences()

Returns list of dereferences variables.

getNodeTags

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

nodeFactory

public GlobalNodeFactory nodeFactory()