SVF::SlicedMTA Class Reference

#include <MTA.h>

Classes
struct	RaceDigests

Public Types
using	RacePair = MTA::RacePair
	The shared race detector lives in MTA; reuse its race-pair type.

Public Member Functions
	SlicedMTA ()
	~SlicedMTA ()
	SlicedMTA (const SlicedMTA &)=delete
SlicedMTA &	operator= (const SlicedMTA &)=delete
bool	runOnModule (SVFIR *pag, AndersenWaveDiff &preAnalysis)
	Run the slicing pipeline with its prepared Andersen pre-analysis.

Private Member Functions
bool	runPreAnalysis ()
bool	runMTASlicingAndAnalysis ()
bool	runPTASlicingAndAnalysis ()
bool	runFinalRaceDetection ()
void	buildPreAnalysisSVFG ()
bool	runWholeProgramDetection ()
BVDataPTAImpl *	getMainPTA () const
std::set< const SVFStmt * >	getVulnerableStmts () const
	Union of both statements of every candidate race pair (the slice targets).
std::set< RacePair >	detectRacePairsOnSlicedGraph (const std::set< RacePair > &preAnalysisRacePairs, BVDataPTAImpl *slicedPTA, MHP *slicedMHP, LockAnalysis *slicedLockAnalysis)
	Refine the pre-analysis candidate pairs with main-phase ILA and FSAM.

Static Private Member Functions
static void	reportOriginalStatistics (SVFIR *svfir)
	Pipeline utilities shared by the sliced and whole-program paths.
static std::set< const ICFGNode * >	collectICFGNodes (SVFG *svfg, const NodeBS &svfgNodeIds)
static void	reportPTASliceStatistics (const std::set< const ICFGNode * > &icfgNodes)
static std::string	raceStatementKey (const SVFStmt *statement)
static void	updateDigest (u64_t &digest, const std::string &value)
static RaceDigests	computeRaceDigests (const std::set< RacePair > &pairs)

Private Attributes
SVFIR *	svfir = nullptr
u32_t	mainContextDepth
std::unique_ptr< TCT >	tct
std::unique_ptr< MHP >	mhp
std::unique_ptr< LockAnalysis >	lockAnalysis
AndersenWaveDiff *	preAndersen = nullptr
ThreadCallGraph *	threadCallGraph = nullptr
std::unique_ptr< MTASVFGBuilder >	preSVFGBuilder
SVFG *	preSVFG = nullptr
std::unique_ptr< MultiStageSlicer >	multiStageSlicer
NodeBS	preCandidateSolveNodeIds
std::unique_ptr< SingleSlicer >	singleSlicer
MTASVFGBuilder::ThreadVFCandidateList	selectedThreadVFCandidates
std::set< const ICFGNode * >	singleSlicedNodes
NodeBS	singleSlicedSVFGNodeIds
std::unique_ptr< SlicedSVFIRView >	mtaSlicedView
std::unique_ptr< SlicedSVFIRView >	ptaSlicedView
std::unique_ptr< SlicedSVFGView >	slicedSVFGView
std::unique_ptr< FlowSensitive >	mainFSMPTA
std::unique_ptr< SlicedTCT >	slicedTCT
std::unique_ptr< MHP >	slicedMHP
std::unique_ptr< LockAnalysis >	slicedLockAnalysis
bool	hasThreadFunctions = false
std::set< RacePair >	racePairs

Detailed Description

Multi-stage on-demand slicing race detection pipeline (MSli).

runOnModule drives five stages on a pre-built SVFIR:

1. (caller) build SVFIR + resolve indirect calls into the PAG
2. pre-analysis: Andersen, TCT, MHP, lock, candidate race pairs, VFG_pre
3. MTA slicing: slice the thread-aware graph, build the sliced MHP/lock
4. PTA slicing + main flow-sensitive FSAM (FSMPTA) on the slice
5. final race detection on the sliced graph using FSAM points-to

It operates entirely on the SVFIR (LLVM-free). The LLVM-aware caller runs the Andersen pre-analysis and materialises its resolved indirect calls into the PAG before invoking runOnModule.

Behaviour is controlled by Options (MTFlowSensitive, MTAEnableSlicing, MTASingleStageSlicing, DumpMTAGraphs).

Definition at line 226 of file MTA.h.

Member Typedef Documentation

RacePair

using SVF::SlicedMTA::RacePair = MTA::RacePair

The shared race detector lives in MTA; reuse its race-pair type.

Definition at line 230 of file MTA.h.

Constructor & Destructor Documentation

SlicedMTA() [1/2]

SlicedMTA::SlicedMTA

(

)

Definition at line 581 of file MTA.cpp.

                     : mainContextDepth(Options::MaxContextLen())
{
}

~SlicedMTA()

SlicedMTA::~SlicedMTA ( )

default

SlicedMTA() [2/2]

SVF::SlicedMTA::SlicedMTA ( const SlicedMTA &  )

delete

Member Function Documentation

buildPreAnalysisSVFG()

void SlicedMTA::buildPreAnalysisSVFG ( )

private

Definition at line 608 of file MTA.cpp.

{
    ScopedPhaseTimer timer("Build thread-aware VFG_pre");
    // Treat fork/join as calls so the SVFG carries the thread-oblivious
    // (fork/join-ordered) value flow.
    if (ThreadCallGraph* tcg = SVFUtil::dyn_cast<ThreadCallGraph>(preAndersen->getCallGraph()))
    {
        tcg->updateCallGraph(preAndersen);
        tcg->updateJoinEdge(preAndersen);
    }
    preSVFGBuilder = std::make_unique<MTASVFGBuilder>(
                         mhp.get(), lockAnalysis.get(),
                         MTASVFGBuilder::InterferenceEdgeMode::SlicingOnly);
    // The Pre-TVF overlay is sliced, never solved: omit its interference-edge
    // labels. Main-TVF labels are added after the pre overlay is removed.
    preSVFG = preSVFGBuilder->buildPTROnlySVFG(preAndersen);
    if (isMTAStatEnabled())
        SVFUtil::outs() << "[BaseSVFG] built once: " << preSVFG->getSVFGNodeNum()
                        << " nodes; [Pre-TVF] "
                        << preSVFGBuilder->getThreadAwareEdgeCount()
                        << " interference edges\n";
}

