BinaryFeasiblePath.h

#ifndef ROSE_BinaryAnalysis_FeasiblePath_H
#define ROSE_BinaryAnalysis_FeasiblePath_H

#include <BaseSemantics2.h>
#include <BinarySmtSolver.h>
#include <BinarySymbolicExprParser.h>
#include <Partitioner2/CfgPath.h>
#include <Sawyer/CommandLine.h>
#include <Sawyer/Message.h>
#include <boost/filesystem/path.hpp>

namespace Rose {
namespace BinaryAnalysis {

class FeasiblePath {
    //                                  Types and public data members
public:
    enum SearchMode { SEARCH_SINGLE_DFS, SEARCH_SINGLE_BFS, SEARCH_MULTI };

    enum SemanticMemoryParadigm {
        LIST_BASED_MEMORY,                              
        MAP_BASED_MEMORY                                
    };

    enum IoMode { READ, WRITE };

    enum MayOrMust { MAY, MUST };

    struct Settings {
        // Path feasibility
        SearchMode searchMode;                          
        Sawyer::Optional<rose_addr_t> initialStackPtr;  
        size_t vertexVisitLimit;                        
        size_t maxPathLength;                           
        size_t maxCallDepth;                            
        size_t maxRecursionDepth;                       
        std::vector<SymbolicExpr::Ptr> postConditions;  
        std::vector<std::string> postConditionStrings;  
        std::vector<rose_addr_t> summarizeFunctions;    
        bool nonAddressIsFeasible;                      
        std::string solverName;                         
        SemanticMemoryParadigm memoryParadigm;          
        // Null dereferences
        struct NullDeref {
            bool check;                                 
            MayOrMust mode;                             
            bool constOnly;                             
            NullDeref()
                : check(false), mode(MUST), constOnly(false) {}
        } nullDeref;                                    
        Settings()
            : searchMode(SEARCH_SINGLE_DFS), vertexVisitLimit((size_t)-1), maxPathLength((size_t)-1), maxCallDepth((size_t)-1),
              maxRecursionDepth((size_t)-1), nonAddressIsFeasible(true), solverName("best"),
              memoryParadigm(LIST_BASED_MEMORY) {}
    };

    static Sawyer::Message::Facility mlog;

     RegisterDescriptor REG_PATH;

    struct VarDetail {
        std::string registerName;
        std::string firstAccessMode;                    
        SgAsmInstruction *firstAccessInsn;              
        Sawyer::Optional<size_t> firstAccessIdx;        
        SymbolicExpr::Ptr memAddress;                   
        size_t memSize;                                 
        size_t memByteNumber;                           
        Sawyer::Optional<rose_addr_t> returnFrom;       
        VarDetail(): firstAccessInsn(NULL), memSize(0), memByteNumber(0) {}
        std::string toString() const;
    };

    typedef Sawyer::Container::Map<std::string /*name*/, FeasiblePath::VarDetail> VarDetails;

    class PathProcessor {
    public:
        enum Action {
            BREAK,                                      
            CONTINUE                                    
        };

        virtual ~PathProcessor() {}

        virtual Action found(const FeasiblePath &analyzer, const Partitioner2::CfgPath &path,
                             const std::vector<SymbolicExpr::Ptr> &pathConditions,
                             const InstructionSemantics2::BaseSemantics::DispatcherPtr&,
                             const SmtSolverPtr &solver) { return CONTINUE; };

        virtual void nullDeref(IoMode ioMode, const InstructionSemantics2::BaseSemantics::SValuePtr &addr, SgAsmInstruction*) {}

        virtual void memoryIo(const FeasiblePath &analyzer, IoMode ioMode,
                              const InstructionSemantics2::BaseSemantics::SValuePtr &addr,
                              const InstructionSemantics2::BaseSemantics::SValuePtr &value,
                              const InstructionSemantics2::BaseSemantics::RiscOperatorsPtr &ops) {}
    };

    struct FunctionSummary {
        rose_addr_t address;                            
        int64_t stackDelta;                             
        std::string name;                               
        FunctionSummary(): stackDelta(SgAsmInstruction::INVALID_STACK_DELTA) {}

        FunctionSummary(const Partitioner2::ControlFlowGraph::ConstVertexIterator &cfgFuncVertex, uint64_t stackDelta);
    };

    typedef Sawyer::Container::Map<rose_addr_t, FunctionSummary> FunctionSummaries;

