SVF::ContextDDA Class Reference

#include <ContextDDA.h>

Inheritance diagram for SVF::ContextDDA:

Public Member Functions
	ContextDDA (SVFIR *_pag, DDAClient *client)
	Constructor.
virtual	~ContextDDA ()
	Destructor.
virtual void	initialize () override
	Initialization of the analysis.
virtual void	finalize () override
	Finalize analysis.
virtual void	analyze () override
	dummy analyze method
virtual void	computeDDAPts (NodeID id) override
	Compute points-to set for an unconditional pointer.
virtual const CxtPtSet &	computeDDAPts (const CxtVar &cxtVar)
	Compute points-to set for a context-sensitive pointer.
void	handleOutOfBudgetDpm (const CxtLocDPItem &dpm)
	Handle out-of-budget dpm.
virtual CxtPtSet	getConservativeCPts (const CxtLocDPItem &dpm) override
	Override parent method.
virtual NodeID	getPtrNodeID (const CxtVar &var) const override
	Override parent method.
virtual bool	handleBKCondition (CxtLocDPItem &dpm, const SVFGEdge *edge) override
	Handle condition for context or path analysis (backward analysis)
virtual bool	isHeapCondMemObj (const CxtVar &var, const StoreSVFGNode *store) override
bool	testIndCallReachability (CxtLocDPItem &dpm, const FunObjVar *callee, const CallICFGNode *cs)
	refine indirect call edge
CallSiteID	getCSIDAtCall (CxtLocDPItem &dpm, const SVFGEdge *edge)
	get callsite id from call, return 0 if it is a spurious call edge
CallSiteID	getCSIDAtRet (CxtLocDPItem &dpm, const SVFGEdge *edge)
	get callsite id from return, return 0 if it is a spurious return edge
virtual void	popRecursiveCallSites (CxtLocDPItem &dpm)
	Pop recursive callsites.
virtual bool	isEdgeInRecursion (CallSiteID csId)
	Whether call/return inside recursion.
virtual void	updateCallGraphAndSVFG (const CxtLocDPItem &dpm, const CallICFGNode *cs, SVFGEdgeSet &svfgEdges) override
	Update call graph.
bool	edgeInCallGraphSCC (const SVFGEdge *edge)
	Return TRUE if this edge is inside a SVFG SCC, i.e., src node and dst node are in the same SCC on the SVFG.
virtual CxtPtSet	processGepPts (const GepSVFGNode *gep, const CxtPtSet &srcPts) override
	processGep node
virtual void	handleAddr (CxtPtSet &pts, const CxtLocDPItem &dpm, const AddrSVFGNode *addr) override
	Handle Address SVFGNode to add proper conditional points-to.
virtual bool	propagateViaObj (const CxtVar &storeObj, const CxtVar &loadObj) override
	Propagate along indirect value-flow if two objects of load and store are same.
virtual bool	isCondCompatible (const ContextCond &cxt1, const ContextCond &cxt2, bool singleton) const override
bool	isInsensitiveCallRet (const SVFGEdge *edge)
	Whether this edge is treated context-insensitively.
ConstSVFGEdgeSet &	getInsensitiveEdgeSet ()
	Return insensitive edge set.
virtual void	dumpContexts (const ContextCond &cxts)
	dump context call strings
virtual const std::string	PTAName () const override
	Return PTA name.
Public Member Functions inherited from SVF::CondPTAImpl< ContextCond >
	CondPTAImpl (SVFIR *pag, PointerAnalysis::PTATY type)
	map a pointer to its conditional points-to set
virtual	~CondPTAImpl ()
	Destructor.
void	destroy ()
	Release memory.
PTDataTy *	getPTDataTy () const
	Get points-to data.
MutPTDataTy *	getMutPTDataTy () const
bool	hasPtsMap (void) const
const MutPTDataTy::PtsMap &	getPtsMap () const
virtual const CPtSet &	getPts (CVar id)
virtual PointsTo &	getPts (NodeID ptr)
	Given a pointer return its bit vector points-to.
virtual const Set< CVar > &	getRevPts (CVar nodeId)
virtual NodeSet &	getRevPts (NodeID obj)
	Given an object return all pointers points to this object.
virtual void	clearPts ()
	Clear all data.
bool	overlap (const CPtSet &cpts1, const CPtSet &cpts2) const
	Whether cpts1 and cpts2 have overlap points-to targets.
void	expandFIObjs (const CPtSet &cpts, CPtSet &expandedCpts)
	Expand all fields of an aggregate in all points-to sets.
virtual void	dumpCPts ()
	Print out conditional pts.
virtual PointsTo	getBVPointsTo (const CPtSet &cpts) const
	Given a conditional pts return its bit vector points-to.
virtual const CPtSet &	getCondPointsTo (NodeID ptr)
	Given a pointer return its conditional points-to.
virtual AliasResult	alias (const SVFVar *V1, const SVFVar *V2)
	Interface expose to users of our pointer analysis, given Value infos.
virtual AliasResult	alias (NodeID node1, NodeID node2)
	Interface expose to users of our pointer analysis, given two pointers.
virtual AliasResult	alias (const CVar &var1, const CVar &var2)
	Interface expose to users of our pointer analysis, given conditional variables.
virtual AliasResult	alias (const CPtSet &pts1, const CPtSet &pts2)
	Interface expose to users of our pointer analysis, given two conditional points-to sets.
bool	containBlackHoleNode (const CPtSet &cpts)
	Test blk node for cpts.
bool	containConstantNode (const CPtSet &cpts)
	Test constant node for cpts.
void	dumpTopLevelPtsTo ()
	Dump points-to information of top-level pointers.
Public Member Functions inherited from SVF::PointerAnalysis
ICFG *	getICFG () const
	Get ICFG.
u32_t	getNumOfResolvedIndCallEdge () const
	Return number of resolved indirect call edges.
