MTA.h

Go to the documentation of this file.

//===- MTA.h -- Analysis of multithreaded programs-------------//
//
//                     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/>.
//
//===----------------------------------------------------------------------===//
 
/*
 * MTA.h
 *
 *  Created on: May 14, 2014
 *      Author: Yulei Sui, Peng Di
 *
 * The base data race detector is based on
 * Yulei Sui, Peng Di, and Jingling Xue. "Sparse Flow-Sensitive Pointer Analysis for Multithreaded Programs".
 * 2016 International Symposium on Code Generation and Optimization (CGO'16)
 *
 * This file also declares SlicedMTA, the multi-stage on-demand program slicing
 * pipeline (MSli) introduced in "Multi-Stage On-Demand Program Slicing for
 * Modular Analysis of Multi-Threaded Programs" (ISSTA 2026).
 */
 
#ifndef MTA_H_
#define MTA_H_
 
#include <set>
#include <string>
#include <vector>
#include <functional>
#include <memory>
#include <utility>
#include "SVFIR/SVFIR.h"
#include "SVFIR/SVFValue.h"
#include "SVFIR/SVFStatements.h"
#include "SVFIR/SVFVariables.h"
#include "MemoryModel/PointsTo.h"
#include "MTA/MHP.h"
#include "MTA/LockAnalysis.h"
#include "WPA/Andersen.h"
#include "Graphs/CallGraph.h"
 
namespace SVF
{
 
class PointerAnalysis;
class AndersenWaveDiff;
class AndersenBase;
class ThreadCallGraph;
class CallGraph;
class MTAStat;
class TCT;
class MHP;
class LockAnalysis;
class SVFStmt;
class SVFIR;
class ICFGNode;
// Forward declarations for the SlicedMTA slicing pipeline (see SlicedMTA impl).
class MTASVFGBuilder;
class SVFG;
class FlowSensitive;
class SlicedSVFGView;
class MultiStageSlicer;
class SingleSlicer;
class SlicedSVFIRView;
class SlicedTCT;
 
class MTA
{
 
public:
    MTA();
 
    virtual ~MTA();
 
 
    virtual bool runOnModule(SVFIR* module);
    virtual MHP* computeMHP(TCT* tct);
    virtual LockAnalysis* computeLocksets(TCT* tct);
    virtual void reportRaces();
 
    // Not implemented for now
    // void dump(Module &module, MHP *mhp, LockAnalysis *lsa);
 
    MHP* getMHP()
    {
        return mhp;
    }
 
    LockAnalysis* getLockAnalysis()
    {
        return lsa;
    }
 
    struct RacePair
    {
        const SVFStmt* stmt1;
        const SVFStmt* stmt2;
        RacePair(const SVFStmt* s1, const SVFStmt* s2) : stmt1(s1), stmt2(s2) {}
        bool operator<(const RacePair& other) const
        {
            if (stmt1 != other.stmt1) return stmt1 < other.stmt1;
            return stmt2 < other.stmt2;
        }
    };
 
    static std::set<const SVFStmt*> detectRace(
        SVFIR* svfIr, AndersenBase* pta, MHP* mhp, LockAnalysis* lockAnalysis,
        CallGraph* callGraph, std::set<RacePair>& outRacePairs);
 
    static PointsTo getGlobalObjectVariables(SVFIR* svfIr);
    static PointsTo getPointsToClosure(AndersenBase* pta, const PointsTo& pts);
 
    static bool hasThreadFunctions(CallGraph* callGraph);
 
private:
    struct RaceOccurrence
    {
        const SVFStmt* stmt;
        const ICFGNode* node;
        bool isStore;
        NodeID tid;
        NodeBS interleav;
        bool locked;
    };
 
 
    static bool occurrencesRace(MHP* mhp, const RaceOccurrence& first, const RaceOccurrence& second);
    static void commitRacePair(std::set<RacePair>& out,
                               const RaceOccurrence& first, const RaceOccurrence& second);
 
