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
 */
 
#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 <deque>
#include "Graphs/ICFGEdge.h"
#include "Graphs/CallGraph.h"
#include "Util/WorkList.h"
#include <memory>
#include <vector>
#include <utility>
 
namespace SVF
{
 
// Forward declarations
class SVFG;
class VFGNode;          // SVFGNode is a typedef for VFGNode
class PointerAnalysis;
 
struct ValueFlowSlice
{
    OrderedSet<const SVFGNode*> svfgNodes;
    OrderedSet<const ICFGNode*> icfgNodes;
 
    NodeBS nodeIds() const
    {
        NodeBS ids;
        for (const SVFGNode* node : svfgNodes)
            ids.set(node->getId());
        return ids;
    }
};
 
 
//===----------------------------------------------------------------------===//
// 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:
    static std::unique_ptr<SlicedTCT> create(
        PointerAnalysis& pointerAnalysis, const SlicedSVFIRView& slicedView,
        u32_t contextLimit);
 
    ~SlicedTCT() override = default;
 
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:
    SlicedTCT(PointerAnalysis& pointerAnalysis,
              const SlicedSVFIRView& slicedView, u32_t contextLimit);
 
    void collectEntryFunInCallGraph() override;
 
    const SlicedThreadCallGraphView& tcgView;
    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* svfg = nullptr);
 
protected:
    SVFIR* svfir;
    AndersenBase* pta;
    MHP* mhp;
    LockAnalysis* lockAnalysis;
    CallGraph* callGraph;
    SVFG* svfg;   
 
    // === Data flow analysis helper ===
    OrderedSet<const VFGNode*> computeDataDependenceSVFGNodes(
        const OrderedSet<const SVFStmt*>& seeds, SVFG* svfg);
 
    static void enqueueSVFGNode(const SVFGNode* node,
                                OrderedSet<const SVFGNode*>& visited,
                                std::deque<const SVFGNode*>& worklist);
 
    OrderedSet<const ICFGNode*> svfgNodesToICFGNodes(
        const OrderedSet<const VFGNode*>& nodes, const OrderedSet<const SVFStmt*>& seeds);
 
    // === Thread analysis helpers ===
    OrderedSet<const CallICFGNode*> getDependentThreadCreate(const ICFGNode* node);
    OrderedSet<const TCTNode*> getTCTNodeSetFromNode(const ICFGNode* node);
 
    // === Lock analysis helpers ===
    OrderedSet<const ICFGNode*> getLockSet(const ICFGNode* node);
    OrderedSet<const CallICFGNode*> collectPthreadStatements(
        const OrderedSet<const ICFGNode*>& sourceNodes);
    OrderedSet<const CallICFGNode*> collectMutexStatements(
        const OrderedSet<const ICFGNode*>& sourceNodes);
 
    // === Common slicing helpers ===
    std::pair<OrderedSet<const CallICFGNode*>, OrderedSet<const CallICFGNode*>>
            collectCommonThreadStatements(const OrderedSet<const ICFGNode*>& sourceNodes);
 
    void addSynchronizationDependencies(
        const OrderedSet<const CallICFGNode*>& pthreadCallNodes,
        const OrderedSet<const CallICFGNode*>& mutexCallNodes,
        OrderedSet<const ICFGNode*>& retainedNodes);
 
    // === ICFG analysis helpers ===
    OrderedSet<const ICFGNode*> expandCallDependence(const OrderedSet<const ICFGNode*>& nodes);
 
};
 
class MultiStageSlicer : public MTASlicerBase
{
public:
    MultiStageSlicer(SVFIR* svfir, AndersenBase* pta, MHP* mhp,
                     LockAnalysis* lockAnalysis, SVFG* svfg = nullptr);
 
    OrderedSet<const ICFGNode*> runILASlicing(
        const OrderedSet<const SVFStmt*>& vulnerableStatements,
        const OrderedSet<const ICFGNode*>& threadVFSources = {});
 
    ValueFlowSlice runPTASlicing(
        const OrderedSet<const SVFStmt*>& vulnerableStatements,
        SVFG* refinedMainVFG);
 
    void computePreCandidateSlice(
        const OrderedSet<const SVFStmt*>& vulnerableStatements);
 
    const ValueFlowSlice& getPreCandidateSlice() const;
 
private:
    ValueFlowSlice preCandidateSlice;
    bool preCandidateComputed = false;
};
 
class SingleSlicer : public MTASlicerBase
{
public:
    SingleSlicer(SVFIR* svfir, AndersenBase* pta, MHP* mhp,
                 LockAnalysis* lockAnalysis, SVFG* svfg = nullptr);
 
    ValueFlowSlice runSlicing(
        const OrderedSet<const SVFStmt*>& vulnerableStatements);
};
 
} // End namespace SVF
 
#endif // MTA_MTASLICER_H