SVF::AbstractInterpretation Class Reference

AbstractInterpretation is same as Abstract Execution. More...

#include <AbstractInterpretation.h>

Public Types
typedef SCCDetection< PTACallGraph * >	CallGraphSCC

Public Member Functions
	AbstractInterpretation ()
	Constructor.
virtual void	runOnModule (ICFG *icfg)
virtual	~AbstractInterpretation ()
	Destructor.
void	analyse ()
	Program entry.
void	addDetector (std::unique_ptr< AEDetector > detector)

Static Public Member Functions
static AbstractInterpretation &	getAEInstance ()

Public Attributes
Set< const CallICFGNode * >	checkpoints

Private Member Functions
virtual void	handleGlobalNode ()
	Global ICFGNode is handled at the entry of the program,.
void	initWTO ()
	Mark recursive functions in the call graph.
bool	mergeStatesFromPredecessors (const ICFGNode *icfgNode)
bool	isBranchFeasible (const IntraCFGEdge *intraEdge, AbstractState &as)
virtual void	handleSingletonWTO (const ICFGSingletonWTO *icfgSingletonWto)
	handle instructions in svf basic blocks
virtual void	handleCallSite (const ICFGNode *node)
virtual void	handleCycleWTO (const ICFGCycleWTO *cycle)
	handle wto cycle (loop)
void	handleWTOComponents (const std::list< const ICFGWTOComp * > &wtoComps)
	Hanlde two types of WTO components (singleton and cycle)
void	handleWTOComponent (const ICFGWTOComp *wtoComp)
virtual void	handleSVFStatement (const SVFStmt *stmt)
virtual void	SkipRecursiveCall (const CallICFGNode *callnode)
bool	isCmpBranchFeasible (const CmpStmt *cmpStmt, s64_t succ, AbstractState &as)
bool	isSwitchBranchFeasible (const SVFVar *var, s64_t succ, AbstractState &as)
void	collectCheckPoint ()
void	checkPointAllSet ()
void	updateStateOnAddr (const AddrStmt *addr)
void	updateStateOnBinary (const BinaryOPStmt *binary)
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)
AbstractState &	getAbsStateFromTrace (const ICFGNode *node)
bool	hasAbsStateFromTrace (const ICFGNode *node)
AbsExtAPI *	getUtils ()
virtual bool	isExtCall (const CallICFGNode *callNode)
virtual void	extCallPass (const CallICFGNode *callNode)
virtual bool	isRecursiveCall (const CallICFGNode *callNode)
virtual void	recursiveCallPass (const CallICFGNode *callNode)
virtual bool	isDirectCall (const CallICFGNode *callNode)
virtual void	directCallFunPass (const CallICFGNode *callNode)
virtual bool	isIndirectCall (const CallICFGNode *callNode)
virtual void	indirectCallFunPass (const CallICFGNode *callNode)

Private Attributes
SVFIR *	svfir
	protected data members, also used in subclasses
AEAPI *	api {nullptr}
	Execution State, used to store the Interval Value of every SVF variable.
ICFG *	icfg
AEStat *	stat
std::vector< const CallICFGNode * >	callSiteStack
Map< const CallGraphNode *, ICFGWTO * >	funcToWTO
Set< const CallGraphNode * >	recursiveFuns
Map< std::string, std::function< void(const CallICFGNode *)> >	func_map
Map< const ICFGNode *, AbstractState >	abstractTrace
std::string	moduleName
std::vector< std::unique_ptr< AEDetector > >	detectors
AbsExtAPI *	utils
Map< s32_t, s32_t >	_reverse_predicate
Map< s32_t, s32_t >	_switch_lhsrhs_predicate

Friends
class	AEStat
class	AEAPI
class	BufOverflowDetector

Detailed Description

AbstractInterpretation is same as Abstract Execution.

Definition at line 102 of file AbstractInterpretation.h.

Member Typedef Documentation

CallGraphSCC

typedef SCCDetection<PTACallGraph*> SVF::AbstractInterpretation::CallGraphSCC

Definition at line 109 of file AbstractInterpretation.h.

Constructor & Destructor Documentation

AbstractInterpretation()

AbstractInterpretation::AbstractInterpretation

(

)

Constructor.

Definition at line 61 of file AbstractInterpretation.cpp.

{
    stat = new AEStat(this);
}

~AbstractInterpretation()

AbstractInterpretation::~AbstractInterpretation ( )

virtual

Destructor.

Definition at line 66 of file AbstractInterpretation.cpp.

{
    delete stat;
    for (auto it: funcToWTO)
        delete it.second;
 
}

Member Function Documentation

addDetector()

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

inline

Definition at line 127 of file AbstractInterpretation.h.

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

analyse()

void AbstractInterpretation::analyse

(

)

Program entry.

Definition at line 103 of file AbstractInterpretation.cpp.

{
    initWTO();
    // handle Global ICFGNode of SVFModule
    handleGlobalNode();
    getAbsStateFromTrace(
        icfg->getGlobalICFGNode())[PAG::getPAG()->getBlkPtr()] = IntervalValue::top();
    if (const CallGraphNode* cgn = svfir->getCallGraph()->getCallGraphNode("main"))
    {
        ICFGWTO* wto = funcToWTO[cgn];
        handleWTOComponents(wto->getWTOComponents());
    }
}

checkPointAllSet()

void AbstractInterpretation::checkPointAllSet ( )

private

Definition at line 951 of file AbstractInterpretation.cpp.

{
    if (checkpoints.size() == 0)
    {
        return;
    }
    else
    {
        SVFUtil::errs() << SVFUtil::errMsg("At least one svf_assert has not been checked!!") << "\n";
        for (const CallICFGNode* call: checkpoints)
            SVFUtil::errs() << call->toString() + "\n";
        assert(false);
    }
 
}

collectCheckPoint()

void AbstractInterpretation::collectCheckPoint ( )

private

Definition at line 920 of file AbstractInterpretation.cpp.

{
    // traverse every ICFGNode
    Set<std::string> ae_checkpoint_names = {"svf_assert"};
    Set<std::string> buf_checkpoint_names = {"UNSAFE_BUFACCESS", "SAFE_BUFACCESS"};
 
    for (auto it = svfir->getICFG()->begin(); it != svfir->getICFG()->end(); ++it)
    {
        const ICFGNode* node = it->second;
        if (const CallICFGNode *call = SVFUtil::dyn_cast<CallICFGNode>(node))
        {
            if (const SVFFunction *fun = call->getCalledFunction())
            {
                if (ae_checkpoint_names.find(fun->getName()) !=
                        ae_checkpoint_names.end())
                {
                    checkpoints.insert(call);
                }
                if (Options::BufferOverflowCheck())
                {
                    if (buf_checkpoint_names.find(fun->getName()) !=
                            buf_checkpoint_names.end())
                    {
                        checkpoints.insert(call);
                    }
                }
            }
        }
    }
}

directCallFunPass()

void AbstractInterpretation::directCallFunPass ( const CallICFGNode *  callNode )

privatevirtual

Definition at line 618 of file AbstractInterpretation.cpp.

{
    AbstractState& as = getAbsStateFromTrace(callNode);
    callSiteStack.push_back(callNode);
 
    abstractTrace[callNode] = as;
 
    const SVFFunction *callfun =callNode->getCalledFunction();
    ICFGWTO* wto = funcToWTO[callfun->getCallGraphNode()];
    handleWTOComponents(wto->getWTOComponents());
 
    callSiteStack.pop_back();
    // handle Ret node
    const RetICFGNode *retNode = callNode->getRetICFGNode();
    // resume ES to callnode
    abstractTrace[retNode] = abstractTrace[callNode];
}

extCallPass()

void AbstractInterpretation::extCallPass ( const CallICFGNode *  callNode )

privatevirtual

Definition at line 571 of file AbstractInterpretation.cpp.

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

getAbsStateFromTrace()

AbstractState & SVF::AbstractInterpretation::getAbsStateFromTrace ( const ICFGNode *  node )

