Balakrishnan and Reps Receive Best Paper Award

Posted 02 April 2004

The paper Analyzing Memory Accesses in x86 Executables by Gogul Balakrishnan and Thomas Reps received the European Association for Programming Languages and Systems (EAPLS) best paper award at the 2004 European Joint Conferences on Theory and Practice of Software (ETAPS).

There is a growing need for binary analysis tools that can be used to understand viruses, worms, etc. Analyzing binaries in the presence of memory operations is difficult because it is not straightforward to disambiguate memory references. Existing tools either perform an unsafe analysis of memory operations or treat memory operations conservatively. In the context of data-dependence analysis this kind of treatment means that the tool shows a lot of spurious data dependences or misses data dependences. The paper presents an abstract interpretation based algorithm, called "Value-Set Analysis", to automatically analyze and understand the memory operations in a binary program. The results of the analysis are safe and at the same time the analysis tries to be as accurate as possible.

This paper further illustrates how Value-Set Analysis creates an Intermediate Representation for binary programs that is akin to the one generated by the back-end of a compiler. The IR is the basis for a tool called CodeSurfer/x86. CodeSurfer/x86 builds a System Dependence Graph (SDG) for the given binary program based on IR and also provides a GUI to browse through the binary program, perform code slices, follow data/control dependences, etc. It also provides a programmatic access to the SDG and other data structure to enable further analysis.

The paper is available online: [Abstract] [pdf] [ps]

<< Back to index

This page updated October 18, 2005.