soot.jimple.spark.pag
Class PAG

java.lang.Object
  extended bysoot.jimple.spark.pag.PAG
All Implemented Interfaces:
PointsToAnalysis

public class PAG
extends Object
implements PointsToAnalysis

Pointer assignment graph.

Author:
Ondrej Lhotak

Field Summary
protected  Map alloc
           
protected  Map allocInv
           
protected  ChunkedQueue edgeQueue
           
protected static Node[] EMPTY_NODE_ARRAY
           
protected  Map load
           
protected  Map loadInv
           
 int maxFinishNumber
           
 NativeMethodDriver nativeMethodDriver
           
protected  soot.options.SparkOptions opts
           
protected  P2SetFactory setFactory
           
protected  Map simple
           
protected  Map simpleInv
           
protected  boolean somethingMerged
           
protected  Map store
           
protected  Map storeInv
           
protected  TypeManager typeManager
           
 
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(soot.options.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)
          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.
 boolean addLoadEdge(FieldRefNode from, VarNode to)
           
 boolean addSimpleEdge(VarNode from, VarNode to)
           
 boolean addStoreEdge(VarNode from, FieldRefNode to)
           
protected  boolean addToMap(Map m, Node key, Node value)
           
 Node[] allocInvLookup(VarNode key)
           
 Set allocInvSources()
           
 Iterator allocInvSourcesIterator()
           
 Node[] allocLookup(AllocNode key)
           
 QueueReader allocNodeListener()
           
 Set allocSources()
           
 Iterator allocSourcesIterator()
           
 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 getDereferences()
          Returns list of dereferences variables.
 ArrayNumberer getFieldRefNodeNumberer()
           
 Map getNodeTags()
           
 int getNumAllocNodes()
           
 OnFlyCallGraph getOnFlyCallGraph()
           
 soot.options.SparkOptions getOpts()
          Returns SparkOptions for this graph.
 P2SetFactory getSetFactory()
           
 TypeManager getTypeManager()
           
 ArrayNumberer getVarNodeNumberer()
           
 Node[] loadInvLookup(VarNode key)
           
 Set loadInvSources()
           
 Iterator loadInvSourcesIterator()
           
 Node[] loadLookup(FieldRefNode key)
           
 Set loadSources()
           
 Iterator loadSourcesIterator()
           
protected  Node[] lookup(Map m, Object key)
           
 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 simpleInvSources()
           
 Iterator simpleInvSourcesIterator()
           
 Node[] simpleLookup(VarNode key)
           
 Set simpleSources()
           
 Iterator simpleSourcesIterator()
           
 Node[] storeInvLookup(FieldRefNode key)
           
 Set storeInvSources()
           
 Iterator storeInvSourcesIterator()
           
 Node[] storeLookup(VarNode key)
           
 Set storeSources()
           
 Iterator 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 soot.options.SparkOptions opts

simple

protected Map simple

load

protected Map load

store

protected Map store

alloc

protected Map alloc

simpleInv

protected Map simpleInv

loadInv

protected Map loadInv

storeInv

protected Map storeInv

allocInv

protected Map allocInv

typeManager

protected TypeManager typeManager

maxFinishNumber

public int maxFinishNumber

nativeMethodDriver

public NativeMethodDriver nativeMethodDriver
Constructor Detail

PAG

public PAG(soot.options.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 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 simpleSources()

allocSources

public Set allocSources()

storeSources

public Set storeSources()

loadSources

public Set loadSources()

simpleInvSources

public Set simpleInvSources()

allocInvSources

public Set allocInvSources()

storeInvSources

public Set storeInvSources()

loadInvSources

public Set loadInvSources()

simpleSourcesIterator

public Iterator simpleSourcesIterator()

allocSourcesIterator

public Iterator allocSourcesIterator()

storeSourcesIterator

public Iterator storeSourcesIterator()

loadSourcesIterator

public Iterator loadSourcesIterator()

simpleInvSourcesIterator

public Iterator simpleInvSourcesIterator()

allocInvSourcesIterator

public Iterator allocInvSourcesIterator()

storeInvSourcesIterator

public Iterator storeInvSourcesIterator()

loadInvSourcesIterator

public Iterator 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 getDereferences()
Returns list of dereferences variables.


getNodeTags

public Map getNodeTags()

getAllocNodeNumberer

public ArrayNumberer getAllocNodeNumberer()

getVarNodeNumberer

public ArrayNumberer getVarNodeNumberer()

getFieldRefNodeNumberer

public ArrayNumberer getFieldRefNodeNumberer()

getAllocDotFieldNodeNumberer

public ArrayNumberer getAllocDotFieldNodeNumberer()

getOpts

public soot.options.SparkOptions getOpts()
Returns SparkOptions for this graph.


addCallTarget

public final void addCallTarget(Edge e)

addCallTarget

public final void addCallTarget(MethodPAG srcmpag,
                                MethodPAG tgtmpag,
                                Stmt s,
                                Context srcContext,
                                Context tgtContext)
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.


addToMap

protected boolean addToMap(Map m,
                           Node key,
                           Node value)

nodeFactory

public GlobalNodeFactory nodeFactory()