SrcSnkDDA.h

Go to the documentation of this file.

//===- SrcSnkDDA.h -- Source-sink analyzer-----------------------------------//
//
//                     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/>.
//
//===----------------------------------------------------------------------===//
 
/*
 * SrcSnkDDA.h
 *
 *  Created on: Apr 1, 2014
 *      Author: Yulei Sui
 *
 * The implementation is based on
 * (1) Yulei Sui, Ding Ye, and Jingling Xue. "Static Memory Leak Detection Using Full-Sparse Value-Flow Analysis".
 * 2012 International Symposium on Software Testing and Analysis (ISSTA'12)
 *
 * (2) Yulei Sui, Ding Ye, and Jingling Xue. "Detecting Memory Leaks Statically with Full-Sparse Value-Flow Analysis".
 * IEEE Transactions on Software Engineering (TSE'14)
 */
 
#ifndef SRCSNKANALYSIS_H_
#define SRCSNKANALYSIS_H_
 
#include "Graphs/SVFGOPT.h"
#include "SABER/ProgSlice.h"
#include "SABER/SaberSVFGBuilder.h"
#include "Util/GraphReachSolver.h"
#include "Util/SVFBugReport.h"
 
namespace SVF
{
 
typedef GraphReachSolver<SVFG*,CxtDPItem> CFLSrcSnkSolver;
 
class SrcSnkDDA : public CFLSrcSnkSolver
{
 
public:
    typedef ProgSlice::SVFGNodeSet SVFGNodeSet;
    typedef Map<const SVFGNode*,ProgSlice*> SVFGNodeToSliceMap;
    typedef SVFGNodeSet::const_iterator SVFGNodeSetIter;
    typedef CxtDPItem DPIm;
    typedef Set<DPIm> DPImSet;                          
    typedef Map<const SVFGNode*, DPImSet> SVFGNodeToDPItemsMap;     
    typedef Set<const CallICFGNode*> CallSiteSet;
    typedef NodeBS SVFGNodeBS;
    typedef ProgSlice::VFWorkList WorkList;
 
private:
    ProgSlice* _curSlice;       
    SVFGNodeSet sources;        
    SVFGNodeSet sinks;      
    std::unique_ptr<SaberCondAllocator> saberCondAllocator;
    SVFGNodeToDPItemsMap nodeToDPItemsMap;  
    SVFGNodeSet visitedSet; 
 
protected:
    SaberSVFGBuilder memSSA;
    SVFG* svfg;
    PTACallGraph* callgraph;
    SVFBugReport report; 
 
public:
 
    SrcSnkDDA() : _curSlice(nullptr), svfg(nullptr), callgraph(nullptr)
    {
        saberCondAllocator = std::make_unique<SaberCondAllocator>();
    }
    ~SrcSnkDDA() override
    {
        svfg = nullptr;
 
        delete _curSlice;
        _curSlice = nullptr;
 
        //if (callgraph != nullptr)
        //    delete callgraph;
        //callgraph = nullptr;
 
        //if(pathCondAllocator)
        //    delete pathCondAllocator;
        //pathCondAllocator = nullptr;
    }
 
    virtual void analyze(SVFModule* module);
 
    virtual void initialize(SVFModule* module);
 
    virtual void finalize()
    {
        dumpSlices();
    }
 
    SVFIR* getPAG() const
    {
        return SVFIR::getPAG();
    }
 
    inline const SVFG* getSVFG() const
    {
        return graph();
    }
 
    inline PTACallGraph* getCallgraph() const
    {
        return callgraph;
    }
 
    inline bool isGlobalSVFGNode(const SVFGNode* node) const
    {
        return memSSA.isGlobalSVFGNode(node);
    }
 
    virtual void setCurSlice(const SVFGNode* src);
 
