Variables.h

#ifndef ROSE_BinaryAnalysis_Variables_H
#define ROSE_BinaryAnalysis_Variables_H
#include <featureTests.h>
#ifdef ROSE_ENABLE_BINARY_ANALYSIS

#include <Rose/BinaryAnalysis/InstructionSemantics/BaseSemantics/BasicTypes.h>
#include <Rose/BinaryAnalysis/InstructionSemantics/BaseSemantics/MemoryCellState.h>
#include <Rose/BinaryAnalysis/Partitioner2/BasicTypes.h>
#include <Rose/BinaryAnalysis/SymbolicExpression.h>

#include <Sawyer/IntervalMap.h>
#include <Sawyer/Message.h>
#include <Sawyer/Optional.h>
#include <Sawyer/Set.h>

#include <boost/serialization/access.hpp>
#include <boost/serialization/split_member.hpp>

#include <chrono>
#include <map>
#include <ostream>
#include <set>
#include <string>
#include <vector>

namespace Rose {
namespace BinaryAnalysis {

namespace Variables {

// Basic types

typedef Sawyer::Container::Set<rose_addr_t> AddressSet;

typedef std::map<int64_t /*offset*/, AddressSet> OffsetToAddresses;

typedef std::map<rose_addr_t /*globalVa*/, AddressSet /*insns*/> AddressToAddresses;

typedef Sawyer::Container::Interval<int64_t> OffsetInterval;

// Global variables

extern Sawyer::Message::Facility mlog;

// Global utilities

void initDiagnostics();

std::string offsetStr(int64_t offset);

std::string sizeStr(uint64_t size);

// Base class for variable descriptors

class BaseVariable {
    rose_addr_t maxSizeBytes_ = 0;                  // maximum possible size of this variable in bytes
    AddressSet insnVas_;                            // instructions where the variable was detected that reference the variable
    InstructionSemantics::BaseSemantics::InputOutputPropertySet ioProperties_; 
    std::string name_;                              // optional variable name

#ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
private:
    friend class boost::serialization::access;

    template<class S>
    void serialize(S &s, const unsigned /*version*/) {
        s & BOOST_SERIALIZATION_NVP(maxSizeBytes_);
        s & BOOST_SERIALIZATION_NVP(insnVas_);
        s & BOOST_SERIALIZATION_NVP(ioProperties_);
        s & BOOST_SERIALIZATION_NVP(name_);
    }
#endif
    
protected:
    BaseVariable();

    BaseVariable(size_t maxSizeBytes, const AddressSet &definingInstructionVas, const std::string &name);

public:
    BaseVariable(const BaseVariable&);
    ~BaseVariable();

public:
    rose_addr_t maxSizeBytes() const;
    void maxSizeBytes(rose_addr_t size);
    const AddressSet& definingInstructionVas() const;
    AddressSet& definingInstructionVas();
    void definingInstructionVas(const AddressSet &vas);
    const InstructionSemantics::BaseSemantics::InputOutputPropertySet& ioProperties() const;
    InstructionSemantics::BaseSemantics::InputOutputPropertySet& ioProperties();
    void ioProperties(const InstructionSemantics::BaseSemantics::InputOutputPropertySet &set);
    const std::string& name() const;
    void name(const std::string &s);
};

// Local variable descriptors

class StackVariable: public BaseVariable {
public:
    enum class Purpose {
        RETURN_ADDRESS,                                 
        FRAME_POINTER,                                  
        SPILL_AREA,                                     
        NORMAL,                                         
        UNKNOWN,                                        
        OTHER                                           
    };

    struct Boundary {
        int64_t frameOffset = 0;                        
        AddressSet definingInsns;                       
        Purpose purpose = Purpose::UNKNOWN;             
    };

    using Boundaries = std::vector<Boundary>;

private:
    Partitioner2::FunctionPtr function_;            // function in which local variable exists
    int64_t frameOffset_ = 0;                       // offset where variable is located in the function's stack frame
    Purpose purpose_ = Purpose::UNKNOWN;

#ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
private:
    friend class boost::serialization::access;

    template<class S>
    void serialize(S &s, const unsigned version) {
        s & BOOST_SERIALIZATION_BASE_OBJECT_NVP(BaseVariable);
        s & BOOST_SERIALIZATION_NVP(function_);
        s & BOOST_SERIALIZATION_NVP(frameOffset_);
        if (version >= 1)
            s & BOOST_SERIALIZATION_NVP(purpose_);
    }
#endif
        
public:
    StackVariable();