CallGraph *	getCallGraph () const
	Return call graph.
CallGraphSCC *	getCallGraphSCC () const
	Return call graph SCC.
	PointerAnalysis (SVFIR *pag, PTATY ty=Default_PTA, bool alias_check=true)
	Constructor.
PTATY	getAnalysisTy () const
	Type of pointer analysis.
PTAImplTy	getImplTy () const
	Return implementation type of the pointer analysis.
bool	printStat ()
	Whether print statistics.
void	disablePrintStat ()
	Whether print statistics.
CallEdgeMap &	getIndCallMap ()
	Get callees from an indirect callsite.
bool	hasIndCSCallees (const CallICFGNode *cs) const
const FunctionSet &	getIndCSCallees (const CallICFGNode *cs) const
virtual void	resolveIndCalls (const CallICFGNode *cs, const PointsTo &target, CallEdgeMap &newEdges)
	Resolve indirect call edges.
void	callGraphSCCDetection ()
	PTACallGraph SCC related methods.
NodeID	getCallGraphSCCRepNode (NodeID id) const
	Get SCC rep node of a SVFG node.
bool	inSameCallGraphSCC (const FunObjVar *fun1, const FunObjVar *fun2)
	Return TRUE if this edge is inside a PTACallGraph SCC, i.e., src node and dst node are in the same SCC on the SVFG.
bool	isInRecursion (const FunObjVar *fun) const
bool	isLocalVarInRecursiveFun (NodeID id) const
	Whether a local variable is in function recursions.
CommonCHGraph *	getCHGraph () const
	get CHGraph
void	getVFnsFromCHA (const CallICFGNode *cs, VFunSet &vfns)
void	getVFnsFromPts (const CallICFGNode *cs, const PointsTo &target, VFunSet &vfns)
void	connectVCallToVFns (const CallICFGNode *cs, const VFunSet &vfns, CallEdgeMap &newEdges)
virtual void	resolveCPPIndCalls (const CallICFGNode *cs, const PointsTo &target, CallEdgeMap &newEdges)
	Resolve cpp indirect call edges.
SVFIR *	getPAG () const
PTAStat *	getStat () const
	Get PTA stat.
OrderedNodeSet &	getAllValidPtrs ()
	Get all Valid Pointers for resolution.
void	printIndCSTargets (const CallICFGNode *cs, const FunctionSet &targets)
	Print targets of a function pointer.
virtual void	dumpAllPts ()
virtual void	dumpPts (NodeID ptr, const PointsTo &pts)
void	printIndCSTargets ()
void	dumpAllTypes ()
void	dumpStat ()
	Dump the statistics.
bool	containBlackHoleNode (const PointsTo &pts)
	Determine whether a points-to contains a black hole or constant node.
bool	containConstantNode (const PointsTo &pts)
virtual bool	isBlkObjOrConstantObj (NodeID ptd) const
bool	isHeapMemObj (NodeID id) const
	Whether this object is heap or array.
bool	isArrayMemObj (NodeID id) const
bool	isFIObjNode (NodeID id) const
NodeID	getBaseObjVar (NodeID id)
NodeID	getFIObjVar (NodeID id)
NodeID	getGepObjVar (NodeID id, const APOffset &ap)
virtual const NodeBS &	getAllFieldsObjVars (NodeID id)
void	setObjFieldInsensitive (NodeID id)
bool	isFieldInsensitive (NodeID id) const
Public Member Functions inherited from SVF::DDAVFSolver< CxtVar, CxtPtSet, CxtLocDPItem >
	DDAVFSolver ()
	Constructor.
virtual	~DDAVFSolver ()
	Destructor.
NodeBS &	getCandidateQueries ()
	Return candidate pointers for DDA.
virtual CxtLocDPItem	getDPIm (const CxtVar &var, const SVFGNode *loc) const
	Given CVar and location (SVFGNode) return a new DPItem.
virtual bool	unionDDAPts (CxtPtSet &pts, const CxtPtSet &targetPts)
	Union pts.
virtual bool	unionDDAPts (CxtLocDPItem dpm, const CxtPtSet &targetPts)
	Union pts.
virtual void	addDDAPts (CxtPtSet &pts, const CxtVar &var)
	Add pts.
SVFG *	getSVFG () const
	Return SVFG.
SVFGSCC *	getSVFGSCC () const
	Return SVFGSCC.
void	dumpCPtSet (const CxtPtSet &cpts) const
virtual const CxtPtSet &	findPT (const CxtLocDPItem &dpm)
	Compute points-to.

Private Attributes
ConstSVFGEdgeSet	insensitveEdges
	insensitive call-return edges
FlowDDA *	flowDDA
	downgrade to flowDDA if out-of-budget
DDAClient *	_client
	DDA client.

Additional Inherited Members
Public Types inherited from SVF::CondPTAImpl< ContextCond >
typedef CondVar< ContextCond >	CVar
typedef CondStdSet< CVar >	CPtSet
typedef PTData< CVar, Set< CVar >, CVar, CPtSet >	PTDataTy
typedef MutablePTData< CVar, Set< CVar >, CVar, CPtSet >	MutPTDataTy
typedef Map< NodeID, PointsTo >	PtrToBVPtsMap
typedef Map< NodeID, NodeSet >	PtrToNSMap
	map a pointer to its BitVector points-to representation
typedef Map< NodeID, CPtSet >	PtrToCPtsMap
Public Types inherited from SVF::PointerAnalysis
enum	PTATY {   Andersen_BASE , Andersen_WPA , AndersenSCD_WPA , AndersenSFR_WPA ,   AndersenWaveDiff_WPA , Steensgaard_WPA , CSCallString_WPA , CSSummary_WPA ,   FSDATAFLOW_WPA , FSSPARSE_WPA , VFS_WPA , FSCS_WPA ,   CFLFICI_WPA , CFLFSCI_WPA , CFLFSCS_WPA , TypeCPP_WPA ,   FieldS_DDA , FlowS_DDA , PathS_DDA , Cxt_DDA ,   Default_PTA }
	Pointer analysis type list. More...
