An Experimental Study of Different Binary Exporters

Overview

The first step to export a disassembled binary is to disassemble it. Numerous tools exist for this task, the most famous one being IDA, a commercial tool by HexRays. During the last years, other tools have been released (Binary Ninja, radare, Ghidra) with different ranges of features and prices. While this blog post does not conduct a complete review of all the existing tools, nor pretends to as it would be slippery, we still wanted to have a more informed opinion on the different options.

The table below lists some important tools to disassemble a complete binary and some of their features.

As seen in the table above, where only active projects are listed, there is a broad range of tools available. It was not possible to compare all the binary disassembly tools, as our time was limited. We thus elected not to include the following:

• Binary Ninja: we had no license for the tool;

• McSema: it relies on IDA to perform the disassembling;

• BAP: the python bindings are using a client/server model that is not really practical for our needs;

• Pharos: tuned to be used for C++ disassembly;

• Macaw: supports a limited set of architecture.

Note: Even if these tools have been left aside because they did not seem to fit our needs, they are nice pieces of engineering. We still encourage everyone to have a look at them. [1]

Binaries

To test the performances of the disassemblers, the three following programs were used, classified in three categories, small, medium and large. The selected binaries are:

• Small: elf-Linux-x64-bash (~900KB) ELF file for x86-64 (source: Linux)

• Medium: delta_generator (17MB) ELF file for x86 (source: Android Open Source Project)

• Large: llvm-opt (34MB) ELF file for x86-64 (source: LLVM)

These programs were selected at random from programs available on our computers at the time of the tests. They are not supposed to have any outstanding features, just regular programs coming from widely used open-source projects.

Disassembly results

All tests were run on a Dell XPS 15 with an Intel® Core™ i7-6700HQ CPU @ 2.60GHz with an SSD and 16 Go RAM running Debian 10 (Buster).

Some notes on the table:

• These disassembly figures should be handled with care as there is no ground truth results (in terms of instructions/functions count). Nonetheless, IDA/Ghidra results can be considered as a close approximation of the right results.

