Hierarchical binary diffing with inductive code representation learning with graph sampling-and-aggregate

Binary program diffing, or simply binary diffing, is a type of program analysis technique that quantifies the similarity between two binary programs to derive their differences. In particular, binary diffing is an essential technique for uncovering vulnerabilities and potential attack vectors in industrial control systems, where patch deployment is complicated by closed and restricted environments. Studies on binary diffing can be broadly categorized into dynamic analysis-based, static analysis-based, and neural network-based approaches. Each category of existing studies has its shortcomings, including limited coverage, low accuracy, and issues with on-demand learning. In this paper, we propose the binary diffing with sampling-and-aggregate, a hierarchical binary diffing model that generates inductive code representations based on graph sampling-and-aggregate. Our model sequentially produces instruction-level embedding, block-level embedding, and function-level embedding from the inter-procedural control flow graph of a given program, and then performs hierarchical code diffing based on these embeddings. We formally define the detailed models and present the algorithm of hierarchical binary diffing. Additionally, we conduct a thorough analysis of this algorithm, deriving several advantages. We implemented a prototype and evaluated it on a large-scale dataset in a cross-version, cross-optimization, and obfuscation settings. Our prototype showed F1-scores up to 0.96 and 0.968 in cross-version setting for function and basic block diffing, respectively. Also, our method demonstrated its robustness over several binary obfuscations. In conclusion, our proposal, which generates basic block- and function-level embedding by considering the control flow, has solid advantages on binary diffing and shows the robustness on the binary tampering. • We formulate sequential generation of instruction- to function-level embeddings for a binary program. • We use hierarchical embeddings to compute function-to-block similarity and perform code diffing. • We implement the DiffSAGE prototype and evaluate it on a large binary dataset, showing it outforms state-of-the-art.