AbstractInterpretation.h

Go to the documentation of this file.

//===- AbstractInterpretation.h -- Abstract Execution----------//
//
//                     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/>.
//
//===----------------------------------------------------------------------===//
 
 
//
//  Created on: Jan 10, 2024
//      Author: Xiao Cheng, Jiawei Wang
// The implementation is based on
// Xiao Cheng, Jiawei Wang and Yulei Sui. Precise Sparse Abstract Execution via Cross-Domain Interaction.
// 46th International Conference on Software Engineering. (ICSE24)
//
#pragma once
#include "AE/Core/AbstractState.h"
#include "AE/Core/ICFGWTO.h"
#include "AE/Svfexe/AEDetector.h"
#include "AE/Svfexe/AbsExtAPI.h"
#include "Util/SVFBugReport.h"
#include "Util/SVFStat.h"
#include "Graphs/SCC.h"
#include "Graphs/CallGraph.h"
#include <deque>
 
namespace SVF
{
class AbstractInterpretation;
class AbsExtAPI;
class AEStat;
class AEAPI;
 
template<typename T> class FILOWorkList;
 
class AEStat : public SVFStat
{
public:
    void countStateSize();
    AEStat(AbstractInterpretation* ae) : _ae(ae)
    {
        startTime = getClk(true);
    }
    ~AEStat()
    {
    }
    inline std::string getMemUsage()
    {
        u32_t vmrss, vmsize;
        return SVFUtil::getMemoryUsageKB(&vmrss, &vmsize) ? std::to_string(vmsize) + "KB" : "cannot read memory usage";
    }
 
    void finializeStat();
    void performStat() override;
 
public:
    AbstractInterpretation* _ae;
    s32_t count{0};
    std::string memory_usage;
    std::string memUsage;
 
 
    u32_t& getFunctionTrace()
    {
        if (generalNumMap.count("Function_Trace") == 0)
        {
            generalNumMap["Function_Trace"] = 0;
        }
        return generalNumMap["Function_Trace"];
    }
    u32_t& getBlockTrace()
    {
        if (generalNumMap.count("Block_Trace") == 0)
        {
            generalNumMap["Block_Trace"] = 0;
        }
        return generalNumMap["Block_Trace"];
    }
    u32_t& getICFGNodeTrace()
    {
        if (generalNumMap.count("ICFG_Node_Trace") == 0)
        {
            generalNumMap["ICFG_Node_Trace"] = 0;
        }
        return generalNumMap["ICFG_Node_Trace"];
    }
};
 
class AbstractInterpretation
{
    friend class AEStat;
    friend class AEAPI;
    friend class BufOverflowDetector;
    friend class NullptrDerefDetector;
 
public:
    typedef SCCDetection<CallGraph*> CallGraphSCC;
 
    /*
     * For recursive test case
     * int demo(int a) {
        if (a >= 10000)
            return a;
            demo(a+1);
        }
 
        int main() {
            int result = demo(0);
        }
     * if set TOP, result = [-oo, +oo] since the return value, and any stored object pointed by q at *q = p in recursive functions will be set to the top value.
     * if set WIDEN_ONLY, result = [10000, +oo] since only widening is applied at the cycle head of recursive functions without narrowing.
     * if set WIDEN_NARROW, result = [10000, 10000] since both widening and narrowing are applied at the cycle head of recursive functions.
     * */
    enum HandleRecur
    {
        TOP,
        WIDEN_ONLY,
        WIDEN_NARROW
    };
 
    AbstractInterpretation();
 
    virtual void runOnModule(ICFG* icfg);
 
    virtual ~AbstractInterpretation();
 
    void analyse();
 
    void analyzeFromAllProgEntries();
 
    std::deque<const FunObjVar*> collectProgEntryFuns();
 
 
    static AbstractInterpretation& getAEInstance()
    {
        static AbstractInterpretation instance;
        return instance;
    }
 
    void addDetector(std::unique_ptr<AEDetector> detector)
    {
        detectors.push_back(std::move(detector));
    }
 
    Set<const CallICFGNode*> checkpoints; // for CI check
 
    AbstractState& getAbsStateFromTrace(const ICFGNode* node)
    {
        if (abstractTrace.count(node) == 0)
        {
            assert(false && "No preAbsTrace for this node");
            abort();
        }
        else
        {
            return abstractTrace[node];
        }
    }
 
private:
    virtual void handleGlobalNode();
 
