ProgSlice.h

Go to the documentation of this file.

//===- ProgSlice.h -- Program slicing based on SVF----------------------------//
//
//                     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/>.
//
//===----------------------------------------------------------------------===//
 
/*
 * ProgSlice.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 PROGSLICE_H_
#define PROGSLICE_H_
 
#include "SABER/SaberCondAllocator.h"
#include "Util/WorkList.h"
#include "Graphs/SVFG.h"
#include "Util/DPItem.h"
#include "Util/SVFBugReport.h"
 
namespace SVF
{
 
class ProgSlice
{
 
public:
    typedef Set<const SVFGNode*> SVFGNodeSet;
    typedef SVFGNodeSet::const_iterator SVFGNodeSetIter;
    typedef SaberCondAllocator::Condition Condition;
    typedef Map<const SVFGNode*, Condition> SVFGNodeToCondMap;  
 
    typedef FIFOWorkList<const SVFGNode*> VFWorkList;           
    typedef FIFOWorkList<const SVFBasicBlock*> CFWorkList;  
 
    typedef SaberCondAllocator::SVFGNodeToSVFGNodeSetMap SVFGNodeToSVFGNodeSetMap;
 
 
    ProgSlice(const SVFGNode* src, SaberCondAllocator* pa, const SVFG* graph):
        root(src), partialReachable(false), fullReachable(false), reachGlob(false),
        pathAllocator(pa), _curSVFGNode(nullptr), finalCond(pa->getFalseCond()), svfg(graph)
    {
    }
 
    virtual ~ProgSlice()
    {
        destroy();
    }
 
    inline u32_t getForwardSliceSize() const
    {
        return forwardslice.size();
    }
    inline u32_t getBackwardSliceSize() const
    {
        return backwardslice.size();
    }
 
    inline void addToForwardSlice(const SVFGNode* node)
    {
        forwardslice.insert(node);
    }
    inline void addToBackwardSlice(const SVFGNode* node)
    {
        backwardslice.insert(node);
    }
    inline bool inForwardSlice(const SVFGNode* node)
    {
        return forwardslice.find(node)!=forwardslice.end();
    }
    inline bool inBackwardSlice(const SVFGNode* node)
    {
        return backwardslice.find(node)!=backwardslice.end();
    }
    inline SVFGNodeSetIter forwardSliceBegin() const
    {
        return forwardslice.begin();
    }
    inline SVFGNodeSetIter forwardSliceEnd() const
    {
        return forwardslice.end();
    }
    inline SVFGNodeSetIter backwardSliceBegin() const
    {
        return backwardslice.begin();
    }
    inline SVFGNodeSetIter backwardSliceEnd() const
    {
        return backwardslice.end();
    }
 
 
    inline const SVFGNode* getSource() const
    {
        return root;
    }
    inline void addToSinks(const SVFGNode* node)
    {
        sinks.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 setPartialReachable()
    {
        partialReachable = true;
    }
    inline void setAllReachable()
    {
        fullReachable = true;
    }
    inline bool setReachGlobal()
    {
        return reachGlob = true;
    }
    inline bool isPartialReachable() const
    {
        return partialReachable || reachGlob;
    }
    inline bool isAllReachable() const
    {
        return fullReachable || reachGlob;
    }
    inline bool isReachGlobal() const
    {
        return reachGlob;
    }
 
    bool AllPathReachableSolve();
    bool isSatisfiableForAll();
    bool isSatisfiableForPairs();
 
 
    const CallICFGNode* getCallSite(const SVFGEdge* edge) const;
    const CallICFGNode* getRetSite(const SVFGEdge* edge) const;
 
 
    inline Condition condAnd(const Condition &lhs, const Condition &rhs)
    {
        return pathAllocator->condAnd(lhs,rhs);
    }
    inline Condition condOr(const Condition &lhs, const Condition &rhs)
    {
        return pathAllocator->condOr(lhs,rhs);
    }
    inline Condition condNeg(const Condition &cond)
    {
        return pathAllocator->condNeg(cond);
    }
    inline Condition getTrueCond() const
    {
        return pathAllocator->getTrueCond();
    }
    inline Condition getFalseCond() const
    {
        return pathAllocator->getFalseCond();
    }
    inline std::string dumpCond(const Condition& cond) const
    {
        return pathAllocator->dumpCond(cond);
    }
    std::string evalFinalCond() const;
    void evalFinalCond2Event(GenericBug::EventStack &eventStack) const;
 
protected:
    inline const SVFG* getSVFG() const
    {
        return svfg;
    }
 
    void destroy();
    inline void clearCFCond()
    {
        pathAllocator->clearCFCond();
    }
 
 
    inline Condition getVFCond(const SVFGNode* node) const
    {
        SVFGNodeToCondMap::const_iterator it = svfgNodeToCondMap.find(node);
        if(it==svfgNodeToCondMap.end())
        {
            return getFalseCond();
        }
        return it->second;
    }
    inline bool setVFCond(const SVFGNode* node, const Condition &cond)
    {
        SVFGNodeToCondMap::iterator it = svfgNodeToCondMap.find(node);
        // until a fixed-point is reached (condition is not changed)
        if(it!=svfgNodeToCondMap.end() && isEquivalentBranchCond(it->second, cond))
            return false;
 
        svfgNodeToCondMap[node] = cond;
        return true;
    }
 
 
    inline Condition ComputeIntraVFGGuard(const SVFBasicBlock* src, const SVFBasicBlock* dst)
    {
        return pathAllocator->ComputeIntraVFGGuard(src,dst);
    }
    inline Condition ComputeInterCallVFGGuard(const SVFBasicBlock* src, const SVFBasicBlock* dst, const SVFBasicBlock* callBB)
    {
        return pathAllocator->ComputeInterCallVFGGuard(src,dst,callBB);
    }
    inline Condition ComputeInterRetVFGGuard(const SVFBasicBlock* src, const SVFBasicBlock* dst, const SVFBasicBlock* retBB)
    {
        return pathAllocator->ComputeInterRetVFGGuard(src,dst,retBB);
    }
 
    inline bool isEquivalentBranchCond(const Condition &lhs, const Condition &rhs) const
    {
        return pathAllocator->isEquivalentBranchCond(lhs, rhs);
    };
 
    inline const SVFBasicBlock* getSVFGNodeBB(const SVFGNode* node) const
    {
        const ICFGNode* icfgNode = node->getICFGNode();
        if(SVFUtil::isa<NullPtrSVFGNode>(node) == false)
        {
            return icfgNode->getBB();
        }
        return nullptr;
    }
 
 
    inline const SVFGNode* getCurSVFGNode() const
    {
        return _curSVFGNode;
    }
    inline void setCurSVFGNode(const SVFGNode* node)
    {
        _curSVFGNode = node;
        pathAllocator->setCurEvalSVFGNode(node);
    }
 
    inline void setFinalCond(const Condition &cond)
    {
        finalCond = cond;
    }
 
    Condition computeInvalidCondFromRemovedSUVFEdge(const SVFGNode * cur);
 
    const SVFGNodeToSVFGNodeSetMap& getRemovedSUVFEdges() const
    {
        return pathAllocator->getRemovedSUVFEdges();
    }
 
private:
    SVFGNodeSet forwardslice;               
    SVFGNodeSet backwardslice;              
    SVFGNodeSet sinks;                      
    const SVFGNode* root;                   
    SVFGNodeToCondMap svfgNodeToCondMap;    
    bool partialReachable;                  
    bool fullReachable;                     
    bool reachGlob;                         
    SaberCondAllocator* pathAllocator;      
    const SVFGNode* _curSVFGNode;           
    Condition finalCond;                    
    const SVFG* svfg;                       
};
 
} // End namespace SVF
 
#endif /* PROGSLICE_H_ */