#include <SaberSVFGBuilder.h>

Inheritance diagram for SVF::SaberSVFGBuilder:

Public Types
typedef Set< const SVFGNode * >	SVFGNodeSet

typedef Map< NodeID, PointsTo >	NodeToPTSSMap

typedef FIFOWorkList< NodeID >	WorkList

Public Types inherited from SVF::SVFGBuilder
typedef PointerAnalysis::CallSiteSet	CallSiteSet

typedef PointerAnalysis::CallEdgeMap	CallEdgeMap

typedef PointerAnalysis::FunctionSet	FunctionSet

typedef SVFG::SVFGEdgeSetTy	SVFGEdgeSet

Public Member Functions
	SaberSVFGBuilder ()
	Constructor.

virtual	~SaberSVFGBuilder ()
	Destructor.

bool	isGlobalSVFGNode (const SVFGNode *node) const

void	addActualParmVFGNode (const PAGNode pagNode, const CallICFGNode cs)
	Add ActualParmVFGNode.

void	setSaberCondAllocator (SaberCondAllocator *allocator)

Public Member Functions inherited from SVF::SVFGBuilder
	SVFGBuilder (bool _SVFGWithIndCall=false)
	Constructor.

virtual	~SVFGBuilder ()=default
	Destructor.

SVFG *	buildPTROnlySVFG (BVDataPTAImpl *pta)

SVFG *	buildFullSVFG (BVDataPTAImpl *pta)

SVFG *	getSVFG () const
	Get SVFG instance.

void	markValidVFEdge (SVFGEdgeSet &edges)
	Mark feasible VF edge by removing it from set vfEdgesAtIndCallSite.

bool	isSpuriousVFEdgeAtIndCallSite (const SVFGEdge *edge)
	Return true if this is an VF Edge pre-connected by Andersen's analysis.

virtual std::unique_ptr< MemSSA >	buildMSSA (BVDataPTAImpl *pta, bool ptrOnlyMSSA)
	Build Memory SSA.

Protected Member Functions
virtual void	buildSVFG ()
	Re-write create SVFG method.

bool	isStrongUpdate (const SVFGNode node, NodeID &singleton, BVDataPTAImpl pta)
	Return TRUE if this is a strong update STORE statement.

void	rmDerefDirSVFGEdges (BVDataPTAImpl *pta)

virtual void	rmIncomingEdgeForSUStore (BVDataPTAImpl *pta)

virtual void	AddExtActualParmSVFGNodes (PTACallGraph *callgraph)
	Add actual parameter SVFGNode for 1st argument of a deallocation like external function.

void	collectGlobals (BVDataPTAImpl *pta)

bool	accessGlobal (BVDataPTAImpl pta, const PAGNode pagNode)
	Whether points-to of a PAGNode points-to global variable.

PointsTo &	CollectPtsChain (BVDataPTAImpl *pta, NodeID id, NodeToPTSSMap &cachedPtsMap)
	Collect objects along points-to chains.

Protected Member Functions inherited from SVF::SVFGBuilder
SVFG *	build (BVDataPTAImpl *pta, VFG::VFGK kind)
	Create a DDA SVFG. By default actualOut and FormalIN are removed, unless withAOFI is set true.

virtual void	releaseMemory ()
	Release global SVFG.

Protected Attributes
PointsTo	globs

SVFGNodeSet	globSVFGNodes
	Store all global SVFG nodes.

SaberCondAllocator *	saberCondAllocator

Protected Attributes inherited from SVF::SVFGBuilder
SVFGEdgeSet	vfEdgesAtIndCallSite
	SVFG Edges connected at indirect call/ret sites.

std::unique_ptr< SVFG >	svfg

bool	SVFGWithIndCall
	SVFG with precomputed indirect call edges.

Detailed Description

Definition at line 43 of file SaberSVFGBuilder.h.

Member Typedef Documentation

◆ NodeToPTSSMap

