A script to find call recursions in binaries


This is a script I’ve slapped together to find potential call recursions in binaries. A call recursion occurs when functions comprise a loop; for instance, function a() calls function b(), and function b() calls function a(). If the recursion depth isn’t properly curtailed, this can lead to a stack overflow, which crashes the program and is essentially a denial-of-service. Especially for server software that can enter a deep recursion upon the instigation of an untrusted client, this is problematic, as it essentially constitutes a remote DoS. Thanks to this program I once found a remote DoS vulnerability in Apache: CVE-2015-0228.
An other way to do this is to use a static C/C++ analyzer to parse the entire source code and find recursion loops on the resulting invocation tree, but this approach saves you the parsing overhead and operates on the end product (the binary) instead.
This script implements my own algorithm to find loops in a graph. I believe scipy offers such an algorithm out-of-the-box, so you may use that instead if it is faster.
The script does not find loops that involve function pointers; this is far more difficult to detect as it requires a semantic understanding of the code.
It is configured to output 25 loops at most, to prevent that excessive output is generated (this happens for some software, try Python or Tor). Change it to suit your needs.
You will probably need to alter it a bit if you’re going to use it for non-x64 binaries.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.