Static Value-Flow Analysis
Loading...
Searching...
No Matches
SVF::FullSparseAbstractInterpretation Class Reference

#include <SparseAbstractInterpretation.h>

Inheritance diagram for SVF::FullSparseAbstractInterpretation:
SVF::SemiSparseAbstractInterpretation SVF::AbstractInterpretation

Public Member Functions

 FullSparseAbstractInterpretation ()
 ~FullSparseAbstractInterpretation () override
void mergeFreedAddrs (AbstractState &dst, const AbstractState &src)
Public Member Functions inherited from SVF::SemiSparseAbstractInterpretation
 SemiSparseAbstractInterpretation ()
 ~SemiSparseAbstractInterpretation () override=default
Public Member Functions inherited from SVF::AbstractInterpretation
virtual void runOnModule ()
virtual ~AbstractInterpretation ()
 Destructor.
void analyse ()
 Program entry.
void analyzeFromAllProgEntries ()
 Analyze all entry points (functions without callers).
FIFOWorkList< const FunObjVar * > collectProgEntryFuns ()
 Get all entry point functions (functions without callers).
void addDetector (std::unique_ptr< AEDetector > detector)
const SVFVar * getSVFVar (NodeID varId) const
 Retrieve SVFVar given its ID; asserts if no such variable exists.
AbstractState & getAbsState (const ICFGNode *node)
bool hasAbsState (const ICFGNode *node)
void getAbsState (const Set< const ValVar * > &vars, AbstractState &result, const ICFGNode *node)
void getAbsState (const Set< const ObjVar * > &vars, AbstractState &result, const ICFGNode *node)
void getAbsState (const Set< const SVFVar * > &vars, AbstractState &result, const ICFGNode *node)
IntervalValue getGepElementIndex (const GepStmt *gep)
IntervalValue getGepByteOffset (const GepStmt *gep)
AddressValue getGepObjAddrs (const ValVar *pointer, IntervalValue offset)
virtual AbstractValue loadValue (const ValVar *pointer, const ICFGNode *node)
 Read memory through the pointer's address targets.
virtual void storeValue (const ValVar *pointer, const AbstractValue &val, const ICFGNode *node)
const SVFType * getPointeeElement (const ObjVar *var, const ICFGNode *node)
AllocationSizeBounds getAllocaInstByteSize (const AddrStmt *addr)
Map< const ICFGNode *, AbstractState > & getTrace ()
AbstractState & operator[] (const ICFGNode *node)

Protected Member Functions

void joinStates (AbstractState &dst, const AbstractState &src, const NodeBS &objs)
bool mergeStatesFromPredecessors (const ICFGNode *node) override
void joinStates (AbstractState &dst, const AbstractState &src) override
Protected Member Functions inherited from SVF::SemiSparseAbstractInterpretation
AbstractState getFullCycleHeadState (const ICFGCycleWTO *cycle) override
bool widenCycleState (const AbstractState &prev, const AbstractState &cur, const ICFGCycleWTO *cycle) override
bool narrowCycleState (const AbstractState &prev, const AbstractState &cur, const ICFGCycleWTO *cycle) override
const AbstractValue & getAbsValue (const ValVar *var, const ICFGNode *node) override
bool hasAbsValue (const ValVar *var, const ICFGNode *node) const override
 Side-effect-free existence check.
void updateAbsValue (const ValVar *var, const AbstractValue &val, const ICFGNode *node) override
void updateAbsState (const ICFGNode *node, const AbstractState &state) override
void joinStates (AbstractState &dst, const AbstractState &src) override
const ICFGNode * getICFGNode (const ValVar *var) const
virtual const AbstractValue & getAbsValue (const ObjVar *var, const ICFGNode *node)
virtual const AbstractValue & getAbsValue (const SVFVar *var, const ICFGNode *node)
virtual bool hasAbsValue (const ObjVar *var, const ICFGNode *node) const
virtual bool hasAbsValue (const SVFVar *var, const ICFGNode *node) const
virtual void updateAbsValue (const ObjVar *var, const AbstractValue &val, const ICFGNode *node)
virtual void updateAbsValue (const SVFVar *var, const AbstractValue &val, const ICFGNode *node)
Protected Member Functions inherited from SVF::AbstractInterpretation
 AbstractInterpretation ()