enum	PTAImplTy { BaseImpl , BVDataImpl , CondImpl }
	Implementation type: BVDataPTAImpl or CondPTAImpl. More...
typedef Set< const CallICFGNode * >	CallSiteSet
	Indirect call edges type, map a callsite to a set of callees.
typedef SVFIR::CallSiteToFunPtrMap	CallSiteToFunPtrMap
typedef Set< const FunObjVar * >	FunctionSet
typedef OrderedMap< const CallICFGNode *, FunctionSet >	CallEdgeMap
typedef SCCDetection< CallGraph * >	CallGraphSCC
typedef Set< const GlobalObjVar * >	VTableSet
typedef Set< const FunObjVar * >	VFunSet
Public Types inherited from SVF::DDAVFSolver< CxtVar, CxtPtSet, CxtLocDPItem >
typedef SCCDetection< SVFG * >	SVFGSCC
typedef SCCDetection< CallGraph * >	CallGraphSCC
typedef CallGraphEdge::CallInstSet	CallInstSet
typedef SVFIR::CallSiteSet	CallSiteSet
typedef OrderedSet< CxtLocDPItem >	DPTItemSet
typedef OrderedMap< CxtLocDPItem, CxtPtSet >	DPImToCPtSetMap
typedef OrderedMap< CxtLocDPItem, CxtVar >	DPMToCVarMap
typedef OrderedMap< CxtLocDPItem, CxtLocDPItem >	DPMToDPMMap
typedef OrderedMap< NodeID, DPTItemSet >	LocToDPMVecMap
typedef OrderedSet< const SVFGEdge * >	ConstSVFGEdgeSet
typedef SVFGEdge::SVFGEdgeSetTy	SVFGEdgeSet
typedef OrderedMap< const SVFGNode *, DPTItemSet >	StoreToPMSetMap
Static Public Member Functions inherited from SVF::CondPTAImpl< ContextCond >
static bool	classof (const PointerAnalysis *pta)
Static Public Attributes inherited from SVF::PointerAnalysis
static const std::string	aliasTestMayAlias = "MAYALIAS"
static const std::string	aliasTestMayAliasMangled = "_Z8MAYALIASPvS_"
static const std::string	aliasTestNoAlias = "NOALIAS"
static const std::string	aliasTestNoAliasMangled = "_Z7NOALIASPvS_"
static const std::string	aliasTestPartialAlias = "PARTIALALIAS"
static const std::string	aliasTestPartialAliasMangled = "_Z12PARTIALALIASPvS_"
static const std::string	aliasTestMustAlias = "MUSTALIAS"
static const std::string	aliasTestMustAliasMangled = "_Z9MUSTALIASPvS_"
static const std::string	aliasTestFailMayAlias = "EXPECTEDFAIL_MAYALIAS"
static const std::string	aliasTestFailMayAliasMangled = "_Z21EXPECTEDFAIL_MAYALIASPvS_"
static const std::string	aliasTestFailNoAlias = "EXPECTEDFAIL_NOALIAS"
static const std::string	aliasTestFailNoAliasMangled = "_Z20EXPECTEDFAIL_NOALIASPvS_"
Protected Member Functions inherited from SVF::CondPTAImpl< ContextCond >
virtual bool	unionPts (CVar id, const CPtSet &target)
virtual bool	unionPts (CVar id, CVar ptd)
virtual bool	addPts (CVar id, CVar ptd)
bool	mustAlias (const CVar &var1, const CVar &var2)
	Internal interface to be used for conditional points-to set queries.
bool	contains (const CPtSet &cpts1, const CPtSet &cpts2)
bool	isSameVar (const CVar &var1, const CVar &var2) const
	Whether two pointers/objects are the same one by considering their conditions.
virtual void	normalizePointsTo ()
	Normalize points-to information to BitVector/conditional representation.
Protected Member Functions inherited from SVF::PointerAnalysis
const CallSiteToFunPtrMap &	getIndirectCallsites () const
	Return all indirect callsites.
NodeID	getFunPtr (const CallICFGNode *cs) const
	Return function pointer PAGNode at a callsite cs.
virtual void	validateTests ()
	Alias check functions to verify correctness of pointer analysis.
virtual void	validateSuccessTests (std::string fun)
virtual void	validateExpectedFailureTests (std::string fun)
void	resetObjFieldSensitive ()
	Reset all object node as field-sensitive.
Protected Member Functions inherited from SVF::DDAVFSolver< CxtVar, CxtPtSet, CxtLocDPItem >
virtual void	handleSingleStatement (const CxtLocDPItem &dpm, CxtPtSet &pts)
	Handle single statement.
void	reCompute (const CxtLocDPItem &dpm)
	recompute points-to for value-flow cycles and indirect calls
void	reComputeForEdges (const CxtLocDPItem &dpm, const SVFGEdgeSet &edgeSet, bool indirectCall=false)
	Traverse along out edges to find all nodes which may be affected by locDPM.
virtual void	buildSVFG (SVFIR *pag)
	Build SVFG.
virtual void	resetQuery ()
	Reset visited map for next points-to query.
void	OOBResetVisited ()
	Reset visited map if the current query is out-of-budget.
const SVFGNode *	getDefSVFGNode (const PAGNode *pagNode) const
	GetDefinition SVFG.
void	backtraceAlongIndirectVF (CxtPtSet &pts, const CxtLocDPItem &oldDpm)
	Backward traverse along indirect value flows.
void	backtraceAlongDirectVF (CxtPtSet &pts, const CxtLocDPItem &oldDpm)
	Backward traverse along direct value flows.