collectICFGNodes()

std::set< const ICFGNode * > SlicedMTA::collectICFGNodes ( SVFG *  svfg, const NodeBS &  svfgNodeIds  )

staticprivate

Definition at line 470 of file MTA.cpp.

{
    std::set<const ICFGNode*> nodes;
    for (NodeID id : svfgNodeIds)
    {
        if (!svfg->hasSVFGNode(id))
            continue;
        if (const StmtVFGNode* stmtNode =
                    SVFUtil::dyn_cast<StmtVFGNode>(svfg->getSVFGNode(id)))
            if (stmtNode->getICFGNode() != nullptr)
                nodes.insert(stmtNode->getICFGNode());
    }
    return nodes;
}

computeRaceDigests()

SlicedMTA::RaceDigests SlicedMTA::computeRaceDigests ( const std::set< RacePair > &  pairs )

staticprivate

Definition at line 543 of file MTA.cpp.

{
    Map<const SVFStmt*, std::string> statementToKey;
    std::set<std::string> statementKeys;
    for (const RacePair& pair : pairs)
    {
        statementToKey.emplace(pair.stmt1, std::string());
        statementToKey.emplace(pair.stmt2, std::string());
    }
    for (auto& statementAndKey : statementToKey)
    {
        statementAndKey.second = raceStatementKey(statementAndKey.first);
        statementKeys.insert(statementAndKey.second);
    }
 
    RaceDigests digests{1469598103934665603ULL, 1469598103934665603ULL};
    for (const std::string& key : statementKeys)
        updateDigest(digests.alarm, key);
 
    std::set<std::pair<std::string, std::string>> pairKeys;
    for (const RacePair& pair : pairs)
    {
        std::string first = statementToKey.at(pair.stmt1);
        std::string second = statementToKey.at(pair.stmt2);
        if (second < first)
            std::swap(first, second);
        pairKeys.emplace(std::move(first), std::move(second));
    }
 
    for (const auto& pair : pairKeys)
    {
        updateDigest(digests.pair, pair.first);
        updateDigest(digests.pair, pair.second);
    }
    return digests;
}

detectRacePairsOnSlicedGraph()

std::set< SlicedMTA::RacePair > SlicedMTA::detectRacePairsOnSlicedGraph ( const std::set< RacePair > &  preAnalysisRacePairs, BVDataPTAImpl *  slicedPTA, MHP *  slicedMHP, LockAnalysis *  slicedLockAnalysis  )

private

Refine the pre-analysis candidate pairs with main-phase ILA and FSAM.

Definition at line 1345 of file MTA.cpp.

{
 
    std::set<RacePair> filteredRacePairs;
 
    // MSli's main phase refines the alarms produced by the conservative
    // pre-analysis. Main ILA and FSMPTA are recomputed independently on their
    // slices; only the candidate universe comes from pre-analysis.
    for (const RacePair& pair : preAnalysisRacePairs)
    {
        const ICFGNode* node1 = pair.stmt1->getICFGNode();
        const ICFGNode* node2 = pair.stmt2->getICFGNode();
 
        if (!slicedMHP->mayHappenInParallelCache(node1, node2))
            continue;
 
        if (slicedLockAnalysis->isProtectedByCommonLock(node1, node2))
            continue;
 
        PointsTo pts1, pts2;
        if (const LoadStmt* ldStmt1 =
                    SVFUtil::dyn_cast<LoadStmt>(pair.stmt1))
        {
            pts1 = slicedPTA->getPts(ldStmt1->getRHSVarID());
        }
        else if (const StoreStmt* stStmt1 =
                     SVFUtil::dyn_cast<StoreStmt>(pair.stmt1))
        {
            pts1 = slicedPTA->getPts(stStmt1->getLHSVarID());
        }
        else
        {
            continue;
        }
 
        if (const LoadStmt* ldStmt2 =
                    SVFUtil::dyn_cast<LoadStmt>(pair.stmt2))
        {
            pts2 = slicedPTA->getPts(ldStmt2->getRHSVarID());
        }
        else if (const StoreStmt* stStmt2 =
                     SVFUtil::dyn_cast<StoreStmt>(pair.stmt2))
        {
            pts2 = slicedPTA->getPts(stStmt2->getLHSVarID());
        }
        else
        {
            continue;
        }
 
        // Check if points-to sets still intersect
        if (pts1.intersects(pts2))
            filteredRacePairs.insert(pair);
    }
 
    return filteredRacePairs;
}

getMainPTA()

BVDataPTAImpl * SlicedMTA::getMainPTA ( ) const

private

Main pointer-analysis instance feeding final race detection (the flow-sensitive FSAM, a BVDataPTAImpl queried polymorphically).

Definition at line 587 of file MTA.cpp.

{
    // The main FSMPTA phase is the flow-sensitive FSAM (FSMPTA), a
    // BVDataPTAImpl, so the downstream race detector queries it polymorphically.
    return mainFSMPTA.get();
}

getVulnerableStmts()

std::set< const SVFStmt * > SlicedMTA::getVulnerableStmts ( ) const

private

Union of both statements of every candidate race pair (the slice targets).

Definition at line 594 of file MTA.cpp.

{
    std::set<const SVFStmt*> vulnerableStatements;
    for (const RacePair& pair : racePairs)
    {
        vulnerableStatements.insert(pair.stmt1);
        vulnerableStatements.insert(pair.stmt2);
    }
    return vulnerableStatements;
}

operator=()

SlicedMTA & SVF::SlicedMTA::operator= ( const SlicedMTA &  )

delete

raceStatementKey()

std::string SlicedMTA::raceStatementKey ( const SVFStmt *  statement )

staticprivate

Definition at line 504 of file MTA.cpp.

{
    std::string key;
    const ICFGNode* node = statement->getICFGNode();
    const FunObjVar* function = node == nullptr ? nullptr : node->getFun();
    const SVFBasicBlock* block = statement->getBB();
    const SVFVar* value = statement->getValue();
 
    const std::string fields[] =
    {
        std::to_string(statement->getEdgeKind()),
        function == nullptr ? std::string() : function->getName(),
        block == nullptr ? std::string() : block->getName(),
        node == nullptr ? std::string() : node->getSourceLoc(),
        value == nullptr ? std::string() : value->getName(),
        value == nullptr ? std::string() : value->getSourceLoc(),
        value != nullptr && value->hasLLVMValue()
        ? value->valueOnlyToString() : std::string()
    };
    for (const std::string& field : fields)
    {
        key += std::to_string(field.size());
        key += ':';
        key += field;
    }
    return key;
}

