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