10

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

2 Answers 2

6

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.

3
  • Thank you for your answer. I actually have read some papers about VSA. Basically, is it the right way to use VSA..? It is doable to leverage VSA on analyzing the "candidacy of indirect control flow transfer", which is a extremely critical issue in reverse engineering based static analysis. However, IMHO, I can not figure the relation between VSA and what I proposed.. Jul 31, 2014 at 21:30
  • anyway, CodeSurfer/x86 is not open source, and I find it really hard to even somehow re-implement a toy version only targeting on the issue I presented... Jul 31, 2014 at 21:31
  • It's not the only option of course. A simpler option, which is also quite successful, is simple recursive disassembly augmented with heuristics. This is the approach ida takes, to good practical effect. As for open source, I believe vine implements vsa and bap has at least a partial implementation per this blog post in 2012 edmcman.bitbucket.org/blog/2012/07/23/cfg-recovery-in-bap
    – broadway
    Jul 31, 2014 at 21:54
3

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.