    StackVariable(const Partitioner2::FunctionPtr&, int64_t frameOffset, rose_addr_t maxSizeBytes, Purpose,
                  const AddressSet &definingInstructionVas = AddressSet(), const std::string &name = "");

    StackVariable(const StackVariable&);
    ~StackVariable();

    Partitioner2::FunctionPtr function() const;
    void function(const Partitioner2::FunctionPtr&);
    int64_t frameOffset() const;
    void frameOffset(int64_t offset);
    Purpose purpose() const;
    void purpose(Purpose p);
    const std::string& setDefaultName();

    bool operator==(const StackVariable &other) const;
    bool operator!=(const StackVariable &other) const;
    OffsetInterval interval() const;

    static Boundary& insertBoundary(Boundaries& /*in,out*/, int64_t frameOffset, rose_addr_t insnVa);

    void print(std::ostream&) const;
    std::string toString() const;
    explicit operator bool() const {
        return !interval().isEmpty();
    }

    bool operator!() const {
        return interval().isEmpty();
    }

    friend std::ostream& operator<<(std::ostream&, const Rose::BinaryAnalysis::Variables::StackVariable&);
};

using StackVariables = Sawyer::Container::IntervalMap<OffsetInterval, StackVariable>;

void print(const StackVariables&, const Partitioner2::PartitionerConstPtr&, std::ostream &out, const std::string &prefix = "");

// Global variable descriptors

class GlobalVariable: public BaseVariable {
    rose_addr_t address_ = 0;                           // starting (lowest) virtual address

#ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
private:
    friend class boost::serialization::access;

    template<class S>
    void serialize(S &s, const unsigned /*version*/) {
        s & BOOST_SERIALIZATION_BASE_OBJECT_NVP(BaseVariable);
        s & BOOST_SERIALIZATION_NVP(address_);
    }
#endif
    
public:
    GlobalVariable();

    GlobalVariable(rose_addr_t startingAddress, rose_addr_t maxSizeBytes,
                   const AddressSet &definingInstructionVas = AddressSet(), const std::string &name = "");

    ~GlobalVariable();

    rose_addr_t address() const;
    void address(rose_addr_t va);
    const std::string& setDefaultName();

    bool operator==(const GlobalVariable &other) const;
    bool operator!=(const GlobalVariable &other) const;
    AddressInterval interval() const;

    void print(std::ostream&) const;
    std::string toString() const;
    explicit operator bool() const {
        return !interval().isEmpty();
    }

    bool operator!() const {
        return interval().isEmpty();
    }

    friend std::ostream& operator<<(std::ostream&, const Rose::BinaryAnalysis::Variables::GlobalVariable&);
};

typedef Sawyer::Container::IntervalMap<AddressInterval, GlobalVariable> GlobalVariables;

void erase(GlobalVariables&, const AddressInterval &toErase);

void print(const GlobalVariables&,const Partitioner2::PartitionerConstPtr&, std::ostream &out, const std::string &prefix = "");

AddressInterval isInconsistent(const GlobalVariables&, Sawyer::Message::Stream&);

// StackFrame

class StackFrame {
public:
    enum Direction {
        GROWS_UP,                                       
        GROWS_DOWN                                      
    };

    Direction growthDirection = GROWS_DOWN;             
    RegisterDescriptor framePointerRegister;            
    Sawyer::Optional<int64_t> maxOffset;                
    Sawyer::Optional<int64_t> minOffset;                
    Sawyer::Optional<uint64_t> size;                    
    std::string rule;                                   
};

// Analyzer

class VariableFinder: public Sawyer::SharedObject {
public:
    struct Settings {
        std::chrono::seconds gvarMethod1MaxTimePerFunction;

        Settings()
            : gvarMethod1MaxTimePerFunction(30) {}
    };

    using Ptr = VariableFinderPtr;

private:
    Settings settings_;

protected:
    explicit VariableFinder(const Settings&);
public:
    ~VariableFinder();

public:
    static Ptr instance(const Settings &settings = Settings());

