soot.jimple.spark.geom.geomPA
Class GeomPointsTo

java.lang.Object
  soot.jimple.spark.pag.PAG
      soot.jimple.spark.geom.geomPA.GeomPointsTo

All Implemented Interfaces:

PointsToAnalysis

public class GeomPointsTo
extends PAG

The main interface for the points-to analysis with geometric encodings. Since we need SPARK to bootstrap our analysis, thus, we identify ourself to be a subclass of SPARK.

Author:

richardxx

Field Summary

static int	ALL_TO_MANY
ZArrayNumberer<IVarAbstraction>	allocations
static int	ASSIGN_CONS
int[]	block_num
protected CgEdge[]	call_graph
static int	cfa_blocks
static int	cg_refine_times
Map<Node,IVarAbstraction>	consG
Vector<PlainConstraint>	constraints
long[]	context_size
String	dump_file_name
protected Map<Edge,CgEdge>	edgeMapping
static RefType	exeception_type
static int	FIELD_ADDRESS
protected Map<SootMethod,Integer>	func2int
protected int[]	indeg_cg
protected Map<Integer,SootMethod>	int2func
static int	LOAD_CONS
protected int[]	low_cg
int	mainID
static int	MANY_TO_ALL
static int	MANY_TO_MANY
static int	max_cons_budget
long[]	max_context_size_block
static long	MAX_CONTEXTS
static int	max_pts_budget
int	max_scc_id
int	max_scc_size
int	n_alloc_sites
int	n_calls
int	n_func
int	n_reach_methods
int	n_reach_user_methods
int	n_var
static int	NEW_CONS
protected IEncodingBroker	nodeGenerator
protected Vector<CgEdge>	obsoletedEdges
protected OfflineProcessor	offlineProcessor
static int	ONE_TO_ONE
ZArrayNumberer<IVarAbstraction>	pointers
protected int	pre_cnt
PrintStream	ps
protected Deque<Integer>	queue_cg
protected int[]	rep_cg
protected Map<Integer,LinkedList<CgEdge>>	rev_call_graph
protected int[]	scc_size
int	solver_encoding
static int	STORE_CONS
static int	SUPER_MAIN
Set<Stmt>	thread_run_callsites
protected TypeManager	typeManager
static int	Undefined_Mapping
static int	UNKNOWN_FUNCTION
protected Map<String,Boolean>	validMethods
protected int[]	vis_cg
protected IWorklist	worklist

Fields inherited from class soot.jimple.spark.pag.PAG

alloc, allocInv, assign2edges, callAssigns, callToMethod, edgeQueue, EMPTY_NODE_ARRAY, load, loadInv, maxFinishNumber, nativeMethodDriver, opts, setFactory, simple, simpleInv, somethingMerged, store, storeInv, 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

GeomPointsTo(SparkOptions opts)

Method Summary

boolean	castNeverFails(Type src, Type dst)
protected int	countReachableMethods(int s)
IVarAbstraction	findAndInsertInstanceField(AllocNode obj, SparkField field)
Set<SootMethod>	getAllReachableMethods()
LinkedList<CgEdge>	getCallEdgesInto(int fid)
CgEdge	getCallEgesOutFrom(int fid)
int	getIDFromSootMethod(SootMethod sm)
CgEdge	getInternalEdgeFromSootEdge(Edge e)
IVarAbstraction	getInternalNode(Node v)
int	getMappedMethodID(Node node)
int	getNumberOfFunctions()
int	getNumberOfObjects()
int	getNumberOfPointers()
SootMethod	getSootMethodFromID(int fid)
IWorklist	getWorklist()
boolean	isReachableMethod(int fid)
boolean	isValidMethod(SootMethod sm)
void	outputNotEvaluatedMethods()
void	parametrize()
PointsToSet	reachingObjects(AllocNode an, SootField f)
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	solve()
String	toString()
void	transformToCIResult() For many applications, they only need the context insensitive points-to result.

Methods inherited from class soot.jimple.spark.pag.PAG

