Neural Machine Translation Inspired Binary Code Similarity Comparison beyond Function Pairs

Abstract

Binary code analysis allows analyzing binary code without having access to the corresponding source code. A binary, after disassembly, is expressed in an assembly language. This inspires us to approach binary analysis by leveraging ideas and techniques from Natural Language Processing (NLP), a fruitful area focused on processing text of various natural languages. We notice that binary code analysis and NLP share many analogical topics, such as semantics extraction, classification, and code/text comparison. This work thus borrows ideas from NLP to address two important code similarity comparison problems. (I) Given a pair of basic blocks of different instruction set architectures (ISAs), determining whether their semantics is similar; and (II) given a piece of code of interest, determining if it is contained in another piece of code of a different ISA. The solutions to these two problems have many applications, such as cross-architecture vulnerability discovery and code plagiarism detection. Despite the evident importance of Problem I, existing solutions are either inefficient or imprecise. Inspired by Neural Machine Translation (NMT), which is a new approach that tackles text across natural languages very well, we regard instructions as words and basic blocks as sentences, and propose a novel cross-(assembly)-lingual deep learning approach to solving Problem I, attaining high efficiency and precision. Many solutions have been proposed to determine whether two pieces of code, e.g., functions, are equivalent (called the equivalence problem), which is different from Problem II (called the containment problem). Resolving the cross-architecture code containment problem is a new and more challenging endeavor. Employing our technique for cross-architecture basic-block comparison, we propose the first solution to Problem II. We implement a prototype system INNEREYE and perform a comprehensive evaluation. A comparison between our approach and existing approaches to Problem I shows that our system outperforms them in terms of accuracy, efficiency and scalability. The case studies applying the system demonstrate that our solution to Problem II is effective. Moreover, this research showcases how to apply ideas and techniques from NLP to large-scale binary code analysis.

1. Introduction

Binary code analysis allows one to analyze binary code without access to the corresponding source code. It is widely used for vulnerability discovery, code clone detection, user-side crash analysis, etc. Today, binary code analysis has become more important than ever. Gartner forecasts that 8.4 billion IoT devices will be in use worldwide in 2017, up 31 percent from 2016, and will reach 20.4 billion by 2020 [22]. Due to code reuse and sharing, a single vulnerability at source code level may spread across hundreds or more devices that have diverse hardware architectures and software platforms [52]. However, it is difficult, often unlikely, to obtain the source code from the many IoT device companies. Thus, binary code analysis becomes the only feasible approach.

Given a code component that is known to contain some vulnerability and a large number of programs that are compiled for different ISAs, by finding programs that contain similar code components, more instances of the vulnerability can be found. Thus, cross-architecture binary code analysis draws great interests [52], [18], [19], [65].

Our insight. A binary, after disassembly, is represented in some assembly language. This inspires us to approach binary code analysis by learning from Natural Language Processing (NLP), a fruitful area focused on processing natural language corpora effectively and efficiently. Interestingly, the two seemingly remote areas—binary code analysis and NLP—actually share plenty of analogical topics, such as semantics extraction from code/text, summarization of paragraphs/functions, classification of code/articles, and code/text similarity comparison. We thus propose to adapt the ideas, methods, and techniques used in NLP to resolving binary code analysis problems. As a showcase, we use this idea to perform cross-architecture binary code similarity comparison.

Previous work [52], [18], [19], [65] essentially resolves the code equivalence problem at the function level: given a pair of functions, it is to determine whether they are equivalent. We consider a different problem: given a code component, which can be part of a function (e.g., the code in a web server that parses the URL) or a set of functions (e.g., an implementation of a crypto algorithm), to determine whether it is contained in a program. Thus, it is a code containment problem. The problem has been emphasized by previous work [27], [37], [45], [66], [60], [61], [38], but the proposed solutions can only work for code of the same ISA. Resolving the cross-architecture code containment problem is a new and important endeavor. A solution to this problem is critical for tasks such as fine-grained code plagiarism detection, thorough vulnerability search, and virus detection. For example, a code plagiarist may steal part of a function or a bunch of functions, and insert the stolen code into other code; that is, the stolen code is not necessarily a function. Code plagiarism detection based on searching for equivalent functions is too limited to handle such cases.