    class FunctionSummarizer: public Sawyer::SharedObject {
    public:
        typedef Sawyer::SharedPointer<FunctionSummarizer> Ptr;
    protected:
        FunctionSummarizer() {}
    public:
        virtual void init(const FeasiblePath &analysis, FunctionSummary &summary /*in,out*/,
                          const Partitioner2::Function::Ptr &function,
                          Partitioner2::ControlFlowGraph::ConstVertexIterator cfgCallTarget) = 0;

        virtual bool process(const FeasiblePath &analysis, const FunctionSummary &summary,
                             const InstructionSemantics2::SymbolicSemantics::RiscOperatorsPtr &ops) = 0;

        virtual InstructionSemantics2::SymbolicSemantics::SValuePtr
        returnValue(const FeasiblePath &analysis, const FunctionSummary &summary,
                    const InstructionSemantics2::SymbolicSemantics::RiscOperatorsPtr &ops) = 0;
    };
    
    //                                  Private data members
private:
    const Partitioner2::Partitioner *partitioner_;      // binary analysis context
    RegisterDictionary *registers_;                     // registers augmented with "path" pseudo-register
    RegisterDescriptor REG_RETURN_;                     // FIXME[Robb P Matzke 2016-10-11]: see source
    Settings settings_;
    FunctionSummaries functionSummaries_;
    Partitioner2::CfgVertexMap vmap_;                   // relates CFG vertices to path vertices
    Partitioner2::ControlFlowGraph paths_;              // all possible paths, feasible or otherwise
    Partitioner2::CfgConstVertexSet pathsBeginVertices_;// vertices of paths_ where searching starts
    Partitioner2::CfgConstVertexSet pathsEndVertices_;  // vertices of paths_ where searching stops
    Partitioner2::CfgConstEdgeSet cfgAvoidEdges_;       // CFG edges to avoid
    Partitioner2::CfgConstVertexSet cfgEndAvoidVertices_;// CFG end-of-path and other avoidance vertices
    FunctionSummarizer::Ptr functionSummarizer_;         // user-defined function for handling function summaries


    //                                  Construction, destruction
public:
    FeasiblePath()
        : registers_(NULL) {}

    virtual ~FeasiblePath() {}
        
    void reset() {
        partitioner_ = NULL;
        registers_ = NULL;
        REG_PATH = REG_RETURN_ = RegisterDescriptor();
        functionSummaries_.clear();
        vmap_.clear();
        paths_.clear();
        pathsBeginVertices_.clear();
        pathsEndVertices_.clear();
        cfgAvoidEdges_.clear();
        cfgEndAvoidVertices_.clear();
    }

    static void initDiagnostics();


    //                                  Settings affecting behavior
public:
    const Settings& settings() const { return settings_; }
    Settings& settings() { return settings_; }
    void settings(const Settings &s) { settings_ = s; }
    static Sawyer::CommandLine::SwitchGroup commandLineSwitches(Settings &settings);


    //                                  Overridable processing functions
public:
    virtual InstructionSemantics2::BaseSemantics::DispatcherPtr
    buildVirtualCpu(const Partitioner2::Partitioner&, PathProcessor*);

    virtual void
    setInitialState(const InstructionSemantics2::BaseSemantics::DispatcherPtr &cpu,
                    const Partitioner2::ControlFlowGraph::ConstVertexIterator &pathsBeginVertex);

    virtual void
    processBasicBlock(const Partitioner2::BasicBlock::Ptr &bblock,
                      const InstructionSemantics2::BaseSemantics::DispatcherPtr &cpu, size_t pathInsnIndex);

    virtual void
    processIndeterminateBlock(const Partitioner2::ControlFlowGraph::ConstVertexIterator &vertex,
                              const InstructionSemantics2::BaseSemantics::DispatcherPtr &cpu,
                              size_t pathInsnIndex);

    virtual void
    processFunctionSummary(const Partitioner2::ControlFlowGraph::ConstVertexIterator &pathsVertex,
                           const InstructionSemantics2::BaseSemantics::DispatcherPtr &cpu,
                           size_t pathInsnIndex);

    virtual void
    processVertex(const InstructionSemantics2::BaseSemantics::DispatcherPtr &cpu,
                  const Partitioner2::ControlFlowGraph::ConstVertexIterator &pathsVertex,
                  size_t &pathInsnIndex /*in,out*/);