reportOriginalStatistics()

void SlicedMTA::reportOriginalStatistics ( SVFIR *  svfir )

staticprivate

Pipeline utilities shared by the sliced and whole-program paths.

Definition at line 445 of file MTA.cpp.

{
    size_t icfgNodeCount = 0;
    for (ICFG::iterator it = svfir->getICFG()->begin(), eit = svfir->getICFG()->end(); it != eit; ++it)
        icfgNodeCount++;
 
    size_t functionCount = 0;
    for (auto it = svfir->getCallGraph()->begin(), eit = svfir->getCallGraph()->end(); it != eit; ++it)
        functionCount++;
 
    size_t pagStmtCount = 0;
    for (ICFG::iterator it = svfir->getICFG()->begin(),
            eit = svfir->getICFG()->end(); it != eit; ++it)
    {
        const ICFGNode* node = it->second;
        if (svfir->hasSVFStmtList(node))
            pagStmtCount += svfir->getSVFStmtList(node).size();
    }
 
    SVFUtil::outs() << "\n[Original SVFIR] Statistics:\n";
    SVFUtil::outs() << "  ICFG nodes: " << icfgNodeCount << "\n";
    SVFUtil::outs() << "  Functions: " << functionCount << "\n";
    SVFUtil::outs() << "  PAG statements: " << pagStmtCount << "\n";
}

reportPTASliceStatistics()

void SlicedMTA::reportPTASliceStatistics ( const std::set< const ICFGNode * > &  icfgNodes )

staticprivate

Definition at line 486 of file MTA.cpp.

{
    std::set<const FunObjVar*> functions;
    std::set<const SVFStmt*> statements;
    for (const ICFGNode* node : icfgNodes)
    {
        if (node->getFun() != nullptr)
            functions.insert(node->getFun());
        statements.insert(node->getSVFStmts().begin(), node->getSVFStmts().end());
    }
 
    SVFUtil::outs() << "[PTA Sliced] Statistics:\n";
    SVFUtil::outs() << "  ICFG nodes: " << icfgNodes.size() << "\n";
    SVFUtil::outs() << "  Functions: " << functions.size() << "\n";
    SVFUtil::outs() << "  PAG statements: " << statements.size() << "\n";
}

runFinalRaceDetection()

bool SlicedMTA::runFinalRaceDetection ( )

private

Definition at line 1087 of file MTA.cpp.

{
    SVFUtil::outs() << "\n=== Final Race Detection ===\n";
 
    if (!hasThreadFunctions)
    {
        SVFUtil::outs() << "[SKIP] No thread functions found\n";
        return true;
    }
    if (racePairs.empty())
    {
        SVFUtil::outs() << "\n=== Race Detection Summary ===\n";
        SVFUtil::outs() << "Race pairs (pre-analysis): 0\n";
        SVFUtil::outs() << "Race pairs (sliced graph): 0\n";
        SVFUtil::outs() << "Race statements (sliced graph): 0\n";
        if (isMTAStatEnabled())
        {
            const RaceDigests digests = computeRaceDigests(racePairs);
            SVFUtil::outs() << "[MSLI-RQ] mode=MSli alarms=0 pairs=0"
                            << " alarm-digest=" << digests.alarm
                            << " pair-digest=" << digests.pair << "\n";
        }
        SVFUtil::outs() << "\nNo race pairs detected in sliced graph.\n";
        return true;
    }
    if (mtaSlicedView == nullptr)
    {
        SVFUtil::errs() << "[ERROR] MTA sliced view not available\n";
        return false;
    }
    if (slicedMHP == nullptr || slicedLockAnalysis == nullptr)
    {
        SVFUtil::errs() << "[ERROR] Sliced MHP or LockAnalysis not available\n";
        return false;
    }
    if (getMainPTA() == nullptr)
    {
        SVFUtil::errs() << "[ERROR] Main flow-sensitive pointer analysis not available\n";
        return false;
    }
 
    std::set<RacePair> detectedPairs;
    {
        ScopedPhaseTimer timer("Final Race Detection");
        detectedPairs = detectRacePairsOnSlicedGraph(
                            racePairs,        // Refine only pre-analysis candidates
                            getMainPTA(),     // Use flow-sensitive FSAM points-to
                            slicedMHP.get(), slicedLockAnalysis.get());
    }
 
    // Distinct racy statements (the endpoints of the race pairs) -- a stabler,
    // smaller-to-report metric than the pair count.
    std::set<const SVFStmt*> racyStmts;
    for (const RacePair& pair : detectedPairs)
    {
        racyStmts.insert(pair.stmt1);
        racyStmts.insert(pair.stmt2);
    }
 
    SVFUtil::outs() << "\n=== Race Detection Summary ===\n";
    SVFUtil::outs() << "Race pairs (pre-analysis): " << racePairs.size() << "\n";
    SVFUtil::outs() << "Race pairs (sliced graph): " << detectedPairs.size() << "\n";
    SVFUtil::outs() << "Race statements (sliced graph): " << racyStmts.size() << "\n";
    // Machine-readable line for the artifact's `msli` table generator: the race
    // statements reported after slicing (the preservation metric).
    if (isMTAStatEnabled())
    {
        const RaceDigests digests = computeRaceDigests(detectedPairs);
        SVFUtil::outs() << "[MSLI-RQ] mode=MSli alarms=" << racyStmts.size()
                        << " pairs=" << detectedPairs.size()
                        << " alarm-digest=" << digests.alarm
                        << " pair-digest=" << digests.pair << "\n";
    }
 
    if (!detectedPairs.empty())
    {
        SVFUtil::outs() << "\n=== Bug Report ===\n";
        SVFUtil::outs() << "Found " << detectedPairs.size() << " race pair(s) in sliced graph\n";
    }
    else
    {
        SVFUtil::outs() << "\nNo race pairs detected in sliced graph.\n";
    }
 
    return true;
}

