Back to search

Aristotle University Of Thessaloniki (AUTH)

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

Abstract

dc:description

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.

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

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/62338

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Karamitas, Chariton; Καραμήτας, Χαρίτων. Graph-based divide-and-conquer techniques for binary diffing. Aristotle University Of Thessaloniki (AUTH), 2026. http://hdl.handle.net/10442/hedi/62338