• angr is a complex tool which performs control flow analysis through code emulation to correctly disassemble a binary. However, this implies to have some stubs [2] written to perform the emulation. While a lot of the necessary stubs are already available, some are still missing (hence the errors shown). To our knowledge, there is no method in angr to disassemble a binary without generating a CFG (see #1116).

• Miasm needs the entry points of a program to start disassembling. It performs the disassembly from one entry point recursively until no instruction is found. The two functions found by the tool are actually the two entry points we specified (_start and main) [3].

• The x86_64 version of the delta_generator program was used for ddisasm because x86 is not (yet) supported by the tool.

• JEB uses a slightly broader notion of functions where every instruction is assigned to a function (while IDA leaves orphaned instructions). New functions are also created for exception handlers and per switch target if it does not succeed in reconstructing it. These are factors which explain the difference in function numbers. In terms of retrieved instruction numbers it performs as well as IDA and Ghidra while being more similar to Ghidra in terms of speed.

• Both IDA and Ghidra stand out for the number of instructions and functions retrieved, with a little advantage to IDA for its disassembly speed. These results are not surprising since IDA and Ghidra are huge players with decades of experience.

Overview

The list of exporters available for the tools tested in the first section is shown below.

• Ghidra provides an IDA plugin to generate an XML file (and a raw data file) so the user can import them in Ghidra.

• The widely used tool BinDiff uses BinExport, a Protobuf generated file, exported from IDA as a basis to perform its diffing. One of the authors of BinExport has started a port of the exporting feature on Ghidra (the proof-of-concept is available in his personal project on GitHub and worked really nicely so far).

• ddisasm is able to parse a binary file and export a lot of information via a Protobuf file. The ultimate goal of the toolchain developed by GrammaTech is to do binary rewriting [4]. As a consequence, the exported features focus on the sole information useful for this task. This represents only a subset of all the available information.

Exporter features

The table below details the various information exported by the different exporters selected. The results were gathered by analyzing the description of the protocol and actual exported files.

Dataset

For the rest of the benchmarks, we gathered a dataset of various binaries coming from different sources. While our dataset is not exhaustive, it tries to mimic the diversity of programs a reverser could encounter. It gathers binaries of various architectures, files formats, size and bitness. The sources used are listed below [5] :

• binary-samples: A test suite for binary analysis tools made by Jonathan Salwan

• AOSP (Android Open Source Project): An open source operating system for mobile devices

• LLVM: The compiler infrastructure project

The graph above shows the number of instructions per program in the dataset. If most of our test suite is made of programs with less than a million instructions, a few large binaries were also included, to better understand how the exporters and disassemblers scaled. As we need to plot large ranges of values in the same graph, most of the curves looks flat for the first points. [6]

Disassembly time

The first metrics we were interested in is the disassembly time, defined as the duration of the automatic analysis. We knew that IDA was faster than Ghidra, but we wanted to measure to what extent.

The results are impressive, Ghidra is much slower than IDA (up to 13 times slower for large binaries). Even if the disassembly step is a one time process, the performances of Ghidra are problematic for scalability. Nevertheless, it should be noted that the results are biased, because Ghidra performs an additional decompilation step.

Export time and size

The first section helped us to draw an overview of the available exporters. Another interesting metrics is the export time for the following disassemblers/exporters pairs:

• IDA + BinExport

• IDA + Ghidra XML

• Ghidra + XML

We chose to keep only those exporters because they were running on the disassemblers we selected, and had an interesting set of exported features. They also had a good support for Ghidra, and BinDiff has been used for years in the community without issues. We may also note that they use different exporting strategies: Ghidra does not export any information on instructions while BinExport decomposes every operand of each instruction and exports them.

The export size of a program is far greater than the program itself for both tools. While BinExport produces a single Protobuf file, Ghidra generates two files, one XML with all the information and a raw byte file containing all the code of the exported binary. The figures on the graph represent the sum of the size of these two files.

We observe that the size of the export for BinExport and XML is roughly the same. However, BinExport exports a lot more information on the binary than Ghidra. Remember that Ghidra does not export any information on the instructions themselves neither on the basic blocks besides their contents (i.e. raw bytes). The sizes of the exported files remain equivalent because of optimizations made by BinExport: the format is specifically designed for compactness (e.g. there is an extensive usage of deduplications tables) and the export file uses a binary serialization protocol, namely Protobuf. This will be further discussed in the next section.

The table above also includes the sizes of the database generated by IDA, the i64 file, which is much larger than any of the exported file considered in this study.

Full export

To summarize the results from the previous tests, we plot hereafter a graph explaining the time spent in the three phases of the export process:

• Disassembly phase: disassembling the binary

• Export phase: generating the export files

• Deserialization / Loading phase: Importing the exported file in Python

This graph shows that the deserialization time can to become non-negligeable with the Protobuf format for large binaries (here mdbook). This observation led us to the next section which explores various binary serialization formats to find which one is the more suitable for our needs.

Introduction

Numerous formats exist [7] for serialization because not all usages (e.g persistent storage, RPC communication, data transfer, ...) require the same set of features. One may want to have the data stored in a "human-readable" way (i.e as text), have a fast-access time, or a compact storage size. For program serialization, we need a trade-off between a compact disk usage, a reasonable deserialization time and a low memory footprint. Since a readable format is not needed and disk usage is a concern, binary serialization formats seemed more appropriate, as opposed to text formats (e.g. JSON, XML).

Binary serialization formats

In this section, we will focus on three formats used for binary serialization:

• Protobuf: A format developed (and extensively used) by Google for serializing structured data.

• FlatBuffers: Another format developed by Google to serialize data. Mostly used for performance critical applications.

• Cap'n Proto: A format developed by Kenton Varda (tech lead of Protobuf while he was working at Google) for Sandstorm.

All these formats use a custom schema definition language to explain how the data will be formatted on the wire. Even if this blog post does not intend to be a crash course on data serialization, nor a tutorial on how to write a schema for the three protocols, the syntax of a basic message is shown below.

message Meta {
  optional string executable_name = 1;
  optional string executable_id = 2;
  optional string architecture_name = 3;
  optional int64 timestamp = 4;
  }
        

struct Meta {
    executableName @0 :Text;
    executableId @1 :Text;
    architectureName @2 :Text;
    timestamp @3 :UInt64;
}
            

table Meta {
  executable_name:string;
  executable_id:string;
  architecture_name:string;
  timestamp:long;
  }
            

The main difference between these formats is how they store data on the wire. Protobuf, the oldest one, uses an encoding/packing step which transforms the input on the wire. This allows Protobuf to be more compact because the encoding step reduces the amount of bytes needed to store an object (see Encoding in Protobuf documentation). However, both FlatBuffers and Cap'n Proto use a 'zero-copy' strategy, meaning that the data on the wire is structured the same way as it is in the memory. The main advantage of this technique is to nullify the time needed to decode the object because no decoding step is performed.

Another huge difference between FlatBuffers/Cap'n Proto and Protobuf is the ability to perform random access reads (the ability to read a specific part of the message without reading the whole message before). With Protobuf this is not possible because the message needs to be parsed upfront (and memory allocated). However, both FlatBuffers and Cap'n Proto implement this feature using pointers, allowing fast access to part of the message.

Allocation (i.e how to write message) has to be done bottom-up for FlatBuffers because a message must be finished before another one is started. This limitation does not apply to Protobuf (because all the message is written at the end) and Cap'n Proto (because the size of an object is known when allocated).

The final difference we will go through is how unset fields (i.e. fields with no values for this specific message) are stored on the wire. Both Protobuf and FlatBuffers do not allocate them while Cap'n Proto still do. This leads to a waste of space for Cap'n Proto.

Benchmarks

For these benchmarks, we translated the BinExport Protobuf into a FlatBuffers and a Cap'n Proto schema. The translation was done manually for Cap'n Proto and using the option --proto of flatc for FlatBuffers (plus some minor revisions). We do not pretend to have fully optimized the new schemes using all the features of the two serializations formats but believe this still leads to an informative comparison.

First, we want to compare how big the exported files are compared to the binaries themselves. This size is represented by the dashed line and is linear ($\def\pelican{\textrm{pelican}^2} y=x$).

We see that the size of the exported file grows non-linearly with the size of the binary. The following graph shows the ratio between the size of the exported file and the size of the binary.

We see that Protobuf is much more compact than the two others (the encoding step is crucial for this part) and the ratio skyrockets for specific binaries. There is still room for improvement in the export size for the two other protocols, mostly by having a better understanding of the ranges of the different values. With Protobuf, one may declare every integers as 64-bits wide integers, the serialization algorithm will only write on the wire the varint encoded value of the number (a reduction up to a scale factor of 8 for the 127 first values). However, with Cap'n Proto and FlatBuffers, the value would need to be 64 bits long anyway.

Another interesting point to study is how much memory is used for loading the serialized file in Python. (Note: using the memory_profiler [8] module to retrieve memory usage.)

As expected, the memory needed to load the export of a binary is much more important for Protobuf. For example, for llvm-opt the Protobuf file is around 150MB but the loading takes around 1.8 Go of RAM.

The last metrics we want to consider is how much time is needed to load an export file in Python from the three files format.

As expected, the Protobuf format takes a lot of time to be deserialized. Cap'n Proto and FlatBuffers have similar performances, mostly because they are based on the same patterns.