void	startNewPTCompFromLoadSrc (CxtPtSet &pts, const CxtLocDPItem &oldDpm)
void	startNewPTCompFromStoreDst (CxtPtSet &pts, const CxtLocDPItem &oldDpm)
void	backtraceToStoreSrc (CxtPtSet &pts, const CxtLocDPItem &oldDpm)
virtual void	backwardPropDpm (CxtPtSet &pts, NodeID ptr, const CxtLocDPItem &oldDpm, const SVFGEdge *edge)
	dpm transit during backward tracing
virtual bool	isMustAlias (const CxtLocDPItem &, const CxtLocDPItem &)
	whether load and store are aliased
virtual bool	isStrongUpdate (const CxtPtSet &dstCPSet, const StoreSVFGNode *store)
	Return TRUE if this is a strong update STORE statement.
virtual bool	isLocalCVarInRecursion (const CxtVar &var) const
	Whether a local variable is in function recursions.
void	resolveFunPtr (const CxtLocDPItem &dpm)
	resolve function pointer
void	markbkVisited (const CxtLocDPItem &dpm)
	Visited flags to avoid cycles.
bool	isbkVisited (const CxtLocDPItem &dpm)
void	clearbkVisited (const CxtLocDPItem &dpm)
virtual const CxtPtSet &	getCachedPointsTo (const CxtLocDPItem &dpm)
	Points-to Caching for top-level pointers and address-taken objects.
virtual void	updateCachedPointsTo (const CxtLocDPItem &dpm, const CxtPtSet &pts)
virtual const CxtPtSet &	getCachedTLPointsTo (const CxtLocDPItem &dpm)
virtual const CxtPtSet &	getCachedADPointsTo (const CxtLocDPItem &dpm)
bool	isTopLevelPtrStmt (const SVFGNode *stmt)
	Whether this is a top-level pointer statement.
virtual CxtLocDPItem	getDPImWithOldCond (const CxtLocDPItem &oldDpm, const CxtVar &var, const SVFGNode *loc)
	Return dpm with old context and path conditions.
void	SVFGSCCDetection ()
	SVFG SCC detection.
NodeID	getSVFGSCCRepNode (NodeID id)
	Get SCC rep node of a SVFG node.
bool	isSVFGNodeInCycle (const SVFGNode *node)
	Return whether this SVFGNode is in cycle.
bool	edgeInSVFGSCC (const SVFGEdge *edge)
	Return TRUE if this edge is inside a SVFG SCC, i.e., src node and dst node are in the same SCC on the SVFG.
void	setCallGraph (CallGraph *cg)
	Set callgraph.
void	setCallGraphSCC (CallGraphSCC *scc)
	Set callgraphSCC.
bool	isArrayCondMemObj (const CxtVar &var) const
bool	isFieldInsenCondMemObj (const CxtVar &var) const
void	addLoadDpmAndCVar (const CxtLocDPItem &dpm, const CxtLocDPItem &loadDpm, const CxtVar &loadVar)
	LoadDpm for must-alias analysis.
void	addLoadDpm (const CxtLocDPItem &dpm, const CxtLocDPItem &loadDpm)
	Note that simply use "dpmToloadDpmMap[dpm]=loadDpm", requires DPIm have a default constructor.
const CxtLocDPItem &	getLoadDpm (const CxtLocDPItem &dpm) const
void	addLoadCVar (const CxtLocDPItem &dpm, const CxtVar &loadVar)
const CxtVar &	getLoadCVar (const CxtLocDPItem &dpm) const
AndersenWaveDiff *	getAndersenAnalysis () const
	Return Andersen's analysis.
void	handleOutOfBudgetDpm (const CxtLocDPItem &dpm)
	handle out-of-budget queries
bool	testOutOfBudget (const CxtLocDPItem &dpm)
bool	isOutOfBudgetQuery () const
void	addOutOfBudgetDpm (const CxtLocDPItem &dpm)
bool	isOutOfBudgetDpm (const CxtLocDPItem &dpm) const
DDAStat *	setDDAStat (DDAStat *s)
	Set DDAStat.
void	addSUStat (const CxtLocDPItem &dpm, const SVFGNode *node)
	stat strong updates num
void	rmSUStat (const CxtLocDPItem &dpm, const SVFGNode *node)
	remove strong updates num if the dpm goes to weak updates branch
Protected Attributes inherited from SVF::CondPTAImpl< ContextCond >
PTDataTy *	ptD
	Points-to data.
bool	normalized
	Normalized flag.
PtrToBVPtsMap	ptrToBVPtsMap
	Normal points-to representation (without conditions)
PtrToNSMap	objToNSRevPtsMap
	Normal points-to representation (without conditions)
PtrToCPtsMap	ptrToCPtsMap
	Conditional points-to representation (with conditions)
Protected Attributes inherited from SVF::PointerAnalysis
bool	print_stat
	User input flags.
bool	alias_validation
	Flag for validating points-to/alias results.
u32_t	OnTheFlyIterBudgetForStat
	Flag for iteration budget for on-the-fly statistics.
PTATY	ptaTy
	Pointer analysis Type.
PTAImplTy	ptaImplTy
	PTA implementation type.
PTAStat *	stat
	Statistics.
CallGraph *	callgraph
	Call graph used for pointer analysis.
CallGraphSCC *	callGraphSCC
	SCC for PTACallGraph.
ICFG *	icfg
	Interprocedural control-flow graph.
CommonCHGraph *	chgraph
	CHGraph.
Protected Attributes inherited from SVF::DDAVFSolver< CxtVar, CxtPtSet, CxtLocDPItem >
bool	outOfBudgetQuery
	Whether the current query is out of step limits.
SVFIR *	_pag
	SVFIR.
SVFG *	_svfg
	SVFG.
AndersenWaveDiff *	_ander
	Andersen's analysis.
NodeBS	candidateQueries
	candidate pointers;
