Paper Appeared in 13th CC
Posted 12 March 2004
The paper Analyzing Memory Accesses in x86 Executables by
Gogul Balakrishnan and Thomas Reps appeared in the 13th
International Conference on Compiler Construction (CC) held in
Barcelona, Spain on April 1 and 2, 2004. Gogul presented the
paper.
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.
