SVF::AbstractInterpretation Class Reference

#include <AbstractInterpretation.h>

Inheritance diagram for SVF::AbstractInterpretation:

Public Types
enum	AESparsity { Dense , SemiSparse , Sparse }
enum	HandleRecur { TOP , WIDEN_ONLY , WIDEN_NARROW }
enum	AEFunEntryMode { MAIN , NO_MAIN }

Public Member Functions
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.
virtual const AbstractValue &	getAbsValue (const ValVar *var, const ICFGNode *node)
virtual const AbstractValue &	getAbsValue (const ObjVar *var, const ICFGNode *node)
virtual const AbstractValue &	getAbsValue (const SVFVar *var, const ICFGNode *node)
virtual bool	hasAbsValue (const ValVar *var, const ICFGNode *node) const
	Side-effect-free existence check.
virtual bool	hasAbsValue (const ObjVar *var, const ICFGNode *node) const
virtual bool	hasAbsValue (const SVFVar *var, const ICFGNode *node) const
virtual void	updateAbsValue (const ValVar *var, const AbstractValue &val, const ICFGNode *node)
virtual void	updateAbsValue (const ObjVar *var, const AbstractValue &val, const ICFGNode *node)
virtual void	updateAbsValue (const SVFVar *var, const AbstractValue &val, const ICFGNode *node)
AbstractState &	getAbsState (const ICFGNode *node)
virtual void	updateAbsState (const ICFGNode *node, const AbstractState &state)
virtual void	joinStates (AbstractState &dst, const AbstractState &src)
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)
	Virtual so full-sparse can layer the GepObj overlay on top.
virtual void	storeValue (const ValVar *pointer, const AbstractValue &val, const ICFGNode *node)
const SVFType *	getPointeeElement (const ObjVar *var, const ICFGNode *node)
u32_t	getAllocaInstByteSize (const AddrStmt *addr)
Map< const ICFGNode *, AbstractState > &	getTrace ()
AbstractState &	operator[] (const ICFGNode *node)

Static Public Member Functions
static AbstractInterpretation &	getAEInstance ()

Protected Member Functions
	AbstractInterpretation ()
virtual AbstractState	getFullCycleHeadState (const ICFGCycleWTO *cycle)
virtual bool	widenCycleState (const AbstractState &prev, const AbstractState &cur, const ICFGCycleWTO *cycle)
virtual bool	narrowCycleState (const AbstractState &prev, const AbstractState &cur, const ICFGCycleWTO *cycle)
virtual bool	mergeStatesFromPredecessors (const ICFGNode *node)
bool	isBranchEdgeFeasible (const IntraCFGEdge *edge, AbstractState &as)
void	collectBranchRefinement (const IntraCFGEdge *edge, AbstractState &as)
virtual void	recordBranchRefinement (NodeID objId, const IntervalValue &narrowed, AbstractState &as, const ICFGNode *loadIcfg, const ICFGNode *succ)
bool	shouldApplyNarrowing (const FunObjVar *fun)
	Check if narrowing should be applied: always for regular loops, mode-dependent for recursion.

Protected Attributes
SVFIR *	svfir {nullptr}
	Data and helpers reachable from SparseAbstractInterpretation.
AEWTO *	preAnalysis {nullptr}
Map< const ICFGNode *, AbstractState >	abstractTrace
	per-node trace; owned here

Private Member Functions
virtual void	handleGlobalNode ()
virtual void	handleCallSite (const ICFGNode *node)
	Handle a call site node: dispatch to ext-call, direct-call, or indirect-call handling.
virtual void	handleLoopOrRecursion (const ICFGCycleWTO *cycle, const CallICFGNode *caller)
	Handle a WTO cycle (loop or recursive function) using widening/narrowing iteration.
void	handleFunction (const ICFGNode *funEntry, const CallICFGNode *caller)
	Handle a function body via worklist-driven WTO traversal starting from funEntry.
bool	handleICFGNode (const ICFGNode *node)
	Handle an ICFG node: execute statements; return true if state changed.
virtual void	handleSVFStatement (const SVFStmt *stmt)
	Dispatch an SVF statement (Addr/Binary/Cmp/Load/Store/Copy/Gep/Select/Phi/Call/Ret) to its handler.
bool	isCmpBranchEdgeFeasible (const IntraCFGEdge *edge, AbstractState &as)
	Returns true if the cmp-conditional branch is feasible.
bool	isSwitchBranchEdgeFeasible (const IntraCFGEdge *edge, AbstractState &as)
	Returns true if the switch branch is feasible.
void	updateStateOnAddr (const AddrStmt *addr)
void	updateStateOnBinary (const BinaryOPStmt *binary)
IntervalValue	evaluatePointerCmp (u32_t predicate, const AddressValue &lhs, const AddressValue &rhs) const
IntervalValue	evaluateIntervalCmp (u32_t predicate, const IntervalValue &lhs, const IntervalValue &rhs) const
void	updateStateOnCmp (const CmpStmt *cmp)
void	updateStateOnLoad (const LoadStmt *load)
void	updateStateOnStore (const StoreStmt *store)
void	updateStateOnCopy (const CopyStmt *copy)
void	updateStateOnCall (const CallPE *callPE)
void	updateStateOnRet (const RetPE *retPE)
void	updateStateOnGep (const GepStmt *gep)
void	updateStateOnSelect (const SelectStmt *select)
void	updateStateOnPhi (const PhiStmt *phi)
AbsExtAPI *	getUtils ()
virtual bool	isExtCall (const CallICFGNode *callNode)
virtual void	handleExtCall (const CallICFGNode *callNode)
virtual bool	isRecursiveFun (const FunObjVar *fun)
	Check if a function is recursive (part of a call graph SCC)
virtual void	skipRecursionWithTop (const CallICFGNode *callNode)
virtual bool	isRecursiveCallSite (const CallICFGNode *callNode, const FunObjVar *)
	Check if caller and callee are in the same CallGraph SCC (i.e. a recursive callsite)
virtual void	handleFunCall (const CallICFGNode *callNode)
bool	skipRecursiveCall (const CallICFGNode *callNode)
	Skip recursive callsites (within SCC); entry calls from outside SCC are not skipped.
const FunObjVar *	getCallee (const CallICFGNode *callNode)
	Get callee function: directly for direct calls, via pointer analysis for indirect calls.

Private Attributes
AEAPI *	api {nullptr}
	Execution State, used to store the Interval Value of every SVF variable.
ICFG *	icfg
CallGraph *	callGraph
AEStat *	stat
Map< std::string, std::function< void(const CallICFGNode *)> >	func_map
Set< const ICFGNode * >	allAnalyzedNodes
std::string	moduleName
std::vector< std::unique_ptr< AEDetector > >	detectors
AbsExtAPI *	utils

Friends
class	AEStat
class	AEAPI
class	BufOverflowDetector
class	NullptrDerefDetector

Detailed Description

AbstractInterpretation is same as Abstract Execution.

Owns the per-node abstract trace and exposes the read/write API directly (no separate state-manager indirection). Sparse modes are implemented as subclasses that override the virtual hooks below (cycle helpers, ValVar accessors, joinStates, def/use queries).

Definition at line 60 of file AbstractInterpretation.h.

Member Enumeration Documentation

AEFunEntryMode

enum SVF::AbstractInterpretation::AEFunEntryMode

Enumerator
MAIN
NO_MAIN

Definition at line 97 of file AbstractInterpretation.h.

    {
        MAIN,
        NO_MAIN
    };

AESparsity

enum SVF::AbstractInterpretation::AESparsity

Enumerator
Dense
SemiSparse
Sparse

Definition at line 83 of file AbstractInterpretation.h.

    {
        Dense,
        SemiSparse,
        Sparse
    };

HandleRecur

enum SVF::AbstractInterpretation::HandleRecur

Enumerator
TOP
WIDEN_ONLY
WIDEN_NARROW

Definition at line 90 of file AbstractInterpretation.h.

    {
        TOP,
        WIDEN_ONLY,
        WIDEN_NARROW
    };

Constructor & Destructor Documentation

~AbstractInterpretation()

AbstractInterpretation::~AbstractInterpretation ( )

virtual

Destructor.

Definition at line 112 of file AbstractInterpretation.cpp.

{
    delete utils;
    delete stat;
    delete preAnalysis;
}

AbstractInterpretation()

AbstractInterpretation::AbstractInterpretation ( )

protected

Factory-only construction. External callers must use getAEInstance(); SparseAbstractInterpretation reaches this via its own ctor.

Definition at line 61 of file AbstractInterpretation.cpp.

{
    stat = new AEStat(this);
    // Run Andersen's pointer analysis and build WTO
    svfir = PAG::getPAG();
    icfg = svfir->getICFG();
    preAnalysis = new AEWTO(svfir, icfg);
    callGraph = preAnalysis->getCallGraph();
    icfg->updateCallGraph(callGraph);
    preAnalysis->initWTO();
}

Member Function Documentation

addDetector()

void SVF::AbstractInterpretation::addDetector ( std::unique_ptr< AEDetector >  detector )

inline

Definition at line 124 of file AbstractInterpretation.h.

    {
        detectors.push_back(std::move(detector));
    }

analyse()

void AbstractInterpretation::analyse

(

)

Program entry.

Program entry - entry policy is selected by -ae-fun-entry.

Definition at line 200 of file AbstractInterpretation.cpp.

{
    analyzeFromAllProgEntries();
}

analyzeFromAllProgEntries()

void AbstractInterpretation::analyzeFromAllProgEntries

(

)

Analyze all entry points (functions without callers)

Analyze the entry functions selected by collectProgEntryFuns(). Abstract state is shared across entry points so that functions analyzed from earlier entries are not re-analyzed from scratch.

Definition at line 208 of file AbstractInterpretation.cpp.

{
    // Collect all entry point functions
    FIFOWorkList<const FunObjVar*> entryFunctions = collectProgEntryFuns();
 
    if (entryFunctions.empty())
    {
        assert(false && "No entry functions found for analysis");
        return;
    }
    // handle Global ICFGNode of SVFModule
    handleGlobalNode();
    const ICFGNode* globalNode = icfg->getGlobalICFGNode();
    while (!entryFunctions.empty())
    {
        const FunObjVar* entryFun = entryFunctions.pop();
        const ICFGNode* funEntry = icfg->getFunEntryICFGNode(entryFun);
        updateAbsState(funEntry, getAbsState(globalNode));
        handleFunction(funEntry, nullptr);
    }
}

collectBranchRefinement()

void AbstractInterpretation::collectBranchRefinement ( const IntraCFGEdge *  edge, AbstractState &  as  )

protected

Collect branch-induced interval refinement after a feasible edge has been selected for normal CFG-state merging.

Definition at line 523 of file AbstractInterpretation.cpp.

