SVF::MTASlicerBase Class Reference

#include <MTASlicer.h>

Inheritance diagram for SVF::MTASlicerBase:

Public Member Functions
	MTASlicerBase (SVFIR *svfIr, AndersenBase *pta, MHP *mhp, LockAnalysis *lockAnalysis, SVFG *vfg=nullptr)
virtual	~MTASlicerBase ()

Protected Member Functions
OrderedSet< const ICFGNode * >	sliceDataDependenceOverVFG (const OrderedSet< const SVFStmt * > &seeds, SVFG *vfg)
OrderedSet< const VFGNode * >	computeDataDependenceSVFGNodes (const OrderedSet< const SVFStmt * > &seeds, SVFG *vfg)
OrderedSet< const ICFGNode * >	svfgNodesToICFGNodes (const OrderedSet< const VFGNode * > &nodes, const OrderedSet< const SVFStmt * > &seeds)
	Project the retained VFG nodes (plus the seeds) onto their ICFG nodes.
OrderedSet< const SVFStmt * >	getDependentThreadCreate (const SVFStmt *stmt)
OrderedSet< const TCTNode * >	getTCTNodeSetFromNode (const ICFGNode *node)
OrderedSet< const ICFGNode * >	getLockSet (const ICFGNode *node)
OrderedSet< const CallICFGNode * >	collectPthreadStatements (const OrderedSet< const SVFStmt * > &vulnerableStmts)
OrderedSet< const CallICFGNode * >	collectMutexStatements (const OrderedSet< const SVFStmt * > &vulnerableStmts)
std::pair< OrderedSet< const CallICFGNode * >, OrderedSet< const CallICFGNode * > >	collectCommonThreadStatements (const OrderedSet< const SVFStmt * > &vulnerableStatements)
OrderedSet< const ICFGNode * >	buildBackwardICFGNodeSet (const OrderedSet< const ICFGNode * > &vulnerableNodes)
OrderedSet< const ICFGNode * >	expandCallDependence (const OrderedSet< const ICFGNode * > &nodes)
OrderedSet< const ICFGNode * >	runDualSlicing (const OrderedSet< const ICFGNode * > &slicedNodes)

Protected Attributes
SVFIR *	svfIr
AndersenBase *	pta
MHP *	mhp
LockAnalysis *	lockAnalysis
CallGraph *	callGraph
SVFG *	vfg
	thread-aware VFG_pre (PTA/Single slicers; null for MTA)

Detailed Description

MTASlicerBase - Base class for program slicing.

Holds the shared helper methods and data members used by both concrete slicers (the ILA and FSPTA stages of MultiStageSlicer).

Definition at line 119 of file MTASlicer.h.

Constructor & Destructor Documentation

MTASlicerBase()

SVF::MTASlicerBase::MTASlicerBase	(	SVFIR *	svfIr,
		AndersenBase *	pta,
		MHP *	mhp,
		LockAnalysis *	lockAnalysis,
		SVFG *	vfg = nullptr
	)

Definition at line 410 of file MTASlicer.cpp.

    : svfIr(svfIr), pta(pta), mhp(mhp), lockAnalysis(lockAnalysis), vfg(vfg)
{
    callGraph = pta->getCallGraph();
}

~MTASlicerBase()

SVF::MTASlicerBase::~MTASlicerBase ( )

virtual

Definition at line 417 of file MTASlicer.cpp.

{
    // No dynamic memory to clean up - all pointers are managed externally
}

Member Function Documentation

buildBackwardICFGNodeSet()

OrderedSet< const ICFGNode * > SVF::MTASlicerBase::buildBackwardICFGNodeSet ( const OrderedSet< const ICFGNode * > &  vulnerableNodes )

protected

Definition at line 747 of file MTASlicer.cpp.