typedef Map<NodeID, PointsTo> SVF::SaberSVFGBuilder::NodeToPTSSMap

Definition at line 48 of file SaberSVFGBuilder.h.

◆ SVFGNodeSet

typedef Set<const SVFGNode*> SVF::SaberSVFGBuilder::SVFGNodeSet

Definition at line 47 of file SaberSVFGBuilder.h.

◆ WorkList

typedef FIFOWorkList<NodeID> SVF::SaberSVFGBuilder::WorkList

Definition at line 49 of file SaberSVFGBuilder.h.

Constructor & Destructor Documentation

◆ SaberSVFGBuilder()

SVF::SaberSVFGBuilder::SaberSVFGBuilder ( )

inline

Constructor.

Definition at line 52 of file SaberSVFGBuilder.h.

52: SVFGBuilder(true) {}

SVF::SVFGBuilder::SVFGBuilder

SVFGBuilder(bool _SVFGWithIndCall=false)

Constructor.

Definition SVFGBuilder.h:52

◆ ~SaberSVFGBuilder()

virtual SVF::SaberSVFGBuilder::~SaberSVFGBuilder ( )

inlinevirtual

Destructor.

Definition at line 55 of file SaberSVFGBuilder.h.

55{}

Member Function Documentation

◆ accessGlobal()

bool SaberSVFGBuilder::accessGlobal	(	BVDataPTAImpl *	pta,
		const PAGNode *	pagNode
	)

protected

Whether points-to of a PAGNode points-to global variable.

Decide whether the node and its points-to contains a global objects

Definition at line 168 of file SaberSVFGBuilder.cpp.

{
 
    NodeID id = pagNode->getId();
    PointsTo pts = pta->getPts(id);
    pts.set(id);
 
    return pts.intersects(globs);
}

◆ addActualParmVFGNode()

void SVF::SaberSVFGBuilder::addActualParmVFGNode	(	const PAGNode *	pagNode,
		const CallICFGNode *	cs
	)

inline

Add ActualParmVFGNode.

Definition at line 63 of file SaberSVFGBuilder.h.

    {
        svfg->addActualParmVFGNode(pagNode, cs);
    }

◆ AddExtActualParmSVFGNodes()

void SaberSVFGBuilder::AddExtActualParmSVFGNodes ( PTACallGraph * callgraph )

protectedvirtual

Add actual parameter SVFGNode for 1st argument of a deallocation like external function.

Add actual parameter SVFGNode for 1st argument of a deallocation like external function In order to path sensitive leak detection

Definition at line 292 of file SaberSVFGBuilder.cpp.

{
    SVFIR* pag = SVFIR::getPAG();
    for(SVFIR::CSToArgsListMap::iterator it = pag->getCallSiteArgsMap().begin(),
            eit = pag->getCallSiteArgsMap().end(); it!=eit; ++it)
    {
        PTACallGraph::FunctionSet callees;
        callgraph->getCallees(it->first, callees);
        for (PTACallGraph::FunctionSet::const_iterator cit = callees.begin(),
                ecit = callees.end(); cit != ecit; cit++)
        {
 
            const SVFFunction* fun = *cit;
            if (SaberCheckerAPI::getCheckerAPI()->isMemDealloc(fun)
                    || SaberCheckerAPI::getCheckerAPI()->isFClose(fun))
            {
                SVFIR::SVFVarList& arglist = it->second;
                for(SVFIR::SVFVarList::const_iterator ait = arglist.begin(), aeit = arglist.end(); ait!=aeit; ++ait)
                {
                    const PAGNode *pagNode = *ait;
                    if (pagNode->isPointer())
                    {
                        addActualParmVFGNode(pagNode, it->first);
                        svfg->addIntraDirectVFEdge(svfg->getDefSVFGNode(pagNode)->getId(), svfg->getActualParmVFGNode(pagNode, it->first)->getId());
                    }
                }
            }
        }
    }
}

◆ buildSVFG()

void SaberSVFGBuilder::buildSVFG ( )