addAllocEdge, addCallTarget, addCallTarget, addDereference, addEdge, addInterproceduralAssignment, addLoadEdge, addSimpleEdge, addStoreEdge, addToMap, allocInvLookup, allocInvSources, allocInvSourcesIterator, allocLookup, allocNodeListener, allocSources, allocSourcesIterator, cleanPAG, cleanUpMerges, doAddAllocEdge, doAddLoadEdge, doAddSimpleEdge, doAddStoreEdge, edgeReader, findAllocDotField, findContextVarNode, findGlobalFieldRefNode, findGlobalVarNode, findLocalFieldRefNode, findLocalVarNode, getAllocDotFieldNodeNumberer, getAllocNodeNumberer, getDereferences, getFieldRefNodeNumberer, getNodeTags, getNumAllocNodes, getOnFlyCallGraph, getOpts, getSetFactory, getTypeManager, getVarNodeNumberer, loadInvLookup, loadInvSources, loadInvSourcesIterator, loadLookup, loadSources, loadSourcesIterator, lookup, lookupEdgesForAssignment, makeAllocDotField, makeAllocNode, makeClassConstantNode, makeContextVarNode, makeContextVarNode, makeFieldRefNode, makeGlobalFieldRefNode, makeGlobalVarNode, makeLocalFieldRefNode, makeLocalVarNode, makeStringConstantNode, nodeFactory, ofcg, setOnFlyCallGraph, simpleInvLookup, simpleInvSources, simpleInvSourcesIterator, simpleLookup, simpleSources, simpleSourcesIterator, storeInvLookup, storeInvSources, storeInvSourcesIterator, storeLookup, storeSources, storeSourcesIterator

Methods inherited from class java.lang.Object

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

Field Detail

NEW_CONS

public static final int NEW_CONS

See Also:

Constant Field Values

ASSIGN_CONS

public static final int ASSIGN_CONS

See Also:

Constant Field Values

LOAD_CONS

public static final int LOAD_CONS

See Also:

Constant Field Values

STORE_CONS

public static final int STORE_CONS

See Also:

Constant Field Values

FIELD_ADDRESS

public static final int FIELD_ADDRESS

See Also:

Constant Field Values

Undefined_Mapping

public static final int Undefined_Mapping

See Also:

Constant Field Values

ONE_TO_ONE

public static final int ONE_TO_ONE

See Also:

Constant Field Values

MANY_TO_MANY

public static final int MANY_TO_MANY

See Also:

Constant Field Values

ALL_TO_MANY

public static final int ALL_TO_MANY

See Also:

Constant Field Values

MANY_TO_ALL

public static final int MANY_TO_ALL

See Also:

Constant Field Values

SUPER_MAIN

public static final int SUPER_MAIN

See Also:

Constant Field Values

UNKNOWN_FUNCTION

public static final int UNKNOWN_FUNCTION

See Also:

Constant Field Values

MAX_CONTEXTS

public static final long MAX_CONTEXTS

See Also:

Constant Field Values

exeception_type

public static final RefType exeception_type

max_cons_budget

public static int max_cons_budget

max_pts_budget

public static int max_pts_budget

cfa_blocks

public static int cfa_blocks

cg_refine_times

public static int cg_refine_times

worklist

protected IWorklist worklist

nodeGenerator

protected IEncodingBroker nodeGenerator

typeManager

protected TypeManager typeManager

offlineProcessor

protected OfflineProcessor offlineProcessor

consG

public Map<Node,IVarAbstraction> consG

pointers

public ZArrayNumberer<IVarAbstraction> pointers

allocations

public ZArrayNumberer<IVarAbstraction> allocations

constraints

public Vector<PlainConstraint> constraints

thread_run_callsites

public Set<Stmt> thread_run_callsites

mainID

public int mainID

context_size

public long[] context_size

max_context_size_block

public long[] max_context_size_block

block_num

public int[] block_num

max_scc_size

public int max_scc_size

max_scc_id

public int max_scc_id

n_var

public int n_var

n_alloc_sites

public int n_alloc_sites

n_func

public int n_func

n_calls

public int n_calls

n_reach_methods

public int n_reach_methods

n_reach_user_methods

public int n_reach_user_methods

dump_file_name

public String dump_file_name

solver_encoding

public int solver_encoding

ps

public PrintStream ps

validMethods

protected Map<String,Boolean> validMethods

