Package soot.jimple.spark.ondemand

Class DemandCSPointsTo

java.lang.Object

soot.jimple.spark.ondemand.DemandCSPointsTo

All Implemented Interfaces:

PointsToAnalysis

public final class DemandCSPointsTo
extends Object
implements PointsToAnalysis

Tries to find imprecision in points-to sets from a previously run analysis. Requires that all sub-results of previous analysis were cached.

Author:

Manu Sridharan

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected static class	DemandCSPointsTo.AllocAndContextCache
protected static class	DemandCSPointsTo.CallingContextSet
protected static class	DemandCSPointsTo.CallSiteAndContext
protected static class	DemandCSPointsTo.CallSiteToTargetsMap
protected static class	DemandCSPointsTo.IncomingEdgeHandler
protected static class	DemandCSPointsTo.VarAndContext
protected static class	DemandCSPointsTo.VarContextAndUp

Field Summary

Fields

Modifier and Type	Field	Description
protected DemandCSPointsTo.AllocAndContextCache	allocAndContextCache
protected Stack<Pair<Integer,ImmutableStack<Integer>>>	callGraphStack
protected DemandCSPointsTo.CallSiteToTargetsMap	callSiteToResolvedTargets
protected HashMap<List<Object>,Set<SootMethod>>	callTargetsArgCache
protected Stack<DemandCSPointsTo.VarAndContext>	contextForAllocsStack
protected Map<DemandCSPointsTo.VarAndContext,Pair<PointsToSetInternal,AllocAndContextSet>>	contextsForAllocsCache
protected ContextSensitiveInfo	csInfo
static boolean	DEBUG
protected static int	DEBUG_NESTING
protected static int	DEBUG_PASS
protected static boolean	DEBUG_VIRT
protected static boolean	DEFAULT_LAZY
protected static int	DEFAULT_MAX_PASSES
protected static int	DEFAULT_MAX_TRAVERSAL
protected boolean	doPointsTo	if true, compute full points-to set for queried variable
protected static ImmutableStack<Integer>	EMPTY_CALLSTACK
protected FieldCheckHeuristic	fieldCheckHeuristic
protected SootUtil.FieldToEdgesMap	fieldToLoads
protected SootUtil.FieldToEdgesMap	fieldToStores
protected HeuristicType	heuristicType
protected int	maxNodesPerPass
protected int	maxPasses
protected int	nesting
protected int	numNodesTraversed
protected int	numPasses
protected PAG	pag
protected AllocAndContextSet	pointsTo
protected Set<DemandCSPointsTo.CallSiteAndContext>	queriedCallSites
protected Map<Local,PointsToSet>	reachingObjectsCache
protected Map<Local,PointsToSet>	reachingObjectsCacheNoCGRefinement
protected int	recursionDepth
protected boolean	refiningCallSite
protected OTFMethodSCCManager	sccManager
protected Map<DemandCSPointsTo.VarContextAndUp,Map<AllocAndContext,DemandCSPointsTo.CallingContextSet>>	upContextCache
protected boolean	useCache
protected ValidMatches	vMatches

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
DemandCSPointsTo(ContextSensitiveInfo csInfo, PAG pag)
DemandCSPointsTo(ContextSensitiveInfo csInfo, PAG pag, int maxTraversal, int maxPasses, boolean lazy)

Method Summary

