discovRE: Efficient Cross-Architecture Identification of Bugs in Binary Code

No ratings

Presented at NDSS 2016 by

The identification of security-critical vulnerabilities is a key for protecting computer systems. Being able to perform this process at the binary level is very important given that many software projects are closed-source. Even if the source code is available, compilation may create a mismatch between the source code and the binary code that is executed by the processor, causing analyses that are performed on source code to fail to detect certain bugs and vulnerabilities. Existing approaches to find bugs in binary code 1) use dynamic analysis which is difficult for firmware; 2) handle a single architecture; or 3) use semantic similarity, which is very slow when analyzing large code bases. In this paper, we present a new approach to efficiently search for bugs in binary code. Starting with a binary function that contains a bug, we identify similar functions in other binaries across different compilers, optimization levels, operating systems, and CPU architectures. The main idea is to compute similarity between functions based on the structure of the corresponding control flow graphs. To minimize this costly computation, we employ an efficient pre-filter based on numeric features to quickly identify a small set of candidate functions. This allows us to efficiently search for similar functions in large code bases. We have designed and implemented a prototype of our approach, called discovRE, that supports four instruction set architectures (x86, x64, ARM, MIPS). We show that discovRE is four orders of magnitude faster than the state-of-the-art academic approach for cross-architecture bug search in binaries. We also show that we can identify Heartbleed and POODLE vulnerabilities in an Android system image that contains over 120,000 native ARM functions in less than 80 milliseconds.