3 ms·

I fell into the rabbit hole of delinking programs back into object files. Long story short, I was inspired by the Super Mario 64 and REDRIVER2 decompilation pr

by boricj 2y ago

I fell into the rabbit hole of delinking programs back into object files. 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.

polishdude20 2y ago
Give us a blog link!
- boricj 2y ago
  It's on my profile page: https://boricj.net https://boricj.net
a2code 2y ago
I am not sure if I follow correctly. Please clarify the following for me. Have you succeeded in making a tool which undoes the work of the linker?
- boricj 2y ago
  I did, you can find the Ghidra extension there: https://github.com/boricj/ghidra-delinker-extension https://github.com/boricj/ghidra-delinker-extension 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.

by boricj 2y ago

polishdude20 2y ago

Give us a blog link!

boricj 2y ago
It's on my profile page: https://boricj.net https://boricj.net

a2code 2y ago

I am not sure if I follow correctly. Please clarify the following for me. Have you succeeded in making a tool which undoes the work of the linker?

boricj 2y ago
I did, you can find the Ghidra extension there: https://github.com/boricj/ghidra-delinker-extension https://github.com/boricj/ghidra-delinker-extension 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.