CallGraph *	_callGraph
	PTACallGraph.
CallGraphSCC *	_callGraphSCC
	SCC for PTACallGraph.
SVFGSCC *	_svfgSCC
	SCC for SVFG.
DPTItemSet	backwardVisited
	visited map during backward traversing
DPImToCPtSetMap	dpmToTLCPtSetMap
	points-to caching map for top-level vars
DPImToCPtSetMap	dpmToADCPtSetMap
	points-to caching map for address-taken vars
LocToDPMVecMap	locToDpmSetMap
	map location to its dpms
DPMToDPMMap	dpmToloadDpmMap
	dpms at loads for may/must-alias analysis with stores
DPMToCVarMap	loadToPTCVarMap
	map a load dpm to its cvar pointed by its pointer operand
DPTItemSet	outOfBudgetDpms
	out of budget dpm set
StoreToPMSetMap	storeToDPMs
	map store to set of DPM which have been stong updated there
DDAStat *	ddaStat
	DDA stat.
SVFGBuilder	svfgBuilder
	SVFG Builder.
Static Protected Attributes inherited from SVF::PointerAnalysis
static SVFIR *	pag = nullptr
	SVFIR.

Detailed Description

Context-, Flow- Sensitive Demand-driven Analysis

Definition at line 54 of file ContextDDA.h.

Constructor & Destructor Documentation

ContextDDA()

ContextDDA::ContextDDA	(	SVFIR *	_pag,
		DDAClient *	client
	)

Constructor.

Constructor

Definition at line 42 of file ContextDDA.cpp.

    : CondPTAImpl<ContextCond>(_pag, PointerAnalysis::Cxt_DDA),DDAVFSolver<CxtVar,CxtPtSet,CxtLocDPItem>(),
      _client(client)
{
    flowDDA = new FlowDDA(_pag, client);
}

~ContextDDA()

ContextDDA::~ContextDDA ( )

virtual

Destructor.

Destructor

Definition at line 52 of file ContextDDA.cpp.

{
    if(flowDDA)
        delete flowDDA;
    flowDDA = nullptr;
}

Member Function Documentation

analyze()

virtual void SVF::ContextDDA::analyze ( )

inlineoverridevirtual

dummy analyze method

Implements SVF::PointerAnalysis.

Definition at line 74 of file ContextDDA.h.

{}

computeDDAPts() [1/2]

const CxtPtSet & ContextDDA::computeDDAPts ( const CxtVar &  var )

virtual

Compute points-to set for a context-sensitive pointer.

Compute points-to set for a context-sensitive pointer

Definition at line 75 of file ContextDDA.cpp.

{
 
    resetQuery();
    LocDPItem::setMaxBudget(Options::CxtBudget());
 
    NodeID id = var.get_id();
    PAGNode* node = getPAG()->getGNode(id);
    CxtLocDPItem dpm = getDPIm(var, getDefSVFGNode(node));
 
    // start DDA analysis
    DOTIMESTAT(double start = DDAStat::getClk(true));
    const CxtPtSet& cpts = findPT(dpm);
    DOTIMESTAT(ddaStat->_AnaTimePerQuery = DDAStat::getClk(true) - start);
    DOTIMESTAT(ddaStat->_TotalTimeOfQueries += ddaStat->_AnaTimePerQuery);
 
    if(isOutOfBudgetQuery() == false)
        unionPts(var,cpts);
    else
        handleOutOfBudgetDpm(dpm);
 
    if (this->printStat())
        DOSTAT(stat->performStatPerQuery(id));
    DBOUT(DGENERAL, stat->printStatPerQuery(id,getBVPointsTo(getPts(var))));
    return this->getPts(var);
}

computeDDAPts() [2/2]

void ContextDDA::computeDDAPts ( NodeID  id )

overridevirtual

Compute points-to set for an unconditional pointer.

Compute points-to set for an unconditional pointer

Reimplemented from SVF::PointerAnalysis.

Definition at line 105 of file ContextDDA.cpp.

{
    ContextCond cxt;
    CxtVar var(cxt, id);
    computeDDAPts(var);
}

dumpContexts()

virtual void SVF::ContextDDA::dumpContexts ( const ContextCond &  cxts )

inlinevirtual

dump context call strings

Definition at line 212 of file ContextDDA.h.

    {
        SVFUtil::outs() << cxts.toString() << "\n";
    }

edgeInCallGraphSCC()

bool SVF::ContextDDA::edgeInCallGraphSCC ( const SVFGEdge *  edge )

inline

Return TRUE if this edge is inside a SVFG SCC, i.e., src node and dst node are in the same SCC on the SVFG.

Definition at line 160 of file ContextDDA.h.

    {
        const FunObjVar* srcfun = edge->getSrcNode()->getFun();
        const FunObjVar* dstfun = edge->getDstNode()->getFun();
 
        if(srcfun && dstfun)
            return inSameCallGraphSCC(srcfun,dstfun);
 
        assert(edge->isRetVFGEdge() == false && "should not be an inter-procedural return edge" );
 
        return false;
    }

finalize()

virtual void SVF::ContextDDA::finalize ( )

inlineoverridevirtual

Finalize analysis.

Reimplemented from SVF::CondPTAImpl< ContextCond >.

Definition at line 68 of file ContextDDA.h.

    {
        CondPTAImpl<ContextCond>::finalize();
    }

getConservativeCPts()

virtual CxtPtSet SVF::ContextDDA::getConservativeCPts ( const CxtLocDPItem &  dpm )

inlineoverridevirtual

Override parent method.

Implements SVF::DDAVFSolver< CxtVar, CxtPtSet, CxtLocDPItem >.

