Graph-based divide-and-conquer techniques for binary diffing

Abstract

In this thesis, we propose a solution to the binary diffing problem aimed at improving runtime efficiency and precision of the results generated. Our approach leverages program partitioning and applies binary diffing algorithms using a divide-and-conquer strategy, implemented in an extensible binary diffing pipeline. Specifically, we introduce three novel program partitioning techniques; (i) a method combining consensus-based Louvain community detection on programs’ Function Call Graphs (FCGs), followed by further splitting of communities into hash buckets using Locality Sensitive Hashing (LSH), (ii) an approximate recovery of a program’s object-file structure (referred to as the REcover technique), and (iii) a modular decomposition of program FCGs into MD-trees, which are unique up to isomorphism for a given graph. Components resulting from these partitionings are first compared at a coarse level, followed by a finer-grained comparison of the functions they contain. Furthermore, we explore efficient features for abstractly representing function characteristics, as well as clusters of functions generated by the above partitionings, using feature vector aggregation. Binary lifting to the VEX Intermediate Representation (IR) is employed to abstract away Instruction Set Architecture (ISA) details. Using these techniques, we develop REveal, a binary diffing framework that implements generic algorithms for performing divide-and-conquer binary diffing, independently of the specific partitioning method used. We demonstrate the efficiency and applicability of the proposed methodologies through a series of experiments against the BinKit dataset, comparing our results with those ofBinDiff and Diaphora, the state-of-the-art tools for binary diffing. Last but not least, we provide open-source implementations of all software in our pipeline for further evaluation by the reverse engineering community.

Στην παρούσα διδακτορική διατριβή προτείνουμε μια λύση στο πρόβλημα του binary diffing, με στόχο τη βελτίωση τόσο της αποδοτικότητας κατά την εκτέλεση, όσο και της ακρίβειας των παραγόμενων αποτελεσμάτων. Η προσέγγισή μας αξιοποιεί την διαμέριση προγραμμάτων (program partitioning) σε επιμέρους κομμάτια και εφαρμόζει αλγορίθμους binary diffing χρησιμοποιώντας στρατηγική διαίρει-και-βασίλευε (divide-and-conquer), υλοποιημένη σε μία επεκτάσιμη ροή εργασιών. Συγκεκριμένα, εισάγουμε τρεις νέες τεχνικές διαμέρισης προγραμμάτων: (i) μια μέθοδο που συνδυάζει συναινετική ανίχνευση κοινοτήτων με χρήση του αλγορίθμου Louvain στα Function Call Graphs (FCGs) των προγραμμάτων, ακολουθούμενη από περαιτέρω διαχωρισμό των κοινοτήτων σε hash buckets χρησιμοποιώντας Locality Sensitive Hashing (LSH), (ii) μια προσεγγιστική ανακατασκευή της δομής ενός προγράμματος στα επιμέρους αρχεία-αντικείμενα (object-files) που το απαρτίζουν (γνωστή ως τεχνική REcover), και (iii) μια τεχνική βασισμένη στο modular decomposition των FCGs σε MD-trees, τα οποία είναι μοναδικά, με ακρίβεια ισομορφισμού, για δοσμένο γράφο. Τα στοιχεία που προκύπτουν από αυτές τις διαμερίσεις συγκρίνονται πρώτα σε υψηλό επίπεδο, ακολουθούμενα από λεπτομερέστερη σύγκριση των συναρτήσεων που περιέχουν. Επιπλέον, διερευνούμε αποδοτικά χαρακτηριστικά με σκοπό την αφηρημένη αναπαράσταση των ιδιοτήτων των συναρτήσεων προγραμμάτων, καθώς και των συστάδων (clusters) συναρτήσεων που προκύπτουν από τις παραπάνω διαμερίσεις, χρησιμοποιώντας συσσωμάτωση (aggregation) των διανυσμάτων χαρακτηριστικών τους, ενώ χρήση τεχνικών binary lifting στο VEX Intermediate Representation (IR) χρησιμοποιείται για την παράβλεψη λεπτομερειών μεταξύ διαφορετικών Instruction Set Architectures (ISA). Με βάση τα παραπάνω, αναπτύσσουμε το REveal, ένα εργαλείο που υλοποιεί γενικούς αλγορίθμους binary diffing με χρήση τεχνικών διαίρει-και-βασίλευε, ανεξαρτήτως της συγκεκριμένης μεθόδου διαμέρισης που χρησιμοποιείται. Αποδεικνύουμε την αποδοτικότητα και την εφαρμοσιμότητα των προτεινόμενων τεχνικών μέσω μιας σειράς πειραμάτων στο σύνολο δεδομένων του BinKit, συγκρίνοντας τα αποτελέσματα μας με αυτά των BinDiff και Diaphora, δύο καθιερωμένων εργαλείων binary diffing. Τέλος, παρέχουμε υλοποιήσεις ανοιχτού κώδικα όλων των εργαλείων της ροής εργασιών μας για περαιτέρω αξιολόγηση από την επιστημονική κοινότητα.