I'll bite! What wheel is this?
It's a Ghidra extension that can export relocatable object files from any program selection. In other words, it reverses the work done by a linker.
I originally built this as part of a video game decompilation project, having rejected the matching decompilation process used by the community at large. I still needed a way to divide and conquer the problem, which is how I got the funny idea of dividing programs. That allows a particular style of decompilation project I call Ship of Theseus: reimplementing chunks of a program one piece at a time and letting the linker stitch everything back together at every step, until you've replaced all the original binary code with reimplemented source code.
It's an exquisitely deep and complex topic, chock-full of ABI tidbits and toolchains shenanigans. There's next to no literature on this and it's antithetical to anything one might learn in CS 101. The technique itself is as powerful as it is esoteric, but I like to think that any reverse-engineer can leverage it with my tooling.
In particular, resynthesizing relocations algorithmically is one of those problems subject to the Pareto principle, where getting 80% of them right is reasonably easy but whittling down the last 20% is punishingly hard. Since I refuse to manually annotate them, I've had to relentlessly improve my analyzers until they get every last corner case right. It's by far the most challenging and exacting software engineering problem I've ever tackled, one that suffers no hacks or shortcuts.
Once I got it working, I then proceeded in the name of science to commit countless crimes against computer science with it (some of those achievements are documented on my blog). Cross-delinking in particular, that is delinking an artifact to a different platform that it originates from, is particularly mind-bending ; I've had some successes with it, but I sadly currently lack the tooling to bring this to its logical conclusion: Mad Max, but with program bits instead of car parts.
Ironically, most of my users are using it for matching decompilation projects: they delink object files from an artifact, then typically launch objdiff and try to create a source file that, when compiled, generates an object file that is equivalent to the one they ripped out of the artifact. I did not expect that to happen at all since I've built this tool to specifically not do this, but I guess when everything's a nail, people will manage to wield anything as a hammer.
A common challenge is decompiling and reverse engineering a compiled program, e.g. a game. The author realized that it's an interesting approach to do a sort of reverse-linking (or I guess unlinking) process of a program into pieces and then focusing on reverse engineering or reimplementing those pieces instead of the whole.
When it comes to decompiling games, enthusiasts in that hobby want to be able to reproduce/obtain source code that compiles to exactly the same instructions as the original game. I think there is usually also a differentiation between instruction matching and byte for byte matching reproduction. But it definitely seems like a simpler and better approach to do this piece by piece and be able to test with each new piece of progress.
That's my layman understanding of it having only dabbled in decompiling stuff.
The key insight of delinking is that object files are relocatable and the process of linking them together (laying their sections in memory, computing all the symbol addresses, applying all the relocations) removes that property. But by reversing this process (creating a symbol table, unapplying the relocations/resynthesizing relocation tables, slicing new sections), code and data can be made relocatable again.
Since properly delinked object files are relocatable, the linker can process them and stitch everything back together seamlessly, even if the pieces are moved around or no longer fit where they used to be (this makes for a particularly powerful form of binary patching, as constraints coming from the original program's memory map no longer apply). Alternatively, they can be fed to anything that can process object files, like a disassembler for example.
Of course, the real fun begins when you start reusing delinked object files to make new programs. I like to say that it breaks down the linear flow of toolchain from compilation to assembly to linking into a big ball of wibbly-wobbly, bitsy wimey stuff. Especially if you start cross-delinking to a different platform than the original pieces of the program came from.
That was never satisfying to me because recompilation (decompiling to source code or IR that can be recompiled for another platform) is an academic field of study [1], so the problem of converting a shared library to a static one should be easier. After all, you have all the assembly and symbol information right there, it seemed like all you needed to do was massage it the right way.
[1] https://rev.ng/
Shared objects are compiled in a way that the exact same code works when loaded at any address, which typically requires base+offset addressing and is less performant, but the same physical pages holding the object can be mapped into different processes at different addresses, ie shared.
Static object addresses the code and and data directly and does not waste a register and requires the addresses in its code to be modified depending on where it is loaded, and the code cannot be shared between different processes.
You can't convert a static library to shared because you can't.
You can convert a shared library to static but there is no point.
My understanding a shared library is closer to an executable than it is to an object file, so it is in that sense that it is "prelinked and ready to map into memory" just as an executable is. (Once loaded dyld still has to do fixups in the GOT, but that's not touching the text segment.)
I mostly agree with your definitions, but you _can_ create a shared library out of a static library assuming the static library was compiled with fPIC, no? I mean I've never tried it but most linkers seem to allow it [1], and given that creating a full executable is similar to created a shared library, I don't see why it wouldn't work.
And if the code wasn't compiled with fPIC, I still feel that it should be possible in theory since the whole point of object files is that they support relocation. Linking a non-PIC object to produce a shared object would just require patches within the text segment at runtime right? Modern linkers probably don't like doing this for security reasons. But otherwise seems isn't some fundamental limitation, just modern OSs and linkers not supporting an obscure use-case with security risk.
When people say that you can't convert a shared library to a static one (or equivalently statically link against a shared library), they usually cite the lack of relocation table info as the reason. Like they have some hierarchy in mind that goes from source code -> object file -> executable/shared library, and so they say it's "obvious" that you can't go the other way. Which is mostly true in terms of the "golden path" and what you'd want to limit yourself to for production, but in a hacker sense you can obviously go the other way with assemblers and decompilers.
So if someone claims that it's impossible to convert a shared library into a static library, there better be good justification for such a hard claim. And on the face of it, the claim doesn't seem watertight because the _stronger_ claim that you can't convert an executable back into recompilable code is falsified by the existence of decompilers that lower down to LLVM IR.
[1] https://stackoverflow.com/questions/655163/convert-a-static-...
Thinking about it a little bit, I'd say the major challenge for converting from shared to static library is that shared libraries have resolved relocations from text to other segments.
In order to create a static library, you need to make it so that text and data can be moved relative to each other again.
At a minimum, this requires disassembling the text segment to find PC-relative addresses and recreate relocations for them. That doesn't sound impossible, but there may be pitfalls I'm not thinking of right now that make it hard to find all necessary fix ups.
My interpretation is it’s basically a hack because C programmers can’t make their libs reliable/memory safe, and it throws some logs under attacker’s feet.
There was this software called MagicErmine or statifier that could convert the two.
Tools like Statifier to convert an executable + its dylibs into a statically linked executable are sort of an in-between hack that does the equivalent of prelinking. But that's not converting a shared library to a static library, because the result isn't an object file that can be linked.
I guess I never stated the punchline explicitly, but boricj's tool seems to prove that there is in fact no such theoretical limitation in converting from shared -> static library. It's a bit hacky of course, but you can indeed reconstruct relocation tables with decompiler-like analysis to go back from executable -> object file for any function, and this also implies you can go from shared library -> static library.
As far as the traditional linker goes, sure. This whole shtick relies on the fact that a platform has ABI conventions, so with a naive toolchain any translation unit (and function) compiled in isolation must be interoperable as-is, because the linker is completely oblivious to whatever's going on within an object file section (relocations excluded). Even then, platform-specific considerations might get in the way.
For artifacts that went through inter-procedural and especially link-time optimization, this breaks down. The former will take advantage of the fact that anything goes as long as the visible interface of an object file section is ABI compliant, the latter effectively turns an entire program into one big translation unit. Among other things, functions may exhibit non-standard calling conventions, which wreaks havoc as soon as you start trying to meld delinked bits with freshly built ones, because the optimizer is unlikely to make the same choices in its custom calling conventions.
I have a user who is decompiling a link-time optimized artifact built over 15 years ago. In order to graft newly compiled code, they binary patched the original compiler to basically add support for __usercall, in order to coerce the toolchain into making the same optimization decisions. If you're up against an artifact built with a non-traditional toolchain with optimizations on, delinking alone most likely won't cut it and additional magic will be required.
I guess the one catch with shared libraries is that if shared library A itself depends on another dylib B, then calls within A to functions of B would go via PLT indirection. So then creating an object file out of this would involve not just moving code and creating relocation entry but also possibly patching the assembly itself to remove the call indirection.
Shared libraries could be converted to static. You would lose the ability of static libraries to only include part of the library.
Windows in 16 and 32bit code defaults to non-PIC code and thus considerable work has been done to ensure system libraries do not overlap in addresses.
What happens when addresses overlap? When runtime linker detects conflicts (or just wants to load a non-PIC library/executable at different address), it utilizes "relocation data" that is shipped with the code which contains essentially information on "where are pointers and how to rewrite them when you move the code"
But yeah, one recurring problem is that without literature on this esoteric and complex topic, any discussion remotely technical about it (especially without prior context) quickly bogs down, as it needs to be bootstrapped from first principles in order to make any sense.
I've been meaning to write the Necronomicon of delinking to at least be able to point people to a document that contains everything they need to know in order to understand or at least decently grasp this. At the very least it should make for a good horror bed time story for linker developers.
https://people.scs.carleton.ca/~soma/pubs/bfoster-gecco-2010...
I’m definitely going to use this for solving some problems that i’m currently facing.
For anyone curious about what hare-brained scheme that one could hatch with this, i’d like the ability to do something like a PGO’d shared library —- watch the process run and exit, tracing all dlopen’s to create a new shared library with only the right functions from all the referenced libraries.
Hopefully this works, and if not, i’ll at least fail at something interesting :)
As for the reinvention part, I was referencing the wheel of video game decompilation specifically. By that point Super Mario 64 was already fully decompiled and several other projects were well underway. The established wheel was matching decompilation (either instruction or byte level) and the community was producing tooling for this sole purpose.
In a sense, I did reinvent the wheel of video game decompilation in stark contrast to everything else that was out there at the time. It just turned out horribly right, because before I knew it I was making chimeras executables made out of bits of programs coming from different platforms.
By platforms you mean different binary formats, right? Not CPUs (just making sure I'm not going crazy here :))
I don't have the tooling to meld together incompatible ABIs. I tried once with two really similar ABIs (MIPS PIC and non-PIC) and while I've managed to work around incompatibilities with assembly trampolines, the debugging experience was so poor that I rage quit. Never tried with different CPUs.
I'm crazy enough to think it ought to be possible (there's plenty of prior art for most of the needed pieces), but I'm already stuck inside a rabbit hole so deep I can't see the bottom... I'll let someone else investigate that.
I've fallen into this trap enough times to recognize it as a trap now. Good for you that it works for you, but in general, automation of loosely-defined problems just doesn't get 100% of cases right and once it works, you need to streamline the manual process instead.
Given the amount of information loss that occurs at the linking stage, delinking is an extremely intricate puzzle to solve. It's also very hard to be sure that you got it right, because there are many, many ways it can go wrong in ways that are a nightmare to troubleshoot. The scale of the endeavor can be also staggering: one user has over 250 000 relocation spots in their artifact, pretty much all of them must be spot-on otherwise glitches and crashes will occur.
The only way I've managed to pull it off is with an analyzer design that makes no assumptions, double-checks everything, logs anything that couldn't be successfully processed and heavily investing into regression testing. The manual process then consists of fixing inaccuracies within the Ghidra database, or (rarely nowadays) fix an unhandled corner case within the analyzer. Also, no manual annotations of relocations means they cannot go stale as the Ghidra database is modified.
I also happened to attempt this first on possibly the worst architecture possible, MIPS. I won't go into the details, but split HI16/LO16 relocations, register dependency graphs and branch delay slots can produce some absolutely gnarly cases to untangle. Let's just say that my MIPS analyzer contains among other things one recursive function that takes 6 parameters, 4 of them shifts one place to the left at each iteration. I'm not exactly sure how it works.
It does have the potential to simplify and improve the decompilation over directly decompiling a linked binary, as it more naturally reverses the process.
Also, my decompilation project's goal was a remaster in the spirit of REDRIVER2, with bugfixes, new features, quality of life improvements and a PC port. The end result would not have been matching or even functionally equivalent anyways.