What is the "standard" approach to find loop in binary code?

Question

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.

Answer 1

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

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

Answer 3

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.

Answer 4

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.

4. 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 ;)

Answer 5

You can use this algo: https://en.wikipedia.org/wiki/Kosaraju's_algorithm

You need to divide the assembler code into graphs (basic blocks) and find strongly connected graphs. https://habr.com/ru/articles/331904/

https://habr.com/ru/articles/537290/