runMTASlicingAndAnalysis()

bool SlicedMTA::runMTASlicingAndAnalysis ( )

private

Definition at line 738 of file MTA.cpp.

{
    SVFUtil::outs() << "\n=== MTA Slicing and Analysis ===\n";
 
    if (racePairs.empty())
    {
        SVFUtil::outs() << "[SKIP] No race pairs found in pre-analysis\n";
        return true;
    }
 
    const bool dumpDot = Options::DumpMTAGraphs();
 
    // Step 1: Get vulnerable statements from race pairs
    std::set<const SVFStmt*> vulnerableStatements = getVulnerableStmts();
 
    std::set<const ICFGNode*> mtaSlicedNodes;
 
    if (Options::MTASingleStageSlicing())
    {
        // Single-pass baseline (MSli §3/§5.4): one unified slice (V_Single)
        // combining synchronization + data + call dependence, shared by both the
        // ILA and the FSPTA stages. Computed once here; reused in PTA slicing.
        SVFUtil::outs() << "[Slicing Mode] Single unified slice (V_Single) for ILA + FSPTA\n";
        singleSlicer = std::make_unique<SingleSlicer>(
                           svfir, preAndersen, mhp.get(), lockAnalysis.get(),
                           preSVFG /* data dependence over the thread-aware VFG_pre */);
        {
            ScopedPhaseTimer timer("Unified Slicing");
            ValueFlowSlice singleSlice =
                singleSlicer->runSlicing(vulnerableStatements);
            singleSlicedNodes = std::move(singleSlice.icfgNodes);
            singleSlicedSVFGNodeIds = singleSlice.nodeIds();
        }
        mtaSlicedNodes = singleSlicedNodes;
        if (isMTAStatEnabled())
            SVFUtil::outs() << "Unified sliced to " << mtaSlicedNodes.size()
                            << " nodes\n";
    }
    else
    {
        SVFUtil::outs() << "[Slicing Mode] Differential slices (separate ILA + FSPTA)\n";
        multiStageSlicer = std::make_unique<MultiStageSlicer>(
                               svfir, preAndersen, mhp.get(), lockAnalysis.get(), preSVFG);
 
        // ILA slicing sources = [INIT] race statements + [THREAD-VF] sources. Keep
        // a candidate edge's query (see MTASVFGBuilder::getThreadVFQueryMap) only if
        // both endpoints survive the FSPTA slice -- i.e. the edge is in
        // ThreadVF(VFG'_pre). Closure computed here (pre<->pre) and reused by PTA slicing.
        std::set<const ICFGNode*> threadVFSources;
        selectedThreadVFCandidates.clear();
        {
            ScopedPhaseTimer timer("Select THREAD-VF slicing sources");
            if (preSVFGBuilder)
            {
                multiStageSlicer->computePreCandidateSlice(vulnerableStatements);
                const ValueFlowSlice& preCandidate =
                    multiStageSlicer->getPreCandidateSlice();
                preCandidateSolveNodeIds =
                    FSMPTA<const SlicedSVFGView*>::buildExecutionDependencyClosure(
                        preSVFG, preAndersen, preCandidate.nodeIds());
                if (preCandidateSolveNodeIds.empty() &&
                        !preCandidate.svfgNodes.empty())
                {
                    SVFUtil::errs() << "[ERROR] Failed to execution-close VFG'_pre\n";
                    return false;
                }
                if (isMTAStatEnabled())
                    SVFUtil::outs()
                            << "[VFG'_pre] " << preCandidate.svfgNodes.size()
                            << " dependency nodes, "
                            << preCandidateSolveNodeIds.count()
                            << " execution-closure nodes\n";
 
                // The query map can be large; use node-ID membership rather than
                // two ordered-set lookups for every candidate edge.
                for (const auto& entry : preSVFGBuilder->getThreadVFQueryMap())
                {
                    const MTASVFGBuilder::ThreadVFEdge& edge = entry.first;
                    if (preCandidateSolveNodeIds.test(edge.first->getId()) &&
                            preCandidateSolveNodeIds.test(edge.second->getId()))
                    {
                        selectedThreadVFCandidates.emplace_back(
                            edge.first->getId(), edge.second->getId());
                        // The query value holds only the lock-span witnesses; the
                        // endpoints are implicit in the edge key.
                        threadVFSources.insert(edge.first->getICFGNode());
                        threadVFSources.insert(edge.second->getICFGNode());
                        threadVFSources.insert(entry.second.begin(), entry.second.end());
                    }
                }
            }
        }
        std::sort(selectedThreadVFCandidates.begin(),
                  selectedThreadVFCandidates.end());
        selectedThreadVFCandidates.erase(
            std::unique(selectedThreadVFCandidates.begin(),
                        selectedThreadVFCandidates.end()),
            selectedThreadVFCandidates.end());
        {
            ScopedPhaseTimer timer("MTA Slicing");
            mtaSlicedNodes = multiStageSlicer->runILASlicing(vulnerableStatements, threadVFSources);
        }
        if (isMTAStatEnabled())
            SVFUtil::outs() << "MTA sliced to " << mtaSlicedNodes.size()
                            << " nodes\n";
    } // end differential MTA slice
 
    // Step 4: Build MTA SlicedSVFIRView (using pre-analysis pointer analysis)
    {
        ScopedPhaseTimer timer("Build MTA Sliced View");
        mtaSlicedView = std::make_unique<SlicedSVFIRView>(
                            svfir, *threadCallGraph, svfir->getICFG(),
                            mtaSlicedNodes);
    }
    if (isMTAStatEnabled())
        mtaSlicedView->dumpStats("MTA Sliced");
 
    const SlicedSVFIRView* slicedView = mtaSlicedView.get();
 
    if (dumpDot)
    {
        SVFUtil::outs() << "\n[Dump] MTA Sliced views:\n";
        slicedView->getICFG()->dump("sliced_icfg");
        if (slicedView->getThreadCallGraph() != nullptr)
            slicedView->getThreadCallGraph()->dump("sliced_tcg");
        slicedView->getPAG()->dump("sliced_pag");
    }
 
    // Step 5: Build Sliced TCT (using pre-analysis pointer analysis)
    {
        ScopedPhaseTimer timer("Sliced Thread Create Tree");
        if (isMTAStatEnabled())
            SVFUtil::outs() << "[SlicedTCT] Using max context length: "
                            << mainContextDepth << " (from -max-cxt)\n";
        // Reuse the shared pre-analysis (Andersen) for the sliced TCT.
        slicedTCT = SlicedTCT::create(
                        *preAndersen, *slicedView, mainContextDepth);
        if (dumpDot)
            slicedTCT->dump("sliced_tct");
    }
 
    // Step 6: Sliced MHP and Lock Analysis
    {
        ScopedPhaseTimer ilaTimer("Sliced Interleaving and Lock Analysis");
        {
            ScopedPhaseTimer timer("Sliced ILA: construct MHP/ForkJoin");
            slicedMHP = MHP::create(
                            slicedTCT.get(), slicedView->getICFG(),
                            slicedView->getThreadCallGraph(),
                            MHP::StateRepresentation::QuerySummaries);
        }
        {
            ScopedPhaseTimer timer("Sliced ILA: MHP propagation");
            slicedMHP->analyze(slicedView->getICFG(), slicedView->getThreadCallGraph());
        }
        {
            ScopedPhaseTimer timer("Sliced ILA: Lock analysis");
            slicedLockAnalysis = std::make_unique<LockAnalysis>(slicedTCT.get());
            slicedLockAnalysis->analyze(slicedView->getICFG(), slicedView->getThreadCallGraph());
        }
    }
 
    return true;
}