protectedvirtual

Re-write create SVFG method.

Reimplemented from SVF::SVFGBuilder.

Reimplemented in SVF::CFLSVFGBuilder.

Definition at line 41 of file SaberSVFGBuilder.cpp.

{
 
    MemSSA* mssa = svfg->getMSSA();
    svfg->buildSVFG();
    BVDataPTAImpl* pta = mssa->getPTA();
    DBOUT(DGENERAL, outs() << pasMsg("\tCollect Global Variables\n"));
 
    collectGlobals(pta);
 
    DBOUT(DGENERAL, outs() << pasMsg("\tRemove Dereference Direct SVFG Edge\n"));
 
    rmDerefDirSVFGEdges(pta);
 
    assert(saberCondAllocator && "saber condition allocator not set yet!");
    rmIncomingEdgeForSUStore(pta);
 
    DBOUT(DGENERAL, outs() << pasMsg("\tAdd Sink SVFG Nodes\n"));
 
    AddExtActualParmSVFGNodes(pta->getCallGraph());
 
    if(pta->printStat())
        svfg->performStat();
}

◆ collectGlobals()

void SaberSVFGBuilder::collectGlobals ( BVDataPTAImpl * pta )

protected

Collect memory pointed global pointers, note that this collection is recursively performed, for example gp-->obj-->obj' obj and obj' are both considered global memory

Recursively collect global memory objects

Definition at line 70 of file SaberSVFGBuilder.cpp.

{
    SVFIR* pag = svfg->getPAG();
    NodeVector worklist;
    for(SVFIR::iterator it = pag->begin(), eit = pag->end(); it!=eit; it++)
    {
        PAGNode* pagNode = it->second;
        if (SVFUtil::isa<DummyValVar, DummyObjVar>(pagNode))
            continue;
 
        if(GepObjVar* gepobj = SVFUtil::dyn_cast<GepObjVar>(pagNode))
        {
            if(SVFUtil::isa<DummyObjVar>(pag->getGNode(gepobj->getBaseNode())))
                continue;
        }
        if ((isa<ObjVar>(pagNode) && isa<GlobalObjVar>(pag->getBaseObject(pagNode->getId()))) ||
                (isa<ValVar>(pagNode) && isa<GlobalValVar>(pag->getBaseValVar(pagNode->getId()))))
            worklist.push_back(it->first);
    }
 
    NodeToPTSSMap cachedPtsMap;
    while(!worklist.empty())
    {
        NodeID id = worklist.back();
        worklist.pop_back();
        globs.set(id);
        const PointsTo& pts = pta->getPts(id);
        for(PointsTo::iterator it = pts.begin(), eit = pts.end(); it!=eit; ++it)
        {
            globs |= CollectPtsChain(pta,*it,cachedPtsMap);
        }
    }
}

◆ CollectPtsChain()

PointsTo & SaberSVFGBuilder::CollectPtsChain	(	BVDataPTAImpl *	pta,
		NodeID	id,
		NodeToPTSSMap &	cachedPtsMap
	)

protected

Collect objects along points-to chains.

Definition at line 120 of file SaberSVFGBuilder.cpp.

{
    SVFIR* pag = svfg->getPAG();
 
    NodeID baseId = pag->getBaseObjVar(id);
    NodeToPTSSMap::iterator it = cachedPtsMap.find(baseId);
    if(it!=cachedPtsMap.end())
    {
        return it->second;
    }
    else
    {
        PointsTo& pts = cachedPtsMap[baseId];
        // base object
        if (!Options::CollectExtRetGlobals())
        {
            if(pta->isFIObjNode(baseId) && pag->getGNode(baseId)->hasValue())
            {
                ValVar* valVar = SVFUtil::dyn_cast<ValVar>(pag->getGNode(baseId));
                if(valVar && valVar->getICFGNode() && SVFUtil::isExtCall(valVar->getICFGNode()))
                {
                    return pts;
                }
            }
        }
 
        pts |= pag->getFieldsAfterCollapse(baseId);
 
        WorkList worklist;
        for(PointsTo::iterator it = pts.begin(), eit = pts.end(); it!=eit; ++it)
            worklist.push(*it);
 
        while(!worklist.empty())
        {
            NodeID nodeId = worklist.pop();
            const PointsTo& tmp = pta->getPts(nodeId);
            for(PointsTo::iterator it = tmp.begin(), eit = tmp.end(); it!=eit; ++it)
            {
                pts |= CollectPtsChain(pta,*it,cachedPtsMap);
            }
        }
        return pts;
    }
}

