BinaryFunctionSimilarity.h

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

#include <BinaryMatrix.h>
#include <Partitioner2/Function.h>
#include <Progress.h>
#include <RoseException.h>
#include <Sawyer/Graph.h>
#include <Sawyer/Map.h>

#ifdef ROSE_HAVE_DLIB
    #include <dlib/optimization.h>
#endif

namespace Rose {
namespace BinaryAnalysis {

class FunctionSimilarity {
    // Public types and data members
public:
    /* Exceptions thrown by this analysis. */
    class Exception: public Rose::Exception {
    public:
        Exception(const std::string &what): Rose::Exception(what) {}
        ~Exception() throw () {}
    };

    enum CValKind {
        CARTESIAN_POINT,                                
        ORDERED_LIST                                    
    };
    typedef std::vector<double> CartesianPoint;         
    typedef std::vector<int> OrderedList;               
    // Collections of characteristic values
    typedef std::vector<CartesianPoint> PointCloud;     
    typedef std::vector<OrderedList> OrderedLists;      
    enum Statistic { AVERAGE, MEDIAN, MAXIMUM };

    typedef size_t CategoryId;                          
    static const CategoryId NO_CATEGORY = -1;           
    typedef std::pair<Partitioner2::Function::Ptr, double /*distance*/> FunctionDistancePair;

    typedef std::pair<Partitioner2::Function::Ptr, Partitioner2::Function::Ptr> FunctionPair;

    static Sawyer::Message::Facility mlog;

    typedef Matrix<double> DistanceMatrix;

    // Private types and data members
private:
    // Declaration for metric categories.
    struct Category {
        std::string name;                               // name of category (or metric for singleton categories)
        CValKind kind;                                  // kind of characteristic values stored here
        double weight;                                  // weight when combining category distances
        size_t dimensionality;                          // dimensionality of Cartesian points; 0 => unknown
        double dflt;                                    // default value when one of the functions is null

        explicit Category(const std::string &name, CValKind kind, double weight = 1.0)
            : name(name), kind(kind), weight(weight), dimensionality(0), dflt(1.0) {}
    };

    std::vector<Category> categories_;
    Sawyer::Container::Map<std::string /*category_name*/, size_t /* categories index */> categoryNames_;

    // Characteristic values for some function + category pair.  Only one of these members is populated with data.
    struct CharacteristicValues {
        PointCloud pointCloud;
        OrderedLists orderedLists;
    };

    // Info about each function
    struct FunctionInfo {
        std::vector<CharacteristicValues> categories;   // characteristic values orgnized by CategoryId
        FunctionInfo(): categories() {}                 // LLVM's clang++ 3.5 and 3.7 don't generate this for const objs
    };

    // Info about all functions
    typedef Sawyer::Container::Map<Partitioner2::Function::Ptr, FunctionInfo> Functions;
    Functions functions_;

    // How to combine category distances to obtain a function distance
    Statistic categoryAccumulatorType_;

    Progress::Ptr progress_;

    // Constructors
public:
    FunctionSimilarity()
        : categoryAccumulatorType_(AVERAGE), progress_(Progress::instance()) {}

    void clear() {
        categories_.clear();
        categoryNames_.clear();
        functions_.clear();
        categoryAccumulatorType_ = AVERAGE;
    }
    
    // Properties
public:
    Statistic categoryAccumulatorType() const { return categoryAccumulatorType_; }
    void categoryAccumulatorType(Statistic s) { categoryAccumulatorType_ = s; }
    Rose::Progress::Ptr progress() const { return progress_; }

    // Category declarations
public:
    CategoryId declarePointCategory(const std::string &name, size_t dimensionality, bool allowExisting = true);

    CategoryId declareListCategory(const std::string &name, bool allowExisting = true);

    size_t nCategories() const { return categories_.size(); }

    CategoryId findCategory(const std::string &name) const { return categoryNames_.getOrElse(name, NO_CATEGORY); }
    CValKind categoryKind(CategoryId) const;

    size_t categoryDimensionality(CategoryId) const;