inlineprivate

Definition at line 258 of file AbstractInterpretation.h.

    {
        const ICFGNode* repNode = icfg->getRepNode(node);
        if (abstractTrace.count(repNode) == 0)
        {
            assert(0 && "No preAbsTrace for this node");
        }
        else
        {
            return abstractTrace[repNode];
        }
    }

getAEInstance()

static AbstractInterpretation & SVF::AbstractInterpretation::getAEInstance ( )

inlinestatic

Definition at line 121 of file AbstractInterpretation.h.

    {
        static AbstractInterpretation instance;
        return instance;
    }

getUtils()

AbsExtAPI * SVF::AbstractInterpretation::getUtils ( )

inlineprivate

Definition at line 277 of file AbstractInterpretation.h.

    {
        return utils;
    }

handleCallSite()

void AbstractInterpretation::handleCallSite ( const ICFGNode *  node )

privatevirtual

handle call node in ICFGNode

Parameters

node	ICFGNode which has a single CallICFGNode

Definition at line 535 of file AbstractInterpretation.cpp.

{
    if (const CallICFGNode* callNode = SVFUtil::dyn_cast<CallICFGNode>(node))
    {
        if (isExtCall(callNode))
        {
            extCallPass(callNode);
        }
        else if (isRecursiveCall(callNode))
        {
            recursiveCallPass(callNode);
        }
        else if (isDirectCall(callNode))
        {
            directCallFunPass(callNode);
        }
        else if (isIndirectCall(callNode))
        {
            indirectCallFunPass(callNode);
        }
        else
        {
            assert(false && "implement this part");
        }
    }
    else
    {
        assert (false && "it is not call node");
    }
}

handleCycleWTO()

void AbstractInterpretation::handleCycleWTO ( const ICFGCycleWTO *  cycle )

privatevirtual

handle wto cycle (loop)

handle wto cycle (loop)

Parameters

cycle

WTOCycle which has weak topo order of basic blocks and nested cycles

Definition at line 672 of file AbstractInterpretation.cpp.

{
    const ICFGNode* cycle_head = cycle->head()->getICFGNode();
    // Flag to indicate if we are in the increasing phase
    bool increasing = true;
    // Infinite loop until a fixpoint is reached,
    for (u32_t cur_iter = 0;; cur_iter++)
    {
        // Start widening or narrowing if cur_iter >= widen threshold (widen delay)
        if (cur_iter >= Options::WidenDelay())
        {
            // Widen or narrow after processing cycle head node
            AbstractState prev_head_state = abstractTrace[cycle_head];
            handleWTOComponent(cycle->head());
            AbstractState cur_head_state = abstractTrace[cycle_head];
            if (increasing)
            {
                // Widening phase
                abstractTrace[cycle_head] = prev_head_state.widening(cur_head_state);
                if (abstractTrace[cycle_head] == prev_head_state)
                {
                    increasing = false;
                    continue;
                }
            }
            else
            {
                // Widening's fixpoint reached in the widening phase, switch to narrowing
                abstractTrace[cycle_head] = prev_head_state.narrowing(cur_head_state);
                if (abstractTrace[cycle_head] == prev_head_state)
                {
                    // Narrowing's fixpoint reached in the narrowing phase, exit loop
                    break;
                }
            }
        }
        else
        {
            // Handle the cycle head
            handleSingletonWTO(cycle->head());
        }
        // Handle the cycle body
        handleWTOComponents(cycle->getWTOComponents());
    }
}

handleGlobalNode()

void AbstractInterpretation::handleGlobalNode ( )

privatevirtual

Global ICFGNode is handled at the entry of the program,.

handle global node

Definition at line 118 of file AbstractInterpretation.cpp.

{
    const ICFGNode* node = icfg->getGlobalICFGNode();
    abstractTrace[node] = AbstractState();
    abstractTrace[node][SymbolTableInfo::NullPtr] = AddressValue();
    // Global Node, we just need to handle addr, load, store, copy and gep
    for (const SVFStmt *stmt: node->getSVFStmts())
    {
        handleSVFStatement(stmt);
    }
}

handleSingletonWTO()

void AbstractInterpretation::handleSingletonWTO ( const ICFGSingletonWTO *  icfgSingletonWto )

privatevirtual

handle instructions in svf basic blocks

handle instructions in ICFGSingletonWTO

Parameters

block

basic block that has one instruction or a series of instructions

Definition at line 476 of file AbstractInterpretation.cpp.

{
    const ICFGNode* node = icfgSingletonWto->getICFGNode();
    stat->getBlockTrace()++;
 
    std::deque<const ICFGNode*> worklist;
 
    const std::vector<const ICFGNode*>& worklist_vec = icfg->getSubNodes(node);
    for (auto it = worklist_vec.begin(); it != worklist_vec.end(); ++it)
    {
        const ICFGNode* curNode = *it;
        stat->getICFGNodeTrace()++;
        // handle SVF Stmt
        for (const SVFStmt *stmt: curNode->getSVFStmts())
        {
            handleSVFStatement(stmt);
        }
        // inlining the callee by calling handleFunc for the callee function
        if (const CallICFGNode* callnode = SVFUtil::dyn_cast<CallICFGNode>(curNode))
        {
            handleCallSite(callnode);
        }
        for (auto& detector: detectors)
            detector->detect(getAbsStateFromTrace(node), node);
        stat->countStateSize();
    }
}

handleSVFStatement()

void AbstractInterpretation::handleSVFStatement ( const SVFStmt *  stmt )

privatevirtual

handle SVF Statement like CmpStmt, CallStmt, GepStmt, LoadStmt, StoreStmt, etc.

Parameters

stmt	SVFStatement which is a value flow of instruction

Definition at line 718 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");
}

handleWTOComponent()

void AbstractInterpretation::handleWTOComponent ( const ICFGWTOComp *  wtoComp )

private

Definition at line 515 of file AbstractInterpretation.cpp.

{
    if (const ICFGSingletonWTO* node = SVFUtil::dyn_cast<ICFGSingletonWTO>(wtoNode))
    {
        if (mergeStatesFromPredecessors(node->getICFGNode()))
            handleSingletonWTO(node);
    }
    // Handle WTO cycles
    else if (const ICFGCycleWTO* cycle = SVFUtil::dyn_cast<ICFGCycleWTO>(wtoNode))
    {
        if (mergeStatesFromPredecessors(cycle->head()->getICFGNode()))
            handleCycleWTO(cycle);
    }
    // Assert false for unknown WTO types
    else
    {
        assert(false && "unknown WTO type!");
    }
}

handleWTOComponents()

void AbstractInterpretation::handleWTOComponents ( const std::list< const ICFGWTOComp * > &  wtoComps )

private

Hanlde two types of WTO components (singleton and cycle)

Definition at line 507 of file AbstractInterpretation.cpp.

{
    for (const ICFGWTOComp* wtoNode : wtoComps)
    {
        handleWTOComponent(wtoNode);
    }
}

hasAbsStateFromTrace()

bool SVF::AbstractInterpretation::hasAbsStateFromTrace ( const ICFGNode *  node )

inlineprivate

Definition at line 271 of file AbstractInterpretation.h.

    {
        const ICFGNode* repNode = icfg->getRepNode(node);
        return abstractTrace.count(repNode) != 0;
    }

indirectCallFunPass()

void AbstractInterpretation::indirectCallFunPass ( const CallICFGNode *  callNode )

privatevirtual

Definition at line 642 of file AbstractInterpretation.cpp.