Modifier and Type	Method	Description
protected boolean	callEdgeInSCC(AssignEdge assignEdge)
protected DemandCSPointsTo.CallingContextSet	checkAllocAndContextCache(AllocAndContext allocAndContext, VarNode targetVar)
protected PointsToSetInternal	checkContextsForAllocsCache(DemandCSPointsTo.VarAndContext varAndContext, AllocAndContextSet ret, PointsToSetInternal locs)
protected boolean	checkP2Set(VarNode v, HeuristicType heuristic, Predicate<Set<AllocAndContext>> p2setPred)	check the computed points-to set of a variable against some predicate
protected DemandCSPointsTo.CallingContextSet	checkUpContextCache(DemandCSPointsTo.VarContextAndUp varContextAndUp, AllocAndContext allocAndContext)
void	clearCache()	clears the cache
protected void	clearState()
protected Set<VarNode>	computeFlowsTo(AllocNode alloc, HeuristicType heuristic)	compute a flows-to set for an allocation site.
protected PointsToSet	computeReachingObjects(Local l)	Computes the possibly refined set of reaching objects for l.
protected PointsToSet	computeRefinedReachingObjects(VarNode v)	Computes the refined set of reaching objects for l.
protected void	debugPrint(String str)
void	disableCache()	disables caching
PointsToSet	doReachingObjects(Local l)
protected void	dumpPathForLoc(VarNode v, AllocNode badLoc, String filePrefix)
void	enableCache()	enables caching
protected Collection<AssignEdge>	filterAssigns(VarNode v, ImmutableStack<Integer> callingContext, boolean forward, boolean refineVirtCalls)
protected AllocAndContextSet	findContextsForAllocs(DemandCSPointsTo.VarAndContext varAndContext, PointsToSetInternal locs)
protected DemandCSPointsTo.CallingContextSet	findUpContextsForVar(AllocAndContext allocAndContext, DemandCSPointsTo.VarContextAndUp varContextAndUp)
protected DemandCSPointsTo.CallingContextSet	findVarContextsFromAlloc(AllocAndContext allocAndContext, VarNode targetVar)
protected Set<SootMethod>	getCallTargets(PointsToSetInternal p2Set, SootMethod callee, Type receiverType, Set<SootMethod> possibleTargets)
protected Set<SootMethod>	getCallTargetsForType(Type type, SootMethod callee, Type receiverType, Set<SootMethod> possibleTargets)
protected Set<VarNode>	getFlowsToHelper(AllocAndContext allocAndContext)
HeuristicType	getHeuristicType()
protected int	getMaxPasses()
PAG	getPAG()
protected void	incrementNodesTraversed()
protected boolean	isRecursive(ImmutableStack<Integer> context, AssignEdge assignEdge)
protected boolean	isRecursiveCallSite(Integer callSite)
boolean	isRefineCallGraph()
static DemandCSPointsTo	makeDefault()	Make a default analysis.
static DemandCSPointsTo	makeWithBudget(int maxTraversal, int maxPasses, boolean lazy)
protected Set<VarNode>	nodesPropagatedThrough(VarNode source, PointsToSetInternal allocs)
protected ImmutableStack<Integer>	popRecursiveCallSites(ImmutableStack<Integer> context)
protected void	processIncomingEdges(DemandCSPointsTo.IncomingEdgeHandler h, Stack<DemandCSPointsTo.VarAndContext> worklist)
protected ImmutableStack<Integer>	pushWithRecursionCheck(ImmutableStack<Integer> context, AssignEdge assignEdge)
PointsToSet	reachingObjects(Context c, Local l)	Currently not implemented.
PointsToSet	reachingObjects(Context c, Local l, SootField f)	Currently not implemented.
PointsToSet	reachingObjects(Local l)	Returns the set of objects pointed to by variable l.
PointsToSet	reachingObjects(Local l, SootField f)	Currently not implemented.
PointsToSet	reachingObjects(PointsToSet s, SootField f)	Currently not implemented.
PointsToSet	reachingObjects(SootField f)	Currently not implemented.
PointsToSet	reachingObjectsOfArrayElement(PointsToSet s)	Currently not implemented.
protected boolean	refineAlias(VarNode v1, VarNode v2, PointsToSetInternal intersection, HeuristicType heuristic)
protected boolean	refineAliasInternal(VarNode v1, VarNode v2, PointsToSetInternal intersection, HeuristicType heuristic)
protected Set<SootMethod>	refineCallSite(Integer callSite, ImmutableStack<Integer> origContext)
protected boolean	refineP2Set(DemandCSPointsTo.VarAndContext varAndContext, PointsToSetInternal badLocs)
protected boolean	refineP2Set(VarNode v, PointsToSetInternal badLocs, HeuristicType heuristic)
void	setHeuristicType(HeuristicType heuristicType)
void	setRefineCallGraph(boolean refineCallGraph)
boolean	usesCache()
protected boolean	weirdCall(Integer callSite)

Methods inherited from class java.lang.Object

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

Field Detail

DEBUG

public static boolean DEBUG

DEBUG_NESTING

protected static final int DEBUG_NESTING

See Also:

Constant Field Values

DEBUG_PASS

protected static final int DEBUG_PASS

See Also:

Constant Field Values

DEBUG_VIRT

protected static final boolean DEBUG_VIRT

DEFAULT_MAX_PASSES

protected static final int DEFAULT_MAX_PASSES

See Also:

Constant Field Values

DEFAULT_MAX_TRAVERSAL

protected static final int DEFAULT_MAX_TRAVERSAL

See Also:

Constant Field Values

DEFAULT_LAZY

protected static final boolean DEFAULT_LAZY

See Also:

Constant Field Values

EMPTY_CALLSTACK

protected static final ImmutableStack<Integer> EMPTY_CALLSTACK

allocAndContextCache

protected final DemandCSPointsTo.AllocAndContextCache allocAndContextCache

callGraphStack

protected Stack<Pair<Integer,ImmutableStack<Integer>>> callGraphStack

callSiteToResolvedTargets

protected final DemandCSPointsTo.CallSiteToTargetsMap callSiteToResolvedTargets

callTargetsArgCache

protected HashMap<List<Object>,Set<SootMethod>> callTargetsArgCache

contextForAllocsStack