    ThreadCallGraph* tcg;
    std::unique_ptr<TCT> tct;
    std::unique_ptr<MTAStat> stat;
    MHP* mhp;
    LockAnalysis* lsa;
};
 
class SlicedMTA
{
public:
    using ResolveIndirectCalls = std::function<void(CallGraph*)>;
 
    using RacePair = MTA::RacePair;
 
    // Out-of-line (defined where the member types are complete) so callers that
    // only see the forward-declared unique_ptr member types need not be complete.
    SlicedMTA();
    ~SlicedMTA();
 
    SlicedMTA(const SlicedMTA&) = delete;
    SlicedMTA& operator=(const SlicedMTA&) = delete;
 
    void runOnModule(SVFIR* pag, const ResolveIndirectCalls& resolveIndirectCalls);
 
private:
    // --- pipeline stages ---
    bool runPreAnalysis(const ResolveIndirectCalls& resolveIndirectCalls);
    bool runMTASlicingAndAnalysis();
    bool runPTASlicingAndAnalysis();
    bool runFinalRaceDetection();
    void buildVFGPre();
 
    void runWholeProgramDetection();
 
    BVDataPTAImpl* getMainPTA() const;
 
    std::set<const SVFStmt*> getVulnerableStmts() const;
 
    // --- race detection ---
    std::set<RacePair> detectRacePairsOnSlicedGraph(
        BVDataPTAImpl* slicedPTA, MHP* slicedMHP, LockAnalysis* slicedLockAnalysis);
 
    // Lock analysis over the WHOLE ICFG (real control flow, no bridging) for the
    // final detection's lock signature. The sliced lock analysis walks bridged
    // edges, which fabricate lock-carrying paths the whole program lacks (a
    // query-preservation break); lock-span is control-flow-sensitive, so it must
    // see real edges. Built lazily, cheap (no FSAM/MHP) next to the slicing win.
    LockAnalysis* buildFullLockAnalysis();
 
    // --- pipeline state (owned unless noted) ---
    SVFIR* svfIr = nullptr;
    // Main-phase context depth, set by runOnModule; the pre-analysis uses it
    // to reconcile context-truncation-merged thread instances.
    u32_t mainCxtDepth = 2;
    std::unique_ptr<TCT> tct;
    std::unique_ptr<MHP> mhp;
    std::unique_ptr<LockAnalysis> lockAnalysis;
    // Inclusion-based Andersen's pre-analysis (a shared singleton, not owned
    // here -- released once in the destructor). Feeds the TCT / MHP / lock /
    // race pre-analysis, the thread-aware VFG_pre, and the main FSMPTA.
    AndersenWaveDiff* preAnder = nullptr;
    std::unique_ptr<MTASVFGBuilder> vfgPreBuilder; // owns vfgPre
    SVFG* vfgPre = nullptr;
    std::unique_ptr<MultiStageSlicer> multiStageSlicer;
    std::unique_ptr<SingleSlicer> singleSlicer;
    // -mta-slicing-single: the one unified slice, computed in MTA slicing and reused
    // (not recomputed) for PTA slicing so both stages share V_Single.
    std::set<const ICFGNode*> singleSlicedNodes;
    std::unique_ptr<SlicedSVFIRView> mtaSlicedView;
    std::unique_ptr<SlicedSVFIRView> ptaSlicedView;
    std::unique_ptr<SlicedSVFGView> slicedSVFGView;
    std::unique_ptr<FlowSensitive> mtaFSMPTA;
    std::unique_ptr<SlicedTCT> slicedTCT;
    std::unique_ptr<MHP> slicedMhp;
    std::unique_ptr<LockAnalysis> slicedLockAnalysis;
    // Whole-ICFG lock analysis for the final detection (see buildFullLockAnalysis).
    std::unique_ptr<SlicedSVFIRView> fullLockView;
    std::unique_ptr<SlicedTCT> fullLockTCT;
    std::unique_ptr<LockAnalysis> fullLockAnalysis;
    bool hasThreadFunctions = false;
    std::set<RacePair> racePairs;
};
 
} // End namespace SVF
 
#endif /* MTA_H_ */