◆ isGlobalSVFGNode()

bool SVF::SaberSVFGBuilder::isGlobalSVFGNode ( const SVFGNode * node ) const

inline

Definition at line 57 of file SaberSVFGBuilder.h.

    {
        return globSVFGNodes.find(node)!=globSVFGNodes.end();
    }

◆ isStrongUpdate()

bool SaberSVFGBuilder::isStrongUpdate	(	const SVFGNode *	node,
		NodeID &	singleton,
		BVDataPTAImpl *	pta
	)

protected

Return TRUE if this is a strong update STORE statement.

Find the unique element in cpts

Definition at line 222 of file SaberSVFGBuilder.cpp.

{
    bool isSU = false;
    if (const StoreSVFGNode* store = SVFUtil::dyn_cast<StoreSVFGNode>(node))
    {
        const PointsTo& dstCPSet = pta->getPts(store->getPAGDstNodeID());
        if (dstCPSet.count() == 1)
        {
            PointsTo::iterator it = dstCPSet.begin();
            singleton = *it;
 
            // Strong update can be made if this points-to target is not heap, array or field-insensitive.
            if (!pta->isHeapMemObj(singleton) && !pta->isArrayMemObj(singleton)
                    && SVFIR::getPAG()->getBaseObj(singleton)->isFieldInsensitive() == false
                    && !pta->isLocalVarInRecursiveFun(singleton))
            {
                isSU = true;
            }
        }
    }
    return isSU;
}

◆ rmDerefDirSVFGEdges()

void SaberSVFGBuilder::rmDerefDirSVFGEdges ( BVDataPTAImpl * pta )

protected

Remove direct value-flow edge to a dereference point for Saber source-sink memory error detection for example, given two statements: p = alloc; q = *p, the direct SVFG edge between them is deleted Because those edges only stand for values used at the dereference points but they can not pass the value to other definitions

for store, connect the RHS/LHS pointer to its def

Definition at line 178 of file SaberSVFGBuilder.cpp.

{
 
    for(SVFG::iterator it = svfg->begin(), eit = svfg->end(); it!=eit; ++it)
    {
        const SVFGNode* node = it->second;
 
        if(const StmtSVFGNode* stmtNode = SVFUtil::dyn_cast<StmtSVFGNode>(node))
        {
            if(SVFUtil::isa<StoreSVFGNode>(stmtNode))
            {
                const SVFGNode* def = svfg->getDefSVFGNode(stmtNode->getPAGDstNode());
                if(SVFGEdge* edge = svfg->getIntraVFGEdge(def,stmtNode,SVFGEdge::IntraDirectVF))
                    svfg->removeSVFGEdge(edge);
                else
                    assert((svfg->getKind()==VFG::FULLSVFG_OPT || svfg->getKind()==VFG::PTRONLYSVFG_OPT)  && "Edge not found!");
 
                if(accessGlobal(pta,stmtNode->getPAGDstNode()))
                {
                    globSVFGNodes.insert(stmtNode);
                }
            }
            else if(SVFUtil::isa<LoadSVFGNode>(stmtNode))
            {
                const SVFGNode* def = svfg->getDefSVFGNode(stmtNode->getPAGSrcNode());
                if(SVFGEdge* edge = svfg->getIntraVFGEdge(def,stmtNode,SVFGEdge::IntraDirectVF))
                    svfg->removeSVFGEdge(edge);
                else
                    assert((svfg->getKind()==VFG::FULLSVFG_OPT || svfg->getKind()==VFG::PTRONLYSVFG_OPT)  && "Edge not found!");
 
                if(accessGlobal(pta,stmtNode->getPAGSrcNode()))
                {
                    globSVFGNodes.insert(stmtNode);
                }
            }
 
        }
    }
}

