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/PreAnalysis.h"
#include "AE/Svfexe/AbsExtAPI.h"
#include "AE/Svfexe/AEStat.h"
#include "Util/SVFBugReport.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 AbstractInterpretation
{
    friend class AEStat;
    friend class AEAPI;
    friend class BufOverflowDetector;
    friend class NullptrDerefDetector;
 
public:
    /*
     * 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));
    }
 
    inline const SVFVar* getSVFVar(NodeID varId) const
    {
        return svfir->getSVFVar(varId);
    }
 
    const AbstractValue& getAbstractValue(const ValVar* var);
 
    const AbstractValue& getAbstractValue(const ICFGNode* node, const ObjVar* var);
 
    const AbstractValue& getAbstractValue(const ICFGNode* node, const SVFVar* var);
 
    void updateAbstractValue(const ValVar* var, const AbstractValue& val);
 
    void updateAbstractValue(const ICFGNode* node, const ObjVar* var, const AbstractValue& val);
 
    void updateAbstractValue(const ICFGNode* node, const SVFVar* var, const AbstractValue& val);
 
    void propagateObjVarAbsVal(const ObjVar* var, const ICFGNode* defSite);
 
    AbstractState& getAbstractState(const ICFGNode* node);
 
    bool hasAbstractState(const ICFGNode* node);
 
    void getAbstractState(const ICFGNode* node, const Set<const ValVar*>& vars, AbstractState& result);
 
    void getAbstractState(const ICFGNode* node, const Set<const ObjVar*>& vars, AbstractState& result);
 
    void getAbstractState(const ICFGNode* node, const Set<const SVFVar*>& vars, AbstractState& result);
 
 
private:
    virtual void handleGlobalNode();
 
    void propagateToSuccessor(const ICFGNode* node,
                              const Set<const ICFGNode*>* withinSet = nullptr);
 
    bool isBranchFeasible(const IntraCFGEdge* intraEdge, AbstractState& as);
 
    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);
 
    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 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;
 
    PreAnalysis* preAnalysis{nullptr};
 
    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 void handleRecursiveCall(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 for nodes (pre-state before execution, post-state after)
    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},  // >= -> <=
    };
 
};
}