Reverse Engineering Stack Exchange is a question and answer site for researchers and developers who explore the principles of a system through analysis of its structure, function, and operation. It only takes a minute to sign up.
Sign up to join this community
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?
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 :
- Disassemble the binary instruction at the instruction pointer.
- Analyse the effects of the instruction.
- 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.
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
