Partitioner2/Engine.h

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

#include <Rose/BinaryAnalysis/BinaryLoader.h>
#include <Rose/BinaryAnalysis/SerialIo.h>
#include <boost/noncopyable.hpp>
#include <boost/regex.hpp>
#include <Rose/BinaryAnalysis/Disassembler/BasicTypes.h>
#include <Rose/FileSystem.h>
#include <Rose/BinaryAnalysis/Partitioner2/Function.h>
#include <Rose/BinaryAnalysis/Partitioner2/ModulesLinux.h>
#include <Rose/BinaryAnalysis/Partitioner2/Partitioner.h>
#include <Rose/BinaryAnalysis/Partitioner2/Thunk.h>
#include <Rose/BinaryAnalysis/Partitioner2/Utility.h>
#include <Rose/Progress.h>
#include <Rose/Exception.h>
#include <Sawyer/DistinctList.h>
#include <stdexcept>

#ifdef ROSE_ENABLE_PYTHON_API
#undef slots                                            // stupid Qt pollution
#include <boost/python.hpp>
#endif

namespace Rose {
namespace BinaryAnalysis {
namespace Partitioner2 {

class ROSE_DLL_API Engine: private boost::noncopyable {
public:
    struct Settings {
        LoaderSettings loader;                          
        DisassemblerSettings disassembler;              
        PartitionerSettings partitioner;                
        EngineSettings engine;                          
        AstConstructionSettings astConstruction;        
    private:
        friend class boost::serialization::access;

        template<class S>
        void serialize(S &s, unsigned version) {
            s & loader & disassembler & partitioner & engine & astConstruction;
        }
    };

    class Exception: public Rose::Exception {
    public:
        Exception(const std::string &mesg)
            : Rose::Exception(mesg) {}
        ~Exception() throw () {}
    };

    //                                  Internal data structures
private:
    // Engine callback for handling instructions added to basic blocks.  This is called when a basic block is discovered,
    // before it's attached to a partitioner, so it shouldn't really be modifying any state in the engine, but rather only
    // preparing the basic block to be processed.
    class BasicBlockFinalizer: public BasicBlockCallback {
        typedef Sawyer::Container::Map<rose_addr_t /*target*/, std::vector<rose_addr_t> /*sources*/> WorkList;
    public:
        static Ptr instance() { return Ptr(new BasicBlockFinalizer); }
        virtual bool operator()(bool chain, const Args &args) override;
    private:
        void fixFunctionReturnEdge(const Args&);
        void fixFunctionCallEdges(const Args&);
        void addPossibleIndeterminateEdge(const Args&);
    };

    // Basic blocks that need to be worked on next. These lists are adjusted whenever a new basic block (or placeholder) is
    // inserted or erased from the CFG.
    class BasicBlockWorkList: public CfgAdjustmentCallback {
        // The following lists are used for adding outgoing E_CALL_RETURN edges to basic blocks based on whether the basic
        // block is a call to a function that might return.  When a new basic block is inserted into the CFG (or a previous
        // block is removed, modified, and re-inserted), the operator() is called and conditionally inserts the block into the
        // "pendingCallReturn" list (if the block is a function call that lacks an E_CALL_RETURN edge and the function is known
        // to return or the analysis was incomplete).
        //
        // When we run out of other ways to create basic blocks, we process the pendingCallReturn list from back to front. If
        // the back block (which gets popped) has a positive may-return result then an E_CALL_RETURN edge is added to the CFG
        // and the normal recursive BB discovery is resumed. Otherwise if the analysis is incomplete the basic block is moved
        // to the processedCallReturn list.  The entire pendingCallReturn list is processed before proceeding.
        //
        // If there is no more pendingCallReturn work to be done, then the processedCallReturn blocks are moved to the
        // finalCallReturn list and finalCallReturn is sorted by approximate CFG height (i.e., leafs first). The contents
        // of the finalCallReturn list is then analyzed and the result (or the default may-return value for failed analyses)
        // is used to decide whether a new CFG edge should be created, possibly adding new basic block addresses to the
        // list of undiscovered blocks.
        //
        Sawyer::Container::DistinctList<rose_addr_t> pendingCallReturn_;   // blocks that might need an E_CALL_RETURN edge
        Sawyer::Container::DistinctList<rose_addr_t> processedCallReturn_; // call sites whose may-return was indeterminate
        Sawyer::Container::DistinctList<rose_addr_t> finalCallReturn_;     // indeterminate call sites awaiting final analysis

