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/AEWTO.h"
#include "AE/Svfexe/AbsExtAPI.h"
#include "AE/Svfexe/AEStat.h"
#include "SVFIR/SVFIR.h"
#include "Util/SVFBugReport.h"
#include "Util/WorkList.h"
#include "Graphs/SCC.h"
#include "Graphs/CallGraph.h"
 
namespace SVF
{
class AbstractInterpretation;
class AbsExtAPI;
class AEStat;
class AEAPI;
class AndersenWaveDiff;
 
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 AESparsity
    {
        Dense,
        SemiSparse,
        Sparse
    };
 
    enum HandleRecur
    {
        TOP,
        WIDEN_ONLY,
        WIDEN_NARROW
    };
 
    enum AEFunEntryMode
    {
        MAIN,
        NO_MAIN
    };
 
    virtual void runOnModule();
 
    virtual ~AbstractInterpretation();
 
    void analyse();
 
    void analyzeFromAllProgEntries();
 
    FIFOWorkList<const FunObjVar*> collectProgEntryFuns();
 
    static AbstractInterpretation& getAEInstance();
 
    void addDetector(std::unique_ptr<AEDetector> detector)
    {
        detectors.push_back(std::move(detector));
    }
 
    inline const SVFVar* getSVFVar(NodeID varId) const
    {
        return svfir->getSVFVar(varId);
    }
 
    // ---- Abstract Value Access ----------------------------------------
 
    virtual const AbstractValue& getAbsValue(const ValVar* var, const ICFGNode* node);
    virtual const AbstractValue& getAbsValue(const ObjVar* var, const ICFGNode* node);
    virtual const AbstractValue& getAbsValue(const SVFVar* var, const ICFGNode* node);
 
    virtual bool hasAbsValue(const ValVar* var, const ICFGNode* node) const;
    virtual bool hasAbsValue(const ObjVar* var, const ICFGNode* node) const;
    virtual bool hasAbsValue(const SVFVar* var, const ICFGNode* node) const;
 
    virtual void updateAbsValue(const ValVar* var, const AbstractValue& val, const ICFGNode* node);
    virtual void updateAbsValue(const ObjVar* var, const AbstractValue& val, const ICFGNode* node);
    virtual void updateAbsValue(const SVFVar* var, const AbstractValue& val, const ICFGNode* node);
 
    // ---- State Access -------------------------------------------------
 
    AbstractState& getAbsState(const ICFGNode* node);
 
    virtual void updateAbsState(const ICFGNode* node, const AbstractState& state);
 
    virtual void joinStates(AbstractState& dst, const AbstractState& src);
 
    bool hasAbsState(const ICFGNode* node);
 
    void getAbsState(const Set<const ValVar*>& vars, AbstractState& result, const ICFGNode* node);
    void getAbsState(const Set<const ObjVar*>& vars, AbstractState& result, const ICFGNode* node);
    void getAbsState(const Set<const SVFVar*>& vars, AbstractState& result, const ICFGNode* node);
 
    // ---- GEP / Load-Store / Type Helpers ------------------------------
 
    IntervalValue getGepElementIndex(const GepStmt* gep);
    IntervalValue getGepByteOffset(const GepStmt* gep);
    AddressValue getGepObjAddrs(const ValVar* pointer, IntervalValue offset);
 
    virtual AbstractValue loadValue(const ValVar* pointer,
                                    const ICFGNode* node);
    virtual void storeValue(const ValVar* pointer, const AbstractValue& val,
                            const ICFGNode* node);
 
    const SVFType* getPointeeElement(const ObjVar* var, const ICFGNode* node);
    u32_t getAllocaInstByteSize(const AddrStmt* addr);
 
    // ---- Direct Trace Access ------------------------------------------
 
    Map<const ICFGNode*, AbstractState>& getTrace()
    {
        return abstractTrace;
    }
    AbstractState& operator[](const ICFGNode* node)
    {
        return abstractTrace[node];
    }
 
protected:
    AbstractInterpretation();
 
    // ---- Cycle helpers overridden by SparseAbstractInterpretation ----
    // The dense versions write only to trace[cycle_head].  The semi-sparse
    // subclass adds def-site scatter on top for body ValVars.
 
    virtual AbstractState getFullCycleHeadState(const ICFGCycleWTO* cycle);
 
    virtual bool widenCycleState(const AbstractState& prev, const AbstractState& cur,
                                 const ICFGCycleWTO* cycle);
 
    virtual bool narrowCycleState(const AbstractState& prev, const AbstractState& cur,
                                  const ICFGCycleWTO* cycle);
 
protected:
    virtual bool mergeStatesFromPredecessors(const ICFGNode* node);
 
    bool isBranchEdgeFeasible(const IntraCFGEdge* edge, AbstractState& as);
 
    void collectBranchRefinement(const IntraCFGEdge* edge, AbstractState& as);
 
    virtual void recordBranchRefinement(NodeID objId,
                                        const IntervalValue& narrowed,
                                        AbstractState& as,
                                        const ICFGNode* loadIcfg,
                                        const ICFGNode* succ);
 
private:
    virtual void handleGlobalNode();
 
    virtual void handleCallSite(const ICFGNode* node);
 
    virtual void handleLoopOrRecursion(const ICFGCycleWTO* cycle, const CallICFGNode* caller);
 
    void handleFunction(const ICFGNode* funEntry, const CallICFGNode* caller);
 
    bool handleICFGNode(const ICFGNode* node);
 
    virtual void handleSVFStatement(const SVFStmt* stmt);
 
    bool isCmpBranchEdgeFeasible(const IntraCFGEdge* edge, AbstractState& as);
 
    bool isSwitchBranchEdgeFeasible(const IntraCFGEdge* edge,
                                    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);
 
    AEAPI* api{nullptr};
 
    ICFG* icfg;
    CallGraph* callGraph;
    AEStat* stat;
 
    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 skipRecursionWithTop(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);
 
    // there data should be shared with subclasses
    Map<std::string, std::function<void(const CallICFGNode*)>> func_map;
 
    Set<const ICFGNode*> allAnalyzedNodes; // All nodes ever analyzed (across all entry points)
    std::string moduleName;
 
    std::vector<std::unique_ptr<AEDetector>> detectors;
    AbsExtAPI* utils;
 
protected:
    SVFIR* svfir{nullptr};
    AEWTO* preAnalysis{nullptr};
    Map<const ICFGNode*, AbstractState> abstractTrace; 
 
    bool shouldApplyNarrowing(const FunObjVar* fun);
};
} // namespace SVF