protected final Stack<DemandCSPointsTo.VarAndContext> contextForAllocsStack

contextsForAllocsCache

protected Map<DemandCSPointsTo.VarAndContext,Pair<PointsToSetInternal,AllocAndContextSet>> contextsForAllocsCache

csInfo

protected final ContextSensitiveInfo csInfo

doPointsTo

protected boolean doPointsTo

if true, compute full points-to set for queried variable

fieldCheckHeuristic

protected FieldCheckHeuristic fieldCheckHeuristic

heuristicType

protected HeuristicType heuristicType

fieldToLoads

protected SootUtil.FieldToEdgesMap fieldToLoads

fieldToStores

protected SootUtil.FieldToEdgesMap fieldToStores

maxNodesPerPass

protected final int maxNodesPerPass

maxPasses

protected final int maxPasses

nesting

protected int nesting

numNodesTraversed

protected int numNodesTraversed

numPasses

protected int numPasses

pag

protected final PAG pag

pointsTo

protected AllocAndContextSet pointsTo

queriedCallSites

protected final Set<DemandCSPointsTo.CallSiteAndContext> queriedCallSites

recursionDepth

protected int recursionDepth

refiningCallSite

protected boolean refiningCallSite

sccManager

protected OTFMethodSCCManager sccManager

upContextCache

protected Map<DemandCSPointsTo.VarContextAndUp,Map<AllocAndContext,DemandCSPointsTo.CallingContextSet>> upContextCache

vMatches

protected ValidMatches vMatches

reachingObjectsCache

protected Map<Local,PointsToSet> reachingObjectsCache

reachingObjectsCacheNoCGRefinement

protected Map<Local,PointsToSet> reachingObjectsCacheNoCGRefinement

useCache

protected boolean useCache

Constructor Detail

DemandCSPointsTo

public DemandCSPointsTo(ContextSensitiveInfo csInfo,
                        PAG pag)

DemandCSPointsTo

public DemandCSPointsTo(ContextSensitiveInfo csInfo,
                        PAG pag,
                        int maxTraversal,
                        int maxPasses,
                        boolean lazy)

Method Detail

makeDefault

public static DemandCSPointsTo makeDefault()

Make a default analysis. Assumes Spark has already run.

Returns:

makeWithBudget

public static DemandCSPointsTo makeWithBudget(int maxTraversal,
                                              int maxPasses,
                                              boolean lazy)

reachingObjects

public PointsToSet reachingObjects(Local l)

Description copied from interface: PointsToAnalysis

Returns the set of objects pointed to by variable l.

Specified by:

reachingObjects in interface PointsToAnalysis

doReachingObjects

public PointsToSet doReachingObjects(Local l)

computeReachingObjects

protected PointsToSet computeReachingObjects(Local l)

Computes the possibly refined set of reaching objects for l.

computeRefinedReachingObjects

protected PointsToSet computeRefinedReachingObjects(VarNode v)

Computes the refined set of reaching objects for l. Returns null if refinement failed.

callEdgeInSCC

protected boolean callEdgeInSCC(AssignEdge assignEdge)

checkAllocAndContextCache

protected DemandCSPointsTo.CallingContextSet checkAllocAndContextCache(AllocAndContext allocAndContext,
                                                                       VarNode targetVar)

checkContextsForAllocsCache

protected PointsToSetInternal checkContextsForAllocsCache(DemandCSPointsTo.VarAndContext varAndContext,
                                                          AllocAndContextSet ret,
                                                          PointsToSetInternal locs)

checkP2Set

protected boolean checkP2Set(VarNode v,
                             HeuristicType heuristic,
                             Predicate<Set<AllocAndContext>> p2setPred)

check the computed points-to set of a variable against some predicate

Parameters:

v - the variable

heuristic - how to refine match edges

p2setPred - the predicate on the points-to set

Returns:

true if the p2setPred holds for the computed points-to set, or if a points-to set cannot be computed in the budget; false otherwise

checkUpContextCache

protected DemandCSPointsTo.CallingContextSet checkUpContextCache(DemandCSPointsTo.VarContextAndUp varContextAndUp,
                                                                 AllocAndContext allocAndContext)

clearState

protected void clearState()

computeFlowsTo

protected Set<VarNode> computeFlowsTo(AllocNode alloc,
                                      HeuristicType heuristic)

compute a flows-to set for an allocation site. for now, we use a simple refinement strategy; just refine as much as possible, maintaining the smallest set of flows-to vars

Parameters:

alloc -

heuristic -

Returns:

debugPrint

protected void debugPrint(String str)

dumpPathForLoc

protected void dumpPathForLoc(VarNode v,
                              AllocNode badLoc,
                              String filePrefix)

filterAssigns

protected Collection<AssignEdge> filterAssigns(VarNode v,
                                               ImmutableStack<Integer> callingContext,
                                               boolean forward,
                                               boolean refineVirtCalls)