runOnModule()

bool SlicedMTA::runOnModule	(	SVFIR *	pag,
		AndersenWaveDiff &	preAnalysis
	)

Run the slicing pipeline with its prepared Andersen pre-analysis.

Definition at line 1276 of file MTA.cpp.

{
    if (svfir != nullptr || pag == nullptr || preAnalysis.getPAG() != pag)
    {
        SVFUtil::errs() << "[ERROR] SlicedMTA is single-use and requires a "
                        << "matching SVFIR and Andersen pre-analysis\n";
        return false;
    }
    svfir = pag;
    preAndersen = &preAnalysis;
 
    SVFUtil::outs() << "[Config] Slicing: "
                    << (Options::MTAEnableSlicing() ? "enabled" : "disabled")
                    << "\n";
 
    if (isMTAStatEnabled())
        reportOriginalStatistics(svfir);
 
    // The pre-analysis is context-insensitive in BOTH modes (the sliced run and
    // the FSAM baseline must share an identical pre-analysis substrate); the
    // main phase then runs at the configured context depth.
    // TCT context bounds are explicit constructor inputs; no process-global
    // option is mutated while the pipeline is running.
    const bool preOk = runPreAnalysis();
    if (!preOk)
        return false;
 
    if (Options::MTAEnableSlicing())
    {
        if (!runMTASlicingAndAnalysis()) return false;
        if (!runPTASlicingAndAnalysis()) return false;
        if (!runFinalRaceDetection()) return false;
    }
    else
    {
        if (!runWholeProgramDetection()) return false;
    }
 
    SVFUtil::outs() << "\n=== Analysis Complete ===\n";
    return true;
}

runPreAnalysis()

bool SlicedMTA::runPreAnalysis ( )

private

Definition at line 631 of file MTA.cpp.

{
    SVFUtil::outs() << "\n=== Pre-Analysis ===\n";
 
    const bool dumpDot = Options::DumpMTAGraphs();
 
    // The LLVM-aware tool has already run Andersen and materialised its resolved
    // indirect calls into the PAG. Reuse that same analysis throughout MSli.
    threadCallGraph =
        SVFUtil::dyn_cast<ThreadCallGraph>(preAndersen->getCallGraph());
    if (threadCallGraph == nullptr)
    {
        SVFUtil::errs() << "[ERROR] Thread call graph failed\n";
        return false;
    }
 
    // Step 2: Build the context-insensitive pre-analysis Thread Creation Tree.
    {
        ScopedPhaseTimer timer("Create Thread Create Tree");
        tct = TCT::create(preAndersen, 0);
    }
    if (dumpDot)
        tct->dump("original_tct");
 
    // A thread with several instances at the main depth must be multiforked in
    // this depth-0 TCT, or the pre-analysis under-approximates the main phase.
    {
        ScopedPhaseTimer timer("Mark truncation-merged multiforked threads");
        std::unique_ptr<TCT> deepTct =
            TCT::create(preAndersen, mainContextDepth);
 
        // >1 instance at the main depth, or a single instance that is itself
        // multiforked (merged just beyond the main depth), marks the fork site.
        Map<const ICFGNode*, u32_t> forkSiteInstances;
        for (const auto& deepPair : *deepTct)
            if (const ICFGNode* forkSite = deepPair.second->getCxtThread().getThread())
            {
                ++forkSiteInstances[forkSite];
                if (deepPair.second->isMultiforked())
                    forkSiteInstances[forkSite] = 2;
            }
 
        for (const auto& prePair : *tct)
        {
            const ICFGNode* forkSite = prePair.second->getCxtThread().getThread();
            if (forkSite == nullptr)
                continue;
            Map<const ICFGNode*, u32_t>::const_iterator fIt = forkSiteInstances.find(forkSite);
            if (fIt != forkSiteInstances.end() && fIt->second > 1)
                prePair.second->setMultiforked(true);
        }
    }
 
    // Step 3: Interleaving and Lock Analysis
    {
        ScopedPhaseTimer ilaTimer("Run Interleaving and Lock Analysis");
        {
            ScopedPhaseTimer timer("ILA: construct MHP/ForkJoin");
            mhp = MHP::create(
                      tct.get(), svfir->getICFG(),
                      const_cast<CallGraph*>(svfir->getCallGraph()));
        }
        {
            ScopedPhaseTimer timer("ILA: MHP propagation");
            mhp->analyze(svfir->getICFG(), const_cast<CallGraph*>(svfir->getCallGraph()));
        }
        {
            ScopedPhaseTimer timer("ILA: Lock analysis");
            lockAnalysis = std::make_unique<LockAnalysis>(tct.get());
            lockAnalysis->analyze(svfir->getICFG(), const_cast<CallGraph*>(svfir->getCallGraph()));
        }
    }
 
    // Step 4: Detect thread functions
    {
        ScopedPhaseTimer timer("Detect Thread Functions");
        hasThreadFunctions = MTA::hasThreadFunctions(preAndersen->getCallGraph());
    }
    if (!hasThreadFunctions)
    {
        SVFUtil::outs() << "[WARNING] No thread functions found\n";
        return true; // Not an error, just no threads to analyze
    }
 
    // Step 5: Detect race statements
    std::set<const SVFStmt*> vulnerableStatements;
    {
        ScopedPhaseTimer timer("Detect Race Statements");
        // Shared equivalence-class detector (the same one MTA::reportRaces uses).
        vulnerableStatements = MTA::detectRace(
                                   svfir, preAndersen, mhp.get(), lockAnalysis.get(),
                                   preAndersen->getCallGraph(), racePairs);
    }
    SVFUtil::outs() << "Found " << vulnerableStatements.size() << " vulnerable statements\n";
    SVFUtil::outs() << "Found " << racePairs.size() << " race pairs\n";
 
    // Step 6: build the thread-aware VFG only when a downstream slice/solve
    // exists. No-race programs end after the pre-detector.
    if (!racePairs.empty())
        buildPreAnalysisSVFG();
    else
        SVFUtil::outs() << "[SKIP] No race candidates; VFG_pre is unnecessary\n";
 
    return true;
}