{
    AbstractState& as = getAbsStateFromTrace(callNode);
    const auto callsiteMaps = svfir->getIndirectCallsites();
    NodeID call_id = callsiteMaps.at(callNode);
    if (!as.inVarToAddrsTable(call_id))
    {
        return;
    }
    AbstractValue Addrs = as[call_id];
    NodeID addr = *Addrs.getAddrs().begin();
    SVFVar *func_var = svfir->getGNode(AbstractState::getInternalID(addr));
    if(const FunObjVar*funObjVar = SVFUtil::dyn_cast<FunObjVar>(func_var))
    {
        const CallGraphNode* callfun = funObjVar->getCallGraphNode();
        callSiteStack.push_back(callNode);
        abstractTrace[callNode] = as;
 
        ICFGWTO* wto = funcToWTO[callfun];
        handleWTOComponents(wto->getWTOComponents());
        callSiteStack.pop_back();
        // handle Ret node
        const RetICFGNode* retNode = callNode->getRetICFGNode();
        abstractTrace[retNode] = abstractTrace[callNode];
    }
}

initWTO()

void AbstractInterpretation::initWTO ( )

private

Mark recursive functions in the call graph.

This function identifies and marks recursive functions in the call graph. It does this by detecting cycles in the call graph's strongly connected components (SCC). Any function found to be part of a cycle is marked as recursive.

Definition at line 81 of file AbstractInterpretation.cpp.

{
    AndersenWaveDiff* ander = AndersenWaveDiff::createAndersenWaveDiff(svfir);
    // Detect if the call graph has cycles by finding its strongly connected components (SCC)
    Andersen::CallGraphSCC* callGraphScc = ander->getCallGraphSCC();
    callGraphScc->find();
    CallGraph* svfirCallGraph = PAG::getPAG()->getCallGraph();
 
    // Iterate through the call graph
    for (auto it = svfirCallGraph->begin(); it != svfirCallGraph->end(); it++)
    {
        // Check if the current function is part of a cycle
        if (callGraphScc->isInCycle(it->second->getId()))
            recursiveFuns.insert(it->second); // Mark the function as recursive
        if (it->second->getFunction()->isDeclaration())
            continue;
        auto* wto = new ICFGWTO(icfg, icfg->getFunEntryICFGNode(it->second->getFunction()));
        wto->init();
        funcToWTO[it->second] = wto;
    }
}

isBranchFeasible()

bool AbstractInterpretation::isBranchFeasible ( const IntraCFGEdge *  intraEdge, AbstractState &  as  )

private

Check if execution state exist at the branch edge

Parameters

intraEdge

the edge from CmpStmt to the next node

Returns

if this edge is feasible

Definition at line 448 of file AbstractInterpretation.cpp.

{
    const SVFVar *cmpVar = intraEdge->getCondition();
    if (cmpVar->getInEdges().empty())
    {
        return isSwitchBranchFeasible(cmpVar,
                                      intraEdge->getSuccessorCondValue(), as);
    }
    else
    {
        assert(!cmpVar->getInEdges().empty() &&
               "no in edges?");
        SVFStmt *cmpVarInStmt = *cmpVar->getInEdges().begin();
        if (const CmpStmt *cmpStmt = SVFUtil::dyn_cast<CmpStmt>(cmpVarInStmt))
        {
            return isCmpBranchFeasible(cmpStmt,
                                       intraEdge->getSuccessorCondValue(), as);
        }
        else
        {
            return isSwitchBranchFeasible(
                       cmpVar, intraEdge->getSuccessorCondValue(), as);
        }
    }
    return true;
}

isCmpBranchFeasible()

bool AbstractInterpretation::isCmpBranchFeasible ( const CmpStmt *  cmpStmt, s64_t  succ, AbstractState &  as  )

private

Check if this cmpStmt and succ are satisfiable to the execution state.

Parameters

cmpStmt	CmpStmt is a conditional branch statement
succ	the value of cmpStmt (True or False)

Returns

if this ICFGNode has preceding execution state

Definition at line 183 of file AbstractInterpretation.cpp.

{
    AbstractState new_es = as;
    // get cmp stmt's op0, op1, and predicate
    NodeID op0 = cmpStmt->getOpVarID(0);
    NodeID op1 = cmpStmt->getOpVarID(1);
    NodeID res_id = cmpStmt->getResID();
    s32_t predicate = cmpStmt->getPredicate();
 
    // if op0 or op1 is undefined, return;
    // skip address compare
    if (new_es.inVarToAddrsTable(op0) || new_es.inVarToAddrsTable(op1))
    {
        as = new_es;
        return true;
    }
    const LoadStmt *load_op0 = nullptr;
    const LoadStmt *load_op1 = nullptr;
    // get '%1 = load i32 s', and load inst may not exist
    SVFVar* loadVar0 = svfir->getGNode(op0);
    if (!loadVar0->getInEdges().empty())
    {
        SVFStmt *loadVar0InStmt = *loadVar0->getInEdges().begin();
        if (const LoadStmt *loadStmt = SVFUtil::dyn_cast<LoadStmt>(loadVar0InStmt))
        {
            load_op0 = loadStmt;
        }
        else if (const CopyStmt *copyStmt = SVFUtil::dyn_cast<CopyStmt>(loadVar0InStmt))
        {
            loadVar0 = svfir->getGNode(copyStmt->getRHSVarID());
            if (!loadVar0->getInEdges().empty())
            {
                SVFStmt *loadVar0InStmt2 = *loadVar0->getInEdges().begin();
                if (const LoadStmt *loadStmt = SVFUtil::dyn_cast<LoadStmt>(loadVar0InStmt2))
                {
                    load_op0 = loadStmt;
                }
            }
        }
    }
 
    SVFVar* loadVar1 = svfir->getGNode(op1);
    if (!loadVar1->getInEdges().empty())
    {
        SVFStmt *loadVar1InStmt = *loadVar1->getInEdges().begin();
        if (const LoadStmt *loadStmt = SVFUtil::dyn_cast<LoadStmt>(loadVar1InStmt))
        {
            load_op1 = loadStmt;
        }
        else if (const CopyStmt *copyStmt = SVFUtil::dyn_cast<CopyStmt>(loadVar1InStmt))
        {
            loadVar1 = svfir->getGNode(copyStmt->getRHSVarID());
            if (!loadVar1->getInEdges().empty())
            {
                SVFStmt *loadVar1InStmt2 = *loadVar1->getInEdges().begin();
                if (const LoadStmt *loadStmt = SVFUtil::dyn_cast<LoadStmt>(loadVar1InStmt2))
                {
                    load_op1 = loadStmt;
                }
            }
        }
    }
    // for const X const, we may get concrete resVal instantly
    // for var X const, we may get [0,1] if the intersection of var and const is not empty set
    IntervalValue resVal = new_es[res_id].getInterval();
    resVal.meet_with(IntervalValue((s64_t) succ, succ));
    // If Var X const generates bottom value, it means this branch path is not feasible.
    if (resVal.isBottom())
    {
        return false;
    }
 
    bool b0 = new_es[op0].getInterval().is_numeral();
    bool b1 = new_es[op1].getInterval().is_numeral();
 
    // if const X var, we should reverse op0 and op1.
    if (b0 && !b1)
    {
        std::swap(op0, op1);
        std::swap(load_op0, load_op1);
        predicate = _switch_lhsrhs_predicate[predicate];
    }
    else
    {
        // if var X var, we cannot preset the branch condition to infer the intervals of var0,var1
        if (!b0 && !b1)
        {
            as = new_es;
            return true;
        }
        // if const X const, we can instantly get the resVal
        else if (b0 && b1)
        {
            as = new_es;
            return true;
        }
    }
    // if cmp is 'var X const == false', we should reverse predicate 'var X' const == true'
    // X' is reverse predicate of X
    if (succ == 0)
    {
        predicate = _reverse_predicate[predicate];
    }
    else {}
    // change interval range according to the compare predicate
    AddressValue addrs;
    if(load_op0 && new_es.inVarToAddrsTable(load_op0->getRHSVarID()))
        addrs = new_es[load_op0->getRHSVarID()].getAddrs();
 
    IntervalValue &lhs = new_es[op0].getInterval(), &rhs = new_es[op1].getInterval();
    switch (predicate)
    {
    case CmpStmt::Predicate::ICMP_EQ:
    case CmpStmt::Predicate::FCMP_OEQ:
    case CmpStmt::Predicate::FCMP_UEQ:
    {
        // Var == Const, so [var.lb, var.ub].meet_with(const)
        lhs.meet_with(rhs);
        // if lhs is register value, we should also change its mem obj
        for (const auto &addr: addrs)
        {
            NodeID objId = new_es.getInternalID(addr);
            if (new_es.inAddrToValTable(objId))
            {
                new_es.load(addr).meet_with(rhs);
            }
        }
        break;
    }
    case CmpStmt::Predicate::ICMP_NE:
    case CmpStmt::Predicate::FCMP_ONE:
    case CmpStmt::Predicate::FCMP_UNE:
        // Compliment set
        break;
    case CmpStmt::Predicate::ICMP_UGT:
    case CmpStmt::Predicate::ICMP_SGT:
    case CmpStmt::Predicate::FCMP_OGT:
    case CmpStmt::Predicate::FCMP_UGT:
        // Var > Const, so [var.lb, var.ub].meet_with([Const+1, +INF])
        lhs.meet_with(IntervalValue(rhs.lb() + 1, IntervalValue::plus_infinity()));
        // if lhs is register value, we should also change its mem obj
        for (const auto &addr: addrs)
        {
            NodeID objId = new_es.getInternalID(addr);
            if (new_es.inAddrToValTable(objId))
            {
                new_es.load(addr).meet_with(
                    IntervalValue(rhs.lb() + 1, IntervalValue::plus_infinity()));
            }
        }
        break;
    case CmpStmt::Predicate::ICMP_UGE:
    case CmpStmt::Predicate::ICMP_SGE:
    case CmpStmt::Predicate::FCMP_OGE:
    case CmpStmt::Predicate::FCMP_UGE:
    {
        // Var >= Const, so [var.lb, var.ub].meet_with([Const, +INF])
        lhs.meet_with(IntervalValue(rhs.lb(), IntervalValue::plus_infinity()));
        // if lhs is register value, we should also change its mem obj
        for (const auto &addr: addrs)
        {
            NodeID objId = new_es.getInternalID(addr);
            if (new_es.inAddrToValTable(objId))
            {
                new_es.load(addr).meet_with(
                    IntervalValue(rhs.lb(), IntervalValue::plus_infinity()));
            }
        }
        break;
    }
    case CmpStmt::Predicate::ICMP_ULT:
    case CmpStmt::Predicate::ICMP_SLT:
    case CmpStmt::Predicate::FCMP_OLT:
    case CmpStmt::Predicate::FCMP_ULT:
    {
        // Var < Const, so [var.lb, var.ub].meet_with([-INF, const.ub-1])
        lhs.meet_with(IntervalValue(IntervalValue::minus_infinity(), rhs.ub() - 1));
        // if lhs is register value, we should also change its mem obj
        for (const auto &addr: addrs)
        {
            NodeID objId = new_es.getInternalID(addr);
            if (new_es.inAddrToValTable(objId))
            {
                new_es.load(addr).meet_with(
                    IntervalValue(IntervalValue::minus_infinity(), rhs.ub() - 1));
            }
        }
        break;
    }
    case CmpStmt::Predicate::ICMP_ULE:
    case CmpStmt::Predicate::ICMP_SLE:
    case CmpStmt::Predicate::FCMP_OLE:
    case CmpStmt::Predicate::FCMP_ULE:
    {
        // Var <= Const, so [var.lb, var.ub].meet_with([-INF, const.ub])
        lhs.meet_with(IntervalValue(IntervalValue::minus_infinity(), rhs.ub()));
        // if lhs is register value, we should also change its mem obj
        for (const auto &addr: addrs)
        {
            NodeID objId = new_es.getInternalID(addr);
            if (new_es.inAddrToValTable(objId))
            {
                new_es.load(addr).meet_with(
                    IntervalValue(IntervalValue::minus_infinity(), rhs.ub()));
            }
        }
        break;
    }
    case CmpStmt::Predicate::FCMP_FALSE:
        break;
    case CmpStmt::Predicate::FCMP_TRUE:
        break;
    default:
        assert(false && "implement this part");
        abort();
    }
    as = new_es;
    return true;
}

