Towards Accurate Binary Correspondence Using Runtime-Observed Values
Ulf Kargén, Nahid Shahmehri · 2016
Establishing binary correspondence is the process of finding corresponding pairs of program elements, e.g., functions or individual instructions, between two semantically equivalent (or nearly-equivalent) but syntactically different program binaries. The binary-correspondence problem has applications in many fields, e.g., plagiarism and clone detection, reverse engineering, and security, and has therefore received significant attention both in industry and academia. Most binary-correspondence methods used in practice today are based on static analysis of the control structure in binaries. Unfortunately, such methods are often highly sensitive to syntactic differences between binaries, and discrepancies in the control structure due to, for example, using different compilers or optimization levels often severely reduce their accuracy. Several recent works have therefore proposed using dynamic analysis and comparing runtime-observed results of computations to establish binary correspondence. In this paper, we study the discriminative power of runtime-values for matching instructions in binaries, and propose several ways to increase the accuracy of value-based analyses. By utilizing techniques from the field of information retrieval combined with dynamic data-flow analysis, we improve matching accuracy by up to 55% in our experiments.