spedi

Spedi

Spedi is a speculative disassembler for the variable-size Thumb ISA. Given an ELF file as input, Spedi can:

• Recover correct assembly instructions.
• Recover targets of switch jumps tables.
• Identify functions in the binary and their call graph.

Spedi works directly on the binary without using symbol information. We found Spedi to outperform IDA Pro in our experiments.

Idea

Spedi recovers all possible Basic Blocks (BBs) available in the binary. BBs that share the same jump instruction are grouped in one Maximal Block (MB). Then, MBs are refined using overlap and CFG conflict analysis. Details can be found in our CASES'16 paper "Speculative disassembly of binary code". The paper is available here.

Result summary

Spedi (almost) perfectly recovers assembly instructions from our benchmarks binaries with 99.96% average. In comparison, IDA Pro has an average of 95.83% skewed by the relative poor performance on sha benchmark.

Spedi precisely recovers 97.46% of functions on average. That is, it identifies the correct start address and end address. Compare that to 40.53% average achieved by IDA Pro.

A nice property of our technique is that it's also fast and scales well with increased benchmark size. For example, spedi disassembles du (50K instructions) in about 150 ms. Note that there is good room for further optimizations.

Citing

To cite Spedi in an academic work please use:

@inproceedings{BenKhadraSK2016,
 author = {Ben Khadra, M. Ammar and Stoffel, Dominik and Kunz, Wolfgang},
 title = {Speculative Disassembly of Binary Code},
 booktitle = {Proceedings of the International Conference on Compilers, Architectures and Synthesis for Embedded Systems},
 year = {2016},
 location = {Pittsburgh, Pennsylvania},
 articleno = {16},
 doi = {10.1145/2968455.2968505},
 acmid = {2968505},
 publisher = {ACM},
}

Usage

Build the project and try it on one of the binaries in our benchmark suite available in this repository.

The following command will instruct spedi to speculatively disassemble the .text section,

$ ./spedi -t -s -f $FILE > speculative.inst

Use the following command to disassemble the .text section based on ARM code mapping symbols which provides the ground truth about correct instructions,

$ ./spedi -t -f $FILE > correct.inst

The easiest way to compare both outputs is by using,

$ diff -y correct.inst speculative.inst |less

Currently, you need to manually modify main.cpp to show results related to switch table and call-graph recovery.

Road map

This tool is an academic proof-of-concept. Currently, it's not on our priority list. However, there are certain features that we have in mind for the future, namely:

• Mixed-mode ARM/Thumb disassembly. The general idea of speculative disassembly
  provides the framework to do this. Basically, one needs to speculatively disassemble a code region twice. One time in Thumb mode, and a second time in ARM mode. Later, mode switching instructions (mainly bx and blx) should be analyzed. This paper provides some related details.
• Support for x86/x64. Thumb and similar RISC-like ISA have limited variability. Basically, instructions can either be 2 or 4 bytes width. We need to push the challenge even further by supporting x86/x64. To this end, overlap analysis might span more than two MB which complicates things. Current Maximal Block data structure is not efficient to do this.
• Refactorings. The code is tightly coupled with our ELF reader. Also, it is specific to Thumb ISA. We need to make it more modular to support other ISAs and binary formats.
• ELF Reader: Our ELF reader is based on libelfin. We inherit some memory leakage issues. Additionally, the reader might crash on binaries with DWARF debug info. These issues needs to be addressed either in upstream or directly here.

Related work

Recently, Andriesse et. al. have been working on Nucleus, a tool for function identification in x64 binaries. Their paper "Compiler-Agnostic Function Detection in Binaries" was accepted at IEEE Euro S&P 2017. They use more or less the same function identification techniques implemented in Spedi. If you are interested in x64 support, you can have a look at their tool.

Note, however, that their tool is based on the assumption that recent x64 compilers allocate jump-table data in .rodata section. That makes instruction recovery significantly easier since it can be done reliably with linear sweep. In comparison, Spedi handles the more general case of mixed code/data using speculative disassembly.

Dependencies

This project depends on Capstone disassembly library (v3.0.4).