isDirectCall()

bool AbstractInterpretation::isDirectCall ( const CallICFGNode *  callNode )

privatevirtual

Definition at line 610 of file AbstractInterpretation.cpp.

{
    const SVFFunction *callfun =callNode->getCalledFunction();
    if (!callfun)
        return false;
    else
        return funcToWTO.find(callfun->getCallGraphNode()) != funcToWTO.end();
}

isExtCall()

bool AbstractInterpretation::isExtCall ( const CallICFGNode *  callNode )

privatevirtual

Definition at line 566 of file AbstractInterpretation.cpp.

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

isIndirectCall()

bool AbstractInterpretation::isIndirectCall ( const CallICFGNode *  callNode )

privatevirtual

Definition at line 636 of file AbstractInterpretation.cpp.

{
    const auto callsiteMaps = svfir->getIndirectCallsites();
    return callsiteMaps.find(callNode) != callsiteMaps.end();
}

isRecursiveCall()

bool AbstractInterpretation::isRecursiveCall ( const CallICFGNode *  callNode )

privatevirtual

Definition at line 582 of file AbstractInterpretation.cpp.

{
    const SVFFunction *callfun = callNode->getCalledFunction();
    if (!callfun)
        return false;
    else
        return recursiveFuns.find(callfun->getCallGraphNode()) != recursiveFuns.end();
}

isSwitchBranchFeasible()

bool AbstractInterpretation::isSwitchBranchFeasible ( const SVFVar *  var, s64_t  succ, AbstractState &  as  )

private

Check if this SwitchInst and succ are satisfiable to the execution state.

Parameters

var	var in switch inst
succ	the case value of switch inst

Returns

if this ICFGNode has preceding execution state

Definition at line 404 of file AbstractInterpretation.cpp.

{
    AbstractState new_es = as;
    IntervalValue& switch_cond = new_es[var->getId()].getInterval();
    s64_t value = succ;
    FIFOWorkList<const SVFStmt*> workList;
    for (SVFStmt *cmpVarInStmt: var->getInEdges())
    {
        workList.push(cmpVarInStmt);
    }
    switch_cond.meet_with(IntervalValue(value, value));
    if (switch_cond.isBottom())
    {
        return false;
    }
    while(!workList.empty())
    {
        const SVFStmt* stmt = workList.pop();
        if (SVFUtil::isa<CopyStmt>(stmt))
        {
            IntervalValue& copy_cond = new_es[var->getId()].getInterval();
            copy_cond.meet_with(IntervalValue(value, value));
        }
        else if (const LoadStmt* load = SVFUtil::dyn_cast<LoadStmt>(stmt))
        {
            if (new_es.inVarToAddrsTable(load->getRHSVarID()))
            {
                AddressValue &addrs = new_es[load->getRHSVarID()].getAddrs();
                for (const auto &addr: addrs)
                {
                    NodeID objId = new_es.getInternalID(addr);
                    if (new_es.inAddrToValTable(objId))
                    {
                        new_es.load(addr).meet_with(switch_cond);
                    }
                }
            }
        }
    }
    as = new_es;
    return true;
}

mergeStatesFromPredecessors()

bool AbstractInterpretation::mergeStatesFromPredecessors ( const ICFGNode *  icfgNode )

private

Check if execution state exist by merging states of predecessor nodes

Parameters

icfgNode

The icfg node to analyse

Returns

if this node has preceding execution state

get execution state by merging states of predecessor blocks Scenario 1: preblock --—(intraEdge)-—> block, join the preES of inEdges Scenario 2: preblock --—(callEdge)-—> block

Definition at line 133 of file AbstractInterpretation.cpp.

