Papers

Analyzing Memory Accesses in x86 Executables


Gogul Balakrishnan and Thomas W. Reps


Abstract:

This paper concerns static-analysis algorithms for analyzing binary executables. The aim of the work is to recover intermediate representations (IRs) that are similar to those that can be created for a program written in a high-level language. Our goal is to perform this task for programs such as viruses, worms, and mobile code. For such programs, symbol-table and debugging information is either entirely absent, or cannot be relied upon if present; hence, the analysis described in the paper makes no use of symbol-table/debugging information.

The main analysis discussed in the paper, called value-set analysis, tracks address-valued and integer-valued quantities simultaneously. It is related to pointer-analysis algorithms that have been developed for programs written in high-level languages, which determine an over-approximation of the set of variables whose addresses each pointer variable can hold. At the same time, value-set analysis is similar to range analysis and other numeric static-analysis algorithms that over-approximate the integer values that each variable can hold.

The techniques described in the paper have been implemented as part of CodeSurfer/x86, a prototype tool for browsing (``surfing''), inspecting, and analyzing x86 executables.

Paper available as: [PDF] [Official Version]