    void initWTO();
 
    bool mergeStatesFromPredecessors(const ICFGNode * icfgNode);
 
    bool isBranchFeasible(const IntraCFGEdge* intraEdge, AbstractState& as);
 
    virtual void handleSingletonWTO(const ICFGSingletonWTO *icfgSingletonWto);
 
    virtual void handleCallSite(const ICFGNode* node);
 
    virtual void handleLoopOrRecursion(const ICFGCycleWTO* cycle, const CallICFGNode* caller = nullptr);
 
    void handleFunction(const ICFGNode* funEntry, const CallICFGNode* caller = nullptr);
 
    bool handleICFGNode(const ICFGNode* node);
 
    std::vector<const ICFGNode*> getNextNodes(const ICFGNode* node) const;
 
    std::vector<const ICFGNode*> getNextNodesOfCycle(const ICFGCycleWTO* cycle) const;
 
    void collectCycleHeads(const std::list<const ICFGWTOComp*>& comps);
 
 
    virtual void handleSVFStatement(const SVFStmt* stmt);
 
    virtual void setTopToObjInRecursion(const CallICFGNode* callnode);
 
 
    bool isCmpBranchFeasible(const CmpStmt* cmpStmt, s64_t succ,
                             AbstractState& as);
 
    bool isSwitchBranchFeasible(const SVFVar* var, s64_t succ,
                                AbstractState& as);
 
 
    void collectCheckPoint();
    void checkPointAllSet();
 
    void updateStateOnAddr(const AddrStmt *addr);
 
    void updateStateOnBinary(const BinaryOPStmt *binary);
 
    void updateStateOnCmp(const CmpStmt *cmp);
 
    void updateStateOnLoad(const LoadStmt *load);
 
    void updateStateOnStore(const StoreStmt *store);
 
    void updateStateOnCopy(const CopyStmt *copy);
 
    void updateStateOnCall(const CallPE *callPE);
 
    void updateStateOnRet(const RetPE *retPE);
 
    void updateStateOnGep(const GepStmt *gep);
 
    void updateStateOnSelect(const SelectStmt *select);
 
    void updateStateOnPhi(const PhiStmt *phi);
 
 
    SVFIR* svfir;
    AEAPI* api{nullptr};
 
    ICFG* icfg;
    CallGraph* callGraph;
    AEStat* stat;
 
    Map<const FunObjVar*, const ICFGWTO*> funcToWTO;
    Set<std::pair<const CallICFGNode*, NodeID>> nonRecursiveCallSites;
    Set<const FunObjVar*> recursiveFuns;
    Map<const ICFGNode*, const ICFGCycleWTO*> cycleHeadToCycle;
 
 
    bool hasAbsStateFromTrace(const ICFGNode* node)
    {
        return abstractTrace.count(node) != 0;
    }
 
    AbsExtAPI* getUtils()
    {
        return utils;
    }
 
    // helper functions in handleCallSite
    virtual bool isExtCall(const CallICFGNode* callNode);
    virtual void handleExtCall(const CallICFGNode* callNode);
    virtual bool isRecursiveFun(const FunObjVar* fun);
    virtual bool isRecursiveCall(const CallICFGNode* callNode);
    virtual void recursiveCallPass(const CallICFGNode *callNode);
    virtual bool isRecursiveCallSite(const CallICFGNode* callNode, const FunObjVar *);
    virtual void handleFunCall(const CallICFGNode* callNode);
 
    bool skipRecursiveCall(const CallICFGNode* callNode);
    const FunObjVar* getCallee(const CallICFGNode* callNode);
    bool shouldApplyNarrowing(const FunObjVar* fun);
 
    // there data should be shared with subclasses
    Map<std::string, std::function<void(const CallICFGNode*)>> func_map;
 
    Map<const ICFGNode*, AbstractState> abstractTrace; // abstract states immediately after nodes
    Set<const ICFGNode*> allAnalyzedNodes; // All nodes ever analyzed (across all entry points)
    std::string moduleName;
 
    std::vector<std::unique_ptr<AEDetector>> detectors;
    AbsExtAPI* utils;
 
    // according to varieties of cmp insts,
    // maybe var X var, var X const, const X var, const X const
    // we accept 'var X const' 'var X var' 'const X const'
    // if 'const X var', we need to reverse op0 op1 and its predicate 'var X' const'
    // X' is reverse predicate of X
    // == -> !=, != -> ==, > -> <=, >= -> <, < -> >=, <= -> >
 