    const Settings& settings() const { return settings_; }
    Settings& settings() { return settings_; }
    StackVariables findStackVariables(const Partitioner2::PartitionerConstPtr&, const Partitioner2::FunctionPtr&);
    StackVariables findStackVariables(const Partitioner2::PartitionerConstPtr&, SgAsmInstruction*);
    GlobalVariables findGlobalVariables(const Partitioner2::PartitionerConstPtr&);

    void evict(const Partitioner2::FunctionPtr&);
    void evict(const Partitioner2::PartitionerConstPtr&);
    bool isCached(const Partitioner2::FunctionPtr&);

    StackFrame detectFrameAttributes(const Partitioner2::PartitionerConstPtr&, const Partitioner2::FunctionPtr&);

    void initializeFrameBoundaries(const StackFrame&, const Partitioner2::PartitionerConstPtr&, const Partitioner2::FunctionPtr&,
                                   StackVariable::Boundaries &boundaries /*in,out*/);

#if 0 // [Robb Matzke 2021-10-27]

    OffsetInterval referencedFrameArea(const Partitioner2::Partitioner&,
                                       const InstructionSemantics::BaseSemantics::RiscOperatorsPtr&,
                                       const SymbolicExpression::Ptr &address, size_t nBytes);
#endif

    std::set<int64_t> findFrameOffsets(const StackFrame&, const Partitioner2::PartitionerConstPtr&, SgAsmInstruction*);

    Partitioner2::FunctionPtr functionForInstruction(const Partitioner2::PartitionerConstPtr&, SgAsmInstruction*);

    AddressToAddresses findGlobalVariableVas(const Partitioner2::PartitionerConstPtr&);

    std::set<rose_addr_t> findConstants(const SymbolicExpression::Ptr&);

    std::set<rose_addr_t> findConstants(SgAsmInstruction*);

    std::set<SymbolicExpression::Ptr> getMemoryAddresses(const InstructionSemantics::BaseSemantics::MemoryCellStatePtr&);

    std::set<rose_addr_t> findAddressConstants(const InstructionSemantics::BaseSemantics::MemoryCellStatePtr&);

#if 0 // [Robb Matzke 2021-10-27]

    InstructionSemantics::BaseSemantics::SValuePtr
    symbolicAddress(const Partitioner2::Partitioner&, const StackVariable&,
                    const InstructionSemantics::BaseSemantics::RiscOperatorsPtr&);
#endif

    void removeOutliers(const StackFrame&, const Partitioner2::PartitionerConstPtr&, const Partitioner2::FunctionPtr&,
                        StackVariable::Boundaries &sortedBoundaries /*in,out*/);

    static bool regionContainsInstructions(const Partitioner2::PartitionerConstPtr&, const AddressInterval&);

    static bool regionIsFullyMapped(const Partitioner2::PartitionerConstPtr&, const AddressInterval&);

    static bool regionIsFullyReadWrite(const Partitioner2::PartitionerConstPtr&, const AddressInterval&);

private:
    // Searches for global variables using a per-function data-flow analysis and distinguishing between global variable
    // addresses based on which instructions wrote to those addresses. The data-flow is inter-procedural only for calls to
    // certain functions (such as the x86 get_pc_thunk variety of functions).
    //
    // The return value is a list of global variable addresses and the instructions at which each global variable address
    // was detected.
    AddressToAddresses findGlobalVariableVasMethod1(const Partitioner2::PartitionerConstPtr&);

    // Searches for global variables by running each instruction individually in symbolic semantics and then searching
    // the memory state addresses. All constants found in address expressions are gathered together.
    //
    // The return value is a list of global variable addresses and the instructions at which each global address was detected.
    AddressToAddresses findGlobalVariableVasMethod2(const Partitioner2::PartitionerConstPtr&);

    // Searches for global variables by looking for constants in instruction ASTs.
    //
    // The retun value is the list of constants and the instructions in which each constant appeared.
    AddressToAddresses findGlobalVariableVasMethod3(const Partitioner2::PartitionerConstPtr&);

    // Merge one set of addresses and their defining instructions into another.
    static void merge(AddressToAddresses&, const AddressToAddresses&);
};

} // namespace
} // namespace
} // namespace

// Class versions must be at global scope
BOOST_CLASS_VERSION(Rose::BinaryAnalysis::Variables::StackVariable, 1);

#endif
#endif