runPTASlicingAndAnalysis()

bool SlicedMTA::runPTASlicingAndAnalysis ( )

private

Definition at line 904 of file MTA.cpp.

{
    SVFUtil::outs() << "\n=== PTA Slicing and Sliced Pointer Analysis ===\n";
 
    if (!hasThreadFunctions)
    {
        SVFUtil::outs() << "[SKIP] No thread functions found in pre-analysis, skipping PTA slicing\n";
        return true;
    }
    if (racePairs.empty())
    {
        SVFUtil::outs() << "[SKIP] No race pairs found in pre-analysis, skipping PTA slicing\n";
        return true;
    }
 
    const bool dumpDot = Options::DumpMTAGraphs();
 
    std::set<const SVFStmt*> vulnerableStatements = getVulnerableStmts();
 
    std::set<const ICFGNode*> ptaSlicedNodes;
    NodeBS finalSVFGNodeIds;
 
    if (slicedMHP == nullptr || slicedLockAnalysis == nullptr ||
            preSVFGBuilder == nullptr || preSVFG == nullptr)
    {
        SVFUtil::outs() << "[Main FSMPTA] Base SVFG or sliced ILA unavailable\n";
        return false;
    }
 
    if (Options::MTASingleStageSlicing())
    {
        // Single-pass baseline: reuse the unified V_Single computed in MTA slicing
        // (no separate data-dependence slice); FSPTA runs on the same slice as ILA.
        SVFUtil::outs() << "[Slicing Mode] Reusing unified slice (V_Single) for FSPTA\n";
        finalSVFGNodeIds =
            FSMPTA<const SlicedSVFGView*>::buildExecutionDependencyClosure(
                preSVFG, preAndersen,
                singleSlicedSVFGNodeIds);
        if (finalSVFGNodeIds.empty() && !singleSlicedSVFGNodeIds.empty())
        {
            SVFUtil::errs() << "[ERROR] Single-slice FSMPTA execution closure failed\n";
            return false;
        }
        ptaSlicedNodes = collectICFGNodes(preSVFG, finalSVFGNodeIds);
        if (isMTAStatEnabled())
            SVFUtil::outs() << "PTA reuses unified slice: "
                            << ptaSlicedNodes.size() << " ICFG nodes, "
                            << finalSVFGNodeIds.count()
                            << " execution-closure SVFG nodes\n";
 
        const SlicedSVFGView mainScope(preSVFG, finalSVFGNodeIds);
 
        const MTASVFGBuilder::ThreadVFBuildConfig mainConfig =
            MTASVFGBuilder::ThreadVFBuildConfig::mainPhase(
                mainScope);
        {
            ScopedPhaseTimer timer("Replace Pre-TVF with Main-TVF overlay");
            preSVFGBuilder->replaceThreadAwareOverlay(
                slicedMHP.get(), slicedLockAnalysis.get(), mainConfig);
        }
    }
    else
    {
        SVFUtil::outs() << "Using " << vulnerableStatements.size() << " vulnerable statements from pre-analysis\n";
        SVFUtil::outs() << "Using " << racePairs.size() << " race pairs from pre-analysis\n";
 
        // Differential stage 1 always constructs this slicer and its conservative
        // pre-candidate closure before stage 2 starts.
        if (multiStageSlicer == nullptr)
        {
            SVFUtil::errs() << "[ERROR] Differential PTA slicing requires the ILA slicer\n";
            return false;
        }
 
        const ValueFlowSlice& preCandidate =
            multiStageSlicer->getPreCandidateSlice();
        if (preCandidateSolveNodeIds.empty() && !preCandidate.svfgNodes.empty())
        {
            SVFUtil::errs() << "[ERROR] Execution-closed VFG'_pre is unavailable\n";
            return false;
        }
        const NodeBS& preCandidateIds = preCandidateSolveNodeIds;
        const SlicedSVFGView mainScope(preSVFG, preCandidateIds);
 
        // The base SVFG is stable. Replace only the pre-analysis TVF overlay
        // with edges derived from the context-sensitive sliced main ILA.
        const MTASVFGBuilder::ThreadVFBuildConfig mainConfig =
            MTASVFGBuilder::ThreadVFBuildConfig::mainPhase(
                mainScope, &selectedThreadVFCandidates);
        {
            ScopedPhaseTimer timer("Replace Pre-TVF with Main-TVF overlay");
            preSVFGBuilder->replaceThreadAwareOverlay(
                slicedMHP.get(), slicedLockAnalysis.get(), mainConfig);
        }
        if (isMTAStatEnabled())
            SVFUtil::outs() << "[Main-TVF] "
                            << preSVFGBuilder->getThreadAwareEdgeCount()
                            << " interference edges over VFG'_pre\n";
 
        ValueFlowSlice finalSlice;
        {
            ScopedPhaseTimer timer("PTA Slicing over refined main VFG");
            finalSlice = multiStageSlicer->runPTASlicing(vulnerableStatements, preSVFG);
        }
        ptaSlicedNodes = finalSlice.icfgNodes;
        finalSVFGNodeIds = finalSlice.nodeIds();
 
        NodeBS outsideCandidate = finalSVFGNodeIds;
        outsideCandidate.intersectWithComplement(preCandidateIds);
        if (!outsideCandidate.empty())
        {
            SVFUtil::errs() << "[ERROR] Initial FSPTA slice escapes VFG'_pre by "
                            << outsideCandidate.count() << " SVFG nodes\n";
            return false;
        }
 
        {
            ScopedPhaseTimer timer("Build FSMPTA execution dependency closure");
            finalSVFGNodeIds =
                FSMPTA<const SlicedSVFGView*>::buildExecutionDependencyClosure(
                    preSVFG, preAndersen, finalSVFGNodeIds);
        }
 
        outsideCandidate = finalSVFGNodeIds;
        outsideCandidate.intersectWithComplement(preCandidateIds);
        if (!outsideCandidate.empty())
        {
            SVFUtil::errs() << "[ERROR] FSMPTA execution closure escapes VFG'_pre by "
                            << outsideCandidate.count() << " SVFG nodes\n";
            return false;
        }
 
        // Report the exact execution-closed solve set, rather than the smaller
        // pre-closure dependency seed shown by the old implementation.
        ptaSlicedNodes = collectICFGNodes(preSVFG, finalSVFGNodeIds);
 
        if (isMTAStatEnabled())
        {
            SVFUtil::outs() << "[FSPTA Slice] " << finalSlice.svfgNodes.size()
                            << " / " << preCandidate.svfgNodes.size() << " / "
                            << preCandidateIds.count()
                            << " SVFG nodes (final / pre-candidate / execution-closed), "
                            << finalSVFGNodeIds.count()
                            << " execution-closure solve nodes\n";
            SVFUtil::outs() << "PTA sliced to " << ptaSlicedNodes.size()
                            << " nodes\n";
        }
    }
 
    if (isMTAStatEnabled())
        reportPTASliceStatistics(ptaSlicedNodes);
 
    // Slicers are no longer needed. The builder and its one stable base SVFG
    // remain alive because FSMPTA solves that graph directly.
    multiStageSlicer.reset();
    singleSlicer.reset();
 
    // Step 5: solve the exact final slice on the stable base SVFG plus Main-TVF.
    SVFUtil::outs() << "[Main FSMPTA] Reusing BaseSVFG; Main-TVF comes from the sliced main ILA\n";
    if (!FSMPTA<const SlicedSVFGView*>::supportsCurrentConfiguration())
    {
        SVFUtil::errs() << "[ERROR] Unsupported FSMPTA mapping/clustering configuration\n";
        return false;
    }
    {
        ScopedPhaseTimer timer("Flow-Sensitive FSAM Analysis");
        slicedSVFGView = std::make_unique<SlicedSVFGView>(
                             preSVFG, finalSVFGNodeIds);
        auto solver = std::make_unique<FSMPTA<const SlicedSVFGView*>>(
                          *preAndersen, *preSVFG, slicedSVFGView.get());
        solver->analyze();
        if (dumpDot)
        {
            solver->getSVFG()->dump("mta_svfg");
            slicedSVFGView->dump("sliced_svfg");
        }
        mainFSMPTA = std::move(solver);
    }
 
    return true;
}

