Research indexJournal article
Graph-based Divide-and-Conquer Techniques for Binary Diffing
Karamitas
Aristotle University of Thessaloniki1 Jan 2026Open access
NobleIDark:/48914/w1/20261105/BE61A9ECDOI10.26262/heal.auth.ir.375650
Graph-based Divide-and-Conquer Techniques for Binary Diffing
Karamitas · Aristotle University of Thessaloniki · 2026
NobleIDark:/48914/w1/20261105/BE61A9ECDOI10.26262/heal.auth.ir.375650
Free to read at the publisher
You can read the abstract here, or the full text at the publisher.
Abstract
Στην παρούσα διδακτορική διατριβή προτείνουμε μια λύση στο πρόβλημα του 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. Τέλος, παρέχουμε υλοποιήσεις ανοιχτού κώδικα όλων των εργαλείων της ροής εργασιών μας για περαιτέρω αξιολόγηση από την επιστημονική κοινότητα.