1

Metasm is an assembly manipulation suite written in Ruby. It does provide a quite extensive API for disassembling and extracting a CFG representation from a binary program.

I would like to know what algorithm is used to extract the CFG. Is this usual linear sweep or recursive traversal, or is another algorithm?

Improve this question
2
  • 2
    Have you looked at Metasm's source code? – Jason Geffner Jun 20 '13 at 13:28
  • This is what I am currently doing (but my Ruby is really not good). There is also a word about it in the README file but I would like to be sure how it is really done. – perror Jun 20 '13 at 15:31
3

The strategy used by Metasm is referenced in the peer-reviewed literature on their website. Look at the article published in the Journal of Computer Virology in 2008, in section 3.1. To quote them,

Standard disassembly.

Out of the box, the disassembly engine in Metasm works this way :

  1. Disassemble the binary instruction at the instruction pointer.
  2. Analyse the effects of the instruction.
  3. Update the instruction pointer.

That sounds more like recursive traversal to me, and less like linear sweep. The engine disassembles the next instruction based upon the effects of the previous instruction, which would allow the disassembly engine to follow branches in the logic, etc.

Also, I have not examined their code in-depth, but in metasm/disassemble.rb it looks like they maintain some sort of autoanalysis queue for addresses to continue analyzing. Look for functions referencing backtracing - it definitely seems like recursive traversal.

Improve this answer
3
  • 1
    Hmmm, this is obviously NOT a recursive traversal. It looks more to a symbolic execution by constraints solving. But, this answer my question. Moreover, I didn't know this paper, so thanks a lot for your answer! – perror Jun 21 '13 at 14:51
  • Is there a good place to read up on the difference? I'm not sure I understand the difference - are symbolic execution and recursive traversal mutually exclusive? – dingo_kinznerhook Jun 21 '13 at 15:00
  • 1
    Well, recursive traversal only track partially the semantics of call/ret instructions, and will perform linear sweep the rest of the time. Symbolic execution will require to grab the semantics of each instruction and apply it from an known initial state (ie the memory at the beginning of the process). So, recursive traversal is what I call a syntaxic-based disassembler and the symbolic execution is a semantics-based disassembler (because it requires to know the semantics of all instructions. – perror Jun 21 '13 at 15:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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