Definition at line 86 of file ContextDDA.h.

    {
        const PointsTo& pts =  getAndersenAnalysis()->getPts(dpm.getCurNodeID());
        CxtPtSet tmpCPts;
        ContextCond cxt;
        for (PointsTo::iterator piter = pts.begin(); piter != pts.end(); ++piter)
        {
            CxtVar var(cxt,*piter);
            tmpCPts.set(var);
        }
        return tmpCPts;
    }

getCSIDAtCall()

CallSiteID ContextDDA::getCSIDAtCall	(	CxtLocDPItem &	dpm,
		const SVFGEdge *	edge
	)

get callsite id from call, return 0 if it is a spurious call edge

get callsite id from call, return 0 if it is a spurious call edge translate the callsite id from pre-computed callgraph on SVFG to the one on current callgraph

Definition at line 210 of file ContextDDA.cpp.

{
 
    CallSiteID svfg_csId = 0;
    if (const CallDirSVFGEdge* callEdge = SVFUtil::dyn_cast<CallDirSVFGEdge>(edge))
        svfg_csId = callEdge->getCallSiteId();
    else
        svfg_csId = SVFUtil::cast<CallIndSVFGEdge>(edge)->getCallSiteId();
 
    const CallICFGNode* cbn = getSVFG()->getCallSite(svfg_csId);
    const FunObjVar* callee = edge->getDstNode()->getFun();
 
    if(getCallGraph()->hasCallSiteID(cbn,callee))
    {
        return getCallGraph()->getCallSiteID(cbn,callee);
    }
 
    return 0;
}

getCSIDAtRet()

CallSiteID ContextDDA::getCSIDAtRet	(	CxtLocDPItem &	dpm,
		const SVFGEdge *	edge
	)

get callsite id from return, return 0 if it is a spurious return edge

get callsite id from return, return 0 if it is a spurious return edge translate the callsite id from pre-computed callgraph on SVFG to the one on current callgraph

Definition at line 234 of file ContextDDA.cpp.

{
 
    CallSiteID svfg_csId = 0;
    if (const RetDirSVFGEdge* retEdge = SVFUtil::dyn_cast<RetDirSVFGEdge>(edge))
        svfg_csId = retEdge->getCallSiteId();
    else
        svfg_csId = SVFUtil::cast<RetIndSVFGEdge>(edge)->getCallSiteId();
 
    const CallICFGNode* cbn = getSVFG()->getCallSite(svfg_csId);
    const FunObjVar* callee = edge->getSrcNode()->getFun();
 
    if(getCallGraph()->hasCallSiteID(cbn,callee))
    {
        return getCallGraph()->getCallSiteID(cbn,callee);
    }
 
    return 0;
}

getInsensitiveEdgeSet()

ConstSVFGEdgeSet & SVF::ContextDDA::getInsensitiveEdgeSet ( )

inline

Return insensitive edge set.

Definition at line 207 of file ContextDDA.h.

    {
        return insensitveEdges;
    }

getPtrNodeID()

virtual NodeID SVF::ContextDDA::getPtrNodeID ( const CxtVar &  var ) const

inlineoverridevirtual

Override parent method.

Implements SVF::DDAVFSolver< CxtVar, CxtPtSet, CxtLocDPItem >.

Definition at line 100 of file ContextDDA.h.

    {
        return var.get_id();
    }

handleAddr()

virtual void SVF::ContextDDA::handleAddr ( CxtPtSet &  pts, const CxtLocDPItem &  dpm, const AddrSVFGNode *  addr  )

inlineoverridevirtual

Handle Address SVFGNode to add proper conditional points-to.

whether this object is set field-insensitive during pre-analysis

Implements SVF::DDAVFSolver< CxtVar, CxtPtSet, CxtLocDPItem >.

Definition at line 177 of file ContextDDA.h.

    {
        NodeID srcID = addr->getPAGSrcNodeID();
        if (isFieldInsensitive(srcID))
            srcID = getFIObjVar(srcID);
 
        CxtVar var(dpm.getCond(),srcID);
        addDDAPts(pts,var);
        DBOUT(DDDA, SVFUtil::outs() << "\t add points-to target " << var << " to dpm ");
        DBOUT(DDDA, dpm.dump());
    }

handleBKCondition()

bool ContextDDA::handleBKCondition ( CxtLocDPItem &  dpm, const SVFGEdge *  edge  )

overridevirtual

Handle condition for context or path analysis (backward analysis)

Handle conditions during backward traversing.

we don't handle context in recursions, they treated as assignments

we don't handle context in recursions, they treated as assignments

TODO: When this call site id is contained in current call string, we may find a recursion. Try to solve this later.

Reimplemented from SVF::DDAVFSolver< CxtVar, CxtPtSet, CxtLocDPItem >.

Definition at line 256 of file ContextDDA.cpp.

{
    _client->handleStatement(edge->getSrcNode(), dpm.getCurNodeID());
 
    if (edge->isCallVFGEdge())
    {
        if(CallSiteID csId = getCSIDAtCall(dpm,edge))
        {
 
            if(isEdgeInRecursion(csId))
            {
                DBOUT(DDDA,outs() << "\t\t call edge " << getCallGraph()->getCallerOfCallSite(csId)->getName() <<
                      "=>" << getCallGraph()->getCalleeOfCallSite(csId)->getName() << "in recursion \n");
                popRecursiveCallSites(dpm);
            }
            else
            {
                if (dpm.matchContext(csId) == false)
                {
                    DBOUT(DDDA, outs() << "\t\t context not match, edge "
                          << edge->getDstID() << " --| " << edge->getSrcID() << " \t");
                    DBOUT(DDDA, dumpContexts(dpm.getCond()));
                    return false;
                }
 
                DBOUT(DDDA, outs() << "\t\t match contexts ");
                DBOUT(DDDA, dumpContexts(dpm.getCond()));
            }
        }
    }
 
    else if (edge->isRetVFGEdge())
    {
        if(CallSiteID csId = getCSIDAtRet(dpm,edge))
        {
 
            if(isEdgeInRecursion(csId))
            {
                DBOUT(DDDA,outs() << "\t\t return edge " << getCallGraph()->getCalleeOfCallSite(csId)->getName() <<
                      "=>" << getCallGraph()->getCallerOfCallSite(csId)->getName() << "in recursion \n");
                popRecursiveCallSites(dpm);
            }
            else
            {
                if (dpm.getCond().containCallStr(csId))
                {
                    outOfBudgetQuery = true;
                    SVFUtil::writeWrnMsg("Call site ID is contained in call string. Is this a recursion?");
                    return false;
                }
                else
                {
                    assert(dpm.getCond().containCallStr(csId) ==false && "contain visited call string ??");
                    if(dpm.pushContext(csId))
                    {
                        DBOUT(DDDA, outs() << "\t\t push context ");
                        DBOUT(DDDA, dumpContexts(dpm.getCond()));
                    }
                    else
                    {
                        DBOUT(DDDA, outs() << "\t\t context is full ");
                        DBOUT(DDDA, dumpContexts(dpm.getCond()));
                    }
                }
            }
        }
    }
 
    return true;
}

