Static Value-Flow Analysis
|
#include <FlowDDA.h>
Public Member Functions | |
FlowDDA (SVFIR *_pag, DDAClient *client) | |
Constructor. More... | |
virtual | ~FlowDDA () |
Destructor. More... | |
virtual void | analyze () override |
dummy analyze method More... | |
void | computeDDAPts (NodeID id) override |
Compute points-to set for all top variable. More... | |
void | handleOutOfBudgetDpm (const LocDPItem &dpm) |
Handle out-of-budget dpm. More... | |
virtual bool | handleBKCondition (LocDPItem &dpm, const SVFGEdge *edge) override |
Handle condition for flow analysis (backward analysis) More... | |
bool | testIndCallReachability (LocDPItem &dpm, const SVFFunction *callee, CallSiteID csId) |
refine indirect call edge More... | |
virtual void | initialize () override |
Initialization of the analysis. More... | |
virtual void | finalize () override |
Finalize analysis. More... | |
virtual bool | isHeapCondMemObj (const NodeID &var, const StoreSVFGNode *store) override |
virtual PointsTo | getConservativeCPts (const LocDPItem &dpm) override |
Override parent method. More... | |
virtual NodeID | getPtrNodeID (const NodeID &var) const override |
Override parent method. More... | |
virtual void | handleAddr (PointsTo &pts, const LocDPItem &dpm, const AddrSVFGNode *addr) override |
Handle Address SVFGNode to add proper points-to. More... | |
virtual PointsTo | processGepPts (const GepSVFGNode *gep, const PointsTo &srcPts) override |
processGep node More... | |
virtual void | updateCallGraphAndSVFG (const LocDPItem &dpm, const CallICFGNode *cs, SVFGEdgeSet &svfgEdges) override |
Update call graph. More... | |
virtual const PointsTo & | getCachedTLPointsTo (const LocDPItem &dpm) override |
Override parent class functions to get/add cached points-to directly via PAGNode ID. More... | |
bool | unionDDAPts (LocDPItem dpm, const PointsTo &targetPts) override |
Union pts. More... | |
virtual const std::string | PTAName () const override |
Return PTA name. More... | |
Public Member Functions inherited from SVF::BVDataPTAImpl | |
BVDataPTAImpl (SVFIR *pag, PointerAnalysis::PTATY type, bool alias_check=true) | |
Constructor. More... | |
~BVDataPTAImpl () override=default | |
Destructor. More... | |
PersistentPointsToCache< PointsTo > & | getPtCache () |
const PointsTo & | getPts (NodeID id) override |
const NodeSet & | getRevPts (NodeID nodeId) override |
virtual void | clearPts (NodeID id, NodeID element) |
Remove element from the points-to set of id. More... | |
virtual void | clearFullPts (NodeID id) |
Clear points-to set of id. More... | |
virtual bool | unionPts (NodeID id, const PointsTo &target) |
virtual bool | unionPts (NodeID id, NodeID ptd) |
virtual bool | addPts (NodeID id, NodeID ptd) |
virtual void | clearAllPts () |
Clear all data. More... | |
virtual void | expandFIObjs (const PointsTo &pts, PointsTo &expandedPts) |
Expand FI objects. More... | |
virtual void | expandFIObjs (const NodeBS &pts, NodeBS &expandedPts) |
TODO: remove repetition. More... | |
void | remapPointsToSets (void) |
Remap all points-to sets to use the current mapping. More... | |
virtual void | writeToFile (const std::string &filename) |
Interface for analysis result storage on filesystem. More... | |
virtual void | writeObjVarToFile (const std::string &filename) |
virtual void | writePtsResultToFile (std::fstream &f) |
virtual void | writeGepObjVarMapToFile (std::fstream &f) |
virtual bool | readFromFile (const std::string &filename) |
virtual void | readPtsResultFromFile (std::ifstream &f) |
virtual void | readGepObjVarMapFromFile (std::ifstream &f) |
virtual void | readAndSetObjFieldSensitivity (std::ifstream &f, const std::string &delimiterStr) |
AliasResult | alias (const SVFValue *V1, const SVFValue *V2) override |
Interface expose to users of our pointer analysis, given Value infos. More... | |
AliasResult | alias (NodeID node1, NodeID node2) override |
Interface expose to users of our pointer analysis, given PAGNodeID. More... | |
virtual AliasResult | alias (const PointsTo &pts1, const PointsTo &pts2) |
Interface expose to users of our pointer analysis, given two pts. More... | |
void | dumpCPts () override |
dump and debug, print out conditional pts More... | |
void | dumpTopLevelPtsTo () override |
void | dumpAllPts () override |
Public Member Functions inherited from SVF::PointerAnalysis | |
ICFG * | getICFG () const |
Get ICFG. More... | |
u32_t | getNumOfResolvedIndCallEdge () const |
Return number of resolved indirect call edges. More... | |
PTACallGraph * | getCallGraph () const |
Return call graph. More... | |
CallGraphSCC * | getCallGraphSCC () const |
Return call graph SCC. More... | |
PointerAnalysis (SVFIR *pag, PTATY ty=Default_PTA, bool alias_check=true) | |
Constructor. More... | |
PTATY | getAnalysisTy () const |
Type of pointer analysis. More... | |
PTAImplTy | getImplTy () const |
Return implementation type of the pointer analysis. More... | |
bool | printStat () |
Whether print statistics. More... | |
void | disablePrintStat () |
Whether print statistics. More... | |
CallEdgeMap & | getIndCallMap () |
Get callees from an indirect callsite. More... | |
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. More... | |
void | callGraphSCCDetection () |
PTACallGraph SCC related methods. More... | |
NodeID | getCallGraphSCCRepNode (NodeID id) const |
Get SCC rep node of a SVFG node. More... | |
bool | inSameCallGraphSCC (const SVFFunction *fun1, const SVFFunction *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. More... | |
bool | isInRecursion (const SVFFunction *fun) const |
bool | isLocalVarInRecursiveFun (NodeID id) const |
Whether a local variable is in function recursions. More... | |
CommonCHGraph * | getCHGraph () const |
get CHGraph More... | |
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. More... | |
SVFIR * | getPAG () const |
PTAStat * | getStat () const |
Get PTA stat. More... | |
SVFModule * | getModule () const |
Module. More... | |
OrderedNodeSet & | getAllValidPtrs () |
Get all Valid Pointers for resolution. More... | |
virtual | ~PointerAnalysis () |
Destructor. More... | |
void | printIndCSTargets (const CallICFGNode *cs, const FunctionSet &targets) |
Print targets of a function pointer. More... | |
virtual void | dumpPts (NodeID ptr, const PointsTo &pts) |
void | printIndCSTargets () |
void | dumpAllTypes () |
void | dumpStat () |
Dump the statistics. More... | |
bool | containBlackHoleNode (const PointsTo &pts) |
Determine whether a points-to contains a black hole or constant node. More... | |
bool | containConstantNode (const PointsTo &pts) |
virtual bool | isBlkObjOrConstantObj (NodeID ptd) const |
bool | isHeapMemObj (NodeID id) const |
Whether this object is heap or array. More... | |
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< NodeID, PointsTo, LocDPItem > | |
DDAVFSolver () | |
Constructor. More... | |
virtual | ~DDAVFSolver () |
Destructor. More... | |
NodeBS & | getCandidateQueries () |
Return candidate pointers for DDA. More... | |
virtual LocDPItem | getDPIm (const NodeID &var, const SVFGNode *loc) const |
Given CVar and location (SVFGNode) return a new DPItem. More... | |
virtual bool | unionDDAPts (PointsTo &pts, const PointsTo &targetPts) |
Union pts. More... | |
virtual void | addDDAPts (PointsTo &pts, const NodeID &var) |
Add pts. More... | |
SVFG * | getSVFG () const |
Return SVFG. More... | |
SVFGSCC * | getSVFGSCC () const |
Return SVFGSCC. More... | |
void | dumpCPtSet (const PointsTo &cpts) const |
virtual const PointsTo & | findPT (const LocDPItem &dpm) |
Compute points-to. More... | |
Private Attributes | |
DDAClient * | _client |
DDA client. More... | |
Additional Inherited Members | |
Static Public Member Functions inherited from SVF::BVDataPTAImpl | |
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::BVDataPTAImpl | |
PTDataTy * | getPTDataTy () const |
Get points-to data structure. More... | |
void | finalize () override |
Finalization of pointer analysis, and normalize points-to information to Bit Vector representation. More... | |
virtual bool | updateCallGraph (const CallSiteToFunPtrMap &) |
Update callgraph. This should be implemented by its subclass. More... | |
DiffPTDataTy * | getDiffPTDataTy () const |
DFPTDataTy * | getDFPTDataTy () const |
MutDFPTDataTy * | getMutDFPTDataTy () const |
VersionedPTDataTy * | getVersionedPTDataTy () const |
virtual void | onTheFlyCallGraphSolve (const CallSiteToFunPtrMap &callsites, CallEdgeMap &newEdges) |
On the fly call graph construction. More... | |
virtual void | onTheFlyThreadCallGraphSolve (const CallSiteToFunPtrMap &callsites, CallEdgeMap &newForkEdges) |
On the fly thread call graph construction respecting forksite. More... | |
virtual void | normalizePointsTo () |
Protected Member Functions inherited from SVF::PointerAnalysis | |
const CallSiteToFunPtrMap & | getIndirectCallsites () const |
Return all indirect callsites. More... | |
NodeID | getFunPtr (const CallICFGNode *cs) const |
Return function pointer PAGNode at a callsite cs. More... | |
virtual void | validateTests () |
Alias check functions to verify correctness of pointer analysis. More... | |
virtual void | validateSuccessTests (std::string fun) |
virtual void | validateExpectedFailureTests (std::string fun) |
void | resetObjFieldSensitive () |
Reset all object node as field-sensitive. More... | |
Protected Member Functions inherited from SVF::DDAVFSolver< NodeID, PointsTo, LocDPItem > | |
virtual void | handleSingleStatement (const LocDPItem &dpm, PointsTo &pts) |
Handle single statement. More... | |
void | reCompute (const LocDPItem &dpm) |
recompute points-to for value-flow cycles and indirect calls More... | |
void | reComputeForEdges (const LocDPItem &dpm, const SVFGEdgeSet &edgeSet, bool indirectCall=false) |
Traverse along out edges to find all nodes which may be affected by locDPM. More... | |
virtual void | buildSVFG (SVFIR *pag) |
Build SVFG. More... | |
virtual void | resetQuery () |
Reset visited map for next points-to query. More... | |
void | OOBResetVisited () |
Reset visited map if the current query is out-of-budget. More... | |
const SVFGNode * | getDefSVFGNode (const PAGNode *pagNode) const |
GetDefinition SVFG. More... | |
void | backtraceAlongIndirectVF (PointsTo &pts, const LocDPItem &oldDpm) |
Backward traverse along indirect value flows. More... | |
void | backtraceAlongDirectVF (PointsTo &pts, const LocDPItem &oldDpm) |
Backward traverse along direct value flows. More... | |
void | startNewPTCompFromLoadSrc (PointsTo &pts, const LocDPItem &oldDpm) |
void | startNewPTCompFromStoreDst (PointsTo &pts, const LocDPItem &oldDpm) |
void | backtraceToStoreSrc (PointsTo &pts, const LocDPItem &oldDpm) |
virtual void | backwardPropDpm (PointsTo &pts, NodeID ptr, const LocDPItem &oldDpm, const SVFGEdge *edge) |
dpm transit during backward tracing More... | |
virtual bool | isMustAlias (const LocDPItem &, const LocDPItem &) |
whether load and store are aliased More... | |
virtual bool | isStrongUpdate (const PointsTo &dstCPSet, const StoreSVFGNode *store) |
Return TRUE if this is a strong update STORE statement. More... | |
virtual bool | isLocalCVarInRecursion (const NodeID &var) const |
Whether a local variable is in function recursions. More... | |
virtual bool | propagateViaObj (const NodeID &storeObj, const NodeID &loadObj) |
If the points-to contain the object obj, we could move forward along indirect value-flow edge. More... | |
void | resolveFunPtr (const LocDPItem &dpm) |
resolve function pointer More... | |
void | markbkVisited (const LocDPItem &dpm) |
Visited flags to avoid cycles. More... | |
bool | isbkVisited (const LocDPItem &dpm) |
void | clearbkVisited (const LocDPItem &dpm) |
virtual const PointsTo & | getCachedPointsTo (const LocDPItem &dpm) |
Points-to Caching for top-level pointers and address-taken objects. More... | |
virtual void | updateCachedPointsTo (const LocDPItem &dpm, const PointsTo &pts) |
virtual const PointsTo & | getCachedADPointsTo (const LocDPItem &dpm) |
bool | isTopLevelPtrStmt (const SVFGNode *stmt) |
Whether this is a top-level pointer statement. More... | |
virtual LocDPItem | getDPImWithOldCond (const LocDPItem &oldDpm, const NodeID &var, const SVFGNode *loc) |
Return dpm with old context and path conditions. More... | |
void | SVFGSCCDetection () |
SVFG SCC detection. More... | |
NodeID | getSVFGSCCRepNode (NodeID id) |
Get SCC rep node of a SVFG node. More... | |
bool | isSVFGNodeInCycle (const SVFGNode *node) |
Return whether this SVFGNode is in cycle. More... | |
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. More... | |
void | setCallGraph (PTACallGraph *cg) |
Set callgraph. More... | |
void | setCallGraphSCC (CallGraphSCC *scc) |
Set callgraphSCC. More... | |
bool | isArrayCondMemObj (const NodeID &var) const |
bool | isFieldInsenCondMemObj (const NodeID &var) const |
void | addLoadDpmAndCVar (const LocDPItem &dpm, const LocDPItem &loadDpm, const NodeID &loadVar) |
LoadDpm for must-alias analysis. More... | |
void | addLoadDpm (const LocDPItem &dpm, const LocDPItem &loadDpm) |
Note that simply use "dpmToloadDpmMap[dpm]=loadDpm", requires DPIm have a default constructor. More... | |
const LocDPItem & | getLoadDpm (const LocDPItem &dpm) const |
void | addLoadCVar (const LocDPItem &dpm, const NodeID &loadVar) |
const NodeID & | getLoadCVar (const LocDPItem &dpm) const |
AndersenWaveDiff * | getAndersenAnalysis () const |
Return Andersen's analysis. More... | |
void | handleOutOfBudgetDpm (const LocDPItem &dpm) |
handle out-of-budget queries More... | |
bool | testOutOfBudget (const LocDPItem &dpm) |
bool | isOutOfBudgetQuery () const |
void | addOutOfBudgetDpm (const LocDPItem &dpm) |
bool | isOutOfBudgetDpm (const LocDPItem &dpm) const |
DDAStat * | setDDAStat (DDAStat *s) |
Set DDAStat. More... | |
void | addSUStat (const LocDPItem &dpm, const SVFGNode *node) |
stat strong updates num More... | |
void | rmSUStat (const LocDPItem &dpm, const SVFGNode *node) |
remove strong updates num if the dpm goes to weak updates branch More... | |
Protected Attributes inherited from SVF::PointerAnalysis | |
bool | print_stat |
User input flags. More... | |
bool | alias_validation |
Flag for validating points-to/alias results. More... | |
u32_t | OnTheFlyIterBudgetForStat |
Flag for iteration budget for on-the-fly statistics. More... | |
SVFModule * | svfMod |
Module. More... | |
PTATY | ptaTy |
Pointer analysis Type. More... | |
PTAImplTy | ptaImplTy |
PTA implementation type. More... | |
PTAStat * | stat |
Statistics. More... | |
PTACallGraph * | callgraph |
Call graph used for pointer analysis. More... | |
CallGraphSCC * | callGraphSCC |
SCC for PTACallGraph. More... | |
ICFG * | icfg |
Interprocedural control-flow graph. More... | |
CommonCHGraph * | chgraph |
CHGraph. More... | |
Protected Attributes inherited from SVF::DDAVFSolver< NodeID, PointsTo, LocDPItem > | |
bool | outOfBudgetQuery |
Whether the current query is out of step limits. More... | |
SVFIR * | _pag |
SVFIR. More... | |
SVFG * | _svfg |
SVFG. More... | |
AndersenWaveDiff * | _ander |
Andersen's analysis. More... | |
NodeBS | candidateQueries |
candidate pointers; More... | |
PTACallGraph * | _callGraph |
PTACallGraph. More... | |
CallGraphSCC * | _callGraphSCC |
SCC for PTACallGraph. More... | |
SVFGSCC * | _svfgSCC |
SCC for SVFG. More... | |
DPTItemSet | backwardVisited |
visited map during backward traversing More... | |
DPImToCPtSetMap | dpmToTLCPtSetMap |
points-to caching map for top-level vars More... | |
DPImToCPtSetMap | dpmToADCPtSetMap |
points-to caching map for address-taken vars More... | |
LocToDPMVecMap | locToDpmSetMap |
map location to its dpms More... | |
DPMToDPMMap | dpmToloadDpmMap |
dpms at loads for may/must-alias analysis with stores More... | |
DPMToCVarMap | loadToPTCVarMap |
map a load dpm to its cvar pointed by its pointer operand More... | |
DPTItemSet | outOfBudgetDpms |
out of budget dpm set More... | |
StoreToPMSetMap | storeToDPMs |
map store to set of DPM which have been stong updated there More... | |
DDAStat * | ddaStat |
DDA stat. More... | |
SVFGBuilder | svfgBuilder |
SVFG Builder. More... | |
Static Protected Attributes inherited from SVF::PointerAnalysis | |
static SVFIR * | pag = nullptr |
SVFIR. More... | |
Constructor.
Definition at line 61 of file FlowDDA.h.
|
inlinevirtual |
|
inlineoverridevirtual |
dummy analyze method
Implements SVF::PointerAnalysis.
|
overridevirtual |
Compute points-to set for all top variable.
Compute points-to set for queries
start DDA analysis
Reimplemented from SVF::PointerAnalysis.
Definition at line 43 of file FlowDDA.cpp.
|
inlineoverridevirtual |
Finalize analysis.
Reimplemented from SVF::PointerAnalysis.
Definition at line 96 of file FlowDDA.h.
|
inlineoverridevirtual |
Override parent class functions to get/add cached points-to directly via PAGNode ID.
Reimplemented from SVF::DDAVFSolver< NodeID, PointsTo, LocDPItem >.
Override parent method.
Implements SVF::DDAVFSolver< NodeID, PointsTo, LocDPItem >.
Definition at line 109 of file FlowDDA.h.
Override parent method.
Implements SVF::DDAVFSolver< NodeID, PointsTo, LocDPItem >.
|
inlineoverridevirtual |
Handle Address SVFGNode to add proper points-to.
whether this object is set field-insensitive during pre-analysis
Implements SVF::DDAVFSolver< NodeID, PointsTo, LocDPItem >.
Definition at line 119 of file FlowDDA.h.
Handle condition for flow analysis (backward analysis)
Reimplemented from SVF::DDAVFSolver< NodeID, PointsTo, LocDPItem >.
Definition at line 102 of file FlowDDA.cpp.
void FlowDDA::handleOutOfBudgetDpm | ( | const LocDPItem & | dpm | ) |
Handle out-of-budget dpm.
Handle out-of-budget dpm
Definition at line 72 of file FlowDDA.cpp.
|
inlineoverridevirtual |
Initialization of the analysis.
Reimplemented from SVF::PointerAnalysis.
Definition at line 86 of file FlowDDA.h.
|
overridevirtual |
we exclude concrete heap here following the conditions: (1) local allocated heap and (2) not escaped to the scope outside the current function (3) not inside loop (4) not involved in recursion
Reimplemented from SVF::DDAVFSolver< NodeID, PointsTo, LocDPItem >.
Definition at line 177 of file FlowDDA.cpp.
|
overridevirtual |
processGep node
Generate field objects for structs
Implements SVF::DDAVFSolver< NodeID, PointsTo, LocDPItem >.
Definition at line 141 of file FlowDDA.cpp.
|
inlineoverridevirtual |
Return PTA name.
Reimplemented from SVF::PointerAnalysis.
bool FlowDDA::testIndCallReachability | ( | LocDPItem & | dpm, |
const SVFFunction * | callee, | ||
CallSiteID | csId | ||
) |
refine indirect call edge
Definition at line 81 of file FlowDDA.cpp.
Union pts.
Reimplemented from SVF::DDAVFSolver< NodeID, PointsTo, LocDPItem >.
Definition at line 161 of file FlowDDA.h.
|
inlineoverridevirtual |
Update call graph.
Reimplemented from SVF::DDAVFSolver< NodeID, PointsTo, LocDPItem >.
Definition at line 135 of file FlowDDA.h.