runWholeProgramDetection()

bool SlicedMTA::runWholeProgramDetection ( )

private

No-slice A/B baseline: run the FSAM detection on the whole program (no slicing), so its time and race set can be compared against the sliced run.

Definition at line 1177 of file MTA.cpp.

{
    SVFUtil::outs() << "\n=== Whole-program FSAM Race Detection (no slicing) ===\n";
    if (!hasThreadFunctions || racePairs.empty())
    {
        SVFUtil::outs() << "[SKIP] No thread functions / race pairs in pre-analysis\n";
        return true;
    }
 
    // SlicedTCT currently consumes the sliced-view representation even for the
    // full baseline. Time that construction explicitly so the A/B phase table
    // accounts for it instead of leaving it in unattributed wall time.
    {
        ScopedPhaseTimer timer("Build Whole-program View");
        std::set<const ICFGNode*> allNodes;
        for (ICFG::iterator it = svfir->getICFG()->begin(),
                eit = svfir->getICFG()->end(); it != eit; ++it)
            allNodes.insert(it->second);
        ptaSlicedView = std::make_unique<SlicedSVFIRView>(
                            svfir, *threadCallGraph, svfir->getICFG(), allNodes);
    }
 
    {
        ScopedPhaseTimer timer("Whole-program TCT/MHP/Lock");
        {
            ScopedPhaseTimer phaseTimer("Whole-program Thread Create Tree");
            slicedTCT = SlicedTCT::create(
                            *preAndersen, *ptaSlicedView, mainContextDepth);
        }
        CallGraph* fullCallGraph = threadCallGraph;
        {
            ScopedPhaseTimer phaseTimer(
                "Whole-program ILA: construct MHP/ForkJoin");
            slicedMHP = MHP::create(
                            slicedTCT.get(), svfir->getICFG(), fullCallGraph,
                            MHP::StateRepresentation::QuerySummaries);
        }
        {
            ScopedPhaseTimer phaseTimer("Whole-program ILA: MHP propagation");
            slicedMHP->analyze(svfir->getICFG(), fullCallGraph);
        }
        {
            ScopedPhaseTimer phaseTimer("Whole-program ILA: Lock analysis");
            slicedLockAnalysis =
                std::make_unique<LockAnalysis>(slicedTCT.get());
            slicedLockAnalysis->analyze(svfir->getICFG(), fullCallGraph);
        }
    }
 
    const MTASVFGBuilder::ThreadVFBuildConfig mainConfig =
        MTASVFGBuilder::ThreadVFBuildConfig::wholeProgram();
    {
        ScopedPhaseTimer timer("Whole-program Replace Pre-TVF with Main-TVF overlay");
        preSVFGBuilder->replaceThreadAwareOverlay(
            slicedMHP.get(), slicedLockAnalysis.get(), mainConfig);
    }
    if (isMTAStatEnabled())
        SVFUtil::outs() << "[Main-TVF] "
                        << preSVFGBuilder->getThreadAwareEdgeCount()
                        << " interference edges over the whole BaseSVFG\n";
 
    {
        ScopedPhaseTimer timer("Whole-program Flow-Sensitive FSMPTA Solve");
        auto solver = std::make_unique<FSMPTA<SVFG*>>(
                          *preAndersen, *preSVFG, preSVFG);
        solver->analyze();
        mainFSMPTA = std::move(solver);
    }
 
    std::set<RacePair> detectedPairs;
    {
        ScopedPhaseTimer timer("Final Race Detection (whole program)");
        detectedPairs = detectRacePairsOnSlicedGraph(
                            racePairs, getMainPTA(), slicedMHP.get(),
                            slicedLockAnalysis.get());
    }
 
    std::set<const SVFStmt*> racyStmts;
    for (const RacePair& pair : detectedPairs)
    {
        racyStmts.insert(pair.stmt1);
        racyStmts.insert(pair.stmt2);
    }
 
    SVFUtil::outs() << "\n=== Race Detection Summary ===\n";
    SVFUtil::outs() << "Race pairs (pre-analysis): " << racePairs.size() << "\n";
    SVFUtil::outs() << "Race pairs (whole program): " << detectedPairs.size() << "\n";
    SVFUtil::outs() << "Race statements (whole program): " << racyStmts.size() << "\n";
    if (isMTAStatEnabled())
    {
        const RaceDigests digests = computeRaceDigests(detectedPairs);
        SVFUtil::outs() << "[MSLI-RQ] mode=FSAM alarms=" << racyStmts.size()
                        << " pairs=" << detectedPairs.size()
                        << " alarm-digest=" << digests.alarm
                        << " pair-digest=" << digests.pair << "\n";
    }
    return true;
}