call_graph

protected CgEdge[] call_graph

obsoletedEdges

protected Vector<CgEdge> obsoletedEdges

rev_call_graph

protected Map<Integer,LinkedList<CgEdge>> rev_call_graph

queue_cg

protected Deque<Integer> queue_cg

vis_cg

protected int[] vis_cg

low_cg

protected int[] low_cg

rep_cg

protected int[] rep_cg

indeg_cg

protected int[] indeg_cg

scc_size

protected int[] scc_size

pre_cnt

protected int pre_cnt

func2int

protected Map<SootMethod,Integer> func2int

int2func

protected Map<Integer,SootMethod> int2func

edgeMapping

protected Map<Edge,CgEdge> edgeMapping

Constructor Detail

GeomPointsTo

public GeomPointsTo(SparkOptions opts)

Method Detail

toString

public String toString()

Overrides:

toString in class Object

parametrize

public void parametrize()

countReachableMethods

protected int countReachableMethods(int s)

transformToCIResult

public void transformToCIResult()

For many applications, they only need the context insensitive points-to result. We provide a way to transfer our result back to SPARK. After the transformation, we discard the context sensitive points-to information. Therefore, the context sensitive queries are not served since then.

solve

public void solve()

getIDFromSootMethod

public int getIDFromSootMethod(SootMethod sm)

getSootMethodFromID

public SootMethod getSootMethodFromID(int fid)

isReachableMethod

public boolean isReachableMethod(int fid)

isValidMethod

public boolean isValidMethod(SootMethod sm)

outputNotEvaluatedMethods

public void outputNotEvaluatedMethods()

getAllReachableMethods

public Set<SootMethod> getAllReachableMethods()

getCallEgesOutFrom

public CgEdge getCallEgesOutFrom(int fid)

getCallEdgesInto

public LinkedList<CgEdge> getCallEdgesInto(int fid)

getMappedMethodID

public int getMappedMethodID(Node node)

getInternalNode

public IVarAbstraction getInternalNode(Node v)

castNeverFails

public boolean castNeverFails(Type src,
                              Type dst)

getNumberOfPointers

public int getNumberOfPointers()

getNumberOfObjects

public int getNumberOfObjects()

getNumberOfFunctions

public int getNumberOfFunctions()

getWorklist

public IWorklist getWorklist()

findAndInsertInstanceField

public IVarAbstraction findAndInsertInstanceField(AllocNode obj,
                                                  SparkField field)

getInternalEdgeFromSootEdge

public CgEdge getInternalEdgeFromSootEdge(Edge e)

reachingObjects

public PointsToSet reachingObjects(Local l)

Description copied from class: PAG

Returns the set of objects pointed to by variable l.

Specified by:

reachingObjects in interface PointsToAnalysis

Overrides:

reachingObjects in class PAG

reachingObjects

public PointsToSet reachingObjects(Context c,
                                   Local l)

Description copied from class: PAG

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

Specified by:

reachingObjects in interface PointsToAnalysis

Overrides:

reachingObjects in class PAG

reachingObjects

public PointsToSet reachingObjects(SootField f)

Description copied from class: PAG

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

Specified by:

reachingObjects in interface PointsToAnalysis

Overrides:

reachingObjects in class PAG

reachingObjects

public PointsToSet reachingObjects(PointsToSet s,
                                   SootField f)

Description copied from class: PAG

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

Specified by:

reachingObjects in interface PointsToAnalysis

Overrides:

reachingObjects in class PAG

reachingObjects

public PointsToSet reachingObjects(Local l,
                                   SootField f)

Description copied from class: PAG

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

Specified by:

reachingObjects in interface PointsToAnalysis

Overrides:

reachingObjects in class PAG

reachingObjects

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

Description copied from class: PAG

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

Overrides:

reachingObjects in class PAG

reachingObjectsOfArrayElement

public PointsToSet reachingObjectsOfArrayElement(PointsToSet s)

Description copied from class: PAG

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

Specified by:

reachingObjectsOfArrayElement in interface PointsToAnalysis

Overrides:

reachingObjectsOfArrayElement in class PAG

reachingObjects

public PointsToSet reachingObjects(AllocNode an,
                                   SootField f)