        Sawyer::Container::DistinctList<rose_addr_t> undiscovered_;        // undiscovered basic block list (last-in-first-out)
        Engine *engine_;                                                   // engine to which this callback belongs
        size_t maxSorts_;                                                  // max sorts before using unsorted lists
    protected:
        BasicBlockWorkList(Engine *engine, size_t maxSorts): engine_(engine), maxSorts_(maxSorts) {}
    public:
        typedef Sawyer::SharedPointer<BasicBlockWorkList> Ptr;
        static Ptr instance(Engine *engine, size_t maxSorts) { return Ptr(new BasicBlockWorkList(engine, maxSorts)); }
        virtual bool operator()(bool chain, const AttachedBasicBlock &args) override;
        virtual bool operator()(bool chain, const DetachedBasicBlock &args) override;
        Sawyer::Container::DistinctList<rose_addr_t>& pendingCallReturn() { return pendingCallReturn_; }
        Sawyer::Container::DistinctList<rose_addr_t>& processedCallReturn() { return processedCallReturn_; }
        Sawyer::Container::DistinctList<rose_addr_t>& finalCallReturn() { return finalCallReturn_; }
        Sawyer::Container::DistinctList<rose_addr_t>& undiscovered() { return undiscovered_; }
        void moveAndSortCallReturn(const Partitioner&);
    };

    // A work list providing constants from instructions that are part of the CFG.
    class CodeConstants: public CfgAdjustmentCallback {
    public:
        typedef Sawyer::SharedPointer<CodeConstants> Ptr;

    private:
        std::set<rose_addr_t> toBeExamined_;            // instructions waiting to be examined
        std::set<rose_addr_t> wasExamined_;             // instructions we've already examined
        rose_addr_t inProgress_;                        // instruction that is currently in progress
        std::vector<rose_addr_t> constants_;            // constants for the instruction in progress

    protected:
        CodeConstants(): inProgress_(0) {}

    public:
        static Ptr instance() { return Ptr(new CodeConstants); }

        // Possibly insert more instructions into the work list when a basic block is added to the CFG
        virtual bool operator()(bool chain, const AttachedBasicBlock &attached) override;

        // Possibly remove instructions from the worklist when a basic block is removed from the CFG
        virtual bool operator()(bool chain, const DetachedBasicBlock &detached) override;

        // Return the next available constant if any.
        Sawyer::Optional<rose_addr_t> nextConstant(const Partitioner &partitioner);

        // Address of instruction being examined.
        rose_addr_t inProgress() const { return inProgress_; }
    };

    //                                  Data members
private:
    Settings settings_;                                 // Settings for the partitioner.
    SgAsmInterpretation *interp_;                       // interpretation set by loadSpecimen
    BinaryLoader::Ptr binaryLoader_;                    // how to remap, link, and fixup
    Disassembler::BasePtr disassembler_;                // not ref-counted yet, but don't destroy it since user owns it
    MemoryMap::Ptr map_;                                // memory map initialized by load()
    BasicBlockWorkList::Ptr basicBlockWorkList_;        // what blocks to work on next
    CodeConstants::Ptr codeFunctionPointers_;           // generates constants that are found in instruction ASTs
    Progress::Ptr progress_;                            // optional progress reporting
    ModulesLinux::LibcStartMain::Ptr libcStartMain_;    // looking for "main" by analyzing libc_start_main?
    ThunkPredicates::Ptr functionMatcherThunks_;        // predicates to find thunks when looking for functions
    ThunkPredicates::Ptr functionSplittingThunks_;      // predicates for splitting thunks from front of functions

    //                                  Constructors
private:
    Engine() = delete;

    explicit Engine(const Settings &settings);

public:
    virtual ~Engine();

    static Engine *instance() { return new Engine(Settings{}); };

    static Engine *instance(const Settings &settings) { return new Engine(settings); };

    //                                  The very top-level use case
public:
    SgAsmBlock* frontend(int argc, char *argv[],
                         const std::string &purpose, const std::string &description);
    virtual SgAsmBlock* frontend(const std::vector<std::string> &args,
                                 const std::string &purpose, const std::string &description);
    //                                  Basic top-level steps
public:
    void reset();