updateDigest()

void SlicedMTA::updateDigest ( u64_t &  digest, const std::string &  value  )

staticprivate

Definition at line 532 of file MTA.cpp.

{
    for (unsigned char byte : value)
    {
        digest ^= static_cast<u64_t>(byte);
        digest *= 1099511628211ULL;
    }
    digest ^= 0xffULL;
    digest *= 1099511628211ULL;
}

Member Data Documentation

hasThreadFunctions

bool SVF::SlicedMTA::hasThreadFunctions = false

private

Definition at line 319 of file MTA.h.

lockAnalysis

std::unique_ptr<LockAnalysis> SVF::SlicedMTA::lockAnalysis

private

Definition at line 293 of file MTA.h.

mainContextDepth

u32_t SVF::SlicedMTA::mainContextDepth

private

Definition at line 290 of file MTA.h.

mainFSMPTA

std::unique_ptr<FlowSensitive> SVF::SlicedMTA::mainFSMPTA

private

Definition at line 315 of file MTA.h.

mhp

std::unique_ptr<MHP> SVF::SlicedMTA::mhp

private

Definition at line 292 of file MTA.h.

mtaSlicedView

std::unique_ptr<SlicedSVFIRView> SVF::SlicedMTA::mtaSlicedView

private

Definition at line 312 of file MTA.h.

multiStageSlicer

std::unique_ptr<MultiStageSlicer> SVF::SlicedMTA::multiStageSlicer

private

Definition at line 301 of file MTA.h.

preAndersen

AndersenWaveDiff* SVF::SlicedMTA::preAndersen = nullptr

private

Definition at line 297 of file MTA.h.

preCandidateSolveNodeIds

NodeBS SVF::SlicedMTA::preCandidateSolveNodeIds

private

Definition at line 302 of file MTA.h.

preSVFG

SVFG* SVF::SlicedMTA::preSVFG = nullptr

private

Definition at line 300 of file MTA.h.

preSVFGBuilder

std::unique_ptr<MTASVFGBuilder> SVF::SlicedMTA::preSVFGBuilder

private

Definition at line 299 of file MTA.h.

ptaSlicedView

std::unique_ptr<SlicedSVFIRView> SVF::SlicedMTA::ptaSlicedView

private

Definition at line 313 of file MTA.h.

racePairs

std::set<RacePair> SVF::SlicedMTA::racePairs

private

Definition at line 320 of file MTA.h.

selectedThreadVFCandidates

MTASVFGBuilder::ThreadVFCandidateList SVF::SlicedMTA::selectedThreadVFCandidates

private

VFG'_pre endpoint-filtered, context-insensitive pre-MHP candidates. This is only a conservative worklist for rebuilding Main-TVF; the main phase independently re-decides every edge with main MHP and lock facts.

Definition at line 307 of file MTA.h.

singleSlicedNodes

std::set<const ICFGNode*> SVF::SlicedMTA::singleSlicedNodes

private

Definition at line 310 of file MTA.h.

singleSlicedSVFGNodeIds

NodeBS SVF::SlicedMTA::singleSlicedSVFGNodeIds

private

Definition at line 311 of file MTA.h.

singleSlicer

std::unique_ptr<SingleSlicer> SVF::SlicedMTA::singleSlicer

private

Definition at line 303 of file MTA.h.

slicedLockAnalysis

std::unique_ptr<LockAnalysis> SVF::SlicedMTA::slicedLockAnalysis

private

Definition at line 318 of file MTA.h.

slicedMHP

std::unique_ptr<MHP> SVF::SlicedMTA::slicedMHP

private

Definition at line 317 of file MTA.h.

slicedSVFGView

std::unique_ptr<SlicedSVFGView> SVF::SlicedMTA::slicedSVFGView

private

Definition at line 314 of file MTA.h.

slicedTCT

std::unique_ptr<SlicedTCT> SVF::SlicedMTA::slicedTCT

private

Definition at line 316 of file MTA.h.

svfir

SVFIR* SVF::SlicedMTA::svfir = nullptr

private

Definition at line 287 of file MTA.h.

tct

std::unique_ptr<TCT> SVF::SlicedMTA::tct

private

Definition at line 291 of file MTA.h.

threadCallGraph

ThreadCallGraph* SVF::SlicedMTA::threadCallGraph = nullptr

private

Definition at line 298 of file MTA.h.

---

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

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