bool isStrongUpdate (const AddressValue &targets, const AbstractState &state) const
bool isBranchEdgeFeasible (const IntraCFGEdge *edge, AbstractState &as)
bool applyBranchRefinement (const IntraCFGEdge *edge, AbstractState &as)
bool shouldApplyNarrowing (const FunObjVar *fun)
 Check if narrowing should be applied: always for regular loops, mode-dependent for recursion.

Private Member Functions

void buildSVFG ()

Private Attributes

std::unique_ptr< SVFGBuilder > svfgBuilder
std::unique_ptr< SparseObjGraph > objRoutes

Additional Inherited Members

Public Types inherited from SVF::AbstractInterpretation
enum  AESparsity { Dense , SemiSparse , Sparse }
enum  HandleRecur { TOP , WIDEN_ONLY , WIDEN_NARROW }
enum  AEFunEntryMode { MAIN , NO_MAIN }
Static Public Member Functions inherited from SVF::AbstractInterpretation
static AbstractInterpretation & getAEInstance ()
Protected Attributes inherited from SVF::AbstractInterpretation
SVFIR * svfir {nullptr}
 Data and helpers reachable from SparseAbstractInterpretation.
AEWTO * preAnalysis {nullptr}
Map< const ICFGNode *, AbstractState > abstractTrace
 per-node trace; owned here

Detailed Description

Full-sparse Obj values follow prebuilt packed-object routes. ValVars retain semi-sparse def-site access; freed addresses follow feasible ICFG edges.

Definition at line 79 of file SparseAbstractInterpretation.h.

Constructor & Destructor Documentation

◆ FullSparseAbstractInterpretation()

SVF::FullSparseAbstractInterpretation::FullSparseAbstractInterpretation ( )
inline

◆ ~FullSparseAbstractInterpretation()

FullSparseAbstractInterpretation::~FullSparseAbstractInterpretation ( )
overridedefault

Member Function Documentation

◆ buildSVFG()

void FullSparseAbstractInterpretation::buildSVFG ( )
private

Definition at line 42 of file SparseAbstractInterpretation.cpp.

43{
44 svfgBuilder = std::make_unique<SVFGBuilder>(true);
45 svfgBuilder->buildFullSVFG(preAnalysis->getPointerAnalysis());
46 objRoutes = std::make_unique<SparseObjGraph>(
47 *svfgBuilder->getSVFG(), *svfir->getICFG(),
48 *preAnalysis->getPointerAnalysis(), *svfir);
49}
SVFIR * svfir
Data and helpers reachable from SparseAbstractInterpretation.

◆ joinStates() [1/2]

void SemiSparseAbstractInterpretation::joinStates ( AbstractState & dst,
const AbstractState & src )
overrideprotectedvirtual

Join src into dst with sparsity-aware semantics. Dense merges everything; semi-sparse skips ValVars.

Reimplemented from SVF::AbstractInterpretation.

Definition at line 72 of file SparseAbstractInterpretation.cpp.

203{
204 // ValVars live at def-sites in semi-sparse mode; they don't flow
205 // through state merges. Iterate src's ObjVar (_addrToAbsVal) entries
206 // directly and join into dst, leaving dst's ValVar map untouched.
207 // _freedAddrs (used by the null-deref detector) also rides along
208 // ICFG edges — there is no SVFG-level encoding of free events.
209 for (const auto& [id, val] : src.getLocToVal())
210 {
212 if (dst.getLocToVal().count(id))
213 dst.load(addr).join_with(val);
214 else
215 dst.store(addr, val);
216 }
217 for (NodeID a : src.getFreedAddrs())
218 dst.addToFreedAddrs(a);
219}
cJSON * a
Definition cJSON.cpp:2560
const AddrToAbsValMap & getLocToVal() const
get loc2val map
void store(u32_t addr, const AbstractValue &val)
const Set< NodeID > & getFreedAddrs() const
virtual AbstractValue & load(u32_t addr)
static u32_t getVirtualMemAddress(u32_t idx)
The physical address starts with 0x7f...... + idx.
void addToFreedAddrs(NodeID addr)
void join_with(const AbstractValue &other)
u32_t NodeID
Definition GeneralType.h:76
unsigned u32_t
Definition GeneralType.h:67

◆ joinStates() [2/2]

void FullSparseAbstractInterpretation::joinStates ( AbstractState & dst,
const AbstractState & src,
const NodeBS & objs )
protected

