Static Value-Flow Analysis
|
#include <PointerAnalysis.h>
Public Types | |
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. More... | |
typedef SVFIR::CallSiteToFunPtrMap | CallSiteToFunPtrMap |
typedef Set< const SVFFunction * > | FunctionSet |
typedef OrderedMap< const CallICFGNode *, FunctionSet > | CallEdgeMap |
typedef SCCDetection< PTACallGraph * > | CallGraphSCC |
typedef Set< const SVFGlobalValue * > | VTableSet |
typedef Set< const SVFFunction * > | VFunSet |
Public Member Functions | |
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... | |
virtual const std::string | PTAName () const |
Return PTA name. 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... | |
Static Public Attributes | |
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 Attributes | |
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... | |
Static Protected Attributes | |
static SVFIR * | pag = nullptr |
SVFIR. More... | |
Private Member Functions | |
void | destroy () |
Release the memory. 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... | |
virtual void | initialize () |
Initialization of a pointer analysis, including building symbol table and SVFIR etc. More... | |
virtual void | finalize () |
Finalization of a pointer analysis, including checking alias correctness. More... | |
virtual void | analyze ()=0 |
Start Analysis here (main part of pointer analysis). It needs to be implemented in child class. More... | |
virtual void | computeDDAPts (NodeID) |
Compute points-to results on-demand, overridden by derived classes. More... | |
virtual AliasResult | alias (const SVFValue *V1, const SVFValue *V2)=0 |
Interface exposed to users of our pointer analysis, given Value infos. More... | |
virtual AliasResult | alias (NodeID node1, NodeID node2)=0 |
Interface exposed to users of our pointer analysis, given PAGNodeID. More... | |
virtual const PointsTo & | getPts (NodeID ptr)=0 |
Get points-to targets of a pointer. It needs to be implemented in child class. More... | |
virtual const NodeSet & | getRevPts (NodeID nodeId)=0 |
void | printIndCSTargets (const CallICFGNode *cs, const FunctionSet &targets) |
Print targets of a function pointer. More... | |
virtual void | dumpTopLevelPtsTo () |
virtual void | dumpAllPts () |
virtual void | dumpCPts () |
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 |
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... | |
Definition at line 57 of file PointerAnalysis.h.
typedef OrderedMap<const CallICFGNode*, FunctionSet> SVF::PointerAnalysis::CallEdgeMap |
Definition at line 105 of file PointerAnalysis.h.
Definition at line 106 of file PointerAnalysis.h.
typedef Set<const CallICFGNode*> SVF::PointerAnalysis::CallSiteSet |
Indirect call edges type, map a callsite to a set of callees.
Definition at line 102 of file PointerAnalysis.h.
Definition at line 103 of file PointerAnalysis.h.
typedef Set<const SVFFunction*> SVF::PointerAnalysis::FunctionSet |
Definition at line 104 of file PointerAnalysis.h.
typedef Set<const SVFFunction*> SVF::PointerAnalysis::VFunSet |
Definition at line 108 of file PointerAnalysis.h.
typedef Set<const SVFGlobalValue*> SVF::PointerAnalysis::VTableSet |
Definition at line 107 of file PointerAnalysis.h.
Implementation type: BVDataPTAImpl or CondPTAImpl.
Enumerator | |
---|---|
BaseImpl | Represents PointerAnalaysis. |
BVDataImpl | Represents BVDataPTAImpl. |
CondImpl | Represents CondPTAImpl. |
Definition at line 93 of file PointerAnalysis.h.
Pointer analysis type list.
Enumerator | |
---|---|
Andersen_BASE | Base Andersen PTA. |
Andersen_WPA | Andersen PTA. |
AndersenSCD_WPA | Selective cycle detection andersen-style WPA. |
AndersenSFR_WPA | Stride-based field representation. |
AndersenWaveDiff_WPA | Diff wave propagation andersen-style WPA. |
Steensgaard_WPA | Steensgaard PTA. |
CSCallString_WPA | Call string based context sensitive WPA. |
CSSummary_WPA | Summary based context sensitive WPA. |
FSDATAFLOW_WPA | Traditional Dataflow-based flow sensitive WPA. |
FSSPARSE_WPA | Sparse flow sensitive WPA. |
VFS_WPA | Versioned sparse flow-sensitive WPA. |
FSCS_WPA | Flow-, context- sensitive WPA. |
CFLFICI_WPA | Flow-, context-, insensitive CFL-reachability-based analysis. |
CFLFSCI_WPA | Flow-insensitive, context-sensitive CFL-reachability-based analysis. |
CFLFSCS_WPA | Flow-, context-, CFL-reachability-based analysis. |
TypeCPP_WPA | Type-based analysis for C++. |
FieldS_DDA | Field sensitive DDA. |
FlowS_DDA | Flow sensitive DDA. |
PathS_DDA | Guarded value-flow DDA. |
Cxt_DDA | context sensitive DDA |
Default_PTA | default pta without any analysis |
Definition at line 62 of file PointerAnalysis.h.
PointerAnalysis::PointerAnalysis | ( | SVFIR * | p, |
PTATY | ty = Default_PTA , |
||
bool | alias_check = true |
||
) |
Constructor.
Constructor
Definition at line 68 of file PointerAnalysis.cpp.
|
virtual |
|
pure virtual |
Interface exposed to users of our pointer analysis, given Value infos.
Implemented in SVF::BVDataPTAImpl, SVF::CondPTAImpl< Cond >, SVF::CondPTAImpl< ContextCond >, and SVF::CFLAlias.
|
pure virtual |
Interface exposed to users of our pointer analysis, given PAGNodeID.
Implemented in SVF::BVDataPTAImpl, SVF::CondPTAImpl< Cond >, SVF::CondPTAImpl< ContextCond >, and SVF::CFLAlias.
|
pure virtual |
Start Analysis here (main part of pointer analysis). It needs to be implemented in child class.
Implemented in SVF::TypeAnalysis, SVF::FlowSensitive, SVF::AndersenBase, SVF::FlowDDA, SVF::ContextDDA, and SVF::CFLBase.
|
inline |
PTACallGraph SCC related methods.
PTACallGraph SCC detection
Definition at line 388 of file PointerAnalysis.h.
|
inlinevirtual |
Compute points-to results on-demand, overridden by derived classes.
Reimplemented in SVF::FlowDDA, and SVF::ContextDDA.
Definition at line 233 of file PointerAnalysis.h.
void PointerAnalysis::connectVCallToVFns | ( | const CallICFGNode * | cs, |
const VFunSet & | vfns, | ||
CallEdgeMap & | newEdges | ||
) |
Definition at line 462 of file PointerAnalysis.cpp.
|
inline |
Determine whether a points-to contains a black hole or constant node.
Definition at line 289 of file PointerAnalysis.h.
|
inline |
Definition at line 293 of file PointerAnalysis.h.
|
private |
|
inline |
Whether print statistics.
Definition at line 361 of file PointerAnalysis.h.
|
inlinevirtual |
void PointerAnalysis::dumpAllTypes | ( | ) |
Definition at line 232 of file PointerAnalysis.cpp.
|
inlinevirtual |
Reimplemented in SVF::BVDataPTAImpl, SVF::CondPTAImpl< Cond >, and SVF::CondPTAImpl< ContextCond >.
Definition at line 256 of file PointerAnalysis.h.
Dump points-to of top-level pointers (ValVar)
print the points-to set of node which has the maximum pts size.
Definition at line 253 of file PointerAnalysis.cpp.
void PointerAnalysis::dumpStat | ( | ) |
|
inlinevirtual |
Reimplemented in SVF::BVDataPTAImpl, SVF::Andersen, SVF::CondPTAImpl< Cond >, and SVF::CondPTAImpl< ContextCond >.
Definition at line 254 of file PointerAnalysis.h.
|
virtual |
Finalization of a pointer analysis, including checking alias correctness.
Finalize the analysis after solving Given the alias results, verify whether it is correct or not using alias check functions
Print statistics
Dump results
Reimplemented in SVF::VersionedFlowSensitive, SVF::TypeAnalysis, SVF::FlowSensitive, SVF::AndersenBase, SVF::BVDataPTAImpl, SVF::FlowDDA, SVF::ContextDDA, SVF::Andersen, SVF::CondPTAImpl< Cond >, SVF::CondPTAImpl< ContextCond >, SVF::CFLVF, SVF::CFLBase, and SVF::CFLAlias.
Definition at line 176 of file PointerAnalysis.cpp.
Definition at line 338 of file PointerAnalysis.h.
|
inline |
Get all Valid Pointers for resolution.
Definition at line 215 of file PointerAnalysis.h.
|
inline |
Type of pointer analysis.
Definition at line 185 of file PointerAnalysis.h.
Definition at line 326 of file PointerAnalysis.h.
|
inline |
Return call graph.
Definition at line 171 of file PointerAnalysis.h.
|
inline |
Return call graph SCC.
Definition at line 176 of file PointerAnalysis.h.
Get SCC rep node of a SVFG node.
Definition at line 396 of file PointerAnalysis.h.
|
inline |
Definition at line 330 of file PointerAnalysis.h.
|
inlineprotected |
Definition at line 334 of file PointerAnalysis.h.
|
inline |
|
inline |
Return implementation type of the pointer analysis.
Definition at line 191 of file PointerAnalysis.h.
|
inline |
Get callees from an indirect callsite.
Definition at line 368 of file PointerAnalysis.h.
|
inline |
Definition at line 376 of file PointerAnalysis.h.
|
inlineprotected |
Return all indirect callsites.
Definition at line 264 of file PointerAnalysis.h.
|
inline |
|
inline |
Return number of resolved indirect call edges.
Definition at line 166 of file PointerAnalysis.h.
|
inline |
Get points-to targets of a pointer. It needs to be implemented in child class.
Implemented in SVF::CondPTAImpl< Cond >, SVF::CondPTAImpl< ContextCond >, SVF::Steensgaard, SVF::BVDataPTAImpl, and SVF::Andersen.
Given an object, get all the nodes having whose pointsto contains the object. Similar to getPts, this also needs to be implemented in child classes.
Implemented in SVF::CondPTAImpl< Cond >, SVF::CondPTAImpl< ContextCond >, SVF::BVDataPTAImpl, and SVF::CFLAlias.
|
inline |
void PointerAnalysis::getVFnsFromCHA | ( | const CallICFGNode * | cs, |
VFunSet & | vfns | ||
) |
Definition at line 427 of file PointerAnalysis.cpp.
void PointerAnalysis::getVFnsFromPts | ( | const CallICFGNode * | cs, |
const PointsTo & | target, | ||
VFunSet & | vfns | ||
) |
Definition at line 436 of file PointerAnalysis.cpp.
|
inline |
Definition at line 372 of file PointerAnalysis.h.
|
virtual |
Initialization of a pointer analysis, including building symbol table and SVFIR etc.
Initialization of pointer analysis
initialise pta call graph for every pointer analysis instance
Reimplemented in SVF::VersionedFlowSensitive, SVF::TypeAnalysis, SVF::FlowSensitive, SVF::AndersenBase, SVF::FlowDDA, SVF::ContextDDA, SVF::AndersenSFR, SVF::AndersenWaveDiff, SVF::Andersen, SVF::CFLVF, and SVF::CFLAlias.
Definition at line 104 of file PointerAnalysis.cpp.
|
inline |
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.
Definition at line 401 of file PointerAnalysis.h.
|
inline |
Definition at line 312 of file PointerAnalysis.h.
|
inlinevirtual |
Definition at line 297 of file PointerAnalysis.h.
|
inline |
Definition at line 347 of file PointerAnalysis.h.
|
inline |
For field-sensitivity
Definition at line 322 of file PointerAnalysis.h.
|
inline |
Whether this object is heap or array.
Definition at line 305 of file PointerAnalysis.h.
|
inline |
Definition at line 407 of file PointerAnalysis.h.
bool PointerAnalysis::isLocalVarInRecursiveFun | ( | NodeID | id | ) | const |
Whether a local variable is in function recursions.
Return TRUE if this node is a local variable of recursive function.
Definition at line 133 of file PointerAnalysis.cpp.
void PointerAnalysis::printIndCSTargets | ( | ) |
Print all indirect callsites
Definition at line 346 of file PointerAnalysis.cpp.
void PointerAnalysis::printIndCSTargets | ( | const CallICFGNode * | cs, |
const FunctionSet & | targets | ||
) |
Print targets of a function pointer.
Print indirect call targets at an indirect callsite
Definition at line 317 of file PointerAnalysis.cpp.
|
inline |
Whether print statistics.
Definition at line 355 of file PointerAnalysis.h.
|
inlinevirtual |
Return PTA name.
Reimplemented in SVF::VersionedFlowSensitive, SVF::FlowSensitive, SVF::FlowDDA, SVF::ContextDDA, and SVF::Andersen.
Definition at line 416 of file PointerAnalysis.h.
|
protected |
Reset all object node as field-sensitive.
Reset field sensitivity
Definition at line 150 of file PointerAnalysis.cpp.
|
virtual |
Resolve cpp indirect call edges.
Definition at line 484 of file PointerAnalysis.cpp.
|
virtual |
Resolve indirect call edges.
Resolve indirect calls
discover indirect pointer target
Definition at line 381 of file PointerAnalysis.cpp.
|
inline |
Definition at line 342 of file PointerAnalysis.h.
|
protectedvirtual |
Pointer analysis validator
Definition at line 565 of file PointerAnalysis.cpp.
|
protectedvirtual |
Find the alias check functions annotated in the C files check whether the alias analysis results consistent with the alias check function itself
Definition at line 500 of file PointerAnalysis.cpp.
|
protectedvirtual |
Alias check functions to verify correctness of pointer analysis.
Validate test cases
Definition at line 214 of file PointerAnalysis.cpp.
|
protected |
Flag for validating points-to/alias results.
Definition at line 135 of file PointerAnalysis.h.
|
static |
Definition at line 119 of file PointerAnalysis.h.
|
static |
Definition at line 120 of file PointerAnalysis.h.
|
static |
Definition at line 121 of file PointerAnalysis.h.
|
static |
Definition at line 122 of file PointerAnalysis.h.
|
static |
Definition at line 111 of file PointerAnalysis.h.
|
static |
Definition at line 112 of file PointerAnalysis.h.
|
static |
Definition at line 117 of file PointerAnalysis.h.
|
static |
Definition at line 118 of file PointerAnalysis.h.
|
static |
Definition at line 113 of file PointerAnalysis.h.
|
static |
Definition at line 114 of file PointerAnalysis.h.
|
static |
Definition at line 115 of file PointerAnalysis.h.
|
static |
Definition at line 116 of file PointerAnalysis.h.
|
protected |
Call graph used for pointer analysis.
Definition at line 151 of file PointerAnalysis.h.
|
protected |
SCC for PTACallGraph.
Definition at line 153 of file PointerAnalysis.h.
|
protected |
Definition at line 157 of file PointerAnalysis.h.
|
protected |
Interprocedural control-flow graph.
Definition at line 155 of file PointerAnalysis.h.
|
protected |
Flag for iteration budget for on-the-fly statistics.
Definition at line 137 of file PointerAnalysis.h.
|
staticprotected |
Definition at line 141 of file PointerAnalysis.h.
|
protected |
User input flags.
Flag for printing the statistic results
Definition at line 133 of file PointerAnalysis.h.
|
protected |
PTA implementation type.
Definition at line 147 of file PointerAnalysis.h.
|
protected |
Pointer analysis Type.
Definition at line 145 of file PointerAnalysis.h.
|
protected |
Statistics.
Definition at line 149 of file PointerAnalysis.h.
|
protected |
Module.
Definition at line 143 of file PointerAnalysis.h.