findContextsForAllocs

protected AllocAndContextSet findContextsForAllocs(DemandCSPointsTo.VarAndContext varAndContext,
                                                   PointsToSetInternal locs)

findUpContextsForVar

protected DemandCSPointsTo.CallingContextSet findUpContextsForVar(AllocAndContext allocAndContext,
                                                                  DemandCSPointsTo.VarContextAndUp varContextAndUp)

findVarContextsFromAlloc

protected DemandCSPointsTo.CallingContextSet findVarContextsFromAlloc(AllocAndContext allocAndContext,
                                                                      VarNode targetVar)

getCallTargets

protected Set<SootMethod> getCallTargets(PointsToSetInternal p2Set,
                                         SootMethod callee,
                                         Type receiverType,
                                         Set<SootMethod> possibleTargets)

getCallTargetsForType

protected Set<SootMethod> getCallTargetsForType(Type type,
                                                SootMethod callee,
                                                Type receiverType,
                                                Set<SootMethod> possibleTargets)

getFlowsToHelper

protected Set<VarNode> getFlowsToHelper(AllocAndContext allocAndContext)

getMaxPasses

protected int getMaxPasses()

incrementNodesTraversed

protected void incrementNodesTraversed()

isRecursive

protected boolean isRecursive(ImmutableStack<Integer> context,
                              AssignEdge assignEdge)

isRecursiveCallSite

protected boolean isRecursiveCallSite(Integer callSite)

nodesPropagatedThrough

protected Set<VarNode> nodesPropagatedThrough(VarNode source,
                                              PointsToSetInternal allocs)

popRecursiveCallSites

protected ImmutableStack<Integer> popRecursiveCallSites(ImmutableStack<Integer> context)

processIncomingEdges

protected void processIncomingEdges(DemandCSPointsTo.IncomingEdgeHandler h,
                                    Stack<DemandCSPointsTo.VarAndContext> worklist)

pushWithRecursionCheck

protected ImmutableStack<Integer> pushWithRecursionCheck(ImmutableStack<Integer> context,
                                                         AssignEdge assignEdge)

refineAlias

protected boolean refineAlias(VarNode v1,
                              VarNode v2,
                              PointsToSetInternal intersection,
                              HeuristicType heuristic)

refineAliasInternal

protected boolean refineAliasInternal(VarNode v1,
                                      VarNode v2,
                                      PointsToSetInternal intersection,
                                      HeuristicType heuristic)

refineCallSite

protected Set<SootMethod> refineCallSite(Integer callSite,
                                         ImmutableStack<Integer> origContext)

refineP2Set

protected boolean refineP2Set(DemandCSPointsTo.VarAndContext varAndContext,
                              PointsToSetInternal badLocs)

refineP2Set

protected boolean refineP2Set(VarNode v,
                              PointsToSetInternal badLocs,
                              HeuristicType heuristic)

weirdCall

protected boolean weirdCall(Integer callSite)

reachingObjects

public PointsToSet reachingObjects(Context c,
                                   Local l)

Currently not implemented.

Specified by:

reachingObjects in interface PointsToAnalysis

Throws:

UnsupportedOperationException - always

reachingObjects

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

Currently not implemented.

Specified by:

reachingObjects in interface PointsToAnalysis

Throws:

UnsupportedOperationException - always

reachingObjects

public PointsToSet reachingObjects(Local l,
                                   SootField f)

Currently not implemented.

Specified by:

reachingObjects in interface PointsToAnalysis

Throws:

UnsupportedOperationException - always

reachingObjects

public PointsToSet reachingObjects(PointsToSet s,
                                   SootField f)

Currently not implemented.

Specified by:

reachingObjects in interface PointsToAnalysis

Throws:

UnsupportedOperationException - always

reachingObjects

public PointsToSet reachingObjects(SootField f)

Currently not implemented.

Specified by:

reachingObjects in interface PointsToAnalysis

Throws:

UnsupportedOperationException - always

reachingObjectsOfArrayElement

public PointsToSet reachingObjectsOfArrayElement(PointsToSet s)

Currently not implemented.

Specified by:

reachingObjectsOfArrayElement in interface PointsToAnalysis

Throws:

UnsupportedOperationException - always

getPAG

public PAG getPAG()

Returns:

returns the (SPARK) pointer assignment graph

usesCache

public boolean usesCache()

Returns:

true is caching is enabled

enableCache

public void enableCache()

enables caching

disableCache

public void disableCache()

disables caching

clearCache

public void clearCache()

clears the cache

isRefineCallGraph

public boolean isRefineCallGraph()

setRefineCallGraph

public void setRefineCallGraph(boolean refineCallGraph)

getHeuristicType

public HeuristicType getHeuristicType()

setHeuristicType

public void setHeuristicType(HeuristicType heuristicType)