{
    const SVFVar* cond = edge->getCondition();
    const ICFGNode* pred = edge->getSrcNode();
    const ICFGNode* succNode = edge->getDstNode();
    s64_t succ = edge->getSuccessorCondValue();
 
    assert(!cond->getInEdges().empty() &&
           "branch condition has no defining edge?");
    const SVFStmt* condDef = *cond->getInEdges().begin();
 
    if (const CmpStmt* cmpStmt = SVFUtil::dyn_cast<CmpStmt>(condDef))
    {
        s32_t predicate = cmpStmt->getPredicate();
 
        if (cmpStmt->getOpVarID(0) == IRGraph::NullPtr ||
                cmpStmt->getOpVarID(1) == IRGraph::NullPtr)
        {
            // p == NULL / p != NULL: no interval obj to refine.
        }
        else
        {
            AbstractValue opVal[2] = {getAbsValue(cmpStmt->getOpVar(0), pred),
                                      getAbsValue(cmpStmt->getOpVar(1), pred)
                                     };
 
            const bool hasIntervalCmp =
                opVal[0].isInterval() && opVal[1].isInterval();
            if (!hasIntervalCmp && (opVal[0].isAddr() || opVal[1].isAddr()))
            {
                // Pointer-valued cmp: branch feasibility only.
            }
            else
            {
                for (int i = 0; i < 2; i++)
                {
                    const int other = 1 - i;
                    const LoadStmt* load =
                        findBackingLoad(cmpStmt->getOpVar(i));
 
                    if (opVal[i].getInterval().is_numeral())
                    {
                        // Example: in x < 5, operand 5 is not refined.
                    }
                    else if (!opVal[other].getInterval().is_numeral())
                    {
                        // Example: x < y, neither side has a fixed bound.
                    }
                    else if (!load)
                    {
                        // Example: cmp uses a computed temporary, not load p.
                    }
                    else
                    {
                        IntervalValue narrowed = computeCmpConstraint(
                                                     predicate, succ, i == 0, opVal[i].getInterval(),
                                                     opVal[other].getInterval());
 
                        if (narrowed.isTop())
                        {
                            // != and unsupported predicates reach here.
                        }
                        else
                        {
                            const ICFGNode* loadIcfg = load->getICFGNode();
                            const AbstractValue& ptrVal =
                                getAbsValue(load->getRHSVar(), loadIcfg);
                            if (!ptrVal.isAddr())
                            {
                                // Cannot map load p back to concrete ObjVars.
                            }
                            else
                            {
                                for (const auto& addr : ptrVal.getAddrs())
                                {
                                    NodeID objId = as.getIDFromAddr(addr);
                                    recordBranchRefinement(objId, narrowed, as,
                                                           loadIcfg, succNode);
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    else
    {
        const SVFVar* var = cond;
 
        AbstractValue condVal = getAbsValue(var, pred);
        IntervalValue switch_cond = condVal.getInterval();
        switch_cond.meet_with(IntervalValue(succ, succ));
        if (switch_cond.isBottom())
        {
            // This case label is not reachable from cond's interval.
        }
        else
        {
            as[var->getId()] = AbstractValue(switch_cond);
 
            FIFOWorkList<const SVFStmt*> stmtList;
            for (SVFStmt* stmt : var->getInEdges())
                stmtList.push(stmt);
            while (!stmtList.empty())
            {
                const SVFStmt* stmt = stmtList.pop();
                const LoadStmt* load = SVFUtil::dyn_cast<LoadStmt>(stmt);
                if (!load)
                {
                    // Skip non-load definitions of the switch condition.
                }
                else
                {
                    const ICFGNode* loadIcfg = load->getICFGNode();
                    const AbstractValue& ptrVal =
                        getAbsValue(load->getRHSVar(), loadIcfg);
                    if (!ptrVal.isAddr())
                    {
                        // Cannot map load p back to concrete ObjVars.
                    }
                    else
                    {
                        for (const auto& addr : ptrVal.getAddrs())
                        {
                            NodeID objId = as.getIDFromAddr(addr);
                            recordBranchRefinement(objId, switch_cond, as,
                                                   loadIcfg, succNode);
                        }
                    }
                }
            }
        }
    }
}

collectProgEntryFuns()

FIFOWorkList< const FunObjVar * > AbstractInterpretation::collectProgEntryFuns

(

)

Get all entry point functions (functions without callers)

Collect entry point functions for analysis. In main mode, entry is main/svf.main. In no-main mode, entries are SCCs with no external caller in the Andersen-resolved CallGraph.

Definition at line 122 of file AbstractInterpretation.cpp.

{
    FIFOWorkList<const FunObjVar*> entryFunctions;
    const bool mainEntry = Options::AEFunEntry() == AEFunEntryMode::MAIN;
    Set<NodeID> visitedEntrySCCs;
    auto* callGraphSCC = preAnalysis->getCallGraphSCC();
 
    for (auto it = callGraph->begin(); it != callGraph->end(); ++it)
    {
        const CallGraphNode* cgNode = it->second;
        const FunObjVar* fun = cgNode->getFunction();
 
        // Skip declarations
        if (fun->isDeclaration())
            continue;
 
        if (mainEntry)
        {
            if (SVFUtil::isProgEntryFunction(fun))
            {
                entryFunctions.push(fun);
                break;
            }
        }
        else
        {
            NodeID repNodeId = callGraphSCC->repNode(cgNode->getId());
            if (visitedEntrySCCs.count(repNodeId))
                continue;
 
            const NodeBS& cgSCCNodes = callGraphSCC->subNodes(repNodeId);
            bool hasExternalCaller = false;
            for (NodeID nodeId : cgSCCNodes)
            {
                const CallGraphNode* sccNode = callGraph->getGNode(nodeId);
                for (auto inEdge : sccNode->getInEdges())
                {
                    if (!cgSCCNodes.test(inEdge->getSrcID()))
                    {
                        hasExternalCaller = true;
                        break;
                    }
                }
                if (hasExternalCaller)
                    break;
            }
 
            if (hasExternalCaller)
                continue;
 
            visitedEntrySCCs.insert(repNodeId);
            const FunObjVar* entryFun = fun;
            for (NodeID nodeId : cgSCCNodes)
            {
                const FunObjVar* sccFun = callGraph->getGNode(nodeId)->getFunction();
                if (SVFUtil::isProgEntryFunction(sccFun))
                {
                    entryFun = sccFun;
                    break;
                }
            }
            entryFunctions.push(entryFun);
        }
    }
 
    if (mainEntry && entryFunctions.empty())
    {
        SVFUtil::errs() << SVFUtil::errMsg(
                            "AE -ae-fun-entry=main requires a program entry function, but main/svf.main was not found.\n");
        assert(false && "No program entry function found for -ae-fun-entry=main");
        abort();
    }
 
    return entryFunctions;
}

evaluateIntervalCmp()

IntervalValue AbstractInterpretation::evaluateIntervalCmp ( u32_t  predicate, const IntervalValue &  lhs, const IntervalValue &  rhs  ) const

private

Definition at line 1177 of file AbstractInterpretation.cpp.

{
    IntervalValue result = IntervalValue::top();
    switch (predicate)
    {
    case CmpStmt::ICMP_EQ:
    case CmpStmt::FCMP_OEQ:
    case CmpStmt::FCMP_UEQ:
        result = (lhs == rhs);
        break;
    case CmpStmt::ICMP_NE:
    case CmpStmt::FCMP_ONE:
    case CmpStmt::FCMP_UNE:
        result = (lhs != rhs);
        break;
    case CmpStmt::ICMP_UGT:
    case CmpStmt::ICMP_SGT:
    case CmpStmt::FCMP_OGT:
    case CmpStmt::FCMP_UGT:
        result = (lhs > rhs);
        break;
    case CmpStmt::ICMP_UGE:
    case CmpStmt::ICMP_SGE:
    case CmpStmt::FCMP_OGE:
    case CmpStmt::FCMP_UGE:
        result = (lhs >= rhs);
        break;
    case CmpStmt::ICMP_ULT:
    case CmpStmt::ICMP_SLT:
    case CmpStmt::FCMP_OLT:
    case CmpStmt::FCMP_ULT:
        result = (lhs < rhs);
        break;
    case CmpStmt::ICMP_ULE:
    case CmpStmt::ICMP_SLE:
    case CmpStmt::FCMP_OLE:
    case CmpStmt::FCMP_ULE:
        result = (lhs <= rhs);
        break;
    case CmpStmt::FCMP_FALSE:
        result = IntervalValue(0, 0);
        break;
    case CmpStmt::FCMP_TRUE:
        result = IntervalValue(1, 1);
        break;
    case CmpStmt::FCMP_ORD:
    case CmpStmt::FCMP_UNO:
        // Keep both outcomes because the interval domain does not track NaN.
        result = IntervalValue(0, 1);
        break;
    default:
        assert(false && "undefined compare: ");
    }
    return result;
}

evaluatePointerCmp()

IntervalValue AbstractInterpretation::evaluatePointerCmp ( u32_t  predicate, const AddressValue &  lhs, const AddressValue &  rhs  ) const

private

Evaluate a pointer-typed ICMP over abstract points-to alternatives. Object IDs identify targets but their numeric order does not model runtime address order, so only equality and inequality can produce a definite result.

Definition at line 1131 of file AbstractInterpretation.cpp.

{
    assert(predicate >= CmpStmt::FIRST_ICMP_PREDICATE &&
           predicate <= CmpStmt::LAST_ICMP_PREDICATE &&
           "pointer comparison must use an ICMP predicate");
 
    const bool lhsTargetKnown =
        !lhs.isBottom() && !lhs.contains(BlackHoleObjAddr);
    const bool rhsTargetKnown =
        !rhs.isBottom() && !rhs.contains(BlackHoleObjAddr);
    const bool hasUnknownTarget = !lhsTargetKnown || !rhsTargetKnown;
    const bool targetsMayBeEqual = lhs.hasIntersect(rhs);
    const bool targetsMustBeEqual =
        targetsMayBeEqual && lhs.size() == 1 && rhs.size() == 1;
 
    IntervalValue equality;
    if (hasUnknownTarget)
    {
        // Case 1: an unknown target may equal or differ from the other target.
        equality = IntervalValue((s64_t)0, (s64_t)1);
    }
    else if (!targetsMayBeEqual)
    {
        // Case 2: known disjoint target sets are definitely unequal.
        equality = IntervalValue((s64_t)0);
    }
    else if (targetsMustBeEqual)
    {
        // Case 3: intersecting single-target sets contain the same target.
        equality = IntervalValue((s64_t)1);
    }
    else
    {
        // Case 4: intersecting sets with multiple choices may be equal.
        equality = IntervalValue((s64_t)0, (s64_t)1);
    }
 
    IntervalValue result((s64_t)0, (s64_t)1);
    if (predicate == CmpStmt::ICMP_EQ)
        result = equality;
    else if (predicate == CmpStmt::ICMP_NE)
        result = IntervalValue((s64_t)1) - equality;
    return result;
}

getAbsState() [1/4]

AbstractState & AbstractInterpretation::getAbsState

(

const ICFGNode *

node

)

Definition at line 44 of file AbstractStateManager.cpp.

{
    if (abstractTrace.count(node) == 0)
    {
        assert(false && "No preAbsTrace for this node");
        abort();
    }
    return abstractTrace[node];
}

getAbsState() [2/4]

void AbstractInterpretation::getAbsState	(	const Set< const ObjVar * > &	vars,
		AbstractState &	result,
		const ICFGNode *	node
	)

Definition at line 171 of file AbstractStateManager.cpp.

{
    AbstractState& as = getAbsState(node);
    for (const ObjVar* var : vars)
    {
        u32_t addr = AbstractState::getVirtualMemAddress(var->getId());
        result.store(addr, as.load(addr));
    }
}

getAbsState() [3/4]

void AbstractInterpretation::getAbsState	(	const Set< const SVFVar * > &	vars,
		AbstractState &	result,
		const ICFGNode *	node
	)

Definition at line 181 of file AbstractStateManager.cpp.

{
    AbstractState& as = getAbsState(node);
    for (const SVFVar* var : vars)
    {
        if (const ValVar* valVar = SVFUtil::dyn_cast<ValVar>(var))
        {
            u32_t id = valVar->getId();
            result[id] = as[id];
        }
        else if (const ObjVar* objVar = SVFUtil::dyn_cast<ObjVar>(var))
        {
            u32_t addr = AbstractState::getVirtualMemAddress(objVar->getId());
            result.store(addr, as.load(addr));
        }
    }
}

getAbsState() [4/4]

void AbstractInterpretation::getAbsState	(	const Set< const ValVar * > &	vars,
		AbstractState &	result,
		const ICFGNode *	node
	)

Definition at line 161 of file AbstractStateManager.cpp.

{
    AbstractState& as = getAbsState(node);
    for (const ValVar* var : vars)
    {
        u32_t id = var->getId();
        result[id] = as[id];
    }
}

getAbsValue() [1/3]

const AbstractValue & AbstractInterpretation::getAbsValue ( const ObjVar *  var, const ICFGNode *  node  )

virtual

Reimplemented in SVF::SemiSparseAbstractInterpretation.

Definition at line 93 of file AbstractStateManager.cpp.

{
    AbstractState& as = getAbsState(node);
    u32_t addr = AbstractState::getVirtualMemAddress(var->getId());
    return as.load(addr);
}

getAbsValue() [2/3]

const AbstractValue & AbstractInterpretation::getAbsValue ( const SVFVar *  var, const ICFGNode *  node  )

virtual

Reimplemented in SVF::SemiSparseAbstractInterpretation.

Definition at line 100 of file AbstractStateManager.cpp.

{
    if (const ObjVar* objVar = SVFUtil::dyn_cast<ObjVar>(var))
        return getAbsValue(objVar, node);
    if (const ValVar* valVar = SVFUtil::dyn_cast<ValVar>(var))
        return getAbsValue(valVar, node);
    assert(false && "Unknown SVFVar kind");
    abort();
}

getAbsValue() [3/3]

const AbstractValue & AbstractInterpretation::getAbsValue ( const ValVar *  var, const ICFGNode *  node  )

virtual

Read a top-level variable's abstract value. Dense base does a direct trace lookup; sparse subclasses override with their own resolution chain (def-site walk, call-result fallback, etc.). All three overloads are virtual so full-sparse can route ObjVar reads through the SVFG.

Dense base: direct trace lookup, with a type-directed top value for genuinely missing entries (e.g. function parameters never written before first read). Sparse subclasses override with a def-site resolution chain.

The "in map" check is a raw map.count — NOT inVarToValTable / inVarToAddrsTable, which gate on isInterval / isAddr. SVF canonically represents uninit and null-pointer shapes as (interval=bottom ∧ addrs=∅); those predicates would falsely report such an entry as "not present", and the top fallback below would then clobber the very signal NullptrDerefDetector::isUninit keys off.

Reimplemented in SVF::SemiSparseAbstractInterpretation, and SVF::SemiSparseAbstractInterpretation.

Definition at line 79 of file AbstractStateManager.cpp.

{
    u32_t id = var->getId();
    AbstractState& as = abstractTrace[node];
    if (!as.getVarToVal().count(id))
    {
        if (var->getType()->isPointerTy())
            as[id] = AddressValue(BlackHoleObjAddr);
        else
            as[id] = IntervalValue::top();
    }
    return as[id];
}

getAEInstance()

AbstractInterpretation & AbstractInterpretation::getAEInstance ( )

static

Factory: returns the singleton instance. The concrete class is chosen once, on first call, from Options::AESparsity(): SemiSparseAbstractInterpretation for SemiSparse, FullSparseAbstractInterpretation for Sparse, otherwise the dense base. Must be called only after the option parser has run.

Factory: first call allocates the concrete subclass based on Options::AESparsity(); all subsequent calls return the same instance. Must only be called after the option parser has populated AESparsity.

Definition at line 76 of file AbstractInterpretation.cpp.

{
    // Leak the singleton on purpose.  AbstractInterpretation owns a
    // Map<std::string, std::function<void(const CallICFGNode*)>> func_map
    // whose lambda closures back-reference state owned by other globals
    // (preAnalysis's WTO, the call graph, ...).  Letting the static
    // unique_ptr's atexit-time destructor run hits a static-destruction-
    // order issue: the func_map hashtable's destructor calls into
    // std::function destroyers whose closures touch already-destroyed
    // state, and ~_Hashtable() segfaults during normal program shutdown.
    //
    // Reliably reproducible from any downstream tool that drives a full
    // AE analysis to completion and then exits normally:
    //   - SSA's ass3 binary (Software-Security-Analysis/Assignment-3)
    //   - pysvf via Python interpreter shutdown
    //
    // A process-lifetime singleton has no observable lifecycle past
    // program exit, so leaking is benign and avoids the use-after-destroy.
    static AbstractInterpretation* instance = []() -> AbstractInterpretation*
    {
        switch (Options::AESparsity())
        {
        case AESparsity::SemiSparse:
            return new SemiSparseAbstractInterpretation();
        case AESparsity::Sparse:
            return new FullSparseAbstractInterpretation();
        case AESparsity::Dense:
        default:
            return new AbstractInterpretation();
        }
    }();
    return *instance;
}

getAllocaInstByteSize()

u32_t AbstractInterpretation::getAllocaInstByteSize

(

const AddrStmt *

addr

)

Definition at line 387 of file AbstractStateManager.cpp.

{
    const ICFGNode* node = addr->getICFGNode();
    if (const ObjVar* objvar = SVFUtil::dyn_cast<ObjVar>(addr->getRHSVar()))
    {
        if (svfir->getBaseObject(objvar->getId())->isConstantByteSize())
        {
            return svfir->getBaseObject(objvar->getId())->getByteSizeOfObj();
        }
        else
        {
            const std::vector<SVFVar*>& sizes = addr->getArrSize();
            u32_t elementSize = 1;
            u64_t res = elementSize;
            for (const SVFVar* value : sizes)
            {
                const AbstractValue& sizeVal = getAbsValue(value, node);
                IntervalValue itv = sizeVal.getInterval();
                if (itv.isBottom())
                    itv = IntervalValue(Options::MaxFieldLimit());
                res = res * itv.ub().getIntNumeral() > Options::MaxFieldLimit()
                      ? Options::MaxFieldLimit() : res * itv.ub().getIntNumeral();
            }
            return (u32_t)res;
        }
    }
    assert(false && "Addr rhs value is not ObjVar");
    abort();
}

getCallee()

const FunObjVar * AbstractInterpretation::getCallee ( const CallICFGNode *  callNode )

private

Get callee function: directly for direct calls, via pointer analysis for indirect calls.

Definition at line 828 of file AbstractInterpretation.cpp.

{
    // Direct call: get callee directly from call node
    if (const FunObjVar* callee = callNode->getCalledFunction())
        return callee;
 
    // Indirect call: resolve callee through pointer analysis
    const auto callsiteMaps = svfir->getIndirectCallsites();
    auto it = callsiteMaps.find(callNode);
    if (it == callsiteMaps.end())
        return nullptr;
 
    NodeID call_id = it->second;
    if (!hasAbsState(callNode))
        return nullptr;
 
    const AbstractValue& Addrs = getAbsValue(svfir->getSVFVar(call_id), callNode);
    if (!Addrs.isAddr() || Addrs.getAddrs().empty())
        return nullptr;
 
    NodeID addr = *Addrs.getAddrs().begin();
    const SVFVar* func_var = getSVFVar(getAbsState(callNode).getIDFromAddr(addr));
    return SVFUtil::dyn_cast<FunObjVar>(func_var);
}

getFullCycleHeadState()

AbstractState AbstractInterpretation::getFullCycleHeadState ( const ICFGCycleWTO *  cycle )

protectedvirtual

Build a full cycle-head AbstractState. Dense default: trace[cycle_head] as-is. Semi-sparse subclass: also pull cycle ValVars from def-sites.

Reimplemented in SVF::SemiSparseAbstractInterpretation.

Definition at line 162 of file AELoopRecursion.cpp.

{
    const ICFGNode* cycle_head = cycle->head()->getICFGNode();
    AbstractState snap;
    if (hasAbsState(cycle_head))
        snap = getAbsState(cycle_head);
    return snap;
}

getGepByteOffset()

IntervalValue AbstractInterpretation::getGepByteOffset

(

const GepStmt *

gep

)

Definition at line 256 of file AbstractStateManager.cpp.

{
    const ICFGNode* node = gep->getICFGNode();
    if (gep->isConstantOffset())
        return IntervalValue((s64_t)gep->accumulateConstantByteOffset());
 
    IntervalValue res(0);
    for (int i = gep->getOffsetVarAndGepTypePairVec().size() - 1; i >= 0; i--)
    {
        const ValVar* idxOperandVar = gep->getOffsetVarAndGepTypePairVec()[i].first;
        const SVFType* idxOperandType = gep->getOffsetVarAndGepTypePairVec()[i].second;
 
        if (SVFUtil::isa<SVFArrayType>(idxOperandType) || SVFUtil::isa<SVFPointerType>(idxOperandType))
        {
            u32_t elemByteSize = 1;
            if (const SVFArrayType* arrOperandType = SVFUtil::dyn_cast<SVFArrayType>(idxOperandType))
                elemByteSize = arrOperandType->getTypeOfElement()->getByteSize();
            else if (SVFUtil::isa<SVFPointerType>(idxOperandType))
                elemByteSize = gep->getAccessPath().gepSrcPointeeType()->getByteSize();
            else
                assert(false && "idxOperandType must be ArrType or PtrType");
 
            if (const ConstIntValVar* op = SVFUtil::dyn_cast<ConstIntValVar>(idxOperandVar))
            {
                s64_t lb = (double)Options::MaxFieldLimit() / elemByteSize >= op->getSExtValue()
                           ? op->getSExtValue() * elemByteSize
                           : Options::MaxFieldLimit();
                res = res + IntervalValue(lb, lb);
            }
            else
            {
                IntervalValue idxVal = getAbsValue(idxOperandVar, node).getInterval();
                if (idxVal.isBottom())
                    res = res + IntervalValue(0, 0);
                else
                {
                    s64_t ub = (idxVal.ub().getIntNumeral() < 0) ? 0
                               : (double)Options::MaxFieldLimit() / elemByteSize >= idxVal.ub().getIntNumeral()
                               ? elemByteSize * idxVal.ub().getIntNumeral()
                               : Options::MaxFieldLimit();
                    s64_t lb = (idxVal.lb().getIntNumeral() < 0) ? 0
                               : (double)Options::MaxFieldLimit() / elemByteSize >= idxVal.lb().getIntNumeral()
                               ? elemByteSize * idxVal.lb().getIntNumeral()
                               : Options::MaxFieldLimit();
                    res = res + IntervalValue(lb, ub);
                }
            }
        }
        else if (const SVFStructType* structOperandType = SVFUtil::dyn_cast<SVFStructType>(idxOperandType))
        {
            res = res + IntervalValue(gep->getAccessPath().getStructFieldOffset(idxOperandVar, structOperandType));
        }
        else
        {
            assert(false && "gep type pair only support arr/ptr/struct");
        }
    }
    return res;
}

getGepElementIndex()

IntervalValue AbstractInterpretation::getGepElementIndex

(

const GepStmt *

gep

)

Definition at line 199 of file AbstractStateManager.cpp.

{
    const ICFGNode* node = gep->getICFGNode();
    if (gep->isConstantOffset())
        return IntervalValue((s64_t)gep->accumulateConstantOffset());
 
    IntervalValue res(0);
    for (int i = gep->getOffsetVarAndGepTypePairVec().size() - 1; i >= 0; i--)
    {
        const ValVar* var = gep->getOffsetVarAndGepTypePairVec()[i].first;
        const SVFType* type = gep->getOffsetVarAndGepTypePairVec()[i].second;
 
        s64_t idxLb, idxUb;
        if (const ConstIntValVar* constInt = SVFUtil::dyn_cast<ConstIntValVar>(var))
            idxLb = idxUb = constInt->getSExtValue();
        else
        {
            IntervalValue idxItv = getAbsValue(var, node).getInterval();
            if (idxItv.isBottom())
                idxLb = idxUb = 0;
            else
            {
                idxLb = idxItv.lb().getIntNumeral();
                idxUb = idxItv.ub().getIntNumeral();
            }
        }
 
        if (SVFUtil::isa<SVFPointerType>(type))
        {
            u32_t elemNum = gep->getAccessPath().getElementNum(gep->getAccessPath().gepSrcPointeeType());
            idxLb = (double)Options::MaxFieldLimit() / elemNum < idxLb ? Options::MaxFieldLimit() : idxLb * elemNum;
            idxUb = (double)Options::MaxFieldLimit() / elemNum < idxUb ? Options::MaxFieldLimit() : idxUb * elemNum;
        }
        else
        {
            if (Options::ModelArrays())
            {
                const std::vector<u32_t>& so = PAG::getPAG()->getTypeInfo(type)->getFlattenedElemIdxVec();
                if (so.empty() || idxUb >= (APOffset)so.size() || idxLb < 0)
                    idxLb = idxUb = 0;
                else
                {
                    idxLb = PAG::getPAG()->getFlattenedElemIdx(type, idxLb);
                    idxUb = PAG::getPAG()->getFlattenedElemIdx(type, idxUb);
                }
            }
            else
                idxLb = idxUb = 0;
        }
        res = res + IntervalValue(idxLb, idxUb);
    }
    res.meet_with(IntervalValue((s64_t)0, (s64_t)Options::MaxFieldLimit()));
    if (res.isBottom())
        res = IntervalValue(0);
    return res;
}

getGepObjAddrs()

AddressValue AbstractInterpretation::getGepObjAddrs	(	const ValVar *	pointer,
		IntervalValue	offset
	)

Definition at line 316 of file AbstractStateManager.cpp.

{
    const ICFGNode* node = pointer->getICFGNode();
    AddressValue gepAddrs;
    AbstractState& as = getAbsState(node);
    APOffset lb = offset.lb().getIntNumeral() < Options::MaxFieldLimit() ? offset.lb().getIntNumeral()
                  : Options::MaxFieldLimit();
    APOffset ub = offset.ub().getIntNumeral() < Options::MaxFieldLimit() ? offset.ub().getIntNumeral()
                  : Options::MaxFieldLimit();
    for (APOffset i = lb; i <= ub; i++)
    {
        const AbstractValue& addrs = getAbsValue(pointer, node);
        for (const auto& addr : addrs.getAddrs())
        {
            // Null and black-hole addresses have no backing object.
            if (AbstractState::isNullOrBlackHoleAddr(addr))
                continue;
            s64_t baseObj = as.getIDFromAddr(addr);
            assert(SVFUtil::isa<ObjVar>(svfir->getSVFVar(baseObj)) && "Fail to get the base object address!");
            NodeID gepObj = svfir->getGepObjVar(baseObj, i);
            as[gepObj] = AddressValue(AbstractState::getVirtualMemAddress(gepObj));
            gepAddrs.insert(AbstractState::getVirtualMemAddress(gepObj));
        }
    }
    return gepAddrs;
}

getPointeeElement()

const SVFType * AbstractInterpretation::getPointeeElement	(	const ObjVar *	var,
		const ICFGNode *	node
	)

Definition at line 372 of file AbstractStateManager.cpp.

{
    const AbstractValue& ptrVal = getAbsValue(var, node);
    if (!ptrVal.isAddr())
        return nullptr;
    for (auto addr : ptrVal.getAddrs())
    {
        NodeID objId = getAbsState(node).getIDFromAddr(addr);
        if (objId == 0)
            continue;
        return svfir->getBaseObject(objId)->getType();
    }
    return nullptr;
}

getSVFVar()

const SVFVar * SVF::AbstractInterpretation::getSVFVar ( NodeID  varId ) const

inline

Retrieve SVFVar given its ID; asserts if no such variable exists.

Definition at line 130 of file AbstractInterpretation.h.

    {
        return svfir->getSVFVar(varId);
    }

getTrace()

Map< const ICFGNode *, AbstractState > & SVF::AbstractInterpretation::getTrace ( )

inline

Definition at line 192 of file AbstractInterpretation.h.

    {
        return abstractTrace;
    }

getUtils()

AbsExtAPI * SVF::AbstractInterpretation::getUtils ( )

inlineprivate

Definition at line 318 of file AbstractInterpretation.h.

    {
        return utils;
    }

handleCallSite()

void AbstractInterpretation::handleCallSite ( const ICFGNode *  node )

privatevirtual

Handle a call site node: dispatch to ext-call, direct-call, or indirect-call handling.

Definition at line 795 of file AbstractInterpretation.cpp.

{
    if (const CallICFGNode* callNode = SVFUtil::dyn_cast<CallICFGNode>(node))
    {
        if (isExtCall(callNode))
        {
            handleExtCall(callNode);
        }
        else
        {
            // Handle both direct and indirect calls uniformly
            handleFunCall(callNode);
        }
    }
    else
        assert (false && "it is not call node");
}

handleExtCall()

void AbstractInterpretation::handleExtCall ( const CallICFGNode *  callNode )

privatevirtual

Definition at line 818 of file AbstractInterpretation.cpp.

{
    utils->handleExtAPI(callNode);
    for (auto& detector : detectors)
    {
        detector->handleStubFunctions(callNode);
    }
}

handleFunCall()

void AbstractInterpretation::handleFunCall ( const CallICFGNode *  callNode )

privatevirtual

Handle direct or indirect call: get callee(s), process function body, set return state.

For direct calls, the callee is known statically. For indirect calls, the previous implementation resolved callees from the abstract state's address domain, which only picked the first address and missed other targets. Since the abstract state's address domain is not an over-approximation for function pointers (it may be uninitialized or incomplete), we now use Andersen's pointer analysis results from the pre-computed call graph, which soundly resolves all possible indirect call targets.

Definition at line 862 of file AbstractInterpretation.cpp.

{
    if (skipRecursiveCall(callNode))
        return;
 
    // Direct call: callee is known
    if (const FunObjVar* callee = callNode->getCalledFunction())
    {
        const ICFGNode* calleeEntry = icfg->getFunEntryICFGNode(callee);
        handleFunction(calleeEntry, callNode);
        const RetICFGNode* retNode = callNode->getRetICFGNode();
        updateAbsState(retNode, getAbsState(callNode));
        return;
    }
 
    // Indirect call: use Andersen's call graph to get all resolved callees.
    const RetICFGNode* retNode = callNode->getRetICFGNode();
    if (callGraph->hasIndCSCallees(callNode))
    {
        const auto& callees = callGraph->getIndCSCallees(callNode);
        for (const FunObjVar* callee : callees)
        {
            if (callee->isDeclaration())
                continue;
            const ICFGNode* calleeEntry = icfg->getFunEntryICFGNode(callee);
            handleFunction(calleeEntry, callNode);
        }
    }
    // Resume return node from caller's state (context-insensitive)
    updateAbsState(retNode, getAbsState(callNode));
}

handleFunction()

void AbstractInterpretation::handleFunction ( const ICFGNode *  funEntry, const CallICFGNode *  caller  )

private

Handle a function body via worklist-driven WTO traversal starting from funEntry.

Handle a function using worklist algorithm guided by WTO order. All top-level WTO components are pushed into the worklist upfront, so the traversal order is exactly the WTO order — each node is visited once, and cycles are handled as whole components.

Definition at line 768 of file AbstractInterpretation.cpp.

{
    auto it = preAnalysis->getFuncToWTO().find(funEntry->getFun());
    assert(it != preAnalysis->getFuncToWTO().end() && "Missing WTO for function");
 
    // Push all top-level WTO components into the worklist in WTO order
    FIFOWorkList<const ICFGWTOComp*> worklist(it->second->getWTOComponents());
 
    while (!worklist.empty())
    {
        const ICFGWTOComp* comp = worklist.pop();
 
        if (const ICFGSingletonWTO* singleton = SVFUtil::dyn_cast<ICFGSingletonWTO>(comp))
        {
            const ICFGNode* node = singleton->getICFGNode();
            if (mergeStatesFromPredecessors(node))
                handleICFGNode(node);
        }
        else if (const ICFGCycleWTO* cycle = SVFUtil::dyn_cast<ICFGCycleWTO>(comp))
        {
            if (mergeStatesFromPredecessors(cycle->head()->getICFGNode()))
                handleLoopOrRecursion(cycle, caller);
        }
    }
}

handleGlobalNode()

void AbstractInterpretation::handleGlobalNode ( )

privatevirtual

Initialize abstract state for the global ICFG node and process global statements

handle global node Initializes the abstract state for the global ICFG node and processes all global statements. This includes setting up the null pointer and black hole pointer (blkPtr). BlkPtr is initialized to point to the BlackHole object, representing an unknown memory location that cannot be statically resolved.

Definition at line 235 of file AbstractInterpretation.cpp.

{
    const ICFGNode* node = icfg->getGlobalICFGNode();
    // Global init is one of the few legitimate direct-mutation sites:
    // updateAbsState filters out ValVars in semi-sparse mode, but NullPtr/
    // BlkPtr have no SVFVar so we cannot route them through updateAbsValue.
    // Use the manager's operator[] (auto-creates the entry if absent).
    AbstractState& init = abstractTrace[node];
    init = AbstractState();
    // NullPtr has no backing SVFVar. Model it directly as the singleton null
    // address; BlkPtr is initialized directly below for the same reason.
    init[IRGraph::NullPtr] = AddressValue(NullMemAddr);
 
    // Global Node, we just need to handle addr, load, store, copy and gep
    for (const SVFStmt *stmt: node->getSVFStmts())
    {
        handleSVFStatement(stmt);
    }
 
    // BlkPtr is the canonical unknown value.  Keep its address-domain meaning
    // for pointer uses, and also give it numeric top so external-input stores
    // can flow through ordinary store/load state as [-inf, +inf].
    AbstractValue blkPtrValue(IntervalValue::top());
    blkPtrValue.getAddrs().insert(BlackHoleObjAddr);
    abstractTrace[node][PAG::getPAG()->getBlkPtr()] = blkPtrValue;
}

handleICFGNode()

bool AbstractInterpretation::handleICFGNode ( const ICFGNode *  node )

private

Handle an ICFG node: execute statements; return true if state changed.

Handle an ICFG node: execute statements on the current abstract state. The node's pre-state must already be in getAbsState(node) (set by mergeStatesFromPredecessors, or by handleGlobalNode for the global node). Returns true if the abstract state has changed, false if fixpoint reached or unreachable.

Definition at line 709 of file AbstractInterpretation.cpp.

{
    // Check reachability: pre-state must have been propagated by predecessors
    bool isFunEntry = SVFUtil::isa<FunEntryICFGNode>(node);
    if (!hasAbsState(node))
    {
        if (isFunEntry)
        {
            // Entry point with no callers: inherit from global node
            const ICFGNode* globalNode = icfg->getGlobalICFGNode();
            if (hasAbsState(globalNode))
                updateAbsState(node, getAbsState(globalNode));
            else
                updateAbsState(node, AbstractState());
        }
        else
        {
            return false;  // unreachable node
        }
    }
 
    // Store the previous state for fixpoint detection
    AbstractState prevState = getAbsState(node);
 
    stat->getBlockTrace()++;
    stat->getICFGNodeTrace()++;
 
    // Handle SVF statements
    for (const SVFStmt *stmt: node->getSVFStmts())
    {
        handleSVFStatement(stmt);
    }
 
    // Handle call sites
    if (const CallICFGNode* callNode = SVFUtil::dyn_cast<CallICFGNode>(node))
    {
        handleCallSite(callNode);
    }
 
    // Run detectors
    for (auto& detector: detectors)
        detector->detect(node);
    stat->countStateSize();
 
    // Track this node as analyzed (for coverage statistics across all entry points)
    allAnalyzedNodes.insert(node);
 
    if (getAbsState(node) == prevState)
        return false;
 
    return true;
}

handleLoopOrRecursion()

void AbstractInterpretation::handleLoopOrRecursion ( const ICFGCycleWTO *  cycle, const CallICFGNode *  caller  )

privatevirtual

Handle a WTO cycle (loop or recursive function) using widening/narrowing iteration.

Definition at line 235 of file AELoopRecursion.cpp.

{
    const ICFGNode* cycle_head = cycle->head()->getICFGNode();
 
    // TOP mode for recursive function cycles: set all stores and return value to TOP
    if (Options::HandleRecur() == TOP && isRecursiveFun(cycle_head->getFun()))
    {
        if (caller)
            skipRecursionWithTop(caller);
        return;
    }
 
    // Iterate until fixpoint with widening/narrowing on the cycle head.
    bool increasing = true;
    u32_t widen_delay = Options::WidenDelay();
    for (u32_t cur_iter = 0;; cur_iter++)
    {
        if (cur_iter >= widen_delay)
        {
            // getFullCycleHeadState handles dense (returns trace[cycle_head])
            // and semi-sparse (collects ValVars from def-sites) uniformly.
            AbstractState prev = getFullCycleHeadState(cycle);
 
            if (mergeStatesFromPredecessors(cycle_head))
                handleICFGNode(cycle_head);
            AbstractState cur = getFullCycleHeadState(cycle);
 
            if (increasing)
            {
                if (widenCycleState(prev, cur, cycle))
                {
                    increasing = false;
                    continue;
                }
            }
            else
            {
                if (narrowCycleState(prev, cur, cycle))
                    break;
            }
        }
        else
        {
            // Before widen_delay: process cycle head with gated pattern
            if (mergeStatesFromPredecessors(cycle_head))
                handleICFGNode(cycle_head);
        }
 
        // Process cycle body components (each with gated merge+handle)
        for (const ICFGWTOComp* comp : cycle->getWTOComponents())
        {
            if (const ICFGSingletonWTO* singleton = SVFUtil::dyn_cast<ICFGSingletonWTO>(comp))
            {
                const ICFGNode* node = singleton->getICFGNode();
                if (mergeStatesFromPredecessors(node))
                    handleICFGNode(node);
            }
            else if (const ICFGCycleWTO* subCycle = SVFUtil::dyn_cast<ICFGCycleWTO>(comp))
            {
                if (mergeStatesFromPredecessors(subCycle->head()->getICFGNode()))
                    handleLoopOrRecursion(subCycle, caller);
            }
        }
    }
}

handleSVFStatement()

void AbstractInterpretation::handleSVFStatement ( const SVFStmt *  stmt )

privatevirtual

Dispatch an SVF statement (Addr/Binary/Cmp/Load/Store/Copy/Gep/Select/Phi/Call/Ret) to its handler.

Definition at line 897 of file AbstractInterpretation.cpp.

{
    if (const AddrStmt *addr = SVFUtil::dyn_cast<AddrStmt>(stmt))
    {
        updateStateOnAddr(addr);
    }
    else if (const BinaryOPStmt *binary = SVFUtil::dyn_cast<BinaryOPStmt>(stmt))
    {
        updateStateOnBinary(binary);
    }
    else if (const CmpStmt *cmp = SVFUtil::dyn_cast<CmpStmt>(stmt))
    {
        updateStateOnCmp(cmp);
    }
    else if (SVFUtil::isa<UnaryOPStmt>(stmt))
    {
    }
    else if (SVFUtil::isa<BranchStmt>(stmt))
    {
        // branch stmt is handled in hasBranchES
    }
    else if (const LoadStmt *load = SVFUtil::dyn_cast<LoadStmt>(stmt))
    {
        updateStateOnLoad(load);
    }
    else if (const StoreStmt *store = SVFUtil::dyn_cast<StoreStmt>(stmt))
    {
        updateStateOnStore(store);
    }
    else if (const CopyStmt *copy = SVFUtil::dyn_cast<CopyStmt>(stmt))
    {
        updateStateOnCopy(copy);
    }
    else if (const GepStmt *gep = SVFUtil::dyn_cast<GepStmt>(stmt))
    {
        updateStateOnGep(gep);
    }
    else if (const SelectStmt *select = SVFUtil::dyn_cast<SelectStmt>(stmt))
    {
        updateStateOnSelect(select);
    }
    else if (const PhiStmt *phi = SVFUtil::dyn_cast<PhiStmt>(stmt))
    {
        updateStateOnPhi(phi);
    }
    else if (const CallPE *callPE = SVFUtil::dyn_cast<CallPE>(stmt))
    {
        // To handle Call Edge
        updateStateOnCall(callPE);
    }
    else if (const RetPE *retPE = SVFUtil::dyn_cast<RetPE>(stmt))
    {
        updateStateOnRet(retPE);
    }
    else
        assert(false && "implement this part");
    // NullPtr should not be changed by any statement. If the entry is missing
    // (not yet auto-inserted) we treat that as "unchanged" — only check the
    // entry if it actually exists.
    {
        const auto& vmap = getAbsState(stmt->getICFGNode()).getVarToVal();
        auto it = vmap.find(IRGraph::NullPtr);
        (void)it; // Suppress warning of unused variable under release build
        assert(it == vmap.end() ||
               (it->second.isAddr() &&
                it->second.getAddrs().equals(AddressValue(NullMemAddr))));
    }
}

hasAbsState()

bool AbstractInterpretation::hasAbsState

(

const ICFGNode *

node

)

Definition at line 64 of file AbstractStateManager.cpp.

{
    return abstractTrace.count(node) != 0;
}

hasAbsValue() [1/3]

bool AbstractInterpretation::hasAbsValue ( const ObjVar *  var, const ICFGNode *  node  ) const

virtual

Reimplemented in SVF::SemiSparseAbstractInterpretation.

Definition at line 122 of file AbstractStateManager.cpp.

{
    auto it = abstractTrace.find(node);
    if (it == abstractTrace.end())
        return false;
    return it->second.getLocToVal().count(var->getId()) != 0;
}

hasAbsValue() [2/3]

bool AbstractInterpretation::hasAbsValue ( const SVFVar *  var, const ICFGNode *  node  ) const

virtual

Reimplemented in SVF::SemiSparseAbstractInterpretation.

Definition at line 130 of file AbstractStateManager.cpp.

{
    if (const ObjVar* objVar = SVFUtil::dyn_cast<ObjVar>(var))
        return hasAbsValue(objVar, node);
    if (const ValVar* valVar = SVFUtil::dyn_cast<ValVar>(var))
        return hasAbsValue(valVar, node);
    return false;
}

hasAbsValue() [3/3]

bool AbstractInterpretation::hasAbsValue ( const ValVar *  var, const ICFGNode *  node  ) const

virtual

Side-effect-free existence check.

Dense base: direct existence check at node. Mirrors the simplified getAbsValue lookup — uses raw map.contains rather than inVar*Table predicates, which would falsely report neutral (interval=bottom ∧ addrs=∅) entries as "not present".

Reimplemented in SVF::SemiSparseAbstractInterpretation, and SVF::SemiSparseAbstractInterpretation.

Definition at line 114 of file AbstractStateManager.cpp.

{
    auto it = abstractTrace.find(node);
    if (it == abstractTrace.end())
        return false;
    return it->second.getVarToVal().count(var->getId()) != 0;
}

isBranchEdgeFeasible()

bool AbstractInterpretation::isBranchEdgeFeasible ( const IntraCFGEdge *  edge, AbstractState &  as  )

protected

Returns true if the branch edge is reachable under the current state. Pure query: does not update as or branch refinement traces.

Definition at line 693 of file AbstractInterpretation.cpp.

{
    const SVFVar* cmpVar = edge->getCondition();
    assert(!cmpVar->getInEdges().empty() && "branch condition has no defining edge?");
    if (SVFUtil::isa<CmpStmt>(*cmpVar->getInEdges().begin()))
        return isCmpBranchEdgeFeasible(edge, as);
    return isSwitchBranchEdgeFeasible(edge, as);
}

isCmpBranchEdgeFeasible()

bool AbstractInterpretation::isCmpBranchEdgeFeasible ( const IntraCFGEdge *  edge, AbstractState &  as  )

private

Returns true if the cmp-conditional branch is feasible.

Definition at line 491 of file AbstractInterpretation.cpp.

{
    const ICFGNode* pred = edge->getSrcNode();
    s64_t succ = edge->getSuccessorCondValue();
    const CmpStmt* cmpStmt = SVFUtil::cast<CmpStmt>(
                                 *edge->getCondition()->getInEdges().begin());
    const AbstractValue& cmpValue = getAbsValue(cmpStmt->getRes(), pred);
    assert(cmpValue.isInterval() &&
           "CmpStmt result must be represented by a Boolean interval");
 
    // Feasibility check: cmp result must be compatible with branch successor
    IntervalValue resVal = cmpValue.getInterval();
    resVal.meet_with(IntervalValue((s64_t)succ, succ));
    return !resVal.isBottom();
}

isExtCall()

bool AbstractInterpretation::isExtCall ( const CallICFGNode *  callNode )

privatevirtual

Definition at line 813 of file AbstractInterpretation.cpp.

{
    return SVFUtil::isExtCall(callNode->getCalledFunction());
}

isRecursiveCallSite()

bool AbstractInterpretation::isRecursiveCallSite ( const CallICFGNode *  callNode, const FunObjVar *  callee  )

privatevirtual

Check if caller and callee are in the same CallGraph SCC (i.e. a recursive callsite)

Definition at line 104 of file AELoopRecursion.cpp.

{
    const FunObjVar* caller = callNode->getCaller();
    return preAnalysis->getPointerAnalysis()->inSameCallGraphSCC(caller, callee);
}

isRecursiveFun()

bool AbstractInterpretation::isRecursiveFun ( const FunObjVar *  fun )

privatevirtual

Check if a function is recursive (part of a call graph SCC)

Definition at line 47 of file AELoopRecursion.cpp.

{
    return preAnalysis->getPointerAnalysis()->isInRecursion(fun);
}

isSwitchBranchEdgeFeasible()

bool AbstractInterpretation::isSwitchBranchEdgeFeasible ( const IntraCFGEdge *  edge, AbstractState &  as  )

private

Returns true if the switch branch is feasible.

Definition at line 508 of file AbstractInterpretation.cpp.

{
    const ICFGNode* pred = edge->getSrcNode();
    s64_t succ = edge->getSuccessorCondValue();
    const SVFVar* var = edge->getCondition();
 
    AbstractValue condVal = getAbsValue(var, pred);
    IntervalValue switch_cond = condVal.getInterval();
    switch_cond.meet_with(IntervalValue(succ, succ));
    if (switch_cond.isBottom())
        return false;
    return true;
}

joinStates()

void AbstractInterpretation::joinStates ( AbstractState &  dst, const AbstractState &  src  )

virtual

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

Reimplemented in SVF::SemiSparseAbstractInterpretation, and SVF::FullSparseAbstractInterpretation.

Definition at line 59 of file AbstractStateManager.cpp.

{
    dst.joinWith(src);
}

loadValue()

AbstractValue AbstractInterpretation::loadValue ( const ValVar *  pointer, const ICFGNode *  node  )

virtual

Virtual so full-sparse can layer the GepObj overlay on top.

Definition at line 343 of file AbstractStateManager.cpp.

{
    const AbstractValue& ptrVal = getAbsValue(pointer, node);
    AbstractState& as = getAbsState(node);
    AbstractValue res;
    for (auto addr : ptrVal.getAddrs())
    {
        // Null and black-hole addresses have no backing object.
        if (AbstractState::isNullOrBlackHoleAddr(addr))
            continue;
        res.join_with(
            getAbsValue(svfir->getSVFVar(as.getIDFromAddr(addr)), node));
    }
    return res;
}

mergeStatesFromPredecessors()

bool AbstractInterpretation::mergeStatesFromPredecessors ( const ICFGNode *  node )

protectedvirtual

Pull-based state merge: read abstractTrace[pred] for each predecessor, apply branch refinement for conditional IntraCFGEdges, and join into abstractTrace[node]. Returns true if at least one predecessor had state. Virtual so full-sparse can layer per-MRSVFGNode obj pulls on top of the base ICFG-edge merge.

Pull-based state merge: for each predecessor that has an abstract state, copy its state, apply branch refinement for conditional IntraCFGEdges, and join all feasible states into getAbsState(node). The join is dispatched through the manager so semi-sparse can skip ValVar merging. Returns true if at least one predecessor contributed state.

Reimplemented in SVF::FullSparseAbstractInterpretation.

Definition at line 268 of file AbstractInterpretation.cpp.

{
    // Collect all feasible predecessor states, then merge at the end.
    AbstractState merged;
    bool hasFeasiblePred = false;
 
    for (auto& edge : node->getInEdges())
    {
        const ICFGNode* pred = edge->getSrcNode();
        if (!hasAbsState(pred))
            continue;
 
        if (const IntraCFGEdge* intraCfgEdge = SVFUtil::dyn_cast<IntraCFGEdge>(edge))
        {
            if (intraCfgEdge->getCondition())
            {
                AbstractState predState = getAbsState(pred);
                if (isBranchEdgeFeasible(intraCfgEdge, predState))
                {
                    collectBranchRefinement(intraCfgEdge, predState);
                    joinStates(merged, predState);
                    hasFeasiblePred = true;
                }
            }
            else
            {
                joinStates(merged, getAbsState(pred));
                hasFeasiblePred = true;
            }
        }
        else if (SVFUtil::isa<CallCFGEdge>(edge))
        {
            joinStates(merged, getAbsState(pred));
            hasFeasiblePred = true;
        }
        else if (SVFUtil::isa<RetCFGEdge>(edge))
        {
            switch (Options::HandleRecur())
            {
            case TOP:
                joinStates(merged, getAbsState(pred));
                hasFeasiblePred = true;
                break;
            case WIDEN_ONLY:
            case WIDEN_NARROW:
            {
                const RetICFGNode* returnSite = SVFUtil::dyn_cast<RetICFGNode>(node);
                const CallICFGNode* callSite = returnSite->getCallICFGNode();
                if (hasAbsState(callSite))
                {
                    joinStates(merged, getAbsState(pred));
                    hasFeasiblePred = true;
                }
                break;
            }
            }
        }
    }
 
    if (!hasFeasiblePred)
        return false;
 
    updateAbsState(node, merged);
 
    return true;
}

narrowCycleState()

bool AbstractInterpretation::narrowCycleState ( const AbstractState &  prev, const AbstractState &  cur, const ICFGCycleWTO *  cycle  )

protectedvirtual

Narrow prev with cur; write the narrowed state back. Returns true when narrowing is disabled or the narrowed state equals prev. Semi-sparse subclass scatters the narrowed ValVars on non-fixpoint.

Reimplemented in SVF::SemiSparseAbstractInterpretation.

Definition at line 183 of file AELoopRecursion.cpp.

{
    const ICFGNode* cycle_head = cycle->head()->getICFGNode();
    if (!shouldApplyNarrowing(cycle_head->getFun()))
        return true;
    AbstractState prev_copy = prev;
    AbstractState next = prev_copy.narrowing(cur);
    if (next == prev)
        return true;  // fixpoint
    abstractTrace[cycle_head] = next;
    return false;
}

operator[]()

AbstractState & SVF::AbstractInterpretation::operator[] ( const ICFGNode *  node )

inline

Definition at line 196 of file AbstractInterpretation.h.

    {
        return abstractTrace[node];
    }

recordBranchRefinement()

void AbstractInterpretation::recordBranchRefinement ( NodeID  objId, const IntervalValue &  narrowed, AbstractState &  as, const ICFGNode *  loadIcfg, const ICFGNode *  succ  )

protectedvirtual

Hook called by collectBranchRefinement for each obj that the branch narrows. Default (dense/semi): MEET narrowed onto obj's value (read at loadIcfg where sparse keeps it) and write the result into the local as (per-edge predState copy) so joinStates carries it to succ. FullSparse overrides to capture into refinementTrace[succ] instead.

Reimplemented in SVF::FullSparseAbstractInterpretation.

Definition at line 660 of file AbstractInterpretation.cpp.

{
    // Default (dense / semi-sparse): MEET narrowed onto obj's current
    // value, store back into the local `as`.  Caller's joinStates
    // propagates `as` into `merged`, then `updateAbsState(succ, merged)`
    // commits it to trace[succ].
    //
    // We can't go through the polymorphic updateAbsValue here: `as` is
    // a transient per-edge predState copy that lives outside
    // abstractTrace, so it has no node id.  Writing via `updateAbsValue`
    // with `succ` as the node would land in trace[succ] but get
    // clobbered by the subsequent `updateAbsState(succ, merged)`; with
    // `loadIcfg` it would corrupt the obj's authoritative value at its
    // load site.  AbstractState::store on the transient `as` is the
    // only sound primitive — and recordBranchRefinement itself is the
    // virtual customisation point (FullSparse routes to
    // refinementTrace instead of touching `as`).
    const ObjVar* objVar = SVFUtil::dyn_cast<ObjVar>(svfir->getGNode(objId));
    if (objVar && hasAbsValue(objVar, loadIcfg))
    {
        AbstractValue cur = getAbsValue(objVar, loadIcfg);
        if (cur.isInterval())
        {
            IntervalValue itv = cur.getInterval();
            itv.meet_with(narrowed);
            u32_t addr = AbstractState::getVirtualMemAddress(objId);
            as.store(addr, AbstractValue(itv));
        }
    }
}

runOnModule()

void AbstractInterpretation::runOnModule ( )

virtual

collect checkpoint

Definition at line 44 of file AbstractInterpretation.cpp.

{
    stat->startClk();
    utils = new AbsExtAPI(this);
    utils->collectCheckPoint();
 
    analyse();
    utils->checkPointAllSet();
    stat->endClk();
    stat->finializeStat();
    if (Options::PStat())
        stat->performStat();
    for (auto& detector: detectors)
        detector->reportBug();
}

shouldApplyNarrowing()

bool AbstractInterpretation::shouldApplyNarrowing ( const FunObjVar *  fun )

protected

Check if narrowing should be applied: always for regular loops, mode-dependent for recursion.

Definition at line 130 of file AELoopRecursion.cpp.

{
    // Non-recursive functions (regular loops): always apply narrowing
    if (!isRecursiveFun(fun))
        return true;
 
    // Recursive functions: WIDEN_NARROW applies narrowing, WIDEN_ONLY does not
    // TOP mode exits early in handleLoopOrRecursion, so should not reach here
    switch (Options::HandleRecur())
    {
    case TOP:
        assert(false && "TOP mode should not reach narrowing phase for recursive functions");
        return false;
    case WIDEN_ONLY:
        return false;  // Skip narrowing for recursive functions
    case WIDEN_NARROW:
        return true;   // Apply narrowing for recursive functions
    default:
        assert(false && "Unknown recursion handling mode");
        return false;
    }
}

skipRecursionWithTop()

void AbstractInterpretation::skipRecursionWithTop ( const CallICFGNode *  callNode )

privatevirtual

TOP mode for recursive calls: skip the function body entirely and conservatively set all reachable stores and the return value to TOP.

Definition at line 54 of file AELoopRecursion.cpp.

{
    const RetICFGNode *retNode = callNode->getRetICFGNode();
 
    // 1. Set return value to TOP
    if (retNode->getSVFStmts().size() > 0)
    {
        if (const RetPE *retPE = SVFUtil::dyn_cast<RetPE>(*retNode->getSVFStmts().begin()))
        {
            if (!retPE->getLHSVar()->isPointer() &&
                    !retPE->getLHSVar()->isConstDataOrAggDataButNotNullPtr())
                updateAbsValue(retPE->getLHSVar(), IntervalValue::top(), callNode);
        }
    }
 
    // 2. Set all stores in callee's reachable BBs to TOP
    if (retNode->getOutEdges().size() > 1)
    {
        updateAbsState(retNode, getAbsState(callNode));
        return;
    }
    for (const SVFBasicBlock* bb : callNode->getCalledFunction()->getReachableBBs())
    {
        for (const ICFGNode* node : bb->getICFGNodeList())
        {
            for (const SVFStmt* stmt : node->getSVFStmts())
            {
                if (const StoreStmt* store = SVFUtil::dyn_cast<StoreStmt>(stmt))
                {
                    const SVFVar* rhsVar = store->getRHSVar();
                    if (!rhsVar->isPointer() && !rhsVar->isConstDataOrAggDataButNotNullPtr())
                    {
                        const AbstractValue& addrs = getAbsValue(store->getLHSVar(), callNode);
                        if (addrs.isAddr())
                        {
                            AbstractState& as = getAbsState(callNode);
                            for (const auto& addr : addrs.getAddrs())
                                as.store(addr, IntervalValue::top());
                        }
                    }
                }
            }
        }
    }
 
    // 3. Copy callNode's state to retNode
    updateAbsState(retNode, getAbsState(callNode));
}

skipRecursiveCall()

bool AbstractInterpretation::skipRecursiveCall ( const CallICFGNode *  callNode )

private

Skip recursive callsites (within SCC); entry calls from outside SCC are not skipped.

Definition at line 112 of file AELoopRecursion.cpp.

{
    const FunObjVar* callee = getCallee(callNode);
    if (!callee)
        return false;
 
    // Non-recursive function: never skip, always inline
    if (!isRecursiveFun(callee))
        return false;
 
    // For recursive functions, skip only recursive callsites (within same SCC).
    // Entry calls (from outside SCC) are not skipped - they are inlined so that
    // handleLoopOrRecursion() can analyze the function body.
    // This applies uniformly to all modes (TOP/WIDEN_ONLY/WIDEN_NARROW).
    return isRecursiveCallSite(callNode, callee);
}

storeValue()

void AbstractInterpretation::storeValue ( const ValVar *  pointer, const AbstractValue &  val, const ICFGNode *  node  )

virtual

Reimplemented in SVF::FullSparseAbstractInterpretation.

Definition at line 359 of file AbstractStateManager.cpp.

{
    const AbstractValue& ptrVal = getAbsValue(pointer, node);
    AbstractState& as = getAbsState(node);
    for (auto addr : ptrVal.getAddrs())
    {
        // Null and black-hole addresses have no backing object.
        if (AbstractState::isNullOrBlackHoleAddr(addr))
            continue;
        updateAbsValue(svfir->getSVFVar(as.getIDFromAddr(addr)), val, node);
    }
}

updateAbsState()

void AbstractInterpretation::updateAbsState ( const ICFGNode *  node, const AbstractState &  state  )

virtual

Replace the state at node. Sparse subclasses replace only the ObjVar map (ValVars live at def-sites).

Reimplemented in SVF::SemiSparseAbstractInterpretation.

Definition at line 54 of file AbstractStateManager.cpp.

{
    abstractTrace[node] = state;
}

updateAbsValue() [1/3]

void AbstractInterpretation::updateAbsValue ( const ObjVar *  var, const AbstractValue &  val, const ICFGNode *  node  )

virtual

Reimplemented in SVF::SemiSparseAbstractInterpretation.

Definition at line 144 of file AbstractStateManager.cpp.

{
    AbstractState& as = getAbsState(node);
    u32_t addr = AbstractState::getVirtualMemAddress(var->getId());
    as.store(addr, val);
}

updateAbsValue() [2/3]

void AbstractInterpretation::updateAbsValue ( const SVFVar *  var, const AbstractValue &  val, const ICFGNode *  node  )

virtual

Reimplemented in SVF::SemiSparseAbstractInterpretation.

Definition at line 151 of file AbstractStateManager.cpp.

{
    if (const ObjVar* objVar = SVFUtil::dyn_cast<ObjVar>(var))
        updateAbsValue(objVar, val, node);
    else if (const ValVar* valVar = SVFUtil::dyn_cast<ValVar>(var))
        updateAbsValue(valVar, val, node);
    else
        assert(false && "Unknown SVFVar kind");
}

updateAbsValue() [3/3]

void AbstractInterpretation::updateAbsValue ( const ValVar *  var, const AbstractValue &  val, const ICFGNode *  node  )

virtual

Write a variable's abstract value. Sparse subclasses re-route ValVar writes to the def-site.

Reimplemented in SVF::SemiSparseAbstractInterpretation, and SVF::SemiSparseAbstractInterpretation.

Definition at line 139 of file AbstractStateManager.cpp.

{
    abstractTrace[node][var->getId()] = val;
}

updateStateOnAddr()

void AbstractInterpretation::updateStateOnAddr ( const AddrStmt *  addr )

private

Definition at line 1053 of file AbstractInterpretation.cpp.

{
    const ICFGNode* node = addr->getICFGNode();
    // initObjVar mutates _varToAbsVal/_addrToAbsVal directly, so we need
    // mutable access; route via the manager.
    AbstractState& as = getAbsState(node);
    as.initObjVar(SVFUtil::cast<ObjVar>(addr->getRHSVar()));
    // AddrStmt: lhs(ValVar) = &rhs(ObjVar).
    // as[rhsId] stores the ObjVar's virtual address in _varToVal,
    // NOT the object contents. So we must use as[] directly for ObjVar.
    u32_t rhsId = addr->getRHSVarID();
    if (addr->getRHSVar()->getType()->getKind() == SVFType::SVFIntegerTy)
        as[rhsId].getInterval().meet_with(utils->getRangeLimitFromType(addr->getRHSVar()->getType()));
    // LHS is a ValVar (pointer), write through the API
    updateAbsValue(addr->getLHSVar(), as[rhsId], node);
}

updateStateOnBinary()

void AbstractInterpretation::updateStateOnBinary ( const BinaryOPStmt *  binary )

private

Definition at line 1071 of file AbstractInterpretation.cpp.

{
    const ICFGNode* node = binary->getICFGNode();
    // Treat bottom (uninitialized) operands as top for soundness
    const AbstractValue& op0Val = getAbsValue(binary->getOpVar(0), node);
    const AbstractValue& op1Val = getAbsValue(binary->getOpVar(1), node);
    IntervalValue lhs = op0Val.getInterval().isBottom() ? IntervalValue::top() : op0Val.getInterval();
    IntervalValue rhs = op1Val.getInterval().isBottom() ? IntervalValue::top() : op1Val.getInterval();
    IntervalValue resVal;
    switch (binary->getOpcode())
    {
    case BinaryOPStmt::Add:
    case BinaryOPStmt::FAdd:
        resVal = (lhs + rhs);
        break;
    case BinaryOPStmt::Sub:
    case BinaryOPStmt::FSub:
        resVal = (lhs - rhs);
        break;
    case BinaryOPStmt::Mul:
    case BinaryOPStmt::FMul:
        resVal = (lhs * rhs);
        break;
    case BinaryOPStmt::SDiv:
    case BinaryOPStmt::FDiv:
    case BinaryOPStmt::UDiv:
        resVal = (lhs / rhs);
        break;
    case BinaryOPStmt::SRem:
    case BinaryOPStmt::FRem:
    case BinaryOPStmt::URem:
        resVal = (lhs % rhs);
        break;
    case BinaryOPStmt::Xor:
        resVal = (lhs ^ rhs);
        break;
    case BinaryOPStmt::And:
        resVal = (lhs & rhs);
        break;
    case BinaryOPStmt::Or:
        resVal = (lhs | rhs);
        break;
    case BinaryOPStmt::AShr:
        resVal = (lhs >> rhs);
        break;
    case BinaryOPStmt::Shl:
        resVal = (lhs << rhs);
        break;
    case BinaryOPStmt::LShr:
        resVal = (lhs >> rhs);
        break;
    default:
        assert(false && "undefined binary: ");
    }
    updateAbsValue(binary->getRes(), resVal, node);
}

updateStateOnCall()

void AbstractInterpretation::updateStateOnCall ( const CallPE *  callPE )

private

Handle CallPE: phi-like merging of actual parameters from all call sites into the formal parameter at FunEntryICFGNode (e.g., formal = join(actual1@cs1, actual2@cs2, ...))

Definition at line 1028 of file AbstractInterpretation.cpp.

{
    const ICFGNode* node = callPE->getICFGNode();
    const SVFVar* res = callPE->getRes();
    AbstractValue rhs;
    for (u32_t i = 0; i < callPE->getOpVarNum(); i++)
    {
        const ICFGNode* opICFGNode = callPE->getOpCallICFGNode(i);
        if (hasAbsState(opICFGNode))
        {
            const AbstractValue& opVal = getAbsValue(callPE->getOpVar(i), opICFGNode);
            rhs.join_with(opVal);
        }
    }
    updateAbsValue(res, rhs, node);
}

updateStateOnCmp()

void AbstractInterpretation::updateStateOnCmp ( const CmpStmt *  cmp )

private

Definition at line 1234 of file AbstractInterpretation.cpp.

{
    const ICFGNode* node = cmp->getICFGNode();
    const AbstractValue& lhsValue = getAbsValue(cmp->getOpVar(0), node);
    const AbstractValue& rhsValue = getAbsValue(cmp->getOpVar(1), node);
    const bool pointerCmp = cmp->getOpVar(0)->getType()->isPointerTy();
    assert(pointerCmp == cmp->getOpVar(1)->getType()->isPointerTy() &&
           "CmpStmt operands must belong to the same value domain");
 
    IntervalValue result;
    if (pointerCmp)
    {
        result = evaluatePointerCmp(cmp->getPredicate(), lhsValue.getAddrs(),
                                    rhsValue.getAddrs());
    }
    else
    {
        const IntervalValue lhs = lhsValue.isInterval()
                                  ? lhsValue.getInterval()
                                  : IntervalValue::top();
        const IntervalValue rhs = rhsValue.isInterval()
                                  ? rhsValue.getInterval()
                                  : IntervalValue::top();
        result = evaluateIntervalCmp(cmp->getPredicate(), lhs, rhs);
    }
    updateAbsValue(cmp->getRes(), result, node);
}

updateStateOnCopy()

void AbstractInterpretation::updateStateOnCopy ( const CopyStmt *  copy )

private

Definition at line 1277 of file AbstractInterpretation.cpp.

{
    const ICFGNode* node = copy->getICFGNode();
    const SVFVar* lhsVar = copy->getLHSVar();
    const SVFVar* rhsVar = copy->getRHSVar();
 
    auto getZExtValue = [&](const SVFVar* var)
    {
        const SVFType* type = var->getType();
        if (SVFUtil::isa<SVFIntegerType>(type))
        {
            u32_t bits = type->getByteSize() * 8;
            const AbstractValue& val = getAbsValue(var, node);
            if (val.getInterval().is_numeral())
            {
                if (bits == 8)
                {
                    int8_t signed_i8_value = val.getInterval().getIntNumeral();
                    u32_t unsigned_value = static_cast<uint8_t>(signed_i8_value);
                    return IntervalValue(unsigned_value, unsigned_value);
                }
                else if (bits == 16)
                {
                    s16_t signed_i16_value = val.getInterval().getIntNumeral();
                    u32_t unsigned_value = static_cast<u16_t>(signed_i16_value);
                    return IntervalValue(unsigned_value, unsigned_value);
                }
                else if (bits == 32)
                {
                    s32_t signed_i32_value = val.getInterval().getIntNumeral();
                    u32_t unsigned_value = static_cast<u32_t>(signed_i32_value);
                    return IntervalValue(unsigned_value, unsigned_value);
                }
                else if (bits == 64)
                {
                    s64_t signed_i64_value = val.getInterval().getIntNumeral();
                    return IntervalValue((s64_t)signed_i64_value, (s64_t)signed_i64_value);
                }
                else
                    assert(false && "cannot support int type other than u8/16/32/64");
            }
            else
            {
                return IntervalValue::top();
            }
        }
        return IntervalValue::top();
    };
 
    auto getTruncValue = [&](const SVFVar* var, const SVFType* dstType)
    {
        const IntervalValue& itv = getAbsValue(var, node).getInterval();
        if(itv.isBottom()) return itv;
        s64_t int_lb = itv.lb().getIntNumeral();
        s64_t int_ub = itv.ub().getIntNumeral();
        u32_t dst_bits = dstType->getByteSize() * 8;
        if (dst_bits == 8)
        {
            int8_t s8_lb = static_cast<int8_t>(int_lb);
            int8_t s8_ub = static_cast<int8_t>(int_ub);
            if (s8_lb > s8_ub)
                return utils->getRangeLimitFromType(dstType);
            return IntervalValue(s8_lb, s8_ub);
        }
        else if (dst_bits == 16)
        {
            s16_t s16_lb = static_cast<s16_t>(int_lb);
            s16_t s16_ub = static_cast<s16_t>(int_ub);
            if (s16_lb > s16_ub)
                return utils->getRangeLimitFromType(dstType);
            return IntervalValue(s16_lb, s16_ub);
        }
        else if (dst_bits == 32)
        {
            s32_t s32_lb = static_cast<s32_t>(int_lb);
            s32_t s32_ub = static_cast<s32_t>(int_ub);
            if (s32_lb > s32_ub)
                return utils->getRangeLimitFromType(dstType);
            return IntervalValue(s32_lb, s32_ub);
        }
        else
        {
            assert(false && "cannot support dst int type other than u8/16/32");
            abort();
        }
    };
 
    const AbstractValue& rhsVal = getAbsValue(rhsVar, node);
 
    if (copy->getCopyKind() == CopyStmt::COPYVAL)
    {
        updateAbsValue(lhsVar, rhsVal, node);
    }
    else if (copy->getCopyKind() == CopyStmt::ZEXT)
    {
        updateAbsValue(lhsVar, getZExtValue(rhsVar), node);
    }
    else if (copy->getCopyKind() == CopyStmt::SEXT)
    {
        updateAbsValue(lhsVar, rhsVal.getInterval(), node);
    }
    else if (copy->getCopyKind() == CopyStmt::FPTOSI)
    {
        updateAbsValue(lhsVar, rhsVal.getInterval(), node);
    }
    else if (copy->getCopyKind() == CopyStmt::FPTOUI)
    {
        updateAbsValue(lhsVar, rhsVal.getInterval(), node);
    }
    else if (copy->getCopyKind() == CopyStmt::SITOFP)
    {
        updateAbsValue(lhsVar, rhsVal.getInterval(), node);
    }
    else if (copy->getCopyKind() == CopyStmt::UITOFP)
    {
        updateAbsValue(lhsVar, rhsVal.getInterval(), node);
    }
    else if (copy->getCopyKind() == CopyStmt::TRUNC)
    {
        updateAbsValue(lhsVar, getTruncValue(rhsVar, lhsVar->getType()), node);
    }
    else if (copy->getCopyKind() == CopyStmt::FPTRUNC)
    {
        updateAbsValue(lhsVar, rhsVal.getInterval(), node);
    }
    else if (copy->getCopyKind() == CopyStmt::INTTOPTR)
    {
        //insert nullptr
    }
    else if (copy->getCopyKind() == CopyStmt::PTRTOINT)
    {
        updateAbsValue(lhsVar, IntervalValue::top(), node);
    }
    else if (copy->getCopyKind() == CopyStmt::BITCAST)
    {
        if (rhsVal.isAddr())
            updateAbsValue(lhsVar, rhsVal, node);
    }
    else
        assert(false && "undefined copy kind");
}

updateStateOnGep()

void AbstractInterpretation::updateStateOnGep ( const GepStmt *  gep )

private

Definition at line 966 of file AbstractInterpretation.cpp.

{
    const ICFGNode* node = gep->getICFGNode();
    IntervalValue offsetPair = getGepElementIndex(gep);
    AddressValue gepAddrs = getGepObjAddrs(SVFUtil::cast<ValVar>(gep->getRHSVar()), offsetPair);
    updateAbsValue(gep->getLHSVar(), gepAddrs, node);
}

updateStateOnLoad()

void AbstractInterpretation::updateStateOnLoad ( const LoadStmt *  load )

private

Definition at line 1262 of file AbstractInterpretation.cpp.

{
    const ICFGNode* node = load->getICFGNode();
    AbstractValue loaded =
        loadValue(SVFUtil::cast<ValVar>(load->getRHSVar()), node);
    updateAbsValue(load->getLHSVar(), loaded, node);
}

updateStateOnPhi()

void AbstractInterpretation::updateStateOnPhi ( const PhiStmt *  phi )

private

Definition at line 993 of file AbstractInterpretation.cpp.

{
    const ICFGNode* icfgNode = phi->getICFGNode();
    AbstractValue rhs;
    for (u32_t i = 0; i < phi->getOpVarNum(); i++)
    {
        const ICFGNode* opICFGNode = phi->getOpICFGNode(i);
        if (hasAbsState(opICFGNode))
        {
            AbstractState tmpState = getAbsState(opICFGNode);
            const AbstractValue& opVal = getAbsValue(phi->getOpVar(i), opICFGNode);
            const ICFGEdge* edge = icfg->getICFGEdge(opICFGNode, icfgNode, ICFGEdge::IntraCF);
            if (edge)
            {
                const IntraCFGEdge* intraEdge = SVFUtil::cast<IntraCFGEdge>(edge);
                if (intraEdge->getCondition())
                {
                    if (isBranchEdgeFeasible(intraEdge, tmpState))
                        rhs.join_with(opVal);
                }
                else
                    rhs.join_with(opVal);
            }
            else
            {
                rhs.join_with(opVal);
            }
        }
    }
    updateAbsValue(phi->getRes(), rhs, icfgNode);
}

updateStateOnRet()

void AbstractInterpretation::updateStateOnRet ( const RetPE *  retPE )

private

Definition at line 1045 of file AbstractInterpretation.cpp.

{
    const ICFGNode* node = retPE->getICFGNode();
    const AbstractValue& rhsVal = getAbsValue(retPE->getRHSVar(), node);
    updateAbsValue(retPE->getLHSVar(), rhsVal, node);
}

updateStateOnSelect()

void AbstractInterpretation::updateStateOnSelect ( const SelectStmt *  select )

private

Definition at line 974 of file AbstractInterpretation.cpp.

{
    const ICFGNode* node = select->getICFGNode();
    const AbstractValue& condVal = getAbsValue(select->getCondition(), node);
    const AbstractValue& tVal = getAbsValue(select->getTrueValue(), node);
    const AbstractValue& fVal = getAbsValue(select->getFalseValue(), node);
    AbstractValue resVal;
    if (condVal.getInterval().is_numeral())
    {
        resVal = condVal.getInterval().is_zero() ? fVal : tVal;
    }
    else
    {
        resVal = tVal;
        resVal.join_with(fVal);
    }
    updateAbsValue(select->getRes(), resVal, node);
}

updateStateOnStore()

void AbstractInterpretation::updateStateOnStore ( const StoreStmt *  store )

private

Definition at line 1270 of file AbstractInterpretation.cpp.

{
    const ICFGNode* node = store->getICFGNode();
    AbstractValue val = getAbsValue(store->getRHSVar(), node);
    storeValue(SVFUtil::cast<ValVar>(store->getLHSVar()), val, node);
}

widenCycleState()

bool AbstractInterpretation::widenCycleState ( const AbstractState &  prev, const AbstractState &  cur, const ICFGCycleWTO *  cycle  )

protectedvirtual

Widen prev with cur; write the widened state to trace[cycle_head]. Returns true when next == prev (fixpoint). Semi-sparse subclass additionally scatters ValVars to their def-sites.

Reimplemented in SVF::SemiSparseAbstractInterpretation.

Definition at line 171 of file AELoopRecursion.cpp.

{
    AbstractState prev_copy = prev;
    AbstractState next = prev_copy.widening(cur);
    // Always write back (even at fixpoint) so cycle_head's trace holds the
    // widened state for the upcoming narrowing phase.
    const ICFGNode* cycle_head = cycle->head()->getICFGNode();
    abstractTrace[cycle_head] = next;
    return next == prev;
}

Friends And Related Symbol Documentation

AEAPI

friend class AEAPI

friend

Definition at line 63 of file AbstractInterpretation.h.

AEStat

friend class AEStat

friend

Definition at line 62 of file AbstractInterpretation.h.

BufOverflowDetector

friend class BufOverflowDetector

friend

Definition at line 64 of file AbstractInterpretation.h.

NullptrDerefDetector

friend class NullptrDerefDetector

friend

Definition at line 65 of file AbstractInterpretation.h.

Member Data Documentation

abstractTrace

Map<const ICFGNode*, AbstractState> SVF::AbstractInterpretation::abstractTrace

protected

per-node trace; owned here

Definition at line 347 of file AbstractInterpretation.h.

allAnalyzedNodes

Set<const ICFGNode*> SVF::AbstractInterpretation::allAnalyzedNodes

private

Definition at line 337 of file AbstractInterpretation.h.

api

AEAPI* SVF::AbstractInterpretation::api {nullptr}

private

Execution State, used to store the Interval Value of every SVF variable.

Definition at line 312 of file AbstractInterpretation.h.

{nullptr};

callGraph

CallGraph* SVF::AbstractInterpretation::callGraph

private

Definition at line 315 of file AbstractInterpretation.h.

detectors

std::vector<std::unique_ptr<AEDetector> > SVF::AbstractInterpretation::detectors

private

Definition at line 340 of file AbstractInterpretation.h.

func_map

Map<std::string, std::function<void(const CallICFGNode*)> > SVF::AbstractInterpretation::func_map

private

Definition at line 335 of file AbstractInterpretation.h.

icfg

ICFG* SVF::AbstractInterpretation::icfg

private

Definition at line 314 of file AbstractInterpretation.h.

moduleName

std::string SVF::AbstractInterpretation::moduleName

private

Definition at line 338 of file AbstractInterpretation.h.

preAnalysis

AEWTO* SVF::AbstractInterpretation::preAnalysis {nullptr}

protected

Definition at line 346 of file AbstractInterpretation.h.

{nullptr};

stat

AEStat* SVF::AbstractInterpretation::stat

private

Definition at line 316 of file AbstractInterpretation.h.

svfir

SVFIR* SVF::AbstractInterpretation::svfir {nullptr}

protected

Data and helpers reachable from SparseAbstractInterpretation.

Definition at line 345 of file AbstractInterpretation.h.

{nullptr};

utils

AbsExtAPI* SVF::AbstractInterpretation::utils

private

Definition at line 341 of file AbstractInterpretation.h.

---

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

• /home/runner/work/SVF/SVF/svf/include/AE/Svfexe/AbstractInterpretation.h
• /home/runner/work/SVF/SVF/svf/lib/AE/Svfexe/AbstractInterpretation.cpp
• /home/runner/work/SVF/SVF/svf/lib/AE/Svfexe/AbstractStateManager.cpp
• /home/runner/work/SVF/SVF/svf/lib/AE/Svfexe/AELoopRecursion.cpp