Aristotle University Of Thessaloniki (AUTH)
Graph-based divide-and-conquer techniques for binary diffing
Abstract
dc:descriptionIn 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.
Degree
thesis:*- Grantor dc:publisher
- Aristotle University Of Thessaloniki (AUTH)
- Year dc:date
- 2026
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Karamitas, Chariton
- Καραμήτας, Χαρίτων
Subjects
dc:subject × 12- Σύγκριση Εκτελέσιμων Αρχείων
- Διαίρεση-Κατάκτηση
- Θεωρία γράφων
- Binary Diffing
- Divide-and-Conquer
- Graph theory
- Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
- Επιστήμες Μηχανικού και Τεχνολογία
- Υπολογιστές, Υλικό (hardware) και Αρχιτεκτονική
- Electrical Engineering, Electronic Engineering, Information Engineering
- Engineering and Technology
- Computer science, Hardware and Architecture
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/62338