handleOutOfBudgetDpm()

void ContextDDA::handleOutOfBudgetDpm

(

const CxtLocDPItem &

dpm

)

Handle out-of-budget dpm.

Handle out-of-budget dpm

Definition at line 115 of file ContextDDA.cpp.

{
 
    DBOUT(DGENERAL,outs() << "~~~Out of budget query, downgrade to flow sensitive analysis \n");
    flowDDA->computeDDAPts(dpm.getCurNodeID());
    const PointsTo& flowPts = flowDDA->getPts(dpm.getCurNodeID());
    CxtPtSet cxtPts;
    for(PointsTo::iterator it = flowPts.begin(), eit = flowPts.end(); it!=eit; ++it)
    {
        ContextCond cxt;
        CxtVar var(cxt, *it);
        cxtPts.set(var);
    }
    updateCachedPointsTo(dpm,cxtPts);
    unionPts(dpm.getCondVar(),cxtPts);
    addOutOfBudgetDpm(dpm);
}

initialize()

void ContextDDA::initialize ( )

overridevirtual

Initialization of the analysis.

Analysis initialization

Reimplemented from SVF::PointerAnalysis.

Definition at line 62 of file ContextDDA.cpp.

{
    CondPTAImpl<ContextCond>::initialize();
    buildSVFG(pag);
    setCallGraph(getCallGraph());
    setCallGraphSCC(getCallGraphSCC());
    stat = setDDAStat(new DDAStat(this));
    flowDDA->initialize();
}

isCondCompatible()

bool ContextDDA::isCondCompatible ( const ContextCond &  cxt1, const ContextCond &  cxt2, bool  singleton  ) const

inlineoverridevirtual

Whether two call string contexts are compatible which may represent the same memory object compare with call strings from last few callsite ids (most recent ids to objects): compatible : (e.g., 123 == 123, 123 == 23). not compatible (e.g., 123 != 423)

context conditions of local(not in recursion) and global variables are compatible

Implements SVF::CondPTAImpl< ContextCond >.

Definition at line 136 of file ContextDDA.cpp.

{
    if(singleton)
        return true;
 
    int i = cxt1.cxtSize() - 1;
    int j = cxt2.cxtSize() - 1;
    for(; i >= 0 && j>=0; i--, j--)
    {
        if(cxt1[i] != cxt2[j])
            return false;
    }
    return true;
}

isEdgeInRecursion()

virtual bool SVF::ContextDDA::isEdgeInRecursion ( CallSiteID  csId )

inlinevirtual

Whether call/return inside recursion.

Definition at line 134 of file ContextDDA.h.

    {
        const FunObjVar* caller = getCallGraph()->getCallerOfCallSite(csId);
        const FunObjVar* callee = getCallGraph()->getCalleeOfCallSite(csId);
        return inSameCallGraphSCC(caller, callee);
    }

isHeapCondMemObj()

bool ContextDDA::isHeapCondMemObj ( const CxtVar &  var, const StoreSVFGNode *  store  )

overridevirtual

we exclude concrete heap given the following conditions: (1) concrete calling context (not involved in recursion and not exceed the maximum context limit) (2) not inside loop

Reimplemented from SVF::DDAVFSolver< CxtVar, CxtPtSet, CxtLocDPItem >.

Definition at line 335 of file ContextDDA.cpp.

{
    const BaseObjVar* obj = _pag->getBaseObject(getPtrNodeID(var));
    assert(obj && "base object is null??");
    const BaseObjVar* baseVar = _pag->getBaseObject(getPtrNodeID(var));
    assert(baseVar && "base object is null??");
    if (SVFUtil::isa<HeapObjVar, DummyObjVar>(baseVar))
    {
        if (!isa<DummyObjVar>(baseVar))
        {
            PAGNode *pnode = _pag->getGNode(getPtrNodeID(var));
            GepObjVar* gepobj = SVFUtil::dyn_cast<GepObjVar>(pnode);
            if (gepobj != nullptr)
            {
                assert(SVFUtil::isa<DummyObjVar>(_pag->getGNode(gepobj->getBaseNode()))
                       && "empty refVal in a gep object whose base is a non-dummy object");
            }
            else
            {
                assert((SVFUtil::isa<DummyObjVar, DummyValVar>(pnode))
                       && "empty refVal in non-dummy object");
            }
            return true;
        }
        else if(const ICFGNode* node = obj->getICFGNode())
        {
            const FunObjVar* svfFun = node->getFun();
            if(_ander->isInRecursion(svfFun))
                return true;
            if(var.get_cond().isConcreteCxt() == false)
                return true;
            if(_pag->getICFG()->isInLoop(node))
                return true;
        }
    }
    return false;
}

isInsensitiveCallRet()

