Reverse Engineering Tools Part 1: BinDiff

When teaching courses on topics like Reverse Engineering or Malware Analysis we always emphasize the need to minimize unneeded work. Because reversing an unknown binary is a time consuming and complex process, tools that simplify the RE process are invaluable when working under time pressure. In this blogpost series I will present multiple tools and techniques that can help to reverse an unknown binary. Please note that these articles do not contain cutting edge research but rather target at newcomers. However, I hope to also provide some useful and interesting information for moreexperienced practitioners.

1. Intro

This blogpost will deal with BinDiff  which is, as its name suggests, a comparison tool for binaries. BinDiff was initially developed by Zynamics, a small company led by Halvar Flake and located in Bochum, which was later bought by Google in 2011. Fortunately, BinDiff was not completely abandoned and is still for sale on the Zynamics website. While no major updates were released in the last years, bugfixes and minor updates are still available. The buyout had another positive side effect: Prices of BinDiff and BinNavi (which we will futher investigate in an upcoming post of this series) heavily decreased and BinDiff is now available for 200$.

As mentioned before, BinDiff is used to compare binary files. This can be useful in several different circumstances. The premier use case for which BinDiff was designed is patch diffing. Patch Diffing is about comparing the patched and unpatched versions of a given executable in order to extract the underlying vulnerability. This technique is quite popular for Microsoft’s security updates where technical details are typically very sparse. Additionally, BinDiff can be used to find copyright violations like misuse of GPL licensed source code or code theft. Finally, it supports porting of symbols between two disassembly files. This can be useful when analyzing applications with large statically linked libraries or new variants of malware.

While BinDiff includes a standalone Java application it is still dependent on IDA Pro as disassembler and only supports IDA Pro database files as input files. While this has the downside of adding a rather expensive requirement, it allows BinDiff to directly work with the very reliable (and user expandable) IDA output.

Before demonstrating a practical example of BinDiff, we need to dive a bit into its underlying algorithms and which advantages and limitations these imply.

2. Algorithms

For obvious reasons a byte-by-byte comparison of executables will fail to produce usable output even for most trivial changes. Even a basic disassembler based approach that compares instruction won’t return useful results, as a compiler has large freedom on instruction order and register
allocation. This means that a different compiler version or even a different optimization setting can lead to large changes concerning used instructions and registers.
To counter this problems BinDiff uses a graph based approach. Instead of relying on the actual content of basic blocks [a group of instructions without branches], the used algorithms analyze two different graph types that characterize an executable: The call graph which describes the relationship between functions by encoding function calls as edges while the functions itself are described as nodes. The control flow graph, which describes the program flow is described inside a single function.
The important observation of BinDiffs developer was that these two graphs, are sufficient to characterize most functions inside an executable. If two functions in the compared executable have edges from and to the same nodes inside the call graph and have similar or identical CFGs the potential of both actually being the same function is very high.

In contrast to instruction based approaches the “structural diff” has a number of advantages: While compiler optimizations and flags often change the used instructions and registers, they normally do not modify the call graph or CFGs (Note: Function inlining and loop unrolling are two popular counter examples that need to be addressed). Furthermore, a certain program will have the similar CG and CFGs even when compiled with a completely different compiler, for a different operating system and even for another architecture.

A nice example of this approache’s advantages is “Targeting The IOS_Kernel”  where the ARM based iOS kernel is diffed with the x64 based OS X kernel in order to port publicly available symbols to the way harder reversible iPhone OS.

Of course, the simple strategy above is not complete. In order to compare the call graph a number of corresponding nodes have to be identified first. Additionally, simple functions with no or only simple control flow structures can not be identified using their trivial CFGs. These problems are minimized by using a set of additional function attributes.
In current BinDiff versions these attributes include checks like a hash of the binary function content, loop count or string references.
The results produced with these techniques are not 100% reliable and can lead to false positives or false negatives. However, they are surprisingly good in many real world cases as we will see in the upcoming demonstration.

3. Patch-Diffing: MS11-083

MS11-083 was a very interesting vulnerability affecting the TCP/IP stack of all Windows operating systems since Vista. The patch notes describe the bug like this:

“The vulnerability could allow remote code execution if an attacker sends a continuous flow of specially crafted UDP packets to a closed port on a target system. … A remote code execution vulnerability exists in the Windows TCP/IP stack due to the processing of a continuous flow of specially crafted UDP packets. An attacker who successfully exploited this vulnerability could run arbitrary code in kernel mode. ”  http://technet.microsoft.com/de-de/security/bulletin/ms11-083

A Microsoft SRD blog post publishedthe same day describes the bug as an “integer overflow of [a] reference counter” and characterizes it as very hard to exploit reliable.

Of course, a bug like this is very interesting for security researchers and in order to find more information about the problem, patch diffing appears as obvious first step. Thanks to Windows Update, we can manually install the specific patch and compare our system status before and after the installation. A quick analysis shows that the only interesting changes seem to be located in “tcpip.sys”. That makes sense since this binary contains the actual code for the Windows TCP/IP Stack. We can also verify that we did not miss any changes by looking at the corresponding knowledge base entry.

Before diffing the two versions of “tcpip.sys” we first have to analyze them using IDA to create the needed IDB files. When IDA is correctly configured it should automatically grab the public symbols from Microsofts symbol server. The public symbol files include the names of all functions in the binary which is an imporant information source used by BinDiff in the matching process.

After loading both binaries in BinDiff we can quickly see that almost all functions are matched and a large percentage of them do not show any modifications. This is often the case when looking at security updates without any changes concerning compiler versions or flags.

A good approach when performing patch diffing is to look for the function pair showing/containing the most modifications. This can be done using the “Similarity” value in BinDiff. In the case of MS11-083 the function with the lowest similarity value is “IppRateLimitIcmp()”. When looking at the old and new CFG we can see that two new basic blocks have been inserted which only call IppDereferenceNeighbor() or IppDereferenceLocalAddress(). When remembering the Microsoft blog post, the issue was described as an integer overflow in a reference counter. A missing dereference call appears as logical cause of this bug.

Additionally, the discussed bugs excclusively affect Microsoft OS versions since Windows Vista and the IppRrateLimitIcmp function that is used by a security feature to slow down certain kinds of port scans was only introduced with Vista.
This demonstrates, that with only a little time investment and a bit of research we were able to quickly identify the function responsible for this bug. Of course this information alone is not yet enough to write an exploit or assess the risk of a successful attack but these issues are not in the scope of this post. For more information about this specific bug see “On the (im)possibility of MS11-083” where the bug is analyzed in more detail.

4. Alternatives

In this post I’ve highlighted BinDiff and showed how it can be used to diff patches in order to find more information about vulnerabilities. While BinDiff is our preferred tool for this task and the only one that supports features as inter architecture symbol porting, free alternatives exist: DarunGrim and PatchDiff2 are both specialized on Patch Diffing and should be evaluated as possible alternatives to BinDiff.