Identifying x86_64 ELF Symbols in Stripped Binaries using AI
Scenario
Let's say we have a binary that we have either reverse engineered or have the associated debugging information. We will refer to this executable as binary S. We also have another executable called P that we know is similar to binary S in some way but it is stripped and has no debugging information. Binary P could have a similar source code to binary S or could be made from the same statically linked library. However, S and P are sufficiently different that they cannot be diffed with BinDiff.
We want to use information from binary S to transpose symbols from S to P.
This blog post will explain how the AI we are developing at RevEng.AI does exactly that. We will look at one technique that explores our program comprehension embeddings API to locate symbols in P given a single known anchor point in it.
Setting the scene
As a running example, S will be the binary miredo from the Debian Sid package miredo/amd64. Miredo is a Teredo client (RFC 4380) that tunnels IPv6 packets in IPv4 UDP packets. We don't have access to the source code but we can access symbol information via the miredo-dbgsym/amd64 package. It is important to note that RFC 4380 uses a combination of MD5 and HMAC in its protocol design. You can download binary S below.
As for executable P, we will be using the binary fdupes from the Debian Sid package fdupes/amd64. FDupes is a program that identifies duplicate files within directories using MD5 hashes and byte by byte comparisons. You can download binary P below.
Our intuition informs us that, given both binaries contain code for processing MD5, can we port MD5 related symbols from S to P?
An inspection of our source binary S reveals the following symbols:
root@desyl:~# readelf -s /usr/sbin/miredo | grep -i md5
81: 0000000000000000 0 FILE LOCAL DEFAULT ABS md5.c
82: 0000000000006360 2113 FUNC LOCAL DEFAULT 14 md5_process
138: 0000000000006e10 194 FUNC GLOBAL DEFAULT 14 md5_finish
369: 0000000000006be0 552 FUNC GLOBAL DEFAULT 14 md5_append
396: 0000000000006bb0 42 FUNC GLOBAL DEFAULT 14 md5_initA quick internet search for "md5" and "fdupes" reveals that FDupes has the same md5_process, md5_finish, md5_append, and md5_init functions in its source code (Github search).
md5_init is a small 42 byte function and should be easy to identify in Ghidra. For the rest of this blog post we are going to assume that we know the location of a single symbol in P - md5_init. This will be our known anchor point in P.
We are going to use this anchor point with the relative difference between symbols' embedded representations from S to locate another symbol in P. Before we explain exactly what that means or why we would want to do that, take a look at md5.c and you will see that md5_process is not a direct caller or callee of md5_init and therefore cannot easily be identified by simple static rules.
We will now explain how to locate md5_process in the stripped binary P using md5_init and the relative difference between md5_process and md5_init in our source executable S.
Machine Learning Background
RevEng.AI's BinNet model uses a deep multi-output transformer architecture to capture the semantic meaning of binary code. It represents binary code (and all strings, XREFS, constants, etc.) as real-valued vectors that can be used for downstream ML tasks.
To understand this properly you need to have a basic understanding of Word2Vec and the concept of word representations. We recommend pausing here and reading the following blog post if you are unfamiliar with modern NLP techniques.
The famous example from Word2Vec allowed for the vector representations of the words king - man + woman ≈ queen. This proved that the vector space generated by Word2Vec captured semantic information beyond what was previously possible by Neural Network Language Models (NNLMs).
You might be able to guess where this is going...
Recovering Symbol Information using Embedded Symbol Representations
We are going to use RevEng.AI's BinNet model and embeddings API to locate md5_process in P by calculating the difference between the embedded representations of md5_process - md5_init in S and adding the representation of md5_init in P.
We will use the following Python code:
from reveng import BinNet, Binary, Symbol
bn = BinNet(apikey='freeware')
S = Binary(path='/usr/bin/miredo')
P = Binary(path='/usr/bin/fdupes')
# run binary analysis, P is stripped
# extract function boundaries from ghidra
S.analyse()
P.analyse(FBD='ghidra', stripped=True)
# store embeddings in numpy matrix, shape=(N, 192)
# N is number of symbols in binary
# 192 is the number of dimensions for BinNet embeddings
Xs = bn.get_embeddings(S.symbols)
Xp = bn.get_embeddings(P.symbols)
# get embeddings for each symbol
# md5_init is at 0x00003f07 in fdupes
s_md5_init = Xs[S.get_symbol('md5_init'), :]
s_md5_process = Xs[S.get_symbol('md5_process'), :]
p_md5_init = Xp[S.get_symbol_at_loc(0x00003f07), :]
# build query vector
query_vec = s_md5_process - s_md5_init + p_md5_initOur query vector is a real-valued numpy vector of 32 bit floats:
In [216]: query_vec
Out[216]:
array([[-1.0754741 , -0.53394 , 2.5343153 , -0.8589107 , -0.80127776,
3.6827471 , -0.2754942 , -0.25956583, -0.9386326 , -0.8809752 ,
-0.94144917, -0.9657012 , -0.37274447, 3.551879 , 1.4170911 ,
...
-0.5281741 , -0.65251297, -0.9238823 , 1.2517035 , -0.77191585,
-0.9819512 , -0.695347 , -0.47379667, -0.6443882 , 0.8159219 ,
-0.20785426, -0.52132106, -0.7369828 , 2.757089 , -0.07254058,
-1.1361468 , -0.45225745]], dtype=float32)We now need to find the closest symbol in P to our query vector. We do this using the cosine similarity against all functions that Ghidra found in P.
from sklearn.metrics.pairwise import cosine_similarity
closest = cosine_similarity(Xp, query_vec).squeeze().argsort()[::-1][0]The closest BinNet embeddings in P to our query can then be accessed by looking up the row corresponding to the closest index:
In [235]: Xp[closest, :]
Out[235]:
array([[-1.03495793, -0.60625399, 2.51171437, -0.84164309, -0.83068409,
3.69240599, -0.31704739, -0.22428862, -1.0581016 , -0.96066797,
-0.87574955, -0.95887101, -0.40816309, 3.62616827, 1.39601726,
...
-0.46266309, -0.58537404, -0.87706089, 1.23309646, -0.75341943,
-0.94693962, -0.58251833, -0.45131244, -0.71748744, 0.77900041,
-0.25757586, -0.56068685, -0.74393312, 2.77102427, -0.04606016,
-1.16797348, -0.41193305]], dtype=float32)And now we can find the matched symbols virtual address:
In [236]: P.symbols[closest].vaddr
Out[236]: 14068The symbol md5_process should have a virtual address of 14068 (0x36f4) in our binary P. If we now download symbol information from the fdupes-dbgsym/amd64 Debian package and merge the ELF files we indeed find this is correct.
How difficult was this?
OK, BinDiff doesn't work but can't we just hash a function's disassembly code and find matches between the two functions? Can we use IDA FLIRT?
Let's download the debugging package and inspect P with symbols. The first thing to note is that md5_process is 2113 bytes in S and 2067 bytes in P. Matching hashes clearly won't work.
Is the disassembly similar? Let's take a look with Rizin:
fdupes
[0x000013b0]> pdf @ sym.md5_process
┌ 2067: sym.md5_process (int64_t arg1, int64_t arg2, int64_t arg_6fa87e4fh);
│ 0x000036f4 4157 push r15
│ 0x000036f6 4156 push r14
│ 0x000036f8 4155 push r13
│ 0x000036fa 4154 push r12
│ 0x000036fc 55 push rbp
│ 0x000036fd 53 push rbx
│ 0x000036fe 8b4708 mov eax, dword [rdi + 8]
│ 0x00003701 894424b8 mov dword [rsp - 0x48], eax
│ 0x00003705 8b470c mov eax, dword [rdi + 0xc]
│ 0x00003708 89442498 mov dword [rsp - 0x68], eax
│ 0x0000370c 8b4710 mov eax, dword [rdi + 0x10]
│ 0x0000370f 8944249c mov dword [rsp - 0x64], eax
│ 0x00003713 8b4714 mov eax, dword [rdi + 0x14]
│ 0x00003716 894424a0 mov dword [rsp - 0x60], eax
│ 0x0000371a 4889f0 mov rax, rsi
│ 0x0000371d 40f6c603 test sil, 3
│ ┌─< 0x00003721 744c je 0x376f
│ │ 0x00003723 488b06 mov rax, qword [rsi]
│ │ 0x00003726 48894424c0 mov qword [rsp - 0x40], rax
│ │ 0x0000372b 488b4608 mov rax, qword [rsi + 8] miredo
[0x00003560]> pdf @ sym.md5_process
┌ 2113: sym.md5_process (int64_t arg1, int64_t arg2, int64_t arg_6fa87e4fh);
| 0x00006360 4157 push r15
│ 0x00006362 4156 push r14
│ 0x00006364 4155 push r13
│ 0x00006366 4154 push r12
│ 0x00006368 55 push rbp
│ 0x00006369 53 push rbx
│ 0x0000636a 4881ec880000. sub rsp, 0x88
│ 0x00006371 64488b042528. mov rax, qword fs:[0x28]
│ 0x0000637a 4889442478 mov qword [var_78h], rax
│ 0x0000637f 31c0 xor eax, eax
│ 0x00006381 8b4708 mov eax, dword [rdi + 8]
│ 0x00006384 89442428 mov dword [var_28h], eaxThe disassembly is significantly different and would not match with hashing or semantic hashing. IDA FLIRT works by matching the first 32 bytes of each function and would fail to find the match.
Discussion
Why would we want to do this? RevEng.AI's BinNet embeddings aren't just useful for matching symbol names. They inherently capture the semantic meaning of binary code and could be used for:
- Porting symbols between different malware samples or OS versions
- Identifying known vulnerabilities in closed source software
- Detecting malware embedded inside proprietary software
- Aiding reverse engineering of never seen before programs
- Speeding up fuzzing by directing path selection to heap allocation functions or other defined behaviour
There are far more efficient ways to use RevEng.AI's API to identify symbols in stripped binaries but this has been a fun example. If you are interested in using our API please contact us via the contact page at https://reveng.ai.
No source code was analysed by our AI in the development of this example.