{
    std::vector<AbstractState> workList;
    AbstractState preAs;
    for (auto& edge: icfgNode->getInEdges())
    {
        if (abstractTrace.find(edge->getSrcNode()) != abstractTrace.end())
        {
            const IntraCFGEdge *intraCfgEdge = SVFUtil::dyn_cast<IntraCFGEdge>(edge);
            if (intraCfgEdge && intraCfgEdge->getCondition())
            {
                AbstractState tmpEs = abstractTrace[edge->getSrcNode()];
                if (isBranchFeasible(intraCfgEdge, tmpEs))
                {
                    workList.push_back(tmpEs);
                }
                else
                {
                    // do nothing
                }
            }
            else
            {
                workList.push_back(abstractTrace[edge->getSrcNode()]);
            }
        }
        else
        {
 
        }
    }
    if (workList.size() == 0)
    {
        return false;
    }
    else
    {
        while (!workList.empty())
        {
            preAs.joinWith(workList.back());
            workList.pop_back();
        }
        // Has ES on the in edges - Feasible block
        // update post as
        abstractTrace[icfgNode] = preAs;
        return true;
    }
}

recursiveCallPass()

void AbstractInterpretation::recursiveCallPass ( const CallICFGNode *  callNode )

privatevirtual

Definition at line 591 of file AbstractInterpretation.cpp.

{
    AbstractState& as = getAbsStateFromTrace(callNode);
    SkipRecursiveCall(callNode);
    const RetICFGNode *retNode = callNode->getRetICFGNode();
    if (retNode->getSVFStmts().size() > 0)
    {
        if (const RetPE *retPE = SVFUtil::dyn_cast<RetPE>(*retNode->getSVFStmts().begin()))
        {
            if (!retPE->getLHSVar()->isPointer() &&
                    !retPE->getLHSVar()->isConstDataOrAggDataButNotNullPtr())
            {
                as[retPE->getLHSVarID()] = IntervalValue::top();
            }
        }
    }
    abstractTrace[retNode] = as;
}

runOnModule()

void AbstractInterpretation::runOnModule ( ICFG *  icfg )

virtual

collect checkpoint

Definition at line 41 of file AbstractInterpretation.cpp.

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

SkipRecursiveCall()

void AbstractInterpretation::SkipRecursiveCall ( const CallICFGNode *  callnode )

privatevirtual

Check if this callnode is recursive call and skip it.

Parameters

callnode

CallICFGNode which calls a recursive function

Definition at line 777 of file AbstractInterpretation.cpp.

{
    AbstractState& as = getAbsStateFromTrace(callNode);
    const RetICFGNode *retNode = callNode->getRetICFGNode();
    if (retNode->getSVFStmts().size() > 0)
    {
        if (const RetPE *retPE = SVFUtil::dyn_cast<RetPE>(*retNode->getSVFStmts().begin()))
        {
            AbstractState as;
            if (!retPE->getLHSVar()->isPointer() && !retPE->getLHSVar()->isConstDataOrAggDataButNotNullPtr())
                as[retPE->getLHSVarID()] = IntervalValue::top();
        }
    }
    if (!retNode->getOutEdges().empty())
    {
        if (retNode->getOutEdges().size() == 1)
        {
 
        }
        else
        {
            return;
        }
    }
    FIFOWorkList<const SVFBasicBlock *> blkWorkList;
    FIFOWorkList<const ICFGNode *> instWorklist;
    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();
                    u32_t lhs = store->getLHSVarID();
                    if (as.inVarToAddrsTable(lhs))
                    {
                        if (!rhsVar->isPointer() && !rhsVar->isConstDataOrAggDataButNotNullPtr())
                        {
                            const AbstractValue &addrs = as[lhs];
                            for (const auto &addr: addrs.getAddrs())
                            {
                                as.store(addr, IntervalValue::top());
                            }
                        }
                    }
                }
            }
        }
    }
}

updateStateOnAddr()

void AbstractInterpretation::updateStateOnAddr ( const AddrStmt *  addr )

private

Definition at line 1057 of file AbstractInterpretation.cpp.

{
    AbstractState& as = getAbsStateFromTrace(addr->getICFGNode());
    as.initObjVar(SVFUtil::cast<ObjVar>(addr->getRHSVar()));
    if (addr->getRHSVar()->getType()->getKind() == SVFType::SVFIntegerTy)
        as[addr->getRHSVarID()].getInterval().meet_with(utils->getRangeLimitFromType(addr->getRHSVar()->getType()));
    as[addr->getLHSVarID()] = as[addr->getRHSVarID()];
}

updateStateOnBinary()

void AbstractInterpretation::updateStateOnBinary ( const BinaryOPStmt *  binary )

private

Find the comparison predicates in "class BinaryOPStmt:OpCode" under SVF/svf/include/SVFIR/SVFStatements.h You are only required to handle integer predicates, including Add, FAdd, Sub, FSub, Mul, FMul, SDiv, FDiv, UDiv, SRem, FRem, URem, Xor, And, Or, AShr, Shl, LShr

Definition at line 1067 of file AbstractInterpretation.cpp.

{
    const ICFGNode* node = binary->getICFGNode();
    AbstractState& as = getAbsStateFromTrace(node);
    u32_t op0 = binary->getOpVarID(0);
    u32_t op1 = binary->getOpVarID(1);
    u32_t res = binary->getResID();
    if (!as.inVarToValTable(op0)) as[op0] = IntervalValue::top();
    if (!as.inVarToValTable(op1)) as[op1] = IntervalValue::top();
    IntervalValue &lhs = as[op0].getInterval(), &rhs = as[op1].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: ");
    }
    as[res] = resVal;
}

updateStateOnCall()

void AbstractInterpretation::updateStateOnCall ( const CallPE *  callPE )

private

Definition at line 1040 of file AbstractInterpretation.cpp.

{
    AbstractState& as = getAbsStateFromTrace(callPE->getICFGNode());
    NodeID lhs = callPE->getLHSVarID();
    NodeID rhs = callPE->getRHSVarID();
    as[lhs] = as[rhs];
}

updateStateOnCmp()

void AbstractInterpretation::updateStateOnCmp ( const CmpStmt *  cmp )

private

Definition at line 1129 of file AbstractInterpretation.cpp.