JOIN only the selected Obj IDs from src into dst; missing values contribute nothing. The caller selects base/sub Objs and handles path constraints and strong/weak updates. ValVars and freed addresses are not copied here. Memory lookups use AbstractState's existing address resolution, including its freed-address handling.

Definition at line 58 of file SparseAbstractInterpretation.cpp.

60{
61 for (NodeID obj : objs)
62 {
64 const auto value = src.getLocToVal().find(src.getIDFromAddr(addr));
65 if (value != src.getLocToVal().end())
66 {
67 if (dst.getLocToVal().count(dst.getIDFromAddr(addr)))
68 dst.load(addr).join_with(value->second);
69 else
70 dst.store(addr, value->second);
71 }
72 }
73}
u32_t getIDFromAddr(u32_t addr) const
Return the internal index if addr is an address otherwise return the value of idx.

◆ mergeFreedAddrs()

void FullSparseAbstractInterpretation::mergeFreedAddrs ( AbstractState & dst,
const AbstractState & src )

Merge only freed addresses from a feasible ICFG predecessor. Obj values are collected separately through sparse object routes.

Definition at line 51 of file SparseAbstractInterpretation.cpp.

53{
54 for (NodeID addr : src.getFreedAddrs())
55 dst.addToFreedAddrs(addr);
56}

◆ mergeStatesFromPredecessors()

bool FullSparseAbstractInterpretation::mergeStatesFromPredecessors ( const ICFGNode * node)
overrideprotectedvirtual

Read incoming route sources, refine branch inputs, and JOIN their selected Obj values into this ICFG node's state.

Reimplemented from SVF::AbstractInterpretation.

Definition at line 75 of file SparseAbstractInterpretation.cpp.

77{
78 const auto& graphEdges = objRoutes->getInputs(node);
79 AbstractState previous;
80 bool hasPrevious = false;
81 for (const SparseObjGraph::Edge* edge : graphEdges)
82 {
83 if (edge->getSrcNode()->getICFGNode() == node && hasAbsState(node))
84 {
85 previous = getAbsState(node);
86 hasPrevious = true;
87 break;
88 }
89 }
90
91 // The ICFG merge determines reachability and propagates freed addresses.
92 const bool reachable = AbstractInterpretation::mergeStatesFromPredecessors(node);
93 if (reachable)
94 {
95 AbstractState merged = getAbsState(node);
96 for (const SparseObjGraph::Edge* edge : graphEdges)
97 {
98 const SparseObjGraph::Node* sourceNode = edge->getSrcNode();
99 const ICFGNode* source = sourceNode->getICFGNode();
100 const AbstractState* sourceState = source == node
101 ? (hasPrevious ? &previous : nullptr)
102 : (hasAbsState(source)
103 ? &getAbsState(source) : nullptr);
104 if (!sourceState)
105 continue;
106
107 const AbstractState* input = sourceState;
108 AbstractState refined;
109 if (sourceNode->branch)
110 {
111 refined = *sourceState;
112 if (!isBranchEdgeFeasible(sourceNode->branch, refined) ||
113 !applyBranchRefinement(sourceNode->branch, refined))
114 continue;
115 input = &refined;
116 }
117 joinStates(merged, *input, svfir->getAllFieldsObjVars(
118 svfir->getBaseObject(sourceNode->base)));
119 }
120 updateAbsState(node, merged);
121 }
122 return reachable;
123}
AbstractState & getAbsState(const ICFGNode *node)
virtual bool mergeStatesFromPredecessors(const ICFGNode *node)
bool hasAbsState(const ICFGNode *node)
void joinStates(AbstractState &dst, const AbstractState &src, const NodeBS &objs)
void updateAbsState(const ICFGNode *node, const AbstractState &state) override
const IntraCFGEdge * branch
const ICFGNode * getICFGNode() const

Member Data Documentation

◆ objRoutes

std::unique_ptr<SparseObjGraph> SVF::FullSparseAbstractInterpretation::objRoutes
private

Definition at line 111 of file SparseAbstractInterpretation.h.

◆ svfgBuilder

std::unique_ptr<SVFGBuilder> SVF::FullSparseAbstractInterpretation::svfgBuilder
private

Definition at line 110 of file SparseAbstractInterpretation.h.


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