Abstract

In this study we present a novel representation for binary programs, which captures semantic similarity and structural properties.  Our representation is composed in a bottom-up approach and enables new methods of analysis.  We show that we can perform search and retrieval of binary executable programs based on similarity of behavioral properties, with an adjustable level of feature resolution.  We begin by extracting data dependency graphs (DDG), which are representative of both program structure and operational semantics.  We then encode each program as a set of graph hashes representing isomorphic uniqueness, a method we have labeled DDG Fingerprinting.  Next, we use k-Nearest Neighbors to search in a metric space constructed from examples.  This approach allows us to perform a quantitative analysis of patterns of program operation. By evaluating similarity of behavior we are able to recognize patterns in novel malware with functionality not previously identified.  We present experimental results from search based on program semantics and structural properties in a dataset of binary executables with features extracted using our method of representation.  We show that the associated metric space allows an adjustable level of resolution. Resolution of the features may be decreased for breadth of search and retrieval, or as the search space is reduced, the resolution may be increased for accuracy and fine-grained analysis of malware behavior.

Statistics