{
    AbstractState& as = getAbsStateFromTrace(cmp->getICFGNode());
    u32_t op0 = cmp->getOpVarID(0);
    u32_t op1 = cmp->getOpVarID(1);
    // if it is address
    if (as.inVarToAddrsTable(op0) && as.inVarToAddrsTable(op1))
    {
        IntervalValue resVal;
        AddressValue addrOp0 = as[op0].getAddrs();
        AddressValue addrOp1 = as[op1].getAddrs();
        u32_t res = cmp->getResID();
        if (addrOp0.equals(addrOp1))
        {
            resVal = IntervalValue(1, 1);
        }
        else if (addrOp0.hasIntersect(addrOp1))
        {
            resVal = IntervalValue(0, 1);
        }
        else
        {
            resVal = IntervalValue(0, 0);
        }
        as[res] = resVal;
    }
    else
    {
        if (!as.inVarToValTable(op0))
            as[op0] = IntervalValue::top();
        if (!as.inVarToValTable(op1))
            as[op1] = IntervalValue::top();
        u32_t res = cmp->getResID();
        if (as.inVarToValTable(op0) && as.inVarToValTable(op1))
        {
            IntervalValue resVal;
            if (as[op0].isInterval() && as[op1].isInterval())
            {
                IntervalValue &lhs = as[op0].getInterval(),
                               &rhs = as[op1].getInterval();
                // AbstractValue
                auto predicate = cmp->getPredicate();
                switch (predicate)
                {
                case CmpStmt::ICMP_EQ:
                case CmpStmt::FCMP_OEQ:
                case CmpStmt::FCMP_UEQ:
                    resVal = (lhs == rhs);
                    // resVal = (lhs.getInterval() == rhs.getInterval());
                    break;
                case CmpStmt::ICMP_NE:
                case CmpStmt::FCMP_ONE:
                case CmpStmt::FCMP_UNE:
                    resVal = (lhs != rhs);
                    break;
                case CmpStmt::ICMP_UGT:
                case CmpStmt::ICMP_SGT:
                case CmpStmt::FCMP_OGT:
                case CmpStmt::FCMP_UGT:
                    resVal = (lhs > rhs);
                    break;
                case CmpStmt::ICMP_UGE:
                case CmpStmt::ICMP_SGE:
                case CmpStmt::FCMP_OGE:
                case CmpStmt::FCMP_UGE:
                    resVal = (lhs >= rhs);
                    break;
                case CmpStmt::ICMP_ULT:
                case CmpStmt::ICMP_SLT:
                case CmpStmt::FCMP_OLT:
                case CmpStmt::FCMP_ULT:
                    resVal = (lhs < rhs);
                    break;
                case CmpStmt::ICMP_ULE:
                case CmpStmt::ICMP_SLE:
                case CmpStmt::FCMP_OLE:
                case CmpStmt::FCMP_ULE:
                    resVal = (lhs <= rhs);
                    break;
                case CmpStmt::FCMP_FALSE:
                    resVal = IntervalValue(0, 0);
                    break;
                case CmpStmt::FCMP_TRUE:
                    resVal = IntervalValue(1, 1);
                    break;
                default:
                {
                    assert(false && "undefined compare: ");
                }
                }
                as[res] = resVal;
            }
            else if (as[op0].isAddr() && as[op1].isAddr())
            {
                AddressValue &lhs = as[op0].getAddrs(),
                              &rhs = as[op1].getAddrs();
                auto predicate = cmp->getPredicate();
                switch (predicate)
                {
                case CmpStmt::ICMP_EQ:
                case CmpStmt::FCMP_OEQ:
                case CmpStmt::FCMP_UEQ:
                {
                    if (lhs.hasIntersect(rhs))
                    {
                        resVal = IntervalValue(0, 1);
                    }
                    else if (lhs.empty() && rhs.empty())
                    {
                        resVal = IntervalValue(1, 1);
                    }
                    else
                    {
                        resVal = IntervalValue(0, 0);
                    }
                    break;
                }
                case CmpStmt::ICMP_NE:
                case CmpStmt::FCMP_ONE:
                case CmpStmt::FCMP_UNE:
                {
                    if (lhs.hasIntersect(rhs))
                    {
                        resVal = IntervalValue(0, 1);
                    }
                    else if (lhs.empty() && rhs.empty())
                    {
                        resVal = IntervalValue(0, 0);
                    }
                    else
                    {
                        resVal = IntervalValue(1, 1);
                    }
                    break;
                }
                case CmpStmt::ICMP_UGT:
                case CmpStmt::ICMP_SGT:
                case CmpStmt::FCMP_OGT:
                case CmpStmt::FCMP_UGT:
                {
                    if (lhs.size() == 1 && rhs.size() == 1)
                    {
                        resVal = IntervalValue(*lhs.begin() > *rhs.begin());
                    }
                    else
                    {
                        resVal = IntervalValue(0, 1);
                    }
                    break;
                }
                case CmpStmt::ICMP_UGE:
                case CmpStmt::ICMP_SGE:
                case CmpStmt::FCMP_OGE:
                case CmpStmt::FCMP_UGE:
                {
                    if (lhs.size() == 1 && rhs.size() == 1)
                    {
                        resVal = IntervalValue(*lhs.begin() >= *rhs.begin());
                    }
                    else
                    {
                        resVal = IntervalValue(0, 1);
                    }
                    break;
                }
                case CmpStmt::ICMP_ULT:
                case CmpStmt::ICMP_SLT:
                case CmpStmt::FCMP_OLT:
                case CmpStmt::FCMP_ULT:
                {
                    if (lhs.size() == 1 && rhs.size() == 1)
                    {
                        resVal = IntervalValue(*lhs.begin() < *rhs.begin());
                    }
                    else
                    {
                        resVal = IntervalValue(0, 1);
                    }
                    break;
                }
                case CmpStmt::ICMP_ULE:
                case CmpStmt::ICMP_SLE:
                case CmpStmt::FCMP_OLE:
                case CmpStmt::FCMP_ULE:
                {
                    if (lhs.size() == 1 && rhs.size() == 1)
                    {
                        resVal = IntervalValue(*lhs.begin() <= *rhs.begin());
                    }
                    else
                    {
                        resVal = IntervalValue(0, 1);
                    }
                    break;
                }
                case CmpStmt::FCMP_FALSE:
                    resVal = IntervalValue(0, 0);
                    break;
                case CmpStmt::FCMP_TRUE:
                    resVal = IntervalValue(1, 1);
                    break;
                default:
                {
                    assert(false && "undefined compare: ");
                }
                }
                as[res] = resVal;
            }
        }
    }
}

updateStateOnCopy()

void AbstractInterpretation::updateStateOnCopy ( const CopyStmt *  copy )

private

Definition at line 1357 of file AbstractInterpretation.cpp.

{
    auto getZExtValue = [](AbstractState& as, const SVFVar* var)
    {
        const SVFType* type = var->getType();
        if (SVFUtil::isa<SVFIntegerType>(type))
        {
            u32_t bits = type->getByteSize() * 8;
            if (as[var->getId()].getInterval().is_numeral())
            {
                if (bits == 8)
                {
                    int8_t signed_i8_value = as[var->getId()].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 = as[var->getId()].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 = as[var->getId()].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 = as[var->getId()].getInterval().getIntNumeral();
                    return IntervalValue((s64_t)signed_i64_value, (s64_t)signed_i64_value);
                    // we only support i64 at most
                }
                else
                {
                    assert(false && "cannot support int type other than u8/16/32/64");
                }
            }
            else
            {
                return IntervalValue::top(); // TODO: may have better solution
            }
        }
        return IntervalValue::top(); // TODO: may have better solution
    };
 
    auto getTruncValue = [&](const AbstractState& as, const SVF::SVFVar* var,
                             const SVFType* dstType)
    {
        const IntervalValue& itv = as[var->getId()].getInterval();
        if(itv.isBottom()) return itv;
        // get the value of ub and lb
        s64_t int_lb = itv.lb().getIntNumeral();
        s64_t int_ub = itv.ub().getIntNumeral();
        // get dst type
        u32_t dst_bits = dstType->getByteSize() * 8;
        if (dst_bits == 8)
        {
            // get the signed value of ub and lb
            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 range of s8
                return utils->getRangeLimitFromType(dstType);
            }
            return IntervalValue(s8_lb, s8_ub);
        }
        else if (dst_bits == 16)
        {
            // get the signed value of ub and lb
            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 range of s16
                return utils->getRangeLimitFromType(dstType);
            }
            return IntervalValue(s16_lb, s16_ub);
        }
        else if (dst_bits == 32)
        {
            // get the signed value of ub and lb
            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 range of s32
                return utils->getRangeLimitFromType(dstType);
            }
            return IntervalValue(s32_lb, s32_ub);
        }
        else
        {
            assert(false && "cannot support dst int type other than u8/16/32");
        }
    };
 
    AbstractState& as = getAbsStateFromTrace(copy->getICFGNode());
    u32_t lhs = copy->getLHSVarID();
    u32_t rhs = copy->getRHSVarID();
 
    if (copy->getCopyKind() == CopyStmt::COPYVAL)
    {
        as[lhs] = as[rhs];
    }
    else if (copy->getCopyKind() == CopyStmt::ZEXT)
    {
        as[lhs] = getZExtValue(as, copy->getRHSVar());
    }
    else if (copy->getCopyKind() == CopyStmt::SEXT)
    {
        as[lhs] = as[rhs].getInterval();
    }
    else if (copy->getCopyKind() == CopyStmt::FPTOSI)
    {
        as[lhs] = as[rhs].getInterval();
    }
    else if (copy->getCopyKind() == CopyStmt::FPTOUI)
    {
        as[lhs] = as[rhs].getInterval();
    }
    else if (copy->getCopyKind() == CopyStmt::SITOFP)
    {
        as[lhs] = as[rhs].getInterval();
    }
    else if (copy->getCopyKind() == CopyStmt::UITOFP)
    {
        as[lhs] = as[rhs].getInterval();
    }
    else if (copy->getCopyKind() == CopyStmt::TRUNC)
    {
        as[lhs] = getTruncValue(as, copy->getRHSVar(), copy->getLHSVar()->getType());
    }
    else if (copy->getCopyKind() == CopyStmt::FPTRUNC)
    {
        as[lhs] = as[rhs].getInterval();
    }
    else if (copy->getCopyKind() == CopyStmt::INTTOPTR)
    {
        //insert nullptr
    }
    else if (copy->getCopyKind() == CopyStmt::PTRTOINT)
    {
        as[lhs] = IntervalValue::top();
    }
    else if (copy->getCopyKind() == CopyStmt::BITCAST)
    {
        if (as[rhs].isAddr())
        {
            as[lhs] = as[rhs];
        }
        else
        {
            // do nothing
        }
    }
    else
    {
        assert(false && "undefined copy kind");
        abort();
    }
}

