How to do static analysis to identify pointer from concrete value in assembly?

Question

So basically I am writing some code to do analysis work on disassembled assembly code.

I am trapped in this issue for a while, here is an simple example of a disassembled asm code by objdump, basically all the address symbols have been translated into concrete value.

1. mov 0x8408080, %eax
2. ....
3. call *%eax

So basically for the above example, it is easy to determine that 0x8408080 used in line 1 is an address of code, and I know it is relatively easy to heuristically consider all the value falling into the range of .text section as a pointer.

However, how to use static analysis to automatically identify this issue? (I want to write a tool to analyze large amount of code as accurate as possible)

I know somehow I should use constant propagation to forwardly do the analysis, but basically as I am new to program analysis, I just don't know actually where to start..

Does anyone have experiences like this? Or is there any implemented tools I can look for help..?

Answer 1

Some decompilers (phoenix for example) use Value Set Analysis to recover the cfg.

Paper 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.

Answer 2

Basically, distinguish between values, addresses and instruction is the role of a type recovery system.

There is an excellent seminal paper from Alan Mycroft about a technique called type-based decompilation (ESOP'99) which might give you some ideas on how to do.

Another, more recent, paper describes the technique that is currently used in the Phoenix decompiler which is called: TIE: Principled Reverse Engineering of Types in Binary Programs (NDSS'11) written by people from CMU and that give an in-depth of the technique they use.

Apart from that, the reconstruction of the shape of the types (array, struct, etc.) can be done by using the DIVINE technique (VMCAI'07) by Reps and Balakrishnan. A more extensive journal paper (TOPLAS'10) has been also published by both authors that gather all their work about the topic.

Still, there are a lot of other works on this domain, but I believe the papers I cited above to be, more or less, the current trend in the 'type-recovery' domain.