ContextDDA.h

Go to the documentation of this file.

//===- ContextDDA.h -- Context-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/>.
//
//===----------------------------------------------------------------------===//
 
/*
 * ContextDDA.h
 *
 *  Created on: Aug 17, 2014
 *      Author: Yulei Sui
 *
 * 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 ContextDDA_H_
#define ContextDDA_H_
 
#include "MemoryModel/PointerAnalysisImpl.h"
#include "DDA/DDAVFSolver.h"
#include "Util/DPItem.h"
#include "Util/GeneralType.h"
 
namespace SVF
{
 
class FlowDDA;
class DDAClient;
typedef CxtStmtDPItem<SVFGNode> CxtLocDPItem;

class ContextDDA : public CondPTAImpl<ContextCond>, public DDAVFSolver<CxtVar,CxtPtSet,CxtLocDPItem>
{
 
public:
    ContextDDA(SVFIR* _pag, DDAClient* client);

    virtual ~ContextDDA();

    virtual void initialize() override;

    virtual inline void finalize() override
    {
        CondPTAImpl<ContextCond>::finalize();
    }

    virtual void analyze() override {}

    virtual void computeDDAPts(NodeID id) override;

    virtual const CxtPtSet& computeDDAPts(const CxtVar& cxtVar);

    void handleOutOfBudgetDpm(const CxtLocDPItem& dpm);

    virtual CxtPtSet getConservativeCPts(const CxtLocDPItem& dpm) override
    {
        const PointsTo& pts =  getAndersenAnalysis()->getPts(dpm.getCurNodeID());
        CxtPtSet tmpCPts;
        ContextCond cxt;
        for (PointsTo::iterator piter = pts.begin(); piter != pts.end(); ++piter)
        {
            CxtVar var(cxt,*piter);
            tmpCPts.set(var);
        }
        return tmpCPts;
    }

    virtual inline NodeID getPtrNodeID(const CxtVar& var) const override
    {
        return var.get_id();
    }

    virtual bool handleBKCondition(CxtLocDPItem& dpm, const SVFGEdge* edge) override;

    virtual bool isHeapCondMemObj(const CxtVar& var, const StoreSVFGNode* store) override;

    bool testIndCallReachability(CxtLocDPItem& dpm, const FunObjVar* callee, const CallICFGNode* cs);

    CallSiteID getCSIDAtCall(CxtLocDPItem& dpm, const SVFGEdge* edge);

    CallSiteID getCSIDAtRet(CxtLocDPItem& dpm, const SVFGEdge* edge);
 

    inline virtual void popRecursiveCallSites(CxtLocDPItem& dpm)
    {
        ContextCond& cxtCond = dpm.getCond();
        cxtCond.setNonConcreteCxt();
        CallStrCxt& cxt = cxtCond.getContexts();
        while(!cxt.empty() && isEdgeInRecursion(cxt.back()))
        {
            cxt.pop_back();
        }
    }

    inline virtual bool isEdgeInRecursion(CallSiteID csId)
    {
        const FunObjVar* caller = getCallGraph()->getCallerOfCallSite(csId);
        const FunObjVar* callee = getCallGraph()->getCalleeOfCallSite(csId);
        return inSameCallGraphSCC(caller, callee);
    }


    virtual void updateCallGraphAndSVFG(const CxtLocDPItem& dpm,const CallICFGNode* cs,SVFGEdgeSet& svfgEdges) override
    {
        CallEdgeMap newEdges;
        resolveIndCalls(cs, getBVPointsTo(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);
            }
        }
    }


    inline bool edgeInCallGraphSCC(const SVFGEdge* edge)
    {
        const FunObjVar* srcfun = edge->getSrcNode()->getFun();
        const FunObjVar* dstfun = edge->getDstNode()->getFun();
 
        if(srcfun && dstfun)
            return inSameCallGraphSCC(srcfun,dstfun);
 
        assert(edge->isRetVFGEdge() == false && "should not be an inter-procedural return edge" );
 
        return false;
    }

    virtual CxtPtSet processGepPts(const GepSVFGNode* gep, const CxtPtSet& srcPts) override;

    virtual void handleAddr(CxtPtSet& pts,const CxtLocDPItem& dpm,const AddrSVFGNode* addr) override
    {
        NodeID srcID = addr->getSrcNodeID();
        if (isFieldInsensitive(srcID))
            srcID = getFIObjVar(srcID);
 
        CxtVar var(dpm.getCond(),srcID);
        addDDAPts(pts,var);
        DBOUT(DDDA, SVFUtil::outs() << "\t add points-to target " << var << " to dpm ");
        DBOUT(DDDA, dpm.dump());
    }

    virtual inline bool propagateViaObj(const CxtVar& storeObj, const CxtVar& loadObj) override
    {
        return isSameVar(storeObj,loadObj);
    }

    virtual inline bool isCondCompatible(const ContextCond& cxt1, const ContextCond& cxt2, bool singleton) const override;

    bool isInsensitiveCallRet(const SVFGEdge* edge)
    {
        return insensitveEdges.find(edge) != insensitveEdges.end();
    }

    inline ConstSVFGEdgeSet& getInsensitiveEdgeSet()
    {
        return insensitveEdges;
    }

    virtual inline void dumpContexts(const ContextCond& cxts)
    {
        SVFUtil::outs() << cxts.toString() << "\n";
    }
 
    virtual const std::string PTAName() const override
    {
        return "Context Sensitive DDA";
    }
 
private:
    ConstSVFGEdgeSet insensitveEdges;
    FlowDDA* flowDDA;           
    DDAClient* _client;         
};
 
} // End namespace SVF
 
#endif /* ContextDDA_H_ */