Detecting recursive functions in IDA

Question

How can I detect/mark recursive functions in IDA?

Trivial method would be to check every function's call list and if it calls itself then it's recursive. I'ld like to put a comment or some kind of indicator that would help me distinguish these functions.

Answer 1

It is not trivial task. You can do it relatively easy if you not taking in account indirect calls (for example such as virtual functions in C++) and calls from another function like this:

int f() {
    g();
}

int g() {
    f();
}

It can be much more complicated if one of your functions is in another binary (dll for example). So, there are two ways to do it, a static and a dynamic way.

Recursive assembly traversal - static analysis approach

You should write the script in IDAPython that passes over the function, and recursively processes each call. If you find current function in collected stack the function is recursive.

Very simple variant looks like this:

# I didn't check it, use carefully, beware the errors in this code
import idautils
import idc
import idaapi

def handle_function(func_start):
    global stack
    if func_start in stack:
        print "This is recursive function", hex(func_start), Name(func_start)
        for x in stack:
            print "\t", hex(x)
        #insert your renaming here, it should be idc.MakeName
        return

    stack.append(func_start)
    for h in idautils.FuncItems(func_start):
        for r in idautils.XrefsFrom(h, 0):
            if r.type == fl_CF or r.type == fl_CN:
                print hex(h), "-->", hex(r.to)
                if r.to == func_start:
                    # Insert renaming here too for simple recursion
                    print "It is simple recursive function that calls itself directly"
                    return
                else:
                    handle_function(r.to)
    stack = stack[:-1]

for f in idautils.Functions():
    stack = []
    handle_function(f)

Breakpoint analysis - dynamic analysis approach

Write script in IDAPython that recognizes all function prologues and filters out all functions that doesn't call anything. Put breakpoint on each collected prologue and run the program. Each time the program stops, analyze stack of the program using IDAPython in order to find function you are stopped on in the stack. If you find it, the function is recursive.

Answer 2

I lack 9 reputation points, so sadly I can't comment the great answer by w_s. ;)

Just for completeness, the concept described is known in graph theory as "Tarjan's Algorithm" for finding strongly connected components.

Wikipedia has a nice animation that helps following the steps.

For study, here is another (more formal) Python implementation, it's the one I have used for finding loops in functions in IDAscope but it's easily adapted for finding recursive functions.