6

I am working on some x86 (32/64 bits) ELF binary code. These binaries are compiled from C and C++ program code and I am trying to detect loops inside the binaries.

I am newbie to this area, and I am wondering, what is the standard way to identify a loop in binary code?

I prefer to use some static methods to detect the loop instances, as I am not able to generate well-performing dynamic test cases.

  • 1
    Why do you think there's a standard way? Optimizations can make quite a mess... – deviantfan Feb 26 '16 at 1:23
  • @deviantfan, thank you. I agree with that. I am just wondering when people want to detect loop, what they will do? any references? – lllllllllllll Feb 26 '16 at 1:29
  • 2
    If you can get your hands on the book Practical Malware Analysis, I suggest you to read "Chapter 6. Recognizing C code constructs in assembly". There you have explained all the major code constructs of C language and how to identify them while reversing. – ubnix Feb 26 '16 at 8:57
  • 1
    I am little bit surprise about unconstructive comments here. Optimizations can make mess, obviously, but they cannot hide structures of loops as well as recursive calls. – Ta Thanh Dinh Feb 26 '16 at 11:03
  • 1
    @TaThanhDinh If an optimization unrolls a loop so that it doesn't exist at all, there's no more loop to detect. – Joshua Taylor May 23 '16 at 21:12
7

The classic, compiler theoretic answer to this question is to build a control flow graph and then do a graph analysis to identify natural loops. I believe algorithms for this can be found in the Dragon Book, and a summary is given in these slides:

http://www.cs.cmu.edu/afs/cs/academic/class/15745-s03/public/lectures/L7_handouts.pdf

You can also see how LLVM implements its loop detection:

http://llvm.org/docs/doxygen/html/LoopInfo_8h_source.html

The search terms you want to find more information are things like "natural loop" and "back edge".

| improve this answer | |
2

You might find this question about finding recursive function helpful, there are very nice answers for it. Under the binary code level, IMHO, there is only little difference about detecting loop (i.e. some jmp to the same target) and recursive call (i.e. some call to the same target).

| improve this answer | |
2

I don't think there's a standard way, but one approach might be to use something like Johnson's algorithm to detect cycles in the function's directed graph.

You can find an implementation of this in libraries like NetworkX simple_cycles.

| improve this answer | |
1

Detecting loops from binary code isn't easily done. There are many algorithms based on multiple graph data structures (CFG, SSA form, DDG, ...). I have provided a set of additional helpful documents link1, link2, link3. You can check MAQAO's implementation of an SSA based loop detector. Also, I would recommend you checking DynInst's code and documentation link4.

Now, you can implement an assembly code analyzer that can detect basic blocks/loops by following branches.

  1. Disassemble your binary and go thhrough instructions.
  2. If a conditional jump is encountered (Jxx pattern), check whether it jumps above or below.
  3. If the jump points above, check the distance (Delta(BRANCH_ADDRESS, BRANCH_TARGET_ADDRESS)), if the distance isn't too large (you'll have to decide of a limit) then you can apply some analysis on the branch condition (check whether it contains a register which is displaced [increment/decrement]). The branch condition analysis could be a simple pattern matching :

       Example 1: 
                 TEST X,X
                 Jxx  X
    
       Example 2: 
                 CMP  X,X
                 Jxx  X
    
       Example 3: 
                 DEC X
                 Jnz X
    

If it all checks out, you got yourself a basic block which has a high probability of being a loop.

  1. If the jump points below, its probability of being part of a loop control structure is less likely. You can therefore ignore it and move on to the next instruction.

If you need more hairy details, I'll be glad to provide more ;)

| improve this answer | |
  • Thank you yaspr. I really appreciate your detailed information! – lllllllllllll Nov 30 '16 at 19:02
  • It's my pleasure. – yaspr Nov 30 '16 at 19:53

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.