{
    OrderedSet<const ICFGNode*> backwardICFGNodeSet;
    std::deque<const ICFGNode*> worklist;
 
    // Initialize with vulnerable nodes
    for (const ICFGNode* node : vulnerableNodes)
    {
        backwardICFGNodeSet.insert(node);
        worklist.push_back(node);
    }
 
    // Traverse backward along ICFG edges
    while (!worklist.empty())
    {
        const ICFGNode* currICFGNode = worklist.front();
        worklist.pop_front();
 
        for (const ICFGEdge* inEdge : currICFGNode->getInEdges())
        {
            const ICFGNode* srcNode = inEdge->getSrcNode();
            if (backwardICFGNodeSet.find(srcNode) == backwardICFGNodeSet.end())
            {
                backwardICFGNodeSet.insert(srcNode);
                worklist.push_back(srcNode);
            }
        }
    }
 
    return backwardICFGNodeSet;
}

collectCommonThreadStatements()

std::pair< OrderedSet< const CallICFGNode * >, OrderedSet< const CallICFGNode * > > SVF::MTASlicerBase::collectCommonThreadStatements ( const OrderedSet< const SVFStmt * > &  vulnerableStatements )

protected

Collect common pthread and mutex statements (shared by PTA and MTA slicing).

Parameters

vulnerableStatements

Set of vulnerable statements

Returns

Pair of (pthreadCallNodes, mutexCallNodes)

Definition at line 700 of file MTASlicer.cpp.

{
    // Step 1: Collect pthread-related statements, i.e., pthread_create and pthread_join
    OrderedSet<const CallICFGNode*> pthreadCallNodes = collectPthreadStatements(vulnerableStatements);
 
    // Step 2: Collect mutex-related statements
    OrderedSet<const CallICFGNode*> mutexCallNodes = collectMutexStatements(vulnerableStatements);
 
    return std::make_pair(pthreadCallNodes, mutexCallNodes);
}

collectMutexStatements()

OrderedSet< const CallICFGNode * > SVF::MTASlicerBase::collectMutexStatements ( const OrderedSet< const SVFStmt * > &  vulnerableStmts )

protected

Definition at line 643 of file MTASlicer.cpp.

{
    OrderedSet<const CallICFGNode*> mutexCallNodes;
 
    ThreadCallGraph* tcg = mhp->getThreadCallGraph();
    ThreadAPI* threadAPI = tcg->getThreadAPI();
 
    // Map mutex_lock nodes to their corresponding mutex_unlock nodes
    OrderedSet<const CallICFGNode*> mutexLockCallNodes;
 
    // First pass: collect all mutex_lock nodes from lock sets
    for (const SVFStmt* stmt : vulnerableStmts)
    {
        OrderedSet<const ICFGNode*> lockSet = getLockSet(stmt->getICFGNode());
        for (const ICFGNode* lockNode : lockSet)
        {
            const CallICFGNode* lockCallNode = SVFUtil::dyn_cast<CallICFGNode>(lockNode);
            if (lockCallNode != nullptr && threadAPI->isTDAcquire(lockCallNode))
            {
                mutexCallNodes.insert(lockCallNode);
                mutexLockCallNodes.insert(lockCallNode);
            }
        }
    }
 
    // Second pass: find corresponding mutex_unlock nodes
    ICFG* icfg = svfIr->getICFG();
    for (ICFG::iterator it = icfg->begin(), eit = icfg->end(); it != eit; ++it)
    {
        const ICFGNode* node = it->second;
        const CallICFGNode* callNode = SVFUtil::dyn_cast<CallICFGNode>(node);
        if (callNode != nullptr && threadAPI->isTDRelease(callNode))
        {
            const SVFVar* unlockVar = threadAPI->getLockVal(callNode);
            if (unlockVar != nullptr)
            {
                for (auto lockCallNode : mutexLockCallNodes)
                {
                    if (lockCallNode != nullptr)
                    {
                        const SVFVar* lockVar = threadAPI->getLockVal(lockCallNode);
                        if (lockVar != nullptr && pta->alias(unlockVar->getId(), lockVar->getId()))
                        {
                            mutexCallNodes.insert(callNode);
                        }
                    }
                }
            }
        }
    }
 
    return mutexCallNodes;
}

collectPthreadStatements()

OrderedSet< const CallICFGNode * > SVF::MTASlicerBase::collectPthreadStatements ( const OrderedSet< const SVFStmt * > &  vulnerableStmts )

protected

Definition at line 583 of file MTASlicer.cpp.