    double categoryWeight(CategoryId) const;
    void categoryWeight(CategoryId, double);
    // Predefined metrics
public:
    CategoryId declareCfgConnectivity(const std::string &categoryName);
    void measureCfgConnectivity(CategoryId, const Partitioner2::Partitioner&, const Partitioner2::Function::Ptr&,
                                size_t maxPoints = UNLIMITED);
    CategoryId declareCallGraphConnectivity(const std::string &categoryName);
    void measureCallGraphConnectivity(CategoryId, const Partitioner2::Partitioner&, const Partitioner2::Function::Ptr&);
    CategoryId declareMnemonicStream(const std::string &categoryName);
    void measureMnemonicStream(CategoryId, const Partitioner2::Partitioner&, const Partitioner2::Function::Ptr&);
    // Low level functions for manipulating characteristic values
public:

    void insertPoint(const Partitioner2::Function::Ptr&, CategoryId, const CartesianPoint&);

    void insertList(const Partitioner2::Function::Ptr&, CategoryId, const OrderedList&);

    size_t size(const Partitioner2::Function::Ptr&, CategoryId) const;

    const PointCloud& points(const Partitioner2::Function::Ptr&, CategoryId) const;

    const OrderedLists& lists(const Partitioner2::Function::Ptr&, CategoryId) const;


    // Comparison interface
public:
    double compare(const Partitioner2::Function::Ptr&, const Partitioner2::Function::Ptr&, double dflt = NAN) const;

    std::vector<FunctionDistancePair> compareOneToAll(const Partitioner2::Function::Ptr&) const;

    template<class FunctionIterator>
    std::vector<FunctionDistancePair>
    compareOneToMany(const Partitioner2::Function::Ptr &needle,
                     const boost::iterator_range<FunctionIterator> &haystack) const {
        std::vector<Partitioner2::Function::Ptr> others;
        BOOST_FOREACH (const Partitioner2::Function::Ptr &other, haystack)
            others.push_back(other);
        return compareOneToMany(needle, others);
    }

    template<class FunctionIterator>
    std::vector<FunctionDistancePair>
    compareOneToMany(const Partitioner2::Function::Ptr &needle,
                     const FunctionIterator &begin, const FunctionIterator &end) const {
        return compareOneToMany(needle, boost::iterator_range<FunctionIterator>(begin, end));
    }

    std::vector<FunctionDistancePair>
    compareOneToMany(const Partitioner2::Function::Ptr &needle,
                     const std::vector<Partitioner2::Function::Ptr> &haystack) const;
    std::vector<std::vector<double> > compareManyToMany(const std::vector<Partitioner2::Function::Ptr>&,
                                                        const std::vector<Partitioner2::Function::Ptr>&) const;

    DistanceMatrix compareManyToManyMatrix(std::vector<Partitioner2::Function::Ptr>,
                                           std::vector<Partitioner2::Function::Ptr>) const;

    std::vector<FunctionPair> findMinimumCostMapping(const std::vector<Partitioner2::Function::Ptr> &list1,
                                                     const std::vector<Partitioner2::Function::Ptr> &list2) const;

    std::vector<double> computeDistances(const std::vector<Partitioner2::Function::Ptr> &list1,
                                         const std::vector<Partitioner2::Function::Ptr> &list2,
                                         size_t nThreads) const;

    // Sorting
public:
    static bool sortByIncreasingDistance(const FunctionDistancePair &a, const FunctionDistancePair &b) {
        return a.second < b.second;
    }

    static bool sortByDecreasingDistance(const FunctionDistancePair &a, const FunctionDistancePair &b) {
        return b.second < a.second;
    }

    static bool sortByAddress(const FunctionDistancePair &a, const FunctionDistancePair &b) {
        if (a.first == NULL || b.first == NULL)
            return a.first == NULL && b.first != NULL;
        return a.first->address() < b.first->address();
    }
    
    // Printing and debugging
public:
    static void initDiagnostics();

    void printCharacteristicValues(std::ostream&) const;

    // Utility functions
public:
    static double cartesianDistance(const FunctionSimilarity::CartesianPoint&, const FunctionSimilarity::CartesianPoint&);

    static std::vector<size_t> findMinimumAssignment(const DistanceMatrix&);

    static double totalAssignmentCost(const DistanceMatrix&, const std::vector<size_t> &assignment);

    static double maximumDistance(const DistanceMatrix&);

    static double averageDistance(const DistanceMatrix&);

    static double medianDistance(const DistanceMatrix&);

    // Internal functions
private:
    static double comparePointClouds(const PointCloud&, const PointCloud&);
    static double compareOrderedLists(const OrderedLists&, const OrderedLists&);
};

std::ostream& operator<<(std::ostream&, const FunctionSimilarity&);

} // namespace
} // namespace

#endif
#endif