    virtual bool
    shouldSummarizeCall(const Partitioner2::ControlFlowGraph::ConstVertexIterator &pathVertex,
                        const Partitioner2::ControlFlowGraph &cfg,
                        const Partitioner2::ControlFlowGraph::ConstVertexIterator &cfgCallTarget);

    virtual bool
    shouldInline(const Partitioner2::CfgPath &path, const Partitioner2::ControlFlowGraph::ConstVertexIterator &cfgCallTarget);

    FunctionSummarizer::Ptr functionSummarizer() const { return functionSummarizer_; }
    void functionSummarizer(const FunctionSummarizer::Ptr &f) { functionSummarizer_ = f; }
    //                                  Utilities
public:
    Partitioner2::ControlFlowGraph::ConstVertexIterator
    pathToCfg(const Partitioner2::ControlFlowGraph::ConstVertexIterator &pathVertex) const;

    Partitioner2::CfgConstVertexSet
    cfgToPaths(const Partitioner2::CfgConstVertexSet&) const;

    bool pathEndsWithFunctionCall(const Partitioner2::CfgPath&) const;

    bool isFunctionCall(const Partitioner2::ControlFlowGraph::ConstVertexIterator&) const;

    void printPathVertex(std::ostream &out, const Partitioner2::ControlFlowGraph::Vertex &pathVertex,
                         size_t &insnIdx /*in,out*/) const;

    void printPath(std::ostream &out, const Partitioner2::CfgPath&) const;

    virtual boost::tribool
    isPathFeasible(const Partitioner2::CfgPath &path, const SmtSolverPtr&,
                   std::vector<SymbolicExpr::Ptr> postConditions, const SymbolicExprParser::RegisterSubstituter::Ptr&,
                   PathProcessor *pathProcessor, std::vector<SymbolicExpr::Ptr> &pathConditions /*in,out*/,
                   InstructionSemantics2::BaseSemantics::DispatcherPtr &cpu /*out*/);

    
    //                                  Functions for describing the search space
public:

    void
    setSearchBoundary(const Partitioner2::Partitioner &partitioner,
                      const Partitioner2::CfgConstVertexSet &cfgBeginVertices,
                      const Partitioner2::CfgConstVertexSet &cfgEndVertices,
                      const Partitioner2::CfgConstVertexSet &cfgAvoidVertices = Partitioner2::CfgConstVertexSet(),
                      const Partitioner2::CfgConstEdgeSet &cfgAvoidEdges = Partitioner2::CfgConstEdgeSet());
    void
    setSearchBoundary(const Partitioner2::Partitioner &partitioner,
                      const Partitioner2::ControlFlowGraph::ConstVertexIterator &cfgBeginVertex,
                      const Partitioner2::ControlFlowGraph::ConstVertexIterator &cfgEndVertex,
                      const Partitioner2::CfgConstVertexSet &cfgAvoidVertices = Partitioner2::CfgConstVertexSet(),
                      const Partitioner2::CfgConstEdgeSet &cfgAvoidEdges = Partitioner2::CfgConstEdgeSet());
    //                                  Functions for searching for paths
public:
    void depthFirstSearch(PathProcessor &pathProcessor);


    //                                  Functions for getting the results
public:
    const Partitioner2::Partitioner& partitioner() const;
    
    const FunctionSummaries& functionSummaries() const {
        return functionSummaries_;
    }

    const FunctionSummary& functionSummary(rose_addr_t entryVa) const;

    const VarDetail& varDetail(const InstructionSemantics2::BaseSemantics::StatePtr &state, const std::string &varName) const;

    const VarDetails& varDetails(const InstructionSemantics2::BaseSemantics::StatePtr &state) const;


    //                                  Private supporting functions
private:
    static rose_addr_t virtualAddress(const Partitioner2::ControlFlowGraph::ConstVertexIterator &vertex);

    void insertCallSummary(const Partitioner2::ControlFlowGraph::ConstVertexIterator &pathsCallSite,
                           const Partitioner2::ControlFlowGraph &cfg,
                           const Partitioner2::ControlFlowGraph::ConstEdgeIterator &cfgCallEdge);

    boost::filesystem::path emitPathGraph(size_t callId, size_t graphId);  // emit paths graph to "rose-debug" directory
};

} // namespace
} // namespace

#endif