    inline ProgSlice* getCurSlice() const
    {
        return _curSlice;
    }
    inline void addSinkToCurSlice(const SVFGNode* node)
    {
        _curSlice->addToSinks(node);
        addToCurForwardSlice(node);
    }
    inline bool isInCurForwardSlice(const SVFGNode* node)
    {
        return _curSlice->inForwardSlice(node);
    }
    inline bool isInCurBackwardSlice(const SVFGNode* node)
    {
        return _curSlice->inBackwardSlice(node);
    }
    inline void addToCurForwardSlice(const SVFGNode* node)
    {
        _curSlice->addToForwardSlice(node);
    }
    inline void addToCurBackwardSlice(const SVFGNode* node)
    {
        _curSlice->addToBackwardSlice(node);
    }
 
    virtual void initSrcs() = 0;
    virtual void initSnks() = 0;
    virtual bool isSourceLikeFun(const SVFFunction* fun)
    {
        return false;
    }
 
    virtual bool isSinkLikeFun(const SVFFunction* fun)
    {
        return false;
    }
 
    bool isSource(const SVFGNode* node) const
    {
        return getSources().find(node)!=getSources().end();
    }
 
    bool isSink(const SVFGNode* node) const
    {
        return getSinks().find(node)!=getSinks().end();
    }
 
    bool isInAWrapper(const SVFGNode* src, CallSiteSet& csIdSet);
 
    virtual void reportBug(ProgSlice* slice) = 0;
 
 
    inline const SVFGNodeSet& getSources() const
    {
        return sources;
    }
    inline SVFGNodeSetIter sourcesBegin() const
    {
        return sources.begin();
    }
    inline SVFGNodeSetIter sourcesEnd() const
    {
        return sources.end();
    }
    inline void addToSources(const SVFGNode* node)
    {
        sources.insert(node);
    }
    inline const SVFGNodeSet& getSinks() const
    {
        return sinks;
    }
    inline SVFGNodeSetIter sinksBegin() const
    {
        return sinks.begin();
    }
    inline SVFGNodeSetIter sinksEnd() const
    {
        return sinks.end();
    }
    inline void addToSinks(const SVFGNode* node)
    {
        sinks.insert(node);
    }
 
    SaberCondAllocator* getSaberCondAllocator() const
    {
        return saberCondAllocator.get();
    }
 
    inline const SVFBugReport& getBugReport() const
    {
        return report;
    }
 
protected:
    inline void FWProcessCurNode(const DPIm& item) override
    {
        const SVFGNode* node = getNode(item.getCurNodeID());
        if(isSink(node))
        {
            addSinkToCurSlice(node);
            _curSlice->setPartialReachable();
        }
        else
            addToCurForwardSlice(node);
    }
    inline void BWProcessCurNode(const DPIm& item) override
    {
        const SVFGNode* node = getNode(item.getCurNodeID());
        if(isInCurForwardSlice(node))
        {
            addToCurBackwardSlice(node);
        }
    }
    void FWProcessOutgoingEdge(const DPIm& item, SVFGEdge* edge) override;
    void BWProcessIncomingEdge(const DPIm& item, SVFGEdge* edge) override;
 
    inline bool forwardVisited(const SVFGNode* node, const DPIm& item)
    {
        SVFGNodeToDPItemsMap::const_iterator it = nodeToDPItemsMap.find(node);
        if(it!=nodeToDPItemsMap.end())
            return it->second.find(item)!=it->second.end();
        else
            return false;
    }
    inline void addForwardVisited(const SVFGNode* node, const DPIm& item)
    {
        nodeToDPItemsMap[node].insert(item);
    }
    inline bool backwardVisited(const SVFGNode* node)
    {
        return visitedSet.find(node)!=visitedSet.end();
    }
    inline void addBackwardVisited(const SVFGNode* node)
    {
        visitedSet.insert(node);
    }
    inline void clearVisitedMap()
    {
        nodeToDPItemsMap.clear();
        visitedSet.clear();
    }
 
    virtual bool isAllPathReachable()
    {
        return _curSlice->isAllReachable();
    }
    virtual bool isSomePathReachable()
    {
        return _curSlice->isPartialReachable();
    }
 
    void dumpSlices();
    void annotateSlice(ProgSlice* slice);
    void printZ3Stat();
 
};
 
} // End namespace SVF
 
#endif /* SRCSNKANALYSIS_H_ */