The problem is properly identifying the relocations spots and their targets inside a Ghidra database, which is based on references. On x86 it's fairly easy because there's usually a 4-byte absolute or relative immediate operand within the instruction that carries the reference. On MIPS it's very hard because of split MIPS_HI16/MIPS_LO16 relocations and the actual reference can be hundreds of instructions away.
So you need both instruction flow analysis strong enough to handle large functions and code built with optimizations, as well as pattern matching for the various possible instruction sequences, some of them overlapping and others looking like regular expressions in the case of accessing multi-dimensional arrays. All of that while trying to avoid algorithms with bad worst cases because it'll take too long to run on large functions (each ADDU instruction generates two paths to analyze because of the two source registers).
Besides that, you're working on top of a Ghidra database mostly filled by Ghidra's analyzers, which aren't perfect. Incorrect data within that database, like constants mistaken for addresses, off-by-n references or missing references will lead to very exotic undefined behaviors by the delinked code unless cleaned up by hand. I have some diagnostics to help identify some of these cases, but it's very tricky.
On top of that, the delinked object file doesn't have debugging symbols, so it's a challenge to figure out what's going wrong with a debugger when there's a failure in a program that uses it. It could be an immediate segmentation fault, or the program can work without crashing but with its execution flow incorrect or generating incorrect data as output. I've thought about generating DWARF or STABS debugging data from Ghidra's database, but it sounds like yet another rabbit hole.
I'm on my fifth or sixth iteration of the MIPS analyzer, each one better than the previous one, but it's still choking on kilobytes-long functions.
Also, I've only covered 32-bit x86 and MIPS on ELF for C code. The matrix of ISAs and object file formats (ELF, Mach-O, COFF, a.out, OMF...) is rather large. C++ or Fortran would require special considerations for COMMON sections (vtables, typeinfos, inline functions, default constructors/destructors, implicit template instantiations...). Also, you need to mend potentially incompatible ABIs together when you mix-and-match different platforms. This is why I think there's a thesis or two to be done here, the rabbit hole is really that deep once you start digging.
Sorry for the walls of text, but without literature on this I'm forced to build up my explanations from basic principles just so that people have a chance of following along.
But let me stick with some basics. So, I can write and compile an x86 test.c program. Then, I use your extension and undo the linking. Then, I use the results to link again into a new executable? Are the executables identical? When does it break?
How much of a task is it to make it a standalone program? What about x64 support?
There are links in the README of my Ghidra extension repository that explain these use-cases in-depth on my blog, but as a summary:
- You can delink the program as a whole and relink it. This can port a program from one file format to another (a.out -> ELF) and change its base address.
- You can delink parts of a program and relink them into a program. This can accomplish a number of things, like transforming a statically-linked program into a dynamically-linked one, swapping the statically linked C standard library for another one, making a port of the program to a foreign system, creating binary patches by swapping out functions or data with new implementations...
- You can delink parts of a program and turn them into a library. For example, I've ripped out the archive code from a PlayStation game built by a COFF toolchain, turned it into a Linux MIPS ELF object file and made an asset extractor that leverages it, without actually figuring out the archive file format or even how this archive code works.
You can probably do even crazier stuff than these examples. This basically turns programs into Lego blocks. As long as you can mend them together, you can do pretty much anything you want. You can also probably work on object files and dynamically-linked libraries too, but I haven't tried it myself.
> Are the executables identical?
Probably not byte-identical, but you can make executables that have the same observable behavior if you don't swap out anything in a manner that impacts it. The interesting stuff happens when you start mixing things up.
> When does it break?
Whenever the object file produced is incorrect or when you don't properly mend together incompatible ABIs. The first case happens mostly when the resynthesized relocations are missing or incorrect, corrupting section bytes in various ways. The second case can happen if you start moving object files across operating systems, file formats, toolchains or platforms.
> How much of a task is it to make it a standalone program?
My analyzers rely on a Ghidra database for symbols, data types, references and disassembly. You can probably port/rewrite that to run on top of another reverse-engineering framework. I don't think turning it into a standalone program would be practical because you'll need to provide either an equivalent database or the analyzers to build it, alongside the UI to fix errors.
> What about x64 support?
Should be fairly straightforward since I already have 32-bit x86 support, so the bulk of the logic is already there.
I encourage you to read my blog if you want to get an idea how this delinking stuff works in practice. You can also send an email to me if you want, Hacker News isn't really set up for long, in-depth technical discussions.
I'm mostly using this delinking technique on PlayStation video games, Linux programs from the 90s and my own test programs, so I'm not that worried about security implications in my case. If you're stuffing bits and pieces taken from artifacts with questionable origins into programs and then execute them without due diligence, that's another story.
Long story short, I was inspired by the Super Mario 64 and REDRIVER2 decompilation projects and wanted to do one. I picked a PlayStation video game from my childhood, started Ghidra and then I quickly realized that the game code's a complete mess. It's bad enough that I don't see myself ever finishing this project unless I can somehow divide-and-conquer this problem into manageable pieces. But you can't exactly break a program into pieces... can you?
So I've started to think for a bit and remembered the basic toolchain workflow: source files are compiled into assembly files, which are assembled into object files, which are all linked together into a program. The last bit stood out to me and I wondered: what if I could undo the work of the linker? I'd get a bunch of object files, dividing the original reverse-engineering problem into smaller pieces.
I searched online and found absolutely nothing on the topic. That should've tipped me off, but instead I started scribbling on a piece of paper. Object files are made up of sections (named arrays of bytes), symbols (named offsets within these sections) and relocations (spots to patch with a symbol's address). The linker lays out the sections, computes the addresses of the symbols and then patches the relocation spots to produce the program. I can't just take the program bytes and stuff them into object files because of these applied relocations, but if I could somehow undo them...
The good idea fairy struck, and the fairy struck hard.
I'm writing scripts in Jython and after a couple hundred lines I get results on sample test cases. I try them on the game and it takes forever due to algorithmic complexity. I rewrote a new implementation in Java, forking Ghidra in the process. I rewrote it a couple more times because my analyzer kept hitting edge cases. I built an elaborate and exhaustive test harness because I keep introducing hard to track down regressions. I submitted a couple of pull requests to Ghidra to solve some painful points and reduce the size of the diff, which spanned thousands of lines. I reply to the questions from the Ghidra team with walls of texts trying to explain my use-case, but the PRs get rejected because they don't fit the current design of Ghidra well.
When the Ghidra team rejected my stuff probably because at this point I was probably speaking in the native language of Cthulhu, I really should've taken the hint.
Instead, I spin off my fork as a Ghidra extension to alleviate the maintenance burden, which by now was getting closer to ten thousand lines. I keep rewriting my MIPS relocation analyzers again and again to improve their correctness, always hitting a new edge case. I've decided to start a blog, because I'm tired of trying to explain this stuff from basic principles to people since there's no literature on this topic. I get side-tracked writing a complete series of articles on the basics of reverse-engineering to introduce the topic. I get side-tracked again writing a series of articles on the applications of delinking related to software ports, with a case study on a x86 program that requires me to write relocation analyzers for this architecture and perform refactorings to support multiple ISAs and object file formats.
I'm finally back on reverse-engineering the video game that started all of this and get side-tracked once more because I'm documenting the process in another series of articles. By sheer luck I stumble upon a SYM debugging symbols file, but I don't have the matching executable for it, so I build a placeholder one that matches its shape, then import the placeholder into Ghidra, then write about a thousand lines of Java to import this data on top of the placeholder, then write a bunch of scripts and my own correlators to version track it onto a executable I do have because Ghidra doesn't know what to do with a source executable that doesn't have a single initialized byte to its name. I've tried to engage with the Ghidra community about this latest problem, but no answer. I assume they're probably busy trying to find an exorcist, so I carry on regardless.
Two years. Two years I've spent digging this rabbit hole that's probably worth a thesis or two. I know enough about delinking now that I could probably write a book that would read like a Lovecraftian horror story to people that develop linkers for a living. I've automated this stuff down to making a selection inside Ghidra and clicking on "File > Export Program...", but there's only so much you can do to make accessible or even understandable a technology that allows you to literally rip out code from a Linux program and shove into a Windows program or from a PlayStation game into a Linux program and have it work, in spite of ABIs or common sense.
TL;DR I've developed a reverse-engineering technique by accident that would give professors teaching Computer Sciences 101 an existential crisis.