FlowDDA.h

Go to the documentation of this file.

//===- FlowDDA.h -- Flow-sensitive demand-driven analysis -------------//
//
//                     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/>.
//
//===----------------------------------------------------------------------===//
 
/*
 * FlowDDA.h
 *
 *  Created on: Jun 30, 2014
 *      Author: Yulei Sui, Sen Ye
 *
 * The implementation is based on
 * (1) Yulei Sui and Jingling Xue. "On-Demand Strong Update Analysis via Value-Flow Refinement".
 * ACM SIGSOFT International Symposium on the Foundation of Software Engineering (FSE'16)
 *
 * (2) Yulei Sui and Jingling Xue. "Value-Flow-Based Demand-Driven Pointer Analysis for C and C++".
 * IEEE Transactions on Software Engineering (TSE'18)
 */
 
#ifndef FlowDDA_H_
#define FlowDDA_H_
 
#include "MemoryModel/PointerAnalysisImpl.h"
#include "DDA/DDAVFSolver.h"
#include "Util/DPItem.h"
#include "Util/GeneralType.h"
 
namespace SVF
{
 
class DDAClient;
typedef StmtDPItem<SVFGNode> LocDPItem;
 
class FlowDDA : public BVDataPTAImpl, public DDAVFSolver<NodeID,PointsTo,LocDPItem>
{
 
public:
    typedef BVDataPTAImpl::CallSiteSet CallSiteSet;
    typedef BVDataPTAImpl::CallEdgeMap  CallEdgeMap;
    typedef BVDataPTAImpl::FunctionSet  FunctionSet;
    FlowDDA(SVFIR* _pag, DDAClient* client): BVDataPTAImpl(_pag, PTATY::FlowS_DDA),
        DDAVFSolver<NodeID,PointsTo,LocDPItem>(),
        _client(client)
    {
    }
    inline virtual ~FlowDDA()
    {
    }
    virtual void analyze() override {}
 
    void computeDDAPts(NodeID id) override;
 
    void handleOutOfBudgetDpm(const LocDPItem& dpm);
 
    virtual bool handleBKCondition(LocDPItem& dpm, const SVFGEdge* edge) override;
 
    bool testIndCallReachability(LocDPItem& dpm, const FunObjVar* callee, CallSiteID csId);
 
    inline virtual void initialize() override
    {
        BVDataPTAImpl::initialize();
        buildSVFG(pag);
        setCallGraph(getCallGraph());
        setCallGraphSCC(getCallGraphSCC());
        stat = setDDAStat(new DDAStat(this));
    }
 
    inline virtual void finalize() override
    {
        BVDataPTAImpl::finalize();
    }
 
    virtual bool isHeapCondMemObj(const NodeID& var, const StoreSVFGNode* store) override;
 
    virtual inline PointsTo getConservativeCPts(const LocDPItem& dpm) override
    {
        return getAndersenAnalysis()->getPts(dpm.getCurNodeID());
    }
    virtual inline NodeID getPtrNodeID(const NodeID& var) const override
    {
        return var;
    }
    virtual inline void handleAddr(PointsTo& pts,const LocDPItem& dpm,const AddrSVFGNode* addr) override
    {
        NodeID srcID = addr->getSrcNodeID();
        if (isFieldInsensitive(srcID))
            srcID = getFIObjVar(srcID);
 
        addDDAPts(pts,srcID);
        DBOUT(DDDA, SVFUtil::outs() << "\t add points-to target " << srcID << " to dpm ");
        DBOUT(DDDA, dpm.dump());
    }
    virtual PointsTo processGepPts(const GepSVFGNode* gep, const PointsTo& srcPts) override;
 
 
    virtual void updateCallGraphAndSVFG(const LocDPItem& dpm,const CallICFGNode* cs,SVFGEdgeSet& svfgEdges) override
    {
        CallEdgeMap newEdges;
        resolveIndCalls(cs, getCachedPointsTo(dpm), newEdges);
        for (CallEdgeMap::const_iterator iter = newEdges.begin(),eiter = newEdges.end(); iter != eiter; iter++)
        {
            const CallICFGNode* newcs = iter->first;
            const FunctionSet & functions = iter->second;
            for (FunctionSet::const_iterator func_iter = functions.begin(); func_iter != functions.end(); func_iter++)
            {
                const FunObjVar* func = *func_iter;
                getSVFG()->connectCallerAndCallee(newcs, func, svfgEdges);
            }
        }
    }
 
 
    virtual inline const PointsTo& getCachedTLPointsTo(const LocDPItem& dpm) override
    {
        return getPts(dpm.getCurNodeID());
    }
 
    bool unionDDAPts(LocDPItem dpm, const PointsTo& targetPts) override
    {
        if (isTopLevelPtrStmt(dpm.getLoc())) return unionPts(dpm.getCurNodeID(), targetPts);
        else return dpmToADCPtSetMap[dpm] |= targetPts;
    }
 
    virtual const std::string PTAName() const override
    {
        return "FlowSensitive DDA";
    }
 
private:
    DDAClient* _client;             
};
 
} // End namespace SVF
 
#endif /* FlowDDA_H_ */