    Sawyer::CommandLine::ParserResult parseCommandLine(int argc, char *argv[],
                                                       const std::string &purpose, const std::string &description) /*final*/;
    virtual Sawyer::CommandLine::ParserResult parseCommandLine(const std::vector<std::string> &args,
                                                               const std::string &purpose, const std::string &description);
    virtual SgAsmInterpretation* parseContainers(const std::vector<std::string> &fileNames);
    SgAsmInterpretation* parseContainers(const std::string &fileName) /*final*/;
    virtual MemoryMap::Ptr loadSpecimens(const std::vector<std::string> &fileNames = std::vector<std::string>());
    MemoryMap::Ptr loadSpecimens(const std::string &fileName) /*final*/;
    virtual Partitioner partition(const std::vector<std::string> &fileNames = std::vector<std::string>());
    Partitioner partition(const std::string &fileName) /*final*/;
    SgAsmBlock* buildAst(const std::vector<std::string> &fileNames = std::vector<std::string>()) /*final*/;
    SgAsmBlock* buildAst(const std::string &fileName) /*final*/;
    virtual void savePartitioner(const Partitioner&, const boost::filesystem::path&, SerialIo::Format fmt = SerialIo::BINARY);

    virtual Partitioner loadPartitioner(const boost::filesystem::path&, SerialIo::Format fmt = SerialIo::BINARY);

    //                                  Command-line parsing
    //
    // top-level: parseCommandLine
public:
    virtual Sawyer::CommandLine::SwitchGroup loaderSwitches();
    static Sawyer::CommandLine::SwitchGroup loaderSwitches(LoaderSettings&);
    virtual Sawyer::CommandLine::SwitchGroup disassemblerSwitches();
    static Sawyer::CommandLine::SwitchGroup disassemblerSwitches(DisassemblerSettings&);
    virtual Sawyer::CommandLine::SwitchGroup partitionerSwitches();
    static Sawyer::CommandLine::SwitchGroup partitionerSwitches(PartitionerSettings&);
    virtual Sawyer::CommandLine::SwitchGroup engineSwitches();
    static Sawyer::CommandLine::SwitchGroup engineSwitches(EngineSettings&);
    virtual Sawyer::CommandLine::SwitchGroup astConstructionSwitches();
    static Sawyer::CommandLine::SwitchGroup astConstructionSwitches(AstConstructionSettings&);
    static std::string specimenNameDocumentation();

    virtual Sawyer::CommandLine::Parser commandLineParser(const std::string &purpose, const std::string &description);

    virtual void checkSettings();

    //                                  Container parsing
    //
    // top-level: parseContainers
public:
    virtual bool isRbaFile(const std::string&);

    virtual bool isNonContainer(const std::string&);

    virtual bool areContainersParsed() const;

    virtual void loadVxCore(const std::string &spec);

    //                                  Load specimens
    //
    // top-level: loadSpecimens
public:
    virtual bool areSpecimensLoaded() const;

    virtual BinaryLoader::Ptr obtainLoader(const BinaryLoader::Ptr &hint = BinaryLoader::Ptr());

    virtual void loadContainers(const std::vector<std::string> &fileNames);

    virtual void loadNonContainers(const std::vector<std::string> &names);

    virtual void adjustMemoryMap();

    MemoryMap::Ptr memoryMap() const /*final*/ { return map_; }
    virtual void memoryMap(const MemoryMap::Ptr &m) { map_ = m; }
    //                                  Disassembler
public:
    virtual Disassembler::BasePtr obtainDisassembler();
    virtual Disassembler::BasePtr obtainDisassembler(const Disassembler::BasePtr &hint);
    //                                  Partitioner high-level functions
    //
    // top-level: partition
public:
    virtual void checkCreatePartitionerPrerequisites() const;

    virtual Partitioner createBarePartitioner();

    virtual Partitioner createGenericPartitioner();

    virtual Partitioner createTunedPartitioner();

    virtual Partitioner createPartitionerFromAst(SgAsmInterpretation*);

    virtual Partitioner createPartitioner();

    virtual void runPartitionerInit(Partitioner&);

    virtual void runPartitionerRecursive(Partitioner&);

    virtual void runPartitionerFinal(Partitioner&);

    virtual void runPartitioner(Partitioner&);


    //                                  Partitioner mid-level functions
    //
    // These are the functions called by the partitioner high-level stuff.  These are sometimes overridden in subclasses,
    // although it is more likely that the high-level stuff is overridden.
public:
    virtual void labelAddresses(Partitioner&, const Configuration&);

    virtual std::vector<DataBlock::Ptr> makeConfiguredDataBlocks(Partitioner&, const Configuration&);

    virtual std::vector<Function::Ptr> makeConfiguredFunctions(Partitioner&, const Configuration&);

    virtual std::vector<Function::Ptr> makeEntryFunctions(Partitioner&, SgAsmInterpretation*);

