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)
 */
 
#ifndef MTA_H_
#define MTA_H_
 
#include <set>
#include <string>
#include <vector>
#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 "MTA/MTASVFGBuilder.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 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();
 
    MHP* getMHP()
    {
        return mhp;
    }
 
    LockAnalysis* getLockAnalysis()
    {
        return lsa;
    }
 
    struct RacePair
    {
        const SVFStmt* stmt1;
        const SVFStmt* stmt2;
        RacePair(const SVFStmt* s1, const SVFStmt* s2)
            : stmt1(statementLess(s2, s1) ? s2 : s1),
              stmt2(statementLess(s2, s1) ? s1 : s2)
        {
        }
 
        static bool statementLess(const SVFStmt* lhs, const SVFStmt* rhs)
        {
            return lhs->getEdgeID() < rhs->getEdgeID();
        }
 
        bool operator<(const RacePair& other) const
        {
            if (stmt1->getEdgeID() != other.stmt1->getEdgeID())
                return stmt1->getEdgeID() < other.stmt1->getEdgeID();
            return stmt2->getEdgeID() < other.stmt2->getEdgeID();
        }
    };
 
    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;
        const NodeBS* interleaving;
        bool locked;
    };
 
    struct RaceClass
    {
        bool isStore;
        bool locked;
        size_t representative;
        std::vector<size_t> members;
    };
 
    struct RaceClassKey
    {
        NodeID tid;
        bool isStore;
        const NodeBS* interleaving;
        bool locked;
        NodeID lockNodeId;
 
        bool operator<(const RaceClassKey& other) const;
    };
 
    using ObjectToRaceOccurrences = Map<NodeID, std::vector<size_t>>;
 
 
    static void collectRaceOccurrences(
        SVFIR* svfir, AndersenBase* pta, MHP* mhp,
        LockAnalysis* lockAnalysis, CallGraph* callGraph,
        const PointsTo& escapedObjects,
        std::vector<RaceOccurrence>& occurrences,
        ObjectToRaceOccurrences& objectToOccurrences);
    static std::vector<RaceClass> buildRaceClasses(
        const std::vector<RaceOccurrence>& occurrences,
        const std::vector<size_t>& occurrenceIndices);
    static void emitRacePairs(
        MHP* mhp, LockAnalysis* lockAnalysis,
        const std::vector<RaceOccurrence>& occurrences,
        const std::vector<RaceClass>& classes,
        std::set<RacePair>& outRacePairs);
    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 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;
 
    bool runOnModule(SVFIR* pag, AndersenWaveDiff& preAnalysis);
 
private:
    // --- pipeline stages ---
    bool runPreAnalysis();
    bool runMTASlicingAndAnalysis();
    bool runPTASlicingAndAnalysis();
    bool runFinalRaceDetection();
    void buildPreAnalysisSVFG();
 
 
    static void reportOriginalStatistics(SVFIR* svfir);
    static std::set<const ICFGNode*> collectICFGNodes(
        SVFG* svfg, const NodeBS& svfgNodeIds);
    static void reportPTASliceStatistics(
        const std::set<const ICFGNode*>& icfgNodes);
    struct RaceDigests
    {
        u64_t alarm;
        u64_t pair;
    };
    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);
 
    bool runWholeProgramDetection();
 
    BVDataPTAImpl* getMainPTA() const;
 
    std::set<const SVFStmt*> getVulnerableStmts() const;
 
    // --- race detection ---
    std::set<RacePair> detectRacePairsOnSlicedGraph(
        const std::set<RacePair>& preAnalysisRacePairs,
        BVDataPTAImpl* slicedPTA, MHP* slicedMHP,
        LockAnalysis* slicedLockAnalysis);
 
    // --- 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 mainContextDepth;
    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; the tool releases it after this object is destroyed). Feeds TCT/MHP/lock/
    // race pre-analysis, the thread-aware VFG_pre, and the main FSMPTA.
    AndersenWaveDiff* preAndersen = nullptr;
    ThreadCallGraph* threadCallGraph = nullptr;
    std::unique_ptr<MTASVFGBuilder> preSVFGBuilder; // owns preSVFG
    SVFG* preSVFG = nullptr;
    std::unique_ptr<MultiStageSlicer> multiStageSlicer;
    NodeBS preCandidateSolveNodeIds;
    std::unique_ptr<SingleSlicer> singleSlicer;
    MTASVFGBuilder::ThreadVFCandidateList selectedThreadVFCandidates;
    // -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;
    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;
};
 
} // End namespace SVF
 
#endif /* MTA_H_ */