bool SVF::ContextDDA::isInsensitiveCallRet ( const SVFGEdge *  edge )

inline

Whether this edge is treated context-insensitively.

Definition at line 202 of file ContextDDA.h.

    {
        return insensitveEdges.find(edge) != insensitveEdges.end();
    }

popRecursiveCallSites()

virtual void SVF::ContextDDA::popRecursiveCallSites ( CxtLocDPItem &  dpm )

inlinevirtual

Pop recursive callsites.

Definition at line 123 of file ContextDDA.h.

    {
        ContextCond& cxtCond = dpm.getCond();
        cxtCond.setNonConcreteCxt();
        CallStrCxt& cxt = cxtCond.getContexts();
        while(!cxt.empty() && isEdgeInRecursion(cxt.back()))
        {
            cxt.pop_back();
        }
    }

processGepPts()

CxtPtSet ContextDDA::processGepPts ( const GepSVFGNode *  gep, const CxtPtSet &  srcPts  )

overridevirtual

processGep node

Generate field objects for structs

Implements SVF::DDAVFSolver< CxtVar, CxtPtSet, CxtLocDPItem >.

Definition at line 154 of file ContextDDA.cpp.

{
    CxtPtSet tmpDstPts;
    for (CxtPtSet::iterator piter = srcPts.begin(); piter != srcPts.end(); ++piter)
    {
 
        CxtVar ptd = *piter;
        if (isBlkObjOrConstantObj(ptd.get_id()))
            tmpDstPts.set(ptd);
        else
        {
            const GepStmt* gepStmt = SVFUtil::cast<GepStmt>(gep->getPAGEdge());
            if (gepStmt->isVariantFieldGep())
            {
                setObjFieldInsensitive(ptd.get_id());
                CxtVar var(ptd.get_cond(),getFIObjVar(ptd.get_id()));
                tmpDstPts.set(var);
            }
            else
            {
                CxtVar var(ptd.get_cond(),getGepObjVar(ptd.get_id(),
                                                       gepStmt->getAccessPath().getConstantStructFldIdx()));
                tmpDstPts.set(var);
            }
        }
    }
 
    DBOUT(DDDA, outs() << "\t return created gep objs ");
    DBOUT(DDDA, outs() << srcPts.toString());
    DBOUT(DDDA, outs() << " --> ");
    DBOUT(DDDA, outs() << tmpDstPts.toString());
    DBOUT(DDDA, outs() << "\n");
    return tmpDstPts;
}

propagateViaObj()

virtual bool SVF::ContextDDA::propagateViaObj ( const CxtVar &  storeObj, const CxtVar &  loadObj  )

inlineoverridevirtual

Propagate along indirect value-flow if two objects of load and store are same.

Reimplemented from SVF::DDAVFSolver< CxtVar, CxtPtSet, CxtLocDPItem >.

Definition at line 191 of file ContextDDA.h.

    {
        return isSameVar(storeObj,loadObj);
    }

PTAName()

virtual const std::string SVF::ContextDDA::PTAName ( ) const

inlineoverridevirtual

Return PTA name.

Reimplemented from SVF::PointerAnalysis.

Definition at line 217 of file ContextDDA.h.

    {
        return "Context Sensitive DDA";
    }

testIndCallReachability()

bool ContextDDA::testIndCallReachability	(	CxtLocDPItem &	dpm,
		const FunObjVar *	callee,
		const CallICFGNode *	cs
	)

refine indirect call edge

Definition at line 189 of file ContextDDA.cpp.

{
    if(getPAG()->isIndirectCallSites(cs))
    {
        NodeID id = getPAG()->getFunPtr(cs);
        PAGNode* node = getPAG()->getGNode(id);
        CxtVar funptrVar(dpm.getCondVar().get_cond(), id);
        CxtLocDPItem funptrDpm = getDPIm(funptrVar,getDefSVFGNode(node));
        PointsTo pts = getBVPointsTo(findPT(funptrDpm));
        if(pts.test(callee->getId()))
            return true;
        else
            return false;
    }
    return true;
}

updateCallGraphAndSVFG()

virtual void SVF::ContextDDA::updateCallGraphAndSVFG ( const CxtLocDPItem &  dpm, const CallICFGNode *  cs, SVFGEdgeSet &  svfgEdges  )

inlineoverridevirtual

Update call graph.

Reimplemented from SVF::DDAVFSolver< CxtVar, CxtPtSet, CxtLocDPItem >.

Definition at line 142 of file ContextDDA.h.

    {
        CallEdgeMap newEdges;
        resolveIndCalls(cs, getBVPointsTo(getCachedPointsTo(dpm)), newEdges);
        for (CallEdgeMap::const_iterator iter = newEdges.begin(),eiter = newEdges.end(); iter != eiter; iter++)
        {
            const CallICFGNode* newcs = iter->first;
            const FunctionSet & functions = iter->second;
            for (FunctionSet::const_iterator func_iter = functions.begin(); func_iter != functions.end(); func_iter++)
            {
                const FunObjVar*  func = *func_iter;
                getSVFG()->connectCallerAndCallee(newcs, func, svfgEdges);
            }
        }
    }

Member Data Documentation

_client

DDAClient* SVF::ContextDDA::_client

private

DDA client.

Definition at line 225 of file ContextDDA.h.

flowDDA

FlowDDA* SVF::ContextDDA::flowDDA

private

downgrade to flowDDA if out-of-budget

Definition at line 224 of file ContextDDA.h.

insensitveEdges

ConstSVFGEdgeSet SVF::ContextDDA::insensitveEdges

private

insensitive call-return edges

Definition at line 223 of file ContextDDA.h.

---

The documentation for this class was generated from the following files:

• /home/runner/work/SVF/SVF/svf/include/DDA/ContextDDA.h
• /home/runner/work/SVF/SVF/svf/lib/DDA/ContextDDA.cpp