◆ rmIncomingEdgeForSUStore()

void SaberSVFGBuilder::rmIncomingEdgeForSUStore ( BVDataPTAImpl * pta )

protectedvirtual

Remove Incoming Edge for strong-update (SU) store instruction Because the SU node does not receive indirect value

e.g., L1: *p = O; (singleton) L2: *p = _; (SU here) We should remove the indirect value flow L1 -> L2 Because the points-to set of O from L1 does not pass to that after L2

Reimplemented in SVF::CFLSVFGBuilder.

Definition at line 256 of file SaberSVFGBuilder.cpp.

{
 
    for(SVFG::iterator it = svfg->begin(), eit = svfg->end(); it!=eit; ++it)
    {
        const SVFGNode* node = it->second;
 
        if(const StoreSVFGNode* stmtNode = SVFUtil::dyn_cast<StoreSVFGNode>(node))
        {
            if(SVFUtil::isa<StoreStmt>(stmtNode->getPAGEdge()))
            {
                NodeID singleton;
                if(isStrongUpdate(node, singleton, pta))
                {
                    Set<SVFGEdge*> toRemove;
                    for (SVFGNode::const_iterator it2 = node->InEdgeBegin(), eit2 = node->InEdgeEnd(); it2 != eit2; ++it2)
                    {
                        if ((*it2)->isIndirectVFGEdge())
                        {
                            toRemove.insert(*it2);
                        }
                    }
                    for (SVFGEdge* edge: toRemove)
                    {
                        if (isa<StoreSVFGNode>(edge->getSrcNode()))
                            saberCondAllocator->getRemovedSUVFEdges()[edge->getSrcNode()].insert(edge->getDstNode());
                        svfg->removeSVFGEdge(edge);
                    }
                }
            }
        }
    }
}

◆ setSaberCondAllocator()

void SVF::SaberSVFGBuilder::setSaberCondAllocator ( SaberCondAllocator * allocator )

inline

Definition at line 68 of file SaberSVFGBuilder.h.

    {
        saberCondAllocator = allocator;
    }

Member Data Documentation

◆ globs

PointsTo SVF::SaberSVFGBuilder::globs

protected

Definition at line 105 of file SaberSVFGBuilder.h.

◆ globSVFGNodes

SVFGNodeSet SVF::SaberSVFGBuilder::globSVFGNodes

protected

Store all global SVFG nodes.

Definition at line 107 of file SaberSVFGBuilder.h.

◆ saberCondAllocator

SaberCondAllocator* SVF::SaberSVFGBuilder::saberCondAllocator

protected

Definition at line 109 of file SaberSVFGBuilder.h.

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

/home/runner/work/SVF/SVF/svf/include/SABER/SaberSVFGBuilder.h
/home/runner/work/SVF/SVF/svf/lib/SABER/SaberSVFGBuilder.cpp

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ NodeToPTSSMap

◆ SVFGNodeSet

◆ WorkList

Constructor & Destructor Documentation

◆ SaberSVFGBuilder()

◆ ~SaberSVFGBuilder()

Member Function Documentation

◆ accessGlobal()

◆ addActualParmVFGNode()

◆ AddExtActualParmSVFGNodes()

◆ buildSVFG()

◆ collectGlobals()

◆ CollectPtsChain()

◆ isGlobalSVFGNode()

◆ isStrongUpdate()

◆ rmDerefDirSVFGEdges()

◆ rmIncomingEdgeForSUStore()

◆ setSaberCondAllocator()

Member Data Documentation

◆ globs

◆ globSVFGNodes

◆ saberCondAllocator