updateStateOnGep()

void AbstractInterpretation::updateStateOnGep ( const GepStmt *  gep )

private

Definition at line 967 of file AbstractInterpretation.cpp.

{
    AbstractState& as = getAbsStateFromTrace(gep->getICFGNode());
    u32_t rhs = gep->getRHSVarID();
    u32_t lhs = gep->getLHSVarID();
    IntervalValue offsetPair = as.getElementIndex(gep);
    AbstractValue gepAddrs;
    APOffset lb = offsetPair.lb().getIntNumeral() < Options::MaxFieldLimit()?
                  offsetPair.lb().getIntNumeral(): Options::MaxFieldLimit();
    APOffset ub = offsetPair.ub().getIntNumeral() < Options::MaxFieldLimit()?
                  offsetPair.ub().getIntNumeral(): Options::MaxFieldLimit();
    for (APOffset i = lb; i <= ub; i++)
        gepAddrs.join_with(as.getGepObjAddrs(rhs,IntervalValue(i)));
    as[lhs] = gepAddrs;
}

updateStateOnLoad()

void AbstractInterpretation::updateStateOnLoad ( const LoadStmt *  load )

private

Definition at line 1341 of file AbstractInterpretation.cpp.

{
    AbstractState& as = getAbsStateFromTrace(load->getICFGNode());
    u32_t rhs = load->getRHSVarID();
    u32_t lhs = load->getLHSVarID();
    as[lhs] = as.loadValue(rhs);
}

updateStateOnPhi()

void AbstractInterpretation::updateStateOnPhi ( const PhiStmt *  phi )

private

Definition at line 1001 of file AbstractInterpretation.cpp.

{
    const ICFGNode* icfgNode = phi->getICFGNode();
    AbstractState& as = getAbsStateFromTrace(icfgNode);
    u32_t res = phi->getResID();
    AbstractValue rhs;
    for (u32_t i = 0; i < phi->getOpVarNum(); i++)
    {
        NodeID curId = phi->getOpVarID(i);
        const ICFGNode* opICFGNode = phi->getOpICFGNode(i);
        if (hasAbsStateFromTrace(opICFGNode))
        {
            AbstractState tmpEs = abstractTrace[opICFGNode];
            AbstractState& opAs = getAbsStateFromTrace(opICFGNode);
            const ICFGEdge* edge =  icfg->getICFGEdge(opICFGNode, icfgNode, ICFGEdge::IntraCF);
            // if IntraEdge, check the condition, if it is feasible, join the value
            // if IntraEdge but not conditional edge, join the value
            // if not IntraEdge, join the value
            if (edge)
            {
                const IntraCFGEdge* intraEdge = SVFUtil::cast<IntraCFGEdge>(edge);
                if (intraEdge->getCondition())
                {
                    if (isBranchFeasible(intraEdge, tmpEs))
                        rhs.join_with(opAs[curId]);
                }
                else
                    rhs.join_with(opAs[curId]);
            }
            else
            {
                rhs.join_with(opAs[curId]);
            }
        }
    }
    as[res] = rhs;
}

updateStateOnRet()

void AbstractInterpretation::updateStateOnRet ( const RetPE *  retPE )

private

Definition at line 1048 of file AbstractInterpretation.cpp.

{
    AbstractState& as = getAbsStateFromTrace(retPE->getICFGNode());
    NodeID lhs = retPE->getLHSVarID();
    NodeID rhs = retPE->getRHSVarID();
    as[lhs] = as[rhs];
}

updateStateOnSelect()

void AbstractInterpretation::updateStateOnSelect ( const SelectStmt *  select )

private

Definition at line 983 of file AbstractInterpretation.cpp.

{
    AbstractState& as = getAbsStateFromTrace(select->getICFGNode());
    u32_t res = select->getResID();
    u32_t tval = select->getTrueValue()->getId();
    u32_t fval = select->getFalseValue()->getId();
    u32_t cond = select->getCondition()->getId();
    if (as[cond].getInterval().is_numeral())
    {
        as[res] = as[cond].getInterval().is_zero() ? as[fval] : as[tval];
    }
    else
    {
        as[res] = as[tval];
        as[res].join_with(as[fval]);
    }
}

updateStateOnStore()

void AbstractInterpretation::updateStateOnStore ( const StoreStmt *  store )

private

Definition at line 1349 of file AbstractInterpretation.cpp.

{
    AbstractState& as = getAbsStateFromTrace(store->getICFGNode());
    u32_t rhs = store->getRHSVarID();
    u32_t lhs = store->getLHSVarID();
    as.storeValue(lhs, as[rhs]);
}

Friends And Related Symbol Documentation

AEAPI

friend class AEAPI

friend

Definition at line 105 of file AbstractInterpretation.h.

AEStat

friend class AEStat

friend

Definition at line 104 of file AbstractInterpretation.h.

BufOverflowDetector

friend class BufOverflowDetector

friend

Definition at line 106 of file AbstractInterpretation.h.

Member Data Documentation

_reverse_predicate

Map<s32_t, s32_t> SVF::AbstractInterpretation::_reverse_predicate

private

Initial value:

=
    {
        {CmpStmt::Predicate::FCMP_OEQ, CmpStmt::Predicate::FCMP_ONE},  
        {CmpStmt::Predicate::FCMP_UEQ, CmpStmt::Predicate::FCMP_UNE},  
        {CmpStmt::Predicate::FCMP_OGT, CmpStmt::Predicate::FCMP_OLE},  
        {CmpStmt::Predicate::FCMP_OGE, CmpStmt::Predicate::FCMP_OLT},  
        {CmpStmt::Predicate::FCMP_OLT, CmpStmt::Predicate::FCMP_OGE},  
        {CmpStmt::Predicate::FCMP_OLE, CmpStmt::Predicate::FCMP_OGT},  
        {CmpStmt::Predicate::FCMP_ONE, CmpStmt::Predicate::FCMP_OEQ},  
        {CmpStmt::Predicate::FCMP_UNE, CmpStmt::Predicate::FCMP_UEQ},  
        {CmpStmt::Predicate::ICMP_EQ, CmpStmt::Predicate::ICMP_NE},  
        {CmpStmt::Predicate::ICMP_NE, CmpStmt::Predicate::ICMP_EQ},  
        {CmpStmt::Predicate::ICMP_UGT, CmpStmt::Predicate::ICMP_ULE},  
        {CmpStmt::Predicate::ICMP_ULT, CmpStmt::Predicate::ICMP_UGE},  
        {CmpStmt::Predicate::ICMP_UGE, CmpStmt::Predicate::ICMP_ULT},  
        {CmpStmt::Predicate::ICMP_SGT, CmpStmt::Predicate::ICMP_SLE},  
        {CmpStmt::Predicate::ICMP_SLT, CmpStmt::Predicate::ICMP_SGE},  
        {CmpStmt::Predicate::ICMP_SGE, CmpStmt::Predicate::ICMP_SLT},  
    }