    virtual std::vector<Function::Ptr> makeErrorHandlingFunctions(Partitioner&, SgAsmInterpretation*);

    virtual std::vector<Function::Ptr> makeImportFunctions(Partitioner&, SgAsmInterpretation*);

    virtual std::vector<Function::Ptr> makeExportFunctions(Partitioner&, SgAsmInterpretation*);

    virtual std::vector<Function::Ptr> makeSymbolFunctions(Partitioner&, SgAsmInterpretation*);

    virtual std::vector<Function::Ptr> makeContainerFunctions(Partitioner&, SgAsmInterpretation*);

    virtual std::vector<Function::Ptr> makeInterruptVectorFunctions(Partitioner&, const AddressInterval &vector);

    virtual std::vector<Function::Ptr> makeUserFunctions(Partitioner&, const std::vector<rose_addr_t>&);

    virtual void discoverBasicBlocks(Partitioner&);

    virtual Function::Ptr makeNextDataReferencedFunction(const Partitioner&, rose_addr_t &startVa /*in,out*/);

    virtual Function::Ptr makeNextCodeReferencedFunction(const Partitioner&);

    virtual std::vector<Function::Ptr> makeCalledFunctions(Partitioner&);

    virtual std::vector<Function::Ptr> makeNextPrologueFunction(Partitioner&, rose_addr_t startVa);
    virtual std::vector<Function::Ptr> makeNextPrologueFunction(Partitioner&, rose_addr_t startVa, rose_addr_t &lastSearchedVa);
    virtual std::vector<Function::Ptr>
    makeFunctionFromInterFunctionCalls(Partitioner &partitioner, rose_addr_t &startVa /*in,out*/);

    virtual void discoverFunctions(Partitioner&);

    virtual std::set<rose_addr_t> attachDeadCodeToFunction(Partitioner&, const Function::Ptr&, size_t maxIterations=size_t(-1));

    virtual DataBlock::Ptr attachPaddingToFunction(Partitioner&, const Function::Ptr&);

    virtual std::vector<DataBlock::Ptr> attachPaddingToFunctions(Partitioner&);

    virtual size_t attachAllSurroundedCodeToFunctions(Partitioner&);

    virtual size_t attachSurroundedCodeToFunctions(Partitioner&);

    virtual void attachBlocksToFunctions(Partitioner&);

    virtual std::set<rose_addr_t> attachDeadCodeToFunctions(Partitioner&, size_t maxIterations=size_t(-1));

    virtual std::vector<DataBlock::Ptr> attachSurroundedDataToFunctions(Partitioner&);

    virtual void updateAnalysisResults(Partitioner&);


    //                                  Partitioner low-level functions
    //
    // These are functions that a subclass seldom overrides, and maybe even shouldn't override because of their complexity or
    // the way the interact with one another.
public:
    virtual bool makeNextCallReturnEdge(Partitioner&, boost::logic::tribool assumeCallReturns);

    virtual BasicBlock::Ptr makeNextBasicBlockFromPlaceholder(Partitioner&);

    virtual BasicBlock::Ptr makeNextBasicBlock(Partitioner&);


    //                                  Build AST
public:
    // Used internally by ROSE's ::frontend disassemble instructions to build the AST that goes under each SgAsmInterpretation.
    static void disassembleForRoseFrontend(SgAsmInterpretation*);


    //                                  Settings and properties
public:
    const Settings& settings() const /*final*/ { return settings_; }
    Settings& settings() /*final*/ { return settings_; }
    Disassembler::BasePtr disassembler() const;
    virtual void disassembler(const Disassembler::BasePtr&);
    SgAsmInterpretation* interpretation() const /*final*/ { return interp_; }
    virtual void interpretation(SgAsmInterpretation *interp) { interp_ = interp; }
    Progress::Ptr progress() const /*final*/ { return progress_; }
    virtual void progress(const Progress::Ptr &progress) { progress_ = progress; }
    //                                  Python API support functions
#ifdef ROSE_ENABLE_PYTHON_API

    // Similar to frontend, but returns a partitioner rather than an AST since the Python API doesn't yet support ASTs.
    Partitioner pythonParseVector(boost::python::list &pyArgs, const std::string &purpose, const std::string &description);
    Partitioner pythonParseSingle(const std::string &specimen, const std::string &purpose, const std::string &description);

#endif

    //                                  Internal stuff
private:
    void init();

    // Similar to ::frontend but a lot less complicated.
    SgProject* roseFrontendReplacement(const std::vector<boost::filesystem::path> &fileNames);
};

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

#endif
#endif