Effective and Accurate Binary Clone Detection
Hayk K. Aslanyan · Mathematical Problems of Computer Science · 2017
Software developers usually copy and paste a particular piece of code as they prefer to use a pre-written or a partial solution as a basis for solving their problem. However, it can lead to various errors, as well as increase the size of the source and binary code. Finding similar parts of code (clones) in binary code becomes more applicable when the source code is not available. Additionally, a compiler can copy some parts of code during various transformations and create code clones, which do not exist in the source code. Detection of binary code clones is used for malware analysis, finding semantic errors, detecting copyright violation, etc. This article discusses the existing methods of binary code clones detection and introduces a new method for binary clone detection. It consists of three main stages. The first stage is based on Binnavi platform [1] and generates program dependence graphs for each binary function. Graphs are generated based on REIL [2] (Reverse Engineering Intermediate Language) platform-independent language. REIL representation is supported for several architectures (x86, x86-64, ARM, MIPS, PPC), thus ensuring the independence of the tool from the target architecture. The second stage detects clones based on previously created graphs. A polynomial heuristic algorithm is suggested for finding the maximum common subgraph of two program dependence graphs. At the third stage, the obtained clones are visualized for manual analysis.