{
    OrderedSet<const CallICFGNode*> pthreadCallNodes;
 
    ThreadCallGraph* tcg = mhp->getThreadCallGraph();
    ThreadAPI* threadAPI = tcg->getThreadAPI();
 
    // Map pthread_create nodes to their corresponding pthread_join nodes
    OrderedSet<const SVFStmt*> pthreadCreateStmts;
 
    // First pass: collect all pthread_create nodes
    for (const SVFStmt* stmt : vulnerableStmts)
    {
        OrderedSet<const SVFStmt*> forkSiteStmts = getDependentThreadCreate(stmt);
 
        for (const SVFStmt* forkSiteStmt : forkSiteStmts)
        {
            const ICFGNode* forkSiteNode = forkSiteStmt->getICFGNode();
            const CallICFGNode* forkCallNode = SVFUtil::dyn_cast<CallICFGNode>(forkSiteNode);
            if (forkCallNode != nullptr && threadAPI->isTDFork(forkCallNode))
            {
                pthreadCallNodes.insert(forkCallNode);
                pthreadCreateStmts.insert(forkSiteStmt);
            }
        }
    }
 
    // Second pass: find corresponding pthread_join nodes
    ICFG* icfg = svfIr->getICFG();
    for (ICFG::iterator it = icfg->begin(), eit = icfg->end(); it != eit; ++it)
    {
        const ICFGNode* node = it->second;
        const CallICFGNode* callNode = SVFUtil::dyn_cast<CallICFGNode>(node);
        if (callNode != nullptr && threadAPI->isTDJoin(callNode))
        {
            const SVFVar* joinThread = threadAPI->getJoinedThread(callNode);
            if (joinThread != nullptr)
            {
                for (auto& createStmt : pthreadCreateStmts)
                {
                    const ICFGNode* createNode = createStmt->getICFGNode();
                    const CallICFGNode* createCallNode = SVFUtil::dyn_cast<CallICFGNode>(createNode);
                    if (createCallNode != nullptr)
                    {
                        const SVFVar* forkedThread = threadAPI->getForkedThread(createCallNode);
                        if (forkedThread != nullptr && threadAPI->isAliasedForkJoin(pta, forkedThread, joinThread))
                        {
                            pthreadCallNodes.insert(callNode);
                        }
                    }
                }
            }
        }
    }
 
    return pthreadCallNodes;
}

computeDataDependenceSVFGNodes()

OrderedSet< const SVFGNode * > SVF::MTASlicerBase::computeDataDependenceSVFGNodes ( const OrderedSet< const SVFStmt * > &  seeds, SVFG *  vfg  )

protected