    Map<s32_t, s32_t> _reverse_predicate =
    {
        {CmpStmt::Predicate::FCMP_OEQ, CmpStmt::Predicate::FCMP_ONE},  // == -> !=
        {CmpStmt::Predicate::FCMP_UEQ, CmpStmt::Predicate::FCMP_UNE},  // == -> !=
        {CmpStmt::Predicate::FCMP_OGT, CmpStmt::Predicate::FCMP_OLE},  // > -> <=
        {CmpStmt::Predicate::FCMP_OGE, CmpStmt::Predicate::FCMP_OLT},  // >= -> <
        {CmpStmt::Predicate::FCMP_OLT, CmpStmt::Predicate::FCMP_OGE},  // < -> >=
        {CmpStmt::Predicate::FCMP_OLE, CmpStmt::Predicate::FCMP_OGT},  // <= -> >
        {CmpStmt::Predicate::FCMP_ONE, CmpStmt::Predicate::FCMP_OEQ},  // != -> ==
        {CmpStmt::Predicate::FCMP_UNE, CmpStmt::Predicate::FCMP_UEQ},  // != -> ==
        {CmpStmt::Predicate::ICMP_EQ, CmpStmt::Predicate::ICMP_NE},  // == -> !=
        {CmpStmt::Predicate::ICMP_NE, CmpStmt::Predicate::ICMP_EQ},  // != -> ==
        {CmpStmt::Predicate::ICMP_UGT, CmpStmt::Predicate::ICMP_ULE},  // > -> <=
        {CmpStmt::Predicate::ICMP_ULT, CmpStmt::Predicate::ICMP_UGE},  // < -> >=
        {CmpStmt::Predicate::ICMP_UGE, CmpStmt::Predicate::ICMP_ULT},  // >= -> <
        {CmpStmt::Predicate::ICMP_SGT, CmpStmt::Predicate::ICMP_SLE},  // > -> <=
        {CmpStmt::Predicate::ICMP_SLT, CmpStmt::Predicate::ICMP_SGE},  // < -> >=
        {CmpStmt::Predicate::ICMP_SGE, CmpStmt::Predicate::ICMP_SLT},  // >= -> <
    };
 
 
    Map<s32_t, s32_t> _switch_lhsrhs_predicate =
    {
        {CmpStmt::Predicate::FCMP_OEQ, CmpStmt::Predicate::FCMP_OEQ},  // == -> ==
        {CmpStmt::Predicate::FCMP_UEQ, CmpStmt::Predicate::FCMP_UEQ},  // == -> ==
        {CmpStmt::Predicate::FCMP_OGT, CmpStmt::Predicate::FCMP_OLT},  // > -> <
        {CmpStmt::Predicate::FCMP_OGE, CmpStmt::Predicate::FCMP_OLE},  // >= -> <=
        {CmpStmt::Predicate::FCMP_OLT, CmpStmt::Predicate::FCMP_OGT},  // < -> >
        {CmpStmt::Predicate::FCMP_OLE, CmpStmt::Predicate::FCMP_OGE},  // <= -> >=
        {CmpStmt::Predicate::FCMP_ONE, CmpStmt::Predicate::FCMP_ONE},  // != -> !=
        {CmpStmt::Predicate::FCMP_UNE, CmpStmt::Predicate::FCMP_UNE},  // != -> !=
        {CmpStmt::Predicate::ICMP_EQ, CmpStmt::Predicate::ICMP_EQ},  // == -> ==
        {CmpStmt::Predicate::ICMP_NE, CmpStmt::Predicate::ICMP_NE},  // != -> !=
        {CmpStmt::Predicate::ICMP_UGT, CmpStmt::Predicate::ICMP_ULT},  // > -> <
        {CmpStmt::Predicate::ICMP_ULT, CmpStmt::Predicate::ICMP_UGT},  // < -> >
        {CmpStmt::Predicate::ICMP_UGE, CmpStmt::Predicate::ICMP_ULE},  // >= -> <=
        {CmpStmt::Predicate::ICMP_SGT, CmpStmt::Predicate::ICMP_SLT},  // > -> <
        {CmpStmt::Predicate::ICMP_SLT, CmpStmt::Predicate::ICMP_SGT},  // < -> >
        {CmpStmt::Predicate::ICMP_SGE, CmpStmt::Predicate::ICMP_SLE},  // >= -> <=
    };
 
};
}