Definition at line 308 of file AbstractInterpretation.h.

    {
        {CmpStmt::Predicate::FCMP_OEQ, CmpStmt::Predicate::FCMP_ONE},  // == -> !=
        {CmpStmt::Predicate::FCMP_UEQ, CmpStmt::Predicate::FCMP_UNE},  // == -> !=
        {CmpStmt::Predicate::FCMP_OGT, CmpStmt::Predicate::FCMP_OLE},  // > -> <=
        {CmpStmt::Predicate::FCMP_OGE, CmpStmt::Predicate::FCMP_OLT},  // >= -> <
        {CmpStmt::Predicate::FCMP_OLT, CmpStmt::Predicate::FCMP_OGE},  // < -> >=
        {CmpStmt::Predicate::FCMP_OLE, CmpStmt::Predicate::FCMP_OGT},  // <= -> >
        {CmpStmt::Predicate::FCMP_ONE, CmpStmt::Predicate::FCMP_OEQ},  // != -> ==
        {CmpStmt::Predicate::FCMP_UNE, CmpStmt::Predicate::FCMP_UEQ},  // != -> ==
        {CmpStmt::Predicate::ICMP_EQ, CmpStmt::Predicate::ICMP_NE},  // == -> !=
        {CmpStmt::Predicate::ICMP_NE, CmpStmt::Predicate::ICMP_EQ},  // != -> ==
        {CmpStmt::Predicate::ICMP_UGT, CmpStmt::Predicate::ICMP_ULE},  // > -> <=
        {CmpStmt::Predicate::ICMP_ULT, CmpStmt::Predicate::ICMP_UGE},  // < -> >=
        {CmpStmt::Predicate::ICMP_UGE, CmpStmt::Predicate::ICMP_ULT},  // >= -> <
        {CmpStmt::Predicate::ICMP_SGT, CmpStmt::Predicate::ICMP_SLE},  // > -> <=
        {CmpStmt::Predicate::ICMP_SLT, CmpStmt::Predicate::ICMP_SGE},  // < -> >=
        {CmpStmt::Predicate::ICMP_SGE, CmpStmt::Predicate::ICMP_SLT},  // >= -> <
    };

_switch_lhsrhs_predicate

Map<s32_t, s32_t> SVF::AbstractInterpretation::_switch_lhsrhs_predicate

private

Initial value:

=
    {
        {CmpStmt::Predicate::FCMP_OEQ, CmpStmt::Predicate::FCMP_OEQ},  
        {CmpStmt::Predicate::FCMP_UEQ, CmpStmt::Predicate::FCMP_UEQ},  
        {CmpStmt::Predicate::FCMP_OGT, CmpStmt::Predicate::FCMP_OLT},  
        {CmpStmt::Predicate::FCMP_OGE, CmpStmt::Predicate::FCMP_OLE},  
        {CmpStmt::Predicate::FCMP_OLT, CmpStmt::Predicate::FCMP_OGT},  
        {CmpStmt::Predicate::FCMP_OLE, CmpStmt::Predicate::FCMP_OGE},  
        {CmpStmt::Predicate::FCMP_ONE, CmpStmt::Predicate::FCMP_ONE},  
        {CmpStmt::Predicate::FCMP_UNE, CmpStmt::Predicate::FCMP_UNE},  
        {CmpStmt::Predicate::ICMP_EQ, CmpStmt::Predicate::ICMP_EQ},  
        {CmpStmt::Predicate::ICMP_NE, CmpStmt::Predicate::ICMP_NE},  
        {CmpStmt::Predicate::ICMP_UGT, CmpStmt::Predicate::ICMP_ULT},  
        {CmpStmt::Predicate::ICMP_ULT, CmpStmt::Predicate::ICMP_UGT},  
        {CmpStmt::Predicate::ICMP_UGE, CmpStmt::Predicate::ICMP_ULE},  
        {CmpStmt::Predicate::ICMP_SGT, CmpStmt::Predicate::ICMP_SLT},  
        {CmpStmt::Predicate::ICMP_SLT, CmpStmt::Predicate::ICMP_SGT},  
        {CmpStmt::Predicate::ICMP_SGE, CmpStmt::Predicate::ICMP_SLE},  
    }

Definition at line 329 of file AbstractInterpretation.h.

    {
        {CmpStmt::Predicate::FCMP_OEQ, CmpStmt::Predicate::FCMP_OEQ},  // == -> ==
        {CmpStmt::Predicate::FCMP_UEQ, CmpStmt::Predicate::FCMP_UEQ},  // == -> ==
        {CmpStmt::Predicate::FCMP_OGT, CmpStmt::Predicate::FCMP_OLT},  // > -> <
        {CmpStmt::Predicate::FCMP_OGE, CmpStmt::Predicate::FCMP_OLE},  // >= -> <=
        {CmpStmt::Predicate::FCMP_OLT, CmpStmt::Predicate::FCMP_OGT},  // < -> >
        {CmpStmt::Predicate::FCMP_OLE, CmpStmt::Predicate::FCMP_OGE},  // <= -> >=
        {CmpStmt::Predicate::FCMP_ONE, CmpStmt::Predicate::FCMP_ONE},  // != -> !=
        {CmpStmt::Predicate::FCMP_UNE, CmpStmt::Predicate::FCMP_UNE},  // != -> !=
        {CmpStmt::Predicate::ICMP_EQ, CmpStmt::Predicate::ICMP_EQ},  // == -> ==
        {CmpStmt::Predicate::ICMP_NE, CmpStmt::Predicate::ICMP_NE},  // != -> !=
        {CmpStmt::Predicate::ICMP_UGT, CmpStmt::Predicate::ICMP_ULT},  // > -> <
        {CmpStmt::Predicate::ICMP_ULT, CmpStmt::Predicate::ICMP_UGT},  // < -> >
        {CmpStmt::Predicate::ICMP_UGE, CmpStmt::Predicate::ICMP_ULE},  // >= -> <=
        {CmpStmt::Predicate::ICMP_SGT, CmpStmt::Predicate::ICMP_SLT},  // > -> <
        {CmpStmt::Predicate::ICMP_SLT, CmpStmt::Predicate::ICMP_SGT},  // < -> >
        {CmpStmt::Predicate::ICMP_SGE, CmpStmt::Predicate::ICMP_SLE},  // >= -> <=
    };

abstractTrace

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

private

Definition at line 295 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 248 of file AbstractInterpretation.h.

{nullptr};

callSiteStack

std::vector<const CallICFGNode*> SVF::AbstractInterpretation::callSiteStack

private

Definition at line 253 of file AbstractInterpretation.h.

checkpoints

Set<const CallICFGNode*> SVF::AbstractInterpretation::checkpoints

Definition at line 132 of file AbstractInterpretation.h.

detectors

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

private

Definition at line 298 of file AbstractInterpretation.h.

func_map

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

private

Definition at line 293 of file AbstractInterpretation.h.

funcToWTO

Map<const CallGraphNode*, ICFGWTO*> SVF::AbstractInterpretation::funcToWTO

private

Definition at line 254 of file AbstractInterpretation.h.

icfg

ICFG* SVF::AbstractInterpretation::icfg

private

Definition at line 250 of file AbstractInterpretation.h.

moduleName

std::string SVF::AbstractInterpretation::moduleName

private

Definition at line 296 of file AbstractInterpretation.h.

recursiveFuns

Set<const CallGraphNode*> SVF::AbstractInterpretation::recursiveFuns

private

Definition at line 255 of file AbstractInterpretation.h.

stat

AEStat* SVF::AbstractInterpretation::stat

private

Definition at line 251 of file AbstractInterpretation.h.

svfir

SVFIR* SVF::AbstractInterpretation::svfir

private

protected data members, also used in subclasses

Definition at line 246 of file AbstractInterpretation.h.

utils

AbsExtAPI* SVF::AbstractInterpretation::utils

private

Definition at line 299 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