The SVFG-node granularity of the data-dependence slice above: the set of VFG nodes reachable backward from the seeds. ThreadVF(VFG'_pre) is exactly the thread-aware edges whose both endpoints lie in this set, so ILA slicing uses it to restrict the [THREAD-VF] sources to surviving edges.

Definition at line 507 of file MTASlicer.cpp.

{
 
    assert(vfg != nullptr && "data-dependence slice requires the thread-aware VFG_pre");
 
    OrderedSet<const SVFGNode*> visited;
    std::deque<const SVFGNode*> worklist;
    auto seed = [&](const SVFGNode* n)
    {
        if (n != nullptr && visited.insert(n).second)
            worklist.push_back(n);
    };
 
    // Seed from the value-flow nodes of the given (e.g. race target) statements.
    // VFG_pre is a pointer-only SVFG, so a load/store of a NON-pointer value (the
    // usual case -- a race on an int/float field) has no statement node. For those
    // we must still preserve the points-to of the dereferenced address pointer, or
    // the sliced flow-sensitive solve sees an empty slice for it, computes empty
    // points-to, and drops the race (a soundness bug). So additionally seed from the
    // definition of each load/store's address pointer (always a pointer, hence
    // always in the pointer-only SVFG); its backward closure keeps the pointer's
    // def chain regardless of the value type.
    for (const SVFStmt* stmt : seeds)
    {
        if (vfg->hasStmtVFGNode(stmt))
            seed(vfg->getStmtVFGNode(stmt));
 
        NodeID addrPtr = 0;
        if (const LoadStmt* ld = SVFUtil::dyn_cast<LoadStmt>(stmt))
            addrPtr = ld->getRHSVarID();
        else if (const StoreStmt* st = SVFUtil::dyn_cast<StoreStmt>(stmt))
            addrPtr = st->getLHSVarID();
        if (addrPtr != 0)
        {
            // getDefSVFGNode takes a ValVar (the address pointer is a top-level
            // value variable).
            const ValVar* ptrNode = SVFUtil::dyn_cast<ValVar>(svfIr->getGNode(addrPtr));
            if (ptrNode != nullptr && vfg->hasDefSVFGNode(ptrNode))
                seed(vfg->getDefSVFGNode(ptrNode));
        }
    }
 
    // Backward over every value-flow edge.
    while (!worklist.empty())
    {
        const SVFGNode* n = worklist.front();
        worklist.pop_front();
        for (const VFGEdge* e : n->getInEdges())
            seed(e->getSrcNode());
    }
 
    return visited;
}

expandCallDependence()

OrderedSet< const ICFGNode * > SVF::MTASlicerBase::expandCallDependence ( const OrderedSet< const ICFGNode * > &  nodes )

protected

Call-dependence expansion (used by MultiStageSlicer): take the kept functions of the given nodes, close upward over the call graph (every transitive caller), then add each kept function's entry/exit nodes and the call/ret nodes of every call site targeting it.

Parameters

nodes

Current set of ICFG nodes

Returns

The input nodes plus the call/ret and entry/exit nodes above

Definition at line 815 of file MTASlicer.cpp.

{
 
    // Determine keptFunctions from the given nodes
    OrderedSet<const FunObjVar*> keptFunctions;
    for (const ICFGNode* node : nodes)
    {
        if (node != nullptr && node->getFun() != nullptr)
        {
            keptFunctions.insert(node->getFun());
        }
    }
 
    // Build ancestor closure (upward traversal in call graph)
    std::queue<const FunObjVar*> worklistFuncs;
    for (const FunObjVar* fun : keptFunctions)
    {
        worklistFuncs.push(fun);
    }
 
    Map<const FunObjVar*, const CallGraphNode*> fun2Node;
    for (auto it = callGraph->begin(), eit = callGraph->end(); it != eit; ++it)
    {
        const CallGraphNode* node = it->second;
        if (node && node->getFunction())
        {
            fun2Node[node->getFunction()] = node;
        }
    }
 
    OrderedSet<const FunObjVar*> visitedFuncs = keptFunctions;
    while (!worklistFuncs.empty())
    {
        const FunObjVar* target = worklistFuncs.front();
        worklistFuncs.pop();
        auto nodeIt = fun2Node.find(target);
        if (nodeIt == fun2Node.end()) continue;
 
        const CallGraphNode* node = nodeIt->second;
        for (const CallGraphEdge* inEdge : node->getInEdges())
        {
            if (inEdge == nullptr) continue;
            const CallGraphNode* callerNode = inEdge->getSrcNode();
            if (callerNode && callerNode->getFunction())
            {
                const FunObjVar* callerFun = callerNode->getFunction();
                if (visitedFuncs.find(callerFun) == visitedFuncs.end())
                {
                    keptFunctions.insert(callerFun);
                    visitedFuncs.insert(callerFun);
                    worklistFuncs.push(callerFun);
                }
            }
        }
    }
 
    // For each keptFunction, add call/ret nodes and entry/exit nodes
    ICFG* icfg = svfIr->getICFG();
    OrderedSet<const ICFGNode*> expandedNodes = nodes;
    for (const FunObjVar* fun : keptFunctions)
    {
        if (!fun) continue;
 
        // Add function entry/exit nodes
        if (fun->hasBasicBlock())
        {
            if (FunEntryICFGNode* entry = icfg->getFunEntryICFGNode(fun))
            {
                expandedNodes.insert(entry);
            }
            if (FunExitICFGNode* exit = icfg->getFunExitICFGNode(fun))
            {
                expandedNodes.insert(exit);
            }
        }
 
        // Find all call/ret nodes that call this function
        auto funNodeIt = fun2Node.find(fun);
        if (funNodeIt != fun2Node.end())
        {
            const CallGraphNode* calleeNode = funNodeIt->second;
 
            // Traverse all edges that call this function
            for (const CallGraphEdge* inEdge : calleeNode->getInEdges())
            {
                if (inEdge == nullptr) continue;
 
                const CallGraphEdge::CallInstSet &directCalls = inEdge->getDirectCalls();
                const CallGraphEdge::CallInstSet &indirectCalls = inEdge->getIndirectCalls();
 
                for (const CallICFGNode* callNode : directCalls)
                {
                    if (callNode != nullptr)
                    {
                        expandedNodes.insert(callNode);
                        const RetICFGNode* retNode = callNode->getRetICFGNode();
                        if (retNode != nullptr)
                        {
                            expandedNodes.insert(retNode);
                        }
                    }
                }
 
                for (const CallICFGNode* callNode : indirectCalls)
                {
                    if (callNode != nullptr)
                    {
                        expandedNodes.insert(callNode);
                        const RetICFGNode* retNode = callNode->getRetICFGNode();
                        if (retNode != nullptr)
                        {
                            expandedNodes.insert(retNode);
                        }
                    }
                }
            }
        }
    }
 
    return expandedNodes;
}

getDependentThreadCreate()

OrderedSet< const SVFStmt * > SVF::MTASlicerBase::getDependentThreadCreate ( const SVFStmt *  stmt )

protected

Definition at line 479 of file MTASlicer.cpp.

{
    OrderedSet<const SVFStmt*> forkSiteStmts;
 
    const ICFGNode* icfgNode = stmt->getICFGNode();
    OrderedSet<const TCTNode*> tctNodeSet = getTCTNodeSetFromNode(icfgNode);
 
    for (const TCTNode* tctNode : tctNodeSet)
    {
        const CxtThread& cxtThread = tctNode->getCxtThread();
        const ICFGNode* forkSite = cxtThread.getThread();
        if (forkSite != nullptr)
        {
            const ICFGNode::SVFStmtList& svfStmts = forkSite->getSVFStmts();
            if (!svfStmts.empty())
            {
                forkSiteStmts.insert(svfStmts.front());
            }
        }
    }
 
    return forkSiteStmts;
}

getLockSet()

OrderedSet< const ICFGNode * > SVF::MTASlicerBase::getLockSet ( const ICFGNode *  node )

protected

Definition at line 423 of file MTASlicer.cpp.

{
    OrderedSet<const ICFGNode*> allLockSites;
 
    // Get intra-procedural locks
    if (lockAnalysis->isInsideIntraLock(node) &&
            !lockAnalysis->isInsideCondIntraLock(node))
    {
        const LockAnalysis::InstSet& intraLocks = lockAnalysis->getIntraLockSet(node);
        for (const ICFGNode* lockSite : intraLocks)
        {
            allLockSites.insert(lockSite);
        }
    }
 
    // Get context-sensitive locks
    if (lockAnalysis->hasCxtStmtFromInst(node))
    {
        const LockAnalysis::CxtStmtSet& cxtStmts = lockAnalysis->getCxtStmtsFromInst(node);
        for (const CxtStmt& cxtStmt : cxtStmts)
        {
            if (lockAnalysis->hasCxtLockfromCxtStmt(cxtStmt))
            {
                const LockAnalysis::CxtLockSet& cxtLocks =
                    lockAnalysis->getCxtLockfromCxtStmt(cxtStmt);
                for (const LockAnalysis::CxtLock& cxtLock : cxtLocks)
                {
                    allLockSites.insert(cxtLock.getStmt());
                }
            }
        }
    }
 
    return allLockSites;
}

getTCTNodeSetFromNode()

OrderedSet< const TCTNode * > SVF::MTASlicerBase::getTCTNodeSetFromNode ( const ICFGNode *  node )

protected

Definition at line 460 of file MTASlicer.cpp.

{
    OrderedSet<const TCTNode*> tctNodeSet;
 
    if (mhp->hasThreadStmtSet(node))
    {
        for (const CxtThreadStmt& cts : mhp->getThreadStmtSet(node))
        {
            if (mhp->getTCT()->hasGNode(cts.getTid()))
            {
                tctNodeSet.insert(mhp->getTCT()->getTCTNode(cts.getTid()));
            }
        }
    }
 
    return tctNodeSet;
}

runDualSlicing()

OrderedSet< const ICFGNode * > SVF::MTASlicerBase::runDualSlicing ( const OrderedSet< const ICFGNode * > &  slicedNodes )

protected

Perform dual slicing (temporal slicing): filter statements based on control flow and parallel execution. This is shared by both PTA and MTA slicing.

Parameters

slicedNodes

Set of statements from statement-level slicing

Returns

Set of ICFG nodes in the dual slice

Definition at line 781 of file MTASlicer.cpp.

{
    OrderedSet<const ICFGNode*> dualSlicedNodes;
 
    // Build backward ICFG node set
    OrderedSet<const ICFGNode*> backwardICFGNodeSet = buildBackwardICFGNodeSet(slicedNodes);
 
    // Perform control slicing
    for (const ICFGNode* stmtICFGNode : slicedNodes)
    {
        // Check if the ICFG node is in backward_icfg_node_set
        if (backwardICFGNodeSet.find(stmtICFGNode) != backwardICFGNodeSet.end())
        {
            dualSlicedNodes.insert(stmtICFGNode);
        }
        else
        {
            // Check if it may happen in parallel with any vulnerable node
            for (const ICFGNode* bugICFGNode : slicedNodes)
            {
                if (mhp->mayHappenInParallelCache(stmtICFGNode, bugICFGNode))
                {
                    dualSlicedNodes.insert(stmtICFGNode);
                    break;
                }
            }
        }
    }
 
    return dualSlicedNodes;
}

sliceDataDependenceOverVFG()

OrderedSet< const ICFGNode * > SVF::MTASlicerBase::sliceDataDependenceOverVFG ( const OrderedSet< const SVFStmt * > &  seeds, SVFG *  vfg  )

protected

Paper-faithful (§4.3) data-dependence slice over the thread-aware SVFG (VFG_pre): seed from the value-flow nodes of the given statements and backward-traverse every value-flow edge – direct (top-level def-use), indirect (address-taken / MemSSA def-use), and thread-aware interference. Returns the kept ICFG nodes. This is the single dependence model used by the FSPTA stage.

Definition at line 576 of file MTASlicer.cpp.

{
    return svfgNodesToICFGNodes(computeDataDependenceSVFGNodes(seeds, vfg), seeds);
}

svfgNodesToICFGNodes()

OrderedSet< const ICFGNode * > SVF::MTASlicerBase::svfgNodesToICFGNodes ( const OrderedSet< const VFGNode * > &  nodes, const OrderedSet< const SVFStmt * > &  seeds  )

protected

Project the retained VFG nodes (plus the seeds) onto their ICFG nodes.

Definition at line 563 of file MTASlicer.cpp.

{
    OrderedSet<const ICFGNode*> result;
    for (const SVFGNode* n : nodes)
        if (const StmtVFGNode* s = SVFUtil::dyn_cast<StmtVFGNode>(n))
            if (s->getICFGNode() != nullptr)
                result.insert(s->getICFGNode());
    for (const SVFStmt* stmt : seeds)
        result.insert(stmt->getICFGNode());
    return result;
}

Member Data Documentation

callGraph

CallGraph* SVF::MTASlicerBase::callGraph

protected

Definition at line 131 of file MTASlicer.h.

lockAnalysis

LockAnalysis* SVF::MTASlicerBase::lockAnalysis

protected

Definition at line 130 of file MTASlicer.h.

mhp

MHP* SVF::MTASlicerBase::mhp

protected

Definition at line 129 of file MTASlicer.h.

pta

AndersenBase* SVF::MTASlicerBase::pta

protected

Definition at line 128 of file MTASlicer.h.

svfIr

SVFIR* SVF::MTASlicerBase::svfIr

protected

Definition at line 127 of file MTASlicer.h.

vfg

SVFG* SVF::MTASlicerBase::vfg

protected

thread-aware VFG_pre (PTA/Single slicers; null for MTA)

Definition at line 132 of file MTASlicer.h.

---

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

• /home/runner/work/SVF/SVF/svf/include/MTA/MTASlicer.h
• /home/runner/work/SVF/SVF/svf/lib/MTA/MTASlicer.cpp