MTASlicer.h

Go to the documentation of this file.

//===- MTASlicer.h -- Multi-stage on-demand program slicers ---------------===//
//
//                     SVF: Static Value-Flow Analysis
//
// Copyright (C) <2013->  <Yulei Sui>
//
 
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
 
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Affero General Public License for more details.
 
// You should have received a copy of the GNU Affero General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.
//
//===----------------------------------------------------------------------===//
 
/*
 * MTASlicer.h
 *
 *      Author: Jiawei Yang
 *
 * The program slicers of "Multi-Stage On-Demand Program Slicing for Modular
 * Analysis of Multi-Threaded Programs" (ISSTA 2026): a shared MTASlicerBase plus
 * three concrete slicers.
 *   - MultiStageSlicer   : ILA (sync + dual + call) slice for the thread-aware analysis
 *   (its FSPTA stage: data-dependence slice over the thread-aware VFG_pre)
 *   - SingleSlicer: one unified slice combining all three dependence kinds, shared
 *                   by both ILA and FSPTA (the single-pass baseline, MSli §3/§5.4)
 */
 
#ifndef MTA_MTASLICER_H
#define MTA_MTASLICER_H
 
#include "SVFIR/SVFIR.h"
#include "SVFIR/SVFStatements.h"
#include "SVFIR/SVFVariables.h"
#include "WPA/Andersen.h"
#include "MTA/MHP.h"
#include "MTA/LockAnalysis.h"
#include "MTA/TCT.h"
#include "Graphs/SlicedGraphs.h"
#include "Graphs/ThreadCallGraph.h"
#include "Graphs/ICFG.h"
#include "Graphs/ICFGNode.h"
#include <fstream>
#include "Graphs/ICFGEdge.h"
#include "Graphs/CallGraph.h"
#include "Util/WorkList.h"
#include <memory>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <utility>
 
namespace SVF
{
 
// Forward declarations
class SVFG;
class VFGNode;          // SVFGNode is a typedef for VFGNode
class PointerAnalysis;
 
 
//===----------------------------------------------------------------------===//
// SlicedTCT - the Thread-Create-Tree rebuilt over a SlicedThreadCallGraphView.
//
// Inherits TCT and overrides the ThreadCallGraph-traversing steps to use the
// sliced view. It sits at the sliced-representation layer (built from the view,
// consumed by the sliced MHP/LockAnalysis graph-access), which is why it lives
// here with the views rather than beside the analyses.
//===----------------------------------------------------------------------===//
class SlicedTCT : public TCT
{
public:
    SlicedTCT(PointerAnalysis* p, const SlicedSVFIRView* slicedView, u32_t maxContextLen = 0);
 
    ~SlicedTCT() override = default;
 
    void pushCxt(CallStrCxt& cxt, const CallICFGNode* call, const FunObjVar* callee) override;
 
protected:
    void build() override;
    void markRelProcs() override;
    void markRelProcs(const FunObjVar* fun) override;
    void collectLoopInfoForJoin() override;
    void handleCallRelation(CxtThreadProc& ctp, const CallGraphEdge* cgEdge, const CallICFGNode* cs) override;
 
private:
    void collectEntryFunInCallGraph() override;
 
    const SlicedThreadCallGraphView* tcgView; // ThreadCallGraph view (from the sliced view)
    u32_t maxContextLen; // 0 means use Options::MaxContextLen()
 
    bool isKeptNode(const CallGraphNode* node) const;
    bool isKeptEdge(const CallGraphEdge* edge) const;
    void getKeptForkSites(std::vector<const ICFGNode*>& out) const;
    void getKeptJoinSites(std::vector<const ICFGNode*>& out) const;
};
 
 
class MTASlicerBase
{
public:
    MTASlicerBase(SVFIR* svfIr, AndersenBase* pta, MHP* mhp,
                  LockAnalysis* lockAnalysis, SVFG* vfg = nullptr);
    virtual ~MTASlicerBase();
 
protected:
    SVFIR* svfIr;
    AndersenBase* pta;
    MHP* mhp;
    LockAnalysis* lockAnalysis;
    CallGraph* callGraph;
    SVFG* vfg;   
 
    // === Data flow analysis helper ===
    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);
 
    // === Thread analysis helpers ===
    OrderedSet<const SVFStmt*> getDependentThreadCreate(const SVFStmt* stmt);
    OrderedSet<const TCTNode*> getTCTNodeSetFromNode(const ICFGNode* node);
 
    // === Lock analysis helpers ===
    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);
 
    // === Common slicing helpers ===
    std::pair<OrderedSet<const CallICFGNode*>, OrderedSet<const CallICFGNode*>>
            collectCommonThreadStatements(const OrderedSet<const SVFStmt*>& vulnerableStatements);
 
    // === ICFG analysis helpers ===
    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);
};
 
class MultiStageSlicer : public MTASlicerBase
{
public:
    MultiStageSlicer(SVFIR* svfIr, AndersenBase* pta, MHP* mhp,
                     LockAnalysis* lockAnalysis, SVFG* vfg = nullptr);
 
    OrderedSet<const ICFGNode*> runILASlicing(
        const OrderedSet<const SVFStmt*>& vulnerableStatements,
        const OrderedSet<const ICFGNode*>& threadVFSources = {});
 
    OrderedSet<const ICFGNode*> runPTASlicing(
        const OrderedSet<const SVFStmt*>& vulnerableStatements);
 
    const OrderedSet<const VFGNode*>& getRetainedSVFGNodes(
        const OrderedSet<const SVFStmt*>& vulnerableStatements);
 
private:
    OrderedSet<const VFGNode*> retainedSVFGNodes; 
    bool retainedComputed = false;
};
 
class SingleSlicer : public MTASlicerBase
{
public:
    SingleSlicer(SVFIR* svfIr, AndersenBase* pta, MHP* mhp,
                 LockAnalysis* lockAnalysis, SVFG* vfg = nullptr);
 
    OrderedSet<const ICFGNode*> runSlicing(
        const OrderedSet<const SVFStmt*>& vulnerableStatements);
};
 
} // End namespace SVF
 
#endif // MTA_MTASLICER_H